[Barrelfish-users] [New release] free() error

[Kornilios Kourtis]

Hi Georgios,

On Tue, Apr 02, 2013 at 09:20:31AM +0000, Georgios Varisteas wrote:
> Everything is regular. The slot number are incrementing with a step of
> 2 as they should. Nothing gets printed during the first call to free
> while slab_alloc fails only when cap.slot is 744. This block is called
> once for each slot number but slab_alloc never returns NULL except that
> one last time. That is why I said that maybe 744 is actually not the
> correct number, that maybe the whole thing should be shifted one slot
> or the process should have stopped at 742. I'm saying all these cause I
> do not understand what is happening. Maybe they are obvious, I can't
> know.

Here's my understanding (this is from reading the code, so I might be
wrong):
 - 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().

The (not so pretty, tested by booting qemu) patch below allocates
appropriately sized buffers for the slab allocator and hopefully fixes
your problem. I'm not sure if this is the proper solution in the long
term, since it adds significant memory overhead.

cheers,
Kornilios.

diff --git a/include/barrelfish/core_state.h b/include/barrelfish/core_state.h
index 6072471..eb6aea5 100644
--- a/include/barrelfish/core_state.h
+++ b/include/barrelfish/core_state.h
@@ -72,12 +72,11 @@ 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[SLAB_STATIC_SIZE(SLOT_ALLOC_CNODE_SLOTS / 2, sizeof(struct cnode_meta))];
+    char    head_buf[SLAB_STATIC_SIZE(SLOT_ALLOC_CNODE_SLOTS / 2, sizeof(struct cnode_meta))];
+    char reserve_buf[SLAB_STATIC_SIZE(SLOT_ALLOC_CNODE_SLOTS / 2, sizeof(struct cnode_meta))];
     struct single_slot_allocator rootca;
-    struct cnode_meta root_buf[DEFAULT_CNODE_SLOTS / 2];
+    char root_buf[SLAB_STATIC_SIZE(DEFAULT_CNODE_SLOTS / 2, sizeof(struct cnode_meta))];
 };
 
 struct terminal_state;
diff --git a/lib/barrelfish/slot_alloc/multi_slot_alloc.c b/lib/barrelfish/slot_alloc/multi_slot_alloc.c
index a12ab48..0cfecca 100644
--- a/lib/barrelfish/slot_alloc/multi_slot_alloc.c
+++ b/lib/barrelfish/slot_alloc/multi_slot_alloc.c
@@ -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 = SLAB_STATIC_SIZE(nslots/2, sizeof(struct cnode_meta)); // XXX?
 
     ret->top = malloc(sizeof(struct single_slot_allocator));
     if (!ret->top) {
diff --git a/lib/barrelfish/slot_alloc/single_slot_alloc.c b/lib/barrelfish/slot_alloc/single_slot_alloc.c
index 56e4d70..547ba5d 100644
--- a/lib/barrelfish/slot_alloc/single_slot_alloc.c
+++ b/lib/barrelfish/slot_alloc/single_slot_alloc.c
@@ -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,7 @@ errval_t single_slot_alloc_init_raw(struct single_slot_allocator *ret,
 
     slab_init(&ret->slab, sizeof(struct cnode_meta), NULL);
     if (buflen > 0) {
+        assert(SLAB_STATIC_SIZE(nslots / 2, sizeof(struct cnode_meta)) == buflen);
         slab_grow(&ret->slab, buf, buflen);
     }
 
@@ -166,7 +183,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 = SLAB_STATIC_SIZE(nslots / 2, sizeof(struct cnode_meta));
     void *buf = malloc(buflen);
     if (!buf) {
         return LIB_ERR_MALLOC_FAIL;
diff --git a/lib/spawndomain/spawn.c b/lib/spawndomain/spawn.c
index 2e9ea56..920c086 100644
--- a/lib/spawndomain/spawn.c
+++ b/lib/spawndomain/spawn.c
@@ -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 = SLAB_STATIC_SIZE(PAGE_CNODE_SLOTS/2, sizeof(struct cnode_meta));
     void *buf = malloc(bufsize);
     assert(buf != NULL);
 

-- 
Kornilios Kourtis