slab: Use BSD_LISTs for the bufctls
authorBarret Rhoden <brho@cs.berkeley.edu>
Sun, 30 Oct 2016 22:23:00 +0000 (18:23 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 29 Nov 2016 16:27:40 +0000 (11:27 -0500)
The slab allocator has a long-standing TODO: BUF.  Instead of using a
hash table to lookup a large object, we just used storage in the object
itself.  This was okay, other than possible fragmentation effects, but
it meant that the slab allocator touched every object it tracked.  We'll
eventually need an option to have "NO_TOUCH" slab allocators, where they
do not touch the objects they are tracking.  To do that, we'll need a
hash table.

This commit switches the bufctl struct from a TAILQ to a BSD_LIST, which
will make the hash table entries smaller.  This also fixes a FOREACH
freeing bug. (use FOREACH_SAFE).

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/slab.h
kern/src/slab.c

index 395cb39..07ea8b8 100644 (file)
@@ -42,11 +42,11 @@ struct kmem_slab;
 
 /* Control block for buffers for large-object slabs */
 struct kmem_bufctl {
-       TAILQ_ENTRY(kmem_bufctl) link;
+       BSD_LIST_ENTRY(kmem_bufctl) link;
        void *buf_addr;
        struct kmem_slab *my_slab;
 };
-TAILQ_HEAD(kmem_bufctl_list, kmem_bufctl);
+BSD_LIST_HEAD(kmem_bufctl_list, kmem_bufctl);
 
 /* Slabs contain the objects.  Can be either full, partial, or empty,
  * determined by checking the number of objects busy vs total.  For large
index 4cc6f13..3717a89 100644 (file)
@@ -105,7 +105,7 @@ static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
                }
                page_decref(kva2page((void*)ROUNDDOWN((uintptr_t)a_slab, PGSIZE)));
        } else {
-               struct kmem_bufctl *i;
+               struct kmem_bufctl *i, *temp;
                void *page_start = (void*)-1;
                /* Figure out how much memory we asked for earlier.  We needed at least
                 * min_pgs.  We asked for the next highest order (power of 2) number of
@@ -113,12 +113,14 @@ static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
                size_t min_pgs = ROUNDUP(NUM_BUF_PER_SLAB * a_slab->obj_size, PGSIZE) /
                                         PGSIZE;
                size_t order_pg_alloc = LOG2_UP(min_pgs);
-               TAILQ_FOREACH(i, &a_slab->bufctl_freelist, link) {
+               BSD_LIST_FOREACH_SAFE(i, &a_slab->bufctl_freelist, link, temp) {
                        // Track the lowest buffer address, which is the start of the buffer
                        page_start = MIN(page_start, i->buf_addr);
                        /* Deconstruct all the objects, if necessary */
                        if (cp->dtor) // TODO: (BUF)
                                cp->dtor(i->buf_addr, cp->obj_size);
+                       /* This is a little dangerous, but we can skip removing, since we
+                        * init the freelist when we reuse the slab. */
                        kmem_cache_free(kmem_bufctl_cache, i);
                }
                // free the pages for the slab's buffer
@@ -185,8 +187,9 @@ void *kmem_cache_alloc(struct kmem_cache *cp, int flags)
                                                        cp->obj_size);
        } else {
                // rip the first bufctl out of the partial slab's buf list
-               struct kmem_bufctl *a_bufctl = TAILQ_FIRST(&a_slab->bufctl_freelist);
-               TAILQ_REMOVE(&a_slab->bufctl_freelist, a_bufctl, link);
+               struct kmem_bufctl *a_bufctl = BSD_LIST_FIRST(&a_slab->bufctl_freelist);
+
+               BSD_LIST_REMOVE(a_bufctl, link);
                retval = a_bufctl->buf_addr;
        }
        a_slab->num_busy_obj++;
@@ -225,7 +228,7 @@ void kmem_cache_free(struct kmem_cache *cp, void *buf)
                // TODO: (BUF) change the interface to not take an offset
                a_bufctl = buf2bufctl(buf, cp->obj_size);
                a_slab = a_bufctl->my_slab;
-               TAILQ_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
+               BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
        }
        a_slab->num_busy_obj--;
        cp->nr_cur_alloc--;
@@ -301,14 +304,14 @@ static bool kmem_cache_grow(struct kmem_cache *cp)
                /* The number of objects is based on the rounded up amt requested. */
                a_slab->num_total_obj = ((1 << order_pg_alloc) * PGSIZE) /
                                        a_slab->obj_size;
-               TAILQ_INIT(&a_slab->bufctl_freelist);
+               BSD_LIST_INIT(&a_slab->bufctl_freelist);
                /* for each buffer, set up a bufctl and point to the buffer */
                for (int i = 0; i < a_slab->num_total_obj; i++) {
                        // Initialize the object, if necessary
                        if (cp->ctor)
                                cp->ctor(buf, cp->obj_size);
                        a_bufctl = kmem_cache_alloc(kmem_bufctl_cache, 0);
-                       TAILQ_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
+                       BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
                        a_bufctl->buf_addr = buf;
                        a_bufctl->my_slab = a_slab;
                        // TODO: (BUF) write the bufctl reference at the bottom of the buffer.