aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJeff Moyer <jmoyer@redhat.com>2007-10-16 04:24:49 -0400
committerLinus Torvalds <torvalds@woody.linux-foundation.org>2007-10-16 12:42:54 -0400
commit26fb1589cb0aaec3a0b4418c54f30c1a2b1781f6 (patch)
tree1486600f31a6f1387f4f5db276684f0b727eec89
parenta4b0672db3a698d0684ee6e54f44e2e162a3da1b (diff)
fix the max path calculation in radix-tree.c
A while back, Nick Piggin introduced a patch to reduce the node memory usage for small files (commit cfd9b7df4abd3257c9e381b0e445817b26a51c0c): -#define RADIX_TREE_MAP_SHIFT 6 +#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) Unfortunately, he didn't take into account the fact that the calculation of the maximum path was based on an assumption of having to round up: #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) So, if CONFIG_BASE_SMALL is set, you will end up with a RADIX_TREE_MAX_PATH that is one greater than necessary. The practical upshot of this is just a bit of wasted memory (one long in the height_to_maxindex array, an extra pre-allocated radix tree node per cpu, and extra stack usage in a couple of functions), but it seems worth getting right. It's also worth noting that I never build with CONFIG_BASE_SMALL. What I did to test this was duplicate the code in a small user-space program and check the results of the calculations for max path and the contents of the height_to_maxindex array. Signed-off-by: Jeff Moyer <jmoyer@redhat.com> Acked-by: Nick Piggin <nickpiggin@yahoo.com.au> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
-rw-r--r--lib/radix-tree.c21
1 files changed, 17 insertions, 4 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 0eee4020a7be..519d3f00ef9e 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -60,9 +60,14 @@ struct radix_tree_path {
60}; 60};
61 61
62#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) 62#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
63#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2) 63#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
64 RADIX_TREE_MAP_SHIFT))
64 65
65static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; 66/*
67 * The height_to_maxindex array needs to be one deeper than the maximum
68 * path as height 0 holds only 1 entry.
69 */
70static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
66 71
67/* 72/*
68 * Radix tree node cache. 73 * Radix tree node cache.
@@ -492,7 +497,11 @@ EXPORT_SYMBOL(radix_tree_tag_set);
492void *radix_tree_tag_clear(struct radix_tree_root *root, 497void *radix_tree_tag_clear(struct radix_tree_root *root,
493 unsigned long index, unsigned int tag) 498 unsigned long index, unsigned int tag)
494{ 499{
495 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 500 /*
501 * The radix tree path needs to be one longer than the maximum path
502 * since the "list" is null terminated.
503 */
504 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
496 struct radix_tree_node *slot = NULL; 505 struct radix_tree_node *slot = NULL;
497 unsigned int height, shift; 506 unsigned int height, shift;
498 507
@@ -934,7 +943,11 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
934 */ 943 */
935void *radix_tree_delete(struct radix_tree_root *root, unsigned long index) 944void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
936{ 945{
937 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path; 946 /*
947 * The radix tree path needs to be one longer than the maximum path
948 * since the "list" is null terminated.
949 */
950 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
938 struct radix_tree_node *slot = NULL; 951 struct radix_tree_node *slot = NULL;
939 struct radix_tree_node *to_free; 952 struct radix_tree_node *to_free;
940 unsigned int height, shift; 953 unsigned int height, shift;