1 // SPDX-License-Identifier: GPL-2.0
2 #include <stdlib.h>
3 #include <assert.h>
4 #include <stdio.h>
5 #include <string.h>
6
7 #include <linux/slab.h>
8 #include <linux/radix-tree.h>
9
10 #include "test.h"
11
12
13 static void
14 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
15 {
16 unsigned long first = 0;
17 int ret;
18
19 item_check_absent(tree, index);
20 assert(item_tag_get(tree, index, tag) == 0);
21
22 item_insert(tree, index);
23 assert(item_tag_get(tree, index, tag) == 0);
24 item_tag_set(tree, index, tag);
25 ret = item_tag_get(tree, index, tag);
26 assert(ret != 0);
27 ret = tag_tagged_items(tree, NULL, first, ~0UL, 10, tag, !tag);
28 assert(ret == 1);
29 ret = item_tag_get(tree, index, !tag);
30 assert(ret != 0);
31 ret = item_delete(tree, index);
32 assert(ret != 0);
33 item_insert(tree, index);
34 ret = item_tag_get(tree, index, tag);
35 assert(ret == 0);
36 ret = item_delete(tree, index);
37 assert(ret != 0);
38 ret = item_delete(tree, index);
39 assert(ret == 0);
40 }
41
42 void simple_checks(void)
43 {
44 unsigned long index;
45 RADIX_TREE(tree, GFP_KERNEL);
46
47 for (index = 0; index < 10000; index++) {
48 __simple_checks(&tree, index, 0);
49 __simple_checks(&tree, index, 1);
50 }
51 verify_tag_consistency(&tree, 0);
52 verify_tag_consistency(&tree, 1);
53 printv(2, "before item_kill_tree: %d allocated\n", nr_allocated);
54 item_kill_tree(&tree);
55 rcu_barrier();
56 printv(2, "after item_kill_tree: %d allocated\n", nr_allocated);
57 }
58
59 /*
60 * Check that tags propagate correctly when extending a tree.
61 */
62 static void extend_checks(void)
63 {
64 RADIX_TREE(tree, GFP_KERNEL);
65
66 item_insert(&tree, 43);
67 assert(item_tag_get(&tree, 43, 0) == 0);
68 item_tag_set(&tree, 43, 0);
69 assert(item_tag_get(&tree, 43, 0) == 1);
70 item_insert(&tree, 1000000);
71 assert(item_tag_get(&tree, 43, 0) == 1);
72
73 item_insert(&tree, 0);
74 item_tag_set(&tree, 0, 0);
75 item_delete(&tree, 1000000);
76 assert(item_tag_get(&tree, 43, 0) != 0);
77 item_delete(&tree, 43);
78 assert(item_tag_get(&tree, 43, 0) == 0); /* crash */
79 assert(item_tag_get(&tree, 0, 0) == 1);
80
81 verify_tag_consistency(&tree, 0);
82
83 item_kill_tree(&tree);
84 }
85
86 /*
87 * Check that tags propagate correctly when contracting a tree.
88 */
89 static void contract_checks(void)
90 {
91 struct item *item;
92 int tmp;
93 RADIX_TREE(tree, GFP_KERNEL);
94
95 tmp = 1<<RADIX_TREE_MAP_SHIFT;
96 item_insert(&tree, tmp);
97 item_insert(&tree, tmp+1);
98 item_tag_set(&tree, tmp, 0);
99 item_tag_set(&tree, tmp, 1);
100 item_tag_set(&tree, tmp+1, 0);
101 item_delete(&tree, tmp+1);
102 item_tag_clear(&tree, tmp, 1);
103
104 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1);
105 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0);
106
107 assert(item_tag_get(&tree, tmp, 0) == 1);
108 assert(item_tag_get(&tree, tmp, 1) == 0);
109
110 verify_tag_consistency(&tree, 0);
111 item_kill_tree(&tree);
112 }
113
114 /*
115 * Stupid tag thrasher
116 *
117 * Create a large linear array corresponding to the tree. Each element in
118 * the array is coherent with each node in the tree
119 */
120
121 enum {
122 NODE_ABSENT = 0,
123 NODE_PRESENT = 1,
124 NODE_TAGGED = 2,
125 };
126
127 #define THRASH_SIZE (1000 * 1000)
128 #define N 127
129 #define BATCH 33
130
131 static void gang_check(struct radix_tree_root *tree,
132 char *thrash_state, int tag)
133 {
134 struct item *items[BATCH];
135 int nr_found;
136 unsigned long index = 0;
137 unsigned long last_index = 0;
138
139 while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
140 index, BATCH, tag))) {
141 int i;
142
143 for (i = 0; i < nr_found; i++) {
144 struct item *item = items[i];
145
146 while (last_index < item->index) {
147 assert(thrash_state[last_index] != NODE_TAGGED);
148 last_index++;
149 }
150 assert(thrash_state[last_index] == NODE_TAGGED);
151 last_index++;
152 }
153 index = items[nr_found - 1]->index + 1;
154 }
155 }
156
157 static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag)
158 {
159 int insert_chunk;
160 int delete_chunk;
161 int tag_chunk;
162 int untag_chunk;
163 int total_tagged = 0;
164 int total_present = 0;
165
166 for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N)
167 for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N)
168 for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N)
169 for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) {
170 int i;
171 unsigned long index;
172 int nr_inserted = 0;
173 int nr_deleted = 0;
174 int nr_tagged = 0;
175 int nr_untagged = 0;
176 int actual_total_tagged;
177 int actual_total_present;
178
179 for (i = 0; i < insert_chunk; i++) {
180 index = rand() % THRASH_SIZE;
181 if (thrash_state[index] != NODE_ABSENT)
182 continue;
183 item_check_absent(tree, index);
184 item_insert(tree, index);
185 assert(thrash_state[index] != NODE_PRESENT);
186 thrash_state[index] = NODE_PRESENT;
187 nr_inserted++;
188 total_present++;
189 }
190
191 for (i = 0; i < delete_chunk; i++) {
192 index = rand() % THRASH_SIZE;
193 if (thrash_state[index] == NODE_ABSENT)
194 continue;
195 item_check_present(tree, index);
196 if (item_tag_get(tree, index, tag)) {
197 assert(thrash_state[index] == NODE_TAGGED);
198 total_tagged--;
199 } else {
200 assert(thrash_state[index] == NODE_PRESENT);
201 }
202 item_delete(tree, index);
203 assert(thrash_state[index] != NODE_ABSENT);
204 thrash_state[index] = NODE_ABSENT;
205 nr_deleted++;
206 total_present--;
207 }
208
209 for (i = 0; i < tag_chunk; i++) {
210 index = rand() % THRASH_SIZE;
211 if (thrash_state[index] != NODE_PRESENT) {
212 if (item_lookup(tree, index))
213 assert(item_tag_get(tree, index, tag));
214 continue;
215 }
216 item_tag_set(tree, index, tag);
217 item_tag_set(tree, index, tag);
218 assert(thrash_state[index] != NODE_TAGGED);
219 thrash_state[index] = NODE_TAGGED;
220 nr_tagged++;
221 total_tagged++;
222 }
223
224 for (i = 0; i < untag_chunk; i++) {
225 index = rand() % THRASH_SIZE;
226 if (thrash_state[index] != NODE_TAGGED)
227 continue;
228 item_check_present(tree, index);
229 assert(item_tag_get(tree, index, tag));
230 item_tag_clear(tree, index, tag);
231 item_tag_clear(tree, index, tag);
232 assert(thrash_state[index] != NODE_PRESENT);
233 thrash_state[index] = NODE_PRESENT;
234 nr_untagged++;
235 total_tagged--;
236 }
237
238 actual_total_tagged = 0;
239 actual_total_present = 0;
240 for (index = 0; index < THRASH_SIZE; index++) {
241 switch (thrash_state[index]) {
242 case NODE_ABSENT:
243 item_check_absent(tree, index);
244 break;
245 case NODE_PRESENT:
246 item_check_present(tree, index);
247 assert(!item_tag_get(tree, index, tag));
248 actual_total_present++;
249 break;
250 case NODE_TAGGED:
251 item_check_present(tree, index);
252 assert(item_tag_get(tree, index, tag));
253 actual_total_present++;
254 actual_total_tagged++;
255 break;
256 }
257 }
258
259 gang_check(tree, thrash_state, tag);
260
261 printv(2, "%d(%d) %d(%d) %d(%d) %d(%d) / "
262 "%d(%d) present, %d(%d) tagged\n",
263 insert_chunk, nr_inserted,
264 delete_chunk, nr_deleted,
265 tag_chunk, nr_tagged,
266 untag_chunk, nr_untagged,
267 total_present, actual_total_present,
268 total_tagged, actual_total_tagged);
269 }
270 }
271
272 static void thrash_tags(void)
273 {
274 RADIX_TREE(tree, GFP_KERNEL);
275 char *thrash_state;
276
277 thrash_state = malloc(THRASH_SIZE);
278 memset(thrash_state, 0, THRASH_SIZE);
279
280 do_thrash(&tree, thrash_state, 0);
281
282 verify_tag_consistency(&tree, 0);
283 item_kill_tree(&tree);
284 free(thrash_state);
285 }
286
287 static void leak_check(void)
288 {
289 RADIX_TREE(tree, GFP_KERNEL);
290
291 item_insert(&tree, 1000000);
292 item_delete(&tree, 1000000);
293 item_kill_tree(&tree);
294 }
295
296 static void __leak_check(void)
297 {
298 RADIX_TREE(tree, GFP_KERNEL);
299
300 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
301 item_insert(&tree, 1000000);
302 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
303 item_delete(&tree, 1000000);
304 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
305 item_kill_tree(&tree);
306 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
307 }
308
309 static void single_check(void)
310 {
311 struct item *items[BATCH];
312 RADIX_TREE(tree, GFP_KERNEL);
313 int ret;
314 unsigned long first = 0;
315
316 item_insert(&tree, 0);
317 item_tag_set(&tree, 0, 0);
318 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
319 assert(ret == 1);
320 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0);
321 assert(ret == 0);
322 verify_tag_consistency(&tree, 0);
323 verify_tag_consistency(&tree, 1);
324 ret = tag_tagged_items(&tree, NULL, first, 10, 10, 0, 1);
325 assert(ret == 1);
326 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
327 assert(ret == 1);
328 item_tag_clear(&tree, 0, 0);
329 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
330 assert(ret == 0);
331 item_kill_tree(&tree);
332 }
333
334 void radix_tree_clear_tags_test(void)
335 {
336 unsigned long index;
337 struct radix_tree_node *node;
338 struct radix_tree_iter iter;
339 void **slot;
340
341 RADIX_TREE(tree, GFP_KERNEL);
342
343 item_insert(&tree, 0);
344 item_tag_set(&tree, 0, 0);
345 __radix_tree_lookup(&tree, 0, &node, &slot);
346 radix_tree_clear_tags(&tree, node, slot);
347 assert(item_tag_get(&tree, 0, 0) == 0);
348
349 for (index = 0; index < 1000; index++) {
350 item_insert(&tree, index);
351 item_tag_set(&tree, index, 0);
352 }
353
354 radix_tree_for_each_slot(slot, &tree, &iter, 0) {
355 radix_tree_clear_tags(&tree, iter.node, slot);
356 assert(item_tag_get(&tree, iter.index, 0) == 0);
357 }
358
359 item_kill_tree(&tree);
360 }
361
362 void tag_check(void)
363 {
364 single_check();
365 extend_checks();
366 contract_checks();
367 rcu_barrier();
368 printv(2, "after extend_checks: %d allocated\n", nr_allocated);
369 __leak_check();
370 leak_check();
371 rcu_barrier();
372 printv(2, "after leak_check: %d allocated\n", nr_allocated);
373 simple_checks();
374 rcu_barrier();
375 printv(2, "after simple_checks: %d allocated\n", nr_allocated);
376 thrash_tags();
377 rcu_barrier();
378 printv(2, "after thrash_tags: %d allocated\n", nr_allocated);
379 radix_tree_clear_tags_test();
380 }
381
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.