Radix Trees!
authorBarret Rhoden <brho@cs.berkeley.edu>
Wed, 14 Jul 2010 03:44:10 +0000 (20:44 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:48 +0000 (17:35 -0700)
Basics of a radix tree, mapping key->void*.  Some very basic testing.

kern/include/radix.h [new file with mode: 0644]
kern/include/testing.h
kern/src/Makefrag
kern/src/init.c
kern/src/radix.c [new file with mode: 0644]
kern/src/testing.c

diff --git a/kern/include/radix.h b/kern/include/radix.h
new file mode 100644 (file)
index 0000000..1fd3bea
--- /dev/null
@@ -0,0 +1,70 @@
+/* Copyright (c) 2010 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Radix Tree, modeled after Linux's (described here:
+ * http://lwn.net/Articles/175432/).
+ *
+ * It maps unsigned longs to void*s, growing the depth of the tree as needed to
+ * handle more items.  It won't allow the insertion of existing keys, and it
+ * can fail due to lack of memory.
+ *
+ * There are some utility functions, probably unimplemented til we need them,
+ * that will make the tree have enough memory for future calls.
+ *
+ * You can also store a tag along with the void* for a given item, and do
+ * lookups based on those tags.  Or you will be able to, once it is
+ * implemented. */
+
+#ifndef ROS_KERN_RADIX_H
+#define ROS_KERN_RADIX_H
+
+#define LOG_RNODE_SLOTS 6
+#define NR_RNODE_SLOTS (1 << LOG_RNODE_SLOTS)
+
+#include <ros/common.h>
+
+struct radix_node {
+       void                                            *items[NR_RNODE_SLOTS];
+       unsigned int                            num_items;
+       bool                                            leaf;
+       struct radix_node                       *parent;
+       struct radix_node                       **my_slot;
+};
+
+/* Defines the whole tree. */
+struct radix_tree {
+       struct radix_node                       *root;
+       unsigned int                            depth;
+       unsigned long                           upper_bound;
+};
+
+void radix_init(void);         /* initializes the whole radix system */
+#define RADIX_INITIALIZER {0, 0, 0}
+void radix_tree_init(struct radix_tree *tree); /* inits one tree */
+void radix_tree_destroy(struct radix_tree *tree);
+
+/* Item management */
+int radix_insert(struct radix_tree *tree, unsigned long key, void *item);
+void *radix_delete(struct radix_tree *tree, unsigned long key);
+void *radix_lookup(struct radix_tree *tree, unsigned long key);
+void **radix_lookup_slot(struct radix_tree *tree, unsigned long key);
+int radix_gang_lookup(struct radix_tree *tree, void **results,
+                      unsigned long first, unsigned int max_items);
+
+/* Memory management */
+int radix_grow(struct radix_tree *tree, unsigned long max);
+int radix_preload(struct radix_tree *tree, int flags);
+
+/* Tag management */
+void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag);
+void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag);
+int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag);
+int radix_tree_tagged(struct radix_tree *tree, int tag);
+int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
+                          unsigned long first, unsigned int max_items, int tag);
+
+/* Debugging */
+void print_radix_tree(struct radix_tree *tree);
+
+#endif /* !ROS_KERN_RADIX_H */
index e5b1f94..ba567f6 100644 (file)
@@ -29,6 +29,7 @@ void test_kmalloc(void);
 void test_hashtable(void);
 void test_bcq(void);
 void test_vm_regions(void);
+void test_radix_tree(void);
 
 struct trapframe_t;
 
index 10a3b64..204f137 100644 (file)
@@ -41,6 +41,7 @@ KERN_SRCFILES := $(KERN_ARCH_SRCFILES) \
                  $(KERN_SRC_DIR)/elf.c \
                  $(KERN_SRC_DIR)/frontend.c \
                  $(KERN_SRC_DIR)/vfs.c \
+                 $(KERN_SRC_DIR)/radix.c \
                  $(KERN_SRC_DIR)/testing.c
 
 # Only build files if they exist.
