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 int tagged) 147 { 148 int anyset = 0; 149 int i; 150 int j; 151 152 slot = entry_to_node(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, shift %u, tagged: %d, anyset: %d\n", 163 tag, slot->shift, tagged, anyset); 164 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 165 printf("tag %d: ", j); 166 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 167 printf("%016lx ", slot->tags[j][i]); 168 printf("\n"); 169 } 170 return 1; 171 } 172 assert(tagged == anyset); 173 174 /* Go for next level */ 175 if (slot->shift > 0) { 176 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 177 if (slot->slots[i]) 178 if (verify_node(slot->slots[i], tag, 179 !!test_bit(i, slot->tags[tag]))) { 180 printf("Failure at off %d\n", i); 181 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 182 printf("tag %d: ", j); 183 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 184 printf("%016lx ", slot->tags[j][i]); 185 printf("\n"); 186 } 187 return 1; 188 } 189 } 190 return 0; 191 } 192 193 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 194 { 195 struct radix_tree_node *node = root->rnode; 196 if (!radix_tree_is_internal_node(node)) 197 return; 198 verify_node(node, tag, !!root_tag_get(root, tag)); 199 } 200 201 void item_kill_tree(struct radix_tree_root *root) 202 { 203 struct item *items[32]; 204 int nfound; 205 206 while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 207 int i; 208 209 for (i = 0; i < nfound; i++) { 210 void *ret; 211 212 ret = radix_tree_delete(root, items[i]->index); 213 assert(ret == items[i]); 214 free(items[i]); 215 } 216 } 217 assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 218 assert(root->rnode == NULL); 219 } 220 221 void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 222 { 223 unsigned shift; 224 struct radix_tree_node *node = root->rnode; 225 if (!radix_tree_is_internal_node(node)) { 226 assert(maxindex == 0); 227 return; 228 } 229 230 node = entry_to_node(node); 231 assert(maxindex <= node_maxindex(node)); 232 233 shift = node->shift; 234 if (shift > 0) 235 assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); 236 else 237 assert(maxindex > 0); 238 } 239