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

Groups > linux.kernel > #1372861

[PATCH 21/30] radix tree test suite: Add multiorder shrinking test

Show all headers | View raw

Ensure that the tree goes back down to the same height when an item is
inserted & removed from the tree at a higher index.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>
Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com>
---
 tools/testing/radix-tree/multiorder.c | 38 +++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 583c5127fbcf..10b9708a71f9 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -46,6 +46,41 @@ static void multiorder_check(unsigned long index, int order)
 		item_check_absent(&tree, i);
 }
 
+static void multiorder_shrink(unsigned long index, int order)
+{
+	unsigned long i;
+	unsigned long max = 1 << order;
+	RADIX_TREE(tree, GFP_KERNEL);
+	struct radix_tree_node *node;
+
+	printf("Multiorder shrink index %ld, order %d\n", index, order);
+
+	assert(item_insert_order(&tree, 0, order) == 0);
+
+	node = tree.rnode;
+
+	assert(item_insert(&tree, index) == 0);
+	assert(node != tree.rnode);
+
+	assert(item_delete(&tree, index) != 0);
+	assert(node == tree.rnode);
+
+	for (i = 0; i < max; i++) {
+		struct item *item = item_lookup(&tree, i);
+		assert(item != 0);
+		assert(item->index == 0);
+	}
+	for (i = max; i < 2*max; i++)
+		item_check_absent(&tree, i);
+
+	if (!item_delete(&tree, 0)) {
+		printf("failed to delete index %ld (order %d)\n", index, order);		abort();
+	}
+
+	for (i = 0; i < 2*max; i++)
+		item_check_absent(&tree, i);
+}
+
 static void multiorder_insert_bug(void)
 {
 	RADIX_TREE(tree, GFP_KERNEL);
@@ -157,6 +192,9 @@ void multiorder_checks(void)
 		multiorder_check((1UL << i) + 1, i);
 	}
 
+	for (i = 0; i < 15; i++)
+		multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
+
 	multiorder_iteration();
 	multiorder_tagged_iteration();
 	multiorder_insert_bug();
-- 
2.8.0.rc3

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH 00/30] Radix tree multiorder fixes Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
  [PATCH 24/30] radix-tree: Rewrite radix_tree_tag_get Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
  [PATCH 21/30] radix tree test suite: Add multiorder shrinking test Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
  [PATCH 30/30] radix-tree: Add copyright statements Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
  [PATCH 13/30] radix-tree: Introduce radix_tree_load_root() Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:30 +0200
  [PATCH 02/30] radix tree test suite: Fix build Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
  [PATCH 05/30] radix tree test suite: keep regression test runs short Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
  [PATCH 06/30] radix tree test suite: rebuild when headers change Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
  [PATCH 10/30] radix-tree: Fix sibling entry insertion Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
  [PATCH 11/30] radix-tree: Fix deleting a multi-order entry through an alias Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200
  [PATCH 01/30] radix-tree: Introduce radix_tree_empty Matthew Wilcox <willy@linux.intel.com> - 2016-04-06 23:40 +0200

csiph-web