狠狠撸

Copyright? 2014 Hitachi, Ltd. All rights reserved. Yokohama Research Lab.
ページフレーム管理
吉田雅徳
2014/6/28(Sat)

ページフレームの管理
? 目的
? 物理メモリをページフレーム（4KB）の集まりと
して管理（割当?解放）
? 異なる種類のメモリを効率的に利用（NUMAノー
ド、メモリゾーン、percpu、など）
2

アジェンダ
? 1. ページフレーム
? 2. NUMA
? 3. メモリゾーン
? 4. ページフレーム割当
? 4.1 ゾーンアロケータ
? 4.2 バディシステム
? 5. ページフレーム解放
3

1. ページフレーム

x86ページング超概要(1)
? Mode
? Real-address mode
? 16bit addressing
? Segmentationによるアドレス変換(Logical→Linear)は常に有効
? Linear address = Physical address
? Protected mode
? 32bit addressing
? Segmentationにおいて保護機構が有効になっている状態を指す
? Pagingのon/o?は直交する要素（どちらもアリ）
? IA-32e mode
? Enabled by IA32_EFER msr s bit8
? 2 sub modes: Compatibility mode(32bit) and 64-bit mode
5

? Address
? Logical address
? カーネルを含むプログラムが直接扱うアドレス(セグメントセレクタ+オフセットからなる(但し普通のプロ
グラムではデフォルトのセグメントセクレタのみを使うので、省略され、あまり意識されない。TLSとか
per-cpuとかで%%gfを指定したりはする))
? Segmentationが適用され、Linear addressに変換される
? Linear address
? Pagingがdisabledであれば、Physicalアドレスと同一のものとして扱われる
? Pagingがenabledであれば、Pagingが適用され、Physical addressに変換される
? Physical address
? メモリアドレスバスに対して指定するアドレス
? 必ずしもRAM上の位置に対応するオフセットではない(最終的に当該アドレスが何のデバイスの何の値にマッ
ピングされるかはHW環境次第)
6

? 以降は、IA-32e mode(64-bit sub mode)を前提として説明を進める。
? Pagingとは
? メモリ上に構築されたpage table structureをMMU(Memory Management Unit)
が解釈し、Linear→Physicalのアドレス変換、保護制御、キャッシュ制御を実行。
? 上記MMU処理の単位である4KBをページと呼ぶ。但しpage tableの指定により
2MB、1GBを1ページとして扱うことも可能。
? ページフレームとは（赤本の定義に準拠）
? 特にRAMについて、領域をページサイズ?ページアラインで区切った時の、各ブ
ロックを「ページフレーム」と呼ぶ。
? すなわち、カーネルが所謂メモリを有限リソースとして管理する際の最低単位。
7

struct page
? ページフレームに一対一で用意され、種々の情報を格納
? ページディスクリプタとも(赤本などでは)呼ばれる
? (有名な話だが)1個のサイズは、キャッシュライン(i7なら64B)
に収まるよう保たれており、サイズ拡張は原則論外とされる
? (あまり知られてないと思うが)中身は更にdouble word(64bit
環境なら16バイト)x4にアラインするように作られている。?
これは、slubのコードでcmpxchg_doubleとかいう atomic
操作を行うため(らしい)
8

mem_map
? 全RAMページフレームに対応するstruct pageを一
つの配列に格納したもの。
? 牧歌的な実装????
#define __pfn_to_page(pfn) ??
(mem_map + ((pfn) - ARCH_PFN_OFFSET))
? ところが、CONFIG_NUMA+CONFIG_X86_64(と
いうかCONFIG_SPARSEMEM)では、全メモリ統
一のmem_mapは存在しない。
9

