Linuxでのpage構造体群の配置

何回か「あれどうだっけ？」と調べるのが面倒なのと、記憶力あまりないので、メモ。(おじさん、記憶力あまりないもんで)
読んだソースはLinux4.10ですが、本質的なところは過去のバージョンでもたぶん変わらないのではないかと思います。

## Linuxのメモリモデル

「物理RAM空間の連続性」に着目すると、「物理的に連続していたフラットなRAM空間」と「物理的に非連続なメモリホールのあるRAM空間」(例えばx86)に分類できます。
Linuxにおいて、ページ構造体を配置する方式は、4通りあり、カーネルコンフィグで指定します。概要は以下の表のとおりです。

| 定義名 | 物理RAM空間はフラット？ | 概要/備考 |
|:---|:---|:---|
| CONFIG_FLATMEM | Yes | 最も単純なRAM空間。一つのRAM空間が途中で途切れることなく連続している。|
| CONFIG_DISCONTIGMEM | No | 非連続なRAM空間を表現する最も昔からある実装。枯れているけど、メモリのホットプラグとは非互換。CONFIG_SPARSEMEMよりパフォーマンス的に劣るかもしれない。 |
| CONFIG_SPARSEMEM | No | CONFIG_DISCONTIGMEMの代替。CONFIG_DISCONTIGMEMよりは多少パフォーマンス的には良くコードも容易。しかしまだ枯れていない。|
| CONFIG_SPARSEMEM_VMEMMAP | No |仮想的にマップされたmemmapによって、pfn_to_page/page_to_pfnを効率よくしたCONFIG_SPARSEMEMの亜種。|

詳しくは、mm/Kconfigを読んでくださいね。
このコンフィグの違いによって、最も異なってくる部分は、page構造体とPFN(物理フレーム番号)の関係です。

## page構造体とPFN(Physical Frame Number)の相互変換

page構造体とPFNとの間の変換は、以下のマクロで行います。

| マクロ名 | 概要 |
|:---|:---|
| __pfn_to_page(pfn) | PFNからそれに対応したpage構造体を取得する |
| __page_to_pfn(page) | page構造体から、それに対応したPFNを取得する |

Linuxのページ構造体配置方法によって、これらのマクロの実装が異なります。これらを一つずつ見ていき、page構造体を取り巻くデータ構造を確認しましょう。

### CONFIG_FLATMEMの場合

2つのマクロは、以下のように実装されています。

```c:include/asm-generic/memory_model.h
#define __pfn_to_page(pfn)  (mem_map + ((pfn) - ARCH_PFN_OFFSET))
#define __page_to_pfn(page) ((unsigned long)((page) - mem_map) + \
                 ARCH_PFN_OFFSET)
```

上記のマクロに現れるmem_mapは以下の通り、page構造体のポインタです。

```c:include/linux/mmzone.h
#ifndef CONFIG_DISCONTIGMEM
/* The array of struct pages - for discontigmem use pgdat->lmem_map */
extern struct page *mem_map;
#endif
```

これは最も簡単な表現方法です。図にするとこんな感じです。(本文書において、「P」という文字が入った四角はpage構造体を表すものとします。)

