レガシーガジェット研究所

気になったことのあれこれ。

Linux Kernel ~ ページング x86編 ~

概要

「詳解Linux Kernel」を参考にVersion 2.6.11のソースコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelx86とする。

今回の内容は前回の「セグメンテーション」の続きとなっており、アドレス変換機構のページングについて見ていく。

ページング機構

x86のプロセッサではcr0制御レジスタPGフラグをセットすることでページングが有効となる。逆にクリアされている場合はリニアアドレス=物理アドレスと見なされる。

ページフレーム

物理メモリを固定長(4096 byte)で分割したものの1つ。よって物理メモリはページフレームの集合体と見なすことができる。

ページ

リニアアドレスを固定長(4096 byte)で分割したものの1つ。よってセグメントはページの集合体と見なすことができる。ページに対応する物理アドレスとアクセス権を設定すれば、メモリのページフレームやディスクに置くことができる。1つのページ内に存在するリニアアドレスは連続する物理アドレスに対応する。アクセス対象のページがメモリに存在しない場合やアクセス権によってアクセスが不可能な場合は「ページフォルト例外」を発生させる。

ページテーブル

リニアアドレスと物理アドレスマッピング情報(ページテーブルエントリ)を管理するためのテーブル。ページテーブルはメモリ上に存在し、ページング回路を有効にする際にカーネルが初期化する。

ページディレクト

テーブルの構造をしており各エントリにはページテーブルの物理アドレスを保持する。ページングを行う際は基本的にページディレクトリ→ページテーブル→ページと階層構造で変換を行う。

ページエントリ

ページディレクトリやページテーブルのエントリは以下のような構造になっている。

bit 用途
0 ページがメモリ上に存在しているか
1 書き込みが可能であるか
2 ユーザ権限であるか
3 ページ情報をライトスルーするか
4 ページキャッシュが無効になっているか
5 アクセスされたか
6 書き込まれたか
7 ページサイズ: 1=2MB~4MB, 0=4KB
8 LTBからクリアするか
9 プログラマが使用可能
10 ~ 11 未使用
12 ~ 31 ページテーブルの実アドレス

ページング

Intelのプロセッサでページング回路が扱うのは4KBのページである。よってプロセスが4GBのメモリを使用する時、ページテーブルエントリが4バイトであれば1ページあたり4KB(4,096byte)の物理アドレスを対象とするので1M(1,048,575)ページ必要となり、合計で1プロセスあたり4MBのメモリを使用することになる。これではメモリ効率が悪いのでページテーブルに全てのエントリを読み込むのではなく、必要なエントリだけをメモリ上に配置するといった方法を取る。

ページングのアドレス変換ではまず32bit長のリニアアドレスを以下の3つのフィールドに分割する。

  • ページディレクトリ内のオフセット: 上位10bit
  • ページテーブル内のオフセット: 中間の10bit
  • ページフレーム内のオフセット: 下位12bit

まずプロセスはページディレクトリをメモリ上に持つ。このページディレクトリの物理アドレスは制御レジスタの1つであるcr3が保持する。cr3レジスタを参照しページディレクトリの物理アドレスを求め、上記のリニアアドレス内の上位10bitをオフセットとして用いてページディレクトリのエントリを指定する。当該エントリはページテーブルの物理アドレスを保持している。オフセットが10bitでなのでページディレクトリは1024個のエントリを持つ。

次に上記で求めたページテーブルの物理アドレスに対し、リニアアドレスの中間10bitをオフセットとして用いることでページテーブル内のエントリを指定する。当該エントリは実際のページフレームの物理アドレスを指す。オフセットが10bitなのでページテーブルは1024個のエントリを持つ。

最後に先ほど求めたページフレームの物理アドレスに対し、リニアアドレスの下位12bitをオフセットとして用いることでページフレーム内の物理アドレスを指定する。

