Let domain allocator merge, enforce vsalloc page granularity
authorJack Miller <jack@codezen.org>
Tue, 5 Apr 2016 05:26:04 +0000 (00:26 -0500)
committerJack Miller <jack@codezen.org>
Tue, 5 Apr 2016 05:26:04 +0000 (00:26 -0500)
I just couldn't let the 32 byte per alloc overhead stand in the default
case. If calling functions want the domain allocator to track size then
it can arrange to have a different priv pointer for each operation, but
I think this case would be far rarer than the case in which we track the
size elsewhere already (like in the page allocator), or where it's
irrelevant (like I would imagine a port map would be implemented).

Meanwhile, while we change vsalloc to use the offset, clarify the
vsalloc size as pages since virtual addresses can only be assigned with
page granularity.

include/domain.h
include/vsalloc.h
kernel/acpi.c
kernel/apic.c
kernel/vga.c
mm/domain.c
mm/page_alloc.c
mm/vsalloc.c

index ed63f12..dc35181 100644 (file)
@@ -27,15 +27,15 @@ struct domain {
 
 void domain_init(struct domain *domain, u64 min, u64 max);
 
-struct domain_block *domain_alloc(struct domain *domain, u64 size, void *priv);
+struct domain_block *domain_alloc(struct domain *domain, u64 size, void *priv, u32 *offset);
 struct domain_block *domain_alloc_near(struct domain *domain, u64 address,
-                                       u64 size, void *priv);
+                                       u64 size, void *priv, u32 *offset);
 struct domain_block *domain_alloc_address(struct domain *domain, u64 address,
-                                          u64 size, void *priv);
+                                          u64 size, void *priv, u32 *offset);
 
 struct domain_block *domain_search(struct domain *domain, u64 address);
 
-void domain_free(struct domain *domain, u64 address);
+void domain_free(struct domain *domain, u64 address, u64 size);
 
 #define TEST_DOMAIN
 
index 3eceb15..4e4ae6e 100644 (file)
@@ -4,5 +4,5 @@
 
 void vsalloc_init(void);
 
-void *vsalloc(char *name, u64 address_hint, u64 size);
-void vfree(void *address);
+void *vsalloc(char *name, u64 address_hint, u64 pages);
+void vfree(void *address, u64 pages);
index 632cada..6b07cb7 100644 (file)
@@ -162,7 +162,7 @@ void __acpi_handle_table(u32 pa)
     }
 
     unmap_pages((u64) allocation, 1);
-    vfree(allocation);
+    vfree(allocation, PAGE_SIZE);
 }
 
 int acpi_init(void)
@@ -191,7 +191,7 @@ int acpi_init(void)
         goto cleanup;
     }
 
-    hdr = vsalloc("ACPI", 0, PAGE_SIZE);
+    hdr = vsalloc("ACPI", 0, 1);
 
     map_pages((u64) hdr, rsdp->rsdt_pa, 1);
     hdr =
@@ -199,18 +199,17 @@ int acpi_init(void)
                                       PAGE_ALIGN_OFF(rsdp->rsdt_pa));
 
     entries = (u32 *) ((u64) hdr + sizeof(struct description_header));
-    for (i = 0; i < ((hdr->length - sizeof(struct description_header)) / 4);
-         i++)
+    for (i = 0; i < ((hdr->length - sizeof(struct description_header)) / 4); i++)
         __acpi_handle_table(entries[i]);
 
     unmap_pages((u64) hdr, 1);
-    vfree(hdr);
+    vfree(hdr, 1);
 
  cleanup:
     unmap_pages((u64) mem, BIOS_ROM_PAGES);
 
  cleanup_virt:
-    vfree(mem);
+    vfree(mem, BIOS_ROM_PAGES);
 
     return ret;
 }
index d489c4b..75c767b 100644 (file)
@@ -152,7 +152,7 @@ static void xapic_init(void)
     wrmsr(MSR_IA32_APIC_BASE, msr | XAPIC_ENABLE);
 
     /* Get a nocache virtual memory of the base memory */
-    mmio_mem = vsalloc("APIC", VSALLOC_HEAP_VIRTUAL, PAGE_SIZE);
+    mmio_mem = vsalloc("APIC", VSALLOC_HEAP_VIRTUAL, 1);
 
     map_page_nocache((u64) mmio_mem, msr & ~(0xFFFUL));
 
index 8b37e47..ddf5d16 100644 (file)
@@ -52,7 +52,7 @@ void vga_clear(void)
 
 void vga_init(void)
 {
-    vga_mem = vsalloc("VGA mem", 0, PAGE_SIZE);
+    vga_mem = vsalloc("VGA mem", 0, 1);
     map_page((u64) vga_mem, 0xB8000);
     vga_clear();
 }
