331 lines · c
1// SPDX-License-Identifier: GPL-2.02#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 if (chunk > 0) {31 item_gang_check_present(&tree, middle - down, up + down,32 chunk, hop);33 item_full_scan(&tree, middle - down, down + up, chunk);34 }35 item_kill_tree(&tree);36}37 38void gang_check(void)39{40 __gang_check(1UL << 30, 128, 128, 35, 2);41 __gang_check(1UL << 31, 128, 128, 32, 32);42 __gang_check(1UL << 31, 128, 128, 32, 100);43 __gang_check(1UL << 31, 128, 128, 17, 7);44 __gang_check(0xffff0000UL, 0, 65536, 17, 7);45 __gang_check(0xfffffffeUL, 1, 1, 17, 7);46}47 48void __big_gang_check(void)49{50 unsigned long start;51 int wrapped = 0;52 53 start = 0;54 do {55 unsigned long old_start;56 57// printf("0x%08lx\n", start);58 __gang_check(start, rand() % 113 + 1, rand() % 71,59 rand() % 157, rand() % 91 + 1);60 old_start = start;61 start += rand() % 1000000;62 start %= 1ULL << 33;63 if (start < old_start)64 wrapped = 1;65 } while (!wrapped);66}67 68void big_gang_check(bool long_run)69{70 int i;71 72 for (i = 0; i < (long_run ? 1000 : 3); i++) {73 __big_gang_check();74 printv(2, "%d ", i);75 fflush(stdout);76 }77}78 79void add_and_check(void)80{81 RADIX_TREE(tree, GFP_KERNEL);82 83 item_insert(&tree, 44);84 item_check_present(&tree, 44);85 item_check_absent(&tree, 43);86 item_kill_tree(&tree);87}88 89void dynamic_height_check(void)90{91 int i;92 RADIX_TREE(tree, GFP_KERNEL);93 tree_verify_min_height(&tree, 0);94 95 item_insert(&tree, 42);96 tree_verify_min_height(&tree, 42);97 98 item_insert(&tree, 1000000);99 tree_verify_min_height(&tree, 1000000);100 101 assert(item_delete(&tree, 1000000));102 tree_verify_min_height(&tree, 42);103 104 assert(item_delete(&tree, 42));105 tree_verify_min_height(&tree, 0);106 107 for (i = 0; i < 1000; i++) {108 item_insert(&tree, i);109 tree_verify_min_height(&tree, i);110 }111 112 i--;113 for (;;) {114 assert(item_delete(&tree, i));115 if (i == 0) {116 tree_verify_min_height(&tree, 0);117 break;118 }119 i--;120 tree_verify_min_height(&tree, i);121 }122 123 item_kill_tree(&tree);124}125 126void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)127{128 int i;129 130 for (i = 0; i < count; i++) {131/* if (i % 1000 == 0)132 putchar('.'); */133 if (idx[i] < start || idx[i] > end) {134 if (item_tag_get(tree, idx[i], totag)) {135 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,136 end, idx[i], item_tag_get(tree, idx[i],137 fromtag),138 item_tag_get(tree, idx[i], totag));139 }140 assert(!item_tag_get(tree, idx[i], totag));141 continue;142 }143 if (item_tag_get(tree, idx[i], fromtag) ^144 item_tag_get(tree, idx[i], totag)) {145 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,146 idx[i], item_tag_get(tree, idx[i], fromtag),147 item_tag_get(tree, idx[i], totag));148 }149 assert(!(item_tag_get(tree, idx[i], fromtag) ^150 item_tag_get(tree, idx[i], totag)));151 }152}153 154#define ITEMS 50000155 156void copy_tag_check(void)157{158 RADIX_TREE(tree, GFP_KERNEL);159 unsigned long idx[ITEMS];160 unsigned long start, end, count = 0, tagged, cur, tmp;161 int i;162 163// printf("generating radix tree indices...\n");164 start = rand();165 end = rand();166 if (start > end && (rand() % 10)) {167 cur = start;168 start = end;169 end = cur;170 }171 /* Specifically create items around the start and the end of the range172 * with high probability to check for off by one errors */173 cur = rand();174 if (cur & 1) {175 item_insert(&tree, start);176 if (cur & 2) {177 if (start <= end)178 count++;179 item_tag_set(&tree, start, 0);180 }181 }182 if (cur & 4) {183 item_insert(&tree, start-1);184 if (cur & 8)185 item_tag_set(&tree, start-1, 0);186 }187 if (cur & 16) {188 item_insert(&tree, end);189 if (cur & 32) {190 if (start <= end)191 count++;192 item_tag_set(&tree, end, 0);193 }194 }195 if (cur & 64) {196 item_insert(&tree, end+1);197 if (cur & 128)198 item_tag_set(&tree, end+1, 0);199 }200 201 for (i = 0; i < ITEMS; i++) {202 do {203 idx[i] = rand();204 } while (item_lookup(&tree, idx[i]));205 206 item_insert(&tree, idx[i]);207 if (rand() & 1) {208 item_tag_set(&tree, idx[i], 0);209 if (idx[i] >= start && idx[i] <= end)210 count++;211 }212/* if (i % 1000 == 0)213 putchar('.'); */214 }215 216// printf("\ncopying tags...\n");217 tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);218 219// printf("checking copied tags\n");220 assert(tagged == count);221 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);222 223 /* Copy tags in several rounds */224// printf("\ncopying tags...\n");225 tmp = rand() % (count / 10 + 2);226 tagged = tag_tagged_items(&tree, start, end, tmp, XA_MARK_0, XA_MARK_2);227 assert(tagged == count);228 229// printf("%lu %lu %lu\n", tagged, tmp, count);230// printf("checking copied tags\n");231 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);232 verify_tag_consistency(&tree, 0);233 verify_tag_consistency(&tree, 1);234 verify_tag_consistency(&tree, 2);235// printf("\n");236 item_kill_tree(&tree);237}238 239static void single_thread_tests(bool long_run)240{241 int i;242 243 printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",244 nr_allocated, preempt_count);245 multiorder_checks();246 rcu_barrier();247 printv(2, "after multiorder_check: %d allocated, preempt %d\n",248 nr_allocated, preempt_count);249 tag_check();250 rcu_barrier();251 printv(2, "after tag_check: %d allocated, preempt %d\n",252 nr_allocated, preempt_count);253 gang_check();254 rcu_barrier();255 printv(2, "after gang_check: %d allocated, preempt %d\n",256 nr_allocated, preempt_count);257 add_and_check();258 rcu_barrier();259 printv(2, "after add_and_check: %d allocated, preempt %d\n",260 nr_allocated, preempt_count);261 dynamic_height_check();262 rcu_barrier();263 printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",264 nr_allocated, preempt_count);265 idr_checks();266 ida_tests();267 rcu_barrier();268 printv(2, "after idr_checks: %d allocated, preempt %d\n",269 nr_allocated, preempt_count);270 big_gang_check(long_run);271 rcu_barrier();272 printv(2, "after big_gang_check: %d allocated, preempt %d\n",273 nr_allocated, preempt_count);274 for (i = 0; i < (long_run ? 2000 : 3); i++) {275 copy_tag_check();276 printv(2, "%d ", i);277 fflush(stdout);278 }279 rcu_barrier();280 printv(2, "after copy_tag_check: %d allocated, preempt %d\n",281 nr_allocated, preempt_count);282}283 284int main(int argc, char **argv)285{286 bool long_run = false;287 int opt;288 unsigned int seed = time(NULL);289 290 while ((opt = getopt(argc, argv, "ls:v")) != -1) {291 if (opt == 'l')292 long_run = true;293 else if (opt == 's')294 seed = strtoul(optarg, NULL, 0);295 else if (opt == 'v')296 test_verbose++;297 }298 299 printf("random seed %u\n", seed);300 srand(seed);301 302 printf("running tests\n");303 304 rcu_register_thread();305 radix_tree_init();306 307 xarray_tests();308 regression1_test();309 regression2_test();310 regression3_test();311 regression4_test();312 iteration_test(0, 10 + 90 * long_run);313 iteration_test(7, 10 + 90 * long_run);314 iteration_test2(10 + 90 * long_run);315 single_thread_tests(long_run);316 317 /* Free any remaining preallocated nodes */318 radix_tree_cpu_dead(0);319 320 benchmark();321 322 rcu_barrier();323 printv(2, "after rcu_barrier: %d allocated, preempt %d\n",324 nr_allocated, preempt_count);325 rcu_unregister_thread();326 327 printf("tests completed\n");328 329 exit(0);330}331