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 2818d0c573SMatthew Wilcox struct item *item_create(unsigned long index, unsigned int order) 291366c37eSMatthew Wilcox { 3018d0c573SMatthew Wilcox struct item *ret = malloc(sizeof(*ret)); 3118d0c573SMatthew Wilcox 3218d0c573SMatthew Wilcox ret->index = index; 3318d0c573SMatthew Wilcox ret->order = order; 3418d0c573SMatthew Wilcox return ret; 354f3755d1SMatthew Wilcox } 364f3755d1SMatthew Wilcox 374bb53bddSMatthew Wilcox int item_insert(struct radix_tree_root *root, unsigned long index) 384f3755d1SMatthew Wilcox { 394bb53bddSMatthew Wilcox struct item *item = item_create(index, 0); 404bb53bddSMatthew Wilcox int err = radix_tree_insert(root, item->index, item); 4118d0c573SMatthew Wilcox if (err) 4218d0c573SMatthew Wilcox free(item); 4318d0c573SMatthew Wilcox return err; 4418d0c573SMatthew Wilcox } 4518d0c573SMatthew Wilcox 46101d9607SMatthew Wilcox void item_sanity(struct item *item, unsigned long index) 47101d9607SMatthew Wilcox { 48101d9607SMatthew Wilcox unsigned long mask; 49101d9607SMatthew Wilcox assert(!radix_tree_is_internal_node(item)); 50101d9607SMatthew Wilcox assert(item->order < BITS_PER_LONG); 51101d9607SMatthew Wilcox mask = (1UL << item->order) - 1; 52101d9607SMatthew Wilcox assert((item->index | mask) == (index | mask)); 531366c37eSMatthew Wilcox } 541366c37eSMatthew Wilcox 5547e0fab2SMatthew Wilcox void item_free(struct item *item, unsigned long index) 5647e0fab2SMatthew Wilcox { 5747e0fab2SMatthew Wilcox item_sanity(item, index); 5847e0fab2SMatthew Wilcox free(item); 5947e0fab2SMatthew Wilcox } 6047e0fab2SMatthew Wilcox 611366c37eSMatthew Wilcox int item_delete(struct radix_tree_root *root, unsigned long index) 621366c37eSMatthew Wilcox { 631366c37eSMatthew Wilcox struct item *item = radix_tree_delete(root, index); 641366c37eSMatthew Wilcox 6547e0fab2SMatthew Wilcox if (!item) 661366c37eSMatthew Wilcox return 0; 6747e0fab2SMatthew Wilcox 6847e0fab2SMatthew Wilcox item_free(item, index); 6947e0fab2SMatthew Wilcox return 1; 701366c37eSMatthew Wilcox } 711366c37eSMatthew Wilcox 723e252fa7SRoss Zwisler static void item_free_rcu(struct rcu_head *head) 733e252fa7SRoss Zwisler { 743e252fa7SRoss Zwisler struct item *item = container_of(head, struct item, rcu_head); 753e252fa7SRoss Zwisler 763e252fa7SRoss Zwisler free(item); 773e252fa7SRoss Zwisler } 783e252fa7SRoss Zwisler 793e252fa7SRoss Zwisler int item_delete_rcu(struct radix_tree_root *root, unsigned long index) 803e252fa7SRoss Zwisler { 813e252fa7SRoss Zwisler struct item *item = radix_tree_delete(root, index); 823e252fa7SRoss Zwisler 833e252fa7SRoss Zwisler if (item) { 843e252fa7SRoss Zwisler item_sanity(item, index); 853e252fa7SRoss Zwisler call_rcu(&item->rcu_head, item_free_rcu); 863e252fa7SRoss Zwisler return 1; 873e252fa7SRoss Zwisler } 883e252fa7SRoss Zwisler return 0; 893e252fa7SRoss Zwisler } 903e252fa7SRoss Zwisler 911366c37eSMatthew Wilcox void item_check_present(struct radix_tree_root *root, unsigned long index) 921366c37eSMatthew Wilcox { 931366c37eSMatthew Wilcox struct item *item; 941366c37eSMatthew Wilcox 951366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 96101d9607SMatthew Wilcox assert(item != NULL); 97101d9607SMatthew Wilcox item_sanity(item, index); 981366c37eSMatthew Wilcox } 991366c37eSMatthew Wilcox 1001366c37eSMatthew Wilcox struct item *item_lookup(struct radix_tree_root *root, unsigned long index) 1011366c37eSMatthew Wilcox { 1021366c37eSMatthew Wilcox return radix_tree_lookup(root, index); 1031366c37eSMatthew Wilcox } 1041366c37eSMatthew Wilcox 1051366c37eSMatthew Wilcox void item_check_absent(struct radix_tree_root *root, unsigned long index) 1061366c37eSMatthew Wilcox { 1071366c37eSMatthew Wilcox struct item *item; 1081366c37eSMatthew Wilcox 1091366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 110101d9607SMatthew Wilcox assert(item == NULL); 1111366c37eSMatthew Wilcox } 1121366c37eSMatthew Wilcox 1131366c37eSMatthew Wilcox /* 1141366c37eSMatthew Wilcox * Scan only the passed (start, start+nr] for present items 1151366c37eSMatthew Wilcox */ 1161366c37eSMatthew Wilcox void item_gang_check_present(struct radix_tree_root *root, 1171366c37eSMatthew Wilcox unsigned long start, unsigned long nr, 1181366c37eSMatthew Wilcox int chunk, int hop) 1191366c37eSMatthew Wilcox { 1201366c37eSMatthew Wilcox struct item *items[chunk]; 1211366c37eSMatthew Wilcox unsigned long into; 1221366c37eSMatthew Wilcox 1231366c37eSMatthew Wilcox for (into = 0; into < nr; ) { 1241366c37eSMatthew Wilcox int nfound; 1251366c37eSMatthew Wilcox int nr_to_find = chunk; 1261366c37eSMatthew Wilcox int i; 1271366c37eSMatthew Wilcox 1281366c37eSMatthew Wilcox if (nr_to_find > (nr - into)) 1291366c37eSMatthew Wilcox nr_to_find = nr - into; 1301366c37eSMatthew Wilcox 1311366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1321366c37eSMatthew Wilcox start + into, nr_to_find); 1331366c37eSMatthew Wilcox assert(nfound == nr_to_find); 1341366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) 1351366c37eSMatthew Wilcox assert(items[i]->index == start + into + i); 1361366c37eSMatthew Wilcox into += hop; 1371366c37eSMatthew Wilcox } 1381366c37eSMatthew Wilcox } 1391366c37eSMatthew Wilcox 1401366c37eSMatthew Wilcox /* 1411366c37eSMatthew Wilcox * Scan the entire tree, only expecting present items (start, start+nr] 1421366c37eSMatthew Wilcox */ 1431366c37eSMatthew Wilcox void item_full_scan(struct radix_tree_root *root, unsigned long start, 1441366c37eSMatthew Wilcox unsigned long nr, int chunk) 1451366c37eSMatthew Wilcox { 1461366c37eSMatthew Wilcox struct item *items[chunk]; 1471366c37eSMatthew Wilcox unsigned long into = 0; 1481366c37eSMatthew Wilcox unsigned long this_index = start; 1491366c37eSMatthew Wilcox int nfound; 1501366c37eSMatthew Wilcox int i; 1511366c37eSMatthew Wilcox 1521366c37eSMatthew Wilcox // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); 1531366c37eSMatthew Wilcox 1541366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, 1551366c37eSMatthew Wilcox chunk))) { 1561366c37eSMatthew Wilcox // printf("At 0x%08lx, nfound=%d\n", into, nfound); 1571366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 1581366c37eSMatthew Wilcox assert(items[i]->index == this_index); 1591366c37eSMatthew Wilcox this_index++; 1601366c37eSMatthew Wilcox } 1611366c37eSMatthew Wilcox // printf("Found 0x%08lx->0x%08lx\n", 1621366c37eSMatthew Wilcox // items[0]->index, items[nfound-1]->index); 1631366c37eSMatthew Wilcox into = this_index; 1641366c37eSMatthew Wilcox } 1651366c37eSMatthew Wilcox if (chunk) 1661366c37eSMatthew Wilcox assert(this_index == start + nr); 1671366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1681366c37eSMatthew Wilcox this_index, chunk); 1691366c37eSMatthew Wilcox assert(nfound == 0); 1701366c37eSMatthew Wilcox } 1711366c37eSMatthew Wilcox 172268f42deSMatthew Wilcox /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */ 173372266baSMatthew Wilcox int tag_tagged_items(struct xarray *xa, unsigned long start, unsigned long end, 174372266baSMatthew Wilcox unsigned batch, xa_mark_t iftag, xa_mark_t thentag) 175268f42deSMatthew Wilcox { 176372266baSMatthew Wilcox XA_STATE(xas, xa, start); 177372266baSMatthew Wilcox unsigned int tagged = 0; 178372266baSMatthew Wilcox struct item *item; 179268f42deSMatthew Wilcox 180268f42deSMatthew Wilcox if (batch == 0) 181268f42deSMatthew Wilcox batch = 1; 182268f42deSMatthew Wilcox 183372266baSMatthew Wilcox xas_lock_irq(&xas); 184372266baSMatthew Wilcox xas_for_each_marked(&xas, item, end, iftag) { 185372266baSMatthew Wilcox xas_set_mark(&xas, thentag); 186372266baSMatthew Wilcox if (++tagged % batch) 187268f42deSMatthew Wilcox continue; 188372266baSMatthew Wilcox 189372266baSMatthew Wilcox xas_pause(&xas); 190372266baSMatthew Wilcox xas_unlock_irq(&xas); 191268f42deSMatthew Wilcox rcu_barrier(); 192372266baSMatthew Wilcox xas_lock_irq(&xas); 193268f42deSMatthew Wilcox } 194372266baSMatthew Wilcox xas_unlock_irq(&xas); 195268f42deSMatthew Wilcox 196268f42deSMatthew Wilcox return tagged; 197268f42deSMatthew Wilcox } 198268f42deSMatthew Wilcox 1991366c37eSMatthew Wilcox static int verify_node(struct radix_tree_node *slot, unsigned int tag, 2000694f0c9SMatthew Wilcox int tagged) 2011366c37eSMatthew Wilcox { 2021366c37eSMatthew Wilcox int anyset = 0; 2031366c37eSMatthew Wilcox int i; 2041366c37eSMatthew Wilcox int j; 2051366c37eSMatthew Wilcox 2064dd6c098SMatthew Wilcox slot = entry_to_node(slot); 207339e6353SMatthew Wilcox 2081366c37eSMatthew Wilcox /* Verify consistency at this level */ 2091366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 2101366c37eSMatthew Wilcox if (slot->tags[tag][i]) { 2111366c37eSMatthew Wilcox anyset = 1; 2121366c37eSMatthew Wilcox break; 2131366c37eSMatthew Wilcox } 2141366c37eSMatthew Wilcox } 2151366c37eSMatthew Wilcox if (tagged != anyset) { 2160694f0c9SMatthew Wilcox printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", 2170694f0c9SMatthew Wilcox tag, slot->shift, tagged, anyset); 2181366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 2191366c37eSMatthew Wilcox printf("tag %d: ", j); 2201366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 2211366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 2221366c37eSMatthew Wilcox printf("\n"); 2231366c37eSMatthew Wilcox } 2241366c37eSMatthew Wilcox return 1; 2251366c37eSMatthew Wilcox } 2261366c37eSMatthew Wilcox assert(tagged == anyset); 2271366c37eSMatthew Wilcox 2281366c37eSMatthew Wilcox /* Go for next level */ 2290694f0c9SMatthew Wilcox if (slot->shift > 0) { 2301366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 2311366c37eSMatthew Wilcox if (slot->slots[i]) 2320694f0c9SMatthew Wilcox if (verify_node(slot->slots[i], tag, 2331366c37eSMatthew Wilcox !!test_bit(i, slot->tags[tag]))) { 2341366c37eSMatthew Wilcox printf("Failure at off %d\n", i); 2351366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 2361366c37eSMatthew Wilcox printf("tag %d: ", j); 2371366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 2381366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 2391366c37eSMatthew Wilcox printf("\n"); 2401366c37eSMatthew Wilcox } 2411366c37eSMatthew Wilcox return 1; 2421366c37eSMatthew Wilcox } 2431366c37eSMatthew Wilcox } 2441366c37eSMatthew Wilcox return 0; 2451366c37eSMatthew Wilcox } 2461366c37eSMatthew Wilcox 2471366c37eSMatthew Wilcox void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 2481366c37eSMatthew Wilcox { 249f8d5d0ccSMatthew Wilcox struct radix_tree_node *node = root->xa_head; 250b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) 2511366c37eSMatthew Wilcox return; 2520694f0c9SMatthew Wilcox verify_node(node, tag, !!root_tag_get(root, tag)); 2531366c37eSMatthew Wilcox } 2541366c37eSMatthew Wilcox 255ccc89e30SMatthew Wilcox void item_kill_tree(struct xarray *xa) 2561366c37eSMatthew Wilcox { 257ccc89e30SMatthew Wilcox XA_STATE(xas, xa, 0); 258ccc89e30SMatthew Wilcox void *entry; 2591366c37eSMatthew Wilcox 260ccc89e30SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 261ccc89e30SMatthew Wilcox if (!xa_is_value(entry)) { 262ccc89e30SMatthew Wilcox item_free(entry, xas.xa_index); 263ccc89e30SMatthew Wilcox } 264ccc89e30SMatthew Wilcox xas_store(&xas, NULL); 2653ad75f8aSMatthew Wilcox } 2663ad75f8aSMatthew Wilcox 267ccc89e30SMatthew Wilcox assert(xa_empty(xa)); 2681366c37eSMatthew Wilcox } 2691366c37eSMatthew Wilcox 2701366c37eSMatthew Wilcox void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 2711366c37eSMatthew Wilcox { 2720694f0c9SMatthew Wilcox unsigned shift; 273f8d5d0ccSMatthew Wilcox struct radix_tree_node *node = root->xa_head; 274b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) { 2750694f0c9SMatthew Wilcox assert(maxindex == 0); 2760694f0c9SMatthew Wilcox return; 2770694f0c9SMatthew Wilcox } 2780694f0c9SMatthew Wilcox 2794dd6c098SMatthew Wilcox node = entry_to_node(node); 2800694f0c9SMatthew Wilcox assert(maxindex <= node_maxindex(node)); 2810694f0c9SMatthew Wilcox 2820694f0c9SMatthew Wilcox shift = node->shift; 2830694f0c9SMatthew Wilcox if (shift > 0) 2840694f0c9SMatthew Wilcox assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); 2850694f0c9SMatthew Wilcox else 2860694f0c9SMatthew Wilcox assert(maxindex > 0); 2871366c37eSMatthew Wilcox } 288