OS homework1

• 四資工三 B10415002 余福浩

CH2 Page Table

page-table的技術：

1. mapping the same memory (the kernel) in several address spaces
2. mapping the same memory more than once in one address space (each user page is also mapped into the kernel’s physical view of memory)
3. guarding a user stack with an unmapped page

Paging hardware

• x86的page table hardware負責將每個虛擬記憶體(virtual address)對應到實體記憶體(physical address)

• 每個x86的page table都是邏輯上的陣列，其中包含 2²⁰ (1,048,576) 的 page table entries (PTEs)

• 而每個PTE包含20 bits的physical page number (PPN) 和 12 bits的flags

  • 12 bits flags包含：
    • P(1 bit):Present
    • W(1 bit):Writable
    • U(1 bit):User
    • WT(1 bit):1=Write-through, 0=Write-back
    • CD(1 bit):Cache Disabled
    • A(1 bit):Accessed
    • D(1 bit):Dirty (0 in page directory)
    • AVL(3 bits):Available for system use
    • 其中有2 bits未使用到
    • FIG:
    • 
  • 對應的程式碼定義如下：
  • 

• page table存在physical memory中的方式為two-level tree

  1. 第一層：4096 bytes的page directory，包含了 1024個 PTE-like references(每個4 bytes) 可對照到page table pages.
  2. 第二層：每個page table中有1024個4 bytes(32 bits)的PTE

• paging hardware轉換virtual address的步驟為：

  • virtual address共32bits： [31:0]
    
  1. 先利用virtual address前20 bits([31:12])找到所對應的PTE
  2. PTE中的前20 bits(即PPN[31:12]) + virtual address的後12 bits(([11:0]))
     • [31:22]bit:可到page directory找到對應PTE所在的page table references
     • [21:12]bit:可在對應出的page table中找到該PTE
  3. 即可組合出對應到的實體記憶體(Physical Address)

Process address space

• process可使用的virtual address：0~KERNBASE
• 以下是一些相關的macro定義：

0201 // Memory layout
0202 #define EXTMEM 0x100000 // Start of extended memory
0203 #define PHYSTOP 0xE000000 // Top physical memory
0204 #define DEVSPACE 0xFE000000 // Other devices are at high addresses
0205
0206 // Key addresses for address space layout (see kmap in vm.c for layout)
0207 #define KERNBASE 0x80000000 // First kernel virtual address
0208 #define KERNLINK (KERNBASE+EXTMEM) // Address where kernel is linked
0209
0210 #define V2P(a) (((uint) (a)) − KERNBASE)
0211 #define P2V(a) (((void *) (a)) + KERNBASE) 
0212
0213 #define V2P_WO(x) ((x) − KERNBASE) // same as V2P, but without casts
0214 #define P2V_WO(x) ((x) + KERNBASE) // same as P2V, but without casts

• 將virtual addresses KERNBASE:KERNBASE+PHYSTOP map 到 0:PHYSTOP
  • 實作方面，利用上面程式碼定義的 V2P(a)和P2V(a) 來進行virtual addresse和Physical Address的轉換
  • KERNBASE是0x80000000
  • Virtual → Physical：V2P(a) (((uint) (a)) − KERNBASE)
  • Physical → Virtual：P2V(a) (((void *) (a)) + KERNBASE)
    

Code: creating an address space

• main 會call kvmalloc (1840) 去 create and switch page table with the mappings above KERNBASE required for the kernel to run

// Set up kernel part of a page table.
pde_t* setupkvm(void)
{
pde_t *pgdir;
struct kmap
*k;
if((pgdir = return 0;
(pde_t*)kalloc()) == 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 − (uint)k−>phys_start, k−>perm)
k−>phys_start, < 0) {
freevm(pgdir);
return 0; }
return pgdir; 
}
// Allocate one page table for the machine for the kernel address 
// space for scheduler processes.
void kvmalloc(void)
{
kpgdir = setupkvm(); switchkvm();
}

• Rmk: pde_t和pte_t都是uint

  0103 typedef uint pde_t;
  //...
  0848 typedef uint pte_t;
  

