glibc detected realloc(): invalid next size: 0x

Question

This code implement an extensible queue using realloc(), this is only a part of the original code.

When I run this get an error:

typedef uint32_t u32;
typedef uint64_t u64;

typedef struct _queue_t *queue_t;

struct _queue_t {
    u32 *array;
    u32 FirstElem;
    u32 LastElem;
    u32 memory_allocated;
    u32 Size;
};

queue_t queue_empty() {
    queue_t queue = calloc (1, sizeof (struct _queue_t));

    assert(queue != NULL);

    queue->array = (u32 *) calloc(16, sizeof(u32));
    queue->FirstElem = 0;
    queue->LastElem = 0;
    queue->memory_allocated = 16*sizeof(u32);
    queue->Size = 0;

    return queue;
}

void increment_queue(queue_t queue) {

    queue->memory_allocated += 16;
    queue->array = realloc (queue->array, queue->memory_allocated);
    assert(queue->array != NULL);
}

queue_t enqueue(queue_t queue, u32 vertex) {

    assert(queue != NULL);
    assert(queue->array != NULL);

    if ((queue->memory_allocated)/sizeof(u32) == queue->Size) {
        increment_queue(queue);
    }

    if (queue->Size == 0) {
    queue->array[queue->LastElem] = vertex;
    } else {
        queue->LastElem += 1;
        queue->array[queue->LastElem] = vertex;
    }

    queue->Size = queue->Size + 1;

    return queue;
}

queue_t dequeue(queue_t queue) {

    assert (queue != NULL);
    assert (queue_size(queue) != 0);

    queue->FirstElem += 1;
    queue->Size -= 1;
    queue->memory_allocated -= sizeof(u32);

    return queue;
}

int main() {
    queue_t newq = queue_empty();

    for (u32 i = 0; i < 20; i++) {
        enqueue(newq, i);
    }
    for (u32 i = 0; i < 10; i++) {
        dequeue(newq);
    }
    for (u32 i = 0; i < 100; i++) {
        enqueue(newq, i);
    }

    return 0;
}

The error is:

* glibc detected ./mini: realloc(): invalid next size: 0x0000000001782030 **
======= Backtrace: ========= ............................

Answer 1

The problem is in dequeue where you decrement queue->memory_allocated. What is happening is this: you create an empty_queue. You start adding elements to the array - this increases the size by 16. We keep entering elements until the 16th time and then we increase the size to 32. And finish using the first 20 of these.

The array in memory at this time is used for the first twenty and then unused for the last 12. Then we start calling dequeue and remove 10 items. Size is now equal to 10 and memory_allocated/u32 is equal to 22. You start adding more elements and add 12 more elements (in the 12 free spaces that we had between number 20 and 32) at which point size == memory_allocated/u32 so we increment the memory_allocated by 16. Memory allocated is now equal to 38.

The array in memory looks like this though: Size is 22.

We start adding more elements and on the 6th one of these we write past the end of the array. Anything that happens now is fair game. You have corrupted memory and obviously write over something of importance eventually.