For your inspection: small id pool
[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
7 struct idpool *init(int size)
8 {
9         int i;
10         struct idpool *id;
11         if (size > MAXAMT)
12                 return NULL;
13         id = malloc(sizeof(*id) + 2*(size+1) + (size + 1));
14         id->size = size;
15         id->ids = (void *)&id[1];
16         id->check = (void *)&id->ids[id->size + 1];
17         for(i = 0; i < id->size+1; i++) {
18                 id->ids[i] = i;
19                 // fe rhymes with "free"
20                 id->check[i] = 0xfe;
21         }
22         // set tos.
23         id->ids[0] = 1;
24         return id;
25 }
26
27
28 int pop(struct idpool *id)
29 {
30         int tos, v;
31         if (id->ids[0] == id->size) {
32                 return -1;
33         }
34         /* NOT SMP SAFE! CAN'T USE IT YET!
35          * the intent here is that we want to be able to atomic ops on the stack pointer
36          * and avoid locking. One way might be to load it and, if it's in range, do a CAS.
37          */
38         tos = id->ids[0];
39         id->ids[0]++;
40         v = id->ids[tos];
41         if (id->check[v] != 0xfe) {
42                 printk("BAD! %d is already allocated (0x%x)\n", v, id->check[v]);
43                 return -1;
44         }
45         id->check[v] = 0x5a;
46         return v;
47 }
48
49 void push(struct idpool *id, int v)
50 {
51         int tos;
52         if (id->check[v] != 0x5a) {
53                 panic("BAD! freeing non-allocated: %d(0x%x)\n", v, id->check[v]);
54                 return;
55         }
56         id->ids[0]--;
57         tos = id->ids[0];
58         id->ids[tos] = v;
59         id->check[v] = 0xfe;
60 }