Skip to contentSkip to conversation

lib : provide a more precise radix_tree_gang_lookup_slot

PATCH In review Huang Shijie 2 participants 3 messages May 25, 2009 – May 27, 2009

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib : provide a more precise radix_tree_gang_lookup_slot

The origin radix_tree_gang_lookup_slot() tries to
lookup max_items slots.But there are maybe holes for find_get_pages_contig() which will only use the contiguous part.

So a more precise radix_tree_gang_lookup_slot() is needed
to avoid unneccessary search work.

---
 include/linux/radix-tree.h |    3 ++-
 lib/radix-tree.c           |   27 +++++++++++++++++++++++----
 mm/filemap.c               |    4 ++--
 3 files changed, 27 insertions(+), 7 deletions(-)
include/linux/radix-tree.h +2 -1
index 355f6e8..03e25f4 100644
@@ -164,7 +164,8 @@ 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_slot(struct radix_tree_root *root, void ***results,
-			unsigned long first_index, unsigned int max_items);
+			unsigned long first_index, unsigned int max_items,
+			int contig);
 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);
lib/radix-tree.c +23 -4
index 4bb42a0..f81c21c 100644
@@ -666,9 +666,13 @@ unsigned long radix_tree_next_hole(struct radix_tree_root *root,
 }
 EXPORT_SYMBOL(radix_tree_next_hole);
 
+/*
+ * contig == 0 : next_index is index for next search
+ * contig == 1 : next_index is MAYBE the index of the first NULL slot
+ */
 static unsigned int
 __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
-	unsigned int max_items, unsigned long *next_index)
+	unsigned int max_items, unsigned long *next_index, int contig)
 {
 	unsigned int nr_found = 0;
 	unsigned int shift, height;
@@ -684,6 +688,9 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
 		for (;;) {
 			if (slot->slots[i] != NULL)
 				break;
+			if (contig)
+				goto out;
+
 			index &= ~((1UL << shift) - 1);
 			index += 1UL << shift;
 			if (index == 0)
@@ -706,6 +713,9 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
 			results[nr_found++] = &(slot->slots[i]);
 			if (nr_found == max_items)
 				goto out;
+		} else if (contig) {
+			index--;
+			goto out;
 		}
 	}
 out:
@@ -763,7 +773,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 		if (cur_index > max_index)
 			break;
 		slots_found = __lookup(node, (void ***)results + ret, cur_index,
-					max_items - ret, &next_index);
+					max_items - ret, &next_index, 0);
 		nr_found = 0;
 		for (i = 0; i < slots_found; i++) {
 			struct radix_tree_node *slot;
@@ -789,6 +799,7 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
  *	@results:	where the results of the lookup are placed
  *	@first_index:	start the lookup from this key
  *	@max_items:	place up to this many items at *results
+ *	@contig:	if the indexes of slots are required to be contiguous
  *
  *	Performs an index-ascending scan of the tree for present items.  Places
  *	their slots at *@results and returns the number of items which were
@@ -802,7 +813,8 @@ EXPORT_SYMBOL(radix_tree_gang_lookup);
  */
 unsigned int
 radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
-			unsigned long first_index, unsigned int max_items)
+			unsigned long first_index, unsigned int max_items,
+			int contig)
 {
 	unsigned long max_index;
 	struct radix_tree_node *node;
@@ -831,11 +843,18 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
 		if (cur_index > max_index)
 			break;
 		slots_found = __lookup(node, results + ret, cur_index,
-					max_items - ret, &next_index);
+					max_items - ret, &next_index, contig);
 		ret += slots_found;
 		if (next_index == 0)
 			break;
 		cur_index = next_index;
+
+		if (contig) {
+			if (slots_found == 0)
+				break;
+			if (next_index & RADIX_TREE_MAP_MASK)
+				break;
+		}
 	}
 
 	return ret;
