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 srand(time(0)); 71 printf("%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 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)); 133 } 134 assert(!item_tag_get(tree, idx[i], totag)); 135 continue; 136 } 137 if (item_tag_get(tree, idx[i], fromtag) ^ 138 item_tag_get(tree, idx[i], totag)) { 139 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)); 140 } 141 assert(!(item_tag_get(tree, idx[i], fromtag) ^ 142 item_tag_get(tree, idx[i], totag))); 143 } 144 } 145 146 #define ITEMS 50000 147 148 void copy_tag_check(void) 149 { 150 RADIX_TREE(tree, GFP_KERNEL); 151 unsigned long idx[ITEMS]; 152 unsigned long start, end, count = 0, tagged, cur, tmp; 153 int i; 154 155 // printf("generating radix tree indices...\n"); 156 start = rand(); 157 end = rand(); 158 if (start > end && (rand() % 10)) { 159 cur = start; 160 start = end; 161 end = cur; 162 } 163 /* Specifically create items around the start and the end of the range 164 * with high probability to check for off by one errors */ 165 cur = rand(); 166 if (cur & 1) { 167 item_insert(&tree, start); 168 if (cur & 2) { 169 if (start <= end) 170 count++; 171 item_tag_set(&tree, start, 0); 172 } 173 } 174 if (cur & 4) { 175 item_insert(&tree, start-1); 176 if (cur & 8) 177 item_tag_set(&tree, start-1, 0); 178 } 179 if (cur & 16) { 180 item_insert(&tree, end); 181 if (cur & 32) { 182 if (start <= end) 183 count++; 184 item_tag_set(&tree, end, 0); 185 } 186 } 187 if (cur & 64) { 188 item_insert(&tree, end+1); 189 if (cur & 128) 190 item_tag_set(&tree, end+1, 0); 191 } 192 193 for (i = 0; i < ITEMS; i++) { 194 do { 195 idx[i] = rand(); 196 } while (item_lookup(&tree, idx[i])); 197 198 item_insert(&tree, idx[i]); 199 if (rand() & 1) { 200 item_tag_set(&tree, idx[i], 0); 201 if (idx[i] >= start && idx[i] <= end) 202 count++; 203 } 204 /* if (i % 1000 == 0) 205 putchar('.'); */ 206 } 207 208 // printf("\ncopying tags...\n"); 209 cur = start; 210 tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1); 211 212 // printf("checking copied tags\n"); 213 assert(tagged == count); 214 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1); 215 216 /* Copy tags in several rounds */ 217 // printf("\ncopying tags...\n"); 218 cur = start; 219 do { 220 tmp = rand() % (count/10+2); 221 tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2); 222 } while (tmp == tagged); 223 224 // printf("%lu %lu %lu\n", tagged, tmp, count); 225 // printf("checking copied tags\n"); 226 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2); 227 assert(tagged < tmp); 228 verify_tag_consistency(&tree, 0); 229 verify_tag_consistency(&tree, 1); 230 verify_tag_consistency(&tree, 2); 231 // printf("\n"); 232 item_kill_tree(&tree); 233 } 234 235 static void __locate_check(struct radix_tree_root *tree, unsigned long index, 236 unsigned order) 237 { 238 struct item *item; 239 unsigned long index2; 240 241 item_insert_order(tree, index, order); 242 item = item_lookup(tree, index); 243 index2 = radix_tree_locate_item(tree, item); 244 if (index != index2) { 245 printf("index %ld order %d inserted; found %ld\n", 246 index, order, index2); 247 abort(); 248 } 249 } 250 251 static void __order_0_locate_check(void) 252 { 253 RADIX_TREE(tree, GFP_KERNEL); 254 int i; 255 256 for (i = 0; i < 50; i++) 257 __locate_check(&tree, rand() % INT_MAX, 0); 258 259 item_kill_tree(&tree); 260 } 261 262 static void locate_check(void) 263 { 264 RADIX_TREE(tree, GFP_KERNEL); 265 unsigned order; 266 unsigned long offset, index; 267 268 __order_0_locate_check(); 269 270 for (order = 0; order < 20; order++) { 271 for (offset = 0; offset < (1 << (order + 3)); 272 offset += (1UL << order)) { 273 for (index = 0; index < (1UL << (order + 5)); 274 index += (1UL << order)) { 275 __locate_check(&tree, index + offset, order); 276 } 277 if (radix_tree_locate_item(&tree, &tree) != -1) 278 abort(); 279 280 item_kill_tree(&tree); 281 } 282 } 283 284 if (radix_tree_locate_item(&tree, &tree) != -1) 285 abort(); 286 __locate_check(&tree, -1, 0); 287 if (radix_tree_locate_item(&tree, &tree) != -1) 288 abort(); 289 item_kill_tree(&tree); 290 } 291 292 static void single_thread_tests(bool long_run) 293 { 294 int i; 295 296 printf("starting single_thread_tests: %d allocated\n", nr_allocated); 297 multiorder_checks(); 298 printf("after multiorder_check: %d allocated\n", nr_allocated); 299 locate_check(); 300 printf("after locate_check: %d allocated\n", nr_allocated); 301 tag_check(); 302 printf("after tag_check: %d allocated\n", nr_allocated); 303 gang_check(); 304 printf("after gang_check: %d allocated\n", nr_allocated); 305 add_and_check(); 306 printf("after add_and_check: %d allocated\n", nr_allocated); 307 dynamic_height_check(); 308 printf("after dynamic_height_check: %d allocated\n", nr_allocated); 309 big_gang_check(long_run); 310 printf("after big_gang_check: %d allocated\n", nr_allocated); 311 for (i = 0; i < (long_run ? 2000 : 3); i++) { 312 copy_tag_check(); 313 printf("%d ", i); 314 fflush(stdout); 315 } 316 printf("after copy_tag_check: %d allocated\n", nr_allocated); 317 } 318 319 int main(int argc, char **argv) 320 { 321 bool long_run = false; 322 int opt; 323 324 while ((opt = getopt(argc, argv, "l")) != -1) { 325 if (opt == 'l') 326 long_run = true; 327 } 328 329 rcu_register_thread(); 330 radix_tree_init(); 331 332 regression1_test(); 333 regression2_test(); 334 regression3_test(); 335 single_thread_tests(long_run); 336 337 sleep(1); 338 printf("after sleep(1): %d allocated\n", nr_allocated); 339 rcu_unregister_thread(); 340 341 exit(0); 342 } 343