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 { 29 return __radix_tree_insert(root, item->index, item->order, item); 30 } 31 32 int item_insert(struct radix_tree_root *root, unsigned long index) 33 { 34 return __item_insert(root, item_create(index, 0)); 35 } 36 37 int item_insert_order(struct radix_tree_root *root, unsigned long index, 38 unsigned order) 39 { 40 return __item_insert(root, item_create(index, order)); 41 } 42 43 void item_sanity(struct item *item, unsigned long index) 44 { 45 unsigned long mask; 46 assert(!radix_tree_is_internal_node(item)); 47 assert(item->order < BITS_PER_LONG); 48 mask = (1UL << item->order) - 1; 49 assert((item->index | mask) == (index | mask)); 50 } 51 52 int item_delete(struct radix_tree_root *root, unsigned long index) 53 { 54 struct item *item = radix_tree_delete(root, index); 55 56 if (item) { 57 item_sanity(item, index); 58 free(item); 59 return 1; 60 } 61 return 0; 62 } 63 64 struct item *item_create(unsigned long index, unsigned int order) 65 { 66 struct item *ret = malloc(sizeof(*ret)); 67 68 ret->index = index; 69 ret->order = order; 70 return ret; 71 } 72 73 void item_check_present(struct radix_tree_root *root, unsigned long index) 74 { 75 struct item *item; 76 77 item = radix_tree_lookup(root, index); 78 assert(item != NULL); 79 item_sanity(item, index); 80 } 81 82 struct item *item_lookup(struct radix_tree_root *root, unsigned long index) 83 { 84 return radix_tree_lookup(root, index); 85 } 86 87 void item_check_absent(struct radix_tree_root *root, unsigned long index) 88 { 89 struct item *item; 90 91 item = radix_tree_lookup(root, index); 92 assert(item == NULL); 93 } 94 95 /* 96 * Scan only the passed (start, start+nr] for present items 97 */ 98 void item_gang_check_present(struct radix_tree_root *root, 99 unsigned long start, unsigned long nr, 100 int chunk, int hop) 101 { 102 struct item *items[chunk]; 103 unsigned long into; 104 105 for (into = 0; into < nr; ) { 106 int nfound; 107 int nr_to_find = chunk; 108 int i; 109 110 if (nr_to_find > (nr - into)) 111 nr_to_find = nr - into; 112 113 nfound = radix_tree_gang_lookup(root, (void **)items, 114 start + into, nr_to_find); 115 assert(nfound == nr_to_find); 116 for (i = 0; i < nfound; i++) 117 assert(items[i]->index == start + into + i); 118 into += hop; 119 } 120 } 121 122 /* 123 * Scan the entire tree, only expecting present items (start, start+nr] 124 */ 125 void item_full_scan(struct radix_tree_root *root, unsigned long start, 126 unsigned long nr, int chunk) 127 { 128 struct item *items[chunk]; 129 unsigned long into = 0; 130 unsigned long this_index = start; 131 int nfound; 132 int i; 133 134 // printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); 135 136 while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, 137 chunk))) { 138 // printf("At 0x%08lx, nfound=%d\n", into, nfound); 139 for (i = 0; i < nfound; i++) { 140 assert(items[i]->index == this_index); 141 this_index++; 142 } 143 // printf("Found 0x%08lx->0x%08lx\n", 144 // items[0]->index, items[nfound-1]->index); 145 into = this_index; 146 } 147 if (chunk) 148 assert(this_index == start + nr); 149 nfound = radix_tree_gang_lookup(root, (void **)items, 150 this_index, chunk); 151 assert(nfound == 0); 152 } 153 154 /* Use the same pattern as tag_pages_for_writeback() in mm/page-writeback.c */ 155 int tag_tagged_items(struct radix_tree_root *root, pthread_mutex_t *lock, 156 unsigned long start, unsigned long end, unsigned batch, 157 unsigned iftag, unsigned thentag) 158 { 159 unsigned long tagged = 0; 160 struct radix_tree_iter iter; 161 void **slot; 162 163 if (batch == 0) 164 batch = 1; 165 166 if (lock) 167 pthread_mutex_lock(lock); 168 radix_tree_for_each_tagged(slot, root, &iter, start, iftag) { 169 if (iter.index > end) 170 break; 171 radix_tree_iter_tag_set(root, &iter, thentag); 172 tagged++; 173 if ((tagged % batch) != 0) 174 continue; 175 slot = radix_tree_iter_resume(slot, &iter); 176 if (lock) { 177 pthread_mutex_unlock(lock); 178 rcu_barrier(); 179 pthread_mutex_lock(lock); 180 } 181 } 182 if (lock) 183 pthread_mutex_unlock(lock); 184 185 return tagged; 186 } 187 188 /* Use the same pattern as find_swap_entry() in mm/shmem.c */ 189 unsigned long find_item(struct radix_tree_root *root, void *item) 190 { 191 struct radix_tree_iter iter; 192 void **slot; 193 unsigned long found = -1; 194 unsigned long checked = 0; 195 196 radix_tree_for_each_slot(slot, root, &iter, 0) { 197 if (*slot == item) { 198 found = iter.index; 199 break; 200 } 201 checked++; 202 if ((checked % 4) != 0) 203 continue; 204 slot = radix_tree_iter_resume(slot, &iter); 205 } 206 207 return found; 208 } 209 210 static int verify_node(struct radix_tree_node *slot, unsigned int tag, 211 int tagged) 212 { 213 int anyset = 0; 214 int i; 215 int j; 216 217 slot = entry_to_node(slot); 218 219 /* Verify consistency at this level */ 220 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { 221 if (slot->tags[tag][i]) { 222 anyset = 1; 223 break; 224 } 225 } 226 if (tagged != anyset) { 227 printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", 228 tag, slot->shift, tagged, anyset); 229 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 230 printf("tag %d: ", j); 231 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 232 printf("%016lx ", slot->tags[j][i]); 233 printf("\n"); 234 } 235 return 1; 236 } 237 assert(tagged == anyset); 238 239 /* Go for next level */ 240 if (slot->shift > 0) { 241 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) 242 if (slot->slots[i]) 243 if (verify_node(slot->slots[i], tag, 244 !!test_bit(i, slot->tags[tag]))) { 245 printf("Failure at off %d\n", i); 246 for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { 247 printf("tag %d: ", j); 248 for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) 249 printf("%016lx ", slot->tags[j][i]); 250 printf("\n"); 251 } 252 return 1; 253 } 254 } 255 return 0; 256 } 257 258 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) 259 { 260 struct radix_tree_node *node = root->rnode; 261 if (!radix_tree_is_internal_node(node)) 262 return; 263 verify_node(node, tag, !!root_tag_get(root, tag)); 264 } 265 266 void item_kill_tree(struct radix_tree_root *root) 267 { 268 struct radix_tree_iter iter; 269 void **slot; 270 struct item *items[32]; 271 int nfound; 272 273 radix_tree_for_each_slot(slot, root, &iter, 0) { 274 if (radix_tree_exceptional_entry(*slot)) 275 radix_tree_delete(root, iter.index); 276 } 277 278 while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { 279 int i; 280 281 for (i = 0; i < nfound; i++) { 282 void *ret; 283 284 ret = radix_tree_delete(root, items[i]->index); 285 assert(ret == items[i]); 286 free(items[i]); 287 } 288 } 289 assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); 290 assert(root->rnode == NULL); 291 } 292 293 void tree_verify_min_height(struct radix_tree_root *root, int maxindex) 294 { 295 unsigned shift; 296 struct radix_tree_node *node = root->rnode; 297 if (!radix_tree_is_internal_node(node)) { 298 assert(maxindex == 0); 299 return; 300 } 301 302 node = entry_to_node(node); 303 assert(maxindex <= node_maxindex(node)); 304 305 shift = node->shift; 306 if (shift > 0) 307 assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT)); 308 else 309 assert(maxindex > 0); 310 } 311