前言

我們昨天看到了 kernel space 中的 kernel virtual address space，今天我們會看到 user virtual address space 的相關分布，以及 user virtual address, kernel virtual address space 和 physical addess space 這三者之間的關係，最後提及用於記憶體管理的兩個函式，kalloc() 和 kfree()。

process's user address space

可以看到在 user space 底下的 process 從0可以最大增長到MAXVA，MAXVA為巨集，定義於kernel/riscv.h

#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))

大約為 256 GB，當 process 需要更多記憶體時，xv6 會通過 kalloc()來分配物理記憶體分頁，接著指向到新的物理記憶體分頁的 PTE 會加入到 process 的 page table 中，接著 xv6 會設置 PTE 的 flag，將分配到的 PTE_V ，讓這個地址可以被 MMU 轉換，剩下的 PTE 的 PTE_V 保持未設置的狀態。

不同 process 的 page table 將 user space virtual address 轉換成不同的物理記憶體分頁，而每個 process 即擁有獨立的記憶體空間 (每個 process 之間的物理記憶體分頁可以是不連續的)。而最上面的 trampoline，kernel 會將 kernel space 的 trampoline 映射到 user space 的 trampoline，因此，所有user space 的 trampoline 都會映射到一個物理記憶體分頁，以下說明 trapoline, trapfram page，並對 trap 快速的進行總覽。

trap 流程

這邊快速的對 trap 流程做一個總覽，後面會詳細的 trace trap 的程式碼，整個 trap 概念如昨天所提及的，可以使用下圖表示

整個 trap 流程大致上可以使用下圖進行表示

這裡可以看到 uservec 和 userret 為使用組合語言撰寫的程式碼，下面大致上說明 uservec 和 userret 的行為

• uservec
  • In user mode
    • 儲存 user mode 的暫存器
    • 載入 supervisor mode 的暫存器
  • In supervisor mode
    • satp 暫存器指向到 kernel page table
• userret
  • In supervisor mode
    • satp 暫存器指向到 user page table
  • In user mode
    • 回復 user mode 的暫存器
    • sret

可以看到 user mode 的暫存器是在 user mode 底下，也就是使用以及儲存的記憶體地址為 user page table 的虛擬記憶體地址。而到了要回復 user mode 的暫存器時，這時候也是在 user mode 底下，使用 user page table，因此，我們會需要 trapframe 這個記憶體分頁。

下面我們看回到 user virtual address space

可以看到 user virtual address space 包含text, data (儲存些機器指令, 暫存器資料)... 而在最上方有兩個記憶體分頁，分別為 trapframe, trampoline

trampoline, trapframe page

• trapoline page
  • 包含 uservec 和 userret 程式碼 (組合語言)
  • 對於 user address space 以及 kernel address space，皆映射到相同的記憶體地址，
  • 該分頁可進行讀寫，但不能夠在 user mode 底下存取，
• trapframe page
  • 對於每一個 process，皆有自己的 trapframe page，可以在 process 結構中看見，每一個 proc 都有一個 trapframe 的結構，我們可以通過 proc->trapframe 進行存取。(如果有 64 個 process，意味著我們有 64 個 trapframe page)
  • trapframe page 中儲存了每一個 process 的暫存器內容 (儲存在 trapframe 結構中 reg area 中)

在前面的篇章，我們介紹了 kernel virtual address space 與實體物理記憶體之間的映射關係，在上面我們也看到了 user virtual address space，我們試著將這三者融合，來觀察對應的關係。

先從 kernel page 與實體物理記憶體，觀察 trappoline page

藍色部分為 kernel virtual address space 中 Trapoline page 映射到實體物理記憶體的位置，而 process 的 trapframe 會位於 Physical memory 中，也就是 physical addresses 中 RAM 的區塊，我們可以試著使用下圖表示:

kalloc.c

kalloc.c為負責記憶體管理的檔案。

kalloc()為用於分配記憶體分頁的函式，分配的記憶體區域對應到 kernel virtual address space 為 Free memory，Free memory 中以頁為單位，這一些可以使用的分頁會被放在一個稱為 free list 的單向鏈結串列的結構上。kalloc()從 free list 得到可用的記憶體分頁，kfree()將使用完畢的記憶體分頁重新放回 free list 中。

void freerange(void *pa_start, void *pa_end);

extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}
...

可以看到 kmem 的結構中，有一個 freelist，指向 run，run 則指向下一個節點，因此 freelist 為一單項鍊結串列，而 kmem 中還有一個 lock，為 spinlock。

我們在上方看到 end，end 為 kernel.ld 進行設置的，意義為在 kernel 進行完一些記憶體分配後，第一個可以使用的記憶體地址。

首先在kinit()會先對 lock 進行初始化，包含 name 設置，locked 設置為0等等，接著會執行 freerange()，freerange(start, end)會將 start 到 end 這一段記憶體空間給清空，在kinit()傳入 end 到 PHYSTOP 就是將 end 到 PHYSTOP 這一段記憶體給清空，end為第一個可用的記憶體地址，PHYSTOP為最高的記憶體地址。至於具體如何清空可以看到freerange()

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}

可以看到是在這一段記憶體空間中，按照一個一個分頁，將每一個分頁使用kfree()放回到 free list 中，也就是freerange()將給定的記憶體區段的記憶體分頁全部放回到 free list 中，使他變成可使用的記憶體分頁。

這裡使用到了PGROUNDUP這個巨集，我們可以將巨集展開查看其行為

#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))

發現到這是用於記憶體對齊的巨集，出來的數字會是4096, 8192 等等。

kalloc()

void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

在最一開始會獲得 lock，接著會得到 free list 的第一個節點，如果成功獲得該節點，就改變 free list 的 head 到下一個節點，也就是r->next，接著將 lock 釋放。

獲得節點後，也會將 lock 釋放，這裡使用 lock 是避免兩個 process 或是 thread 存取到同一個節點。接著下方會使用 memset 將分頁的內容覆蓋，接著將 page，也就是節點回傳。

整個kalloc()行為，就是從 free list 拿出可用的記憶體分頁，接著回傳。

kfree()

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

在最一開始的 if 判斷式，會進行給定記憶體分頁記憶體地址的邊界判斷，如果 pa 不在 end ~ PHYSTOP 這一個記憶體區段內，或是沒有記憶體分頁對齊，也就是根據每一個 page 大小進行對齊 (如果有對齊，如4096, 8192，則對4096取餘數，應該都為0)，則會使用 panic() 報錯。

接著我們將該 page 塞滿 1。

下面我們將取得 lock，接著將該記憶體分頁，也就是節點放到 free list 的 head 節點，也就是可使用的記憶體分頁加入到 free list 中，接著將 lock 釋放。

reference

SiFive FU540-C000 Manual v1p0
xv6-riscv
Operating System Concepts, 9/e
RISC-V xv6 Book
Process Table and Process Control Block (PCB)
xv6 Kernel-11: Memory Layout