6011bc7431ef7e156fa3d124296f7c23ebe11484
[akaros.git] / kern / src / pmap.c
1 /* See COPYRIGHT for copyright information. */
2 #ifdef __DEPUTY__
3 #pragma nodeputy
4 #endif
5
6 #include <arch/arch.h>
7 #include <arch/mmu.h>
8
9 #include <ros/error.h>
10
11 #include <atomic.h>
12 #include <string.h>
13 #include <assert.h>
14 #include <pmap.h>
15 #include <kclock.h>
16 #include <process.h>
17 #include <stdio.h>
18
19 //
20 // Allocate n bytes of physical memory aligned on an 
21 // align-byte boundary.  Align must be a power of two.
22 // Return kernel virtual address.  Returned memory is uninitialized.
23 //
24 // If we're out of memory, boot_alloc should panic.
25 // This function may ONLY be used during initialization,
26 // before the page_free_list has been set up.
27 // 
28 void*
29 boot_alloc(uint32_t n, uint32_t align)
30 {
31         extern char end[];
32         void *v;
33
34         // Initialize boot_freemem if this is the first time.
35         // 'end' is a magic symbol automatically generated by the linker,
36         // which points to the end of the kernel's bss segment -
37         // i.e., the first virtual address that the linker
38         // did _not_ assign to any kernel code or global variables.
39         if (boot_freemem == 0)
40                 boot_freemem = end;
41
42         //      Step 1: round boot_freemem up to be aligned properly
43         boot_freemem = ROUNDUP(boot_freemem, align);
44
45         //      Step 2: save current value of boot_freemem as allocated chunk
46         v = boot_freemem;
47         //  Step 2.5: check if we can alloc
48         if (PADDR(boot_freemem + n) > maxaddrpa)
49                 panic("Out of memory in boot alloc, you fool!\n");
50         //      Step 3: increase boot_freemem to record allocation
51         boot_freemem += n;      
52         //      Step 4: return allocated chunk
53         return v;
54 }
55
56 //
57 // Initialize a Page structure.
58 // The result has null links and 0 refcount.
59 // Note that the corresponding physical page is NOT initialized!
60 //
61 static void
62 page_initpp(page_t *pp)
63 {
64         memset(pp, 0, sizeof(*pp));
65 }
66
67 /*
68  * Allocates a physical page.
69  * Does NOT set the contents of the physical page to zero -
70  * the caller must do that if necessary.
71  *
72  * *pp_store   -- is set to point to the Page struct 
73  *                of the newly allocated page
74  *
75  * RETURNS 
76  *   0         -- on success
77  *   -ENOMEM   -- otherwise 
78  */
79 int page_alloc(page_t **pp_store)
80 {
81         if (LIST_EMPTY(&page_free_list))
82                 return -ENOMEM;
83         *pp_store = LIST_FIRST(&page_free_list);
84         LIST_REMOVE(*pp_store, pp_link);
85         page_initpp(*pp_store);
86         return 0;
87 }
88
89 /*
90  * Allocates a specific physical page.
91  * Does NOT set the contents of the physical page to zero -
92  * the caller must do that if necessary.
93  *
94  * *pp_store   -- is set to point to the Page struct 
95  *                of the newly allocated page
96  *
97  * RETURNS 
98  *   0         -- on success
99  *   -ENOMEM   -- otherwise 
100  */
101 int page_alloc_specific(page_t **pp_store, size_t ppn)
102 {
103         page_t* page = ppn2page(ppn);
104         if( page->pp_ref != 0 )
105                 return -ENOMEM;
106         *pp_store = page;
107         LIST_REMOVE(*pp_store, pp_link);
108         page_initpp(*pp_store);
109         return 0;
110 }
111
112 int page_is_free(size_t ppn) {
113         page_t* page = ppn2page(ppn);
114         if( page->pp_ref == 0 )
115                 return TRUE;
116         return FALSE;
117 }
118
119 //
120 // Return a page to the free list.
121 // (This function should only be called when pp->pp_ref reaches 0.)
122 //
123 void page_free(page_t *pp)
124 {
125         // this check allows us to call this on null ptrs, which helps when
126         // allocating and checking for errors on several pages at once
127         if (pp) {
128                 if (pp->pp_ref)
129                         panic("Attempting to free page with non-zero reference count!");
130                 LIST_INSERT_HEAD(&page_free_list, pp, pp_link);
131         }
132 }
133
134 //
135 // Decrement the reference count on a page,
136 // freeing it if there are no more refs.
137 //
138 void
139 page_decref(page_t *pp)
140 {
141         if (--pp->pp_ref == 0)
142                 page_free(pp);
143 }
144
145 //
146 // Map the physical page 'pp' at virtual address 'va'.
147 // The permissions (the low 12 bits) of the page table
148 //  entry should be set to 'perm|PTE_P'.
149 //
150 // Details
151 //   - If there is already a page mapped at 'va', it is page_remove()d.
152 //   - If necessary, on demand, allocates a page table and inserts it into
153 //     'pgdir'.
154 //   - pp->pp_ref should be incremented if the insertion succeeds.
155 //   - The TLB must be invalidated if a page was formerly present at 'va'.
156 //     (this is handled in page_remove)
157 //
158 // RETURNS: 
159 //   0 on success
160 //   -ENOMEM, if page table couldn't be allocated
161 //
162 // Hint: The TA solution is implemented using pgdir_walk, page_remove,
163 // and page2pa.
164 //
165 // No support for jumbos here.  will need to be careful of trying to insert
166 // regular pages into something that was already jumbo, and the overloading
167 // of the PTE_PS and PTE_PAT flags...
168 int
169 page_insert(pde_t *pgdir, page_t *pp, void *va, int perm) 
170 {
171         pte_t* pte = pgdir_walk(pgdir, va, 1);
172         if (!pte)
173                 return -ENOMEM;
174         // need to up the ref count in case pp is already mapped at va
175         // and we don't want to page_remove (which could free pp) and then 
176         // continue as if pp wasn't freed.  moral = up the ref asap
177         pp->pp_ref++;
178         if (*pte & PTE_P) {
179                 page_remove(pgdir, va);
180         }
181         *pte = PTE(page2ppn(pp), PTE_P | perm);
182         return 0;
183 }
184
185 //
186 // Map the physical page 'pp' at the first virtual address that is free 
187 // in the range 'vab' to 'vae'.
188 // The permissions (the low 12 bits) of the page table entry get set to 
189 // 'perm|PTE_P'.
190 //
191 // Details
192 //   - If there is no free entry in the range 'vab' to 'vae' this 
193 //     function returns -ENOMEM.
194 //   - If necessary, on demand, this function will allocate a page table 
195 //     and inserts it into 'pgdir'.
196 //   - pp->pp_ref should be incremented if the insertion succeeds.
197 //
198 // RETURNS: 
199 //   NULL, if no free va in the range (vab, vae) could be found
200 //   va,   the virtual address where pp has been mapped in the 
201 //         range (vab, vae)
202 //
203 void* page_insert_in_range(pde_t *pgdir, page_t *pp, 
204                            void *vab, void *vae, int perm) 
205 {
206         pte_t* pte = NULL;
207         void* new_va;
208         
209         for(new_va = vab; new_va <= vae; new_va+= PGSIZE) {
210                 pte = pgdir_walk(pgdir, new_va, 1);
211                 if(pte != NULL && !(*pte & PTE_P)) break;
212                 else pte = NULL;
213         }
214         if (!pte) return NULL;
215         *pte = page2pa(pp) | PTE_P | perm;
216         return new_va;
217 }
218
219 //
220 // Return the page mapped at virtual address 'va'.
221 // If pte_store is not zero, then we store in it the address
222 // of the pte for this page.  This is used by page_remove
223 // but should not be used by other callers.
224 //
225 // Return 0 if there is no page mapped at va.
226 //
227 // Hint: the TA solution uses pgdir_walk and pa2page.
228 //
229 // For jumbos, right now this returns the first Page* in the 4MB
230 page_t *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
231 {
232         pte_t* pte = pgdir_walk(pgdir, va, 0);
233         if (!pte || !(*pte & PTE_P))
234                 return 0;
235         if (pte_store)
236                 *pte_store = pte;
237         return pa2page(PTE_ADDR(*pte));
238 }
239
240 //
241 // Unmaps the physical page at virtual address 'va'.
242 // If there is no physical page at that address, silently does nothing.
243 //
244 // Details:
245 //   - The ref count on the physical page should decrement.
246 //   - The physical page should be freed if the refcount reaches 0.
247 //   - The pg table entry corresponding to 'va' should be set to 0.
248 //     (if such a PTE exists)
249 //   - The TLB must be invalidated if you remove an entry from
250 //     the pg dir/pg table.
251 //
252 // Hint: The TA solution is implemented using page_lookup,
253 //      tlb_invalidate, and page_decref.
254 //
255 // This may be wonky wrt Jumbo pages and decref.  
256 void
257 page_remove(pde_t *pgdir, void *va)
258 {
259         pte_t* pte;
260         page_t *page;
261         page = page_lookup(pgdir, va, &pte);
262         if (!page)
263                 return;
264         *pte = 0;
265         tlb_invalidate(pgdir, va);
266         page_decref(page);
267 }
268
269 //
270 // Invalidate a TLB entry, but only if the page tables being
271 // edited are the ones currently in use by the processor.
272 //
273 // Need to sort this for cross core lovin'  TODO
274 void
275 tlb_invalidate(pde_t *pgdir, void *va)
276 {
277         // Flush the entry only if we're modifying the current address space.
278         // For now, there is only one address space, so always invalidate.
279         invlpg(va);
280 }
281
282 static void *DANGEROUS user_mem_check_addr;
283
284 //
285 // Check that an environment is allowed to access the range of memory
286 // [va, va+len) with permissions 'perm | PTE_P'.
287 // Normally 'perm' will contain PTE_U at least, but this is not required.
288 // 'va' and 'len' need not be page-aligned; you must test every page that
289 // contains any of that range.  You will test either 'len/PGSIZE',
290 // 'len/PGSIZE + 1', or 'len/PGSIZE + 2' pages.
291 //
292 // A user program can access a virtual address if (1) the address is below
293 // ULIM, and (2) the page table gives it permission.  These are exactly
294 // the tests you should implement here.
295 //
296 // If there is an error, set the 'user_mem_check_addr' variable to the first
297 // erroneous virtual address.
298 //
299 // Returns 0 if the user program can access this range of addresses,
300 // and -EFAULT otherwise.
301 //
302 // Hint: The TA solution uses pgdir_walk.
303 //
304
305 // zra: I've modified the interface to these two functions so that Ivy can
306 // check that user pointers aren't dereferenced. User pointers get the
307 // DANGEROUS qualifier. After validation, these functions return a
308 // COUNT(len) pointer. user_mem_check now returns NULL on error instead of
309 // -EFAULT.
310
311 void *COUNT(len)
312 user_mem_check(env_t *env, const void *DANGEROUS va, size_t len, int perm)
313 {
314         // TODO - will need to sort this out wrt page faulting / PTE_P
315         // also could be issues with sleeping and waking up to find pages
316         // are unmapped, though i think the lab ignores this since the 
317         // kernel is uninterruptible
318         void *DANGEROUS start, *DANGEROUS end;
319         size_t num_pages, i;
320         pte_t *pte;
321
322         perm |= PTE_P;
323         start = ROUNDDOWN((void*)va, PGSIZE);
324         end = ROUNDUP((void*)va + len, PGSIZE);
325         if (start >= end) {
326                 warn("Blimey!  Wrap around in VM range calculation!");  
327                 return NULL;
328         }
329         num_pages = PPN(end - start);
330         for (i = 0; i < num_pages; i++, start += PGSIZE) {
331                 pte = pgdir_walk(env->env_pgdir, start, 0);
332                 // ensures the bits we want on are turned on.  if not, error out
333                 if ( !pte || ((*pte & perm) != perm) ) {
334                         if (i = 0)
335                                 user_mem_check_addr = (void*)va;
336                         else
337                                 user_mem_check_addr = start;
338                         return NULL;
339                 }
340         }
341         // this should never be needed, since the perms should catch it
342         if ((uintptr_t)end > ULIM) {
343                 warn ("I suck - Bug in user permission mappings!");
344                 return NULL;
345         }
346         return (void *COUNT(len))TC(va);
347 }
348
349 //
350 // Checks that environment 'env' is allowed to access the range
351 // of memory [va, va+len) with permissions 'perm | PTE_U'.
352 // If it can, then the function simply returns.
353 // If it cannot, 'env' is destroyed.
354 //
355 void *COUNT(len)
356 user_mem_assert(env_t *env, const void *DANGEROUS va, size_t len, int perm)
357 {
358     void *COUNT(len) res = user_mem_check(env,va,len,perm | PTE_USER_RO);
359         if (!res) {
360                 cprintf("[%08x] user_mem_check assertion failure for "
361                         "va %08x\n", env->env_id, user_mem_check_addr);
362                 proc_destroy(env);      // may not return
363         return NULL;
364         }
365     return res;
366 }
367
368 // copies data from a user buffer to a kernel buffer.
369 // EFAULT if page not present, user lacks perms, or invalid addr.
370 error_t
371 memcpy_from_user(env_t* env, void* COUNT(len) dest,
372                  const void *DANGEROUS va, size_t len)
373 {
374         const void *DANGEROUS start, *DANGEROUS end;
375         size_t num_pages, i;
376         pte_t *pte;
377         uintptr_t perm = PTE_P | PTE_USER_RO;
378         size_t bytes_copied = 0;
379
380         static_assert(ULIM % PGSIZE == 0 && ULIM != 0); // prevent wrap-around
381
382         start = ROUNDDOWN(va, PGSIZE);
383         end = ROUNDUP(va + len, PGSIZE);
384
385         if(start >= (void*SNT)ULIM || end >= (void*SNT)ULIM)
386                 return -EFAULT;
387
388         num_pages = PPN(end - start);
389         for(i = 0; i < num_pages; i++)
390         {
391                 pte = pgdir_walk(env->env_pgdir, start+i*PGSIZE, 0);
392                 if(!pte || (*pte & perm) != perm)
393                         return -EFAULT;
394
395                 void*COUNT(PGSIZE) kpage = KADDR(PTE_ADDR(pte));
396                 void* src_start = i > 0 ? kpage : kpage+(va-start);
397                 void* dst_start = dest+bytes_copied;
398                 size_t copy_len = PGSIZE;
399                 if(i == 0)
400                         copy_len -= va-start;
401                 if(i == num_pages-1)
402                         copy_len -= end-(start+len);
403
404                 memcpy(dst_start,src_start,copy_len);
405                 bytes_copied += copy_len;
406         }
407
408         assert(bytes_copied == len);
409
410         return ESUCCESS;
411 }