tools/testing/radix-tree/test.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3 #include <stdio.h>
   4 #include <linux/types.h>
   5 #include <linux/kernel.h>
   6 #include <linux/bitops.h>
   7
   8 #include "test.h"
   9
  10 struct item *
  11 item_tag_set(struct radix_tree_root *root, unsigned long index, int tag)
  12 {
  13         return radix_tree_tag_set(root, index, tag);
  14 }
  15
  16 struct item *
  17 item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
  18 {
  19         return radix_tree_tag_clear(root, index, tag);
  20 }
  21
  22 int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
  23 {
  24         return radix_tree_tag_get(root, index, tag);
  25 }
  26
  27 int __item_insert(struct radix_tree_root *root, struct item *item,
  28                         unsigned order)
  29 {
  30         return __radix_tree_insert(root, item->index, order, item);
  31 }
  32
  33 int item_insert(struct radix_tree_root *root, unsigned long index)
  34 {
  35         return __item_insert(root, item_create(index), 0);
  36 }
  37
  38 int item_insert_order(struct radix_tree_root *root, unsigned long index,
  39                         unsigned order)
  40 {
  41         return __item_insert(root, item_create(index), order);
  42 }
  43
  44 int item_delete(struct radix_tree_root *root, unsigned long index)
  45 {
  46         struct item *item = radix_tree_delete(root, index);
  47
  48         if (item) {
  49                 assert(item->index == index);
  50                 free(item);
  51                 return 1;
  52         }
  53         return 0;
  54 }
  55
  56 struct item *item_create(unsigned long index)
  57 {
  58         struct item *ret = malloc(sizeof(*ret));
  59
  60         ret->index = index;
  61         return ret;
  62 }
  63
  64 void item_check_present(struct radix_tree_root *root, unsigned long index)
  65 {
  66         struct item *item;
  67
  68         item = radix_tree_lookup(root, index);
  69         assert(item != 0);
  70         assert(item->index == index);
  71 }
  72
  73 struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
  74 {
  75         return radix_tree_lookup(root, index);
  76 }
  77
  78 void item_check_absent(struct radix_tree_root *root, unsigned long index)
  79 {
  80         struct item *item;
  81
  82         item = radix_tree_lookup(root, index);
  83         assert(item == 0);
  84 }
  85
  86 /*
  87  * Scan only the passed (start, start+nr] for present items
  88  */
  89 void item_gang_check_present(struct radix_tree_root *root,
  90                         unsigned long start, unsigned long nr,
  91                         int chunk, int hop)
  92 {
  93         struct item *items[chunk];
  94         unsigned long into;
  95
  96         for (into = 0; into < nr; ) {
  97                 int nfound;
  98                 int nr_to_find = chunk;
  99                 int i;
 100
 101                 if (nr_to_find > (nr - into))
 102                         nr_to_find = nr - into;
 103
 104                 nfound = radix_tree_gang_lookup(root, (void **)items,
 105                                                 start + into, nr_to_find);
 106                 assert(nfound == nr_to_find);
 107                 for (i = 0; i < nfound; i++)
 108                         assert(items[i]->index == start + into + i);
 109                 into += hop;
 110         }
 111 }
 112
 113 /*
 114  * Scan the entire tree, only expecting present items (start, start+nr]
 115  */
 116 void item_full_scan(struct radix_tree_root *root, unsigned long start,
 117                         unsigned long nr, int chunk)
 118 {
 119         struct item *items[chunk];
 120         unsigned long into = 0;
 121         unsigned long this_index = start;
 122         int nfound;
 123         int i;
 124
 125 //      printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);
 126
 127         while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,
 128                                         chunk))) {
 129 //              printf("At 0x%08lx, nfound=%d\n", into, nfound);
 130                 for (i = 0; i < nfound; i++) {
 131                         assert(items[i]->index == this_index);
 132                         this_index++;
 133                 }
 134 //              printf("Found 0x%08lx->0x%08lx\n",
 135 //                      items[0]->index, items[nfound-1]->index);
 136                 into = this_index;
 137         }
 138         if (chunk)
 139                 assert(this_index == start + nr);
 140         nfound = radix_tree_gang_lookup(root, (void **)items,
 141                                         this_index, chunk);
 142         assert(nfound == 0);
 143 }
 144
 145 static int verify_node(struct radix_tree_node *slot, unsigned int tag,
 146                         unsigned int height, int tagged)
 147 {
 148         int anyset = 0;
 149         int i;
 150         int j;
 151
 152         slot = indirect_to_ptr(slot);
 153
 154         /* Verify consistency at this level */
 155         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
 156                 if (slot->tags[tag][i]) {
 157                         anyset = 1;
 158                         break;
 159                 }
 160         }
 161         if (tagged != anyset) {
 162                 printf("tag: %u, height %u, tagged: %d, anyset: %d\n", tag, height, tagged, anyset);
 163                 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 164                         printf("tag %d: ", j);
 165                         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 166                                 printf("%016lx ", slot->tags[j][i]);
 167                         printf("\n");
 168                 }
 169                 return 1;
 170         }
 171         assert(tagged == anyset);
 172
 173         /* Go for next level */
 174         if (height > 1) {
 175                 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
 176                         if (slot->slots[i])
 177                                 if (verify_node(slot->slots[i], tag, height - 1,
 178                                             !!test_bit(i, slot->tags[tag]))) {
 179                                         printf("Failure at off %d\n", i);
 180                                         for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 181                                                 printf("tag %d: ", j);
 182                                                 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 183                                                         printf("%016lx ", slot->tags[j][i]);
 184                                                 printf("\n");
 185                                         }
 186                                         return 1;
 187                                 }
 188         }
 189         return 0;
 190 }
 191
 192 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
 193 {
 194         if (!root->height)
 195                 return;
 196         verify_node(root->rnode, tag, root->height, !!root_tag_get(root, tag));
 197 }
 198
 199 void item_kill_tree(struct radix_tree_root *root)
 200 {
 201         struct item *items[32];
 202         int nfound;
 203
 204         while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) {
 205                 int i;
 206
 207                 for (i = 0; i < nfound; i++) {
 208                         void *ret;
 209
 210                         ret = radix_tree_delete(root, items[i]->index);
 211                         assert(ret == items[i]);
 212                         free(items[i]);
 213                 }
 214         }
 215         assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0);
 216         assert(root->rnode == NULL);
 217 }
 218
 219 void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
 220 {
 221         assert(radix_tree_maxindex(root->height) >= maxindex);
 222         if (root->height > 1)
 223                 assert(radix_tree_maxindex(root->height-1) < maxindex);
 224         else if (root->height == 1)
 225                 assert(radix_tree_maxindex(root->height-1) <= maxindex);
 226 }