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

[Georgios Varisteas]

Hi again,

Applying the patch left me unable to boot BF. The assertion added at single_slot_alloc.c:162 actually fails after booting core 12 [of 32].

Monitor 0: booting x86_64 core 12 as '/x86_64/sbin/cpu loglevel=4'
Kernel starting at address 0xffffff802a001000
Barrelfish CPU driver starting on x86_64 apic_id 12
assertion "SLAB_STATIC_SIZE(nslots / 2, sizeof(struct cnode_meta)) == buflen" failed: file "../src/lib/barrelfish/slot_alloc/single_slot_alloc.c", line 162, function: single_slot_alloc_init_raw
Aborted
kernel 0: monitor terminated; expect badness!

I tested this just on Qemu but I do not think that it makes any difference.

Removing the assertion, BF booted normally (or so it seems). Memory consumption is not that bad although visibly increased. Moreover the error is indeed fixed and my programs terminate normally.

However, I'm going to revert the patch and choose the simple workaround of commenting out one of the calls to free(). In other parts of my code, I have other consecutive calls to free on non-consecutive memory blocks and get no error; so it takes very special circumstances for this behavior to appear which can easily be avoided without hacking BF internals.

I will assist anyone who wants to solve this, though.

cheers,
Georgios


________________________________________
From: Kornilios Kourtis [kornilios.kourtis at inf.ethz.ch]
Sent: Tuesday, April 02, 2013 14:10
To: Georgios Varisteas
Cc: barrelfish-users at lists.inf.ethz.ch
Subject: Re: [Barrelfish-users] [New release] free() error

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