C - glibc检测到realloc():无效下一个大小:0x

Question

这段代码使用realloc()实现了一个可扩展队列，这只是原始代码的一部分。

当我运行这个得到一个错误:

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

错误是:

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

Answer 1

问题是在您减量queue->memory_allocated的dequeue中。发生的事情是这样的:您创建了一个empty_queue。你开始向数组中添加元素——这会使数组的大小增加16。我们一直输入元素，直到第16次，然后将大小增加到32。然后用完前20个。

此时内存中的数组用于前20个，然后在最后12个中未使用。然后我们开始调用dequeue并删除10个条目。Size现在等于10,memory_allocated/u32等于22。您开始添加更多元素，并添加12个元素(在20到32之间的12个空闲空间中)，此时size == memory_allocated/u32，因此我们将memory_allocated增加16。分配的内存现在等于38。

内存中的数组看起来是这样的:

开始添加更多元素，在第6个元素中，将放在数组末尾的后面。现在发生的任何事都是公平的。你的记忆被破坏了，很明显你最终会把一些重要的东西写掉。

Answer 2

Dave是对的，但是我真的认为您需要重新考虑这段代码。在您添加20个值，然后减去10个值之后，您将得到如下所示的内存(不可缩放):

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

所以'Size'是10,memory_allocated真的很奇怪，因为你先增加16*sizeof(u32)，然后在increment_queue()中增加16，这被认为是一个bug。

但最重要的是，然后你调用realloc()与queue->数组作为指针…如果你真的想把队列的大小调整到10个元素，你实际上要做的是把缓冲区从0开始截断到10个元素。丢弃队列中有效部分(10到20之间)的所有值。

如果这个例子没有帮助…想想当您添加20个元素，然后取出20个元素时会发生什么。FirstElem和LastElem = 20, size = 0，第一个和最后一个永远不会重置。如果您继续添加16个元素，您将在queue->array上调用realloc，其大小为16，但是您添加的新16个元素都不会在重新分配的缓冲区中。Realloc可能会从queue->array截断为queue->array+16*sizeof(u32)..但是您的元素将处于queue->array+20，并且现在处于未分配的内存中。

我认为你需要重新考虑你的整个算法。或者，如果您只是在unix系统上寻找一个简单的队列实现，请查看'man queue'(或查看/usr/include/sys/queue.h)。