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

Groups > linux.kernel > #1541489 > unrolled thread

[PATCH 0/5] Additional radix tree patches for 4.10

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/5] Additional radix tree patches for 4.10 Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-12-13 21:30 +0100
    [PATCH 4/5] radix tree test suite: Delete unused rcupdate.c Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-12-13 21:30 +0100
    [PATCH 3/5] radix tree test suite: Add new tag check Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-12-13 21:30 +0100
    [PATCH 1/5] radix tree test suite: Cache recently freed objects Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-12-13 21:30 +0100
    [PATCH 2/5] radix-tree: Ensure counts are initialised Matthew Wilcox <mawilcox@linuxonhyperv.com> - 2016-12-13 21:30 +0100

#1541489 — [PATCH 0/5] Additional radix tree patches for 4.10

From: Matthew Wilcox <mawilcox@microsoft.com>

Hi Andrew,

One bug has popped up in testing which is reasonably hard to hit (fixed
by patch 2 in this series).  I needed to change the test suite to be
able to catch the bug in action.  The test suite was returning freed
memory to glibc's malloc, but we have to keep a cache of objects in
order to notice that we freed something non-zero and then neglected to
initialise it back to zero upon reallocation.

Please drop the existing "reimplement IDR and IDA using the radix tree"
patch from your queue and replace it with these five patches.  I'd like
to see the first four patches head to Linus along with the rest of the
radix tree patches, and we can continue with the plan of holding patch 5
until 4.11.

I took your suggestion of moving as much as possible of the IDA and
IDR functionality back to idr.c.  That prompted creation of some nicer
APIs, such as radix_tree_iter_delete() and radix_tree_iter_lookup().

There are also some good bugs fixed in this revision, such as:
 - returning the correct error value from ida_get_new_above() if we run
   out of memory,
 - handling attempts to allocate from a full IDA correctly.
 - Correctly handle deleting the only entry at root with
   radix_tree_iter_delete()
I wrote test cases for all these situations, so they shouldn't
regress again.

Matthew Wilcox (5):
  radix tree test suite: Cache recently freed objects
  radix-tree: Ensure counts are initialised
  radix tree test suite: Add new tag check
  radix tree test suite: Delete unused rcupdate.c
  Reimplement IDR and IDA using the radix tree

 include/linux/idr.h                     |  138 ++--
 include/linux/radix-tree.h              |   53 +-
 init/main.c                             |    3 +-
 lib/idr.c                               | 1144 ++++++-------------------------
 lib/radix-tree.c                        |  358 ++++++++--
 tools/include/linux/spinlock.h          |    4 +
 tools/testing/radix-tree/.gitignore     |    1 +
 tools/testing/radix-tree/Makefile       |   10 +-
 tools/testing/radix-tree/idr-test.c     |  200 ++++++
 tools/testing/radix-tree/linux.c        |   48 +-
 tools/testing/radix-tree/linux/export.h |    1 +
 tools/testing/radix-tree/linux/gfp.h    |    8 +-
 tools/testing/radix-tree/linux/idr.h    |    1 +
 tools/testing/radix-tree/linux/kernel.h |    2 +
 tools/testing/radix-tree/linux/slab.h   |    5 -
 tools/testing/radix-tree/main.c         |    6 +
 tools/testing/radix-tree/multiorder.c   |   45 +-
 tools/testing/radix-tree/rcupdate.c     |   86 ---
 tools/testing/radix-tree/tag_check.c    |    3 +
 tools/testing/radix-tree/test.h         |    2 +
 20 files changed, 914 insertions(+), 1204 deletions(-)
 create mode 100644 tools/include/linux/spinlock.h
 create mode 100644 tools/testing/radix-tree/idr-test.c
 create mode 100644 tools/testing/radix-tree/linux/idr.h
 delete mode 100644 tools/testing/radix-tree/rcupdate.c

-- 
2.10.2

[toc] | [next] | [standalone]

#1541492 — [PATCH 4/5] radix tree test suite: Delete unused rcupdate.c

From: Matthew Wilcox <mawilcox@microsoft.com>

This file was used to implement call_rcu() before liburcu implemented
that function.  It hasn't even been compiled since before the test suite
was added to the kernel.  Remove it to reduce confusion.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/testing/radix-tree/rcupdate.c | 86 -------------------------------------
 1 file changed, 86 deletions(-)
 delete mode 100644 tools/testing/radix-tree/rcupdate.c

