[PATCH] radix-tree reinitialisation fix

This patch fixes a problem which was discovered by Vladimir Saveliev
<vs@namesys.com>

Radix trees have a `height' field, which defines how far the pages are
from the root of the tree.  It starts out at zero and increases as the
trees depth is grown.

But it is never decreased.  It cannot be decreased without a full tree
traversal.

Because radix_tree_delete() does not decrease `height', we end up
returning inodes to their filesystem's inode slab cache with a non-zero
height.

And when that inode is reused from slab for a new file, it still has a
non-zero height.  So we're breaking the slab rules by not putting
objects back in a fully reinitialised state.

So the new file starts out life with whatever height the previous owner
of the inode had.  Which is space- and speed-inefficient.

The most efficient place to fix this would be in destroy_inode().  But
that only fixes the problem for inodes - there are other users of radix
trees.

So fix it in radix_tree_delete(): if the tree was emptied, reset
`height' to zero.

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 6cb4ee3..dfa732c 100644 (file)
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -334,6 +334,9 @@ int radix_tree_delete(struct radix_tree_root *root, unsigned long index)
                radix_tree_node_free(pathp[1].node);
        }
 
+       if (root->rnode == NULL)
+               root->height = 0;  /* Empty tree, we can reset the height */
+
        return 0;
 }
 EXPORT_SYMBOL(radix_tree_delete);