lib : provide a more precise radix_tree_gang_lookup_slot
Subsystems (3)
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
@@ -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
@@ -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
@@ -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>
Andrew Morton
maintainerQuoted 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
lookupmax_itemsslots.But there are maybe holes forfind_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@@ -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>
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@@ -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 typebool'. 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>