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

Nick Piggin
2007-07-23T07:58:21Z

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.