上記から、1024(= 10bit = ページディレクトリの総エントリ数) * 1024(= 10bit = ページテーブルの総エントリ数) * 4096バイト(= 12bit = 1ページのサイズ) で合計32bitで4GBが表現できていることがわかる。先ほども言った通りこれら全てのエントリを保持することは効率的でないので必要なページテーブルのみをメモリ上に配置することでメモリを節約を行う。

実装

仮想アドレス(リニアアドレス)からページテーブルエントリを取得する関数は以下のように定義されている。 (コードブロックの1行目にファイルパスを記載している)

pte_t *lookup_address(unsigned long address) 
{ 
    pgd_t *pgd = pgd_offset_k(address);
    pud_t *pud;
    pmd_t *pmd;
    if (pgd_none(*pgd))
        return NULL;
    pud = pud_offset(pgd, address);
    if (pud_none(*pud))
        return NULL;
    pmd = pmd_offset(pud, address);
    if (pmd_none(*pmd))
        return NULL;
    if (pmd_large(*pmd))
        return (pte_t *)pmd;
        return pte_offset_kernel(pmd, address);
} 

まずページディレクトリのアドレスを取得するpgd_offset_k()は以下のように定義されている。

// arch/x86/include/asm/pgtable.h
/*
 * a shortcut which implies the use of the kernel's pgd, instead
 * of a process's
 */
#define pgd_offset_k(address) pgd_offset(&init_mm, (address))

上記のinit_mmは以下のように定義されており、メンバー変数であるswapper_pg_dirがページディレクトリの配列を保持している。

// arch/i386/kernel/init_task.c
struct mm_struct init_mm = INIT_MM(init_mm);

// include/linux/init_task.h
#define INIT_MM(name) \
{                              \
   .mm_rb      = RB_ROOT,              \
   .pgd        = swapper_pg_dir,           \
   .mm_users   = ATOMIC_INIT(2),          \
   .mm_count   = ATOMIC_INIT(1),          \
   .mmap_sem   = __RWSEM_INITIALIZER(name.mmap_sem),   \
   .page_table_lock =  SPIN_LOCK_UNLOCKED,         \
   .mmlist     = LIST_HEAD_INIT(name.mmlist),      \
   .cpu_vm_mask    = CPU_MASK_ALL,             \
   .default_kioctx = INIT_KIOCTX(name.default_kioctx, name),   \
}

include/asm-i386/pgtable.h
extern pgd_t swapper_pg_dir[1024];

先ほどのpgd_offset()だが、以下のようにページディレクトリとリニアアドレスから取り出したオフセットを加算し、ページディレクトリのエントリを取得しているのがわかる。

/*
 * the pgd page can be thought of an array like this: pgd_t[PTRS_PER_PGD]
 *
 * this macro returns the index of the entry in the pgd page which would
 * control the given virtual address
 */
#define pgd_index(address) (((address) >> PGDIR_SHIFT) & (PTRS_PER_PGD - 1))

/*
 * pgd_offset() returns a (pgd_t *)
 * pgd_index() is used get the offset into the pgd page's array of pgd_t's;
 */
#define pgd_offset_pgd(pgd, address) (pgd + pgd_index((address)))
/*
 * a shortcut to get a pgd_t in a given mm
 */
#define pgd_offset(mm, address) pgd_offset_pgd((mm)->pgd, (address))

pgd_index()でシフトやマスクに使用されている変数は以下のように定義されており、しっかりとページディレクトリのオフセット(上位10bit)を取得しているのがわかる。

pgd_offset()で第一引数となっているのはプロセスのメモリなどに関係する情報を持つmm_struct構造体で、そのプロセスに対応するページディレクトリのアドレスをメンバー変数で保持している。pgd_offset()マクロではまずそのメンバー変数とオフセットとなるアドレスをpgd_offset_pgd()マクロに渡している。

pgd_offset_pgd()では第一引数のページディレクトリのアドレスに第二引数のオフセットとなるアドレスを取るpgd_index()マクロの結果を加算している。

