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