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