KSM内部解析

概要

KSM(Kernel SamePage Merging)とは、ユーザプロセスのメモリ領域を走査して、同一内容のページを1つのページにマージすることで使用メモリ量を削減するLinuxカーネルの機能です。マージされたページはCoW(Copy on Write)状態に設定され、ページへの書き込みが発生すると再び個別のページに分裂されます。

KSMはバージョン2.6.32でマージされ、主に同一内容のページを重複して持つ可能性が比較的多いVM利用時の使用メモリ削減が期待されています。

この記事はKSMの内部構造と動作を解析するものです。

忙しい人のための解析概略
  • ユーザインタフェースはmadvise(の新しいオプションMADV_MERGEABLEとMADV_UNMERGEABLE)と/sys/kernel/mm/ksm/以下のsysfsファイル
    • ユーザプロセスがmadviseでマージしても良いページを指定
    • 管理者がsysfs経由でKSMの動作パラメタを変更
  • KSMの仕事は基本的にページをマージさせるところまでで、CoWの動作はLinuxの存在する機能をそのまま使う。
    • UNMERGEするときも当該ページに擬似的に書き込みが起きたように見せかけるだけ
  • 走査対象メモリはAnonymousメモリのみ(ほんとんどの場合ヒープ領域のはず)
    • File Cacheは対象にならない
  • 現在の実装ではマージされたページはSwap outされなくなる(制限)
    • いずれ解消される予定
  • ページを走査するのはksmdというカーネルスレッド
    • 指定間隔で指定ページ数だけページ走査を行ない、見つかった同一内容のページをマージしていく
  • ページ内容の比較(同定)にはmemcmp(つまり2つのページ全体を舐める)を用いる
  • 同一内容ページの探索/挿入/削除は赤黒木を用いることで高速化している
    • VMwareの特許を避けるための苦肉の策と思われる

KSMの使い方

この記事では、KSMはどう動いているかに着目するので、KSMのセットアップの方法等には触れません。その辺りは情報は以下のページを参照してください。

注意

  • 本記事はmmotmツリーにマージされた頃のKSMを解析したものなので、Linusツリーにマージされてからの変更には追従できていない箇所があります。動作の大筋は変わっていないようですが、ご注意ください
  • またOOMに関係する例外処理については触れていません。とはいえ動作の大筋に影響はないと思います
  • 内容を鵜呑みしないでください。私のLinuxメモリ管理回りの理解が深くないので、間違っている部分があるかもしれません
  • 読みにくいです
    • 図がない
    • 書きなぐったメモと大差ない
    • 時間があれば直します。すみません。。。

解析：データ構造

備考
  • mmのコードを変更しない方針
    • もともとkernel moduleとして実装することを意図していた
    • 現時点ではカーネル組み込み機能
  • PageKSM
    • PageAnonの仲間
    • PageAnonかつanon_vma(特定の仮想アドレス空間のアドレス領域リスト) == NULL
  • VM_MERGEABLE
    • vm_area_structのフラグ
  • MMF_VM_MERGEABLE
    • mm_structのフラグ
Stable & unstable trees
  • 走査したページを格納するデータ構造
  • 赤黒木(Red-Black tree)
  • マージできたページをstableにマージできなかった(けど内容に変更がなかった)ページをunstalbe treeに入れる
    • 内容に変更があったページは2つの木の中には入れない
  • stable treeの要素(node == rmap_item)はリストになっている
    • マージされたページは複数のrmap_itemから参照されている
  • unstable treeの要素もrmap_item
    • ただしリストにはなっていない
mm_slot
  • 1 mm_struct (≒プロセス)につき1つ用意される？
  • ksmはmm_slotのリストを保持し、そこからvm_area_struct, page tableとたどってpageを取得する
  • @link: hash list?
  • @mm_list: ksm_mm_head用
  • @rmap_list: このmm_slotのrmap_itemリスト
  • @mm: 当該mm_struct
  • なおmadviseでmm_structと指定された領域をもつvm_area_structにMERGEABLEフラグが設定されている
    • vm_area_struct単位なのでそれより小さい領域を指定すると多少空回りする？ addressを使って無駄をはぶいている
rmap_item
  • reverse mapping item for virtual address
  • @link: mm_slot用
    • rmap_itemは明示的にremoveされない限り基本的に生成されたらmm_slotに繋がれたまま
    • 指しているページがマージされてもrmap_itemは残る
      • 例外：ただし走査中に変なアドレスを指すrmap_itemがあった場合はremove&freeする
  • @address
    • low bitはflag
      • SENR_MASK:
      • NODE_FLAG
      • STABLE_FLAG
  • 1つにつき1ページを指している
    • 直接pageを持たない
    • pageを得るときは@mm + @addressを使って毎回PTをたどる
  • 繋がれている場所によって保持データも違う
    • stable tree: @prev, @next, @node: 次のrmap
      • 何に使ってるんだろ？
    • unstable tree: @oldchecksum, @node
      • @nodeがわからん
  • @oldchecksum: 内容が変更されたか否かの判定のみに利用される