sparse memoryでの
__pfn_to_page()
? #define __pfn_to_page(pfn) ?
({ unsigned long __pfn = (pfn); ?
struct mem_section *__sec = __pfn_to_section(__pfn); ?
__section_mem_map_addr(__sec) + __pfn; ?
})
? 二段テーブル構造
? 1段目：struct mem_sectionのリスト
? 2段目 : mem_section::section_mem_map?
ある長さの連続領域(後述するように128MB分)の中のページフレーム
に対応するミニmem_mapの役割
? sparseな物理メモリレイアウトに対応。
10

RAM情報の取得
? __init memblock_x86_?ll()
? 物理メモリ上の何処がRAMにマップされている
か特定する関数
? BIOS(e820)から得たRAM領域情報を使い、?
memblockリストを作成。?
(E820_RAMまたはE820_RESERVED_KERNな
e820entry毎に、memblock_add()を呼び出し)
11

mem_section(離散型mem_map)の?
作成
? void __init sparse_memory_present_with_active_regions(int nid)?
{?
unsigned long start_pfn, end_pfn;?
int i, this_nid;?
?
for_each_mem_pfn_range(i, nid, &start_pfn, &end_pfn, &this_nid)?
memory_present(this_nid, start_pfn, end_pfn);?
}
? for_each_…は前頁で作成したmemblockリストをiterationする
もの。memory_present()の中では、memblockを128MB長毎に
区切り、それぞれmem_sectionを作成する。
? 128MB = PAGE_SIZE * (2MB / sizeof(struct page))。?
つまり、一つのmem_sectionが保持するミニmem_mapのサイズ
がhuge pageに収まるようにしている。
12

2. NUMA

NUMAって
? NUMA(Non-Uniform Memory Architecture)
? CPUからメモリの距離(レイテンシ)が一様でない
? 各CPUと各メモリの全対全に特性が定義される？
? => No.?
1個以上のCPU群と最大1個の物理メモリレンジからなる
nodeを単位として、node間(or同node内)で特性が定義
される。
? x86ではACPIから構成情報を取得する。
14

ACPIからNUMA情報取得
? __init initmem_init()?
-> __init x86_numa_init()?
-> __init numa_init(init_func=x86_acpi_numa_init)
? ACPIからNUMA情報を取得
? SRAT(Static Resource A?nity Table)
? SLIT(System Locality Information Table)
? 最終的にstruct pglist_data(pg_data_t)をセット
アップ
15

ACPI SRAT
? pxm_to_node_map[MAX_PXM_DOMAINS]?
node_to_pxm_map[MAX_NUMNODES]
? nodeとACPI proximity domainの双方向マッピング
? LinuxではACPI proximity domainをnodeに抽象化?
(可搬性：ACPI以外でNUMAサポートしてるアーキがある(多分))
? __apicid_to_node[MAX_LOCAL_APIC]
? APIC ID(=x86アーキ内部でのCPU番号)からnodeへの単方向マッピング
? numa_meminfo
? 物理メモリ範囲(start+end)とnodeの双方向マッピング?
(この範囲に稠密にRAMがマップされてるとは限らないのでe820情報も使う)
16

ACPI SLIT
? SLIT(System Locality Information Table)
? node(proximity domain)間の距離の情報
? 1byte(0 255)で定義される。
? 0 9=予約済、255=node間アクセス不可
? 10 29: 比較的近い(zone_reclaim対象(後述))
17

NODE情報の保存
? __init numa_register_memblks()
? ACPI SRAT/SLITから得た情報に基づき、
node_data[]を設定
? node_data[]はNUMA_NODE(nid)マクロ経由で
使用される、NUMA情報を格納する構造体
18

CPUとNODEのマッピング
? 先ほど、ACPIから得た情報
? __apicid_to_node[MAX_LOCAL_APIC]
? APIC IDからnodeへの単方向マッピング
? だがしかし：Linuxにおけるprocessor ID != ACPI ID
? processor IDとAPIC IDのマッピング
? early_per_cpr(x86_cpu_to_apicid)に格納(別途、APIC周りの初期化処理による)
? 上記2種のテーブルをマージして、最終的に
? per_cpu(node_map, cpu)を設定する。cpu_to_node()ユーティリティ関数で参照
? processor IDからnode IDへのマッピング。
19

