fix buflen when calling single_slot_alloc_raw()
authorKornilios Kourtis <kkourt@inf.ethz.ch>
Tue, 2 Apr 2013 12:40:51 +0000 (14:40 +0200)
committerKornilios Kourtis <kkourt@inf.ethz.ch>
Mon, 22 Apr 2013 15:31:50 +0000 (17:31 +0200)
Here's my understanding (this is from reading the code):
 - single_slot_alloc manages slots for a single cnode  using a list of
   free nodes. The list is maintained starting with ->head, and each node
   represents a range of slots (slot, space).  The list is initialized
   with a single node with {slot=0, space=nslots}

 - The worst case scenario for the size of the list is when only the odd
   (or even) slots are free. This is the worst case because for all nodes
   in the list space=1. Adding nodes should result in smaller number of
   nodes but with higher ->space values.

 - The list nodes are allocated/freed using a (simple) slab allocator.
   Hence, the slab allocator should be initialized so that it contains
   nslots/2 objects to accommodate for the worst case.

The problem is that this does not happen: the slab allocator requires some
additional memory for adding headers to objects which is not accounted for.
This is why in your case the allocator does not have additional objects to
provide in slab_alloc().

This commit allocates appropriately sized buffers for the slab allocator and
hopefully fixes your problem.

Many thanks to Georgios Varisteas <yorgos@kth.se> for reporting the bug and
help us debug the problem.

include/barrelfish/core_state.h
include/barrelfish/slot_alloc.h
lib/barrelfish/slot_alloc/multi_slot_alloc.c
lib/barrelfish/slot_alloc/single_slot_alloc.c
lib/barrelfish/slot_alloc/slot_alloc.c
lib/spawndomain/spawn.c

index 6072471..a766a8f 100644 (file)
@@ -72,12 +72,12 @@ struct slot_alloc_state {
     struct slot_allocator_list head;
     struct slot_allocator_list reserve;
 
-    struct cnode_meta top_buf[SLOT_ALLOC_CNODE_SLOTS / 2];
-    struct cnode_meta head_buf[SLOT_ALLOC_CNODE_SLOTS / 2];
-    struct cnode_meta reserve_buf[SLOT_ALLOC_CNODE_SLOTS / 2];
+    char     top_buf[SINGLE_SLOT_ALLOC_BUFLEN(SLOT_ALLOC_CNODE_SLOTS)];
+    char    head_buf[SINGLE_SLOT_ALLOC_BUFLEN(SLOT_ALLOC_CNODE_SLOTS)];
+    char reserve_buf[SINGLE_SLOT_ALLOC_BUFLEN(SLOT_ALLOC_CNODE_SLOTS)];
+    char    root_buf[SINGLE_SLOT_ALLOC_BUFLEN(DEFAULT_CNODE_SLOTS   )];
 
     struct single_slot_allocator rootca;
-    struct cnode_meta root_buf[DEFAULT_CNODE_SLOTS / 2];
 };
 
 struct terminal_state;
index cceea58..da25dd1 100644 (file)
@@ -71,6 +71,10 @@ struct range_slot_allocator {
     struct thread_mutex mutex;   ///< Mutex for thread safety
 };
 
