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