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