Linux2.2 on x86 での メモリ管理機構 Dec 2001 安田 泰勲

目次 x86アーキテクチャにおけるメモリ管理 Linux におけるメモリ管理 Linuxのメモリ管理の用語 アドレス空間モデルとデータ構造 セグメンテーションとページング アドレッシング Linux におけるメモリ管理 Linuxのメモリ管理の用語 アドレス空間モデルとデータ構造 ページングの流れ ページング処理(demand paging, copy on write…) メモリ領域管理(buddy system, slab allocator)

x86アーキテクチャの メモリ管理機構 x86アーキテクチャでは二種類のメモリ管理機構が利用可能 セグメンテーション機構 ページング機構 複数のタスク(プロセス)が相互に干渉しないで同じプロセッサ上で実行できる様にコード、データ、スタックを分離する機構(required) プロセス(=セグメント)毎に異なるリニアアドレス空間を利用 ページング機構 従来のデマンドページの仮想記憶システム(プログラムの実行環境のページが必要に応じて物理メモリにマップされる)を使用するための機構(optional) プロセス毎に同じリニアアドレス空間を利用

メモリアドレッシング x86アーキテクチャでのメモリアドレス Segmentation Unit Paging Unit Physical address(物理アドレス) プロセッサがアドレスバス上で指定できるアドレス空間。フラット(セグメント化されていない)であり、連続領域(0x0 -0xFFFFFFFFh) 4G(2^32)バイトの物理アドレス空間が利用可能。 Linear address(リニアアドレス) 32bit で表現されるリニアアドレス空間内のページング機構でのアドレス。物理アドレスと同様にフラットでセグメント化されていない。プロセッサは論理アドレスをリニアアドレスに変換してからメモリにアクセスする。 Logical address(論理アドレス) 16bitのセグメントセレクタと32bitのオフセットで構成されるセグメント機構でのアドレス 論理アドレス 物理アドレス リニアアドレス Segmentation Unit Paging Unit

セグメンテーションと ページング Segment selector offset Directory Table offset Segmentation Paging Logical address Linear address Segment selector offset Directory Table offset Page Directory Entry Page Table Entry Physical address Segment Descriptor Linear Address Global Descriptor Table Page Directory Page Table Page Linear Address Space CR3

x86用語 基本フラットモデル ページディレクトリ ページテーブル ページ OS およびアプリケーションは連続したセグメント化されていないアドレス空間を利用する。コードセグメントおよびデータセグメントが1つの同じリニア アドレス空間にマップされる。 ページディレクトリ 4K バイトページに入っている 32bit の PDE(ページディレクトリエントリ)の配列。1024 個までの PDE を保持可能。 ページテーブル 4K バイトページに入っている 32bit の PTE(ページテーブルエントリ)の配列。1024 個までの PTE を保持可能。 ページ 4K バイト, 2M バイト, もしくは 4M バイトのフラットなアドレス空間。メモリはページ単位で扱う。 TLB (Translation Lookaside Buffer) PDE, PTE 用のオンチップのキャッシュ。

Linuxでのセグメンテーションとページングの利用 セグメント機構とページング機構を両方利用することは冗長 同じリニアアドレス空間を利用することによってメモリ管理機構をシンプルにできる 他のアーキテクチャへの移植性を保つため RISCチップには限定的なセグメント機構しか持たない者もある 1つの大きなセグメント内にプロセス毎に同じ 仮想アドレス空間というモデル

Linux でのメモリ管理の特徴 仮想アドレス空間のサポート デマンドページング／コピーオンライト スワッピング 多様なキャッシュのサポート 抽象化したメモリモデルを用いた広大な仮想アドレス空間が利用可能にする デマンドページング／コピーオンライト フリーページを実際のアクセス時に仮想アドレス空間に割り当てることによって使用効率／パフォーマンスを向上する技術 スワッピング フリーページが足りない場合、使用中のページを一時的にスワップ領域に退避し、フリーページを確保することによって実際の物理メモリより多くのメモリを利用可能にする 多様なキャッシュのサポート フリーページを多様なキャッシュに利用することによってパフォーマンスを向上する

