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