Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()

[Nick Piggin <nickpiggin@yahoo.com.au>]

Fengguang Wu wrote:
> Introduce radix_tree_scan_hole(root, index, max_scan) to scan radix tree
> for the first hole. It will be used in interleaved readahead.
>
> The implementation is dumb and obviously correct.
> It can help debug(and document) the possible smart one in future.

Reasonable function to want. Is radix_tree_scan_hole the best name?
What about radix_tree_next_hole or _find_next_hole? (Andrew, any
suggestions?)

> Cc: Nick Piggin <nickpiggin@yahoo.com.au>
> Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
> ---
>
>  include/linux/radix-tree.h |    2 ++
>  lib/radix-tree.c           |   34 ++++++++++++++++++++++++++++++++++
>  2 files changed, 36 insertions(+)
>
> --- linux-2.6.22-rc6-mm1.orig/include/linux/radix-tree.h
> +++ linux-2.6.22-rc6-mm1/include/linux/radix-tree.h
> @@ -155,6 +155,8 @@ void *radix_tree_delete(struct radix_tre
>  unsigned int
>  radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
>  			unsigned long first_index, unsigned int max_items);
> +unsigned long radix_tree_scan_hole(struct radix_tree_root *root,
> +				unsigned long index, unsigned long max_scan);
>  int radix_tree_preload(gfp_t gfp_mask);
>  void radix_tree_init(void);
>  void *radix_tree_tag_set(struct radix_tree_root *root,
> --- linux-2.6.22-rc6-mm1.orig/lib/radix-tree.c
> +++ linux-2.6.22-rc6-mm1/lib/radix-tree.c
> @@ -601,6 +601,40 @@ int radix_tree_tag_get(struct radix_tree
>  EXPORT_SYMBOL(radix_tree_tag_get);
>  #endif
>  
> +static unsigned long
> +radix_tree_scan_hole_dumb(struct radix_tree_root *root,
> +				unsigned long index, unsigned long max_scan)
> +{
> +	unsigned long i;
> +
> +	for (i = 0; i < max_scan; i++) {
> +		if (!radix_tree_lookup(root, index))
> +			break;
> +		if (++index == 0)
> +			break;

Minor nit: I think it is preferred to have index++; on its own line.

> +	}
> +
> +	return index;
> +}
> +
> +/**
> + *	radix_tree_scan_hole    -    scan for hole
> + *	@root:		radix tree root
> + *	@index:		index key
> + *	@max_scan:      advice on max items to scan (it may scan a little more)
> + *
> + *      Scan forward from @index for a hole/empty item, stop when
> + *      - hit hole
> + *      - wrap-around to index 0
> + *      - @max_scan or more items scanned
> + */

Some suggestions on the comment:

/**
 *	radix_tree_next_hole    -    find the next hole (not-present entry)
 *	@root:		radix tree root
 *	@index:		index key
 *	@max_scan:      maximum range to search
 *
 *      Search the set [index,  min(index+max_scan-1, MAX_INDEX)] for the lowest
 *      indexed hole.
 *
 *      Returns: the index of the hole if found, otherwise returns an index
 *      outside of the set specified (in which case 'return - index >= max_scan'
 *      will be true).
 *
 *      radix_tree_next_hole may be called under rcu_read_lock. However, like
 *      radix_tree_gang_lookup, this will not atomically search a snapshot of the
 *      tree at a single point in time. For example, if a hole is created at index
 *      5, then subsequently a hole is created at index 10, radix_tree_next_hole
 *      covering both indexes may return 10 if called under rcu_read_lock.
 */


> +unsigned long radix_tree_scan_hole(struct radix_tree_root *root,
> +				unsigned long index, unsigned long max_scan)
> +{
> +	return radix_tree_scan_hole_dumb(root, index, max_scan);
> +}
> +EXPORT_SYMBOL(radix_tree_scan_hole);

Don't do this scan_hole_dumb thing. Just implement it in place.

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