| Message ID | 1479341856-30320-60-git-send-email-mawilcox@linuxonhyperv.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox <mawilcox@linuxonhyperv.com> wrote: > From: Matthew Wilcox <mawilcox@microsoft.com> > > This rather complicated function can be better implemented as an iterator. > It has only one caller, so move the functionality to the only place that > needs it. Update the test suite to follow the same pattern. Looks good. I suppose this patch could be applied separately. > > Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> > --- > include/linux/radix-tree.h | 1 - > lib/radix-tree.c | 99 ----------------------------------- > mm/shmem.c | 26 ++++++++- > tools/testing/radix-tree/main.c | 8 +-- > tools/testing/radix-tree/multiorder.c | 2 +- > tools/testing/radix-tree/test.c | 22 ++++++++ > tools/testing/radix-tree/test.h | 2 + > 7 files changed, 54 insertions(+), 106 deletions(-) > > diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h > index 36c6175..57bf635 100644 > --- a/include/linux/radix-tree.h > +++ b/include/linux/radix-tree.h > @@ -306,7 +306,6 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, > unsigned long nr_to_tag, > unsigned int fromtag, unsigned int totag); > int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag); > -unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item); > > static inline void radix_tree_preload_end(void) > { > diff --git a/lib/radix-tree.c b/lib/radix-tree.c > index 27b53ef..7e70ac9 100644 > --- a/lib/radix-tree.c > +++ b/lib/radix-tree.c > @@ -1605,105 +1605,6 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, > } > EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); > > -#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP) > -#include <linux/sched.h> /* for cond_resched() */ > - > -struct locate_info { > - unsigned long found_index; > - bool stop; > -}; > - > -/* > - * This linear search is at present only useful to shmem_unuse_inode(). > - */ > -static unsigned long __locate(struct radix_tree_node *slot, void *item, > - unsigned long index, struct locate_info *info) > -{ > - unsigned long i; > - > - do { > - unsigned int shift = slot->shift; > - > - for (i = (index >> shift) & RADIX_TREE_MAP_MASK; > - i < RADIX_TREE_MAP_SIZE; > - i++, index += (1UL << shift)) { > - struct radix_tree_node *node = > - rcu_dereference_raw(slot->slots[i]); > - if (node == RADIX_TREE_RETRY) > - goto out; > - if (!radix_tree_is_internal_node(node)) { > - if (node == item) { > - info->found_index = index; > - info->stop = true; > - goto out; > - } > - continue; > - } > - node = entry_to_node(node); > - if (is_sibling_entry(slot, node)) > - continue; > - slot = node; > - break; > - } > - } while (i < RADIX_TREE_MAP_SIZE); > - > -out: > - if ((index == 0) && (i == RADIX_TREE_MAP_SIZE)) > - info->stop = true; > - return index; > -} > - > -/** > - * radix_tree_locate_item - search through radix tree for item > - * @root: radix tree root > - * @item: item to be found > - * > - * Returns index where item was found, or -1 if not found. > - * Caller must hold no lock (since this time-consuming function needs > - * to be preemptible), and must check afterwards if item is still there. > - */ > -unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) > -{ > - struct radix_tree_node *node; > - unsigned long max_index; > - unsigned long cur_index = 0; > - struct locate_info info = { > - .found_index = -1, > - .stop = false, > - }; > - > - do { > - rcu_read_lock(); > - node = rcu_dereference_raw(root->rnode); > - if (!radix_tree_is_internal_node(node)) { > - rcu_read_unlock(); > - if (node == item) > - info.found_index = 0; > - break; > - } > - > - node = entry_to_node(node); > - > - max_index = node_maxindex(node); > - if (cur_index > max_index) { > - rcu_read_unlock(); > - break; > - } > - > - cur_index = __locate(node, item, cur_index, &info); > - rcu_read_unlock(); > - cond_resched(); > - } while (!info.stop && cur_index <= max_index); > - > - return info.found_index; > -} > -#else > -unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) > -{ > - return -1; > -} > -#endif /* CONFIG_SHMEM && CONFIG_SWAP */ > - > /** > * radix_tree_shrink - shrink radix tree to minimum height > * @root radix tree root > diff --git a/mm/shmem.c b/mm/shmem.c > index 0b3fe33..8f9c9aa 100644 > --- a/mm/shmem.c > +++ b/mm/shmem.c > @@ -1046,6 +1046,30 @@ static void shmem_evict_inode(struct inode *inode) > clear_inode(inode); > } > > +static unsigned long find_swap_entry(struct radix_tree_root *root, void *item) > +{ > + struct radix_tree_iter iter; > + void **slot; > + unsigned long found = -1; > + unsigned int checked = 0; > + > + rcu_read_lock(); > + radix_tree_for_each_slot(slot, root, &iter, 0) { > + if (*slot == item) { > + found = iter.index; > + break; > + } > + checked++; > + if ((checked % 4096) != 0) > + continue; > + slot = radix_tree_iter_next(slot, &iter); > + cond_resched_rcu(); > + } > + > + rcu_read_unlock(); > + return found; > +} > + > /* > * If swap found in inode, free it and move page from swapcache to filecache. > */ > @@ -1059,7 +1083,7 @@ static int shmem_unuse_inode(struct shmem_inode_info *info, > int error = 0; > > radswap = swp_to_radix_entry(swap); > - index = radix_tree_locate_item(&mapping->page_tree, radswap); > + index = find_swap_entry(&mapping->page_tree, radswap); > if (index == -1) > return -EAGAIN; /* tell shmem_unuse we found nothing */ > > diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c > index 8621542..93a77f9 100644 > --- a/tools/testing/radix-tree/main.c > +++ b/tools/testing/radix-tree/main.c > @@ -239,7 +239,7 @@ static void __locate_check(struct radix_tree_root *tree, unsigned long index, > > item_insert_order(tree, index, order); > item = item_lookup(tree, index); > - index2 = radix_tree_locate_item(tree, item); > + index2 = find_item(tree, item); > if (index != index2) { > printf("index %ld order %d inserted; found %ld\n", > index, order, index2); > @@ -273,17 +273,17 @@ static void locate_check(void) > index += (1UL << order)) { > __locate_check(&tree, index + offset, order); > } > - if (radix_tree_locate_item(&tree, &tree) != -1) > + if (find_item(&tree, &tree) != -1) > abort(); > > item_kill_tree(&tree); > } > } > > - if (radix_tree_locate_item(&tree, &tree) != -1) > + if (find_item(&tree, &tree) != -1) > abort(); > __locate_check(&tree, -1, 0); > - if (radix_tree_locate_item(&tree, &tree) != -1) > + if (find_item(&tree, &tree) != -1) > abort(); > item_kill_tree(&tree); > } > diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c > index 588209a..400de5c 100644 > --- a/tools/testing/radix-tree/multiorder.c > +++ b/tools/testing/radix-tree/multiorder.c > @@ -347,7 +347,7 @@ static void __multiorder_join(unsigned long index, > item_insert_order(&tree, index, order2); > item = radix_tree_lookup(&tree, index); > radix_tree_join(&tree, index + 1, order1, item2); > - loc = radix_tree_locate_item(&tree, item); > + loc = find_item(&tree, item); > if (loc == -1) > free(item); > item = radix_tree_lookup(&tree, index + 1); > diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c > index a6e8099..a68ed3b 100644 > --- a/tools/testing/radix-tree/test.c > +++ b/tools/testing/radix-tree/test.c > @@ -142,6 +142,28 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start, > assert(nfound == 0); > } > > +/* Use the same pattern as find_swap_entry() in mm/shmem.c */ > +unsigned long find_item(struct radix_tree_root *root, void *item) > +{ > + struct radix_tree_iter iter; > + void **slot; > + unsigned long found = -1; > + unsigned long checked = 0; > + > + radix_tree_for_each_slot(slot, root, &iter, 0) { > + if (*slot == item) { > + found = iter.index; > + break; > + } > + checked++; > + if ((checked % 4) != 0) > + continue; > + slot = radix_tree_iter_next(slot, &iter); > + } > + > + return found; > +} > + > static int verify_node(struct radix_tree_node *slot, unsigned int tag, > int tagged) > { > diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h > index b678f13..ccdd3c1 100644 > --- a/tools/testing/radix-tree/test.h > +++ b/tools/testing/radix-tree/test.h > @@ -27,6 +27,8 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start, > unsigned long nr, int chunk); > void item_kill_tree(struct radix_tree_root *root); > > +unsigned long find_item(struct radix_tree_root *, void *item); > + > void tag_check(void); > void multiorder_checks(void); > void iteration_test(void); > -- > 2.10.2 > > -- > To unsubscribe, send a message with 'unsubscribe linux-mm' in > the body to majordomo@kvack.org. For more info on Linux MM, > see: http://www.linux-mm.org/ . > Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a> -- To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
From: Konstantin Khlebnikov [mailto:koct9i@gmail.com] > On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox > <mawilcox@linuxonhyperv.com> wrote: > > This rather complicated function can be better implemented as an iterator. > > It has only one caller, so move the functionality to the only place that > > needs it. Update the test suite to follow the same pattern. > > Looks good. I suppose this patch could be applied separately. Yes, a number of these patches stand alone from each other and could easily be separated out. I'm going to put your Reviewed-by: on the patches you've said "Looks good" to. Thanks!
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 36c6175..57bf635 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -306,7 +306,6 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, unsigned long nr_to_tag, unsigned int fromtag, unsigned int totag); int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag); -unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item); static inline void radix_tree_preload_end(void) { diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 27b53ef..7e70ac9 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1605,105 +1605,6 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results, } EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); -#if defined(CONFIG_SHMEM) && defined(CONFIG_SWAP) -#include <linux/sched.h> /* for cond_resched() */ - -struct locate_info { - unsigned long found_index; - bool stop; -}; - -/* - * This linear search is at present only useful to shmem_unuse_inode(). - */ -static unsigned long __locate(struct radix_tree_node *slot, void *item, - unsigned long index, struct locate_info *info) -{ - unsigned long i; - - do { - unsigned int shift = slot->shift; - - for (i = (index >> shift) & RADIX_TREE_MAP_MASK; - i < RADIX_TREE_MAP_SIZE; - i++, index += (1UL << shift)) { - struct radix_tree_node *node = - rcu_dereference_raw(slot->slots[i]); - if (node == RADIX_TREE_RETRY) - goto out; - if (!radix_tree_is_internal_node(node)) { - if (node == item) { - info->found_index = index; - info->stop = true; - goto out; - } - continue; - } - node = entry_to_node(node); - if (is_sibling_entry(slot, node)) - continue; - slot = node; - break; - } - } while (i < RADIX_TREE_MAP_SIZE); - -out: - if ((index == 0) && (i == RADIX_TREE_MAP_SIZE)) - info->stop = true; - return index; -} - -/** - * radix_tree_locate_item - search through radix tree for item - * @root: radix tree root - * @item: item to be found - * - * Returns index where item was found, or -1 if not found. - * Caller must hold no lock (since this time-consuming function needs - * to be preemptible), and must check afterwards if item is still there. - */ -unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) -{ - struct radix_tree_node *node; - unsigned long max_index; - unsigned long cur_index = 0; - struct locate_info info = { - .found_index = -1, - .stop = false, - }; - - do { - rcu_read_lock(); - node = rcu_dereference_raw(root->rnode); - if (!radix_tree_is_internal_node(node)) { - rcu_read_unlock(); - if (node == item) - info.found_index = 0; - break; - } - - node = entry_to_node(node); - - max_index = node_maxindex(node); - if (cur_index > max_index) { - rcu_read_unlock(); - break; - } - - cur_index = __locate(node, item, cur_index, &info); - rcu_read_unlock(); - cond_resched(); - } while (!info.stop && cur_index <= max_index); - - return info.found_index; -} -#else -unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item) -{ - return -1; -} -#endif /* CONFIG_SHMEM && CONFIG_SWAP */ - /** * radix_tree_shrink - shrink radix tree to minimum height * @root radix tree root diff --git a/mm/shmem.c b/mm/shmem.c index 0b3fe33..8f9c9aa 100644 --- a/mm/shmem.c +++ b/mm/shmem.c @@ -1046,6 +1046,30 @@ static void shmem_evict_inode(struct inode *inode) clear_inode(inode); } +static unsigned long find_swap_entry(struct radix_tree_root *root, void *item) +{ + struct radix_tree_iter iter; + void **slot; + unsigned long found = -1; + unsigned int checked = 0; + + rcu_read_lock(); + radix_tree_for_each_slot(slot, root, &iter, 0) { + if (*slot == item) { + found = iter.index; + break; + } + checked++; + if ((checked % 4096) != 0) + continue; + slot = radix_tree_iter_next(slot, &iter); + cond_resched_rcu(); + } + + rcu_read_unlock(); + return found; +} + /* * If swap found in inode, free it and move page from swapcache to filecache. */ @@ -1059,7 +1083,7 @@ static int shmem_unuse_inode(struct shmem_inode_info *info, int error = 0; radswap = swp_to_radix_entry(swap); - index = radix_tree_locate_item(&mapping->page_tree, radswap); + index = find_swap_entry(&mapping->page_tree, radswap); if (index == -1) return -EAGAIN; /* tell shmem_unuse we found nothing */ diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c index 8621542..93a77f9 100644 --- a/tools/testing/radix-tree/main.c +++ b/tools/testing/radix-tree/main.c @@ -239,7 +239,7 @@ static void __locate_check(struct radix_tree_root *tree, unsigned long index, item_insert_order(tree, index, order); item = item_lookup(tree, index); - index2 = radix_tree_locate_item(tree, item); + index2 = find_item(tree, item); if (index != index2) { printf("index %ld order %d inserted; found %ld\n", index, order, index2); @@ -273,17 +273,17 @@ static void locate_check(void) index += (1UL << order)) { __locate_check(&tree, index + offset, order); } - if (radix_tree_locate_item(&tree, &tree) != -1) + if (find_item(&tree, &tree) != -1) abort(); item_kill_tree(&tree); } } - if (radix_tree_locate_item(&tree, &tree) != -1) + if (find_item(&tree, &tree) != -1) abort(); __locate_check(&tree, -1, 0); - if (radix_tree_locate_item(&tree, &tree) != -1) + if (find_item(&tree, &tree) != -1) abort(); item_kill_tree(&tree); } diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c index 588209a..400de5c 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -347,7 +347,7 @@ static void __multiorder_join(unsigned long index, item_insert_order(&tree, index, order2); item = radix_tree_lookup(&tree, index); radix_tree_join(&tree, index + 1, order1, item2); - loc = radix_tree_locate_item(&tree, item); + loc = find_item(&tree, item); if (loc == -1) free(item); item = radix_tree_lookup(&tree, index + 1); diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c index a6e8099..a68ed3b 100644 --- a/tools/testing/radix-tree/test.c +++ b/tools/testing/radix-tree/test.c @@ -142,6 +142,28 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start, assert(nfound == 0); } +/* Use the same pattern as find_swap_entry() in mm/shmem.c */ +unsigned long find_item(struct radix_tree_root *root, void *item) +{ + struct radix_tree_iter iter; + void **slot; + unsigned long found = -1; + unsigned long checked = 0; + + radix_tree_for_each_slot(slot, root, &iter, 0) { + if (*slot == item) { + found = iter.index; + break; + } + checked++; + if ((checked % 4) != 0) + continue; + slot = radix_tree_iter_next(slot, &iter); + } + + return found; +} + static int verify_node(struct radix_tree_node *slot, unsigned int tag, int tagged) { diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h index b678f13..ccdd3c1 100644 --- a/tools/testing/radix-tree/test.h +++ b/tools/testing/radix-tree/test.h @@ -27,6 +27,8 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start, unsigned long nr, int chunk); void item_kill_tree(struct radix_tree_root *root); +unsigned long find_item(struct radix_tree_root *, void *item); + void tag_check(void); void multiorder_checks(void); void iteration_test(void);