Unix

xv6OSを真面目に読みこんでカーネルを完全に理解する -ページテーブル(PDT/PTD) 編-

はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみにインスパイアされてxv6 OSを読んでます。

UNIX V6自体はx86CPUでは動作しないため、基本的には、UNIXv6をX86アーキテクチャで動くようにしたxv6 OSのリポジトリをForkしたkash1064/xv6-public: xv6 OSのソースコードを読んでいくことにしました。

前回main関数で初めに実行されるkinit1関数による排他制御周りの挙動を確認しました。

xv6OSを真面目に読みこんでカーネルを完全に理解する -メモリ割り当て・排他制御 編- xv6OSを真面目に読みこんでカーネルを完全に理解する -GDBデバッグ環境構築編- はじめてのOSコードリーディング ~UNIX...

今回はkvmalloc関数によるxv6カーネルのページテーブルの初期化を追っていきます。

もくじ

32bitページングについて

今回はxv6OSのkvmalloc関数から読んでいきます。

kvmalloc関数はカーネルのページテーブルを作成する関数です。

そのため、ソースコードを読む前に、32bit環境でのページング機構について整理しておきます。

ページング機構はMMU(Memory Management Unit)によって実装されます。

x86環境では、MMUはPD(ページングディレクトリ)とPT(ページングテーブル)を利用してメモリマップを行います。

PDTとPT

PDTとPTにはそれぞれPDE(ページディレクトリエントリ)とPTE(ページテーブルエントリ)が含まれます。

PDEとPTEはどちらも1つ当たり4バイト(32bit)のサイズであり、PDにはPDEが、PTにはPTEが、それぞれ1024個含まれます。

これによってPDEとPTEはどちらも4KiBのサイズ(x86におけるデフォルトの1ページ分)になります。

各エントリの詳細については以下のリンク先が参考になります。

参考:Paging – OSDev Wiki

仮想アドレスから物理アドレスを参照する流れ

仮想アドレスを物理アドレスに変換する際、仮想アドレスは以下の3つに分割されます。

  • 最上位10bit:PDEのインデックス
  • 次の10bit:PTEのインデックス
  • 最下位12bit:ページオフセット

アドレス変換の際、MMUはPDを参照して仮想アドレスのインデックスからPDEを特定します。

次にPDEの情報と、仮想アドレスのインデックスからPTEを特定します。

PTEは物理アドレスのベースアドレスを解決するため、仮想アドレスのオフセットと合わせて参照先の物理アドレスを特定することができます。

詳細な流れは以下の図がわかりやすかったため引用しています。

https://yukituna.com/wp-content/uploads/2022/01/zu04.jpg

参照画像:第6回 メモリー上のデータを見えなくする(前編) | 日経クロステック(xTECH)

PDは単なるPDEの配列形式になっています。

PDの先頭アドレスはCR3レジスタに格納されています。

kvmalloc関数

さて、前回に引き続きカーネルのmain関数の処理を追っていきます。

// Bootstrap processor starts running C code here.
// Allocate a real stack and switch to it, first
// doing some setup required for memory allocator to work.
int main(void)
{
  kinit1(end, P2V(4*1024*1024)); // phys page allocator
  kvmalloc();      // kernel page table
  mpinit();        // detect other processors
  lapicinit();     // interrupt controller
  seginit();       // segment descriptors
  picinit();       // disable pic
  ioapicinit();    // another interrupt controller
  consoleinit();   // console hardware
  uartinit();      // serial port
  pinit();         // process table
  tvinit();        // trap vectors
  binit();         // buffer cache
  fileinit();      // file table
  ideinit();       // disk 
  startothers();   // start other processors
  kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
  userinit();      // first user process
  mpmain();        // finish this processor's setup
}

前回kinit1関数が終了するところまで進めたので、今回はkvmalloc関数から見ていきます。

kvmalloc関数はvm.cで以下のように定義されています。

// Allocate one page table for the machine for the kernel address
// space for scheduler processes.
void kvmalloc(void)
{
  kpgdir = setupkvm();
  switchkvm();
}

kvmalloc関数はカーネルのページテーブルを変更します。

ここで、カーネルがプロセスのアドレス空間を管理するための設計を持ったページテーブルに切り替えます。

参考:P.30 xv6OS

なお、xv6OSではプロセスごとに1つのページテーブルが作成され、プロセスの実行時にはカーネルは現在のプロセスのページテーブルを使用します。

また、kpgdirというCPUが実行していないプロセスを管理するページテーブルが用意されています。

仮想メモリについて

xv6OSだけでなく、WindowsやLinuxなどの32bitOS(x86アーキテクチャ)では、プロセスごとに仮想メモリというプライベートなメモリ空間が割り当てられます。

