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