Re: [patch] fix the max path calculation in radix-tree.c

[Nick Piggin]

On Tue, Aug 21, 2007 at 03:48:42PM -0400, Jeff Moyer wrote:
> Hi,
> 
> 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.
> 
> Cheers.
> 
> Signed-off-by: Jeff Moyer <jmoyer@xxxxxxxxxx>
> 
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 514efb2..67c908f 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -60,7 +60,8 @@ struct radix_tree_path {
>  };
>  
>  #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
> -#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
> +#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
> +					  RADIX_TREE_MAP_SHIFT) + 1)
>  
>  static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
>  

OK, after you DIV_ROUND_UP, what is the extra 1 for? For paths, it is because
they are NULL terminated paths I guess (without remembering too hard), and for
height_to_maxindex array it is needed for 0-height trees I think. So it would
be kinda cleaner to have the _real_ MAX_PATH, and two other constants for
this array and the paths arrays (that just happen to be identical due to
implementation). Don't you think?

But that's not to nack this patch. On the contrary I think your logic is
correct, and it should be fixed. I didn't check the maths myself but I trust
you :)

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/