glibc detected realloc(): invalid next size: 0x [duplicate]

Question

This question already has answers here:

Facing an error "*** glibc detected *** free(): invalid next size (fast)" (2 answers)

Closed 8 years ago.

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.

Answer 2

Dave is correct, but I really think you want to re-think this code. After you add 20 values, and then subtract 10, you get memory that looks like this (not to scale):

queue->array             beginning of queue         end of queue          end of buffer
|  |  |   |   |   |   |  |  |   |  |   |   |   |   |   |   |   |   |   |   | |   |   | 
0                        10                           20                   32             

So 'Size' is 10, memory_allocated is really bizarre because you increment it first by 16*sizeof(u32), and then by just plain 16 in increment_queue(), which is think is a bug)..

But most importantly, then you call realloc() with queue->array as the pointer... if you're really trying to resize the queue to 10 elements at that point, what you'll actually do is truncate the buffer to 10 elements starting at 0.. throwing away all the values in the valid part of the queue (between 10 and 20).

If this example doesn't help.. think about what happens when you add 20 elements, and then dequeue 20 elements. FirstElem and LastElem = 20, size = 0, first and last never get reset.. if you go on to add 16 more elements, you'll call realloc on queue->array with size 16, but none of the new 16 elements you added will be in the reallocated buffer. realloc will likely truncate from the queue->array to queue->array+16*sizeof(u32).. but your elements will be at queue->array+20, and now in unallocated memory.

I think you need to rethink your whole algorithm. Or if you're just looking for a simple queue implementation on a unix system, look at 'man queue' (or look in /usr/include/sys/queue.h).