Linuxのメモリ管理 勉強記録 その2

# Linux 物理メモリ構造

## 全体像イメージ図

ざっくりイメージ図。
Node はひとつしかない前提（UMA 環境）。
関数名は、メモリ確保時の関数のみ記載。
vmalloc()（非連続ページの確保）は以下の図よりもさらに上のレイヤで、kmalloc() と alloc_pages() を組み合わせることで実現されている。

```
 +-----------------------------------------------------------------------------------------+
 | Linux                                                                                   |
 +-----------------------------------------------------------------------------------------+
     |                                                  |                            |
     |                                                  |kmalloc(size, flags)：      |
     |                                                  | 汎用スラブオブジェクト獲得 |
     |                                                  |kmem_cache_alloc()：        |kmem_cache_init()  ：汎用スラブキャッシュ作成
     |                                                  | 専用スラブオブジェクト獲得 |kmem_cache_create()：専用スラブキャッシュ作成
     |                                                  |                            |
     |                                               +-----+-----+-----+    +-----+  |
     |                                               | Obj | Obj | Obj |    | Obj |  |
     |                                               +-----+-----+-----+----+-----+----+---+
     |                                               | Slab                 | Slab     |...|
     |                                               +----------------------+----------+---+
     |                                                               |
     |                                                               |kmem_getpages()
     |                                                               |    ↓
     |alloc_pages()                                                  |alloc_pages()：連続ページの確保。
     |    ↓                                                         |    ↓
     |__alloc_pages_nodemask()                                       |__alloc_pages_nodemask()：メモリを割り当てられなかった時のメモリ回収処理、リトライ処理など。
     |    ↓                                                         |    ↓
     |get_page_from_freelist()                                       |get_page_from_freelist()：ゾーンの選定、メモリ割り当て。
     |                                                               |
 +-----------------------------------------------------------------------------------------+
 | Node 0                                                                                  |
 +-----------------------------------------------------------------------------------------+
     |        |                                      |
     |        |                                      |buffred_rmqueue(zone, order, gfp_flags)：ゾーンからのメモリ割り当て
     |        |                                      |
 +------+-------------+--------------------------------------------------------------------+
 | DMA  | DMA32       | Normal                                                             |
 | 16MB | 16MB ～ 4GB | 4GB ～                                                             |
 +------+-------------+--------------------------------------------------------------------+
     |        |                                      |
     |        |                  order == 0          |     order > 1
     :        :                   +------------------+---------------+
                                  |                                  |
                                  |                                  |
                      +--------------------+                         |
                      | CPU ごとのページ   l                         |
                      | フレームキャッシュ |                         |
                      +--------------------+                         |
                                  |                                  |
                                  |   GFP_COLD                       |
                            +-----+-----+                            |
                            |           |                            |
                      +----------+---------+                         |
                      | 活性     | 非活性  l                         |
                      +----------+---------+                         |
                                 |                                   |
                                 |__rmqueue(zone, order)             |__rmqueue(zone, order)：ゾーンからのメモリ割り当て
                                 |                                   |
                      +--------------------------------------------------------------------+ 
                      | Buddy System                                                       |
                      +--------------------------------------------------------------------+
                       :   :     :         :                               :
                       :   :     :         :                               :
                       :   :     :         :                               :
                      +-+ +--+ +----+ +--------+               +---------------------------+
                      |4| |8K| |16KB| | 32KB   | ............. | 4MB                       |
                      +-+ +--+ +----+ +--------+               +---------------------------+
                       :   :     :         :                               :
                      +-+ +--+ +----+ +--------+               +---------------------------+
                      | | |  | |    | |        | ............. |                           |
                      +-+ +--+ +----+ +--------+               +---------------------------+
                       :   :               :                               
                      +-+ +--+        +--------+               
                      | | |  |        |        | ............. 
                      +-+ +--+        +--------+               
                       :                   :                               
                      +-+             +--------+               
                      | |             |        | ............. 
                      +-+             +--------+               
```

## Node と Zone

x86_64 アーキテクチャの場合、物理メモリは以下のような区画に分けて管理される。

区画分けするのは、周辺デバイスなどが DMA（ダイレクトメモリアクセス）でアクセスできる領域が先頭から 16MB だけ、という場合があるからだ。
限りある DMA ゾーンのリソースの使用はできるだけ節約しなければならない。

```
 Node 0 --+----- Zone DMA    :  0 MB ～ 16 MB 
          |
          +----- Zone DMA32  : 16 MB ～  4 GB
          |
          +----- Zone Normal : 4 GB ～
```

