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

void *p = malloc(13);安全なCプログラムを書くとき、私たちほとんどがこれを見たことがあるでしょう。この行が何をするかは知っています、少なくともその目的は知っています。13バイトを要求し、13バイトを取得する。それが私が金曜日に好奇心からこれを構築し始めたときの私の考えでした。コードを一行も書かずに30分後…これがほとんど決して起こらないことを知りました。この単純な行には、舞台裏で複数の興味深い計算と割り当てが含まれています。例えば、私が13バイトを要求するとき。実際に予約されるもの：+--------+--------------+---------+-------------+ | Header | Back Pointer | Padding | 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()`がないからです。アリーナ全体を一度にしか解放できず、その中の単一のオブジェクトを解放することはできません。これにより、明白な疑問が生じます。1つのものを解放できない場合、どうすればあの13バイトを取り戻せるのでしょうか？わかった…できません、この設計では。個別の`free()`を機能させるには、アロケータはそれが渡したすべての割り当てについて何かを覚えておく必要があります。そして、その時点でメタデータはオプションではなくなります。なぜメタデータ`free(ptr)`は1つの引数だけを受け取ります。それはポインタです。アロケータの仕事がそのメモリを回収して再利用可能にすることであるなら、それは呼び出し元が決して伝えない質問に答えなければなりません。この割り当てはどのくらいの大きさでしたか、そしてそれは実際にどこから始まりますか？答えを得る唯一の方法は、アロケータが後で見つけられるように、`ptr`だけを使って答えをどこかに保存することです。明白な場所は、あなたが渡したメモリのすぐ前です。typedef struct { size_t size; } Header; そのため、単に生のメモリを返すのではなく、`alloc()`は次のようになります。[ Header ][ User Memory ] ^ 呼び出し元に返される`free(ptr)`は後方に歩きます：Header *h = (Header *)ptr - 1; // これでh->sizeはこのブロックの大きさがわかります これはナイーブなアプローチです。もっとあります ;)ナイーブなヘッダー対アライメントすべての型が任意の場所で生きることを望むわけではありません。それらはアライメントと呼びます。charはメモリ内のどこに配置されるかを気にしません。（アライメント = 0）doubleはほとんどのプラットフォームで8の倍数で始まるアドレス（アライメント = 8）を要求します…そして他の多くの型のためにさらに多くのものがあります。異なるアライメントを使用してもプログラムがコンパイルされるのを厳密に止めるルールはありません。パフォーマンスが低下したり、予期せずクラッシュしたりする可能性があります。そのため、`alloc()`は単にポインタを返すだけでなく、呼び出し元がそこに格納しようとしている型に対して正しくアライメントされたポインタを返す必要があります。これは、ヘッダーが終わる場所とユーザーポインタが実際に開始する必要がある場所の間にギャップがある可能性があることを意味します。そして、そのギャップは、要求されたアライメントによって異なるサイズになります。ギャップはパディングと呼ばれるものです。[ Header ][ ...可変パディング... ][ User Memory ] そして、これはまさに`header = (Header *)ptr - 1`がうまくいかないところです。その減算は、`ptr`からヘッダーまでの固定距離を想定しています。しかし、パディングは固定されておらず、割り当てごとに異なります。`free()`は、この特定のポインタのためにどれだけのパディングが挿入されたかを知る方法がないため、ヘッダーを見つけるために信頼性を持って後方に歩くことができません。バックポインタヘッダーまでの距離が固定されていない場合は、距離に依存しないでください。代わりに、常に固定された位置にヘッダーへのポインタを格納します。[ Header ][ ...可変パディング... ][ Back Pointer ][ User Memory ] ^ パディングがどれだけあっても、ユーザーメモリから常に`sizeof(void*)`バイトの位置バックポインタはヘッダーを指すだけです。ヘッダーはどこにでも、どれだけ離れていても構いません。そしてバックポインタはそれを指すだけです。さて、実際にはどのポインタがアライメントされるのでしょうか？待ってください…アライメントが必要なのはアリーナカーソルではありません。ユーザーポインタ、つまり呼び出し元に実際に返すものです。アリーナカーソルは着地した場所に座ることができます。誰もそれを直接逆参照しません。そのため、実際の計算は次のようになります。candidate = header + sizeof(Header) + sizeof(void*) padding = align(candidate, alignment) user_ptr = candidate + padding そしてパディング量はヘッダーにも格納されます。これは主にデバッグやテストに役立つことが判明したためです。user_ptr - paddingがcandidateに正確に戻ることを確認できます。内部フラグメンテーションこれらすべてが機能した後 => ヘッダー、バックポインタ、アライメント。レイアウトをしばらく見ました：[ Header ][ Back Pointer ][ Padding ][ User Memory ] そして、明白な質問が現れました。メタデータと実際のオブジェクトの間のこれらのパディングバイト…それらは単にそこに座っていて、割り当ての全期間未使用です。アロケータがそれらを再利用できないのはなぜですか？割り当ては1つの連続したブロックである必要があるためです。呼び出し元は`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つのパスではなく2つのパスがあります。十分な大きさのブロックを探してフリーリストを歩きます（search_free）。何も適合しない場合は、古いバンプ・ザ・カーソル動作にフォールバックします。ファーストフィットは最も単純な検索戦略です…十分な大きさの最初のブロックを取得し、深く考えません。より洗練されたもの（ベストフィット、サイズクラスごとのセグリゲーテッドリスト）は本当の深淵ですが、ファーストフィットは概念が機能することを示すのに十分です。分割私の最初のアロケータバージョンには、かなり愚かな習慣がありました。十分な大きさのフリーブロックを見つけた場合、たとえわずかな部分しか必要なくても、その全体を渡してしまいました。要求：8バイトフリーブロック：+-------------------------------------------+ | 200バイト | +---------------------