Linuxで実装されている キャッシュ バッファキャッシュ(buffer cache) ページキャッシュ(page cache) ブロックデバイスから読み書きするデータ用のキャッシュ。全てのブロックデバイスはバッファキャッシュを経由してデータを取得する。ブロック単位で扱う。デバイス ID とブロック番 号でアクセス。 ページキャッシュ(page cache) ディスク上のイメージやデータを読み書きを高速化する(mmap したfileへのアクセス等)時に利用されるキャッシュ。ページ単位で扱う。ファイル名とオフセットでアクセス。 スワップキャッシュ(swap cache) スワップインされてから変更されていないページのページテーブルエントリとフラグ(ページとスワップファイルの情報)のキャッシュ。ページ単位で扱う。スワップファイルへの書出しを効率化するために用いる。

メモリマップと ページテーブル ページテーブル メモリマップ Linux では 64bitアドレス空間に対応できるように3 段のページテーブル(PGD, PMD,PTE)を持っている alpha は3段であるためそのまま利用 x86 は 2 段であるため、PMD は何もしない仮想的なテーブルになっている(メモリ上に存在しない)。x86 ではページテーブルはページング対象外であり、物理メモリ上にマップされたカーネル空間に常に存在する メモリマップ 物理メモリはPAGE_OFFSET(0xC0000000h)以降にマップ カーネルは 全てのプロセスの仮想アドレス空間の PAGE_OFFSET からストレートマップされる セグメントのプロテクション機能などの対象外 1GB以上の物理メモリを利用する場合にはPAGE_OFFSETをずらす

Linuxのメモリマップ(32bit) text text text data data data kernel bss bss bss プロセス毎の 仮想アドレス空間 ディスク File System 0x00000000 heap stack *.so mapped data text bss heap stack *.so mapped data text bss heap stack *.so mapped data text bss Swap 0xc0000000 kernel kernel stack stack stack stack 0x40000000 vmalloc space High mem 0xffffffff 0xc0000000 物理メモリ

2レベルページング(x86) Linear Address Directory Table Offset CR3 31 22 21 12 11 Directory Table Offset Page Page Table Page Directory CR3

3レベルページング(Linux) Linear Address Global Dir Middle Dir Table Offset CR3 Page Page Table Page Middle Directory Page Global Directory CR3 ※x86 Linuxでは PMDはメモリ上に存在しない (PGDからのアクセスはスルーしてPTにいく)

アドレス空間モデル mm_struct vm_area_struct vm_area_struct vm_next vm_next NULL mmap vm_file vm_file pgd vm_start vm_start NULL task_struct vm_end vm_end mm PTE virtual address space PGD PTE PMD Physical memory Page cache Swap cache File system Swap device

アドレス空間を管理する データ構造 struct task_struct struct mm_struct プロセスの情報を保持するデータ 伝統的UNIX でのu構造体を含むすべてのデータ プロセス毎に一つ struct mm_struct プロセスの仮想アドレス空間を管理するデータ task_struct からポイントされる struct vm_area_struct プロセスの仮想アドレス空間内のある連続領域を管理するデータ 仮想アドレス空間毎に複数存在し、それぞれの領域(vm_area_struct)が線形リスト／AVL ツリーで連結されている 先頭のデータは mm_struct からポイントされる

アドレス空間の複製 fork(2)時に複製 複製処理の流れ(kernel/fork.c) init 以外はすべてこれを利用 1) 新規に mm_struct{}を確保し、内容は親プロセスのものをコピー(copy_ mm()) 2) 親プロセスのもつメモリを全てコピーオンライトでマップし直す(dup_mmap()) PTEにおいて全てのページをReadOnly属性にする Read時: 問題無し Write時: Page Fault 発生。コピーオンライト処理を実施

