11366c37eSMatthew Wilcox #include <stdlib.h> 21366c37eSMatthew Wilcox #include <assert.h> 31366c37eSMatthew Wilcox #include <stdio.h> 41366c37eSMatthew Wilcox #include <linux/types.h> 51366c37eSMatthew Wilcox #include <linux/kernel.h> 61366c37eSMatthew Wilcox #include <linux/bitops.h> 71366c37eSMatthew Wilcox 81366c37eSMatthew Wilcox #include "test.h" 91366c37eSMatthew Wilcox 101366c37eSMatthew Wilcox struct item * 111366c37eSMatthew Wilcox item_tag_set(struct radix_tree_root *root, unsigned long index, int tag) 121366c37eSMatthew Wilcox { 131366c37eSMatthew Wilcox return radix_tree_tag_set(root, index, tag); 141366c37eSMatthew Wilcox } 151366c37eSMatthew Wilcox 161366c37eSMatthew Wilcox struct item * 171366c37eSMatthew Wilcox item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) 181366c37eSMatthew Wilcox { 191366c37eSMatthew Wilcox return radix_tree_tag_clear(root, index, tag); 201366c37eSMatthew Wilcox } 211366c37eSMatthew Wilcox 221366c37eSMatthew Wilcox int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag) 231366c37eSMatthew Wilcox { 241366c37eSMatthew Wilcox return radix_tree_tag_get(root, index, tag); 251366c37eSMatthew Wilcox } 261366c37eSMatthew Wilcox 27101d9607SMatthew Wilcox int __item_insert(struct radix_tree_root *root, struct item *item) 281366c37eSMatthew Wilcox { 29101d9607SMatthew Wilcox return __radix_tree_insert(root, item->index, item->order, item); 301366c37eSMatthew Wilcox } 311366c37eSMatthew Wilcox 321366c37eSMatthew Wilcox int item_insert(struct radix_tree_root *root, unsigned long index) 331366c37eSMatthew Wilcox { 34101d9607SMatthew Wilcox return __item_insert(root, item_create(index, 0)); 354f3755d1SMatthew Wilcox } 364f3755d1SMatthew Wilcox 374f3755d1SMatthew Wilcox int item_insert_order(struct radix_tree_root *root, unsigned long index, 384f3755d1SMatthew Wilcox unsigned order) 394f3755d1SMatthew Wilcox { 40101d9607SMatthew Wilcox return __item_insert(root, item_create(index, order)); 41101d9607SMatthew Wilcox } 42101d9607SMatthew Wilcox 43101d9607SMatthew Wilcox void item_sanity(struct item *item, unsigned long index) 44101d9607SMatthew Wilcox { 45101d9607SMatthew Wilcox unsigned long mask; 46101d9607SMatthew Wilcox assert(!radix_tree_is_internal_node(item)); 47101d9607SMatthew Wilcox assert(item->order < BITS_PER_LONG); 48101d9607SMatthew Wilcox mask = (1UL << item->order) - 1; 49101d9607SMatthew Wilcox assert((item->index | mask) == (index | mask)); 501366c37eSMatthew Wilcox } 511366c37eSMatthew Wilcox 521366c37eSMatthew Wilcox int item_delete(struct radix_tree_root *root, unsigned long index) 531366c37eSMatthew Wilcox { 541366c37eSMatthew Wilcox struct item *item = radix_tree_delete(root, index); 551366c37eSMatthew Wilcox 561366c37eSMatthew Wilcox if (item) { 57101d9607SMatthew Wilcox item_sanity(item, index); 581366c37eSMatthew Wilcox free(item); 591366c37eSMatthew Wilcox return 1; 601366c37eSMatthew Wilcox } 611366c37eSMatthew Wilcox return 0; 621366c37eSMatthew Wilcox } 631366c37eSMatthew Wilcox 64101d9607SMatthew Wilcox struct item *item_create(unsigned long index, unsigned int order) 651366c37eSMatthew Wilcox { 661366c37eSMatthew Wilcox struct item *ret = malloc(sizeof(*ret)); 671366c37eSMatthew Wilcox 681366c37eSMatthew Wilcox ret->index = index; 69101d9607SMatthew Wilcox ret->order = order; 701366c37eSMatthew Wilcox return ret; 711366c37eSMatthew Wilcox } 721366c37eSMatthew Wilcox 731366c37eSMatthew Wilcox void item_check_present(struct radix_tree_root *root, unsigned long index) 741366c37eSMatthew Wilcox { 751366c37eSMatthew Wilcox struct item *item; 761366c37eSMatthew Wilcox 771366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 78101d9607SMatthew Wilcox assert(item != NULL); 79101d9607SMatthew Wilcox item_sanity(item, index); 801366c37eSMatthew Wilcox } 811366c37eSMatthew Wilcox 821366c37eSMatthew Wilcox struct item *item_lookup(struct radix_tree_root *root, unsigned long index) 831366c37eSMatthew Wilcox { 841366c37eSMatthew Wilcox return radix_tree_lookup(root, index); 851366c37eSMatthew Wilcox } 861366c37eSMatthew Wilcox 871366c37eSMatthew Wilcox void item_check_absent(struct radix_tree_root *root, unsigned long index) 881366c37eSMatthew Wilcox { 891366c37eSMatthew Wilcox struct item *item; 901366c37eSMatthew Wilcox 911366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 92101d9607SMatthew Wilcox assert(item == NULL); 931366c37eSMatthew Wilcox } 941366c37eSMatthew Wilcox 951366c37eSMatthew Wilcox /* 961366c37eSMatthew Wilcox * Scan only the passed (start, start+nr] for present items 971366c37eSMatthew Wilcox */ 981366c37eSMatthew Wilcox void item_gang_check_present(struct radix_tree_root *root, 991366c37eSMatthew Wilcox unsigned long start, unsigned long nr, 1001366c37eSMatthew Wilcox int chunk, int hop) 1011366c37eSMatthew Wilcox { 1021366c37eSMatthew Wilcox struct item *items[chunk]; 1031366c37eSMatthew Wilcox unsigned long into; 1041366c37eSMatthew Wilcox 1051366c37eSMatthew Wilcox for (into = 0; into < nr; ) { 1061366c37eSMatthew Wilcox int nfound; 1071366c37eSMatthew Wilcox int nr_to_find = chunk; 1081366c37eSMatthew Wilcox int i; 1091366c37eSMatthew Wilcox 1101366c37eSMatthew Wilcox if (nr_to_find > (nr - into)) 1111366c37eSMatthew Wilcox nr_to_find = nr - into; 1121366c37eSMatthew Wilcox 1131366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1141366c37eSMatthew Wilcox start + into, nr_to_find); 1151366c37eSMatthew Wilcox assert(nfound == nr_to_find); 1161366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) 1171366c37eSMatthew Wilcox assert(items[i]->index == start + into + i); 1181366c37eSMatthew Wilcox into += hop; 1191366c37eSMatthew Wilcox } 1201366c37eSMatthew Wilcox } 1211366c37eSMatthew Wilcox 1221366c37eSMatthew Wilcox /* 1231366c37eSMatthew Wilcox * Scan the entire tree, only expecting present items (start, start+nr] 1241366c37eSMatthew Wilcox */ 1251366c37eSMatthew Wilcox void item_full_scan(struct radix_tree_root *root, unsigned long start, 1261366c37eSMatthew Wilcox unsigned long nr, int chunk) 1271366c37eSMatthew Wilcox { 1281366c37eSMatthew Wilcox struct item *items[chunk]; 1291366c37eSMatthew Wilcox unsigned long into = 0; 1301366c37eSMatthew Wilcox unsigned long this_index = start; 1311366c37eSMatthew Wilcox int nfound; 1321366c37eSMatthew Wilcox int i; 1331366c37eSMatthew Wilcox 1341366c37eSMatthew Wilcox // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); 1351366c37eSMatthew Wilcox 1361366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, 1371366c37eSMatthew Wilcox chunk))) { 1381366c37eSMatthew Wilcox // printf("At 0x%08lx, nfound=%d\n", into, nfound); 1391366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 1401366c37eSMatthew Wilcox assert(items[i]->index == this_index); 1411366c37eSMatthew Wilcox this_index++; 1421366c37eSMatthew Wilcox } 1431366c37eSMatthew Wilcox // printf("Found 0x%08lx->0x%08lx\n", 1441366c37eSMatthew Wilcox // items[0]->index, items[nfound-1]->index); 1451366c37eSMatthew Wilcox into = this_index; 1461366c37eSMatthew Wilcox } 1471366c37eSMatthew Wilcox if (chunk) 1481366c37eSMatthew Wilcox assert(this_index == start + nr); 1491366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1501366c37eSMatthew Wilcox this_index, chunk); 1511366c37eSMatthew Wilcox assert(nfound == 0); 1521366c37eSMatthew Wilcox } 1531366c37eSMatthew Wilcox 1541366c37eSMatthew Wilcox static int verify_node(struct radix_tree_node *slot, unsigned int tag, 1550694f0c9SMatthew Wilcox int tagged) 1561366c37eSMatthew Wilcox { 1571366c37eSMatthew Wilcox int anyset = 0; 1581366c37eSMatthew Wilcox int i; 1591366c37eSMatthew Wilcox int j; 1601366c37eSMatthew Wilcox 1614dd6c098SMatthew Wilcox slot = entry_to_node(slot); 162339e6353SMatthew Wilcox 1631366c37eSMatthew Wilcox /* Verify consistency at this level */ 1641366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 1651366c37eSMatthew Wilcox if (slot->tags[tag][i]) { 1661366c37eSMatthew Wilcox anyset = 1; 1671366c37eSMatthew Wilcox break; 1681366c37eSMatthew Wilcox } 1691366c37eSMatthew Wilcox } 1701366c37eSMatthew Wilcox if (tagged != anyset) { 1710694f0c9SMatthew Wilcox printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", 1720694f0c9SMatthew Wilcox tag, slot->shift, tagged, anyset); 1731366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 1741366c37eSMatthew Wilcox printf("tag %d: ", j); 1751366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 1761366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 1771366c37eSMatthew Wilcox printf("\n"); 1781366c37eSMatthew Wilcox } 1791366c37eSMatthew Wilcox return 1; 1801366c37eSMatthew Wilcox } 1811366c37eSMatthew Wilcox assert(tagged == anyset); 1821366c37eSMatthew Wilcox 1831366c37eSMatthew Wilcox /* Go for next level */ 1840694f0c9SMatthew Wilcox if (slot->shift > 0) { 1851366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 1861366c37eSMatthew Wilcox if (slot->slots[i]) 1870694f0c9SMatthew Wilcox if (verify_node(slot->slots[i], tag, 1881366c37eSMatthew Wilcox !!test_bit(i, slot->tags[tag]))) { 1891366c37eSMatthew Wilcox printf("Failure at off %d\n", i); 1901366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 1911366c37eSMatthew Wilcox printf("tag %d: ", j); 1921366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 1931366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 1941366c37eSMatthew Wilcox printf("\n"); 1951366c37eSMatthew Wilcox } 1961366c37eSMatthew Wilcox return 1; 1971366c37eSMatthew Wilcox } 1981366c37eSMatthew Wilcox } 1991366c37eSMatthew Wilcox return 0; 2001366c37eSMatthew Wilcox } 2011366c37eSMatthew Wilcox 2021366c37eSMatthew Wilcox void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 2031366c37eSMatthew Wilcox { 2040694f0c9SMatthew Wilcox struct radix_tree_node *node = root->rnode; 205b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) 2061366c37eSMatthew Wilcox return; 2070694f0c9SMatthew Wilcox verify_node(node, tag, !!root_tag_get(root, tag)); 2081366c37eSMatthew Wilcox } 2091366c37eSMatthew Wilcox 2101366c37eSMatthew Wilcox void item_kill_tree(struct radix_tree_root *root) 2111366c37eSMatthew Wilcox { 2123ad75f8aSMatthew Wilcox struct radix_tree_iter iter; 2133ad75f8aSMatthew Wilcox void **slot; 2141366c37eSMatthew Wilcox struct item *items[32]; 2151366c37eSMatthew Wilcox int nfound; 2161366c37eSMatthew Wilcox 2173ad75f8aSMatthew Wilcox radix_tree_for_each_slot(slot, root, &iter, 0) { 2183ad75f8aSMatthew Wilcox if (radix_tree_exceptional_entry(*slot)) 2193ad75f8aSMatthew Wilcox radix_tree_delete(root, iter.index); 2203ad75f8aSMatthew Wilcox } 2213ad75f8aSMatthew Wilcox 2221366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 2231366c37eSMatthew Wilcox int i; 2241366c37eSMatthew Wilcox 2251366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 2261366c37eSMatthew Wilcox void *ret; 2271366c37eSMatthew Wilcox 2281366c37eSMatthew Wilcox ret = radix_tree_delete(root, items[i]->index); 2291366c37eSMatthew Wilcox assert(ret == items[i]); 2301366c37eSMatthew Wilcox free(items[i]); 2311366c37eSMatthew Wilcox } 2321366c37eSMatthew Wilcox } 2331366c37eSMatthew Wilcox assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 2341366c37eSMatthew Wilcox assert(root->rnode == NULL); 2351366c37eSMatthew Wilcox } 2361366c37eSMatthew Wilcox 2371366c37eSMatthew Wilcox void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 2381366c37eSMatthew Wilcox { 2390694f0c9SMatthew Wilcox unsigned shift; 2400694f0c9SMatthew Wilcox struct radix_tree_node *node = root->rnode; 241b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) { 2420694f0c9SMatthew Wilcox assert(maxindex == 0); 2430694f0c9SMatthew Wilcox return; 2440694f0c9SMatthew Wilcox } 2450694f0c9SMatthew Wilcox 2464dd6c098SMatthew Wilcox node = entry_to_node(node); 2470694f0c9SMatthew Wilcox assert(maxindex <= node_maxindex(node)); 2480694f0c9SMatthew Wilcox 2490694f0c9SMatthew Wilcox shift = node->shift; 2500694f0c9SMatthew Wilcox if (shift > 0) 2510694f0c9SMatthew Wilcox assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); 2520694f0c9SMatthew Wilcox else 2530694f0c9SMatthew Wilcox assert(maxindex > 0); 2541366c37eSMatthew Wilcox } 255