+// single_slot_alloc_init_raw() requires a specific buflen
+#define SINGLE_SLOT_ALLOC_BUFLEN(nslots) \
+    (SLAB_STATIC_SIZE(nslots / 2, sizeof(struct cnode_meta)))
+
 errval_t single_slot_alloc_init(struct single_slot_allocator *ret,
                                 cslot_t nslots, cslot_t *retslots);
 errval_t single_slot_alloc_init_raw(struct single_slot_allocator *ret,
index a12ab48..b6e264d 100644 (file)
@@ -239,7 +239,7 @@ errval_t multi_slot_alloc_init_raw(struct multi_slot_allocator *ret,
 
     /* Slab */
     size_t allocation_unit = sizeof(struct slot_allocator_list) +
-        sizeof(struct cnode_meta) * nslots / 2;
+                             SINGLE_SLOT_ALLOC_BUFLEN(nslots);
     slab_init(&ret->slab, allocation_unit, NULL);
 
     return SYS_ERR_OK;
@@ -253,7 +253,7 @@ errval_t multi_slot_alloc_init(struct multi_slot_allocator *ret,
 {
     errval_t err;
     nslots = ROUND_UP(nslots, DEFAULT_CNODE_SLOTS);
-    size_t bufsize = sizeof(struct cnode_meta) * nslots / 2; // XXX: ?
+    size_t bufsize = SINGLE_SLOT_ALLOC_BUFLEN(nslots); // XXX?
 
     ret->top = malloc(sizeof(struct single_slot_allocator));
     if (!ret->top) {
index 56e4d70..c4dd033 100644 (file)
@@ -92,6 +92,15 @@ static errval_t sfree(struct slot_allocator *ca, struct capref cap)
         // Freeing at the edge of walk
         if (cap.slot == walk->slot + walk->space) {
             walk->space++;
+
+            // check if we can merge walk to next
+            struct cnode_meta *next = walk->next;
+            if (next && next->slot == walk->slot + walk->space) {
+                walk->space += next->space;
+                walk->next = next->next;
+                slab_free(&sca->slab, next);
+            }
+
             goto finish;
         }
         else if (cap.slot < walk->slot + walk->space) {
@@ -99,6 +108,13 @@ static errval_t sfree(struct slot_allocator *ca, struct capref cap)
             goto unlock;
         }
 
+        // Freing just before walk->next
+        if (walk->next && cap.slot + 1 == walk->next->slot) {
+            walk->next->slot = cap.slot;
+            walk->next->space++;
+            goto finish;
+        }
+
         // Freeing after walk and before walk->next
         if (walk->next && cap.slot < walk->next->slot) {
             struct cnode_meta *new = walk->next;
@@ -143,6 +159,17 @@ errval_t single_slot_alloc_init_raw(struct single_slot_allocator *ret,
 
     slab_init(&ret->slab, sizeof(struct cnode_meta), NULL);
     if (buflen > 0) {
+        // check for callers that do not provide enough buffer space
+        #if !defined(NDEBUG)
+        size_t buflen_proper = SINGLE_SLOT_ALLOC_BUFLEN(nslots);
+        if (buflen != buflen_proper) {
+            debug_printf("******* FIXME: %s buflen=%lu != buflen_proper=%lu"
+                         "call stack: %p %p\n",
+                         __FUNCTION__, buflen, buflen_proper,
+                         __builtin_return_address(0),
+                         __builtin_return_address(1));
+        }
+        #endif
         slab_grow(&ret->slab, buf, buflen);
     }
 
@@ -166,7 +193,7 @@ errval_t single_slot_alloc_init(struct single_slot_allocator *ret,
     if (err_is_fail(err)) {
         return err_push(err, LIB_ERR_CNODE_CREATE);
     }
-    size_t buflen = sizeof(struct cnode_meta) * nslots / 2; // worst case
+    size_t buflen = SINGLE_SLOT_ALLOC_BUFLEN(nslots);
     void *buf = malloc(buflen);
     if (!buf) {
         return LIB_ERR_MALLOC_FAIL;
index 44e0cf2..1b683e0 100644 (file)
@@ -161,7 +161,7 @@ errval_t slot_alloc_init(void)
 
     // Slab
     size_t allocation_unit = sizeof(struct slot_allocator_list) +
-        sizeof(struct cnode_meta) * SLOT_ALLOC_CNODE_SLOTS / 2;
+                             SINGLE_SLOT_ALLOC_BUFLEN(SLOT_ALLOC_CNODE_SLOTS);
     slab_init(&def->slab, allocation_unit, NULL);
 
     // Vspace mgmt
index 2e9ea56..6a549c5 100644 (file)
@@ -167,7 +167,7 @@ static errval_t spawn_setup_vspace(struct spawninfo *si)
     /* Init pagecn's slot allocator */
 
     // XXX: satisfy a peculiarity of the single_slot_alloc_init_raw API
-    size_t bufsize = sizeof(struct cnode_meta) * PAGE_CNODE_SLOTS / 2;
+    size_t bufsize = SINGLE_SLOT_ALLOC_BUFLEN(PAGE_CNODE_SLOTS);
     void *buf = malloc(bufsize);
     assert(buf != NULL);