HN 日本語サマリー

← 一覧へ戻る
プログラミング

なぜmallocは常に要求以上のことをするのか?

Why malloc always does more than I asked for? (ssenthilnathan3.github.io)

44 pointsby nathaah336 コメント

要約

C言語で`malloc(13)`のようにメモリを要求しても、実際にはそれ以上の領域が確保される理由を解説しています。これは、ヘッダー情報、アライメントのためのパディング、および`free()`関数がメモリブロックを正しく識別するために必要なメタデータ(バックポインタなど)を格納するためのオーバーヘッドによるものです。この記事では、バンプアロケータから始まり、メタデータ、アライメント、パディング、内部フラグメンテーションといった概念を段階的に説明し、最終的に`malloc`がなぜ常に要求以上のメモリを返すのかを明らかにします。

全文翻訳

mallocはなぜ私が要求したものより多くを確保するのか

void *p = malloc(13);

安全なCプログラムを書く際に、ほとんどの人がこれを目にしたことがあるでしょう。この行が何をするのか、少なくともその目的はわかっているはずです。

13バイトを要求し、13バイトを得る

好奇心から金曜日にこれを構築し始めたとき、私はそう思っていました。コードを一行も書かずに30分後…これはほとんど起こらないということを知りました。

この単純な一行は、その裏で複数の興味深い計算とアロケーションを含んでいます。

例えば、私が13バイトを要求した場合。

実際に確保されるもの:

+--------+---------+--------------+-------------+
| Header | Padding | Back Pointer | User Memory |
+--------+---------+--------------+-------------+

User Memory(ユーザーメモリ)だけが私たちが使用するものであり、*p はそのメモリの開始位置を返します。他のすべてはそこにあるだけ…使用するためではなく…なぜでしょうか?

理論に入る代わりに、アロケータを構築して解放してみようと思いました。

最も単純なアロケータ

最も単純なアロケータには free() さえありません。これはバンプアロケータと呼ばれます。事前に大きなメモリチャンク(アリーナ)を与えられ、すべてのアロケーションは単にポインタを前方に移動させるだけです。

typedef struct {
  uint8_t *cursor;
  uint8_t *limit;
} Arena;

cursor は次のアロケーションが開始される場所です。limit はアリーナの終端です。それが全体の設計です。

void *bump_alloc(Arena *a, size_t size) {
  if (a->cursor + size > a->limit) return NULL; // メモリ不足
  void *ptr = a->cursor;
  a->cursor += size;
  return ptr;
}

これだけです。常に前方にしか移動できません。これは最も高速なアロケータですが、free() がないため、長期間実行されるものには機能的に役に立ちません。アリーナ全体を一度に解放できるだけで、その中の個々のオブジェクトを解放することはできません。

これにより、当然の疑問が生じます:一つのものを解放できないなら、どうすればあの13バイトを取り戻せるのでしょうか?

この設計では、それはできません。個別の free() を機能させるためには、アロケータは渡したすべてのアロケーションについて何かを覚えておく必要があります。そして、メタデータがオプションでなくなる瞬間です。

free(ptr) はポインタという一つの引数だけを受け取ります。アロケータの仕事がそのメモリを回収して再利用可能にすることであるなら、それは呼び出し元が決して伝えない質問に答えなければなりません:

このアロケーションはどれくらいの大きさで、実際にはどこから始まるのか?

それに答える唯一の方法は、ptr だけを使って、アロケータが後で見つけられるようにどこかにその答えを保存することです。明白な場所は、あなたが渡したメモリのすぐ前です。

typedef struct {
    size_t size;
} Header;

したがって、単に生のメモリを返すのではなく、alloc() は次のように動作します:

[ Header ][ User Memory ]
           ^
           呼び出し元に返される

そして free(ptr) は後方に移動します:

Header *h = (Header *)ptr - 1;
// now h->size tells us how big this block was

これは単純なアプローチです。もっとあります ;)