NUMA の場合、Node が複数あるだろう。

```
 Node 0 --+----- Zone DMA    :    0 MB ～    16 MB 
          |
          +----- Zone DMA32  :   16 MB ～  4096 MB
          |
          +----- Zone Normal : 4096 MB ～
 
 Node 1 -------- Zone Normal :    0 MB ～
```

ゾーンの情報は /proc/zoneinfo から確認できる。
/proc/zoneinfo では Linux カーネルの zone 構造体の各要素の値が確認できる。

```console
# grep Node /proc/zoneinfo
Node 0, zone      DMA
Node 0, zone    DMA32
Node 0, zone   Normal
```

## Buddy System

Linux では効率よくメモリを割り当てる（できるだけフラグメンテーションさせない）ために、Buddy System を採用している。

Buddy System は各ゾーンごとに構築される。
Buddy Ssytem では、空きメモリを 2^n 単位で管理している。

```
  Zone Normal --+------ 1 page 空きリスト --- [ ]->[ ]->[ ]->[ ]
                |
                +------ 2 page 空きリスト --- [  ]->[  ]->[  ]
                |
                +------ 4 page 空きリスト --- [    ]->[    ]->[    ]
                |
                +------ 8 page 空きリスト --- [        ]->[        ]->[        ]
                |
                :          :
                |
                +------ 1024 page 空きリスト --- [   ...   ]->[   ...   ]
```

Buddy System では、メモリ割り当て要求に対して最もサイズが近い空きメモリをアサインする仕組みになっている。

```
 <5 page の割り当て要求>
     |
     |
     V
  Zone Normal --+------ 1 page 空きリスト --- [ ]->[ ]->[ ]->[ ]
                |
                +------ 2 page 空きリスト --- [  ]->[  ]->[  ]
                |
                +------ 4 page 空きリスト --- [    ]->[    ]->[    ]
                |
                +------ 8 page 空きリスト --- [        ]->[        ]->[        ]
                |                             ^^^^^^^^^^★サイズの最も近い空き page を割り当てる。
                :          :
                |
                +------ 1024 page 空きリスト --- [   ...   ]->[   ...   ]-
```

空きリストの長さは /proc/buddyinfo で確認できる。

```
# cat /proc/buddyinfo
Node 0, zone      DMA      4      2      2      4      2      2      2      2      3      1      2
Node 0, zone    DMA32   7634   3778   1738    495     36      1      1      0      0      0      0
Node 0, zone   Normal   2637   1013    513    127     15      1      0      0      0      0      0
                        ^^^^   ^^^^   ^^^^                                                       ^
                          |      |     |                                                         +--- 1024 page 連続して空いている領域の数
                          |      |     |                                                                :
                          |      |     +------------------------------------------------------------- 4 page 連続して空いている領域の数
                          |      +------------------------------------------------------------------- 2 page 連続して空いている領域の数
                          +-------------------------------------------------------------------------- 1 page 連続して空いている領域の数
```

以下の場合だと、2 page 連続で空いている領域が枯渇してしまっている。

```
Node 0, zone      DMA      3      2      2      3      2      2      1      0      0      1      3
Node 0, zone    DMA32  19178   2647    290     60     15      1      2      1      0      0      0
Node 0, zone   Normal  46169      0      0      0      0      0      0      0      0      0      1
                             ^^^^^^★
```

この場合、ページの割り当てに失敗し、以下のようなログが残されることがある。

```
 kernel: find: page allocation failure. order:1, mode:0x20
                                              ^★2^1 の連続ページの割り当てを要求
```

## slab

Buddy System ではページ単位でメモリを確保する。
しかし、Linux カーネルではページ（4096 Byte）よりももっと小さい単位でデータの割り当て要求をすることも多い。
その場合にページ単位でメモリを割り当てていては非効率だ。

※inode キャッシュや dentry、tcp のソケット情報、などなど。

そのため、あらかじめページを割り当てておいて、その中で細かくメモリを割り当てるための仕組みがある。
それが slab だ。

※詳細はいずれ書く。

## メモリ割り当て

Linux カーネル内で物理メモリを取得する主要な関数は以下当たりだろうか。

* page *alloc_pages(gfp_t gfp_mask, unsigned int order)()：2^order ページ単位での連続メモリ領域獲得
* void *kmalloc(size_t size, gfp_t flags)：byte 単位で連続メモリ領域獲得（汎用スラブから）
* void *vmalloc(unsigned long size)：非連続ページの獲得（ページテーブルが変更され、リニアアドレス空間としては連続に並ぶ）
* void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)：専用スラブオブジェクトの獲得

