1 #include <stdlib.h> 2 #include <assert.h> 3 #include <stdio.h> 4 #include <string.h> 5 6 #include <linux/slab.h> 7 #include <linux/radix-tree.h> 8 9 #include "test.h" 10 11 12 static void 13 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag) 14 { 15 int ret; 16 17 item_check_absent(tree, index); 18 assert(item_tag_get(tree, index, tag) == 0); 19 20 item_insert(tree, index); 21 assert(item_tag_get(tree, index, tag) == 0); 22 item_tag_set(tree, index, tag); 23 ret = item_tag_get(tree, index, tag); 24 assert(ret != 0); 25 ret = item_delete(tree, index); 26 assert(ret != 0); 27 item_insert(tree, index); 28 ret = item_tag_get(tree, index, tag); 29 assert(ret == 0); 30 ret = item_delete(tree, index); 31 assert(ret != 0); 32 ret = item_delete(tree, index); 33 assert(ret == 0); 34 } 35 36 void simple_checks(void) 37 { 38 unsigned long index; 39 RADIX_TREE(tree, GFP_KERNEL); 40 41 for (index = 0; index < 10000; index++) { 42 __simple_checks(&tree, index, 0); 43 __simple_checks(&tree, index, 1); 44 } 45 verify_tag_consistency(&tree, 0); 46 verify_tag_consistency(&tree, 1); 47 printf("before item_kill_tree: %d allocated\n", nr_allocated); 48 item_kill_tree(&tree); 49 printf("after item_kill_tree: %d allocated\n", nr_allocated); 50 } 51 52 /* 53 * Check that tags propagate correctly when extending a tree. 54 */ 55 static void extend_checks(void) 56 { 57 RADIX_TREE(tree, GFP_KERNEL); 58 59 item_insert(&tree, 43); 60 assert(item_tag_get(&tree, 43, 0) == 0); 61 item_tag_set(&tree, 43, 0); 62 assert(item_tag_get(&tree, 43, 0) == 1); 63 item_insert(&tree, 1000000); 64 assert(item_tag_get(&tree, 43, 0) == 1); 65 66 item_insert(&tree, 0); 67 item_tag_set(&tree, 0, 0); 68 item_delete(&tree, 1000000); 69 assert(item_tag_get(&tree, 43, 0) != 0); 70 item_delete(&tree, 43); 71 assert(item_tag_get(&tree, 43, 0) == 0); /* crash */ 72 assert(item_tag_get(&tree, 0, 0) == 1); 73 74 verify_tag_consistency(&tree, 0); 75 76 item_kill_tree(&tree); 77 } 78 79 /* 80 * Check that tags propagate correctly when contracting a tree. 81 */ 82 static void contract_checks(void) 83 { 84 struct item *item; 85 int tmp; 86 RADIX_TREE(tree, GFP_KERNEL); 87 88 tmp = 1<<RADIX_TREE_MAP_SHIFT; 89 item_insert(&tree, tmp); 90 item_insert(&tree, tmp+1); 91 item_tag_set(&tree, tmp, 0); 92 item_tag_set(&tree, tmp, 1); 93 item_tag_set(&tree, tmp+1, 0); 94 item_delete(&tree, tmp+1); 95 item_tag_clear(&tree, tmp, 1); 96 97 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1); 98 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0); 99 100 assert(item_tag_get(&tree, tmp, 0) == 1); 101 assert(item_tag_get(&tree, tmp, 1) == 0); 102 103 verify_tag_consistency(&tree, 0); 104 item_kill_tree(&tree); 105 } 106 107 /* 108 * Stupid tag thrasher 109 * 110 * Create a large linear array corresponding to the tree. Each element in 111 * the array is coherent with each node in the tree 112 */ 113 114 enum { 115 NODE_ABSENT = 0, 116 NODE_PRESENT = 1, 117 NODE_TAGGED = 2, 118 }; 119 120 #define THRASH_SIZE 1000 * 1000 121 #define N 127 122 #define BATCH 33 123 124 static void gang_check(struct radix_tree_root *tree, 125 char *thrash_state, int tag) 126 { 127 struct item *items[BATCH]; 128 int nr_found; 129 unsigned long index = 0; 130 unsigned long last_index = 0; 131 132 while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items, 133 index, BATCH, tag))) { 134 int i; 135 136 for (i = 0; i < nr_found; i++) { 137 struct item *item = items[i]; 138 139 while (last_index < item->index) { 140 assert(thrash_state[last_index] != NODE_TAGGED); 141 last_index++; 142 } 143 assert(thrash_state[last_index] == NODE_TAGGED); 144 last_index++; 145 } 146 index = items[nr_found - 1]->index + 1; 147 } 148 } 149 150 static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag) 151 { 152 int insert_chunk; 153 int delete_chunk; 154 int tag_chunk; 155 int untag_chunk; 156 int total_tagged = 0; 157 int total_present = 0; 158 159 for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N) 160 for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N) 161 for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N) 162 for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) { 163 int i; 164 unsigned long index; 165 int nr_inserted = 0; 166 int nr_deleted = 0; 167 int nr_tagged = 0; 168 int nr_untagged = 0; 169 int actual_total_tagged; 170 int actual_total_present; 171 172 for (i = 0; i < insert_chunk; i++) { 173 index = rand() % THRASH_SIZE; 174 if (thrash_state[index] != NODE_ABSENT) 175 continue; 176 item_check_absent(tree, index); 177 item_insert(tree, index); 178 assert(thrash_state[index] != NODE_PRESENT); 179 thrash_state[index] = NODE_PRESENT; 180 nr_inserted++; 181 total_present++; 182 } 183 184 for (i = 0; i < delete_chunk; i++) { 185 index = rand() % THRASH_SIZE; 186 if (thrash_state[index] == NODE_ABSENT) 187 continue; 188 item_check_present(tree, index); 189 if (item_tag_get(tree, index, tag)) { 190 assert(thrash_state[index] == NODE_TAGGED); 191 total_tagged--; 192 } else { 193 assert(thrash_state[index] == NODE_PRESENT); 194 } 195 item_delete(tree, index); 196 assert(thrash_state[index] != NODE_ABSENT); 197 thrash_state[index] = NODE_ABSENT; 198 nr_deleted++; 199 total_present--; 200 } 201 202 for (i = 0; i < tag_chunk; i++) { 203 index = rand() % THRASH_SIZE; 204 if (thrash_state[index] != NODE_PRESENT) { 205 if (item_lookup(tree, index)) 206 assert(item_tag_get(tree, index, tag)); 207 continue; 208 } 209 item_tag_set(tree, index, tag); 210 item_tag_set(tree, index, tag); 211 assert(thrash_state[index] != NODE_TAGGED); 212 thrash_state[index] = NODE_TAGGED; 213 nr_tagged++; 214 total_tagged++; 215 } 216 217 for (i = 0; i < untag_chunk; i++) { 218 index = rand() % THRASH_SIZE; 219 if (thrash_state[index] != NODE_TAGGED) 220 continue; 221 item_check_present(tree, index); 222 assert(item_tag_get(tree, index, tag)); 223 item_tag_clear(tree, index, tag); 224 item_tag_clear(tree, index, tag); 225 assert(thrash_state[index] != NODE_PRESENT); 226 thrash_state[index] = NODE_PRESENT; 227 nr_untagged++; 228 total_tagged--; 229 } 230 231 actual_total_tagged = 0; 232 actual_total_present = 0; 233 for (index = 0; index < THRASH_SIZE; index++) { 234 switch (thrash_state[index]) { 235 case NODE_ABSENT: 236 item_check_absent(tree, index); 237 break; 238 case NODE_PRESENT: 239 item_check_present(tree, index); 240 assert(!item_tag_get(tree, index, tag)); 241 actual_total_present++; 242 break; 243 case NODE_TAGGED: 244 item_check_present(tree, index); 245 assert(item_tag_get(tree, index, tag)); 246 actual_total_present++; 247 actual_total_tagged++; 248 break; 249 } 250 } 251 252 gang_check(tree, thrash_state, tag); 253 254 printf("%d(%d) %d(%d) %d(%d) %d(%d) / " 255 "%d(%d) present, %d(%d) tagged\n", 256 insert_chunk, nr_inserted, 257 delete_chunk, nr_deleted, 258 tag_chunk, nr_tagged, 259 untag_chunk, nr_untagged, 260 total_present, actual_total_present, 261 total_tagged, actual_total_tagged); 262 } 263 } 264 265 static void thrash_tags(void) 266 { 267 RADIX_TREE(tree, GFP_KERNEL); 268 char *thrash_state; 269 270 thrash_state = malloc(THRASH_SIZE); 271 memset(thrash_state, 0, THRASH_SIZE); 272 273 do_thrash(&tree, thrash_state, 0); 274 275 verify_tag_consistency(&tree, 0); 276 item_kill_tree(&tree); 277 free(thrash_state); 278 } 279 280 static void leak_check(void) 281 { 282 RADIX_TREE(tree, GFP_KERNEL); 283 284 item_insert(&tree, 1000000); 285 item_delete(&tree, 1000000); 286 item_kill_tree(&tree); 287 } 288 289 static void __leak_check(void) 290 { 291 RADIX_TREE(tree, GFP_KERNEL); 292 293 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); 294 item_insert(&tree, 1000000); 295 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); 296 item_delete(&tree, 1000000); 297 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); 298 item_kill_tree(&tree); 299 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); 300 } 301 302 static void single_check(void) 303 { 304 struct item *items[BATCH]; 305 RADIX_TREE(tree, GFP_KERNEL); 306 int ret; 307 308 item_insert(&tree, 0); 309 item_tag_set(&tree, 0, 0); 310 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0); 311 assert(ret == 1); 312 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0); 313 assert(ret == 0); 314 verify_tag_consistency(&tree, 0); 315 verify_tag_consistency(&tree, 1); 316 item_kill_tree(&tree); 317 } 318 319 void tag_check(void) 320 { 321 single_check(); 322 extend_checks(); 323 contract_checks(); 324 printf("after extend_checks: %d allocated\n", nr_allocated); 325 __leak_check(); 326 leak_check(); 327 printf("after leak_check: %d allocated\n", nr_allocated); 328 simple_checks(); 329 printf("after simple_checks: %d allocated\n", nr_allocated); 330 thrash_tags(); 331 printf("after thrash_tags: %d allocated\n", nr_allocated); 332 } 333