malloc

ひとことで

libc 関数malloc, freeとゆかいな仲間たちの再実装。

要件

malloc, freeなどの関数を含んだライブラリを作成する。

実装すべき関数

以下の libc 関数を再実装する:

• void* malloc(size_t size);
• void free(void *ptr);
• void* realloc(void *ptr, size_t size);

さらに, 以下の関数を実装する:

• void show_alloc_mem(void);

これはこの課題独自の関数で, 呼び出すとその時点でアロケートされているメモリ領域をゾーン(後述)ごとにアドレスの昇順に出力する。

・・・この「アドレスの昇順に」が無ければ結構色々できるんだけどなあ。

アロケーション手法についての要件

libc 実装ではメモリアロケーションのために brk(sbrk)あるいは mmap システムコールが使われるが, この課題ではmmapのみ許可されている。

そしてmalloc1 回ごとにmmapを 1 回呼ぶのはもったいないので, 1 度のmmap呼び出しである程度大きなサイズのメモリをアロケートすることが要請されている。
1 度のmmapでアロケートされるメモリ領域のことを「ゾーン」(zone)と呼ぶ。
ゾーンはmalloc(n)のnに応じて TINY, SMALL, LARGE の 3 種類ある。
さらに細かい要件は課題 PDF を見ること。

ボーナス要件

マルチスレッド対応

作ったライブラリが「スレッドセーフである」なら加点さ。

要件としては単にそれだけだが、このリポジトリではさらにマルチスレッド環境において速度が落ちにくいようにしてある。

環境変数

実際のmalloc系関数は, 環境変数により動作を変えることができるので、同じような機能を組み込むと加点。

show_alloc_mem_ex()関数

show_alloc_mem()関数よりさらに詳しい情報を表示する関数show_alloc_mem_ex()を作成すると加点。

「デフラグ」機能

「デフラグ」を行う機能を作成すると加点。

ただ、いわゆるディスクのデフラグのようにメモリ領域を勝手に再配置すると普通にクラッシュすると思うので、少し違う方向性になるはず。
(メモリアドレスを直接いじれない言語なら再配置できそうな気はするが・・・)

このリポジトリでは、free時のアルゴリズムで断片化を抑制している(ただしこれは良し悪しがある)他、「実行すると、使用済み領域を持たないゾーンをすべて解放する」関数を実装した。

おまけ実装内容

課題では特に要求されていない、趣味的な実装。

追加関数

以下の関数が追加されている:

void*	calloc(size_t count, size_t size);
size_t 	malloc_usable_size (void *ptr);
void*	memalign(size_t alignment, size_t size);
void*	aligned_alloc(size_t alignment, size_t size);
int		posix_memalign(void **memptr, size_t alignment, size_t size);

これにより, ライブラリ差し替えのもとで bash, vimが起動・使用できる。

性能について

残念ながらそれほど早くない。
たとえばtime node -e 'console.log("hello")'の結果は:

real    0m3.955s
user    0m3.853s
sys     0m0.093s

なぜこんなに遅いのか。

このリポジトリの実装方針は大筋ではmalloc 動画で解説されている内容に基づいているが、取りこぼしが結構ある:

• チャンクのデータ構造の差異
• fastbins
  • やると課題の評価項目的に厳しそう
• 遅延合体
• などなど...

この辺を詰めると早くなるのかもしれない。

ちなみにnodeやvimは遅いがbashはあまり遅さを感じない。遅くなるアロケーションのパターン, というものがあるのだろう。