## alloc_pages()
メモリを確保するゾーンの選定から行うので、ゾーンアロケータとも呼ばれる。
alloc_pages では、各ゾーンを精査し、空きメモリの量などからメモリを割り当てるゾーンを選択し、メモリを割り当て、割り当てたページ配列のポインタを返す。

※詳細はいずれ書く。

# メモリ枯渇時の動作

メモリが枯渇した場合にはキャッシュの開放やスワップが行われる。
OS の重要な処理中で本当に空きメモリがなくなったりしては困るので、Linux カーネルは常に空きメモリを一定以上確保しようする。

"枯渇" の判断基準はゾーンごとに定められており、/proc/zoneinfo で確認できる。

```:/proc/zoneinfo
Node 0, zone   Normal
  pages free     8446 ★空き page の数
        min      4277 ★メモリ枯渇の閾値。空きページ数がこれを下回ったら、プロセスのメモリ割り当て要求をブロックして、空きメモリを確保する。
        low      5346 ★メモリ枯渇の閾値。空きページ数がこれを下回ったら、kswapd が動き出し、バックグラウンドでメモリの開放が行われる。
        high     6415 ★kswpd によるメモリの開放の上限値。空きメモリがこれを上回ったら kswapd は活動を停止する。
        scanned  0
        spanned  262144
        present  262144 ★ゾーンのサイズ（page）
        managed  245463
```

# ゾーンの保護

ゾーンには DMA/DMA32/NORMAL など複数あり、低位のゾーンほどどのような用途にでも使えるゾーンなわけだが、
カーネルがページを要求（alloc_pagse）するとき、どのゾーン以下のゾーンから割り当ててほしい、という要求をする。

```
 arch/arm/include/asm/pgalloc.h
   pte = alloc_pages(PGALLOC_GFP | __GFP_HIGHMEM, 0);
                                   ^^^^^^^^^^^^^★HIGHMEM 以下のゾーンからページを割り当ててほしい。
```

この時、本当は HIGHMEM ゾーンからの割り当てでも良いのに、DMA からぽんぽんメモリを持っていかれたら困るわけである。
DMA は周辺デバイスのダイレクトメモリアクセスに使えるゾーンであり、そこが枯渇したらダイレクトメモリアクセスができなってしまう。
DMA からメモリを取得されて mlock(2) なんてされたら、いよいよ DMA ゾーンは枯渇してしまう。
つまり、上位のゾーンを使っても良いのであれば、上位のゾーンからページを確保すべきで、下位のゾーンからページを持っていかれすぎないようにする必要がある。
その仕組みが protection である。

protection の値は /proc/zoneinfo から確認できる。

```console
 $ cat proc/zoneinfo |grep -e zone -e protection
 Node 0, zone      DMA
         protection: (0, 2125, 515151, 515151)
 Node 0, zone    DMA32
         protection: (0, 0, 513026, 513026)
 Node 0, zone   Normal
         protection: (0, 0, 0, 0)
```

見方は少し複雑だが、以下のように読む。

```
 Node 0, zone      DMA
         protection: (0, 2125, 515151, 515151)
                      ^  ^^^^  ^^^^^^  ^^^^^^
                      |    |     |       +------ 未使用（今回はゾーンが 3 つしかないため、4つ目の項目は使われない）
                      |    |     +-------------- Normal ゾーンでも良い要求の場合は、DMA は 515151 page 分は必ず残して、それ以上ページアロケートしない。
                      |    +-------------------- DMA32 ゾーンでも良い要求の場合は、DMA は 2125 page 分は必ず残して、それ以上ページアロケートしない。
                      +------------------------- DMA ゾーンに対する要求の場合は、DMA は保護せず、すべてのページを割り当て可能とする。

 Node 0, zone    DMA32
         protection: (0, 0, 513026, 513026)
                      ^  ^  ^^^^^^  ^^^^^^
                      |  |    |       +------ 未使用（今回はゾーンが 3 つしかないため、4つ目の項目は使われない）
                      |  |    +-------------- Normal ゾーンでも良い要求の場合は、DMA は 513026 page 分は必ず残して、それ以上ページアロケートしない。
                      |  +------------------- DMA32 ゾーンに対する要求の場合は、DMA32 は保護せず、すべてのページを割り当て可能とする。
                      +---------------------- 未使用（DMA ゾーンに対する要求にたいして、DMA32 ゾーンからページを割り当てることはできない）
```


# 参考資料
* 詳解 Linux カーネル
* https://www.kernel.org/doc/gorman/html/understand/understand005.html