グローバル変数
  • ksm_mm_head
    • mm_slotリスト
  • ksm_scan
    • cursor for scanning
    • ページ走査カーソル
    • 現在走査中のページを指している
    • @mm_slot + @address + @rmap_item
    • seqnrってどう使われているの？
  • root_stable_tree
  • root_unstable_tree
  • rmap_item_cache？
  • mm_slot_cache？
  • mm_slots_hash
    • mm_slotのリストを要素とするハッシュ
    • mm_slotを削除するときだけに使われている
      • 通常のmm_slotアクセスはmm_slot_headからリストをたどる
    • ハッシュサイズは1,024
      • スケールしない気が。。。
      • まぁ削除するときだけならスケールする必要はないか


統計値

  • ksm_pages_shared
    • stable tree内のnode数(!=rmap_item数)
  • ksm_page_sharing
    • stable tree内の非node数
  • ksm_pages_unshared
    • unstable tree内のnode数(=rmap_item数)
  • ksm_rmap_items
    • allocされたrmap_itemの総数(のべ数ではない)
  • ksm_pages_volatile
    • ksm_rmap_items - ksm_pages_shared - ksm_pages_sharing - ksm_pages_unshared
    • これ自体はカウントアップ/ダウンされない

コンフィグ

  • ksm_max_kernel_pages (default = 2000)
    • ksm_pages_sharedしても良い最大ページ数
  • ksm_thread_pages_to_scan (default = 200)
  • ksm_thread_sleep_millisecs (default = 20)
  • ksm_run (default = 1)
    • KSM_RUN_STOP=0
    • KSM_RUN_MERGE=1
    • KSM_RUN_UNMERGE=2 (強制unmerge)

解析：動作(API)

madvise
  • madvise(MADV_MERGEABLE) -> ... -> madvise_behavior() -> ksm_madvise() -> __ksm_enter()
    • vm_area_structが渡されてくる
    • start, endは無視される
    • vm_area_structおよびmm_structのフラグにMERGEABLEビットを立てる
    • mm_slotが生成され(alloc_mm_slot)、カーソルのmm_slotリストの最後に繋がれる
  • madvise(MADV_UNMERGEABLE) -> ... -> ksm_madvise()
    • 当該vm_area_structのMERGEABLEビットを落とす
    • vm_area_struct内のstart..endの範囲のKsmPageをunmergeする
      • handle_mm_fault(FAULT_FLAG_WRITE)を呼ぶだけ
    • __ksm_exit()はここでは呼ばれない
sysfs
  • 個々のグローバル変数が変更される
    • run = 1: wake_up_interruptible()
    • run = 2: unmerge_and_remove_all_rmap_items()
      • mm_slot_headをたどってひたすらKsmPageをunmerge & rmapをfree
      • mm_slot自体は残しておく
      • 使用メモリが大量に増えると思われるのでやらない方がいいような。。。
__ksm_exit() (ksm_exit())
static inline void ksm_exit(struct mm_struct *mm,
                            struct mmu_gather **tlbp, unsigned long end)
{
       if (test_bit(MMF_VM_MERGEABLE, &mm->flags))
               __ksm_exit(mm, tlbp, end);
}
  • 引数
    • struct mm_struct *mm
    • struct mmu_gather **tlbp
    • unsigned long end
  • 動作
    • OOM deadlockを考慮してちょっとトリッキーになっている
  • mmからmm_slotを得る
  • mm_slotがrmap_itemを一つも持っていなければfree_mm_slot()
    • mm_structのMERGEABLEフラグを落とす
  • そうでなければカーソルの位置を当該mm_slotにしておまじないをして終了
    • tlb_finish_mmu(*tlbp, 0, end)
      • Called at the end of the shootdown operation to free up any resources that were required
    • *tlbp = tlb_gather_mmu(mm, 1)
      • Return a pointer to an initialized struct mmu_gather
    • mm_structのMERGEABLEビットは残る
  • mm_slotが解放されるタイミング
    • unmerge_and_remove_all_rmap_items()
      • echo 2 > /sys/kernel/mm/ksm/run
    • scan_get_next_rmap_item()
      • mm_slotリストを走査中
  • __ksm_exit()が呼ばれるタイミング

解析：動作(ksmd)

