メモリのデフラグはどうやって動いてる？　Linux Kernelの「Compaction」にみる断片化解消の仕組み

メモリの虫食い状態を緩和するデフラグメンテーション

齊加匠氏：「Deep Dive into the Linux Kernel　メモリ管理におけるCompaction機能について」というタイトルで株式会社エヌ・ティ・ティ・データの齋加が発表します。

自己紹介です。所属は株式会社エヌ・ティ・ティ・データで、業務はアプリケーション開発です。OSは関係ないんですが、アプリケーション開発をしていて、主にSpringを使っています。好きなものはGolangやArch Linuxです。かねてよりメモリ管理に興味があって、Linux Kernelのメモリ管理について詳しく知ってみたいと思っていたので、今回はCompactionを見てみようと思いました。

テーマの方針ですが、今回はCompaction機能について調査しました。具体的には、Linux Kernelのコードを読んでどういう処理を行っているか、仕組みや工夫点を調査しました。使用したKernelのバージョンは5.8.2です。

そもそもCompactionとは何かというところですが、これはフラグメンテーションを緩和する手法で、つまりデフラグ（デフラグメンテーション）です。フラグメンテーションとは何かというと、メモリに対してallocationとdeallocationを繰り返していると、メモリが虫食い状態になって、使用可能な連続した領域が少なくなってしまう現象です。Compactionはこれを緩和する手法です。

デフラグメンテーションの仕組み

具体的にそれをどう緩和するのか仕組みの概要です。LWN（https://lwn.net/）によると、まず2つの探索が走ります。1つ目は低位から高位へ動かせるページを探索する処理で、もう1つは高位から低位へとフリーなページを探索する処理です。この2つの探索が走ります。

2つの探索がぶつかると、探索を止めてmovable pagesからfree pagesへ移動する仕組みになっています。ここでいうpageとはphysical pageのことです。

「memory isolation」で性能の向上を図っている

実際に処理のソースコードを見ていきます。これはCompaction.cですが、処理の工夫点はここですね。memory isolationをやっています。これは候補のリストを作って、それを操作しています。つまり、Compactionの処理中にページのロックをつかみ続ける必要がないので、性能が向上するという工夫がされています。

全体の呼び出し関係

全体の呼び出し関係についてちょっと見ていきます。Compactionの処理は基本的にCompaction.cに書かれています。そもそもpage_alloc.cから呼び出されて、_try_to_compact_apgesからcompact_zone_order、そこからcompact_zoneを呼び出します。zoneというのはメモリの分割単位です。

そこ（compact_zone）から2つに分かれています。movable pagesを探す処理のisolate_migratepagesとfree pagesを探す処理のisolate_freepagesです。この2つが対応する関係になっています。compact_zone_orderから呼び出されたmigrate.cのmigrate_pagesで、実際にページマイグレーションを行っています。

まずisolate_migratepagesについてソースコードを見ていきたいと思います。「//略」と書いているところには、本当は多くのコードがあるのですが、説明の都合上、主要な箇所を抜粋しています。これはmovable pagesを探す処理になっているんですが、for文でループが回っていて、低位から高位へとループが回ってmovable pagesを探索します。実際に実行する処理はisolate_migratepages_blockに実装されています。ブロックとメモリを分割する単位です。

次にisolate_freepagesを見ていきたいと思います。ここも先ほどの処理と対応していて、for文があって、今度は逆に高位から低位へfree pagesを探索する処理が行われています。実際の処理は、isolate_freepages_blockに実装されています。

次にcompact_zoneについて見ていきたいと思います。ゾーンもメモリの分割単位ですが、これをcompactionする処理になっています。ここではwhileでループが回っていて、停止条件はcompact_finishedです。

このcompact_finishedはcompact_scanners_metを呼び出しています。その実装はこの資料には記載してないのですが、free pages scannerがmovable pages scannerよりも低位にいた場合、つまりぶつかった場合に止まるように実装されています。

コードを見ると、isolate_migratepagesが呼び出されていたり、compaction_allocがisolate_freepagesを呼び出しており、それらをマイグレートします。

次はそのcompact_zoneから呼び出されているのを実際にマイグレートする処理ですね。migrate.cのmigrate_pagesを見ていきたいと思います。これは実際にマイグレートしている処理なんですが、ここに関してループが回っていて、10回試す、もしくはmovable pagesがない場合にリターンするという処理です。

実際にマイグレートしているのはこのunmap_and_moveという部分で、free pagesにマイグレートする処理が行われています。

まとめです。まずCompactionはデフラグ（デフラグメンテーション）の手法です。Compactionの機能について、実際にどう動作しているのか、Kernelのソースコードレベルで今回は把握できたんじゃないかなと思います。Compactionの基本の原理自体は既知だったんですが、どのようにコードレベルで動作しているのかを解説した資料はたぶんなかったので、そこについて今回発表できたと思います。

実装の工夫点として、memory isolationで行うことで性能向上を図っていることがわかりました。以上で発表を終わります。ありがとうございました。