6

これは、CでのCooley-Tukeyアルゴリズムの実装の抜粋です。そうです、大学の宿題です。しかしとにかく...アルゴリズムは正常に機能しますが、巨大な入力データの膨大なメモリリークを取り除くために、ar1とar2を解放する必要がありますが、試行するたびに無効な読み取りが発生します。理論的には、ar1とar2は関数の現在のインスタンスによってのみ使用されるべきであり、すべてのインスタンスが独自の出力をmallocするため、これらは一意である必要があります。

complex_exp * dft(complex_exp * from, int N, int s, int inverse) {

if(N == 1)
    return from;

int i;
complex_exp * transformed = (complex_exp *) malloc(N * sizeof(complex_exp));
complex_exp * ar1 = dft(from, N / 2, 2*s, inverse); //LINE 83
complex_exp * ar2 = dft(from + s, N / 2, 2*s, inverse); // LINE 84

for(i = 0; i < N/2; i++) {

    transformed[i] = ar1[i]; //LINE 88
}

for(i = N/2; i < N; i++) {
    transformed[i] = ar2[i - N/2];
}

//Do stuff with the transformed array - NO reference to ar1 or ar2.

free(ar1); //LINE 113
return transformed;
}

Valgrindは言う:

==69597== Invalid read of size 8
==69597==    at 0x100000EE6: dft (progtest05.c:88)
==69597==    by 0x100000EA2: dft (progtest05.c:84)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100001A0E: main (progtest05.c:233)
==69597==  Address 0x100007250 is 64 bytes inside a block of size 256 free'd
==69597==    at 0xDCB8: free (vg_replace_malloc.c:450)
==69597==    by 0x1000011E5: dft (progtest05.c:113)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100000E67: dft (progtest05.c:83)
==69597==    by 0x100001A0E: main (progtest05.c:233)

したがって、83行目のdftを呼び出すとメモリが解放され、次の行のdftを呼び出すとアクセスが試みられるようです。実際に何が起こっているのか、そしてどうすればリークを取り除くことができるのか、何か考えはありますか?

4

2 に答える 2

8

「すべてのインスタンスが独自の出力を malloc する」と言いますが、このステートメントではそうではありません。

if(N == 1)
    return from;

おそらく、N==1 の場合は、のコピーを返す必要がありますfrom(つまり、新しいメモリを malloc し、の内容を新しいメモリにコピーし、そのコピーを返します)。

どうすれば漏れを取り除くことができますか?

変換して返す前に、ar1 と ar2 を解放する必要があると思います。

于 2012-11-11T09:43:56.880 に答える
1

これらの問題を修正する最善の方法は、前提条件と事後条件を明確に定義することです。返された結果が malloc されていると思いますか? もしそうなら、あなたは "from" を返し、"ar2" を解放しないことでこれに違反しているように見えます。返された結果が malloc されていないと想定する場合は、このメモリが呼び出し元によって提供されていることを確認し、malloc されたメモリを返さないようにする必要があります。

于 2012-11-11T09:42:27.077 に答える