1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <unistd.h> 4 #include <time.h> 5 #include <assert.h> 6 #include <limits.h> 7 8 #include <linux/slab.h> 9 #include <linux/radix-tree.h> 10 11 #include "test.h" 12 #include "regression.h" 13 14 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop) 15 { 16 long idx; 17 RADIX_TREE(tree, GFP_KERNEL); 18 19 middle = 1 << 30; 20 21 for (idx = -down; idx < up; idx++) 22 item_insert(&tree, middle + idx); 23 24 item_check_absent(&tree, middle - down - 1); 25 for (idx = -down; idx < up; idx++) 26 item_check_present(&tree, middle + idx); 27 item_check_absent(&tree, middle + up); 28 29 item_gang_check_present(&tree, middle - down, 30 up + down, chunk, hop); 31 item_full_scan(&tree, middle - down, down + up, chunk); 32 item_kill_tree(&tree); 33 } 34 35 void gang_check(void) 36 { 37 __gang_check(1 << 30, 128, 128, 35, 2); 38 __gang_check(1 << 31, 128, 128, 32, 32); 39 __gang_check(1 << 31, 128, 128, 32, 100); 40 __gang_check(1 << 31, 128, 128, 17, 7); 41 __gang_check(0xffff0000, 0, 65536, 17, 7); 42 __gang_check(0xfffffffe, 1, 1, 17, 7); 43 } 44 45 void __big_gang_check(void) 46 { 47 unsigned long start; 48 int wrapped = 0; 49 50 start = 0; 51 do { 52 unsigned long old_start; 53 54 // printf("0x%08lx\n", start); 55 __gang_check(start, rand() % 113 + 1, rand() % 71, 56 rand() % 157, rand() % 91 + 1); 57 old_start = start; 58 start += rand() % 1000000; 59 start %= 1ULL << 33; 60 if (start < old_start) 61 wrapped = 1; 62 } while (!wrapped); 63 } 64 65 void big_gang_check(bool long_run) 66 { 67 int i; 68 69 for (i = 0; i < (long_run ? 1000 : 3); i++) { 70 __big_gang_check(); 71 printv(2, "%d ", i); 72 fflush(stdout); 73 } 74 } 75 76 void add_and_check(void) 77 { 78 RADIX_TREE(tree, GFP_KERNEL); 79 80 item_insert(&tree, 44); 81 item_check_present(&tree, 44); 82 item_check_absent(&tree, 43); 83 item_kill_tree(&tree); 84 } 85 86 void dynamic_height_check(void) 87 { 88 int i; 89 RADIX_TREE(tree, GFP_KERNEL); 90 tree_verify_min_height(&tree, 0); 91 92 item_insert(&tree, 42); 93 tree_verify_min_height(&tree, 42); 94 95 item_insert(&tree, 1000000); 96 tree_verify_min_height(&tree, 1000000); 97 98 assert(item_delete(&tree, 1000000)); 99 tree_verify_min_height(&tree, 42); 100 101 assert(item_delete(&tree, 42)); 102 tree_verify_min_height(&tree, 0); 103 104 for (i = 0; i < 1000; i++) { 105 item_insert(&tree, i); 106 tree_verify_min_height(&tree, i); 107 } 108 109 i--; 110 for (;;) { 111 assert(item_delete(&tree, i)); 112 if (i == 0) { 113 tree_verify_min_height(&tree, 0); 114 break; 115 } 116 i--; 117 tree_verify_min_height(&tree, i); 118 } 119 120 item_kill_tree(&tree); 121 } 122 123 void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag) 124 { 125 int i; 126 127 for (i = 0; i < count; i++) { 128 /* if (i % 1000 == 0) 129 putchar('.'); */ 130 if (idx[i] < start || idx[i] > end) { 131 if (item_tag_get(tree, idx[i], totag)) { 132 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, 133 end, idx[i], item_tag_get(tree, idx[i], 134 fromtag), 135 item_tag_get(tree, idx[i], totag)); 136 } 137 assert(!item_tag_get(tree, idx[i], totag)); 138 continue; 139 } 140 if (item_tag_get(tree, idx[i], fromtag) ^ 141 item_tag_get(tree, idx[i], totag)) { 142 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end, 143 idx[i], item_tag_get(tree, idx[i], fromtag), 144 item_tag_get(tree, idx[i], totag)); 145 } 146 assert(!(item_tag_get(tree, idx[i], fromtag) ^ 147 item_tag_get(tree, idx[i], totag))); 148 } 149 } 150 151 #define ITEMS 50000 152 153 void copy_tag_check(void) 154 { 155 RADIX_TREE(tree, GFP_KERNEL); 156 unsigned long idx[ITEMS]; 157 unsigned long start, end, count = 0, tagged, cur, tmp; 158 int i; 159 160 // printf("generating radix tree indices...\n"); 161 start = rand(); 162 end = rand(); 163 if (start > end && (rand() % 10)) { 164 cur = start; 165 start = end; 166 end = cur; 167 } 168 /* Specifically create items around the start and the end of the range 169 * with high probability to check for off by one errors */ 170 cur = rand(); 171 if (cur & 1) { 172 item_insert(&tree, start); 173 if (cur & 2) { 174 if (start <= end) 175 count++; 176 item_tag_set(&tree, start, 0); 177 } 178 } 179 if (cur & 4) { 180 item_insert(&tree, start-1); 181 if (cur & 8) 182 item_tag_set(&tree, start-1, 0); 183 } 184 if (cur & 16) { 185 item_insert(&tree, end); 186 if (cur & 32) { 187 if (start <= end) 188 count++; 189 item_tag_set(&tree, end, 0); 190 } 191 } 192 if (cur & 64) { 193 item_insert(&tree, end+1); 194 if (cur & 128) 195 item_tag_set(&tree, end+1, 0); 196 } 197 198 for (i = 0; i < ITEMS; i++) { 199 do { 200 idx[i] = rand(); 201 } while (item_lookup(&tree, idx[i])); 202 203 item_insert(&tree, idx[i]); 204 if (rand() & 1) { 205 item_tag_set(&tree, idx[i], 0); 206 if (idx[i] >= start && idx[i] <= end) 207 count++; 208 } 209 /* if (i % 1000 == 0) 210 putchar('.'); */ 211 } 212 213 // printf("\ncopying tags...\n"); 214 tagged = tag_tagged_items(&tree, NULL, start, end, ITEMS, 0, 1); 215 216 // printf("checking copied tags\n"); 217 assert(tagged == count); 218 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1); 219 220 /* Copy tags in several rounds */ 221 // printf("\ncopying tags...\n"); 222 tmp = rand() % (count / 10 + 2); 223 tagged = tag_tagged_items(&tree, NULL, start, end, tmp, 0, 2); 224 assert(tagged == count); 225 226 // printf("%lu %lu %lu\n", tagged, tmp, count); 227 // printf("checking copied tags\n"); 228 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2); 229 verify_tag_consistency(&tree, 0); 230 verify_tag_consistency(&tree, 1); 231 verify_tag_consistency(&tree, 2); 232 // printf("\n"); 233 item_kill_tree(&tree); 234 } 235 236 static void __locate_check(struct radix_tree_root *tree, unsigned long index, 237 unsigned order) 238 { 239 struct item *item; 240 unsigned long index2; 241 242 item_insert_order(tree, index, order); 243 item = item_lookup(tree, index); 244 index2 = find_item(tree, item); 245 if (index != index2) { 246 printv(2, "index %ld order %d inserted; found %ld\n", 247 index, order, index2); 248 abort(); 249 } 250 } 251 252 static void __order_0_locate_check(void) 253 { 254 RADIX_TREE(tree, GFP_KERNEL); 255 int i; 256 257 for (i = 0; i < 50; i++) 258 __locate_check(&tree, rand() % INT_MAX, 0); 259 260 item_kill_tree(&tree); 261 } 262 263 static void locate_check(void) 264 { 265 RADIX_TREE(tree, GFP_KERNEL); 266 unsigned order; 267 unsigned long offset, index; 268 269 __order_0_locate_check(); 270 271 for (order = 0; order < 20; order++) { 272 for (offset = 0; offset < (1 << (order + 3)); 273 offset += (1UL << order)) { 274 for (index = 0; index < (1UL << (order + 5)); 275 index += (1UL << order)) { 276 __locate_check(&tree, index + offset, order); 277 } 278 if (find_item(&tree, &tree) != -1) 279 abort(); 280 281 item_kill_tree(&tree); 282 } 283 } 284 285 if (find_item(&tree, &tree) != -1) 286 abort(); 287 __locate_check(&tree, -1, 0); 288 if (find_item(&tree, &tree) != -1) 289 abort(); 290 item_kill_tree(&tree); 291 } 292 293 static void single_thread_tests(bool long_run) 294 { 295 int i; 296 297 printv(1, "starting single_thread_tests: %d allocated, preempt %d\n", 298 nr_allocated, preempt_count); 299 multiorder_checks(); 300 rcu_barrier(); 301 printv(2, "after multiorder_check: %d allocated, preempt %d\n", 302 nr_allocated, preempt_count); 303 locate_check(); 304 rcu_barrier(); 305 printv(2, "after locate_check: %d allocated, preempt %d\n", 306 nr_allocated, preempt_count); 307 tag_check(); 308 rcu_barrier(); 309 printv(2, "after tag_check: %d allocated, preempt %d\n", 310 nr_allocated, preempt_count); 311 gang_check(); 312 rcu_barrier(); 313 printv(2, "after gang_check: %d allocated, preempt %d\n", 314 nr_allocated, preempt_count); 315 add_and_check(); 316 rcu_barrier(); 317 printv(2, "after add_and_check: %d allocated, preempt %d\n", 318 nr_allocated, preempt_count); 319 dynamic_height_check(); 320 rcu_barrier(); 321 printv(2, "after dynamic_height_check: %d allocated, preempt %d\n", 322 nr_allocated, preempt_count); 323 idr_checks(); 324 ida_checks(); 325 rcu_barrier(); 326 printv(2, "after idr_checks: %d allocated, preempt %d\n", 327 nr_allocated, preempt_count); 328 big_gang_check(long_run); 329 rcu_barrier(); 330 printv(2, "after big_gang_check: %d allocated, preempt %d\n", 331 nr_allocated, preempt_count); 332 for (i = 0; i < (long_run ? 2000 : 3); i++) { 333 copy_tag_check(); 334 printv(2, "%d ", i); 335 fflush(stdout); 336 } 337 rcu_barrier(); 338 printv(2, "after copy_tag_check: %d allocated, preempt %d\n", 339 nr_allocated, preempt_count); 340 } 341 342 int main(int argc, char **argv) 343 { 344 bool long_run = false; 345 int opt; 346 unsigned int seed = time(NULL); 347 348 while ((opt = getopt(argc, argv, "ls:v")) != -1) { 349 if (opt == 'l') 350 long_run = true; 351 else if (opt == 's') 352 seed = strtoul(optarg, NULL, 0); 353 else if (opt == 'v') 354 test_verbose++; 355 } 356 357 printf("random seed %u\n", seed); 358 srand(seed); 359 360 printf("running tests\n"); 361 362 rcu_register_thread(); 363 radix_tree_init(); 364 365 regression1_test(); 366 regression2_test(); 367 regression3_test(); 368 iteration_test(0, 10 + 90 * long_run); 369 iteration_test(7, 10 + 90 * long_run); 370 single_thread_tests(long_run); 371 ida_thread_tests(); 372 373 /* Free any remaining preallocated nodes */ 374 radix_tree_cpu_dead(0); 375 376 benchmark(); 377 378 rcu_barrier(); 379 printv(2, "after rcu_barrier: %d allocated, preempt %d\n", 380 nr_allocated, preempt_count); 381 rcu_unregister_thread(); 382 383 printf("tests completed\n"); 384 385 exit(0); 386 } 387