radix: Add for_each iterators
[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",
23                                          sizeof(struct radix_node),
24                                          __alignof__(struct radix_node), 0,
25                                          NULL, 0, 0, NULL);
26 }
27
28 /* Initializes a tree dynamically */
29 void radix_tree_init(struct radix_tree *tree)
30 {
31         tree->root = 0;
32         tree->depth = 0;
33         tree->upper_bound = 0;
34 }
35
36 /* Will clean up all the memory associated with a tree.  Shouldn't be necessary
37  * if you delete all of the items, which you should do anyways since they are
38  * usually void*.  Might expand this to have a function to call on every leaf
39  * slot. */
40 void radix_tree_destroy(struct radix_tree *tree)
41 {
42         /* Currently, we may have a root node, even if all the elements were removed
43          */
44         panic("Not implemented");
45 }
46
47 /* Attempts to insert an item in the tree at the given key.  ENOMEM if we ran
48  * out of memory, EEXIST if an item is already in the tree.  On success, will
49  * also return the slot pointer, if requested. */
50 int radix_insert(struct radix_tree *tree, unsigned long key, void *item,
51                  void ***slot_p)
52 {
53         printd("RADIX: insert %p at %d\n", item, key);
54         struct radix_node *r_node;
55         void **slot;
56         /* Is the tree tall enough?  if not, it needs to grow a level.  This will
57          * also create the initial node (upper bound starts at 0). */
58         while (key >= tree->upper_bound) {
59                 r_node = kmem_cache_alloc(radix_kcache, 0);
60                 if (!r_node)
61                         return -ENOMEM;
62                 memset(r_node, 0, sizeof(struct radix_node));
63                 if (tree->root) {
64                         /* tree->root is the old root, now a child of the future root */
65                         r_node->items[0] = tree->root;
66                         tree->root->parent = r_node;
67                         tree->root->my_slot = (struct radix_node**)&r_node->items[0];
68                         r_node->num_items = 1;
69                 } else {
70                         /* if there was no root before, we're both the root and a leaf */
71                         r_node->leaf = TRUE;
72                         r_node->parent = 0;
73                 }
74                 tree->root = r_node;
75                 r_node->my_slot = &tree->root;
76                 tree->depth++;
77                 tree->upper_bound = 1ULL << (LOG_RNODE_SLOTS * tree->depth);
78         }
79         assert(tree->root);
80         /* the tree now thinks it is tall enough, so find the last node, insert in
81          * it, etc */
82         r_node = __radix_lookup_node(tree, key, TRUE);
83         assert(r_node);         /* we want an ENOMEM actually, but i want to see this */
84         slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
85         if (*slot)
86                 return -EEXIST;
87         *slot = item;
88         r_node->num_items++;
89         if (slot_p)
90                 *slot_p = slot;
91         return 0;
92 }
93
94 /* Removes an item from it's parent's structure, freeing the parent if there is
95  * nothing left, potentially recursively. */
96 static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **slot)
97 {
98         assert(*slot);          /* make sure there is something there */
99         *slot = 0;
100         r_node->num_items--;
101         /* this check excludes the root, but the if else handles it.  For now, once
102          * we have a root, we'll always keep it (will need some changing in
103          * radix_insert() */
104         if (!r_node->num_items && r_node->parent) {
105                 if (r_node->parent)
106                         __radix_remove_slot(r_node->parent, r_node->my_slot);
107                 else                    /* we're the last node, attached to the actual tree */
108                         *(r_node->my_slot) = 0;
109                 kmem_cache_free(radix_kcache, r_node);
110         }
111 }
112
113 /* Removes a key/item from the tree, returning that item (the void*).  If it
114  * detects a radix_node is now unused, it will dealloc that node.  Though the
115  * tree will still think it is tall enough to handle its old upper_bound.  It
116  * won't "shrink". */
117 void *radix_delete(struct radix_tree *tree, unsigned long key)
118 {
119         printd("RADIX: delete %d\n", key);
120         void **slot;
121         void *retval;
122         struct radix_node *r_node = __radix_lookup_node(tree, key, 0);
123         if (!r_node)
124                 return 0;
125         slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
126         retval = *slot;
127         if (retval) {
128                 __radix_remove_slot(r_node, (struct radix_node**)slot);
129         } else {
130                 /* it's okay to delete an empty, but i want to know about it for now */
131                 warn("Tried to remove a non-existant item from a radix tree!");
132         }
133         return retval;
134 }
135
136 /* Returns the item for a given key.  0 means no item, etc. */
137 void *radix_lookup(struct radix_tree *tree, unsigned long key)
138 {
139         printd("RADIX: lookup %d\n", key);
140         void **slot = radix_lookup_slot(tree, key);
141         if (!slot)
142                 return 0;
143         return *slot;
144 }
145
146 /* Returns a pointer to the radix_node holding a given key.  0 if there is no
147  * such node, due to the tree being too small or something.
148  *
149  * If the depth is greater than one, we need to walk down the tree a level.  The
150  * key is 'partitioned' among the levels of the tree, like so:
151  * ......444444333333222222111111
152  *
153  * If an interior node of the tree is missing, this will add one if it was
154  * directed to extend the tree. */
155 static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
156                                               unsigned long key, bool extend)
157 {
158         printd("RADIX: lookup_node %d, %d\n", key, extend);
159         unsigned long idx;
160         struct radix_node *child_node, *r_node = tree->root;
161         if (key >= tree->upper_bound) {
162                 if (extend)
163                         warn("Bound (%d) not set for key %d!\n", tree->upper_bound, key);
164                 return 0;
165         }
166         for (int i = tree->depth; i > 1; i--) {  /* i = ..., 4, 3, 2 */
167                 idx = (key >> (LOG_RNODE_SLOTS * (i - 1))) & (NR_RNODE_SLOTS - 1);
168                 /* There might not be a node at this part of the tree */
169                 if (!r_node->items[idx]) {
170                         if (!extend) {
171                                 return 0;
172                         } else {
173                                 /* so build one, possibly returning 0 if we couldn't */
174                                 child_node = kmem_cache_alloc(radix_kcache, 0);
175                                 if (!child_node)
176                                         return 0;
177                                 r_node->items[idx] = child_node;
178                                 memset(child_node, 0, sizeof(struct radix_node));
179                                 /* when we are on the last iteration (i == 2), the child will be
180                                  * a leaf. */
181                                 child_node->leaf = (i == 2) ? TRUE : FALSE;
182                                 child_node->parent = r_node;
183                                 child_node->my_slot = (struct radix_node**)&r_node->items[idx];
184                                 r_node->num_items++;
185                                 r_node = (struct radix_node*)r_node->items[idx];
186                         }
187                 } else {
188                         r_node = (struct radix_node*)r_node->items[idx];
189                 }
190         }
191         return r_node;
192 }
193
194 /* Returns a pointer to the slot for the given key.  0 if there is no such slot,
195  * etc */
196 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key)
197 {
198         printd("RADIX: lookup slot %d\n", key);
199         struct radix_node *r_node = __radix_lookup_node(tree, key, FALSE);
200         if (!r_node)
201                 return 0;
202         key = key & (NR_RNODE_SLOTS - 1);
203         return &r_node->items[key];
204 }
205
206 /* [x_left, x_right) and [y_left, y_right). */
207 static bool ranges_overlap(unsigned long x_left, unsigned long x_right,
208                            unsigned long y_left, unsigned long y_right)
209 {
210         return ((x_left <= y_left) && (y_left < x_right)) ||
211                ((y_left <= x_left) && (x_left < y_right));
212 }
213
214 /* Given an index at a depth for a child, returns whether part of it is in the
215  * global range.
216  *
217  * Recall the key is partitioned like so: ....444444333333222222111111.  The
218  * depth is 1 when we're in the last rnode and our children are items.  When
219  * we're an intermediate node, our depth is higher, and our start/end is the
220  * entire reach of us + our children. */
221 static bool child_overlaps_range(unsigned long idx, int depth,
222                                  unsigned long glb_start_idx,
223                                  unsigned long glb_end_idx)
224 {
225         unsigned long start = idx << (LOG_RNODE_SLOTS * (depth - 1));
226         unsigned long end = (idx + 1) << (LOG_RNODE_SLOTS * (depth - 1));
227
228         return ranges_overlap(start, end, glb_start_idx, glb_end_idx);
229 }
230
231 /* Helper for walking down a tree.
232  * - depth == 1 means we're on the last radix_node, whose items are all the
233  *   actual items.
234  * - tree_idx is the index for our item/node.  It encodes the path we took
235  *   through the radix tree to get to where we are.  For leaves (items), it is
236  *   their index in the address space.  For internal rnodes, it is a temporary
237  *   number, but combined with the depth, you can determine the range of the
238  *   rnode's descendents.
239  * - glb_start_idx and glb_end_idx is the global start and end for the entire
240  *   for_each operation.
241  *
242  * Returns true if our r_node *was already deleted*.  When we call
243  * __radix_remove_slot(), if we removed the last item for r_node, the removal
244  * code will recurse *up* the tree, such that r_node might already be freed.
245  * Same goes for our parent!  Hence, we're careful to only access r_node when we
246  * know we have children (once we enter the loop and might remove a slot). */
247 static bool rnode_for_each(struct radix_node *r_node, int depth,
248                            unsigned long tree_idx, unsigned long glb_start_idx,
249                            unsigned long glb_end_idx,
250                            radix_cb_t cb, void *arg)
251 {
252         unsigned int num_children = ACCESS_ONCE(r_node->num_items);
253
254         /* The tree_idx we were passed was from our parent's perspective.  We need
255          * shift it over each time we walk down to put it in terms of our
256          * level/depth.  Or think of it as making room for our bits (the values of
257          * i). */
258         tree_idx <<= LOG_RNODE_SLOTS;
259         for (int i = 0; num_children && (i < NR_RNODE_SLOTS); i++) {
260                 if (r_node->items[i]) {
261                         /* If we really care, we can try to abort the rest of the loop.  Not
262                          * a big deal */
263                         if (!child_overlaps_range(tree_idx + i, depth, glb_start_idx,
264                                                   glb_end_idx))
265                                 continue;
266                         if (depth > 1) {
267                                 if (rnode_for_each(r_node->items[i], depth - 1, tree_idx + i,
268                                                    glb_start_idx, glb_end_idx, cb, arg))
269                                         num_children--;
270                         } else {
271                                 if (cb(&r_node->items[i], tree_idx + i, arg)) {
272                                         __radix_remove_slot(r_node,
273                                                             (struct radix_node**)&r_node->items[i]);
274                                         num_children--;
275                                 }
276                         }
277                 }
278         }
279         return num_children ? false : true;
280 }
281
282 /* [start_idx, end_idx) */
283 void radix_for_each_slot_in_range(struct radix_tree *tree,
284                                   unsigned long start_idx,
285                                   unsigned long end_idx,
286                                   radix_cb_t cb, void *arg)
287 {
288         if (!tree->root)
289                 return;
290         rnode_for_each(tree->root, tree->depth, 0, start_idx, end_idx, cb, arg);
291 }
292
293 void radix_for_each_slot(struct radix_tree *tree, radix_cb_t cb, void *arg)
294 {
295         radix_for_each_slot_in_range(tree, 0, ULONG_MAX, cb, arg);
296 }
297
298 int radix_gang_lookup(struct radix_tree *tree, void **results,
299                       unsigned long first, unsigned int max_items)
300 {
301         panic("Not implemented");
302         return -1; /* TODO! */
303 }
304
305
306 int radix_grow(struct radix_tree *tree, unsigned long max)
307 {
308         panic("Not implemented");
309         return -1; /* TODO! */
310 }
311
312 int radix_preload(struct radix_tree *tree, int flags)
313 {
314         panic("Not implemented");
315         return -1; /* TODO! */
316 }
317
318
319 void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag)
320 {
321         panic("Tagging not implemented!");
322         return (void*)-1; /* TODO! */
323 }
324
325 void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag)
326 {
327         panic("Tagging not implemented!");
328         return (void*)-1; /* TODO! */
329 }
330
331 int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag)
332 {
333         panic("Tagging not implemented!");
334         return -1; /* TODO! */
335 }
336
337 int radix_tree_tagged(struct radix_tree *tree, int tag)
338 {
339         panic("Tagging not implemented!");
340         return -1; /* TODO! */
341 }
342
343 int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
344                           unsigned long first, unsigned int max_items, int tag)
345 {
346         panic("Tagging not implemented!");
347         return -1; /* TODO! */
348 }
349
350 void print_radix_tree(struct radix_tree *tree)
351 {
352         printk("Tree %p, Depth: %d, Bound: %d\n", tree, tree->depth,
353                tree->upper_bound);
354
355         void print_rnode(struct radix_node *r_node, int depth)
356         {
357                 if (!r_node)
358                         return;
359                 char buf[32] = {0};
360                 for (int i = 0; i < depth; i++)
361                         buf[i] = '\t';
362                 printk("%sRnode %p, parent %p, myslot %p, %d items, leaf? %d\n",
363                        buf, r_node, r_node->parent, r_node->my_slot, r_node->num_items,
364                        r_node->leaf);
365                 for (int i = 0; i < NR_RNODE_SLOTS; i++) {
366                         if (!r_node->items[i])
367                                 continue;
368                         if (r_node->leaf)
369                                 printk("\t%sRnode Item %d: %p\n", buf, i, r_node->items[i]);
370                         else
371                                 print_rnode(r_node->items[i], depth + 1);
372                 }
373         }
374         print_rnode(tree->root, 0);
375 }