1 /*
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>
5  *
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.
9  *
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
13  * more details.
14  */
15 #include <linux/radix-tree.h>
16 #include <pthread.h>
17 #include "test.h"
18 
19 #define NUM_THREADS	5
20 #define MAX_IDX		100
21 #define TAG		0
22 #define NEW_TAG		1
23 
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;
29 static int max_order;
30 
31 /* relentlessly fill the tree with tagged entries */
32 static void *add_entries_fn(void *arg)
33 {
34 	rcu_register_thread();
35 
36 	while (!test_complete) {
37 		unsigned long pgoff;
38 		int order;
39 
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)
44 						== 0) {
45 					item_tag_set(&tree, pgoff, TAG);
46 					break;
47 				}
48 			}
49 			pthread_mutex_unlock(&tree_lock);
50 		}
51 	}
52 
53 	rcu_unregister_thread();
54 
55 	return NULL;
56 }
57 
58 /*
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.
64  */
65 static void *tagged_iteration_fn(void *arg)
66 {
67 	struct radix_tree_iter iter;
68 	void **slot;
69 
70 	rcu_register_thread();
71 
72 	while (!test_complete) {
73 		rcu_read_lock();
74 		radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) {
75 			void *entry = radix_tree_deref_slot(slot);
76 			if (unlikely(!entry))
77 				continue;
78 
79 			if (radix_tree_deref_retry(entry)) {
80 				slot = radix_tree_iter_retry(&iter);
81 				continue;
82 			}
83 
84 			if (rand_r(&seeds[0]) % 50 == 0) {
85 				slot = radix_tree_iter_resume(slot, &iter);
86 				rcu_read_unlock();
87 				rcu_barrier();
88 				rcu_read_lock();
89 			}
90 		}
91 		rcu_read_unlock();
92 	}
93 
94 	rcu_unregister_thread();
95 
96 	return NULL;
97 }
98 
99 /*
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.
105  */
106 static void *untagged_iteration_fn(void *arg)
107 {
108 	struct radix_tree_iter iter;
109 	void **slot;
110 
111 	rcu_register_thread();
112 
113 	while (!test_complete) {
114 		rcu_read_lock();
115 		radix_tree_for_each_slot(slot, &tree, &iter, 0) {
116 			void *entry = radix_tree_deref_slot(slot);
117 			if (unlikely(!entry))
118 				continue;
119 
120 			if (radix_tree_deref_retry(entry)) {
121 				slot = radix_tree_iter_retry(&iter);
122 				continue;
123 			}
124 
125 			if (rand_r(&seeds[1]) % 50 == 0) {
126 				slot = radix_tree_iter_resume(slot, &iter);
127 				rcu_read_unlock();
128 				rcu_barrier();
129 				rcu_read_lock();
130 			}
131 		}
132 		rcu_read_unlock();
133 	}
134 
135 	rcu_unregister_thread();
136 
137 	return NULL;
138 }
139 
140 /*
141  * Randomly remove entries to help induce radix_tree_iter_retry() calls in the
142  * two iteration functions.
143  */
144 static void *remove_entries_fn(void *arg)
145 {
146 	rcu_register_thread();
147 
148 	while (!test_complete) {
149 		int pgoff;
150 
151 		pgoff = rand_r(&seeds[2]) % MAX_IDX;
152 
153 		pthread_mutex_lock(&tree_lock);
154 		item_delete(&tree, pgoff);
155 		pthread_mutex_unlock(&tree_lock);
156 	}
157 
158 	rcu_unregister_thread();
159 
160 	return NULL;
161 }
162 
163 static void *tag_entries_fn(void *arg)
164 {
165 	rcu_register_thread();
166 
167 	while (!test_complete) {
168 		tag_tagged_items(&tree, &tree_lock, 0, MAX_IDX, 10, TAG,
169 					NEW_TAG);
170 	}
171 	rcu_unregister_thread();
172 	return NULL;
173 }
174 
175 /* This is a unit test for a bug found by the syzkaller tester */
176 void iteration_test(unsigned order, unsigned test_duration)
177 {
178 	int i;
179 
180 	printv(1, "Running %siteration tests for %d seconds\n",
181 			order > 0 ? "multiorder " : "", test_duration);
182 
183 	max_order = order;
184 	test_complete = false;
185 
186 	for (i = 0; i < 3; i++)
187 		seeds[i] = rand();
188 
189 	if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
190 		perror("create tagged iteration thread");
191 		exit(1);
192 	}
193 	if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
194 		perror("create untagged iteration thread");
195 		exit(1);
196 	}
197 	if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
198 		perror("create add entry thread");
199 		exit(1);
200 	}
201 	if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
202 		perror("create remove entry thread");
203 		exit(1);
204 	}
205 	if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) {
206 		perror("create tag entry thread");
207 		exit(1);
208 	}
209 
210 	sleep(test_duration);
211 	test_complete = true;
212 
213 	for (i = 0; i < NUM_THREADS; i++) {
214 		if (pthread_join(threads[i], NULL)) {
215 			perror("pthread_join");
216 			exit(1);
217 		}
218 	}
219 
220 	item_kill_tree(&tree);
221 }
222