mallocの仕組み
ヒープと空きリストについて学びます。
「mallocの仕組み」はCoddyKit上の無料C Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
mallocが実際に行っていること
malloc(n)を呼び出すと、Cライブラリは少なくともnバイトの利用可能な領域を指すポインタを渡します。ただし、ヒープは、アロケータが代わりに管理するプロセスのメモリ領域にすぎません。
アロケータの役割は、どのバイトが使用中か、どのバイトが空いているか、解放されたメモリを効率よく再利用する方法を記録することです。
ヒープはOSから取得される
アロケータが何もないところからメモリを作り出すわけではありません。brk/sbrkやmmapのようなシステムコールを通じて、OSに大きなチャンクを要求します。
そして、そのチャンクを小さなブロックに分割して、プログラムのmalloc呼び出しに割り当てます。OSへの要求は高コストなので、アロケータはメモリをまとめて要求し、再利用します。
/* Conceptual: grow the heap by 4096 bytes */
void *base = sbrk(4096);
if (base == (void *)-1) {
/* out of memory */
}sbrkとプログラムブレーク
sbrk(n)は「プログラムブレーク」をnバイト分上へ移動し、移動前のブレークを返します。新たに公開された領域が、利用可能なヒープ領域になります。
直線的で単純ですが、途中にあるメモリを返すのは容易ではありません。現代のアロケータは、大きな要求にはmmapを優先します。
void *prev_break = sbrk(0); /* current break */
sbrk(1024); /* grow by 1 KB */
/* prev_break now points to fresh memory */ブロックのメタデータ
アロケータは、割り当てごとにデータの隣へ小さなヘッダーを保存します。ヘッダーにはサイズと、空いているかどうかが記録されます。このヘッダーがあるため、freeは渡されたデータポインタだけで処理できます。
mallocから受け取るポインタはヘッダーの後ろを指すため、メタデータは利用者から見えません。
typedef struct block {
size_t size;
int free;
struct block *next;
} block_t;ヘッダーの直後を指すポインタ
よく使われる方法にポインタ演算があります。ユーザーポインタはheader + 1です。ユーザーポインタが与えられると、ヘッダーはその1つ前のblock_tにあります。
これにより、free(p)は、利用者から渡されなくても、割り当てたブロックのサイズを復元できます。
block_t *hdr = (block_t *)user_ptr - 1;
printf("block size = %zu\n", hdr->size);小さなヘッダー配置デモ
静的バッファ上にヘッダーを配置し、そこから読み戻してみましょう。実際のアロケータが領域をヘッダーとペイロードに分割する方法を示します。
OSの呼び出しを行わないため、どこでも実行できます。
#include <stdio.h>
#include <stddef.h>
typedef struct { size_t size; int free; } block_t;
static char buffer[256];
int main(void) {
block_t *h = (block_t *)buffer;
h->size = 64;
h->free = 0;
void *payload = (char *)buffer + sizeof(block_t);
printf("header bytes = %zu\n", sizeof(block_t));
printf("payload offset = %ld\n", (long)((char *)payload - buffer));
printf("size field = %zu\n", h->size);
return 0;
}空きリストの考え方
多くのアロケータは、空きブロックをリンクリストにつなぎます。mallocを呼び出すと、アロケータはこのリストをたどり、十分な大きさのブロックを探します。
freeを呼び出すと、ブロックは空きとしてマークされ、後で再利用できるようリストに戻されます。これにより、OSへ新たに要求せずに済みます。
block_t *find_free(block_t *head, size_t size) {
block_t *b = head;
while (b && !(b->free && b->size >= size))
b = b->next;
return b;
}freeが行うべきこと
free(p)はpのヘッダーを見つけて空きとしてマークし、可能なら隣接する空きブロックと結合（coalescing）して、断片化を抑えます。
同じポインタに対してfreeを2回呼び出したり、ヒープ上のものではないポインタを解放したりすると、メタデータが壊れるため未定義動作になります。
void my_free(void *p) {
if (!p) return;
block_t *hdr = (block_t *)p - 1;
hdr->free = 1;
/* real allocators coalesce neighbors here */
}断片化
時間が経つと、異なるサイズのメモリを解放したり割り当てたりすることで隙間が残ります。外部断片化とは、空きメモリは存在するものの細かく分散していて、要求を満たせる大きさの連続領域がない状態です。
内部断片化とは、必要以上に大きいブロックの内部で無駄になる領域です。アラインメントや丸めによって発生することがよくあります。
アラインメント要件
mallocは、あらゆる型に適したアラインメントのメモリを返さなければなりません。多くの64ビットシステムでは、これは16バイト境界のアラインメントを意味し、max_align_tを満たします。
アラインメントされていないポインタは、CPUによってはクラッシュの原因になったり、別のCPUではアクセスを遅くしたりします。そのため、アロケータは常にペイロードのサイズをアラインメント境界まで切り上げます。
#include <stdalign.h>
/* alignof(max_align_t) is the strictest required alignment */
size_t a = alignof(max_align_t);全体を組み合わせる
したがって、最小限のアロケータには、メモリの供給元（静的バッファ、sbrk、mmap）、ブロックごとのヘッダー、空き領域を探す方法、アラインメント処理が必要です。
次のレッスンでは、これらの要素を構築します。まずバンプアロケータ、次に空きリスト、最後にアラインメントとブロック分割を扱います。
/* The four pillars of a custom allocator */
/* 1. memory source 2. block headers */
/* 3. free-block search 4. alignment */簡単な確認
アロケータの内部動作について理解度を確認しましょう。
まとめ
mallocは、sbrkまたはmmapを通じてOSから取得したヒープを管理し、サイズと空き状態を記録する非公開のヘッダー付きブロックに分割します。
空きリストによって再利用が可能になり、アラインメントによってあらゆる型に対応できます。断片化は中心的な課題です。これらの考え方が、次に構築するアロケータの基盤になります。
よくある質問
「mallocの仕組み」レッスンは無料ですか？
はい。「mallocの仕組み」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「mallocの仕組み」で何を学びますか？
ヒープと空きリストについて学びます。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「mallocの仕組み」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- mallocの仕組み
- シンプルなバンプアロケーター
- 空きリストと再利用
- アラインメントと分割