]> git.baikalelectronics.ru Git - kernel.git/commit
fix the max path calculation in radix-tree.c
authorJeff Moyer <jmoyer@redhat.com>
Tue, 16 Oct 2007 08:24:49 +0000 (01:24 -0700)
committerLinus Torvalds <torvalds@woody.linux-foundation.org>
Tue, 16 Oct 2007 16:42:54 +0000 (09:42 -0700)
commit6238cd3065172b5eb04d9c1046991376d1d8002c
tree1486600f31a6f1387f4f5db276684f0b727eec89
parentaec5413b9084ae8bc1bd82e886da56f0de5f856a
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 b4c13f1009beee60f0529d45f29d97b055563898):

-#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>
lib/radix-tree.c