最後にpgd_index()だが、このマクロがアドレス変換の主要部分となる。ページディレクトリのオフセットアドレスであるリニアアドレスの上位10bitを取得するために引数であるリニアアドレスをPGDIR_SHIFT分シフトしている。上記ではPGDIR_SHIFTは22と定義されているのでこれで上位10bitが取得できるのがわかる。そして最後にPTRS_PER_PGDから1減算した数とAND演算を行なっている。これは上位10bit以外を削ぎ落とすための処理でPTRS_PER_PGDの1024から1引くことで全てのビット(10bit)が1となり、それによって10bitのみを取得する。PGDIR_SHIFT及びPTRS_PER_PGDは以下のように定義されている。

// arch/x86/include/asm/pgtable-2level_types.h
/*
 * traditional i386 two-level paging structure:
 */
#define PGDIR_SHIFT    22
#define PTRS_PER_PGD   1024

lookup_addressのコードを見ると何段階にも分けて仮想アドレスを変換しているのがわかる。実は前述したページディレクトリとページテーブル以外にも別のテーブルがいくつか存在し実際には以下の4種類がある。

ページアッパーディレクトリおよびページミドルディレクトリは両者とも構造やエントリの構造は前述したページディレクトリやページテーブルと同じである。 ページ変換の段数はアーキテクチャに大きく依存し、今回の場合だとx86(32bit)アーキテクチャを対象にしているので実際のところは2段階となっている。

コードを見ると4段階で変換されているように見えるが実際にページアッパーディレクトリやページミドルディレクトリのエントリを取り出す際にはページ変換の段数を考慮し、今回の場合(2段階)だと単純にページグローバルディレクトリのエントリを返すようになっている。これが64bitアーキテクチャになると挙動が異なってくる。

実際にソースを見るとわかるが、まず上記のp4d_offset()は以下のように定義されている。 そのままページグローバルディレクトリのエントリが返されるのがわかる。

// include/asm-generic/pgtable-nop4d.h
static inline p4d_t *p4d_offset(pgd_t *pgd, unsigned long address)
{
    return (p4d_t *)pgd;
}

次のpud_offset()を見て行く。定義は以下のようにされており、またもキャストされてそのまま返されている。

// include/asm-generic/pgtable-nopud.h
static inline pud_t *pud_offset(p4d_t *p4d, unsigned long address)
{
    return (pud_t *)p4d;
}

次にpmd_offset()だが先ほどと同様にページグローバルディレクトリのエントリを返す。

// include/asm-generic/pgtable-nopmd.h
static inline pmd_t * pmd_offset(pud_t * pud, unsigned long address)
{
    return (pmd_t *)pud;
}

最後にページテーブルのエントリを返しているpte_offset_kernel()だが、以下のように定義されている。

// arch/x86/include/asm/pgtable.h
static inline pte_t *pte_offset_kernel(pmd_t *pmd, unsigned long address)
{
    return (pte_t *)pmd_page_vaddr(*pmd) + pte_index(address);
}

先にページテーブルのインデックスを取得するpte_index()から見ていく。定義は以下のようになっている。

// arch/x86/include/asm/pgtable.h
/*
 * the pte page can be thought of an array like this: pte_t[PTRS_PER_PTE]
 *
 * this function returns the index of the entry in the pte page which would
 * control the given virtual address
 */
static inline unsigned long pte_index(unsigned long address)
{
    return (address >> PAGE_SHIFT) & (PTRS_PER_PTE - 1);
}

// arch/x86/include/asm/page_types.h
/* PAGE_SHIFT determines the page size */
#define PAGE_SHIFT     12

// arch/x86/include/asm/pgtable-2level_types.h
/*
 * the i386 is two-level, so we don't really have any
 * PMD directory physically.
 */
#define PTRS_PER_PTE   1024

