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 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
| From | Matthew Wilcox <mawilcox@microsoft.com> |
|---|---|
| Date | 2016-11-18 22:00 +0100 |
| Subject | RE: [PATCH 20/29] radix tree: Improve multiorder iterators |
| Message-ID | <sEYql-3F7-5@gated-at.bofh.it> |
| In reply to | #1525598 |
From: Konstantin Khlebnikov [mailto:koct9i@gmail.com]
> On Fri, Nov 18, 2016 at 7:31 PM, Matthew Wilcox <mawilcox@microsoft.com>
> wrote:
> > 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.
The point of this API is that it's never possible, because we're about to drop the lock and allow other users to modify the tree. Actually, it is different from radix_tree_iter_init() because it has to set ->tags to 0 and ->index == ->next_index in order to get through a call to radix_tree_next_slot().
> > 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.
If you read the patch below, you'll see that most callers don't need to be concerned with the size of the entry they're looking at. I'll trim away the trivial ones so it's easier to see my point.
It's not a huge amount of code in each caller, but is this a burden we really want to push onto the callers when we could handle it behind the interface?
diff --git a/mm/shmem.c b/mm/shmem.c
index 8f9c9aa..90dd18d9 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -658,7 +658,10 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping,
swapped++;
if (need_resched()) {
- slot = radix_tree_iter_next(slot, &iter);
+ unsigned int order = 0;
+ if (!radix_tree_exceptional_entry(page))
+ order = compound_order(page);
+ slot = radix_tree_iter_save(&iter, order);
cond_resched_rcu();
}
}
@@ -2450,6 +2453,7 @@ static void shmem_tag_pins(struct address_space *mapping)
slot = radix_tree_iter_retry(&iter);
continue;
}
+ page = NULL;
} else if (page_count(page) - page_mapcount(page) > 1) {
spin_lock_irq(&mapping->tree_lock);
radix_tree_tag_set(&mapping->page_tree, iter.index,
@@ -2458,7 +2462,8 @@ static void shmem_tag_pins(struct address_space *mapping)
}
if (need_resched()) {
- slot = radix_tree_iter_next(slot, &iter);
+ unsigned int order = page ? compound_order(page) : 0;
+ slot = radix_tree_iter_save(&iter, order);
cond_resched_rcu();
}
}
@@ -2528,7 +2533,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 | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 17/29] radix-tree: Improve dump output |
| Message-ID | <sEh23-uC-47@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 04/29] radix tree test suite: Free preallocated nodes |
| Message-ID | <sEh23-uC-45@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@infradead.org>
It can be a source of mild concern when the test suite shows that we're
leaking nodes. While poring over the source code looking for leaks
can lead to some fascinating bugs being discovered, sometimes the leak
is simply that these nodes were preallocated and are sitting on the
per-CPU list. Free them by faking a CPU_DEAD event.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
tools/testing/radix-tree/main.c | 3 +++
tools/testing/radix-tree/test.h | 4 ++++
2 files changed, 7 insertions(+)
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 64ffe67..2930560 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -344,6 +344,9 @@ int main(int argc, char **argv)
iteration_test();
single_thread_tests(long_run);
+ /* Free any remaining preallocated nodes */
+ radix_tree_callback(NULL, CPU_DEAD, NULL);
+
sleep(1);
printf("after sleep(1): %d allocated, preempt %d\n",
nr_allocated, preempt_count);
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 217fb24..8cd666a 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -2,6 +2,8 @@
#include <linux/types.h>
#include <linux/radix-tree.h>
#include <linux/rcupdate.h>
+#include <linux/notifier.h>
+#include <linux/cpu.h>
struct item {
unsigned long index;
@@ -44,3 +46,5 @@ 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 *);
unsigned long shift_maxindex(unsigned int shift);
+int radix_tree_callback(struct notifier_block *nfb,
+ unsigned long action, void *hcpu);
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 09/29] radix tree test suite: Use common find-bit code |
| Message-ID | <sEh22-uC-25@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
Remove the old find_next_bit code in favour of linking in the find_bit
code from tools/lib.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
tools/testing/radix-tree/Makefile | 7 ++-
tools/testing/radix-tree/find_next_bit.c | 57 ----------------------
tools/testing/radix-tree/linux/bitops.h | 40 +++++++++------
tools/testing/radix-tree/linux/bitops/non-atomic.h | 13 +++--
tools/testing/radix-tree/linux/kernel.h | 11 +++++
5 files changed, 48 insertions(+), 80 deletions(-)
delete mode 100644 tools/testing/radix-tree/find_next_bit.c
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 08283a8..3635e4d 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -18,7 +18,12 @@ main: $(OFILES)
clean:
$(RM) -f $(TARGETS) *.o radix-tree.c
-$(OFILES): *.h */*.h ../../../include/linux/radix-tree.h ../../include/linux/*.h
+find_next_bit.o: ../../lib/find_bit.c
+ $(CC) $(CFLAGS) -c -o $@ $<
+
+$(OFILES): *.h */*.h \
+ ../../include/linux/*.h \
+ ../../../include/linux/radix-tree.h
radix-tree.c: ../../../lib/radix-tree.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
diff --git a/tools/testing/radix-tree/find_next_bit.c b/tools/testing/radix-tree/find_next_bit.c
deleted file mode 100644
index d1c2178..0000000
--- a/tools/testing/radix-tree/find_next_bit.c
+++ /dev/null
@@ -1,57 +0,0 @@
-/* find_next_bit.c: fallback find next bit implementation
- *
- * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
- * Written by David Howells (dhowells@redhat.com)
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version
- * 2 of the License, or (at your option) any later version.
- */
-
-#include <linux/types.h>
-#include <linux/bitops.h>
-
-#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
-
-/*
- * Find the next set bit in a memory region.
- */
-unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
- unsigned long offset)
-{
- const unsigned long *p = addr + BITOP_WORD(offset);
- unsigned long result = offset & ~(BITS_PER_LONG-1);
- unsigned long tmp;
-
- if (offset >= size)
- return size;
- size -= result;
- offset %= BITS_PER_LONG;
- if (offset) {
- tmp = *(p++);
- tmp &= (~0UL << offset);
- if (size < BITS_PER_LONG)
- goto found_first;
- if (tmp)
- goto found_middle;
- size -= BITS_PER_LONG;
- result += BITS_PER_LONG;
- }
- while (size & ~(BITS_PER_LONG-1)) {
- if ((tmp = *(p++)))
- goto found_middle;
- result += BITS_PER_LONG;
- size -= BITS_PER_LONG;
- }
- if (!size)
- return result;
- tmp = *p;
-
-found_first:
- tmp &= (~0UL >> (BITS_PER_LONG - size));
- if (tmp == 0UL) /* Are any bits set? */
- return result + size; /* Nope. */
-found_middle:
- return result + __ffs(tmp);
-}
diff --git a/tools/testing/radix-tree/linux/bitops.h b/tools/testing/radix-tree/linux/bitops.h
index 71d58427..a13e9bc 100644
--- a/tools/testing/radix-tree/linux/bitops.h
+++ b/tools/testing/radix-tree/linux/bitops.h
@@ -2,9 +2,14 @@
#define _ASM_GENERIC_BITOPS_NON_ATOMIC_H_
#include <linux/types.h>
+#include <linux/bitops/find.h>
+#include <linux/bitops/hweight.h>
+#include <linux/kernel.h>
-#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
-#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
+#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
+#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
+#define BITS_PER_BYTE 8
+#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
/**
* __set_bit - Set a bit in memory
@@ -17,16 +22,16 @@
*/
static inline void __set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
*p |= mask;
}
static inline void __clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
*p &= ~mask;
}
@@ -42,8 +47,8 @@ static inline void __clear_bit(int nr, volatile unsigned long *addr)
*/
static inline void __change_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
*p ^= mask;
}
@@ -59,8 +64,8 @@ static inline void __change_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
unsigned long old = *p;
*p = old | mask;
@@ -78,8 +83,8 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
unsigned long old = *p;
*p = old & ~mask;
@@ -90,8 +95,8 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
static inline int __test_and_change_bit(int nr,
volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
unsigned long old = *p;
*p = old ^ mask;
@@ -105,7 +110,7 @@ static inline int __test_and_change_bit(int nr,
*/
static inline int test_bit(int nr, const volatile unsigned long *addr)
{
- return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
+ return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
}
/**
@@ -147,4 +152,9 @@ unsigned long find_next_bit(const unsigned long *addr,
unsigned long size,
unsigned long offset);
+static inline unsigned long hweight_long(unsigned long w)
+{
+ return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
+}
+
#endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */
diff --git a/tools/testing/radix-tree/linux/bitops/non-atomic.h b/tools/testing/radix-tree/linux/bitops/non-atomic.h
index 46a825c..6a1bcb9 100644
--- a/tools/testing/radix-tree/linux/bitops/non-atomic.h
+++ b/tools/testing/radix-tree/linux/bitops/non-atomic.h
@@ -3,7 +3,6 @@
#include <asm/types.h>
-#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
/**
@@ -17,7 +16,7 @@
*/
static inline void __set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
*p |= mask;
@@ -25,7 +24,7 @@ static inline void __set_bit(int nr, volatile unsigned long *addr)
static inline void __clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
*p &= ~mask;
@@ -42,7 +41,7 @@ static inline void __clear_bit(int nr, volatile unsigned long *addr)
*/
static inline void __change_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
*p ^= mask;
@@ -59,7 +58,7 @@ static inline void __change_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
unsigned long old = *p;
@@ -78,7 +77,7 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
unsigned long old = *p;
@@ -90,7 +89,7 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
static inline int __test_and_change_bit(int nr,
volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
unsigned long old = *p;
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index dbe4b92..23e77f5 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -47,4 +47,15 @@ static inline int in_interrupt(void)
{
return 0;
}
+
+/*
+ * This looks more complex than it should be. But we need to
+ * get the type for the ~ right in round_down (it needs to be
+ * as wide as the result!), and we want to evaluate the macro
+ * arguments just once each.
+ */
+#define __round_mask(x, y) ((__typeof__(x))((y)-1))
+#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
+#define round_down(x, y) ((x) & ~__round_mask(x, y))
+
#endif /* _KERNEL_H */
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() |
| Message-ID | <sEh23-uC-51@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <mawilcox@microsoft.com>
This is an exceptionally complicated function with just one caller
(tag_pages_for_writeback). We devote a large portion of the runtime
of the test suite to testing this one function which has one caller.
By introducing the new function radix_tree_iter_tag_set(), we
can eliminate all of the complexity while keeping the performance.
The caller can now use a fairly standard radix_tree_for_each() loop,
and it doesn't need to worry about tricksy things like 'start' wrapping.
The test suite continues to spend a large amount of time investigating
this function, but now it's testing the underlying primitives such as
radix_tree_iter_next() and the radix_tree_for_each_tagged() iterator
which are also used by other parts of the kernel.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
include/linux/radix-tree.h | 74 ++++++++++-----------
lib/radix-tree.c | 114 +++++----------------------------
mm/page-writeback.c | 28 +++++---
tools/testing/radix-tree/main.c | 12 ++--
tools/testing/radix-tree/multiorder.c | 13 ++--
tools/testing/radix-tree/regression2.c | 3 +-
tools/testing/radix-tree/tag_check.c | 4 +-
tools/testing/radix-tree/test.c | 25 ++++++++
tools/testing/radix-tree/test.h | 3 +
9 files changed, 113 insertions(+), 163 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 57bf635..ca4eea1 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -124,6 +124,41 @@ static inline bool radix_tree_empty(struct radix_tree_root *root)
}
/**
+ * struct radix_tree_iter - radix tree iterator state
+ *
+ * @index: index of current slot
+ * @next_index: one beyond the last index for this chunk
+ * @tags: bit-mask for tag-iterating
+ * @node: node that contains current slot
+ * @shift: shift for the node that holds our slots
+ *
+ * This radix tree iterator works in terms of "chunks" of slots. A chunk is a
+ * subinterval of slots contained within one radix tree leaf node. It is
+ * described by a pointer to its first slot and a struct radix_tree_iter
+ * which holds the chunk's position in the tree and its size. For tagged
+ * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
+ * radix tree tag.
+ */
+struct radix_tree_iter {
+ unsigned long index;
+ unsigned long next_index;
+ unsigned long tags;
+ struct radix_tree_node *node;
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+ unsigned int shift;
+#endif
+};
+
+static inline unsigned int iter_shift(struct radix_tree_iter *iter)
+{
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+ return iter->shift;
+#else
+ return 0;
+#endif
+}
+
+/**
* Radix-tree synchronization
*
* The radix-tree API requires that users provide all synchronisation (with
@@ -293,6 +328,8 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
unsigned long index, unsigned int tag);
int radix_tree_tag_get(struct radix_tree_root *root,
unsigned long index, unsigned int tag);
+void radix_tree_iter_tag_set(struct radix_tree_root *root,
+ const struct radix_tree_iter *iter, unsigned int tag);
unsigned int
radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
unsigned long first_index, unsigned int max_items,
@@ -301,10 +338,6 @@ unsigned int
radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
unsigned long first_index, unsigned int max_items,
unsigned int tag);
-unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
- unsigned long *first_indexp, unsigned long last_index,
- unsigned long nr_to_tag,
- unsigned int fromtag, unsigned int totag);
int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
static inline void radix_tree_preload_end(void)
@@ -318,39 +351,6 @@ int radix_tree_split(struct radix_tree_root *, unsigned long index,
int radix_tree_join(struct radix_tree_root *, unsigned long index,
unsigned new_order, void *);
-/**
- * struct radix_tree_iter - radix tree iterator state
- *
- * @index: index of current slot
- * @next_index: one beyond the last index for this chunk
- * @tags: bit-mask for tag-iterating
- * @shift: shift for the node that holds our slots
- *
- * This radix tree iterator works in terms of "chunks" of slots. A chunk is a
- * subinterval of slots contained within one radix tree leaf node. It is
- * described by a pointer to its first slot and a struct radix_tree_iter
- * which holds the chunk's position in the tree and its size. For tagged
- * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
- * radix tree tag.
- */
-struct radix_tree_iter {
- unsigned long index;
- unsigned long next_index;
- unsigned long tags;
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- unsigned int shift;
-#endif
-};
-
-static inline unsigned int iter_shift(struct radix_tree_iter *iter)
-{
-#ifdef CONFIG_RADIX_TREE_MULTIORDER
- return iter->shift;
-#else
- return 0;
-#endif
-}
-
#define RADIX_TREE_ITER_TAG_MASK 0x00FF /* tag index in lower byte */
#define RADIX_TREE_ITER_TAGGED 0x0100 /* lookup tagged slots */
#define RADIX_TREE_ITER_CONTIG 0x0200 /* stop at first hole */
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 7e70ac9..c8ef657 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1049,6 +1049,20 @@ static void node_tag_set(struct radix_tree_root *root,
}
/**
+ * radix_tree_iter_tag_set - set a tag on the current iterator entry
+ *
+ * @root: radix tree root
+ * @iter: iterator state
+ * @tag: tag to set
+ */
+void radix_tree_iter_tag_set(struct radix_tree_root *root,
+ const struct radix_tree_iter *iter, unsigned int tag)
+{
+ unsigned offset = (iter->index >> iter->shift) & RADIX_TREE_MAP_MASK;
+ node_tag_set(root, iter->node, tag, offset);
+}
+
+/**
* radix_tree_tag_clear - clear a tag on a radix tree node
* @root: radix tree root
* @index: index key
@@ -1176,6 +1190,7 @@ void ** __radix_tree_next_slot(void **slot, struct radix_tree_iter *iter,
if (node == RADIX_TREE_RETRY)
return slot;
node = entry_to_node(node);
+ iter->node = node;
if (flags & RADIX_TREE_ITER_TAGGED) {
unsigned tag_long, tag_bit;
@@ -1275,6 +1290,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
iter->index = index;
iter->next_index = maxindex + 1;
iter->tags = 1;
+ iter->node = NULL;
__set_iter_shift(iter, 0);
return (void **)&root->rnode;
}
@@ -1319,6 +1335,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
/* Update the iterator state */
iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
iter->next_index = (index | node_maxindex(node)) + 1;
+ iter->node = node;
__set_iter_shift(iter, node->shift);
/* Construct iter->tags bit-mask from node->tags[tag] array */
@@ -1344,103 +1361,6 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
EXPORT_SYMBOL(radix_tree_next_chunk);
/**
- * radix_tree_range_tag_if_tagged - for each item in given range set given
- * tag if item has another tag set
- * @root: radix tree root
- * @first_indexp: pointer to a starting index of a range to scan
- * @last_index: last index of a range to scan
- * @nr_to_tag: maximum number items to tag
- * @iftag: tag index to test
- * @settag: tag index to set if tested tag is set
- *
- * This function scans range of radix tree from first_index to last_index
- * (inclusive). For each item in the range if iftag is set, the function sets
- * also settag. The function stops either after tagging nr_to_tag items or
- * after reaching last_index.
- *
- * The tags must be set from the leaf level only and propagated back up the
- * path to the root. We must do this so that we resolve the full path before
- * setting any tags on intermediate nodes. If we set tags as we descend, then
- * we can get to the leaf node and find that the index that has the iftag
- * set is outside the range we are scanning. This reults in dangling tags and
- * can lead to problems with later tag operations (e.g. livelocks on lookups).
- *
- * The function returns the number of leaves where the tag was set and sets
- * *first_indexp to the first unscanned index.
- * WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
- * be prepared to handle that.
- */
-unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
- unsigned long *first_indexp, unsigned long last_index,
- unsigned long nr_to_tag,
- unsigned int iftag, unsigned int settag)
-{
- struct radix_tree_node *node, *child;
- unsigned long maxindex;
- unsigned long tagged = 0;
- unsigned long index = *first_indexp;
-
- radix_tree_load_root(root, &child, &maxindex);
- last_index = min(last_index, maxindex);
- if (index > last_index)
- return 0;
- if (!nr_to_tag)
- return 0;
- if (!root_tag_get(root, iftag)) {
- *first_indexp = last_index + 1;
- return 0;
- }
- if (!radix_tree_is_internal_node(child)) {
- *first_indexp = last_index + 1;
- root_tag_set(root, settag);
- return 1;
- }
-
- node = entry_to_node(child);
-
- for (;;) {
- unsigned offset = radix_tree_descend(node, &child, index);
- if (!child)
- goto next;
- if (!tag_get(node, iftag, offset))
- goto next;
- /* Sibling slots never have tags set on them */
- if (radix_tree_is_internal_node(child)) {
- node = entry_to_node(child);
- continue;
- }
-
- tagged++;
- node_tag_set(root, node, settag, offset);
- next:
- /* Go to next entry in node */
- index = ((index >> node->shift) + 1) << node->shift;
- /* Overflow can happen when last_index is ~0UL... */
- if (index > last_index || !index)
- break;
- offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
- while (offset == 0) {
- /*
- * We've fully scanned this node. Go up. Because
- * last_index is guaranteed to be in the tree, what
- * we do below cannot wander astray.
- */
- node = node->parent;
- offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
- }
- if (is_sibling_entry(node, node->slots[offset]))
- goto next;
- if (tagged >= nr_to_tag)
- break;
- }
-
- *first_indexp = index;
-
- return tagged;
-}
-EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
-
-/**
* radix_tree_gang_lookup - perform multiple lookup on a radix tree
* @root: radix tree root
* @results: where the results of the lookup are placed
diff --git a/mm/page-writeback.c b/mm/page-writeback.c
index 439cc63..c593715 100644
--- a/mm/page-writeback.c
+++ b/mm/page-writeback.c
@@ -2105,18 +2105,26 @@ void tag_pages_for_writeback(struct address_space *mapping,
pgoff_t start, pgoff_t end)
{
#define WRITEBACK_TAG_BATCH 4096
- unsigned long tagged;
-
- do {
- spin_lock_irq(&mapping->tree_lock);
- tagged = radix_tree_range_tag_if_tagged(&mapping->page_tree,
- &start, end, WRITEBACK_TAG_BATCH,
- PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
+ unsigned long tagged = 0;
+ struct radix_tree_iter iter;
+ void **slot;
+
+ spin_lock_irq(&mapping->tree_lock);
+ radix_tree_for_each_tagged(slot, &mapping->page_tree, &iter, start,
+ PAGECACHE_TAG_DIRTY) {
+ if (iter.index > end)
+ break;
+ radix_tree_iter_tag_set(&mapping->page_tree, &iter,
+ PAGECACHE_TAG_TOWRITE);
+ tagged++;
+ if ((tagged % WRITEBACK_TAG_BATCH) != 0)
+ continue;
+ slot = radix_tree_iter_next(slot, &iter);
spin_unlock_irq(&mapping->tree_lock);
- WARN_ON_ONCE(tagged > WRITEBACK_TAG_BATCH);
cond_resched();
- /* We check 'start' to handle wrapping when end == ~0UL */
- } while (tagged >= WRITEBACK_TAG_BATCH && start);
+ spin_lock_irq(&mapping->tree_lock);
+ }
+ spin_unlock_irq(&mapping->tree_lock);
}
EXPORT_SYMBOL(tag_pages_for_writeback);
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 93a77f9..7d14812 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -205,8 +205,7 @@ void copy_tag_check(void)
}
// printf("\ncopying tags...\n");
- cur = start;
- tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1);
+ tagged = tag_tagged_items(&tree, start, end, ITEMS, 0, 1);
// printf("checking copied tags\n");
assert(tagged == count);
@@ -214,16 +213,13 @@ void copy_tag_check(void)
/* Copy tags in several rounds */
// printf("\ncopying tags...\n");
- cur = start;
- do {
- tmp = rand() % (count/10+2);
- tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2);
- } while (tmp == tagged);
+ tmp = rand() % (count / 10 + 2);
+ tagged = tag_tagged_items(&tree, start, end, tmp, 0, 2);
+ assert(tagged == count);
// printf("%lu %lu %lu\n", tagged, tmp, count);
// printf("checking copied tags\n");
check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
- assert(tagged < tmp);
verify_tag_consistency(&tree, 0);
verify_tag_consistency(&tree, 1);
verify_tag_consistency(&tree, 2);
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 400de5c..6a0287d 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -26,7 +26,6 @@ static void __multiorder_tag_test(int index, int order)
{
RADIX_TREE(tree, GFP_KERNEL);
int base, err, i;
- unsigned long first = 0;
/* our canonical entry */
base = index & ~((1 << order) - 1);
@@ -60,7 +59,7 @@ static void __multiorder_tag_test(int index, int order)
assert(!radix_tree_tag_get(&tree, i, 1));
}
- assert(radix_tree_range_tag_if_tagged(&tree, &first, ~0UL, 10, 0, 1) == 1);
+ assert(tag_tagged_items(&tree, 0, ~0UL, 10, 0, 1) == 1);
assert(radix_tree_tag_clear(&tree, index, 0));
for_each_index(i, base, order) {
@@ -252,7 +251,6 @@ void multiorder_tagged_iteration(void)
RADIX_TREE(tree, GFP_KERNEL);
struct radix_tree_iter iter;
void **slot;
- unsigned long first = 0;
int i, j;
printf("Multiorder tagged iteration test\n");
@@ -297,8 +295,8 @@ void multiorder_tagged_iteration(void)
}
}
- radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
- MT_NUM_ENTRIES, 1, 2);
+ assert(tag_tagged_items(&tree, 0, ~0UL, TAG_ENTRIES, 1, 2) ==
+ TAG_ENTRIES);
for (j = 0; j < 256; j++) {
int mask, k;
@@ -325,9 +323,8 @@ void multiorder_tagged_iteration(void)
}
}
- first = 1;
- radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
- MT_NUM_ENTRIES, 1, 0);
+ assert(tag_tagged_items(&tree, 1, ~0UL, MT_NUM_ENTRIES * 2, 1, 0)
+ == TAG_ENTRIES);
i = 0;
radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
assert(iter.index == tag_index[i]);
diff --git a/tools/testing/radix-tree/regression2.c b/tools/testing/radix-tree/regression2.c
index 63bf347..5cd2c0f 100644
--- a/tools/testing/radix-tree/regression2.c
+++ b/tools/testing/radix-tree/regression2.c
@@ -50,6 +50,7 @@
#include <stdio.h>
#include "regression.h"
+#include "test.h"
#define PAGECACHE_TAG_DIRTY 0
#define PAGECACHE_TAG_WRITEBACK 1
@@ -90,7 +91,7 @@ void regression2_test(void)
/* 1. */
start = 0;
end = max_slots - 2;
- radix_tree_range_tag_if_tagged(&mt_tree, &start, end, 1,
+ tag_tagged_items(&mt_tree, start, end, 1,
PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
/* 2. */
diff --git a/tools/testing/radix-tree/tag_check.c b/tools/testing/radix-tree/tag_check.c
index 186f6e4..b047b2d 100644
--- a/tools/testing/radix-tree/tag_check.c
+++ b/tools/testing/radix-tree/tag_check.c
@@ -23,7 +23,7 @@ __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
item_tag_set(tree, index, tag);
ret = item_tag_get(tree, index, tag);
assert(ret != 0);
- ret = radix_tree_range_tag_if_tagged(tree, &first, ~0UL, 10, tag, !tag);
+ ret = tag_tagged_items(tree, first, ~0UL, 10, tag, !tag);
assert(ret == 1);
ret = item_tag_get(tree, index, !tag);
assert(ret != 0);
@@ -320,7 +320,7 @@ static void single_check(void)
assert(ret == 0);
verify_tag_consistency(&tree, 0);
verify_tag_consistency(&tree, 1);
- ret = radix_tree_range_tag_if_tagged(&tree, &first, 10, 10, 0, 1);
+ ret = tag_tagged_items(&tree, first, 10, 10, 0, 1);
assert(ret == 1);
ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
assert(ret == 1);
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index a68ed3b..322c34b 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -142,6 +142,31 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start,
assert(nfound == 0);
}
+/* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */
+int tag_tagged_items(struct radix_tree_root *root,
+ unsigned long start, unsigned long end, unsigned batch,
+ unsigned iftag, unsigned thentag)
+{
+ unsigned long tagged = 0;
+ struct radix_tree_iter iter;
+ void **slot;
+
+ if (batch == 0)
+ batch = 1;
+
+ radix_tree_for_each_tagged(slot, root, &iter, start, iftag) {
+ if (iter.index > end)
+ break;
+ radix_tree_iter_tag_set(root, &iter, thentag);
+ tagged++;
+ if ((tagged % batch) != 0)
+ continue;
+ slot = radix_tree_iter_next(slot, &iter);
+ }
+
+ return tagged;
+}
+
/* Use the same pattern as find_swap_entry() in mm/shmem.c */
unsigned long find_item(struct radix_tree_root *root, void *item)
{
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index ccdd3c1..1faf0a3 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -27,6 +27,9 @@ 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);
+int tag_tagged_items(struct radix_tree_root *, unsigned long start,
+ unsigned long end, unsigned batch,
+ unsigned iftag, unsigned thentag);
unsigned long find_item(struct radix_tree_root *, void *item);
void tag_check(void);
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 13/29] radix-tree: Fix typo |
| Message-ID | <sEh23-uC-53@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com> --- lib/radix-tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6d73575..e917c56 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1147,7 +1147,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root, * because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG. * * This condition also used by radix_tree_next_slot() to stop - * contiguous iterating, and forbid swithing to the next chunk. + * contiguous iterating, and forbid switching to the next chunk. */ index = iter->next_index; if (!index && iter->index) -- 2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() |
| Message-ID | <sEh23-uC-61@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <mawilcox@microsoft.com>
idr_find_slowpath() is not intended to be part of the public API, it's
an implementation detail. There's no reason to skip straight to the
slowpath here.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
drivers/char/tpm/tpm-chip.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/drivers/char/tpm/tpm-chip.c b/drivers/char/tpm/tpm-chip.c
index e595013..447b6ca 100644
--- a/drivers/char/tpm/tpm-chip.c
+++ b/drivers/char/tpm/tpm-chip.c
@@ -84,7 +84,7 @@ EXPORT_SYMBOL_GPL(tpm_put_ops);
*
* The return'd chip has been tpm_try_get_ops'd and must be released via
* tpm_put_ops
- */
+ */
struct tpm_chip *tpm_chip_find_get(int chip_num)
{
struct tpm_chip *chip, *res = NULL;
@@ -103,7 +103,7 @@ struct tpm_chip *tpm_chip_find_get(int chip_num)
}
} while (chip_prev != chip_num);
} else {
- chip = idr_find_slowpath(&dev_nums_idr, chip_num);
+ chip = idr_find(&dev_nums_idr, chip_num);
if (chip && !tpm_try_get_ops(chip))
res = chip;
}
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 04/29] radix tree test suite: Free preallocated nodes |
| Message-ID | <sEh23-uC-59@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@infradead.org>
It can be a source of mild concern when the test suite shows that we're
leaking nodes. While poring over the source code looking for leaks
can lead to some fascinating bugs being discovered, sometimes the leak
is simply that these nodes were preallocated and are sitting on the
per-CPU list. Free them by faking a CPU_DEAD event.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
tools/testing/radix-tree/main.c | 3 +++
tools/testing/radix-tree/test.h | 4 ++++
2 files changed, 7 insertions(+)
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 64ffe67..2930560 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -344,6 +344,9 @@ int main(int argc, char **argv)
iteration_test();
single_thread_tests(long_run);
+ /* Free any remaining preallocated nodes */
+ radix_tree_callback(NULL, CPU_DEAD, NULL);
+
sleep(1);
printf("after sleep(1): %d allocated, preempt %d\n",
nr_allocated, preempt_count);
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 217fb24..8cd666a 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -2,6 +2,8 @@
#include <linux/types.h>
#include <linux/radix-tree.h>
#include <linux/rcupdate.h>
+#include <linux/notifier.h>
+#include <linux/cpu.h>
struct item {
unsigned long index;
@@ -44,3 +46,5 @@ 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 *);
unsigned long shift_maxindex(unsigned int shift);
+int radix_tree_callback(struct notifier_block *nfb,
+ unsigned long action, void *hcpu);
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() |
| Message-ID | <sEh23-uC-63@gated-at.bofh.it> |
| In reply to | #1523884 |
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.
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
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 |
| Message-ID | <sEh22-uC-27@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com> In preparation for merging the IDR and radix tree, reduce the fanout at each level from 256 to 64. If this causes a performance problem then a bisect will point to this commit, and we'll have a better idea about what we might do to fix it. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- include/linux/idr.h | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/include/linux/idr.h b/include/linux/idr.h index 1eb755f..3c01b89 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -18,12 +18,11 @@ #include <linux/rcupdate.h> /* - * We want shallower trees and thus more bits covered at each layer. 8 - * bits gives us large enough first layer for most use cases and maximum - * tree depth of 4. Each idr_layer is slightly larger than 2k on 64bit and - * 1k on 32bit. + * Using 6 bits at each layer allows us to allocate 7 layers out of each page. + * 8 bits only gave us 3 layers out of every pair of pages, which is less + * efficient except for trees with a largest element between 192-255 inclusive. */ -#define IDR_BITS 8 +#define IDR_BITS 6 #define IDR_SIZE (1 << IDR_BITS) #define IDR_MASK ((1 << IDR_BITS)-1) -- 2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:40 +0100 |
| Subject | [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 |
| Message-ID | <sEh23-uC-55@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com> In preparation for merging the IDR and radix tree, reduce the fanout at each level from 256 to 64. If this causes a performance problem then a bisect will point to this commit, and we'll have a better idea about what we might do to fix it. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> --- include/linux/idr.h | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/include/linux/idr.h b/include/linux/idr.h index 1eb755f..3c01b89 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -18,12 +18,11 @@ #include <linux/rcupdate.h> /* - * We want shallower trees and thus more bits covered at each layer. 8 - * bits gives us large enough first layer for most use cases and maximum - * tree depth of 4. Each idr_layer is slightly larger than 2k on 64bit and - * 1k on 32bit. + * Using 6 bits at each layer allows us to allocate 7 layers out of each page. + * 8 bits only gave us 3 layers out of every pair of pages, which is less + * efficient except for trees with a largest element between 192-255 inclusive. */ -#define IDR_BITS 8 +#define IDR_BITS 6 #define IDR_SIZE (1 << IDR_BITS) #define IDR_MASK ((1 << IDR_BITS)-1) -- 2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:50 +0100 |
| Subject | [PATCH 28/29] radix-tree: Create all_tag_set |
| Message-ID | <sEhbI-xX-9@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:50 +0100 |
| Subject | [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful |
| Message-ID | <sEhbI-xX-1@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:50 +0100 |
| Subject | [PATCH 05/29] radix tree test suite: Make runs more reproducible |
| Message-ID | <sEhbI-xX-7@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@infradead.org>
Instead of reseeding the random number generator every time around the
loop in big_gang_check(), seed it at the beginning of execution. Use
rand_r() and an independent base seed for each thread in iteration_test()
so they don't stomp all over each others state. Since this particular
test depends on the kernel scheduler, the iteration test can't be
reproduced based purely on the random seed, but at least it won't pollute
the other tests.
Print the seed, and allow the seed to be specified so that a run which
hits a problem can be reproduced.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
tools/testing/radix-tree/iteration_check.c | 11 +++++++----
tools/testing/radix-tree/main.c | 9 +++++++--
2 files changed, 14 insertions(+), 6 deletions(-)
diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c
index 9adb8e7..11d570c 100644
--- a/tools/testing/radix-tree/iteration_check.c
+++ b/tools/testing/radix-tree/iteration_check.c
@@ -20,6 +20,7 @@
#define TAG 0
static pthread_mutex_t tree_lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_t threads[NUM_THREADS];
+static unsigned int seeds[3];
RADIX_TREE(tree, GFP_KERNEL);
bool test_complete;
@@ -71,7 +72,7 @@ static void *tagged_iteration_fn(void *arg)
continue;
}
- if (rand() % 50 == 0)
+ if (rand_r(&seeds[0]) % 50 == 0)
slot = radix_tree_iter_next(&iter);
}
rcu_read_unlock();
@@ -111,7 +112,7 @@ static void *untagged_iteration_fn(void *arg)
continue;
}
- if (rand() % 50 == 0)
+ if (rand_r(&seeds[1]) % 50 == 0)
slot = radix_tree_iter_next(&iter);
}
rcu_read_unlock();
@@ -129,7 +130,7 @@ static void *remove_entries_fn(void *arg)
while (!test_complete) {
int pgoff;
- pgoff = rand() % 100;
+ pgoff = rand_r(&seeds[2]) % 100;
pthread_mutex_lock(&tree_lock);
item_delete(&tree, pgoff);
@@ -146,9 +147,11 @@ void iteration_test(void)
printf("Running iteration tests for 10 seconds\n");
- srand(time(0));
test_complete = false;
+ for (i = 0; i < 3; i++)
+ seeds[i] = rand();
+
if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
perror("pthread_create");
exit(1);
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 2930560..5ddec8e 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -67,7 +67,6 @@ void big_gang_check(bool long_run)
for (i = 0; i < (long_run ? 1000 : 3); i++) {
__big_gang_check();
- srand(time(0));
printf("%d ", i);
fflush(stdout);
}
@@ -329,12 +328,18 @@ int main(int argc, char **argv)
{
bool long_run = false;
int opt;
+ unsigned int seed = time(NULL);
- while ((opt = getopt(argc, argv, "l")) != -1) {
+ while ((opt = getopt(argc, argv, "ls:")) != -1) {
if (opt == 'l')
long_run = true;
+ else if (opt == 's')
+ seed = strtoul(optarg, NULL, 0);
}
+ printf("random seed %u\n", seed);
+ srand(seed);
+
rcu_register_thread();
radix_tree_init();
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:50 +0100 |
| Subject | [PATCH 03/29] radix tree test suite: Track preempt_count |
| Message-ID | <sEhbI-xX-17@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@infradead.org>
Rather than simply NOP out preempt_enable() and preempt_disable(),
keep track of preempt_count and display it regularly in case either
the test suite or the code under test is forgetting to balance the
enables & disables. Only found a test-case that was forgetting to
re-enable preemption, but it's a possibility worth checking.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
tools/testing/radix-tree/linux.c | 1 +
tools/testing/radix-tree/linux/preempt.h | 6 +++---
tools/testing/radix-tree/main.c | 30 ++++++++++++++++++++----------
3 files changed, 24 insertions(+), 13 deletions(-)
diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index 3cfb04e..1f32a16 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -9,6 +9,7 @@
#include <urcu/uatomic.h>
int nr_allocated;
+int preempt_count;
void *mempool_alloc(mempool_t *pool, int gfp_mask)
{
diff --git a/tools/testing/radix-tree/linux/preempt.h b/tools/testing/radix-tree/linux/preempt.h
index 6210672..65c04c2 100644
--- a/tools/testing/radix-tree/linux/preempt.h
+++ b/tools/testing/radix-tree/linux/preempt.h
@@ -1,4 +1,4 @@
-/* */
+extern int preempt_count;
-#define preempt_disable() do { } while (0)
-#define preempt_enable() do { } while (0)
+#define preempt_disable() uatomic_inc(&preempt_count)
+#define preempt_enable() uatomic_dec(&preempt_count)
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index daa9010..64ffe67 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -293,27 +293,36 @@ static void single_thread_tests(bool long_run)
{
int i;
- printf("starting single_thread_tests: %d allocated\n", nr_allocated);
+ printf("starting single_thread_tests: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
multiorder_checks();
- printf("after multiorder_check: %d allocated\n", nr_allocated);
+ printf("after multiorder_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
locate_check();
- printf("after locate_check: %d allocated\n", nr_allocated);
+ printf("after locate_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
tag_check();
- printf("after tag_check: %d allocated\n", nr_allocated);
+ printf("after tag_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
gang_check();
- printf("after gang_check: %d allocated\n", nr_allocated);
+ printf("after gang_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
add_and_check();
- printf("after add_and_check: %d allocated\n", nr_allocated);
+ printf("after add_and_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
dynamic_height_check();
- printf("after dynamic_height_check: %d allocated\n", nr_allocated);
+ printf("after dynamic_height_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
big_gang_check(long_run);
- printf("after big_gang_check: %d allocated\n", nr_allocated);
+ printf("after big_gang_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
for (i = 0; i < (long_run ? 2000 : 3); i++) {
copy_tag_check();
printf("%d ", i);
fflush(stdout);
}
- printf("after copy_tag_check: %d allocated\n", nr_allocated);
+ printf("after copy_tag_check: %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
}
int main(int argc, char **argv)
@@ -336,7 +345,8 @@ int main(int argc, char **argv)
single_thread_tests(long_run);
sleep(1);
- printf("after sleep(1): %d allocated\n", nr_allocated);
+ printf("after sleep(1): %d allocated, preempt %d\n",
+ nr_allocated, preempt_count);
rcu_unregister_thread();
exit(0);
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:50 +0100 |
| Subject | [PATCH 09/29] radix tree test suite: Use common find-bit code |
| Message-ID | <sEhbI-xX-15@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
Remove the old find_next_bit code in favour of linking in the find_bit
code from tools/lib.
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
tools/testing/radix-tree/Makefile | 7 ++-
tools/testing/radix-tree/find_next_bit.c | 57 ----------------------
tools/testing/radix-tree/linux/bitops.h | 40 +++++++++------
tools/testing/radix-tree/linux/bitops/non-atomic.h | 13 +++--
tools/testing/radix-tree/linux/kernel.h | 11 +++++
5 files changed, 48 insertions(+), 80 deletions(-)
delete mode 100644 tools/testing/radix-tree/find_next_bit.c
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 08283a8..3635e4d 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -18,7 +18,12 @@ main: $(OFILES)
clean:
$(RM) -f $(TARGETS) *.o radix-tree.c
-$(OFILES): *.h */*.h ../../../include/linux/radix-tree.h ../../include/linux/*.h
+find_next_bit.o: ../../lib/find_bit.c
+ $(CC) $(CFLAGS) -c -o $@ $<
+
+$(OFILES): *.h */*.h \
+ ../../include/linux/*.h \
+ ../../../include/linux/radix-tree.h
radix-tree.c: ../../../lib/radix-tree.c
sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
diff --git a/tools/testing/radix-tree/find_next_bit.c b/tools/testing/radix-tree/find_next_bit.c
deleted file mode 100644
index d1c2178..0000000
--- a/tools/testing/radix-tree/find_next_bit.c
+++ /dev/null
@@ -1,57 +0,0 @@
-/* find_next_bit.c: fallback find next bit implementation
- *
- * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
- * Written by David Howells (dhowells@redhat.com)
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version
- * 2 of the License, or (at your option) any later version.
- */
-
-#include <linux/types.h>
-#include <linux/bitops.h>
-
-#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
-
-/*
- * Find the next set bit in a memory region.
- */
-unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
- unsigned long offset)
-{
- const unsigned long *p = addr + BITOP_WORD(offset);
- unsigned long result = offset & ~(BITS_PER_LONG-1);
- unsigned long tmp;
-
- if (offset >= size)
- return size;
- size -= result;
- offset %= BITS_PER_LONG;
- if (offset) {
- tmp = *(p++);
- tmp &= (~0UL << offset);
- if (size < BITS_PER_LONG)
- goto found_first;
- if (tmp)
- goto found_middle;
- size -= BITS_PER_LONG;
- result += BITS_PER_LONG;
- }
- while (size & ~(BITS_PER_LONG-1)) {
- if ((tmp = *(p++)))
- goto found_middle;
- result += BITS_PER_LONG;
- size -= BITS_PER_LONG;
- }
- if (!size)
- return result;
- tmp = *p;
-
-found_first:
- tmp &= (~0UL >> (BITS_PER_LONG - size));
- if (tmp == 0UL) /* Are any bits set? */
- return result + size; /* Nope. */
-found_middle:
- return result + __ffs(tmp);
-}
diff --git a/tools/testing/radix-tree/linux/bitops.h b/tools/testing/radix-tree/linux/bitops.h
index 71d58427..a13e9bc 100644
--- a/tools/testing/radix-tree/linux/bitops.h
+++ b/tools/testing/radix-tree/linux/bitops.h
@@ -2,9 +2,14 @@
#define _ASM_GENERIC_BITOPS_NON_ATOMIC_H_
#include <linux/types.h>
+#include <linux/bitops/find.h>
+#include <linux/bitops/hweight.h>
+#include <linux/kernel.h>
-#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
-#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
+#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
+#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
+#define BITS_PER_BYTE 8
+#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
/**
* __set_bit - Set a bit in memory
@@ -17,16 +22,16 @@
*/
static inline void __set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
*p |= mask;
}
static inline void __clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
*p &= ~mask;
}
@@ -42,8 +47,8 @@ static inline void __clear_bit(int nr, volatile unsigned long *addr)
*/
static inline void __change_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
*p ^= mask;
}
@@ -59,8 +64,8 @@ static inline void __change_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
unsigned long old = *p;
*p = old | mask;
@@ -78,8 +83,8 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
unsigned long old = *p;
*p = old & ~mask;
@@ -90,8 +95,8 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
static inline int __test_and_change_bit(int nr,
volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
- unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
+ unsigned long mask = BIT_MASK(nr);
+ unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
unsigned long old = *p;
*p = old ^ mask;
@@ -105,7 +110,7 @@ static inline int __test_and_change_bit(int nr,
*/
static inline int test_bit(int nr, const volatile unsigned long *addr)
{
- return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
+ return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
}
/**
@@ -147,4 +152,9 @@ unsigned long find_next_bit(const unsigned long *addr,
unsigned long size,
unsigned long offset);
+static inline unsigned long hweight_long(unsigned long w)
+{
+ return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
+}
+
#endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */
diff --git a/tools/testing/radix-tree/linux/bitops/non-atomic.h b/tools/testing/radix-tree/linux/bitops/non-atomic.h
index 46a825c..6a1bcb9 100644
--- a/tools/testing/radix-tree/linux/bitops/non-atomic.h
+++ b/tools/testing/radix-tree/linux/bitops/non-atomic.h
@@ -3,7 +3,6 @@
#include <asm/types.h>
-#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
/**
@@ -17,7 +16,7 @@
*/
static inline void __set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
*p |= mask;
@@ -25,7 +24,7 @@ static inline void __set_bit(int nr, volatile unsigned long *addr)
static inline void __clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
*p &= ~mask;
@@ -42,7 +41,7 @@ static inline void __clear_bit(int nr, volatile unsigned long *addr)
*/
static inline void __change_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
*p ^= mask;
@@ -59,7 +58,7 @@ static inline void __change_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
unsigned long old = *p;
@@ -78,7 +77,7 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
*/
static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
unsigned long old = *p;
@@ -90,7 +89,7 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
static inline int __test_and_change_bit(int nr,
volatile unsigned long *addr)
{
- unsigned long mask = BITOP_MASK(nr);
+ unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr);
unsigned long old = *p;
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index dbe4b92..23e77f5 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -47,4 +47,15 @@ static inline int in_interrupt(void)
{
return 0;
}
+
+/*
+ * This looks more complex than it should be. But we need to
+ * get the type for the ~ right in round_down (it needs to be
+ * as wide as the result!), and we want to evaluate the macro
+ * arguments just once each.
+ */
+#define __round_mask(x, y) ((__typeof__(x))((y)-1))
+#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
+#define round_down(x, y) ((x) & ~__round_mask(x, y))
+
#endif /* _KERNEL_H */
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:50 +0100 |
| Subject | [PATCH 27/29] radix tree test suite: Add some more functionality |
| Message-ID | <sEhbJ-xX-37@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
IDR needs more functionality from the kernel: kmalloc()/kfree(), and xchg().
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
tools/testing/radix-tree/linux.c | 15 +++++++++++++++
tools/testing/radix-tree/linux/kernel.h | 3 +++
tools/testing/radix-tree/linux/slab.h | 3 +++
3 files changed, 21 insertions(+)
diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index 1f32a16..ff0452e 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -54,6 +54,21 @@ void kmem_cache_free(struct kmem_cache *cachep, void *objp)
free(objp);
}
+void *kmalloc(size_t size, gfp_t gfp)
+{
+ void *ret = malloc(size);
+ uatomic_inc(&nr_allocated);
+ return ret;
+}
+
+void kfree(void *p)
+{
+ if (!p)
+ return;
+ uatomic_dec(&nr_allocated);
+ free(p);
+}
+
struct kmem_cache *
kmem_cache_create(const char *name, size_t size, size_t offset,
unsigned long flags, void (*ctor)(void *))
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index 23e77f5..9b43b49 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -8,6 +8,7 @@
#include <limits.h>
#include "../../include/linux/compiler.h"
+#include "../../include/linux/err.h"
#include "../../../include/linux/kconfig.h"
#ifdef BENCHMARK
@@ -58,4 +59,6 @@ static inline int in_interrupt(void)
#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1)
#define round_down(x, y) ((x) & ~__round_mask(x, y))
+#define xchg(ptr, x) uatomic_xchg(ptr, x)
+
#endif /* _KERNEL_H */
diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h
index 452e2bf..446639f 100644
--- a/tools/testing/radix-tree/linux/slab.h
+++ b/tools/testing/radix-tree/linux/slab.h
@@ -7,6 +7,9 @@
#define SLAB_PANIC 2
#define SLAB_RECLAIM_ACCOUNT 0x00020000UL /* Objects are reclaimable */
+void *kmalloc(size_t size, gfp_t);
+void kfree(void *);
+
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:50 +0100 |
| Subject | [PATCH 12/29] radix-tree: Add radix_tree_split_preload() |
| Message-ID | <sEhbI-xX-21@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
Calculate how many nodes we need to allocate to split an old_order entry
into multiple entries, each of size new_order. The test suite checks that
we allocated exactly the right number of nodes; neither too many (checked
by rtp->nr == 0), nor too few (checked by comparing nr_allocated before
and after the call to radix_tree_split()).
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
include/linux/radix-tree.h | 1 +
lib/radix-tree.c | 24 +++++++++++++++++++++++-
tools/testing/radix-tree/multiorder.c | 32 ++++++++++++++++++++++++++++++--
tools/testing/radix-tree/test.h | 5 +++++
4 files changed, 59 insertions(+), 3 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index f5518f1..8ffb051 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -319,6 +319,7 @@ static inline void radix_tree_preload_end(void)
preempt_enable();
}
+int radix_tree_split_preload(unsigned old_order, unsigned new_order, gfp_t);
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,
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index eaf0f353..6d73575 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -344,7 +344,7 @@ radix_tree_node_free(struct radix_tree_node *node)
* To make use of this facility, the radix tree must be initialised without
* __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE().
*/
-static int __radix_tree_preload(gfp_t gfp_mask, int nr)
+static int __radix_tree_preload(gfp_t gfp_mask, unsigned nr)
{
struct radix_tree_preload *rtp;
struct radix_tree_node *node;
@@ -410,6 +410,28 @@ int radix_tree_maybe_preload(gfp_t gfp_mask)
}
EXPORT_SYMBOL(radix_tree_maybe_preload);
+#ifdef CONFIG_RADIX_TREE_MULTIORDER
+/*
+ * Preload with enough objects to ensure that we can split a single entry
+ * of order @old_order into many entries of size @new_order
+ */
+int radix_tree_split_preload(unsigned int old_order, unsigned int new_order,
+ gfp_t gfp_mask)
+{
+ unsigned top = 1 << (old_order % RADIX_TREE_MAP_SHIFT);
+ unsigned layers = (old_order / RADIX_TREE_MAP_SHIFT) -
+ (new_order / RADIX_TREE_MAP_SHIFT);
+ unsigned nr = 0;
+
+ WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
+ BUG_ON(new_order >= old_order);
+
+ while (layers--)
+ nr = nr * RADIX_TREE_MAP_SIZE + 1;
+ return __radix_tree_preload(gfp_mask, top * nr);
+}
+#endif
+
/*
* The same as function above, but preload number of nodes required to insert
* (1 << order) continuous naturally-aligned elements.
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index d9e8155..25e0463 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -356,18 +356,46 @@ static void multiorder_join(void)
}
}
+static void check_mem(unsigned old_order, unsigned new_order, unsigned alloc)
+{
+ struct radix_tree_preload *rtp = &radix_tree_preloads;
+ if (rtp->nr != 0)
+ printf("split(%u %u) remaining %u\n", old_order, new_order,
+ rtp->nr);
+ /*
+ * Can't check for equality here as some nodes may have been
+ * RCU-freed while we ran. But we should never finish with more
+ * nodes allocated since they should have all been preloaded.
+ */
+ if (nr_allocated > alloc)
+ printf("split(%u %u) allocated %u %u\n", old_order, new_order,
+ alloc, nr_allocated);
+}
+
static void __multiorder_split(int old_order, int new_order)
{
- RADIX_TREE(tree, GFP_KERNEL);
+ RADIX_TREE(tree, GFP_ATOMIC);
void **slot;
struct radix_tree_iter iter;
+ unsigned alloc;
+
+ radix_tree_preload(GFP_KERNEL);
+ assert(item_insert_order(&tree, 0, old_order) == 0);
+ radix_tree_preload_end();
+
+ /* Wipe out the preloaded cache or it'll confuse check_mem() */
+ radix_tree_callback(NULL, CPU_DEAD, NULL);
- item_insert_order(&tree, 0, old_order);
radix_tree_tag_set(&tree, 0, 2);
+
+ radix_tree_split_preload(old_order, new_order, GFP_KERNEL);
+ alloc = nr_allocated;
radix_tree_split(&tree, 0, new_order);
+ check_mem(old_order, new_order, alloc);
radix_tree_for_each_slot(slot, &tree, &iter, 0) {
radix_tree_replace_slot(slot, item_create(iter.index));
}
+ radix_tree_preload_end();
item_kill_tree(&tree);
}
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index f2dc35f..33d2b6b 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -49,3 +49,8 @@ unsigned long node_maxindex(struct radix_tree_node *);
unsigned long shift_maxindex(unsigned int shift);
int radix_tree_callback(struct notifier_block *nfb,
unsigned long action, void *hcpu);
+struct radix_tree_preload {
+ unsigned nr;
+ struct radix_tree_node *nodes;
+};
+extern struct radix_tree_preload radix_tree_preloads;
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:50 +0100 |
| Subject | [PATCH 01/29] tools: Add WARN_ON_ONCE |
| Message-ID | <sEhbI-xX-23@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
The radix tree uses its own buggy WARN_ON_ONCE. Replace it with the
definition from asm-generic/bug.h
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
tools/include/asm/bug.h | 11 +++++++++++
tools/testing/radix-tree/Makefile | 2 +-
tools/testing/radix-tree/linux/bug.h | 2 +-
tools/testing/radix-tree/linux/types.h | 2 --
4 files changed, 13 insertions(+), 4 deletions(-)
diff --git a/tools/include/asm/bug.h b/tools/include/asm/bug.h
index 9e5f484..beda1a8 100644
--- a/tools/include/asm/bug.h
+++ b/tools/include/asm/bug.h
@@ -12,6 +12,17 @@
unlikely(__ret_warn_on); \
})
+#define WARN_ON_ONCE(condition) ({ \
+ static int __warned; \
+ int __ret_warn_once = !!(condition); \
+ \
+ if (unlikely(__ret_warn_once && !__warned)) { \
+ __warned = true; \
+ WARN_ON(1); \
+ } \
+ unlikely(__ret_warn_once); \
+})
+
#define WARN_ONCE(condition, format...) ({ \
static int __warned; \
int __ret_warn_once = !!(condition); \
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index f2e07f2..3c338dc 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -1,5 +1,5 @@
-CFLAGS += -I. -g -O2 -Wall -D_LGPL_SOURCE
+CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE
LDFLAGS += -lpthread -lurcu
TARGETS = main
OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \
diff --git a/tools/testing/radix-tree/linux/bug.h b/tools/testing/radix-tree/linux/bug.h
index ccbe444..23b8ed5 100644
--- a/tools/testing/radix-tree/linux/bug.h
+++ b/tools/testing/radix-tree/linux/bug.h
@@ -1 +1 @@
-#define WARN_ON_ONCE(x) assert(x)
+#include "asm/bug.h"
diff --git a/tools/testing/radix-tree/linux/types.h b/tools/testing/radix-tree/linux/types.h
index faa0b6f..8491d89 100644
--- a/tools/testing/radix-tree/linux/types.h
+++ b/tools/testing/radix-tree/linux/types.h
@@ -6,8 +6,6 @@
#define __rcu
#define __read_mostly
-#define BITS_PER_LONG (sizeof(long) * 8)
-
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
--
2.10.2
[toc] | [prev] | [next] | [standalone]
| From | Matthew Wilcox <mawilcox@linuxonhyperv.com> |
|---|---|
| Date | 2016-11-16 23:50 +0100 |
| Subject | [PATCH 15/29] radix-tree: Create node_tag_set() |
| Message-ID | <sEhbI-xX-31@gated-at.bofh.it> |
| In reply to | #1523884 |
From: Matthew Wilcox <willy@linux.intel.com>
Similar to node_tag_clear(), factor node_tag_set() out of
radix_tree_range_tag_if_tagged().
Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
lib/radix-tree.c | 41 +++++++++++++++++++----------------------
1 file changed, 19 insertions(+), 22 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index baf4ba1..bf1303f 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1028,6 +1028,22 @@ static void node_tag_clear(struct radix_tree_root *root,
root_tag_clear(root, tag);
}
+static void node_tag_set(struct radix_tree_root *root,
+ struct radix_tree_node *node,
+ unsigned int tag, unsigned int offset)
+{
+ while (node) {
+ if (tag_get(node, tag, offset))
+ return;
+ tag_set(node, tag, offset);
+ offset = node->offset;
+ node = node->parent;
+ }
+
+ if (!root_tag_get(root, tag))
+ root_tag_set(root, tag);
+}
+
/**
* radix_tree_tag_clear - clear a tag on a radix tree node
* @root: radix tree root
@@ -1268,7 +1284,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
unsigned long nr_to_tag,
unsigned int iftag, unsigned int settag)
{
- struct radix_tree_node *parent, *node, *child;
+ struct radix_tree_node *node, *child;
unsigned long maxindex;
unsigned long tagged = 0;
unsigned long index = *first_indexp;
@@ -1303,22 +1319,8 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
continue;
}
- /* tag the leaf */
tagged++;
- tag_set(node, settag, offset);
-
- /* walk back up the path tagging interior nodes */
- parent = node;
- for (;;) {
- offset = parent->offset;
- parent = parent->parent;
- if (!parent)
- break;
- /* stop if we find a node with the tag already set */
- if (tag_get(parent, settag, offset))
- break;
- tag_set(parent, settag, offset);
- }
+ node_tag_set(root, node, settag, offset);
next:
/* Go to next entry in node */
index = ((index >> node->shift) + 1) << node->shift;
@@ -1340,12 +1342,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
if (tagged >= nr_to_tag)
break;
}
- /*
- * We need not to tag the root tag if there is no tag which is set with
- * settag within the range from *first_indexp to last_index.
- */
- if (tagged > 0)
- root_tag_set(root, settag);
+
*first_indexp = index;
return tagged;
--
2.10.2
[toc] | [prev] | [next] | [standalone]
Page 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
Back to top | Article view | linux.kernel
csiph-web