アドレス空間の生成と解放 execve(2)時に生成 生成処理の流れ(fs/exec.c) exit(2)時に解放 1) 古いmm_struct の内容を破棄し、初期化する(exec_mmap()) 2) プログラムをロードし、新しく生成したアドレス空間にmmapする vm_area_struct は mmap処理内(do_mmap())で生成される それ以外の領域についてはデマンドページングで処理される(ページは割り当てられない) exit(2)時に解放 解放処理の流れ(kernel/exit.c) 1) mm_struct の解放(exit_mm())

ページングの流れ Page faultのハンドリング Does the address belong to the process address space? YES NO Does the access type match the memory region access right? Did the exception occur in User Mode? YES NO YES NO Legal access: Allocate a new Page frame Illegal access: Send a SIGSEGV signal Kernel bug: Kill the process handle_mm_fault()

Page fault In interrupt or kernel thread Address in Memory region NO In interrupt or kernel thread YES Address in Memory region YES NO Address could Belong to user Mode stack YES NO YES NO Write access NO YES YES NO Page is present In user mode Region is writable YES NO Region is readable or executable Address is a wrong system call parameter YES NO NO YES Copy on write Demand Paging Send SIGSEGV Kernel process And kernel “Oops” “Fixup code” (typically send SIGSEGV)

ページングの流れ ページ割り当て (1) NO YES Is the PTE present? ※3 invoke do_no_page() Demand paging Is the PTE empty? invoke do_swap_page() NO Have a file already mapped? YES ※2 invoke vma->vm_ops->no_page() invoke do_anonymous_page() ※1 YES NO Write access? Mapped ZERO_PAGE & Set PTE as ReadOnly Allocate a page & 0 clear & Set PTE as writable

ページングの流れ ページ割り当て(2) Demand paging ※1 NO Found the page in page cache? YES invoke page_cache_read() YES NO Is the cache valid? Allocate a page & Set PTE & load the file NO Is the page to be shared? YES load the file Allocate a page & Set PTE & load the file Set PTE as shared page

ページングの流れ ページ割り当て(3) ※2 Demand paging NO Is present vm_ops->swapin? YES invoke swap_in() NO YES Is swap cache present? Make a swap cache NO Is read access or shared? YES Set PTE with Writable&dirty Set PTE

ページングの流れ ページ割り当て(4) ※3 Set PTE & aging NO YES Is write access? NO YES invoke do_wp_page() Do nothing Is writable page? Set PTE with dirty flag ※4 Copy on write

ページングの流れ ページ割り当て(5) ※4 Copy on write Does multiple Processes refer the page? NO YES Set PTE as writable &dirty (copy no page) Allocate a page & Set PTE as writable & Copy data from old page

デマンドページング (Demand Paging) 仮想アドレス空間の生成時、実際にアクセスがあるまで物理ページの割り当てを遅らせるメモリ割り当て手法 メリット 仮想空間生成時のCPUのオーバヘッドが少ない 物理メモリの利用効率向上 デメリット Page fault 時のCPUのオーバヘッドが重い 採用理由 ローカリティの原理からpage faultはレアなイベントである プロセスは少ないアドレス空間のみ利用する Linuxでは仮想アドレス空間生成時にはPTE 作成するがページはNULLを指す 実際のアクセス時に page faultが発生

コピーオンライト (Copy on Write) 仮想アドレス空間の複製時、実際に書き込みアクセスがあるまでページのコピーを遅らせるメモリ割り当て手法 メリット 仮想空間複製時のCPUのオーバヘッドが少ない 物理メモリの利用効率向上 デメリット Page fault 時のCPUのオーバヘッドが重い 採用理由 読み込みのみのページは永続的に共有可能 仮想空間複製直後に破棄されることが多い Linuxでは仮想アドレス空間複製時、当該空間にマップされているページを全てReadOnlyで両方の空間からマップし直す 書き込み時に page fault が発生 -> Copy on Write 処理へ

