From 372266ba0267803564824b1c09f1bb7f3f3fc761 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Sat, 18 Aug 2018 07:09:22 -0400 Subject: radix tree test suite: Convert tag_tagged_items to XArray The tag_tagged_items() function is supposed to test the page-writeback tagging code. Since that has been converted to the XArray, there's not much point in testing the radix tree's tagging code. This requires using the pthread mutex embedded in the xarray instead of an external lock, so remove the pthread mutexes which protect xarrays/radix trees. Also remove radix_tree_iter_tag_set() as this was the last user. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/iteration_check.c | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) (limited to 'tools/testing/radix-tree/iteration_check.c') diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c index a92bab513701..d047327bb9ef 100644 --- a/tools/testing/radix-tree/iteration_check.c +++ b/tools/testing/radix-tree/iteration_check.c @@ -18,10 +18,9 @@ #define NUM_THREADS 5 #define MAX_IDX 100 -#define TAG 0 -#define NEW_TAG 1 +#define TAG XA_MARK_0 +#define NEW_TAG XA_MARK_1 -static pthread_mutex_t tree_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_t threads[NUM_THREADS]; static unsigned int seeds[3]; static RADIX_TREE(tree, GFP_KERNEL); @@ -38,7 +37,7 @@ static void *add_entries_fn(void *arg) int order; for (pgoff = 0; pgoff < MAX_IDX; pgoff++) { - pthread_mutex_lock(&tree_lock); + xa_lock(&tree); for (order = max_order; order >= 0; order--) { if (item_insert_order(&tree, pgoff, order) == 0) { @@ -46,7 +45,7 @@ static void *add_entries_fn(void *arg) break; } } - pthread_mutex_unlock(&tree_lock); + xa_unlock(&tree); } } @@ -150,9 +149,9 @@ static void *remove_entries_fn(void *arg) pgoff = rand_r(&seeds[2]) % MAX_IDX; - pthread_mutex_lock(&tree_lock); + xa_lock(&tree); item_delete(&tree, pgoff); - pthread_mutex_unlock(&tree_lock); + xa_unlock(&tree); } rcu_unregister_thread(); @@ -165,8 +164,7 @@ static void *tag_entries_fn(void *arg) rcu_register_thread(); while (!test_complete) { - tag_tagged_items(&tree, &tree_lock, 0, MAX_IDX, 10, TAG, - NEW_TAG); + tag_tagged_items(&tree, 0, MAX_IDX, 10, TAG, NEW_TAG); } rcu_unregister_thread(); return NULL; -- cgit v1.2.3 From 47e0fab2b15155e33fdff777c791bebfd5855bbc Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Mon, 20 Aug 2018 15:48:46 -0400 Subject: radix tree test suite: Convert iteration test to XArray With no code left in the kernel using the multiorder radix tree, convert the iteration test from the radix tree to the XArray. It's unlikely to suffer the same bug as the radix tree, but this test will prevent that bug from ever creeping into the XArray implementation. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/iteration_check.c | 103 ++++++++++++++--------------- 1 file changed, 51 insertions(+), 52 deletions(-) (limited to 'tools/testing/radix-tree/iteration_check.c') diff --git a/tools/testing/radix-tree/iteration_check.c b/tools/testing/radix-tree/iteration_check.c index d047327bb9ef..238db187aa15 100644 --- a/tools/testing/radix-tree/iteration_check.c +++ b/tools/testing/radix-tree/iteration_check.c @@ -1,5 +1,5 @@ /* - * iteration_check.c: test races having to do with radix tree iteration + * iteration_check.c: test races having to do with xarray iteration * Copyright (c) 2016 Intel Corporation * Author: Ross Zwisler * @@ -12,7 +12,6 @@ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for * more details. */ -#include #include #include "test.h" @@ -23,29 +22,44 @@ static pthread_t threads[NUM_THREADS]; static unsigned int seeds[3]; -static RADIX_TREE(tree, GFP_KERNEL); +static DEFINE_XARRAY(array); static bool test_complete; static int max_order; -/* relentlessly fill the tree with tagged entries */ +void my_item_insert(struct xarray *xa, unsigned long index) +{ + XA_STATE(xas, xa, index); + struct item *item = item_create(index, 0); + int order; + +retry: + xas_lock(&xas); + for (order = max_order; order >= 0; order--) { + xas_set_order(&xas, index, order); + item->order = order; + if (xas_find_conflict(&xas)) + continue; + xas_store(&xas, item); + xas_set_mark(&xas, TAG); + break; + } + xas_unlock(&xas); + if (xas_nomem(&xas, GFP_KERNEL)) + goto retry; + if (order < 0) + free(item); +} + +/* relentlessly fill the array with tagged entries */ static void *add_entries_fn(void *arg) { rcu_register_thread(); while (!test_complete) { unsigned long pgoff; - int order; for (pgoff = 0; pgoff < MAX_IDX; pgoff++) { - xa_lock(&tree); - for (order = max_order; order >= 0; order--) { - if (item_insert_order(&tree, pgoff, order) - == 0) { - item_tag_set(&tree, pgoff, TAG); - break; - } - } - xa_unlock(&tree); + my_item_insert(&array, pgoff); } } @@ -55,33 +69,25 @@ static void *add_entries_fn(void *arg) } /* - * Iterate over the tagged entries, doing a radix_tree_iter_retry() as we find - * things that have been removed and randomly resetting our iteration to the - * next chunk with radix_tree_iter_resume(). Both radix_tree_iter_retry() and - * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a - * NULL 'slot' variable. + * Iterate over tagged entries, retrying when we find ourselves in a deleted + * node and randomly pausing the iteration. */ static void *tagged_iteration_fn(void *arg) { - struct radix_tree_iter iter; - void **slot; + XA_STATE(xas, &array, 0); + void *entry; rcu_register_thread(); while (!test_complete) { + xas_set(&xas, 0); rcu_read_lock(); - radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) { - void *entry = radix_tree_deref_slot(slot); - if (unlikely(!entry)) + xas_for_each_marked(&xas, entry, ULONG_MAX, TAG) { + if (xas_retry(&xas, entry)) continue; - if (radix_tree_deref_retry(entry)) { - slot = radix_tree_iter_retry(&iter); - continue; - } - if (rand_r(&seeds[0]) % 50 == 0) { - slot = radix_tree_iter_resume(slot, &iter); + xas_pause(&xas); rcu_read_unlock(); rcu_barrier(); rcu_read_lock(); @@ -96,33 +102,25 @@ static void *tagged_iteration_fn(void *arg) } /* - * Iterate over the entries, doing a radix_tree_iter_retry() as we find things - * that have been removed and randomly resetting our iteration to the next - * chunk with radix_tree_iter_resume(). Both radix_tree_iter_retry() and - * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a - * NULL 'slot' variable. + * Iterate over the entries, retrying when we find ourselves in a deleted + * node and randomly pausing the iteration. */ static void *untagged_iteration_fn(void *arg) { - struct radix_tree_iter iter; - void **slot; + XA_STATE(xas, &array, 0); + void *entry; rcu_register_thread(); while (!test_complete) { + xas_set(&xas, 0); rcu_read_lock(); - radix_tree_for_each_slot(slot, &tree, &iter, 0) { - void *entry = radix_tree_deref_slot(slot); - if (unlikely(!entry)) + xas_for_each(&xas, entry, ULONG_MAX) { + if (xas_retry(&xas, entry)) continue; - if (radix_tree_deref_retry(entry)) { - slot = radix_tree_iter_retry(&iter); - continue; - } - if (rand_r(&seeds[1]) % 50 == 0) { - slot = radix_tree_iter_resume(slot, &iter); + xas_pause(&xas); rcu_read_unlock(); rcu_barrier(); rcu_read_lock(); @@ -137,7 +135,7 @@ static void *untagged_iteration_fn(void *arg) } /* - * Randomly remove entries to help induce radix_tree_iter_retry() calls in the + * Randomly remove entries to help induce retries in the * two iteration functions. */ static void *remove_entries_fn(void *arg) @@ -146,12 +144,13 @@ static void *remove_entries_fn(void *arg) while (!test_complete) { int pgoff; + struct item *item; pgoff = rand_r(&seeds[2]) % MAX_IDX; - xa_lock(&tree); - item_delete(&tree, pgoff); - xa_unlock(&tree); + item = xa_erase(&array, pgoff); + if (item) + item_free(item, pgoff); } rcu_unregister_thread(); @@ -164,7 +163,7 @@ static void *tag_entries_fn(void *arg) rcu_register_thread(); while (!test_complete) { - tag_tagged_items(&tree, 0, MAX_IDX, 10, TAG, NEW_TAG); + tag_tagged_items(&array, 0, MAX_IDX, 10, TAG, NEW_TAG); } rcu_unregister_thread(); return NULL; @@ -215,5 +214,5 @@ void iteration_test(unsigned order, unsigned test_duration) } } - item_kill_tree(&tree); + item_kill_tree(&array); } -- cgit v1.2.3