Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1523884 > unrolled thread
| Started by | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| First post | 2016-11-16 23:30 +0100 |
| Last post | 2016-11-16 23:50 +0100 |
| Articles | 20 on this page of 66 — 4 participants |
Back to article view | Back to linux.kernel
[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
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-11-18 13:00 +0100 |
| Subject | Re: [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() |
| Message-ID | <sEPZM-6BF-3@gated-at.bofh.it> |
| In reply to | #1523908 |
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>
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@microsoft.com> |
|---|---|
| Date | 2016-11-18 17:50 +0100 |
| Subject | RE: [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() |
| Message-ID | <sEUwp-1by-7@gated-at.bofh.it> |
| In reply to | #1525225 |
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!
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 11/29] radix-tree: Add radix_tree_split |
| Message-ID | <sEh22-uC-5@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
This new function splits a larger multiorder entry into smaller entries
(potentially multi-order entries). These entries are initialised to
RADIX_TREE_RETRY to ensure that RCU walkers who see this state aren't
confused. The caller should then call radix_tree_for_each_slot() and
radix_tree_replace_slot() in order to turn these retry entries into the
intended new entries. Tags are replicated from the original multiorder
entry into each new entry.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
include/linux/radix-tree.h | 3 +
lib/radix-tree.c | 109 ++++++++++++++++++++++++++++++++--
tools/testing/radix-tree/multiorder.c | 26 ++++++++
3 files changed, 134 insertions(+), 4 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 1efd81f..f5518f1 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -319,8 +319,11 @@ static inline void radix_tree_preload_end(void)
preempt_enable();
}
+int radix_tree_split(struct radix_tree_root *, unsigned long index,
+ unsigned new_order);
int radix_tree_join(struct radix_tree_root *, unsigned long index,
unsigned new_order, void *);
+
/**
* struct radix_tree_iter - radix tree iterator state
*
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 6a76252..eaf0f353 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -231,7 +231,10 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
void *entry = node->slots[i];
if (!entry)
continue;
- if (is_sibling_entry(node, entry)) {
+ if (entry == RADIX_TREE_RETRY) {
+ pr_debug("radix retry offset %ld indices %ld-%ld\n",
+ i, first, last);
+ } else if (is_sibling_entry(node, entry)) {
pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
entry, i,
*(void **)entry_to_node(entry),
@@ -641,7 +644,10 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot,
unsigned i, n, tag, offset, tags = 0;
if (node) {
- n = 1 << (order - node->shift);
+ if (order > node->shift)
+ n = 1 << (order - node->shift);
+ else
+ n = 1;
offset = get_slot_offset(node, slot);
} else {
n = 1;
@@ -680,7 +686,8 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot,
tag_set(node, tag, offset);
}
if (radix_tree_is_internal_node(old) &&
- !is_sibling_entry(node, old))
+ !is_sibling_entry(node, old) &&
+ (old != RADIX_TREE_RETRY))
radix_tree_free_nodes(old);
}
if (node)
@@ -843,6 +850,98 @@ int radix_tree_join(struct radix_tree_root *root, unsigned long index,
return error;
}
+
+int radix_tree_split(struct radix_tree_root *root, unsigned long index,
+ unsigned order)
+{
+ struct radix_tree_node *parent, *node, *child;
+ void **slot;
+ unsigned int offset, end;
+ unsigned n, tag, tags = 0;
+
+ if (!__radix_tree_lookup(root, index, &parent, &slot))
+ return -ENOENT;
+ if (!parent)
+ return -ENOENT;
+
+ offset = get_slot_offset(parent, slot);
+
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ if (tag_get(parent, tag, offset))
+ tags |= 1 << tag;
+
+ for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) {
+ if (!is_sibling_entry(parent, parent->slots[end]))
+ break;
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ if (tags & (1 << tag))
+ tag_set(parent, tag, end);
+ /* rcu_assign_pointer ensures tags are set before RETRY */
+ rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY);
+ }
+
+ if (order == parent->shift)
+ return 0;
+ if (order > parent->shift) {
+ while (offset < end)
+ offset += insert_entries(parent, &parent->slots[offset],
+ RADIX_TREE_RETRY, order, true);
+ return 0;
+ }
+
+ node = parent;
+
+ for (;;) {
+ if (node->shift > order) {
+ child = radix_tree_node_alloc(root);
+ if (!child)
+ goto nomem;
+ child->shift = node->shift - RADIX_TREE_MAP_SHIFT;
+ child->offset = offset;
+ child->count = 0;
+ child->parent = node;
+ if (node != parent) {
+ node->count++;
+ node->slots[offset] = node_to_entry(child);
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ if (tags & (1 << tag))
+ tag_set(node, tag, offset);
+ }
+
+ node = child;
+ offset = 0;
+ continue;
+ }
+
+ n = insert_entries(node, &node->slots[offset],
+ RADIX_TREE_RETRY, order, false);
+ BUG_ON(n > RADIX_TREE_MAP_SIZE);
+
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ if (tags & (1 << tag))
+ tag_set(node, tag, offset);
+ offset += n;
+
+ while (offset == RADIX_TREE_MAP_SIZE) {
+ if (node == parent)
+ break;
+ offset = node->offset;
+ child = node;
+ node = node->parent;
+ rcu_assign_pointer(node->slots[offset],
+ node_to_entry(child));
+ offset++;
+ }
+ if ((node == parent) && (offset == end))
+ return 0;
+ }
+
+ nomem:
+ /* Shouldn't happen; did user forget to preload? */
+ /* TODO: free all the allocated nodes */
+ WARN_ON(1);
+ return -ENOMEM;
+}
#endif
/**
@@ -1081,8 +1180,10 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
child = rcu_dereference_raw(node->slots[offset]);
}
- if ((child == NULL) || (child == RADIX_TREE_RETRY))
+ if (!child)
goto restart;
+ if (child == RADIX_TREE_RETRY)
+ break;
} while (radix_tree_is_internal_node(child));
/* Update the iterator state */
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 4c66acc..d9e8155 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -356,6 +356,31 @@ static void multiorder_join(void)
}
}
+static void __multiorder_split(int old_order, int new_order)
+{
+ RADIX_TREE(tree, GFP_KERNEL);
+ void **slot;
+ struct radix_tree_iter iter;
+
+ item_insert_order(&tree, 0, old_order);
+ radix_tree_tag_set(&tree, 0, 2);
+ radix_tree_split(&tree, 0, new_order);
+ radix_tree_for_each_slot(slot, &tree, &iter, 0) {
+ radix_tree_replace_slot(slot, item_create(iter.index));
+ }
+
+ item_kill_tree(&tree);
+}
+
+static void multiorder_split(void)
+{
+ int i, j;
+
+ for (i = 9; i < 19; i++)
+ for (j = 0; j < i; j++)
+ __multiorder_split(i, j);
+}
+
void multiorder_checks(void)
{
int i;
@@ -374,4 +399,5 @@ void multiorder_checks(void)
multiorder_iteration();
multiorder_tagged_iteration();
multiorder_join();
+ multiorder_split();
}
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 08/29] tools: Add more bitmap functions |
| Message-ID | <sEh22-uC-9@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
I need the following functions for the radix tree:
bitmap_fill
find_next_zero_bit
bitmap_empty
bitmap_full
Copy the implementations from include/linux/bitmap.h and lib/find_bit.c
---
tools/include/linux/bitmap.h | 26 ++++++++++++++++++++++++++
tools/lib/find_bit.c | 8 ++++++++
2 files changed, 34 insertions(+)
diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h
index 43c1c50..eef41d5 100644
--- a/tools/include/linux/bitmap.h
+++ b/tools/include/linux/bitmap.h
@@ -35,6 +35,32 @@ static inline void bitmap_zero(unsigned long *dst, int nbits)
}
}
+static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
+{
+ unsigned int nlongs = BITS_TO_LONGS(nbits);
+ if (!small_const_nbits(nbits)) {
+ unsigned int len = (nlongs - 1) * sizeof(unsigned long);
+ memset(dst, 0xff, len);
+ }
+ dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
+}
+
+static inline int bitmap_empty(const unsigned long *src, unsigned nbits)
+{
+ if (small_const_nbits(nbits))
+ return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
+
+ return find_first_bit(src, nbits) == nbits;
+}
+
+static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
+{
+ if (small_const_nbits(nbits))
+ return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
+
+ return find_first_zero_bit(src, nbits) == nbits;
+}
+
static inline int bitmap_weight(const unsigned long *src, int nbits)
{
if (small_const_nbits(nbits))
diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c
index 9122a9e..de26b6f 100644
--- a/tools/lib/find_bit.c
+++ b/tools/lib/find_bit.c
@@ -66,6 +66,14 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
}
#endif
+#ifndef find_next_zero_bit
+unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
+ unsigned long offset)
+{
+ return _find_next_bit(addr, size, offset, ~0UL);
+}
+#endif
+
#ifndef find_first_bit
/*
* Find the first set bit in a memory region.
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 07/29] radix tree test suite: Use rcu_barrier |
| Message-ID | <sEh22-uC-7@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <mawilcox@microsoft.com>
Calling rcu_barrier() allows all of the rcu-freed memory to be actually
returned to the pool, and allows nr_allocated to return to 0. As well
as allowing diffs between runs to be more useful, it also lets us
pinpoint leaks more effectively.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
tools/testing/radix-tree/main.c | 12 ++++++++++--
tools/testing/radix-tree/tag_check.c | 5 +++++
2 files changed, 15 insertions(+), 2 deletions(-)
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index f43706c..8621542 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -295,24 +295,31 @@ static void single_thread_tests(bool long_run)
printf("starting single_thread_tests: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
multiorder_checks();
+ rcu_barrier();
printf("after multiorder_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
locate_check();
+ rcu_barrier();
printf("after locate_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
tag_check();
+ rcu_barrier();
printf("after tag_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
gang_check();
+ rcu_barrier();
printf("after gang_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
add_and_check();
+ rcu_barrier();
printf("after add_and_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
dynamic_height_check();
+ rcu_barrier();
printf("after dynamic_height_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
big_gang_check(long_run);
+ rcu_barrier();
printf("after big_gang_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
for (i = 0; i < (long_run ? 2000 : 3); i++) {
@@ -320,6 +327,7 @@ static void single_thread_tests(bool long_run)
printf("%d ", i);
fflush(stdout);
}
+ rcu_barrier();
printf("after copy_tag_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
}
@@ -354,8 +362,8 @@ int main(int argc, char **argv)
benchmark();
- sleep(1);
- printf("after sleep(1): %d allocated, preempt %d\n",
+ rcu_barrier();
+ printf("after rcu_barrier: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
rcu_unregister_thread();
diff --git a/tools/testing/radix-tree/tag_check.c b/tools/testing/radix-tree/tag_check.c
index b0ac057..186f6e4 100644
--- a/tools/testing/radix-tree/tag_check.c
+++ b/tools/testing/radix-tree/tag_check.c
@@ -51,6 +51,7 @@ void simple_checks(void)
verify_tag_consistency(&tree, 1);
printf("before item_kill_tree: %d allocated\n", nr_allocated);
item_kill_tree(&tree);
+ rcu_barrier();
printf("after item_kill_tree: %d allocated\n", nr_allocated);
}
@@ -331,12 +332,16 @@ void tag_check(void)
single_check();
extend_checks();
contract_checks();
+ rcu_barrier();
printf("after extend_checks: %d allocated\n", nr_allocated);
__leak_check();
leak_check();
+ rcu_barrier();
printf("after leak_check: %d allocated\n", nr_allocated);
simple_checks();
+ rcu_barrier();
printf("after simple_checks: %d allocated\n", nr_allocated);
thrash_tags();
+ rcu_barrier();
printf("after thrash_tags: %d allocated\n", nr_allocated);
}
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 28/29] radix-tree: Create all_tag_set |
| Message-ID | <sEh22-uC-11@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
all_tag_set() sets every tag on a node. This is useful for the IDR code
when we're creating new nodes which contain only free slots.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
lib/radix-tree.c | 8 +++++++-
1 file changed, 7 insertions(+), 1 deletion(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index c8ef657..e063ca2 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -22,6 +22,8 @@
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
+#include <linux/bitmap.h>
+#include <linux/bitops.h>
#include <linux/errno.h>
#include <linux/init.h>
#include <linux/kernel.h>
@@ -33,7 +35,6 @@
#include <linux/notifier.h>
#include <linux/cpu.h>
#include <linux/string.h>
-#include <linux/bitops.h>
#include <linux/rcupdate.h>
#include <linux/preempt.h> /* in_interrupt() */
@@ -184,6 +185,11 @@ static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
return 0;
}
+static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag)
+{
+ bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE);
+}
+
/**
* radix_tree_find_next_bit - find the next set bit in a memory region
*
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 10/29] radix-tree: Add radix_tree_join |
| Message-ID | <sEh22-uC-17@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
This new function allows for the replacement of many smaller entries in
the radix tree with one larger multiorder entry. From the point of view
of an RCU walker, they may see a mixture of the smaller entries and the
large entry during the same walk, but they will never see NULL for an
index which was populated before the join.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
include/linux/radix-tree.h | 2 +
lib/radix-tree.c | 159 +++++++++++++++++++++++++++-------
tools/testing/radix-tree/multiorder.c | 32 +++++++
3 files changed, 163 insertions(+), 30 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index af3581b..1efd81f 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -319,6 +319,8 @@ static inline void radix_tree_preload_end(void)
preempt_enable();
}
+int radix_tree_join(struct radix_tree_root *, unsigned long index,
+ unsigned new_order, void *);
/**
* struct radix_tree_iter - radix tree iterator state
*
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 8e6d552..6a76252 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -314,18 +314,14 @@ static void radix_tree_node_rcu_free(struct rcu_head *head)
{
struct radix_tree_node *node =
container_of(head, struct radix_tree_node, rcu_head);
- int i;
/*
- * must only free zeroed nodes into the slab. radix_tree_shrink
- * can leave us with a non-NULL entry in the first slot, so clear
- * that here to make sure.
+ * Must only free zeroed nodes into the slab. We can be left with
+ * non-NULL entries by radix_tree_free_nodes, so clear the entries
+ * and tags here.
*/
- for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)
- tag_clear(node, i, 0);
-
- node->slots[0] = NULL;
- node->count = 0;
+ memset(node->slots, 0, sizeof(node->slots));
+ memset(node->tags, 0, sizeof(node->tags));
kmem_cache_free(radix_tree_node_cachep, node);
}
@@ -563,14 +559,14 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
shift = radix_tree_load_root(root, &child, &maxindex);
/* Make sure the tree is high enough. */
+ if (order > 0 && max == ((1UL << order) - 1))
+ max++;
if (max > maxindex) {
int error = radix_tree_extend(root, max, shift);
if (error < 0)
return error;
shift = error;
child = root->rnode;
- if (order == shift)
- shift += RADIX_TREE_MAP_SHIFT;
}
while (shift > order) {
@@ -582,6 +578,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
return -ENOMEM;
child->shift = shift;
child->offset = offset;
+ child->count = 0;
child->parent = node;
rcu_assign_pointer(*slot, node_to_entry(child));
if (node)
@@ -595,31 +592,113 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
slot = &node->slots[offset];
}
+ if (nodep)
+ *nodep = node;
+ if (slotp)
+ *slotp = slot;
+ return 0;
+}
+
#ifdef CONFIG_RADIX_TREE_MULTIORDER
- /* Insert pointers to the canonical entry */
- if (order > shift) {
- unsigned i, n = 1 << (order - shift);
+/*
+ * Free any nodes below this node. The tree is presumed to not need
+ * shrinking, and any user data in the tree is presumed to not need a
+ * destructor called on it. If we need to add a destructor, we can
+ * add that functionality later. Note that we may not clear tags or
+ * slots from the tree as an RCU walker may still have a pointer into
+ * this subtree. We could replace the entries with RADIX_TREE_RETRY,
+ * but we'll still have to clear those in rcu_free.
+ */
+static void radix_tree_free_nodes(struct radix_tree_node *node)
+{
+ unsigned offset = 0;
+ struct radix_tree_node *child = entry_to_node(node);
+
+ for (;;) {
+ void *entry = child->slots[offset];
+ if (radix_tree_is_internal_node(entry) &&
+ !is_sibling_entry(child, entry)) {
+ child = entry_to_node(entry);
+ offset = 0;
+ continue;
+ }
+ offset++;
+ while (offset == RADIX_TREE_MAP_SIZE) {
+ struct radix_tree_node *old = child;
+ offset = child->offset + 1;
+ child = child->parent;
+ radix_tree_node_free(old);
+ if (old == entry_to_node(node))
+ return;
+ }
+ }
+}
+
+static inline int insert_entries(struct radix_tree_node *node, void **slot,
+ void *ptr, unsigned order, bool replace)
+{
+ struct radix_tree_node *child;
+ unsigned i, n, tag, offset, tags = 0;
+
+ if (node) {
+ n = 1 << (order - node->shift);
+ offset = get_slot_offset(node, slot);
+ } else {
+ n = 1;
+ offset = 0;
+ }
+
+ if (n > 1) {
offset = offset & ~(n - 1);
slot = &node->slots[offset];
- child = node_to_entry(slot);
- for (i = 0; i < n; i++) {
- if (slot[i])
+ }
+ child = node_to_entry(slot);
+
+ for (i = 0; i < n; i++) {
+ if (slot[i]) {
+ if (replace) {
+ node->count--;
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ if (tag_get(node, tag, offset + i))
+ tags |= 1 << tag;
+ } else
return -EEXIST;
}
+ }
- for (i = 1; i < n; i++) {
+ for (i = 0; i < n; i++) {
+ struct radix_tree_node *old = slot[i];
+ if (i) {
rcu_assign_pointer(slot[i], child);
- node->count++;
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ if (tags & (1 << tag))
+ tag_clear(node, tag, offset + i);
+ } else {
+ rcu_assign_pointer(slot[i], ptr);
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ if (tags & (1 << tag))
+ tag_set(node, tag, offset);
}
+ if (radix_tree_is_internal_node(old) &&
+ !is_sibling_entry(node, old))
+ radix_tree_free_nodes(old);
}
-#endif
-
- if (nodep)
- *nodep = node;
- if (slotp)
- *slotp = slot;
- return 0;
+ if (node)
+ node->count += n;
+ return n;
+}
+#else
+static inline int insert_entries(struct radix_tree_node *node, void **slot,
+ void *ptr, unsigned order, bool replace)
+{
+ if (*slot)
+ return -EEXIST;
+ rcu_assign_pointer(*slot, ptr);
+ if (node)
+ node->count++;
+ return 1;
}
+#endif
/**
* __radix_tree_insert - insert into a radix tree
@@ -642,13 +721,13 @@ int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
error = __radix_tree_create(root, index, order, &node, &slot);
if (error)
return error;
- if (*slot != NULL)
- return -EEXIST;
- rcu_assign_pointer(*slot, item);
+
+ error = insert_entries(node, slot, item, order, false);
+ if (error < 0)
+ return error;
if (node) {
unsigned offset = get_slot_offset(node, slot);
- node->count++;
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
BUG_ON(tag_get(node, 2, offset));
@@ -746,6 +825,26 @@ void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
}
EXPORT_SYMBOL(radix_tree_lookup);
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+int radix_tree_join(struct radix_tree_root *root, unsigned long index,
+ unsigned order, void *item)
+{
+ struct radix_tree_node *node;
+ void **slot;
+ int error;
+
+ BUG_ON(radix_tree_is_internal_node(item));
+
+ error = __radix_tree_create(root, index, order, &node, &slot);
+ if (!error)
+ error = insert_entries(node, slot, item, order, true);
+ if (error > 0)
+ error = 0;
+
+ return error;
+}
+#endif
+
/**
* radix_tree_tag_set - set a tag on a radix tree node
* @root: radix tree root
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 05d7bc4..4c66acc 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -325,6 +325,37 @@ void multiorder_tagged_iteration(void)
item_kill_tree(&tree);
}
+static void __multiorder_join(unsigned long index,
+ unsigned order1, unsigned order2)
+{
+ unsigned long loc;
+ void *item, *item2 = item_create(index + 1);
+ RADIX_TREE(tree, GFP_KERNEL);
+
+ 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);
+ if (loc == -1)
+ free(item);
+ item = radix_tree_lookup(&tree, index + 1);
+ assert(item == item2);
+ item_kill_tree(&tree);
+}
+
+static void multiorder_join(void)
+{
+ int i, j, idx;
+
+ for (idx = 0; idx < 1024; idx = idx * 2 + 3) {
+ for (i = 1; i < 15; i++) {
+ for (j = 0; j < i; j++) {
+ __multiorder_join(idx, i, j);
+ }
+ }
+ }
+}
+
void multiorder_checks(void)
{
int i;
@@ -342,4 +373,5 @@ void multiorder_checks(void)
multiorder_tag_tests();
multiorder_iteration();
multiorder_tagged_iteration();
+ multiorder_join();
}
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 17/29] radix-tree: Improve dump output |
| Message-ID | <sEh22-uC-15@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@infradead.org>
Print the indices of the entries as unsigned (instead of signed) integers
and print the parent node of each entry to help navigate around larger
trees where the layout is not quite so obvious. Print the indices
covered by a node. Rearrange the order of fields printed so the indices
and parents line up for each type of entry.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
lib/radix-tree.c | 50 +++++++++++++++++++++++++-------------------------
1 file changed, 25 insertions(+), 25 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 2c3fac4..09c5f1d 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -214,15 +214,29 @@ radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,
return RADIX_TREE_MAP_SIZE;
}
+/*
+ * The maximum index which can be stored in a radix tree
+ */
+static inline unsigned long shift_maxindex(unsigned int shift)
+{
+ return (RADIX_TREE_MAP_SIZE << shift) - 1;
+}
+
+static inline unsigned long node_maxindex(struct radix_tree_node *node)
+{
+ return shift_maxindex(node->shift);
+}
+
#ifndef __KERNEL__
static void dump_node(struct radix_tree_node *node, unsigned long index)
{
unsigned long i;
- pr_debug("radix node: %p offset %d tags %lx %lx %lx shift %d count %d parent %p\n",
- node, node->offset,
+ pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d\n",
+ node, node->offset, index, index | node_maxindex(node),
+ node->parent,
node->tags[0][0], node->tags[1][0], node->tags[2][0],
- node->shift, node->count, node->parent);
+ node->shift, node->count);
for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
unsigned long first = index | (i << node->shift);
@@ -231,16 +245,15 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
if (!entry)
continue;
if (entry == RADIX_TREE_RETRY) {
- pr_debug("radix retry offset %ld indices %ld-%ld\n",
- i, first, last);
- } else if (is_sibling_entry(node, entry)) {
- pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
- entry, i,
- *(void **)entry_to_node(entry),
- first, last);
+ pr_debug("radix retry offset %ld indices %lu-%lu parent %p\n",
+ i, first, last, node);
} else if (!radix_tree_is_internal_node(entry)) {
- pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
- entry, i, first, last);
+ pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p\n",
+ entry, i, first, last, node);
+ } else if (is_sibling_entry(node, entry)) {
+ pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p\n",
+ entry, i, first, last, node,
+ *(void **)entry_to_node(entry));
} else {
dump_node(entry_to_node(entry), first);
}
@@ -477,19 +490,6 @@ int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order)
return __radix_tree_preload(gfp_mask, nr_nodes);
}
-/*
- * The maximum index which can be stored in a radix tree
- */
-static inline unsigned long shift_maxindex(unsigned int shift)
-{
- return (RADIX_TREE_MAP_SIZE << shift) - 1;
-}
-
-static inline unsigned long node_maxindex(struct radix_tree_node *node)
-{
- return shift_maxindex(node->shift);
-}
-
static unsigned radix_tree_load_root(struct radix_tree_root *root,
struct radix_tree_node **nodep, unsigned long *maxindex)
{
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list |
| Message-ID | <sEh22-uC-29@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@infradead.org>
I want to be able to reference node->parent after freeing node.
Currently node->parent is in a union with rcu_head, so it is overwritten
when the node is put on the RCU list. We know that private_list is not
referenced after the node is freed, so it is safe for these two members
to share space.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
include/linux/radix-tree.h | 14 ++++----------
lib/radix-tree.c | 1 +
2 files changed, 5 insertions(+), 10 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 8ffb051..66fb8c0 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -88,18 +88,12 @@ struct radix_tree_node {
unsigned char shift; /* Bits remaining in each slot */
unsigned char offset; /* Slot offset in parent */
unsigned int count;
+ struct radix_tree_node *parent; /* Used when ascending tree */
+ void *private_data; /* For tree user */
union {
- struct {
- /* Used when ascending tree */
- struct radix_tree_node *parent;
- /* For tree user */
- void *private_data;
- };
- /* Used when freeing node */
- struct rcu_head rcu_head;
+ struct list_head private_list; /* For tree user */
+ struct rcu_head rcu_head; /* Used when freeing node */
};
- /* For tree user */
- struct list_head private_list;
void __rcu *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index e917c56..baf4ba1 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -325,6 +325,7 @@ static void radix_tree_node_rcu_free(struct rcu_head *head)
*/
memset(node->slots, 0, sizeof(node->slots));
memset(node->tags, 0, sizeof(node->tags));
+ INIT_LIST_HEAD(&node->private_list);
kmem_cache_free(radix_tree_node_cachep, node);
}
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail |
| Message-ID | <sEh22-uC-13@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
In order to test the preload code, it is necessary to fail GFP_ATOMIC
allocations, which requires defining GFP_KERNEL and GFP_ATOMIC properly.
Remove the obsolete __GFP_WAIT and copy the definitions of the __GFP
flags which are used from the kernel include files. We also need the
real definition of gfpflags_allow_blocking() to persuade the radix tree
to actually use its preallocated nodes.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
tools/testing/radix-tree/linux.c | 7 ++++++-
tools/testing/radix-tree/linux/gfp.h | 22 +++++++++++++++++++---
tools/testing/radix-tree/linux/slab.h | 5 -----
3 files changed, 25 insertions(+), 9 deletions(-)
diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index 1548237..3cfb04e 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -33,7 +33,12 @@ mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn,
void *kmem_cache_alloc(struct kmem_cache *cachep, int flags)
{
- void *ret = malloc(cachep->size);
+ void *ret;
+
+ if (flags & __GFP_NOWARN)
+ return NULL;
+
+ ret = malloc(cachep->size);
if (cachep->ctor)
cachep->ctor(ret);
uatomic_inc(&nr_allocated);
diff --git a/tools/testing/radix-tree/linux/gfp.h b/tools/testing/radix-tree/linux/gfp.h
index 5201b91..5b09b2c 100644
--- a/tools/testing/radix-tree/linux/gfp.h
+++ b/tools/testing/radix-tree/linux/gfp.h
@@ -3,8 +3,24 @@
#define __GFP_BITS_SHIFT 26
#define __GFP_BITS_MASK ((gfp_t)((1 << __GFP_BITS_SHIFT) - 1))
-#define __GFP_WAIT 1
-#define __GFP_ACCOUNT 0
-#define __GFP_NOWARN 0
+
+#define __GFP_HIGH 0x20u
+#define __GFP_IO 0x40u
+#define __GFP_FS 0x80u
+#define __GFP_NOWARN 0x200u
+#define __GFP_ATOMIC 0x80000u
+#define __GFP_ACCOUNT 0x100000u
+#define __GFP_DIRECT_RECLAIM 0x400000u
+#define __GFP_KSWAPD_RECLAIM 0x2000000u
+
+#define __GFP_RECLAIM (__GFP_DIRECT_RECLAIM|__GFP_KSWAPD_RECLAIM)
+
+#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
+#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
+
+static inline bool gfpflags_allow_blocking(const gfp_t gfp_flags)
+{
+ return !!(gfp_flags & __GFP_DIRECT_RECLAIM);
+}
#endif
diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h
index 6d5a347..452e2bf 100644
--- a/tools/testing/radix-tree/linux/slab.h
+++ b/tools/testing/radix-tree/linux/slab.h
@@ -7,11 +7,6 @@
#define SLAB_PANIC 2
#define SLAB_RECLAIM_ACCOUNT 0x00020000UL /* Objects are reclaimable */
-static inline int gfpflags_allow_blocking(gfp_t mask)
-{
- return 1;
-}
-
struct kmem_cache {
int size;
void (*ctor)(void *);
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals |
| Message-ID | <sEh22-uC-31@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <mawilcox@microsoft.com>
Add idr_get_cursor() / idr_set_cursor() APIs, and remove the rounding
up to IDR_SIZE.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
include/linux/idr.h | 26 ++++++++++++++++++++++++++
net/rxrpc/af_rxrpc.c | 11 ++++++-----
net/rxrpc/conn_client.c | 4 ++--
3 files changed, 34 insertions(+), 7 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 3639a28..1eb755f 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -56,6 +56,32 @@ struct idr {
#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
/**
+ * idr_get_cursor - Return the current position of the cyclic allocator
+ * @idr: idr handle
+ *
+ * The value returned is the value that will be next returned from
+ * idr_alloc_cyclic() if it is free (otherwise the search will start from
+ * this position).
+ */
+static inline unsigned int idr_get_cursor(struct idr *idr)
+{
+ return READ_ONCE(idr->cur);
+}
+
+/**
+ * idr_set_cursor - Set the current position of the cyclic allocator
+ * @idr: idr handle
+ * @val: new position
+ *
+ * The next call to idr_alloc_cyclic() will return @val if it is free
+ * (otherwise the search will start from this position).
+ */
+static inline void idr_set_cursor(struct idr *idr, unsigned int val)
+{
+ WRITE_ONCE(idr->cur, val);
+}
+
+/**
* DOC: idr sync
* idr synchronization (stolen from radix-tree.h)
*
diff --git a/net/rxrpc/af_rxrpc.c b/net/rxrpc/af_rxrpc.c
index 2d59c9b..5f63f6d 100644
--- a/net/rxrpc/af_rxrpc.c
+++ b/net/rxrpc/af_rxrpc.c
@@ -762,16 +762,17 @@ static const struct net_proto_family rxrpc_family_ops = {
static int __init af_rxrpc_init(void)
{
int ret = -1;
+ unsigned int tmp;
BUILD_BUG_ON(sizeof(struct rxrpc_skb_priv) > FIELD_SIZEOF(struct sk_buff, cb));
get_random_bytes(&rxrpc_epoch, sizeof(rxrpc_epoch));
rxrpc_epoch |= RXRPC_RANDOM_EPOCH;
- get_random_bytes(&rxrpc_client_conn_ids.cur,
- sizeof(rxrpc_client_conn_ids.cur));
- rxrpc_client_conn_ids.cur &= 0x3fffffff;
- if (rxrpc_client_conn_ids.cur == 0)
- rxrpc_client_conn_ids.cur = 1;
+ get_random_bytes(&tmp, sizeof(tmp));
+ tmp &= 0x3fffffff;
+ if (tmp == 0)
+ tmp = 1;
+ idr_set_cursor(&rxrpc_client_conn_ids, tmp);
ret = -ENOMEM;
rxrpc_call_jar = kmem_cache_create(
diff --git a/net/rxrpc/conn_client.c b/net/rxrpc/conn_client.c
index 60ef960..9706f60 100644
--- a/net/rxrpc/conn_client.c
+++ b/net/rxrpc/conn_client.c
@@ -263,12 +263,12 @@ static bool rxrpc_may_reuse_conn(struct rxrpc_connection *conn)
* times the maximum number of client conns away from the current
* allocation point to try and keep the IDs concentrated.
*/
- id_cursor = READ_ONCE(rxrpc_client_conn_ids.cur);
+ id_cursor = idr_get_cursor(&rxrpc_client_conn_ids);
id = conn->proto.cid >> RXRPC_CIDSHIFT;
distance = id - id_cursor;
if (distance < 0)
distance = -distance;
- limit = round_up(rxrpc_max_client_connections, IDR_SIZE) * 4;
+ limit = rxrpc_max_client_connections * 4;
if (distance > limit)
goto mark_dont_reuse;
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail |
| Message-ID | <sEh22-uC-35@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
In order to test the preload code, it is necessary to fail GFP_ATOMIC
allocations, which requires defining GFP_KERNEL and GFP_ATOMIC properly.
Remove the obsolete __GFP_WAIT and copy the definitions of the __GFP
flags which are used from the kernel include files. We also need the
real definition of gfpflags_allow_blocking() to persuade the radix tree
to actually use its preallocated nodes.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
tools/testing/radix-tree/linux.c | 7 ++++++-
tools/testing/radix-tree/linux/gfp.h | 22 +++++++++++++++++++---
tools/testing/radix-tree/linux/slab.h | 5 -----
3 files changed, 25 insertions(+), 9 deletions(-)
diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index 1548237..3cfb04e 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -33,7 +33,12 @@ mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn,
void *kmem_cache_alloc(struct kmem_cache *cachep, int flags)
{
- void *ret = malloc(cachep->size);
+ void *ret;
+
+ if (flags & __GFP_NOWARN)
+ return NULL;
+
+ ret = malloc(cachep->size);
if (cachep->ctor)
cachep->ctor(ret);
uatomic_inc(&nr_allocated);
diff --git a/tools/testing/radix-tree/linux/gfp.h b/tools/testing/radix-tree/linux/gfp.h
index 5201b91..5b09b2c 100644
--- a/tools/testing/radix-tree/linux/gfp.h
+++ b/tools/testing/radix-tree/linux/gfp.h
@@ -3,8 +3,24 @@
#define __GFP_BITS_SHIFT 26
#define __GFP_BITS_MASK ((gfp_t)((1 << __GFP_BITS_SHIFT) - 1))
-#define __GFP_WAIT 1
-#define __GFP_ACCOUNT 0
-#define __GFP_NOWARN 0
+
+#define __GFP_HIGH 0x20u
+#define __GFP_IO 0x40u
+#define __GFP_FS 0x80u
+#define __GFP_NOWARN 0x200u
+#define __GFP_ATOMIC 0x80000u
+#define __GFP_ACCOUNT 0x100000u
+#define __GFP_DIRECT_RECLAIM 0x400000u
+#define __GFP_KSWAPD_RECLAIM 0x2000000u
+
+#define __GFP_RECLAIM (__GFP_DIRECT_RECLAIM|__GFP_KSWAPD_RECLAIM)
+
+#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
+#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
+
+static inline bool gfpflags_allow_blocking(const gfp_t gfp_flags)
+{
+ return !!(gfp_flags & __GFP_DIRECT_RECLAIM);
+}
#endif
diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h
index 6d5a347..452e2bf 100644
--- a/tools/testing/radix-tree/linux/slab.h
+++ b/tools/testing/radix-tree/linux/slab.h
@@ -7,11 +7,6 @@
#define SLAB_PANIC 2
#define SLAB_RECLAIM_ACCOUNT 0x00020000UL /* Objects are reclaimable */
-static inline int gfpflags_allow_blocking(gfp_t mask)
-{
- return 1;
-}
-
struct kmem_cache {
int size;
void (*ctor)(void *);
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() |
| Message-ID | <sEh22-uC-33@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <mawilcox@microsoft.com> We drop the lock which protects the radix tree, so we must call radix_tree_iter_next() in order to avoid a modification to the tree invalidating the iterator state. Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> --- fs/btrfs/tests/btrfs-tests.c | 1 + 1 file changed, 1 insertion(+) diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c index bf62ad9..73076a0 100644 --- a/fs/btrfs/tests/btrfs-tests.c +++ b/fs/btrfs/tests/btrfs-tests.c @@ -162,6 +162,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info) slot = radix_tree_iter_retry(&iter); continue; } + slot = radix_tree_iter_next(&iter); spin_unlock(&fs_info->buffer_lock); free_extent_buffer_stale(eb); spin_lock(&fs_info->buffer_lock); -- 2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 23/29] idr: Add ida_is_empty |
| Message-ID | <sEh22-uC-19@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
Two of the USB Gadgets were poking around in the internals of struct ida
in order to determine if it is empty. Add the appropriate abstraction.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
drivers/usb/gadget/function/f_hid.c | 6 +++---
drivers/usb/gadget/function/f_printer.c | 6 +++---
include/linux/idr.h | 5 +++++
3 files changed, 11 insertions(+), 6 deletions(-)
diff --git a/drivers/usb/gadget/function/f_hid.c b/drivers/usb/gadget/function/f_hid.c
index e2966f8..b9b04fc 100644
--- a/drivers/usb/gadget/function/f_hid.c
+++ b/drivers/usb/gadget/function/f_hid.c
@@ -840,7 +840,7 @@ static void hidg_free_inst(struct usb_function_instance *f)
mutex_lock(&hidg_ida_lock);
hidg_put_minor(opts->minor);
- if (idr_is_empty(&hidg_ida.idr))
+ if (ida_is_empty(&hidg_ida))
ghid_cleanup();
mutex_unlock(&hidg_ida_lock);
@@ -866,7 +866,7 @@ static struct usb_function_instance *hidg_alloc_inst(void)
mutex_lock(&hidg_ida_lock);
- if (idr_is_empty(&hidg_ida.idr)) {
+ if (ida_is_empty(&hidg_ida)) {
status = ghid_setup(NULL, HIDG_MINORS);
if (status) {
ret = ERR_PTR(status);
@@ -879,7 +879,7 @@ static struct usb_function_instance *hidg_alloc_inst(void)
if (opts->minor < 0) {
ret = ERR_PTR(opts->minor);
kfree(opts);
- if (idr_is_empty(&hidg_ida.idr))
+ if (ida_is_empty(&hidg_ida))
ghid_cleanup();
goto unlock;
}
diff --git a/drivers/usb/gadget/function/f_printer.c b/drivers/usb/gadget/function/f_printer.c
index 0de36cd..8054da9 100644
--- a/drivers/usb/gadget/function/f_printer.c
+++ b/drivers/usb/gadget/function/f_printer.c
@@ -1265,7 +1265,7 @@ static void gprinter_free_inst(struct usb_function_instance *f)
mutex_lock(&printer_ida_lock);
gprinter_put_minor(opts->minor);
- if (idr_is_empty(&printer_ida.idr))
+ if (ida_is_empty(&printer_ida))
gprinter_cleanup();
mutex_unlock(&printer_ida_lock);
@@ -1289,7 +1289,7 @@ static struct usb_function_instance *gprinter_alloc_inst(void)
mutex_lock(&printer_ida_lock);
- if (idr_is_empty(&printer_ida.idr)) {
+ if (ida_is_empty(&printer_ida)) {
status = gprinter_setup(PRINTER_MINORS);
if (status) {
ret = ERR_PTR(status);
@@ -1302,7 +1302,7 @@ static struct usb_function_instance *gprinter_alloc_inst(void)
if (opts->minor < 0) {
ret = ERR_PTR(opts->minor);
kfree(opts);
- if (idr_is_empty(&printer_ida.idr))
+ if (ida_is_empty(&printer_ida))
gprinter_cleanup();
goto unlock;
}
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 083d61e..3639a28 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -195,6 +195,11 @@ static inline int ida_get_new(struct ida *ida, int *p_id)
return ida_get_new_above(ida, 0, p_id);
}
+static inline bool ida_is_empty(struct ida *ida)
+{
+ return idr_is_empty(&ida->idr);
+}
+
void __init idr_init_cache(void);
#endif /* __IDR_H__ */
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-11-18 13:00 +0100 |
| Subject | Re: [PATCH 23/29] idr: Add ida_is_empty |
| Message-ID | <sEPZM-6BF-23@gated-at.bofh.it> |
| In reply to | #1523920 |
On Thu, Nov 17, 2016 at 3:16 AM, Matthew Wilcox
<mawilcox@linuxonhyperv.com> wrote:
> From: Matthew Wilcox <willy@linux.intel.com>
>
> Two of the USB Gadgets were poking around in the internals of struct ida
> in order to determine if it is empty. Add the appropriate abstraction.
Looks good. This could be applied separately.
>
> Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
> ---
> drivers/usb/gadget/function/f_hid.c | 6 +++---
> drivers/usb/gadget/function/f_printer.c | 6 +++---
> include/linux/idr.h | 5 +++++
> 3 files changed, 11 insertions(+), 6 deletions(-)
>
> diff --git a/drivers/usb/gadget/function/f_hid.c b/drivers/usb/gadget/function/f_hid.c
> index e2966f8..b9b04fc 100644
> --- a/drivers/usb/gadget/function/f_hid.c
> +++ b/drivers/usb/gadget/function/f_hid.c
> @@ -840,7 +840,7 @@ static void hidg_free_inst(struct usb_function_instance *f)
> mutex_lock(&hidg_ida_lock);
>
> hidg_put_minor(opts->minor);
> - if (idr_is_empty(&hidg_ida.idr))
> + if (ida_is_empty(&hidg_ida))
> ghid_cleanup();
>
> mutex_unlock(&hidg_ida_lock);
> @@ -866,7 +866,7 @@ static struct usb_function_instance *hidg_alloc_inst(void)
>
> mutex_lock(&hidg_ida_lock);
>
> - if (idr_is_empty(&hidg_ida.idr)) {
> + if (ida_is_empty(&hidg_ida)) {
> status = ghid_setup(NULL, HIDG_MINORS);
> if (status) {
> ret = ERR_PTR(status);
> @@ -879,7 +879,7 @@ static struct usb_function_instance *hidg_alloc_inst(void)
> if (opts->minor < 0) {
> ret = ERR_PTR(opts->minor);
> kfree(opts);
> - if (idr_is_empty(&hidg_ida.idr))
> + if (ida_is_empty(&hidg_ida))
> ghid_cleanup();
> goto unlock;
> }
> diff --git a/drivers/usb/gadget/function/f_printer.c b/drivers/usb/gadget/function/f_printer.c
> index 0de36cd..8054da9 100644
> --- a/drivers/usb/gadget/function/f_printer.c
> +++ b/drivers/usb/gadget/function/f_printer.c
> @@ -1265,7 +1265,7 @@ static void gprinter_free_inst(struct usb_function_instance *f)
> mutex_lock(&printer_ida_lock);
>
> gprinter_put_minor(opts->minor);
> - if (idr_is_empty(&printer_ida.idr))
> + if (ida_is_empty(&printer_ida))
> gprinter_cleanup();
>
> mutex_unlock(&printer_ida_lock);
> @@ -1289,7 +1289,7 @@ static struct usb_function_instance *gprinter_alloc_inst(void)
>
> mutex_lock(&printer_ida_lock);
>
> - if (idr_is_empty(&printer_ida.idr)) {
> + if (ida_is_empty(&printer_ida)) {
> status = gprinter_setup(PRINTER_MINORS);
> if (status) {
> ret = ERR_PTR(status);
> @@ -1302,7 +1302,7 @@ static struct usb_function_instance *gprinter_alloc_inst(void)
> if (opts->minor < 0) {
> ret = ERR_PTR(opts->minor);
> kfree(opts);
> - if (idr_is_empty(&printer_ida.idr))
> + if (ida_is_empty(&printer_ida))
> gprinter_cleanup();
> goto unlock;
> }
> diff --git a/include/linux/idr.h b/include/linux/idr.h
> index 083d61e..3639a28 100644
> --- a/include/linux/idr.h
> +++ b/include/linux/idr.h
> @@ -195,6 +195,11 @@ static inline int ida_get_new(struct ida *ida, int *p_id)
> return ida_get_new_above(ida, 0, p_id);
> }
>
> +static inline bool ida_is_empty(struct ida *ida)
> +{
> + return idr_is_empty(&ida->idr);
> +}
> +
> void __init idr_init_cache(void);
>
> #endif /* __IDR_H__ */
> --
> 2.10.2
>
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful |
| Message-ID | <sEh22-uC-23@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
Since this function is specialised to the radix tree, pass in the node
and tag to calculate the address of the bitmap in radix_tree_find_next_bit()
instead of the caller. Likewise, there is no need to pass in the size of
the bitmap.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
lib/radix-tree.c | 17 +++++++----------
1 file changed, 7 insertions(+), 10 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index bf1303f..2c3fac4 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -191,13 +191,12 @@ static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
* Returns next bit offset, or size if nothing found.
*/
static __always_inline unsigned long
-radix_tree_find_next_bit(const unsigned long *addr,
- unsigned long size, unsigned long offset)
+radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,
+ unsigned long offset)
{
- if (!__builtin_constant_p(size))
- return find_next_bit(addr, size, offset);
+ const unsigned long *addr = node->tags[tag];
- if (offset < size) {
+ if (offset < RADIX_TREE_MAP_SIZE) {
unsigned long tmp;
addr += offset / BITS_PER_LONG;
@@ -205,14 +204,14 @@ radix_tree_find_next_bit(const unsigned long *addr,
if (tmp)
return __ffs(tmp) + offset;
offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
- while (offset < size) {
+ while (offset < RADIX_TREE_MAP_SIZE) {
tmp = *++addr;
if (tmp)
return __ffs(tmp) + offset;
offset += BITS_PER_LONG;
}
}
- return size;
+ return RADIX_TREE_MAP_SIZE;
}
#ifndef __KERNEL__
@@ -1197,9 +1196,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
return NULL;
if (flags & RADIX_TREE_ITER_TAGGED)
- offset = radix_tree_find_next_bit(
- node->tags[tag],
- RADIX_TREE_MAP_SIZE,
+ offset = radix_tree_find_next_bit(node, tag,
offset + 1);
else
while (++offset < RADIX_TREE_MAP_SIZE) {
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 20/29] radix tree: Improve multiorder iterators |
| Message-ID | <sEh22-uC-39@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <mawilcox@microsoft.com>
This fixes several interlinked problems with the iterators in the
presence of multiorder entries.
1. radix_tree_iter_next() would only advance by one slot, which would
result in the iterators returning the same entry more than once if there
were sibling entries.
2. radix_tree_next_slot() could return an internal pointer instead of
a user pointer if a tagged multiorder entry was immediately followed by
an entry of lower order.
3. radix_tree_next_slot() expanded to a lot more code than it used to
when multiorder support was compiled in. And I wasn't comfortable with
entry_to_node() being in a header file.
Fixing radix_tree_iter_next() for the presence of sibling entries
necessarily involves examining the contents of the radix tree, so we now
need to pass 'slot' to radix_tree_iter_next(), and we need to change the
calling convention so it is called *before* dropping the lock which
protects the tree. Fortunately, unconverted code won't compile.
radix_tree_next_slot() becomes closer to how it looked before multiorder
support was introduced. It only checks to see if the next entry in the
chunk is a sibling entry or a pointer to a node; this should be rare
enough that handling this case out of line is not a performance impact
(and such impact is amortised by the fact that the entry we just
processed was a multiorder entry). Also, radix_tree_next_slot() used
to force a new chunk lookup for untagged entries, which is more
expensive than the out of line sibling entry skipping.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
fs/btrfs/tests/btrfs-tests.c | 2 +-
include/linux/radix-tree.h | 63 ++++++++------------
lib/radix-tree.c | 94 ++++++++++++++++++++++++++++++
mm/khugepaged.c | 2 +-
mm/shmem.c | 6 +-
tools/testing/radix-tree/iteration_check.c | 4 +-
tools/testing/radix-tree/multiorder.c | 12 ++++
tools/testing/radix-tree/regression3.c | 6 +-
tools/testing/radix-tree/test.h | 1 +
9 files changed, 142 insertions(+), 48 deletions(-)
diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
index 73076a0..6d3457a 100644
--- a/fs/btrfs/tests/btrfs-tests.c
+++ b/fs/btrfs/tests/btrfs-tests.c
@@ -162,7 +162,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
slot = radix_tree_iter_retry(&iter);
continue;
}
- slot = radix_tree_iter_next(&iter);
+ slot = radix_tree_iter_next(slot, &iter);
spin_unlock(&fs_info->buffer_lock);
free_extent_buffer_stale(eb);
spin_lock(&fs_info->buffer_lock);
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 66fb8c0..36c6175 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -424,15 +424,10 @@ __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
*
* If the iterator needs to release then reacquire a lock, the chunk may
* have been invalidated by an insertion or deletion. Call this function
- * to continue the iteration from the next index.
+ * before releasing the lock to continue the iteration from the next index.
*/
-static inline __must_check
-void **radix_tree_iter_next(struct radix_tree_iter *iter)
-{
- iter->next_index = __radix_tree_iter_add(iter, 1);
- iter->tags = 0;
- return NULL;
-}
+void **__must_check radix_tree_iter_next(void **slot,
+ struct radix_tree_iter *iter);
/**
* radix_tree_chunk_size - get current chunk size
@@ -446,10 +441,17 @@ radix_tree_chunk_size(struct radix_tree_iter *iter)
return (iter->next_index - iter->index) >> iter_shift(iter);
}
-static inline struct radix_tree_node *entry_to_node(void *ptr)
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
+ unsigned flags);
+#else
+/* Can't happen without sibling entries, but the compiler can't tell that */
+static inline void ** __radix_tree_next_slot(void **slot,
+ struct radix_tree_iter *iter, unsigned flags)
{
- return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
+ return slot;
}
+#endif
/**
* radix_tree_next_slot - find next slot in chunk
@@ -474,51 +476,31 @@ static __always_inline void **
radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
{
if (flags & RADIX_TREE_ITER_TAGGED) {
- void *canon = slot;
-
iter->tags >>= 1;
if (unlikely(!iter->tags))
return NULL;
- while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_internal_node(slot[1])) {
- if (entry_to_node(slot[1]) == canon) {
- iter->tags >>= 1;
- iter->index = __radix_tree_iter_add(iter, 1);
- slot++;
- continue;
- }
- iter->next_index = __radix_tree_iter_add(iter, 1);
- return NULL;
- }
if (likely(iter->tags & 1ul)) {
iter->index = __radix_tree_iter_add(iter, 1);
- return slot + 1;
+ slot++;
+ goto found;
}
if (!(flags & RADIX_TREE_ITER_CONTIG)) {
unsigned offset = __ffs(iter->tags);
- iter->tags >>= offset;
- iter->index = __radix_tree_iter_add(iter, offset + 1);
- return slot + offset + 1;
+ iter->tags >>= offset++;
+ iter->index = __radix_tree_iter_add(iter, offset);
+ slot += offset;
+ goto found;
}
} else {
long count = radix_tree_chunk_size(iter);
- void *canon = slot;
while (--count > 0) {
slot++;
iter->index = __radix_tree_iter_add(iter, 1);
- if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_internal_node(*slot)) {
- if (entry_to_node(*slot) == canon)
- continue;
- iter->next_index = iter->index;
- break;
- }
-
if (likely(*slot))
- return slot;
+ goto found;
if (flags & RADIX_TREE_ITER_CONTIG) {
/* forbid switching to the next chunk */
iter->next_index = 0;
@@ -527,6 +509,11 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
}
}
return NULL;
+
+ found:
+ if (unlikely(radix_tree_is_internal_node(*slot)))
+ return __radix_tree_next_slot(slot, iter, flags);
+ return slot;
}
/**
@@ -577,6 +564,6 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
slot || (slot = radix_tree_next_chunk(root, iter, \
RADIX_TREE_ITER_TAGGED | tag)) ; \
slot = radix_tree_next_slot(slot, iter, \
- RADIX_TREE_ITER_TAGGED))
+ RADIX_TREE_ITER_TAGGED | tag))
#endif /* _LINUX_RADIX_TREE_H */
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 09c5f1d..27b53ef 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -69,6 +69,11 @@ struct radix_tree_preload {
};
static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
+static inline struct radix_tree_node *entry_to_node(void *ptr)
+{
+ return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
+}
+
static inline void *node_to_entry(void *ptr)
{
return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
@@ -1138,6 +1143,95 @@ static inline void __set_iter_shift(struct radix_tree_iter *iter,
#endif
}
+static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
+ void **slot, struct radix_tree_iter *iter)
+{
+ void *sib = node_to_entry(slot - 1);
+
+ while (iter->index < iter->next_index) {
+ *nodep = rcu_dereference_raw(*slot);
+ if (*nodep && *nodep != sib)
+ return slot;
+ slot++;
+ iter->index = __radix_tree_iter_add(iter, 1);
+ iter->tags >>= 1;
+ }
+
+ *nodep = NULL;
+ return NULL;
+}
+
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
+ unsigned flags)
+{
+ unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
+ struct radix_tree_node *node = rcu_dereference_raw(*slot);
+
+ slot = __radix_tree_iter_next(&node, slot, iter);
+
+ while (radix_tree_is_internal_node(node)) {
+ unsigned offset;
+
+ if (node == RADIX_TREE_RETRY)
+ return slot;
+ node = entry_to_node(node);
+
+ if (flags & RADIX_TREE_ITER_TAGGED) {
+ unsigned tag_long, tag_bit;
+ offset = radix_tree_find_next_bit(node, tag, 0);
+ if (offset == RADIX_TREE_MAP_SIZE)
+ return NULL;
+ slot = &node->slots[offset];
+
+ tag_long = offset / BITS_PER_LONG;
+ tag_bit = offset % BITS_PER_LONG;
+ iter->tags = node->tags[tag][tag_long] >> tag_bit;
+ BUG_ON(iter->tags >= (RADIX_TREE_MAP_SIZE * 2));
+ node = rcu_dereference_raw(*slot);
+ } else {
+ offset = 0;
+ slot = &node->slots[0];
+ for (;;) {
+ node = rcu_dereference_raw(*slot);
+ if (node)
+ break;
+ slot++;
+ offset++;
+ if (offset == RADIX_TREE_MAP_SIZE)
+ return NULL;
+ }
+ }
+ if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0))
+ goto none;
+ iter->shift -= RADIX_TREE_MAP_SHIFT;
+ iter->index = __radix_tree_iter_add(iter, offset);
+ iter->next_index = (iter->index | shift_maxindex(iter->shift)) +
+ 1;
+ }
+
+ return slot;
+ none:
+ iter->next_index = 0;
+ return NULL;
+}
+EXPORT_SYMBOL(__radix_tree_next_slot);
+#endif
+
+void **radix_tree_iter_next(void **slot, struct radix_tree_iter *iter)
+{
+ struct radix_tree_node *node;
+
+ slot++;
+ iter->index = __radix_tree_iter_add(iter, 1);
+ node = rcu_dereference_raw(*slot);
+ __radix_tree_iter_next(&node, slot, iter);
+ iter->next_index = iter->index;
+ iter->tags = 0;
+ return NULL;
+}
+EXPORT_SYMBOL(radix_tree_iter_next);
+
/**
* radix_tree_next_chunk - find next chunk of slots for iteration
*
diff --git a/mm/khugepaged.c b/mm/khugepaged.c
index 728d779..46155d1 100644
--- a/mm/khugepaged.c
+++ b/mm/khugepaged.c
@@ -1614,8 +1614,8 @@ static void khugepaged_scan_shmem(struct mm_struct *mm,
present++;
if (need_resched()) {
+ slot = radix_tree_iter_next(slot, &iter);
cond_resched_rcu();
- slot = radix_tree_iter_next(&iter);
}
}
rcu_read_unlock();
diff --git a/mm/shmem.c b/mm/shmem.c
index 166ebf5..0b3fe33 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -658,8 +658,8 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
swapped++;
if (need_resched()) {
+ slot = radix_tree_iter_next(slot, &iter);
cond_resched_rcu();
- slot = radix_tree_iter_next(&iter);
}
}
@@ -2434,8 +2434,8 @@ static void shmem_tag_pins(struct address_space *mapping)
}
if (need_resched()) {
+ slot = radix_tree_iter_next(slot, &iter);
cond_resched_rcu();
- slot = radix_tree_iter_next(&iter);
}
}
rcu_read_unlock();
@@ -2504,8 +2504,8 @@ static int shmem_wait_for_pins(struct address_space *mapping)
spin_unlock_irq(&mapping->tree_lock);
continue_resched:
if (need_resched()) {
+ slot = radix_tree_iter_next(slot, &iter);
cond_resched_rcu();
- slot = radix_tree_iter_next(&iter);
}
}
rcu_read_unlock();
diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c
index df71cb8..6eca4c2 100644
--- a/tools/testing/radix-tree/iteration_check.c
+++ b/tools/testing/radix-tree/iteration_check.c
@@ -79,7 +79,7 @@ static void *tagged_iteration_fn(void *arg)
}
if (rand_r(&seeds[0]) % 50 == 0) {
- slot = radix_tree_iter_next(&iter);
+ slot = radix_tree_iter_next(slot, &iter);
rcu_read_unlock();
rcu_barrier();
rcu_read_lock();
@@ -127,7 +127,7 @@ static void *untagged_iteration_fn(void *arg)
}
if (rand_r(&seeds[1]) % 50 == 0) {
- slot = radix_tree_iter_next(&iter);
+ slot = radix_tree_iter_next(slot, &iter);
rcu_read_unlock();
rcu_barrier();
rcu_read_lock();
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 25e0463..588209a 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -232,10 +232,14 @@ void multiorder_iteration(void)
int height = order[i] / RADIX_TREE_MAP_SHIFT;
int shift = height * RADIX_TREE_MAP_SHIFT;
int mask = (1 << order[i]) - 1;
+ struct item *item = *slot;
assert(iter.index >= (index[i] &~ mask));
assert(iter.index <= (index[i] | mask));
assert(iter.shift == shift);
+ assert(!radix_tree_is_internal_node(item));
+ assert(item->index >= (index[i] &~ mask));
+ assert(item->index <= (index[i] | mask));
i++;
}
}
@@ -279,12 +283,16 @@ void multiorder_tagged_iteration(void)
}
radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
+ struct item *item = *slot;
for (k = i; index[k] < tag_index[i]; k++)
;
mask = (1 << order[k]) - 1;
assert(iter.index >= (tag_index[i] &~ mask));
assert(iter.index <= (tag_index[i] | mask));
+ assert(!radix_tree_is_internal_node(item));
+ assert(item->index >= (tag_index[i] &~ mask));
+ assert(item->index <= (tag_index[i] | mask));
i++;
}
}
@@ -303,12 +311,16 @@ void multiorder_tagged_iteration(void)
}
radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
+ struct item *item = *slot;
for (k = i; index[k] < tag_index[i]; k++)
;
mask = (1 << order[k]) - 1;
assert(iter.index >= (tag_index[i] &~ mask));
assert(iter.index <= (tag_index[i] | mask));
+ assert(!radix_tree_is_internal_node(item));
+ assert(item->index >= (tag_index[i] &~ mask));
+ assert(item->index <= (tag_index[i] | mask));
i++;
}
}
diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c
index 1f06ed7..4d28eeb 100644
--- a/tools/testing/radix-tree/regression3.c
+++ b/tools/testing/radix-tree/regression3.c
@@ -88,7 +88,7 @@ void regression3_test(void)
printf("slot %ld %p\n", iter.index, *slot);
if (!iter.index) {
printf("next at %ld\n", iter.index);
- slot = radix_tree_iter_next(&iter);
+ slot = radix_tree_iter_next(slot, &iter);
}
}
@@ -96,7 +96,7 @@ void regression3_test(void)
printf("contig %ld %p\n", iter.index, *slot);
if (!iter.index) {
printf("next at %ld\n", iter.index);
- slot = radix_tree_iter_next(&iter);
+ slot = radix_tree_iter_next(slot, &iter);
}
}
@@ -106,7 +106,7 @@ void regression3_test(void)
printf("tagged %ld %p\n", iter.index, *slot);
if (!iter.index) {
printf("next at %ld\n", iter.index);
- slot = radix_tree_iter_next(&iter);
+ slot = radix_tree_iter_next(slot, &iter);
}
}
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 33d2b6b..b678f13 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -43,6 +43,7 @@ void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag);
extern int nr_allocated;
/* Normally private parts of lib/radix-tree.c */
+struct radix_tree_node *entry_to_node(void *ptr);
void radix_tree_dump(struct radix_tree_root *root);
int root_tag_get(struct radix_tree_root *root, unsigned int tag);
unsigned long node_maxindex(struct radix_tree_node *);
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-11-18 12:50 +0100 |
| Subject | Re: [PATCH 20/29] radix tree: Improve multiorder iterators |
| Message-ID | <sEPQ5-6yx-5@gated-at.bofh.it> |
| In reply to | #1523922 |
On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox
<mawilcox@linuxonhyperv.com> wrote:
> From: Matthew Wilcox <mawilcox@microsoft.com>
This code still looks overengineered for me.
>
> This fixes several interlinked problems with the iterators in the
> presence of multiorder entries.
>
> 1. radix_tree_iter_next() would only advance by one slot, which would
> result in the iterators returning the same entry more than once if there
> were sibling entries.
Is this a problem? Do we have users who cannot evalate length of entry
by looking into it head?
>
> 2. radix_tree_next_slot() could return an internal pointer instead of
> a user pointer if a tagged multiorder entry was immediately followed by
> an entry of lower order.
>
> 3. radix_tree_next_slot() expanded to a lot more code than it used to
> when multiorder support was compiled in. And I wasn't comfortable with
> entry_to_node() being in a header file.
>
> Fixing radix_tree_iter_next() for the presence of sibling entries
> necessarily involves examining the contents of the radix tree, so we now
> need to pass 'slot' to radix_tree_iter_next(), and we need to change the
> calling convention so it is called *before* dropping the lock which
> protects the tree. Fortunately, unconverted code won't compile.
>
> radix_tree_next_slot() becomes closer to how it looked before multiorder
> support was introduced. It only checks to see if the next entry in the
> chunk is a sibling entry or a pointer to a node; this should be rare
> enough that handling this case out of line is not a performance impact
> (and such impact is amortised by the fact that the entry we just
> processed was a multiorder entry). Also, radix_tree_next_slot() used
> to force a new chunk lookup for untagged entries, which is more
> expensive than the out of line sibling entry
>
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> ---
> fs/btrfs/tests/btrfs-tests.c | 2 +-
> include/linux/radix-tree.h | 63 ++++++++------------
> lib/radix-tree.c | 94 ++++++++++++++++++++++++++++++
> mm/khugepaged.c | 2 +-
> mm/shmem.c | 6 +-
> tools/testing/radix-tree/iteration_check.c | 4 +-
> tools/testing/radix-tree/multiorder.c | 12 ++++
> tools/testing/radix-tree/regression3.c | 6 +-
> tools/testing/radix-tree/test.h | 1 +
> 9 files changed, 142 insertions(+), 48 deletions(-)
>
> diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
> index 73076a0..6d3457a 100644
> --- a/fs/btrfs/tests/btrfs-tests.c
> +++ b/fs/btrfs/tests/btrfs-tests.c
> @@ -162,7 +162,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
> slot = radix_tree_iter_retry(&iter);
> continue;
> }
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> spin_unlock(&fs_info->buffer_lock);
> free_extent_buffer_stale(eb);
> spin_lock(&fs_info->buffer_lock);
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 66fb8c0..36c6175 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -424,15 +424,10 @@ __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
> *
> * If the iterator needs to release then reacquire a lock, the chunk may
> * have been invalidated by an insertion or deletion. Call this function
> - * to continue the iteration from the next index.
> + * before releasing the lock to continue the iteration from the next index.
> */
> -static inline __must_check
> -void **radix_tree_iter_next(struct radix_tree_iter *iter)
> -{
> - iter->next_index = __radix_tree_iter_add(iter, 1);
> - iter->tags = 0;
> - return NULL;
> -}
> +void **__must_check radix_tree_iter_next(void **slot,
> + struct radix_tree_iter *iter);
>
> /**
> * radix_tree_chunk_size - get current chunk size
> @@ -446,10 +441,17 @@ radix_tree_chunk_size(struct radix_tree_iter *iter)
> return (iter->next_index - iter->index) >> iter_shift(iter);
> }
>
> -static inline struct radix_tree_node *entry_to_node(void *ptr)
> +#ifdef CONFIG_RADIX_TREE_MULTIORDER
> +void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> + unsigned flags);
> +#else
> +/* Can't happen without sibling entries, but the compiler can't tell that */
> +static inline void ** __radix_tree_next_slot(void **slot,
> + struct radix_tree_iter *iter, unsigned flags)
> {
> - return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
> + return slot;
> }
> +#endif
>
> /**
> * radix_tree_next_slot - find next slot in chunk
> @@ -474,51 +476,31 @@ static __always_inline void **
> radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> {
> if (flags & RADIX_TREE_ITER_TAGGED) {
> - void *canon = slot;
> -
> iter->tags >>= 1;
> if (unlikely(!iter->tags))
> return NULL;
> - while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
> - radix_tree_is_internal_node(slot[1])) {
> - if (entry_to_node(slot[1]) == canon) {
> - iter->tags >>= 1;
> - iter->index = __radix_tree_iter_add(iter, 1);
> - slot++;
> - continue;
> - }
> - iter->next_index = __radix_tree_iter_add(iter, 1);
> - return NULL;
> - }
> if (likely(iter->tags & 1ul)) {
> iter->index = __radix_tree_iter_add(iter, 1);
> - return slot + 1;
> + slot++;
> + goto found;
> }
> if (!(flags & RADIX_TREE_ITER_CONTIG)) {
> unsigned offset = __ffs(iter->tags);
>
> - iter->tags >>= offset;
> - iter->index = __radix_tree_iter_add(iter, offset + 1);
> - return slot + offset + 1;
> + iter->tags >>= offset++;
> + iter->index = __radix_tree_iter_add(iter, offset);
> + slot += offset;
> + goto found;
> }
> } else {
> long count = radix_tree_chunk_size(iter);
> - void *canon = slot;
>
> while (--count > 0) {
> slot++;
> iter->index = __radix_tree_iter_add(iter, 1);
>
> - if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
> - radix_tree_is_internal_node(*slot)) {
> - if (entry_to_node(*slot) == canon)
> - continue;
> - iter->next_index = iter->index;
> - break;
> - }
> -
> if (likely(*slot))
> - return slot;
> + goto found;
> if (flags & RADIX_TREE_ITER_CONTIG) {
> /* forbid switching to the next chunk */
> iter->next_index = 0;
> @@ -527,6 +509,11 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> }
> }
> return NULL;
> +
> + found:
> + if (unlikely(radix_tree_is_internal_node(*slot)))
> + return __radix_tree_next_slot(slot, iter, flags);
> + return slot;
> }
>
> /**
> @@ -577,6 +564,6 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
> slot || (slot = radix_tree_next_chunk(root, iter, \
> RADIX_TREE_ITER_TAGGED | tag)) ; \
> slot = radix_tree_next_slot(slot, iter, \
> - RADIX_TREE_ITER_TAGGED))
> + RADIX_TREE_ITER_TAGGED | tag))
>
> #endif /* _LINUX_RADIX_TREE_H */
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 09c5f1d..27b53ef 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -69,6 +69,11 @@ struct radix_tree_preload {
> };
> static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
>
> +static inline struct radix_tree_node *entry_to_node(void *ptr)
> +{
> + return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
> +}
> +
> static inline void *node_to_entry(void *ptr)
> {
> return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
> @@ -1138,6 +1143,95 @@ static inline void __set_iter_shift(struct radix_tree_iter *iter,
> #endif
> }
>
> +static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
> + void **slot, struct radix_tree_iter *iter)
> +{
> + void *sib = node_to_entry(slot - 1);
> +
> + while (iter->index < iter->next_index) {
> + *nodep = rcu_dereference_raw(*slot);
> + if (*nodep && *nodep != sib)
> + return slot;
> + slot++;
> + iter->index = __radix_tree_iter_add(iter, 1);
> + iter->tags >>= 1;
> + }
> +
> + *nodep = NULL;
> + return NULL;
> +}
> +
> +#ifdef CONFIG_RADIX_TREE_MULTIORDER
> +void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> + unsigned flags)
> +{
> + unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
> + struct radix_tree_node *node = rcu_dereference_raw(*slot);
> +
> + slot = __radix_tree_iter_next(&node, slot, iter);
> +
> + while (radix_tree_is_internal_node(node)) {
> + unsigned offset;
> +
> + if (node == RADIX_TREE_RETRY)
> + return slot;
> + node = entry_to_node(node);
> +
> + if (flags & RADIX_TREE_ITER_TAGGED) {
> + unsigned tag_long, tag_bit;
> + offset = radix_tree_find_next_bit(node, tag, 0);
> + if (offset == RADIX_TREE_MAP_SIZE)
> + return NULL;
> + slot = &node->slots[offset];
> +
> + tag_long = offset / BITS_PER_LONG;
> + tag_bit = offset % BITS_PER_LONG;
> + iter->tags = node->tags[tag][tag_long] >> tag_bit;
> + BUG_ON(iter->tags >= (RADIX_TREE_MAP_SIZE * 2));
> + node = rcu_dereference_raw(*slot);
> + } else {
> + offset = 0;
> + slot = &node->slots[0];
> + for (;;) {
> + node = rcu_dereference_raw(*slot);
> + if (node)
> + break;
> + slot++;
> + offset++;
> + if (offset == RADIX_TREE_MAP_SIZE)
> + return NULL;
> + }
> + }
> + if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0))
> + goto none;
> + iter->shift -= RADIX_TREE_MAP_SHIFT;
> + iter->index = __radix_tree_iter_add(iter, offset);
> + iter->next_index = (iter->index | shift_maxindex(iter->shift)) +
> + 1;
> + }
> +
> + return slot;
> + none:
> + iter->next_index = 0;
> + return NULL;
> +}
> +EXPORT_SYMBOL(__radix_tree_next_slot);
> +#endif
> +
> +void **radix_tree_iter_next(void **slot, struct radix_tree_iter *iter)
> +{
> + struct radix_tree_node *node;
> +
> + slot++;
> + iter->index = __radix_tree_iter_add(iter, 1);
> + node = rcu_dereference_raw(*slot);
> + __radix_tree_iter_next(&node, slot, iter);
> + iter->next_index = iter->index;
> + iter->tags = 0;
> + return NULL;
> +}
> +EXPORT_SYMBOL(radix_tree_iter_next);
> +
> /**
> * radix_tree_next_chunk - find next chunk of slots for iteration
> *
> diff --git a/mm/khugepaged.c b/mm/khugepaged.c
> index 728d779..46155d1 100644
> --- a/mm/khugepaged.c
> +++ b/mm/khugepaged.c
> @@ -1614,8 +1614,8 @@ static void khugepaged_scan_shmem(struct mm_struct *mm,
> present++;
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> diff --git a/mm/shmem.c b/mm/shmem.c
> index 166ebf5..0b3fe33 100644
> --- a/mm/shmem.c
> +++ b/mm/shmem.c
> @@ -658,8 +658,8 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
> swapped++;
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
>
> @@ -2434,8 +2434,8 @@ static void shmem_tag_pins(struct address_space *mapping)
> }
>
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> @@ -2504,8 +2504,8 @@ static int shmem_wait_for_pins(struct address_space *mapping)
> spin_unlock_irq(&mapping->tree_lock);
> continue_resched:
> if (need_resched()) {
> + slot = radix_tree_iter_next(slot, &iter);
> cond_resched_rcu();
> - slot = radix_tree_iter_next(&iter);
> }
> }
> rcu_read_unlock();
> diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c
> index df71cb8..6eca4c2 100644
> --- a/tools/testing/radix-tree/iteration_check.c
> +++ b/tools/testing/radix-tree/iteration_check.c
> @@ -79,7 +79,7 @@ static void *tagged_iteration_fn(void *arg)
> }
>
> if (rand_r(&seeds[0]) % 50 == 0) {
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> rcu_read_unlock();
> rcu_barrier();
> rcu_read_lock();
> @@ -127,7 +127,7 @@ static void *untagged_iteration_fn(void *arg)
> }
>
> if (rand_r(&seeds[1]) % 50 == 0) {
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> rcu_read_unlock();
> rcu_barrier();
> rcu_read_lock();
> diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
> index 25e0463..588209a 100644
> --- a/tools/testing/radix-tree/multiorder.c
> +++ b/tools/testing/radix-tree/multiorder.c
> @@ -232,10 +232,14 @@ void multiorder_iteration(void)
> int height = order[i] / RADIX_TREE_MAP_SHIFT;
> int shift = height * RADIX_TREE_MAP_SHIFT;
> int mask = (1 << order[i]) - 1;
> + struct item *item = *slot;
>
> assert(iter.index >= (index[i] &~ mask));
> assert(iter.index <= (index[i] | mask));
> assert(iter.shift == shift);
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (index[i] &~ mask));
> + assert(item->index <= (index[i] | mask));
> i++;
> }
> }
> @@ -279,12 +283,16 @@ void multiorder_tagged_iteration(void)
> }
>
> radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
> + struct item *item = *slot;
> for (k = i; index[k] < tag_index[i]; k++)
> ;
> mask = (1 << order[k]) - 1;
>
> assert(iter.index >= (tag_index[i] &~ mask));
> assert(iter.index <= (tag_index[i] | mask));
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (tag_index[i] &~ mask));
> + assert(item->index <= (tag_index[i] | mask));
> i++;
> }
> }
> @@ -303,12 +311,16 @@ void multiorder_tagged_iteration(void)
> }
>
> radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
> + struct item *item = *slot;
> for (k = i; index[k] < tag_index[i]; k++)
> ;
> mask = (1 << order[k]) - 1;
>
> assert(iter.index >= (tag_index[i] &~ mask));
> assert(iter.index <= (tag_index[i] | mask));
> + assert(!radix_tree_is_internal_node(item));
> + assert(item->index >= (tag_index[i] &~ mask));
> + assert(item->index <= (tag_index[i] | mask));
> i++;
> }
> }
> diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c
> index 1f06ed7..4d28eeb 100644
> --- a/tools/testing/radix-tree/regression3.c
> +++ b/tools/testing/radix-tree/regression3.c
> @@ -88,7 +88,7 @@ void regression3_test(void)
> printf("slot %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> @@ -96,7 +96,7 @@ void regression3_test(void)
> printf("contig %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> @@ -106,7 +106,7 @@ void regression3_test(void)
> printf("tagged %ld %p\n", iter.index, *slot);
> if (!iter.index) {
> printf("next at %ld\n", iter.index);
> - slot = radix_tree_iter_next(&iter);
> + slot = radix_tree_iter_next(slot, &iter);
> }
> }
>
> diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
> index 33d2b6b..b678f13 100644
> --- a/tools/testing/radix-tree/test.h
> +++ b/tools/testing/radix-tree/test.h
> @@ -43,6 +43,7 @@ void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag);
> extern int nr_allocated;
>
> /* Normally private parts of lib/radix-tree.c */
> +struct radix_tree_node *entry_to_node(void *ptr);
> void radix_tree_dump(struct radix_tree_root *root);
> int root_tag_get(struct radix_tree_root *root, unsigned int tag);
> unsigned long node_maxindex(struct radix_tree_node *);
> --
> 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>
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@microsoft.com> |
|---|---|
| Date | 2016-11-18 17:40 +0100 |
| Subject | RE: [PATCH 20/29] radix tree: Improve multiorder iterators |
| Message-ID | <sEUmJ-18a-21@gated-at.bofh.it> |
| In reply to | #1525218 |
From: Konstantin Khlebnikov [mailto:koct9i@gmail.com]
> On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox
> <mawilcox@linuxonhyperv.com> wrote:
> > This fixes several interlinked problems with the iterators in the
> > presence of multiorder entries.
> >
> > 1. radix_tree_iter_next() would only advance by one slot, which would
> > result in the iterators returning the same entry more than once if there
> > were sibling entries.
>
> Is this a problem? Do we have users who cannot evalate length of entry
> by looking into it head?
At the moment we have no users in tree :-) The two users I know of are the page cache and DAX. The page cache stores a pointer to a struct page, which has compound_order() to tell you the size. DAX uses a couple of bits in the radix tree entry to describe whether this is a PTE/PMD/PUD and so also knows the size of the entry that it found. We also store swap cache entries in the same radix tree (tagged exceptional). These currently have no information in them to describe their size because each one represents only one page. The latest patchset to support swapping huge pages inserts 512 entries into the radix tree instead of taking advantage of the multiorder entry infrastructure. Hopefully that gets fixed soon, but it will require stealing a bit from either the number of swap files allowed or from the maximum size of each swap file (currently 32/128GB)
I think what you're suggesting is that we introduce a new API:
slot = radix_tree_iter_save(&iter, order);
where the caller tells us the order of the entry it just consumed. Or maybe you're suggesting
slot = radix_tree_iter_advance(&iter, newindex)
which would allow us to skip to any index. Although ... isn't that just radix_tree_iter_init()?
It does push a bit of complexity onto the callers. We have 7 callers of radix_tree_iter_next() in my current tree (after applying this patch set, so range_tag_if_tagged and locate_item have been pushed into their callers): btrfs, kugepaged, page-writeback and shmem. btrfs knows its objects occupy one slot. khugepaged knows that its page is order 0 at the time it calls radix_tree_iter_next(). Page-writeback has a struct page and can simply use compound_order(). It's shmem where things get sticky, although it's all solvable with some temporary variables.
MM people, what do you think of this patch? It's on top of my current IDR tree, although I'd fold it into patch 20 of the series if it's acceptable.
diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
index 6d3457a..7f864ec 100644
--- a/fs/btrfs/tests/btrfs-tests.c
+++ b/fs/btrfs/tests/btrfs-tests.c
@@ -162,7 +162,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
slot = radix_tree_iter_retry(&iter);
continue;
}
- slot = radix_tree_iter_next(slot, &iter);
+ slot = radix_tree_iter_save(&iter, 0);
spin_unlock(&fs_info->buffer_lock);
free_extent_buffer_stale(eb);
spin_lock(&fs_info->buffer_lock);
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 4e42d4d..4419325 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -421,15 +421,22 @@ __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
}
/**
- * radix_tree_iter_next - resume iterating when the chunk may be invalid
- * @iter: iterator state
+ * radix_tree_iter_save - resume iterating when the chunk may be invalid
+ * @iter: iterator state
+ * @order: order of the entry that was just processed
*
- * If the iterator needs to release then reacquire a lock, the chunk may
- * have been invalidated by an insertion or deletion. Call this function
+ * If the iteration needs to release then reacquire a lock, the chunk may
+ * be invalidated by an insertion or deletion. Call this function
* before releasing the lock to continue the iteration from the next index.
*/
-void **__must_check radix_tree_iter_next(void **slot,
- struct radix_tree_iter *iter);
+static inline void **__must_check
+radix_tree_iter_save(struct radix_tree_iter *iter, unsigned order)
+{
+ iter->next_index = round_up(iter->index, 1 << order);
+ iter->index = 0;
+ iter->tags = 0;
+ return NULL;
+}
/**
* radix_tree_chunk_size - get current chunk size
@@ -467,7 +474,7 @@ static inline void ** __radix_tree_next_slot(void **slot,
* For tagged lookup it also eats @iter->tags.
*
* There are several cases where 'slot' can be passed in as NULL to this
- * function. These cases result from the use of radix_tree_iter_next() or
+ * function. These cases result from the use of radix_tree_iter_save() or
* radix_tree_iter_retry(). In these cases we don't end up dereferencing
* 'slot' because either:
* a) we are doing tagged iteration and iter->tags has been set to 0, or
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 7e2469b..fcbadad 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1245,6 +1245,7 @@ static inline void __set_iter_shift(struct radix_tree_iter *iter,
#endif
}
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
void **slot, struct radix_tree_iter *iter)
{
@@ -1263,7 +1264,6 @@ static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
return NULL;
}
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
unsigned flags)
{
@@ -1321,20 +1321,6 @@ void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
EXPORT_SYMBOL(__radix_tree_next_slot);
#endif
-void **radix_tree_iter_next(void **slot, struct radix_tree_iter *iter)
-{
- struct radix_tree_node *node;
-
- slot++;
- iter->index = __radix_tree_iter_add(iter, 1);
- node = rcu_dereference_raw(*slot);
- __radix_tree_iter_next(&node, slot, iter);
- iter->next_index = iter->index;
- iter->tags = 0;
- return NULL;
-}
-EXPORT_SYMBOL(radix_tree_iter_next);
-
/**
* radix_tree_next_chunk - find next chunk of slots for iteration
*
diff --git a/mm/khugepaged.c b/mm/khugepaged.c
index 46155d1..54446e6 100644
--- a/mm/khugepaged.c
+++ b/mm/khugepaged.c
@@ -1614,7 +1614,7 @@ static void khugepaged_scan_shmem(struct mm_struct *mm,
present++;
if (need_resched()) {
- slot = radix_tree_iter_next(slot, &iter);
+ slot = radix_tree_iter_save(&iter, 0);
cond_resched_rcu();
}
}
diff --git a/mm/page-writeback.c b/mm/page-writeback.c
index c593715..7d6b870 100644
--- a/mm/page-writeback.c
+++ b/mm/page-writeback.c
@@ -2119,7 +2119,7 @@ void tag_pages_for_writeback(struct address_space *mapping,
tagged++;
if ((tagged % WRITEBACK_TAG_BATCH) != 0)
continue;
- slot = radix_tree_iter_next(slot, &iter);
+ slot = radix_tree_iter_save(&iter, compound_order(*slot));
spin_unlock_irq(&mapping->tree_lock);
cond_resched();
spin_lock_irq(&mapping->tree_lock);
diff --git a/mm/shmem.c b/mm/shmem.c
index 8f9c9aa..3f2d07a 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -644,6 +644,7 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
rcu_read_lock();
radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
+ unsigned int order = 0;
if (iter.index >= end)
break;
@@ -656,9 +657,11 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
if (radix_tree_exceptional_entry(page))
swapped++;
+ else
+ order = compound_order(page);
if (need_resched()) {
- slot = radix_tree_iter_next(slot, &iter);
+ slot = radix_tree_iter_save(&iter, order);
cond_resched_rcu();
}
}
@@ -1062,7 +1065,7 @@ static unsigned long find_swap_entry(struct radix_tree_root *root, void *item)
checked++;
if ((checked % 4096) != 0)
continue;
- slot = radix_tree_iter_next(slot, &iter);
+ slot = radix_tree_iter_save(&iter, 0);
cond_resched_rcu();
}
@@ -2444,21 +2447,25 @@ static void shmem_tag_pins(struct address_space *mapping)
rcu_read_lock();
radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
+ unsigned int order = 0;
page = radix_tree_deref_slot(slot);
if (!page || radix_tree_exception(page)) {
if (radix_tree_deref_retry(page)) {
slot = radix_tree_iter_retry(&iter);
continue;
}
- } else if (page_count(page) - page_mapcount(page) > 1) {
- spin_lock_irq(&mapping->tree_lock);
- radix_tree_tag_set(&mapping->page_tree, iter.index,
- SHMEM_TAG_PINNED);
- spin_unlock_irq(&mapping->tree_lock);
+ } else {
+ order = compound_order(page);
+ if (page_count(page) - page_mapcount(page) > 1) {
+ spin_lock_irq(&mapping->tree_lock);
+ radix_tree_tag_set(&mapping->page_tree,
+ iter.index, SHMEM_TAG_PINNED);
+ spin_unlock_irq(&mapping->tree_lock);
+ }
}
if (need_resched()) {
- slot = radix_tree_iter_next(slot, &iter);
+ slot = radix_tree_iter_save(&iter, order);
cond_resched_rcu();
}
}
@@ -2528,7 +2535,10 @@ static int shmem_wait_for_pins(struct address_space *mapping)
spin_unlock_irq(&mapping->tree_lock);
continue_resched:
if (need_resched()) {
- slot = radix_tree_iter_next(slot, &iter);
+ unsigned int order = 0;
+ if (page)
+ order = compound_order(page);
+ slot = radix_tree_iter_save(&iter, order);
cond_resched_rcu();
}
}
[toc] | [prev] | [next] | [standalone]
| From | Konstantin Khlebnikov <koct9i@gmail.com> |
|---|---|
| Date | 2016-11-18 19:00 +0100 |
| Subject | Re: [PATCH 20/29] radix tree: Improve multiorder iterators |
| Message-ID | <sEVCa-1Ow-7@gated-at.bofh.it> |
| In reply to | #1525503 |
On Fri, Nov 18, 2016 at 7:31 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> From: Konstantin Khlebnikov [mailto:koct9i@gmail.com]
>> On Thu, Nov 17, 2016 at 3:17 AM, Matthew Wilcox
>> <mawilcox@linuxonhyperv.com> wrote:
>> > This fixes several interlinked problems with the iterators in the
>> > presence of multiorder entries.
>> >
>> > 1. radix_tree_iter_next() would only advance by one slot, which would
>> > result in the iterators returning the same entry more than once if there
>> > were sibling entries.
>>
>> Is this a problem? Do we have users who cannot evalate length of entry
>> by looking into it head?
>
> At the moment we have no users in tree :-) The two users I know of are the page cache and DAX. The page cache stores a pointer to a struct page, which has compound_order() to tell you the size. DAX uses a couple of bits in the radix tree entry to describe whether this is a PTE/PMD/PUD and so also knows the size of the entry that it found. We also store swap cache entries in the same radix tree (tagged exceptional). These currently have no information in them to describe their size because each one represents only one page. The latest patchset to support swapping huge pages inserts 512 entries into the radix tree instead of taking advantage of the multiorder entry infrastructure. Hopefully that gets fixed soon, but it will require stealing a bit from either the number of swap files allowed or from the maximum size of each swap file (currently 32/128GB)
>
> I think what you're suggesting is that we introduce a new API:
>
> slot = radix_tree_iter_save(&iter, order);
>
> where the caller tells us the order of the entry it just consumed. Or maybe you're suggesting
>
> slot = radix_tree_iter_advance(&iter, newindex)
Yes, someting like that.
>
> which would allow us to skip to any index. Although ... isn't that just radix_tree_iter_init()?
Iterator could keep pointer to current node and reuse it for next
iteration if possible.
>
> It does push a bit of complexity onto the callers. We have 7 callers of radix_tree_iter_next() in my current tree (after applying this patch set, so range_tag_if_tagged and locate_item have been pushed into their callers): btrfs, kugepaged, page-writeback and shmem. btrfs knows its objects occupy one slot. khugepaged knows that its page is order 0 at the time it calls radix_tree_iter_next(). Page-writeback has a struct page and can simply use compound_order(). It's shmem where things get sticky, although it's all solvable with some temporary variables.
>
Users who work only with single slot enties don't get any complications,
all other already manage these multiorder entries somehow.
> MM people, what do you think of this patch? It's on top of my current IDR tree, although I'd fold it into patch 20 of the series if it's acceptable.
>
> diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c
> index 6d3457a..7f864ec 100644
> --- a/fs/btrfs/tests/btrfs-tests.c
> +++ b/fs/btrfs/tests/btrfs-tests.c
> @@ -162,7 +162,7 @@ void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info)
> slot = radix_tree_iter_retry(&iter);
> continue;
> }
> - slot = radix_tree_iter_next(slot, &iter);
> + slot = radix_tree_iter_save(&iter, 0);
> spin_unlock(&fs_info->buffer_lock);
> free_extent_buffer_stale(eb);
> spin_lock(&fs_info->buffer_lock);
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 4e42d4d..4419325 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -421,15 +421,22 @@ __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
> }
>
> /**
> - * radix_tree_iter_next - resume iterating when the chunk may be invalid
> - * @iter: iterator state
> + * radix_tree_iter_save - resume iterating when the chunk may be invalid
> + * @iter: iterator state
> + * @order: order of the entry that was just processed
> *
> - * If the iterator needs to release then reacquire a lock, the chunk may
> - * have been invalidated by an insertion or deletion. Call this function
> + * If the iteration needs to release then reacquire a lock, the chunk may
> + * be invalidated by an insertion or deletion. Call this function
> * before releasing the lock to continue the iteration from the next index.
> */
> -void **__must_check radix_tree_iter_next(void **slot,
> - struct radix_tree_iter *iter);
> +static inline void **__must_check
> +radix_tree_iter_save(struct radix_tree_iter *iter, unsigned order)
> +{
> + iter->next_index = round_up(iter->index, 1 << order);
> + iter->index = 0;
> + iter->tags = 0;
> + return NULL;
> +}
>
> /**
> * radix_tree_chunk_size - get current chunk size
> @@ -467,7 +474,7 @@ static inline void ** __radix_tree_next_slot(void **slot,
> * For tagged lookup it also eats @iter->tags.
> *
> * There are several cases where 'slot' can be passed in as NULL to this
> - * function. These cases result from the use of radix_tree_iter_next() or
> + * function. These cases result from the use of radix_tree_iter_save() or
> * radix_tree_iter_retry(). In these cases we don't end up dereferencing
> * 'slot' because either:
> * a) we are doing tagged iteration and iter->tags has been set to 0, or
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 7e2469b..fcbadad 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -1245,6 +1245,7 @@ static inline void __set_iter_shift(struct radix_tree_iter *iter,
> #endif
> }
>
> +#ifdef CONFIG_RADIX_TREE_MULTIORDER
> static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
> void **slot, struct radix_tree_iter *iter)
> {
> @@ -1263,7 +1264,6 @@ static void ** __radix_tree_iter_next(struct radix_tree_node **nodep,
> return NULL;
> }
>
> -#ifdef CONFIG_RADIX_TREE_MULTIORDER
> void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> unsigned flags)
> {
> @@ -1321,20 +1321,6 @@ void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
> EXPORT_SYMBOL(__radix_tree_next_slot);
> #endif
>
> -void **radix_tree_iter_next(void **slot, struct radix_tree_iter *iter)
> -{
> - struct radix_tree_node *node;
> -
> - slot++;
> - iter->index = __radix_tree_iter_add(iter, 1);
> - node = rcu_dereference_raw(*slot);
> - __radix_tree_iter_next(&node, slot, iter);
> - iter->next_index = iter->index;
> - iter->tags = 0;
> - return NULL;
> -}
> -EXPORT_SYMBOL(radix_tree_iter_next);
> -
> /**
> * radix_tree_next_chunk - find next chunk of slots for iteration
> *
> diff --git a/mm/khugepaged.c b/mm/khugepaged.c
> index 46155d1..54446e6 100644
> --- a/mm/khugepaged.c
> +++ b/mm/khugepaged.c
> @@ -1614,7 +1614,7 @@ static void khugepaged_scan_shmem(struct mm_struct *mm,
> present++;
>
> if (need_resched()) {
> - slot = radix_tree_iter_next(slot, &iter);
> + slot = radix_tree_iter_save(&iter, 0);
> cond_resched_rcu();
> }
> }
> diff --git a/mm/page-writeback.c b/mm/page-writeback.c
> index c593715..7d6b870 100644
> --- a/mm/page-writeback.c
> +++ b/mm/page-writeback.c
> @@ -2119,7 +2119,7 @@ void tag_pages_for_writeback(struct address_space *mapping,
> tagged++;
> if ((tagged % WRITEBACK_TAG_BATCH) != 0)
> continue;
> - slot = radix_tree_iter_next(slot, &iter);
> + slot = radix_tree_iter_save(&iter, compound_order(*slot));
> spin_unlock_irq(&mapping->tree_lock);
> cond_resched();
> spin_lock_irq(&mapping->tree_lock);
> diff --git a/mm/shmem.c b/mm/shmem.c
> index 8f9c9aa..3f2d07a 100644
> --- a/mm/shmem.c
> +++ b/mm/shmem.c
> @@ -644,6 +644,7 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
> rcu_read_lock();
>
> radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
> + unsigned int order = 0;
> if (iter.index >= end)
> break;
>
> @@ -656,9 +657,11 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
>
> if (radix_tree_exceptional_entry(page))
> swapped++;
> + else
> + order = compound_order(page);
>
> if (need_resched()) {
> - slot = radix_tree_iter_next(slot, &iter);
> + slot = radix_tree_iter_save(&iter, order);
> cond_resched_rcu();
> }
> }
> @@ -1062,7 +1065,7 @@ static unsigned long find_swap_entry(struct radix_tree_root *root, void *item)
> checked++;
> if ((checked % 4096) != 0)
> continue;
> - slot = radix_tree_iter_next(slot, &iter);
> + slot = radix_tree_iter_save(&iter, 0);
> cond_resched_rcu();
> }
>
> @@ -2444,21 +2447,25 @@ static void shmem_tag_pins(struct address_space *mapping)
> rcu_read_lock();
>
> radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
> + unsigned int order = 0;
> page = radix_tree_deref_slot(slot);
> if (!page || radix_tree_exception(page)) {
> if (radix_tree_deref_retry(page)) {
> slot = radix_tree_iter_retry(&iter);
> continue;
> }
> - } else if (page_count(page) - page_mapcount(page) > 1) {
> - spin_lock_irq(&mapping->tree_lock);
> - radix_tree_tag_set(&mapping->page_tree, iter.index,
> - SHMEM_TAG_PINNED);
> - spin_unlock_irq(&mapping->tree_lock);
> + } else {
> + order = compound_order(page);
> + if (page_count(page) - page_mapcount(page) > 1) {
> + spin_lock_irq(&mapping->tree_lock);
> + radix_tree_tag_set(&mapping->page_tree,
> + iter.index, SHMEM_TAG_PINNED);
> + spin_unlock_irq(&mapping->tree_lock);
> + }
> }
>
> if (need_resched()) {
> - slot = radix_tree_iter_next(slot, &iter);
> + slot = radix_tree_iter_save(&iter, order);
> cond_resched_rcu();
> }
> }
> @@ -2528,7 +2535,10 @@ static int shmem_wait_for_pins(struct address_space *mapping)
> spin_unlock_irq(&mapping->tree_lock);
> continue_resched:
> if (need_resched()) {
> - slot = radix_tree_iter_next(slot, &iter);
> + unsigned int order = 0;
> + if (page)
> + order = compound_order(page);
> + slot = radix_tree_iter_save(&iter, order);
> cond_resched_rcu();
> }
> }
[toc] | [prev] | [next] | [standalone]
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
Back to top | Article view | linux.kernel
csiph-web