Splits the mm_lock
[akaros.git] / kern / src / mm.c
1 /* Copyright (c) 2009, 2010 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Virtual memory management functions.  Creation, modification, etc, of virtual
6  * memory regions (VMRs) as well as mmap(), mprotect(), and munmap().
7  *
8  * In general, error checking / bounds checks are done in the main function
9  * (e.g. mmap()), and the work is done in a do_ function (e.g. do_mmap()).
10  * Versions of those functions that are called when the vmr lock is already held
11  * begin with __ (e.g. __do_munmap()).
12  *
13  * Note that if we were called from kern/src/syscall.c, we probably don't have
14  * an edible reference to p. */
15
16 #include <frontend.h>
17 #include <ros/common.h>
18 #include <pmap.h>
19 #include <mm.h>
20 #include <process.h>
21 #include <stdio.h>
22 #include <syscall.h>
23 #include <slab.h>
24 #include <kmalloc.h>
25 #include <vfs.h>
26 #include <smp.h>
27
28 static int __vmr_free_pgs(struct proc *p, pte_t *pte, void *va, void *arg);
29
30 struct kmem_cache *vmr_kcache;
31
32 void vmr_init(void)
33 {
34         vmr_kcache = kmem_cache_create("vm_regions", sizeof(struct vm_region),
35                                        __alignof__(struct dentry), 0, 0, 0);
36 }
37
38 /* For now, the caller will set the prot, flags, file, and offset.  In the
39  * future, we may put those in here, to do clever things with merging vm_regions
40  * that are the same.
41  *
42  * TODO: take a look at solari's vmem alloc.  And consider keeping these in a
43  * tree of some sort for easier lookups. */
44 struct vm_region *create_vmr(struct proc *p, uintptr_t va, size_t len)
45 {
46         struct vm_region *vmr = 0, *vm_i, *vm_next;
47         uintptr_t gap_end;
48
49         assert(!PGOFF(va));
50         assert(!PGOFF(len));
51         assert(va + len <= UMAPTOP);
52         /* Is there room before the first one: */
53         vm_i = TAILQ_FIRST(&p->vm_regions);
54         /* This works for now, but if all we have is BRK_END ones, we'll start
55          * growing backwards (TODO) */
56         if (!vm_i || (va + len < vm_i->vm_base)) {
57                 vmr = kmem_cache_alloc(vmr_kcache, 0);
58                 if (!vmr)
59                         panic("EOM!");
60                 memset(vmr, 0, sizeof(struct vm_region));
61                 vmr->vm_base = va;
62                 TAILQ_INSERT_HEAD(&p->vm_regions, vmr, vm_link);
63         } else {
64                 TAILQ_FOREACH(vm_i, &p->vm_regions, vm_link) {
65                         vm_next = TAILQ_NEXT(vm_i, vm_link);
66                         gap_end = vm_next ? vm_next->vm_base : UMAPTOP;
67                         /* skip til we get past the 'hint' va */
68                         if (va >= gap_end)
69                                 continue;
70                         /* Find a gap that is big enough */
71                         if (gap_end - vm_i->vm_end >= len) {
72                                 vmr = kmem_cache_alloc(vmr_kcache, 0);
73                                 if (!vmr)
74                                         panic("EOM!");
75                                 memset(vmr, 0, sizeof(struct vm_region));
76                                 /* if we can put it at va, let's do that.  o/w, put it so it
77                                  * fits */
78                                 if ((gap_end >= va + len) && (va >= vm_i->vm_end))
79                                         vmr->vm_base = va;
80                                 else
81                                         vmr->vm_base = vm_i->vm_end;
82                                 TAILQ_INSERT_AFTER(&p->vm_regions, vm_i, vmr, vm_link);
83                                 break;
84                         }
85                 }
86         }
87         /* Finalize the creation, if we got one */
88         if (vmr) {
89                 vmr->vm_proc = p;
90                 vmr->vm_end = vmr->vm_base + len;
91         }
92         if (!vmr)
93                 warn("Not making a VMR, wanted %p, + %p = %p", va, len, va + len);
94         return vmr;
95 }
96
97 /* Split a VMR at va, returning the new VMR.  It is set up the same way, with
98  * file offsets fixed accordingly.  'va' is the beginning of the new one, and
99  * must be page aligned. */
100 struct vm_region *split_vmr(struct vm_region *old_vmr, uintptr_t va)
101 {
102         struct vm_region *new_vmr;
103
104         assert(!PGOFF(va));
105         if ((old_vmr->vm_base >= va) || (old_vmr->vm_end <= va))
106                 return 0;
107         new_vmr = kmem_cache_alloc(vmr_kcache, 0);
108         TAILQ_INSERT_AFTER(&old_vmr->vm_proc->vm_regions, old_vmr, new_vmr,
109                            vm_link);
110         new_vmr->vm_proc = old_vmr->vm_proc;
111         new_vmr->vm_base = va;
112         new_vmr->vm_end = old_vmr->vm_end;
113         old_vmr->vm_end = va;
114         new_vmr->vm_prot = old_vmr->vm_prot;
115         new_vmr->vm_flags = old_vmr->vm_flags;
116         if (old_vmr->vm_file) {
117                 kref_get(&old_vmr->vm_file->f_kref, 1);
118                 new_vmr->vm_file = old_vmr->vm_file;
119                 new_vmr->vm_foff = old_vmr->vm_foff +
120                                       old_vmr->vm_end - old_vmr->vm_base;
121         } else {
122                 new_vmr->vm_file = 0;
123                 new_vmr->vm_foff = 0;
124         }
125         return new_vmr;
126 }
127
128 /* Merges two vm regions.  For now, it will check to make sure they are the
129  * same.  The second one will be destroyed. */
130 int merge_vmr(struct vm_region *first, struct vm_region *second)
131 {
132         assert(first->vm_proc == second->vm_proc);
133         if ((first->vm_end != second->vm_base) ||
134             (first->vm_prot != second->vm_prot) ||
135             (first->vm_flags != second->vm_flags) ||
136             (first->vm_file != second->vm_file))
137                 return -1;
138         if ((first->vm_file) && (second->vm_foff != first->vm_foff +
139                                  first->vm_end - first->vm_base))
140                 return -1;
141         first->vm_end = second->vm_end;
142         destroy_vmr(second);
143         return 0;
144 }
145
146 /* Attempts to merge vmr with adjacent VMRs, returning a ptr to be used for vmr.
147  * It could be the same struct vmr, or possibly another one (usually lower in
148  * the address space. */
149 struct vm_region *merge_me(struct vm_region *vmr)
150 {
151         struct vm_region *vmr_temp;
152         /* Merge will fail if it cannot do it.  If it succeeds, the second VMR is
153          * destroyed, so we need to be a bit careful. */
154         vmr_temp = TAILQ_PREV(vmr, vmr_tailq, vm_link);
155         if (vmr_temp)
156                 if (!merge_vmr(vmr_temp, vmr))
157                         vmr = vmr_temp;
158         vmr_temp = TAILQ_NEXT(vmr, vm_link);
159         if (vmr_temp)
160                 merge_vmr(vmr, vmr_temp);
161         return vmr;
162 }
163
164 /* Grows the vm region up to (and not including) va.  Fails if another is in the
165  * way, etc. */
166 int grow_vmr(struct vm_region *vmr, uintptr_t va)
167 {
168         assert(!PGOFF(va));
169         struct vm_region *next = TAILQ_NEXT(vmr, vm_link);
170         if (next && next->vm_base < va)
171                 return -1;
172         if (va <= vmr->vm_end)
173                 return -1;
174         vmr->vm_end = va;
175         return 0;
176 }
177
178 /* Shrinks the vm region down to (and not including) va.  Whoever calls this
179  * will need to sort out the page table entries. */
180 int shrink_vmr(struct vm_region *vmr, uintptr_t va)
181 {
182         assert(!PGOFF(va));
183         if ((va < vmr->vm_base) || (va > vmr->vm_end))
184                 return -1;
185         vmr->vm_end = va;
186         return 0;
187 }
188
189 /* Called by the unmapper, just cleans up.  Whoever calls this will need to sort
190  * out the page table entries. */
191 void destroy_vmr(struct vm_region *vmr)
192 {
193         if (vmr->vm_file)
194                 kref_put(&vmr->vm_file->f_kref);
195         TAILQ_REMOVE(&vmr->vm_proc->vm_regions, vmr, vm_link);
196         kmem_cache_free(vmr_kcache, vmr);
197 }
198
199 /* Given a va and a proc (later an mm, possibly), returns the owning vmr, or 0
200  * if there is none. */
201 struct vm_region *find_vmr(struct proc *p, uintptr_t va)
202 {
203         struct vm_region *vmr;
204         /* ugly linear seach */
205         TAILQ_FOREACH(vmr, &p->vm_regions, vm_link) {
206                 if ((vmr->vm_base <= va) && (vmr->vm_end > va))
207                         return vmr;
208         }
209         return 0;
210 }
211
212 /* Finds the first vmr after va (including the one holding va), or 0 if there is
213  * none. */
214 struct vm_region *find_first_vmr(struct proc *p, uintptr_t va)
215 {
216         struct vm_region *vmr;
217         /* ugly linear seach */
218         TAILQ_FOREACH(vmr, &p->vm_regions, vm_link) {
219                 if ((vmr->vm_base <= va) && (vmr->vm_end > va))
220                         return vmr;
221                 if (vmr->vm_base > va)
222                         return vmr;
223         }
224         return 0;
225 }
226
227 /* Makes sure that no VMRs cross either the start or end of the given region
228  * [va, va + len), splitting any VMRs that are on the endpoints. */
229 void isolate_vmrs(struct proc *p, uintptr_t va, size_t len)
230 {
231         struct vm_region *vmr;
232         if ((vmr = find_vmr(p, va)))
233                 split_vmr(vmr, va);
234         /* TODO: don't want to do another find (linear search) */
235         if ((vmr = find_vmr(p, va + len)))
236                 split_vmr(vmr, va + len);
237 }
238
239 void unmap_and_destroy_vmrs(struct proc *p)
240 {
241         struct vm_region *vmr_i, *vmr_temp;
242         /* this only gets called from __proc_free, so there should be no sync
243          * concerns.  still, better safe than sorry. */
244         spin_lock(&p->vmr_lock);
245         spin_lock(&p->pte_lock);
246         TAILQ_FOREACH(vmr_i, &p->vm_regions, vm_link) {
247                 /* note this CB sets the PTE = 0, regardless of if it was P or not */
248                 env_user_mem_walk(p, (void*)vmr_i->vm_base,
249                                   vmr_i->vm_end - vmr_i->vm_base, __vmr_free_pgs, 0);
250         }
251         spin_unlock(&p->pte_lock);
252         /* need the safe style, since destroy_vmr modifies the list.  also, we want
253          * to do this outside the pte lock, since it grabs the pm lock. */
254         TAILQ_FOREACH_SAFE(vmr_i, &p->vm_regions, vm_link, vmr_temp)
255                 destroy_vmr(vmr_i);
256         spin_unlock(&p->vmr_lock);
257 }
258
259 /* Helper: copies the contents of pages from p to new p.  For pages that aren't
260  * present, once we support swapping or CoW, we can do something more
261  * intelligent.  0 on success, -ERROR on failure. */
262 static int copy_pages(struct proc *p, struct proc *new_p, uintptr_t va_start,
263                       uintptr_t va_end)
264 {
265         /* Sanity checks.  If these fail, we had a screwed up VMR.
266          * Check for: alignment, wraparound, or userspace addresses */
267         if ((PGOFF(va_start)) ||
268             (PGOFF(va_end)) ||
269             (va_end < va_start) ||      /* now, start > UMAPTOP -> end > UMAPTOP */
270             (va_end > UMAPTOP)) {
271                 warn("VMR mapping is probably screwed up (%p - %p)", va_start,
272                      va_end);
273                 return -EINVAL;
274         }
275         int copy_page(struct proc *p, pte_t *pte, void *va, void *arg) {
276                 struct proc *new_p = (struct proc*)arg;
277                 struct page *pp;
278                 if (PAGE_UNMAPPED(*pte))
279                         return 0;
280                 /* pages could be !P, but right now that's only for file backed VMRs
281                  * undergoing page removal, which isn't the caller of copy_pages. */
282                 if (PAGE_PRESENT(*pte)) {
283                         /* TODO: check for jumbos */
284                         if (upage_alloc(new_p, &pp, 0))
285                                 return -ENOMEM;
286                         if (page_insert(new_p->env_pgdir, pp, va, *pte & PTE_PERM)) {
287                                 page_decref(pp);
288                                 return -ENOMEM;
289                         }
290                         memcpy(page2kva(pp), ppn2kva(PTE2PPN(*pte)), PGSIZE);
291                         page_decref(pp);
292                 } else if (PAGE_PAGED_OUT(*pte)) {
293                         /* TODO: (SWAP) will need to either make a copy or CoW/refcnt the
294                          * backend store.  For now, this PTE will be the same as the
295                          * original PTE */
296                         panic("Swapping not supported!");
297                 } else {
298                         panic("Weird PTE %p in %s!", *pte, __FUNCTION__);
299                 }
300                 return 0;
301         }
302         return env_user_mem_walk(p, (void*)va_start, va_end - va_start, &copy_page,
303                                  new_p);
304 }
305
306 /* This will make new_p have the same VMRs as p, and it will make sure all
307  * physical pages are copied over, with the exception of MAP_SHARED files.
308  * This is used by fork().
309  *
310  * Note that if you are working on a VMR that is a file, you'll want to be
311  * careful about how it is mapped (SHARED, PRIVATE, etc). */
312 int duplicate_vmrs(struct proc *p, struct proc *new_p)
313 {
314         int ret = 0;
315         struct vm_region *vmr, *vm_i;
316         TAILQ_FOREACH(vm_i, &p->vm_regions, vm_link) {
317                 vmr = kmem_cache_alloc(vmr_kcache, 0);
318                 if (!vmr)
319                         return -ENOMEM;
320                 vmr->vm_proc = new_p;
321                 vmr->vm_base = vm_i->vm_base;
322                 vmr->vm_end = vm_i->vm_end;
323                 vmr->vm_prot = vm_i->vm_prot;   
324                 vmr->vm_flags = vm_i->vm_flags; 
325                 if (vm_i->vm_file)
326                         kref_get(&vm_i->vm_file->f_kref, 1);
327                 vmr->vm_file = vm_i->vm_file;
328                 vmr->vm_foff = vm_i->vm_foff;
329                 if (!vmr->vm_file || vmr->vm_flags & MAP_PRIVATE) {
330                         assert(!(vmr->vm_flags & MAP_SHARED));
331                         /* Copy over the memory from one VMR to the other */
332                         if ((ret = copy_pages(p, new_p, vmr->vm_base, vmr->vm_end)))
333                                 return ret;
334                 }
335                 TAILQ_INSERT_TAIL(&new_p->vm_regions, vmr, vm_link);
336         }
337         return 0;
338 }
339
340 void print_vmrs(struct proc *p)
341 {
342         int count = 0;
343         struct vm_region *vmr;
344         printk("VM Regions for proc %d\n", p->pid);
345         TAILQ_FOREACH(vmr, &p->vm_regions, vm_link)
346                 printk("%02d: (%p - %p): 0x%08x, 0x%08x, %p, %p\n", count++,
347                        vmr->vm_base, vmr->vm_end, vmr->vm_prot, vmr->vm_flags,
348                        vmr->vm_file, vmr->vm_foff);
349 }
350
351 /* Helper: returns the number of pages required to hold nr_bytes */
352 unsigned long nr_pages(unsigned long nr_bytes)
353 {
354         return (nr_bytes >> PGSHIFT) + (PGOFF(nr_bytes) ? 1 : 0);
355 }
356
357 /* Error values aren't quite comprehensive - check man mmap() once we do better
358  * with the FS.
359  *
360  * The mmap call's offset is in units of PGSIZE (like Linux's mmap2()), but
361  * internally, the offset is tracked in bytes.  The reason for the PGSIZE is for
362  * 32bit apps to enumerate large files, but a full 64bit system won't need that.
363  * We track things internally in bytes since that is how file pointers work, vmr
364  * bases and ends, and similar math.  While it's not a hard change, there's no
365  * need for it, and ideally we'll be a fully 64bit system before we deal with
366  * files that large. */
367 void *mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
368            int fd, size_t offset)
369 {
370         struct file *file = NULL;
371         offset <<= PGSHIFT;
372         printd("mmap(addr %x, len %x, prot %x, flags %x, fd %x, off %x)\n", addr,
373                len, prot, flags, fd, offset);
374         if (fd >= 0 && (flags & MAP_ANON)) {
375                 set_errno(EBADF);
376                 return MAP_FAILED;
377         }
378         if (!len) {
379                 set_errno(EINVAL);
380                 return MAP_FAILED;
381         }
382         if (fd != -1) {
383                 file = get_file_from_fd(&p->open_files, fd);
384                 if (!file) {
385                         set_errno(EBADF);
386                         return MAP_FAILED;
387                 }
388         }
389         /* If they don't care where to put it, we'll start looking after the break.
390          * We could just have userspace handle this (in glibc's mmap), so we don't
391          * need to know about BRK_END, but this will work for now (and may avoid
392          * bugs).  Note that this limits mmap(0) a bit.  Keep this in sync with
393          * __do_mmap()'s check.  (Both are necessary).  */
394         if (addr == 0)
395                 addr = BRK_END;
396         /* Still need to enforce this: */
397         addr = MAX(addr, MMAP_LOWEST_VA);
398         /* Need to check addr + len, after we do our addr adjustments */
399         if ((addr + len > UMAPTOP) || (PGOFF(addr))) {
400                 set_errno(EINVAL);
401                 return MAP_FAILED;
402         }
403         void *result = do_mmap(p, addr, len, prot, flags, file, offset);
404         if (file)
405                 kref_put(&file->f_kref);
406         return result;
407 }
408
409 void *do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
410               struct file *file, size_t offset)
411 {
412         /* read/write vmr lock (will change the tree) */
413         spin_lock(&p->vmr_lock);
414         void *ret = __do_mmap(p, addr, len, prot, flags, file, offset);
415         spin_unlock(&p->vmr_lock);
416         return ret;
417 }
418
419 /* Helper: returns TRUE if the VMR is allowed to access the file with prot.
420  * This is a bit ghetto still: messes with the file mode and assumes it can walk
421  * the dentry/inode paths without locking.  It also ignores the CoW stuff we'll
422  * need to do eventually. */
423 static bool check_file_perms(struct vm_region *vmr, struct file *file, int prot)
424 {
425         assert(file);
426         if (prot & PROT_READ) {
427                 if (check_perms(file->f_dentry->d_inode, S_IRUSR))
428                         goto out_error;
429         }
430         if (prot & PROT_WRITE) {
431                 /* if vmr maps a file as MAP_SHARED, then we need to make sure the
432                  * protection change is in compliance with the open mode of the
433                  * file. */
434                 if (vmr->vm_flags & MAP_SHARED) {
435                         if (!(file->f_mode & S_IWUSR)) {
436                                 /* at this point, we have a file opened in the wrong mode,
437                                  * but we may be allowed to access it still. */
438                                 if (check_perms(file->f_dentry->d_inode, S_IWUSR)) {
439                                         goto out_error;
440                                 } else {
441                                         /* it is okay, though we need to change the file mode. (note
442                                          * the lack of a lock/protection (TODO) */
443                                         file->f_mode |= S_IWUSR;
444                                 }
445                         }
446                 } else {        /* PRIVATE mapping */
447                         /* TODO: we want a CoW mapping (like we want in handle_page_fault()),
448                          * since there is a concern of a process having the page already
449                          * mapped in to a file it does not have permissions to, and then
450                          * mprotecting it so it can access it.  So we can't just change
451                          * the prot, and we don't know yet if a page is mapped in.  To
452                          * handle this, we ought to sort out the CoW bit, and then this
453                          * will be easy.  Til then, just do a permissions check.  If we
454                          * start having weird issues with libc overwriting itself (since
455                          * procs mprotect that W), then change this. */
456                         if (check_perms(file->f_dentry->d_inode, S_IWUSR))
457                                 goto out_error;
458                 }
459         }
460         return TRUE;
461 out_error:      /* for debugging */
462         printk("[kernel] mmap perm check failed for %s for access %d\n",
463                file_name(file), prot);
464         return FALSE;
465 }
466
467 void *__do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
468                 struct file *file, size_t offset)
469 {
470         len = ROUNDUP(len, PGSIZE);
471         int num_pages = len / PGSIZE;
472         int retval;
473
474         struct vm_region *vmr, *vmr_temp;
475
476         /* Sanity check, for callers that bypass mmap().  We want addr for anon
477          * memory to start above the break limit (BRK_END), but not 0.  Keep this in
478          * sync with BRK_END in mmap(). */
479         if (addr == 0)
480                 addr = BRK_END;
481         assert(!PGOFF(offset));
482
483 #ifndef CONFIG_DEMAND_PAGING
484         flags |= MAP_POPULATE;
485 #endif
486         /* Need to make sure nothing is in our way when we want a FIXED location.
487          * We just need to split on the end points (if they exist), and then remove
488          * everything in between.  __do_munmap() will do this.  Careful, this means
489          * an mmap can be an implied munmap() (not my call...). */
490         if (flags & MAP_FIXED)
491                 __do_munmap(p, addr, len);
492         vmr = create_vmr(p, addr, len);
493         if (!vmr) {
494                 printk("[kernel] do_mmap() aborted for %p + %d!\n", addr, len);
495                 set_errno(ENOMEM);
496                 return MAP_FAILED;              /* TODO: error propagation for mmap() */
497         }
498         vmr->vm_prot = prot;
499         vmr->vm_flags = flags;
500         if (file) {
501                 if (!check_file_perms(vmr, file, prot)) {
502                         destroy_vmr(vmr);
503                         set_errno(EACCES);
504                         return MAP_FAILED;
505                 }
506                 /* TODO: consider locking the file while checking (not as manadatory as
507                  * in handle_page_fault() */
508                 if (nr_pages(offset + len) > nr_pages(file->f_dentry->d_inode->i_size)) {
509                         /* We're allowing them to set up the VMR, though if they attempt to
510                          * fault in any pages beyond the file's limit, they'll fail.  Since
511                          * they might not access the region, we need to make sure POPULATE
512                          * is off.  FYI, 64 bit glibc shared libs map in an extra 2MB of
513                          * unaligned space between their RO and RW sections, but then
514                          * immediately mprotect it to PROT_NONE. */
515                         flags &= ~MAP_POPULATE;
516                 }
517                 kref_get(&file->f_kref, 1);
518         }
519         vmr->vm_file = file;
520         vmr->vm_foff = offset;
521         /* Prep the FS to make sure it can mmap the file.  Slightly weird semantics:
522          * they will have a hole in their VM now. */
523         if (file && file->f_op->mmap(file, vmr)) {
524                 destroy_vmr(vmr);
525                 set_errno(EACCES);      /* not quite */
526                 return MAP_FAILED;
527         }
528         addr = vmr->vm_base;            /* so we know which pages to populate later */
529         vmr = merge_me(vmr);            /* attempts to merge with neighbors */
530         /* Fault in pages now if MAP_POPULATE.  We want to populate the region
531          * requested, but we need to be careful and only populate the requested
532          * length and not any merged regions, which is why we set addr above and use
533          * it here.
534          *
535          * If HPF errors out, we'll warn and fail for now.  This could be due to
536          * some userspace error, but also occurs when we run out of memory.  If we
537          * are out of memory, the kernel can't really handle it. */
538         if (flags & MAP_POPULATE && vmr->vm_prot != PROT_NONE)
539                 for (int i = 0; i < num_pages; i++) {
540                         retval = __handle_page_fault(p, addr + i * PGSIZE, vmr->vm_prot);
541                         if (retval) {
542                                 warn("do_mmap() failing (%d) on addr %p with prot 0x%x",
543                                      retval, addr + i * PGSIZE,  vmr->vm_prot);
544                                 destroy_vmr(vmr);
545                                 set_errno(-retval);
546                                 if (retval == -ENOMEM) {
547                                         printk("[kernel] ENOMEM, killing %d\n", p->pid);
548                                         proc_destroy(p);
549                                 }
550                                 return MAP_FAILED;
551                         }
552                 }
553         return (void*SAFE)TC(addr);
554 }
555
556 int mprotect(struct proc *p, uintptr_t addr, size_t len, int prot)
557 {
558         printd("mprotect: (addr %p, len %p, prot 0x%x)\n", addr, len, prot);
559         if (!len)
560                 return 0;
561         if ((addr % PGSIZE) || (addr < MMAP_LOWEST_VA)) {
562                 set_errno(EINVAL);
563                 return -1;
564         }
565         uintptr_t end = ROUNDUP(addr + len, PGSIZE);
566         if (end > UMAPTOP || addr > end) {
567                 set_errno(ENOMEM);
568                 return -1;
569         }
570         /* read/write lock, will probably change the tree and settings */
571         spin_lock(&p->vmr_lock);
572         int ret = __do_mprotect(p, addr, len, prot);
573         spin_unlock(&p->vmr_lock);
574         return ret;
575 }
576
577 /* This does not care if the region is not mapped.  POSIX says you should return
578  * ENOMEM if any part of it is unmapped.  Can do this later if we care, based on
579  * the VMRs, not the actual page residency. */
580 int __do_mprotect(struct proc *p, uintptr_t addr, size_t len, int prot)
581 {
582         struct vm_region *vmr, *next_vmr;
583         pte_t *pte;
584         bool shootdown_needed = FALSE;
585         int pte_prot = (prot & PROT_WRITE) ? PTE_USER_RW :
586                        (prot & (PROT_READ|PROT_EXEC)) ? PTE_USER_RO : 0;
587         /* TODO: this is aggressively splitting, when we might not need to if the
588          * prots are the same as the previous.  Plus, there are three excessive
589          * scans.  Finally, we might be able to merge when we are done. */
590         isolate_vmrs(p, addr, len);
591         vmr = find_first_vmr(p, addr);
592         while (vmr && vmr->vm_base < addr + len) {
593                 if (vmr->vm_prot == prot)
594                         continue;
595                 if (vmr->vm_file && !check_file_perms(vmr, vmr->vm_file, prot)) {
596                         set_errno(EACCES);
597                         return -1;
598                 }
599                 vmr->vm_prot = prot;
600                 spin_lock(&p->pte_lock);        /* walking and changing PTEs */
601                 /* TODO: use a memwalk */
602                 for (uintptr_t va = vmr->vm_base; va < vmr->vm_end; va += PGSIZE) { 
603                         pte = pgdir_walk(p->env_pgdir, (void*)va, 0);
604                         if (pte && PAGE_PRESENT(*pte)) {
605                                 *pte = (*pte & ~PTE_PERM) | pte_prot;
606                                 shootdown_needed = TRUE;
607                         }
608                 }
609                 spin_unlock(&p->pte_lock);
610                 next_vmr = TAILQ_NEXT(vmr, vm_link);
611                 vmr = next_vmr;
612         }
613         if (shootdown_needed)
614                 proc_tlbshootdown(p, addr, addr + len);
615         return 0;
616 }
617
618 int munmap(struct proc *p, uintptr_t addr, size_t len)
619 {
620         printd("munmap(addr %x, len %x)\n", addr, len);
621         if (!len)
622                 return 0;
623         if ((addr % PGSIZE) || (addr < MMAP_LOWEST_VA)) {
624                 set_errno(EINVAL);
625                 return -1;
626         }
627         uintptr_t end = ROUNDUP(addr + len, PGSIZE);
628         if (end > UMAPTOP || addr > end) {
629                 set_errno(EINVAL);
630                 return -1;
631         }
632         /* read/write: changing the vmrs (trees, properties, and whatnot) */
633         spin_lock(&p->vmr_lock);
634         int ret = __do_munmap(p, addr, len);
635         spin_unlock(&p->vmr_lock);
636         return ret;
637 }
638
639 static int __munmap_mark_not_present(struct proc *p, pte_t *pte, void *va,
640                                      void *arg)
641 {
642         bool *shootdown_needed = (bool*)arg;
643         struct page *page;
644         /* could put in some checks here for !P and also !0 */
645         if (!PAGE_PRESENT(*pte))        /* unmapped (== 0) *ptes are also not PTE_P */
646                 return 0;
647         page = ppn2page(PTE2PPN(*pte));
648         *pte &= ~PTE_P;
649         *shootdown_needed = TRUE;
650         return 0;
651 }
652
653 /* If our page is actually in the PM, we don't do anything.  All a page map
654  * really needs is for our VMR to no longer track it (vmr being in the pm's
655  * list) and to not point at its pages (mark it 0, dude).
656  *
657  * But private mappings mess with that a bit.  Luckily, we can tell by looking
658  * at a page whether the specific page is in the PM or not.  If it isn't, we
659  * still need to free our "VMR local" copy.
660  *
661  * For pages in a PM, we're racing with PM removers.  Both of us sync with the
662  * mm lock, so once we hold the lock, it's a matter of whether or not the PTE is
663  * 0 or not.  If it isn't, then we're still okay to look at the page.  Consider
664  * the PTE a weak ref on the page.  So long as you hold the mm lock, you can
665  * look at the PTE and know the page isn't being freed. */
666 static int __vmr_free_pgs(struct proc *p, pte_t *pte, void *va, void *arg)
667 {
668         struct page *page;
669         if (!*pte)
670                 return 0;
671         page = ppn2page(PTE2PPN(*pte));
672         *pte = 0;
673         if (!(atomic_read(&page->pg_flags) & PG_PAGEMAP))
674                 page_decref(page);
675         return 0;
676 }
677
678 int __do_munmap(struct proc *p, uintptr_t addr, size_t len)
679 {
680         struct vm_region *vmr, *next_vmr, *first_vmr;
681         pte_t *pte;
682         bool shootdown_needed = FALSE;
683
684         /* TODO: this will be a bit slow, since we end up doing three linear
685          * searches (two in isolate, one in find_first). */
686         isolate_vmrs(p, addr, len);
687         first_vmr = find_first_vmr(p, addr);
688         vmr = first_vmr;
689         spin_lock(&p->pte_lock);        /* changing PTEs */
690         while (vmr && vmr->vm_base < addr + len) {
691                 env_user_mem_walk(p, (void*)vmr->vm_base, vmr->vm_end - vmr->vm_base,
692                                   __munmap_mark_not_present, &shootdown_needed);
693                 vmr = TAILQ_NEXT(vmr, vm_link);
694         }
695         spin_unlock(&p->pte_lock);
696         /* we haven't freed the pages yet; still using the PTEs to store the them.
697          * There should be no races with inserts/faults, since we still hold the mm
698          * lock since the previous CB. */
699         if (shootdown_needed)
700                 proc_tlbshootdown(p, addr, addr + len);
701         vmr = first_vmr;
702         while (vmr && vmr->vm_base < addr + len) {
703                 /* there is rarely more than one VMR in this loop.  o/w, we'll need to
704                  * gather up the vmrs and destroy outside the pte_lock. */
705                 spin_lock(&p->pte_lock);        /* changing PTEs */
706                 env_user_mem_walk(p, (void*)vmr->vm_base, vmr->vm_end - vmr->vm_base,
707                                       __vmr_free_pgs, 0);
708                 spin_unlock(&p->pte_lock);
709                 next_vmr = TAILQ_NEXT(vmr, vm_link);
710                 destroy_vmr(vmr);
711                 vmr = next_vmr;
712         }
713         return 0;
714 }
715
716 int handle_page_fault(struct proc* p, uintptr_t va, int prot)
717 {
718         va = ROUNDDOWN(va,PGSIZE);
719
720         if (prot != PROT_READ && prot != PROT_WRITE && prot != PROT_EXEC)
721                 panic("bad prot!");
722         /* read access to the VMRs TODO: RCU */
723         spin_lock(&p->vmr_lock);
724         int ret = __handle_page_fault(p, va, prot);
725         spin_unlock(&p->vmr_lock);
726         return ret;
727 }
728
729 /* Returns 0 on success, or an appropriate -error code.  Assumes you hold the
730  * vmr_lock.
731  *
732  * Notes: if your TLB caches negative results, you'll need to flush the
733  * appropriate tlb entry.  Also, you could have a weird race where a present PTE
734  * faulted for a different reason (was mprotected on another core), and the
735  * shootdown is on its way.  Userspace should have waited for the mprotect to
736  * return before trying to write (or whatever), so we don't care and will fault
737  * them. */
738 int __handle_page_fault(struct proc *p, uintptr_t va, int prot)
739 {
740         struct vm_region *vmr;
741         struct page *a_page;
742         unsigned int f_idx;     /* index of the missing page in the file */
743         int retval;
744         pte_t *pte;
745
746         /* Check the vmr's protection */
747         vmr = find_vmr(p, va);
748         if (!vmr)                                                       /* not mapped at all */
749                 return -EFAULT;
750         if (!(vmr->vm_prot & prot))                     /* wrong prots for this vmr */
751                 return -EPERM;
752         if (!vmr->vm_file) {
753                 /* No file - just want anonymous memory */
754                 if (upage_alloc(p, &a_page, TRUE))
755                         return -ENOMEM;
756         } else {
757                 /* If this fails, either something got screwed up with the VMR, or the
758                  * permissions changed after mmap/mprotect.  Either way, I want to know
759                  * (though it's not critical). */
760                 if (!check_file_perms(vmr, vmr->vm_file, prot))
761                         printk("[kernel] possible issue with VMR prots on file %s!\n",
762                                file_name(vmr->vm_file));
763                 /* Load the file's page in the page cache.
764                  * TODO: (BLK) Note, we are holding the mem lock!  We need to rewrite
765                  * this stuff so we aren't hold the lock as excessively as we are, and
766                  * such that we can block and resume later. */
767                 assert(!PGOFF(va - vmr->vm_base + vmr->vm_foff));
768                 f_idx = (va - vmr->vm_base + vmr->vm_foff) >> PGSHIFT;
769                 /* TODO: need some sort of lock on the file to deal with someone
770                  * concurrently shrinking it.  Adding 1 to f_idx, since it is
771                  * zero-indexed */
772                 if (f_idx + 1 > nr_pages(vmr->vm_file->f_dentry->d_inode->i_size)) {
773                         /* We're asking for pages that don't exist in the file */
774                         /* TODO: unlock the file */
775                         return -ESPIPE; /* linux sends a SIGBUS at access time */
776                 }
777                 retval = pm_load_page(vmr->vm_file->f_mapping, f_idx, &a_page);
778                 /* TODO: should be able to let go of that file shrink-lock now.  We have
779                  * a page refcnt, which might be enough (depending on how it works) */
780                 if (retval)
781                         return retval;
782                 /* If we want a private map, we'll preemptively give you a new page.  We
783                  * used to just care if it was private and writable, but were running
784                  * into issues with libc changing its mapping (map private, then
785                  * mprotect to writable...)  In the future, we want to CoW this anyway,
786                  * so it's not a big deal. */
787                 if ((vmr->vm_flags & MAP_PRIVATE)) {
788                         struct page *cache_page = a_page;
789                         if (upage_alloc(p, &a_page, FALSE)) {
790                                 page_decref(cache_page);        /* was the original a_page */
791                                 return -ENOMEM;
792                         }
793                         memcpy(page2kva(a_page), page2kva(cache_page), PGSIZE);
794                         page_decref(cache_page);                /* was the original a_page */
795                         /* Debugging */
796                         if (!(vmr->vm_prot & PROT_WRITE))
797                                 printd("[kernel] private, but unwritable file mapping of %s "
798                                        "at va %p\n", file_name(vmr->vm_file), va);
799                 }
800                 /* if this is an executable page, we might have to flush the instruction
801                  * cache if our HW requires it. */
802                 if (vmr->vm_prot & PROT_EXEC)
803                         icache_flush_page((void*)va, page2kva(a_page));
804         }
805         /* update the page table TODO: careful with MAP_PRIVATE etc.  might do this
806          * separately (file, no file) */
807         int pte_prot = (vmr->vm_prot & PROT_WRITE) ? PTE_USER_RW :
808                        (vmr->vm_prot & (PROT_READ|PROT_EXEC)) ? PTE_USER_RO : 0;
809         spin_lock(&p->pte_lock);        /* walking and changing PTEs */
810         /* find offending PTE (prob don't read this in).  This might alloc an
811          * intermediate page table page. */
812         pte = pgdir_walk(p->env_pgdir, (void*)va, 1);
813         if (!pte) {
814                 spin_unlock(&p->pte_lock);
815                 pm_put_page(a_page);
816                 return -ENOMEM;
817         }
818         /* a spurious, valid PF is possible due to a legit race: the page might have
819          * been faulted in by another core already (and raced on the memory lock),
820          * in which case we should just return. */
821         if (PAGE_PRESENT(*pte)) {
822                 spin_unlock(&p->pte_lock);
823                 pm_put_page(a_page);
824                 return 0;
825         } else if (PAGE_PAGED_OUT(*pte)) {
826                 /* TODO: (SWAP) bring in the paged out frame. (BLK) */
827                 panic("Swapping not supported!");
828                 spin_unlock(&p->pte_lock);
829                 pm_put_page(a_page);
830                 return -1;
831         }
832         /* We have a ref to a_page, which we are storing in the PTE */
833         *pte = PTE(page2ppn(a_page), PTE_P | pte_prot);
834         spin_unlock(&p->pte_lock);
835         return 0;
836 }
837
838 /* Kernel Dynamic Memory Mappings */
839 uintptr_t dyn_vmap_llim = KERN_DYN_TOP;
840 spinlock_t dyn_vmap_lock = SPINLOCK_INITIALIZER;
841
842 /* Reserve space in the kernel dynamic memory map area */
843 uintptr_t get_vmap_segment(unsigned long num_pages)
844 {
845         uintptr_t retval;
846         spin_lock(&dyn_vmap_lock);
847         retval = dyn_vmap_llim - num_pages * PGSIZE;
848         if ((retval > ULIM) && (retval < KERN_DYN_TOP)) {
849                 dyn_vmap_llim = retval;
850         } else {
851                 warn("[kernel] dynamic mapping failed!");
852                 retval = 0;
853         }
854         spin_unlock(&dyn_vmap_lock);
855         return retval;
856 }
857
858 /* Give up your space.  Note this isn't supported yet */
859 uintptr_t put_vmap_segment(uintptr_t vaddr, unsigned long num_pages)
860 {
861         /* TODO: use vmem regions for adjustable vmap segments */
862         warn("Not implemented, leaking vmem space.\n");
863         return 0;
864 }
865
866 /* Map a virtual address chunk to physical addresses.  Make sure you got a vmap
867  * segment before actually trying to do the mapping.
868  *
869  * Careful with more than one 'page', since it will assume your physical pages
870  * are also contiguous.  Most callers will only use one page.
871  *
872  * Finally, note that this does not care whether or not there are real pages
873  * being mapped, and will not attempt to incref your page (if there is such a
874  * thing).  Handle your own refcnting for pages. */
875 int map_vmap_segment(uintptr_t vaddr, uintptr_t paddr, unsigned long num_pages,
876                      int perm)
877 {
878         /* For now, we only handle the root pgdir, and not any of the other ones
879          * (like for processes).  To do so, we'll need to insert into every pgdir,
880          * and send tlb shootdowns to those that are active (which we don't track
881          * yet). */
882         extern int booting;
883         assert(booting);
884
885         /* TODO: (MM) you should lock on boot pgdir modifications.  A vm region lock
886          * isn't enough, since there might be a race on outer levels of page tables.
887          * For now, we'll just use the dyn_vmap_lock (which technically works). */
888         spin_lock(&dyn_vmap_lock);
889         pte_t *pte;
890 #ifdef CONFIG_X86
891         perm |= PTE_G;
892 #endif
893         for (int i = 0; i < num_pages; i++) {
894                 pte = pgdir_walk(boot_pgdir, (void*)(vaddr + i * PGSIZE), 1);
895                 if (!pte) {
896                         spin_unlock(&dyn_vmap_lock);
897                         return -ENOMEM;
898                 }
899                 /* You probably should have unmapped first */
900                 if (*pte)
901                         warn("Existing PTE value %p\n", *pte);
902                 *pte = PTE(pa2ppn(paddr + i * PGSIZE), perm);
903         }
904         spin_unlock(&dyn_vmap_lock);
905         return 0;
906 }
907
908 /* Unmaps / 0's the PTEs of a chunk of vaddr space */
909 int unmap_vmap_segment(uintptr_t vaddr, unsigned long num_pages)
910 {
911         /* Not a big deal - won't need this til we do something with kthreads */
912         warn("Incomplete, don't call this yet.");
913         spin_lock(&dyn_vmap_lock);
914         /* TODO: For all pgdirs */
915         pte_t *pte;
916         for (int i = 0; i < num_pages; i++) {
917                 pte = pgdir_walk(boot_pgdir, (void*)(vaddr + i * PGSIZE), 1);
918                 *pte = 0;
919         }
920         /* TODO: TLB shootdown.  Also note that the global flag is set on the PTE
921          * (for x86 for now), which requires a global shootdown.  bigger issue is
922          * the TLB shootdowns for multiple pgdirs.  We'll need to remove from every
923          * pgdir, and send tlb shootdowns to those that are active (which we don't
924          * track yet). */
925         spin_unlock(&dyn_vmap_lock);
926         return 0;
927 }
928
929 uintptr_t vmap_pmem(uintptr_t paddr, size_t nr_bytes)
930 {
931         uintptr_t vaddr;
932         unsigned long nr_pages = ROUNDUP(nr_bytes, PGSIZE) >> PGSHIFT;
933         assert(nr_bytes && paddr);
934         vaddr = get_vmap_segment(nr_pages);
935         if (!vaddr) {
936                 warn("Unable to get a vmap segment");   /* probably a bug */
937                 return 0;
938         }
939         if (map_vmap_segment(vaddr, paddr, nr_pages, PTE_P | PTE_KERN_RW)) {
940                 warn("Unable to map a vmap segment");   /* probably a bug */
941                 return 0;
942         }
943         return vaddr;
944 }
945
946 int vunmap_vmem(uintptr_t vaddr, size_t nr_bytes)
947 {
948         unsigned long nr_pages = ROUNDUP(nr_bytes, PGSIZE) >> PGSHIFT;
949         unmap_vmap_segment(vaddr, nr_pages);
950         put_vmap_segment(vaddr, nr_pages);
951         return 0;
952 }