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 int radix_gang_lookup(struct radix_tree *tree, void **results,
 207                       unsigned long first, unsigned int max_items)
 208 {
 209         panic("Not implemented");
 210         return -1; /* TODO! */
 211 }
 212
 213
 214 int radix_grow(struct radix_tree *tree, unsigned long max)
 215 {
 216         panic("Not implemented");
 217         return -1; /* TODO! */
 218 }
 219
 220 int radix_preload(struct radix_tree *tree, int flags)
 221 {
 222         panic("Not implemented");
 223         return -1; /* TODO! */
 224 }
 225
 226
 227 void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag)
 228 {
 229         panic("Tagging not implemented!");
 230         return (void*)-1; /* TODO! */
 231 }
 232
 233 void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag)
 234 {
 235         panic("Tagging not implemented!");
 236         return (void*)-1; /* TODO! */
 237 }
 238
 239 int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag)
 240 {
 241         panic("Tagging not implemented!");
 242         return -1; /* TODO! */
 243 }
 244
 245 int radix_tree_tagged(struct radix_tree *tree, int tag)
 246 {
 247         panic("Tagging not implemented!");
 248         return -1; /* TODO! */
 249 }
 250
 251 int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
 252                           unsigned long first, unsigned int max_items, int tag)
 253 {
 254         panic("Tagging not implemented!");
 255         return -1; /* TODO! */
 256 }
 257
 258 void print_radix_tree(struct radix_tree *tree)
 259 {
 260         printk("Tree %p, Depth: %d, Bound: %d\n", tree, tree->depth,
 261                tree->upper_bound);
 262
 263         void print_rnode(struct radix_node *r_node, int depth)
 264         {
 265                 if (!r_node)
 266                         return;
 267                 char buf[32] = {0};
 268                 for (int i = 0; i < depth; i++)
 269                         buf[i] = '\t';
 270                 printk("%sRnode %p, parent %p, myslot %p, %d items, leaf? %d\n",
 271                        buf, r_node, r_node->parent, r_node->my_slot, r_node->num_items,
 272                        r_node->leaf);
 273                 for (int i = 0; i < NR_RNODE_SLOTS; i++) {
 274                         if (!r_node->items[i])
 275                                 continue;
 276                         if (r_node->leaf)
 277                                 printk("\t%sRnode Item %d: %p\n", buf, i, r_node->items[i]);
 278                         else
 279                                 print_rnode(r_node->items[i], depth + 1);
 280                 }
 281         }
 282         print_rnode(tree->root, 0);
 283 }