slab: fix alignment issues
authorBarret Rhoden <brho@cs.berkeley.edu>
Mon, 16 Sep 2019 16:19:57 +0000 (12:19 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 8 Oct 2019 21:11:11 +0000 (17:11 -0400)
This clarifies many of the issues around alignment and source quantum.

Previously, there were a lot of assumptions about source alignment
(assumed PGSIZE, but it was actually quantum), object size (assumed big
enough for a pointer), etc.  If you had an arena with quantum > PGSIZE
and made a slab / KC from it (e.g. a qcache), you'd trip the assertion
too.

We also didn't have any guarantees about carrying a source's
quantum-multiple-alignment through to the slab, which matters for
non-power-of-two sources that want to use qcaches.  We use the "if
obj_size is a multiple of quantum, you'll get quantum-multiple-aligned
allocations" guarantee to solve the problem for qcaches.

Slab align is a separate item from both arena quantum and arena align.
The object we get from a source gets aligned up (or is already the right
alignment, for the pro-touch/non-bufctl case), which requires us to
track the original address from the arena in the slab.  That's fine.
Might as well use that for the pro-touch case.

I considered getting rid of PGSIZE, but its usage in obj->slab lookups
is pretty handy.

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

index 182b2bc..d625d92 100644 (file)
@@ -94,6 +94,7 @@ struct kmem_slab {
        TAILQ_ENTRY(kmem_slab) link;
        size_t num_busy_obj;
        size_t num_total_obj;
+       void *source_obj;
        union {
                struct kmem_bufctl_list bufctl_freelist;
                void *free_small_obj;
index ff53d92..3dd0084 100644 (file)
@@ -127,8 +127,14 @@ static void setup_qcaches(struct arena *arena, size_t quantum,
        for (int i = 0; i < nr_qcaches; i++) {
                qc_size = (i + 1) * quantum;
                snprintf(kc_name, KMC_NAME_SZ, "%s_%d", arena->name, qc_size);
-               __kmem_cache_create(&arena->qcaches[i], kc_name, qc_size,
-                                   quantum, KMC_NOTOUCH | KMC_QCACHE, arena,
+               /* Alignment == 1.  These QCs will give out quantum-aligned
+                * (actually multiples) objects, even without an alignment
+                * request.  The reason is that the QCs pull their slabs from
+                * us, and we give out quantum-aligned objects (i.e. the slabs).
+                * Those slabs are made of up objects that are multiples
+                * of quantum. */
+               __kmem_cache_create(&arena->qcaches[i], kc_name, qc_size, 1,
+                                   KMC_NOTOUCH | KMC_QCACHE, arena,
                                    NULL, NULL, NULL);
        }
 }
index 55b7776..602cf2d 100644 (file)
@@ -293,22 +293,74 @@ void __kmem_cache_create(struct kmem_cache *kc, const char *name,
                          void (*dtor)(void *, void *), void *priv)
 {
        assert(kc);
-       assert(align);
+       /* Our alignment is independent of our source's quantum.  We pull from
+        * our source, which gives us quantum-multiple/aligned chunks, but our
+        * alignment and object size is our own business.  Mostly.
+        *
+        * There is one guarantee we must make:
+        * - If aligned-obj_size (ALIGN(obj_size, align)) is a multiple of our
+        *   source's quantum, then all objects we return are
+        *   quantum-multiple-aligned (addresses are multiples of quantum).
+        *
+        * The main restriction for us is that when we get a slab from our
+        * source, we need to hand out objects at the beginning of the slab
+        * (where we are source quantum-aligned).
+        *
+        * As an example, if our source quantum is 15, and we give out 45 byte
+        * objects, we must give out e.g. [15,60), but not [10,55).  This really
+        * only comes up for qcaches for arenas that aren't memory, since all
+        * memory users will be going with power-of-two alignment.  And
+        * typically the slabs will have their own alignment.  e.g.
+        * alignof(struct foo), with a PGSIZE-quantum source.
+        *
+        * Our objects are always aligned to 'align', regardless of our source's
+        * alignment/quantum.  Similarly, if our source's quantum is a multiple
+        * of aligned-obj_size, then all objects we return are
+        * obj_size-multiple-aligned. */
+       assert(IS_PWR2(align));
+       /* Every allocation is aligned, and every allocation is the same
+        * size, so we might as well align-up obj_size. */
+       obj_size = ALIGN(obj_size, align);
        spinlock_init_irqsave(&kc->cache_lock);
        strlcpy(kc->name, name, KMC_NAME_SZ);
-       kc->obj_size = ROUNDUP(obj_size, align);
+       /* We might want some sort of per-call site NUMA-awareness in the
+        * future. */
+       source = source ?: kpages_arena;
+       kc->source = source;
+       kc->obj_size = obj_size;
+       kc->align = align;
+       kc->flags = flags;
+       /* No touch must use bufctls, even for small objects, so that it does
+        * not use the object as memory.  RAM objects need enough space for a
+        * pointer to form the linked list of objects. */
+       if (obj_size < sizeof(void*) || obj_size > SLAB_LARGE_CUTOFF
+           || flags & KMC_NOTOUCH) {
+               kc->flags |= __KMC_USE_BUFCTL;
+       } else {
+               /* pro-touch (non-bufctl) slabs must get a page-aligned slab
+                * from the source.  quantum < PGSIZE won't guarantee that.
+                * quantum > PGSIZE is a waste and a programmer error. */
+               if (kc->source->quantum != PGSIZE) {
+                       warn("KC %s is 'pro-touch', but source arena %s has non-PGSIZE quantum %d",
+                            kc->name, source->name, source->quantum);
+                       kc->flags |= __KMC_USE_BUFCTL;
+               }
+       }
+       /* Note that import_amt is only used for bufctls.  The alternative puts
+        * the slab at the end of a PGSIZE chunk, and fills the page with
+        * objects.  The reliance on PGSIZE is used when finding a slab for a
+        * given buffer.
+        *
+        * Also note that import_amt can be ignored for qcaches too.  If the
+        * object is small and pro-touch, we'll still try and get a page from
+        * the source, even if that is very large.  Consider a source with
+        * qcache_max = 5, quantum = 1.  It's actually fine - we may waste a
+        * little (unused allocations), but we save on not having bufctls. */
        if (flags & KMC_QCACHE)
                kc->import_amt = ROUNDUPPWR2(3 * source->qcache_max);
        else
-               kc->import_amt = ROUNDUP(NUM_BUF_PER_SLAB * obj_size, PGSIZE);
-       kc->align = align;
-       if (align > PGSIZE)
-               panic("Cache %s object alignment is actually MIN(PGSIZE, align (%p))",
-                     name, align);
-       kc->flags = flags;
-       /* We might want some sort of per-call site NUMA-awareness in the
-        * future. */
-       kc->source = source ? source : kpages_arena;
+               kc->import_amt = ROUNDUP(NUM_BUF_PER_SLAB * obj_size,
+                                        ROUNDUP(PGSIZE, source->quantum));
        TAILQ_INIT(&kc->full_slab_list);
        TAILQ_INIT(&kc->partial_slab_list);
        TAILQ_INIT(&kc->empty_slab_list);
@@ -321,13 +373,6 @@ void __kmem_cache_create(struct kmem_cache *kc, const char *name,
        hash_init_hh(&kc->hh);
        for (int i = 0; i < kc->hh.nr_hash_lists; i++)
                BSD_LIST_INIT(&kc->static_hash[i]);
-       /* No touch must use bufctls, even for small objects, so that it does
-        * not use the object as memory.  Note that if we have an arbitrary
-        * source, small objects, and we're 'pro-touch', the small allocation
-        * path will assume we're importing from a PGSIZE-aligned source arena.
-        */
-       if ((obj_size > SLAB_LARGE_CUTOFF) || (flags & KMC_NOTOUCH))
-               kc->flags |= __KMC_USE_BUFCTL;
        depot_init(&kc->depot);
        kmem_trace_ht_init(&kc->trace_ht);
        /* We do this last, since this will all into the magazine cache - which
@@ -429,20 +474,16 @@ static void depot_destroy(struct kmem_cache *kc)
 static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
 {
        if (!__use_bufctls(cp)) {
-               arena_free(cp->source, ROUNDDOWN(a_slab, PGSIZE), PGSIZE);
+               arena_free(cp->source, a_slab->source_obj, PGSIZE);
        } else {
                struct kmem_bufctl *i, *temp;
-               void *buf_start = (void*)SIZE_MAX;
 
                BSD_LIST_FOREACH_SAFE(i, &a_slab->bufctl_freelist, link, temp) {
-                       // Track the lowest buffer address, which is the start
-                       // of the buffer
-                       buf_start = MIN(buf_start, i->buf_addr);
                        /* 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);
                }
-               arena_free(cp->source, buf_start, cp->import_amt);
+               arena_free(cp->source, a_slab->source_obj, cp->import_amt);
                kmem_cache_free(kmem_slab_cache, a_slab);
        }
 }
@@ -768,20 +809,19 @@ static bool kmem_cache_grow(struct kmem_cache *cp)
        if (!__use_bufctls(cp)) {
                void *a_page;
 
-               /* Careful, this assumes our source is a PGSIZE-aligned
-                * allocator.  We could use xalloc to enforce the alignment, but
-                * that'll bypass the qcaches, which we don't want.  Caller
-                * beware. */
                a_page = arena_alloc(cp->source, PGSIZE, MEM_ATOMIC);
                if (!a_page)
                        return FALSE;
-               // the slab struct is stored at the end of the page
+               /* The slab struct is stored at the end of the page.  Keep it
+                * there, so that our first object is page aligned, and thus
+                * aligned to all smaller alignments.  If align > PGSIZE,
+                * obj_size > PGSIZE, and we'd use bufctls. */
                a_slab = (struct kmem_slab*)(a_page + PGSIZE
                                             - sizeof(struct kmem_slab));
+               a_slab->source_obj = a_page;
                a_slab->num_busy_obj = 0;
                a_slab->num_total_obj = (PGSIZE - sizeof(struct kmem_slab)) /
                                        cp->obj_size;
-               // TODO: consider staggering this IAW section 4.3
                a_slab->free_small_obj = a_page;
                /* Walk and create the free list, which is circular.  Each item
                 * stores the location of the next one at the beginning of the
@@ -795,17 +835,29 @@ static bool kmem_cache_grow(struct kmem_cache *cp)
                *((uintptr_t**)buf) = NULL;
        } else {
                void *buf;
+               uintptr_t delta;
 
                a_slab = kmem_cache_alloc(kmem_slab_cache, 0);
                if (!a_slab)
                        return FALSE;
                buf = arena_alloc(cp->source, cp->import_amt, MEM_ATOMIC);
-               if (!buf) {
-                       kmem_cache_free(kmem_slab_cache, a_slab);
-                       return FALSE;
+               if (!buf)
+                       goto err_slab;
+               a_slab->source_obj = buf;
+               buf = ALIGN(buf, cp->align);
+               delta = buf - a_slab->source_obj;
+               if (delta >= cp->import_amt) {
+                       /* Shouldn't happen - the import_amt should always be
+                        * enough for at least two objects, with obj_size >=
+                        * align.  Maybe if a qcache had an alignment (which
+                        * they don't). */
+                       warn("Delta %p >= import_amt %p! (buf %p align %p)",
+                            delta, cp->import_amt, a_slab->source_obj,
+                            cp->align);
+                       goto err_source_obj;
                }
                a_slab->num_busy_obj = 0;
-               a_slab->num_total_obj = cp->import_amt / cp->obj_size;
+               a_slab->num_total_obj = (cp->import_amt - delta) / cp->obj_size;
                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++) {
@@ -821,6 +873,12 @@ static bool kmem_cache_grow(struct kmem_cache *cp)
        TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
 
        return TRUE;
+
+err_source_obj:
+       arena_free(cp->source, a_slab->source_obj, cp->import_amt);
+err_slab:
+       kmem_cache_free(kmem_slab_cache, a_slab);
+       return FALSE;
 }
 
 /* This deallocs every slab from the empty list.  TODO: think a bit more about