自前 malloc — ヒープを自分で管理する

この回の位置づけ

コマ12 の資料で「malloc の仕組みは実装しない」と言った、その中身を作る。

malloc は何をしているのか

コマ12 では、こう説明した。

malloc は、指定されたバイト数ぶんのメモリ領域をヒープから確保し、 その先頭アドレスを返すライブラリ関数である。

ではその「確保」とは何か。大きな領域を、要求されたぶんずつ切り分けて配ることである。 配った場所を覚えておかないと、次の要求で同じ場所を二重に配ってしまう。

この回では、ヒープの元になる領域（プール）を呼び出し側から渡してもらう。

#include "lib.h"

char *pool;
pool = malloc(1024);
heap_init(pool, 1024);

プール自体は libc の malloc から借り、その中の切り分け（自作アロケータ）を 自分で書く、という位置づけである。

本物の malloc は OS から brk / mmap で領域をもらうが、 そこは R1 のシステムコールの話で、割り当ての本質ではない。

段階1: バンプ割り当て — ただ切り出す

いちばん単純な方式は、「次に配る位置」を1つ覚えておき、要求されたぶんだけ進めることである。

pool ┌──────┬──────┬────────────────────────┐
     │ 16B  │ 32B  │       未使用            │
     └──────┴──────┴────────────────────────┘
                    ^ heap_brk（次はここから配る）

heap_brk を進めるだけなので非常に速い。しかし free ができない （真ん中を返されても、heap_brk を戻せない）。 それでもコンパイラのような「起動して、確保しまくって、終わったら全部捨てる」 プログラムには十分で、実際に発展課題 P1（C 移植・セルフホスト）の C 実装の規約でも「free は不要」としている。

段階2: ヘッダを付けて再利用する

free を作るには、返された領域がどれだけの大きさだったかを知る必要がある。 my_free(p) に渡されるのはアドレスだけだからである。

そこで、配る領域の手前に管理用のヘッダを置く。

      ┌────────────┬──────────────────┐
      │ Header     │ ユーザ領域        │
      └────────────┴──────────────────┘
      ^ h                ^ my_malloc が返すアドレス p
                         p = h + sizeof(Header)
                         h = p - sizeof(Header)

ヘッダには、大きさ・解放済みフラグ・次のブロックへのポインタを持たせる。 コマ12 で作った自己参照構造体そのものである。

struct Header {
    int size;
    int free;
    struct Header *next;
};

これで、my_free(p) は「p の手前のヘッダを見て free = 1 にする」だけでよい。 my_malloc は、まず管理リストから「解放済みで十分な大きさ」のブロックを探し （first fit）、あればそれを再利用する。なければ未使用領域から切り出す。

8バイト境界に揃える

要求サイズは 8 の倍数に切り上げる（align8）。 コマ8・コマ12 で見たように、int は4バイト境界、ポインタは8バイト境界に 置かれる必要があり、揃っていないアドレスを返すと Bus error や 無音の誤動作になるからである。 「アラインメントを揃える」のは、フレームサイズのときと同じ考え方である。

実装

Step 1 だけでも tests/list_build.c は通る。 Step 2 まで進むと tests/reuse.c（解放した跡地が再利用される）が通る。

テスト

python3 check.py

exhaust.c は「無限に確保できてしまう」バグ（終端チェック忘れ）を検出する。

この回の編集対象は C なので、未実装は NotImplementedError ではなく mymalloc.c の TODO(...) コメントで表してある。check.py は TODO が残っている間、 テストを回さず [SKIP] 未実装: … と報告する。SKIP は未達なので、完了条件は満たしていない。

発展課題

1. 12bit の壁を越える: フィールドの多い struct のローカル変数を いくつも並べてフレームを膨らませ、実際に壁を越えさせてみる。そのうえで、 オフセットが範囲外のときは li で一度レジスタに入れてから add する コード生成に直す（コマ3・コマ6 のプロローグとローカル変数アクセス）
2. 分割（split）: 100 バイトの空きブロックに 16 バイトの要求が来たとき、 いまは 100 バイト丸ごと使ってしまう。余りを新しい空きブロックに分ける
3. 併合（coalesce）: 隣り合う空きブロックを1つにまとめる。 さもないと、小さな空きだらけになって大きな要求が通らなくなる（断片化）
4. best fit にする: find_free を「最初に見つかったもの」ではなく 「要求に最も近い大きさのもの」を返す方式に変え、断片化の減り方を比べる
5. libc の malloc と差し替えて計測: 確保・解放を何万回も繰り返すプログラムを書き、 自前版と libc 版で実行時間を比べる

この資料の原稿を見る