summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMartin Mares <mj@ucw.cz>2000-03-05 23:48:30 +0100
committerMartin Mares <mj@ucw.cz>2000-03-05 23:48:30 +0100
commit3549667925d04fa6a46ea35f56a9d3c741634d6a (patch)
treeacb5a8ef56724e19c427cb8a924efabeab0897e6
parent9f4929e749d945c727f245ed7ef30c557124c352 (diff)
downloadbird-3549667925d04fa6a46ea35f56a9d3c741634d6a.tar
bird-3549667925d04fa6a46ea35f56a9d3c741634d6a.zip
Implemented real slab allocator. If you suspect it from being buggy,
just #define FAKE_SLAB at the top of lib/slab.c to bypass it.
-rw-r--r--TODO2
-rw-r--r--lib/slab.c209
2 files changed, 197 insertions, 14 deletions
diff --git a/TODO b/TODO
index ccbe59c..fc7f8fa 100644
--- a/TODO
+++ b/TODO
@@ -1,7 +1,5 @@
Core
~~~~
-- better memory allocators
-
- static: check validity of route destination?
- static: allow specifying a per-route filter program for setting route attributes?
diff --git a/lib/slab.c b/lib/slab.c
index ad691f7..98c3ec5 100644
--- a/lib/slab.c
+++ b/lib/slab.c
@@ -1,7 +1,9 @@
/*
- * BIRD Resource Manager -- SLABs
+ * BIRD Resource Manager -- A SLAB-like Memory Allocator
*
- * (c) 1998 Martin Mares <mj@ucw.cz>
+ * Heavily inspired by the original SLAB paper by Jeff Bonwick.
+ *
+ * (c) 1998--2000 Martin Mares <mj@ucw.cz>
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
@@ -12,31 +14,35 @@
#include "nest/bird.h"
#include "lib/resource.h"
+#undef FAKE_SLAB /* Turn on if you want to debug memory allocations */
+
+static void slab_free(resource *r);
+static void slab_dump(resource *r);
+
+#ifdef FAKE_SLAB
+
/*
- * These are only fake, soon to change...
+ * Fake version used for debugging.
*/
-struct sl_obj {
- node n;
- byte data[0];
-};
-
struct slab {
resource r;
unsigned size;
list objs;
};
-static void slab_free(resource *r);
-static void slab_dump(resource *r);
-
static struct resclass sl_class = {
- "Slab",
+ "FakeSlab",
sizeof(struct slab),
slab_free,
slab_dump
};
+struct sl_obj {
+ node n;
+ byte data[0];
+};
+
slab *
sl_new(pool *p, unsigned size)
{
@@ -85,3 +91,182 @@ slab_dump(resource *r)
cnt++;
debug("(%d objects per %d bytes)\n", cnt, s->size);
}
+
+#else
+
+/*
+ * Real efficient version.
+ */
+
+#define SLAB_SIZE 4096
+#define MAX_EMPTY_HEADS 1
+
+struct slab {
+ resource r;
+ unsigned obj_size, head_size, objs_per_slab, num_empty_heads;
+ list empty_heads, partial_heads, full_heads;
+};
+
+static struct resclass sl_class = {
+ "Slab",
+ sizeof(struct slab),
+ slab_free,
+ slab_dump
+};
+
+struct sl_head {
+ node n;
+ struct sl_obj *first_free;
+ int num_full;
+};
+
+struct sl_obj {
+ struct sl_head *slab;
+ union {
+ struct sl_obj *next;
+ byte data[0];
+ } u;
+};
+
+struct sl_alignment { /* Magic structure for testing of alignment */
+ byte data;
+ int x[0];
+};
+
+slab *
+sl_new(pool *p, unsigned size)
+{
+ slab *s = ralloc(p, &sl_class);
+ unsigned int align = sizeof(struct sl_alignment);
+ if (align < sizeof(int))
+ align = sizeof(int);
+ size += OFFSETOF(struct sl_obj, u.data);
+ if (size < sizeof(struct sl_obj))
+ size = sizeof(struct sl_obj);
+ size = (size + align - 1) / align * align;
+ s->obj_size = size;
+ s->head_size = (sizeof(struct sl_head) + align - 1) / align * align;
+ s->objs_per_slab = (SLAB_SIZE - s->head_size) / size;
+ if (!s->objs_per_slab)
+ bug("Slab: object too large");
+ s->num_empty_heads = 0;
+ init_list(&s->empty_heads);
+ init_list(&s->partial_heads);
+ init_list(&s->full_heads);
+ return s;
+}
+
+struct sl_head *
+sl_new_head(slab *s)
+{
+ struct sl_head *h = xmalloc(SLAB_SIZE);
+ struct sl_obj *o = (struct sl_obj *)((byte *)h+s->head_size);
+ struct sl_obj *no;
+ unsigned int n = s->objs_per_slab;
+
+ h->first_free = o;
+ h->num_full = 0;
+ while (n--)
+ {
+ o->slab = h;
+ no = (struct sl_obj *)((char *) o+s->obj_size);
+ o->u.next = n ? no : NULL;
+ o = no;
+ }
+ return h;
+}
+
+void *
+sl_alloc(slab *s)
+{
+ struct sl_head *h;
+ struct sl_obj *o;
+
+redo:
+ h = HEAD(s->partial_heads);
+ if (!h->n.next)
+ goto no_partial;
+okay:
+ o = h->first_free;
+ if (!o)
+ goto full_partial;
+ h->first_free = o->u.next;
+ h->num_full++;
+ return o->u.data;
+
+full_partial:
+ rem_node(&h->n);
+ add_tail(&s->full_heads, &h->n);
+ goto redo;
+
+no_partial:
+ h = HEAD(s->empty_heads);
+ if (h->n.next)
+ {
+ rem_node(&h->n);
+ add_head(&s->partial_heads, &h->n);
+ s->num_empty_heads--;
+ goto okay;
+ }
+ h = sl_new_head(s);
+ add_head(&s->partial_heads, &h->n);
+ goto okay;
+}
+
+void
+sl_free(slab *s, void *oo)
+{
+ struct sl_obj *o = SKIP_BACK(struct sl_obj, u.data, oo);
+ struct sl_head *h = o->slab;
+
+ o->u.next = h->first_free;
+ h->first_free = o;
+ if (!--h->num_full)
+ {
+ rem_node(&h->n);
+ if (s->num_empty_heads >= MAX_EMPTY_HEADS)
+ xfree(h);
+ else
+ {
+ add_head(&s->empty_heads, &h->n);
+ s->num_empty_heads++;
+ }
+ }
+ else if (!o->u.next)
+ {
+ rem_node(&h->n);
+ add_head(&s->partial_heads, &h->n);
+ }
+}
+
+static void
+slab_free(resource *r)
+{
+ slab *s = (slab *) r;
+ struct sl_head *h, *g;
+
+ WALK_LIST_DELSAFE(h, g, s->empty_heads)
+ xfree(h);
+ WALK_LIST_DELSAFE(h, g, s->partial_heads)
+ xfree(h);
+ WALK_LIST_DELSAFE(h, g, s->full_heads)
+ xfree(h);
+}
+
+static void
+slab_dump(resource *r)
+{
+ slab *s = (slab *) r;
+ int ec=0, pc=0, fc=0;
+ struct sl_head *h;
+
+ WALK_LIST(h, s->empty_heads)
+ ec++;
+ WALK_LIST(h, s->partial_heads)
+ pc++;
+ WALK_LIST(h, s->full_heads)
+ fc++;
+ debug("(%de+%dp+%df blocks per %d objs per %d bytes)\n", ec, pc, fc, s->objs_per_slab, s->obj_size);
+}
+
+#endif