a4e1a8684805ee3121c8e1ba3f0cf4736e69e640
[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 <env.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 // Return the page mapped at virtual address 'va'.
186 // If pte_store is not zero, then we store in it the address
187 // of the pte for this page.  This is used by page_remove
188 // but should not be used by other callers.
189 //
190 // Return 0 if there is no page mapped at va.
191 //
192 // Hint: the TA solution uses pgdir_walk and pa2page.
193 //
194 // For jumbos, right now this returns the first Page* in the 4MB
195 page_t *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
196 {
197         pte_t* pte = pgdir_walk(pgdir, va, 0);
198         if (!pte || !(*pte & PTE_P))
199                 return 0;
200         if (pte_store)
201                 *pte_store = pte;
202         return pa2page(PTE_ADDR(*pte));
203 }
204
205 //
206 // Unmaps the physical page at virtual address 'va'.
207 // If there is no physical page at that address, silently does nothing.
208 //
209 // Details:
210 //   - The ref count on the physical page should decrement.
211 //   - The physical page should be freed if the refcount reaches 0.
212 //   - The pg table entry corresponding to 'va' should be set to 0.
213 //     (if such a PTE exists)
214 //   - The TLB must be invalidated if you remove an entry from
215 //     the pg dir/pg table.
216 //
217 // Hint: The TA solution is implemented using page_lookup,
218 //      tlb_invalidate, and page_decref.
219 //
220 // This may be wonky wrt Jumbo pages and decref.  
221 void
222 page_remove(pde_t *pgdir, void *va)
223 {
224         pte_t* pte;
225         page_t *page;
226         page = page_lookup(pgdir, va, &pte);
227         if (!page)
228                 return;
229         *pte = 0;
230         tlb_invalidate(pgdir, va);
231         page_decref(page);
232 }
233
234 //
235 // Invalidate a TLB entry, but only if the page tables being
236 // edited are the ones currently in use by the processor.
237 //
238 // Need to sort this for cross core lovin'  TODO
239 void
240 tlb_invalidate(pde_t *pgdir, void *va)
241 {
242         // Flush the entry only if we're modifying the current address space.
243         // For now, there is only one address space, so always invalidate.
244         invlpg(va);
245 }
246
247 static void *DANGEROUS user_mem_check_addr;
248
249 //
250 // Check that an environment is allowed to access the range of memory
251 // [va, va+len) with permissions 'perm | PTE_P'.
252 // Normally 'perm' will contain PTE_U at least, but this is not required.
253 // 'va' and 'len' need not be page-aligned; you must test every page that
254 // contains any of that range.  You will test either 'len/PGSIZE',
255 // 'len/PGSIZE + 1', or 'len/PGSIZE + 2' pages.
256 //
257 // A user program can access a virtual address if (1) the address is below
258 // ULIM, and (2) the page table gives it permission.  These are exactly
259 // the tests you should implement here.
260 //
261 // If there is an error, set the 'user_mem_check_addr' variable to the first
262 // erroneous virtual address.
263 //
264 // Returns 0 if the user program can access this range of addresses,
265 // and -E_FAULT otherwise.
266 //
267 // Hint: The TA solution uses pgdir_walk.
268 //
269
270 // zra: I've modified the interface to these two functions so that Ivy can
271 // check that user pointers aren't dereferenced. User pointers get the
272 // DANGEROUS qualifier. After validation, these functions return a
273 // COUNT(len) pointer. user_mem_check now returns NULL on error instead of
274 // -EFAULT.
275
276 void *COUNT(len)
277 user_mem_check(env_t *env, const void *DANGEROUS va, size_t len, int perm)
278 {
279         // TODO - will need to sort this out wrt page faulting / PTE_P
280         // also could be issues with sleeping and waking up to find pages
281         // are unmapped, though i think the lab ignores this since the 
282         // kernel is uninterruptible
283         void *DANGEROUS start, *DANGEROUS end;
284         size_t num_pages, i;
285         pte_t *pte;
286
287         perm |= PTE_P;
288         start = ROUNDDOWN((void*)va, PGSIZE);
289         end = ROUNDUP((void*)va + len, PGSIZE);
290         if (start >= end) {
291                 warn("Blimey!  Wrap around in VM range calculation!");  
292                 return NULL;
293         }
294         num_pages = PPN(end - start);
295         for (i = 0; i < num_pages; i++, start += PGSIZE) {
296                 pte = pgdir_walk(env->env_pgdir, start, 0);
297                 // ensures the bits we want on are turned on.  if not, error out
298                 if ( !pte || ((*pte & perm) != perm) ) {
299                         if (i = 0)
300                                 user_mem_check_addr = (void*)va;
301                         else
302                                 user_mem_check_addr = start;
303                         return NULL;
304                 }
305         }
306         // this should never be needed, since the perms should catch it
307         if ((uintptr_t)end > ULIM) {
308                 warn ("I suck - Bug in user permission mappings!");
309                 return NULL;
310         }
311         return (void *COUNT(len))TC(va);
312 }
313
314 //
315 // Checks that environment 'env' is allowed to access the range
316 // of memory [va, va+len) with permissions 'perm | PTE_U'.
317 // If it can, then the function simply returns.
318 // If it cannot, 'env' is destroyed.
319 //
320 void *COUNT(len)
321 user_mem_assert(env_t *env, const void *DANGEROUS va, size_t len, int perm)
322 {
323     void *COUNT(len) res = user_mem_check(env,va,len,perm | PTE_USER_RO);
324         if (!res) {
325                 cprintf("[%08x] user_mem_check assertion failure for "
326                         "va %08x\n", env->env_id, user_mem_check_addr);
327                 env_destroy(env);       // may not return
328         return NULL;
329         }
330     return res;
331 }
332
333 // copies data from a user buffer to a kernel buffer.
334 // EFAULT if page not present, user lacks perms, or invalid addr.
335 error_t
336 memcpy_from_user(env_t* env, void* COUNT(len) dest,
337                  const void *DANGEROUS va, size_t len)
338 {
339         void *DANGEROUS start, *DANGEROUS end;
340         size_t num_pages, i;
341         pte_t *pte;
342         uintptr_t perm = PTE_P | PTE_USER_RO;
343         size_t bytes_copied = 0;
344
345         static_assert(ULIM % PGSIZE == 0 && ULIM != 0); // prevent wrap-around
346
347         start = ROUNDDOWN(va, PGSIZE);
348         end = ROUNDUP(va + len, PGSIZE);
349
350         if(start >= (void*SNT)ULIM || end >= (void*SNT)ULIM)
351                 return -EFAULT;
352
353         num_pages = PPN(end - start);
354         for(i = 0; i < num_pages; i++)
355         {
356                 pte = pgdir_walk(env->env_pgdir, start+i*PGSIZE, 0);
357                 if(!pte || (*pte & perm) != perm)
358                         return -EFAULT;
359
360                 void*COUNT(PGSIZE) kpage = KADDR(PTE_ADDR(pte));
361                 void* src_start = i > 0 ? kpage : kpage+(va-start);
362                 void* dst_start = dest+bytes_copied;
363                 size_t copy_len = PGSIZE;
364                 if(i == 0)
365                         copy_len -= va-start;
366                 if(i == num_pages-1)
367                         copy_len -= end-(start+len);
368
369                 memcpy(dst_start,src_start,copy_len);
370                 bytes_copied += copy_len;
371         }
372
373         assert(bytes_copied == len);
374
375         return ESUCCESS;
376 }