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                         int tagged)
 147 {
 148         int anyset = 0;
 149         int i;
 150         int j;
 151
 152         slot = entry_to_node(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, shift %u, tagged: %d, anyset: %d\n",
 163                         tag, slot->shift, tagged, anyset);
 164                 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 165                         printf("tag %d: ", j);
 166                         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 167                                 printf("%016lx ", slot->tags[j][i]);
 168                         printf("\n");
 169                 }
 170                 return 1;
 171         }
 172         assert(tagged == anyset);
 173
 174         /* Go for next level */
 175         if (slot->shift > 0) {
 176                 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
 177                         if (slot->slots[i])
 178                                 if (verify_node(slot->slots[i], tag,
 179                                             !!test_bit(i, slot->tags[tag]))) {
 180                                         printf("Failure at off %d\n", i);
 181                                         for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 182                                                 printf("tag %d: ", j);
 183                                                 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 184                                                         printf("%016lx ", slot->tags[j][i]);
 185                                                 printf("\n");
 186                                         }
 187                                         return 1;
 188                                 }
 189         }
 190         return 0;
 191 }
 192
 193 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
 194 {
 195         struct radix_tree_node *node = root->rnode;
 196         if (!radix_tree_is_internal_node(node))
 197                 return;
 198         verify_node(node, tag, !!root_tag_get(root, tag));
 199 }
 200
 201 void item_kill_tree(struct radix_tree_root *root)
 202 {
 203         struct item *items[32];
 204         int nfound;
 205
 206         while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) {
 207                 int i;
 208
 209                 for (i = 0; i < nfound; i++) {
 210                         void *ret;
 211
 212                         ret = radix_tree_delete(root, items[i]->index);
 213                         assert(ret == items[i]);
 214                         free(items[i]);
 215                 }
 216         }
 217         assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0);
 218         assert(root->rnode == NULL);
 219 }
 220
 221 void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
 222 {
 223         unsigned shift;
 224         struct radix_tree_node *node = root->rnode;
 225         if (!radix_tree_is_internal_node(node)) {
 226                 assert(maxindex == 0);
 227                 return;
 228         }
 229
 230         node = entry_to_node(node);
 231         assert(maxindex <= node_maxindex(node));
 232
 233         shift = node->shift;
 234         if (shift > 0)
 235                 assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));
 236         else
 237                 assert(maxindex > 0);
 238 }