3. メモリゾーン

zoneとは
? zoneとは、物理メモリをアドレスによって分類したもの。
? enum zone_type {?
ZONE_DMA, //<16MB?
ZONE_DMA32, //<4GB?
ZONE_NORMAL, //全部?
ZONE_HIGHMEM, //x86_64では定義しない?
ZONE_MOVABLE, //？？？?
__MAX_NR_ZONES?
};
? ZONE_MOVABLEって？
? migrationによるページ移動を許可する領域。デフォルトでは存在しない。カーネルオプショ
ン kernelcore= で設定(ZONE_NORMALのサイズを設定する。但し=0の場合は
ZONE_MOVABLEは作られない)
? __GFP_MOVABLEを指定した時のみ、当該ゾーンからページを割当てる。
? Memory hot-removeに必須(movableなメモリのみremove可能)。
21

NUMAノード毎のzone/zonelist
? typedef struct pglist_data {?
struct zone node_zones[MAX_NR_ZONES];?
struct zonelist node_zonelists[MAX_ZONELISTS];?
int nr_zones;?
…?
};
? node_zones[]
? node配下のzoneのリスト。どのnodeも全てのゾーンを持つ。?
(但し、幾つかの又は全てのnodeが空の場合もある)
? node_zonelists[]
? nodeに属すCPUがメモリ割当を実行する際に、?
割当を試行する対象となるzoneを、試行する順序で並べたもの。
22

struct zonelist node_zonelists[]
? サイズはCONFIG_NUMAなら2、さもなくば1
? node_zonelists[0]
? 実行中CPUが属すNODEから割当可能な全てのzone(任
意のzone)を含むリスト
? node_zonelists[1]
? 実行中CPUが属すNODE内のzoneのみを列挙したリ
スト(__GFP_THISNODEで使用)
23

zonelists[0]の順序
? zonelists[0]内のzoneの順序はsysctlで変更可能。
? zone
? Higher zoneから優先して使う方法。ローカルのZONE_DMA32よりもリモート
のZONE_NORMALを先に使う。DMA領域温存を優先するポリシー。
? node
? 近傍NUMA nodeから優先して使う方法。局所性を優先するポリシー。
? default
? ZONE_DMAとZONE_NORMALのサイズを比較し、 zone か node かを自動的
に選択(ZONE_NORMALの割合が十分大きければDMA領域温存を重視し
て zone 、小さければ node )
24

zone::watermark[NR_WMARK]
? ページ割当時に、フリーページ量に応じて動作変更を行う。3種類ある(min <
low < high)。
? WMARK_LOW?
zonelistの全zoneでフリーページ量がlowを下回ってると、slowpathへ移行。?
この段階で、kswapdを起床するが、そのページ回収完了は待たずにページ割
当を実行(非同期的ページ回収)
? WMARK_MIN?
minも下回っていると、slowpathの延長で自らページ回収(同期的ページ回収)
? WMARK_HIGH?
node毎に動作するkswapdは一度起床されると、配下の全zoneのフリーペー
ジがhighを超えるまで動作し続ける。
25

zone::lowmem_reserve[MAX_NR_ZONES]
? どのzoneからメモリ割当の試行を開始するかは、GFPフラグで
決まる（大抵はZONE_NORMAL)から。
? 高位zone(e.g. _NORMAL)でのページ割当に失敗して、低位
zone(e.g. _DMA32)でページ割当を試行する際に、watermark
に一定量(=reserve)を加算して割当のハードルを上げる。
? z0から割当試行を開始して、z1にfall backしてきた場合、z1-
>lowmem_reserve[z0]がreserveになる。
? 同じzone_type(e.g. _NORMAL同士)ではreserveは0。
26