• it calls mappages to install the translations that the kernel needs, which are described in the kmap (1809) array.
• mappages installs mappings into a page table for a range of virtual addresses to a corresponding range of physical addresses.

1756 // Create PTEs for virtual addresses starting at va that refer to 1757 // physical addresses starting at pa. va and size might not
1758 // be page−aligned.
1759 static int
1760 mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm) 1761 {
1762 char *a, *last;
1763 pte_t *pte;
1764
1765 a = (char*)PGROUNDDOWN((uint)va);
1766 last = (char*)PGROUNDDOWN(((uint)va) + size − 1);
1767 for(;;){
1768 if((pte = walkpgdir(pgdir, a, 1)) == 0)
1769 return −1;
1770 if(*pte & PTE_P)
1771 panic("remap");
1772 *pte = pa | perm | PTE_P;
1773 if(a == last)
1774 break;
1775 a += PGSIZE;
1776 pa += PGSIZE;
1777 }
1778 return 0;
1779 }

• walkpgdir使用virtual address的最前 10 bits 尋找對應的PDE(page directory entry)，在用接下來的10 bits找到PTE
  
  

Physical memory allocation

• kernel 必須負責 allocate and free physical memory at run-time
• Allocation的作法為從linked list removing一個page
• freeing 的作法為adding一個freed page 到list中

Code: Physical memory allocator

• allocator’s data structure is a free list of physical memory pages that are available for allocation
  • struct run結構用來產生一個linked list
    
    
• main calls kinit1 and kinit2 to initialize the allocator (3131).
• kinit1 and kinit2 call freerange to add memory to the free list via perpage calls to kfree
  • 
  • main程式片段：
  • 
• kfree (3164) 會把每個要free的byte 設成 1
• kfree 會將 v 轉型成 (struct run *)，將freelist串到r->next，並將freelist放到r，再更新到kmem.freelist
• 

程式流程

User part of an address space

• 上圖為一個執行中的process的memory(start at 0)
• 當process 呼叫 sbrk function時，可以增加頂端的heap
• text、data和stack區段的記憶體是連續存放的，但heap不是，heap可以使用任意的free physical page，搭配一個virtual page就可以相互對照
• stack區段有一個單獨的page，包含了argc和argv(如圖)

Code: sbrk

• Sbrk是一個system call，能讓process增加、縮小自己的的memory

  • 
  • 
  • 利用下對照表進入到sys_sbrk
  • 
  • 

• Sbrk主要以growproc(2558)來實作

  • 如果n>0，會allocate physical pages並將他map 到process’s address space頂端
  • 如果n<0，會deallocate unmap process’s address space中的page，並將對應的 physical pages釋放掉
  • 
  • 其中的allocuvm和deallocuvm:
    • 
    • 

• x86中在Translation Look-aside Buffer (TLB) caches PTEs，當page table改變時必須將cache的entry無效化

程式流程

Code: exec

• Exec是用來creates the user part of an address space的system call
• Exec (6610) opens the named binary path using namei (6623)
  • 
  • 
  • 其中namei為：
    • 
• 他會讀取ELF檔的header
  • Xv6用widely-used ELF format來描述
  • 相關的資料結構定義如下：
  • struct elfhdr:
  • 
  • struct proghdr:
  • 
• 步驟：
  • 1.確認header檔elf.magic必須= ELF_MAGIC，否則失敗
    • 因為ELF binary標頭的開頭為4 bytes的 magic number(0x7F, ’E’, ’L’, ’F’)
    • 定義在ELF_MAGIC上(需轉為little endian)

    •   #define ELF_MAGIC 0x464C457FU // "\x7FELF" in little endian
      

  • 2.讀取program到 memory
  • 3.allocates 新的 page table with no user mappings with setupkvm (6637)
  • 4.allocates memory for each ELF segment with allocuvm (6651) 和 loads each segment into memory with loaduvm (6655).
• 程式的header區段 /init是由第一個使用exec的使用者創造的
• exec會allocates、initializes user stack，並複製argument strings進去，以 null做結束，在依序由上而下放上argv、argc、return PC
• 不可被access的page會放到 stack page之後
• exec遇到錯誤會跳出bad label

程式流程