what exactly causes `malloc()` to fail with `malloc(): corrupted top size`-CodePudding

I am implementing a quadtree (it is just a normal tree with each node having four children) data structure that holds data about moving lines.

When I run the program in gdb I get an error malloc(): corrupted top size on quadtree_t *quadtree = malloc(sizeof(quadtree_t));.

I tried to search for that error, but what I found were some bugs related to buffer overflow (which is not the case I think).

Edit: It turned out to be a bug in the dynamic array implementation. Which was detected by 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)

This is a snippet from the code I am using.

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);
}

And this is gdb's output

(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);

CodePudding user response：

The bug was in linesbucket_push() which is using a completely untested generic dynamic-array. Which was reallocating memory less than required (much less than required).

It was using darr->data = realloc(darr->data, darr->max_size); instead of darr->data = realloc(darr->data, darr->max_size * darr->obj_size);

Running valgrind immediately caught this.

==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 ---

Also, you could use -fsanitizer=address as @Some programmer dude mentioned in the comments.