2 * iteration_check.c: test races having to do with radix tree iteration
3 * Copyright (c) 2016 Intel Corporation
4 * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms and conditions of the GNU General Public License,
8 * version 2, as published by the Free Software Foundation.
10 * This program is distributed in the hope it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 #include <linux/radix-tree.h>
24 static pthread_mutex_t tree_lock = PTHREAD_MUTEX_INITIALIZER;
25 static pthread_t threads[NUM_THREADS];
26 static unsigned int seeds[3];
27 static RADIX_TREE(tree, GFP_KERNEL);
28 static bool test_complete;
31 /* relentlessly fill the tree with tagged entries */
32 static void *add_entries_fn(void *arg)
34 rcu_register_thread();
36 while (!test_complete) {
40 for (pgoff = 0; pgoff < MAX_IDX; pgoff++) {
41 pthread_mutex_lock(&tree_lock);
42 for (order = max_order; order >= 0; order--) {
43 if (item_insert_order(&tree, pgoff, order)
45 item_tag_set(&tree, pgoff, TAG);
49 pthread_mutex_unlock(&tree_lock);
53 rcu_unregister_thread();
59 * Iterate over the tagged entries, doing a radix_tree_iter_retry() as we find
60 * things that have been removed and randomly resetting our iteration to the
61 * next chunk with radix_tree_iter_resume(). Both radix_tree_iter_retry() and
62 * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a
63 * NULL 'slot' variable.
65 static void *tagged_iteration_fn(void *arg)
67 struct radix_tree_iter iter;
70 rcu_register_thread();
72 while (!test_complete) {
74 radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) {
75 void *entry = radix_tree_deref_slot(slot);
79 if (radix_tree_deref_retry(entry)) {
80 slot = radix_tree_iter_retry(&iter);
84 if (rand_r(&seeds[0]) % 50 == 0) {
85 slot = radix_tree_iter_resume(slot, &iter);
94 rcu_unregister_thread();
100 * Iterate over the entries, doing a radix_tree_iter_retry() as we find things
101 * that have been removed and randomly resetting our iteration to the next
102 * chunk with radix_tree_iter_resume(). Both radix_tree_iter_retry() and
103 * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a
104 * NULL 'slot' variable.
106 static void *untagged_iteration_fn(void *arg)
108 struct radix_tree_iter iter;
111 rcu_register_thread();
113 while (!test_complete) {
115 radix_tree_for_each_slot(slot, &tree, &iter, 0) {
116 void *entry = radix_tree_deref_slot(slot);
117 if (unlikely(!entry))
120 if (radix_tree_deref_retry(entry)) {
121 slot = radix_tree_iter_retry(&iter);
125 if (rand_r(&seeds[1]) % 50 == 0) {
126 slot = radix_tree_iter_resume(slot, &iter);
135 rcu_unregister_thread();
141 * Randomly remove entries to help induce radix_tree_iter_retry() calls in the
142 * two iteration functions.
144 static void *remove_entries_fn(void *arg)
146 rcu_register_thread();
148 while (!test_complete) {
151 pgoff = rand_r(&seeds[2]) % MAX_IDX;
153 pthread_mutex_lock(&tree_lock);
154 item_delete(&tree, pgoff);
155 pthread_mutex_unlock(&tree_lock);
158 rcu_unregister_thread();
163 static void *tag_entries_fn(void *arg)
165 rcu_register_thread();
167 while (!test_complete) {
168 tag_tagged_items(&tree, &tree_lock, 0, MAX_IDX, 10, TAG,
171 rcu_unregister_thread();
175 /* This is a unit test for a bug found by the syzkaller tester */
176 void iteration_test(unsigned order, unsigned test_duration)
180 printv(1, "Running %siteration tests for %d seconds\n",
181 order > 0 ? "multiorder " : "", test_duration);
184 test_complete = false;
186 for (i = 0; i < 3; i++)
189 if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
190 perror("create tagged iteration thread");
193 if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
194 perror("create untagged iteration thread");
197 if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
198 perror("create add entry thread");
201 if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
202 perror("create remove entry thread");
205 if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) {
206 perror("create tag entry thread");
210 sleep(test_duration);
211 test_complete = true;
213 for (i = 0; i < NUM_THREADS; i++) {
214 if (pthread_join(threads[i], NULL)) {
215 perror("pthread_join");
220 item_kill_tree(&tree);