tools/testing/radix-tree/test.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 #include <stdio.h>
   5 #include <linux/types.h>
   6 #include <linux/kernel.h>
   7 #include <linux/bitops.h>
   8
   9 #include "test.h"
  10
  11 struct item *
  12 item_tag_set(struct radix_tree_root *root, unsigned long index, int tag)
  13 {
  14         return radix_tree_tag_set(root, index, tag);
  15 }
  16
  17 struct item *
  18 item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
  19 {
  20         return radix_tree_tag_clear(root, index, tag);
  21 }
  22
  23 int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
  24 {
  25         return radix_tree_tag_get(root, index, tag);
  26 }
  27
  28 struct item *item_create(unsigned long index, unsigned int order)
  29 {
  30         struct item *ret = malloc(sizeof(*ret));
  31
  32         ret->index = index;
  33         ret->order = order;
  34         return ret;
  35 }
  36
  37 int item_insert(struct radix_tree_root *root, unsigned long index)
  38 {
  39         struct item *item = item_create(index, 0);
  40         int err = radix_tree_insert(root, item->index, item);
  41         if (err)
  42                 free(item);
  43         return err;
  44 }
  45
  46 void item_sanity(struct item *item, unsigned long index)
  47 {
  48         unsigned long mask;
  49         assert(!radix_tree_is_internal_node(item));
  50         assert(item->order < BITS_PER_LONG);
  51         mask = (1UL << item->order) - 1;
  52         assert((item->index | mask) == (index | mask));
  53 }
  54
  55 void item_free(struct item *item, unsigned long index)
  56 {
  57         item_sanity(item, index);
  58         free(item);
  59 }
  60
  61 int item_delete(struct radix_tree_root *root, unsigned long index)
  62 {
  63         struct item *item = radix_tree_delete(root, index);
  64
  65         if (!item)
  66                 return 0;
  67
  68         item_free(item, index);
  69         return 1;
  70 }
  71
  72 static void item_free_rcu(struct rcu_head *head)
  73 {
  74         struct item *item = container_of(head, struct item, rcu_head);
  75
  76         free(item);
  77 }
  78
  79 int item_delete_rcu(struct xarray *xa, unsigned long index)
  80 {
  81         struct item *item = xa_erase(xa, index);
  82
  83         if (item) {
  84                 item_sanity(item, index);
  85                 call_rcu(&item->rcu_head, item_free_rcu);
  86                 return 1;
  87         }
  88         return 0;
  89 }
  90
  91 void item_check_present(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         item_sanity(item, index);
  98 }
  99
 100 struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
 101 {
 102         return radix_tree_lookup(root, index);
 103 }
 104
 105 void item_check_absent(struct radix_tree_root *root, unsigned long index)
 106 {
 107         struct item *item;
 108
 109         item = radix_tree_lookup(root, index);
 110         assert(item == NULL);
 111 }
 112
 113 /*
 114  * Scan only the passed (start, start+nr] for present items
 115  */
 116 void item_gang_check_present(struct radix_tree_root *root,
 117                         unsigned long start, unsigned long nr,
 118                         int chunk, int hop)
 119 {
 120         struct item *items[chunk];
 121         unsigned long into;
 122
 123         for (into = 0; into < nr; ) {
 124                 int nfound;
 125                 int nr_to_find = chunk;
 126                 int i;
 127
 128                 if (nr_to_find > (nr - into))
 129                         nr_to_find = nr - into;
 130
 131                 nfound = radix_tree_gang_lookup(root, (void **)items,
 132                                                 start + into, nr_to_find);
 133                 assert(nfound == nr_to_find);
 134                 for (i = 0; i < nfound; i++)
 135                         assert(items[i]->index == start + into + i);
 136                 into += hop;
 137         }
 138 }
 139
 140 /*
 141  * Scan the entire tree, only expecting present items (start, start+nr]
 142  */
 143 void item_full_scan(struct radix_tree_root *root, unsigned long start,
 144                         unsigned long nr, int chunk)
 145 {
 146         struct item *items[chunk];
 147         unsigned long into = 0;
 148         unsigned long this_index = start;
 149         int nfound;
 150         int i;
 151
 152 //      printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);
 153
 154         while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,
 155                                         chunk))) {
 156 //              printf("At 0x%08lx, nfound=%d\n", into, nfound);
 157                 for (i = 0; i < nfound; i++) {
 158                         assert(items[i]->index == this_index);
 159                         this_index++;
 160                 }
 161 //              printf("Found 0x%08lx->0x%08lx\n",
 162 //                      items[0]->index, items[nfound-1]->index);
 163                 into = this_index;
 164         }
 165         if (chunk)
 166                 assert(this_index == start + nr);
 167         nfound = radix_tree_gang_lookup(root, (void **)items,
 168                                         this_index, chunk);
 169         assert(nfound == 0);
 170 }
 171
 172 /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */
 173 int tag_tagged_items(struct xarray *xa, unsigned long start, unsigned long end,
 174                 unsigned batch, xa_mark_t iftag, xa_mark_t thentag)
 175 {
 176         XA_STATE(xas, xa, start);
 177         unsigned int tagged = 0;
 178         struct item *item;
 179
 180         if (batch == 0)
 181                 batch = 1;
 182
 183         xas_lock_irq(&xas);
 184         xas_for_each_marked(&xas, item, end, iftag) {
 185                 xas_set_mark(&xas, thentag);
 186                 if (++tagged % batch)
 187                         continue;
 188
 189                 xas_pause(&xas);
 190                 xas_unlock_irq(&xas);
 191                 rcu_barrier();
 192                 xas_lock_irq(&xas);
 193         }
 194         xas_unlock_irq(&xas);
 195
 196         return tagged;
 197 }
 198
 199 static int verify_node(struct radix_tree_node *slot, unsigned int tag,
 200                         int tagged)
 201 {
 202         int anyset = 0;
 203         int i;
 204         int j;
 205
 206         slot = entry_to_node(slot);
 207
 208         /* Verify consistency at this level */
 209         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
 210                 if (slot->tags[tag][i]) {
 211                         anyset = 1;
 212                         break;
 213                 }
 214         }
 215         if (tagged != anyset) {
 216                 printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",
 217                         tag, slot->shift, tagged, anyset);
 218                 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 219                         printf("tag %d: ", j);
 220                         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 221                                 printf("%016lx ", slot->tags[j][i]);
 222                         printf("\n");
 223                 }
 224                 return 1;
 225         }
 226         assert(tagged == anyset);
 227
 228         /* Go for next level */
 229         if (slot->shift > 0) {
 230                 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
 231                         if (slot->slots[i])
 232                                 if (verify_node(slot->slots[i], tag,
 233                                             !!test_bit(i, slot->tags[tag]))) {
 234                                         printf("Failure at off %d\n", i);
 235                                         for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
 236                                                 printf("tag %d: ", j);
 237                                                 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
 238                                                         printf("%016lx ", slot->tags[j][i]);
 239                                                 printf("\n");
 240                                         }
 241                                         return 1;
 242                                 }
 243         }
 244         return 0;
 245 }
 246
 247 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
 248 {
 249         struct radix_tree_node *node = root->xa_head;
 250         if (!radix_tree_is_internal_node(node))
 251                 return;
 252         verify_node(node, tag, !!root_tag_get(root, tag));
 253 }
 254
 255 void item_kill_tree(struct xarray *xa)
 256 {
 257         XA_STATE(xas, xa, 0);
 258         void *entry;
 259
 260         xas_for_each(&xas, entry, ULONG_MAX) {
 261                 if (!xa_is_value(entry)) {
 262                         item_free(entry, xas.xa_index);
 263                 }
 264                 xas_store(&xas, NULL);
 265         }
 266
 267         assert(xa_empty(xa));
 268 }
 269
 270 void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
 271 {
 272         unsigned shift;
 273         struct radix_tree_node *node = root->xa_head;
 274         if (!radix_tree_is_internal_node(node)) {
 275                 assert(maxindex == 0);
 276                 return;
 277         }
 278
 279         node = entry_to_node(node);
 280         assert(maxindex <= node_maxindex(node));
 281
 282         shift = node->shift;
 283         if (shift > 0)
 284                 assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));
 285         else
 286                 assert(maxindex > 0);
 287 }