Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1523884 > unrolled thread

[PATCH 00/29] Improve radix tree for 4.10

Started byMatthew Wilcox <mawilcox@linuxonhyperv.com>
First post2016-11-16 23:30 +0100
Last post2016-11-16 23:50 +0100
Articles 6 on this page of 66 — 4 participants

Back to article view | Back to linux.kernel

Contents

  [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 4 of 4 — ← Prev page 1 2 3 [4]

#1523946 — [PATCH 11/29] radix-tree: Add radix_tree_split

FromMatthew Wilcox <mawilcox@linuxonhyperv.com>
Date2016-11-16 23:50 +0100
Subject[PATCH 11/29] radix-tree: Add radix_tree_split
Message-ID<sEhbI-xX-27@gated-at.bofh.it>
In reply to#1523884
From: Matthew Wilcox <willy@linux.intel.com>

This new function splits a larger multiorder entry into smaller entries
(potentially multi-order entries).  These entries are initialised to
RADIX_TREE_RETRY to ensure that RCU walkers who see this state aren't
confused.  The caller should then call radix_tree_for_each_slot() and
radix_tree_replace_slot() in order to turn these retry entries into the
intended new entries.  Tags are replicated from the original multiorder
entry into each new entry.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
---
 include/linux/radix-tree.h            |   3 +
 lib/radix-tree.c                      | 109 ++++++++++++++++++++++++++++++++--
 tools/testing/radix-tree/multiorder.c |  26 ++++++++
 3 files changed, 134 insertions(+), 4 deletions(-)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 1efd81f..f5518f1 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -319,8 +319,11 @@ static inline void radix_tree_preload_end(void)
 	preempt_enable();
 }
 
+int radix_tree_split(struct radix_tree_root *, unsigned long index,
+			unsigned new_order);
 int radix_tree_join(struct radix_tree_root *, unsigned long index,
 			unsigned new_order, void *);
