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 */ 179268f42deSMatthew Wilcox int tag_tagged_items(struct radix_tree_root *root, pthread_mutex_t *lock, 180268f42deSMatthew Wilcox unsigned long start, unsigned long end, unsigned batch, 181268f42deSMatthew Wilcox unsigned iftag, unsigned thentag) 182268f42deSMatthew Wilcox { 183268f42deSMatthew Wilcox unsigned long tagged = 0; 184268f42deSMatthew Wilcox struct radix_tree_iter iter; 185268f42deSMatthew Wilcox void **slot; 186268f42deSMatthew Wilcox 187268f42deSMatthew Wilcox if (batch == 0) 188268f42deSMatthew Wilcox batch = 1; 189268f42deSMatthew Wilcox 190268f42deSMatthew Wilcox if (lock) 191268f42deSMatthew Wilcox pthread_mutex_lock(lock); 192268f42deSMatthew Wilcox radix_tree_for_each_tagged(slot, root, &iter, start, iftag) { 193268f42deSMatthew Wilcox if (iter.index > end) 194268f42deSMatthew Wilcox break; 195268f42deSMatthew Wilcox radix_tree_iter_tag_set(root, &iter, thentag); 196268f42deSMatthew Wilcox tagged++; 197268f42deSMatthew Wilcox if ((tagged % batch) != 0) 198268f42deSMatthew Wilcox continue; 199268f42deSMatthew Wilcox slot = radix_tree_iter_resume(slot, &iter); 200268f42deSMatthew Wilcox if (lock) { 201268f42deSMatthew Wilcox pthread_mutex_unlock(lock); 202268f42deSMatthew Wilcox rcu_barrier(); 203268f42deSMatthew Wilcox pthread_mutex_lock(lock); 204268f42deSMatthew Wilcox } 205268f42deSMatthew Wilcox } 206268f42deSMatthew Wilcox if (lock) 207268f42deSMatthew Wilcox pthread_mutex_unlock(lock); 208268f42deSMatthew Wilcox 209268f42deSMatthew Wilcox return tagged; 210268f42deSMatthew Wilcox } 211268f42deSMatthew Wilcox 212478922e2SMatthew Wilcox /* Use the same pattern as find_swap_entry() in mm/shmem.c */ 213478922e2SMatthew Wilcox unsigned long find_item(struct radix_tree_root *root, void *item) 214478922e2SMatthew Wilcox { 215478922e2SMatthew Wilcox struct radix_tree_iter iter; 216478922e2SMatthew Wilcox void **slot; 217478922e2SMatthew Wilcox unsigned long found = -1; 218478922e2SMatthew Wilcox unsigned long checked = 0; 219478922e2SMatthew Wilcox 220478922e2SMatthew Wilcox radix_tree_for_each_slot(slot, root, &iter, 0) { 221478922e2SMatthew Wilcox if (*slot == item) { 222478922e2SMatthew Wilcox found = iter.index; 223478922e2SMatthew Wilcox break; 224478922e2SMatthew Wilcox } 225478922e2SMatthew Wilcox checked++; 226478922e2SMatthew Wilcox if ((checked % 4) != 0) 227478922e2SMatthew Wilcox continue; 228478922e2SMatthew Wilcox slot = radix_tree_iter_resume(slot, &iter); 229478922e2SMatthew Wilcox } 230478922e2SMatthew Wilcox 231478922e2SMatthew Wilcox return found; 232478922e2SMatthew Wilcox } 233478922e2SMatthew Wilcox 2341366c37eSMatthew Wilcox static int verify_node(struct radix_tree_node *slot, unsigned int tag, 2350694f0c9SMatthew Wilcox int tagged) 2361366c37eSMatthew Wilcox { 2371366c37eSMatthew Wilcox int anyset = 0; 2381366c37eSMatthew Wilcox int i; 2391366c37eSMatthew Wilcox int j; 2401366c37eSMatthew Wilcox 2414dd6c098SMatthew Wilcox slot = entry_to_node(slot); 242339e6353SMatthew Wilcox 2431366c37eSMatthew Wilcox /* Verify consistency at this level */ 2441366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 2451366c37eSMatthew Wilcox if (slot->tags[tag][i]) { 2461366c37eSMatthew Wilcox anyset = 1; 2471366c37eSMatthew Wilcox break; 2481366c37eSMatthew Wilcox } 2491366c37eSMatthew Wilcox } 2501366c37eSMatthew Wilcox if (tagged != anyset) { 2510694f0c9SMatthew Wilcox printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", 2520694f0c9SMatthew Wilcox tag, slot->shift, tagged, anyset); 2531366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 2541366c37eSMatthew Wilcox printf("tag %d: ", j); 2551366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 2561366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 2571366c37eSMatthew Wilcox printf("\n"); 2581366c37eSMatthew Wilcox } 2591366c37eSMatthew Wilcox return 1; 2601366c37eSMatthew Wilcox } 2611366c37eSMatthew Wilcox assert(tagged == anyset); 2621366c37eSMatthew Wilcox 2631366c37eSMatthew Wilcox /* Go for next level */ 2640694f0c9SMatthew Wilcox if (slot->shift > 0) { 2651366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 2661366c37eSMatthew Wilcox if (slot->slots[i]) 2670694f0c9SMatthew Wilcox if (verify_node(slot->slots[i], tag, 2681366c37eSMatthew Wilcox !!test_bit(i, slot->tags[tag]))) { 2691366c37eSMatthew Wilcox printf("Failure at off %d\n", i); 2701366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 2711366c37eSMatthew Wilcox printf("tag %d: ", j); 2721366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 2731366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 2741366c37eSMatthew Wilcox printf("\n"); 2751366c37eSMatthew Wilcox } 2761366c37eSMatthew Wilcox return 1; 2771366c37eSMatthew Wilcox } 2781366c37eSMatthew Wilcox } 2791366c37eSMatthew Wilcox return 0; 2801366c37eSMatthew Wilcox } 2811366c37eSMatthew Wilcox 2821366c37eSMatthew Wilcox void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 2831366c37eSMatthew Wilcox { 284f8d5d0ccSMatthew Wilcox struct radix_tree_node *node = root->xa_head; 285b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) 2861366c37eSMatthew Wilcox return; 2870694f0c9SMatthew Wilcox verify_node(node, tag, !!root_tag_get(root, tag)); 2881366c37eSMatthew Wilcox } 2891366c37eSMatthew Wilcox 2901366c37eSMatthew Wilcox void item_kill_tree(struct radix_tree_root *root) 2911366c37eSMatthew Wilcox { 2923ad75f8aSMatthew Wilcox struct radix_tree_iter iter; 2933ad75f8aSMatthew Wilcox void **slot; 2941366c37eSMatthew Wilcox struct item *items[32]; 2951366c37eSMatthew Wilcox int nfound; 2961366c37eSMatthew Wilcox 2973ad75f8aSMatthew Wilcox radix_tree_for_each_slot(slot, root, &iter, 0) { 2983159f943SMatthew Wilcox if (xa_is_value(*slot)) 2993ad75f8aSMatthew Wilcox radix_tree_delete(root, iter.index); 3003ad75f8aSMatthew Wilcox } 3013ad75f8aSMatthew Wilcox 3021366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 3031366c37eSMatthew Wilcox int i; 3041366c37eSMatthew Wilcox 3051366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 3061366c37eSMatthew Wilcox void *ret; 3071366c37eSMatthew Wilcox 3081366c37eSMatthew Wilcox ret = radix_tree_delete(root, items[i]->index); 3091366c37eSMatthew Wilcox assert(ret == items[i]); 3101366c37eSMatthew Wilcox free(items[i]); 3111366c37eSMatthew Wilcox } 3121366c37eSMatthew Wilcox } 3131366c37eSMatthew Wilcox assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 314f8d5d0ccSMatthew Wilcox assert(root->xa_head == NULL); 3151366c37eSMatthew Wilcox } 3161366c37eSMatthew Wilcox 3171366c37eSMatthew Wilcox void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 3181366c37eSMatthew Wilcox { 3190694f0c9SMatthew Wilcox unsigned shift; 320f8d5d0ccSMatthew Wilcox struct radix_tree_node *node = root->xa_head; 321b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) { 3220694f0c9SMatthew Wilcox assert(maxindex == 0); 3230694f0c9SMatthew Wilcox return; 3240694f0c9SMatthew Wilcox } 3250694f0c9SMatthew Wilcox 3264dd6c098SMatthew Wilcox node = entry_to_node(node); 3270694f0c9SMatthew Wilcox assert(maxindex <= node_maxindex(node)); 3280694f0c9SMatthew Wilcox 3290694f0c9SMatthew Wilcox shift = node->shift; 3300694f0c9SMatthew Wilcox if (shift > 0) 3310694f0c9SMatthew Wilcox assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); 3320694f0c9SMatthew Wilcox else 3330694f0c9SMatthew Wilcox assert(maxindex > 0); 3341366c37eSMatthew Wilcox } 335