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 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 38 void 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 48 void __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 68 void 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 79 void 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 89 void 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 126 void 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 50000 155 156 void 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 range 172 * 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, NULL, start, end, ITEMS, 0, 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, NULL, start, end, tmp, 0, 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 239 static void __locate_check(struct radix_tree_root *tree, unsigned long index, 240 unsigned order) 241 { 242 struct item *item; 243 unsigned long index2; 244 245 item_insert_order(tree, index, order); 246 item = item_lookup(tree, index); 247 index2 = find_item(tree, item); 248 if (index != index2) { 249 printv(2, "index %ld order %d inserted; found %ld\n", 250 index, order, index2); 251 abort(); 252 } 253 } 254 255 static void __order_0_locate_check(void) 256 { 257 RADIX_TREE(tree, GFP_KERNEL); 258 int i; 259 260 for (i = 0; i < 50; i++) 261 __locate_check(&tree, rand() % INT_MAX, 0); 262 263 item_kill_tree(&tree); 264 } 265 266 static void locate_check(void) 267 { 268 RADIX_TREE(tree, GFP_KERNEL); 269 unsigned order; 270 unsigned long offset, index; 271 272 __order_0_locate_check(); 273 274 for (order = 0; order < 20; order++) { 275 for (offset = 0; offset < (1 << (order + 3)); 276 offset += (1UL << order)) { 277 for (index = 0; index < (1UL << (order + 5)); 278 index += (1UL << order)) { 279 __locate_check(&tree, index + offset, order); 280 } 281 if (find_item(&tree, &tree) != -1) 282 abort(); 283 284 item_kill_tree(&tree); 285 } 286 } 287 288 if (find_item(&tree, &tree) != -1) 289 abort(); 290 __locate_check(&tree, -1, 0); 291 if (find_item(&tree, &tree) != -1) 292 abort(); 293 item_kill_tree(&tree); 294 } 295 296 static void single_thread_tests(bool long_run) 297 { 298 int i; 299 300 printv(1, "starting single_thread_tests: %d allocated, preempt %d\n", 301 nr_allocated, preempt_count); 302 multiorder_checks(); 303 rcu_barrier(); 304 printv(2, "after multiorder_check: %d allocated, preempt %d\n", 305 nr_allocated, preempt_count); 306 locate_check(); 307 rcu_barrier(); 308 printv(2, "after locate_check: %d allocated, preempt %d\n", 309 nr_allocated, preempt_count); 310 tag_check(); 311 rcu_barrier(); 312 printv(2, "after tag_check: %d allocated, preempt %d\n", 313 nr_allocated, preempt_count); 314 gang_check(); 315 rcu_barrier(); 316 printv(2, "after gang_check: %d allocated, preempt %d\n", 317 nr_allocated, preempt_count); 318 add_and_check(); 319 rcu_barrier(); 320 printv(2, "after add_and_check: %d allocated, preempt %d\n", 321 nr_allocated, preempt_count); 322 dynamic_height_check(); 323 rcu_barrier(); 324 printv(2, "after dynamic_height_check: %d allocated, preempt %d\n", 325 nr_allocated, preempt_count); 326 idr_checks(); 327 ida_tests(); 328 rcu_barrier(); 329 printv(2, "after idr_checks: %d allocated, preempt %d\n", 330 nr_allocated, preempt_count); 331 big_gang_check(long_run); 332 rcu_barrier(); 333 printv(2, "after big_gang_check: %d allocated, preempt %d\n", 334 nr_allocated, preempt_count); 335 for (i = 0; i < (long_run ? 2000 : 3); i++) { 336 copy_tag_check(); 337 printv(2, "%d ", i); 338 fflush(stdout); 339 } 340 rcu_barrier(); 341 printv(2, "after copy_tag_check: %d allocated, preempt %d\n", 342 nr_allocated, preempt_count); 343 } 344 345 int main(int argc, char **argv) 346 { 347 bool long_run = false; 348 int opt; 349 unsigned int seed = time(NULL); 350 351 while ((opt = getopt(argc, argv, "ls:v")) != -1) { 352 if (opt == 'l') 353 long_run = true; 354 else if (opt == 's') 355 seed = strtoul(optarg, NULL, 0); 356 else if (opt == 'v') 357 test_verbose++; 358 } 359 360 printf("random seed %u\n", seed); 361 srand(seed); 362 363 printf("running tests\n"); 364 365 rcu_register_thread(); 366 radix_tree_init(); 367 368 regression1_test(); 369 regression2_test(); 370 regression3_test(); 371 iteration_test(0, 10 + 90 * long_run); 372 iteration_test(7, 10 + 90 * long_run); 373 single_thread_tests(long_run); 374 375 /* Free any remaining preallocated nodes */ 376 radix_tree_cpu_dead(0); 377 378 benchmark(); 379 380 rcu_barrier(); 381 printv(2, "after rcu_barrier: %d allocated, preempt %d\n", 382 nr_allocated, preempt_count); 383 rcu_unregister_thread(); 384 385 printf("tests completed\n"); 386 387 exit(0); 388 } 389