Valgrind：大小 4 -> sigsegv 的读取无效，无需 valgrind 且在 Visual Studio 中也能正常工作

Question

我已经实现了一种压缩算法（使用霍夫曼编码），该算法使用节点的优先级队列（我定义的结构）。现在，当我在 Linux 或 Visual Studio 中运行代码时，一切正常。当我在 Visual Studio 中检查内存泄漏时，没有给出任何内存泄漏。

现在的问题是，当我使用 valgrind 分析我的程序时，它以信号 11 (sigsegv) 终止。 遇到的第一个错误是方法delete min 中的“无效读取大小4”。此后的其他错误有：释放的大小为 453 的块内的地址为 0 字节、大小为 4 的写入无效、释放、删除或重新分配无效。

任何人都可以给我关于我可能犯下什么样的错误的建议吗？我已经在互联网上搜索了几个小时，但找不到我做错了什么（特别是因为它在不使用 valgrind 时才有效）。或者提示如何调试并找出导致读取错误的原因。

非常感谢！

这里是代码，以防有人想查看它，但我想仅仅深入研究这个特定代码并不那么容易。

我猜这与代码的优先级队列有关：

我执行霍夫曼部分的部分 -> 每次删除 2 个最小节点并将两者的总和添加回作为一个节点。

while(queue->size > 1){
    node* n1 = delete_min(queue);
    node* n2 = delete_min(queue); // all the errors are encountered in this call
    node* temp = (node*) calloc(sizeof(node),1);
    temp->amount = n1->amount + n2->amount;
    insert_node(queue,temp);
    n1->parent = temp;
    n2->parent = temp;
    temp->left = n1;
    temp->right = n2;
}

这里是优先级队列的delete_min和insert_node方法：

void insert_node(priority_queue* p_queue, node* x){
    int i = p_queue->size;
    if(i == 0){
        p_queue->queue = (node**) malloc(sizeof(node*));
    }
    else{
        p_queue->queue = (node**) realloc(p_queue->queue,sizeof(node*)*(p_queue->size+1));
    }
    p_queue->queue[p_queue->size] = x;

    while(i>=0 && p_queue->queue[i]->amount < p_queue->queue[(i-1)/2]->amount){
        node* temp = p_queue->queue[i];
        p_queue->queue[i] = p_queue->queue[(i-1)/2];
        p_queue->queue[(i-1)/2] = temp;
        i = (i-1)/2;
    }
    p_queue->size++;
}

node* delete_min(priority_queue* p_queue){
    node** queue = p_queue->queue;
    node* min = queue[0];

    if(p_queue->size>1){
        int r = 0;
        int current = 1; //left child of root

        queue[0] = queue[p_queue->size-1];
        queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->size));
        while(current < p_queue->size){
            //in case of 2 children, check if current needs to be right or left child
            if(current < p_queue->size-1 && queue[current] > queue[current+1]){
                current++;
            } 
            if(queue[current] < queue[r]){
                node* temp = queue[r];
                queue[r] = queue[current];
                queue[current] = temp;

                r = current;
                current = 2 * current;
            }
            else{
                break;
            }
            current++;
        }
    }
    else{
        free(queue);
        p_queue->size--;
    }
    return min;
}

编辑：添加了 valgrind 输出：

Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049901: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441db64 is 444 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid write of size 4
==1893==    at 0x8049906: delete_min (huffman.c:333)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid free() / delete / delete[] / realloc()
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893== 
==1893== Invalid read of size 4
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==1893== 
==1893== 
==1893== Process terminating with default action of signal 11 (SIGSEGV)
==1893==  Access not within mapped region at address 0x0
==1893==    at 0x8049A0E: delete_min (huffman.c:337)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

第331行是delete_min中的行：node* min =queue[0];

编辑：

问题现在已经解决了。在接受的答案中，解释了原因。只需正确分配重新分配的值，在delete_min中就解决了所有问题。

//realloc queue and assign new value to local queue var
p_queue->queue = (node**) realloc(queue,sizeof(node*)*(--p_queue->grootte));
queue = p_queue->queue;

Answer 1

我会向你解释第一个错误。

==1893== Invalid read of size 4
==1893==    at 0x80498E0: delete_min (huffman.c:331)
==1893==    by 0x80492DA: huffman_encode (huffman.c:196)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)

在第 331 行，您可能正在读取一个 unsigned int，该内存位于您尚未为程序分配的内存中。

==1893==  Address 0x441d9a8 is 0 bytes inside a block of size 452 free'd
==1893==    at 0x402BC70: realloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==1893==    by 0x8049922: delete_min (huffman.c:335)
==1893==    by 0x80492CC: huffman_encode (huffman.c:195)
==1893==    by 0x8049DDE: encode_file (main.c:94)
==1893==    by 0x8049BBE: main (main.c:32)
==1893==

这部分提供了有关您尝试读取的内存部分的更多信息。它表示您已经使用了该内存，但是

realloc

释放了它。这意味着您正在从旧指针读取已重新分配的内存部分。

您应该确保使用指针

realloc

返回，而不是旧的。

在 Valgrind 之外运行时不会崩溃的原因是，大多数时候，同一部分内存将由

realloc

分配。因此指针保持不变，因此您的代码将起作用。然而，有时，

realloc

会决定移动部分内存，然后你的代码就会崩溃。 Valgrind 试图就此警告您。

当您使用返回的指针时，其余的错误可能会得到解决。

Answer 2

根据您的 Valgrind 错误，您可能正在访问然后释放已删除的节点。 您应该考虑发布带有相应行号的 Valgrind 错误（在 gcc 中使用 -g 编译），以便我们更轻松地为您提供帮助。

编辑：最明显的错误，即段错误，是您应该开始调试的地方。 此行失败：

while((2*i)+2 < p_queue->grootte-1 && (queue[i]->amount > queue[(2*i)+1]->amount || queue[i]->amount > queue[(2*i)+2]->amount)){

大概是因为

queue

为 NULL。 为什么它是NULL？ 可能是因为 realloc 没有分配任何东西。 为什么没有分配任何东西？ 要么是因为您耗尽了内存（不太可能），要么是因为您尝试分配大小为 0 的内容。（有关 realloc 的详细信息，请参阅 http://www.cplusplus.com/reference/cstdlib/realloc/ ）。 你怎么能要求0号呢？ 如果

p_queue->size-1

为 0.