スワップ処理 (Swapping) 空き物理ページが少なくなった時に、使用中の物理ページを二次記憶に退避し、利用可能な物理ページを確保する技術 メリット プロセスが実際に利用可能なアドレス空間を拡張できる プロセス実行時に割り当て可能な物理メモリを増やすことができる デメリット スワッピング処理のCPUのオーバヘッドが大きい 物理メモリが極端に少ない場合にスラッシングが発生し、システムの応答性が極端に下がる 採用理由 大きな／多くのプロセスが動かせるメリットが大きい Linuxではプロセスレベルではなくページレベルのスワッピングを実現 CPUのページング機構を利用して実装

犠牲ページの決定 アルゴリズム 基本は LRU (Least Recently Used)ベース ただし厳密なLRUではない x86ではチップのサポートが不十分(アクセスビットのみ) Linux x86ではアクセスビット を利用したagingで実現 当該ページにアクセスすると、チップがページテーブルのアクセスビットをたてる スワップ用のフリーページの検索時、アクセスビットが立っていればビットは落とされる(その時はページは解放されない) スワップ用のフリーページの検索時、アクセスビットが立っていなければ犠牲ページ候補となる 優先度毎にも最も利用物理ページ数が多いプロセスから犠牲ページの決定を実施

スワップ処理の流れ swap_out() do_swap_page() swap_out_process() swap_in() The page fault handler must swap in a page A page must be swapped out swap_out() do_swap_page() swap_out_process() swap_in() swap_out_vma() swapin_readahead() swap_out_pgd() read_swap_cache_async() swap_out_pmd() try_to_swap_out() rw_swap_page() Low-level swapping function brw_page() Block device driver function

