Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1525225
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | Re: [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() |
| Date | 2016-11-18 13:00 +0100 |
| Message-ID | <sEPZM-6BF-3@gated-at.bofh.it> (permalink) |
| References | <sEgSl-rg-1@gated-at.bofh.it> <sEh22-uC-3@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
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>
Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
[PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:30 +0100
[PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
Re: [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 13:00 +0100
RE: [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 17:50 +0100
[PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
Re: [PATCH 23/29] idr: Add ida_is_empty Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 13:00 +0100
[PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
Re: [PATCH 20/29] radix tree: Improve multiorder iterators Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 12:50 +0100
RE: [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 17:40 +0100
Re: [PATCH 20/29] radix tree: Improve multiorder iterators Konstantin Khlebnikov <koct9i@gmail.com> - 2016-11-18 19:00 +0100
RE: [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 22:00 +0100
[PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 13/29] radix-tree: Fix typo Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:40 +0100
[PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
[PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
RE: [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-17 21:00 +0100
Re: [PATCH 00/29] Improve radix tree for 4.10 Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-11-17 23:20 +0100
RE: [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox <mawilcox@microsoft.com> - 2016-11-18 05:40 +0100
[PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-11-16 23:50 +0100
csiph-web