testing/radix-tree/main.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include <stdio.h>
0003 #include <stdlib.h>
0004 #include <unistd.h>
0005 #include <time.h>
0006 #include <assert.h>
0007 #include <limits.h>
0008
0009 #include <linux/slab.h>
0010 #include <linux/radix-tree.h>
0011
0012 #include "test.h"
0013 #include "regression.h"
0014
0015 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
0016 {
0017     long idx;
0018     RADIX_TREE(tree, GFP_KERNEL);
0019
0020     middle = 1 << 30;
0021
0022     for (idx = -down; idx < up; idx++)
0023         item_insert(&tree, middle + idx);
0024
0025     item_check_absent(&tree, middle - down - 1);
0026     for (idx = -down; idx < up; idx++)
0027         item_check_present(&tree, middle + idx);
0028     item_check_absent(&tree, middle + up);
0029
0030     if (chunk > 0) {
0031         item_gang_check_present(&tree, middle - down, up + down,
0032                 chunk, hop);
0033         item_full_scan(&tree, middle - down, down + up, chunk);
0034     }
0035     item_kill_tree(&tree);
0036 }
0037
0038 void gang_check(void)
0039 {
0040     __gang_check(1UL << 30, 128, 128, 35, 2);
0041     __gang_check(1UL << 31, 128, 128, 32, 32);
0042     __gang_check(1UL << 31, 128, 128, 32, 100);
0043     __gang_check(1UL << 31, 128, 128, 17, 7);
0044     __gang_check(0xffff0000UL, 0, 65536, 17, 7);
0045     __gang_check(0xfffffffeUL, 1, 1, 17, 7);
0046 }
0047
0048 void __big_gang_check(void)
0049 {
0050     unsigned long start;
0051     int wrapped = 0;
0052
0053     start = 0;
0054     do {
0055         unsigned long old_start;
0056
0057 //      printf("0x%08lx\n", start);
0058         __gang_check(start, rand() % 113 + 1, rand() % 71,
0059                 rand() % 157, rand() % 91 + 1);
0060         old_start = start;
0061         start += rand() % 1000000;
0062         start %= 1ULL << 33;
0063         if (start < old_start)
0064             wrapped = 1;
0065     } while (!wrapped);
0066 }
0067
0068 void big_gang_check(bool long_run)
0069 {
0070     int i;
0071
0072     for (i = 0; i < (long_run ? 1000 : 3); i++) {
0073         __big_gang_check();
0074         printv(2, "%d ", i);
0075         fflush(stdout);
0076     }
0077 }
0078
0079 void add_and_check(void)
0080 {
0081     RADIX_TREE(tree, GFP_KERNEL);
0082
0083     item_insert(&tree, 44);
0084     item_check_present(&tree, 44);
0085     item_check_absent(&tree, 43);
0086     item_kill_tree(&tree);
0087 }
0088
0089 void dynamic_height_check(void)
0090 {
0091     int i;
0092     RADIX_TREE(tree, GFP_KERNEL);
0093     tree_verify_min_height(&tree, 0);
0094
0095     item_insert(&tree, 42);
0096     tree_verify_min_height(&tree, 42);
0097
0098     item_insert(&tree, 1000000);
0099     tree_verify_min_height(&tree, 1000000);
0100
0101     assert(item_delete(&tree, 1000000));
0102     tree_verify_min_height(&tree, 42);
0103
0104     assert(item_delete(&tree, 42));
0105     tree_verify_min_height(&tree, 0);
0106
0107     for (i = 0; i < 1000; i++) {
0108         item_insert(&tree, i);
0109         tree_verify_min_height(&tree, i);
0110     }
0111
0112     i--;
0113     for (;;) {
0114         assert(item_delete(&tree, i));
0115         if (i == 0) {
0116             tree_verify_min_height(&tree, 0);
0117             break;
0118         }
0119         i--;
0120         tree_verify_min_height(&tree, i);
0121     }
0122
0123     item_kill_tree(&tree);
0124 }
0125
0126 void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
0127 {
0128     int i;
0129
0130     for (i = 0; i < count; i++) {
0131 /*      if (i % 1000 == 0)
0132             putchar('.'); */
0133         if (idx[i] < start || idx[i] > end) {
0134             if (item_tag_get(tree, idx[i], totag)) {
0135                 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
0136                        end, idx[i], item_tag_get(tree, idx[i],
0137                                  fromtag),
0138                        item_tag_get(tree, idx[i], totag));
0139             }
0140             assert(!item_tag_get(tree, idx[i], totag));
0141             continue;
0142         }
0143         if (item_tag_get(tree, idx[i], fromtag) ^
0144             item_tag_get(tree, idx[i], totag)) {
0145             printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
0146                    idx[i], item_tag_get(tree, idx[i], fromtag),
0147                    item_tag_get(tree, idx[i], totag));
0148         }
0149         assert(!(item_tag_get(tree, idx[i], fromtag) ^
0150              item_tag_get(tree, idx[i], totag)));
0151     }
0152 }
0153
0154 #define ITEMS 50000
0155
0156 void copy_tag_check(void)
0157 {
0158     RADIX_TREE(tree, GFP_KERNEL);
0159     unsigned long idx[ITEMS];
0160     unsigned long start, end, count = 0, tagged, cur, tmp;
0161     int i;
0162
0163 //  printf("generating radix tree indices...\n");
0164     start = rand();
0165     end = rand();
0166     if (start > end && (rand() % 10)) {
0167         cur = start;
0168         start = end;
0169         end = cur;
0170     }
0171     /* Specifically create items around the start and the end of the range
0172      * with high probability to check for off by one errors */
0173     cur = rand();
0174     if (cur & 1) {
0175         item_insert(&tree, start);
0176         if (cur & 2) {
0177             if (start <= end)
0178                 count++;
0179             item_tag_set(&tree, start, 0);
0180         }
0181     }
0182     if (cur & 4) {
0183         item_insert(&tree, start-1);
0184         if (cur & 8)
0185             item_tag_set(&tree, start-1, 0);
0186     }
0187     if (cur & 16) {
0188         item_insert(&tree, end);
0189         if (cur & 32) {
0190             if (start <= end)
0191                 count++;
0192             item_tag_set(&tree, end, 0);
0193         }
0194     }
0195     if (cur & 64) {
0196         item_insert(&tree, end+1);
0197         if (cur & 128)
0198             item_tag_set(&tree, end+1, 0);
0199     }
0200
0201     for (i = 0; i < ITEMS; i++) {
0202         do {
0203             idx[i] = rand();
0204         } while (item_lookup(&tree, idx[i]));
0205
0206         item_insert(&tree, idx[i]);
0207         if (rand() & 1) {
0208             item_tag_set(&tree, idx[i], 0);
0209             if (idx[i] >= start && idx[i] <= end)
0210                 count++;
0211         }
0212 /*      if (i % 1000 == 0)
0213             putchar('.'); */
0214     }
0215
0216 //  printf("\ncopying tags...\n");
0217     tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);
0218
0219 //  printf("checking copied tags\n");
0220     assert(tagged == count);
0221     check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
0222
0223     /* Copy tags in several rounds */
0224 //  printf("\ncopying tags...\n");
0225     tmp = rand() % (count / 10 + 2);
0226     tagged = tag_tagged_items(&tree, start, end, tmp, XA_MARK_0, XA_MARK_2);
0227     assert(tagged == count);
0228
0229 //  printf("%lu %lu %lu\n", tagged, tmp, count);
0230 //  printf("checking copied tags\n");
0231     check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
0232     verify_tag_consistency(&tree, 0);
0233     verify_tag_consistency(&tree, 1);
0234     verify_tag_consistency(&tree, 2);
0235 //  printf("\n");
0236     item_kill_tree(&tree);
0237 }
0238
0239 static void single_thread_tests(bool long_run)
0240 {
0241     int i;
0242
0243     printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
0244         nr_allocated, preempt_count);
0245     multiorder_checks();
0246     rcu_barrier();
0247     printv(2, "after multiorder_check: %d allocated, preempt %d\n",
0248         nr_allocated, preempt_count);
0249     tag_check();
0250     rcu_barrier();
0251     printv(2, "after tag_check: %d allocated, preempt %d\n",
0252         nr_allocated, preempt_count);
0253     gang_check();
0254     rcu_barrier();
0255     printv(2, "after gang_check: %d allocated, preempt %d\n",
0256         nr_allocated, preempt_count);
0257     add_and_check();
0258     rcu_barrier();
0259     printv(2, "after add_and_check: %d allocated, preempt %d\n",
0260         nr_allocated, preempt_count);
0261     dynamic_height_check();
0262     rcu_barrier();
0263     printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
0264         nr_allocated, preempt_count);
0265     idr_checks();
0266     ida_tests();
0267     rcu_barrier();
0268     printv(2, "after idr_checks: %d allocated, preempt %d\n",
0269         nr_allocated, preempt_count);
0270     big_gang_check(long_run);
0271     rcu_barrier();
0272     printv(2, "after big_gang_check: %d allocated, preempt %d\n",
0273         nr_allocated, preempt_count);
0274     for (i = 0; i < (long_run ? 2000 : 3); i++) {
0275         copy_tag_check();
0276         printv(2, "%d ", i);
0277         fflush(stdout);
0278     }
0279     rcu_barrier();
0280     printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
0281         nr_allocated, preempt_count);
0282 }
0283
0284 int main(int argc, char **argv)
0285 {
0286     bool long_run = false;
0287     int opt;
0288     unsigned int seed = time(NULL);
0289
0290     while ((opt = getopt(argc, argv, "ls:v")) != -1) {
0291         if (opt == 'l')
0292             long_run = true;
0293         else if (opt == 's')
0294             seed = strtoul(optarg, NULL, 0);
0295         else if (opt == 'v')
0296             test_verbose++;
0297     }
0298
0299     printf("random seed %u\n", seed);
0300     srand(seed);
0301
0302     printf("running tests\n");
0303
0304     rcu_register_thread();
0305     radix_tree_init();
0306
0307     xarray_tests();
0308     regression1_test();
0309     regression2_test();
0310     regression3_test();
0311     regression4_test();
0312     iteration_test(0, 10 + 90 * long_run);
0313     iteration_test(7, 10 + 90 * long_run);
0314     iteration_test2(10 + 90 * long_run);
0315     single_thread_tests(long_run);
0316
0317     /* Free any remaining preallocated nodes */
0318     radix_tree_cpu_dead(0);
0319
0320     benchmark();
0321
0322     rcu_barrier();
0323     printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
0324         nr_allocated, preempt_count);
0325     rcu_unregister_thread();
0326
0327     printf("tests completed\n");
0328
0329     exit(0);
0330 }