vmap: Use an arena allocator for kernel vmaps
authorBarret Rhoden <brho@cs.berkeley.edu>
Sun, 27 Nov 2016 15:12:36 +0000 (10:12 -0500)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 29 Nov 2016 16:27:40 +0000 (11:27 -0500)
The kernel has a region of virtual addresses that are not mapped 1:1
with physical memory (which is the KERNBASE mapping).  We currently use
these for MMIO remapping, such as when a device wants an uncached
mapping.

Previously, we were using a homemade incremental allocator to manage the
virtual addresses and did not have a nice way to free the addresses.
Now, we have an arena allocator that also allows us to free the vmaps.
We use two arenas and the outer arena's free-func to free the vmaps in
batches, amortizing the overhead of the global TLB shootdown.

Note that there are a couple things to do still for safe unmappings at
runtime.  Specifically, we need to make sure that all PML4s in the
system always have the same contents as boot_pgdir for the vmap region.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/arch/riscv/ros/mmu.h
kern/arch/x86/ros/mmu64.h
kern/include/mm.h
kern/src/init.c
kern/src/mm.c

index 28c16dc..d8bf3bb 100644 (file)
 # define PTSIZE                   L1PGSIZE
 #endif
 
 # define PTSIZE                   L1PGSIZE
 #endif
 
-/* All arches must define this, which is the lower limit of their static
- * mappings, and where the dynamic mappings will start. */
+/* This is the range of the dynamic virtual mappings. */
 #define KERN_DYN_TOP    KERNBASE
 #define KERN_DYN_TOP    KERNBASE
+#warning "pick a better DYN_BOT"
+#define KERN_DYN_BOT   ULIM
 
 /* **************************************** */
 /* Page table constants, macros, etc */
 
 /* **************************************** */
 /* Page table constants, macros, etc */
