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