各プロセスごとの仮想アドレス空間は独立しているため、それぞれが任意のアドレスから2GiB分の仮想アドレスを指定してメモリアクセスを行うことができます。

(プロセス側があるアドレスの参照を行ったときに、実際に物理メモリのどのアドレスを参照することになるかは、カーネル側で管理します。)

この仕組みによって、ページングを行っていてもプロセスは常に仮想アドレスに対してメモリアクセスを行うことができるため、アプリケーション側は物理メモリのアドレス変更を考慮することなく開発することができます。

また、32bitOSは最大4GiBまでのアドレス空間しか管理することができません。

しかし、プロセスごとに仮想アドレス空間を作成しページングの仕組みを利用することで、実際よりも大きなメモリ空間を利用してシステムを動かすことができるようになります。

そのほかにも、プロセス間でメモリ空間が独立していることによってメモリの競合を防いだりやアクセス制御を行ったりすることもできます。

ちなみに、なぜ32bitOSの扱うことができるアドレス空間が最大4GiBなのに、仮想アドレス空間は2GiBなのかというと、上位2GiBはカーネルに予約されているためのようです。

詳しくは以下の図が参考になります。

https://yukituna.com/wp-content/uploads/2022/01/image-20.png

参考画像:P.31 xv6OS

setupkvm関数

とりあえずkvmalloc関数の処理を追ってみます。

kpgdir = setupkvm();の行では、setupkvm関数の戻り値をpde_t型のkpgdirに格納しています。

ちなみに、pde_t型はmmu.hで以下のように定義されており、uint型であることがわかります。

typedef uint pte_t;

setupkvm関数はvm.cで以下のように定義されています。

// Set up kernel part of a page table.
pde_t* setupkvm(void)
{
  pde_t *pgdir;
  struct kmap *k;

  if((pgdir = (pde_t*)kalloc()) == 0) return 0;
  memset(pgdir, 0, PGSIZE);
  if (P2V(PHYSTOP) > (void*)DEVSPACE) panic("PHYSTOP too high");
  for(k = kmap; k < &kmap[NELEM(kmap)]; k++)
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,
                (uint)k->phys_start, k->perm) < 0) 
    {
      freevm(pgdir);
      return 0;
    }
  return pgdir;
}

まずは変数宣言の部分です。

pde_t *pgdir;
struct kmap *k;

pde_tは前述の通りuintと同義です。

次のkmap構造体はvm.cで定義されているカーネルのメモリマッピングテーブルです。

// This table defines the kernel's mappings, which are present in
// every process's page table.
static struct kmap {
  void *virt;
  uint phys_start;
  uint phys_end;
  int perm;
} kmap[] = {
 { (void*)KERNBASE, 0,             EXTMEM,    PTE_W}, // I/O space
 { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0},     // kern text+rodata
 { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory
 { (void*)DEVSPACE, DEVSPACE,      0,         PTE_W}, // more devices
};

開始・終了アドレスと権限が定義されています。

初期化されているテーブルのマッピングは、先ほど貼った以下の画像のレイアウトと一致します。

https://yukituna.com/wp-content/uploads/2022/01/image-20.png

参考画像:P.31 xv6OS

kalloc関数によるページの確保

ページテーブルの初期化後、使用するメモリ領域の確認と初期化を行っています。

if((pgdir = (pde_t*)kalloc()) == 0) return 0;
memset(pgdir, 0, PGSIZE);
if (P2V(PHYSTOP) > (void*)DEVSPACE) panic("PHYSTOP too high");

kalloc関数はkalloc.cで定義されている以下の関数です。

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
char* kalloc(void)
{
  struct run *r;
  if(kmem.use_lock) acquire(&kmem.lock);
  r = kmem.freelist;
  if(r) kmem.freelist = r->next;
  if(kmem.use_lock) release(&kmem.lock);
  return (char*)r;
}

前回の記事で確認した通り、この時点ではまだロックは無効化されています。

そのためacquire関数とrelease関数は無視します。

kmem.freelistには、解放されているページが短方向連結リストで格納されています。

つまり、kalloc関数は単に解放されている領域の有無を確認して、1ページ分の領域を確保している処理を行っているようです。

確保に成功した場合kalloc関数は確保したページのポインタ(?)を返却し、pgdirに格納します。

これによって、次の行のmemset(pgdir, 0, PGSIZE);で確保した1ページ分のメモリ領域を0で初期化することができます。

memset関数の挙動も前回の記事で確認したので割愛します。

最後の行はPHYSTOPの値がDEVSPACEを超過していないかを検証しているだけなので割愛します。

最終的に確保された1ページ分の領域pgdirが、この後PDTとして使用されます。

仮想アドレスのPTEの作成

ここまでの処理でpgdirには確保した1ページ分のメモリ領域の参照が格納されています。

for(k = kmap; k < &kmap[NELEM(kmap)]; k++) 
{
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start, (uint)k->phys_start, k->perm) < 0) 
    {
        freevm(pgdir);
        return 0;
    }
}
return pgdir;

