　ちょっと最近mallocの勉強してるので、軽くまとめでも。
　経緯としては、研究でmemory allocaterを書くことになったからですね。memory allocaterを書くからには、mallocのソース読まないと！！ってなって、ソース読む前に勉強でも、といった感じです。

##mallocってなんだっけ……？
ということで、「programming Ⅰ」って感じの軽い説明。

void *malloc(size_t size);

mallocはsizeバイト分のメモリを割り当て、ポインタを返す
返ってくるのはvoidのポインタなので、戻り値を型でキャストする必要がある
中身は初期化されていない
確保したら、freeを忘れずに

char *str = (char*)malloc(length); // 使う型でキャストする

##古典的ｍalloc

C Programming Language (Prentice Hall Software)
	Brian W. Ritchie, Dennis Kernighan Prentice Hall 1988-03-22 売り上げランキング : 6166 Amazonで詳しく見る by G-Tools

プログラミング作法でお馴染み、カーニハンが著者の一人である「C Programming Language」でも紹介された、Unix初期のmallocについて触れていきます。

リストを使ってメモリを管理
使用可能なブロックを繋げたリスト
管理領域(header)分だけ多くallocateし、ブロックの先頭に管理領域を付加する
first fit方式で使用するメモリを選択する

空きブロックが白色で、そこについてるヘッダーが青色です。

first fit

リストを頭から見ていって、最初に見つけたものを使用するというすごいシンプルな方法。

しかし欠点があって、この場合に損することに。

実は、後一個さきにもっと適切なブロックがあった……、という場合。これに対応できないので、first fitはよくない。

Free!

mallocの勉強する以上、freeも避けては通れないです。

void free(void* ptr);

メモリの開放は、使用中のブロックを使用可能listに入れてやるだけで良い。
これだけ見ると、引数で受け取ったポインタの部分を開放してやればよいかに思える。でも、それだけじゃダメ。
開放したい領域と隣接してるブロックに、空きブロックがあるなら併合しないといけない。

以下で、例を交えながら説明する。

listから最初のポインタと二番目のポインタを取ってきて、prev < p < nextとなるまで探す。

あった！！！

解放後、隣接している空きブロックがあったら併合しなければならないので、prevとp・pとnextが隣接しているかチェックする。

(prev + prev->size) != p なので、prevとpは隣接していない
(p+p->size)          = nextなので、pとnextは隣接している

チェックに引っかかったところを併合します。
"併合"=リストの更新。prevとnextをポインタで繋げばおっけーです。これでfreeできた、と。

これでフラグメンテーションが鬼のように進むmallocが理解できました。糞ですよね。でもこのmallocが作られたころは糞じゃなかったんですよ。当時は「メモリを一気に確保する」というのが常識だったのでこれでも実用可能でした。「メモリが一気に確保する」という前提ならmallocはO(1)だからです。ですが、時代は流れていきます。
GUI、Java, Rubyなどのスクリプト言語は小さいmallocが連発されるので、よくない。なので、改良が進んでいきます。まあ今回は古典malloc&free、ということで。