Why do I get a C malloc assertion failure?

Question

I am implementing a divide and conquer polynomial algorithm so I can benchmark it against an OpenCL implementation, but I can't get malloc to work. When I run the program, it allocates a bunch of stuff, checks some things, then sends the size/2 to the algorithm. Then when I hit the malloc line again it spits out this:

malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
Aborted

The line in question is:

int *mult(int size, int *a, int *b) {
    int *out,i, j, *tmp1, *tmp2, *tmp3, *tmpa1, *tmpa2, *tmpb1, *tmpb2,d, *res1, *res2;
    fprintf(stdout, "size: %d\n", size);

    out = (int *)malloc(sizeof(int) * size * 2);
}

I checked size with a fprintf, and it is a positive integer (usually 50 at that point). I tried calling malloc with a plain number as well and I still get the error. I'm just stumped at what's going on, and nothing from Google I have found so far is helpful.

Any ideas what's going on? I'm trying to figure out how to compile a newer GCC in case it's a compiler error, but I really doubt it.

Answer 1

99.9% likely that you have corrupted memory (over- or under-flowed a buffer, wrote to a pointer after it was freed, called free twice on the same pointer, etc.)

Run your code under Valgrind to see where your program did something incorrect.

Answer 2

To give you a better understanding of why this happens, I'd like to expand upon @r-samuel-klatchko's answer a bit.

When you call malloc, what is really happening is a bit more complicated than just giving you a chunk of memory to play with. Under the hood, malloc also keeps some housekeeping information about the memory it has given you (most importantly, its size), so that when you call free, it knows things like how much memory to free. This information is commonly kept right before the memory location returned to you by malloc. More exhaustive information can be found on the internet™, but the (very) basic idea is something like this:

+------+-------------------------------------------------+
+ size |                  malloc'd memory                +
+------+-------------------------------------------------+
       ^-- location in pointer returned by malloc

Building on this (and simplifying things greatly), when you call malloc, it needs to get a pointer to the next part of memory that is available. One very simple way of doing this is to look at the previous bit of memory it gave away, and move size bytes further down (or up) in memory. With this implementation, you end up with your memory looking something like this after allocating p1, p2 and p3:

+------+----------------+------+--------------------+------+----------+
+ size |                | size |                    | size |          +
+------+----------------+------+--------------------+------+----------+
       ^- p1                   ^- p2                       ^- p3

So, what is causing your error?

Well, imagine that your code erroneously writes past the amount of memory you've allocated (either because you allocated less than you needed as was your problem or because you're using the wrong boundary conditions somewhere in your code). Say your code writes so much data to p2 that it starts overwriting what is in p3's size field. When you now next call malloc, it will look at the last memory location it returned, look at its size field, move to p3 + size and then start allocating memory from there. Since your code has overwritten size, however, this memory location is no longer after the previously allocated memory.

Needless to say, this can wreck havoc! The implementors of malloc have therefore put in a number of "assertions", or checks, that try to do a bunch of sanity checking to catch this (and other issues) if they are about to happen. In your particular case, these assertions are violated, and thus malloc aborts, telling you that your code was about to do something it really shouldn't be doing.

As previously stated, this is a gross oversimplification, but it is sufficient to illustrate the point. The glibc implementation of malloc is more than 5k lines, and there have been substantial amounts of research into how to build good dynamic memory allocation mechanisms, so covering it all in a SO answer is not possible. Hopefully this has given you a bit of a view of what is really causing the problem though!