+
 /**
  * struct radix_tree_iter - radix tree iterator state
  *
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 6a76252..eaf0f353 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -231,7 +231,10 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
 		void *entry = node->slots[i];
 		if (!entry)
 			continue;
-		if (is_sibling_entry(node, entry)) {
+		if (entry == RADIX_TREE_RETRY) {
+			pr_debug("radix retry offset %ld indices %ld-%ld\n",
+					i, first, last);
+		} else if (is_sibling_entry(node, entry)) {
 			pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
 					entry, i,
 					*(void **)entry_to_node(entry),
@@ -641,7 +644,10 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot,
 	unsigned i, n, tag, offset, tags = 0;
 
 	if (node) {
-		n = 1 << (order - node->shift);
+		if (order > node->shift)
+			n = 1 << (order - node->shift);
+		else
+			n = 1;
 		offset = get_slot_offset(node, slot);
 	} else {
 		n = 1;
@@ -680,7 +686,8 @@ static inline int insert_entries(struct radix_tree_node *node, void **slot,
 					tag_set(node, tag, offset);
 		}
 		if (radix_tree_is_internal_node(old) &&
-					!is_sibling_entry(node, old))
+					!is_sibling_entry(node, old) &&
+					(old != RADIX_TREE_RETRY))
 			radix_tree_free_nodes(old);
 	}
 	if (node)
@@ -843,6 +850,98 @@ int radix_tree_join(struct radix_tree_root *root, unsigned long index,
 
 	return error;
 }
+
+int radix_tree_split(struct radix_tree_root *root, unsigned long index,
+				unsigned order)
+{
+	struct radix_tree_node *parent, *node, *child;
+	void **slot;
+	unsigned int offset, end;
+	unsigned n, tag, tags = 0;
+
+	if (!__radix_tree_lookup(root, index, &parent, &slot))
+		return -ENOENT;
+	if (!parent)
+		return -ENOENT;
+
+	offset = get_slot_offset(parent, slot);
+
+	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+		if (tag_get(parent, tag, offset))
+			tags |= 1 << tag;
+
+	for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) {
+		if (!is_sibling_entry(parent, parent->slots[end]))
+			break;
+		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+			if (tags & (1 << tag))
+				tag_set(parent, tag, end);
+		/* rcu_assign_pointer ensures tags are set before RETRY */
+		rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY);
+	}
+
+	if (order == parent->shift)
+		return 0;
+	if (order > parent->shift) {
+		while (offset < end)
+			offset += insert_entries(parent, &parent->slots[offset],
+					RADIX_TREE_RETRY, order, true);
+		return 0;
+	}
+
+	node = parent;
+
+	for (;;) {
+		if (node->shift > order) {
+			child = radix_tree_node_alloc(root);
+			if (!child)
+				goto nomem;
+			child->shift = node->shift - RADIX_TREE_MAP_SHIFT;
+			child->offset = offset;
+			child->count = 0;
+			child->parent = node;
+			if (node != parent) {
+				node->count++;
+				node->slots[offset] = node_to_entry(child);
+				for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+					if (tags & (1 << tag))
+						tag_set(node, tag, offset);
+			}
+
+			node = child;
+			offset = 0;
+			continue;
+		}
+
+		n = insert_entries(node, &node->slots[offset],
+					RADIX_TREE_RETRY, order, false);
+		BUG_ON(n > RADIX_TREE_MAP_SIZE);
+
+		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+			if (tags & (1 << tag))
+				tag_set(node, tag, offset);
+		offset += n;
+
+		while (offset == RADIX_TREE_MAP_SIZE) {
+			if (node == parent)
+				break;
+			offset = node->offset;
+			child = node;
+			node = node->parent;
+			rcu_assign_pointer(node->slots[offset],
+						node_to_entry(child));
+			offset++;
+		}
+		if ((node == parent) && (offset == end))
+			return 0;
+	}
+
+ nomem:
+	/* Shouldn't happen; did user forget to preload? */
+	/* TODO: free all the allocated nodes */
+	WARN_ON(1);
+	return -ENOMEM;
+}
 #endif
 
 /**
@@ -1081,8 +1180,10 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
 			child = rcu_dereference_raw(node->slots[offset]);
 		}
 
-		if ((child == NULL) || (child == RADIX_TREE_RETRY))
+		if (!child)
 			goto restart;
+		if (child == RADIX_TREE_RETRY)
+			break;
 	} while (radix_tree_is_internal_node(child));
 
 	/* Update the iterator state */
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 4c66acc..d9e8155 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -356,6 +356,31 @@ static void multiorder_join(void)
 	}
 }
 
+static void __multiorder_split(int old_order, int new_order)
+{
+	RADIX_TREE(tree, GFP_KERNEL);
+	void **slot;
+	struct radix_tree_iter iter;
+
+	item_insert_order(&tree, 0, old_order);
+	radix_tree_tag_set(&tree, 0, 2);
+	radix_tree_split(&tree, 0, new_order);
+	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
+		radix_tree_replace_slot(slot, item_create(iter.index));
+	}
+
+	item_kill_tree(&tree);
+}
+
+static void multiorder_split(void)
+{
+	int i, j;
+
+	for (i = 9; i < 19; i++)
+		for (j = 0; j < i; j++)
+			__multiorder_split(i, j);
+}
+
 void multiorder_checks(void)
 {
 	int i;
@@ -374,4 +399,5 @@ void multiorder_checks(void)
 	multiorder_iteration();
 	multiorder_tagged_iteration();
 	multiorder_join();
+	multiorder_split();
 }
-- 
2.10.2

[toc] | [prev] | [next] | [standalone]

#1523947

FromMatthew Wilcox <mawilcox@linuxonhyperv.com>
Date2016-11-16 23:50 +0100
Message-ID<sEhbJ-xX-39@gated-at.bofh.it>
In reply to#1523884
From: Matthew Wilcox <mawilcox@microsoft.com>

Hi Andrew,

