VM regions: management functions and structs
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 11 Jun 2010 01:26:09 +0000 (18:26 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:48 +0000 (17:35 -0700)
They aren't used for anything yet, and their interface might change a
bit.  Long term, any mapping into an address space should use these.

kern/include/env.h
kern/include/mm.h
kern/include/process.h
kern/include/testing.h
kern/include/vfs.h
kern/src/init.c
kern/src/kfs.c
kern/src/mm.c
kern/src/process.c
kern/src/testing.c

index fb401ba..508751f 100644 (file)
 #include <arch/arch.h>
 #include <sys/queue.h>
 #include <atomic.h>
-
-struct Env;
-typedef struct Env env_t;
+#include <mm.h>
 
 // TODO: clean this up.
-struct Env {
-       TAILQ_ENTRY(Env) proc_link NOINIT;      // Free list link pointers
+struct proc {
+       TAILQ_ENTRY(proc) proc_link NOINIT;     // Free list link pointers
        spinlock_t proc_lock;
        trapframe_t env_tf;                                             // Saved registers
        ancillary_state_t env_ancillary_state;  // State saved when descheduled
@@ -50,7 +48,7 @@ struct Env {
        // Address space
        pde_t *COUNT(NPDENTRIES) env_pgdir;                     // Kernel virtual address of page dir
        physaddr_t env_cr3;                     // Physical address of page dir
-//     struct memregion_list memregions;
+       struct vmr_tailq vm_regions;
 
        // Per process info and data pages
        procinfo_t *SAFE procinfo;       // KVA of per-process shared info table (RO)
@@ -65,6 +63,10 @@ struct Env {
        sysevent_front_ring_t syseventfrontring;
 };
 
+/* Til we remove all Env references */
+#define Env proc
+typedef struct proc env_t;
+
 /* Process Flags */
 #define PROC_TRANSITION_TO_M                   0x0001
 
index 1ec8c61..e03de90 100644 (file)
@@ -11,7 +11,6 @@
 #define ROS_KERN_MM_H
 
 #include <ros/common.h>
-#include <process.h>
 #include <atomic.h>
 #include <sys/queue.h>
 #include <slab.h>
  * will also affect get_free_va_range
  *     - also, do we want a separate brk per?  or just support mmap on private mem?
  */
+struct file;
+struct proc;                                                           /* preprocessor games */
+
+/* Basic structure defining a region of a process's virtual memory */
 struct vm_region {
-       TAILQ_ENTRY(vm_region) link; // actually, i'd like a sorted tree of these
-       uintptr_t base;
-       size_t len;
-       int perm;
+       TAILQ_ENTRY(vm_region)          vm_link;
+       struct proc                                     *vm_proc;       /* owning process, for now */
+       //struct mm                                     *vm_mm;         /* owning address space */
+       uintptr_t                                       vm_base;
+       uintptr_t                                       vm_end;
+       int                                                     vm_perm;        
+       int                                                     vm_flags;       
+       struct file                                     *vm_file;
+       size_t                                          vm_foff;
 };
-TAILQ_HEAD(vm_region_list, vm_region); // Declares 'struct memregion_list'
+TAILQ_HEAD(vmr_tailq, vm_region);                      /* Declares 'struct vmr_tailq' */
+
+#include <process.h>                                           /* preprocessor games */
+
+/* VM Region Management Functions.  For now, these just maintain themselves -
+ * anything related to mapping needs to be done by the caller. */
+void vmr_init(void);
+struct vm_region *create_vmr(struct proc *p, uintptr_t va, size_t len);
+struct vm_region *split_vmr(struct vm_region *vmr, uintptr_t va);
+int merge_vmr(struct vm_region *first, struct vm_region *second);
+int grow_vmr(struct vm_region *vmr, uintptr_t va);
+int shrink_vmr(struct vm_region *vmr, uintptr_t va);
+void destroy_vmr(struct vm_region *vmr);
+struct vm_region *find_vmr(struct proc *p, uintptr_t va);
+struct vm_region *find_first_vmr(struct proc *p, uintptr_t va);
+void print_vmrs(struct proc *p);
 
 // at least for now, we aren't using vm regions. we're storing pointers
 // to pfault_info_t inside the PTEs in an arch-specific way.
-struct file;
 typedef struct pfault_info {
        struct file* file; // or NULL for zero-fill
        size_t pgoff; // offset into file
@@ -83,6 +105,8 @@ struct mm {
        // lists of vm_regions for all contexts
        // base cr3 for all contexts
        // previous brk, last checked vm_region
+       // should also track the num of vm_regions, or think about perverse things
+       // processes can do to gobble up kernel memory
 
 };
 // would rather this be a mm struct
index 99ea1bf..d960dd0 100644 (file)
@@ -52,9 +52,6 @@
 
 #include <env.h>
 
-// Till we remove the old struct Env
-#define proc Env
-
 TAILQ_HEAD(proc_list, proc);           // Declares 'struct proc_list'
 
 extern spinlock_t runnablelist_lock;
index 0caf2f0..e5b1f94 100644 (file)
@@ -28,6 +28,7 @@ void test_slab(void);
 void test_kmalloc(void);
 void test_hashtable(void);
 void test_bcq(void);
+void test_vm_regions(void);
 
 struct trapframe_t;
 
index 0bfb7df..8beb857 100644 (file)
@@ -19,6 +19,7 @@
 #include <atomic.h>
 #include <timing.h>
 #include <page_alloc.h>
+#include <mm.h>
 
 // TODO: temp typedefs, etc.  remove when we support this stuff.
 typedef int dev_t;
@@ -40,7 +41,6 @@ struct inode_operations;
 struct file;
 struct file_operations;
 struct fs_type;
-struct vm_area_struct;
 struct vfsmount;
 
 /* part of the kernel interface, ripped from man pages, ought to work. */
@@ -273,7 +273,7 @@ struct file_operations {
        ssize_t (*read) (struct file *, char *, size_t, off_t *);
        ssize_t (*write) (struct file *, const char *, size_t, off_t *);
        int (*readdir) (struct file *, struct dirent *);
-       int (*mmap) (struct file *, struct vm_area_struct *);
+       int (*mmap) (struct file *, struct vm_region *);
        int (*open) (struct inode *, struct file *);
        int (*flush) (struct file *);
        int (*release) (struct inode *, struct file *);
index 48d8ab6..523a52c 100644 (file)
@@ -75,7 +75,7 @@ void kernel_init(multiboot_info_t *mboot_info)
        hashtable_init();
        cache_color_alloc_init();       // Inits data structs
        colored_page_alloc_init();      // Allocates colors for agnostic processes
-       mmap_init();
+       vmr_init();
        file_init();
        page_check();
        vfs_init();
index 57e778a..76a1720 100644 (file)
@@ -630,9 +630,15 @@ int kfs_readdir(struct file *dir, struct dirent *dirent)
        return 1;                                                       /* normal success for readdir */
 }
 
-/* Memory maps the file into the virtual memory area */
-int kfs_mmap(struct file *file, struct vm_area_struct *vma)
+/* Sets up a memory mapping of the file into the vm_region, based on the
+ * parameters in the vmr. */
+int kfs_mmap(struct file *file, struct vm_region *vmr)
 {
+       /* the file is not page-aligned yet, so we need to copy it to fresh pages.
+        * this should only be done once per SHARED file (inode), so only make fresh
+        * copies if people want new ones.  Also note that MAP_PRIVATE does not get
+        * carried through to the underlying file. */
+
        return -1;
 }
 
index 988f417..675f195 100644 (file)
 #include <syscall.h>
 #include <slab.h>
 #include <kmalloc.h>
+#include <vfs.h>
+
+struct kmem_cache *vmr_kcache;
+struct kmem_cache *pfault_info_cache;
+
+void vmr_init(void)
+{
+       vmr_kcache = kmem_cache_create("vm_regions", sizeof(struct vm_region),
+                                      __alignof__(struct dentry), 0, 0, 0);
+       pfault_info_cache = kmem_cache_create("pfault_info",
+                                             sizeof(pfault_info_t), 8, 0, 0, 0);
+}
+
+/* For now, the caller will set the prot, flags, file, and offset.  In the
+ * future, we may put those in here, to do clever things with merging vm_regions
+ * that are the same.
+ *
+ * TODO: take a look at solari's vmem alloc.  And consider keeping these in a
+ * tree of some sort for easier lookups. */
+struct vm_region *create_vmr(struct proc *p, uintptr_t va, size_t len)
+{
+       struct vm_region *vmr = 0, *vm_i, *vm_link;
+       uintptr_t gap_end;
+
+       /* Don't allow a vm region into the 0'th page (null ptr issues) */
+       if (va == 0)
+               va = 1 * PGSIZE;
+
+       assert(!PGOFF(va));
+       assert(!PGOFF(len));
+       assert(va + len <= USTACKBOT);
+
+       /* Is there room before the first one: */
+       vm_i = TAILQ_FIRST(&p->vm_regions);
+       if (!vm_i || (va + len < vm_i->vm_base)) {
+               vmr = kmem_cache_alloc(vmr_kcache, 0);
+               vmr->vm_base = va;
+               TAILQ_INSERT_HEAD(&p->vm_regions, vmr, vm_link);
+       } else {
+               TAILQ_FOREACH(vm_i, &p->vm_regions, vm_link) {
+                       vm_link = TAILQ_NEXT(vm_i, vm_link); 
+                       gap_end = vm_link ? vm_link->vm_base : USTACKBOT;
+                       /* skip til we get past the 'hint' va */
+                       if (va >= gap_end)
+                               continue;
+                       /* Found a gap that is big enough */
+                       if (gap_end - vm_i->vm_end >= len) {
+                               vmr = kmem_cache_alloc(vmr_kcache, 0);
+                               /* if we can put it at va, let's do that.  o/w, put it so it
+                                * fits */
+                               if (gap_end >= va + len)
+                                       vmr->vm_base = va;
+                               else
+                                       vmr->vm_base = vm_i->vm_end;
+                               TAILQ_INSERT_AFTER(&p->vm_regions, vm_i, vmr, vm_link);
+                               break;
+                       }
+               }
+       }
+       /* Finalize the creation, if we got one */
+       if (vmr) {
+               vmr->vm_proc = p;
+               vmr->vm_end = vmr->vm_base + len;
+       }
+       return vmr;
+}
+
+/* Split a VMR at va, returning the new VMR.  It is set up the same way, with
+ * file offsets fixed accordingly.  'va' is the beginning of the new one, and
+ * must be page aligned. */
+struct vm_region *split_vmr(struct vm_region *old_vmr, uintptr_t va)
+{
+       struct vm_region *new_vmr;
+
+       assert(!PGOFF(va));
+       if ((old_vmr->vm_base >= va) || (old_vmr->vm_end <= va))
+               return 0;
+       new_vmr = kmem_cache_alloc(vmr_kcache, 0);
+       TAILQ_INSERT_AFTER(&old_vmr->vm_proc->vm_regions, old_vmr, new_vmr,
+                          vm_link);
+       new_vmr->vm_proc = old_vmr->vm_proc;
+       new_vmr->vm_base = va;
+       new_vmr->vm_end = old_vmr->vm_end;
+       old_vmr->vm_end = va;
+       new_vmr->vm_perm = old_vmr->vm_perm;
+       new_vmr->vm_flags = old_vmr->vm_flags;
+       if (old_vmr->vm_file) {
+               new_vmr->vm_file = old_vmr->vm_file;
+               atomic_inc(&new_vmr->vm_file->f_refcnt);
+               new_vmr->vm_foff = old_vmr->vm_foff +
+                                     old_vmr->vm_end - old_vmr->vm_base;
+       } else {
+               new_vmr->vm_file = 0;
+               new_vmr->vm_foff = 0;
+       }
+       return new_vmr;
+}
+
+/* Merges two vm regions.  For now, it will check to make sure they are the
+ * same.  The second one will be destroyed. */
+int merge_vmr(struct vm_region *first, struct vm_region *second)
+{
+       assert(first->vm_proc == second->vm_proc);
+       if ((first->vm_end != second->vm_base) ||
+           (first->vm_perm != second->vm_perm) ||
+           (first->vm_flags != second->vm_flags) ||
+           (first->vm_file != second->vm_file))
+               return -1;
+       if ((first->vm_file) && (second->vm_foff != first->vm_foff +
+                                first->vm_end - first->vm_base))
+               return -1;
+       first->vm_end = second->vm_end;
+       destroy_vmr(second);
+       return 0;
+}
+
+/* Grows the vm region up to (and not including) va.  Fails if another is in the
+ * way, etc. */
+int grow_vmr(struct vm_region *vmr, uintptr_t va)
+{
+       assert(!PGOFF(va));
+       struct vm_region *next = TAILQ_NEXT(vmr, vm_link);
+       if (next && next->vm_base < va)
+               return -1;
+       if (va <= vmr->vm_end)
+               return -1;
+       vmr->vm_end = va;
+       return 0;
+}
+
+/* Shrinks the vm region down to (and not including) va.  Whoever calls this
+ * will need to sort out the page table entries. */
+int shrink_vmr(struct vm_region *vmr, uintptr_t va)
+{
+       assert(!PGOFF(va));
+       if ((va < vmr->vm_base) || (va > vmr->vm_end))
+               return -1;
+       vmr->vm_end = va;
+       return 0;
+}
+
+/* Called by the unmapper, just cleans up.  Whoever calls this will need to sort
+ * out the page table entries. */
+void destroy_vmr(struct vm_region *vmr)
+{
+       if (vmr->vm_file)
+               atomic_dec(&vmr->vm_file->f_refcnt);
+       TAILQ_REMOVE(&vmr->vm_proc->vm_regions, vmr, vm_link);
+       kmem_cache_free(vmr_kcache, vmr);
+}
+
+/* Given a va and a proc (later an mm, possibly), returns the owning vmr, or 0
+ * if there is none. */
+struct vm_region *find_vmr(struct proc *p, uintptr_t va)
+{
+       struct vm_region *vmr;
+       /* ugly linear seach */
+       TAILQ_FOREACH(vmr, &p->vm_regions, vm_link) {
+               if ((vmr->vm_base <= va) && (vmr->vm_end > va))
+                       return vmr;
+       }
+       return 0;
+}
+
+/* Finds the first vmr after va (including the one holding va), or 0 if there is
+ * none. */
+struct vm_region *find_first_vmr(struct proc *p, uintptr_t va)
+{
+       struct vm_region *vmr;
+       /* ugly linear seach */
+       TAILQ_FOREACH(vmr, &p->vm_regions, vm_link) {
+               if ((vmr->vm_base <= va) && (vmr->vm_end > va))
+                       return vmr;
+               if (vmr->vm_base > va)
+                       return vmr;
+       }
+       return 0;
+}
+
+void print_vmrs(struct proc *p)
+{
+       int count = 0;
+       struct vm_region *vmr;
+       printk("VM Regions for proc %d\n", p->pid);
+       TAILQ_FOREACH(vmr, &p->vm_regions, vm_link)
+               printk("%02d: (0x%08x - 0x%08x)\n", count++, vmr->vm_base, vmr->vm_end);
+}
+
 
 void *mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
            int fd, size_t offset)
@@ -60,6 +248,7 @@ void *do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
        return ret;
 }
 
+/* Consider moving the top half of this to another function, like mmap(). */
 void *__do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
                 struct file* file, size_t offset)
 {
@@ -69,8 +258,11 @@ void *__do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
        flags |= MAP_POPULATE;
 #endif
        
+       /* TODO: if FIXED, need to handle overlap on another region */
        if(!(flags & MAP_FIXED))
        {
+               /* this should be arch indep, and once we add the new region to the
+                * list, this won't think the region is free */
                addr = (uintptr_t)get_free_va_range(p->env_pgdir,addr,len);
                if(!addr)
                        goto mmap_abort;
@@ -78,6 +270,13 @@ void *__do_mmap(struct proc *p, uintptr_t addr, size_t len, int prot, int flags,
                assert(!PGOFF(addr));
                assert(addr + num_pages*PGSIZE <= USTACKBOT);
        }
+       #if 0
+       struct vm_region *vmr = create_vmr(p, addr, len);
+       vmr->vm_perm = prot;
+       vmr->vm_flags = flags;
+       vmr->vm_file = file;
+       vmr->vm_foff = offset;
+       #endif
 
        // get a list of pfault_info_t's and pte's a priori,
        // because if their allocation fails, we could end up
@@ -330,13 +529,6 @@ out:
        return ret;
 }
 
-struct kmem_cache* pfault_info_cache;
-void mmap_init(void)
-{
-       pfault_info_cache = kmem_cache_create("pfault_info",
-                                             sizeof(pfault_info_t), 8, 0, 0, 0);
-}
-
 pfault_info_t* pfault_info_alloc(struct file* file)
 {
        if(file)
@@ -350,4 +542,3 @@ void pfault_info_free(pfault_info_t* pfi)
                file_decref(pfi->file);
        kmem_cache_free(pfault_info_cache,pfi);
 }
-
index 34ec812..0247a42 100644 (file)
@@ -284,6 +284,7 @@ static error_t proc_alloc(struct proc *SAFE*SAFE pp, pid_t parent_id)
        memset(&p->resources, 0, sizeof(p->resources));
        memset(&p->env_ancillary_state, 0, sizeof(p->env_ancillary_state));
        memset(&p->env_tf, 0, sizeof(p->env_tf));
+       TAILQ_INIT(&p->vm_regions); /* could init this in the slab */
 
        /* Initialize the contents of the e->procinfo structure */
        proc_init_procinfo(p);
index b72b03e..9dd343d 100644 (file)
@@ -933,3 +933,119 @@ void test_bcq(void)
        }
        
 }
+
+/* rudimentary tests.  does the basics, create, merge, split, etc.  Feel free to
+ * add more, esp for the error conditions and finding free slots.  This is also
+ * a bit lazy with setting the caller's fields (perm, flags, etc). */
+void test_vm_regions(void)
+{
+       #define MAX_VMR_TESTS 10
+       struct proc pr, *p = &pr;       /* too lazy to even create one */
+       int n = 0;
+       TAILQ_INIT(&p->vm_regions);
+
+       struct vmr_summary {
+               uintptr_t base; 
+               uintptr_t end; 
+       };
+       int check_vmrs(struct proc *p, struct vmr_summary *results, int len, int n)
+       {
+               int count = 0;
+               struct vm_region *vmr;
+               TAILQ_FOREACH(vmr, &p->vm_regions, vm_link) {
+                       if (count >= len) {
+                               printk("More vm_regions than expected\n");
+                               break;
+                       }
+                       if ((vmr->vm_base != results[count].base) ||
+                           (vmr->vm_end != results[count].end)) {
+                               printk("VM test case %d failed!\n", n);
+                               print_vmrs(p);
+                               return -1;
+                       }
+                       count++;
+               }
+               return count;
+       }
+       struct vm_region *vmrs[MAX_VMR_TESTS];
+       struct vmr_summary results[MAX_VMR_TESTS];
+
+       memset(results, 0, sizeof(results));
+       /* Make one */
+       vmrs[0] = create_vmr(p, 0x2000, 0x1000);
+       results[0].base = 0x2000;
+       results[0].end = 0x3000;
+       check_vmrs(p, results, 1, n++);
+       /* Grow it */
+       grow_vmr(vmrs[0], 0x4000);
+       results[0].base = 0x2000;
+       results[0].end = 0x4000;
+       check_vmrs(p, results, 1, n++);
+       /* Grow it poorly */
+       if (-1 != grow_vmr(vmrs[0], 0x3000))
+               printk("Bad grow test failed\n");
+       check_vmrs(p, results, 1, n++);
+       /* Make another right next to it */
+       vmrs[1] = create_vmr(p, 0x4000, 0x1000);
+       results[1].base = 0x4000;
+       results[1].end = 0x5000;
+       check_vmrs(p, results, 2, n++);
+       /* try to grow through it */
+       if (-1 != grow_vmr(vmrs[0], 0x5000))
+               printk("Bad grow test failed\n");
+       check_vmrs(p, results, 2, n++);
+       /* Merge them */
+       merge_vmr(vmrs[0], vmrs[1]);
+       results[0].end = 0x5000;
+       results[1].base = 0;
+       results[1].end = 0;
+       check_vmrs(p, results, 1, n++);
+       vmrs[1]= create_vmr(p, 0x6000, 0x4000);
+       results[1].base = 0x6000;
+       results[1].end = 0xa000;
+       check_vmrs(p, results, 2, n++);
+       /* try to merge unmergables (just testing ranges) */
+       if (-1 != merge_vmr(vmrs[0], vmrs[1]))
+               printk("Bad merge test failed\n");
+       check_vmrs(p, results, 2, n++);
+       vmrs[2] = split_vmr(vmrs[1], 0x8000);
+       results[1].end = 0x8000;
+       results[2].base = 0x8000;
+       results[2].end = 0xa000;
+       check_vmrs(p, results, 3, n++);
+       /* destroy one */
+       destroy_vmr(vmrs[1]);
+       results[1].base = 0x8000;
+       results[1].end = 0xa000;
+       check_vmrs(p, results, 2, n++);
+       /* shrink */
+       shrink_vmr(vmrs[2], 0x9000);
+       results[1].base = 0x8000;
+       results[1].end = 0x9000;
+       check_vmrs(p, results, 2, n++);
+       if (vmrs[2] != find_vmr(p, 0x8500))
+               printk("Failed to find the right vmr!");
+       if (vmrs[2] != find_first_vmr(p, 0x8500))
+               printk("Failed to find the right vmr!");
+       if (vmrs[2] != find_first_vmr(p, 0x7500))
+               printk("Failed to find the right vmr!");
+       if (find_first_vmr(p, 0x9500))
+               printk("Found a vmr when we shouldn't!\n");
+       /* grow up to another */
+       grow_vmr(vmrs[0], 0x8000);
+       results[0].end = 0x8000;
+       check_vmrs(p, results, 2, n++);
+       vmrs[0]->vm_perm = 88;
+       vmrs[2]->vm_perm = 77;
+       /* should be unmergeable due to perms */
+       if (-1 != merge_vmr(vmrs[0], vmrs[2]))
+               printk("Bad merge test failed\n");
+       check_vmrs(p, results, 2, n++);
+       /* should merge now */
+       vmrs[2]->vm_perm = 88;
+       merge_vmr(vmrs[0], vmrs[2]);
+       results[0].end = 0x9000;
+       check_vmrs(p, results, 1, n++);
+
+       printk("Finished vm_regions test!\n");
+}