linux-kernel - Re: [PATCH 6/7] radixtree: introduce radix_tree_scan

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <46A45F8A.5060600@yahoo.com.au>
Date:	Mon, 23 Jul 2007 17:58:02 +1000
From:	Nick Piggin <nickpiggin@...oo.com.au>
To:	Fengguang Wu <wfg@...l.ustc.edu.cn>
CC:	Andrew Morton <akpm@...l.org>, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()

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@...oo.com.au>
> Signed-off-by: Fengguang Wu <wfg@...l.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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/