1月版　無視できないフラグメンテーション問題への解答は？

小崎資広
2010/2/10

　当初、今回はmemory compactionとtransparent hugepageという2つのトピックを取り上げ「Hugepage大特集」にしようと思っていたのですが、並列プログラミングカンファレンスに触発され（正確には、そのカンファレンスに参加できなくて悔しかったことに触発され）、後者を急きょ、ロックレスネタに差し替えて紹介します。

　でもこれが大失敗で、調査が大変過ぎて泣けたうえに、スケジュールがとんでもないことに。人間、思い付きで行動してはいけないといういい見本ですね。

Melの悲願なるか？ Memory Compactionチャレンジ

　Mel Gormanは、Memory Compaction v1パッチシリーズを投稿しました。これは「Linuxメモリ管理の最先端を探る」で説明したAnti Fragmentationパッチを拡張して、フラグメンテーションが増えてきた場合にデフラグを行う機能です。

■余談

実のところ経緯は逆です。Melは数年前に、メモリデフラグパッチをLKMLに投稿したのですが、デフラグ嫌いのLinusが登場。ビッグ・フレームウォーを起こした挙げ句、NAK（却下）されてしまったという悲しい過去があります。その後Melは方針を変更し、デフラグ機能本体は削除して、メモリ割り当て時にフラグメンテーションを起こしにくい構造に割り当てる機能（anti fragmentation）のみをマージさせました。今回のパッチはそれに対する捲土（けんど）重来になるか、注目です。

　背景には、

（a）近年、パケット受信用に連続するページを要求する無線LANデバイスが増え、フラグメンテーションが原因となってメモリ確保に失敗する事例が多く報告されるようになった

（b）標準的なシステムが搭載するメモリ容量が増えるに従い、Hugepageの利用は増加傾向にあり（注1）、かつOS起動後にHugepage量を変更する使用例が増えてきた

といった理由から、フラグメンテーションの問題がますます無視できなくなってきたという事情が挙げられます。

　さて、デフラグ処理をしようとすると、まず「フラグメンテーションとは何か」を定義しなければいけません。そのためこのパッチは、システムのメモリフラグメンテーションの度合いを測定する2つの指標、「unusable_index」と「fragmentation_index」を導入します。

式1

式2

requested	要求する連続ページ数
free_pages	空きページ数（空きメモリ量／ページサイズ）
free_blocks_total	バディアロケータが管理している空きブロックの数
free_blocks_suitable	要求する連続ページ以上の大きさを持つ空きブロックの数

　簡単にいうと、unusable_indexは「まだメモリを獲得できる状況において、フラグメンテーションにより使えなくなっているページの割合」で、fragmentation_indexは「もうメモリ獲得がまったくできない状況における、空きメモリ量とフリーリスト中のメモリブロック数の割合」を示しています。どちらも数値が大きいほどフラグメントが進んでいることを示します。unusable_indexは、requestedパラメタで与えられた連続ページがもう獲得できないときは「1」になります。

　前者の方がより直感的な指標ですが、大きな連続ページの割り当て（Hugepageの割り当てなど）の場合は、指標が常に1（まったく使えるメモリがない）に張り付いてしまいます。このため、内部的なコンパクション開始のトリガーとしては使いにくいものがあります。

　後者は、Linuxが採用している、バディアロケータが連続する空きメモリを1つのブロックにまとめる性質を利用して、「空きブロック数：空きページ量」という図式でフラグメンテーションを定義しています。具体例を以下に示します。

（図をクリックすると拡大します）

　これらの指標は、/proc/pagetypeinfoでも見ることができます。例えば、筆者のシステムでは以下のように表示されました。

Unusable free space index at order

Node    0, zone      DMA                         0      8      8      8      8     40    104    232    488   1000   1000

        Node    0, zone    DMA32                         0      7     44     92    394    697    697    697   1000   1000   1000


      Fragmentation index at order

        Node    0, zone      DMA                        -1     -1     -1     -1     -1     -1     -1     -1     -1    781    835

        Node    0, zone    DMA32                        -1     -1     -1     -1     -1     -1     -1     -1    936    956    966

　読み方ですが、左から順に、order-0（1ページ）からorder-10（1024ページ連続）のメモリ割り当て要求に対する11種類の指標が表示されています。

　なお、表示される値は、上記の式で得られる値を1000倍した整数値です。例えばDMA32ゾーンは、order-0からorder-7までunusable_indexが徐々に上がっていき、order-8からは1000になります。そしてそれに合わせるように、fragmentation_indexはorder-0からorder-7までは-1（測定不能）であり、order-8からorder-10まで徐々に値が上がっていきます。

　つまり、order-8（2^8=256page＝1MB連続）以上のページを割り当てるならば、ページキャッシュを捨てるかコンパクションを行わないと、メモリ割り当てが成功しそうにない、ということを示しています。

　なお、order-0ではもちろんフラグメンテーションは発生しようがないので、表示には意味がありません。しかし、同じファイル中のフラグメント指標以外の項目（本例では表記を省略しました）と表示をそろえるために、このような表示になっています。

　さて、フラグメンテーション指標が定義できたので、次は「いつコンパクションを起動するか」を決めるわけですが、現在は、メモリ割り当てに失敗しメモリ回収を始める直前に「fragmentaion_indexが0.5を超えていたらコンパクションする」という単純な起動ロジックになっています。この0.5という閾（しきい）値はどうも便宜的なもので、あまり深い意味はないそうです。うーん、ええんかな。

　起動したコンパクション本体の動きはとてもシンプルです。Melのコンパクションは、物理アドレスの低位にあるページを高位に移動させ、低位に連続空きメモリを作るという論理です。このために

