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 {
  29         return __radix_tree_insert(root, item->index, item->order, item);
  30 }
  31
  32 struct item *item_create(unsigned long index, unsigned int order)
  33 {
  34         struct item *ret = malloc(sizeof(*ret));
  35
  36         ret->index = index;
  37         ret->order = order;
  38         return ret;
  39 }
  40
  41 int item_insert_order(struct radix_tree_root *root, unsigned long index,
  42                         unsigned order)
  43 {
  44         struct item *item = item_create(index, order);
  45         int err = __item_insert(root, item);
  46         if (err)
  47                 free(item);
  48         return err;
  49 }
  50
  51 int item_insert(struct radix_tree_root *root, unsigned long index)
  52 {
  53         return item_insert_order(root, index, 0);
  54 }
  55
  56 void item_sanity(struct item *item, unsigned long index)
  57 {
  58         unsigned long mask;
  59         assert(!radix_tree_is_internal_node(item));
  60         assert(item->order < BITS_PER_LONG);
  61         mask = (1UL << item->order) - 1;
  62         assert((item->index | mask) == (index | mask));
  63 }
  64
  65 int item_delete(struct radix_tree_root *root, unsigned long index)
  66 {
  67         struct item *item = radix_tree_delete(root, index);
  68
  69         if (item) {
  70                 item_sanity(item, index);
  71                 free(item);
  72                 return 1;
  73         }
  74         return 0;
  75 }
  76
  77 void item_check_present(struct radix_tree_root *root, unsigned long index)
  78 {
  79         struct item *item;
  80
  81         item = radix_tree_lookup(root, index);
  82         assert(item != NULL);
  83         item_sanity(item, index);
  84 }
  85
  86 struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
  87 {
  88         return radix_tree_lookup(root, index);
  89 }
  90
  91 void item_check_absent(struct radix_tree_root *root, unsigned long index)
  92 {
  93         struct item *item;
  94
  95         item = radix_tree_lookup(root, index);
  96         assert(item == NULL);
  97 }
  98
  99 /*
 100  * Scan only the passed (start, start+nr] for present items
 101  */
 102 void item_gang_check_present(struct radix_tree_root *root,
 103                         unsigned long start, unsigned long nr,
 104                         int chunk, int hop)
 105 {
 106         struct item *items[chunk];
 107         unsigned long into;
 108
 109         for (into = 0; into < nr; ) {
 110                 int nfound;
 111                 int nr_to_find = chunk;
 112                 int i;
 113
 114                 if (nr_to_find > (nr - into))
 115                         nr_to_find = nr - into;
 116
 117                 nfound = radix_tree_gang_lookup(root, (void **)items,
 118                                                 start + into, nr_to_find);
 119                 assert(nfound == nr_to_find);
 120                 for (i = 0; i < nfound; i++)
 121                         assert(items[i]->index == start + into + i);
 122                 into += hop;
 123         }
 124 }
 125
 126 /*
 127  * Scan the entire tree, only expecting present items (start, start+nr]
 128  */
 129 void item_full_scan(struct radix_tree_root *root, unsigned long start,
 130                         unsigned long nr, int chunk)
 131 {
 132         struct item *items[chunk];
 133         unsigned long into = 0;
 134         unsigned long this_index = start;
 135         int nfound;
 136         int i;
 137
 138 //      printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);
 139
 140         while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,
 141                                         chunk))) {
 142 //              printf("At 0x%08lx, nfound=%d\n", into, nfound);
 143                 for (i = 0; i < nfound; i++) {
 144                         assert(items[i]->index == this_index);
 145                         this_index++;
 146                 }
 147 //              printf("Found 0x%08lx->0x%08lx\n",
 148 //                      items[0]->index, items[nfound-1]->index);
 149                 into = this_index;
 150         }
 151         if (chunk)
 152                 assert(this_index == start + nr);
 153         nfound = radix_tree_gang_lookup(root, (void **)items,
 154                                         this_index, chunk);
 155         assert(nfound == 0);
 156 }
 157
 158 /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */
 159 int tag_tagged_items(struct radix_tree_root *root, pthread_mutex_t *lock,
 160                         unsigned long start, unsigned long end, unsigned batch,
 161                         unsigned iftag, unsigned thentag)
 162 {
 163         unsigned long tagged = 0;
 164         struct radix_tree_iter iter;
 165         void **slot;
 166
 167         if (batch == 0)
 168                 batch = 1;
 169
 170         if (lock)
 171                 pthread_mutex_lock(lock);
 172         radix_tree_for_each_tagged(slot, root, &iter, start, iftag) {
 173                 if (iter.index > end)
 174                         break;
 175                 radix_tree_iter_tag_set(root, &iter, thentag);
 176                 tagged++;
 177                 if ((tagged % batch) != 0)
 178                         continue;
 179                 slot = radix_tree_iter_resume(slot, &iter);
 180                 if (lock) {
 181                         pthread_mutex_unlock(lock);
 182                         rcu_barrier();
 183                         pthread_mutex_lock(lock);
 184                 }
 185         }
 186         if (lock)
 187                 pthread_mutex_unlock(lock);
 188
 189         return tagged;
 190 }
 191
 192 /* Use the same pattern as find_swap_entry() in mm/shmem.c */
 193 unsigned long find_item(struct radix_tree_root *root, void *item)
 194 {
 195         struct radix_tree_iter iter;
 196         void **slot;
 197         unsigned long found = -1;
 198         unsigned long checked = 0;
 199
 200         radix_tree_for_each_slot(slot, root, &iter, 0) {
 201                 if (*slot == item) {
 202                         found = iter.index;
 203                         break;
 204                 }
 205                 checked++;
 206                 if ((checked % 4) != 0)
 207                         continue;
 208                 slot = radix_tree_iter_resume(slot, &iter);
 209         }
 210
 211         return found;
 212 }
 213
 214 static int verify_node(struct radix_tree_node *slot, unsigned int tag,
 215                         int tagged)
 216 {
 217         int anyset = 0;
 218         int i;
 219         int j;
 220
 221         slot = entry_to_node(slot);
 222
 223         /* Verify consistency at this level */
 224         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
 225                 if (slot->tags[tag][i]) {
 226                         anyset = 1;
 227                         break;
 228                 }
 229         }
 230         if (tagged != anyset) {
 231                 printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",
 232                         tag, slot->shift, tagged, anyset);
 233                 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 234                         printf("tag %d: ", j);
 235                         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 236                                 printf("%016lx ", slot->tags[j][i]);
 237                         printf("\n");
 238                 }
 239                 return 1;
 240         }
 241         assert(tagged == anyset);
 242
 243         /* Go for next level */
 244         if (slot->shift > 0) {
 245                 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
 246                         if (slot->slots[i])
 247                                 if (verify_node(slot->slots[i], tag,
 248                                             !!test_bit(i, slot->tags[tag]))) {
 249                                         printf("Failure at off %d\n", i);
 250                                         for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 251                                                 printf("tag %d: ", j);
 252                                                 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 253                                                         printf("%016lx ", slot->tags[j][i]);
 254                                                 printf("\n");
 255                                         }
 256                                         return 1;
 257                                 }
 258         }
 259         return 0;
 260 }
 261
 262 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
 263 {
 264         struct radix_tree_node *node = root->rnode;
 265         if (!radix_tree_is_internal_node(node))
 266                 return;
 267         verify_node(node, tag, !!root_tag_get(root, tag));
 268 }
 269
 270 void item_kill_tree(struct radix_tree_root *root)
 271 {
 272         struct radix_tree_iter iter;
 273         void **slot;
 274         struct item *items[32];
 275         int nfound;
 276
 277         radix_tree_for_each_slot(slot, root, &iter, 0) {
 278                 if (radix_tree_exceptional_entry(*slot))
 279                         radix_tree_delete(root, iter.index);
 280         }
 281
 282         while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) {
 283                 int i;
 284
 285                 for (i = 0; i < nfound; i++) {
 286                         void *ret;
 287
 288                         ret = radix_tree_delete(root, items[i]->index);
 289                         assert(ret == items[i]);
 290                         free(items[i]);
 291                 }
 292         }
 293         assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0);
 294         assert(root->rnode == NULL);
 295 }
 296
 297 void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
 298 {
 299         unsigned shift;
 300         struct radix_tree_node *node = root->rnode;
 301         if (!radix_tree_is_internal_node(node)) {
 302                 assert(maxindex == 0);
 303                 return;
 304         }
 305
 306         node = entry_to_node(node);
 307         assert(maxindex <= node_maxindex(node));
 308
 309         shift = node->shift;
 310         if (shift > 0)
 311                 assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));
 312         else
 313                 assert(maxindex > 0);
 314 }