NELEMdefs.hで定義された以下のマクロで、固定サイズの配列の要素数を返却します。

// number of elements in fixed-size array
#define NELEM(x) (sizeof(x)/sizeof((x)[0]))

つまり、k = kmap; k < &kmap[NELEM(kmap)]; k++のループ条件は単にすべてのkmap配列の要素に対して処理を実行せよという命令と同義です。

ここで肝になるのが以下の行です。

if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,(uint)k->phys_start, k->perm) < 0) 
{
    freevm(pgdir);
    return 0;
}

mappages関数は、vm.cで定義された関数で、 引数として与えられた仮想アドレスのPTE(ページテーブルエントリ)を作成し、同じく引数として与えられた物理アドレスを参照します。

PTEはページに対応する物理アドレスの値とアクセス制御や属性に関する情報を保持します。

https://yukituna.com/wp-content/uploads/2022/01/zu03b.jpg

参考画像:第6回 メモリー上のデータを見えなくする(前編) | 日経クロステック(xTECH)

参考:0から作るOS開発 ページングその1 ページとPTEとPDE

まずはソースコードを見てみます。

// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// be page-aligned.
static int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
  char *a, *last;
  pte_t *pte;

  a = (char*)PGROUNDDOWN((uint)va);
  last = (char*)PGROUNDDOWN(((uint)va) + size - 1);
  for(;;){
    if((pte = walkpgdir(pgdir, a, 1)) == 0)
      return -1;
    if(*pte & PTE_P)
      panic("remap");
    *pte = pa | perm | PTE_P;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

mappagesは以下の5つの引数を受け取ります。

  • *pgdir:確保したページ(PDT)
  • *va:PTEを作成する仮想アドレス
  • size:紐づける物理アドレス領域のサイズ
  • pa:紐づける物理アドレスの先頭アドレス
  • perm:割り当てる権限

まず、PTEを作成する仮想アドレスと紐づける物理アドレス領域のサイズをもとにしてページサイズでアラインメントされたアドレスがalastに格納されます。

アラインメントに使用するPGROUNDDOWNについては過去の記事で解説済みのため割愛します。

次のループはこのalastと一致するまでページサイズを加算しつつ実行されます。

for(;;){
  if((pte = walkpgdir(pgdir, a, 1)) == 0) return -1;
  if(*pte & PTE_P) panic("remap");
  *pte = pa | perm | PTE_P;
  if(a == last) break;
  a += PGSIZE;
  pa += PGSIZE;
}

実際にPTEの領域を確保しているのはwalkpgdir関数です。

walkpgdir関数はvm.cで定義された関数です。

引数として受け取ったページテーブルpgdirのPTEのアドレスを返します。


// Return the address of the PTE in page table pgdir
// that corresponds to virtual address va.  If alloc!=0,
// create any required page table pages.
static pte_t * 
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
  pde_t *pde;
  pte_t *pgtab;

  pde = &pgdir[PDX(va)];
  if(*pde & PTE_P){
    pgtab = (pte_t*)P2V(PTE_ADDR(*pde));
  } else {
    if(!alloc || (pgtab = (pte_t*)kalloc()) == 0) return 0;
    // Make sure all those PTE_P bits are zero.
    memset(pgtab, 0, PGSIZE);
    // The permissions here are overly generous, but they can
    // be further restricted by the permissions in the page table
    // entries, if necessary.
    *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;
  }
  return &pgtab[PTX(va)];
}

まず、pde = &pgdir[PDX(va)];の行ではPDTとして確保しているページのうち、PTEを格納するインデックスを解決しています。

PDX(va)mmu.hで定義されているマクロで、仮想アドレスからpage directory indexを解決しています。

// A virtual address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory |   Page Table   | Offset within Page  |
// |      Index     |      Index     |                     |
// +----------------+----------------+---------------------+
//  \--- PDX(va) --/ \--- PTX(va) --/

// page directory index
#define PDX(va)         (((uint)(va) >> PDXSHIFT) & 0x3FF)

// page table index
#define PTX(va)         (((uint)(va) >> PTXSHIFT) & 0x3FF)

