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