testing/radix-tree/test.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include <stdlib.h>
0003 #include <assert.h>
0004 #include <stdio.h>
0005 #include <linux/types.h>
0006 #include <linux/kernel.h>
0007 #include <linux/bitops.h>
0008
0009 #include "test.h"
0010
0011 struct item *
0012 item_tag_set(struct radix_tree_root *root, unsigned long index, int tag)
0013 {
0014     return radix_tree_tag_set(root, index, tag);
0015 }
0016
0017 struct item *
0018 item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
0019 {
0020     return radix_tree_tag_clear(root, index, tag);
0021 }
0022
0023 int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
0024 {
0025     return radix_tree_tag_get(root, index, tag);
0026 }
0027
0028 struct item *item_create(unsigned long index, unsigned int order)
0029 {
0030     struct item *ret = malloc(sizeof(*ret));
0031
0032     ret->index = index;
0033     ret->order = order;
0034     return ret;
0035 }
0036
0037 int item_insert(struct radix_tree_root *root, unsigned long index)
0038 {
0039     struct item *item = item_create(index, 0);
0040     int err = radix_tree_insert(root, item->index, item);
0041     if (err)
0042         free(item);
0043     return err;
0044 }
0045
0046 void item_sanity(struct item *item, unsigned long index)
0047 {
0048     unsigned long mask;
0049     assert(!radix_tree_is_internal_node(item));
0050     assert(item->order < BITS_PER_LONG);
0051     mask = (1UL << item->order) - 1;
0052     assert((item->index | mask) == (index | mask));
0053 }
0054
0055 void item_free(struct item *item, unsigned long index)
0056 {
0057     item_sanity(item, index);
0058     free(item);
0059 }
0060
0061 int item_delete(struct radix_tree_root *root, unsigned long index)
0062 {
0063     struct item *item = radix_tree_delete(root, index);
0064
0065     if (!item)
0066         return 0;
0067
0068     item_free(item, index);
0069     return 1;
0070 }
0071
0072 static void item_free_rcu(struct rcu_head *head)
0073 {
0074     struct item *item = container_of(head, struct item, rcu_head);
0075
0076     free(item);
0077 }
0078
0079 int item_delete_rcu(struct xarray *xa, unsigned long index)
0080 {
0081     struct item *item = xa_erase(xa, index);
0082
0083     if (item) {
0084         item_sanity(item, index);
0085         call_rcu(&item->rcu_head, item_free_rcu);
0086         return 1;
0087     }
0088     return 0;
0089 }
0090
0091 void item_check_present(struct radix_tree_root *root, unsigned long index)
0092 {
0093     struct item *item;
0094
0095     item = radix_tree_lookup(root, index);
0096     assert(item != NULL);
0097     item_sanity(item, index);
0098 }
0099
0100 struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
0101 {
0102     return radix_tree_lookup(root, index);
0103 }
0104
0105 void item_check_absent(struct radix_tree_root *root, unsigned long index)
0106 {
0107     struct item *item;
0108
0109     item = radix_tree_lookup(root, index);
0110     assert(item == NULL);
0111 }
0112
0113 /*
0114  * Scan only the passed (start, start+nr] for present items
0115  */
0116 void item_gang_check_present(struct radix_tree_root *root,
0117             unsigned long start, unsigned long nr,
0118             int chunk, int hop)
0119 {
0120     struct item *items[chunk];
0121     unsigned long into;
0122
0123     for (into = 0; into < nr; ) {
0124         int nfound;
0125         int nr_to_find = chunk;
0126         int i;
0127
0128         if (nr_to_find > (nr - into))
0129             nr_to_find = nr - into;
0130
0131         nfound = radix_tree_gang_lookup(root, (void **)items,
0132                         start + into, nr_to_find);
0133         assert(nfound == nr_to_find);
0134         for (i = 0; i < nfound; i++)
0135             assert(items[i]->index == start + into + i);
0136         into += hop;
0137     }
0138 }
0139
0140 /*
0141  * Scan the entire tree, only expecting present items (start, start+nr]
0142  */
0143 void item_full_scan(struct radix_tree_root *root, unsigned long start,
0144             unsigned long nr, int chunk)
0145 {
0146     struct item *items[chunk];
0147     unsigned long into = 0;
0148     unsigned long this_index = start;
0149     int nfound;
0150     int i;
0151
0152 //  printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);
0153
0154     while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,
0155                     chunk))) {
0156 //      printf("At 0x%08lx, nfound=%d\n", into, nfound);
0157         for (i = 0; i < nfound; i++) {
0158             assert(items[i]->index == this_index);
0159             this_index++;
0160         }
0161 //      printf("Found 0x%08lx->0x%08lx\n",
0162 //          items[0]->index, items[nfound-1]->index);
0163         into = this_index;
0164     }
0165     if (chunk)
0166         assert(this_index == start + nr);
0167     nfound = radix_tree_gang_lookup(root, (void **)items,
0168                     this_index, chunk);
0169     assert(nfound == 0);
0170 }
0171
0172 /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */
0173 int tag_tagged_items(struct xarray *xa, unsigned long start, unsigned long end,
0174         unsigned batch, xa_mark_t iftag, xa_mark_t thentag)
0175 {
0176     XA_STATE(xas, xa, start);
0177     unsigned int tagged = 0;
0178     struct item *item;
0179
0180     if (batch == 0)
0181         batch = 1;
0182
0183     xas_lock_irq(&xas);
0184     xas_for_each_marked(&xas, item, end, iftag) {
0185         xas_set_mark(&xas, thentag);
0186         if (++tagged % batch)
0187             continue;
0188
0189         xas_pause(&xas);
0190         xas_unlock_irq(&xas);
0191         rcu_barrier();
0192         xas_lock_irq(&xas);
0193     }
0194     xas_unlock_irq(&xas);
0195
0196     return tagged;
0197 }
0198
0199 static int verify_node(struct radix_tree_node *slot, unsigned int tag,
0200             int tagged)
0201 {
0202     int anyset = 0;
0203     int i;
0204     int j;
0205
0206     slot = entry_to_node(slot);
0207
0208     /* Verify consistency at this level */
0209     for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
0210         if (slot->tags[tag][i]) {
0211             anyset = 1;
0212             break;
0213         }
0214     }
0215     if (tagged != anyset) {
0216         printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",
0217             tag, slot->shift, tagged, anyset);
0218         for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
0219             printf("tag %d: ", j);
0220             for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
0221                 printf("%016lx ", slot->tags[j][i]);
0222             printf("\n");
0223         }
0224         return 1;
0225     }
0226     assert(tagged == anyset);
0227
0228     /* Go for next level */
0229     if (slot->shift > 0) {
0230         for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
0231             if (slot->slots[i])
0232                 if (verify_node(slot->slots[i], tag,
0233                         !!test_bit(i, slot->tags[tag]))) {
0234                     printf("Failure at off %d\n", i);
0235                     for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
0236                         printf("tag %d: ", j);
0237                         for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
0238                             printf("%016lx ", slot->tags[j][i]);
0239                         printf("\n");
0240                     }
0241                     return 1;
0242                 }
0243     }
0244     return 0;
0245 }
0246
0247 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
0248 {
0249     struct radix_tree_node *node = root->xa_head;
0250     if (!radix_tree_is_internal_node(node))
0251         return;
0252     verify_node(node, tag, !!root_tag_get(root, tag));
0253 }
0254
0255 void item_kill_tree(struct xarray *xa)
0256 {
0257     XA_STATE(xas, xa, 0);
0258     void *entry;
0259
0260     xas_for_each(&xas, entry, ULONG_MAX) {
0261         if (!xa_is_value(entry)) {
0262             item_free(entry, xas.xa_index);
0263         }
0264         xas_store(&xas, NULL);
0265     }
0266
0267     assert(xa_empty(xa));
0268 }
0269
0270 void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
0271 {
0272     unsigned shift;
0273     struct radix_tree_node *node = root->xa_head;
0274     if (!radix_tree_is_internal_node(node)) {
0275         assert(maxindex == 0);
0276         return;
0277     }
0278
0279     node = entry_to_node(node);
0280     assert(maxindex <= node_maxindex(node));
0281
0282     shift = node->shift;
0283     if (shift > 0)
0284         assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));
0285     else
0286         assert(maxindex > 0);
0287 }