index 7c120bd..a18c7f2 100644 (file)
@@ -34,19 +34,19 @@ typedef struct x86_pgdir {
  *                     |            IOAPIC            | RW/--  APIC_SIZE (1MB)
  *                     |                              |
  *   IOAPIC_BASE  -->  +------------------------------+ 0xffffffffbff00000
  *                     |            IOAPIC            | RW/--  APIC_SIZE (1MB)
  *                     |                              |
  *   IOAPIC_BASE  -->  +------------------------------+ 0xffffffffbff00000
+ *                     :                              :
+ *                     |          Unmapped            | --/--
  *                     |                              |
  *                     |                              |
- *                     |                              | RW/--  APIC_SIZE (1MB)
- *                     |                              |
- *   KERN_DYN_TOP -->  +------------------------------+ 0xffffffffbfe00000
+ *                     |  Kernel static linking limit |
+ *   KERN_DYN_TOP -->  +------------------------------+ 0xffffffff80000000
  *                     |   Kernel Dynamic Mappings    |
  *                     |              .               |
  *                     :              .               :
  *                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ RW/--
  *                     |   Kernel Dynamic Mappings    |
  *                     |              .               |
  *                     :              .               :
  *                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ RW/--
- *                     :                              :
- *                     |          Unmapped            | --/--
- *                     |                              |
- *                     |  Kernel static linking limit |
- *                     +------------------------------+ 0xffffffff80000000
+ *                     |              .               |
+ *                     |              .               |
+ *                     |              .               |
+ *   KERN_DYN_BOT -->  +------------------------------+ 0xfffffff000000000
  *                     |                              |
  *                     |                              |
  *                     |                              |
  *                     |                              |
  *                     |                              |
  *                     |                              |
@@ -164,9 +164,9 @@ typedef struct x86_pgdir {
 /* Static kernel mappings */
 #define APIC_SIZE              0x100000
 #define IOAPIC_BASE            (KERN_LOAD_ADDR - APIC_SIZE)
 /* Static kernel mappings */
 #define APIC_SIZE              0x100000
 #define IOAPIC_BASE            (KERN_LOAD_ADDR - APIC_SIZE)
-/* All arches must define this, which is the lower limit of their static
- * mappings, and where the dynamic mappings will start. */
-#define KERN_DYN_TOP   IOAPIC_BASE
+/* This is the range of the dynamic virtual mappings. */
+#define KERN_DYN_TOP   0xffffffff80000000
+#define KERN_DYN_BOT   0xfffffff000000000
 
 /* Virtual page table.  Every PML4 has a PTE at the slot (PML4(VPT))
  * corresponding to VPT that points to that PML4's base.  In essence, the 512
 
 /* Virtual page table.  Every PML4 has a PTE at the slot (PML4(VPT))
  * corresponding to VPT that points to that PML4's base.  In essence, the 512
index 6d7ab1c..2a9813d 100644 (file)
@@ -74,14 +74,16 @@ int __do_mprotect(struct proc *p, uintptr_t addr, size_t len, int prot);
 int __do_munmap(struct proc *p, uintptr_t addr, size_t len);
 
 /* Kernel Dynamic Memory Mappings */
 int __do_munmap(struct proc *p, uintptr_t addr, size_t len);
 
 /* Kernel Dynamic Memory Mappings */
-/* These two are just about reserving VA space */
-uintptr_t get_vmap_segment(unsigned long num_pages);
-uintptr_t put_vmap_segment(uintptr_t vaddr, unsigned long num_pages);
-/* These two are about actually mapping stuff in some reserved space */
+struct arena *vmap_arena;
+void vmap_init(void);
+/* Gets PML1 page-aligned virtual addresses for the kernel's dynamic vmap.
+ * You'll need to map it to something.  When you're done, 'put-' will also unmap
+ * the vaddr for you. */
+uintptr_t get_vmap_segment(size_t nr_bytes);
+void put_vmap_segment(uintptr_t vaddr, size_t nr_bytes);
 int map_vmap_segment(uintptr_t vaddr, uintptr_t paddr, unsigned long num_pages,
                      int perm);
 int map_vmap_segment(uintptr_t vaddr, uintptr_t paddr, unsigned long num_pages,
                      int perm);
-int unmap_vmap_segment(uintptr_t vaddr, unsigned long num_pages);
-/* Helper wrappers, since no one will probably call the *_segment funcs */
+/* Helper wrappers for getting and mapping a specific paddr. */
 uintptr_t vmap_pmem(uintptr_t paddr, size_t nr_bytes);
 uintptr_t vmap_pmem_nocache(uintptr_t paddr, size_t nr_bytes);
 uintptr_t vmap_pmem_writecomb(uintptr_t paddr, size_t nr_bytes);
 uintptr_t vmap_pmem(uintptr_t paddr, size_t nr_bytes);
 uintptr_t vmap_pmem_nocache(uintptr_t paddr, size_t nr_bytes);
 uintptr_t vmap_pmem_writecomb(uintptr_t paddr, size_t nr_bytes);
index 50bb32a..ec18d95 100644 (file)
@@ -142,6 +142,7 @@ void kernel_init(multiboot_info_t *mboot_info)
        num_cores = get_early_num_cores();
        pmem_init(multiboot_kaddr);
        kmalloc_init();
        num_cores = get_early_num_cores();
        pmem_init(multiboot_kaddr);
        kmalloc_init();
+       vmap_init();
        hashtable_init();
        radix_init();
        acpiinit();
        hashtable_init();
        radix_init();
        acpiinit();
index b8f27e1..c10bf34 100644 (file)
@@ -1160,31 +1160,90 @@ unsigned long populate_va(struct proc *p, uintptr_t va, unsigned long nr_pgs)
 }
 
 /* Kernel Dynamic Memory Mappings */
 }
 
 /* Kernel Dynamic Memory Mappings */
-uintptr_t dyn_vmap_llim = KERN_DYN_TOP;
-spinlock_t dyn_vmap_lock = SPINLOCK_INITIALIZER;
 
 
-/* Reserve space in the kernel dynamic memory map area */
-uintptr_t get_vmap_segment(unsigned long num_pages)
+static struct arena *vmap_addr_arena;
+struct arena *vmap_arena;
+static spinlock_t vmap_lock = SPINLOCK_INITIALIZER;
+struct vmap_free_tracker {
+       void                                            *addr;
+       size_t                                          nr_bytes;
+};
+static struct vmap_free_tracker *vmap_to_free;
+static size_t vmap_nr_to_free;
+/* This value tunes the ratio of global TLB shootdowns to __vmap_free()s. */
+#define VMAP_MAX_TO_FREE 1000
+
+/* Unmaps / 0's the PTEs of a chunk of vaddr space.  Caller needs to send a
+ * global TLB shootdown before freeing the vaddr. */
+static int __unmap_vmap_segment(uintptr_t vaddr, unsigned long num_pages)
 {
 {
-       uintptr_t retval;
-       spin_lock(&dyn_vmap_lock);
-       retval = dyn_vmap_llim - num_pages * PGSIZE;
-       if ((retval > ULIM) && (retval < KERN_DYN_TOP)) {
-               dyn_vmap_llim = retval;
-       } else {
-               warn("[kernel] dynamic mapping failed!");
-               retval = 0;
+       pte_t pte;
+
+       for (int i = 0; i < num_pages; i++) {
+               pte = pgdir_walk(boot_pgdir, (void*)(vaddr + i * PGSIZE), 1);
+               if (pte_walk_okay(pte))
+                       pte_clear(pte);
        }
        }
-       spin_unlock(&dyn_vmap_lock);
-       return retval;
+       return 0;
 }
 
 }
 
