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