Cleaned up issues with PAGE_UNMAPPED and friends
[akaros.git] / kern / src / pmap.c
1 /* See COPYRIGHT for copyright information. */
2
3 /** @file 
4  * This file is responsible for managing physical pages as they 
5  * are mapped into the page tables of a particular virtual address
6  * space.  The functions defined in this file operate on these
7  * page tables to insert and remove physical pages from them at 
8  * particular virtual addresses.
9  *
10  * @author Kevin Klues <klueska@cs.berkeley.edu>
11  * @author Barret Rhoden <brho@cs.berkeley.edu>
12  */
13
14 #ifdef __SHARC__
15 #pragma nosharc
16 #endif
17
18 #ifdef __DEPUTY__
19 #pragma nodeputy
20 #endif
21
22 #include <arch/arch.h>
23 #include <arch/mmu.h>
24
25 #include <error.h>
26
27 #include <kmalloc.h>
28 #include <atomic.h>
29 #include <string.h>
30 #include <assert.h>
31 #include <pmap.h>
32 #include <kclock.h>
33 #include <process.h>
34 #include <stdio.h>
35 #include <mm.h>
36
37 /**
38  * @brief Global variable used to store erroneous virtual addresses as the
39  *        result of a failed user_mem_check().
40  *
41  * zra: What if two checks fail at the same time? Maybe this should be per-cpu?
42  *
43  */
44 static void *DANGEROUS RACY user_mem_check_addr;
45
46 volatile uint32_t vpt_lock = 0;
47 volatile uint32_t vpd_lock = 0;
48
49 /**
50  * @brief Initialize the array of physical pages and memory free list.
51  *
52  * The 'pages' array has one 'page_t' entry per physical page.
53  * Pages are reference counted, and free pages are kept on a linked list.
54  */
55 void page_init(void)
56 {
57         /*
58      * First, make 'pages' point to an array of size 'npages' of
59          * type 'page_t'.
60          * The kernel uses this structure to keep track of physical pages;
61          * 'npages' equals the number of physical pages in memory.
62          * round up to the nearest page
63          */
64         pages = (page_t*)boot_alloc(npages*sizeof(page_t), PGSIZE);
65         memset(pages, 0, npages*sizeof(page_t));
66
67         /*
68      * Then initilaize everything so pages can start to be alloced and freed
69          * from the memory free list
70          */
71         page_alloc_init();
72
73         static_assert(PROCINFO_NUM_PAGES <= PTSIZE);
74         static_assert(PROCDATA_NUM_PAGES <= PTSIZE);
75 }
76
77 /** 
78  * @brief Map the physical page 'pp' into the virtual address 'va' in page
79  *        directory 'pgdir'
80  *
81  * Map the physical page 'pp' at virtual address 'va'.
82  * The permissions (the low 12 bits) of the page table
83  * entry should be set to 'perm|PTE_P'.
84  * 
85  * Details:
86  *   - If there is already a page mapped at 'va', it is page_remove()d.
87  *   - If necessary, on demand, allocates a page table and inserts it into 
88  *     'pgdir'.
89  *   - page_incref() should be called if the insertion succeeds. 
90  *   - The TLB must be invalidated if a page was formerly present at 'va'.
91  *     (this is handled in page_remove)
92  *
93  * No support for jumbos here.  We will need to be careful when trying to
94  * insert regular pages into something that was already jumbo.  We will
95  * also need to be careful with our overloading of the PTE_PS and 
96  * PTE_PAT flags...
97  *
98  * @param[in] pgdir the page directory to insert the page into
99  * @param[in] pp    a pointr to the page struct representing the
100  *                  physical page that should be inserted.
101  * @param[in] va    the virtual address where the page should be
102  *                  inserted.
103  * @param[in] perm  the permition bits with which to set up the 
104  *                  virtual mapping.
105  *
106  * @return ESUCCESS  on success
107  * @return -ENOMEM   if a page table could not be allocated
108  *                   into which the page should be inserted
109  *
110  */
111 int page_insert(pde_t *pgdir, page_t *pp, void *va, int perm) 
112 {
113         pte_t* pte = pgdir_walk(pgdir, va, 1);
114         if (!pte)
115                 return -ENOMEM;
116         // need to up the ref count in case pp is already mapped at va
117         // and we don't want to page_remove (which could free pp) and then 
118         // continue as if pp wasn't freed.  moral = up the ref asap
119         page_incref(pp);
120         /* Careful, page remove handles the cases where the page is PAGED_OUT. */
121         if (!PAGE_UNMAPPED(*pte))
122                 page_remove(pgdir, va);
123         *pte = PTE(page2ppn(pp), PTE_P | perm);
124         return 0;
125 }
126
127 /**
128  * DEPRECATED - this conflicts with VM regions.
129  *
130  * @brief Map the physical page 'pp' at the first virtual address that is free 
131  * in the range 'vab' to 'vae' in page directory 'pgdir'.
132  *
133  * The permissions (the low 12 bits) of the page table entry get set to 
134  * 'perm|PTE_P'.
135  *
136  * Details:
137  *   - If there is no free entry in the range 'vab' to 'vae' this 
138  *     function returns NULL.
139  *   - If necessary, on demand, this function will allocate a page table 
140  *     and inserts it into 'pgdir'.
141  *   - page_incref() will be called if the insertion succeeds.
142  * 
143  * @param[in] pgdir the page directory to insert the page into
144  * @param[in] pp    a pointr to the page struct representing the
145  *                  physical page that should be inserted.
146  * @param[in] vab   the first virtual address in the range in which the 
147  *                  page can be inserted.
148  * @param[in] vae   the last virtual address in the range in which the 
149  *                  page can be inserted.
150  * @param[in] perm  the permition bits with which to set up the 
151  *                  virtual mapping.
152  *
153  * @return VA   the virtual address where pp has been mapped in the 
154  *              range (vab, vae)
155  * @return NULL no free va in the range (vab, vae) could be found
156  */
157 void* page_insert_in_range(pde_t *pgdir, page_t *pp, 
158                            void *vab, void *vae, int perm) 
159 {
160         pte_t* pte = NULL;
161         void*SNT new_va;
162         
163         for(new_va = vab; new_va <= vae; new_va+= PGSIZE) {
164                 pte = pgdir_walk(pgdir, new_va, 1);
165                 if(pte != NULL && PAGE_UNMAPPED(*pte)) break;
166                 else pte = NULL;
167         }
168         if (!pte) return NULL;
169         *pte = page2pa(pp) | PTE_P | perm;
170         return TC(new_va); // trusted because mapping a page is like allocation
171 }
172
173 /**
174  * @brief Return the page mapped at virtual address 'va' in 
175  * page directory 'pgdir'.
176  *
177  * If pte_store is not NULL, then we store in it the address
178  * of the pte for this page.  This is used by page_remove
179  * but should not be used by other callers.
180  *
181  * For jumbos, right now this returns the first Page* in the 4MB range
182  *
183  * @param[in]  pgdir     the page directory from which we should do the lookup
184  * @param[in]  va        the virtual address of the page we are looking up
185  * @param[out] pte_store the address of the page table entry for the returned page
186  *
187  * @return PAGE the page mapped at virtual address 'va'
188  * @return NULL No mapping exists at virtual address 'va', or it's paged out
189  */
190 page_t *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
191 {
192         pte_t* pte = pgdir_walk(pgdir, va, 0);
193         if (!pte || !PAGE_PRESENT(*pte))
194                 return 0;
195         if (pte_store)
196                 *pte_store = pte;
197         return pa2page(PTE_ADDR(*pte));
198 }
199
200 /**
201  * @brief Unmaps the physical page at virtual address 'va' in page directory
202  * 'pgdir'.
203  *
204  * If there is no physical page at that address, this function silently 
205  * does nothing.
206  *
207  * Details:
208  *   - The ref count on the physical page is decrement when the page is removed
209  *   - The physical page is freed if the refcount reaches 0.
210  *   - The pg table entry corresponding to 'va' is set to 0.
211  *     (if such a PTE exists)
212  *   - The TLB is invalidated if an entry is removes from the pg dir/pg table.
213  *
214  * This may be wonky wrt Jumbo pages and decref.  
215  *
216  * @param pgdir the page directory from with the page sholuld be removed
217  * @param va    the virtual address at which the page we are trying to 
218  *              remove is mapped
219  * TODO: consider deprecating this, or at least changing how it works with TLBs.
220  * Might want to have the caller need to manage the TLB.  Also note it is used
221  * in env_user_mem_free, minus the walk. */
222 void page_remove(pde_t *pgdir, void *va)
223 {
224         pte_t *pte;
225         page_t *page;
226
227         pte = pgdir_walk(pgdir,va,0);
228         if (!pte || PAGE_UNMAPPED(*pte))
229                 return;
230
231         if (PAGE_PRESENT(*pte)) {
232                 /* TODO: (TLB) need to do a shootdown, inval sucks.  And might want to
233                  * manage the TLB / free pages differently. (like by the caller).
234                  * Careful about the proc/memory lock here. */
235                 page = ppn2page(PTE2PPN(*pte));
236                 *pte = 0;
237                 tlb_invalidate(pgdir, va);
238                 page_decref(page);
239         } else if (PAGE_PAGED_OUT(*pte)) {
240                 /* TODO: (SWAP) need to free this from the swap */
241                 panic("Swapping not supported!");
242                 *pte = 0;
243         }
244 }
245
246 /**
247  * @brief Invalidate a TLB entry, but only if the page tables being
248  * edited are the ones currently in use by the processor.
249  *
250  * TODO: (TLB) Need to sort this for cross core lovin'
251  *
252  * @param pgdir the page directory assocaited with the tlb entry 
253  *              we are trying to invalidate
254  * @param va    the virtual address associated with the tlb entry
255  *              we are trying to invalidate
256  */
257 void tlb_invalidate(pde_t *pgdir, void *va)
258 {
259         // Flush the entry only if we're modifying the current address space.
260         // For now, there is only one address space, so always invalidate.
261         invlpg(va);
262 }
263
264 /**
265  * @brief Check that an environment is allowed to access the range of memory
266  * [va, va+len) with permissions 'perm | PTE_P'.
267  *
268  * Normally 'perm' will contain PTE_U at least, but this is not required.  The
269  * function get_va_perms only checks for PTE_U, PTE_W, and PTE_P.  It won't
270  * check for things like PTE_PS, PTE_A, etc.
271  * 'va' and 'len' need not be page-aligned;
272  *
273  * A user program can access a virtual address if:
274  *     -# the address is below ULIM
275  *     -# the page table gives it permission.  
276  *
277  * If there is an error, 'user_mem_check_addr' is set to the first
278  * erroneous virtual address.
279  *
280  * @param env  the environment associated with the user program trying to access
281  *             the virtual address range
282  * @param va   the first virtual address in the range
283  * @param len  the length of the virtual address range
284  * @param perm the permissions the user is trying to access the virtual address 
285  *             range with
286  *
287  * @return VA a pointer of type COUNT(len) to the address range
288  * @return NULL trying to access this range of virtual addresses is not allowed
289  */
290 void* user_mem_check(env_t *env, const void *DANGEROUS va, size_t len, int perm)
291 {
292         if (len == 0) {
293                 warn("Called user_mem_check with a len of 0. Don't do that. Returning NULL");
294                 return NULL;
295         }
296         
297         // TODO - will need to sort this out wrt page faulting / PTE_P
298         // also could be issues with sleeping and waking up to find pages
299         // are unmapped, though i think the lab ignores this since the 
300         // kernel is uninterruptible
301         void *DANGEROUS start, *DANGEROUS end;
302         size_t num_pages, i;
303         int page_perms = 0;
304
305         perm |= PTE_P;
306         start = ROUNDDOWN((void*DANGEROUS)va, PGSIZE);
307         end = ROUNDUP((void*DANGEROUS)va + len, PGSIZE);
308         if (start >= end) {
309                 warn("Blimey!  Wrap around in VM range calculation!");  
310                 return NULL;
311         }
312         num_pages = LA2PPN(end - start);
313         for (i = 0; i < num_pages; i++, start += PGSIZE) {
314                 page_perms = get_va_perms(env->env_pgdir, start);
315                 // ensures the bits we want on are turned on.  if not, error out
316                 if ((page_perms & perm) != perm) {
317                         if (i == 0)
318                                 user_mem_check_addr = (void*DANGEROUS)va;
319                         else
320                                 user_mem_check_addr = start;
321                         return NULL;
322                 }
323         }
324         // this should never be needed, since the perms should catch it
325         if ((uintptr_t)end > ULIM) {
326                 warn ("I suck - Bug in user permission mappings!");
327                 return NULL;
328         }
329         return (void *COUNT(len))TC(va);
330 }
331
332 /**
333  * @brief Use the kernel to copy a string from a buffer stored in userspace
334  *        to a buffer stored elsewhere in the address space (potentially in 
335  *        memory only accessible by the kernel)
336  *
337  * @param env  the environment associated with the user program from which
338  *             the string is being copied
339  * @param dst  the destination of the buffer into which the string 
340  *             is being copied
341  * @param va   the start address of the buffer where the string resides
342  * @param len  the length of the buffer 
343  * @param perm the permissions with which the user is trying to access 
344  *             elements of the original buffer 
345  *
346  * @return LEN the length of the new buffer copied into 'dst'
347  */
348 size_t
349 user_mem_strlcpy(env_t *env, char *_dst, const char *DANGEROUS va,
350                  size_t _len, int perm)
351 {
352         const char *DANGEROUS src = va;
353         size_t len = _len;
354         char *NT COUNT(_len-1) dst_in = _dst;
355         char *NT BND(_dst,_dst + _len - 1) dst = _dst;
356
357         if (len > 0) {
358                 while (1) {
359                         char *c;
360                         // what if len was 1?
361                         if (--len <= 0) break;
362                         c = user_mem_check(env, src, 1, perm);
363                         if (!c) break;
364                         if (*c == '\0') break;
365                         // TODO: ivy bitches about this
366                         *dst++ = *c;
367                         src++;
368                 }
369                 *dst = '\0';
370         }
371
372         return dst - dst_in;
373 }
374
375 /**
376  * @brief Checks that environment 'env' is allowed to access the range
377  * of memory [va, va+len) with permissions 'perm | PTE_U'. Destroy 
378  * environment 'env' if the assertion fails.
379  *
380  * This function is identical to user_mem_assert() except that it has a side
381  * affect of destroying the environment 'env' if the memory check fails.
382  *
383  * @param env  the environment associated with the user program trying to access
384  *             the virtual address range
385  * @param va   the first virtual address in the range
386  * @param len  the length of the virtual address range
387  * @param perm the permissions the user is trying to access the virtual address 
388  *             range with
389  *
390  * @return VA a pointer of type COUNT(len) to the address range
391  * @return NULL trying to access this range of virtual addresses is not allowed
392  *              environment 'env' is destroyed
393  */
394 void *
395 user_mem_assert(env_t *env, const void *DANGEROUS va, size_t len, int perm)
396 {
397         if (len == 0) {
398                 warn("Called user_mem_assert with a len of 0. Don't do that. Returning NULL");
399                 return NULL;
400         }
401         
402         void *COUNT(len) res = user_mem_check(env,va,len,perm | PTE_USER_RO);
403         if (!res) {
404                 cprintf("[%08x] user_mem_check assertion failure for "
405                         "va %08x\n", env->pid, user_mem_check_addr);
406                 proc_destroy(env);      // may not return
407         return NULL;
408         }
409     return res;
410 }
411
412 /**
413  * @brief Copies data from a user buffer to a kernel buffer.
414  * 
415  * @param env  the environment associated with the user program
416  *             from which the buffer is being copied
417  * @param dest the destination address of the kernel buffer
418  * @param va   the address of the userspace buffer from which we are copying
419  * @param len  the length of the userspace buffer
420  *
421  * @return ESUCCESS on success
422  * @return -EFAULT  the page assocaited with 'va' is not present, the user 
423  *                  lacks the proper permissions, or there was an invalid 'va'
424  */
425 error_t memcpy_from_user(env_t* env, void* COUNT(len) dest,
426                  const void *DANGEROUS va, size_t len)
427 {
428         const void *DANGEROUS start, *DANGEROUS end;
429         size_t num_pages, i;
430         pte_t *pte;
431         uintptr_t perm = PTE_P | PTE_USER_RO;
432         size_t bytes_copied = 0;
433
434         static_assert(ULIM % PGSIZE == 0 && ULIM != 0); // prevent wrap-around
435
436         start = ROUNDDOWN(va, PGSIZE);
437         end = ROUNDUP(va + len, PGSIZE);
438
439         if(start >= (void*SNT)ULIM || end > (void*SNT)ULIM)
440                 return -EFAULT;
441
442         num_pages = LA2PPN(end - start);
443         for(i = 0; i < num_pages; i++)
444         {
445                 pte = pgdir_walk(env->env_pgdir, start+i*PGSIZE, 0);
446                 if(!pte)
447                         return -EFAULT;
448                 if((*pte & PTE_P) && (*pte & PTE_USER_RO) != PTE_USER_RO)
449                         return -EFAULT;
450                 if(!(*pte & PTE_P))
451                         if(handle_page_fault(env,(uintptr_t)start+i*PGSIZE,PROT_READ))
452                                 return -EFAULT;
453
454                 void*COUNT(PGSIZE) kpage = KADDR(PTE_ADDR(*pte));
455                 const void* src_start = i > 0 ? kpage : kpage+(va-start);
456                 void* dst_start = dest+bytes_copied;
457                 size_t copy_len = PGSIZE;
458                 if(i == 0)
459                         copy_len -= va-start;
460                 if(i == num_pages-1)
461                         copy_len -= end-(va+len);
462
463                 memcpy(dst_start,src_start,copy_len);
464                 bytes_copied += copy_len;
465         }
466
467         assert(bytes_copied == len);
468
469         return ESUCCESS;
470 }
471
472 /**
473  * @brief Copies data to a user buffer from a kernel buffer.
474  * 
475  * @param env  the environment associated with the user program
476  *             to which the buffer is being copied
477  * @param dest the destination address of the user buffer
478  * @param va   the address of the kernel buffer from which we are copying
479  * @param len  the length of the user buffer
480  *
481  * @return ESUCCESS on success
482  * @return -EFAULT  the page assocaited with 'va' is not present, the user 
483  *                  lacks the proper permissions, or there was an invalid 'va'
484  */
485 error_t memcpy_to_user(env_t* env, void*DANGEROUS va,
486                  const void *COUNT(len) src, size_t len)
487 {
488         const void *DANGEROUS start, *DANGEROUS end;
489         size_t num_pages, i;
490         pte_t *pte;
491         uintptr_t perm = PTE_P | PTE_USER_RW;
492         size_t bytes_copied = 0;
493
494         static_assert(ULIM % PGSIZE == 0 && ULIM != 0); // prevent wrap-around
495
496         start = ROUNDDOWN(va, PGSIZE);
497         end = ROUNDUP(va + len, PGSIZE);
498
499         if(start >= (void*SNT)ULIM || end > (void*SNT)ULIM)
500                 return -EFAULT;
501
502         num_pages = LA2PPN(end - start);
503         for(i = 0; i < num_pages; i++)
504         {
505                 pte = pgdir_walk(env->env_pgdir, start+i*PGSIZE, 0);
506                 if(!pte)
507                         return -EFAULT;
508                 if((*pte & PTE_P) && (*pte & PTE_USER_RW) != PTE_USER_RW)
509                         return -EFAULT;
510                 if(!(*pte & PTE_P))
511                         if(handle_page_fault(env,(uintptr_t)start+i*PGSIZE,PROT_WRITE))
512                                 return -EFAULT;
513
514                 void*COUNT(PGSIZE) kpage = KADDR(PTE_ADDR(*pte));
515                 void* dst_start = i > 0 ? kpage : kpage+(va-start);
516                 const void* src_start = src+bytes_copied;
517                 size_t copy_len = PGSIZE;
518                 if(i == 0)
519                         copy_len -= va-start;
520                 if(i == num_pages-1)
521                         copy_len -= end-(va+len);
522
523                 memcpy(dst_start,src_start,copy_len);
524                 bytes_copied += copy_len;
525         }
526
527         assert(bytes_copied == len);
528
529         return ESUCCESS;
530 }