mm/filemap.c +2 -2
index 379ff0b..ec17645 100644
@@ -807,7 +807,7 @@ unsigned find_get_pages(struct address_space *mapping, pgoff_t start,
 	rcu_read_lock();
 restart:
 	nr_found = radix_tree_gang_lookup_slot(&mapping->page_tree,
-				(void ***)pages, start, nr_pages);
+				(void ***)pages, start, nr_pages, 0);
 	ret = 0;
 	for (i = 0; i < nr_found; i++) {
 		struct page *page;
@@ -860,7 +860,7 @@ unsigned find_get_pages_contig(struct address_space *mapping, pgoff_t index,
 	rcu_read_lock();
 restart:
 	nr_found = radix_tree_gang_lookup_slot(&mapping->page_tree,
-				(void ***)pages, index, nr_pages);
+				(void ***)pages, index, nr_pages, 1);
 	ret = 0;
 	for (i = 0; i < nr_found; i++) {
 		struct page *page;
Signature · 7 lines
1.6.0.6

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
maintainer
#1 lore raw
Quoted 7 lines · On Mon, 25 May 2009 11:53:55 +0800 Huang Shijie <[email protected]> wrote:

The origin radix_tree_gang_lookup_slot() tries to
lookup max_items slots.But there are maybe holes for find_get_pages_contig() which will only use the contiguous part.

So a more precise radix_tree_gang_lookup_slot() is needed
to avoid unneccessary search work.

OK..

include/linux/radix-tree.h radix_tree_gang_lookup(struct radix_tree_root *root, void **results, · line 168

Quoted 11 lines
include/linux/radix-tree.h +2 -1
index 355f6e8..03e25f4 100644
@@ -164,7 +164,8 @@ 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_slot(struct radix_tree_root *root, void ***results,
-			unsigned long first_index, unsigned int max_items);
+			unsigned long first_index, unsigned int max_items,
+			int contig);

Variable contig' could have the type bool'. Did you consider and reject that option, or just didn't think of it?

Quoted 8 lines

...

include/linux/radix-tree.h +7 -0
+			if (contig)
+				goto out;
+
+		} else if (contig) {
+			index--;
+			goto out;
+

include/linux/radix-tree.h

Quoted 10 lines
include/linux/radix-tree.h +8 -2
+		if (contig) {
+			if (slots_found == 0)
+				break;
+			if (next_index & RADIX_TREE_MAP_MASK)
+				break;
+		}
-				(void ***)pages, start, nr_pages);
+				(void ***)pages, start, nr_pages, 0);
-				(void ***)pages, index, nr_pages);
+				(void ***)pages, index, nr_pages, 1);

The patch adds cycles in some cases and saves them in others.

Does the saving exceed the adding? How do we know that the patch is a net benefit?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#2 lore raw
Quoted 19 lines

include/linux/radix-tree.h radix_tree_gang_lookup(struct radix_tree_root *root, void **results, · line 169

Quoted 13 lines
include/linux/radix-tree.h +2 -1
index 355f6e8..03e25f4 100644
@@ -164,7 +164,8 @@ 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_slot(struct radix_tree_root *root, void ***results,
-			unsigned long first_index, unsigned int max_items);
+			unsigned long first_index, unsigned int max_items,
+			int contig);
 

Variable contig' could have the type bool'. Did you consider and reject that option, or just didn't think of it?

Yes, type `bool' is better.

Quoted 22 lines
Quoted 9 lines

...

include/linux/radix-tree.h +7 -0
+			if (contig)
+				goto out;
+
+		} else if (contig) {
+			index--;
+			goto out;
+

include/linux/radix-tree.h

Quoted 10 lines
include/linux/radix-tree.h +8 -2
+		if (contig) {
+			if (slots_found == 0)
+				break;
+			if (next_index & RADIX_TREE_MAP_MASK)
+				break;
+		}
-				(void ***)pages, start, nr_pages);
+				(void ***)pages, start, nr_pages, 0);
-				(void ***)pages, index, nr_pages);
+				(void ***)pages, index, nr_pages, 1);

The patch adds cycles in some cases and saves them in others.

Quoted 4 lines

Does the saving exceed the adding? How do we know that the patch is a net benefit?

Assume that:
f0 = called frequency of find_get_pages() (contig == 0) f1 = called frequency of find_get_pages_contig() (contig == 1)

The primary user of find_get_pages() is ->writepage[s] of some file systems such as ext4. ( I think the shmem_lock() ,truncate() run occasionally which also call it.)

The primary user of find_get_pages_contig() is also the ->writepage[s] of some filesystem such as afs.( I am not sure whether btrfs is also the main user of it )

So if (f0 nearly equal f1)
cycles saving >> cycles adding

__lookup() saves much cycles when there are holes and the contig==1.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>