From 612d6c19db2fd0dc97b0fa370613ecd4a305ffc3 Mon Sep 17 00:00:00 2001 From: Nick Piggin Date: Fri, 23 Jun 2006 02:03:22 -0700 Subject: [PATCH] radix-tree: direct data The ability to have height 0 radix trees (a direct pointer to the data item rather than going through a full node->slot) quietly disappeared with old-2.6-bkcvs commit ffee171812d51652f9ba284302d9e5c5cc14bdfd. On 64-bit machines this causes nearly 600 bytes to be used for every <= 4K file in pagecache. Re-introduce this feature, root tags stored in spare ->gfp_mask bits. Simplify radix_tree_delete's complex tag clearing arrangement (which would become even more complex) by just falling back to tag clearing functions (the pagecache radix-tree never uses this path anyway, so the icache savings will mean it's actually a speedup). On my 4GB G5, this saves 8MB RAM per kernel kernel source+object tree in pagecache. Pagecache lookup, insertion, and removal speed for small files will also be improved. This makes RCU radix tree harder, but it's worth it. Signed-off-by: Nick Piggin Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- include/linux/radix-tree.h | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'include/linux/radix-tree.h') diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index dd83cca2800160..9158a68140c9e0 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -23,6 +23,9 @@ #include #include +#define RADIX_TREE_MAX_TAGS 2 + +/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */ struct radix_tree_root { unsigned int height; gfp_t gfp_mask; @@ -45,8 +48,6 @@ do { \ (root)->rnode = NULL; \ } while (0) -#define RADIX_TREE_MAX_TAGS 2 - int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); void *radix_tree_lookup(struct radix_tree_root *, unsigned long); void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long); -- cgit 1.2.3-korg