はじめに
この記事は Akatsuki Advent Calendar 2017 の22日目の記事です。どんな記事を書こうか色々模索しましたが、自分の得意な話が一番書き進められたので、この話を書いてみました。
この記事の対象者
C言語でプログラムするとき、動的にメモリを確保するのに
int * a = (int*)malloc(sizeof(int) * n); // int n個分
とかやると思いますが、このmallocで帰ってくるメモリがどこから来るか答えられる人は居ますか？バッチリ答えられるという人、glibcのソースコードを読んだことある人は帰っていただいて大丈夫です。メモリは天から降ってくる恵みだと思っている人、学校では習った気がするけど実はよく知らないという方はこの記事を読むとよいと思います。
C言語でプログラムを書かないから関係ないという方も一読してみてください。C++でプログラムを書いたとしても、new演算子で動的にメモリを確保する際には内部でmallocが使われています。他の言語で書いている場合でも動的なメモリの確保の際、密かにmallocのお世話になっているのです。少しでもメモリの気持ちがわかることで、メモリに優しいプログラム、メモリ不足でクラッシュしにくいプログラムを書くことができるようになります。
なお、malloc関数はシステムコールではなくライブラリなので、ライブラリの実装によるというのがある意味正解ではありますが、それを言ってしまうと先へ進めないので、この記事ではlinux系OSのデファクトで用いられるglibcでの実装についてお話ししようと思います。
mallocのメモリ割り当て戦略
mallocのメモリはヒープから割り当てられると学校で習った方も多いかもしれません。それは半分正解ですが、半分は間違っています。mallocで割り当てられる領域は下図のように２種類存在します。
このように、必要なサイズに応じて、ページから割り当てられる場合と、ヒープから割り当てられる場合にわかれます。以降はそれぞれの仕組みについて詳しく説明して、なぜ、サイズに応じて２つの仕組みが使い分けられるかを解説していきます。
ページとはなんぞや
最近のCPU(x86、ARM、MIPSなど)にはMMUと呼ばれるメモリを管理するためのデバイスが付いています。このMMUには、実際に存在するメモリ(物理メモリ)から細かい領域をかき集めてきて、１つのつながったメモリとして見せる仮想メモリという機能があります。この細かい領域の単位のことをページと呼びます。図解すると次のようなイメージです。
この機能を使うことで、物理メモリの空いている領域を集めてきて、大きな領域を確保するということができるようになります。この仕組みであれば、後述するフラグメンテーションの問題も起こらず、いいことづくめのようで、じゃあこれで全部賄えばいいじゃんということにもなりそうですが、残念ながらそうはいきません。
この仕組みを実現するためにはページがどの状態にあるか(使用中か、解放済かなど)を管理するためのテーブル(ページテーブル)が必要になります。このテーブルもメモリ上に載せなければいけませんが、このテーブルのサイズを現実的に収めるためにはそれなりに大きいサイズで区切らないといけません。
linuxのページサイズは伝統的に4KBが用いられてきましたが、近年のメモリサイズの増大により2MBなどの大きなページサイズ(Large Page)もよく用いられるようになりました。仮にページサイズ4KBのシステムで動いているとすると、このシステムで割り当てることのできる最小のサイズは4KBということになります。つまり、mallocで1バイトとか2バイトのメモリを要求したとしても、4KBのメモリが割り当てられてしまうことになります。これはメモリの利用効率としてよいものではないですね。ゆえに小さいメモリ領域に関しては後述するヒープによってメモリを確保する必要が出てきます。
ヒープとはなんぞや
次にヒープについて説明します。ヒープとは下図のようにメモリ領域を先頭にヘッダーをつけた細かい領域に分割し、その細かい領域をリンクリストでつないだ構造を指します。
mallocでメモリを割り当てるには、freeのデータのリストをたどっていって、所望のサイズ以上の領域が見つかったらその領域を切り取って返せばよいということになります。
freeのデータリストをたどって最初に見つかった領域を返すアルゴリズム(first fit)がプログラミング言語C(かの有名なK & R)という本に載っていて、初期のUNIXでは実際に使われていたそうですが、どうせなら、要求に近いサイズの領域を返してあげた方(best fit)がよい気がしますよね。とはいえ、リストの最初から最後まで舐めて最適の領域を見つけるのはとても計算量がかかってよくありません。そのためにglibcではfreeサイズのレンジ毎にリストを分割することでなるべく最適な領域を見つけられるように改善しています。
フラグメンテーション
万能とも思えるヒープですが、ヒープでメモリを確保する場合、どうしてもフラグメンテーションという問題がつきまといます。
例えば、ヒープ領域が10KBあるとしましょう。
- 5KBをmalloc
- 1KBをmalloc
- 5KBをfree
という順番に処理を行うと、
(※ 細かいのでヘッダー部分は除いています)
上記のようなメモリ配置になってしまうため、空き領域としては9KBあることになりますが、最大で確保できるサイズが5KBになってしまいます。この現象がフラグメンテーション(断片化)です。フラグメンテーションが起こると空き領域としては十分あるように見えるにもかかわらず、mallocで必要なサイズを取ってこられないという現象が発生します。
メモリに優しいプログラミング
以上を踏まえて、メモリに優しいプログラミングとはどういうものかを考えます。
フラグメンテーションの課題があるヒープ領域のことを考えると、
なるべく小さなメモリ領域のmallocは行わない
ということを気をつけていただけるといいかなと思います。オブジェクト指向のプログラミングをされていれば、自然とデータは意味のある構造体の形にまとまるはずです。その構造体をなるべく予測の付く範囲内でまとめて確保することで、フラグメンテーションの起こりにくいプログラムを書くことができます。
int * x = (int*)malloc(sizeof(int));
みたいなコードを書いたら、私からしばかれることは間違いないです(笑)
またこれもフラグメンテーションを避けるために、
なるべくmalloc、freeの頻度を下げる
を意識していただけるとよいです。例えば、とあるメソッドでデータのentityを渡すといった処理を書いた場合、そのメソッドを呼ぶたびにmallocして、処理が終わったら解放というように書くこともできますが、なるべく領域を使い回せるように工夫すべきです。メソッドの引数に格納領域へのポインタを渡す、C++であればshared_ptrを使って領域を使い回すなどのテクニックを利用して、不必要なmalloc、freeを削減することができるでしょう。またメソッド内で使い捨てる変数であればなるべくスタック(ローカル変数)を利用するようにしましょう。
マルチスレッドで扱う場合はどうなる？
mallocをマルチスレッドで扱った場合どうなるか考えてみましょう。もし複数のスレッドでヒープのリンクリストを触ったら当然ですが壊れます。それは困るのでglibcではリンクリストに対して、mutexを使ってロックをかけて扱うようにしています。確かにそうすれば安全にアクセスできるようになりますが、今度はmallocを実行できるのが1スレッドに限られてしまうため、スレッドの持つ並列性が損なわれることにつながります。この課題を改善するために、glibcでは競合するスレッドではヒープ領域を別々に扱える仕組みを導入しています(Arena)。しかし、これも万能ではなく、別々に扱うことで１つだった場合に比べてメモリを速く食い潰してしまう可能性があったり、複数のロックを扱うことによるパフォーマンスへのペナルティがあったりします。よってマルチスレッドでなるべくmallocを扱わないようにした方が、メモリに優しいプログラミングと言えます。
例えばデザインパターンでいうworkerパターンを用いる場合、work領域はメインスレッドで確保して、そのポインタをworkerに渡してやることで、workerスレッド側でmallocを呼び出すという行為を回避することができます。
参考になる資料
こちらのスライドは私が述べたところを全て押さえていてわかりやすくてオススメです。
https://www.slideshare.net/kosaki55tea/glibc-malloc
他にも似たようなことを勉強している記事がありました
malloc初級編
malloc中級編
まとめ
glibcにおけるmallocの挙動を解説し、メモリに優しいプログラムの書き方を少しだけお話ししました。プログラミング初心者、中級者の方々に是非理解していただいてプログラミングのレベルアップをしていただけるとうれしいです。