zone_watermark_ok()
(watermark判定ロジック)
? 目的：引数で指定したwatermark値とフリーページ量を比較して、割当可否を判定
? 主要な引数：order(割り当てたいページのオーダ数)、mark(判定に使うwatermark値)、alloc_?ags(GFP由来のフラグ)
? 処理
1. alloc_?agsに基づきmarkを調整
? ALLOC_HIGH => markを1/2
? ALLOC_HARDER => markを1/4
2. orderサイズのページ割当後のフリーページ総数が、mark+lowmem_reserveを超えているかチェック
3. 更に以下の条件をチェック(フラグメンテーション度合いのチェック)
? オーダが1 MAX_ORDER-1のフリーページ総数がmark>>1を超えているか？
? オーダが2 MAX_ORDER-1のフリーページ総数がmark>>2を超えているか？
? ???
? オーダがorder～MAX_ORDER-1のフリーページ総数がmark>>orderを超えているか？
27

zone::dirty_balance_reserve
? 当該zoneにおいて、dirtyにしないメモリ量。?
全ページから本reserve値を引いた数が、?
dirtyに出来るページ量の限界値となる。
? max(lowmem_reserve) + high_wmark_pagesで算出
/*
* Lowmem reserves are not available to
* GFP_HIGHUSER page cache allocations and
* kswapd tries to balance zones to their high
* watermark. As a result, neither should be
* regarded as dirtyable memory, to prevent a
* situation where reclaim has to clean pages
* in order to balance the zones.
*/
28

zone::percpu_drift_mark
? マイナーな機能。zone_watermark_ok_safe()でのみ使われる。
? zone_page_state(z, NR_FREE_PAGES)がpercpu_drift_mark
を下回っていた場合、?
zone_page_state_snapshot(percpuのNR_FREE_PAGESも加
算する)をfree_pagesとして、__zone_watermark_ok()を呼び
出す。
? percpu_drift_mark==0の時は無効
? page 迫時にpercpuのfree pageも動員する、その閾値を決め
るものと見なせる。
29

zone::pageset
? 型
? struct per_cpu_pageset __percpu *pageset;
? 各zoneはpercpuのキャッシュを持ち、出来るだけこの
キャッシュからページ割当を行う。?
解放時も最初はこのキャッシュへページを追加。
? ページが余ってくるとバディシステムに戻される。
? CPUキャッシュヒット率を高めることが目的。
30

zone::free_area[MAX_ORDER]
? zone毎のバディシステム(後述)。
31

zone::lruvec
? zone毎の、ユーザページ(無名メモリorページキャッシュ)の使用頻度順に並べた
LRU(Least Recently Used)リスト。ページ回収で使う。
? enum lru_list {?
" LRU_INACTIVE_ANON = LRU_BASE,?
" LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,?
" LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,?
" LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,?
" LRU_UNEVICTABLE,?
" NR_LRU_LISTS?
};?
struct lruvec {?
struct list_head lists[NR_LRU_LISTS];?
struct zone_reclaim_stat reclaim_stat;?
};"
? anon/?le及びactive/inactiveを個別に管理している。また、ページ回収対象外の
(mlockされてるページなど)を走査対象から外すための独立したリストとして
unevictableリストも管理される。
32

zone::***_pages
? spanned_pages
? 単にzone_end_pfn - zone_start_pfn。?
holesもreserved pagesも含む。
? present_pages
? spanned_pagesからholesを除いたもの。?
reserved pagesは含む
? managed_pages
? presend_pagesからreserved_pagesも除いたもの。
? ページ資源管理の文脈では普通、これをzoneの総ページとして扱うことになる。
33

4. ページフレーム割当
4.1 ゾーンアローケータ
4.2 バディアロケータ

4.1 ゾーンアロケータ

