kern/src/smallidpool.c

   1 /* Copyright (c) 2015 Google Inc.
   2  * Ron Minnich <rminnich@google.com>
   3  * Barret Rhoden <brho@cs.berkeley.edu>
   4  *
   5  * Trivial thread-safe ID pool for small sets of things (< 64K)
   6  * implemented as a stack.
   7  */
   8
   9 #include <smallidpool.h>
  10 #include <kmalloc.h>
  11 #include <atomic.h>
  12 #include <stdio.h>
  13 #include <assert.h>
  14
  15 struct u16_pool *create_u16_pool(unsigned int size)
  16 {
  17         struct u16_pool *id;
  18         /* We could have size be a u16, but this might catch bugs where users
  19          * tried to ask for more than 2^16 and had it succeed. */
  20         if (size > MAX_U16_POOL_SZ)
  21                 return NULL;
  22         /* ids and check are alloced and aligned right after the id struct */
  23         id = kmalloc(sizeof(*id) + sizeof(uint16_t) * size + size, MEM_WAIT);
  24         spinlock_init_irqsave(&id->lock);
  25         id->size = size;
  26         id->ids = (void *)&id[1];
  27         id->check = (void *)&id->ids[id->size];
  28         for (int i = 0; i < id->size; i++) {
  29                 id->ids[i] = i;
  30                 // fe rhymes with "free"
  31                 id->check[i] = 0xfe;
  32         }
  33         id->tos = 0;
  34         return id;
  35 }
  36
  37 /* Returns an unused u16, or -1 on failure (pool full or corruption).
  38  *
  39  * The invariant is that the stackpointer (TOS) will always point to the next
  40  * slot that can be popped, if there are any.  All free slots will be below the
  41  * TOS, ranging from indexes [0, TOS), where if TOS == 0, then there are no free
  42  * slots to push.  The last valid slot is when TOS == size - 1. */
  43 int get_u16(struct u16_pool *id)
  44 {
  45         uint16_t v;
  46         spin_lock_irqsave(&id->lock);
  47         if (id->tos == id->size) {
  48                 spin_unlock_irqsave(&id->lock);
  49                 return -1;
  50         }
  51         v = id->ids[id->tos++];
  52         spin_unlock_irqsave(&id->lock);
  53         /* v is ours, we can freely read and write its check field */
  54         if (id->check[v] != 0xfe) {
  55                 printk("BAD! %d is already allocated (0x%x)\n", v, id->check[v]);
  56                 return -1;
  57         }
  58         id->check[v] = 0x5a;
  59         return v;
  60 }
  61
  62 void put_u16(struct u16_pool *id, int v)
  63 {
  64         /* we could check for if v is in range before dereferencing. */
  65         if (id->check[v] != 0x5a) {
  66                 printk("BAD! freeing non-allocated: %d(0x%x)\n", v, id->check[v]);
  67                 return;
  68         }
  69         id->check[v] = 0xfe;
  70         spin_lock_irqsave(&id->lock);
  71         id->ids[--id->tos] = v;
  72         spin_unlock_irqsave(&id->lock);
  73 }