上記ではまず引数で受け取ったaddress(リニアアドレス)をPAGE_SHIFT(12bit)シフトし、PTRS_PER_PTE - 1(0x3FF)と論理積を取ることで中間の10bit = ページテーブル内のオフセットを取得している。

続いてページテーブルのアドレスを取得するpmd_page_vaddr()を見ていく。

// arch/x86/include/asm/pgtable.h
static inline unsigned long pmd_page_vaddr(pmd_t pmd)
{
    return (unsigned long)__va(pmd_val(pmd) & pmd_pfn_mask(pmd));
}

上記では複数の関数が呼ばれているので順に見ていく。pmd_val()は以下のように定義されている。

// arch/x86/include/asm/pgtable.h
#define pmd_val(x) native_pmd_val(x)

// arch/x86/include/asm/pgtable_types.h
static inline pmdval_t native_pmd_val(pmd_t pmd)
{
    return native_pgd_val(pmd.pud.p4d.pgd);
}

先ほどにもあったように、ページディレクトリのエントリを返していることがわかる。続いてpmd_pfn_mask()を見ていく。

// arch/x86/include/asm/pgtable_types.h
static inline pmdval_t pmd_pfn_mask(pmd_t pmd)
{
    if (native_pmd_val(pmd) & _PAGE_PSE)
        return PHYSICAL_PMD_PAGE_MASK;
    else
        return PTE_PFN_MASK;
}

上記の条件分岐ではページのサイズを確認し戻り値を返している。_PAGE_PSEは以下のように定義されておりページのサイズが2 ~ 4MBバイトである場合に1となるフラグで、今回の場合は上記の条件式は「偽」を返すので戻り値はPTE_PFN_MASKとなる。

// arch/x86/include/asm/pgtable_types.h
#define _PAGE_BIT_PSE      7  /* 4 MB (or 2MB) page */
#define _PAGE_PSE  (_AT(pteval_t, 1) << _PAGE_BIT_PSE)

戻り値となるPTE_PFN_MASKは以下のように定義されており、PAGE_MASK__PHYSICAL_MASK論理積からなっている。

// arch/x86/include/asm/pgtable_types.h
/* Extracts the PFN from a (pte|pmd|pud|pgd)val_t of a 4KB page */
#define PTE_PFN_MASK       ((pteval_t)PHYSICAL_PAGE_MASK)

// arch/x86/include/asm/pgtable_types.h
/* Cast *PAGE_MASK to a signed type so that it is sign-extended if
   virtual addresses are 32-bits but physical addresses are larger
   (ie, 32-bit PAE). */
#define PHYSICAL_PAGE_MASK (((signed long)PAGE_MASK) & __PHYSICAL_MASK)

PAGE_MASKは以下のように定義されており、上記の場合は0 ~ 11bit目が"0"となり、それ以外が"1"となるため、インデックス以外のページテーブルの実アドレス部分(12bit ~ 31bit)が残ることになる。

#define PAGE_MASK       (~(PAGE_SIZE-1))

// arch/x86/include/asm/page_types.h
/* PAGE_SHIFT determines the page size */
#define PAGE_SHIFT     12
#define PAGE_SIZE      (_AC(1,UL) << PAGE_SHIFT)

__PHYSICAL_MASKは以下のようになっている。これは0bit ~ 31bit目までを"1"とする処理でそれ以降をそぎ落とすために使用する。

#define __PHYSICAL_MASK     ((phys_addr_t)(__sme_clr((1ULL << __PHYSICAL_MASK_SHIFT) - 1)))

// arch/x86/include/asm/page_32_types.h
#define __PHYSICAL_MASK_SHIFT  32

ここまででpmd_val()のアドレスからpmd_pfn_mask()を用いてページテーブルのアドレスを取得するまでの処理となる。

ページテーブルのアドレスに先ほどpte_index()で取得したページテーブルのオフセットを加算することでテーブルエントリを取得できる。

参考文献