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 274f3755d1SMatthew Wilcox int __item_insert(struct radix_tree_root *root, struct item *item, 284f3755d1SMatthew Wilcox unsigned order) 291366c37eSMatthew Wilcox { 304f3755d1SMatthew Wilcox return __radix_tree_insert(root, item->index, order, item); 311366c37eSMatthew Wilcox } 321366c37eSMatthew Wilcox 331366c37eSMatthew Wilcox int item_insert(struct radix_tree_root *root, unsigned long index) 341366c37eSMatthew Wilcox { 354f3755d1SMatthew Wilcox return __item_insert(root, item_create(index), 0); 364f3755d1SMatthew Wilcox } 374f3755d1SMatthew Wilcox 384f3755d1SMatthew Wilcox int item_insert_order(struct radix_tree_root *root, unsigned long index, 394f3755d1SMatthew Wilcox unsigned order) 404f3755d1SMatthew Wilcox { 414f3755d1SMatthew Wilcox return __item_insert(root, item_create(index), order); 421366c37eSMatthew Wilcox } 431366c37eSMatthew Wilcox 441366c37eSMatthew Wilcox int item_delete(struct radix_tree_root *root, unsigned long index) 451366c37eSMatthew Wilcox { 461366c37eSMatthew Wilcox struct item *item = radix_tree_delete(root, index); 471366c37eSMatthew Wilcox 481366c37eSMatthew Wilcox if (item) { 491366c37eSMatthew Wilcox assert(item->index == index); 501366c37eSMatthew Wilcox free(item); 511366c37eSMatthew Wilcox return 1; 521366c37eSMatthew Wilcox } 531366c37eSMatthew Wilcox return 0; 541366c37eSMatthew Wilcox } 551366c37eSMatthew Wilcox 561366c37eSMatthew Wilcox struct item *item_create(unsigned long index) 571366c37eSMatthew Wilcox { 581366c37eSMatthew Wilcox struct item *ret = malloc(sizeof(*ret)); 591366c37eSMatthew Wilcox 601366c37eSMatthew Wilcox ret->index = index; 611366c37eSMatthew Wilcox return ret; 621366c37eSMatthew Wilcox } 631366c37eSMatthew Wilcox 641366c37eSMatthew Wilcox void item_check_present(struct radix_tree_root *root, unsigned long index) 651366c37eSMatthew Wilcox { 661366c37eSMatthew Wilcox struct item *item; 671366c37eSMatthew Wilcox 681366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 691366c37eSMatthew Wilcox assert(item != 0); 701366c37eSMatthew Wilcox assert(item->index == index); 711366c37eSMatthew Wilcox } 721366c37eSMatthew Wilcox 731366c37eSMatthew Wilcox struct item *item_lookup(struct radix_tree_root *root, unsigned long index) 741366c37eSMatthew Wilcox { 751366c37eSMatthew Wilcox return radix_tree_lookup(root, index); 761366c37eSMatthew Wilcox } 771366c37eSMatthew Wilcox 781366c37eSMatthew Wilcox void item_check_absent(struct radix_tree_root *root, unsigned long index) 791366c37eSMatthew Wilcox { 801366c37eSMatthew Wilcox struct item *item; 811366c37eSMatthew Wilcox 821366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 831366c37eSMatthew Wilcox assert(item == 0); 841366c37eSMatthew Wilcox } 851366c37eSMatthew Wilcox 861366c37eSMatthew Wilcox /* 871366c37eSMatthew Wilcox * Scan only the passed (start, start+nr] for present items 881366c37eSMatthew Wilcox */ 891366c37eSMatthew Wilcox void item_gang_check_present(struct radix_tree_root *root, 901366c37eSMatthew Wilcox unsigned long start, unsigned long nr, 911366c37eSMatthew Wilcox int chunk, int hop) 921366c37eSMatthew Wilcox { 931366c37eSMatthew Wilcox struct item *items[chunk]; 941366c37eSMatthew Wilcox unsigned long into; 951366c37eSMatthew Wilcox 961366c37eSMatthew Wilcox for (into = 0; into < nr; ) { 971366c37eSMatthew Wilcox int nfound; 981366c37eSMatthew Wilcox int nr_to_find = chunk; 991366c37eSMatthew Wilcox int i; 1001366c37eSMatthew Wilcox 1011366c37eSMatthew Wilcox if (nr_to_find > (nr - into)) 1021366c37eSMatthew Wilcox nr_to_find = nr - into; 1031366c37eSMatthew Wilcox 1041366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1051366c37eSMatthew Wilcox start + into, nr_to_find); 1061366c37eSMatthew Wilcox assert(nfound == nr_to_find); 1071366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) 1081366c37eSMatthew Wilcox assert(items[i]->index == start + into + i); 1091366c37eSMatthew Wilcox into += hop; 1101366c37eSMatthew Wilcox } 1111366c37eSMatthew Wilcox } 1121366c37eSMatthew Wilcox 1131366c37eSMatthew Wilcox /* 1141366c37eSMatthew Wilcox * Scan the entire tree, only expecting present items (start, start+nr] 1151366c37eSMatthew Wilcox */ 1161366c37eSMatthew Wilcox void item_full_scan(struct radix_tree_root *root, unsigned long start, 1171366c37eSMatthew Wilcox unsigned long nr, int chunk) 1181366c37eSMatthew Wilcox { 1191366c37eSMatthew Wilcox struct item *items[chunk]; 1201366c37eSMatthew Wilcox unsigned long into = 0; 1211366c37eSMatthew Wilcox unsigned long this_index = start; 1221366c37eSMatthew Wilcox int nfound; 1231366c37eSMatthew Wilcox int i; 1241366c37eSMatthew Wilcox 1251366c37eSMatthew Wilcox // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); 1261366c37eSMatthew Wilcox 1271366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, 1281366c37eSMatthew Wilcox chunk))) { 1291366c37eSMatthew Wilcox // printf("At 0x%08lx, nfound=%d\n", into, nfound); 1301366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 1311366c37eSMatthew Wilcox assert(items[i]->index == this_index); 1321366c37eSMatthew Wilcox this_index++; 1331366c37eSMatthew Wilcox } 1341366c37eSMatthew Wilcox // printf("Found 0x%08lx->0x%08lx\n", 1351366c37eSMatthew Wilcox // items[0]->index, items[nfound-1]->index); 1361366c37eSMatthew Wilcox into = this_index; 1371366c37eSMatthew Wilcox } 1381366c37eSMatthew Wilcox if (chunk) 1391366c37eSMatthew Wilcox assert(this_index == start + nr); 1401366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1411366c37eSMatthew Wilcox this_index, chunk); 1421366c37eSMatthew Wilcox assert(nfound == 0); 1431366c37eSMatthew Wilcox } 1441366c37eSMatthew Wilcox 1451366c37eSMatthew Wilcox static int verify_node(struct radix_tree_node *slot, unsigned int tag, 1460694f0c9SMatthew Wilcox int tagged) 1471366c37eSMatthew Wilcox { 1481366c37eSMatthew Wilcox int anyset = 0; 1491366c37eSMatthew Wilcox int i; 1501366c37eSMatthew Wilcox int j; 1511366c37eSMatthew Wilcox 1524dd6c098SMatthew Wilcox slot = entry_to_node(slot); 153339e6353SMatthew Wilcox 1541366c37eSMatthew Wilcox /* Verify consistency at this level */ 1551366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 1561366c37eSMatthew Wilcox if (slot->tags[tag][i]) { 1571366c37eSMatthew Wilcox anyset = 1; 1581366c37eSMatthew Wilcox break; 1591366c37eSMatthew Wilcox } 1601366c37eSMatthew Wilcox } 1611366c37eSMatthew Wilcox if (tagged != anyset) { 1620694f0c9SMatthew Wilcox printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", 1630694f0c9SMatthew Wilcox tag, slot->shift, tagged, anyset); 1641366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 1651366c37eSMatthew Wilcox printf("tag %d: ", j); 1661366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 1671366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 1681366c37eSMatthew Wilcox printf("\n"); 1691366c37eSMatthew Wilcox } 1701366c37eSMatthew Wilcox return 1; 1711366c37eSMatthew Wilcox } 1721366c37eSMatthew Wilcox assert(tagged == anyset); 1731366c37eSMatthew Wilcox 1741366c37eSMatthew Wilcox /* Go for next level */ 1750694f0c9SMatthew Wilcox if (slot->shift > 0) { 1761366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 1771366c37eSMatthew Wilcox if (slot->slots[i]) 1780694f0c9SMatthew Wilcox if (verify_node(slot->slots[i], tag, 1791366c37eSMatthew Wilcox !!test_bit(i, slot->tags[tag]))) { 1801366c37eSMatthew Wilcox printf("Failure at off %d\n", i); 1811366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 1821366c37eSMatthew Wilcox printf("tag %d: ", j); 1831366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 1841366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 1851366c37eSMatthew Wilcox printf("\n"); 1861366c37eSMatthew Wilcox } 1871366c37eSMatthew Wilcox return 1; 1881366c37eSMatthew Wilcox } 1891366c37eSMatthew Wilcox } 1901366c37eSMatthew Wilcox return 0; 1911366c37eSMatthew Wilcox } 1921366c37eSMatthew Wilcox 1931366c37eSMatthew Wilcox void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 1941366c37eSMatthew Wilcox { 1950694f0c9SMatthew Wilcox struct radix_tree_node *node = root->rnode; 196b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) 1971366c37eSMatthew Wilcox return; 1980694f0c9SMatthew Wilcox verify_node(node, tag, !!root_tag_get(root, tag)); 1991366c37eSMatthew Wilcox } 2001366c37eSMatthew Wilcox 2011366c37eSMatthew Wilcox void item_kill_tree(struct radix_tree_root *root) 2021366c37eSMatthew Wilcox { 2031366c37eSMatthew Wilcox struct item *items[32]; 2041366c37eSMatthew Wilcox int nfound; 2051366c37eSMatthew Wilcox 2061366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 2071366c37eSMatthew Wilcox int i; 2081366c37eSMatthew Wilcox 2091366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 2101366c37eSMatthew Wilcox void *ret; 2111366c37eSMatthew Wilcox 2121366c37eSMatthew Wilcox ret = radix_tree_delete(root, items[i]->index); 2131366c37eSMatthew Wilcox assert(ret == items[i]); 2141366c37eSMatthew Wilcox free(items[i]); 2151366c37eSMatthew Wilcox } 2161366c37eSMatthew Wilcox } 2171366c37eSMatthew Wilcox assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 2181366c37eSMatthew Wilcox assert(root->rnode == NULL); 2191366c37eSMatthew Wilcox } 2201366c37eSMatthew Wilcox 2211366c37eSMatthew Wilcox void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 2221366c37eSMatthew Wilcox { 2230694f0c9SMatthew Wilcox unsigned shift; 2240694f0c9SMatthew Wilcox struct radix_tree_node *node = root->rnode; 225b194d16cSMatthew Wilcox if (!radix_tree_is_internal_node(node)) { 2260694f0c9SMatthew Wilcox assert(maxindex == 0); 2270694f0c9SMatthew Wilcox return; 2280694f0c9SMatthew Wilcox } 2290694f0c9SMatthew Wilcox 2304dd6c098SMatthew Wilcox node = entry_to_node(node); 2310694f0c9SMatthew Wilcox assert(maxindex <= node_maxindex(node)); 2320694f0c9SMatthew Wilcox 2330694f0c9SMatthew Wilcox shift = node->shift; 2340694f0c9SMatthew Wilcox if (shift > 0) 2350694f0c9SMatthew Wilcox assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); 2360694f0c9SMatthew Wilcox else 2370694f0c9SMatthew Wilcox assert(maxindex > 0); 2381366c37eSMatthew Wilcox } 239