~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/testing/radix-tree/main.c

Version: ~ [ linux-6.4-rc3 ] ~ [ linux-6.3.4 ] ~ [ linux-6.2.16 ] ~ [ linux-6.1.30 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.113 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.180 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.243 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.283 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.315 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.4.302 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 
 15 void __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 
 36 void 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 
 46 void __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 
 66 void 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 
 77 void 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 
 87 void 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 
124 void 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 
154 void 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 
237 static 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 
253 static 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 
264 static 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 
294 static 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 
343 int 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 }
388 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp