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