main loop
while (scan_pages--) {
  page, rmap_item = scan_get_next_rmap_item()
  if (PageKSM(page) && in_stable_tree(rmap_item) continue
  cmp_and_merge_page(page, rmap_item)
}
scan_get_next_rmap_item()
  1. mm_slotがなければ終了(スレッドも休眠)
  2. カーソルがmm_slot_headだったら == mm_slotリストを全て走査した
    • 最初から走査するための初期化
  3. カーソルが指す(mm+address)vm_area_structを走査
    • find_vma(mm, ksm_scan.address)
    • addressの位置のページから一つずつ取り出す
    • 取り出すときは(*)のような感じ
    • カーソルはどのタイミングからでもループを抜けて、再度ループの途中から走査を続行するためのもの
    • PageAnonがあれば、該当pageとそのrmap_itemを持ってreturn
      • rmap_itemはget_next_rmap_item()で取得する
      • 正常パスはここで終了
  4. mm_slotにVM_MERGEABLEなvm_area_structがない場合
    • mm_slotをmm_slotリストから外す
    • 次のmm_slotを走査
    • mm_slotがなければ終了
  5. 当該vm_area_structリストにこれ以上VM_MERGEABLEがなかった
    • 次のmm_slotを走査
  6. ksm_scan.seqnr++

(*)

foreach (mm_slot in mm_slots where mm_slot->mm_struct is MERGEABLE) {
  foreach (vm_area_struct in vm_area_structs of mm_slot->mm_struct where vm_area_struct is MERGEABLE) {
    foreach (page in pages of vm_area_struct) { // follow PTs
      do_something(page);
    }
  } 
}
get_next_rmap_item()
  • 引数
    • mm_slot
    • cur
    • addr
  • 動作
    • mm_slotのrmap_itemリストをcurの位置からたどってaddrに対応するrmap_itemを得る
    • rmap_item.address == addrならばそれを返す
      • このときunstable treeに繋がっていれば取り外す
    • なければalloc_rmap_item()
    • 例外：rmap_item->address <= addrだったらfree_rmap_item()
      • どういう場合にこうなる？
cmp_and_merge_page()
  1. rmap_itemがstable tree内にあったら木から外す
    • stable & !KsmPageの場合 == CoWが壊れてた場合
  2. Stable treeを走査(stable_tree_search)
    1. 同一ページがあった場合
      • pages_sharing++
      • stable treeに繋げる
    2. 同一内容(&違うページ)のページがあった場合
      • try_to_merge_with_ksm_page()
      • *stable treeにあるページとマージ
      • 成功したらstable_tree_append()
    3. otherwise
      • fall through
  3. ページ内容のチェックサムを計算する
    • ページサイズの1/4だけ使う
    • チェックサムが変わっていた(== ページ内容が変化した)場合return
    • つまりunstable treeにも入れない
  4. Unstable treeを走査&挿入(unstable_tree_search_insert)
    • 同一内容のページがあればそれのrmap_itemを取り出し挿入はしない
      • なければ当該rmap_itemを挿入し終了
    • 取り出したrmap_itemをtree_rmap_itemと呼ぶ
    • 二つのページをマージしようとする
    • 成功の場合
      • ksm_pages_unshared--
      • stable treeにtree_rmap_itemを入れる(stable_tree_insert)
      • *失敗したら、2つのページのCoWを壊す
      • 成功：
      • *stable_tree_insert()内でksm_pages_shared++
      • *stable_tree_append()でtree_rmap_itemにrmap_itemを繋げる
stable_tree_append()
  • 引数
    • rmap_item: appendされるrmap_item
    • tree_rmap_item: treeにあるrmap_item。NODE_FLAGが立っている(はず)
  • 動作
    • tree_rmap_itemの真後ろにrmap_itemを繋げる
    • rmap_itemにSTABLE_FLAGを立てる
    • ksm_pages_sharing++
  • 備考
    • appendされるrmap_itemはrbtreeの一部に'''ならない'''
try_to_merge_two_pages()
  • 引数
    • ページ1: page1, mm1, address1
    • ページ2: page2, mm2, address2
  • 動作
    • if (ksm_max_kernel_pages <= ksm_pages_shared) return
    • kpage = alloc_page(GFP_HIGHUSER)
    • page1のvm_area_structを取ってくる => vma
    • copy_user_highpage(kpage, page1, addr1, vma)
    • try_to_merge_one_page(vma, page1, kpage)
      • write_protect_page()
      • ページ内容が同じかチェックしたのちreplace_page()
      • *mm1, address1からたどれるpteをkpageのものに置き換える
      • *当該pteに対してmmu_notifier->change_pte()を呼ぶ
    • try_to_merge_with_ksm_page(mm2, addr2, page2, kpage)
      • 失敗したらbreak_cow(mm1, addr1)
get_ksm_page()
  • stable_tree_search(), stable_tree_insert()から呼ばれる
  • treeにあるrmap_itemからpageを得る
    • このときPTをたどる
  • 以下の場合NULLが帰ってくる
    • rmap_itemが指しているpageがPageKsm()でない
      • つまりそのpageがunmergeして単なるPageAnon()になっていた
    • rmap_itemが所属するvm_area_structがMERGEABLEでなかった