index 523a52c..eba2f84 100644 (file)
@@ -29,6 +29,7 @@
 #include <testing.h>
 #include <kmalloc.h>
 #include <hashtable.h>
+#include <radix.h>
 #include <mm.h>
 #include <frontend.h>
 
@@ -73,6 +74,7 @@ void kernel_init(multiboot_info_t *mboot_info)
        kmem_cache_init();              // Sets up slab allocator
        kmalloc_init();
        hashtable_init();
+       radix_init();
        cache_color_alloc_init();       // Inits data structs
        colored_page_alloc_init();      // Allocates colors for agnostic processes
        vmr_init();
diff --git a/kern/src/radix.c b/kern/src/radix.c
new file mode 100644 (file)
index 0000000..b8fc00e
--- /dev/null
@@ -0,0 +1,262 @@
+/* Copyright (c) 2010 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Radix Trees!  Just the basics, doesn't do tagging or anything fancy. */
+
+#include <ros/errno.h>
+#include <radix.h>
+#include <slab.h>
+#include <string.h>
+#include <stdio.h>
+
+struct kmem_cache *radix_kcache;
+static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
+                                              unsigned long key,
+                                              bool extend);
+static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **slot);
+
+/* Initializes the radix tree system, mostly just builds the kcache */
+void radix_init(void)
+{
+       radix_kcache = kmem_cache_create("radix_nodes", sizeof(struct radix_node),
+                                        __alignof__(struct radix_node), 0, 0, 0);
+}
+
+/* Initializes a tree dynamically */
+void radix_tree_init(struct radix_tree *tree)
+{
+       tree->root = 0;
+       tree->depth = 0;
+       tree->upper_bound = 0;
+}
+
+/* Will clean up all the memory associated with a tree.  Shouldn't be necessary
+ * if you delete all of the items, which you should do anyways since they are
+ * usually void*.  Might expand this to have a function to call on every leaf
+ * slot. */
+void radix_tree_destroy(struct radix_tree *tree)
+{
+       panic("Not implemented");
+}
+
+/* Attempts to insert an item in the tree at the given key.  ENOMEM if we ran
+ * out of memory, EEXIST if an item is already in the tree. */
+int radix_insert(struct radix_tree *tree, unsigned long key, void *item)
+{
+       struct radix_node *r_node;
+       void **slot;
+       /* Is the tree tall enough?  if not, it needs to grow a level.  This will
+        * also create the initial node (upper bound starts at 0). */
+       if (key >= tree->upper_bound) {
+               r_node = kmem_cache_alloc(radix_kcache, 0);
+               if (!r_node)
+                       return -ENOMEM;
+               memset(r_node, 0, sizeof(struct radix_node));
+               if (tree->root) {
+                       /* tree->root is the old root, now a child of the future root */
+                       r_node->items[0] = tree->root;
+                       tree->root->parent = r_node;
+                       tree->root->my_slot = (struct radix_node**)&r_node->items[0];
+                       r_node->num_items = 1;
+               } else {
+                       /* if there was no root before, we're both the root and a leaf */
+                       r_node->leaf = TRUE;
+               }
+               tree->root = r_node;
+               r_node->my_slot = &tree->root;
+               tree->depth++;
+               tree->upper_bound = 1 << (LOG_RNODE_SLOTS * tree->depth);
+       }
+       /* the tree now thinks it is tall enough, so find the last node, insert in
+        * it, etc */
+       r_node = __radix_lookup_node(tree, key, TRUE);
+       assert(r_node);         /* we want an ENOMEM actually, but i want to see this */
+       slot = &r_node->items[key & (LOG_RNODE_SLOTS - 1)];
+       if (*slot)
+               return -EEXIST;
+       *slot = item;
+       r_node->num_items++;
+       return 0;
+}
+
+/* Removes an item from it's parent's structure, freeing the parent if there is
+ * nothing left, potentially recursively. */
+static void __radix_remove_slot(struct radix_node *r_node, struct radix_node **slot)
+{
+       assert(*slot);          /* make sure there is something there */
+       *slot = 0;
+       r_node->num_items--;
+       if (!r_node->num_items) {
+               if (r_node->parent)
+                       __radix_remove_slot(r_node->parent, r_node->my_slot);
+               else                    /* we're the last node, attached to the actual tree */
+                       *(r_node->my_slot) = 0;
+               kmem_cache_free(radix_kcache, r_node);
+       }
+}
+
+/* Removes a key/item from the tree, returning that item (the void*).  If it
+ * detects a radix_node is now unused, it will dealloc that node.  Though the
+ * tree will still think it is tall enough to handle its old upper_bound.  It
+ * won't "shrink". */
+void *radix_delete(struct radix_tree *tree, unsigned long key)
+{
+       void **slot;
+       void *retval;
+       struct radix_node *r_node = __radix_lookup_node(tree, key, 0);
+       if (!r_node)
+               return 0;
+       slot = &r_node->items[key & (LOG_RNODE_SLOTS - 1)];
+       retval = *slot;
+       if (retval) {
+               __radix_remove_slot(r_node, (struct radix_node**)slot); 
+       } else {
+               /* it's okay to delete an empty, but i want to know about it for now */
+               warn("Tried to remove a non-existant item from a radix tree!");
+       }
+       return retval;
+}
+
+/* Returns the item for a given key.  0 means no item, etc. */
+void *radix_lookup(struct radix_tree *tree, unsigned long key)
+{
+       void **slot = radix_lookup_slot(tree, key);
+       if (!slot)
+               return 0;
+       return *slot;
+}
+
+/* Returns a pointer to the radix_node holding a given key.  0 if there is no
+ * such node, due to the tree being too small or something.
+ *
+ * If the depth is greater than one, we need to walk down the tree a level.  The
+ * key is 'partitioned' among the levels of the tree, like so:
+ * ......444444333333222222111111
+ *
+ * If an interior node of the tree is missing, this will add one if it was
+ * directed to extend the tree. */
+static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
+                                              unsigned long key, bool extend)
+{
+       unsigned long idx;
+       struct radix_node *child_node, *r_node = tree->root;
+       if (key >= tree->upper_bound)
+               return 0;
+       for (int i = tree->depth; i > 1; i--) {  /* i = ..., 4, 3, 2 */
+               idx = (key >> (LOG_RNODE_SLOTS * (i - 1))) & (LOG_RNODE_SLOTS - 1);
+               /* There might not be a node at this part of the tree */
+               if (!r_node->items[idx]) {
+                       if (!extend) {
+                               return 0;
+                       } else {
+                               /* so build one, possibly returning 0 if we couldn't */
+                               child_node = kmem_cache_alloc(radix_kcache, 0);
+                               if (!child_node)
+                                       return 0;
+                               r_node->items[idx] = child_node;
+                               memset(child_node, 0, sizeof(struct radix_node));
+                               /* when we are on the last iteration (i == 2), the child will be
+                                * a leaf. */
+                               child_node->leaf = (i == 2) ? TRUE : FALSE;
+                               child_node->parent = r_node;
+                               child_node->my_slot = (struct radix_node**)&r_node->items[idx];
+                               r_node->num_items++;
+                               r_node = (struct radix_node*)r_node->items[idx];
+                       }
+               } else {
+                       r_node = (struct radix_node*)r_node->items[idx];
+               }
+       }
+       return r_node;
+}
+
+/* Returns a pointer to the slot for the given key.  0 if there is no such slot,
+ * etc */
+void **radix_lookup_slot(struct radix_tree *tree, unsigned long key)
+{
+       struct radix_node *r_node = __radix_lookup_node(tree, key, FALSE);
+       if (!r_node)
+               return 0;
+       key = key & (LOG_RNODE_SLOTS - 1);
+       return &r_node->items[key];
+}
+
+int radix_gang_lookup(struct radix_tree *tree, void **results,
+                      unsigned long first, unsigned int max_items)
+{
+       panic("Not implemented");
+       return -1; /* TODO! */
+}
+
+
+int radix_grow(struct radix_tree *tree, unsigned long max)
+{
+       panic("Not implemented");
+       return -1; /* TODO! */
+}
+
+int radix_preload(struct radix_tree *tree, int flags)
+{
+       panic("Not implemented");
+       return -1; /* TODO! */
+}
+
+
+void *radix_tag_set(struct radix_tree *tree, unsigned long key, int tag)
+{
+       panic("Tagging not implemented!");
+       return (void*)-1; /* TODO! */
+}
+
+void *radix_tag_clear(struct radix_tree *tree, unsigned long key, int tag)
+{
+       panic("Tagging not implemented!");
+       return (void*)-1; /* TODO! */
+}
+
+int radix_tag_get(struct radix_tree *tree, unsigned long key, int tag)
+{
+       panic("Tagging not implemented!");
+       return -1; /* TODO! */
+}
+
+int radix_tree_tagged(struct radix_tree *tree, int tag)
+{
+       panic("Tagging not implemented!");
+       return -1; /* TODO! */
+}
+
+int radix_tag_gang_lookup(struct radix_tree *tree, void **results,
+                          unsigned long first, unsigned int max_items, int tag)
+{
+       panic("Tagging not implemented!");
+       return -1; /* TODO! */
+}
+
+void print_radix_tree(struct radix_tree *tree)
+{
+       printk("Tree %08p, Depth: %d, Bound: %d\n", tree, tree->depth,
+              tree->upper_bound);
+
+       void print_rnode(struct radix_node *r_node, int depth)
+       {
+               if (!r_node)
+                       return;
+               char buf[32] = {0};
+               for (int i = 0; i < depth; i++)
+                       buf[i] = '\t';
+               printk("%sRnode %08p, parent %08p, myslot %08p, %d items, leaf? %d\n",
+                      buf, r_node, r_node->parent, r_node->my_slot, r_node->num_items,
+                      r_node->leaf);
+               for (int i = 0; i < NR_RNODE_SLOTS; i++) {
+                       if (!r_node->items[i])
+                               continue;
+                       if (r_node->leaf)
+                               printk("\t%sRnode Item %d: %08p\n", buf, i, r_node->items[i]);
+                       else
+                               print_rnode(r_node->items[i], depth + 1);
+               }
+       }
+       print_rnode(tree->root, 0);
+}
index f0834f2..e5a7e8f 100644 (file)
@@ -30,6 +30,7 @@
 #include <slab.h>
 #include <kmalloc.h>
 #include <hashtable.h>
