Radix Bug - growing quickly
[akaros.git] / kern / src / radix.c
1 /* Copyright (c) 2010 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Radix Trees!  Just the basics, doesn't do tagging or anything fancy. */
6
7 #include <ros/errno.h>
8 #include <radix.h>
9 #include <slab.h>
10 #include <string.h>
11 #include <stdio.h>
12
13 struct kmem_cache *radix_kcache;
14 static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
15                                               unsigned long key,
16                                               bool extend);
17 static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **slot);
18
19 /* Initializes the radix tree system, mostly just builds the kcache */
20 void radix_init(void)
21 {
22         radix_kcache = kmem_cache_create("radix_nodes", sizeof(struct radix_node),
23                                          __alignof__(struct radix_node), 0, 0, 0);
24 }
25
26 /* Initializes a tree dynamically */
27 void radix_tree_init(struct radix_tree *tree)
28 {
29         tree->root = 0;
30         tree->depth = 0;
31         tree->upper_bound = 0;
32 }
33
34 /* Will clean up all the memory associated with a tree.  Shouldn't be necessary
35  * if you delete all of the items, which you should do anyways since they are
36  * usually void*.  Might expand this to have a function to call on every leaf
37  * slot. */
38 void radix_tree_destroy(struct radix_tree *tree)
39 {
40         panic("Not implemented");
41 }
42
43 /* Attempts to insert an item in the tree at the given key.  ENOMEM if we ran
44  * out of memory, EEXIST if an item is already in the tree. */
45 int radix_insert(struct radix_tree *tree, unsigned long key, void *item)
46 {
47         struct radix_node *r_node;
48         void **slot;
49         /* Is the tree tall enough?  if not, it needs to grow a level.  This will
50          * also create the initial node (upper bound starts at 0). */
51         while (key >= tree->upper_bound) {
52                 r_node = kmem_cache_alloc(radix_kcache, 0);
53                 if (!r_node)
54                         return -ENOMEM;
55                 memset(r_node, 0, sizeof(struct radix_node));
56                 if (tree->root) {
57                         /* tree->root is the old root, now a child of the future root */
58                         r_node->items[0] = tree->root;
59                         tree->root->parent = r_node;
60                         tree->root->my_slot = (struct radix_node**)&r_node->items[0];
61                         r_node->num_items = 1;
62                 } else {
63                         /* if there was no root before, we're both the root and a leaf */
64                         r_node->leaf = TRUE;
65                 }
66                 tree->root = r_node;
67                 r_node->my_slot = &tree->root;
68                 tree->depth++;
69                 tree->upper_bound = 1 << (LOG_RNODE_SLOTS * tree->depth);
70         }
71         /* the tree now thinks it is tall enough, so find the last node, insert in
72          * it, etc */
73         r_node = __radix_lookup_node(tree, key, TRUE);
74         assert(r_node);         /* we want an ENOMEM actually, but i want to see this */
75         slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
76         if (*slot)
77                 return -EEXIST;
78         *slot = item;
79         r_node->num_items++;
80         return 0;
81 }
82
83 /* Removes an item from it's parent's structure, freeing the parent if there is
84  * nothing left, potentially recursively. */
85 static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **slot)
86 {
87         assert(*slot);          /* make sure there is something there */
88         *slot = 0;
89         r_node->num_items--;
90         if (!r_node->num_items) {
91                 if (r_node->parent)
92                         __radix_remove_slot(r_node->parent, r_node->my_slot);
93                 else                    /* we're the last node, attached to the actual tree */
94                         *(r_node->my_slot) = 0;
95                 kmem_cache_free(radix_kcache, r_node);
96         }
97 }
98
99 /* Removes a key/item from the tree, returning that item (the void*).  If it
100  * detects a radix_node is now unused, it will dealloc that node.  Though the
101  * tree will still think it is tall enough to handle its old upper_bound.  It
102  * won't "shrink". */
103 void *radix_delete(struct radix_tree *tree, unsigned long key)
104 {
105         void **slot;
106         void *retval;
107         struct radix_node *r_node = __radix_lookup_node(tree, key, 0);
108         if (!r_node)
109                 return 0;
110         slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
111         retval = *slot;
112         if (retval) {
113                 __radix_remove_slot(r_node, (struct radix_node**)slot); 
114         } else {
115                 /* it's okay to delete an empty, but i want to know about it for now */
116                 warn("Tried to remove a non-existant item from a radix tree!");
117         }
118         return retval;
119 }
120
121 /* Returns the item for a given key.  0 means no item, etc. */
122 void *radix_lookup(struct radix_tree *tree, unsigned long key)
123 {
124         void **slot = radix_lookup_slot(tree, key);
125         if (!slot)
126                 return 0;
127         return *slot;
128 }
129
130 /* Returns a pointer to the radix_node holding a given key.  0 if there is no
131  * such node, due to the tree being too small or something.
132  *
133  * If the depth is greater than one, we need to walk down the tree a level.  The
134  * key is 'partitioned' among the levels of the tree, like so:
135  * ......444444333333222222111111
136  *
137  * If an interior node of the tree is missing, this will add one if it was
138  * directed to extend the tree. */
139 static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
140                                               unsigned long key, bool extend)
141 {
142         unsigned long idx;
143         struct radix_node *child_node, *r_node = tree->root;
144         if (key >= tree->upper_bound) {
145                 if (extend)
146                         warn("Bound (%d) not set for key %d!\n", tree->upper_bound, key);
147                 return 0;
148         }
149         for (int i = tree->depth; i > 1; i--) {  /* i = ..., 4, 3, 2 */
150                 idx = (key >> (LOG_RNODE_SLOTS * (i - 1))) & (NR_RNODE_SLOTS - 1);
151                 /* There might not be a node at this part of the tree */
152                 if (!r_node->items[idx]) {
153                         if (!extend) {
154                                 return 0;
155                         } else {
156                                 /* so build one, possibly returning 0 if we couldn't */
157                                 child_node = kmem_cache_alloc(radix_kcache, 0);
158                                 if (!child_node)
159                                         return 0;
160                                 r_node->items[idx] = child_node;
161                                 memset(child_node, 0, sizeof(struct radix_node));
162                                 /* when we are on the last iteration (i == 2), the child will be
163                                  * a leaf. */
164                                 child_node->leaf = (i == 2) ? TRUE : FALSE;
165                                 child_node->parent = r_node;
166                                 child_node->my_slot = (struct radix_node**)&r_node->items[idx];
167                                 r_node->num_items++;
168                                 r_node = (struct radix_node*)r_node->items[idx];
169                         }
170                 } else {
171                         r_node = (struct radix_node*)r_node->items[idx];
172                 }
173         }
174         return r_node;
175 }
176
177 /* Returns a pointer to the slot for the given key.  0 if there is no such slot,
178  * etc */
179 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key)
180 {
181         struct radix_node *r_node = __radix_lookup_node(tree, key, FALSE);
182         if (!r_node)
183                 return 0;
184         key = key & (NR_RNODE_SLOTS - 1);
185         return &r_node->items[key];
186 }
187
188 int radix_gang_lookup(struct radix_tree *tree, void **results,
189                       unsigned long first, unsigned int max_items)
190 {
191         panic("Not implemented");
192         return -1; /* TODO! */
193 }
194
195
196 int radix_grow(struct radix_tree *tree, unsigned long max)
197 {
198         panic("Not implemented");
199         return -1; /* TODO! */
200 }
201
202 int radix_preload(struct radix_tree *tree, int flags)
203 {
204         panic("Not implemented");
205         return -1; /* TODO! */
206 }
207
208
209 void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag)
210 {
211         panic("Tagging not implemented!");
212         return (void*)-1; /* TODO! */
213 }
214
215 void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag)
216 {
217         panic("Tagging not implemented!");
218         return (void*)-1; /* TODO! */
219 }
220
221 int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag)
222 {
223         panic("Tagging not implemented!");
224         return -1; /* TODO! */
225 }
226
227 int radix_tree_tagged(struct radix_tree *tree, int tag)
228 {
229         panic("Tagging not implemented!");
230         return -1; /* TODO! */
231 }
232
233 int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
234                           unsigned long first, unsigned int max_items, int tag)
235 {
236         panic("Tagging not implemented!");
237         return -1; /* TODO! */
238 }
239
240 void print_radix_tree(struct radix_tree *tree)
241 {
242         printk("Tree %08p, Depth: %d, Bound: %d\n", tree, tree->depth,
243                tree->upper_bound);
244
245         void print_rnode(struct radix_node *r_node, int depth)
246         {
247                 if (!r_node)
248                         return;
249                 char buf[32] = {0};
250                 for (int i = 0; i < depth; i++)
251                         buf[i] = '\t';
252                 printk("%sRnode %08p, parent %08p, myslot %08p, %d items, leaf? %d\n",
253                        buf, r_node, r_node->parent, r_node->my_slot, r_node->num_items,
254                        r_node->leaf);
255                 for (int i = 0; i < NR_RNODE_SLOTS; i++) {
256                         if (!r_node->items[i])
257                                 continue;
258                         if (r_node->leaf)
259                                 printk("\t%sRnode Item %d: %08p\n", buf, i, r_node->items[i]);
260                         else
261                                 print_rnode(r_node->items[i], depth + 1);
262                 }
263         }
264         print_rnode(tree->root, 0);
265 }