diff options
author | Matthew Wilcox <mawilcox@microsoft.com> | 2016-12-14 15:09:07 -0800 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2016-12-14 16:04:10 -0800 |
commit | a90eb3a2a405cf7e96093ed531a285067dfdbc9d (patch) | |
tree | 5bcc4f8c9da0dabf082a6cf411ba9558ffe63d13 /tools | |
parent | 2791653a6814d170fa893344618563a7b1da95c6 (diff) | |
download | linux-a90eb3a2a405cf7e96093ed531a285067dfdbc9d.tar.gz linux-a90eb3a2a405cf7e96093ed531a285067dfdbc9d.tar.bz2 linux-a90eb3a2a405cf7e96093ed531a285067dfdbc9d.zip |
radix-tree: fix replacement for multiorder entries
When replacing an entry with NULL, we need to delete any sibling
entries. Also account deleting exceptional entries properly. Also fix
a bug with radix_tree_iter_replace() where we would fail to remove
entirely freed nodes. Also fix accounting bug when switching between
normal and exceptional entries with replace_slot. Also add testcases
for all these bugs.
Link: http://lkml.kernel.org/r/1480369871-5271-61-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.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.c | 87 |
1 files changed, 75 insertions, 12 deletions
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c index 5421f015f46c..9757b8928bd4 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -410,8 +410,6 @@ static void __multiorder_split(int old_order, int new_order) 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); @@ -434,58 +432,122 @@ static void __multiorder_split(int old_order, int new_order) radix_tree_preload_end(); item_kill_tree(&tree); +} + +static void __multiorder_split2(int old_order, int new_order) +{ + RADIX_TREE(tree, GFP_KERNEL); + void **slot; + struct radix_tree_iter iter; + struct radix_tree_node *node; + void *item; - 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); assert(node->exceptional == 0); item_kill_tree(&tree); +} + +static void __multiorder_split3(int old_order, int new_order) +{ + RADIX_TREE(tree, GFP_KERNEL); + void **slot; + struct radix_tree_iter iter; + struct radix_tree_node *node; + void *item; - 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); assert(node->exceptional > 0); item_kill_tree(&tree); + + __radix_tree_insert(&tree, 0, old_order, (void *)0x12); + + item = __radix_tree_lookup(&tree, 0, &node, NULL); + assert(item == (void *)0x12); + assert(node->exceptional > 0); + + radix_tree_split(&tree, 0, new_order); + radix_tree_for_each_slot(slot, &tree, &iter, 0) { + if (iter.index == (1 << new_order)) + radix_tree_iter_replace(&tree, &iter, slot, + (void *)0x16); + else + radix_tree_iter_replace(&tree, &iter, slot, NULL); + } + + item = __radix_tree_lookup(&tree, 1 << new_order, &node, NULL); + assert(item == (void *)0x16); + assert(node->count == node->exceptional); + do { + node = node->parent; + if (!node) + break; + assert(node->count == 1); + assert(node->exceptional == 0); + } while (1); + + item_kill_tree(&tree); } static void multiorder_split(void) { int i, j; - for (i = 9; i < 19; i++) - for (j = 0; j < i; j++) + for (i = 3; i < 11; i++) + for (j = 0; j < i; j++) { __multiorder_split(i, j); + __multiorder_split2(i, j); + __multiorder_split3(i, j); + } +} + +static void multiorder_account(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + struct radix_tree_node *node; + void **slot; + + item_insert_order(&tree, 0, 5); + + __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12); + __radix_tree_lookup(&tree, 0, &node, NULL); + assert(node->count == node->exceptional * 2); + radix_tree_delete(&tree, 1 << 5); + assert(node->exceptional == 0); + + __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12); + __radix_tree_lookup(&tree, 1 << 5, &node, &slot); + assert(node->count == node->exceptional * 2); + __radix_tree_replace(&tree, node, slot, NULL, NULL, NULL); + assert(node->exceptional == 0); + + item_kill_tree(&tree); } void multiorder_checks(void) @@ -507,6 +569,7 @@ void multiorder_checks(void) multiorder_tagged_iteration(); multiorder_join(); multiorder_split(); + multiorder_account(); radix_tree_cpu_dead(0); } |