alloc_pages
? alloc_pages()?
-> alloc_pages_current()?
-> get_task_mempolicy()?
-> if MPOL_INTERLEAVE:?
-> alloc_pages_interleave?
(MPOL_INTERLEAVEポリシーでゾーン選択して割当)?
-> else:?
-> __alloc_pages_nodemask()?
-> 初回get_page_from_freelist()?
-> for_each_zone_zonelist_nodemaskループ?
-> 初回はzonelistの中でローカルnode内のzoneから割当を試行?
-> もしダメなら、二回目get_page_from_freelist()?
-> for_each_zone_zonelist_nodemaskループ?
-> 二回目はzonelistの中のzoneから割当を試行?
-> もしダメなら、__alloc_pages_slowpath()
36

for_each_zone_zonelist_n
odemaskループ!
1. zone_dirty_limitを越えてない？
? zone内のdirty page cacheの量に閾値がある。溜めすぎると?ush時にシステム止まるため。
2. zone->watermark(ここではlow)を下回ってない？
? sysctl -w zone_reclaim_mode=1 した場合のみ、zone_reclaim()を実行。?
でなければこの時点でこのzoneからの割当は諦め
? zone_reclaim()：?
* Zone reclaim reclaims unmapped ?le backed pages and?
* slab pages if we are over the de?ned limits.?
*?
* A small portion of unmapped ?le backed pages is needed for?
* ?le I/O otherwise pages read by ?le I/O will be immediately?
* thrown out if the zone is overallocated. So we do not reclaim?
* if less than a speci?ed percentage of the zone is used by?
* unmapped ?le backed pages.
3. OKなら、このzoneのバディアロケータへ進む
37

__alloc_page_slowpath
? 簡単に???
1. wake_all_kswapds()
2. if alloc_?ags & ALLOC_NO_WATERMARKS:?
__alloc_pages_high_priority() … 緊急用メモリを使ってページを割当
3. __alloc_pages_direct_compact()?
CONFIG_COMPACTION is unsetなら何もしない
4. __alloc_pages_direct_reclaim()?
slow pathの主役っぽい。?
try_to_free_pages()してからget_page_from_freelist()を試行
5. __alloc_pages_may_oom()?
reclaimのprogressが全く無くなった場合に実行する
6. __alloc_pages_direct_compact()?
前回は非同期で、今回は同期的に実行（完了を待つ）
38

Memory policy
? Memory policyは、modeとnodemaskで定義される
? mode : MPOL_*** (後述)
? nodemask : mode毎に意味が違うが、基本的には割当に(優
先的に)使われるNUMA node群を示すbit mask
? 関連システムコール
? set_mempolicy(2): set memory policy for a process
? mbind(2): set memory policy for a memory range
39

Memory policy mode
? MPOL_PREFERRED
? nodemaskには1つのnodeだけ指定可能。ページ割当時は当該nodeか
らのアロケーションを試行し、失敗時は近傍のnodeへfallback。
? MPOL_INTERLEAVE
? nodemaskに1つ以上のnodeを指定。ページ割当のたびに、初回にアロ
ケーションを試行するnodeをround-robin。
? MPOL_BIND
? nodemaskに1つ以上のnodeを指定。ページ割当のたびに、node番号
昇順にページ割当を試行。nodemask外のnodeに対しては試行しない。
40

dirty page ?ush
? c.f. sysctl/vm.txt
? 3 triggers
? dirty_background_{bytes,ratio}?
dirtyメモリがこのバイト数/割合を超えると、background kernel threadがwrite
back開始
? dirty_{bytes,ratio}?
ユーザプロセスのwriteによってこの閾値を超えると、プロセスコンテキストの延長
でwrite back開始
? dirty_expire_centisecs, dirty_writeback_centisecs?
expire_centisecsを経過すると、ページはoldと見なされる。?
oldなページは次回のperiodical write back(周期:writeback_centisecs)でwrite
backされる。
41