index a494f7e..74b553d 100644 (file)
@@ -7,20 +7,6 @@
  * page_alloc_to_virtual to expand the amount of memory it can use which makes
  * it suitable to use as the backend for our virtual address space allocator
  * vsalloc.
- *
- * Now, ideally, this would implement an RB or AVL tree to get that sweet
- * sweet O(log n) operation time, however it's unclear how large these domains
- * are going to get so the CPU time saved by optimizing the lookup may be
- * outweighed by the time spent analyzing the tree.
- *
- * I would implement a binary tree to get the average time, but considering a
- * base case would be linear allocation (i.e. allocated address immediately
- * follows the previous address) the un-balanced tree would almost immediately
- * devolve into a singly-linked list anyway.
- *
- * Anyway... considering there is there literally no such thing as a heavy
- * usecase (yet), I'm not going to solve performance problems that I don't
- * actually have.
  */
 
 #include <kernel.h>
@@ -74,16 +60,25 @@ static inline int __bounds_ok(struct domain *domain, u64 address, u64 end)
     return ((address >= domain->min) && (end <= domain->max));
 }
 
+/* __search is the overall workhorse, finding conflicting blocks and setting
+ * prev / next based on the proper position in the linked list. It takes *sb as
+ * an index to a starting block so callers can continue a search at an offset.
+ * This is used to keep progressive searching (like near_ok allocs) from being
+ * O(n^2).
+ */
+
 static struct domain_block *__search(struct domain *domain, u64 address,
                                      u64 size, s64 * sb,
-                                     struct domain_block **prev)
+                                     struct domain_block **prev,
+                                     struct domain_block **next)
 {
     struct domain_block *ret;
 
     s64 ret_idx;
     s64 prev_idx = -1;
+    s64 next_idx = -1;
 
-    if ((!sb) || (*sb = -1))
+    if ((!sb) || (*sb == -1))
         ret_idx = domain->used_offset;
     else
         ret_idx = *sb;
@@ -104,15 +99,16 @@ static struct domain_block *__search(struct domain *domain, u64 address,
         /* cur is higher than we need */
 
         if (end < ret->address) {
-            *prev = ret;
-            return NULL;
+            next_idx = ret_idx;
+            break;
         }
 
+        next_idx = ret->next;
         goto found;
     }
 
-    /* If we fell out of the above loop, prev_idx has already been
-     * set, and there is no collision
+    /* If we fell out of the above loop, prev/next_idx has already been set,
+     * and there is no collision, so dereference the idxs and return.
      */
 
     ret = NULL;
@@ -123,30 +119,18 @@ static struct domain_block *__search(struct domain *domain, u64 address,
     else
         *prev = NULL;
 
+    if (next_idx >= 0)
+        *next = DB(next_idx);
+    else
+        *next = NULL;
+
     return ret;
 }
 
-static struct domain_block *__alloc(struct domain *domain, u64 address,
-                                    u64 size, u32 near_ok, void *priv)
+static struct domain_block *__newblock(struct domain *domain, struct domain_block *prev, u64 address, u64 end, void *priv)
 {
-    struct domain_block *cur, *prev, *free;
-    u64 end, free_idx;
-    s64 save = -1;
-
-    do {
-        end = address + size - 1;   // -1 because 0 counts (0x1000 at 0x0 = 0x->0xFFF)
-
-        if (!__bounds_ok(domain, address, end))
-            return NULL;
-
-        cur = __search(domain, address, size, &save, &prev);
-
-        if (cur) {
-            if (!near_ok)
-                return NULL;
-            address = cur->end + 1;
-        }
-    } while (cur);
+    struct domain_block *free;
+    s64 free_idx;
 
     if ((domain->free_offset == -1) && (__bump_allocation(domain)))
         return NULL;
@@ -171,31 +155,121 @@ static struct domain_block *__alloc(struct domain *domain, u64 address,
     return free;
 }
 
+static struct domain_block *__alloc(struct domain *domain, u64 address,
+                                    u64 size, u32 near_ok, void *priv, u32 *offset)
+{
+    struct domain_block *cur, *prev, *next;
+    u64 end;
+    s64 save = -1;
+    int merged = 0;
+
+    *offset = 0;
+
+    do {
+        end = address + size - 1;   // -1 because 0 counts (0x1000 at 0x0 = 0x->0xFFF)
+
+        if (!__bounds_ok(domain, address, end))
+            return NULL;
+
+        cur = __search(domain, address, size, &save, &prev, &next);
+
+        if (cur) {
+
+            /* If we had a conflict bail, or continue search */
+
+            if (!near_ok)
+                return NULL;
+            address = cur->end + 1;
+
+        /* If we didn't have a conflict, check if we can merge */
+        } else {
+
+            /* First check if we can merge with previous */
+            if ((prev) && (prev->priv == priv) && (prev->end + 1 == address)) {
+                prev->end += size;
+                *offset = (address - cur->address);
+                merged = 1;
+            }
+
+            if ((next) && (next->priv == priv) && (next->address == end + 1)) {
+                /* if we didn't just merge, just expand this block */
+                if (!merged) {
+                    next->address = address;
+                    next->end += size;
+                    return next;
+
+                /* If we did just merge, expand prev even more and free this block */
+                } else {
+                    prev->end = next->end;
+                    prev->next = next->next;
+
+                    next->next = domain->free_offset;
+                    domain->free_offset = prev->next;
+                    return prev;
+                }
+
+            /* Next wasn't adjacent, but prev still was */
+            } else if (merged)
+                return prev;
+        }
+    } while (cur);
+
+    /* If we got here, we know we have a standalone block, so grab a new one
+     * and patch it in after prev */
+
+    return __newblock(domain, prev, address, end, priv);
+}
+
 static struct domain_block *__alloc_locked(struct domain *domain, u64 address,
-                                           u64 size, u32 near_ok, void *priv)
+                                           u64 size, u32 near_ok, void *priv, u32 *offset)
 {
     struct domain_block *ret;
 
     spinlock_lock(&domain->lock);
 
-    ret = __alloc(domain, address, size, near_ok, priv);
+    ret = __alloc(domain, address, size, near_ok, priv, offset);
 
     spinlock_unlock(&domain->lock);
 
     return ret;
 }
 
-void domain_free(struct domain *domain, u64 address)
+void domain_free(struct domain *domain, u64 address, u64 size)
 {
-    struct domain_block *cur, *prev;
-
+    struct domain_block *cur, *prev, *next;
+    u64 end = address + size - 1;
     s64 cur_idx;
 
     spinlock_lock(&domain->lock);
 
-    cur = __search(domain, address, 1, NULL, &prev);
+    cur = __search(domain, address, 1, NULL, &prev, &next);
 
-    if (cur) {
+    if (!cur)
+        goto cleanup;
+
+    if (cur->address < address) {
+        /* If we're in the middle of an allocation, we're can't just shrink the allocation,
+         * we need to split it into two */
+
+        if (cur->end > end) {
+
+            /* If newblock fails we ran out of memory, so err on the side of
+             * caution and leave this section allocated, it's better to leak
+             * the freed memory than to possibly hand out allocated memory
+             * again
+             */
+
+            if(__newblock(domain, prev, cur->address, address, cur->priv) == NULL)
+                goto cleanup;
+
+            cur->address = end;
+        } else
+            cur->end = address;
+    } else if (cur->end > end)
+        cur->address = end;
+
+    /* If we're freeing the entire block, patch it out */
+    else {
         if (prev) {
             cur_idx = prev->next;
             prev->next = cur->next;
@@ -209,38 +283,38 @@ void domain_free(struct domain *domain, u64 address)
         }
     }
 
+cleanup:
     spinlock_unlock(&domain->lock);
 }
 
 struct domain_block *domain_search(struct domain *domain, u64 address)
 {
-    struct domain_block *cur;
-    struct domain_block *prev;
+    struct domain_block *cur, *prev, *next;
 
     spinlock_lock(&domain->lock);
 
-    cur = __search(domain, address, 1, NULL, &prev);
+    cur = __search(domain, address, 1, NULL, &prev, &next);
 
     spinlock_unlock(&domain->lock);
 
     return cur;
 }
 
-struct domain_block *domain_alloc(struct domain *domain, u64 size, void *priv)
+struct domain_block *domain_alloc(struct domain *domain, u64 size, void *priv, u32 *offset)
 {
-    return __alloc_locked(domain, domain->min, size, 1, priv);
+    return __alloc_locked(domain, domain->min, size, 1, priv, offset);
 }
 
 struct domain_block *domain_alloc_near(struct domain *domain, u64 address,
-                                       u64 size, void *priv)
+                                       u64 size, void *priv, u32 *offset)
 {
-    return __alloc_locked(domain, address, size, 1, priv);
+    return __alloc_locked(domain, address, size, 1, priv, offset);
 }
 
 struct domain_block *domain_alloc_address(struct domain *domain, u64 address,
-                                          u64 size, void *priv)
+                                          u64 size, void *priv, u32 *offset)
 {
-    return __alloc_locked(domain, address, size, 0, priv);
+    return __alloc_locked(domain, address, size, 0, priv, offset);
 }
 
 void domain_init(struct domain *domain, u64 min, u64 max)
