0

最終編集：これは、文字列関数にもmallocにも関連しないスタックオーバーフローの問題であることが判明しました。GDBの出力によると、問題はそれがあった場所の数行上にあり、混乱しましたが、Valgrindで実行するのに時間がかかるとすぐに、問題がわかりました。

非常に大きな有向グラフ（約600万ノード）内の最短経路を見つけるための双方向幅優先探索プログラムを作成しました。100ノードのテスト入力ファイルを使用すると、すべてがうまく機能します。入力がいっぱいになると、はるかに多くのメモリが使用され、プログラムにセグメンテーション違反が発生します。

GDBは、検索関数の開始時に結果バッファーをクリーンアップすると、segfaultingであると言いますn = sprintf(result, "");。関連する関数は次のとおりです。

char *bidirbfs(int x, int y, char *result){
    int n;
    n = sprintf(result, "");
    ...

これを呼び出して、resultバッファを割り当てます。

int main (){
    int n=0;
    char *result;
    result = (char *)malloc(sizeof(char)*2000);
    if(result == NULL){
        printf("MALLOC FAILED!"); exit(1);}

    //Methods for initializing graph
    readStructureFromFile(); 
    calcArticlesIn();

    //Search the graph
    result = bidirbfs(1,2, result);
    printf("%s\n", result);
    ...
}

繰り返しますが、小さな入力ですべてが機能します。フルサイズの入力を使用すると、プログラムはすべてを正常に読み取りますが、segfaultsを実行します。代わりにstrncpyの非常によく似た呼び出しを使用して配列を空にすると、同じ動作が発生するため、一般的な問題のようです。文字列関数を使用します。何が起こっているのかわかりません。

sprintfは取得しているポインターを気に入らないようです。そのため、mallocが何か奇妙なことをしているのではないかと思います。完全な入力を使用すると、mallocは1300万回*呼び出されるので、これが原因で奇妙な動作を示し、文字列バッファーを奇妙なもので上書きしているのではないかと思います。同時に、私は図書館のせいにすることを非常に躊躇しています。

何が起こっているのか考えてみませんか？

*残念ながら、これは実際に必要だと思います。グラフの各要素には、インバウンドエッジとアウトバウンドエッジの配列があります。各配列のサイズは、入力が読み取られるまで不明であるため、mallocによって正しいサイズに動的に割り当てられる必要があります。

編集：Valgrindは以下を返しました。私はそれが何を意味するのかを理解するために取り組んでいますが、一見すると、実際にはある種のスタックオーバーフローである可能性があります。

==27263== Warning: client switching stacks?  SP change: 0xbea50634 --> 0xbb815340
==27263==          to suppress, use: --max-stackframe=52671220 or greater
==27263== Invalid write of size 4
==27263==    at 0x8048D78: bidirbfs (load_data.c:184)
==27263==    by 0x80491CD: main (load_data.c:304)
==27263==  Address 0xbb815348 is on thread 1's stack
==27263== 
==27263== 
==27263== Process terminating with default action of signal 11 (SIGSEGV)
==27263==  Access not within mapped region at address 0xBB815348
==27263==    at 0x8048D78: bidirbfs (load_data.c:184)
==27263==  If you believe this happened as a result of a stack
==27263==  overflow in your program's main thread (unlikely but
==27263==  possible), you can try to increase the size of the
==27263==  main thread stack using the --main-stacksize= flag.
==27263==  The main thread stack size used in this run was 8388608.
==27263== 
==27263== Process terminating with default action of signal 11 (SIGSEGV)
==27263==  Access not within mapped region at address 0xBB81533C
==27263==    at 0x401F4DD: _vgnU_freeres (vg_preloaded.c:58)
==27263==  If you believe this happened as a result of a stack
==27263==  overflow in your program's main thread (unlikely but
==27263==  possible), you can try to increase the size of the
==27263==  main thread stack using the --main-stacksize= flag.
==27263==  The main thread stack size used in this run was 8388608.
==27263== 
==27263== HEAP SUMMARY:
==27263==     in use at exit: 1,021,539,288 bytes in 13,167,791 blocks
==27263==   total heap usage: 13,167,792 allocs, 1 frees, 1,047,874,864 bytes allocated
==27263== 
==27263== LEAK SUMMARY:
==27263==    definitely lost: 0 bytes in 0 blocks
==27263==    indirectly lost: 0 bytes in 0 blocks
==27263==      possibly lost: 0 bytes in 0 blocks
==27263==    still reachable: 1,021,539,288 bytes in 13,167,791 blocks
==27263==         suppressed: 0 bytes in 0 blocks
==27263== Rerun with --leak-check=full to see details of leaked memory
==27263== 
==27263== For counts of detected and suppressed errors, rerun with: -v
==27263== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 12 from 7)

編集2：最終的な解決策：それはスタックオーバーフローでした。sprintfステートメントの直後に、ノードの数に比例するサイズの配列を作成しました。私はmallocを使用していなかったので、これはスタック上に直接作成され、オーバーフローしました。mallocを使用するように変更すると問題が解決し、すべてが期待どおりに実行されるようになりました。提案してくれたみんなに感謝します！

4

2 に答える 2

1

この時点では推測ですが、次の簡単な変更を試してください。

result変数に何かを書き込む場所では、を使用してみてください

n = snprintf(result, 2000, "...", ...);

ここで...は、実際に文字列に書き込みたいものを表しresultます。

の割り当ての終わりを超えて書き込むresultと、影響は予測できなくなります。

于 2012-04-14T23:32:13.410 に答える
1

valgrindでプログラムを実行します。それが何を言っているか見てください。私はあなたが出力を啓発するのを見つけるでしょう。

于 2012-04-14T23:51:15.980 に答える