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, order: 0); |
25 | int order; |
26 | |
27 | retry: |
28 | xas_lock(&xas); |
29 | for (order = max_order; order >= 0; order--) { |
30 | xas_set_order(xas: &xas, index, order); |
31 | item->order = order; |
32 | if (xas_find_conflict(&xas)) |
33 | continue; |
34 | xas_store(&xas, entry: 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(xa: &array, index: 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: &xas, index: 0); |
76 | rcu_read_lock(); |
77 | xas_for_each_marked(&xas, entry, ULONG_MAX, TAG) { |
78 | if (xas_retry(xas: &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: &xas, index: 0); |
109 | rcu_read_lock(); |
110 | xas_for_each(&xas, entry, ULONG_MAX) { |
111 | if (xas_retry(xas: &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, index: pgoff); |
144 | if (item) |
145 | item_free(item, index: 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, start: 0, MAX_IDX, batch: 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(root: &array); |
210 | } |
211 | |