Add a bulk interface to sem_down()
[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 /* Removes an item from it's parent's structure, freeing the parent if there is
113  * nothing left, potentially recursively. */
114 static void __radix_remove_slot(struct radix_node *r_node,
115                                 struct radix_node **slot)
116 {
117         assert(*slot);          /* make sure there is something there */
118         rcu_assign_pointer(*slot, NULL);
119         r_node->num_items--;
120         /* this check excludes the root, but the if else handles it.  For now, once
121          * we have a root, we'll always keep it (will need some changing in
122          * radix_insert() */
123         if (!r_node->num_items && r_node->parent) {
124                 if (r_node->parent)
125                         __radix_remove_slot(r_node->parent, r_node->my_slot);
126                 else                    /* we're the last node, attached to the actual tree */
127                         *(r_node->my_slot) = 0;
128                 synchronize_rcu();
129                 kmem_cache_free(radix_kcache, r_node);
130         }
131 }
132
133 /* Removes a key/item from the tree, returning that item (the void*).  If it
134  * detects a radix_node is now unused, it will dealloc that node.  Though the
135  * tree will still think it is tall enough to handle its old upper_bound.  It
136  * won't "shrink".
137  *
138  * Caller must maintain mutual exclusion (qlock) */
139 void *radix_delete(struct radix_tree *tree, unsigned long key)
140 {
141         void **slot;
142         void *retval;
143         struct radix_node *r_node;
144
145         /* This is an rcu-protected pointer, though the caller holds a lock. */
146         r_node = __radix_lookup_node(tree, key, false);
147         if (!r_node)
148                 return 0;
149         slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
150         retval = rcu_dereference(*slot);
151         if (retval) {
152                 __radix_remove_slot(r_node, (struct radix_node**)slot);
153         } else {
154                 /* it's okay to delete an empty, but i want to know about it for now */
155                 warn("Tried to remove a non-existant item from a radix tree!");
156         }
157         return retval;
158 }
159
160 /* Returns the item for a given key.  0 means no item, etc. */
161 void *radix_lookup(struct radix_tree *tree, unsigned long key)
162 {
163         void **slot = radix_lookup_slot(tree, key);
164
165         if (!slot)
166                 return 0;
167         /* slot was rcu-protected, pointing into the memory of an r_node.  we also
168          * want *slot, which is "void *item" to be an rcu-protected pointer. */
169         return rcu_dereference(*slot);
170 }
171
172 /* Returns a pointer to the radix_node holding a given key.  0 if there is no
173  * such node, due to the tree being too small or something.
174  *
175  * If the depth is greater than one, we need to walk down the tree a level.  The
176  * key is 'partitioned' among the levels of the tree, like so:
177  * ......444444333333222222111111
178  *
179  * If an interior node of the tree is missing, this will add one if it was
180  * directed to extend the tree.
181  *
182  * If we might extend, the caller must maintain mutual exclusion (qlock) */
183 static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
184                                               unsigned long key, bool extend)
185 {
186         unsigned long idx, upper_bound;
187         unsigned int depth;
188         seq_ctr_t seq;
189         struct radix_node *child_node, *r_node;
190
191         do {
192                 seq = ACCESS_ONCE(tree->seq);
193                 rmb();
194                 r_node = rcu_dereference(tree->root);
195                 depth = tree->depth;
196                 upper_bound = tree->upper_bound;
197         } while (seqctr_retry(tree->seq, seq));
198
199         if (key >= upper_bound) {
200                 if (extend)
201                         warn("Bound (%d) not set for key %d!\n", upper_bound, key);
202                 return 0;
203         }
204         for (int i = depth; i > 1; i--) {        /* i = ..., 4, 3, 2 */
205                 idx = (key >> (LOG_RNODE_SLOTS * (i - 1))) & (NR_RNODE_SLOTS - 1);
206                 /* There might not be a node at this part of the tree */
207                 if (!r_node->items[idx]) {
208                         if (!extend)
209                                 return 0;
210                         child_node = kmem_cache_alloc(radix_kcache, MEM_WAIT);
211                         memset(child_node, 0, sizeof(struct radix_node));
212                         /* when we are on the last iteration (i == 2), the child will be
213                          * a leaf. */
214                         child_node->leaf = (i == 2) ? TRUE : FALSE;
215                         child_node->parent = r_node;
216                         child_node->my_slot = (struct radix_node**)&r_node->items[idx];
217                         r_node->num_items++;
218                         rcu_assign_pointer(r_node->items[idx], child_node);
219                 }
220                 r_node = (struct radix_node*)rcu_dereference(r_node->items[idx]);
221         }
222         return r_node;
223 }
224
225 /* Returns a pointer to the slot for the given key.  0 if there is no such slot,
226  * etc */
227 void **radix_lookup_slot(struct radix_tree *tree, unsigned long key)
228 {
229         struct radix_node *r_node = __radix_lookup_node(tree, key, FALSE);
230
231         if (!r_node)
232                 return 0;
233         key = key & (NR_RNODE_SLOTS - 1);
234         /* r_node is rcu-protected.  Our retval is too, since it's a pointer into
235          * the same object as r_node. */
236         return &r_node->items[key];
237 }
238
239 /* [x_left, x_right) and [y_left, y_right). */
240 static bool ranges_overlap(unsigned long x_left, unsigned long x_right,
241                            unsigned long y_left, unsigned long y_right)
242 {
243         return ((x_left <= y_left) && (y_left < x_right)) ||
244                ((y_left <= x_left) && (x_left < y_right));
245 }
246
247 /* Given an index at a depth for a child, returns whether part of it is in the
248  * global range.
249  *
250  * Recall the key is partitioned like so: ....444444333333222222111111.  The
251  * depth is 1 when we're in the last rnode and our children are items.  When
252  * we're an intermediate node, our depth is higher, and our start/end is the
253  * entire reach of us + our children. */
254 static bool child_overlaps_range(unsigned long idx, int depth,
255                                  unsigned long glb_start_idx,
256                                  unsigned long glb_end_idx)
257 {
258         unsigned long start = idx << (LOG_RNODE_SLOTS * (depth - 1));
259         unsigned long end = (idx + 1) << (LOG_RNODE_SLOTS * (depth - 1));
260
261         return ranges_overlap(start, end, glb_start_idx, glb_end_idx);
262 }
263
264 /* Helper for walking down a tree.
265  * - depth == 1 means we're on the last radix_node, whose items are all the
266  *   actual items.
267  * - tree_idx is the index for our item/node.  It encodes the path we took
268  *   through the radix tree to get to where we are.  For leaves (items), it is
269  *   their index in the address space.  For internal rnodes, it is a temporary
270  *   number, but combined with the depth, you can determine the range of the
271  *   rnode's descendents.
272  * - glb_start_idx and glb_end_idx is the global start and end for the entire
273  *   for_each operation.
274  *
275  * Returns true if our r_node *was already deleted*.  When we call
276  * __radix_remove_slot(), if we removed the last item for r_node, the removal
277  * code will recurse *up* the tree, such that r_node might already be freed.
278  * Same goes for our parent!  Hence, we're careful to only access r_node when we
279  * know we have children (once we enter the loop and might remove a slot). */
280 static bool rnode_for_each(struct radix_node *r_node, int depth,
281                            unsigned long tree_idx, unsigned long glb_start_idx,
282                            unsigned long glb_end_idx,
283                            radix_cb_t cb, void *arg)
284 {
285         unsigned int num_children = ACCESS_ONCE(r_node->num_items);
286
287         /* The tree_idx we were passed was from our parent's perspective.  We need
288          * shift it over each time we walk down to put it in terms of our
289          * level/depth.  Or think of it as making room for our bits (the values of
290          * i). */
291         tree_idx <<= LOG_RNODE_SLOTS;
292         for (int i = 0; num_children && (i < NR_RNODE_SLOTS); i++) {
293                 if (r_node->items[i]) {
294                         /* If we really care, we can try to abort the rest of the loop.  Not
295                          * a big deal */
296                         if (!child_overlaps_range(tree_idx + i, depth, glb_start_idx,
297                                                   glb_end_idx))
298                                 continue;
299                         if (depth > 1) {
300                                 if (rnode_for_each(r_node->items[i], depth - 1, tree_idx + i,
301                                                    glb_start_idx, glb_end_idx, cb, arg))
302                                         num_children--;
303                         } else {
304                                 if (cb(&r_node->items[i], tree_idx + i, arg)) {
305                                         __radix_remove_slot(r_node,
306                                                             (struct radix_node**)&r_node->items[i]);
307                                         num_children--;
308                                 }
309                         }
310                 }
311         }
312         return num_children ? false : true;
313 }
314
315 /* [start_idx, end_idx).
316  *
317  * Caller must maintain mutual exclusion (qlock) */
318 void radix_for_each_slot_in_range(struct radix_tree *tree,
319                                   unsigned long start_idx,
320                                   unsigned long end_idx,
321                                   radix_cb_t cb, void *arg)
322 {
323         if (!tree->root)
324                 return;
325         rnode_for_each(tree->root, tree->depth, 0, start_idx, end_idx, cb, arg);
326 }
327
328 /* Caller must maintain mutual exclusion (qlock) */
329 void radix_for_each_slot(struct radix_tree *tree, radix_cb_t cb, void *arg)
330 {
331         radix_for_each_slot_in_range(tree, 0, ULONG_MAX, cb, arg);
332 }
333
334 int radix_gang_lookup(struct radix_tree *tree, void **results,
335                       unsigned long first, unsigned int max_items)
336 {
337         panic("Not implemented");
338         return -1; /* TODO! */
339 }
340
341
342 int radix_grow(struct radix_tree *tree, unsigned long max)
343 {
344         panic("Not implemented");
345         return -1; /* TODO! */
346 }
347
348 int radix_preload(struct radix_tree *tree, int flags)
349 {
350         panic("Not implemented");
351         return -1; /* TODO! */
352 }
353
354
355 void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag)
356 {
357         panic("Tagging not implemented!");
358         return (void*)-1; /* TODO! */
359 }
360
361 void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag)
362 {
363         panic("Tagging not implemented!");
364         return (void*)-1; /* TODO! */
365 }
366
367 int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag)
368 {
369         panic("Tagging not implemented!");
370         return -1; /* TODO! */
371 }
372
373 int radix_tree_tagged(struct radix_tree *tree, int tag)
374 {
375         panic("Tagging not implemented!");
376         return -1; /* TODO! */
377 }
378
379 int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
380                           unsigned long first, unsigned int max_items, int tag)
381 {
382         panic("Tagging not implemented!");
383         return -1; /* TODO! */
384 }
385
386 void print_radix_tree(struct radix_tree *tree)
387 {
388         printk("Tree %p, Depth: %d, Bound: %d\n", tree, tree->depth,
389                tree->upper_bound);
390
391         void print_rnode(struct radix_node *r_node, int depth)
392         {
393                 if (!r_node)
394                         return;
395                 char buf[32] = {0};
396                 for (int i = 0; i < depth; i++)
397                         buf[i] = '\t';
398                 printk("%sRnode %p, parent %p, myslot %p, %d items, leaf? %d\n",
399                        buf, r_node, r_node->parent, r_node->my_slot, r_node->num_items,
400                        r_node->leaf);
401                 for (int i = 0; i < NR_RNODE_SLOTS; i++) {
402                         if (!r_node->items[i])
403                                 continue;
404                         if (r_node->leaf)
405                                 printk("\t%sRnode Item %d: %p\n", buf, i, r_node->items[i]);
406                         else
407                                 print_rnode(r_node->items[i], depth + 1);
408                 }
409         }
410         print_rnode(tree->root, 0);
411 }