すべての型が任意のメモリアドレスに配置されることを望むわけではありません。それをアライメントと呼びます。

  • char はメモリ上のどこに配置されても気にしません。(アライメント = 0)
  • double はほとんどのプラットフォームで8の倍数であるアドレスから始まることを要求します(アライメント = 8)…そして他の多くの型についても同様です。

異なるアライメントを使用してもプログラムがコンパイルされないという厳格なルールはありません。パフォーマンスが低下したり、予期せぬクラッシュが発生したりする可能性があります。

したがって、alloc() は単にあるポインタを返すだけでなく、呼び出し元がそこに格納しようとしている型に対して正しくアライメントされたポインタを返す必要があります。

これは、ヘッダーが終わる場所とユーザーポインタが実際に開始する必要がある場所の間にギャップがある可能性があることを意味します。そして、そのギャップは、要求されたアライメントによって、毎回異なるサイズになります。

そのギャップはパディングと呼ばれるものです。

[ Header ][ ...variable padding... ][ User Memory ]

そして、まさにここで header = (Header *)ptr - 1 がうまくいかなくなります。その減算は、ptr からヘッダーまでの固定された距離を想定しています。しかし、パディングは固定されておらず、アロケーションごとに変化します。

free() は、この特定のポインタに対してどれだけのパディングが挿入されたかを知る方法がないため、ヘッダーを見つけるために後方に信頼できる方法で移動できません。

バックポインタ

ヘッダーまでの距離が固定されていないなら、距離に依存しないでください。代わりに、常に固定された位置にヘッダーへのポインタを保存します。

[ Header ][ ...variable padding... ][ Back Pointer ][ User Memory ]
                                     ^返されるポインタの
                                      直前にある、常に sizeof(void*) の位置

これで free() はパディングを知ったり再計算したりする必要がなくなります。単に次のように動作します:

Header *h = *(Header **)((uint8_t *)ptr - sizeof(void*));

そのスロットは、アライメントに関係なく、常にユーザーポインタから sizeof(void*) バイト手前にあります。

ヘッダーはどこにでも配置でき、どれだけ離れていても構いません。そしてバックポインタがそれを指します。

では、実際にはどのポインタがアライメントされるのか?

待ってください…アライメントされる必要があるのはアリーナのカーソルではなく、ユーザーポインタ、つまり呼び出し元に実際に返すものです。アリーナカーソルは着地した場所に留まることができます。誰もそれを直接逆参照することはありません。

したがって、実際の計算は次のようになります:

candidate = header + sizeof(Header)
padding   = align(candidate + sizeof(void*), alignment)
user_ptr  = candidate + sizeof(void*) + padding

そしてパディング量はヘッダーにも格納されます。主に、後でデバッグやテストに役立つことが判明したためです。user_ptr - padding が candidate に正確に戻ることを確認できます。

内部フラグメンテーション

ヘッダー、バックポインタ、アライメントをすべて機能させた後、レイアウトをしばらく見てみました:

[ Header ][ Padding ][ Back Pointer ][ User Memory ]

そして、明白な質問が現れました:

ヘッダーとバックポインタの間にあるあのパディングバイト…それらはアロケーションの全期間中、ただそこにあり、未使用のままです。アロケータはそれらを再利用できないのでしょうか?

アロケーションは一つの連続したブロックでなければならないからです。呼び出し元は user_ptr で始まるN個の連続したバイトを約束されており、「ここにあなたのメモリがありますが、真ん中のこれらの3バイトは別のものです」と説明する方法はありません。これはアロケーションそのものの契約を破ることになります。

したがって、それらのバイトはアロケートされている、つまりこのブロックに属しており、他の誰にも与えることができないという意味ではありますが、決して誰にも、決して触られることはありません。それが内部フラグメンテーションであり、アライメント要件のみによって発生する無駄であり、パディングを必要とするすべてのアロケーションに焼き付けられています。

確保されたメモリを解放するにはどうすればよいか?

PythonやGolangのようなほとんどの言語には、インタプリタやコンパイラ自体にガベージコレクタと呼ばれるコンポーネントがあり、メモリのライフタイムをチェックし、スコープ外になったりフローで使われなくなったりした場合にそのスペースをクリアします。

