Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Mon, Jul 23, 2007 at 04:04:05PM +0800, Fengguang Wu wrote: > On Mon, Jul 23, 2007 at 05:58:02PM +1000, Nick Piggin wrote: > > 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?) > > Thank you! > > All comments seems reasonable, so I simply attach the updated patch. > > Fengguang > --- > Subject: radixtree: introduce radix_tree_next_hole() > Cc: Nick Piggin <[EMAIL PROTECTED]> > > Introduce radix_tree_next_hole(root, index, max_scan) to scan radix tree > for the first hole. It will be used in interleaved readahead. > > Cc: Nick Piggin <[EMAIL PROTECTED]> > Signed-off-by: Fengguang Wu <[EMAIL PROTECTED]> And another rename fix for the interleaved readahead patch. Signed-off-by: Fengguang Wu <[EMAIL PROTECTED]> --- mm/readahead.c |2 +- 1 file changed, 1 insertion(+), 1 deletion(-) --- linux-2.6.22-rc6-mm1.orig/mm/readahead.c +++ linux-2.6.22-rc6-mm1/mm/readahead.c @@ -372,7 +372,7 @@ ondemand_readahead(struct address_space pgoff_t start; read_lock_irq(>tree_lock); - start = radix_tree_scan_hole(>page_tree, offset, max+1); + start = radix_tree_next_hole(>page_tree, offset, max+1); read_unlock_irq(>tree_lock); if (!start || start - offset > max) - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Mon, Jul 23, 2007 at 05:58:02PM +1000, Nick Piggin wrote:
> 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?)
Thank you!
All comments seems reasonable, so I simply attach the updated patch.
Fengguang
---
Subject: radixtree: introduce radix_tree_next_hole()
Cc: Nick Piggin <[EMAIL PROTECTED]>
Introduce radix_tree_next_hole(root, index, max_scan) to scan radix tree
for the first hole. It will be used in interleaved readahead.
Cc: Nick Piggin <[EMAIL PROTECTED]>
Signed-off-by: Fengguang Wu <[EMAIL PROTECTED]>
---
include/linux/radix-tree.h |2 +
lib/radix-tree.c | 36 +++
2 files changed, 38 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_next_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,42 @@ int radix_tree_tag_get(struct radix_tree
EXPORT_SYMBOL(radix_tree_tag_get);
#endif
+/**
+ * radix_tree_next_hole-find the next hole (not-present entry)
+ * @root: 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_next_hole(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;
+ index++;
+ if (index == 0)
+ break;
+ }
+
+ return index;
+}
+EXPORT_SYMBOL(radix_tree_next_hole);
+
static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
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 <[EMAIL PROTECTED]>
Signed-off-by: Fengguang Wu <[EMAIL PROTECTED]>
---
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 [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
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 [EMAIL PROTECTED]
Signed-off-by: Fengguang Wu [EMAIL PROTECTED]
---
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 [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Mon, Jul 23, 2007 at 05:58:02PM +1000, Nick Piggin wrote:
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?)
Thank you!
All comments seems reasonable, so I simply attach the updated patch.
Fengguang
---
Subject: radixtree: introduce radix_tree_next_hole()
Cc: Nick Piggin [EMAIL PROTECTED]
Introduce radix_tree_next_hole(root, index, max_scan) to scan radix tree
for the first hole. It will be used in interleaved readahead.
Cc: Nick Piggin [EMAIL PROTECTED]
Signed-off-by: Fengguang Wu [EMAIL PROTECTED]
---
include/linux/radix-tree.h |2 +
lib/radix-tree.c | 36 +++
2 files changed, 38 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_next_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,42 @@ int radix_tree_tag_get(struct radix_tree
EXPORT_SYMBOL(radix_tree_tag_get);
#endif
+/**
+ * radix_tree_next_hole-find the next hole (not-present entry)
+ * @root: 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_next_hole(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;
+ index++;
+ if (index == 0)
+ break;
+ }
+
+ return index;
+}
+EXPORT_SYMBOL(radix_tree_next_hole);
+
static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Mon, Jul 23, 2007 at 04:04:05PM +0800, Fengguang Wu wrote: On Mon, Jul 23, 2007 at 05:58:02PM +1000, Nick Piggin wrote: 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?) Thank you! All comments seems reasonable, so I simply attach the updated patch. Fengguang --- Subject: radixtree: introduce radix_tree_next_hole() Cc: Nick Piggin [EMAIL PROTECTED] Introduce radix_tree_next_hole(root, index, max_scan) to scan radix tree for the first hole. It will be used in interleaved readahead. Cc: Nick Piggin [EMAIL PROTECTED] Signed-off-by: Fengguang Wu [EMAIL PROTECTED] And another rename fix for the interleaved readahead patch. Signed-off-by: Fengguang Wu [EMAIL PROTECTED] --- mm/readahead.c |2 +- 1 file changed, 1 insertion(+), 1 deletion(-) --- linux-2.6.22-rc6-mm1.orig/mm/readahead.c +++ linux-2.6.22-rc6-mm1/mm/readahead.c @@ -372,7 +372,7 @@ ondemand_readahead(struct address_space pgoff_t start; read_lock_irq(mapping-tree_lock); - start = radix_tree_scan_hole(mapping-page_tree, offset, max+1); + start = radix_tree_next_hole(mapping-page_tree, offset, max+1); read_unlock_irq(mapping-tree_lock); if (!start || start - offset max) - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Fri, Jul 20, 2007 at 10:48:59PM -0700, Andrew Morton wrote: > On Sat, 21 Jul 2007 12:43:06 +0800 Fengguang Wu <[EMAIL PROTECTED]> 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. > > If you're ever feeling fantastically bored, please consider updating the > userspace radix-tree test harness for this? Cook up a couple of testcases > for the new functionality? Thanks for the reminding. I'd add some test cases if I'm to optimize it. But this _dumb_ scan function is obviously correct(and won't be too slow on 1M readahead). In fact it is pretty suitable for testing the optimized one ;) - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Fri, Jul 20, 2007 at 10:48:59PM -0700, Andrew Morton wrote: On Sat, 21 Jul 2007 12:43:06 +0800 Fengguang Wu [EMAIL PROTECTED] 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. If you're ever feeling fantastically bored, please consider updating the userspace radix-tree test harness for this? Cook up a couple of testcases for the new functionality? Thanks for the reminding. I'd add some test cases if I'm to optimize it. But this _dumb_ scan function is obviously correct(and won't be too slow on 1M readahead). In fact it is pretty suitable for testing the optimized one ;) - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Sat, 21 Jul 2007 12:43:06 +0800 Fengguang Wu <[EMAIL PROTECTED]> 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. If you're ever feeling fantastically bored, please consider updating the userspace radix-tree test harness for this? Cook up a couple of testcases for the new functionality? Thanks. http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz is the latest. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
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.
Cc: Nick Piggin <[EMAIL PROTECTED]>
Signed-off-by: Fengguang Wu <[EMAIL PROTECTED]>
---
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;
+ }
+
+ 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
+ */
+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);
+
static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
--
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
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.
Cc: Nick Piggin [EMAIL PROTECTED]
Signed-off-by: Fengguang Wu [EMAIL PROTECTED]
---
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;
+ }
+
+ 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
+ */
+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);
+
static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
--
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 6/7] radixtree: introduce radix_tree_scan_hole()
On Sat, 21 Jul 2007 12:43:06 +0800 Fengguang Wu [EMAIL PROTECTED] 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. If you're ever feeling fantastically bored, please consider updating the userspace radix-tree test harness for this? Cook up a couple of testcases for the new functionality? Thanks. http://www.zip.com.au/~akpm/linux/patches/stuff/rtth.tar.gz is the latest. - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
