このページは、 教科書 K&R2 などで一通りＣ言語について学んだ人を対象としています。 ある程度 void* malloc(size_t size) と void free(void* p) を使った経験がないと、 おもしろみがわかりにくいかも知れません。
K&R2 §8.7 Example --- A Storage Alocator に、 malloc() と free() を実現する方法が載っています。 ただしここは第 8 章 The UNIX System Interface の一節なので、 ANSI C からはみ出したプログラミングになっています。 そこで、 そのアイディアに習いつつ、 ANSI C の範囲で malloc() と free() の私家版を書いてみましょう。 これらは引数や返り値が“本家”とはやや異なり、 char* mymalloc(size_t size) と void myfree(char* p) になります。
まず、メモリの大きなかたまりを取ってきます。 malloc() を使っても、配列を使っても構いません。 この先ではこの大きさが 256 バイトであるとして説明しますが、 適当に改変すればもっと大きなかたまりでも扱えます。 この先頭アドレスを a とします。 よって、このかたまり内のメモリは a[i]（i は 0 から 255 まで） としてアクセスできます。 この i のことを以下ではオフセットと呼ぶことにします。
このかたまりを、最初の 1 バイト a[0]（以下では「先頭部分」と呼ぶ）を除いて、 いくつか（＝一つ以上）のブロックに分けます。 これらのブロックは「使用中」「空き」の二種類に分類されます。 「使用中」ブロックどうしが並んでも構いませんが、 「空き」ブロックどうしは並ばないものとします。
+-+------+--------+--------+------------+------+------+
（例）| |使用中| 空き | 使用中 | 使用中 | 空き |使用中|
+-+------+--------+--------+------------+------+------+
各「空き」ブロックの先頭の 1 バイトには「サイズ」が、 次の 1 バイトには「次の『空き』のオフセット」が書き込まれています。 「サイズ」とはこのブロックのサイズから「サイズ」の部分の 1 バイトを引いたもの、 「次の『空き』のオフセット」とは次の空きブロックのオフセットです。
|<------------- サイズ ------------->|
+----------+----------+----------( (------------+
（例）| サイズ |オフセット| ) ) |
+----------+----------+----------( (------------+
|
+--------------------------------------> 次の空きブロックを指す
かたまりの「先頭部分」a[0] には一番左の空きブロックのオフセットをいれておきます。
これによって、空きブロックたちは（一方向）リスト構造をなすことになります。
最も右の空きブロックの「次の『空き』のオフセット」、
および空きブロックが一つもないときの「先頭部分」には 0 を入れ、
「ない」ことを表わします。
各「使用中」ブロックの 1 バイト目にはそのブロックのサイズから 1 を引いたものがはいっています。 2 バイト目以下は mymalloc() を call したユーザが自由に使っています。
メモリのこのかたまりは、常に上で述べたようになっているものとします。
mymalloc(size_t size) は、次のような操作を行ないます。 空きブロックのリストを先頭からたどり、 サイズが size 以上である空きブロックをさがします。
myfree(char* p) は、p を空きブロックのリストに挿入します。 返されたブロックの左または右が空きブロックである場合には、 隣り合った空きブロックの併合を行ない、 空きブロックどうしが隣り合わないようにします。
上のやり方では、 要求を満たすことのできる空きブロックが二つ以上ある場合、 最初に見つかった（＝一番左の）ブロックを返します。 このやり方にはむだがあるように見えます。 たとえば空きブロックのサイズが順に 89, 16, 17 で size が 15 の要求がなされた場合、 サイズ 89 のブロックが分割されて返されるので、残りは 73, 16, 17 となります。 これで次にサイズ 80 の要求がきたら、NULL を返すしかありません。 もしもサイズ 16 か 17 のブロックを返していれば、 サイズ 89 のブロックは手つかずですからサイズ 80 の要求に答えられます。 しかし、 メモリ割り当てとメモリ開放をくり返していると、 小さいブロックが左のほうに、大きいブロックが右のほうに集まってきて、 これでもそれほど効率は悪くないそうです。 これとは別に、 要求を満たす中で最小のブロックを返す方法もあります。 これだと、一つ見つかっても、リストを最後までたどる必要があります。
また、上の説明では、ブロックが大きすぎるときはブロックの後ろを切り分けて返していますが、 前を切り分けることもできるでしょう。
上のようにして、 関数 char* mymalloc(size_t size) と void myfree(char* p) を書いてください。 また、デバッグ用のプログラムを書いてください。
この課題では、 デバッグ用プログラムのほうが結構めんどうになります。 一つ二つ、mymalloc() と myfree() を実行して“無事”であっても、 バグがないとは限らないからです。 一つのやり方は、このメモリのかたまりを“ダンプ”するルーチンを書く方法です。 たとえば下のようなスタイルにすれば 16 行で 256 バイトの表示ができます。
0000 01 FE 00 00 00 00 00 00-00 00 00 00 00 00 00 00
0010 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00
.......
00F0 00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00
使用中ブロックと空きブロックなどで色を変えると見やすいでしょう。
main() 関数のループでは、
一案としては、
キーボードからのコマンドを受け付け、
それに応じてメモリを要求したり開放したりします。
要求したメモリには何かを記憶させたほうがダンプ画面上でわかりやすいかもしれません。
もう一案は、乱数を発生させ、
それに従ってメモリの要求・開放をくり返してはときどき止まる、
というものです。
そのまますぐにコンパイルして試せるようにしてメールで送ってください。 オプション課題なので、期限は特に決めません。 また、メールの Subject は適当につけて、 メール本文でどのオプション課題に対するレポートなのか説明してください。
※ この課題の解答となるプログラムを私は以前に書いたことがあるが、 上の説明は記憶に基づいて書いたものである。 よって、誤りがある可能性があるが、 その場合は適当に修正しつつ取り組んでみてほしい。
※ こうやって私家版を書いてみると、 malloc() で割り当てられたメモリの外に書き込んだり、 free() されたメモリをもう一度 free() したり、 といった illegal なコードを書くとおかしなことがおこるのがなぜか、 よくわかるだろう。
※ 本家で void* だったところが char* となっているのは、 2 バイト以上を占める型の変数を任意のアドレスから始まるメモリに置くことができるとは限らないからだ。 この点について ANSI C の範囲で解決する方法を思いついた人は、教えてほしい。