しかし、Cのような古い言語では、確保されたメモリを手動で解放する必要があります。それにはルールがあり、それ自体がブログ記事になるでしょう。

ヘッダーとバックポインタが整理されたので、free() がついに可能になります。しかし、バンプアロケータは、再利用の概念がどこにもないため、それを実行できません。したがって、設計は形状を変える必要があります。前方にしか移動しないカーソルの代わりに、

解放されて、再利用可能になったブロックの連結リストであるフリーリストが必要です。

typedef struct FreeNode {
    size_t size;
    struct FreeNode *next;
} FreeNode;

free(ptr) は(バックポインタ経由で)ヘッダーを見つけ、それをこのリストの先頭にプッシュします:

void push_free(FreeNode *node) {
    node->next = free_list;
    free_list = node;
}

そして alloc() は、一つのパスではなく二つのパスを持つようになります:

  1. フリーリストを歩き回り、十分な大きさのブロックを探す (search_free)
  2. 何も適合しない場合、古いカーソルをバンプする動作にフォールバックする

ファーストフィットは最も単純な検索戦略です…十分な大きさの最初のブロックを取得し、深く考えません。より洗練されたもの(ベストフィット、サイズクラスごとの分離リスト)は本当の落とし穴ですが、ファーストフィットは概念が機能することを示すには十分です。

スプリッティング

私のアロケータの最初のバージョンは、かなり愚かな習慣を持っていました。

十分な大きさのフリーブロックを見つけた場合、たとえごくわずかな部分しか必要なくても、その全体を渡してしまいました。

要求: 8 バイト

フリーブロック:
+-------------------------------------------+
|                 200 バイト                 |
+-------------------------------------------+

結果:
+-------------------------------------------+
|          すべて 200 バイトが占有される       |
+-------------------------------------------+

プログラムは最初の数バイトしか使用しませんが、残りの192バイトは、そのアロケーションが解放されるまで誰にも使用できません。これは無駄なメモリです。修正はスプリッティングです。

ブロック全体を引き渡す代わりに、二つの部分にカットします。

前

+-------------------------------------------+
|              フリーブロック               |
+-------------------------------------------+

後

+------------+------------------------------+
| アロケーション |      まだフリー           |
+------------+------------------------------+

先頭がアロケーションになります。

残りはフリーリストに直接戻され、次の要求のために準備されます。さて、それは簡単そうに聞こえました。しかし、そうではありませんでした。

最初に実装したとき、誤って第二ブロックを間違った場所に開始してしまいました。最初のブロックのメタデータもスペースを占めることを忘れていました。最初のブロックが完全に終了した後に第二ブロックを作成する代わりに、少し早めに作成してしまいました。

アロケータはすぐにクラッシュしなかったため、バグを見つけるのに時間がかかりました。静かに自身を破損させていました。

もう一つの教訓は、分割しない場合を知ることでした。

分割によってわずかなバイトしか残らないと仮定します。それは実際には別のフリーブロックではありません。それは単なる散らかりです。残りがそれ自体を説明するのに十分な大きさでない場合、それを保持する意味はありません。

したがって、時には小さなブロックを作成するよりも、数バイトを無駄にする方が良い場合があります。そのブロックは二度と使用できません。

この制限を min_split_size と呼びました。

コアレッシング:パズルを元に戻す

さて、スプリッティングはより小さなブロックを作成します。しかし、最終的には反対の問題が現れます。

紙をたくさんの小さな断片にカットすることを想像してください。全体として十分な紙があっても、どれも必要なものには十分な大きさではないかもしれません。メモリも同様に動作します。

二つのブロックを確保したと仮定します。

+--------+--------+
|   a    |   b    |
+--------+--------+

後で、両方が解放されます。

+--------+--------+
| フリー a | フリー b |
+--------+--------+

それらはメモリ上で隣接しています。一緒に、それらはより大きなアロケーションのために十分な大きさになります。

