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