Linux メモリ断片化 (外部フラグメンテーション) の概要と解消方法

■ 記事概要

Linux OS におけるメモリ断片化 ¹ ( 以降、断片化 ) について、調査したことのまとめ。

■ 要約

• 断片化していると、空きメモリが十分あるにも関わらず、メモリ確保に失敗することがある。

• 断片化の影響を受けるのは、DMA ( Direct Memory Access ) のように物理メモリ領域を直接参照する必要があるもの ( 仮想メモリを使える場合は、物理メモリ領域が連続している必要がないため影響なし )。

• 断片化のレベルは /proc/buddyinfo や /sys/kernel/debug/extfrag/unusable_index から確認可能。

• 明示的に断片化を解消する方法は、OS 再起動と、# echo 1 > /proc/sys/vm/compact_memory がある。

■ 物理メモリ領域について

断片化の話の前に物理メモリ領域について整理する。

• Linux では、図 1 のように物理メモリ領域をページサイズ単位 ( # getconf PAGE_SIZE )に分割して管理している。
• 分割された領域をページフレーム ( あるいは、物理ページ、実ページ ) と呼ぶ。
• 物理メモリの割り当てと解放はこのページフレームの単位で行われる。
• 要求されるメモリ量によって、割り当てられるページフレームの個数も変わる。1個分のページフレームで済むこともあれば、2個分、4個分 ( あるいは、それ以上 ) 要求されることもある。

図 1 : 物理メモリ領域

　　　青 ... 割り当て済みのページフレーム
　　　白 ... 空きページフレーム

■ 断片化とは

断片化とは、空きメモリが十分あるにも関わらず、メモリ確保に失敗する状態。

図 2 のような物理メモリ領域が、連続するページフレームの割り当てと解放の繰り返しにより、図 3 のような割り当て済みのページフレーム郡の間に、小さな空きページフレームが散らばって存在する状態 ( 「虫食い」状態 ) となる。図 2 では最大で4個分の連続する空きページフレームがあるのに対し、図 3 では、最大2個分で、単一の空きページフレームも多い。

図 2 : 断片化が進んでいない物理メモリ領域

図 3 : 断片化が進んだ物理メモリ領域

このように断片化が進むと、空きページフレームが十分 ( 空きメモリが十分 ) でも、連続するページフレームの割り当てに失敗 ( メモリ確保に失敗 ) することがある。たとえば 図 3 の状態では、最大でも2個分の連続する空きページフレームしかないため、それより多くの連続する空きページフレームが要求されると、メモリ確保に失敗する。

ここで重要なのは、連続する空きページフレーム ( 物理的に ) が要求された場合ということ。そもそも、Linux では仮想メモリ（ ページテーブル ） があり、物理的に連続していなくとも、仮想メモリ上で連続しているように見せることができる。よって、仮想メモリを使用できる場合は、断片化の影響がない。影響があるのは、DMA のように物理メモリ領域を直接参照する必要があるもの ( デバイスドライバからの要求など ) ²。

■ 断片化のレベル

/proc/buddyinfo から確認できる。

これは、Buddy System という物理メモリ割り当てのアルゴリズムによって管理された連続する空きページフレームの状態。Buddy System では、連続する空きページフレームを2のべき乗の大きさ ( 2^0、2^1...2^10 )毎に分類、管理している。実行例 1 の 9569 などは、2^0 の大きさ ( 1個分の連続する空きページフレーム ) を持つ空きページフレームの総数を示す。

断片化のレベルが高い場合、実行例 1 にある 9569 55888 18209 など左側にある数値が大きく、右側にある数値が小さくなっていく。これは、小さな空きページフレームの総数が多く ( 1個や2個の連続する空きページフレームが多く )、大きな空きページフレームの総数が少ないということを示すため、断片化のレベルも高い。

実行例1

root@lnxmnt19:~# cat /proc/buddyinfo 
Node 0, zone      DMA      4      2      1      3      2      2      0      0      1      1      3 
Node 0, zone    DMA32  64115  51522  24898   6071    604     19      0      0      0      0      0 
Node 0, zone   Normal   9569  55888  18209   1637    262     29      1      0      0      0      0
### comment: order       2^0    2^1    2^2    2^3    2^4    2^5    2^6    2^7    2^8    2^9   2^10

これらについて 図 4 で補足する。見て分かるとおり、 連続する空きページフレームは $2^{0}( 1個分)$ から $2^{10}(1024個分)$ までの 11 種類の大きさ ( 連続する空きページフレーム ) 毎に分類され、それぞれがリストを持っている。この図で言うと、$2^{0}$ の大きさを持つ空きページフレームの総数は4つ、$2^{1}$ なら4つ ... $2^{2}$ なら2つとなる ( 以降、省略 )。実行例 1 にある数値はこんなイメージ ( なお、DMA、DMA32、Normal とは、ZONE という用途ごとに分けられた物理メモリの領域。ページフレームは、この ZONE ごとに管理されている )。

図 4 : 連続する空きページフレームのリスト

■ 断片化のレベル ( その2 )

実行例2

root@lnxmnt19:~# cat /sys/kernel/debug/extfrag/unusable_index
Node 0, zone      DMA 0.000 0.001 0.002 0.003 0.009 0.017 0.033 0.033 0.033 0.097 0.226 
Node 0, zone    DMA32 0.000 0.197 0.514 0.820 0.968 0.998 1.000 1.000 1.000 1.000 1.000 
Node 0, zone   Normal 0.000 0.160 0.688 0.925 0.980 0.995 0.999 1.000 1.000 1.000 1.000
### comment: order      2^0   2^1   2^2   2^3   2^4   2^5   2^6   2^7   2^8   2^9  2^10

基本的な見方は、/proc/buddyinfo と同じ。こちらの場合は、利用不可な連続する空きページフレームのブロックの割り合いを示す。値が 0.000 に近づくほど、利用可能なブロックの数が多く、1.000 に近づくほど、利用可能なブロックの数が少ない。

■ 断片化を解消する術

断片化を解消する方法はいくつかある。

1. OS を再起動する

OS を再起動すれば、解消される。

2. OS を再起動しない方法

/proc/sys/vm/compact_memory に 1 を書き込む ³。

# echo 1 > /proc/sys/vm/compact_memory

Linux kernel 内のドキュメント ( /Documentation/sysctl/vm.txt )によると、1 を書き込むと、すべての ZONE (用途別に分けられた物理メモリの領域) が圧縮され、可能な限りの連続する空きページフレームが利用可能になるとのことです。ただし、この機能を利用するには、CONFIG_COMPACTION を有効にする必要あり ⁴。

3. 何もしない

前述の Buddy System によりメモリ回収の際に、割り当て済みのブロックが解放されると、解放されたブロックは隣合う同じ大きさの塊と結合 ( Buddy...仲間、相棒の意味 )し、可能な限り、より大きな塊へ変わる動きをするため ( たとえば、$2^{0}$ の塊同士が結合し、1つ大きな $2^{1}$ の塊となる )、特に何もしなくても、自然と断片化が解消することもある。

明示的に断片化を解消したい場合 ( 緊急時など ) は、前述の方法を使う。

■ compact_memory の効果

# echo 1 > /proc/sys/vm/compact_memory の効果が気になったので確認。

環境情報

root@lnxmnt19:~# lsb_release -d
Description:	Linux Mint 19.1 Tessa

root@lnxmnt19:~# uname -r
4.15.0-20-generic

効果確認用のスクリプト

#!/bin/bash

echo "--------------------------------------------------------------------------------"

cat /proc/buddyinfo

echo "--------------------------------------------------------------------------------"

cat /sys/kernel/debug/extfrag/unusable_index

echo "--------------------------------------------------------------------------------"

# 記事には説明なし。説明割愛。
cat /proc/vmstat | grep compact　

echo "--------------------------------------------------------------------------------"

# 記事には説明なし。説明割愛。
cat /proc/pagetypeinfo

実行前の状態

root@lnxmnt19:~# ./memory_fragment.sh 
--------------------------------------------------------------------------------
Node 0, zone      DMA      4      2      1      3      2      2      0      0      1      1      3 
Node 0, zone    DMA32  50311  43673  29118  12645   2612    281     27      3      1      1      0 
Node 0, zone   Normal  19659  17036   8875   3676    184      4      2      0      0      0      0 
--------------------------------------------------------------------------------
Node 0, zone      DMA 0.000 0.001 0.002 0.003 0.009 0.017 0.033 0.033 0.033 0.097 0.226 
Node 0, zone    DMA32 0.000 0.123 0.336 0.621 0.868 0.970 0.992 0.997 0.998 0.998 1.000 
Node 0, zone   Normal 0.000 0.161 0.441 0.732 0.973 0.997 0.998 1.000 1.000 1.000 1.000 
--------------------------------------------------------------------------------
compact_migrate_scanned 36380
compact_free_scanned 618680
compact_isolated 37028
compact_stall 0
compact_fail 0
compact_success 0
compact_daemon_wake 40
compact_daemon_migrate_scanned 36380
compact_daemon_free_scanned 618680
--------------------------------------------------------------------------------
Page block order: 9
Pages per block:  512

Free pages count per migrate type at order       0      1      2      3      4      5      6      7      8      9     10 
Node    0, zone      DMA, type    Unmovable      4      2      1      3      2      2      0      0      1      0      0 
Node    0, zone      DMA, type      Movable      0      0      0      0      0      0      0      0      0      1      3 
Node    0, zone      DMA, type  Reclaimable      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type   HighAtomic      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type          CMA      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone    DMA32, type    Unmovable   1170    752    360    109     16      0      0      0      0      0      0 
Node    0, zone    DMA32, type      Movable  45945  40069  26433  11110   2023     71      1      0      0      0      0 
Node    0, zone    DMA32, type  Reclaimable   3196   2852   2325   1426    573    210     26      3      1      1      0 
Node    0, zone    DMA32, type   HighAtomic      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone    DMA32, type          CMA      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone    DMA32, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone   Normal, type    Unmovable    364    227    194      3      0      0      0      0      0      0      0 
Node    0, zone   Normal, type      Movable  18214  16217   8479   3387    119      0      0      0      0      0      0 
Node    0, zone   Normal, type  Reclaimable   1077    602    190    280     60      0      0      0      0      0      0 
Node    0, zone   Normal, type   HighAtomic      5      5     12      6      5      4      2      0      0      0      0 
Node    0, zone   Normal, type          CMA      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone   Normal, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 

Number of blocks type     Unmovable      Movable  Reclaimable   HighAtomic          CMA      Isolate 
Node 0, zone      DMA            1            7            0            0            0            0 
Node 0, zone    DMA32           15         1019          110            0            0            0 
Node 0, zone   Normal          124         2573          241            1            0            0 

実行後の状態

root@lnxmnt19:~# ./memory_fragment.sh 
--------------------------------------------------------------------------------
Node 0, zone      DMA      4      2      1      3      2      2      0      0      1      1      3 
Node 0, zone    DMA32   3914   3343   3081   2300   1471    983    637    416    262    182     57 
Node 0, zone   Normal   1471   1279   1387    916    417    215    141     86     50     45     31 
--------------------------------------------------------------------------------
Node 0, zone      DMA 0.000 0.001 0.002 0.003 0.009 0.017 0.033 0.033 0.033 0.097 0.226 
Node 0, zone    DMA32 0.000 0.009 0.025 0.056 0.101 0.158 0.235 0.335 0.465 0.629 0.857 
Node 0, zone   Normal 0.000 0.012 0.034 0.081 0.143 0.199 0.258 0.334 0.427 0.536 0.731 
--------------------------------------------------------------------------------
compact_migrate_scanned 591336
compact_free_scanned 1933859
compact_isolated 379231
compact_stall 0
compact_fail 0
compact_success 0
compact_daemon_wake 40
compact_daemon_migrate_scanned 36380
compact_daemon_free_scanned 618680
--------------------------------------------------------------------------------
Page block order: 9
Pages per block:  512

Free pages count per migrate type at order       0      1      2      3      4      5      6      7      8      9     10 
Node    0, zone      DMA, type    Unmovable      4      2      1      3      2      2      0      0      1      0      0 
Node    0, zone      DMA, type      Movable      0      0      0      0      0      0      0      0      0      1      3 
Node    0, zone      DMA, type  Reclaimable      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type   HighAtomic      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type          CMA      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone      DMA, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone    DMA32, type    Unmovable   1158    747    363    108     17      1      0      0      0      0      0 
Node    0, zone    DMA32, type      Movable   1198   1211   1354   1160    913    750    556    394    253    171     54 
Node    0, zone    DMA32, type  Reclaimable   1558   1385   1364   1032    541    232     81     22      9     11      3 
Node    0, zone    DMA32, type   HighAtomic      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone    DMA32, type          CMA      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone    DMA32, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone   Normal, type    Unmovable    453    227    186      3      1      0      1      1      1      1      0 
Node    0, zone   Normal, type      Movable    664    622    672    531    349    211    138     85     49     44     31 
Node    0, zone   Normal, type  Reclaimable    280    426    526    376     62      0      0      0      0      0      0 
Node    0, zone   Normal, type   HighAtomic      5      5     12      6      5      4      2      0      0      0      0 
Node    0, zone   Normal, type          CMA      0      0      0      0      0      0      0      0      0      0      0 
Node    0, zone   Normal, type      Isolate      0      0      0      0      0      0      0      0      0      0      0 

Number of blocks type     Unmovable      Movable  Reclaimable   HighAtomic          CMA      Isolate 
Node 0, zone      DMA            1            7            0            0            0            0 
Node 0, zone    DMA32           15         1019          110            0            0            0 
Node 0, zone   Normal          126         2571          241            1            0            0 

結果は次のとおり。

左が実行前、右が実行後。

order の小さな塊は減少し、大きな塊は増加している。たしかに断片化のレベルが緩和しているように見える。

■ さいごに

個人的には、まだまだ調べ足りない気がしますが、この辺で一旦終了。もう少し中身の部分にまで触れたかったけど、調べれば調べるほどハマっていく感じがあり、終わりが見えないなあと。

以下、調べきれなかったこと / 調べたいこと

• カーネルメモリ割り当てに使用する関数の違いが断片化に影響するかどうか。kmalloc() は物理的に連続する領域を確保することを保証するのに対し、vmalloc() は保証しない。つまり、断片化の影響があるのは、kmalloc() で vmalloc() では影響がないように見えるけど、実際はどうなんだろう。
• IOMMU やスキャッターギャザー DMA なら、断片化の影響受けないっぽいけど本当かどうか。これらの仕組みの理解。
• cat /proc/vmstat | grep compact で見える compact_migrate_scanned、compact_free_scanned、compact_isolated の意味。
• Buddy System などの実装周り。

断片化を理解するには、もっと勉強が必要そうです。

■ 参考

• LWN.net: Memory compaction
• LWN.net: A reworked contiguous memory allocator
• System-wide Memory Defragmenter Without Killing any application
• Continuous Memory Allocator - Allocating big chunks of physically contiguous memory
• Memory Allocation Guide
• 無視できないフラグメンテーション問題への解答は？
• メモリ管理、Buddyシステム、kmalloc、スラブアロケータ
• 詳解 Linuxカーネル 第3版

1. タイトルのとおり、外部フラグメンテーションのこと。内部フラグメンテーションについて言及しない。 ↩

2. ただし、IOMMU やスキャッターギャザーを使っている場合は、物理メモリ領域が連続している必要がないため、問題とならない模様。 ↩

3. RHEL 6.4 (kernel-2.6.32-421.el6 未満) の環境で実行すると kernel panic が発生する問題 (全文読むにはログインが必要) が報告されていますので、RHEL 6.4 では実行しないか、kernel を 2.6.32-421.el6 (影響を受けないバージョン) 以降にアップデートしてから実行することをオススメ。 ↩

4. 手元の Linux Mint 19、Ubuntu 18.10、Fedora 28、CentOS 7.6、openSUSE Leap 15.0 ではデフォルトで有効化されていることを確認済み。 ↩