diff --git a/tools/testing/radix-tree/rcupdate.c b/tools/testing/radix-tree/rcupdate.c
deleted file mode 100644
index 31a2d14..0000000
--- a/tools/testing/radix-tree/rcupdate.c
+++ /dev/null
@@ -1,86 +0,0 @@
-#include <linux/rcupdate.h>
-#include <pthread.h>
-#include <stdio.h>
-#include <assert.h>
-
-static pthread_mutex_t rculock = PTHREAD_MUTEX_INITIALIZER;
-static struct rcu_head *rcuhead_global = NULL;
-static __thread int nr_rcuhead = 0;
-static __thread struct rcu_head *rcuhead = NULL;
-static __thread struct rcu_head *rcutail = NULL;
-
-static pthread_cond_t rcu_worker_cond = PTHREAD_COND_INITIALIZER;
-
-/* switch to urcu implementation when it is merged. */
-void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *head))
-{
-	head->func = func;
-	head->next = rcuhead;
-	rcuhead = head;
-	if (!rcutail)
-		rcutail = head;
-	nr_rcuhead++;
-	if (nr_rcuhead >= 1000) {
-		int signal = 0;
-
-		pthread_mutex_lock(&rculock);
-		if (!rcuhead_global)
-			signal = 1;
-		rcutail->next = rcuhead_global;
-		rcuhead_global = head;
-		pthread_mutex_unlock(&rculock);
-
-		nr_rcuhead = 0;
-		rcuhead = NULL;
-		rcutail = NULL;
-
-		if (signal) {
-			pthread_cond_signal(&rcu_worker_cond);
-		}
-	}
-}
-
-static void *rcu_worker(void *arg)
-{
-	struct rcu_head *r;
-
-	rcupdate_thread_init();
-
-	while (1) {
-		pthread_mutex_lock(&rculock);
-		while (!rcuhead_global) {
-			pthread_cond_wait(&rcu_worker_cond, &rculock);
-		}
-		r = rcuhead_global;
-		rcuhead_global = NULL;
-
-		pthread_mutex_unlock(&rculock);
-
-		synchronize_rcu();
-
-		while (r) {
-			struct rcu_head *tmp = r->next;
-			r->func(r);
-			r = tmp;
-		}
-	}
-
-	rcupdate_thread_exit();
-
-	return NULL;
-}
-
-static pthread_t worker_thread;
-void rcupdate_init(void)
-{
-	pthread_create(&worker_thread, NULL, rcu_worker, NULL);
-}
-
-void rcupdate_thread_init(void)
-{
-	rcu_register_thread();
-}
-void rcupdate_thread_exit(void)
-{
-	rcu_unregister_thread();
-}
-- 
2.10.2

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

#1541494 — [PATCH 3/5] radix tree test suite: Add new tag check

From: Matthew Wilcox <mawilcox@microsoft.com>

We have a check that setting a tag on a single entry at root succeeds,
but we were missing a check that clearing a tag on that same entry also
succeeds.

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

diff --git a/tools/testing/radix-tree/tag_check.c b/tools/testing/radix-tree/tag_check.c
index ed5f87d..fd98c13 100644
--- a/tools/testing/radix-tree/tag_check.c
+++ b/tools/testing/radix-tree/tag_check.c
@@ -324,6 +324,9 @@ static void single_check(void)
 	assert(ret == 1);
 	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
 	assert(ret == 1);
+	item_tag_clear(&tree, 0, 0);
+	ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
+	assert(ret == 0);
 	item_kill_tree(&tree);
 }
 
-- 
2.10.2

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

#1541495 — [PATCH 1/5] radix tree test suite: Cache recently freed objects

From: Matthew Wilcox <mawilcox@microsoft.com>

The kmem_cache_alloc implementation simply allocates new memory
from malloc() and calls the ctor, which zeroes out the entire object.
This means it cannot spot bugs where the object isn't properly
reinitialised before being freed.

Add a small (11 objects) cache before freeing objects back to malloc.
This is enough to let us write a test to catch it, although the memory
allocator is now aware of the structure of the radix tree node, since it
chains free objects through ->private_data (like the percpu cache does).

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/testing/radix-tree/linux.c      | 48 ++++++++++++++++++++++++++++++-----
 tools/testing/radix-tree/linux/slab.h |  5 ----
 2 files changed, 41 insertions(+), 12 deletions(-)

diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index ff0452e..d31ea7c 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -1,16 +1,27 @@
 #include <stdlib.h>
 #include <string.h>
 #include <malloc.h>
+#include <pthread.h>
 #include <unistd.h>
 #include <assert.h>
 
 #include <linux/mempool.h>
+#include <linux/poison.h>
 #include <linux/slab.h>
+#include <linux/radix-tree.h>
 #include <urcu/uatomic.h>
 
 int nr_allocated;
 int preempt_count;
 
