1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * iteration_check.c: test races having to do with xarray iteration
4  * Copyright (c) 2016 Intel Corporation
5  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
6  */
7 #include <pthread.h>
8 #include "test.h"
9 
10 #define NUM_THREADS	5
11 #define MAX_IDX		100
12 #define TAG		XA_MARK_0
13 #define NEW_TAG		XA_MARK_1
14 
15 static pthread_t threads[NUM_THREADS];
16 static unsigned int seeds[3];
17 static DEFINE_XARRAY(array);
18 static bool test_complete;
19 static int max_order;
20 
21 void my_item_insert(struct xarray *xa, unsigned long index)
22 {
23 	XA_STATE(xas, xa, index);
24 	struct item *item = item_create(index, 0);
25 	int order;
26 
27 retry:
28 	xas_lock(&xas);
29 	for (order = max_order; order >= 0; order--) {
30 		xas_set_order(&xas, index, order);
31 		item->order = order;
32 		if (xas_find_conflict(&xas))
33 			continue;
34 		xas_store(&xas, item);
35 		xas_set_mark(&xas, TAG);
36 		break;
37 	}
38 	xas_unlock(&xas);
39 	if (xas_nomem(&xas, GFP_KERNEL))
40 		goto retry;
41 	if (order < 0)
42 		free(item);
43 }
44 
45 /* relentlessly fill the array with tagged entries */
46 static void *add_entries_fn(void *arg)
47 {
48 	rcu_register_thread();
49 
50 	while (!test_complete) {
51 		unsigned long pgoff;
52 
53 		for (pgoff = 0; pgoff < MAX_IDX; pgoff++) {
54 			my_item_insert(&array, pgoff);
55 		}
56 	}
57 
58 	rcu_unregister_thread();
59 
60 	return NULL;
61 }
62 
63 /*
64  * Iterate over tagged entries, retrying when we find ourselves in a deleted
65  * node and randomly pausing the iteration.
66  */
67 static void *tagged_iteration_fn(void *arg)
68 {
69 	XA_STATE(xas, &array, 0);
70 	void *entry;
71 
72 	rcu_register_thread();
73 
74 	while (!test_complete) {
75 		xas_set(&xas, 0);
76 		rcu_read_lock();
77 		xas_for_each_marked(&xas, entry, ULONG_MAX, TAG) {
78 			if (xas_retry(&xas, entry))
79 				continue;
80 
81 			if (rand_r(&seeds[0]) % 50 == 0) {
82 				xas_pause(&xas);
83 				rcu_read_unlock();
84 				rcu_barrier();
85 				rcu_read_lock();
86 			}
87 		}
88 		rcu_read_unlock();
89 	}
90 
91 	rcu_unregister_thread();
92 
93 	return NULL;
94 }
95 
96 /*
97  * Iterate over the entries, retrying when we find ourselves in a deleted
98  * node and randomly pausing the iteration.
99  */
100 static void *untagged_iteration_fn(void *arg)
101 {
102 	XA_STATE(xas, &array, 0);
103 	void *entry;
104 
105 	rcu_register_thread();
106 
107 	while (!test_complete) {
108 		xas_set(&xas, 0);
109 		rcu_read_lock();
110 		xas_for_each(&xas, entry, ULONG_MAX) {
111 			if (xas_retry(&xas, entry))
112 				continue;
113 
114 			if (rand_r(&seeds[1]) % 50 == 0) {
115 				xas_pause(&xas);
116 				rcu_read_unlock();
117 				rcu_barrier();
118 				rcu_read_lock();
119 			}
120 		}
121 		rcu_read_unlock();
122 	}
123 
124 	rcu_unregister_thread();
125 
126 	return NULL;
127 }
128 
129 /*
130  * Randomly remove entries to help induce retries in the
131  * two iteration functions.
132  */
133 static void *remove_entries_fn(void *arg)
134 {
135 	rcu_register_thread();
136 
137 	while (!test_complete) {
138 		int pgoff;
139 		struct item *item;
140 
141 		pgoff = rand_r(&seeds[2]) % MAX_IDX;
142 
143 		item = xa_erase(&array, pgoff);
144 		if (item)
145 			item_free(item, pgoff);
146 	}
147 
148 	rcu_unregister_thread();
149 
150 	return NULL;
151 }
152 
153 static void *tag_entries_fn(void *arg)
154 {
155 	rcu_register_thread();
156 
157 	while (!test_complete) {
158 		tag_tagged_items(&array, 0, MAX_IDX, 10, TAG, NEW_TAG);
159 	}
160 	rcu_unregister_thread();
161 	return NULL;
162 }
163 
164 /* This is a unit test for a bug found by the syzkaller tester */
165 void iteration_test(unsigned order, unsigned test_duration)
166 {
167 	int i;
168 
169 	printv(1, "Running %siteration tests for %d seconds\n",
170 			order > 0 ? "multiorder " : "", test_duration);
171 
172 	max_order = order;
173 	test_complete = false;
174 
175 	for (i = 0; i < 3; i++)
176 		seeds[i] = rand();
177 
178 	if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
179 		perror("create tagged iteration thread");
180 		exit(1);
181 	}
182 	if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
183 		perror("create untagged iteration thread");
184 		exit(1);
185 	}
186 	if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
187 		perror("create add entry thread");
188 		exit(1);
189 	}
190 	if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
191 		perror("create remove entry thread");
192 		exit(1);
193 	}
194 	if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) {
195 		perror("create tag entry thread");
196 		exit(1);
197 	}
198 
199 	sleep(test_duration);
200 	test_complete = true;
201 
202 	for (i = 0; i < NUM_THREADS; i++) {
203 		if (pthread_join(threads[i], NULL)) {
204 			perror("pthread_join");
205 			exit(1);
206 		}
207 	}
208 
209 	item_kill_tree(&array);
210 }
211