Skip to contentSkip to conversation

: introduce radix_tree_gang_lookup_range

PATCH In review David Chinner 2 participants 3 messages Nov 22, 2007 – Nov 25, 2007 Library code

lore
Share & tools
lore

David Chinner

author
#0 lore raw

PATCH 1/9 : introduce radix_tree_gang_lookup_range

Introduce radix_tree_gang_lookup_range()

The inode clustering in XFS requires a gang lookup on the radix tree to find all the inodes in the cluster. The gang lookup has to set the maximum items to that of a fully populated cluster so we get all the inodes in the cluster, but we only populate the radix tree sparsely (on demand).

As a result, the gang lookup can search way, way past the index of end of the cluster because it is looking for a fixed number of entries to return.

We know we want to terminate the search at either a specific index or a maximum number of items, so we need to add a "last_index" parameter to the lookup.

Furthermore, the existing radix_tree_gang_lookup() can use this same function if we define a RADIX_TREE_MAX_INDEX value so the search is not limited by the last_index.

Signed-off-by Dave Chinner <[email protected]>
---
 include/linux/radix-tree.h |    7 ++++-
 lib/radix-tree.c           |   55 ++++++++++++++++++++++++++++++++++++---------
 2 files changed, 51 insertions(+), 11 deletions(-)
include/linux/radix-tree.h +6 -1
Index: 2.6.x-xfs-new/include/linux/radix-tree.h
===================================================================
@@ -98,10 +98,11 @@ do {									\
  * radix_tree_lookup
  * radix_tree_tag_get
  * radix_tree_gang_lookup
+ * radix_tree_gang_lookup_range
  * radix_tree_gang_lookup_tag
  * radix_tree_tagged
  *
- * The first 4 functions are able to be called locklessly, using RCU. The
+ * The first 5 functions are able to be called locklessly, using RCU. The
  * caller must ensure calls to these functions are made within rcu_read_lock()
  * regions. Other readers (lock-free or otherwise) and modifications may be
  * running concurrently.

@@ -155,6 +156,10 @@ 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 int
+radix_tree_gang_lookup_range(struct radix_tree_root *root, void **results,
+			unsigned long first_index, unsigned long last_index,
+			unsigned int max_items);
 int radix_tree_preload(gfp_t gfp_mask);
 void radix_tree_init(void);
 void *radix_tree_tag_set(struct radix_tree_root *root,
lib/radix-tree.c +45 -10

111 lines not on this page · raw message

#1 lore raw
Quoted 8 lines · David Chinner

Introduce radix_tree_gang_lookup_range()

The inode clustering in XFS requires a gang lookup on the radix tree to find all the inodes in the cluster. The gang lookup has to set the maximum items to that of a fully populated cluster so we get all the inodes in the cluster, but we only populate the radix tree sparsely (on demand).

Quoted 7 lines

As a result, the gang lookup can search way, way past the index of end of the cluster because it is looking for a fixed number of entries to return.

We know we want to terminate the search at either a specific index or a maximum number of items, so we need to add a "last_index" parameter to the lookup.

Yeah, this fixes one downside of the gang lookup API. For consistency it would be nice to do this for the tag lookup API as well...

Quoted 3 lines

Furthermore, the existing radix_tree_gang_lookup() can use this same function if we define a RADIX_TREE_MAX_INDEX value so the search is not limited by the last_index.

Nit: should just define it to be ULONG_MAX.

Quoted 2 lines
Signed-off-by Dave Chinner <[email protected]>

Otherwise, Acked-by: Nick Piggin <[email protected]>

author
#2 lore raw
Quoted 13 lines · Nick Piggin
Quoted 12 lines · David Chinner

Introduce radix_tree_gang_lookup_range()

The inode clustering in XFS requires a gang lookup on the radix tree to find all the inodes in the cluster. The gang lookup has to set the maximum items to that of a fully populated cluster so we get all the inodes in the cluster, but we only populate the radix tree sparsely (on demand).

As a result, the gang lookup can search way, way past the index of end of the cluster because it is looking for a fixed number of entries to return.

Quoted 6 lines
Quoted 3 lines

We know we want to terminate the search at either a specific index or a maximum number of items, so we need to add a "last_index" parameter to the lookup.

Yeah, this fixes one downside of the gang lookup API. For consistency it would be nice to do this for the tag lookup API as well...

Sure, I have need to do that as well. ;)

Quoted 5 lines
Quoted 3 lines

Furthermore, the existing radix_tree_gang_lookup() can use this same function if we define a RADIX_TREE_MAX_INDEX value so the search is not limited by the last_index.

Nit: should just define it to be ULONG_MAX.

Oh, right. Silly me. I'll post updated radix tree patches later today.

Thanks, Nick.

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
Principal Engineer
SGI Australian Software Group