Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 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 | |
Matthew Wilcox | 4f3755d | 2016-05-20 17:02:14 -0700 | [diff] [blame] | 27 | int __item_insert(struct radix_tree_root *root, struct item *item, |
| 28 | unsigned order) |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 29 | { |
Matthew Wilcox | 4f3755d | 2016-05-20 17:02:14 -0700 | [diff] [blame] | 30 | return __radix_tree_insert(root, item->index, order, item); |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 31 | } |
| 32 | |
| 33 | int item_insert(struct radix_tree_root *root, unsigned long index) |
| 34 | { |
Matthew Wilcox | 4f3755d | 2016-05-20 17:02:14 -0700 | [diff] [blame] | 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); |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 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, |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 146 | int tagged) |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 147 | { |
| 148 | int anyset = 0; |
| 149 | int i; |
| 150 | int j; |
| 151 | |
Matthew Wilcox | 4dd6c09 | 2016-05-20 17:03:27 -0700 | [diff] [blame] | 152 | slot = entry_to_node(slot); |
Matthew Wilcox | 339e635 | 2016-03-17 14:21:48 -0700 | [diff] [blame] | 153 | |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 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) { |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 162 | printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", |
| 163 | tag, slot->shift, tagged, anyset); |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 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 */ |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 175 | if (slot->shift > 0) { |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 176 | for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) |
| 177 | if (slot->slots[i]) |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 178 | if (verify_node(slot->slots[i], tag, |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 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 | { |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 195 | struct radix_tree_node *node = root->rnode; |
Matthew Wilcox | b194d16 | 2016-05-20 17:03:30 -0700 | [diff] [blame] | 196 | if (!radix_tree_is_internal_node(node)) |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 197 | return; |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 198 | verify_node(node, tag, !!root_tag_get(root, tag)); |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 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 | { |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 223 | unsigned shift; |
| 224 | struct radix_tree_node *node = root->rnode; |
Matthew Wilcox | b194d16 | 2016-05-20 17:03:30 -0700 | [diff] [blame] | 225 | if (!radix_tree_is_internal_node(node)) { |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 226 | assert(maxindex == 0); |
| 227 | return; |
| 228 | } |
| 229 | |
Matthew Wilcox | 4dd6c09 | 2016-05-20 17:03:27 -0700 | [diff] [blame] | 230 | node = entry_to_node(node); |
Matthew Wilcox | 0694f0c | 2016-05-20 17:03:16 -0700 | [diff] [blame] | 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); |
Matthew Wilcox | 1366c37 | 2016-03-17 14:21:45 -0700 | [diff] [blame] | 238 | } |