Cleans up smallpool, adds locking
authorBarret Rhoden <brho@cs.berkeley.edu>
Wed, 28 Jan 2015 18:22:09 +0000 (13:22 -0500)
committerBarret Rhoden <brho@cs.berkeley.edu>
Thu, 29 Jan 2015 02:44:35 +0000 (21:44 -0500)
I tried various CAS schemes, but they don't work very well.  Using a
history counter, I was able to make get/pop lock-free, but not put/push.
The issue was that the pusher needs to have 'v' written by the time it
decrements, but it can't be sure of its slot when until decrement
succeeds.  It would work with only one pusher, or with an additional
'ready' flag per slot, similar to BCQs.

kern/include/smallidpool.h
kern/src/Kbuild
kern/src/smallidpool.c

index a775e7f..fd7c3e7 100644 (file)
@@ -1,19 +1,40 @@
 /* Copyright (c) 2015 Google Inc.
+ * Ron Minnich <rminnich@google.com>
+ * Barret Rhoden <brho@cs.berkeley.edu>
  *
- * Trivial ID pool for small sets of things (< 64K)
+ * Trivial thread-safe ID pool for small sets of things (< 64K)
  * implemented as a stack.
  */
 
-#define MAXAMT 65535
+#ifndef ROS_KERN_SMALLIDPOOL_H
+#define ROS_KERN_SMALLIDPOOL_H
 