zone reclaim
? c.f. mm/vmscan.c:3686
? /*?
* Zone reclaim reclaims unmapped ?le backed pages and?
* slab pages if we are over the de?ned limits.?
*?
* A small portion of unmapped ?le backed pages is needed for?
* ?le I/O otherwise pages read by ?le I/O will be immediately?
* thrown out if the zone is overallocated. So we do not reclaim?
* if less than a speci?ed percentage of the zone is used by?
* unmapped ?le backed pages.?
*/
? 目的は恐らく???
? zonelistを走査してフリーメモリを探し、全滅だと__alloc_pages_slowpathに入るわけ
だけど、その前にlocal zoneで回収可能なページの回収を試みる。局所性維持が狙い。
42

try_to_free_pages,
kswapd, compaction
? ページ回収系については次回以降でお願いします
43

4.2 バディアロケータ

バディシステム(1)
? 赤本既読を前提に一言で済ませると、フリーページ
のリストを、order毎に分けて管理するもの。?
(orderとはページフレームが幾つ物理的に連続して
いるかを2の冪で示したもの。order=nなら2^n個
のページが連続)
? higher orderのページはなるべく割り当てないよ
うにして、fragmentationを防ぐ。
45

バディシステム(2)
? 調べきれてないので簡単にポイントだけ
? バディシステムはstruct zone毎に独立して管理される。?
nodeまたぎやzoneまたぎの連続ページ割当というのはあり得ないということ。
? freelistは、各order 各migrate_typeに作られる。?
migrate_typeはpage migrationとかCMA(continuous memory allocation)に使わ
れる種別値。まだ理解できてない???
? order=0の場合のみ、per-cpu cacheがある。?
order=0でのアロケーションが失敗すると、per-cpu cacheを充填した上でページを
割り当てる。
? ページは用途に応じてhot or coldがある。これはキャッシュに乗っている可能性が高
い/低いことを示すタームで、割当?解放時に、lruの先頭から/へ割当/解放するか、lru
の末尾にするかを切り分けることができる。デフォルトでは割当/解放ともhot扱い。
46

バディアロケータ
? get_page_from_freelist()の最後に実行される
bu?ered_rmqueue()が本体
? バディシステムからメモリを取ってくる
? 注：watermarkやdirtylimitをクリアしてから実行
されるわけだが、ロックは取ってるわけではないの
で、結局タイミングによっては失敗する可能性あり
47

bu?ered_rmqueue()
? struct page *buffered_rmqueue(…)?
{?
bool cold = ((gfp_flags & __GFP_COLD) != 0);?
again:?
if (likely(order == 0)) {?
" " pcp = &this_cpu_ptr(zone->pageset)->pcp; /* CPU毎 */?
" " list = &pcp->lists[migratetype]; /* migrate type毎 */?
" " if (list_empty(list)) {?
" " " /* rmqueue_bulk()でバディシステムから補充 */?
" " }?
" " if (cold) /* hot or cold */?
" " " page = list_entry(list->prev, struct page, lru);?
" " else?
" " " page = list_entry(list->next, struct page, lru);?
} else {?
" " page = __rmqueue(); /* バディシステムから直接取得 */?
" }?
" if (prep_new_page(page, order, gfp_flags))?
" " goto again;?
" return page;?
}
48

5. ページフレーム解放

order=0なページ解放
? free_hot_cold_page(struct page *page , bool cold)
? per-cpuのキャッシュ(zone::pageset)を取り出し、
? hotページは同キャッシュのLRUリストの先頭に、?
coldページは同キャッシュのLRUリストの末尾に追加
? per-cpuキャッシュのフリーページが閾値を超えた場
合は、バディシステムへページを返す。
50

order>0なページ解放
? free_one_page()
? バディシステムへ指定されたorder分のページを
返す
? 同orderリスト内で連続ページが作成出来たら、
連結して、zone->free_area[order]から?
zone->free_area[order+1]へ移動
51

99. 今後
1. ページ回収
2. プロセス空間
3. スラブ(slub, slab, slob)
52

狠狠撸

Page frame management

More Related Content

Page frame management