* [PATCH] lib : provide a more precise radix_tree_gang_lookup_slot
@ 2009-05-25 3:53 Huang Shijie
2009-05-26 21:30 ` Andrew Morton
0 siblings, 1 reply; 3+ messages in thread
From: Huang Shijie @ 2009-05-25 3:53 UTC (permalink / raw)
To: akpm; +Cc: cl, linux-mm, linux-kernel, Huang Shijie
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.
Signed-off-by: Huang Shijie <shijie8@gmail.com>
---
include/linux/radix-tree.h | 3 ++-
lib/radix-tree.c | 27 +++++++++++++++++++++++----
mm/filemap.c | 4 ++--
3 files changed, 27 insertions(+), 7 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 355f6e8..03e25f4 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -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);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 4bb42a0..f81c21c 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -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;
diff --git a/mm/filemap.c b/mm/filemap.c
index 379ff0b..ec17645 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -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;
--
1.6.0.6
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH] lib : provide a more precise radix_tree_gang_lookup_slot
2009-05-25 3:53 [PATCH] lib : provide a more precise radix_tree_gang_lookup_slot Huang Shijie
@ 2009-05-26 21:30 ` Andrew Morton
2009-05-27 7:39 ` Huang Shijie
0 siblings, 1 reply; 3+ messages in thread
From: Andrew Morton @ 2009-05-26 21:30 UTC (permalink / raw)
To: Huang Shijie; +Cc: cl, linux-mm, linux-kernel, shijie8
On Mon, 25 May 2009 11:53:55 +0800
Huang Shijie <shijie8@gmail.com> 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..
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 355f6e8..03e25f4 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -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?
> ...
> + if (contig)
> + goto out;
> +
> + } else if (contig) {
> + index--;
> + goto out;
> +
> + 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?
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] lib : provide a more precise radix_tree_gang_lookup_slot
2009-05-26 21:30 ` Andrew Morton
@ 2009-05-27 7:39 ` Huang Shijie
0 siblings, 0 replies; 3+ messages in thread
From: Huang Shijie @ 2009-05-27 7:39 UTC (permalink / raw)
To: Andrew Morton; +Cc: cl, linux-mm, linux-kernel
>> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
>> index 355f6e8..03e25f4 100644
>> --- a/include/linux/radix-tree.h
>> +++ b/include/linux/radix-tree.h
>> @@ -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.
>> ...
>> + if (contig)
>> + goto out;
>> +
>> + } else if (contig) {
>> + index--;
>> + goto out;
>> +
>> + 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?
>
>
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.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2009-05-27 7:44 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-05-25 3:53 [PATCH] lib : provide a more precise radix_tree_gang_lookup_slot Huang Shijie
2009-05-26 21:30 ` Andrew Morton
2009-05-27 7:39 ` Huang Shijie
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).