675f195a11eed1e0a5e68087e78f111d3a55df6f
[akaros.git] / kern / src / mm.c
1 /*
2  * Copyright (c) 2009 The Regents of the University of California
3  * Barret Rhoden <brho@cs.berkeley.edu>
4  * See LICENSE for details.
5  *
6  */
7
8 #include <frontend.h>
9 #include <ros/common.h>
10 #include <ros/mman.h>
11 #include <pmap.h>
12 #include <mm.h>
13 #include <process.h>
14 #include <stdio.h>
15 #include <syscall.h>
16 #include <slab.h>
17 #include <kmalloc.h>
18 #include <vfs.h>
19
20 struct kmem_cache *vmr_kcache;
21 struct kmem_cache *pfault_info_cache;
22
23 void vmr_init(void)
24 {
25         vmr_kcache = kmem_cache_create("vm_regions", sizeof(struct vm_region),
26                                        __alignof__(struct dentry), 0, 0, 0);
27         pfault_info_cache = kmem_cache_create("pfault_info",
28                                               sizeof(pfault_info_t), 8, 0, 0, 0);
29 }
30
31 /* For now, the caller will set the prot, flags, file, and offset.  In the
32  * future, we may put those in here, to do clever things with merging vm_regions
33  * that are the same.
34  *
35  * TODO: take a look at solari's vmem alloc.  And consider keeping these in a
36  * tree of some sort for easier lookups. */
37 struct vm_region *create_vmr(struct proc *p, uintptr_t va, size_t len)
38 {
39         struct vm_region *vmr = 0, *vm_i, *vm_link;
40         uintptr_t gap_end;
41
42         /* Don't allow a vm region into the 0'th page (null ptr issues) */
43         if (va == 0)
44                 va = 1 * PGSIZE;
45
46         assert(!PGOFF(va));
47         assert(!PGOFF(len));
48         assert(va + len <= USTACKBOT);
49
50         /* Is there room before the first one: */
51         vm_i = TAILQ_FIRST(&p->vm_regions);
52         if (!vm_i || (va + len < vm_i->vm_base)) {
53                 vmr = kmem_cache_alloc(vmr_kcache, 0);
54                 vmr->vm_base = va;
55                 TAILQ_INSERT_HEAD(&p->vm_regions, vmr, vm_link);
56         } else {
57                 TAILQ_FOREACH(vm_i, &p->vm_regions, vm_link) {
58                         vm_link = TAILQ_NEXT(vm_i, vm_link); 
59                         gap_end = vm_link ? vm_link->vm_base : USTACKBOT;
60                         /* skip til we get past the 'hint' va */
61                         if (va >= gap_end)
62                                 continue;
63                         /* Found a gap that is big enough */
64                         if (gap_end - vm_i->vm_end >= len) {
65                                 vmr = kmem_cache_alloc(vmr_kcache, 0);
66                                 /* if we can put it at va, let's do that.  o/w, put it so it
67                                  * fits */
68                                 if (gap_end >= va + len)
69                                         vmr->vm_base = va;
70                                 else
71                                         vmr->vm_base = vm_i->vm_end;
72                                 TAILQ_INSERT_AFTER(&p->vm_regions, vm_i, vmr, vm_link);
73                                 break;
74                         }
75                 }
76         }
77         /* Finalize the creation, if we got one */
78         if (vmr) {
79                 vmr->vm_proc = p;
80                 vmr->vm_end = vmr->vm_base + len;
81         }
82         return vmr;
83 }
84
85 /* Split a VMR at va, returning the new VMR.  It is set up the same way, with
86  * file offsets fixed accordingly.  'va' is the beginning of the new one, and
87  * must be page aligned. */
88 struct vm_region *split_vmr(struct vm_region *old_vmr, uintptr_t va)
89 {
90         struct vm_region *new_vmr;
91
92         assert(!PGOFF(va));
93         if ((old_vmr->vm_base >= va) || (old_vmr->vm_end <= va))
94                 return 0;
95         new_vmr = kmem_cache_alloc(vmr_kcache, 0);
96         TAILQ_INSERT_AFTER(&old_vmr->vm_proc->vm_regions, old_vmr, new_vmr,
97                            vm_link);
98         new_vmr->vm_proc = old_vmr->vm_proc;
99         new_vmr->vm_base = va;
100         new_vmr->vm_end = old_vmr->vm_end;
101         old_vmr->vm_end = va;
102         new_vmr->vm_perm = old_vmr->vm_perm;
103         new_vmr->vm_flags = old_vmr->vm_flags;
104         if (old_vmr->vm_file) {
105                 new_vmr->vm_file = old_vmr->vm_file;
106                 atomic_inc(&new_vmr->vm_file->f_refcnt);
107                 new_vmr->vm_foff = old_vmr->vm_foff +
108                                       old_vmr->vm_end - old_vmr->vm_base;
109         } else {
110                 new_vmr->vm_file = 0;
111                 new_vmr->vm_foff = 0;
112         }
113         return new_vmr;
114 }
115
116 /* Merges two vm regions.  For now, it will check to make sure they are the
117  * same.  The second one will be destroyed. */
118 int merge_vmr(struct vm_region *first, struct vm_region *second)
119 {
120         assert(first->vm_proc == second->vm_proc);
121         if ((first->vm_end != second->vm_base) ||
122             (first->vm_perm != second->vm_perm) ||
123             (first->vm_flags != second->vm_flags) ||
124             (first->vm_file != second->vm_file))
125                 return -1;
126         if ((first->vm_file) && (second->vm_foff != first->vm_foff +
127                                  first->vm_end - first->vm_base))
128                 return -1;
129         first->vm_end = second->vm_end;
130         destroy_vmr(second);
131         return 0;
132 }
133
134 /* Grows the vm region up to (and not including) va.  Fails if another is in the
135  * way, etc. */
136 int grow_vmr(struct vm_region *vmr, uintptr_t va)
137 {
138         assert(!PGOFF(va));
139         struct vm_region *next = TAILQ_NEXT(vmr, vm_link);
140         if (next && next->vm_base < va)
141                 return -1;
142         if (va <= vmr->vm_end)
143                 return -1;
144         vmr->vm_end = va;
145         return 0;
146 }
147
148 /* Shrinks the vm region down to (and not including) va.  Whoever calls this
149  * will need to sort out the page table entries. */
150 int shrink_vmr(struct vm_region *vmr, uintptr_t va)
151 {
152         assert(!PGOFF(va));
153         if ((va < vmr->vm_base) || (va > vmr->vm_end))
154                 return -1;
155         vmr->vm_end = va;
156         return 0;
157 }
158
159 /* Called by the unmapper, just cleans up.  Whoever calls this will need to sort
160  * out the page table entries. */
161 void destroy_vmr(struct vm_region *vmr)
162 {
163         if (vmr->vm_file)
164                 atomic_dec(&vmr->vm_file->f_refcnt);
165         TAILQ_REMOVE(&vmr->vm_proc->vm_regions, vmr, vm_link);
166         kmem_cache_free(vmr_kcache, vmr);
167 }
168
169 /* Given a va and a proc (later an mm, possibly), returns the owning vmr, or 0
170  * if there is none. */
171 struct vm_region *find_vmr(struct proc *p, uintptr_t va)
172 {
173         struct vm_region *vmr;
174         /* ugly linear seach */
175         TAILQ_FOREACH(vmr, &p->vm_regions, vm_link) {
176                 if ((vmr->vm_base <= va) && (vmr->vm_end > va))
177                         return vmr;
178         }
179         return 0;
180 }
181
182 /* Finds the first vmr after va (including the one holding va), or 0 if there is
183  * none. */
184 struct vm_region *find_first_vmr(struct proc *p, uintptr_t va)
185 {
186         struct vm_region *vmr;
187         /* ugly linear seach */
188         TAILQ_FOREACH(vmr, &p->vm_regions, vm_link) {
189                 if ((vmr->vm_base <= va) && (vmr->vm_end > va))
190                         return vmr;
191                 if (vmr->vm_base > va)
192                         return vmr;
193         }
194         return 0;
195 }
196
197 void print_vmrs(struct proc *p)
198 {
199         int count = 0;
200         struct vm_region *vmr;
201         printk("VM Regions for proc %d\n", p->pid);
202         TAILQ_FOREACH(vmr, &p->vm_regions, vm_link)
203                 printk("%02d: (0x%08x - 0x%08x)\n", count++, vmr->vm_base, vmr->vm_end);
204 }
205
206
207 void *mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
208            int fd, size_t offset)
209 {
210         printd("mmap(addr %x, len %x, prot %x, flags %x, fd %x, off %x)\n", addr,
211                len, prot, flags, fd, offset);
212         if (fd >= 0 && (flags & MAP_SHARED)) {
213                 printk("[kernel] mmap() for files requires !MAP_SHARED.\n");
214                 return (void*)-1;
215         }
216         if (fd >= 0 && (flags & MAP_ANON)) {
217                 printk("[kernel] mmap() with MAP_ANONYMOUS requires fd == -1.\n");
218                 return (void*)-1;
219         }
220         if((flags & MAP_FIXED) && PGOFF(addr)) {
221                 printk("[kernel] mmap() page align your addr.\n");
222                 return (void*SAFE)TC(-1);
223         }
224
225         struct file* file = NULL;
226         if(fd != -1)
227         {
228                 file = file_open_from_fd(p,fd);
229                 if(!file)
230                         return (void*)-1;
231         }
232
233         void* result = do_mmap(p,addr,len,prot,flags,file,offset);
234
235         if(file)
236                 file_decref(file);
237
238         return result;
239 }
240
241 void *do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
242               struct file* file, size_t offset)
243 {
244         // TODO: grab the appropriate mm_lock
245         spin_lock(&p->proc_lock);
246         void* ret = __do_mmap(p,addr,len,prot,flags,file,offset);
247         spin_unlock(&p->proc_lock);
248         return ret;
249 }
250
251 /* Consider moving the top half of this to another function, like mmap(). */
252 void *__do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
253                 struct file* file, size_t offset)
254 {
255         int num_pages = ROUNDUP(len, PGSIZE) / PGSIZE;
256
257 #ifndef __CONFIG_DEMAND_PAGING__
258         flags |= MAP_POPULATE;
259 #endif
260         
261         /* TODO: if FIXED, need to handle overlap on another region */
262         if(!(flags & MAP_FIXED))
263         {
264                 /* this should be arch indep, and once we add the new region to the
265                  * list, this won't think the region is free */
266                 addr = (uintptr_t)get_free_va_range(p->env_pgdir,addr,len);
267                 if(!addr)
268                         goto mmap_abort;
269
270                 assert(!PGOFF(addr));
271                 assert(addr + num_pages*PGSIZE <= USTACKBOT);
272         }
273         #if 0
274         struct vm_region *vmr = create_vmr(p, addr, len);
275         vmr->vm_perm = prot;
276         vmr->vm_flags = flags;
277         vmr->vm_file = file;
278         vmr->vm_foff = offset;
279         #endif
280
281         // get a list of pfault_info_t's and pte's a priori,
282         // because if their allocation fails, we could end up
283         // in an inconsistent state
284
285         pfault_info_t** pfis = kmalloc(sizeof(pfault_info_t*)*num_pages,0);
286         pte_t** ptes = kmalloc(sizeof(pte_t*)*num_pages,0);
287         if(!pfis || !ptes)
288         {
289                 kfree(ptes);
290                 kfree(pfis);
291                 goto mmap_abort;
292         }
293
294         for(int i = 0; i < num_pages; i++)
295         {
296                 pfis[i] = pfault_info_alloc(file);
297                 ptes[i] = pgdir_walk(p->env_pgdir,(char*)addr+i*PGSIZE,1);
298
299                 // cleanup allocated pfault_info_t's on allocation failure
300                 if(!pfis[i] || !ptes[i])
301                 {
302                         int free_until = pfis[i] ? i+1 : i;
303                         for(int j = 0; j < free_until; j++)
304                                 pfault_info_free(pfis[j]);
305
306                         kfree(ptes);
307                         kfree(pfis);
308                         goto mmap_abort;
309                 }
310         }
311
312         // make the lazy mapping finally
313         for(int i = 0; i < num_pages; i++)
314         {
315                 // free an old page that was present here
316                 if(PAGE_PRESENT(*ptes[i]))
317                         page_decref(ppn2page(PTE2PPN(*ptes[i])));
318                 // free the pfault_info for a page that wasn't faulted-in yet
319                 else if(PAGE_PAGED_OUT(*ptes[i]))
320                         pfault_info_free(PTE2PFAULT_INFO(*ptes[i]));
321
322                 pfis[i]->file = file;
323                 pfis[i]->pgoff = offset+i;
324                 pfis[i]->read_len = PGSIZE;
325                 // zero-fill end of last page
326                 if(i == num_pages-1 && len % PGSIZE)
327                         pfis[i]->read_len = len % PGSIZE;
328                 pfis[i]->prot = prot;
329                 *ptes[i] = PFAULT_INFO2PTE(pfis[i]);
330         }
331
332         kfree(ptes);
333         kfree(pfis);
334
335         // fault in pages now if MAP_POPULATE.  die on failure.
336         if(flags & MAP_POPULATE)
337                 for(int i = 0; i < num_pages; i++)
338                         if(__handle_page_fault(p,addr+i*PGSIZE,PROT_READ))
339                                 proc_destroy(p);
340
341         return (void*SAFE)TC(addr);
342
343         // TODO: if there's a failure, we should go back through the addr+len range
344         // and dealloc everything.  or at least define what we want to do if we run
345         // out of memory.
346         mmap_abort:
347                 // not a kernel problem, like if they ask to mmap a mapped location.
348                 printk("[kernel] mmap() aborted!\n");
349                 // mmap's semantics.  we need a better error propagation system
350                 return (void*SAFE)TC(-1); // this is also ridiculous
351 }
352
353 int mprotect(struct proc* p, void* addr, size_t len, int prot)
354 {
355         printd("mprotect(addr %x, len %x, prot %x)\n",addr,len,prot);
356         if((uintptr_t)addr % PGSIZE || (len == 0 && (prot & PROT_UNMAP)))
357         {
358                 set_errno(current_tf,EINVAL);
359                 return -1;
360         }
361
362         // overflow of end is handled in the for loop's parameters
363         char* end = ROUNDUP((char*)addr+len,PGSIZE);
364         if(addr >= (void*)UTOP || end > (char*)UTOP)
365         {
366                 set_errno(current_tf, (prot & PROT_UNMAP) ? EINVAL : ENOMEM);
367                 return -1;
368         }
369
370         spin_lock(&p->proc_lock);
371         int ret = __mprotect(p,addr,len,prot);
372         spin_unlock(&p->proc_lock);
373
374         return ret;
375 }
376
377 int __mprotect(struct proc* p, void* addr, size_t len, int prot)
378 {
379         int newperm = (prot & PROT_WRITE) ? PTE_USER_RW :
380                       (prot & (PROT_READ|PROT_EXEC)) ? PTE_USER_RO : 0;
381
382         char* end = ROUNDUP((char*)addr+len,PGSIZE);
383         for(char* a = (char*)addr; a < end; a += PGSIZE)
384         {
385                 pte_t* pte = pgdir_walk(p->env_pgdir,a,0);
386
387                 // unmapped page? error out, behavior undefined (per POSIX)
388                 if(!pte || PAGE_UNMAPPED(*pte))
389                 {
390                         set_errno(current_tf,ENOMEM);
391                         return -1;
392                 }
393                 // common case: the page is present
394                 else if(PAGE_PRESENT(*pte))
395                 {
396                         // TODO: do munmap() in munmap(), instead of mprotect()
397                         if(prot & PROT_UNMAP)
398                         {
399                                 page_t* page = ppn2page(PTE2PPN(*pte));
400                                 *pte = 0;
401                                 page_decref(page);
402                         }
403                         else
404                         {
405                                 *pte = (*pte & ~PTE_PERM) | newperm;
406                         }
407                 }
408                 // or, the page might be mapped, but not yet faulted-in
409                 else // PAGE_PAGED_OUT(*pte)
410                 {
411                         if(prot & PROT_UNMAP)
412                         {
413                                 pfault_info_free(PTE2PFAULT_INFO(*pte));
414                                 *pte = 0;
415                         }
416                         else
417                                 PTE2PFAULT_INFO(*pte)->prot = prot;
418                 }
419         }
420
421         /* TODO: (TLB) make this take a sensible range.  For now, it doesn't matter
422          * since we ignore it in the process code.  Also, make sure you are holding
423          * the proc_lock when calling this. */
424         __proc_tlbshootdown(p, 0, 0xffffffff);
425         return 0;
426 }
427
428 int munmap(struct proc* p, void* addr, size_t len)
429 {
430         return mprotect(p, addr, len, PROT_UNMAP);
431 }
432
433 int __munmap(struct proc* p, void* addr, size_t len)
434 {
435         return __mprotect(p, addr, len, PROT_UNMAP);
436 }
437
438 int handle_page_fault(struct proc* p, uintptr_t va, int prot)
439 {
440         va = ROUNDDOWN(va,PGSIZE);
441
442         if(prot != PROT_READ && prot != PROT_WRITE && prot != PROT_EXEC)
443                 panic("bad prot!");
444
445         spin_lock(&p->proc_lock);
446         int ret = __handle_page_fault(p,va,prot);
447         spin_unlock(&p->proc_lock);
448         return ret;
449 }
450         
451 int __handle_page_fault(struct proc* p, uintptr_t va, int prot)
452 {
453         int ret = -1;
454         // find offending PTE
455         pte_t* ppte = pgdir_walk(p->env_pgdir,(void*)va,0);
456         // if PTE is NULL, this is a fault that should kill the process
457         if(!ppte)
458                 goto out;
459
460         pte_t pte = *ppte;
461
462         // if PTE is present, why did we fault?
463         if(PAGE_PRESENT(pte))
464         {
465                 int perm = pte & PTE_PERM;
466                 // a race is possible: the page might have been faulted in by
467                 // another core already, in which case we should just return.
468                 // otherwise, it's a fault that should kill the user
469                 switch(prot)
470                 {
471                         case PROT_READ:
472                         case PROT_EXEC:
473                                 if(perm == PTE_USER_RO || perm == PTE_USER_RW)
474                                         ret = 0;
475                                 goto out;
476                         case PROT_WRITE:
477                                 if(perm == PTE_USER_RW)
478                                         ret = 0;
479                                 goto out;
480                 }
481                 // can't get here
482         }
483
484         // if the page isn't present, kill the user
485         if(PAGE_UNMAPPED(pte))
486                 goto out;
487
488         // now, we know that PAGE_PAGED_OUT(pte) is true
489         pfault_info_t* info = PTE2PFAULT_INFO(pte);
490
491         // allocate a page; maybe zero-fill it
492         int zerofill = info->file == NULL;
493         page_t* a_page;
494         if(upage_alloc(p, &a_page, zerofill))
495                 goto out;
496
497         // if this isn't a zero-filled page, read it in from file
498         if(!zerofill)
499         {
500                 int read_len = file_read_page(info->file,page2pa(a_page),info->pgoff);
501                 if(read_len < 0)
502                 {
503                         page_free(a_page);
504                         goto out;
505                 }
506
507                 // if we read too much, zero that part out
508                 if(info->read_len < read_len)
509                         memset(page2kva(a_page)+info->read_len,0,read_len-info->read_len);
510
511                 // if this is an executable page, we might have to flush
512                 // the instruction cache if our HW requires it
513                 if(info->prot & PROT_EXEC)
514                         icache_flush_page((void*)va,page2kva(a_page));
515         }
516
517         int perm = (info->prot & PROT_WRITE) ? PTE_USER_RW :
518                    (info->prot & (PROT_READ|PROT_EXEC))  ? PTE_USER_RO : 0;
519
520         // update the page table
521         page_incref(a_page);
522         *ppte = PTE(page2ppn(a_page),PTE_P | perm);
523
524         pfault_info_free(info);
525         ret = 0;
526
527 out:
528         tlbflush();
529         return ret;
530 }
531
532 pfault_info_t* pfault_info_alloc(struct file* file)
533 {
534         if(file)
535                 file_incref(file);
536         return kmem_cache_alloc(pfault_info_cache,0);
537 }
538
539 void pfault_info_free(pfault_info_t* pfi)
540 {
541         if(pfi->file)
542                 file_decref(pfi->file);
543         kmem_cache_free(pfault_info_cache,pfi);
544 }