summaryrefslogtreecommitdiffstats
path: root/tools
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@linux.intel.com>2016-12-14 15:09:04 -0800
committerLinus Torvalds <torvalds@linux-foundation.org>2016-12-14 16:04:10 -0800
commit2791653a6814d170fa893344618563a7b1da95c6 (patch)
tree635c8ca43b49ac15836e5d4b5786d64733661755 /tools
parente157b555945fb16ddc6cce605a1eb6b4135ea5f1 (diff)
downloadlinux-2791653a6814d170fa893344618563a7b1da95c6.tar.bz2
radix-tree: add radix_tree_split_preload()
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()). Link: http://lkml.kernel.org/r/1480369871-5271-60-git-send-email-mawilcox@linuxonhyperv.com Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Tested-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Matthew Wilcox <mawilcox@microsoft.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'tools')
-rw-r--r--tools/testing/radix-tree/multiorder.c42
-rw-r--r--tools/testing/radix-tree/test.h5
2 files changed, 45 insertions, 2 deletions
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index fa6effe997a3..5421f015f46c 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -389,35 +389,67 @@ 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;
struct radix_tree_node *node;
void *item;
+ 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_cpu_dead(0);
- 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_iter_replace(&tree, &iter, slot,
item_create(iter.index, new_order));
}
+ radix_tree_preload_end();
item_kill_tree(&tree);
+ radix_tree_preload(GFP_KERNEL);
__radix_tree_insert(&tree, 0, old_order, (void *)0x12);
+ radix_tree_preload_end();
item = __radix_tree_lookup(&tree, 0, &node, NULL);
assert(item == (void *)0x12);
assert(node->exceptional > 0);
+ radix_tree_split_preload(old_order, new_order, GFP_KERNEL);
radix_tree_split(&tree, 0, new_order);
radix_tree_for_each_slot(slot, &tree, &iter, 0) {
radix_tree_iter_replace(&tree, &iter, slot,
item_create(iter.index, new_order));
}
+ radix_tree_preload_end();
item = __radix_tree_lookup(&tree, 0, &node, NULL);
assert(item != (void *)0x12);
@@ -425,16 +457,20 @@ static void __multiorder_split(int old_order, int new_order)
item_kill_tree(&tree);
+ radix_tree_preload(GFP_KERNEL);
__radix_tree_insert(&tree, 0, old_order, (void *)0x12);
+ radix_tree_preload_end();
item = __radix_tree_lookup(&tree, 0, &node, NULL);
assert(item == (void *)0x12);
assert(node->exceptional > 0);
+ radix_tree_split_preload(old_order, new_order, GFP_KERNEL);
radix_tree_split(&tree, 0, new_order);
radix_tree_for_each_slot(slot, &tree, &iter, 0) {
radix_tree_iter_replace(&tree, &iter, slot, (void *)0x16);
}
+ radix_tree_preload_end();
item = __radix_tree_lookup(&tree, 0, &node, NULL);
assert(item == (void *)0x16);
@@ -471,4 +507,6 @@ void multiorder_checks(void)
multiorder_tagged_iteration();
multiorder_join();
multiorder_split();
+
+ radix_tree_cpu_dead(0);
}
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index e11e4d260b4e..7c2611caa6d2 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -52,3 +52,8 @@ 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_cpu_dead(unsigned int cpu);
+struct radix_tree_preload {
+ unsigned nr;
+ struct radix_tree_node *nodes;
+};
+extern struct radix_tree_preload radix_tree_preloads;