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