-// Element 0 is top of stack pointer. It  initially points to 1.
-// You therefore can not get ID 0. The max id you can get is 65534,
-// due to the use of uint16_t for the stack elements. That covers just
-// about everything we've ever needed.
-// The check array is used instead of a bitfield because these architectures
-// suck at those.
-struct idpool {
-       unit16_t *ids;
-       unit8_t *check;
+#define MAX_U16_POOL_SZ (1 << 16)
+
+#include <atomic.h>
+
+/* IDS is the stack of 16 bit integers we give out.  TOS is the top of stack -
+ * it is the index of the next slot that can be popped, if there are any.  It's
+ * a u32 so it can be greater than a u16.
+ *
+ * All free slots in ids will be below the TOS, ranging from indexes [0, TOS),
+ * where if TOS == 0, then there are no free slots to push.
+ *
+ * We can hand out u16s in the range [0, 65535].
+ *
+ * The check array is used instead of a bitfield because these architectures
+ * suck at those. */
+
+struct u16_pool {
+       spinlock_t lock;
+       uint32_t tos;
+       uint16_t *ids;
+       uint8_t *check;
        int size;
 };
+
+struct u16_pool *create_u16_pool(unsigned int size);
+int get_u16(struct u16_pool *id);
+void put_u16(struct u16_pool *id, int v);
+
+#endif /* ROS_KERN_SMALLIDPOOL_H */
index 4cb25b3..4b83645 100644 (file)
@@ -43,6 +43,7 @@ obj-y                                         += rendez.o
 obj-y                                          += rwlock.o
 obj-y                                          += schedule.o
 obj-y                                          += slab.o
+obj-y                                          += smallidpool.o
 obj-y                                          += smp.o
 obj-y                                          += string.o
 obj-y                                          += strstr.o
index fba964a..42f7931 100644 (file)
@@ -1,61 +1,56 @@
 /* Copyright (c) 2015 Google Inc.
+ * Ron Minnich <rminnich@google.com>
+ * Barret Rhoden <brho@cs.berkeley.edu>
  *
- * Trivial ID pool for small sets of things (< 64K)
+ * Trivial thread-safe ID pool for small sets of things (< 64K)
  * implemented as a stack.
- *
- * TODO:
- * - Kbuild, change function names, kmalloc, ifdefs, size should be unsigned
- * - walk through what happens if size == 0.  See TODO below in pop.
- * - look into CAS options.  The problem is that although we can CAS on TOS, we
- *   cannot yank out v without some sort of ABA issue.  maybe if we have a
- *   separate index variable and maintain a history counter along with the idx.
- * - maybe build in locking, if we think we'll have an SMP-safe option?
  */
 
-struct idpool *init(int size)
+#include <smallidpool.h>
+#include <kmalloc.h>
+#include <atomic.h>
+#include <stdio.h>
+#include <assert.h>
+
+struct u16_pool *create_u16_pool(unsigned int size)
 {
-       int i;
-       struct idpool *id;
-       /* they give us e.g. size = 65535, we make an array of 65536 elements.
-        * array[0] is a tracking slot, not an item slot.  so there are still only
-        * 65535 elements available, numbered 1..65535 (which is the max u16). */
-       if (size > MAXAMT)
+       struct u16_pool *id;
+       /* We could have size be a u16, but this might catch bugs where users
+        * tried to ask for more than 2^16 and had it succeed. */
+       if (size > MAX_U16_POOL_SZ)
                return NULL;
-       id = malloc(sizeof(*id) + 2 * (size + 1) + (size + 1));
+       /* ids and check are alloced and aligned right after the id struct */
+       id = kmalloc(sizeof(*id) + sizeof(uint16_t) * size + size, KMALLOC_WAIT);
+       spinlock_init_irqsave(&id->lock);
        id->size = size;
        id->ids = (void *)&id[1];
-       id->check = (void *)&id->ids[id->size + 1];
-       for (i = 0; i < id->size + 1; i++) {
+       id->check = (void *)&id->ids[id->size];
+       for (int i = 0; i < id->size; i++) {
                id->ids[i] = i;
                // fe rhymes with "free"
                id->check[i] = 0xfe;
        }
-       // set tos.
-       id->ids[0] = 1;
-       id->check[0] = 0x5a;    /* never give out id 0 */
+       id->tos = 0;
        return id;
 }
 
-/* The invariant is that the stackpointer (TOS) will always point to the next
+/* Returns an unused u16, or -1 on failure (pool full or corruption).
+ *
+ * The invariant is that the stackpointer (TOS) will always point to the next
  * slot that can be popped, if there are any.  All free slots will be below the
- * TOS, ranging from indexes [1, TOS), where if TOS == 1, then there are no free
- * slots to push. */
-int pop(struct idpool *id)
+ * TOS, ranging from indexes [0, TOS), where if TOS == 0, then there are no free
+ * slots to push.  The last valid slot is when TOS == size - 1. */
+int get_u16(struct u16_pool *id)
 {
-       int tos, v;
-       /* TODO: is this off by one?  this means we won't give out 65535.  right
-        * now, we are pointing at the last valid slot, right?  Based on how push
-        * subtracts right away, it should be okay. */
-       if (id->ids[0] == id->size) {
+       uint16_t v;
+       spin_lock_irqsave(&id->lock);
+       if (id->tos == id->size) {
+               spin_unlock_irqsave(&id->lock);
                return -1;
        }
-       /* NOT SMP SAFE! CAN'T USE IT YET!  the intent here is that we want to be
-        * able to atomic ops on the stack pointer and avoid locking. One way might
-        * be to load it and, if it's in range, do a CAS.
-        */
-       tos = id->ids[0];
-       id->ids[0]++;
-       v = id->ids[tos];
+       v = id->ids[id->tos++];
+       spin_unlock_irqsave(&id->lock);
+       /* v is ours, we can freely read and write its check field */
        if (id->check[v] != 0xfe) {
                printk("BAD! %d is already allocated (0x%x)\n", v, id->check[v]);
                return -1;
@@ -64,15 +59,15 @@ int pop(struct idpool *id)
        return v;
 }
 
-void push(struct idpool *id, int v)
+void put_u16(struct u16_pool *id, int v)
 {
-       int tos;
+       /* we could check for if v is in range before dereferencing. */
        if (id->check[v] != 0x5a) {
-               panic("BAD! freeing non-allocated: %d(0x%x)\n", v, id->check[v]);
+               printk("BAD! freeing non-allocated: %d(0x%x)\n", v, id->check[v]);
                return;
        }
-       id->ids[0]--;
-       tos = id->ids[0];
-       id->ids[tos] = v;
        id->check[v] = 0xfe;
+       spin_lock_irqsave(&id->lock);
+       id->ids[--id->tos] = v;
+       spin_unlock_irqsave(&id->lock);
 }