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 271366c37eSMatthew Wilcox int __item_insert(struct radix_tree_root *root, struct item *item) 281366c37eSMatthew Wilcox { 291366c37eSMatthew Wilcox return radix_tree_insert(root, item->index, item); 301366c37eSMatthew Wilcox } 311366c37eSMatthew Wilcox 321366c37eSMatthew Wilcox int item_insert(struct radix_tree_root *root, unsigned long index) 331366c37eSMatthew Wilcox { 341366c37eSMatthew Wilcox return __item_insert(root, item_create(index)); 351366c37eSMatthew Wilcox } 361366c37eSMatthew Wilcox 371366c37eSMatthew Wilcox int item_delete(struct radix_tree_root *root, unsigned long index) 381366c37eSMatthew Wilcox { 391366c37eSMatthew Wilcox struct item *item = radix_tree_delete(root, index); 401366c37eSMatthew Wilcox 411366c37eSMatthew Wilcox if (item) { 421366c37eSMatthew Wilcox assert(item->index == index); 431366c37eSMatthew Wilcox free(item); 441366c37eSMatthew Wilcox return 1; 451366c37eSMatthew Wilcox } 461366c37eSMatthew Wilcox return 0; 471366c37eSMatthew Wilcox } 481366c37eSMatthew Wilcox 491366c37eSMatthew Wilcox struct item *item_create(unsigned long index) 501366c37eSMatthew Wilcox { 511366c37eSMatthew Wilcox struct item *ret = malloc(sizeof(*ret)); 521366c37eSMatthew Wilcox 531366c37eSMatthew Wilcox ret->index = index; 541366c37eSMatthew Wilcox return ret; 551366c37eSMatthew Wilcox } 561366c37eSMatthew Wilcox 571366c37eSMatthew Wilcox void item_check_present(struct radix_tree_root *root, unsigned long index) 581366c37eSMatthew Wilcox { 591366c37eSMatthew Wilcox struct item *item; 601366c37eSMatthew Wilcox 611366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 621366c37eSMatthew Wilcox assert(item != 0); 631366c37eSMatthew Wilcox assert(item->index == index); 641366c37eSMatthew Wilcox } 651366c37eSMatthew Wilcox 661366c37eSMatthew Wilcox struct item *item_lookup(struct radix_tree_root *root, unsigned long index) 671366c37eSMatthew Wilcox { 681366c37eSMatthew Wilcox return radix_tree_lookup(root, index); 691366c37eSMatthew Wilcox } 701366c37eSMatthew Wilcox 711366c37eSMatthew Wilcox void item_check_absent(struct radix_tree_root *root, unsigned long index) 721366c37eSMatthew Wilcox { 731366c37eSMatthew Wilcox struct item *item; 741366c37eSMatthew Wilcox 751366c37eSMatthew Wilcox item = radix_tree_lookup(root, index); 761366c37eSMatthew Wilcox assert(item == 0); 771366c37eSMatthew Wilcox } 781366c37eSMatthew Wilcox 791366c37eSMatthew Wilcox /* 801366c37eSMatthew Wilcox * Scan only the passed (start, start+nr] for present items 811366c37eSMatthew Wilcox */ 821366c37eSMatthew Wilcox void item_gang_check_present(struct radix_tree_root *root, 831366c37eSMatthew Wilcox unsigned long start, unsigned long nr, 841366c37eSMatthew Wilcox int chunk, int hop) 851366c37eSMatthew Wilcox { 861366c37eSMatthew Wilcox struct item *items[chunk]; 871366c37eSMatthew Wilcox unsigned long into; 881366c37eSMatthew Wilcox 891366c37eSMatthew Wilcox for (into = 0; into < nr; ) { 901366c37eSMatthew Wilcox int nfound; 911366c37eSMatthew Wilcox int nr_to_find = chunk; 921366c37eSMatthew Wilcox int i; 931366c37eSMatthew Wilcox 941366c37eSMatthew Wilcox if (nr_to_find > (nr - into)) 951366c37eSMatthew Wilcox nr_to_find = nr - into; 961366c37eSMatthew Wilcox 971366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 981366c37eSMatthew Wilcox start + into, nr_to_find); 991366c37eSMatthew Wilcox assert(nfound == nr_to_find); 1001366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) 1011366c37eSMatthew Wilcox assert(items[i]->index == start + into + i); 1021366c37eSMatthew Wilcox into += hop; 1031366c37eSMatthew Wilcox } 1041366c37eSMatthew Wilcox } 1051366c37eSMatthew Wilcox 1061366c37eSMatthew Wilcox /* 1071366c37eSMatthew Wilcox * Scan the entire tree, only expecting present items (start, start+nr] 1081366c37eSMatthew Wilcox */ 1091366c37eSMatthew Wilcox void item_full_scan(struct radix_tree_root *root, unsigned long start, 1101366c37eSMatthew Wilcox unsigned long nr, int chunk) 1111366c37eSMatthew Wilcox { 1121366c37eSMatthew Wilcox struct item *items[chunk]; 1131366c37eSMatthew Wilcox unsigned long into = 0; 1141366c37eSMatthew Wilcox unsigned long this_index = start; 1151366c37eSMatthew Wilcox int nfound; 1161366c37eSMatthew Wilcox int i; 1171366c37eSMatthew Wilcox 1181366c37eSMatthew Wilcox // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); 1191366c37eSMatthew Wilcox 1201366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, 1211366c37eSMatthew Wilcox chunk))) { 1221366c37eSMatthew Wilcox // printf("At 0x%08lx, nfound=%d\n", into, nfound); 1231366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 1241366c37eSMatthew Wilcox assert(items[i]->index == this_index); 1251366c37eSMatthew Wilcox this_index++; 1261366c37eSMatthew Wilcox } 1271366c37eSMatthew Wilcox // printf("Found 0x%08lx->0x%08lx\n", 1281366c37eSMatthew Wilcox // items[0]->index, items[nfound-1]->index); 1291366c37eSMatthew Wilcox into = this_index; 1301366c37eSMatthew Wilcox } 1311366c37eSMatthew Wilcox if (chunk) 1321366c37eSMatthew Wilcox assert(this_index == start + nr); 1331366c37eSMatthew Wilcox nfound = radix_tree_gang_lookup(root, (void **)items, 1341366c37eSMatthew Wilcox this_index, chunk); 1351366c37eSMatthew Wilcox assert(nfound == 0); 1361366c37eSMatthew Wilcox } 1371366c37eSMatthew Wilcox 1381366c37eSMatthew Wilcox static int verify_node(struct radix_tree_node *slot, unsigned int tag, 1391366c37eSMatthew Wilcox unsigned int height, int tagged) 1401366c37eSMatthew Wilcox { 1411366c37eSMatthew Wilcox int anyset = 0; 1421366c37eSMatthew Wilcox int i; 1431366c37eSMatthew Wilcox int j; 1441366c37eSMatthew Wilcox 145339e6353SMatthew Wilcox slot = indirect_to_ptr(slot); 146339e6353SMatthew Wilcox 1471366c37eSMatthew Wilcox /* Verify consistency at this level */ 1481366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 1491366c37eSMatthew Wilcox if (slot->tags[tag][i]) { 1501366c37eSMatthew Wilcox anyset = 1; 1511366c37eSMatthew Wilcox break; 1521366c37eSMatthew Wilcox } 1531366c37eSMatthew Wilcox } 1541366c37eSMatthew Wilcox if (tagged != anyset) { 1551366c37eSMatthew Wilcox printf("tag: %u, height %u, tagged: %d, anyset: %d\n", tag, height, tagged, anyset); 1561366c37eSMatthew Wilcox for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 1571366c37eSMatthew Wilcox printf("tag %d: ", j); 1581366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 1591366c37eSMatthew Wilcox printf("%016lx ", slot->tags[j][i]); 1601366c37eSMatthew Wilcox printf("\n"); 1611366c37eSMatthew Wilcox } 1621366c37eSMatthew Wilcox return 1; 1631366c37eSMatthew Wilcox } 1641366c37eSMatthew Wilcox assert(tagged == anyset); 1651366c37eSMatthew Wilcox 1661366c37eSMatthew Wilcox /* Go for next level */ 1671366c37eSMatthew Wilcox if (height > 1) { 1681366c37eSMatthew Wilcox for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 1691366c37eSMatthew Wilcox if (slot->slots[i]) 1701366c37eSMatthew Wilcox if (verify_node(slot->slots[i], tag, height - 1, 1711366c37eSMatthew Wilcox !!test_bit(i, slot->tags[tag]))) { 1721366c37eSMatthew Wilcox printf("Failure at off %d\n", i); 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 } 1821366c37eSMatthew Wilcox return 0; 1831366c37eSMatthew Wilcox } 1841366c37eSMatthew Wilcox 1851366c37eSMatthew Wilcox void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 1861366c37eSMatthew Wilcox { 1871366c37eSMatthew Wilcox if (!root->height) 1881366c37eSMatthew Wilcox return; 189339e6353SMatthew Wilcox verify_node(root->rnode, tag, root->height, !!root_tag_get(root, tag)); 1901366c37eSMatthew Wilcox } 1911366c37eSMatthew Wilcox 1921366c37eSMatthew Wilcox void item_kill_tree(struct radix_tree_root *root) 1931366c37eSMatthew Wilcox { 1941366c37eSMatthew Wilcox struct item *items[32]; 1951366c37eSMatthew Wilcox int nfound; 1961366c37eSMatthew Wilcox 1971366c37eSMatthew Wilcox while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 1981366c37eSMatthew Wilcox int i; 1991366c37eSMatthew Wilcox 2001366c37eSMatthew Wilcox for (i = 0; i < nfound; i++) { 2011366c37eSMatthew Wilcox void *ret; 2021366c37eSMatthew Wilcox 2031366c37eSMatthew Wilcox ret = radix_tree_delete(root, items[i]->index); 2041366c37eSMatthew Wilcox assert(ret == items[i]); 2051366c37eSMatthew Wilcox free(items[i]); 2061366c37eSMatthew Wilcox } 2071366c37eSMatthew Wilcox } 2081366c37eSMatthew Wilcox assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 2091366c37eSMatthew Wilcox assert(root->rnode == NULL); 2101366c37eSMatthew Wilcox } 2111366c37eSMatthew Wilcox 2121366c37eSMatthew Wilcox void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 2131366c37eSMatthew Wilcox { 2141366c37eSMatthew Wilcox assert(radix_tree_maxindex(root->height) >= maxindex); 2151366c37eSMatthew Wilcox if (root->height > 1) 2161366c37eSMatthew Wilcox assert(radix_tree_maxindex(root->height-1) < maxindex); 2171366c37eSMatthew Wilcox else if (root->height == 1) 2181366c37eSMatthew Wilcox assert(radix_tree_maxindex(root->height-1) <= maxindex); 2191366c37eSMatthew Wilcox } 220