tools/testing/radix-tree/tag_check.c

   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 }