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         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 }