实现四叉树时malloc()出现malloc(): corrupted top size错误的原因

问题背景 #

我正在实现一个存储移动线段数据的四叉树（每个节点包含四个子节点）。运行程序时，执行quadtree_t *quadtree = malloc(sizeof(quadtree_t));语句触发malloc(): corrupted top size错误。最初以为不是缓冲区溢出问题，后来用Valgrind检测发现动态数组实现存在Bug。

Valgrind错误日志 #

==10704== Invalid write of size 8
==10704==    at 0x4850210: memmove (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10704==    by 0x109547: dynamic_array_push (dynamic-arrays.c:52)
==10704==    by 0x10B87C: linesbucket_push (linesbucket.c:33)
==10704==    by 0x10CC6E: quadtree_insert (quadtree.c:172)
==10704==    by 0x10CC58: quadtree_insert (quadtree.c:170)
==10704==    by 0x10CC58: quadtree_insert (quadtree.c:170)

相关代码片段 #

象限枚举定义 #

typedef enum {
  NORTHEAST = 0,
  NORTHWEST = 1,
  SOUTHEAST = 2,
  SOUTHWEST = 3,
  ROOT = 4,
} quarter_t;

四叉树结构体与创建函数 #

typedef struct quadtree quadtree_t;
struct quadtree {
  Vec min_dim;
  Vec max_dim;
  linesbucket_t lines;
  quadtree_t *children[4];
  size_t treesize;
  bool split;
};

quadtree_t *quadtree_new(Vec min_dim, Vec max_dim) {
  quadtree_t *quadtree = malloc(sizeof(quadtree_t));
  if (quadtree == NULL) {
    return NULL;
  }
  quadtree->min_dim = min_dim;
  quadtree->max_dim = max_dim;
  quadtree->lines = linesbucket_new(QUADTREE_MAX_LINES);
  quadtree->treesize = 0;
  quadtree->split = false;
  for (size_t i = 0; i < 4; i++) {
    quadtree->children[i] = NULL;
  }
  return quadtree;
}

四叉树插入函数 #

void quadtree_insert(quadtree_t *restrict quadtree, const Line *restrict l, timestep_t step) {
  assert(quadtree);

  quadtree->treesize += 1;
  if (quadtree->split) {

    // 确保所有子节点都是有效的树
    for (size_t i = 0; i < 4; i++) {
      assert(quadtree->children[i]);
    }

    quarter_t pos = quadtree_get_moving_line_pos(quadtree, l, step);
    if (pos != ROOT) {
      // 递归插入子树
      quadtree_insert(quadtree->children[pos], l, step);
    } else {
      linesbucket_push(&quadtree->lines, l);
    }

  } else if (linesbucket_get_size(&quadtree->lines) < QUADTREE_MAX_LINES) {
    // 插入到叶子节点
    linesbucket_push(&quadtree->lines, l);
  } else {
    // 分裂并递归处理
    quadtree->split = true;

    quadtree_allocate_subtrees(quadtree);

    const Line *lines = linesbucket_get_data(&quadtree->lines);

    linesbucket_t newlines = linesbucket_new(8);
    for (size_t i = 0; i < linesbucket_get_size(&quadtree->lines); i++) {
      quarter_t pos = quadtree_get_moving_line_pos(quadtree, &lines[i], step);
      if (pos != ROOT) {
        quadtree_insert(quadtree->children[pos], &lines[i], step);
      } else {
        linesbucket_push(&newlines, &lines[i]);
      }
    }

    quarter_t pos = quadtree_get_moving_line_pos(quadtree, l, step);
    if (pos != ROOT) {
      quadtree_insert(quadtree->children[pos], l, step);
    } else {
      linesbucket_push(&newlines, l);
    }
    linesbucket_free(&quadtree->lines);
    quadtree->lines = newlines;
  }
}

子树分配函数 #

static void quadtree_allocate_subtrees(quadtree_t *const quadtree) {
  vec_dimension south_min = quadtree->min_dim.y;
  vec_dimension west_min = quadtree->min_dim.x;
  vec_dimension north_min = (quadtree->min_dim.y + quadtree->max_dim.y) / 2;
  vec_dimension east_min = (quadtree->min_dim.x + quadtree->max_dim.x) / 2;
  vec_dimension east_max = quadtree->max_dim.x;
  vec_dimension north_max = quadtree->max_dim.y;

  Vec southwest_min = {.x = west_min, .y = south_min};
  Vec southwest_max = {.x = east_min, .y = north_min};
  quadtree->children[SOUTHWEST] = quadtree_new(southwest_min, southwest_max);

  Vec southeast_min = {.x = east_min, .y = south_min};
  Vec southeast_max = {.x = east_max, .y = north_min};
  quadtree->children[SOUTHEAST] = quadtree_new(southeast_min, southeast_max);

  Vec northeast_min = {.x = east_min, .y = north_min};
  Vec northeast_max = {.x = east_max, .y = north_max};
  quadtree->children[NORTHEAST] = quadtree_new(northeast_min, northeast_max);

  Vec northwest_min = {.x = east_min, .y = north_min};
  Vec northwest_max = {.x = east_max, .y = north_max};
  quadtree->children[NORTHWEST] = quadtree_new(northwest_min, northwest_max);
}

GDB调试输出 #

(gdb) break malloc_printerr
Breakpoint 1 at 0x7ffff7beb210: file malloc.c, line 5658.
# --- 省略部分输出 ---
Breakpoint 1, malloc_printerr (str=str@entry=0x7ffff7cf2140 "malloc(): corrupted top size") at malloc.c:5658
(gdb) bt
#0  malloc_printerr (str=str@entry=0x7ffff7cf2140 "malloc(): corrupted top size") at malloc.c:5658
#1  0x00007ffff7bee9fc in _int_malloc (av=av@entry=0x7ffff7d31ba0 <main_arena>, bytes=<optimized out>) at malloc.c:4369
#2  0x00007ffff7bef582 in __GI___libc_malloc (bytes=<optimized out>) at malloc.c:3315
#3  0x0000555555558a53 in quadtree_new (min_dim=..., max_dim=...) at src/quadtree.c:113
#4  0x0000555555558f3c in quadtree_allocate_subtrees (quadtree=0x555555574430) at src/quadtree.c:138
#5  0x0000555555558cb2 in quadtree_insert (quadtree=0x555555574430, l=0x555555562910, step=0.5) at src/quadtree.c:183
#6  0x0000555555558c59 in quadtree_insert (quadtree=0x5555555718a0, l=0x555555562910, step=0.5) at src/quadtree.c:171
#7  0x0000555555558c59 in quadtree_insert (quadtree=0x555555560140, l=0x555555562910, step=0.5) at src/quadtree.c:171
#8  0x0000555555558c59 in quadtree_insert (quadtree=0x55555555f940, l=0x555555562910, step=0.5) at src/quadtree.c:171
# --- 省略部分输出 ---
(gdb) up 3
#3  0x0000555555558a53 in quadtree_new (min_dim=..., max_dim=...) at src/quadtree.c:113
113   quadtree_t *quadtree = malloc(sizeof(quadtree_t)); 
(gdb) print sizeof(quadtree_t)
$1 = 112
(gdb) up
#4  0x0000555555558f3c in quadtree_allocate_subtrees (quadtree=0x555555571540)
    at src/quadtree.c:138
138       quadtree->children[SOUTHWEST] = quadtree_new(southwest_min, southwest_max);

内容的提问来源于stack exchange，提问作者Mostafa Khaled