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(void) 65 { 66 int i; 67 68 for (i = 0; i < 1000; 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 single_thread_tests(void) 236 { 237 int i; 238 239 tag_check(); 240 printf("after tag_check: %d allocated\n", nr_allocated); 241 gang_check(); 242 printf("after gang_check: %d allocated\n", nr_allocated); 243 add_and_check(); 244 printf("after add_and_check: %d allocated\n", nr_allocated); 245 dynamic_height_check(); 246 printf("after dynamic_height_check: %d allocated\n", nr_allocated); 247 big_gang_check(); 248 printf("after big_gang_check: %d allocated\n", nr_allocated); 249 for (i = 0; i < 2000; i++) { 250 copy_tag_check(); 251 printf("%d ", i); 252 fflush(stdout); 253 } 254 printf("after copy_tag_check: %d allocated\n", nr_allocated); 255 } 256 257 int main(void) 258 { 259 rcu_register_thread(); 260 radix_tree_init(); 261 262 regression1_test(); 263 regression2_test(); 264 regression3_test(); 265 single_thread_tests(); 266 267 sleep(1); 268 printf("after sleep(1): %d allocated\n", nr_allocated); 269 rcu_unregister_thread(); 270 271 exit(0); 272 } 273