1. ホーム
  2. c

[解決済み] Valgrind: サイズ4の無効な読み取り -> sigsegv、valgrindなしとビジュアルスタジオでは問題なく動作する

2022-03-04 19:54:38

質問

私は、ノード(私が定義した構造体)の優先キューを使用する圧縮アルゴリズム(ハフマンコーディングを使用)を実装しています。現在、私はLinuxまたはビジュアルスタジオでコードを実行すると、すべてがうまく動作します。ビジュアルスタジオでメモリリークをチェックすると、何も表示されません。

問題は、valgrindを使って私のプログラムを解析すると、シグナル11(sigsegv)で終了してしまうことです。 最初に遭遇したエラーは、メソッドdelete minの'invalid read of size 4'です。そのあとの他のエラーは Adress is 0 bytes inside a block of size 453 freed, invalid write of size 4, invalid free,delete or realloc.です。

どなたか、どのようなエラーが考えられるか、アドバイスをお願いします。何時間もインターネットを検索していますが、何が間違っているのか見つかりません(特に、valgrindを使用していないときは、ただ動作しているので)。また、デバッグの方法、読み込みエラーの原因を見つけるためのヒントも。

ありがとうございます。

誰かがレビューしたい場合に備えて、ここにコードがありますが、私はそれがこの特定のコードに飛び込むだけではそれほど簡単ではないと思います。

コードの優先順位キューと関係があるんでしょうね。

ハフマン部分 -> を行っている部分は、毎回2つの最小ノードを削除し、両方の合計を1つのノードとして足し戻しています。

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

EDIT: 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]の行です。

EDITです。

これで問題は解決です。受理された回答で、その理由が説明されています。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;

解決方法は?

最初のエラーについて説明します。

==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行目では、おそらく自分のプログラム用に割り当てられていないメモリの一部で、(符号なし)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==

この部分は、読み込もうとしたメモリの部分についての詳細な情報を提供します。これは、あなたがすでにそのメモリを使用していて、reallox がそれを解放したと言っています。つまり、再起したメモリの一部への古いポインタから読み取ろうとしているのです。

reallocが返すポインタは古いものではなく、必ず使うようにする必要があります。

valgrind の外で実行してもクラッシュしないのは、ほとんどの場合、同じ部分のメモリが realloc によって確保されるからです。つまり、ポインターは同じままなので、あなたのコードは動作するのです。しかし、時々、realloc がメモリの一部を移動することになり、コードがクラッシュすることがあります。Valgrind はこのために警告を出そうとしているのです。

残りのエラーは、おそらく返されたポインタを使用しているときに解決されるでしょう。