#define PTXSHIFT        12      // offset of PTX in a linear address
#define PDXSHIFT        22      // offset of PDX in a linear address

続いて、if(*pde & PTE_P)の行では、取得したPDEのPresentビットを確認します。

PDEのPresentビットはページが現在物理メモリにあるのか仮想メモリにあるのかを特定するために使用します。

参考:Paging – OSDev Wiki

ここでは、引数として受け取った仮想アドレスのPDEの有無を検証しているようです。

初期状態では、memset関数によってPDは0に初期化されているため、以下の処理が呼び出されます。

if(!alloc || (pgtab = (pte_t*)kalloc()) == 0) return 0;

// Make sure all those PTE_P bits are zero.
memset(pgtab, 0, PGSIZE);
// The permissions here are overly generous, but they can
// be further restricted by the permissions in the page table
// entries, if necessary.
*pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;

第3引数のallocが1に設定されており、かつ仮想アドレスに対応するPDEが存在しない場合、ここで必要なPTが作成されます。

kalloc関数の挙動は先ほども確認したので割愛します。

ここで取得された1ページ分の領域はpgtabとして参照されます。

また、memsetによってすべてのバイトが0に初期化されます。

そして、PDEには物理アドレスに変換されたpgtabのアドレスと、PDEに設定される権限が与えられます。

最終的にwalkpgdir関数の戻り値としては、引数で受け取った仮想アドレスに対応するPDEから解決されるPDTの参照となります。

return &pgtab[PTX(va)];

さて、walkpgdir関数が終了したのでmappages関数に戻ります。

for(;;){
  if((pte = walkpgdir(pgdir, a, 1)) == 0) return -1;
  if(*pte & PTE_P) panic("remap");
  *pte = pa | perm | PTE_P;
  if(a == last) break;
  a += PGSIZE;
  pa += PGSIZE;
}

pteにはこの仮想アドレスに対応するPTEの領域が確保されました。

walkpgdir関数が実行された段階ではまだPTEはすべて0で初期化されたままですので、*pte = pa | perm | PTE_P;の行で物理アドレスとパーミッションの割り当てを行っています。

これで、mappages関数によって仮想アドレスと物理アドレスを紐づけるPTEの作成が完了しました。

freevm関数

最後にsetupkvm関数に戻ります。

以下のループはkmap配列の要素の数だけ繰り返されていました。

mappages関数によって、仮想アドレスと物理アドレスを紐づけるPDEとPTEが作成されました。

for(k = kmap; k < &kmap[NELEM(kmap)]; k++)
{
  if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,
              (uint)k->phys_start, k->perm) < 0) {
    freevm(pgdir);
    return 0;
  }
}
return pgdir;

もしページテーブルの作成に失敗した場合、freevm関数の引数にここまで使用してきたPDTのページpgdirが与えられメモリ領域が解放されます。

freevm関数もvm.cで定義された関数です。

freevm関数この時点では実行されないため、詳細は割愛します。

// Free a page table and all the physical memory pages
// in the user part.
void freevm(pde_t *pgdir)
{
  uint i;
  if(pgdir == 0) panic("freevm: no pgdir");
  deallocuvm(pgdir, KERNBASE, 0);
  for(i = 0; i < NPDENTRIES; i++){
    if(pgdir[i] & PTE_P){
      char * v = P2V(PTE_ADDR(pgdir[i]));
      kfree(v);
    }
  }
  kfree((char*)pgdir);
}

switchkvm関数

ここまででsetupkvm関数の処理は終了し、戻り値としてカーネルのPDTが返却されます。

// Allocate one page table for the machine for the kernel address
// space for scheduler processes.
void kvmalloc(void)
{
  kpgdir = setupkvm();
  switchkvm();
}

この記事の前半で確認した通り、カーネルの参照するPDTの先頭アドレスは、x86ではCR3レジスタに格納されます。

switchkvm関数の挙動はシンプルで、CR3レジスタに作成したPDTの仮想アドレスを物理アドレスに変換して格納しています。

// Switch h/w page table register to the kernel-only page table,
// for when no process is running.
void switchkvm(void)
{
  lcr3(V2P(kpgdir));   // switch to the kernel page table
}

lcr3関数はx86.hに定義されています。

static inline void
lcr3(uint val)
{
  asm volatile("movl %0,%%cr3" : : "r" (val));
}

これでkvmalloc関数によるカーネルのページテーブルの作成と切り替えが完了しました。

まとめ

これでxv6カーネルのmain関数で呼び出している18個の関数のうち、3つのソースコードを読みました。

まだまだ先は長いですが少しずつ進めていきます。

参考書籍

COMMENT

メールアドレスが公開されることはありません。