+struct kmem_cache {
+	pthread_mutex_t lock;
+	int size;
+	int nr_objs;
+	void *objs;
+	void (*ctor)(void *);
+};
+
 void *mempool_alloc(mempool_t *pool, int gfp_mask)
 {
 	return pool->alloc(gfp_mask, pool->data);
@@ -34,24 +45,44 @@ mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn,
 
 void *kmem_cache_alloc(struct kmem_cache *cachep, int flags)
 {
-	void *ret;
+	struct radix_tree_node *node;
 
 	if (flags & __GFP_NOWARN)
 		return NULL;
 
-	ret = malloc(cachep->size);
-	if (cachep->ctor)
-		cachep->ctor(ret);
+	pthread_mutex_lock(&cachep->lock);
+	if (cachep->nr_objs) {
+		cachep->nr_objs--;
+		node = cachep->objs;
+		cachep->objs = node->private_data;
+		pthread_mutex_unlock(&cachep->lock);
+		node->private_data = NULL;
+	} else {
+		pthread_mutex_unlock(&cachep->lock);
+		node = malloc(cachep->size);
+		if (cachep->ctor)
+			cachep->ctor(node);
+	}
+
 	uatomic_inc(&nr_allocated);
-	return ret;
+	return node;
 }
 
 void kmem_cache_free(struct kmem_cache *cachep, void *objp)
 {
 	assert(objp);
 	uatomic_dec(&nr_allocated);
-	memset(objp, 0, cachep->size);
-	free(objp);
+	pthread_mutex_lock(&cachep->lock);
+	if (cachep->nr_objs > 10) {
+		memset(objp, POISON_FREE, cachep->size);
+		free(objp);
+	} else {
+		struct radix_tree_node *node = objp;
+		cachep->nr_objs++;
+		node->private_data = cachep->objs;
+		cachep->objs = node;
+	}
+	pthread_mutex_unlock(&cachep->lock);
 }
 
 void *kmalloc(size_t size, gfp_t gfp)
@@ -75,7 +106,10 @@ kmem_cache_create(const char *name, size_t size, size_t offset,
 {
 	struct kmem_cache *ret = malloc(sizeof(*ret));
 
+	pthread_mutex_init(&ret->lock, NULL);
 	ret->size = size;
+	ret->nr_objs = 0;
+	ret->objs = NULL;
 	ret->ctor = ctor;
 	return ret;
 }
diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h
index 446639f..e40337f 100644
--- a/tools/testing/radix-tree/linux/slab.h
+++ b/tools/testing/radix-tree/linux/slab.h
@@ -10,11 +10,6 @@
 void *kmalloc(size_t size, gfp_t);
 void kfree(void *);
 
-struct kmem_cache {
-	int size;
-	void (*ctor)(void *);
-};
-
 void *kmem_cache_alloc(struct kmem_cache *cachep, int flags);
 void kmem_cache_free(struct kmem_cache *cachep, void *objp);
 
-- 
2.10.2

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

#1541496 — [PATCH 2/5] radix-tree: Ensure counts are initialised

From: Matthew Wilcox <mawilcox@microsoft.com>

radix_tree_join() was freeing nodes with a non-zero ->exceptional count,
and radix_tree_split() wasn't zeroing ->exceptional when it allocated
the new node.  Fix this by making all callers of radix_tree_node_alloc()
pass in the new counts (and some other always-initialised fields),
which will prevent the problem recurring if in future we decide to do
something similar.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 lib/radix-tree.c                      | 41 ++++++++++++++++---------------
 tools/testing/radix-tree/multiorder.c | 45 +++++++++++++++++++++++++++++++----
 2 files changed, 61 insertions(+), 25 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index a227727..6f382e0 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -287,7 +287,10 @@ static void radix_tree_dump(struct radix_tree_root *root)
  * that the caller has pinned this thread of control to the current CPU.
  */
 static struct radix_tree_node *
-radix_tree_node_alloc(struct radix_tree_root *root)
+radix_tree_node_alloc(struct radix_tree_root *root,
+			struct radix_tree_node *parent,
+			unsigned int shift, unsigned int offset,
+			unsigned int count, unsigned int exceptional)
 {
 	struct radix_tree_node *ret = NULL;
 	gfp_t gfp_mask = root_gfp_mask(root);
@@ -332,6 +335,13 @@ radix_tree_node_alloc(struct radix_tree_root *root)
 	ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
 out:
 	BUG_ON(radix_tree_is_internal_node(ret));
+	if (ret) {
+		ret->parent = parent;
+		ret->shift = shift;
+		ret->offset = offset;
+		ret->count = count;
+		ret->exceptional = exceptional;
+	}
 	return ret;
 }
 
@@ -537,8 +547,8 @@ static int radix_tree_extend(struct radix_tree_root *root,
 		goto out;
 
 	do {
-		struct radix_tree_node *node = radix_tree_node_alloc(root);
-
+		struct radix_tree_node *node = radix_tree_node_alloc(root,
+							NULL, shift, 0, 1, 0);
 		if (!node)
 			return -ENOMEM;
 
@@ -549,16 +559,11 @@ static int radix_tree_extend(struct radix_tree_root *root,
 		}
 
 		BUG_ON(shift > BITS_PER_LONG);
-		node->shift = shift;
-		node->offset = 0;
-		node->count = 1;
-		node->parent = NULL;
 		if (radix_tree_is_internal_node(slot)) {
 			entry_to_node(slot)->parent = node;
-		} else {
+		} else if (radix_tree_exceptional_entry(slot)) {
 			/* Moving an exceptional root->rnode to a node */
-			if (radix_tree_exceptional_entry(slot))
-				node->exceptional = 1;
+			node->exceptional = 1;
 		}
 		node->slots[0] = slot;
 		slot = node_to_entry(node);
@@ -711,14 +716,10 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
 		shift -= RADIX_TREE_MAP_SHIFT;
 		if (child == NULL) {
 			/* Have to add a child node.  */
-			child = radix_tree_node_alloc(root);
+			child = radix_tree_node_alloc(root, node, shift,
+							offset, 0, 0);
 			if (!child)
 				return -ENOMEM;
-			child->shift = shift;
-			child->offset = offset;
-			child->count = 0;
-			child->exceptional = 0;
-			child->parent = node;
 			rcu_assign_pointer(*slot, node_to_entry(child));
 			if (node)
 				node->count++;
@@ -1208,13 +1209,11 @@ int radix_tree_split(struct radix_tree_root *root, unsigned long index,
 
 	for (;;) {
 		if (node->shift > order) {
-			child = radix_tree_node_alloc(root);
+			child = radix_tree_node_alloc(root, node,
+					node->shift - RADIX_TREE_MAP_SHIFT,
+					offset, 0, 0);
 			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);
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 08b4e16..f79812a 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -355,7 +355,7 @@ void multiorder_tagged_iteration(void)
 	item_kill_tree(&tree);
 }
 
-static void __multiorder_join(unsigned long index,
+static void multiorder_join1(unsigned long index,
 				unsigned order1, unsigned order2)
 {
 	unsigned long loc;
@@ -373,7 +373,7 @@ static void __multiorder_join(unsigned long index,
 	item_kill_tree(&tree);
 }
 
-static void __multiorder_join2(unsigned order1, unsigned order2)
+static void multiorder_join2(unsigned order1, unsigned order2)
 {
 	RADIX_TREE(tree, GFP_KERNEL);
 	struct radix_tree_node *node;
@@ -393,6 +393,39 @@ static void __multiorder_join2(unsigned order1, unsigned order2)
 	item_kill_tree(&tree);
 }
 
+/*
+ * This test revealed an accounting bug for exceptional entries at one point.
+ * Nodes were being freed back into the pool with an elevated exception count
+ * by radix_tree_join() and then radix_tree_split() was failing to zero the
+ * count of exceptional entries.
+ */
+static void multiorder_join3(unsigned int order)
+{
+	RADIX_TREE(tree, GFP_KERNEL);
+	struct radix_tree_node *node;
+	void **slot;
+	struct radix_tree_iter iter;
+	unsigned long i;
+
+	for (i = 0; i < (1 << order); i++) {
+		radix_tree_insert(&tree, i, (void *)0x12UL);
+	}
+
+	radix_tree_join(&tree, 0, order, (void *)0x16UL);
+	rcu_barrier();
+
+	radix_tree_split(&tree, 0, 0);
+
+	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
+		radix_tree_iter_replace(&tree, &iter, slot, (void *)0x12UL);
+	}
+
+	__radix_tree_lookup(&tree, 0, &node, NULL);
+	assert(node->exceptional == node->count);
+
+	item_kill_tree(&tree);
+}
+
 static void multiorder_join(void)
 {
 	int i, j, idx;
@@ -400,16 +433,20 @@ static void multiorder_join(void)
 	for (idx = 0; idx < 1024; idx = idx * 2 + 3) {
 		for (i = 1; i < 15; i++) {
 			for (j = 0; j < i; j++) {
-				__multiorder_join(idx, i, j);
+				multiorder_join1(idx, i, j);
 			}
 		}
 	}
 
 	for (i = 1; i < 15; i++) {
 		for (j = 0; j < i; j++) {
-			__multiorder_join2(i, j);
+			multiorder_join2(i, j);
 		}
 	}
+
+	for (i = 3; i < 10; i++) {
+		multiorder_join3(i);
+	}
 }
 
 static void check_mem(unsigned old_order, unsigned new_order, unsigned alloc)
-- 
2.10.2

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web