フリーページの取得処理 (1) do_try_to_free_pages() try_to_free_pages() -> do_try_to_free_pages() 物理ページ割り当て処理部や kswapd から呼ばれる for (priority = 6;priority; priority--) { while (shrink_mmap(priority,gfp_mask)) { /* ページキャッシュの解放 */ if (空きページが十分) return; } while (shm_swap(priority ,gfp_mask)) { /* 共有メモリの解放 */ while (swap_out(priority,gfp_mask)) { /* スワップアウトによる解放 */ shrink_dcache_memory();/* ディレクトリエントリの解放*/

フリーページの取得処理 (2) swap_out() for (counter=nr_tasks/(priority+1);counter;counter--) { int max_cnt=0; struct task_struct *pbest; for (init以外のすべてのプロセス) { if (最近スワップアウトされていない && 使用物理ページ数 > max_cnt) { max_cnt = 使用物理ページ数; pbest = 当該プロセス; } swap_out_process(pbest,gfp_mask);

フリーページの取得処理 (3) try_to_swap_out() swap_out_process() → … → try_to_swap_out() if (有効なページがない || 予約／ロックされたページ) { return;} if (最近アクセスがあった) { PTE のアクセスビットをクリア; page 構造体の参照ビットをたてる; return; } if (スワップキャッシュ上にある) { スワップキャッシュの参照数をあげる; PTE の設定; __free_page (); return; if (書き込みされていない) { PTE の設定; __free_page (); return; if (独自swapout 関数がある) { PTEクリア; swapout 関数を呼び出す; __free_page(); return; 空きスワップの検索; PTEの設定; ページの内容をメモリに書き出す; __free_page(); return;

kswapd 空きページを作る処理を行う、永続的に動作するカーネルスレッド 定期的(1回/秒)に起動あるいは物理ページ割り当て処理部から起動される 空きページ判定の閾値は最大256*3ページ 最大物理メモリ量に関係 while (1) { while (空きページが十分でない) { if (do_try_to_free_pages(GFP_KSWAPD) { if (スケジュール必要) { schedule(); } schedule_timeout(10*HZ);

メモリ領域管理機構 (1) Buddy system 空きページを複数種類のページ数*2のべき乗の単位で管理する方式 領域の split, coalescing が簡単にできるため、要求されたメモリサイズにあわせて柔軟な割り当てが可能 要求サイズはページサイズ*2のべき乗に切り上げて割り当て 必要なサイズのエリアが足りない時は1つ上のサイズのリストからもらう(split) あるサイズのフリーなエリアの量が過剰な時は1つ上のサイズのリストに二個一化にして渡す(coalescing) External Fragmentation を解決する一つの方式 ページ単位でのメモリフラグメンテーションを解決 Linux x86では 2^0 から 2^9 ページサイズの10種類

メモリ領域管理機構 (1) Buddy system 10 kbytes の メモリの要求 Free area list (n *page/block) 1page 1page … n= 2^0 pager n= 2^1 2page 2page merge 4page 4page n= 2^2 split 2^2page*1 の メモリの割り当て 8page 8page n= 2^3 …

メモリ領域管理機構 (2) Slab allocator カーネル内で利用するメモリをオブジェクト単位で扱い、再利用に最適化したメモリ管理方式 再利用による管理オーバヘッドの低下 ページ単位の管理よりも小さいメモリ領域も扱える ハードウェアキャッシュの効率向上 キャッシュラインを乱さないようなメモリ割り当てを行える Internal Fragmentation を解決する一つの方式 ページより小さいサイズのメモリフラグメントを解決 e.g.) /etc/slabinfo 参照 i-node cache, socket buffer, …

メモリ領域管理機構 (2) Slab allocator Page-level allocator (buddy system) back end vnode cache proc cache file cache … Slab allocator front end active vnodes active procs active files coloring area unused Slab data Linked list N page free active NULL

メモリ領域管理機構 (2) Slab allocator Linux で使われている slab の種類 カーネル内で利用される各structure用のブロック slabinfo,kmem_cache, tcp_tw_bucket, tcp_bind_bucket, tcp_open_request, inet_peer_cache, ip_fib_hash, ip_dst_cache, arp_cache, uhci_urb_priv, blkdev_requests, nfs_read_data, nfs_inode_cache, nfs_write_data, nfs_page, journal_head, revoke_table, revoke_record, dnotify, file, fasync, uid_cache, skbuff_head_cache, sock, sigqueue, kiobuf, cdev_cache, bdev_cache, mnt_cache, inode_cache, dentry_cache, filp, names_cache, buffer_head, mm_struct, vm_area_struct, fs_cache, files_cache 2^{5,6,7,8,9,10,11,12,13,14,15,16,17}bytesのブロック 通常／DMA用  ※ /proc/slabinfo で確認可能

参考文献 Understanding Linux Kernel UNIX Internals: The New Frontiers Daniel P. Bovet & Marco Cesati, O’reilly, 2001 UNIX Internals: The New Frontiers Uresh Vahalia, Prentice Hall, 1996 Intel Architecture Developers Manual Vol1,2,3 Intel Corp., 1999

ブート時のメモリ管理 起動ステップ 1 (real mode) 起動ステップ 2 (protect mode) 4MB のアドレススペース用のページテーブルをコンパイル時に初期化(pg0, arch/kernel/head.S で実施) 固定値(static な配列) 範囲[PAGE_OFFSET, PAGE_PFFSET+0x3fffff] ※ページングは使えない状態 ※起動ステップ 2 に移行後は使用しない 起動ステップ 2 (protect mode) paging_init() ルーチンで初期化(swapper_pg_dir[], arch/mm/init.c) ページテーブルに PAGE_OFFSET 以降の仮想アドレスに対応する物理アドレスを書き込む 0x0 をアンマップする(NULL Pointer access用の領域となる) ※Pentium 以降では 4MB ページテーブルも利用可能