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