+#include <radix.h>
 
 #define l1 (available_caches.l1)
 #define l2 (available_caches.l2)
@@ -1077,3 +1078,30 @@ void test_vm_regions(void)
 
        printk("Finished vm_regions test!\n");
 }
+
+void test_radix_tree(void)
+{
+       struct radix_tree real_tree = RADIX_INITIALIZER;
+       struct radix_tree *tree = &real_tree;
+       
+       if (radix_insert(tree, 3, (void*)0xdeadbeef))
+               printk("Failed to insert first!\n");
+       radix_insert(tree, 4, (void*)0x04040404);
+       assert((void*)0xdeadbeef == radix_lookup(tree, 3));
+       if (radix_insert(tree, 65, (void*)0xcafebabe))
+               printk("Failed to insert a two-tier!\n");
+       if (!radix_insert(tree, 4, (void*)0x03030303))
+               printk("Should not let us reinsert\n");
+       if (radix_insert(tree, 4095, (void*)0x4095))
+               printk("Failed to insert a two-tier boundary!\n");
+       if (radix_insert(tree, 4096, (void*)0x4096))
+               printk("Failed to insert a three-tier!\n");
+       //print_radix_tree(tree);
+       radix_delete(tree, 65);
+       radix_delete(tree, 3);
+       radix_delete(tree, 4);
+       radix_delete(tree, 4095);
+       radix_delete(tree, 4096);
+       //print_radix_tree(tree);
+       printk("Finished radix tree tests!\n");
+}