しかし、私のアロケータはそれらを二つの別々のブロックと考えています。

したがって、誰かが個々のブロックよりも大きいものを要求した場合…

必要: 32 バイト

利用可能:
16 バイト
16 バイト

…全体として十分なメモリがあるにもかかわらず、アロケーションは失敗します。

修正はコアレッシングと呼ばれます。

これは、隣接するフリーブロックを再び結合することの、単なる派手な言葉です。

前

+--------+--------+
| フリー a | フリー b |
+--------+--------+

後

+-----------------+
|   一つの大きなブロック |
+-----------------+

右側のブロックを見つけるのは簡単でした。なぜなら、各ブロックは自身のサイズを知っており、それによって前のブロックの終端がわかったからです。しかし、どれも前のブロックがどこから始まったかを知りませんでした。

解決策は驚くほど単純でした。

サイズを二度書き込みます。一度はブロックの先頭に。そしてもう一度は末尾に。

+--------+---------+--------+
| header |  data   | footer |
+--------+---------+--------+

これで、任意のブロックの先頭に立ったとき、すぐ後ろを見ることができ、フッターから前のブロックのサイズを読み取り、そのヘッダーに直接ジャンプできます。

その時になって初めて、両方向にブロックをマージできました。

これは、一つの問題を解決するために、さらに多くのメタデータを追加する必要があった、私がアロケータを「小さく」しようとし始めたときに予想していたこととは正反対の、まさに予想外の瞬間の一つでした。

まとめ

「自分で malloc を書いてみよう」として始まったことは、すぐにトレードオフの連続になりました。アライメントを追加するとパディングが導入され、落とし穴に陥り、すべての解決策が一つ問題を修正する一方で、次の問題を引き起こしました。おそらく、このプロジェクトから得た最大の教訓はそれでしょう。

…さらに知りたい人のために

これらはメインの記事には含まれていませんでしたが、おそらく私が最も多く学んだバグです。

バグ #1: 「待て…これはなぜクラッシュしているんだ?」

スプリッティングを実装した後、すべて順調に見えました。

次に -fsanitize=undefined でコンパイルしました。

runtime error: member access within misaligned address 0x61d000000173
for type 'struct FreeNode', which requires 8 byte alignment

私の最初の考えは、「それは意味がない。すでにすべてのアロケーションをアライメントしているのに」でした。

実際には、ユーザーポインタをアライメントしており、残りのヘッダーをアライメントしていなかったことが判明しました。

大きなブロックが分割されたとき、残りのバイトが開始された場所ならどこでも、単に FreeNode をドロップしていました。

FreeNode *remainder =
    (FreeNode *)((uint8_t *)header + sizeof(FreeNode) + needed);

時にはそのアドレスは8で割り切れず、時には割り切れました。これがバグが時々しか現れなかった理由を説明しています。

修正は、残りを FreeNode として扱う前に単にアライメントすることでした。

その後、サニタイザーは満足しました。約5分間は。

バグ #2: 400回の操作後に破損

これは最悪でした。

私のストレステストは、数千回のランダムなアロケーションと解放を実行しました。すべて順調に見えましたが、数百回の操作後、まだ触られてもいないアロケーションが突然破損しました。

原因は、恥ずかしいほど単純であることが判明しました。フッターは、ブロックを解放するとき、またはブロックを分割するときにのみ書き込んでいました。通常の(新規)アロケーションにはフッターが設定されませんでした。

そのため、ずっと後になって、コアレッシングが後方に移動しようとしたとき、フッターがあるべき場所に座っていたランダムなバイトを読み取りました。それらのランダムなバイトはランダムなブロックサイズになりました。ランダムなブロックサイズはランダムなポインタになりました。

修正は、ブロックのサイズが変更されるたびに、そのフッターを書き込むことでした。常に!!

ソースコード

この記事はアイデアと設計上の決定に焦点を当てています。完全な実装、テスト、デバッグの旅はここで入手できます:

https://github.com/ssenthilnathan3/bump-allocation-c.git