Please include these patches in the -mm tree for 4.10.  Mostly these are
improvements; the only bug fixes in here relate to multiorder entries
(which as far as I'm aware remain unused).  The IDR rewrite has the
highest potential for causing mayhem as the test suite is quite spartan.
We have an Outreachy intern scheduled to work on the test suite for the
2016 winter season, so hopefully it will improve soon.

I posted a series of patches to improve the radix tree code two months
ago, and Konstantin had the quite reasonable objection that they slowed
down the iterators.  He helpfully sent out the benchmark he used.
With this revision of the patchset, I have slightly improved performance
on his benchmark.

Noteworthy changes from the last revision of the patchset:

 - Fix the existing radix tree iterator design instead of rewriting it
 - Avoid adding the new radix_tree_for_each_tagged_max iterator; just
   check in the one caller whether we've exceeded the limit.
 - Change the name of radix_tree_iter_save() back to
   radix_tree_iter_next().  I went back and forth on this one, and could
   easily be convinced to rename it as I think radix_tree_iter_save()
   makes more sense to the callers.
 - Add radix_tree_iter_delete() instead of poking around the internals
   of the radix tree in ida_destroy()
 - Add accessors for the idr cyclic allocation cursor

Patches 1-9: Test suite improvements, including Konstantin's benchmark
Patches 10-12: join/split (Kirill wants these for huge page cache)
Patches 13-17: General improvements to the radix tree
Patches 18-22: Radix tree iterator improvements
Patches 23-29: Replace the IDR with the radix tree

Konstantin Khlebnikov (1):
  radix tree test suite: benchmark for iterator

Matthew Wilcox (28):
  tools: Add WARN_ON_ONCE
  radix tree test suite: Allow GFP_ATOMIC allocations to fail
  radix tree test suite: Track preempt_count
  radix tree test suite: Free preallocated nodes
  radix tree test suite: Make runs more reproducible
  radix tree test suite: Use rcu_barrier
  tools: Add more bitmap functions
  radix tree test suite: Use common find-bit code
  radix-tree: Add radix_tree_join
  radix-tree: Add radix_tree_split
  radix-tree: Add radix_tree_split_preload()
  radix-tree: Fix typo
  radix-tree: Move rcu_head into a union with private_list
  radix-tree: Create node_tag_set()
  radix-tree: Make radix_tree_find_next_bit more useful
  radix-tree: Improve dump output
  btrfs: Fix race in btrfs_free_dummy_fs_info()
  radix tree test suite: iteration test misuses RCU
  radix tree: Improve multiorder iterators
  radix-tree: Delete radix_tree_locate_item()
  radix-tree: Delete radix_tree_range_tag_if_tagged()
  idr: Add ida_is_empty
  tpm: Use idr_find(), not idr_find_slowpath()
  rxrpc: Abstract away knowledge of IDR internals
  idr: Reduce the number of bits per level from 8 to 6
  radix tree test suite: Add some more functionality
  radix-tree: Create all_tag_set
  Reimplement IDR and IDA using the radix tree

 drivers/char/tpm/tpm-chip.c                        |    4 +-
 drivers/usb/gadget/function/f_hid.c                |    6 +-
 drivers/usb/gadget/function/f_printer.c            |    6 +-
 fs/btrfs/tests/btrfs-tests.c                       |    1 +
 include/linux/idr.h                                |  156 +--
 include/linux/radix-tree.h                         |  161 ++-
 init/main.c                                        |    3 +-
 lib/idr.c                                          | 1075 ----------------
 lib/radix-tree.c                                   | 1328 +++++++++++++++-----
 mm/khugepaged.c                                    |    2 +-
 mm/page-writeback.c                                |   28 +-
 mm/shmem.c                                         |   32 +-
 net/rxrpc/af_rxrpc.c                               |   11 +-
 net/rxrpc/conn_client.c                            |    4 +-
 tools/include/asm/bug.h                            |   11 +
 tools/include/linux/bitmap.h                       |   26 +
 tools/lib/find_bit.c                               |    8 +
 tools/testing/radix-tree/Makefile                  |   18 +-
 tools/testing/radix-tree/benchmark.c               |   98 ++
 tools/testing/radix-tree/find_next_bit.c           |   57 -
 tools/testing/radix-tree/idr.c                     |  148 +++
 tools/testing/radix-tree/iteration_check.c         |   39 +-
 tools/testing/radix-tree/linux.c                   |   23 +-
 tools/testing/radix-tree/linux/bitops.h            |   40 +-
 tools/testing/radix-tree/linux/bitops/non-atomic.h |   13 +-
 tools/testing/radix-tree/linux/bug.h               |    2 +-
 tools/testing/radix-tree/linux/gfp.h               |   22 +-
 tools/testing/radix-tree/linux/idr.h               |    1 +
 tools/testing/radix-tree/linux/kernel.h            |   20 +
 tools/testing/radix-tree/linux/preempt.h           |    6 +-
 tools/testing/radix-tree/linux/slab.h              |    6 +-
 tools/testing/radix-tree/linux/types.h             |    2 -
 tools/testing/radix-tree/main.c                    |   80 +-
 tools/testing/radix-tree/multiorder.c              |  111 +-
 tools/testing/radix-tree/regression2.c             |    3 +-
 tools/testing/radix-tree/regression3.c             |    6 +-
 tools/testing/radix-tree/tag_check.c               |    9 +-
 tools/testing/radix-tree/test.c                    |   47 +
 tools/testing/radix-tree/test.h                    |   18 +
 39 files changed, 1884 insertions(+), 1747 deletions(-)
 create mode 100644 tools/testing/radix-tree/benchmark.c
 delete mode 100644 tools/testing/radix-tree/find_next_bit.c
 create mode 100644 tools/testing/radix-tree/idr.c
 create mode 100644 tools/testing/radix-tree/linux/idr.h

-- 
2.10.2

[toc] | [prev] | [next] | [standalone]

#1524786

FromMatthew Wilcox <mawilcox@microsoft.com>
Date2016-11-17 21:00 +0100
Message-ID<sEB0K-53b-9@gated-at.bofh.it>
In reply to#1523947
My apologies for the confusion here.  Some of these patches are indeed duplicates of each other.  I had run git format-patch, then noticed a mistake, edited the patch set and ran git format-patch again without emptying the directory of patches, so I ended up sending 36 emails instead of 29.

There were also a couple of small bugs caught by 0day and an infelicity in the rxrpc code pointed out by Dave Howells.  Instead of spamming you all with another 29 emails, the latest version of the patchset can be found here:

http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-11-17

[toc] | [prev] | [next] | [standalone]

#1524847

FromRoss Zwisler <ross.zwisler@linux.intel.com>
Date2016-11-17 23:20 +0100
Message-ID<sEDce-6KN-23@gated-at.bofh.it>
In reply to#1523947
On Wed, Nov 16, 2016 at 04:17:01PM -0800, Matthew Wilcox wrote:
> From: Matthew Wilcox <mawilcox@microsoft.com>
> 
> Hi Andrew,
> 
> Please include these patches in the -mm tree for 4.10.  Mostly these are
> improvements; the only bug fixes in here relate to multiorder entries
> (which as far as I'm aware remain unused).  

My DAX PMD patches use multiorder entries, and are queued for v4.10 merge:

http://www.spinics.net/lists/linux-fsdevel/msg104041.html

[toc] | [prev] | [next] | [standalone]

#1525001

FromMatthew Wilcox <mawilcox@microsoft.com>
Date2016-11-18 05:40 +0100
Message-ID<sEJ7X-2aO-3@gated-at.bofh.it>
In reply to#1524847
From: Ross Zwisler [mailto:ross.zwisler@linux.intel.com]
> On Wed, Nov 16, 2016 at 04:17:01PM -0800, Matthew Wilcox wrote:
> > From: Matthew Wilcox <mawilcox@microsoft.com>
> >
> > Hi Andrew,
> >
> > Please include these patches in the -mm tree for 4.10.  Mostly these are
> > improvements; the only bug fixes in here relate to multiorder entries
> > (which as far as I'm aware remain unused).
> 
> My DAX PMD patches use multiorder entries, and are queued for v4.10 merge:

That's great; the point that I was trying to make was that while there are indeed bug fixes in the patches, they're latent bugs because there are no current users in the tree.  So there's no need to hurry up and get these fixes in, they can wait for 4.10.  I don't think your patches will run into these bugs either because you don't use tags.  I do think that Kirill's patches might hit them though.

[toc] | [prev] | [next] | [standalone]

#1523948 — [PATCH 19/29] radix tree test suite: iteration test misuses RCU

FromMatthew Wilcox <mawilcox@linuxonhyperv.com>
Date2016-11-16 23:50 +0100
Subject[PATCH 19/29] radix tree test suite: iteration test misuses RCU
Message-ID<sEhbJ-xX-35@gated-at.bofh.it>
In reply to#1523884
From: Matthew Wilcox <mawilcox@microsoft.com>

Each thread needs to register itself with RCU, otherwise the reading
thread's read lock has no effect and the freeing thread will free the
memory in the tree without waiting for the read lock to be dropped.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/testing/radix-tree/iteration_check.c | 28 ++++++++++++++++++++++++++--
 1 file changed, 26 insertions(+), 2 deletions(-)

diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c
index 11d570c..df71cb8 100644
--- a/tools/testing/radix-tree/iteration_check.c
+++ b/tools/testing/radix-tree/iteration_check.c
@@ -29,6 +29,8 @@ static void *add_entries_fn(void *arg)
 {
 	int pgoff;
 
+	rcu_register_thread();
+
 	while (!test_complete) {
 		for (pgoff = 0; pgoff < 100; pgoff++) {
 			pthread_mutex_lock(&tree_lock);
@@ -38,6 +40,8 @@ static void *add_entries_fn(void *arg)
 		}
 	}
 
+	rcu_unregister_thread();
+
 	return NULL;
 }
 
@@ -53,6 +57,8 @@ static void *tagged_iteration_fn(void *arg)
 	struct radix_tree_iter iter;
 	void **slot;
 
+	rcu_register_thread();
+
 	while (!test_complete) {
 		rcu_read_lock();
 		radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) {
@@ -72,12 +78,18 @@ static void *tagged_iteration_fn(void *arg)
 				continue;
 			}
 
-			if (rand_r(&seeds[0]) % 50 == 0)
+			if (rand_r(&seeds[0]) % 50 == 0) {
 				slot = radix_tree_iter_next(&iter);
+				rcu_read_unlock();
+				rcu_barrier();
+				rcu_read_lock();
+			}
 		}
 		rcu_read_unlock();
 	}
 
+	rcu_unregister_thread();
+
 	return NULL;
 }
 
