root/kernel/vm.c

DEFINITIONS

1. kvmmake
2. kvmmap
3. kvminit
4. kvminithart
5. walk
6. walkaddr
7. mappages
8. uvmcreate
9. uvmunmap
10. uvmalloc
11. uvmdealloc
12. freewalk
13. uvmfree
14. uvmcopy
15. uvmclear
16. copyout
17. copyin
18. copyinstr
19. vmfault
20. ismapped

   1 #include "param.h"
   2 #include "types.h"
   3 #include "memlayout.h"
   4 #include "elf.h"
   5 #include "riscv.h"
   6 #include "defs.h"
   7 #include "spinlock.h"
   8 #include "proc.h"
   9 #include "fs.h"
  10 
  11 /*
  12  * the kernel's page table.
  13  */
  14 pagetable_t kernel_pagetable;
  15 
  16 extern char etext[];  // kernel.ld sets this to end of kernel code.
  17 
  18 extern char trampoline[]; // trampoline.S
  19 
  20 // Make a direct-map page table for the kernel.
  21 pagetable_t
  22 kvmmake(void)
  23 {
  24   pagetable_t kpgtbl;
  25 
  26   kpgtbl = (pagetable_t) kalloc();
  27   memset(kpgtbl, 0, PGSIZE);
  28 
  29   // uart registers
  30   kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);
  31 
  32   // virtio mmio disk interface
  33   kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
  34 
  35   // PLIC
  36   kvmmap(kpgtbl, PLIC, PLIC, 0x4000000, PTE_R | PTE_W);
  37 
  38   // map kernel text executable and read-only.
  39   kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
  40 
  41   // map kernel data and the physical RAM we'll make use of.
  42   kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
  43 
  44   // map the trampoline for trap entry/exit to
  45   // the highest virtual address in the kernel.
  46   kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  47 
  48   // allocate and map a kernel stack for each process.
  49   proc_mapstacks(kpgtbl);
  50   
  51   return kpgtbl;
  52 }
  53 
  54 // add a mapping to the kernel page table.
  55 // only used when booting.
  56 // does not flush TLB or enable paging.
  57 void
  58 kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
  59 {
  60   if(mappages(kpgtbl, va, sz, pa, perm) != 0)
  61     panic("kvmmap");
  62 }
  63 
  64 // Initialize the kernel_pagetable, shared by all CPUs.
  65 void
  66 kvminit(void)
  67 {
  68   kernel_pagetable = kvmmake();
  69 }
  70 
  71 // Switch the current CPU's h/w page table register to
  72 // the kernel's page table, and enable paging.
  73 void
  74 kvminithart()
  75 {
  76   // wait for any previous writes to the page table memory to finish.
  77   sfence_vma();
  78 
  79   w_satp(MAKE_SATP(kernel_pagetable));
  80 
  81   // flush stale entries from the TLB.
  82   sfence_vma();
  83 }
  84 
  85 // Return the address of the PTE in page table pagetable
  86 // that corresponds to virtual address va.  If alloc!=0,
  87 // create any required page-table pages.
  88 //
  89 // The risc-v Sv39 scheme has three levels of page-table
  90 // pages. A page-table page contains 512 64-bit PTEs.
  91 // A 64-bit virtual address is split into five fields:
  92 //   39..63 -- must be zero.
  93 //   30..38 -- 9 bits of level-2 index.
  94 //   21..29 -- 9 bits of level-1 index.
  95 //   12..20 -- 9 bits of level-0 index.
  96 //    0..11 -- 12 bits of byte offset within the page.
  97 pte_t *
  98 walk(pagetable_t pagetable, uint64 va, int alloc)
  99 {
 100   if(va >= MAXVA)
 101     panic("walk");
 102 
 103   for(int level = 2; level > 0; level--) {
 104     pte_t *pte = &pagetable[PX(level, va)];
 105     if(*pte & PTE_V) {
 106       pagetable = (pagetable_t)PTE2PA(*pte);
 107     } else {
 108       if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
 109         return 0;
 110       memset(pagetable, 0, PGSIZE);
 111       *pte = PA2PTE(pagetable) | PTE_V;
 112     }
 113   }
 114   return &pagetable[PX(0, va)];
 115 }
 116 
 117 // Look up a virtual address, return the physical address,
 118 // or 0 if not mapped.
 119 // Can only be used to look up user pages.
 120 uint64
 121 walkaddr(pagetable_t pagetable, uint64 va)
 122 {
 123   pte_t *pte;
 124   uint64 pa;
 125 
 126   if(va >= MAXVA)
 127     return 0;
 128 
 129   pte = walk(pagetable, va, 0);
 130   if(pte == 0)
 131     return 0;
 132   if((*pte & PTE_V) == 0)
 133     return 0;
 134   if((*pte & PTE_U) == 0)
 135     return 0;
 136   pa = PTE2PA(*pte);
 137   return pa;
 138 }
 139 
 140 // Create PTEs for virtual addresses starting at va that refer to
 141 // physical addresses starting at pa.
 142 // va and size MUST be page-aligned.
 143 // Returns 0 on success, -1 if walk() couldn't
 144 // allocate a needed page-table page.
 145 int
 146 mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
 147 {
 148   uint64 a, last;
 149   pte_t *pte;
 150 
 151   if((va % PGSIZE) != 0)
 152     panic("mappages: va not aligned");
 153 
 154   if((size % PGSIZE) != 0)
 155     panic("mappages: size not aligned");
 156 
 157   if(size == 0)
 158     panic("mappages: size");
 159   
 160   a = va;
 161   last = va + size - PGSIZE;
 162   for(;;){
 163     if((pte = walk(pagetable, a, 1)) == 0)
 164       return -1;
 165     if(*pte & PTE_V)
 166       panic("mappages: remap");
 167     *pte = PA2PTE(pa) | perm | PTE_V;
 168     if(a == last)
 169       break;
 170     a += PGSIZE;
 171     pa += PGSIZE;
 172   }
 173   return 0;
 174 }
 175 
 176 // create an empty user page table.
 177 // returns 0 if out of memory.
 178 pagetable_t
 179 uvmcreate()
 180 {
 181   pagetable_t pagetable;
 182   pagetable = (pagetable_t) kalloc();
 183   if(pagetable == 0)
 184     return 0;
 185   memset(pagetable, 0, PGSIZE);
 186   return pagetable;
 187 }
 188 
 189 // Remove npages of mappings starting from va. va must be
 190 // page-aligned. It's OK if the mappings don't exist.
 191 // Optionally free the physical memory.
 192 void
 193 uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
 194 {
 195   uint64 a;
 196   pte_t *pte;
 197 
 198   if((va % PGSIZE) != 0)
 199     panic("uvmunmap: not aligned");
 200 
 201   for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
 202     if((pte = walk(pagetable, a, 0)) == 0) // leaf page table entry allocated?
 203       continue;   
 204     if((*pte & PTE_V) == 0)  // has physical page been allocated?
 205       continue;
 206     if(do_free){
 207       uint64 pa = PTE2PA(*pte);
 208       kfree((void*)pa);
 209     }
 210     *pte = 0;
 211   }
 212 }
 213 
 214 // Allocate PTEs and physical memory to grow a process from oldsz to
 215 // newsz, which need not be page aligned.  Returns new size or 0 on error.
 216 uint64
 217 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
 218 {
 219   char *mem;
 220   uint64 a;
 221 
 222   if(newsz < oldsz)
 223     return oldsz;
 224 
 225   oldsz = PGROUNDUP(oldsz);
 226   for(a = oldsz; a < newsz; a += PGSIZE){
 227     mem = kalloc();
 228     if(mem == 0){
 229       uvmdealloc(pagetable, a, oldsz);
 230       return 0;
 231     }
 232     memset(mem, 0, PGSIZE);
 233     if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
 234       kfree(mem);
 235       uvmdealloc(pagetable, a, oldsz);
 236       return 0;
 237     }
 238   }
 239   return newsz;
 240 }
 241 
 242 // Deallocate user pages to bring the process size from oldsz to
 243 // newsz.  oldsz and newsz need not be page-aligned, nor does newsz
 244 // need to be less than oldsz.  oldsz can be larger than the actual
 245 // process size.  Returns the new process size.
 246 uint64
 247 uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
 248 {
 249   if(newsz >= oldsz)
 250     return oldsz;
 251 
 252   if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
 253     int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
 254     uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
 255   }
 256 
 257   return newsz;
 258 }
 259 
 260 // Recursively free page-table pages.
 261 // All leaf mappings must already have been removed.
 262 void
 263 freewalk(pagetable_t pagetable)
 264 {
 265   // there are 2^9 = 512 PTEs in a page table.
 266   for(int i = 0; i < 512; i++){
 267     pte_t pte = pagetable[i];
 268     if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
 269       // this PTE points to a lower-level page table.
 270       uint64 child = PTE2PA(pte);
 271       freewalk((pagetable_t)child);
 272       pagetable[i] = 0;
 273     } else if(pte & PTE_V){
 274       panic("freewalk: leaf");
 275     }
 276   }
 277   kfree((void*)pagetable);
 278 }
 279 
 280 // Free user memory pages,
 281 // then free page-table pages.
 282 void
 283 uvmfree(pagetable_t pagetable, uint64 sz)
 284 {
 285   if(sz > 0)
 286     uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);
 287   freewalk(pagetable);
 288 }
 289 
 290 // Given a parent process's page table, copy
 291 // its memory into a child's page table.
 292 // Copies both the page table and the
 293 // physical memory.
 294 // returns 0 on success, -1 on failure.
 295 // frees any allocated pages on failure.
 296 int
 297 uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
 298 {
 299   pte_t *pte;
 300   uint64 pa, i;
 301   uint flags;
 302   char *mem;
 303 
 304   for(i = 0; i < sz; i += PGSIZE){
 305     if((pte = walk(old, i, 0)) == 0)
 306       continue;   // page table entry hasn't been allocated
 307     if((*pte & PTE_V) == 0)
 308       continue;   // physical page hasn't been allocated
 309     pa = PTE2PA(*pte);
 310     flags = PTE_FLAGS(*pte);
 311     if((mem = kalloc()) == 0)
 312       goto err;
 313     memmove(mem, (char*)pa, PGSIZE);
 314     if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
 315       kfree(mem);
 316       goto err;
 317     }
 318   }
 319   return 0;
 320 
 321  err:
 322   uvmunmap(new, 0, i / PGSIZE, 1);
 323   return -1;
 324 }
 325 
 326 // mark a PTE invalid for user access.
 327 // used by exec for the user stack guard page.
 328 void
 329 uvmclear(pagetable_t pagetable, uint64 va)
 330 {
 331   pte_t *pte;
 332   
 333   pte = walk(pagetable, va, 0);
 334   if(pte == 0)
 335     panic("uvmclear");
 336   *pte &= ~PTE_U;
 337 }
 338 
 339 // Copy from kernel to user.
 340 // Copy len bytes from src to virtual address dstva in a given page table.
 341 // Return 0 on success, -1 on error.
 342 int
 343 copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
 344 {
 345   uint64 n, va0, pa0;
 346   pte_t *pte;
 347 
 348   while(len > 0){
 349     va0 = PGROUNDDOWN(dstva);
 350     if(va0 >= MAXVA)
 351       return -1;
 352   
 353     pa0 = walkaddr(pagetable, va0);
 354     if(pa0 == 0) {
 355       if((pa0 = vmfault(pagetable, va0, 0)) == 0) {
 356         return -1;
 357       }
 358     }
 359 
 360     pte = walk(pagetable, va0, 0);
 361     // forbid copyout over read-only user text pages.
 362     if((*pte & PTE_W) == 0)
 363       return -1;
 364       
 365     n = PGSIZE - (dstva - va0);
 366     if(n > len)
 367       n = len;
 368     memmove((void *)(pa0 + (dstva - va0)), src, n);
 369 
 370     len -= n;
 371     src += n;
 372     dstva = va0 + PGSIZE;
 373   }
 374   return 0;
 375 }
 376 
 377 // Copy from user to kernel.
 378 // Copy len bytes to dst from virtual address srcva in a given page table.
 379 // Return 0 on success, -1 on error.
 380 int
 381 copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
 382 {
 383   uint64 n, va0, pa0;
 384 
 385   while(len > 0){
 386     va0 = PGROUNDDOWN(srcva);
 387     pa0 = walkaddr(pagetable, va0);
 388     if(pa0 == 0) {
 389       if((pa0 = vmfault(pagetable, va0, 0)) == 0) {
 390         return -1;
 391       }
 392     }
 393     n = PGSIZE - (srcva - va0);
 394     if(n > len)
 395       n = len;
 396     memmove(dst, (void *)(pa0 + (srcva - va0)), n);
 397 
 398     len -= n;
 399     dst += n;
 400     srcva = va0 + PGSIZE;
 401   }
 402   return 0;
 403 }
 404 
 405 // Copy a null-terminated string from user to kernel.
 406 // Copy bytes to dst from virtual address srcva in a given page table,
 407 // until a '\0', or max.
 408 // Return 0 on success, -1 on error.
 409 int
 410 copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
 411 {
 412   uint64 n, va0, pa0;
 413   int got_null = 0;
 414 
 415   while(got_null == 0 && max > 0){
 416     va0 = PGROUNDDOWN(srcva);
 417     pa0 = walkaddr(pagetable, va0);
 418     if(pa0 == 0)
 419       return -1;
 420     n = PGSIZE - (srcva - va0);
 421     if(n > max)
 422       n = max;
 423 
 424     char *p = (char *) (pa0 + (srcva - va0));
 425     while(n > 0){
 426       if(*p == '\0'){
 427         *dst = '\0';
 428         got_null = 1;
 429         break;
 430       } else {
 431         *dst = *p;
 432       }
 433       --n;
 434       --max;
 435       p++;
 436       dst++;
 437     }
 438 
 439     srcva = va0 + PGSIZE;
 440   }
 441   if(got_null){
 442     return 0;
 443   } else {
 444     return -1;
 445   }
 446 }
 447 
 448 // allocate and map user memory if process is referencing a page
 449 // that was lazily allocated in sys_sbrk().
 450 // returns 0 if va is invalid or already mapped, or if
 451 // out of physical memory, and physical address if successful.
 452 uint64
 453 vmfault(pagetable_t pagetable, uint64 va, int read)
 454 {
 455   uint64 mem;
 456   struct proc *p = myproc();
 457 
 458   if (va >= p->sz)
 459     return 0;
 460   va = PGROUNDDOWN(va);
 461   if(ismapped(pagetable, va)) {
 462     return 0;
 463   }
 464   mem = (uint64) kalloc();
 465   if(mem == 0)
 466     return 0;
 467   memset((void *) mem, 0, PGSIZE);
 468   if (mappages(p->pagetable, va, PGSIZE, mem, PTE_W|PTE_U|PTE_R) != 0) {
 469     kfree((void *)mem);
 470     return 0;
 471   }
 472   return mem;
 473 }
 474 
 475 int
 476 ismapped(pagetable_t pagetable, uint64 va)
 477 {
 478   pte_t *pte = walk(pagetable, va, 0);
 479   if (pte == 0) {
 480     return 0;
 481   }
 482   if (*pte & PTE_V){
 483     return 1;
 484   }
 485   return 0;
 486 }