4.4 Paging under LINUX

UNIXは利用可能なプライマリメモリよりも多い量のメモリを要求されても帳尻を合わせるために,スワッピングと呼ばれるものを使う.スワッピングはメモリからプロセス全体をセカンダリへ保存し,再び読み戻す.

VAXアーキテクチャは デマンドページング を開発. メモリ管理ユニット(MMU)はメモリをページ単位に分割する.Linuxでは,プロセスの仮想メモリ空間に直接配置されているメモリのページは do_mmap() を使う.

Linuxは2種類の方法でページを別のメディアへ保存できる.

  1. 完全なブロックデバイスを外部媒体のように扱う.
  2. ファイルシステム内の固定長のファイルを使う.

swapon システムコールはカーネルのためにスワップデバイスやスワップファイルの使用を開始する( mm/swap.c).

/*
 * 1992年1月25日にSimmule Turnerによって書かれ,
 * Linusが大幅な変更を加えた.
 * swaponのシステムコール
 */
asmlinkage int sys_swapon(const char * specialfile)
{
    struct swap_info_struct * p;
    struct inode * swap_inode;
    unsigned int type;
    int i, j;
    int error;
    struct file flip;

    ...
    p->swap_lockmap = (unsigned char *) get_free_page(GFP_USER);
    ...
    read_swap_page(SWP_ENTRY(type,0), (char *) p->swap_lockmap);
    ...
    memset(p->swap_lockmap+PAGE_SIZE-10,0,10);
    j = 0;
    p->lowest_bit = 0;
    p->highest_bit = 0;
    /*
     * スワップ空間の中で書き込み可能な範囲を探す.
     */
    for (i = 1; i < 8*PAGE_SIZE ; i++) {
        if (test_bit(i,p->swap_lockmap)) {
            if (!p->lowest_bit)
                p->lowest_bit = i;
            p->highest_bit = i;
            p->max = i+1;
            j++;
        }
    }
    if (!j) {
        printk("Empty swap-file\n");
        error = -EINVAL;
        goto bad_swap;
    }
    p->swap_map = (unsigned char *) vmalloc(p->max);
    ...
    for (i = 1; i < p->max ; i++) {
        if (test_bit(i,p->swap_lockmap))
            p->swap_map[i] = 0;
        else
            p->swap_map[i] = 0x80;
    }
    p->swap_map[0] = 0x80;
    memset(p->swap_lockmap,0,PAGE_SIZE);
    p->flags = SWP_WRITEOK;
    p->pages = j;
    nr_swap_pages += j;
    printk("Adding Swap: %dk swap-space\n", j<<2);
    return 0;

swapoff システムコールはカーネルがスワップファイルかスワップデバイスの使用を止めるよう試みる( mm/swap.c).

asmlinkage int sys_swapoff(const char * specialfile)

4.4.1 Finding a free page

優先度 説明
GFP_BUFFER 物理メモリ内の空きページが利用可能な場合のみ返される空きページ
GFP_ATOMIC __get_free_pages 関数はカレントプロセスに割り込む必要はない.しかしもし可能であればページは返される.
GFP_USER スワップページのために現在のプロセスは割り込まれる.
GFP_KERNEL このパラメータは GFP_USER と同じ.
GFP_NOBUFFER メモリ内の空きページを探そうとすることによって,バッファキャッシュは減少しないだろう.
GFP_NFS これと GFP_USER の違いは, GFP_ATOMIC のために予約されているページ数が min_free_pages によって5つに減らされることだ.

物理ページが予約され始めたら,カーネル関数 __get_free_pages() が呼び出される.

unsigned long __get_free_pages(int priority, unsigned long order)
{
    unsigned long flags;
    int reserved_pages;

    if (intr_count && priority != GFP_ATOMIC) {
        static int count = 0;
        if (++count < 5) {
            printk("gfp called nonatomically from interrupt %p\n",
                __builtin_return_address(0));
            priority = GFP_ATOMIC;
        }
    }
    reserved_pages = 5;
    if (priority != GFP_NFS)
        reserved_pages = min_free_pages;
    save_flags(flags);
repeat:
    cli();
    if ((priority==GFP_ATOMIC) || nr_free_pages > reserved_pages) {
        RMQUEUE(order);
        restore_flags(flags);
        return 0;
    }
    restore_flags(flags);
    if (priority != GFP_BUFFER && try_to_free_page(priority))
        goto repeat;
    return 0;
}

優先度によって関数の処理が変わる.

GFP_ATOMIC は割り込みルーチンから __get_free_pages()を呼び, GFP_BUFFER はバッファキャッシュの管理に使われる.priority に別の値が使われたなら,プロセスは割り込まれ,スケジューラが呼ばれるだろう.

第二引数は予約が始まる連続したページのメモリブロックのための大きさ.ブロック o は2の o 乗の大きさである.Linuxカーネルは NR_MEM_LISTS マクロ未満のサイズしか許可しない.つまりブロックのサイズは4, 8, 16, 32, 64, 128キロバイト 単位で割り当てられる.

カーネルは free_area_list[]free_area_map[] の2つのデータ構造を管理する.

free_area_list[] は空きメモリブロックの循環リストを含む.ここで,先頭の要素は空きページを参照しないリストの一部である.

free_area_map[] は各大きさの順のビットマップを含み,同じ大きさの順に並んだ2つの連続したメモリブロックのために1ビット予約されている.このビットは2つのブロックのうち1つが空いたならセットされ,もうひとつは部分的に予約されるだけだろう.

Linuxの実装では2つの連続したメモリブロックの空きがより大きいブロックに結び付く可能性はないのを保証している.サイズが小さい順の空いたブロックがないことがある.もし作られたこれらのうちの1つが要求されたなら,最も大きい順にブロックが分割され,関連したリスト free_area_list[]free_area_map[] が更新される.

また,データ構造 mem_map[] がある.これは各ページの16ビットの値を保持する.もし最も大きいビットがセットされたなら,このページは予約され,おそらくスワップされていないだろう.ユーザセグメントにマップされたメモリのページのために,この値はアクセスするプロセスの数だけ与えられる.ほか全てのブロックに対して,最初のページ向けにこの値には1が入る.もしこのブロックが使用中であれば0が入る.現在の空きページの数は nr_free_pages によって与えられる.このうち min_free_pagesGFP_ATOMIC 呼び出しのために予約される.

__get_free_pages() はページ確保のために try_to_free_page() を呼び出し,検査をおこなう.

static int try_to_free_page(int priority)
{
    static int state = 0;
    int i=6;

    switch (state) {
        do {
        case 0:
            if (priority != GFP_NOBUFFER && shrink_buffers(i))
                return 1;
            state = 1;
        case 1:
            if (shm_swap(i))
                return 1;
            state = 2;
        default:
            if (swap_out(i))
                return 1;
            state = 0;
        } while(--i);
    }
    return 0;
}

shrink_buffers()fs/buffer.c で定義されている.

/*
 * バッファキャッシュの圧縮によって空いているページの確保を試みる
 *
 * 優先度はバッファを圧縮するのがいかに大変かを教えてくれる:
 * 3 は "あまり気にするな", 値が0の間は
 * "空いているページを確保できた"を意味する.
 */
int shrink_buffers(unsigned int priority)
{
    if (priority < 2) {
        sync_buffers(0,0);
    }

    if(priority == 2) wakeup_bdflush(1);

    if(maybe_shrink_lav_buffers(0)) return 1;

    /* 対象のサイズはよくない - 探せる範囲で大きさを確保する */
        return shrink_specific_buffers(priority, 0);
}

shrink_buffer() 関数は最初に,特定のサイズのバッファブロックが不釣り合いな量の領域を占めるのであれば,それを減らそうとする.これの裏付けとして,バッファキャッシュは buffers_lav[] テーブルで管理される.

もし shrink_buffers() がとても高い優先度で呼ばれたのであれば, bdflush プロセスが起動され,また優先度がいまだに高いのであれば,すべての修正されたブロックバッファは非同期的にページアウトされるだろう.

shm_swap() 関数は,System-Vのプロセス間通信の共有メモリ関数を使って,予約されたメモリ空間の保存を試みる(Chapter 5 をみよ).

swap_out() 関数はプロセスのユーザセグメントからスワップアウトかメモリのページの破棄を試みる.これは興味深い関数であり,直近スワップインされたか高い頻度でスワップインしたプロセスで,破棄可能またはページ可能なページに対して 集中的な検査手続きを踏む.これは各プロセスがどれだけのページが次のプロセスへ向かう swap_outの前に保存されるべきかを指す値 swap_cntを活用する.破棄可能またはページ可能なページの探索はいつも,前回終了した関数のプロセスのページの後に,swap_out()によっておこなわれる.Tanenbaum(1986)はこの手続きを「クロックアルゴリズム」と呼んだ.

swap_out()による処理をより詳しく見てみよう.swap_cntがゼロになったときか新しいプロセスでswap_outが始まったとき,再計算が行われる.

Δmaj_flt = maj_flt - old_maj_flt

ここでΔmaj_flt は,前期にセカンダリメディアへのアクセスがおこなわれたさいのページエラーの数である.

dec_flt' = 3/4 * dec_flt * Δmaj_flt

             SWAP_RATIO   dec_flt' >= SWAP_RATIO / SWAP_MIN
dec_flt" = { 
             dec_flt'     otherwise

dec_fltはページエラーの重みである. この値からswap_cntが生成される.SWAP_MINSWAP_MAXにはswap_cntにとって可能な最小値と最大値が与えられる.これらは SWAP_RATIOに128がセットされている間,4から32までの値をとる.

             SWAP_MIN    dec_flt' >= SWAP_RATIO / SWAP_MIN

swap_cnt = { SWAP_MAX    dec_flt' <= SWAP_RATIO / SWAP_MAX

             SWAP_RATIO / dec_flt' otherwise

swap_out()swap_out_process() を使って保存するページを探す.この関数はページアウト可能なページのためにユーザセグメント内の個々の仮想メモリ空間を探索する.これはページディレクトリを通じて探索をし,各ページテーブルエントリに対してtry_to_swap_out()を呼ぶ. try_to_swap_out() では,プロセスの仮想アドレス空間のページは,メモリがあり予約されていないことを確かめるためにチェックされる.もしページに対する「年齢」要素がまだセットされていないなら,セットされ関数は返る.Linuxはメモリページのために単純な加齢関数(aging function)を実装している.直近のページはすぐにはページアウトには使われない.この手続きはTanenbaumによってセカンドチャンスアルゴリズムと呼ばれている.

もしページが変更されたら,ただひとつのプロセスによって使われ始めたのであればページアウトする.このケースでは mem_map[PAGE_NR(page)] は1になるだろう.この場合,スワップ空間の数とページが書き込まれる領域のページ数はページテーブルに入力される.

もし変更されていないページがずっとスワップ空間にいるなら,これは単純に破棄される.これをチェックするために,Linuxは各ページに対し区分されたエントリを管理するswap_cache[] テーブルを保持している.それ以外の場合はページは free_page() を使ってページディレクトリから除去される.

空きページがなければtry_to_free_page()は0を返す. これがもし1より大きいのであれば,ページはページディレクトリから除去されているが,他のページテーブルから参照されたままである.もし1を返したなら,ページは空きメモリ空間の管理に使われているデータ構造へ入力される(free_area_list[]free_area_map[]).この場合,またはプロセスの数が優先度によって指定されたならswap_out() が返る.

free_pages()によってメモリのブロックが解放される.もし必要なら,mem_map[]の割り当てられた値が減算される.そしてもしその値が0になったなら,そのブロックは空きブロック管理ルーチンに引き継がれる.特別な場合はバッファキャッシュからユーザセグメントへ直接マップされていたページだろう.もしこのmem_map[]の値が1に届いたなら,同様のバッファブロックはブロックバッファリストBUF_UNSHAREDに入力される.

__get_dma_pages関数は,__get_free_pages()呼び出しによって物理メモリの下16MB内のメモリのブロックを予約する.予約されたブロックもまたアドレスが分割され始める.この帰ってきたメモリはDMAのために使われる.

get_free_page()__get_free_page()マクロはメモリ内の空きページを予約する.get_free_page()関数もまたページの中身を0にセットする.双方とも__get_free_pages()をそれぞれのタスクのために実行する.

連続したページの数はfree_pages()関数で解放できる.free_page()マクロは単一のページに対してfree_pages()関数を呼び出す.

4.4.2 Page errors and reloading a page

X86プロセッサでは,ページにアクセスできなかったならページフォルト割り込みを生成する.エラーコードはスタックに書き込まれ,割り込みがかかった場所の線形アドレスはレジスタCR2に格納される.

Linuxでは,do_page_fault()ルーチンが呼ばれる(arch/i386/mm/fault.c

/*
 * このルーチンはページフォルトを操作する.アドレスとその問題を見つけ出し,
 * それを適当なルーチンのために終わらせる
 *
 * error_code:
 *    bit 0 == 0 はページが見つからない. 1 は保護フォルトを意味する.
 *    bit 1 == 0 は読み込み, 1 は書き込みを意味する.
 *    bit 2 == 0 はカーネル 1 はユーザモードを意味する.
 */
asmlinkage void do_page_fault(struct pt_regs *regs, unsigned long error_code)
{

このルーチンは,フォルトを引き起こしたユーザセグメント内のアドレスが見つかる,現在活動中のプロセスの仮想メモリ空間を探索する.

もし仮想メモリ空間にアドレスがあければ,このルーチンは次の仮想メモリ空間のためのVM_GROWSDOWNフラグがセットされていないかチェックする.この類の空間はスタックのためのメモリを提供し,下向きに成長する可能性がある.do_page_fault()ルーチンは必要な拡張を処理する.次の仮想メモリ空間を拡張できない場合,do_pae_fault()はエラーを引き起こしたプロセスにSIGSEGVシグナルを送る.

もしカーネルセグメントを指すアドレスがアクセスエラーの原因であったなら,システムモードでは書き込み保護ビットでテストが引き起こされているかのチェックが行われる.これはx86プロセッサでは無視される.書き込み保護ビットがカーネルセグメントで無視されたとき,verify_area()関数による特別な処理が必要になる.そうでなければ,printk()によってカーネルの警告文がコンソールに出力される.そしてプロセスはエラーを引き起こし,終了するだろう.

もしアドレスが仮想メモリ空間にあるなら,仮想メモリ空間のフラグを参照することで,読み書き命令の正当性が確認される.もし正当なら,ページエラー操作ルーチンはdo_no_page()do_wp_page()を呼び出す.そうでなければ,再びSIGSEGVシグナルが送られる.

( include/linux/mm.h )

extern void do_wp_page(struct vm_area_struct * vma, unsigned long address, int write_access);
extern void do_no_page(struct vm_area_struct * vma, unsigned long address, int write_access);

( mm/memory.c )

/*
 * このルーチンは,ユーザが共有ページに書き込もうとすると
 * 現在のページを操作する.この操作は,ページを新しいアドレスにコピーし,
 * 古いページの共有ページカウンタを減算する.
 *
 * Goto純粋主義者は注意せよ: ここでgotoを使う唯一の理由は,アセンブリコード
 * よりマシになるということだ. "default"はジャンプしない.
 *
 * このルーチンは,保護チェックが呼び出し元によっておこなわれたことを
 * 前提としている(ほとんどの場合は低レベルでのページフォルトルーチン).
 * したがって,必要なCopy-on-Writeを実行したら書き込み可能にできる.
 *
 * また,実際に書き込みがおこなわれると,ページが変更されるのにもかかわらず
 * 汚れたページとマークされる.これにより,いくつかの競合が回避され,
 * 潜在的により効率的となる.
 */
void do_wp_page(struct vm_area_struct * vma, unsigned long address,
    int write_access)
{
    pgd_t *page_dir;
    pmd_t *page_middle;
    pte_t *page_table, pte;
    unsigned long old_page, new_page;

    new_page = __get_free_page(GFP_KERNEL);
    page_dir = pgd_offset(vma->vm_task,address);
    if (pgd_none(*page_dir))
        goto end_wp_page;
    if (pgd_bad(*page_dir))
        goto bad_wp_pagedir;
    page_middle = pmd_offset(page_dir, address);
    if (pmd_none(*page_middle))
        goto end_wp_page;
    if (pmd_bad(*page_middle))
        goto bad_wp_pagemiddle;
    page_table = pte_offset(page_middle, address);
    pte = *page_table;
    if (!pte_present(pte))
        goto end_wp_page;
    if (pte_write(pte))
        goto end_wp_page;
    old_page = pte_page(pte);
    if (old_page >= high_memory)
        goto bad_wp_page;
    vma->vm_task->mm->min_flt++;
    /*
     * コピーすべき?
     */
    if (mem_map[MAP_NR(old_page)] != 1) {
        if (new_page) {
            if (mem_map[MAP_NR(old_page)] & MAP_PAGE_RESERVED)
                ++vma->vm_task->mm->rss;
            copy_page(old_page,new_page);
            *page_table = pte_mkwrite(pte_mkdirty(mk_pte(new_page, vma->vm_page_prot)));
            free_page(old_page);
            invalidate();
            return;
        }
        *page_table = BAD_PAGE;
        free_page(old_page);
        oom(vma->vm_task);
        invalidate();
        return;
    }
    *page_table = pte_mkdirty(pte_mkwrite(pte));
    invalidate();
    if (new_page)
        free_page(new_page);
    return;
bad_wp_page:
    printk("do_wp_page: bogus page at address %08lx (%08lx)\n",address,old_page);
    send_sig(SIGKILL, vma->vm_task, 1);
    goto end_wp_page;
bad_wp_pagemiddle:
    printk("do_wp_page: bogus page-middle at address %08lx (%08lx)\n", address, pmd_val(*page_middle));
    send_sig(SIGKILL, vma->vm_task, 1);
    goto end_wp_page;
bad_wp_pagedir:
    printk("do_wp_page: bogus page-dir entry at address %08lx (%08lx)\n", address, pgd_val(*page_dir));
    send_sig(SIGKILL, vma->vm_task, 1);
end_wp_page:
    if (new_page)
        free_page(new_page);
    return;
}

/*
 * do_no_page()は新しいページのマッピングを作ろうとする.
 * これは既存のページと共有しようとするが,次のページフォルトを避けるため
 * "write_access"パラメータが真である場合は別のコピーを作る.
 * 
 */
void do_no_page(struct vm_area_struct * vma, unsigned long address,
    int write_access)
{
    pte_t * page_table;
    pte_t entry;
    unsigned long page;

    page_table = get_empty_pgtable(vma->vm_task,address);
    if (!page_table)
        return;
    entry = *page_table;
    if (pte_present(entry))
        return;
    if (!pte_none(entry)) {
        do_swap_page(vma, address, page_table, entry, write_access);
        return;
    }
    address &= PAGE_MASK;
    if (!vma->vm_ops || !vma->vm_ops->nopage) {
        ++vma->vm_task->mm->rss;
        ++vma->vm_task->mm->min_flt;
        get_empty_page(vma, page_table);
        return;
    }
    page = get_free_page(GFP_KERNEL);
    if (share_page(vma, address, write_access, page)) {
        ++vma->vm_task->mm->min_flt;
        ++vma->vm_task->mm->rss;
        return;
    }
    if (!page) {
        oom(current);
        put_page(page_table, BAD_PAGE);
        return;
    }
    ++vma->vm_task->mm->maj_flt;
    ++vma->vm_task->mm->rss;
    /*
     * 4番目の引数は低レベルのコードにコピーを支持し,共有が可能であっても
     * ページを共有しない"no_share"である.これは本質的にCopy-on-Writeを
     * すぐ検出するものとなる.
     */
    page = vma->vm_ops->nopage(vma, address, page,
        write_access && !(vma->vm_flags & VM_SHARED));
    if (share_page(vma, address, write_access, 0)) {
        free_page(page);
        return;
    }
    /*
     * この早めの馬鹿げたPAGE_DIRTY設定は,i386のページ保護がクソなので
     * 競合を取り除く.だが他のアーキテクチャにも使えるだろう.
     *
     * もしwrite_accessが真であれば,ページの排他的なコピーをもつか,あるいは
     * これは共有マッピングなので,あとでそれを処理する必要がないように
     * 書き込み可能かつ汚れているものであるとする.
     * 
     */
    entry = mk_pte(page, vma->vm_page_prot);
    if (write_access) {
        entry = pte_mkwrite(pte_mkdirty(entry));
    } else if (mem_map[MAP_NR(page)] > 1 && !(vma->vm_flags & VM_SHARED))
        entry = pte_wrprotect(entry);
    put_page(page_table, entry);
}

do_wp_page()関数は書き込み保護されたページが最初に指定されたアドレスにあるかどうかを確認する.一度しか参照されない場合,書き込み保護は取り消される.何度も参照されていれば,そのページのコピーが生成され,エラーの原因となったプロセスのページテーブルへ,書き込み保護なしで入力される.

もしpresence attributeがセットされていないページテーブルに,空でないエントリが存在するなら,do_no_page()関数はdo_swap_page()関数を呼び出す.仮想メモリ空間に対してnopage()ルーチンが定義されていないなら,空のページがメモリ空間にマップされる.そうでないなら,ページが別のプロセスと共有できるかどうかを確認する.だめならnopage()が呼び出される.

static inline void do_swap_page(struct vm_area_struct * vma, unsigned long address,
        pte_t * page_table, pte_t entry, int write_access)
{
    pte_t page;

    if (!vma->vm_ops || !vma->vm_ops->swapin) {
        swap_in(vma, page_table, pte_val(entry), write_access);
        return;
    }
    page = vma->vm_ops->swapin(vma, address - vma->vm_start + vma->vm_offset, pte_val(entry));
    if (pte_val(*page_table) != pte_val(entry)) {
        free_page(pte_page(page));
        return;
    }
    if (mem_map[MAP_NR(pte_page(page))] > 1 && !(vma->vm_flags & VM_SHARED))
        page = pte_wrprotect(page);
    ++vma->vm_task->mm->rss;
    ++vma->vm_task->mm->maj_flt;
    *page_table = page;
    return;
}

パラメータとして与えられた仮想メモリ空間に対してswapin()が定義されていない場合,swap_in()関数が呼び出される.

( include/linux/mm.h )

extern void swap_in(struct vm_area_struct *, pte_t *, unsigned long id, int write_access);

( mm/swap.c )

/*
 * このテストは馬鹿げているようにみえるが,基本的には待ち状態と同じように
 * 他のプロセスがスワップインしていないことを確認している.
 *
 * また,このページインが書き込みアクセスが原因だった場合,
 * スワップキャッシュに追加するのは面倒ではない.
 */
void swap_in(struct vm_area_struct * vma, pte_t * page_table,
        unsigned long entry, int write_access)
{
        unsigned long page = get_free_page(GFP_KERNEL);

        if (pte_val(*page_table) != entry) {
                free_page(page);
                return;
        }
        if (!page) {
                *page_table = BAD_PAGE;
                swap_free(entry);
                oom(current);
                return;
        }
        read_swap_page(entry, (char *) page);
        if (pte_val(*page_table) != entry) {
                free_page(page);
                return;
        }
        vma->vm_task->mm->rss++;
        vma->vm_task->mm->maj_flt++;
        if (!write_access && add_to_swap_cache(page, entry)) {
                *page_table = mk_pte(page, vma->vm_page_prot);
                return;
        }
        *page_table = pte_mkwrite(pte_mkdirty(mk_pte(page, vma->vm_page_prot)));
        swap_free(entry);
        return;
}

この関数はページを読む.該当するスワップ空間の番号とスワップ空間のページ番号はentryで指定する.

スワップ空間のページはswap_free()によって解放される.これはswap_mapの適切なビットを解除する.

仮想メモリ空間のswap_in()ルーチンはページを読み込む.次の章では,この機能をSystem Vの共有メモリとともに検討する.