arena: add arena tests
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 26 Sep 2019 16:40:07 +0000 (12:40 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Tue, 8 Oct 2019 21:11:11 +0000 (17:11 -0400)
And some details about the difference between qcaches and regular slab
allocators.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/src/arena.c
kern/src/ktest/Kbuild
kern/src/ktest/Kconfig.kernel
kern/src/ktest/kt_arena.c [new file with mode: 0644]

index 3dd0084..5a006d9 100644 (file)
@@ -51,6 +51,9 @@
  *   poke the CV if the first waiter is likely to succeed.
  * - Reclaim: have a ktask that sleeps on a rendez.  We poke it, even from IRQ
  *   context.  It qlocks arenas_and_slabs_lock, then does the reclaim.
+ * - There's an issue with when slab objects get deconstructed, and how that
+ *   interacts with what I wanted to do with kstacks and TLB shootdowns.  I
+ *   think right now (2019-09) there is a problem with it.
  *
  * FAQ:
  * - Does allocating memory from an arena require it to take a btag?  Yes -
  *   will have their own stats, and it'd be a minor pain to sync up with them
  *   all the time.  Also, the important stat is when the base arena starts to
  *   run out of memory, and base arenas don't have qcaches, so it's moot.
+ * - What's the difference between a kmem_cache (slab / KC) that is used as a
+ *   qcache and one that just sources from the arena?  Two things: qcaches are
+ *   set up to be KMC_NOTOUCH, meaning that the objects we allocate cannot be
+ *   treated as memory at any point.  When the KC is "pro-touch", it can use
+ *   the memory of unallocated objects, meaning allocated from the arena to the
+ *   KC but not allocated to the user, for bookkeeping.  NOTOUCH means we cannot
+ *   do that.  e.g. an integer allocator: don't just write to random addresses!
+ *   In general, all arenas are NOTOUCH by default, to avoid these sorts of
+ *   disasters.  The only time you'd want 'pro-touch' is for small-size KCs that
+ *   are actually backed by memory.  In those cases, you just make slabs that
+ *   source from an arena that are not qcaches.  These are the kmalloc slabs.
+ *   The other difference between a qcache and a KC sourcing is the qcaches have
+ *   a different import_amt.  It's just a performance decision recommended in
+ *   the vmem paper.  import_amt is only used with large or no-touch objects,
+ *   which is always the case with qcaches.  Small, pro-touch KCs just grab a
+ *   page at a time and use that for the slab struct and linked list.  Finally,
+ *   all qcaches, being NOTOUCH, therefore use bufctls in the slab.  These are
+ *   basically the same as the arena btags.  So ultimately, all objects
+ *   allocated from an arena, even those from qcaches, have some sort of btag.
+ *   Each slab has an *additional* BT in the arena, representing the source's
+ *   alloc.  (Actually, that alloc can be from another, larger qcache of the
+ *   arena!).
  */
 
 #include <arena.h>
index 4498f30..5b74f7c 100644 (file)
@@ -1,3 +1,4 @@
 obj-y                                          += ktest.o
+obj-$(CONFIG_KTEST_ARENA)                      += kt_arena.o
 obj-$(CONFIG_PB_KTESTS)                                += pb_ktests.o
 obj-$(CONFIG_NET_KTESTS)                       += net_ktests.o
index 0aa2a21..ebbc874 100644 (file)
@@ -6,3 +6,10 @@ menuconfig KERNEL_TESTING
 
 source "kern/src/ktest/Kconfig.postboot"
 source "kern/src/ktest/Kconfig.net"
+
+config KTEST_ARENA
+       depends on KERNEL_TESTING
+       bool "Arena kernel test"
+       default y
+       help
+       Run the arena tests
diff --git a/kern/src/ktest/kt_arena.c b/kern/src/ktest/kt_arena.c
new file mode 100644 (file)
index 0000000..29c3978
--- /dev/null
@@ -0,0 +1,458 @@
+#include <arena.h>
+#include <slab.h>
+#include <ktest.h>
+#include <linker_func.h>
+
+KTEST_SUITE("ARENA")
+
+static bool test_nextfit(void)
+{
+       struct arena *a;
+       void *o1, *o2, *o3;
+
+       a = arena_create(__func__, (void*)1, 30, 1, NULL, NULL, NULL, 0,
+                        MEM_WAIT);
+       o1 = arena_alloc(a, 1, MEM_WAIT | ARENA_NEXTFIT);
+       o2 = arena_alloc(a, 1, MEM_WAIT | ARENA_NEXTFIT);
+       /* If we didn't NEXTFIT, the allocator would likely give us '1' back */
+       arena_free(a, o1, 1);
+       o3 = arena_alloc(a, 1, MEM_WAIT | ARENA_NEXTFIT);
+       KT_ASSERT(o3 == o2 + 1);
+       arena_free(a, o2, 1);
+       arena_free(a, o3, 1);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_bestfit(void)
+{
+       struct arena *a;
+       void *o1;
+
+       a = arena_create(__func__, NULL, 0, 1, NULL, NULL, NULL, 0, MEM_WAIT);
+       /* Each span will be an independent chunk in the allocator.  Their base
+        * values don't matter; they just identify the spans.
+        *
+        * BESTFIT for 65 should be 67.  INSTANTFIT should be 128.  The (128-1)
+        * objects around 67 are to make sure we check all objects on the 2^6
+        * list. */
+       arena_add(a, (void*)1000, 64, MEM_WAIT);
+       arena_add(a, (void*)3000, 128 - 1, MEM_WAIT);
+       arena_add(a, (void*)2000, 67, MEM_WAIT);
+       arena_add(a, (void*)4000, 128 - 1, MEM_WAIT);
+       arena_add(a, (void*)5000, 128, MEM_WAIT);
+       o1 = arena_alloc(a, 65, MEM_WAIT | ARENA_BESTFIT);
+       KT_ASSERT(o1 == (void*)2000);
+       arena_free(a, o1, 65);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_instantfit(void)
+{
+       struct arena *a;
+       void *o1;
+
+       a = arena_create(__func__, NULL, 0, 1, NULL, NULL, NULL, 0, MEM_WAIT);
+       arena_add(a, (void*)1000, 64, MEM_WAIT);
+       arena_add(a, (void*)2000, 67, MEM_WAIT);
+       arena_add(a, (void*)3000, 64, MEM_WAIT);
+       arena_add(a, (void*)4000, 128, MEM_WAIT);
+       o1 = arena_alloc(a, 65, MEM_WAIT | ARENA_INSTANTFIT);
+       KT_ASSERT(o1 == (void*)4000);
+       arena_free(a, o1, 65);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_quantum_align(void)
+{
+       struct arena *a;
+       void *o1, *o2;
+
+       a = arena_create(__func__, NULL, 0, 32, NULL, NULL, NULL, 0, MEM_WAIT);
+       /* this should give us one object only: */
+       arena_add(a, (void*)(4096 + 1), 64, MEM_WAIT);
+       /* 1 gets rounded up to quantum, so we're really asking for 32 */
+       o1 = arena_alloc(a, 1, MEM_WAIT);
+       KT_ASSERT(o1 == ROUNDUP((void*)(4096 + 1), a->quantum));
+       /* Should be nothing quantum-sized left */
+       o2 = arena_alloc(a, 1, MEM_ATOMIC);
+       KT_ASSERT(o2 == NULL);
+       arena_free(a, o1, 1);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_odd_quantum(void)
+{
+       struct arena *a;
+       void *o1, *o2;
+
+       a = arena_create(__func__, NULL, 0, 7, NULL, NULL, NULL, 0, MEM_WAIT);
+       arena_add(a, (void*)7, 49, MEM_WAIT);
+       o1 = arena_alloc(a, 7, MEM_WAIT);
+       KT_ASSERT(o1 == (void*)7);
+       o2 = arena_alloc(a, 7, MEM_WAIT);
+       KT_ASSERT(o2 == (void*)14);
+       arena_free(a, o1, 7);
+       arena_free(a, o2, 7);
+
+       /* In older arena code, this would fragment such that it could hand out
+        * non-quantum-aligned objects. */
+       o1 = arena_xalloc(a, 7, 4, 0, 0, NULL, NULL, MEM_WAIT);
+       o2 = arena_alloc(a, 7, MEM_WAIT);
+       KT_ASSERT(!((uintptr_t)o2 % 7));
+       arena_xfree(a, o1, 7);
+       arena_free(a, o2, 7);
+       arena_destroy(a);
+
+       return true;
+}
+
+/* The nocross-fallback hops over the first nocross boundary in a segment try,
+ * in the hopes that the rest of the segment can satisfy the constraints. */
+static bool test_nocross_fallback(void)
+{
+       struct arena *a;
+       void *o1;
+
+       a = arena_create(__func__, NULL, 0, 3, NULL, NULL, NULL, 0, MEM_WAIT);
+       arena_add(a, (void*)3, 20, MEM_WAIT);
+       o1 = arena_xalloc(a, 3, 1, 0, 4, NULL, NULL, MEM_WAIT);
+       /* 6 would be wrong.  We hopped over 4, but then didn't check that
+        * segment either (crosses 8). */
+       KT_ASSERT(o1 == (void*)9);
+       arena_xfree(a, o1, 3);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_xalloc_from_freelist(void)
+{
+       struct arena *a;
+       void *o1;
+
+       a = arena_create(__func__, NULL, 0, 1, NULL, NULL, NULL, 0, MEM_WAIT);
+       /* one object on the order 3 list: size [8, 15].  it also starts at 15,
+        * which will satisfy align=8 phase=7. */
+       arena_add(a, (void*)15, 15, MEM_WAIT);
+       /* adding phase + ALIGN(align) would have us look on the order 4 list,
+        * which is what older code did. */
+       o1 = arena_xalloc(a, 15, 8, 7, 0, NULL, NULL,
+                         MEM_ATOMIC | ARENA_BESTFIT);
+       KT_ASSERT(o1 == (void*)15);
+       arena_xfree(a, o1, 15);
+       arena_destroy(a);
+
+       return true;
+}
+
+/* Right now, instantfit failures do *not* fall back to bestfit.  If we ever do
+ * that, we can turn on this test.  {,x}alloc with a source will fallback to
+ * bestfit *after* it went to the source. */
+static bool test_alloc_instantfit_fallback(void)
+{
+       struct arena *a;
+       void *o1;
+
+       a = arena_create(__func__, NULL, 0, 1, NULL, NULL, NULL, 0, MEM_WAIT);
+       /* one object on the order 3 list: size [8, 15], at 1. */
+       arena_add(a, (void*)1, 15, MEM_WAIT);
+       o1 = arena_alloc(a, 15, MEM_ATOMIC);
+       KT_ASSERT(o1 == (void*)1);
+       arena_free(a, o1, 15);
+       o1 = arena_xalloc(a, 15, 1, 0, 0, NULL, NULL, MEM_ATOMIC);
+       KT_ASSERT(o1 == (void*)1);
+       arena_xfree(a, o1, 15);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_qcache(void)
+{
+       struct arena *a;
+       void *o1, *o2, *o3, *o4;
+
+       /* 3 qcaches */
+       a = arena_create(__func__, NULL, 0, 1, NULL, NULL, NULL, 3, MEM_WAIT);
+       arena_add(a, (void*)1, 10000, MEM_WAIT);
+       /* Alloc from each qc, plus the arena. */
+       o1 = arena_alloc(a, 1, MEM_WAIT);
+       o2 = arena_alloc(a, 2, MEM_WAIT);
+       o3 = arena_alloc(a, 3, MEM_WAIT);
+       o4 = arena_alloc(a, 4, MEM_WAIT);
+
+       arena_free(a, o1, 1);
+       arena_free(a, o2, 2);
+       arena_free(a, o3, 3);
+       arena_free(a, o4, 4);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_qc_odd_quantum(void)
+{
+       struct arena *a;
+       void *o[4];
+
+       /* 3 qcaches, non-power-of-two quantum.  This checks the slab guarantee
+        * that if slab objects (qcaches) are a multiple of source->quantum,
+        * then all allocations are multiples of quantum. */
+       a = arena_create(__func__, NULL, 0, 7, NULL, NULL, NULL, 21, MEM_WAIT);
+       arena_add(a, (void*)7, 10000, MEM_WAIT);
+       /* Alloc from each qc, plus the arena, ensure quantum alignment. */
+       for (int i = 1; i < 4; i++) {
+               size_t amt = 7 * i;
+
+               /* Get a few before checking them all */
+               for (int j = 0; j < ARRAY_SIZE(o); j++)
+                       o[j] = arena_alloc(a, amt, MEM_WAIT);
+               for (int j = 0; j < ARRAY_SIZE(o); j++)
+                       KT_ASSERT(!((uintptr_t)o[j] % 7));
+               for (int j = 0; j < ARRAY_SIZE(o); j++)
+                       arena_free(a, o[j], amt);
+       }
+       arena_destroy(a);
+
+       return true;
+}
+
+/* slab code had an issue with align > PGSIZE.  QCs are quantum aligned, so
+ * quantum > PGSIZE with a QC caused trouble. */
+static bool test_qc_large_quantum(void)
+{
+       struct arena *a;
+       void *o1;
+
+       a = arena_create(__func__, NULL, 0, 8192, NULL, NULL, NULL, 8192,
+                        MEM_WAIT);
+       arena_add(a, (void*)8192, 8192 * 4, MEM_WAIT);
+       o1 = arena_alloc(a, 8192, MEM_WAIT);
+       arena_free(a, o1, 8192);
+       arena_destroy(a);
+
+       return true;
+}
+
+/* Just examples of stuff you can do. */
+static void *tiaf(struct arena *a, size_t amt, int flags)
+{
+       void *obj = arena_alloc(a, amt, flags);
+
+       return (void*)((uintptr_t)obj << 15);
+}
+
+static void tiff(struct arena *a, void *obj, size_t amt)
+{
+       arena_free(a, (void*)((uintptr_t)obj >> 15), amt);
+}
+
+static bool test_import(void)
+{
+       struct arena *a, *s;
+       void *o1, *o2;
+
+       s = arena_create("test_import-source", NULL, 0, 4096, NULL, NULL, NULL,
+                        0, MEM_WAIT);
+       arena_add(s, (void*)4096, 4096 * 4, MEM_WAIT);
+       a = arena_create("test_import-actual", NULL, 0, 1, tiaf, tiff, s, 2,
+                        MEM_WAIT);
+
+       o1 = arena_alloc(a, 1, MEM_WAIT);
+       o2 = arena_alloc(a, 2, MEM_WAIT);
+       /* Make sure our handlers run.  The source gives 'a' addresses around
+        * 4096, which the import funcs translate to above 1 << 15. */
+       KT_ASSERT((uintptr_t)o1 >= (1 << 15));
+       KT_ASSERT((uintptr_t)o2 >= (1 << 15));
+
+       arena_free(a, o1, 1);
+       arena_free(a, o2, 2);
+       arena_destroy(a);
+       arena_destroy(s);
+
+       return true;
+}
+
+static bool test_import_slab(void)
+{
+       struct arena *s;
+       struct kmem_cache *kc;
+       void *o[3];
+
+       s = arena_create(__func__, NULL, 0, 7, NULL, NULL, NULL,
+                        0, MEM_WAIT);
+       /* We need to have a sizable amount here, since the KCs will pull a lot
+        * of resources when growing.  7000 isn't enough. */
+       arena_add(s, (void*)7, 70000, MEM_WAIT);
+
+       /* Quantum-preserving guarantee */
+       kc = kmem_cache_create("test_import_slab-QP", 14, 1, KMC_NOTOUCH, s,
+                              NULL, NULL, NULL);
+       for (int i = 0; i < ARRAY_SIZE(o); i++)
+               o[i] = kmem_cache_alloc(kc, MEM_WAIT);
+       for (int i = 0; i < ARRAY_SIZE(o); i++)
+               KT_ASSERT(!((uintptr_t)o[i] % 7));
+       for (int i = 0; i < ARRAY_SIZE(o); i++)
+               kmem_cache_free(kc, o[i]);
+       kmem_cache_destroy(kc);
+
+
+       /* Listen to slab's alignment guarantee */
+       kc = kmem_cache_create("test_import_slab-AG", 1, 16, KMC_NOTOUCH, NULL,
+                              NULL, NULL, NULL);
+       for (int i = 0; i < ARRAY_SIZE(o); i++)
+               o[i] = kmem_cache_alloc(kc, MEM_WAIT);
+       for (int i = 0; i < ARRAY_SIZE(o); i++)
+               KT_ASSERT(ALIGNED(o[i], 16));
+       for (int i = 0; i < ARRAY_SIZE(o); i++)
+               kmem_cache_free(kc, o[i]);
+       kmem_cache_destroy(kc);
+
+
+       arena_destroy(s);
+
+       return true;
+}
+
+/* Arena import code wasn't grabbing enough, such that when we aligned the
+ * source object to a's np2sb (which happened to be a power of 2), we had
+ * nothing left to actually put in the arena.
+ *
+ * Additionally, arena's weren't freeing the segment back to their sources. */
+static bool test_import_alignment(void)
+{
+       struct arena *s, *a;
+       void *o1;
+
+       s = arena_create("test_import_alignment-s", NULL, 0, 1,
+                        NULL, NULL, NULL, 0, MEM_WAIT);
+       arena_add(s, (void*)1, 1000, MEM_WAIT);
+       a = arena_create("test_import_alignment-a", NULL, 0, 16,
+                        arena_alloc, arena_free, s,
+                        0, MEM_WAIT);
+       o1 = arena_alloc(a, 16, MEM_WAIT);
+       KT_ASSERT(o1);
+       arena_free(a, o1, 16);
+       arena_destroy(a);
+       arena_destroy(s);
+
+       return true;
+}
+
+static bool test_xalloc(void)
+{
+       struct arena *a;
+       void *o1, *o2, *o3, *o4;
+
+       a = arena_create(__func__, NULL, 0, 3, NULL, NULL, NULL, 0, MEM_WAIT);
+       arena_add(a, (void*)3, 4096, MEM_WAIT);
+
+       /* align 16, phase 6 */
+       o1 = arena_xalloc(a, 3, 16, 6, 0, NULL, NULL, MEM_WAIT);
+       KT_ASSERT(ALIGNED((uintptr_t)o1 - 6, 16));
+       KT_ASSERT(!((uintptr_t)o1 % 3));
+
+       /* nocross 16 */
+       o2 = arena_xalloc(a, 15, 1, 0, 16, NULL, NULL, MEM_WAIT);
+       KT_ASSERT(!((uintptr_t)o2 % 3));
+       KT_ASSERT(ROUNDUP(o2 + 1, 16) >= o2 + 15);
+
+       /* min 81, max 252.  should be available. */
+       o3 = arena_xalloc(a, 3, 1, 0, 0, (void*)81, (void*)252, MEM_WAIT);
+       KT_ASSERT(!((uintptr_t)o3 % 3));
+       KT_ASSERT(81 <= (uintptr_t)o3 && (uintptr_t)o3 < 252);
+
+       /* older xalloc code could hand out non-free segments! */
+       o4 = arena_xalloc(a, 3, 1, 0, 0, (void*)81, (void*)252, MEM_WAIT);
+       KT_ASSERT(!((uintptr_t)o4 % 3));
+       KT_ASSERT(81 <= (uintptr_t)o4 && (uintptr_t)o4 < 252);
+       KT_ASSERT(o4 != o3);
+
+       arena_xfree(a, o1, 3);
+       arena_xfree(a, o2, 15);
+       arena_xfree(a, o3, 3);
+       arena_xfree(a, o4, 3);
+       arena_destroy(a);
+
+       return true;
+}
+
+static bool test_xalloc_minmax(void)
+{
+       struct arena *a;
+       void *o1, *o2;
+
+       a = arena_create(__func__, NULL, 0, 1, NULL, NULL, NULL, 0, MEM_WAIT);
+       arena_add(a, (void*)1, 100, MEM_WAIT);
+       o1 = arena_xalloc(a, 20, 1, 0, 0, (void*)10, (void*)30, MEM_ATOMIC);
+       KT_ASSERT((uintptr_t)o1 == 10);
+       o2 = arena_xalloc(a, 20, 1, 0, 0, (void*)30, (void*)50, MEM_ATOMIC);
+       KT_ASSERT((uintptr_t)o2 == 30);
+       arena_xfree(a, o1, 20);
+       arena_xfree(a, o2, 20);
+       arena_destroy(a);
+
+       return true;
+}
+
+/* Note we don't use qcaches - they throw off the measurements, since all qcache
+ * objects (free or not) are counted as allocated from the arena's perspective.
+ */
+static bool test_accounting(void)
+{
+       struct arena *a;
+       void *o1, *o2;
+
+       a = arena_create(__func__, NULL, 0, 1, NULL, NULL, NULL, 0, MEM_WAIT);
+       arena_add(a, (void*)1, 100, MEM_WAIT);
+       KT_ASSERT(arena_amt_free(a) == 100);
+       KT_ASSERT(arena_amt_total(a) == 100);
+
+       /* Ensuring some fragmentation */
+       o1 = arena_xalloc(a, 15, 1, 0, 0, (void*)10, (void*)40, MEM_WAIT);
+       o2 = arena_xalloc(a, 15, 1, 0, 0, (void*)50, (void*)90, MEM_WAIT);
+
+       KT_ASSERT(arena_amt_free(a) == 70);
+       KT_ASSERT(arena_amt_total(a) == 100);
+
+       arena_free(a, o1, 15);
+       arena_free(a, o2, 15);
+       arena_destroy(a);
+
+       return true;
+}
+
+static struct ktest ktests[] = {
+       KTEST_REG(nextfit,              CONFIG_KTEST_ARENA),
+       KTEST_REG(bestfit,              CONFIG_KTEST_ARENA),
+       KTEST_REG(instantfit,           CONFIG_KTEST_ARENA),
+       KTEST_REG(quantum_align,        CONFIG_KTEST_ARENA),
+       KTEST_REG(odd_quantum,          CONFIG_KTEST_ARENA),
+       KTEST_REG(nocross_fallback,     CONFIG_KTEST_ARENA),
+       KTEST_REG(xalloc_from_freelist, CONFIG_KTEST_ARENA),
+       KTEST_REG(qcache,               CONFIG_KTEST_ARENA),
+       KTEST_REG(qc_odd_quantum,       CONFIG_KTEST_ARENA),
+       KTEST_REG(qc_large_quantum,     CONFIG_KTEST_ARENA),
+       KTEST_REG(import,               CONFIG_KTEST_ARENA),
+       KTEST_REG(import_slab,          CONFIG_KTEST_ARENA),
+       KTEST_REG(import_alignment,     CONFIG_KTEST_ARENA),
+       KTEST_REG(xalloc,               CONFIG_KTEST_ARENA),
+       KTEST_REG(xalloc_minmax,        CONFIG_KTEST_ARENA),
+       KTEST_REG(accounting,           CONFIG_KTEST_ARENA),
+};
+
+static int num_ktests = sizeof(ktests) / sizeof(struct ktest);
+
+static void __init register_arena_ktests(void)
+{
+        REGISTER_KTESTS(ktests, num_ktests);
+}
+init_func_1(register_arena_ktests);