概要
「詳解Linux Kernel」を参考にVersion 2.6.11のコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelのx86とする。
今回はメモリ管理について見ていく。
メモリ管理
x86ではセグメンテーションとページングによって物理メモリが管理され、RAMの一部はカーネルコードや静的なカーネルデータによって永続的に使用される。残りのRAMは動的に確保及び解放が行われる。
参考: https://www.amazon.co.jp/dp/487311313X
ページフレーム
ページフレームは物理メモリをある一定サイズで区画分けしたもので、IntelのPentiumプロセッサではページフレームのサイズとして4KBもしくは4MB(PSE有効時)(PAEを使用する場合は2MB)が使用可能である。しかし基本的には以下の理由から4KBを採用している。
- ページフォルト発生時にページの存在確認やページの使用が可能かなどの確認が容易。
- メモリ及びディスク間の転送は小さい単位で行う方がより効率的。
ページディスクリプタ
カーネルはページフレームの状態を把握しており、カーネルのコード用もしくはデータ用なのか、また通常のプロセス用などを識別する。加えてそのページフレームが使用されているかなどの情報も管理している。ページフレームの情報はページディスクリプタとしてpage構造体が定義されている。
// include/linux/mm.h struct page { page_flags_t flags; /* ページフレームの状態 */ atomic_t _count; /* ページフレームの参照カウンタ */ atomic_t _mapcount; /* 当該ページフレームを参照しているページフレームエントリ */ unsigned long private; /* 自由に使用が可能なメンバ */ struct address_space *mapping; /* このページフレームをページキャッシュまたは無名リージョンとして使用する際に等メンバを使用する */ pgoff_t index; /* マッピング時のオフセット */ struct list_head lru; /* "Least Recently Used"アルゴリズムでページフレームのスワップなどを行う際に使用 */ #if defined(WANT_PAGE_VIRTUAL) void *virtual; /* カーネル空間の仮想アドレス(kmappedされていない時はNULL) */ #endif /* WANT_PAGE_VIRTUAL */ };
_countメンバは参照カウンタで、対応するページフレームが未使用(参照数が0)の際には-1が設定される。指定ページフレームの参照数を返すマクロであるpage_count()は以下のように定義されており、カウンタ値に1を加算した値を返すのがわかる。
// include/linux/mm.h #define page_count(p) (atomic_read(&(p)->_count) + 1)
flagsメンバはページフレームの状態を返すメンバで各種状態として以下のような定数が定義されている。
// include/linux/page-flags.h #define PG_locked 0 /* ページがロックされている。I/Oの前後でセット/アンセットする */ #define PG_error 1 /* ページ上でI/Oエラーが発生した */ #define PG_referenced 2 /* ページに最近アクセスがあった。スワップアウトの対象を選択する時などに使用される */ #define PG_uptodate 3 /* ページ上のデータが有効である、I/Oエラーがなく正常に読み込まれた際に設定される */ #define PG_dirty 4 /* ページの内容が変更されている */ #define PG_lru 5 /* ページがアクティブまたは非アクティブLRUリスト内に存在する */ #define PG_active 6 /* ページがアクティブLRUリスト内に存在する */ #define PG_slab 7 /* スラブ用のページである */ #define PG_highmem 8 /* ZONE_HIGHMEMゾーン内のページである */ #define PG_checked 9 /* ファイルシステムで使用される */ #define PG_arch_1 10 /* x86では未使用 */ #define PG_reserved 11 /* カーネルが予約済みもしくは使用不可のページ。スワップアウトされない */ #define PG_private 12 /* privateメンバがデータを保持している */ #define PG_writeback 13 /* ページ上のデータがディスクに書き戻しされている */ #define PG_nosave 14 /* サスペンドやレジューム時に使用する */ #define PG_compound 15 /* 拡張ページングの一部 */ #define PG_swapcache 16 /* スワップキャッシュ用のページ */ #define PG_mappedtodisk 17 /* ディスク上のブロックに対応するデータを保持している */ #define PG_reclaim 18 /* メモリ回収のためこのページをディスクに書き出す */ #define PG_nosave_free 19 /* サスペンドやレジューム時に使用する */
余談だが上記のフラグはソースコード内にも丁寧なコメントが存在し、各フラグについてどういった用途に使用されるのか詳しく解説されている。
全てのページディスクリプタはmem_map配列によって保持されており以下のように定義されている。
// mm/memory.c struct page *mem_map;
NUMA(Non-Uniform Memory Architecture: 不均等メモリアクセス)
NUMAアーキテクチャではノードという概念が存在し、一組みのCPUとメモリから構成される。同じノード上にあるCPUからメモリへのアクセスは高速に行われるが、異なるノードに存在するメモリへのアクセスは低速である。
参考: https://support.hpe.com/hpsc/doc/public/display?docId=emr_na-c03261871
Linuxでは各ノードに存在するメモリは複数のゾーンで構成されており、各ノードはそのゾーンをpg_data_t構造体型のノードディスクリプタで管理している。カーネルはメモリを割り当てを行う際に以下のzone_list構造体型のメンバであるnode_zonelistsから希望するゾーンを指定する。
// include/linux/mmzone.h typedef struct pglist_data { struct zone node_zones[MAX_NR_ZONES]; /* ゾーンディスクリプタの配列 */ struct zonelist node_zonelists[GFP_ZONETYPES]; /* ページ割り当てに使用するzone_listの配列 */ int nr_zones; /* ノードに存在するゾーン数 */ struct page *node_mem_map; /* ノードが扱うのページディスクリプタ */ struct bootmem_data *bdata; /* システム初期化時に使用 */ unsigned long node_start_pfn; /* ノード内の先頭ページフレームのインデックス */ unsigned long node_present_pages; /* メモリホールを除いたページフレーム数 */ unsigned long node_spanned_pages; /* メモリホールを含んだページフレーム数 */ int node_id; /* ID */ struct pglist_data *pgdat_next; /* メモリノードの次の要素 */ wait_queue_head_t kswapd_wait; /* kswapdが使用する待ちキュー */ struct task_struct *kswapd; /* kswapdのプロセスディスクリプタ */ int kswapd_max_order; /* kswapdが回収するブロック数(2を底とした対数) */ } pg_data_t;
全てのノードディスクリプタはリストで管理されており、先頭要素をpgdat_listが保持している。
// include/linux/mmzone.h extern struct pglist_data *pgdat_list;
IBM互換機のようにUMA(Uniform Memory Access: 均等メモリアクセス)を採用している場合には、Linuxではシステム上の全ての物理メモリを1つノードとして扱う。pgdat_list変数は1つのノードディスクリプタしか保持しない。
メモリゾーン
ページフレームはメモリの格納単位で、カーネルデータ、ユーザデータ、ディスクのバッファなどに使うことが可能。しかしx86アーキテクチャでは以下の制約が存在する。
- 古いISAバスのDMA(Direct Memory Access)回路はRAM先頭16MBしかアクセスできない。
- 32bitコンピュータに大量のRAMを搭載した場合CPUは全てのメモリにアクセスすることができない(アクセス可能なアドレスの範囲が狭いため)
上記の制約に対処するためにLinuxでは全ての物理メモリを3つのゾーンに分類している。
// include/linux/mmzone.h #define ZONE_DMA 0 /* 先頭から16MBまでのページフレームが存在するゾーン */ #define ZONE_NORMAL 1 /* 16MB ~ 896MBまでのページフレームが存在するゾーン */ #define ZONE_HIGHMEM 2 /* 896MB以降のページフレームが存在するゾーン */
ZONE_DMAは古いISAが使用するページフレームが存在する。ZONE_DMA及びZONE_NORMALには0xC000000以降のリニアアドレス空間を通じてカーネルからアクセスすることができる。しかしZONE_HIGHMEMにはアクセスできない。
各メモリゾーンはzone構造体型のゾーンディスクリプタを保持している。
// include/linux/mmzone.h struct zone { unsigned long free_pages; /* 空きページフレーム数 */ /* ゾーンの予約空きページ数, ページフレーム回収下限閾値, ページフレーム回収上限閾値 */ unsigned long pages_min, pages_low, pages_high; unsigned long lowmem_reserve[MAX_NR_ZONES]; /* メモリ不足の状況を回避するために確保するページフレームの最低予約数 */ struct per_cpu_pageset pageset[NR_CPUS]; /* ページフレームの独自キャッシュを実現するのに用いられる */ spinlock_t lock; /* ロック */ struct free_area free_area[MAX_ORDER]; /* ゾーン内の空きページフレームのサイズ別ブロックリスト */ ZONE_PADDING(_pad1_) /* Fields commonly accessed by the page reclaim scanner */ spinlock_t lru_lock; /* ページリストが使用するロック */ struct list_head active_list; /* ゾーン内のアクティブページリスト */ struct list_head inactive_list; /* ゾーン内の非アクティブページリスト */ unsigned long nr_scan_active; /* アクティブページ数(メモリ回収時に算出) */ unsigned long nr_scan_inactive; /* 非アクティブページ数(メモリ回収時に算出) */ unsigned long nr_active; /* アクティブページリスト内のページ数 */ unsigned long nr_inactive; /* 非アクティブページリスト内のページ数 */ unsigned long pages_scanned; /* ページフレームの回収時に使用する */ int all_unreclaimable; /* 全てのページフレームが回収不可能かどうか */ int temp_priority; /* 一時的な優先度 */ int prev_priority; /* ゾーンの優先度(0 ~ 12) */ wait_queue_head_t * wait_table; /* あるページの処理を待っているプロセスの待ちキューハッシュテーブル */ unsigned long wait_table_size; /* 待ちキューハッシュテーブルのサイズ */ unsigned long wait_table_bits; /* 待ちキューハッシュテーブルのサイズ(2の累乗) */ /* * Discontig memory support fields. */ struct pglist_data *zone_pgdat; /* ゾーンが属するメモリゾーン */ struct page *zone_mem_map; /* ゾーンの先頭ページディスクリプタへのポインタ */ unsigned long zone_start_pfn; /* ゾーンの先頭ページフレーム番号 */ unsigned long spanned_pages; /* ページ数(メモリホールを含む) */ unsigned long present_pages; /* ページ数(メモリホールを含まない) */ char *name; /* ゾーン名へのポインタ(DMA|Normal|HighMem) */ } ____cacheline_maxaligned_in_smp;
全てのゾーンはzone_table配列で管理され、free_area_init_core()関数で初期化される。
// include/linux/mm.h extern struct zone *zone_table[]; // mm/page_alloc.c static void __init free_area_init_core(struct pglist_data *pgdat, unsigned long *zones_size, unsigned long *zholes_size) { unsigned long i, j; const unsigned long zone_required_alignment = 1UL << (MAX_ORDER-1); int cpu, nid = pgdat->node_id; unsigned long zone_start_pfn = pgdat->node_start_pfn; pgdat->nr_zones = 0; init_waitqueue_head(&pgdat->kswapd_wait); pgdat->kswapd_max_order = 0; for (j = 0; j < MAX_NR_ZONES; j++) { struct zone *zone = pgdat->node_zones + j; unsigned long size, realsize; unsigned long batch; zone_table[NODEZONE(nid, j)] = zone; realsize = size = zones_size[j]; if (zholes_size) realsize -= zholes_size[j]; if (j == ZONE_DMA || j == ZONE_NORMAL) nr_kernel_pages += realsize; ...
先ほど見たページディスクリプタはそのページディスクリプタ自身が属しているゾーン及びノードの情報を保持しており、ページディスクリプタのflagsメンバの高位ビットがzone_tableのインデックスとなる。ページディスクリプタが所属するゾーンディスクリプタの取得を行うpage_zone()関数は以下のように定義されており、ページディスクリプタのメンバであるflagsメンバの高位ビットをインデックスとして使用している。
// include/linux/mm.h static inline struct zone *page_zone(struct page *page) { return zone_table[page->flags >> NODEZONE_SHIFT]; }
空きページフレームの予約
通常のメモリ要求では空きメモリが存在すれば即座にそのメモリを割り当て、メモリが不足している場合にはメモリの回収をする必要がありメモリ割り当ては中断される。処理を中断することができない割り込みやクリティカル区間での"不可分な"メモリ要求も存在し、この場合にはメモリ割り当ては失敗する。カーネルはメモリ不足の際に"不可分な"メモリ要求の失敗を回避するために予めある程度のページフレームを予約している。
ゾーン毎のページアロケータ
ゾーン毎のページアロケータは連続したページフレームの割り当て要求を処理するカーネルのサブシステムで、アロケータ及びバディシステムから構成される。
ゾーンアロケータは動的なメモリの割り当てや解放要求を受け、割り当ての場合であれば要求のあったサイズの連続するページフレームを割り当て可能なゾーンを探す。各ゾーンではバディシステムがページフレームを扱う。
参考: https://www.amazon.co.jp/dp/487311313X
ページフレームの要求及び解放
ページフレームの要求や解放で用いる関数では以下のフラグを使用する。
// include/linux/gfp.h #define __GFP_DMA 0x01 /* ZONE_DMAに属するページフレームを取得する */ #define __GFP_HIGHMEM 0x02 /* ZONE_HIGHMEMに属するページフレームを取得する */ #define __GFP_WAIT 0x10 /* 空きページフレームの取得が完了するまでプロセスを待機させることが可能 */ #define __GFP_HIGH 0x20 /* 予約ページフレームの使用を許可する */ #define __GFP_IO 0x40 /* ページフレーム解放の際にI/O転送の発生を許可する */ #define __GFP_FS 0x80 /* ファイルシステム関連の操作を許可する */ #define __GFP_COLD 0x100 /* 要求したページフレームが不活性である */ #define __GFP_NOWARN 0x200 /* メモリ割り当てに失敗した際の警告を出さない */ #define __GFP_REPEAT 0x400 /* 成功するまで複数回に渡りメモリ割り当てをリトライする(失敗の可能性がある) */ #define __GFP_NOFAIL 0x800 /* 成功するまでメモリ割り当てをリトライする(成功するまで繰り返す) */ #define __GFP_NORETRY 0x1000 /* メモリ割り当てに失敗してもリトライしない */ #define __GFP_NO_GROW 0x2000 /* スラブアロケータがスラブキャッシュを大きくしないことを示す */ #define __GFP_COMP 0x4000 /* 拡張ページング領域に属するページフレームを取得する */ #define __GFP_ZERO 0x8000 /* ゼロクリアしたページを割り当てる */ /* これらいずれかが指定されていない場合カーネルはクラッシュする */ #define GFP_LEVEL_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS| \ __GFP_COLD|__GFP_NOWARN|__GFP_REPEAT| \ __GFP_NOFAIL|__GFP_NORETRY|__GFP_NO_GROW|__GFP_COMP) #define GFP_ATOMIC (__GFP_HIGH) #define GFP_NOIO (__GFP_WAIT) #define GFP_NOFS (__GFP_WAIT | __GFP_IO) #define GFP_KERNEL (__GFP_WAIT | __GFP_IO | __GFP_FS) #define GFP_USER (__GFP_WAIT | __GFP_IO | __GFP_FS) #define GFP_HIGHUSER (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HIGHMEM) #define GFP_DMA __GFP_DMA
実際のページフレームの割り当て要求では__GFPの接頭語から始めるフラグを組み合わせたGFP_の接頭語から始まるフラグを用いる。
__GFP_DMA及び__GFP_HIGHMEMはゾーン修飾子(zone modifier)で、空きページフレームを探す対象ゾーンを指定する。
__GFP_DMAフラグが指定されている場合にはZONE_DMAからのみページフレームを割り当てる。__GFP_HIGHMEMフラグが指定されている場合にはZONE_HIGHMEM,ZONE_NORMAL,ZONE_DMAの順に割り当てが可能なゾーンからページフレームを割り当てる。- 上記2つのフラグが両者とも指定されていない場合には
ZONE_NORMAL,ZONE_DMAの順に割り当てが可能なゾーンからページフレームを割り当てる。
ページフレームの獲得
ページフレームの獲得には以下の関数を使用する。
// include/linux/gfp.h /* * 2のorder乗に連続するページフレームを取得する。 * 戻り値は先頭ページフレームに対応するページディスクリプタ */ static inline struct page * alloc_pages(unsigned int gfp_mask, unsigned int order) { if (unlikely(order >= MAX_ORDER)) // バリデーション return NULL; return alloc_pages_current(gfp_mask, order); } // 単一のページフレームを取得する。戻り値はページディスクリプタ #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0) // mm/page_alloc.c // ゼロクリアされた単一のページフレームを取得する。戻り値はページフレームのリニアアドレス fastcall unsigned long get_zeroed_page(unsigned int gfp_mask) { struct page * page; page = alloc_pages(gfp_mask | __GFP_ZERO, 0); // ゼロクリア用のフラグを指定しページディスクリプタを取得 if (page) return (unsigned long) page_address(page); // ディスクリプタからリニアアドレスに変換 return 0; } // mm/page_alloc.c /* * 2のorder乗に連続するページフレームを取得する。 * 戻り値は先頭ページフレームのリニアアドレスを返す。 */ fastcall unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order) { struct page * page; page = alloc_pages(gfp_mask, order); // ページディスクリプタを取得 if (!page) return 0; return (unsigned long) page_address(page); // ディスクリプタからリニアアドレスに変換 } // include/linux/gfp.h // 単一のページフレームを取得する。戻り値はページフレームのリニアアドレス #define __get_free_page(gfp_mask) \ __get_free_pages((gfp_mask),0) // include/linux/gfp.h /* * 2のorder乗に連続するページフレームをZONE_DMAから取得する。 * 戻り値は先頭ページフレームのリニアアドレスを返す。 */ #define __get_dma_pages(gfp_mask, order) \ __get_free_pages((gfp_mask) | GFP_DMA,(order))
ページフレームの解放
ページフレームの解放には以下の関数を使用する。
// include/linux/gfp.h /* * ページが予約されておらず且つ参照カウンタ減算の結果が0の場合は指定のページを解放する */ fastcall void __free_pages(struct page *page, unsigned int order) { if (!PageReserved(page) && put_page_testzero(page)) { if (order == 0) free_hot_page(page); else __free_pages_ok(page, order); } } // include/linux/gfp.h // ページディスクリプタで指定された単一のページを解放する。 #define __free_page(page) __free_pages((page), 0) // mm/page_alloc.c // アドレスで指定したページフレームに対応するページディスクリプタを解放する。 fastcall void free_pages(unsigned long addr, unsigned int order) { if (addr != 0) { BUG_ON(!virt_addr_valid((void *)addr)); __free_pages(virt_to_page((void *)addr), order); } } // include/linux/gfp.h // ページのリニアアドレスで指定されたページを解放する。 #define free_page(addr) free_pages((addr),0)
バディシステム
カーネルは効率的に連続したページフレームの割り当てを行う必要があり、フラグメンテーションに対応する必要がある。対応策として以下の2点があげられる。
- ページング機構を用いて非連続なページフレームを連続したリニアアドレス空間にマッピングする。
- 小さなサイズのページフレーム要求を受け取った際には大きく連続したページフレームを分割し割り当てることはせず、小さく連続したページフレームを割り当てる。
後者がカーネルに向いており、それには以下のような理由が存在する。
- 要求によっては物理的に連続している必要がある。DMAコントローラは複数のディスクセクタにI/O処理をかける際、ページング機構に用いずアドレスバスに直接アクセスするため連続したページフレームである必要がある。
- 連続したページフレームが必要でない場合でも、連続したページフレームを割り当てるとページテーブルの切り替えが発生する頻度が減りTLBミスが減少するため効率よくメモリアクセスを行うことができる。
- 大きく連続した物理メモリに対して大きなページサイズでアクセスすることが可能となり効率的にメモリにアクセスすることが可能になる。
Linuxではバディシステムというサブシステムを用いてフラグメンテーションの問題を解決する。全ての空きページフレームを1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024個の連続したページフレームのブロックとして分類し、各ブロックのサイズ毎に11個のリストを形成する。
1MB(ページフレーム256個分)のメモリ割り当て要求があった際には、まず256個のリストから連続したページフレームのブロックを探し見つかればそれを割り当てる。もし見つからなければ1つ大きいサイズのリスト(今回であれば512個分)からブロックを探し、ブロックが見つかるまで大きなサイズのリストへと繰り返す。仮に1024個のリストからブロックを割り当てる場合には256個(1MB)分連続したページフレームを割り当てた後、残りの768個のブロックは512個のリストに1ブロック、256個のリストに1ブロック繋ぐ。要求されたサイズのメモリが見つからない場合にはエラーを返す。
開放時も同様に解放したメモリブロックを出来るだけ大きく連続したページフレームのブロックにまとめ適切なサイズをリストに繋ぐ。
Linuxでは各ゾーンで異なるバディシステムを用いており、x86では3つのバディシステムを使用している。1つ目はZONE_DMA用のページフレームのみを処理し、2つ目はZONE_NORMALのページフレームを、そして3つ目はZONE_HIGHMEMのページフレームを処理する。バディシステムは以下のデータを使用する。
- 全てのページフレームを保持するページディスクリプタリストの
mem_map配列。ゾーンディスクリプタ(struct zone)のzone_mem_mapメンバ(struct page *)はゾーンで扱うページディスクリプタリスト(mem_map配列の部分集合)の先頭要素で、先頭のページディスクリプタのsizeメンバはこの部分集合のサイズである。 - ゾーンディスクリプタの
free_areaメンバ。free_area構造体型で各ブロックサイズに対応したMAX_ORDER個の要素を保持している。
// include/linux/mmzone.h #define MAX_ORDER 11
free_area構造体は以下のように定義されている。
// include/linux/mmzone.h struct free_area { struct list_head free_list; // リストの先頭ページディスクリプタを指す unsigned long nr_free; };
ゾーンディスクリプタのfree_areaメンバは双方好循環リストで、n番目にあるメンバの要素は2のn乗サイズの連続したページフレームブロックのリストに対応するfree_area構造体変数を指している。free_areaのfree_listメンバはページブロックの先頭ページディスクリプタを指しており、各ページブロックはページディスクリプタのlruメンバを介して繋がっている。nr_freeメンバは空きブロック数を表す。ブロックの先頭ページディスクリプタのprivateメンバにはブロックサイズの2を底とする対数を保持している。
ブロックの割り当て
ブロックの割り当てには__rmqueue()を使用する。
/* * 呼び出し前にゾーンディスクリプタをロックする必要がある。 * zone: 指定ゾーンからブロックの割り当てを行う * order: 要求ページ数の2を底とする対数 */ static struct page *__rmqueue(struct zone *zone, unsigned int order) { struct free_area * area; unsigned int current_order; struct page *page; /* 指定サイズからそれ以上のサイズのブロックリストをトラバース */ for (current_order = order; current_order < MAX_ORDER; ++current_order) { area = zone->free_area + current_order; // 指定サイズのブロックリストを取得 if (list_empty(&area->free_list)) // リストに空きブロックが無い場合 continue; page = list_entry(area->free_list.next, struct page, lru); // ブロックの先頭ページディスクリプタを取得 list_del(&page->lru); // ブロックリストから外す rmv_page_order(page); // privateメンバ(ブロックサイズの２を底とする対数)をクリア area->nr_free--; // 空きブロック数をデクリメント zone->free_pages -= 1UL << order; // 空きページ数を減算 /* 指定サイズより大きいブロックのリストから連続するページを割り当てた場合に余りのブロックを繋ぎ直す処理 */ return expand(zone, page, order, current_order, area); // 先頭ページディスクリプタを返す。 } return NULL; }
ブロックの解放
ページフレームの解放には__free_pages_bulk()を使用する。
// mm/page_alloc.c /* * page: 解放するブロックの先頭ページディスクリプタ * base: ゾーンディスクリプタが保持するページディスクリプタリストの先頭要素 * zone: ゾーンディスクリプタ * order: ブロックサイズの2を底とした対数 */ static inline void __free_pages_bulk (struct page *page, struct page *base, struct zone *zone, unsigned int order) { unsigned long page_idx; struct page *coalesced; int order_size = 1 << order; // 実際のブロックサイズ if (unlikely(order)) destroy_compound_page(page, order); // ページディスクリプタの拡張ページフラグを落とす page_idx = page - base; // ページディスクリプタリストのインデックスを算出 zone->free_pages += order_size; // ブロックサイズ分を空きページサイズに加算 while (order < MAX_ORDER-1) { // バディシステムとして結合可能であるか調べていく struct free_area *area; struct page *buddy; int buddy_idx; buddy_idx = (page_idx ^ (1 << order)); // バディシステムのインデックスを取得 buddy = base + buddy_idx; // if (!page_is_buddy(buddy, order)) // 空きブロックの先頭でない break; /* Move the buddy up one level. */ list_del(&buddy->lru); area = zone->free_area + order; // 適切なサイズのブロックリストを取得 area->nr_free--; // 空きブロック数をデクリメント rmv_page_order(buddy); // ブロックサイズ(の2を底とする対数)の値を削除 page_idx &= buddy_idx; // order++; // 次のサイズへ } coalesced = base + page_idx; // 結合したページフレームn set_page_order(coalesced, order); // 結合したブロックのサイズを保存 list_add(&coalesced->lru, &zone->free_area[order].free_list); // 適切なリストに繋ぎ直す。 zone->free_area[order].nr_free++; // 空きブロック数をインクリメント }
CPU毎のページキャッシュ
単一のページフレームに対する割り当て要求や解放は頻繁に発生する。そのような要求の効率化のために導入されたのがCPU毎のページフレームキャッシュである。各キャッシュは割り当て済みのページフレームをいくつか保持しており、これを単一のページフレームに対する割り当て要求を受け取った際に使用する。
実際には各メモリゾーンがホットキャッシュ及びコールドキャッシュの2種類のキャッシュを保持しており、ホットキャッシュはCPUのハードウェアキャッシュに載っている可能性が高いキャッシュ、コールドキャッシュがそうでないキャッシュとなる。
ホットキャッシュから割り当てられたページフレームはCPUのハードウェアキャッシュに載っていることが多いため、そのページフレームに対するアクセスを高速に行うことが可能となる。コールドキャッシュから割り当てたページフレームはCPUのハードウェアキャッシュには載らないDMA操作を行うようなページフレームに使用する。
CPU毎のページフレームキャッシュはゾーンディスクリプタのpageset[NR_CPUS]メンバが保持しており、CPU数分の値を保持している。pagesetはper_cpu_pageset構造体型で、当該構造体は以下のように定義されている。
// include/linux/mmzone.h struct per_cpu_pageset { struct per_cpu_pages pcp[2]; /* 0: hot. 1: cold */ #ifdef CONFIG_NUMA unsigned long numa_hit; /* allocated in intended node */ unsigned long numa_miss; /* allocated in non intended node */ unsigned long numa_foreign; /* was intended here, hit elsewhere */ unsigned long interleave_hit; /* interleaver prefered this zone */ unsigned long local_node; /* allocation from local node */ unsigned long other_node; /* allocation from other node */ #endif } ____cacheline_aligned_in_smp;
per_cpu_pageset構造体のメンバであるpcpは2つの要素を持つ配列として定義されており、それぞれホットキャッシュとコールドキャッシュとなっている。pcpはper_cpu_pages構造体で以下のように定義されている。
// include/linux/mmzone.h struct per_cpu_pages { int count; /* キャッシュ内のページフレーム数 */ int low; /* キャッシュ内のページフレーム数の下限。下回ると補充される */ int high; /* キャッシュ内のページフレーム数の上限。上回ると解放される */ int batch; /* 一度に補充/解放されるページフレーム数 */ struct list_head list; /* キャッシュ内のページフレームリスト */ };
キャッシュのサイズやキャッシュに含まれるページフレームリストなどを保持しているのがわかる。
ページキャッシュからのページフレーム割り当て
buffered_rmqueue関数は指定のゾーンからページフレームを割り当てる関数だが、割り当て要求がサイズが1である場合にはCPU毎のページフレームキャッシュから割り当てる。
// mm/page_alloc.c /* * zone: 指定のゾーン * order: 要求サイズの2を底とした対数 * gfp_flags: フラグ値("__GFP_COLD"が指定された場合にはコールドキャッシュからのページ割り当てを試みる) */ static struct page * buffered_rmqueue(struct zone *zone, int order, int gfp_flags) { unsigned long flags; struct page *page = NULL; int cold = !!(gfp_flags & __GFP_COLD); // フラグ値からホット/コールドを決定 if (order == 0) { // 要求されたページフレームが1つである。 struct per_cpu_pages *pcp; pcp = &zone->pageset[get_cpu()].pcp[cold]; // キャッシュを取得 local_irq_save(flags); // ロック if (pcp->count <= pcp->low) // キャッシュされているページ数が下限以下である場合 pcp->count += rmqueue_bulk(zone, 0, pcp->batch, &pcp->list); // キャッシュにページを補充 if (pcp->count) { // キャッシュにページが存在する page = list_entry(pcp->list.next, struct page, lru); // ページを取得 list_del(&page->lru); // リストから削除 pcp->count--; // ページ数のカウンタをデクリメント } local_irq_restore(flags); // アンロック put_cpu(); // プリエンプト可能に } if (page == NULL) { // ページが割り当てられていない = 要求ページ数が1ではない spin_lock_irqsave(&zone->lock, flags); // ロック page = __rmqueue(zone, order); // ページの割り当て spin_unlock_irqrestore(&zone->lock, flags); // アンロック } if (page != NULL) { // 割り当てが完了している mod_page_state_zone(zone, pgalloc, 1 << order); prep_new_page(page, order); // 割り当てられた先頭ページの初期化 if (gfp_flags & __GFP_ZERO) // ゼロクリア prep_zero_page(page, order, gfp_flags); if (order && (gfp_flags & __GFP_COMP)) // 拡張ページングである場合 prep_compound_page(page, order); } return page; // 割り当てた先頭ページを返す }
ページキャッシュへのページフレーム解放
ホットキャッシュ及びコールドキャッシュの解放にはfree_hot_page()及びfree_cold_page()を使用する。`
// mm/page_alloc.c void fastcall free_hot_page(struct page *page) { free_hot_cold_page(page, 0); } void fastcall free_cold_page(struct page *page) { free_hot_cold_page(page, 1); }
上記からもわかる通りfree_hot_cold_page()のラップ関数となっている。free_hot_cold_page()の定義は以下。
// mm/page_alloc.c /* * page: 解放対象ページ * cold: コールドキャッシュかどうか(1: コールドキャッシュ, 0: ホットキャッシュ) */ static void fastcall free_hot_cold_page(struct page *page, int cold) { struct zone *zone = page_zone(page); // ページディスクリプタから所属するゾーンを取得 struct per_cpu_pages *pcp; unsigned long flags; arch_free_page(page, 0); // マッピングを解除 kernel_map_pages(page, 1, 0); inc_page_state(pgfree); if (PageAnon(page)) page->mapping = NULL; free_pages_check(__FUNCTION__, page); // ページが有効であるか pcp = &zone->pageset[get_cpu()].pcp[cold]; // キャッシュを取得 local_irq_save(flags); // ロック if (pcp->count >= pcp->high) // キャッシュ内のページ数が上限を超えている場合 pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0); // キャッシュされているページを解放 list_add(&page->lru, &pcp->list); // 解放されたページをリストへ追加 pcp->count++; // カウントをインクリメント local_irq_restore(flags); // アンロック put_cpu(); // プリエンプト可能に }
カーネルの2.6.11ではコールドキャッシュに対してページフレームを解放することはなく、常に解放するページはホットキャッシュに対して処理を行う。
ゾーンアロケータ
ゾーンアロケータはページフレーム割り当てのフロントエンドにあたり、割り当て要求サイズの空きを保持するメモリゾーンを特定する。ゾーンアロケータでは以下のことに考慮する必要がある。
- 可能な限り予約ページの使用は回避する。
- 空きメモリが不足し且つカレントプロセスが中断可能な場合はメモリの回収を行なった後、再度割り当て処理をやり直す。
- 可能な限り小さなゾーン(ZONE_DMAなど)の使用を回避する。
ページフレームの割り当て
前述のようにページの割り当てには主にalloc_pages()で行われる。
// include/linux/gfp.h alloc_pages(unsigned int gfp_mask, unsigned int order) { if (unlikely(order >= MAX_ORDER)) return NULL; return alloc_pages_current(gfp_mask, order); }
alloc_pages_current()は以下のように定義されている。
// mm/mempolicy.c /** * gfp: フラグ値 * order: 要求サイズ(の2を底とする対数) */ struct page *alloc_pages_current(unsigned gfp, unsigned order) { struct mempolicy *pol = current->mempolicy; if (!pol || in_interrupt()) // ポリシーが存在しないまたは割り込みコンテキストである場合 pol = &default_policy; // デフォルトのポリシーを使用 if (pol->policy == MPOL_INTERLEAVE) return alloc_page_interleave(gfp, order, interleave_nodes(pol)); return __alloc_pages(gfp, order, zonelist_policy(gfp, pol)); }
内部で呼び出されている__alloc_pages()の定義は以下。当該関数が主要な処理を行う。
// mm/page_alloc.c /* * gfp_mask: フラグ値 * order: 要求サイズ(の2を底とする対数) * zonelist: ゾーンリスト */ struct page * fastcall __alloc_pages(unsigned int gfp_mask, unsigned int order, struct zonelist *zonelist) { const int wait = gfp_mask & __GFP_WAIT; struct zone **zones, *z; struct page *page; struct reclaim_state reclaim_state; struct task_struct *p = current; int i; int classzone_idx; int do_retry; int can_try_harder; int did_some_progress; might_sleep_if(wait); /* リアルタイムタスクまたは割り込みコンテキスト内でない、または待機が不可能な場合 */ can_try_harder = (unlikely(rt_task(p)) && !in_interrupt()) || !wait; // 複数回に渡りページ割り当てを試みる zones = zonelist->zones; /* ゾーンリストを取得 */ /* ゾーンが存在しない(起こりえないと考えられている) */ if (unlikely(zones[0] == NULL)) { return NULL; } classzone_idx = zone_idx(zones[0]); // ゾーンインデックスを取得 restart: /* ゾーンリストをトラバースしていく */ for (i = 0; (z = zones[i]) != NULL; i++) { /* * 閾値をチェック。以下を確認する * - 要求ページ数を割り当てた後、ゾーンに設定されている空きページ数の下限値を下回らないか * - 要求ページ数を割り当てた後、ページブロックリストに各サイズのブロックがある程度の残るかどうか */ if (!zone_watermark_ok(z, order, z->pages_low, classzone_idx, 0, 0)) continue; page = buffered_rmqueue(z, order, gfp_mask); // 要求ページの割り当て if (page) // 割り当てに成功した場合 goto got_pg; } /* ゾーンリストをトラバース */ for (i = 0; (z = zones[i]) != NULL; i++) wakeup_kswapd(z, order); // 各ゾーン用にページフレーム回収用のカーネルスレッドを起動 /* ゾーンリストをトラバース */ for (i = 0; (z = zones[i]) != NULL; i++) { /* * 閾値をチェック。以下を確認する * - 要求ページ数を割り当てた後、ゾーンに設定されている空きページ数の下限値を下回らないか * - 要求ページ数を割り当てた後、ページブロックリストに各サイズのブロックがある程度の残るかどうか */ if (!zone_watermark_ok(z, order, z->pages_min, classzone_idx, can_try_harder, gfp_mask & __GFP_HIGH)) // 予約ページの使用も許可 continue; page = buffered_rmqueue(z, order, gfp_mask); // ページの割り当て if (page) // 割り当てに成功した場合 goto got_pg; } /* 割り込み処理でなく且つページフレーム回収用のプロセスである場合 */ if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) && !in_interrupt()) { /* * ゾーンリストをトラバース * 先ほどのチェックは行わないため下限値は考慮しない * メモリ不足時用の予約ページフレームが使用可能 */ for (i = 0; (z = zones[i]) != NULL; i++) { page = buffered_rmqueue(z, order, gfp_mask); // メモリの割り当て if (page) // 成功した場合 goto got_pg; } goto nopage; // ページ割り当て失敗 } /* プロセスが待機不可能である場合 */ if (!wait) goto nopage; // ページ割り当て失敗 rebalance: cond_resched(); // 他のプロセスがリスケジュール要求をしている場合は再度プロセススケジューリングを行う p->flags |= PF_MEMALLOC; // カレントプロセスがメモリ回収を行なっているの意 reclaim_state.reclaimed_slab = 0; // p->reclaim_state = &reclaim_state; did_some_progress = try_to_free_pages(zones, gfp_mask, order); // ページフレームの回収 p->reclaim_state = NULL; p->flags &= ~PF_MEMALLOC; // // カレントプロセスがメモリ回収を行なっていないの意 cond_resched(); // 他のプロセスがリスケジュール要求をしている場合は再度プロセススケジューリングを行う /* ページフレームの回収に成功した場合 */ if (likely(did_some_progress)) { /* ゾーンリストをトラバース */ for (i = 0; (z = zones[i]) != NULL; i++) { if (!zone_watermark_ok(z, order, z->pages_min, classzone_idx, can_try_harder, gfp_mask & __GFP_HIGH)) // 予約ページの使用も許可 continue; page = buffered_rmqueue(z, order, gfp_mask); // ページの割り当て if (page) // 割り当てが成功した場合 goto got_pg; } /* ファイルシステムの操作が可能で且つリトライを許可されている場合 */ } else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) { /* ゾーンリストをトラバース */ for (i = 0; (z = zones[i]) != NULL; i++) { if (!zone_watermark_ok(z, order, z->pages_high, classzone_idx, 0, 0)) continue; page = buffered_rmqueue(z, order, gfp_mask); // ページの割り当て if (page) // 割り当てが成功した場合 goto got_pg; } /** * 以下の3つ選択肢から1つを実行する。 * - ランダムにプロセスをキルする * - システムをクラッシュさせる * - 選択したプロセスをキルする */ out_of_memory(gfp_mask); goto restart; } do_retry = 0; if (!(gfp_mask & __GFP_NORETRY)) { // リトライの許可がない場合 if ((order <= 3) || (gfp_mask & __GFP_REPEAT)) // オーダが3以下またはメモリ割り当ての再試行が要求されている場合 do_retry = 1; // リトライを行う if (gfp_mask & __GFP_NOFAIL) // 失敗が不可能な場合 do_retry = 1; // リトライを行う } if (do_retry) { blk_congestion_wait(WRITE, HZ/50); // TASK_UNINTERRUPTIBLEでスリープ goto rebalance; } nopage: if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) { printk(KERN_WARNING "%s: page allocation failure." " order:%d, mode:0x%x\n", p->comm, order, gfp_mask); dump_stack(); } return NULL; // ページの割り当てに失敗 got_pg: zone_statistics(zonelist, z); // ゾーンの統計情報を更新 return page; // 取得したページの先頭を返す }
ページフレームの解放
ページフレームの解放は__free_pages()によって行われる。
// mm/page_alloc.c fastcall void __free_pages(struct page *page, unsigned int order) { /* 予約ページでなく、且つ参照されていない場合 */ if (!PageReserved(page) && put_page_testzero(page)) { if (order == 0) // 単一ページの解放の場合 free_hot_page(page); // ページキャッシュへページフレームを戻す。 else __free_pages_ok(page, order); // パディシステムへページフレームを解放する } } // mm/page_alloc.c /** * ページキャッシュへページフレームを戻す。 */ void fastcall free_hot_page(struct page *page) { free_hot_cold_page(page, 0); // 前述のページキャッシュへのページフレーム解放処理 }