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