@@ -93,6 +105,8 @@ static void *untagged_iteration_fn(void *arg)
 	struct radix_tree_iter iter;
 	void **slot;
 
+	rcu_register_thread();
+
 	while (!test_complete) {
 		rcu_read_lock();
 		radix_tree_for_each_slot(slot, &tree, &iter, 0) {
@@ -112,12 +126,18 @@ static void *untagged_iteration_fn(void *arg)
 				continue;
 			}
 
-			if (rand_r(&seeds[1]) % 50 == 0)
+			if (rand_r(&seeds[1]) % 50 == 0) {
 				slot = radix_tree_iter_next(&iter);
+				rcu_read_unlock();
+				rcu_barrier();
+				rcu_read_lock();
+			}
 		}
 		rcu_read_unlock();
 	}
 
+	rcu_unregister_thread();
+
 	return NULL;
 }
 
@@ -127,6 +147,8 @@ static void *untagged_iteration_fn(void *arg)
  */
 static void *remove_entries_fn(void *arg)
 {
+	rcu_register_thread();
+
 	while (!test_complete) {
 		int pgoff;
 
@@ -137,6 +159,8 @@ static void *remove_entries_fn(void *arg)
 		pthread_mutex_unlock(&tree_lock);
 	}
 
+	rcu_unregister_thread();
+
 	return NULL;
 }
 
-- 
2.10.2

[toc] | [prev] | [standalone]

Page 4 of 4 — ← Prev page 1 2 3 [4]

Back to top | Article view | linux.kernel

csiph-web