1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 21366c37eSMatthew Wilcox #include <stdlib.h> 31366c37eSMatthew Wilcox #include <assert.h> 41366c37eSMatthew Wilcox #include <stdio.h> 51366c37eSMatthew Wilcox #include <linux/types.h> 61366c37eSMatthew Wilcox #include <linux/kernel.h> 71366c37eSMatthew Wilcox #include <linux/bitops.h> 81366c37eSMatthew Wilcox 91366c37eSMatthew Wilcox #include "test.h" 101366c37eSMatthew Wilcox 111366c37eSMatthew Wilcox struct item * 121366c37eSMatthew Wilcox item_tag_set(struct radix_tree_root *root, unsigned long index, int tag) 131366c37eSMatthew Wilcox { 141366c37eSMatthew Wilcox return radix_tree_tag_set(root, index, tag); 151366c37eSMatthew Wilcox } 161366c37eSMatthew Wilcox 171366c37eSMatthew Wilcox struct item * 181366c37eSMatthew Wilcox item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) 191366c37eSMatthew Wilcox { 201366c37eSMatthew Wilcox return radix_tree_tag_clear(root, index, tag); 211366c37eSMatthew Wilcox } 221366c37eSMatthew Wilcox 231366c37eSMatthew Wilcox int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag) 241366c37eSMatthew Wilcox { 251366c37eSMatthew Wilcox return radix_tree_tag_get(root, index, tag); 261366c37eSMatthew Wilcox } 271366c37eSMatthew Wilcox 28101d9607SMatthew Wilcox int __item_insert(struct radix_tree_root *root, struct item *item) 291366c37eSMatthew Wilcox { 30101d9607SMatthew Wilcox return __radix_tree_insert(root, item->index, item->order, item); 311366c37eSMatthew Wilcox } 321366c37eSMatthew Wilcox 3318d0c573SMatthew Wilcox struct item *item_create(unsigned long index, unsigned int order) 341366c37eSMatthew Wilcox { 3518d0c573SMatthew Wilcox struct item *ret = malloc(sizeof(*ret)); 3618d0c573SMatthew Wilcox 3718d0c573SMatthew Wilcox ret->index = index; 3818d0c573SMatthew Wilcox ret->order = order; 3918d0c573SMatthew Wilcox return ret; 404f3755d1SMatthew Wilcox } 414f3755d1SMatthew Wilcox 424f3755d1SMatthew Wilcox int item_insert_order(struct radix_tree_root *root, unsigned long index, 434f3755d1SMatthew Wilcox unsigned order) 444f3755d1SMatthew Wilcox { 4518d0c573SMatthew Wilcox struct item *item = item_create(index, order); 4618d0c573SMatthew Wilcox int err = __item_insert(root, item); 4718d0c573SMatthew Wilcox if (err) 4818d0c573SMatthew Wilcox free(item); 4918d0c573SMatthew Wilcox return err; 5018d0c573SMatthew Wilcox } 5118d0c573SMatthew Wilcox 5218d0c573SMatthew Wilcox int item_insert(struct radix_tree_root *root, unsigned long index) 5318d0c573SMatthew Wilcox { 5418d0c573SMatthew Wilcox return item_insert_order(root, index, 0); 55101d9607SMatthew Wilcox } 56101d9607SMatthew Wilcox 57101d9607SMatthew Wilcox void item_sanity(struct item *item, unsigned long index) 58101d9607SMatthew Wilcox { 59101d9607SMatthew Wilcox unsigned long mask; 60101d9607SMatthew Wilcox assert(!radix_tree_is_internal_node(item)); 61101d9607SMatthew Wilcox assert(item->order < BITS_PER_LONG); 62101d9607SMatthew Wilcox mask = (1UL << item->order) - 1; 63101d9607SMatthew Wilcox assert((item->index | mask) == (index | mask)); 641366c37eSMatthew Wilcox } 651366c37eSMatthew Wilcox 661366c37eSMatthew Wilcox int item_delete(struct radix_tree_root *root, unsigned long index) 671366c37eSMatthew Wilcox { 681366c37eSMatthew Wilcox struct item *item = radix_tree_delete(root, index); 691366c37eSMatthew Wilcox 701366c37eSMatthew Wilcox if (item) { 71101d9607SMatthew Wilcox item_sanity(item, index); 721366c37eSMatthew Wilcox free(item); 731366c37eSMatthew Wilcox return 1; 741366c37eSMatthew Wilcox } 751366c37eSMatthew Wilcox return 0; 761366c37eSMatthew Wilcox } 771366c37eSMatthew Wilcox 783e252fa7SRoss Zwisler static void item_free_rcu(struct rcu_head *head) 793e252fa7SRoss Zwisler { 803e252fa7SRoss Zwisler struct item *item = container_of(head, struct item, rcu_head); 813e252fa7SRoss Zwisler 823e252fa7SRoss Zwisler free(item); 833e252fa7SRoss Zwisler } 843e252fa7SRoss Zwisler 853e252fa7SRoss Zwisler int item_delete_rcu(struct radix_tree_root *root, unsigned long index) 863e252fa7SRoss Zwisler { 873e252fa7SRoss Zwisler struct item *item = radix_tree_delete(root, index); 883e252fa7SRoss Zwisler 893e252fa7SRoss Zwisler if (item) { 903e252fa7SRoss Zwisler item_sanity(item, index); 913e252fa7SRoss Zwisler call_rcu(&item->rcu_head, item_free_rcu); 923e252fa7SRoss Zwisler return 1; 933e252fa7SRoss Zwisler } 943e252fa7SRoss Zwisler return 0; 953e252fa7SRoss Zwisler } 963e252fa7SRoss Zwisler 971366c37eSMatthew Wilcox void item_check_present(struct radix_tree_root *root, unsigned long index) 981366c37eSMatthew Wilcox { 991366c37eSMatthew Wilcox struct item *item; 1001366c37eSMatthew Wilcox 1011366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 102101d9607SMatthew Wilcox assert(item != NULL); 103101d9607SMatthew Wilcox item_sanity(item, index); 1041366c37eSMatthew Wilcox } 1051366c37eSMatthew Wilcox 1061366c37eSMatthew Wilcox struct item *item_lookup(struct radix_tree_root *root, unsigned long index) 1071366c37eSMatthew Wilcox { 1081366c37eSMatthew Wilcox return radix_tree_lookup(root, index); 1091366c37eSMatthew Wilcox } 1101366c37eSMatthew Wilcox 1111366c37eSMatthew Wilcox void item_check_absent(struct radix_tree_root *root, unsigned long index) 1121366c37eSMatthew Wilcox { 1131366c37eSMatthew Wilcox struct item *item; 1141366c37eSMatthew Wilcox 1151366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 116101d9607SMatthew Wilcox assert(item == NULL); 1171366c37eSMatthew Wilcox } 1181366c37eSMatthew Wilcox 1191366c37eSMatthew Wilcox /* 1201366c37eSMatthew Wilcox * Scan only the passed (start, start+nr] for present items 1211366c37eSMatthew Wilcox */ 1221366c37eSMatthew Wilcox void item_gang_check_present(struct radix_tree_root *root, 1231366c37eSMatthew Wilcox unsigned long start, unsigned long nr, 1241366c37eSMatthew Wilcox int chunk, int hop) 1251366c37eSMatthew Wilcox { 1261366c37eSMatthew Wilcox struct item *items[chunk]; 1271366c37eSMatthew Wilcox unsigned long into; 1281366c37eSMatthew Wilcox 1291366c37eSMatthew Wilcox for (into = 0; into < nr; ) { 1301366c37eSMatthew Wilcox int nfound; 1311366c37eSMatthew Wilcox int nr_to_find = chunk; 1321366c37eSMatthew Wilcox int i; 1331366c37eSMatthew Wilcox 1341366c37eSMatthew Wilcox if (nr_to_find > (nr - into)) 1351366c37eSMatthew Wilcox nr_to_find = nr - into; 1361366c37eSMatthew Wilcox 1371366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1381366c37eSMatthew Wilcox start + into, nr_to_find); 1391366c37eSMatthew Wilcox assert(nfound == nr_to_find); 1401366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) 1411366c37eSMatthew Wilcox assert(items[i]->index == start + into + i); 1421366c37eSMatthew Wilcox into += hop; 1431366c37eSMatthew Wilcox } 1441366c37eSMatthew Wilcox } 1451366c37eSMatthew Wilcox 1461366c37eSMatthew Wilcox /* 1471366c37eSMatthew Wilcox * Scan the entire tree, only expecting present items (start, start+nr] 1481366c37eSMatthew Wilcox */ 1491366c37eSMatthew Wilcox void item_full_scan(struct radix_tree_root *root, unsigned long start, 1501366c37eSMatthew Wilcox unsigned long nr, int chunk) 1511366c37eSMatthew Wilcox { 1521366c37eSMatthew Wilcox struct item *items[chunk]; 1531366c37eSMatthew Wilcox unsigned long into = 0; 1541366c37eSMatthew Wilcox unsigned long this_index = start; 1551366c37eSMatthew Wilcox int nfound; 1561366c37eSMatthew Wilcox int i; 1571366c37eSMatthew Wilcox 1581366c37eSMatthew Wilcox // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); 1591366c37eSMatthew Wilcox 1601366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, 1611366c37eSMatthew Wilcox chunk))) { 1621366c37eSMatthew Wilcox // printf("At 0x%08lx, nfound=%d\n", into, nfound); 1631366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 1641366c37eSMatthew Wilcox assert(items[i]->index == this_index); 1651366c37eSMatthew Wilcox this_index++; 1661366c37eSMatthew Wilcox } 1671366c37eSMatthew Wilcox // printf("Found 0x%08lx->0x%08lx\n", 1681366c37eSMatthew Wilcox // items[0]->index, items[nfound-1]->index); 1691366c37eSMatthew Wilcox into = this_index; 1701366c37eSMatthew Wilcox } 1711366c37eSMatthew Wilcox if (chunk) 1721366c37eSMatthew Wilcox assert(this_index == start + nr); 1731366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1741366c37eSMatthew Wilcox this_index, chunk); 1751366c37eSMatthew Wilcox assert(nfound == 0); 1761366c37eSMatthew Wilcox } 1771366c37eSMatthew Wilcox 178268f42deSMatthew Wilcox /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */ 179372266baSMatthew Wilcox int tag_tagged_items(struct xarray *xa, unsigned long start, unsigned long end, 180372266baSMatthew Wilcox unsigned batch, xa_mark_t iftag, xa_mark_t thentag) 181268f42deSMatthew Wilcox { 182372266baSMatthew Wilcox XA_STATE(xas, xa, start); 183372266baSMatthew Wilcox unsigned int tagged = 0; 184372266baSMatthew Wilcox struct item *item; 185268f42deSMatthew Wilcox 186268f42deSMatthew Wilcox if (batch == 0) 187268f42deSMatthew Wilcox batch = 1; 188268f42deSMatthew Wilcox 189372266baSMatthew Wilcox xas_lock_irq(&xas); 190372266baSMatthew Wilcox xas_for_each_marked(&xas, item, end, iftag) { 191372266baSMatthew Wilcox xas_set_mark(&xas, thentag); 192372266baSMatthew Wilcox if (++tagged % batch) 193268f42deSMatthew Wilcox continue; 194372266baSMatthew Wilcox 195372266baSMatthew Wilcox xas_pause(&xas); 196372266baSMatthew Wilcox xas_unlock_irq(&xas); 197268f42deSMatthew Wilcox rcu_barrier(); 198372266baSMatthew Wilcox xas_lock_irq(&xas); 199268f42deSMatthew Wilcox } 200372266baSMatthew Wilcox xas_unlock_irq(&xas); 201268f42deSMatthew Wilcox 202268f42deSMatthew Wilcox return tagged; 203268f42deSMatthew Wilcox } 204268f42deSMatthew Wilcox 2051366c37eSMatthew Wilcox static int verify_node(struct radix_tree_node *slot, unsigned int tag, 2060694f0c9SMatthew Wilcox int tagged) 2071366c37eSMatthew Wilcox { 2081366c37eSMatthew Wilcox int anyset = 0; 2091366c37eSMatthew Wilcox int i; 2101366c37eSMatthew Wilcox int j; 2111366c37eSMatthew Wilcox 2124dd6c098SMatthew Wilcox slot = entry_to_node(slot); 213339e6353SMatthew Wilcox 2141366c37eSMatthew Wilcox /* Verify consistency at this level */ 2151366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 2161366c37eSMatthew Wilcox if (slot->tags[tag][i]) { 2171366c37eSMatthew Wilcox anyset = 1; 2181366c37eSMatthew Wilcox break; 2191366c37eSMatthew Wilcox } 2201366c37eSMatthew Wilcox } 2211366c37eSMatthew Wilcox if (tagged != anyset) { 2220694f0c9SMatthew Wilcox printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", 2230694f0c9SMatthew Wilcox tag, slot->shift, tagged, anyset); 2241366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 2251366c37eSMatthew Wilcox printf("tag %d: ", j); 2261366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 2271366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 2281366c37eSMatthew Wilcox printf("\n"); 2291366c37eSMatthew Wilcox } 2301366c37eSMatthew Wilcox return 1; 2311366c37eSMatthew Wilcox } 2321366c37eSMatthew Wilcox assert(tagged == anyset); 2331366c37eSMatthew Wilcox 2341366c37eSMatthew Wilcox /* Go for next level */ 2350694f0c9SMatthew Wilcox if (slot->shift > 0) { 2361366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 2371366c37eSMatthew Wilcox if (slot->slots[i]) 2380694f0c9SMatthew Wilcox if (verify_node(slot->slots[i], tag, 2391366c37eSMatthew Wilcox !!test_bit(i, slot->tags[tag]))) { 2401366c37eSMatthew Wilcox printf("Failure at off %d\n", i); 2411366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 2421366c37eSMatthew Wilcox printf("tag %d: ", j); 2431366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 2441366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 2451366c37eSMatthew Wilcox printf("\n"); 2461366c37eSMatthew Wilcox } 2471366c37eSMatthew Wilcox return 1; 2481366c37eSMatthew Wilcox } 2491366c37eSMatthew Wilcox } 2501366c37eSMatthew Wilcox return 0; 2511366c37eSMatthew Wilcox } 2521366c37eSMatthew Wilcox 2531366c37eSMatthew Wilcox void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 2541366c37eSMatthew Wilcox { 255f8d5d0ccSMatthew Wilcox struct radix_tree_node *node = root->xa_head; 256b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) 2571366c37eSMatthew Wilcox return; 2580694f0c9SMatthew Wilcox verify_node(node, tag, !!root_tag_get(root, tag)); 2591366c37eSMatthew Wilcox } 2601366c37eSMatthew Wilcox 2611366c37eSMatthew Wilcox void item_kill_tree(struct radix_tree_root *root) 2621366c37eSMatthew Wilcox { 2633ad75f8aSMatthew Wilcox struct radix_tree_iter iter; 2643ad75f8aSMatthew Wilcox void **slot; 2651366c37eSMatthew Wilcox struct item *items[32]; 2661366c37eSMatthew Wilcox int nfound; 2671366c37eSMatthew Wilcox 2683ad75f8aSMatthew Wilcox radix_tree_for_each_slot(slot, root, &iter, 0) { 2693159f943SMatthew Wilcox if (xa_is_value(*slot)) 2703ad75f8aSMatthew Wilcox radix_tree_delete(root, iter.index); 2713ad75f8aSMatthew Wilcox } 2723ad75f8aSMatthew Wilcox 2731366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 2741366c37eSMatthew Wilcox int i; 2751366c37eSMatthew Wilcox 2761366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 2771366c37eSMatthew Wilcox void *ret; 2781366c37eSMatthew Wilcox 2791366c37eSMatthew Wilcox ret = radix_tree_delete(root, items[i]->index); 2801366c37eSMatthew Wilcox assert(ret == items[i]); 2811366c37eSMatthew Wilcox free(items[i]); 2821366c37eSMatthew Wilcox } 2831366c37eSMatthew Wilcox } 2841366c37eSMatthew Wilcox assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 285f8d5d0ccSMatthew Wilcox assert(root->xa_head == NULL); 2861366c37eSMatthew Wilcox } 2871366c37eSMatthew Wilcox 2881366c37eSMatthew Wilcox void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 2891366c37eSMatthew Wilcox { 2900694f0c9SMatthew Wilcox unsigned shift; 291f8d5d0ccSMatthew Wilcox struct radix_tree_node *node = root->xa_head; 292b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) { 2930694f0c9SMatthew Wilcox assert(maxindex == 0); 2940694f0c9SMatthew Wilcox return; 2950694f0c9SMatthew Wilcox } 2960694f0c9SMatthew Wilcox 2974dd6c098SMatthew Wilcox node = entry_to_node(node); 2980694f0c9SMatthew Wilcox assert(maxindex <= node_maxindex(node)); 2990694f0c9SMatthew Wilcox 3000694f0c9SMatthew Wilcox shift = node->shift; 3010694f0c9SMatthew Wilcox if (shift > 0) 3020694f0c9SMatthew Wilcox assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); 3030694f0c9SMatthew Wilcox else 3040694f0c9SMatthew Wilcox assert(maxindex > 0); 3051366c37eSMatthew Wilcox } 306