![mem_map_1.jpg](https://qiita-image-store.s3.amazonaws.com/0/19975/35ed3603-f9ed-143c-12fd-899eb7ddb0be.jpeg)

この図を見た上で、先に引用したコードを見るとわかりやすいと思います。

| 定義名 | 概要 |
|:---|:---|
| __pfn_to_page(pfn)| pageがPFN番号順に並んでいるだけなので、mem_mapの先頭からpfn番目のpage構造体を単純な足し算で求められる。|
| __page_to_pfn(page) | mem_mapが先頭のpage構造体のアドレスを指している。よって、page構造体のアドレスを使った引き算でPFNを算出可能 |

### CONFIG_DISCONTIGMEMの場合

2つのマクロは、以下のように実装されています。

```c:include/asm-generic/memory_model.h
#elif defined(CONFIG_DISCONTIGMEM)
#define __pfn_to_page(pfn)          \
({  unsigned long __pfn = (pfn);        \
    unsigned long __nid = arch_pfn_to_nid(__pfn);  \
    NODE_DATA(__nid)->node_mem_map + arch_local_page_offset(__pfn, __nid);\
})

#define __page_to_pfn(pg)                       \
({  const struct page *__pg = (pg);                 \
    struct pglist_data *__pgdat = NODE_DATA(page_to_nid(__pg)); \
    (unsigned long)(__pg - __pgdat->node_mem_map) +         \
     __pgdat->node_start_pfn;                   \
})
```

やや複雑になりましたが、以下のような実装をイメージしてください。
(NODE_DATAやarch_local_page_offset()の実装はアーキテクチャごとに異なりますので、細部は異なるかもしれません。詳細を知りたければ、実装を読んでみましょう。本質的な部分は変わらないと思います。)

![mem_map_2.jpg](https://qiita-image-store.s3.amazonaws.com/0/19975/856b67e9-a9a2-cc9c-9804-f2ee4297af68.jpeg)

### CONFIG_SPARSEMEMの場合

2つのマクロは、以下のように実装されています。CONFIG_DISCONTIGMEMに比べ複雑に見えます。

```c:include/asm-generic/memory_model.h
#elif defined(CONFIG_SPARSEMEM)
/*
 * Note: section's mem_map is encoded to reflect its start_pfn.
 * section[i].section_mem_map == mem_map's address - start_pfn;
 */
#define __page_to_pfn(pg)                   \
({  const struct page *__pg = (pg);             \
    int __sec = page_to_section(__pg);          \
    (unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec))); \
})

#define __pfn_to_page(pfn)              \
({  unsigned long __pfn = (pfn);            \
    struct mem_section *__sec = __pfn_to_section(__pfn);    \
    __section_mem_map_addr(__sec) + __pfn;      \
})
#endif /* CONFIG_FLATMEM/DISCONTIGMEM/SPARSEMEM */
```

今回はmem_sectionというデータ構造が増えています。2段階に分けて図示します。
まずは第一段階。page構造体とmem_sectionとの関係です。

(CONFIG_SPARSEMEM_EXTREMEが有効な場合)

![mem_map_3.jpg](https://qiita-image-store.s3.amazonaws.com/0/19975/faf6651e-33d7-16d8-6064-7eae3733e0dc.jpeg)

(CONFIG_SPARSEMEM_EXTREMEが無効な場合)

![mem_map_4.jpg](https://qiita-image-store.s3.amazonaws.com/0/19975/404951e4-8c2d-93b9-e5d6-2b8cdb371809.jpeg)

続いて、mem_sectionを詳しく見ていきましょう。

### mem_sectionの説明

mem_sectionとは何でしょうか。ソースコードにはこれだけしかありません・・・。

```c:mm/sparce.c
* 1) mem_section   - memory sections, mem_map's for valid memory
```

mem_sectionは、有効なある固定サイズの物理メモリ空間を表現するためのデータ構造です。
メモリページも物理RAM空間を固定サイズに分割して管理しますが、これとは関係ありません。ページサイズよりも大きなサイズの固定サイズ領域で、Linuxのレベルで物理的に連続した(複数の物理ページから構成される)物理RAM領域を”大雑把に”管理するために用いるものだと思われます。
イメージとしては、以下のとおりです。

![mem_map_5.jpg](https://qiita-image-store.s3.amazonaws.com/0/19975/06cafea5-74a6-53ee-532f-1ab89a6a4217.jpeg)

次に、mem_sectionに関連したコードを見ましょう。
まず、page構造体から、そのページが所属するmem_sectionの番号(sectionid)を求めるコードを見ましょう。
ソースを見ると、page構造体のflagsの一部に番号を格納していることがわかります。

```c:include/linux/mm.h
static inline unsigned long page_to_section(const struct page *page)
{
    return (page->flags >> SECTIONS_PGSHIFT) & SECTIONS_MASK;
}
```

次に、セクションの番号から、それに対応するmem_sectionのアドレスを取得するコードを見ます。

```c:include/linux/mmzone.h
static inline struct mem_section *__nr_to_section(unsigned long nr)
{
    if (!mem_section[SECTION_NR_TO_ROOT(nr)])
        return NULL;
    return &mem_section[SECTION_NR_TO_ROOT(nr)][nr & SECTION_ROOT_MASK];
}
```

#### mem_sectionのsection_mem_map

先ほどの図において、「section_mem_mapはページ構造体のリストを直接指しておらず、計算によって、ページ構造体の先頭を求める」と書きました。
この点をコードで確認したいと思います。

まず、__section_mem_map_addr()を見ます。最終的にpage構造体のアドレスを返しています。

```c:include/linux/mmzone.h
static inline struct page *__section_mem_map_addr(struct mem_section *section)
{
    unsigned long map = section->section_mem_map;
    map &= SECTION_MAP_MASK;
    return (struct page *)map;
}
```

__section_mem_map_addr()は以下2箇所でしか呼び出されていません。

```c:include/asm-generic/memory_model.h
#elif defined(CONFIG_SPARSEMEM)
/*
 * Note: section's mem_map is encoded to reflect its start_pfn.
 * section[i].section_mem_map == mem_map's address - start_pfn;
 */
#define __page_to_pfn(pg)                   \
({  const struct page *__pg = (pg);             \
    int __sec = page_to_section(__pg);          \
    (unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec))); \
})

#define __pfn_to_page(pfn)              \
({  unsigned long __pfn = (pfn);            \
    struct mem_section *__sec = __pfn_to_section(__pfn);    \
    __section_mem_map_addr(__sec) + __pfn;      \
})
#endif /* CONFIG_FLATMEM/DISCONTIGMEM/SPARSEMEM */
```

ここで、\_\_pfn_to_page()を見るとわかるのですが、直接\_\_section\_mem\_map\_addrの戻り値を返していません。戻り値(page構造体のアドレス) + \_\_pfn、つまりpage構造体のアドレス + \_\_pfn * sizeof(page構造体)を返しています。

では、section_mem_mapには何が設定されているのでしょうか。実はブート時に、以下のsparse_encode_mem_map()の戻り値が格納されます。
なお、第一引数のmem_mapは、該当ページ構造体のリストの先頭アドレス、第二引数はセクションの番号(sectionid)です。

```c:mm/sparse.c
/*
 * Subtle, we encode the real pfn into the mem_map such that
 * the identity pfn - section_mem_map will return the actual
 * physical page frame number.
 */
static unsigned long sparse_encode_mem_map(struct page *mem_map, unsigned long pnum)
{
    return (unsigned long)(mem_map - (section_nr_to_pfn(pnum)));
}
```

これが肝です。**mem_sectionのsection_mem_mapはpage構造体のリストを直接参照していません。**
**「page構造体のリストの先頭アドレス - 該当mem_sectionに対応したRAM空間先頭のPFN \ sizeof(page構造体)」**がセットされます。
※上記のmem_map - (section_nr_to_pfn(pnum))がポインタ演算であることに注意しましょう。

ここで、__page_to_pfnのマクロを見ましょう。

```c:include/asm-generic/memory_model.h
#define __page_to_pfn(pg)                   \
({  \
    const struct page *__pg = (pg);             \
    /* 渡されたpgが含まれるmem_sectionを指すsection idを取得する */
    int __sec = page_to_section(__pg);          \
    /* もし仮に、mem_sectionのsection_mem_mapが直接page構造体のリストを参照しているとすると・・・ */ \
    /* 以下の演算で求まるのは「RAM空間全体視点でのPFN」でなく、「該当mem_section内のpage構造体リストの何番目 */ \
    /* のpage構造体か」というmem_section内でのインデックスでしかない。 */ \
    (unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec))); \
})
```
動作については、上に補足コメントを書いたとおりです。
sparse_encode_mem_map()の戻り値として「page構造体のリストの先頭アドレス - 該当mem_sectionに対応したメモリ領域の先頭のPFN」を返すことにより、上記の式は

```
= PFNを求めたいpage構造体のアドレス - (該当mem_sectionのpage構造体リストの先頭アドレス - 該当mem_sectionに対応したメモリ領域の先頭のPFN)
= (PFNを求めたいpage構造体のアドレス - 該当mem_sectionのpage構造体リストの先頭アドレス) + 該当mem_sectionに対応したメモリ領域の先頭のPFN
= mem_section内におけるpage構造体のオフセット + 該当mem_sectionに対応したメモリ領域の先頭のPFN
= RAM空間全体視点でのPFN
となります。
```

このような一見すると面倒なことをしている理由は、mem_section構造体のパラメータを減らしたいのではないか、と想像します。アルゴリズムのわかりやすさから言うと、mem_section先頭のPFNを持たせたほうが、より簡潔になるのではないかと思います。
※sparse_encode_mem_map()やマクロで実施している演算はポインタ演算なので、厳密には上記の途中経過の説明は正しくありません。
ここで言いたいのは、「該当mem_sectionに対応したメモリ領域先頭のPFN分があらかじめ考慮されることで、__page_to_pfnが意図通り動く」ということです。(このあたり、私の日本語能力のダメさ加減でして・・・)

### CONFIG_SPARSEMEM_VMEMMAPの場合

最後に、CONFIG_SPARSEMEM_VMEMMAPを見ましょう。2つのマクロは、以下のように実装されています。

```c:include/asm-generic/memory_model.h
/* memmap is virtually contiguous.  */
#define __pfn_to_page(pfn)  (vmemmap + (pfn))
#define __page_to_pfn(page) (unsigned long)((page) - vmemmap)
```

？！これって、CONFIG_FLATMEMよりも単純ですね。しかも、コメントに「virtually contiguous」と書かれていますし。
気になるので見てみましょう。
結論から言うと、以下のようになります。これだけを見ると、CONFIG_SPARSEMEMの場合と大差無いように見えます。

![mem_map_6.jpg](https://qiita-image-store.s3.amazonaws.com/0/19975/7d77d821-0249-d48e-ddfc-cc0fa05a4a03.jpeg)

しかし、実はページ構造体群の仮想アドレス割り振りにひと工夫あるのです。

![mem_map_7.jpg](https://qiita-image-store.s3.amazonaws.com/0/19975/960780ba-4616-697e-e12e-77fd263d0ab9.jpeg)

この部分、少し見ましょう。(ただし、ここではCONFIG_SPARSEMEM_ALLOC_MEM_MAP_TOGETHERは無効と仮定します)
メモリノード内の物理メモリに対応したページ構造体群を割り当てるのは、sparse_init()内から呼ばれるsparse_early_mem_map_alloc()です。

```c:mm/sparse.c
void __init sparse_init(void)
{
    /* 略 */
    for (pnum = 0; pnum < NR_MEM_SECTIONS; pnum++) {
    /* 略 */
#ifdef CONFIG_SPARSEMEM_ALLOC_MEM_MAP_TOGETHER
        map = map_map[pnum];
#else
        map = sparse_early_mem_map_alloc(pnum);
#endif
        if (!map)
            continue;
    /* 略 */
    }   
```

sparse_early_mem_map_alloc()はsparse_mem_map_populate()を呼び出します。
第一引数にmem_section番号を、第二引数にnode idを渡します。

```c:mm/sparse.c
static struct page __init *sparse_early_mem_map_alloc(unsigned long pnum)
{
    struct page *map;
    struct mem_section *ms = __nr_to_section(pnum);
    int nid = sparse_early_nid(ms);

    map = sparse_mem_map_populate(pnum, nid);
    if (map)
        return map;
    /* 略 */
}
```

はい。以下のsparse_mem_map_populate()からvmemmap_populate()を呼び出して仮想アドレス空間とそれに紐付いた物理メモリを確保できました。
これで1つのmem_section分のページ構造体群は確保できました。

```c:mm/sparse-vmemmap.c
struct page * __meminit sparse_mem_map_populate(unsigned long pnum, int nid)
{
    unsigned long start;
    unsigned long end;
    struct page *map;

    // 該当mem_sectionの先頭ページに対応した仮想アドレスを取り出す
    map = pfn_to_page(pnum * PAGES_PER_SECTION);
    start = (unsigned long)map;
    /* 空間のサイズはmem_sectionのサイズ */
    end = (unsigned long)(map + PAGES_PER_SECTION);

    /* 仮想アドレス空間とそれに紐付いた物理メモリの割当(つまり、ページ構造体群の割当) */
    if (vmemmap_populate(start, end, nid))
        return NULL;

    return map;
}
```

・・・え、そもそもどうやって仮想アドレスを決めているんだって？
ここで、pfn_to_page()を見ましょう。pfn_to_page()の実体は__pfn_to_page()です。

```c:include/asm-generic/memory_model.h
/* memmap is virtually contiguous.  */
#define __pfn_to_page(pfn)  (vmemmap + (pfn))
```

じゃあ、vmemmapを見ましょう。実はvmemmapはarchの下にあります。ここではx86を見ます。

```c:arch/x86/include/asm/pgtable_64.h
#define vmemmap ((struct page *)VMEMMAP_START)
```

```c:arch/x86/include/asm/pgtable_64_types.h
#define VMEMMAP_START        vmemmap_base
```

```c:arch/x86/mm/kaslr.c
unsigned long vmemmap_base = __VMEMMAP_BASE;
```

```c:arch/x86/include/asm/pgtable_64_types.h
#define __VMEMMAP_BASE       _AC(0xffffea0000000000, UL)
```

こんな感じで、あらかじめページ構造体を配置する仮想アドレスが定義されています。
(Kernel Address Space Layout Randomizationが有効な場合はちょっと変わってきますが、最終的には一意な値となります。興味のある人はarch/x86/mm/kaslr.cを是非)

ついでにARM64も載せておきます。同じようにあらかじめページ構造体を配置する仮想アドレスが定義されています。

```c:arch/arm64/include/asm/pgtable.h
#define vmemmap                      ((struct page *)VMEMMAP_START - (memstart_addr >> PAGE_SHIFT))
```

```c:arch/arm64/include/asm/memory.h
#define VMEMMAP_START                (PAGE_OFFSET - VMEMMAP_SIZE)
```

```c:arch/arm64/include/asm/memory.h
#define VMEMMAP_SIZE (UL(1) << (VA_BITS - PAGE_SHIFT - 1 + STRUCT_PAGE_MAX_SHIFT))
```

```c:arch/arm64/include/asm/memory.h
#define VA_BITS                      (CONFIG_ARM64_VA_BITS)
```

```c:arch/arm64/include/asm/memory.h
#define STRUCT_PAGE_MAX_SHIFT        6
```

こんな感じで、4つのページ構造体配置方式を見てきました。ちょっとメモっておきたいので書きましたが、参考になれば幸いです。