Fixes radix tree bug
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 23 Jul 2010 00:31:50 +0000 (17:31 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:49 +0000 (17:35 -0700)
Be more careful with masking, and write more tests!  This was a pain to
find when the FS was reordering pages somewhere else...

kern/src/radix.c
kern/src/testing.c

index b8fc00e..6910d8a 100644 (file)
@@ -72,7 +72,7 @@ int radix_insert(struct radix_tree *tree, unsigned long key, void *item)
         * 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)];
+       slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
        if (*slot)
                return -EEXIST;
        *slot = item;
@@ -107,7 +107,7 @@ void *radix_delete(struct radix_tree *tree, unsigned long key)
        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)];
+       slot = &r_node->items[key & (NR_RNODE_SLOTS - 1)];
        retval = *slot;
        if (retval) {
                __radix_remove_slot(r_node, (struct radix_node**)slot); 
@@ -144,7 +144,7 @@ static struct radix_node *__radix_lookup_node(struct radix_tree *tree,
        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);
+               idx = (key >> (LOG_RNODE_SLOTS * (i - 1))) & (NR_RNODE_SLOTS - 1);
                /* There might not be a node at this part of the tree */
                if (!r_node->items[idx]) {
                        if (!extend) {
@@ -178,7 +178,7 @@ 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);
+       key = key & (NR_RNODE_SLOTS - 1);
        return &r_node->items[key];
 }
 
index e5a7e8f..230b550 100644 (file)
@@ -31,6 +31,7 @@
 #include <kmalloc.h>
 #include <hashtable.h>
 #include <radix.h>
+#include <monitor.h>
 
 #define l1 (available_caches.l1)
 #define l2 (available_caches.l2)
@@ -1083,11 +1084,19 @@ void test_radix_tree(void)
 {
        struct radix_tree real_tree = RADIX_INITIALIZER;
        struct radix_tree *tree = &real_tree;
+       void *retval;
        
        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));
+       for (int i = 5; i < 100; i++)
+               if ((retval = radix_lookup(tree, i))) {
+                       printk("Extra item %08p at slot %d in tree %08p\n", retval, i,
+                              tree);
+                       print_radix_tree(tree);
+                       monitor(0);
+               }
        if (radix_insert(tree, 65, (void*)0xcafebabe))
                printk("Failed to insert a two-tier!\n");
        if (!radix_insert(tree, 4, (void*)0x03030303))