Loading...
1#include <stdio.h>
2#include <stdlib.h>
3#include <unistd.h>
4#include <time.h>
5#include <assert.h>
6
7#include <linux/slab.h>
8#include <linux/radix-tree.h>
9
10#include "test.h"
11#include "regression.h"
12
13void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
14{
15 long idx;
16 RADIX_TREE(tree, GFP_KERNEL);
17
18 middle = 1 << 30;
19
20 for (idx = -down; idx < up; idx++)
21 item_insert(&tree, middle + idx);
22
23 item_check_absent(&tree, middle - down - 1);
24 for (idx = -down; idx < up; idx++)
25 item_check_present(&tree, middle + idx);
26 item_check_absent(&tree, middle + up);
27
28 item_gang_check_present(&tree, middle - down,
29 up + down, chunk, hop);
30 item_full_scan(&tree, middle - down, down + up, chunk);
31 item_kill_tree(&tree);
32}
33
34void gang_check(void)
35{
36 __gang_check(1 << 30, 128, 128, 35, 2);
37 __gang_check(1 << 31, 128, 128, 32, 32);
38 __gang_check(1 << 31, 128, 128, 32, 100);
39 __gang_check(1 << 31, 128, 128, 17, 7);
40 __gang_check(0xffff0000, 0, 65536, 17, 7);
41 __gang_check(0xfffffffe, 1, 1, 17, 7);
42}
43
44void __big_gang_check(void)
45{
46 unsigned long start;
47 int wrapped = 0;
48
49 start = 0;
50 do {
51 unsigned long old_start;
52
53// printf("0x%08lx\n", start);
54 __gang_check(start, rand() % 113 + 1, rand() % 71,
55 rand() % 157, rand() % 91 + 1);
56 old_start = start;
57 start += rand() % 1000000;
58 start %= 1ULL << 33;
59 if (start < old_start)
60 wrapped = 1;
61 } while (!wrapped);
62}
63
64void big_gang_check(bool long_run)
65{
66 int i;
67
68 for (i = 0; i < (long_run ? 1000 : 3); i++) {
69 __big_gang_check();
70 printf("%d ", i);
71 fflush(stdout);
72 }
73}
74
75void add_and_check(void)
76{
77 RADIX_TREE(tree, GFP_KERNEL);
78
79 item_insert(&tree, 44);
80 item_check_present(&tree, 44);
81 item_check_absent(&tree, 43);
82 item_kill_tree(&tree);
83}
84
85void dynamic_height_check(void)
86{
87 int i;
88 RADIX_TREE(tree, GFP_KERNEL);
89 tree_verify_min_height(&tree, 0);
90
91 item_insert(&tree, 42);
92 tree_verify_min_height(&tree, 42);
93
94 item_insert(&tree, 1000000);
95 tree_verify_min_height(&tree, 1000000);
96
97 assert(item_delete(&tree, 1000000));
98 tree_verify_min_height(&tree, 42);
99
100 assert(item_delete(&tree, 42));
101 tree_verify_min_height(&tree, 0);
102
103 for (i = 0; i < 1000; i++) {
104 item_insert(&tree, i);
105 tree_verify_min_height(&tree, i);
106 }
107
108 i--;
109 for (;;) {
110 assert(item_delete(&tree, i));
111 if (i == 0) {
112 tree_verify_min_height(&tree, 0);
113 break;
114 }
115 i--;
116 tree_verify_min_height(&tree, i);
117 }
118
119 item_kill_tree(&tree);
120}
121
122void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
123{
124 int i;
125
126 for (i = 0; i < count; i++) {
127/* if (i % 1000 == 0)
128 putchar('.'); */
129 if (idx[i] < start || idx[i] > end) {
130 if (item_tag_get(tree, idx[i], totag)) {
131 printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag));
132 }
133 assert(!item_tag_get(tree, idx[i], totag));
134 continue;
135 }
136 if (item_tag_get(tree, idx[i], fromtag) ^
137 item_tag_get(tree, idx[i], totag)) {
138 printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag));
139 }
140 assert(!(item_tag_get(tree, idx[i], fromtag) ^
141 item_tag_get(tree, idx[i], totag)));
142 }
143}
144
145#define ITEMS 50000
146
147void copy_tag_check(void)
148{
149 RADIX_TREE(tree, GFP_KERNEL);
150 unsigned long idx[ITEMS];
151 unsigned long start, end, count = 0, tagged, cur, tmp;
152 int i;
153
154// printf("generating radix tree indices...\n");
155 start = rand();
156 end = rand();
157 if (start > end && (rand() % 10)) {
158 cur = start;
159 start = end;
160 end = cur;
161 }
162 /* Specifically create items around the start and the end of the range
163 * with high probability to check for off by one errors */
164 cur = rand();
165 if (cur & 1) {
166 item_insert(&tree, start);
167 if (cur & 2) {
168 if (start <= end)
169 count++;
170 item_tag_set(&tree, start, 0);
171 }
172 }
173 if (cur & 4) {
174 item_insert(&tree, start-1);
175 if (cur & 8)
176 item_tag_set(&tree, start-1, 0);
177 }
178 if (cur & 16) {
179 item_insert(&tree, end);
180 if (cur & 32) {
181 if (start <= end)
182 count++;
183 item_tag_set(&tree, end, 0);
184 }
185 }
186 if (cur & 64) {
187 item_insert(&tree, end+1);
188 if (cur & 128)
189 item_tag_set(&tree, end+1, 0);
190 }
191
192 for (i = 0; i < ITEMS; i++) {
193 do {
194 idx[i] = rand();
195 } while (item_lookup(&tree, idx[i]));
196
197 item_insert(&tree, idx[i]);
198 if (rand() & 1) {
199 item_tag_set(&tree, idx[i], 0);
200 if (idx[i] >= start && idx[i] <= end)
201 count++;
202 }
203/* if (i % 1000 == 0)
204 putchar('.'); */
205 }
206
207// printf("\ncopying tags...\n");
208 tagged = tag_tagged_items(&tree, NULL, start, end, ITEMS, 0, 1);
209
210// printf("checking copied tags\n");
211 assert(tagged == count);
212 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
213
214 /* Copy tags in several rounds */
215// printf("\ncopying tags...\n");
216 tmp = rand() % (count / 10 + 2);
217 tagged = tag_tagged_items(&tree, NULL, start, end, tmp, 0, 2);
218 assert(tagged == count);
219
220// printf("%lu %lu %lu\n", tagged, tmp, count);
221// printf("checking copied tags\n");
222 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
223 verify_tag_consistency(&tree, 0);
224 verify_tag_consistency(&tree, 1);
225 verify_tag_consistency(&tree, 2);
226// printf("\n");
227 item_kill_tree(&tree);
228}
229
230static void __locate_check(struct radix_tree_root *tree, unsigned long index,
231 unsigned order)
232{
233 struct item *item;
234 unsigned long index2;
235
236 item_insert_order(tree, index, order);
237 item = item_lookup(tree, index);
238 index2 = find_item(tree, item);
239 if (index != index2) {
240 printf("index %ld order %d inserted; found %ld\n",
241 index, order, index2);
242 abort();
243 }
244}
245
246static void __order_0_locate_check(void)
247{
248 RADIX_TREE(tree, GFP_KERNEL);
249 int i;
250
251 for (i = 0; i < 50; i++)
252 __locate_check(&tree, rand() % INT_MAX, 0);
253
254 item_kill_tree(&tree);
255}
256
257static void locate_check(void)
258{
259 RADIX_TREE(tree, GFP_KERNEL);
260 unsigned order;
261 unsigned long offset, index;
262
263 __order_0_locate_check();
264
265 for (order = 0; order < 20; order++) {
266 for (offset = 0; offset < (1 << (order + 3));
267 offset += (1UL << order)) {
268 for (index = 0; index < (1UL << (order + 5));
269 index += (1UL << order)) {
270 __locate_check(&tree, index + offset, order);
271 }
272 if (find_item(&tree, &tree) != -1)
273 abort();
274
275 item_kill_tree(&tree);
276 }
277 }
278
279 if (find_item(&tree, &tree) != -1)
280 abort();
281 __locate_check(&tree, -1, 0);
282 if (find_item(&tree, &tree) != -1)
283 abort();
284 item_kill_tree(&tree);
285}
286
287static void single_thread_tests(bool long_run)
288{
289 int i;
290
291 printf("starting single_thread_tests: %d allocated, preempt %d\n",
292 nr_allocated, preempt_count);
293 multiorder_checks();
294 rcu_barrier();
295 printf("after multiorder_check: %d allocated, preempt %d\n",
296 nr_allocated, preempt_count);
297 locate_check();
298 rcu_barrier();
299 printf("after locate_check: %d allocated, preempt %d\n",
300 nr_allocated, preempt_count);
301 tag_check();
302 rcu_barrier();
303 printf("after tag_check: %d allocated, preempt %d\n",
304 nr_allocated, preempt_count);
305 gang_check();
306 rcu_barrier();
307 printf("after gang_check: %d allocated, preempt %d\n",
308 nr_allocated, preempt_count);
309 add_and_check();
310 rcu_barrier();
311 printf("after add_and_check: %d allocated, preempt %d\n",
312 nr_allocated, preempt_count);
313 dynamic_height_check();
314 rcu_barrier();
315 printf("after dynamic_height_check: %d allocated, preempt %d\n",
316 nr_allocated, preempt_count);
317 big_gang_check(long_run);
318 rcu_barrier();
319 printf("after big_gang_check: %d allocated, preempt %d\n",
320 nr_allocated, preempt_count);
321 for (i = 0; i < (long_run ? 2000 : 3); i++) {
322 copy_tag_check();
323 printf("%d ", i);
324 fflush(stdout);
325 }
326 rcu_barrier();
327 printf("after copy_tag_check: %d allocated, preempt %d\n",
328 nr_allocated, preempt_count);
329}
330
331int main(int argc, char **argv)
332{
333 bool long_run = false;
334 int opt;
335 unsigned int seed = time(NULL);
336
337 while ((opt = getopt(argc, argv, "ls:")) != -1) {
338 if (opt == 'l')
339 long_run = true;
340 else if (opt == 's')
341 seed = strtoul(optarg, NULL, 0);
342 }
343
344 printf("random seed %u\n", seed);
345 srand(seed);
346
347 rcu_register_thread();
348 radix_tree_init();
349
350 regression1_test();
351 regression2_test();
352 regression3_test();
353 iteration_test(0, 10);
354 iteration_test(7, 20);
355 single_thread_tests(long_run);
356
357 /* Free any remaining preallocated nodes */
358 radix_tree_cpu_dead(0);
359
360 benchmark();
361
362 rcu_barrier();
363 printf("after rcu_barrier: %d allocated, preempt %d\n",
364 nr_allocated, preempt_count);
365 rcu_unregister_thread();
366
367 exit(0);
368}
1// SPDX-License-Identifier: GPL-2.0
2#include <stdio.h>
3#include <stdlib.h>
4#include <unistd.h>
5#include <time.h>
6#include <assert.h>
7#include <limits.h>
8
9#include <linux/slab.h>
10#include <linux/radix-tree.h>
11
12#include "test.h"
13#include "regression.h"
14
15void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
16{
17 long idx;
18 RADIX_TREE(tree, GFP_KERNEL);
19
20 middle = 1 << 30;
21
22 for (idx = -down; idx < up; idx++)
23 item_insert(&tree, middle + idx);
24
25 item_check_absent(&tree, middle - down - 1);
26 for (idx = -down; idx < up; idx++)
27 item_check_present(&tree, middle + idx);
28 item_check_absent(&tree, middle + up);
29
30 item_gang_check_present(&tree, middle - down,
31 up + down, chunk, hop);
32 item_full_scan(&tree, middle - down, down + up, chunk);
33 item_kill_tree(&tree);
34}
35
36void gang_check(void)
37{
38 __gang_check(1 << 30, 128, 128, 35, 2);
39 __gang_check(1 << 31, 128, 128, 32, 32);
40 __gang_check(1 << 31, 128, 128, 32, 100);
41 __gang_check(1 << 31, 128, 128, 17, 7);
42 __gang_check(0xffff0000, 0, 65536, 17, 7);
43 __gang_check(0xfffffffe, 1, 1, 17, 7);
44}
45
46void __big_gang_check(void)
47{
48 unsigned long start;
49 int wrapped = 0;
50
51 start = 0;
52 do {
53 unsigned long old_start;
54
55// printf("0x%08lx\n", start);
56 __gang_check(start, rand() % 113 + 1, rand() % 71,
57 rand() % 157, rand() % 91 + 1);
58 old_start = start;
59 start += rand() % 1000000;
60 start %= 1ULL << 33;
61 if (start < old_start)
62 wrapped = 1;
63 } while (!wrapped);
64}
65
66void big_gang_check(bool long_run)
67{
68 int i;
69
70 for (i = 0; i < (long_run ? 1000 : 3); i++) {
71 __big_gang_check();
72 printv(2, "%d ", i);
73 fflush(stdout);
74 }
75}
76
77void add_and_check(void)
78{
79 RADIX_TREE(tree, GFP_KERNEL);
80
81 item_insert(&tree, 44);
82 item_check_present(&tree, 44);
83 item_check_absent(&tree, 43);
84 item_kill_tree(&tree);
85}
86
87void dynamic_height_check(void)
88{
89 int i;
90 RADIX_TREE(tree, GFP_KERNEL);
91 tree_verify_min_height(&tree, 0);
92
93 item_insert(&tree, 42);
94 tree_verify_min_height(&tree, 42);
95
96 item_insert(&tree, 1000000);
97 tree_verify_min_height(&tree, 1000000);
98
99 assert(item_delete(&tree, 1000000));
100 tree_verify_min_height(&tree, 42);
101
102 assert(item_delete(&tree, 42));
103 tree_verify_min_height(&tree, 0);
104
105 for (i = 0; i < 1000; i++) {
106 item_insert(&tree, i);
107 tree_verify_min_height(&tree, i);
108 }
109
110 i--;
111 for (;;) {
112 assert(item_delete(&tree, i));
113 if (i == 0) {
114 tree_verify_min_height(&tree, 0);
115 break;
116 }
117 i--;
118 tree_verify_min_height(&tree, i);
119 }
120
121 item_kill_tree(&tree);
122}
123
124void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
125{
126 int i;
127
128 for (i = 0; i < count; i++) {
129/* if (i % 1000 == 0)
130 putchar('.'); */
131 if (idx[i] < start || idx[i] > end) {
132 if (item_tag_get(tree, idx[i], totag)) {
133 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
134 end, idx[i], item_tag_get(tree, idx[i],
135 fromtag),
136 item_tag_get(tree, idx[i], totag));
137 }
138 assert(!item_tag_get(tree, idx[i], totag));
139 continue;
140 }
141 if (item_tag_get(tree, idx[i], fromtag) ^
142 item_tag_get(tree, idx[i], totag)) {
143 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
144 idx[i], item_tag_get(tree, idx[i], fromtag),
145 item_tag_get(tree, idx[i], totag));
146 }
147 assert(!(item_tag_get(tree, idx[i], fromtag) ^
148 item_tag_get(tree, idx[i], totag)));
149 }
150}
151
152#define ITEMS 50000
153
154void copy_tag_check(void)
155{
156 RADIX_TREE(tree, GFP_KERNEL);
157 unsigned long idx[ITEMS];
158 unsigned long start, end, count = 0, tagged, cur, tmp;
159 int i;
160
161// printf("generating radix tree indices...\n");
162 start = rand();
163 end = rand();
164 if (start > end && (rand() % 10)) {
165 cur = start;
166 start = end;
167 end = cur;
168 }
169 /* Specifically create items around the start and the end of the range
170 * with high probability to check for off by one errors */
171 cur = rand();
172 if (cur & 1) {
173 item_insert(&tree, start);
174 if (cur & 2) {
175 if (start <= end)
176 count++;
177 item_tag_set(&tree, start, 0);
178 }
179 }
180 if (cur & 4) {
181 item_insert(&tree, start-1);
182 if (cur & 8)
183 item_tag_set(&tree, start-1, 0);
184 }
185 if (cur & 16) {
186 item_insert(&tree, end);
187 if (cur & 32) {
188 if (start <= end)
189 count++;
190 item_tag_set(&tree, end, 0);
191 }
192 }
193 if (cur & 64) {
194 item_insert(&tree, end+1);
195 if (cur & 128)
196 item_tag_set(&tree, end+1, 0);
197 }
198
199 for (i = 0; i < ITEMS; i++) {
200 do {
201 idx[i] = rand();
202 } while (item_lookup(&tree, idx[i]));
203
204 item_insert(&tree, idx[i]);
205 if (rand() & 1) {
206 item_tag_set(&tree, idx[i], 0);
207 if (idx[i] >= start && idx[i] <= end)
208 count++;
209 }
210/* if (i % 1000 == 0)
211 putchar('.'); */
212 }
213
214// printf("\ncopying tags...\n");
215 tagged = tag_tagged_items(&tree, NULL, start, end, ITEMS, 0, 1);
216
217// printf("checking copied tags\n");
218 assert(tagged == count);
219 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
220
221 /* Copy tags in several rounds */
222// printf("\ncopying tags...\n");
223 tmp = rand() % (count / 10 + 2);
224 tagged = tag_tagged_items(&tree, NULL, start, end, tmp, 0, 2);
225 assert(tagged == count);
226
227// printf("%lu %lu %lu\n", tagged, tmp, count);
228// printf("checking copied tags\n");
229 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
230 verify_tag_consistency(&tree, 0);
231 verify_tag_consistency(&tree, 1);
232 verify_tag_consistency(&tree, 2);
233// printf("\n");
234 item_kill_tree(&tree);
235}
236
237static void __locate_check(struct radix_tree_root *tree, unsigned long index,
238 unsigned order)
239{
240 struct item *item;
241 unsigned long index2;
242
243 item_insert_order(tree, index, order);
244 item = item_lookup(tree, index);
245 index2 = find_item(tree, item);
246 if (index != index2) {
247 printv(2, "index %ld order %d inserted; found %ld\n",
248 index, order, index2);
249 abort();
250 }
251}
252
253static void __order_0_locate_check(void)
254{
255 RADIX_TREE(tree, GFP_KERNEL);
256 int i;
257
258 for (i = 0; i < 50; i++)
259 __locate_check(&tree, rand() % INT_MAX, 0);
260
261 item_kill_tree(&tree);
262}
263
264static void locate_check(void)
265{
266 RADIX_TREE(tree, GFP_KERNEL);
267 unsigned order;
268 unsigned long offset, index;
269
270 __order_0_locate_check();
271
272 for (order = 0; order < 20; order++) {
273 for (offset = 0; offset < (1 << (order + 3));
274 offset += (1UL << order)) {
275 for (index = 0; index < (1UL << (order + 5));
276 index += (1UL << order)) {
277 __locate_check(&tree, index + offset, order);
278 }
279 if (find_item(&tree, &tree) != -1)
280 abort();
281
282 item_kill_tree(&tree);
283 }
284 }
285
286 if (find_item(&tree, &tree) != -1)
287 abort();
288 __locate_check(&tree, -1, 0);
289 if (find_item(&tree, &tree) != -1)
290 abort();
291 item_kill_tree(&tree);
292}
293
294static void single_thread_tests(bool long_run)
295{
296 int i;
297
298 printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
299 nr_allocated, preempt_count);
300 multiorder_checks();
301 rcu_barrier();
302 printv(2, "after multiorder_check: %d allocated, preempt %d\n",
303 nr_allocated, preempt_count);
304 locate_check();
305 rcu_barrier();
306 printv(2, "after locate_check: %d allocated, preempt %d\n",
307 nr_allocated, preempt_count);
308 tag_check();
309 rcu_barrier();
310 printv(2, "after tag_check: %d allocated, preempt %d\n",
311 nr_allocated, preempt_count);
312 gang_check();
313 rcu_barrier();
314 printv(2, "after gang_check: %d allocated, preempt %d\n",
315 nr_allocated, preempt_count);
316 add_and_check();
317 rcu_barrier();
318 printv(2, "after add_and_check: %d allocated, preempt %d\n",
319 nr_allocated, preempt_count);
320 dynamic_height_check();
321 rcu_barrier();
322 printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
323 nr_allocated, preempt_count);
324 idr_checks();
325 ida_checks();
326 rcu_barrier();
327 printv(2, "after idr_checks: %d allocated, preempt %d\n",
328 nr_allocated, preempt_count);
329 big_gang_check(long_run);
330 rcu_barrier();
331 printv(2, "after big_gang_check: %d allocated, preempt %d\n",
332 nr_allocated, preempt_count);
333 for (i = 0; i < (long_run ? 2000 : 3); i++) {
334 copy_tag_check();
335 printv(2, "%d ", i);
336 fflush(stdout);
337 }
338 rcu_barrier();
339 printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
340 nr_allocated, preempt_count);
341}
342
343int main(int argc, char **argv)
344{
345 bool long_run = false;
346 int opt;
347 unsigned int seed = time(NULL);
348
349 while ((opt = getopt(argc, argv, "ls:v")) != -1) {
350 if (opt == 'l')
351 long_run = true;
352 else if (opt == 's')
353 seed = strtoul(optarg, NULL, 0);
354 else if (opt == 'v')
355 test_verbose++;
356 }
357
358 printf("random seed %u\n", seed);
359 srand(seed);
360
361 printf("running tests\n");
362
363 rcu_register_thread();
364 radix_tree_init();
365
366 regression1_test();
367 regression2_test();
368 regression3_test();
369 iteration_test(0, 10 + 90 * long_run);
370 iteration_test(7, 10 + 90 * long_run);
371 single_thread_tests(long_run);
372 ida_thread_tests();
373
374 /* Free any remaining preallocated nodes */
375 radix_tree_cpu_dead(0);
376
377 benchmark();
378
379 rcu_barrier();
380 printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
381 nr_allocated, preempt_count);
382 rcu_unregister_thread();
383
384 printf("tests completed\n");
385
386 exit(0);
387}