aboutsummaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorNick Piggin <npiggin@suse.de>2006-06-23 05:03:22 -0400
committerLinus Torvalds <torvalds@g5.osdl.org>2006-06-23 10:42:49 -0400
commit612d6c19db2fd0dc97b0fa370613ecd4a305ffc3 (patch)
tree3ab670895b5c3e389ff922192a572cbfd8159d03 /include
parent929f97276bcf7f4a95272ed08a85339b98ba210d (diff)
[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 <npiggin@suse.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'include')
-rw-r--r--include/linux/radix-tree.h5
1 files changed, 3 insertions, 2 deletions
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index dd83cca28001..9158a68140c9 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -23,6 +23,9 @@
23#include <linux/preempt.h> 23#include <linux/preempt.h>
24#include <linux/types.h> 24#include <linux/types.h>
25 25
26#define RADIX_TREE_MAX_TAGS 2
27
28/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
26struct radix_tree_root { 29struct radix_tree_root {
27 unsigned int height; 30 unsigned int height;
28 gfp_t gfp_mask; 31 gfp_t gfp_mask;
@@ -45,8 +48,6 @@ do { \
45 (root)->rnode = NULL; \ 48 (root)->rnode = NULL; \
46} while (0) 49} while (0)
47 50
48#define RADIX_TREE_MAX_TAGS 2
49
50int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); 51int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
51void *radix_tree_lookup(struct radix_tree_root *, unsigned long); 52void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
52void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long); 53void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);