一応前回初級編だったので名目上タイトルを中級編にしましたが、中級編かなぁ……。まだ初級編のような気はします。
最初で書くべきことではあったのですが、今回の勉強は小崎資広さんがThe 67th Yokohama Kernel Reading Partyという怪しげな(褒めてます)集まりで発表した「mallocの旅」を参考にしています。結構図とか真似したりしてますし、本家のほうを参照したほうがいいかもしれませんね。色々省略とかしてますし。
動画
資料
というか、前回のブログは図に間違いが少しあります。まあ崩壊するほどじゃないので気にしないことにします。
じゃあまず、前回のおさらいでも。
K&R malloc、すげえフラグメンテーション頻発する！
- K&R mallocが主流だった頃は「メモリはプログラムの最初に一気に確保するもの」だった
- メモリが充分に空いている状態で必要なメモリを一気に確保するなら、当然フラグメンテーションは起きにくくなる
- 今はJava・C++みたいなオブジェクト指向言語、Rubyのようなスクリプト言語等があり、小さいmallocが頻発→フラグメンテーション
- それをfirst fitでやるのはよくない
こんな感じかな？本当はこっから少しずつmallocが改良されていくんですが、一気に飛びます。
「そもそも、一つのfree litsで管理すること自体無理があるんじゃね……？」
一つのリストで頑張って管理するのではなく、複数のリストを用意してやればフラグメンテーションはマシになるのではないか、という発想です。フラグメンテーションは小さいブロックと大きいブロックが連続したりすることで起きます。だったらsizeごとにリストを分けて管理してしまおう！ということで、サイズ16Byte用のリスト、サイズ24Byte用のリスト……というようにリストを複数作ります。
- mallocで要求されたsizeを8で割れば自分が使用するindexになる
- 無限にリストを増やすわけにはいかないので、このリストは512Byteのみにする
- 512Byte以上の大きいデータは特殊な管理を行う
- 大きいデータと小さいデータを一緒に管理するからフラグメンテーションが進むんだ
→大きいデータ用の領域がもう一個欲しい
→そうだ、mmapを使おう
mmapってなんだっけ…？
- ファイル(fdで指定したリソース)をメモリにマップする
- fdで"/dev/zero"を指定することでmmapをメモリ確保用のAPIとして使用できる
- このAPIを使ってHuge Block(sizeの大きいブロック)はkernelから直接取得する
コード書くとしたらこんな感じ？compileしてないのでわかんないけど……。
void *alloc_mmap(size_t size) {
int fd = open("/dev/zero", O_RDONLY);
void *ret = mmap(addr, length, prot, flags, fd, offset);
return ret;
}
一応引数の復習ー。
| 引数 | 説明 |
|---|---|
| addr | mapするメモリアドレス。NULLを渡せばkernelがアドレスを選択する。 |
| length | addrから何バイトマッピングするか。 |
| prot | マッピングのメモリ保護の指定。Read Write Exec None等がある。 |
| flags | マップを要求された時、共有するかコピーを渡すか。 |
| offset | ファイルの何バイト目からをメモリにマップするか。 |
HugeBlock
このHuge Blockはmmapで確保するので、free listからは独立しています。図にするとしたらこんな感じ。
listからは独立しているので、当然listをたどったりしなくて良い。
メモリが欲しくなったらmmapして、いらないならaddressを指定してmunmapするだけ。
- free list上でフラグメンテーションが起きにくくなった(当たり前)
- メモリの無駄が少ない
大きなメモリは同じサイズでもう一度mallocされる可能性は低いので、使わなくなったらすぐにOSに返却する、というのは正しい。
Huge Blockをmmapで管理するのは確かに手っ取り早いし効率も良いのですが、何ByteからHugeBlockとみなすかを動かすプログラムや実行環境からちゃんと考えてあげないといけない……らしい。
大きいmallocがたくさん呼ばれるとき……かな？多分。大きいmallocが多いならmmapじゃなくてリストの方が良いんじゃないかなあ。
HugeBlockのサイズは環境変数で宣言されてるので、そこをいじる感じですね。
まあ、mallocの勉強はこんなもんでいいかなあ。本当はこれからarenaという機構を導入した、mallocの並列化とかもあるんですけど一旦mallocの勉強はやめてソース読むなり別の勉強するなりしようかと思ってます。
今回のmallocお勉強では結構簡単なとこだけ触れたんですが中々にbrain damegedでした。
freelistのヘッダーに一個フラグをつけたいが、メンバ変数増やしたくない→ポインタの下位2bitは絶対０だからそこをフラグとして扱おう！
freelistのこのメンバ変数ってfreeされてる時は使うけど、mallocされたらいらないんじゃね？→じゃあ破壊してもいいや
的な。僕程度から見たら危なっかしいんですが、これで大丈夫らしいです……。まあ確かに動いてはいますし。
malloc結構奥が深くて面白かったです。機会があったらarenaの勉強もしてみようかな。