Commit | Line | Data |
---|---|---|
eec48525 RZ |
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 4 | |
20 | #define TAG 0 | |
21 | static pthread_mutex_t tree_lock = PTHREAD_MUTEX_INITIALIZER; | |
22 | static pthread_t threads[NUM_THREADS]; | |
061ef393 | 23 | static unsigned int seeds[3]; |
eec48525 RZ |
24 | RADIX_TREE(tree, GFP_KERNEL); |
25 | bool test_complete; | |
26 | ||
27 | /* relentlessly fill the tree with tagged entries */ | |
28 | static void *add_entries_fn(void *arg) | |
29 | { | |
30 | int pgoff; | |
31 | ||
ba20cd60 MW |
32 | rcu_register_thread(); |
33 | ||
eec48525 RZ |
34 | while (!test_complete) { |
35 | for (pgoff = 0; pgoff < 100; pgoff++) { | |
36 | pthread_mutex_lock(&tree_lock); | |
37 | if (item_insert(&tree, pgoff) == 0) | |
38 | item_tag_set(&tree, pgoff, TAG); | |
39 | pthread_mutex_unlock(&tree_lock); | |
40 | } | |
41 | } | |
42 | ||
ba20cd60 MW |
43 | rcu_unregister_thread(); |
44 | ||
eec48525 RZ |
45 | return NULL; |
46 | } | |
47 | ||
48 | /* | |
49 | * Iterate over the tagged entries, doing a radix_tree_iter_retry() as we find | |
50 | * things that have been removed and randomly resetting our iteration to the | |
148deab2 MW |
51 | * next chunk with radix_tree_iter_resume(). Both radix_tree_iter_retry() and |
52 | * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a | |
eec48525 RZ |
53 | * NULL 'slot' variable. |
54 | */ | |
55 | static void *tagged_iteration_fn(void *arg) | |
56 | { | |
57 | struct radix_tree_iter iter; | |
58 | void **slot; | |
59 | ||
ba20cd60 MW |
60 | rcu_register_thread(); |
61 | ||
eec48525 RZ |
62 | while (!test_complete) { |
63 | rcu_read_lock(); | |
64 | radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) { | |
65 | void *entry; | |
66 | int i; | |
67 | ||
68 | /* busy wait to let removals happen */ | |
69 | for (i = 0; i < 1000000; i++) | |
70 | ; | |
71 | ||
72 | entry = radix_tree_deref_slot(slot); | |
73 | if (unlikely(!entry)) | |
74 | continue; | |
75 | ||
76 | if (radix_tree_deref_retry(entry)) { | |
77 | slot = radix_tree_iter_retry(&iter); | |
78 | continue; | |
79 | } | |
80 | ||
ba20cd60 | 81 | if (rand_r(&seeds[0]) % 50 == 0) { |
148deab2 | 82 | slot = radix_tree_iter_resume(slot, &iter); |
ba20cd60 MW |
83 | rcu_read_unlock(); |
84 | rcu_barrier(); | |
85 | rcu_read_lock(); | |
86 | } | |
eec48525 RZ |
87 | } |
88 | rcu_read_unlock(); | |
89 | } | |
90 | ||
ba20cd60 MW |
91 | rcu_unregister_thread(); |
92 | ||
eec48525 RZ |
93 | return NULL; |
94 | } | |
95 | ||
96 | /* | |
97 | * Iterate over the entries, doing a radix_tree_iter_retry() as we find things | |
98 | * that have been removed and randomly resetting our iteration to the next | |
148deab2 MW |
99 | * chunk with radix_tree_iter_resume(). Both radix_tree_iter_retry() and |
100 | * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a | |
eec48525 RZ |
101 | * NULL 'slot' variable. |
102 | */ | |
103 | static void *untagged_iteration_fn(void *arg) | |
104 | { | |
105 | struct radix_tree_iter iter; | |
106 | void **slot; | |
107 | ||
ba20cd60 MW |
108 | rcu_register_thread(); |
109 | ||
eec48525 RZ |
110 | while (!test_complete) { |
111 | rcu_read_lock(); | |
112 | radix_tree_for_each_slot(slot, &tree, &iter, 0) { | |
113 | void *entry; | |
114 | int i; | |
115 | ||
116 | /* busy wait to let removals happen */ | |
117 | for (i = 0; i < 1000000; i++) | |
118 | ; | |
119 | ||
120 | entry = radix_tree_deref_slot(slot); | |
121 | if (unlikely(!entry)) | |
122 | continue; | |
123 | ||
124 | if (radix_tree_deref_retry(entry)) { | |
125 | slot = radix_tree_iter_retry(&iter); | |
126 | continue; | |
127 | } | |
128 | ||
ba20cd60 | 129 | if (rand_r(&seeds[1]) % 50 == 0) { |
148deab2 | 130 | slot = radix_tree_iter_resume(slot, &iter); |
ba20cd60 MW |
131 | rcu_read_unlock(); |
132 | rcu_barrier(); | |
133 | rcu_read_lock(); | |
134 | } | |
eec48525 RZ |
135 | } |
136 | rcu_read_unlock(); | |
137 | } | |
138 | ||
ba20cd60 MW |
139 | rcu_unregister_thread(); |
140 | ||
eec48525 RZ |
141 | return NULL; |
142 | } | |
143 | ||
144 | /* | |
145 | * Randomly remove entries to help induce radix_tree_iter_retry() calls in the | |
146 | * two iteration functions. | |
147 | */ | |
148 | static void *remove_entries_fn(void *arg) | |
149 | { | |
ba20cd60 MW |
150 | rcu_register_thread(); |
151 | ||
eec48525 RZ |
152 | while (!test_complete) { |
153 | int pgoff; | |
154 | ||
061ef393 | 155 | pgoff = rand_r(&seeds[2]) % 100; |
eec48525 RZ |
156 | |
157 | pthread_mutex_lock(&tree_lock); | |
158 | item_delete(&tree, pgoff); | |
159 | pthread_mutex_unlock(&tree_lock); | |
160 | } | |
161 | ||
ba20cd60 MW |
162 | rcu_unregister_thread(); |
163 | ||
eec48525 RZ |
164 | return NULL; |
165 | } | |
166 | ||
167 | /* This is a unit test for a bug found by the syzkaller tester */ | |
168 | void iteration_test(void) | |
169 | { | |
170 | int i; | |
171 | ||
172 | printf("Running iteration tests for 10 seconds\n"); | |
173 | ||
eec48525 RZ |
174 | test_complete = false; |
175 | ||
061ef393 MW |
176 | for (i = 0; i < 3; i++) |
177 | seeds[i] = rand(); | |
178 | ||
eec48525 RZ |
179 | if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) { |
180 | perror("pthread_create"); | |
181 | exit(1); | |
182 | } | |
183 | if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) { | |
184 | perror("pthread_create"); | |
185 | exit(1); | |
186 | } | |
187 | if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) { | |
188 | perror("pthread_create"); | |
189 | exit(1); | |
190 | } | |
191 | if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) { | |
192 | perror("pthread_create"); | |
193 | exit(1); | |
194 | } | |
195 | ||
196 | sleep(10); | |
197 | test_complete = true; | |
198 | ||
199 | for (i = 0; i < NUM_THREADS; i++) { | |
200 | if (pthread_join(threads[i], NULL)) { | |
201 | perror("pthread_join"); | |
202 | exit(1); | |
203 | } | |
204 | } | |
205 | ||
206 | item_kill_tree(&tree); | |
207 | } |