-/* Give up your space.  Note this isn't supported yet */
-uintptr_t put_vmap_segment(uintptr_t vaddr, unsigned long num_pages)
+/* We don't immediately return the addrs to their source (vmap_addr_arena).
+ * Instead, we hold on to them until we have a suitable amount, then free them
+ * in a batch.  This amoritizes the cost of the TLB global shootdown.  We can
+ * explore other tricks in the future too (like RCU for a certain index in the
+ * vmap_to_free array). */
+static void __vmap_free(struct arena *source, void *obj, size_t size)
 {
 {
-       /* TODO: use vmem regions for adjustable vmap segments */
-       warn("Not implemented, leaking vmem space.\n");
-       return 0;
+       unsigned long nr_pages;
+       struct vmap_free_tracker *vft;
+
+       nr_pages = ROUNDUP(size, PGSIZE) >> PGSHIFT;
+       spin_lock(&vmap_lock);
+       /* All objs get *unmapped* immediately, but we'll shootdown later.  Note
+        * that it is OK (but slightly dangerous) for the kernel to reuse the paddrs
+        * pointed to by the vaddrs before a TLB shootdown. */
+       __unmap_vmap_segment((uintptr_t)obj, nr_pages);
+       if (vmap_nr_to_free < VMAP_MAX_TO_FREE) {
+               vft = &vmap_to_free[vmap_nr_to_free++];
+               vft->addr = obj;
+               vft->nr_bytes = size;
+               spin_unlock(&vmap_lock);
+               return;
+       }
+       tlb_shootdown_global();
+       for (int i = 0; i < vmap_nr_to_free; i++) {
+               vft = &vmap_to_free[i];
+               arena_free(source, vft->addr, vft->nr_bytes);
+       }
+       /* don't forget to free the one passed in */
+       arena_free(source, obj, size);
+       vmap_nr_to_free = 0;
+       spin_unlock(&vmap_lock);
+}
+
+void vmap_init(void)
+{
+       vmap_addr_arena = arena_create("vmap_addr", (void*)KERN_DYN_BOT,
+                                      KERN_DYN_TOP - KERN_DYN_BOT,
+                                      PGSIZE, NULL, NULL, NULL, 0, MEM_WAIT);
+       vmap_arena = arena_create("vmap", NULL, 0, PGSIZE, arena_alloc, __vmap_free,
+                                 vmap_addr_arena, 0, MEM_WAIT);
+       vmap_to_free = kmalloc(sizeof(struct vmap_free_tracker) * VMAP_MAX_TO_FREE,
+                              MEM_WAIT);
+}
+
+uintptr_t get_vmap_segment(size_t nr_bytes)
+{
+       uintptr_t ret;
+
+       ret = (uintptr_t)arena_alloc(vmap_arena, nr_bytes, MEM_ATOMIC);
+       assert(ret);
+       return ret;
+}
+
+void put_vmap_segment(uintptr_t vaddr, size_t nr_bytes)
+{
+       arena_free(vmap_arena, (void*)vaddr, nr_bytes);
 }
 
 /* Map a virtual address chunk to physical addresses.  Make sure you got a vmap
 }
 
 /* Map a virtual address chunk to physical addresses.  Make sure you got a vmap
@@ -1207,8 +1266,8 @@ int map_vmap_segment(uintptr_t vaddr, uintptr_t paddr, unsigned long num_pages,
 
        /* TODO: (MM) you should lock on boot pgdir modifications.  A vm region lock
         * isn't enough, since there might be a race on outer levels of page tables.
 
        /* TODO: (MM) you should lock on boot pgdir modifications.  A vm region lock
         * isn't enough, since there might be a race on outer levels of page tables.
-        * For now, we'll just use the dyn_vmap_lock (which technically works). */
-       spin_lock(&dyn_vmap_lock);
+        * For now, we'll just use the vmap_lock (which technically works). */
+       spin_lock(&vmap_lock);
        pte_t pte;
 #ifdef CONFIG_X86
        perm |= PTE_G;
        pte_t pte;
 #ifdef CONFIG_X86
        perm |= PTE_G;
@@ -1216,7 +1275,7 @@ int map_vmap_segment(uintptr_t vaddr, uintptr_t paddr, unsigned long num_pages,
        for (int i = 0; i < num_pages; i++) {
                pte = pgdir_walk(boot_pgdir, (void*)(vaddr + i * PGSIZE), 1);
                if (!pte_walk_okay(pte)) {
        for (int i = 0; i < num_pages; i++) {
                pte = pgdir_walk(boot_pgdir, (void*)(vaddr + i * PGSIZE), 1);
                if (!pte_walk_okay(pte)) {
-                       spin_unlock(&dyn_vmap_lock);
+                       spin_unlock(&vmap_lock);
                        return -ENOMEM;
                }
                /* You probably should have unmapped first */
                        return -ENOMEM;
                }
                /* You probably should have unmapped first */
@@ -1224,29 +1283,7 @@ int map_vmap_segment(uintptr_t vaddr, uintptr_t paddr, unsigned long num_pages,
                        warn("Existing PTE value %p\n", pte_print(pte));
                pte_write(pte, paddr + i * PGSIZE, perm);
        }
                        warn("Existing PTE value %p\n", pte_print(pte));
                pte_write(pte, paddr + i * PGSIZE, perm);
        }
-       spin_unlock(&dyn_vmap_lock);
-       return 0;
-}
-
-/* Unmaps / 0's the PTEs of a chunk of vaddr space */
-int unmap_vmap_segment(uintptr_t vaddr, unsigned long num_pages)
-{
-       /* Not a big deal - won't need this til we do something with kthreads */
-       warn("Incomplete, don't call this yet.");
-       spin_lock(&dyn_vmap_lock);
-       /* TODO: For all pgdirs */
-       pte_t pte;
-       for (int i = 0; i < num_pages; i++) {
-               pte = pgdir_walk(boot_pgdir, (void*)(vaddr + i * PGSIZE), 1);
-               if (pte_walk_okay(pte))
-                       pte_clear(pte);
-       }
-       /* TODO: TLB shootdown.  Also note that the global flag is set on the PTE
-        * (for x86 for now), which requires a global shootdown.  bigger issue is
-        * the TLB shootdowns for multiple pgdirs.  We'll need to remove from every
-        * pgdir, and send tlb shootdowns to those that are active (which we don't
-        * track yet). */
-       spin_unlock(&dyn_vmap_lock);
+       spin_unlock(&vmap_lock);
        return 0;
 }
 
        return 0;
 }
 
@@ -1255,10 +1292,11 @@ static uintptr_t vmap_pmem_flags(uintptr_t paddr, size_t nr_bytes, int flags)
 {
        uintptr_t vaddr;
        unsigned long nr_pages;
 {
        uintptr_t vaddr;
        unsigned long nr_pages;
+
        assert(nr_bytes && paddr);
        nr_bytes += PGOFF(paddr);
        nr_pages = ROUNDUP(nr_bytes, PGSIZE) >> PGSHIFT;
        assert(nr_bytes && paddr);
        nr_bytes += PGOFF(paddr);
        nr_pages = ROUNDUP(nr_bytes, PGSIZE) >> PGSHIFT;
-       vaddr = get_vmap_segment(nr_pages);
+       vaddr = get_vmap_segment(nr_bytes);
        if (!vaddr) {
                warn("Unable to get a vmap segment");   /* probably a bug */
                return 0;
        if (!vaddr) {
                warn("Unable to get a vmap segment");   /* probably a bug */
                return 0;
@@ -1290,11 +1328,7 @@ uintptr_t vmap_pmem_writecomb(uintptr_t paddr, size_t nr_bytes)
 
 int vunmap_vmem(uintptr_t vaddr, size_t nr_bytes)
 {
 
 int vunmap_vmem(uintptr_t vaddr, size_t nr_bytes)
 {
-       unsigned long nr_pages;
-
        nr_bytes += PGOFF(vaddr);
        nr_bytes += PGOFF(vaddr);
-       nr_pages = ROUNDUP(nr_bytes, PGSIZE) >> PGSHIFT;
-       unmap_vmap_segment(PG_ADDR(vaddr), nr_pages);
-       put_vmap_segment(PG_ADDR(vaddr), nr_pages);
+       put_vmap_segment(PG_ADDR(vaddr), nr_bytes);
        return 0;
 }
        return 0;
 }