1 #include <stdlib.h> 2 #include <assert.h> 3 #include <stdio.h> 4 #include <linux/types.h> 5 #include <linux/kernel.h> 6 #include <linux/bitops.h> 7 8 #include "test.h" 9 10 struct item * 11 item_tag_set(struct radix_tree_root *root, unsigned long index, int tag) 12 { 13 return radix_tree_tag_set(root, index, tag); 14 } 15 16 struct item * 17 item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) 18 { 19 return radix_tree_tag_clear(root, index, tag); 20 } 21 22 int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag) 23 { 24 return radix_tree_tag_get(root, index, tag); 25 } 26 27 int __item_insert(struct radix_tree_root *root, struct item *item, 28 unsigned order) 29 { 30 return __radix_tree_insert(root, item->index, order, item); 31 } 32 33 int item_insert(struct radix_tree_root *root, unsigned long index) 34 { 35 return __item_insert(root, item_create(index), 0); 36 } 37 38 int item_insert_order(struct radix_tree_root *root, unsigned long index, 39 unsigned order) 40 { 41 return __item_insert(root, item_create(index), order); 42 } 43 44 int item_delete(struct radix_tree_root *root, unsigned long index) 45 { 46 struct item *item = radix_tree_delete(root, index); 47 48 if (item) { 49 assert(item->index == index); 50 free(item); 51 return 1; 52 } 53 return 0; 54 } 55 56 struct item *item_create(unsigned long index) 57 { 58 struct item *ret = malloc(sizeof(*ret)); 59 60 ret->index = index; 61 return ret; 62 } 63 64 void item_check_present(struct radix_tree_root *root, unsigned long index) 65 { 66 struct item *item; 67 68 item = radix_tree_lookup(root, index); 69 assert(item != 0); 70 assert(item->index == index); 71 } 72 73 struct item *item_lookup(struct radix_tree_root *root, unsigned long index) 74 { 75 return radix_tree_lookup(root, index); 76 } 77 78 void item_check_absent(struct radix_tree_root *root, unsigned long index) 79 { 80 struct item *item; 81 82 item = radix_tree_lookup(root, index); 83 assert(item == 0); 84 } 85 86 /* 87 * Scan only the passed (start, start+nr] for present items 88 */ 89 void item_gang_check_present(struct radix_tree_root *root, 90 unsigned long start, unsigned long nr, 91 int chunk, int hop) 92 { 93 struct item *items[chunk]; 94 unsigned long into; 95 96 for (into = 0; into < nr; ) { 97 int nfound; 98 int nr_to_find = chunk; 99 int i; 100 101 if (nr_to_find > (nr - into)) 102 nr_to_find = nr - into; 103 104 nfound = radix_tree_gang_lookup(root, (void **)items, 105 start + into, nr_to_find); 106 assert(nfound == nr_to_find); 107 for (i = 0; i < nfound; i++) 108 assert(items[i]->index == start + into + i); 109 into += hop; 110 } 111 } 112 113 /* 114 * Scan the entire tree, only expecting present items (start, start+nr] 115 */ 116 void item_full_scan(struct radix_tree_root *root, unsigned long start, 117 unsigned long nr, int chunk) 118 { 119 struct item *items[chunk]; 120 unsigned long into = 0; 121 unsigned long this_index = start; 122 int nfound; 123 int i; 124 125 // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); 126 127 while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, 128 chunk))) { 129 // printf("At 0x%08lx, nfound=%d\n", into, nfound); 130 for (i = 0; i < nfound; i++) { 131 assert(items[i]->index == this_index); 132 this_index++; 133 } 134 // printf("Found 0x%08lx->0x%08lx\n", 135 // items[0]->index, items[nfound-1]->index); 136 into = this_index; 137 } 138 if (chunk) 139 assert(this_index == start + nr); 140 nfound = radix_tree_gang_lookup(root, (void **)items, 141 this_index, chunk); 142 assert(nfound == 0); 143 } 144 145 static int verify_node(struct radix_tree_node *slot, unsigned int tag, 146 unsigned int height, int tagged) 147 { 148 int anyset = 0; 149 int i; 150 int j; 151 152 slot = indirect_to_ptr(slot); 153 154 /* Verify consistency at this level */ 155 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 156 if (slot->tags[tag][i]) { 157 anyset = 1; 158 break; 159 } 160 } 161 if (tagged != anyset) { 162 printf("tag: %u, height %u, tagged: %d, anyset: %d\n", tag, height, tagged, anyset); 163 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 164 printf("tag %d: ", j); 165 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 166 printf("%016lx ", slot->tags[j][i]); 167 printf("\n"); 168 } 169 return 1; 170 } 171 assert(tagged == anyset); 172 173 /* Go for next level */ 174 if (height > 1) { 175 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 176 if (slot->slots[i]) 177 if (verify_node(slot->slots[i], tag, height - 1, 178 !!test_bit(i, slot->tags[tag]))) { 179 printf("Failure at off %d\n", i); 180 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 181 printf("tag %d: ", j); 182 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 183 printf("%016lx ", slot->tags[j][i]); 184 printf("\n"); 185 } 186 return 1; 187 } 188 } 189 return 0; 190 } 191 192 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 193 { 194 if (!root->height) 195 return; 196 verify_node(root->rnode, tag, root->height, !!root_tag_get(root, tag)); 197 } 198 199 void item_kill_tree(struct radix_tree_root *root) 200 { 201 struct item *items[32]; 202 int nfound; 203 204 while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 205 int i; 206 207 for (i = 0; i < nfound; i++) { 208 void *ret; 209 210 ret = radix_tree_delete(root, items[i]->index); 211 assert(ret == items[i]); 212 free(items[i]); 213 } 214 } 215 assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 216 assert(root->rnode == NULL); 217 } 218 219 void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 220 { 221 assert(radix_tree_maxindex(root->height) >= maxindex); 222 if (root->height > 1) 223 assert(radix_tree_maxindex(root->height-1) < maxindex); 224 else if (root->height == 1) 225 assert(radix_tree_maxindex(root->height-1) <= maxindex); 226 } 227