低位から順番に、ページの物理的な位置が変わっても問題のないページを見つける
高位から順番に空きページを見つける
（1）のページを（2）の場所に移動させる

　という3つの手順を踏む必要があることが分かります。

　（1）はページアウトであり、ディスクに追い出せるページならば移動もできるはずだ、と気付けば、単にページアウト用のLRUにつながっているかどうかで判定できると分かります。（2）はもっと簡単で、バディアロケータのフリーリストにつながっているものが空きページである判定できます。そして（3）のページ移動に関しては、mbind()システムコールのMPOL_MF_MOVEの内部処理であるページマイグレーションコードがそのまま利用できます。

　このようにMelのパッチには、技術的にはかなり面白いテクニックがいろいろ入っています。しかし筆者の感想では、現状のパッチはまだ粗削り過ぎ、以下の対応が必要ではないかと考えています。

現状はゾーン単位でしかコンパクションを行わないが、DMA領域枯渇を防ぐため、DMAゾーンから高位ゾーンへと、ゾーンをまたいだページ移動を行った方がよい
mlockされたページは、ページアウト可能ではないがコンパクション可能なはず
メモリが足りないことが確定してからコンパクションを行うのは、速度的にいかがなものかと思われるので、kswapdと統合し、バックグラウンドでコンパクションした方がよい

　このあたりは、今後議論を詰めていきたいところです。

注1：例えばx86では2MBのHugepageを作成できますが、CPUアーキテクチャの制約上、作成するには2MBの物理アドレス的に連続な領域が必要です。2MB＝4KB（通常ページのページサイズ）×512ですから、普通にOSを動かしているとまず空いていません。

■LKML名言集：It's not "Linus C"

　思い付きで面白メールを紹介するコーナー（不定期）を作ってみました。

kernel/kfifo.c:83:35: warning: Using plain integer as NULL pointer


         buffer = kmalloc(size, gfp_mask);

         if (!buffer) {

  -                _kfifo_init(fifo, 0, 0);

  +                _kfifo_init(fifo, NULL, 0);

　LKMLにこんなパッチを投稿した人がいたのですが、そこで出てきた意見が、

Stefani Seibold「どうやってこのwarningを得たのか知らないけど、ANSI C standardでは、0をNULLのつもりで渡すのは正しいよ」

Andi Kleen「それは『Linus C』じゃない。sparse（注2）はそういうふうには実装されてないんだよ」

　「Linus C」っていう表現があるんですね。matz lispみたいなものかな？（←違います）

注2：Linusによって作られたC言語構文チェッカー。make C=1でカーネルビルドすると有効になる。ユーザー空間へのポインタを示す__userなど、Linux独自のアノテーションを解釈して、警告を出してくれる。

2009年12月版へ

1/2

Index
Linux Kernel Watch　1月版　無視できないフラグメンテーション問題への解答は？

	Page 1 　Melの悲願なるか？ Memory Compactionチャレンジコラム　LKML名言集：It's not "Linus C"
	Page 2 　ユーザー空間でRCU？ membarrier()システムコールとは

連載 Linux Kernel Watch

　Linux Squareフォーラム Linuxカーネル関連記事

	連載：Linux Kernel Watch（連載中） Linuxカーネル開発の現場ではさまざまな提案や議論が交わされています。その中からいくつかのトピックをピックアップしてお伝えします
	連載：Linuxファイルシステム技術解説ファイルシステムにはそれぞれ特性がある。本連載では、基礎技術から各ファイルシステムの特徴、パフォーマンスを検証する
	特集：全貌を現したLinuxカーネル2.6［第1章］エンタープライズ向けに刷新されたカーネル・コアついに全貌が明らかになったカーネル2.6。6月に正式リリースされる予定の次期安定版カーネルの改良点や新機能を詳しく解説する
	特集：/procによるLinuxチューニング［前編］ /procで理解するOSの状態 Linuxの状態確認や挙動の変更で重要なのが/procファイルシステムである。/procの概念や/procを利用したOSの状態確認方法を解説する
	特集：仮想OS「User Mode Linux」活用法 Linux上で仮想的なLinuxを動かすUMLの仕組みからインストール／管理方法やIPv6などに対応させるカーネル構築までを徹底解説
	Linuxのカーネルメンテナは柔軟なシステムカーネルメンテナが語るコミュニティとIA-64 Linux IA-64 LinuxのカーネルメンテナであるBjorn Helgaas氏。同氏にLinuxカーネルの開発体制などについて伺った
	more

MONOist組み込み開発フォーラムの中から、Linux関連記事を紹介します

Linux ＆ OSS フォーラム新着記事

【 pidof 】コマンド――コマンド名からプロセスIDを探す （2017/7/27）
本連載は、Linuxのコマンドについて、基本書式からオプション、具体的な実行例までを紹介していきます。今回は、コマンド名からプロセスIDを探す「pidof」コマンドです。
Linuxの「ジョブコントロール」をマスターしよう （2017/7/21）
　今回は、コマンドライン環境でのジョブコントロールを試してみましょう。X環境を持たないサーバ管理やリモート接続時に役立つ操作です
【 pidstat 】コマンド――プロセスのリソース使用量を表示する （2017/7/21）
本連載は、Linuxのコマンドについて、基本書式からオプション、具体的な実行例までを紹介していきます。今回は、プロセスごとのCPUの使用率やI/Oデバイスの使用状況を表示する「pidstat」コマンドです。
【 iostat 】コマンド――I/Oデバイスの使用状況を表示する （2017/7/20）
本連載は、Linuxのコマンドについて、基本書式からオプション、具体的な実行例までを紹介していきます。今回は、I/Oデバイスの使用状況を表示する「iostat」コマンドです。