我正在实现一个四叉树(它只是一个普通树，每个节点有四个子节点(数据结构，它保存关于移动线的数据。
当我在gdb中运行程序时，我在上收到一个错误malloc(): corrupted top sizequadtree_t *quadtree = malloc(sizeof(quadtree_t));。
我试图搜索那个错误，但我发现了一些与缓冲区溢出有关的错误(我认为情况并非如此(。
编辑：这是动态数组实现中的一个错误。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) {
// ensure that all children are valid trees.
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) {
// recurse into the subtree
quadtree_insert(quadtree->children[pos], l, step);
} else {
linesbucket_push(&quadtree->lines, l);
}
} else if (linesbucket_get_size(&quadtree->lines) < QUADTREE_MAX_LINES) {
// insert into the leaf
linesbucket_push(&quadtree->lines, l);
} else {
// devide and recurse
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.
# --- snip ---
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
# --- snip ---
(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);
错误出现在linesbucket_push()中，它使用了一个完全未经测试的通用动态数组。这意味着重新分配的内存少于所需内存(远低于所需内存(。
它正在使用darr->data = realloc(darr->data, darr->max_size);代替darr->data = realloc(darr->data, darr->max_size * darr->obj_size);
- 运行
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)
--- snip ---
此外，您可以使用-fsanitizer=address作为评论中提到的@Some programmer dude。