xv6 paging読む

次は kernelの初期化部分を見ていきます. 解説記事というよりは作業記録であり, 備忘録です. ネット上に先人が書いてくださった記事が大量にあってありがたい.

entry.S -> main.c

memlayout.h

// Key addresses for address space layout (see kmap in vm.c for layout)
#define KERNBASE 0x80000000         // First kernel virtual address
#define KERNLINK (KERNBASE+EXTMEM)  // Address where kernel is linked

#define V2P(a) (((uint) (a)) - KERNBASE)
#define P2V(a) ((void *)(((char *) (a)) + KERNBASE))

#define V2P_WO(x) ((x) - KERNBASE)    // same as V2P, but without casts
#define P2V_WO(x) ((x) + KERNBASE)    // same as P2V, but without casts

• V: 0x80100000 -> P: 0x00100000

entry.S

.globl _start
_start = V2P_WO(entry)

.globl entry
entry:
 # paging 処理
 # set 4MiB paging
 movl    %cr4, %eax
  orl     $(CR4_PSE), %eax
  movl    %eax, %cr4

  # Set page directory
  movl    $(V2P_WO(entrypgdir)), %eax
  movl    %eax, %cr3

  # Turn on paging.
  movl    %cr0, %eax
  orl     $(CR0_PG|CR0_WP), %eax
  movl    %eax, %cr0

  # Set up the stack pointer.
  movl $(stack + KSTACKSIZE), %esp

 mov $main, %eax
  jmp *%eax

• movl = mov + l
  • op-suffix: l: long
    • GAS_基本文法 CapmNetwork

set 4MiB paging

• %cr4 && CR4_PSE: PSE = page sizeを4MiBにするかのフラグ, デフォルトは4KiB
  • Control register - Wikipedia

set page directory

• %cr3: Page Directory Base Register

  • #todo [[Page Directory]] ってなんだ
    • xv6実装の詳解(boot処理編: segmentationとpagingを中心に) - Qiita

• paging関連の設定した後に main() にjmp

• #todo $main はアドレスのようだがどこから来たのか?

• gasでx86アセンブラ(メモ) - Qiita

main.c

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
}

kinit

kalloc.c

// Initialization happens in two phases.
// 1. main() calls kinit1() while still using entrypgdir to place just
// the pages mapped by entrypgdir on free list.
// 2. main() calls kinit2() with the rest of the physical pages
// after installing a full page table that maps them on all cores.

kinit1(void* vstart, void* vend)

first address after kernel loaded from ELF file

• end は kernel.ld の PROVIDE(end = .) のアドレスを指す
• P2V(4 * 1024 * 1024) は 4MiB + KERNBASE

void
kinit1(void *vstart, void *vend)
{
  initlock(&kmem.lock, "kmem");
  kmem.use_lock = 0;
  freerange(vstart, vend);
}

freerange

void
freerange(void *vstart, void *vend)
{
  char *p;
  p = (char*)PGROUNDUP((uint)vstart);
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
    kfree(p);
}

kfree

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(char *v)
{
 // 単方向リスト
  struct run *r;

  if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
    panic("kfree");

 // 1埋め
  memset(v, 1, PGSIZE);

  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = (struct run*)v;
  # 前と繋げる
  r->next = kmem.freelist;
  kmem.freelist = r;
  if(kmem.use_lock)
    release(&kmem.lock);
}

• kmem.freelist を前回の run のポインタとして単方向リストとして繋げていく, それをページ毎にやるので逆向きにつながる.

kvmalloc

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

setupkvm()

• stand for kernel virtual mapping?
• やることはページの領域を kalloc() で確保していく作業

(xv6 PDF pp.31 から引用)

static struct kmap
{
  void *virt;
  uint phys_start;
  uint phys_end;
  // permission
  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
};

paging関連の用語

• pgdir: PDTを指す
• PDT: Page Directory Table = Page Directoryの集まり(4MiB * 1024 = 4GB)
  • PT: Page Table: PTEの集まり(4KiB * 1024 = 4MiB)
    • PTE: ページ=Page Table Entry(4KiB)
• 4つのPage Directoryがある

// 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;
}

• page directory: ページ置いておくための領域?
• kalloc() でVAが貰える
  • PTE: Page Table Entry?
  • pde_t: uint

mmu.h

perm はこれ

// Page table/directory entry flags.
#define PTE_P           0x001   // Present
#define PTE_W           0x002   // Writeable
#define PTE_U           0x004   // User
#define PTE_PS          0x080   // Page Size

VAからPAに変換してページを特定する

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 (;;)
  {
    // VAの情報をしまうためのPTEを取得
    if ((pte = walkpgdir(pgdir, a, 1)) == 0)
      return -1;
    if (*pte & PTE_P)
      panic("remap");

    // page table entryに物理アドレスを設定
    // alloc済みを示す = PTE_Pを立てる
    *pte = pa | perm | PTE_P;
    if (a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

• walkpgdir でやりたいこと: VAからPTE(ページ)のPAを特定してPTEのポインタを返す
  • 確保されていない場合(!PTE_P), PTE分の領域を kalloc() する
  • VAの上位bitからPDE, PTEのインデックスを計算

static pte_t *
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
  // 0x3ff == 1023
  // 22shiftするので上位10bitのみを使いpage directoryからどのpgdir entryかを特定する
  // page directory entry == page tableのアドレスを指す
  pde = &pgdir[PDX(va)];
  if (*pde & PTE_P)
  {
    pgtab = (pte_t *)P2V(PTE_ADDR(*pde));
  }
  else
  {
   // allocが1で呼ばれるのでallocされる
    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)];
}

// 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

// 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) --/

switchkvm()

lcr3(V2P(kpgdir)); // switch to the kernel page table

• kpgdirのPAを %cr3 にしまう

Page Table Entry

VAの :31..12 と Page-Directory Entryの :31..12 でページのPAを特定し, VAの :11..0 ページ内の何バイト目かがわかる.

(File:X86 Paging 4K.svg - Wikipedia より)

• メモリ管理ユニット - Wikipedia

疑問: VA->PA変換はCPUがやるのか

-> CPUのMMUがやる. やるかどうかは CR0 の :31 が決める(entry.S L60) Linux(64bit)のページング機構 - 人生は勉強ブログ

mpinit()

• マルチプロセッサに対応するための機能
• x86-64ではマルチプロセッサの為の [[MultiProcessor Specification]] が策定されているらしい
  • いくらか発展的な話題ぽいのでskip? #todo

参考文献

• xv6 pdf
• xv6実装の詳解(boot処理編: segmentationとpagingを中心に) - Qiita
• 詳解xv6 Page tables 1 – うたもく