Lindent + comments
[akaros.git] / kern / src / smallidpool.c
1 /* Copyright (c) 2015 Google Inc.
2  *
3  * Trivial ID pool for small sets of things (< 64K)
4  * implemented as a stack.
5  *
6  * TODO:
7  * - Kbuild, change function names, kmalloc, ifdefs, size should be unsigned
8  * - walk through what happens if size == 0.  See TODO below in pop.
9  * - look into CAS options.  The problem is that although we can CAS on TOS, we
10  *   cannot yank out v without some sort of ABA issue.  maybe if we have a
11  *   separate index variable and maintain a history counter along with the idx.
12  * - maybe build in locking, if we think we'll have an SMP-safe option?
13  */
14
15 struct idpool *init(int size)
16 {
17         int i;
18         struct idpool *id;
19         /* they give us e.g. size = 65535, we make an array of 65536 elements.
20          * array[0] is a tracking slot, not an item slot.  so there are still only
21          * 65535 elements available, numbered 1..65535 (which is the max u16). */
22         if (size > MAXAMT)
23                 return NULL;
24         id = malloc(sizeof(*id) + 2 * (size + 1) + (size + 1));
25         id->size = size;
26         id->ids = (void *)&id[1];
27         id->check = (void *)&id->ids[id->size + 1];
28         for (i = 0; i < id->size + 1; i++) {
29                 id->ids[i] = i;
30                 // fe rhymes with "free"
31                 id->check[i] = 0xfe;
32         }
33         // set tos.
34         id->ids[0] = 1;
35         id->check[0] = 0x5a;    /* never give out id 0 */
36         return id;
37 }
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 [1, TOS), where if TOS == 1, then there are no free
42  * slots to push. */
43 int pop(struct idpool *id)
44 {
45         int tos, v;
46         /* TODO: is this off by one?  this means we won't give out 65535.  right
47          * now, we are pointing at the last valid slot, right?  Based on how push
48          * subtracts right away, it should be okay. */
49         if (id->ids[0] == id->size) {
50                 return -1;
51         }
52         /* NOT SMP SAFE! CAN'T USE IT YET!  the intent here is that we want to be
53          * able to atomic ops on the stack pointer and avoid locking. One way might
54          * be to load it and, if it's in range, do a CAS.
55          */
56         tos = id->ids[0];
57         id->ids[0]++;
58         v = id->ids[tos];
59         if (id->check[v] != 0xfe) {
60                 printk("BAD! %d is already allocated (0x%x)\n", v, id->check[v]);
61                 return -1;
62         }
63         id->check[v] = 0x5a;
64         return v;
65 }
66
67 void push(struct idpool *id, int v)
68 {
69         int tos;
70         if (id->check[v] != 0x5a) {
71                 panic("BAD! freeing non-allocated: %d(0x%x)\n", v, id->check[v]);
72                 return;
73         }
74         id->ids[0]--;
75         tos = id->ids[0];
76         id->ids[tos] = v;
77         id->check[v] = 0xfe;
78 }