@@ -299,8 +373,8 @@ static void __test_overlap(struct domain_block *a, struct domain_block *b)
 
 void test_domain(void)
 {
-    struct domain_block *ret;
-    struct domain_block *ret2;
+    struct domain_block *ret, *ret2;
+    u32 offset;
 
     /* vsalloc's not inited but we can borrow it's big virtual address for a moment */
 
@@ -308,12 +382,12 @@ void test_domain(void)
 
     /* Test bounding */
 
-    ret = domain_alloc(&td, 4096, NULL);
+    ret = domain_alloc(&td, 4096, NULL, &offset);
     __test_bounds(ret);
 
-    /* Test non-overlapping */
+    /* Test non-overlapping with different priv */
 
-    ret2 = domain_alloc(&td, 100, NULL);
+    ret2 = domain_alloc(&td, 100, (void *) 0x1, &offset);
     __test_overlap(ret, ret2);
 
     /* Searching for a sub set range should still return conflict */
@@ -323,7 +397,7 @@ void test_domain(void)
     if (ret != ret2)
         while (1) ;
 
-    domain_free(&td, ret->address);
+    domain_free(&td, ret->address, 4096);
 
     /* This should now be free */
     ret2 = domain_search(&td, 3);
index dbbad55..086dfe7 100644 (file)
@@ -76,11 +76,8 @@ static void __page_list_add(struct page_block **head, struct page_block *new)
 
     prev = NULL;
     for (cur = *head; cur; prev = cur, cur = cur->next) {
-        if (cur->address > new->address) {
-            new->next = cur;
-            __setprev(head, prev, new);
-            return;
-        }
+        if (cur->address > new->address)
+            break;
     }
 
     __setprev(head, prev, new);
@@ -327,7 +324,7 @@ void *page_alloc(u32 order)
     if (order > MAX_ORDER)
         return NULL;
 
-    virtual = vsalloc("page heap", 0, (1 << (order + PAGE_SHIFT)));
+    virtual = vsalloc("page heap", 0, 1 << order);
 
     if (virtual == NULL)
         return NULL;
@@ -335,7 +332,7 @@ void *page_alloc(u32 order)
     ret = page_alloc_to_virtual((u64) virtual, order);
 
     if (ret == NULL) {
-        vfree(virtual);
+        vfree(virtual, 1 << order);
         return NULL;
     }
 
@@ -344,8 +341,8 @@ void *page_alloc(u32 order)
 
 void page_alloc_free(void *virtual)
 {
-    vfree(virtual);
-    page_alloc_free_from_virtual((u64) virtual);
+    s64 order = page_alloc_free_from_virtual((u64) virtual);
+    vfree(virtual, (1 << (order + PAGE_SHIFT)));
 }
 
 /* vmalloc functions give finer grain control of the allocation size, but you
@@ -374,7 +371,7 @@ void *page_vmalloc(u32 pages)
     u32 size;
     int i;
 
-    virtual = vsalloc("page vmalloc", 0, (pages << PAGE_SHIFT));
+    virtual = vsalloc("page vmalloc", 0, pages);
 
     if (virtual == NULL)
         return NULL;
index 9fddca3..6267903 100644 (file)
@@ -8,23 +8,24 @@
 
 static struct domain vs_domain = DOMAIN(KERNEL_VIRT_END, 0xFFFFFFFFFFFFFFFF);
 
-void *vsalloc(char *name, u64 address_hint, u64 size)
+void *vsalloc(char *name, u64 address_hint, u64 pages)
 {
     struct domain_block *ret;
+    u32 offset;
 
     if (address_hint == 0)
         address_hint = KERNEL_VIRT_END;
 
-    ret = domain_alloc_near(&vs_domain, address_hint, size, name);
+    ret = domain_alloc_near(&vs_domain, address_hint, pages << PAGE_SHIFT, name, &offset);
 
     if (ret)
-        return (void *)ret->address;
+        return (void *) (ret->address + offset);
     return NULL;
 }
 
-void vfree(void *address)
+void vfree(void *address, u64 pages)
 {
-    domain_free(&vs_domain, (u64) address);
+    domain_free(&vs_domain, (u64) address, pages << PAGE_SHIFT);
 }
 
 void vsalloc_init(void)