5

Linux 2.6カーネルを搭載したDebianを使用しており、ヒープがとでどのように機能/動作するかを理解しようとしていmalloc()ますfree()。malloc()アルゴリズムとヒープ構造を検索しようとしましたfree()が、役立つものが見つかりませんでした。そして残念ながら、私はLinuxとメモリのしくみについてあまり知らず、とのソースコードを理解できませfree()んmalloc()。

これはサンプルコードです：

int main(int argc, char **argv)
{
    char *a, *b, *c;

    a = malloc(32);
    b = malloc(32);
    c = malloc(32);

    strcpy(a, argv[1]);
    strcpy(b, argv[2]);
    strcpy(c, argv[3]);

    free(c);
    free(b);
    free(a);
}

でgdb、run AAAA BBBB CCCCヒープを調べることができます。これは、：の後のstrcpys前の状態です。frees

(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x41414141  0x00000000
0x804c010:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c020:  0x00000000  0x00000000  0x00000000  0x00000029
0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89

char配列が非常によくわかります。次に、なぜ0x29（dec 41）があるのか​​を理解しようとしました。0x20（dec 32）または0x24（dec 36）のようなものを期待します。

  • なぜmallocアルゴリズムはこのスペースを浪費するのですか？
  • 0x29であるとどのように判断されますか？
  • そして最後の0xf89は何を表していますか？
  • プログラムは、割り当てられたものと無料のものをどのように追跡しますか？

特に、どのように機能するのかを理解したいと思いfree()ます。3回の解放後、ヒープは次のようになります。

(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x0804c028  0x00000000
0x804c010:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c020:  0x00000000  0x00000000  0x00000000  0x00000029
0x804c030:  0x0804c050  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x00000000  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
  • char配列がこの特定のアドレスに置き換えられるのはなぜですか？
  • freeが行う疑似コードとは何ですか？

この例を見てください：

(gdb) run AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADDDDD BBBB CCCC
...
(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x41414141  0x41414141
0x804c010:  0x41414141  0x41414141  0x41414141  0x41414141
0x804c020:  0x41414141  0x41414141  0x44444444  0x00000044
0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
...
(gdb) c
Program exited with code 021.

0x29を上書きしましたが、プログラムは正常に終了します。しかし、別のバイトを追加すると、セグメンテーション違反が発生します。

(gdb) run AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADDDDD BBBB CCCC
...
(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x41414141  0x41414141
0x804c010:  0x41414141  0x41414141  0x41414141  0x41414141
0x804c020:  0x41414141  0x41414141  0x44444444  0x00004444
0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
...
(gdb) c
Program received signal SIGSEGV, Segmentation fault.
0x080498b9 in free (mem=0x804c030) at common/malloc.c:3631

私にとって最も重要な質問は次のとおりです。

  • free()より多くのバイトを上書きすると、なぜセグメンテーション違反が発生するのですか？
  • free()アルゴリズムはどのように機能しますか？
  • そして、mallocとfreeはどのようにアドレスを追跡しますか？

読んでいただきありがとうございます、よろしくお願いします

4

3 に答える 3

9

ほとんどのmalloc()実装は、メモリの割り当てられたブロックの直前および/または直後に、ヒープ自体内のヒープのステータスを追跡することによって機能します。割り当てられたブロックをオーバーランすると、このデータが破損します。このデータの一部にはポインターまたは長さが含まれている可能性があり、それらが破損すると、実装が無効なメモリ位置にアクセスしようとします。

実装がどのように機能するかの詳細は、malloc()使用しているシステムと libc によって異なります。glibc を使用している場合 (おそらく Linux を使用している場合)、それがどのように機能するかについてのかなり良い説明があります:

http://gee.cs.oswego.edu/dl/html/malloc.html

これが事実であると仮定すると、0x29あなたが見ているのはおそらくブロックサイズ (32 = 0x20) といくつかのフラグのビットごとの OR です。これが可能なのは、すべてのヒープ割り当てが最も近い 16 バイト (またはそれ以上) に丸められるためです。そのため、サイズの下位 8 ビットは常にゼロであると見なすことができます。

于 2012-05-10T19:36:04.347 に答える
2

詳細は正確にはわかりません。しかし、一般的には、次のように機能します。

大きいmalloc()ものは 経由mmap()で処理されるため、小さいものに集中します。しきい値を設定できる限界がどこかにあります。

より小さいmalloc()は、データ セグメントの最後で処理されます。brk()これは、システム コールとを使用して glibc で処理およびサイズ変更できますsbrk()。

メモリ ブロックを取得した後、 が呼び出されmalloc()たときにどれだけ解放するかを知るために保持する必要がfree()あり、次のブロックへのポインターを保持して、それらをすべて見つけてチェーン化する必要があります。

free()最後にあるメモリ ブロックを ing した後、データ セグメントは で縮小されsbrk()ます。free()最後ではないブロックを ing した後、そのブロックはフリー リストに追加されます。これは、空きメモリ ブロックを再利用するためのリンク リストです。

0x29、つまり は41、割り当てたメモリ ブロック サイズに、前述のフィールド (サイズと次のポインタ) を保持するためのメモリのビットを加えたもので、8 バイトが必要です。9番目が何のためにあるかはわかりませんが、アライメントに関係している可能性があります.

「約束された」32 バイトを超えて書き込むと、このリンク リストとそれに関連付けられたポインタが破棄されます。そのため、free()誤ったデータを信頼して、許可されていない場所に書き込もうとして、SIGSEGV.

于 2012-05-10T19:36:48.720 に答える
0

より多くのバイトを上書きすると、free() でセグメンテーション違反が発生するのはなぜですか?

要求したスペースの終わりを通過すると、技術的には未定義の動作が呼び出されるため、何でも可能です。最終的には、内部データ構造のポインターまたはサイズ フィールドを上書きします。この破損によって、存在しないページ全体を参照するほど乱暴な参照が発生する場合と発生しない場合があります。

つまり、セグメンテーション違反はページ保護の結果です。これは、あるプログラム全体を別の無関係なプログラムから保護するのにうまく機能し、オペレーティング システムが単一のユーザー モード アドレス空間への損傷を制限するために使用するツールです。このメカニズムは、内部データ構造と密接に同期していません。有効なポインターと有効なページの間には大まかな対応がありますが、正確なものはありません。

また、free() アルゴリズムはどのように機能しますか?

ブロックが malloc() によって返されると、内部データ構造が作成されるため、正確なブロックが free() に渡されたときに認識され、フリー リストにリンクされます。可能であれば、隣接する空きブロックと結合されます。

また、malloc と free はどのようにアドレスを追跡しているのでしょうか?

Linux を実行しているため、ソース コードが利用可能であり、それを読むことで当然、最も正確な答えが得られます。ただし、一般的な答えは、ディレクトリが保持されるというものです。 このディレクトリは、別のデータ構造である場合もあれば、返される実際のアドレスの前にメタデータが保持されたリンク リストの形式である場合もあります。

なぜ無駄なスペースがあるのですか？

正確には無駄ではありません。領域の一部はディレクトリに使用される場合があり、一部はブロックをキャッシュ境界に合わせて維持することでパフォーマンスと引き換えに使用される場合があります。サイズがキャッシュ ラインと同じか、それよりも小さい小さなブロックをイメージします。このブロックがキャッシュ ラインの境界とオーバーラップする場合、キャッシュ内に保持するには、必要な容量の 2 倍のスペースが必要になります。これがどこでも発生した場合、キャッシュは実質的に半分のサイズになり、ヒット率が低下します。(まあ、隣接するアドレスが実際に必要な場合を除いて。) より大きなブロックを使用すると、内部の断片化も少なくなり、malloc() と free() の呼び出しのバランスが取れている定常状態では、実際には全体的にメモリの使用量が少なくなる可能性があります。長期にわたるプロセス。

于 2012-05-10T19:36:37.950 に答える