Commit | Line | Data |
---|---|---|
1366c37e MW |
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 | ||
4f3755d1 MW |
27 | int __item_insert(struct radix_tree_root *root, struct item *item, |
28 | unsigned order) | |
1366c37e | 29 | { |
4f3755d1 | 30 | return __radix_tree_insert(root, item->index, order, item); |
1366c37e MW |
31 | } |
32 | ||
33 | int item_insert(struct radix_tree_root *root, unsigned long index) | |
34 | { | |
4f3755d1 MW |
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); | |
1366c37e MW |
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, | |
0694f0c9 | 146 | int tagged) |
1366c37e MW |
147 | { |
148 | int anyset = 0; | |
149 | int i; | |
150 | int j; | |
151 | ||
4dd6c098 | 152 | slot = entry_to_node(slot); |
339e6353 | 153 | |
1366c37e MW |
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) { | |
0694f0c9 MW |
162 | printf("tag: %u, shift %u, tagged: %d, anyset: %d\n", |
163 | tag, slot->shift, tagged, anyset); | |
1366c37e MW |
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 */ | |
0694f0c9 | 175 | if (slot->shift > 0) { |
1366c37e MW |
176 | for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) |
177 | if (slot->slots[i]) | |
0694f0c9 | 178 | if (verify_node(slot->slots[i], tag, |
1366c37e MW |
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 | { | |
0694f0c9 | 195 | struct radix_tree_node *node = root->rnode; |
b194d16c | 196 | if (!radix_tree_is_internal_node(node)) |
1366c37e | 197 | return; |
0694f0c9 | 198 | verify_node(node, tag, !!root_tag_get(root, tag)); |
1366c37e MW |
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 | { | |
0694f0c9 MW |
223 | unsigned shift; |
224 | struct radix_tree_node *node = root->rnode; | |
b194d16c | 225 | if (!radix_tree_is_internal_node(node)) { |
0694f0c9 MW |
226 | assert(maxindex == 0); |
227 | return; | |
228 | } | |
229 | ||
4dd6c098 | 230 | node = entry_to_node(node); |
0694f0c9 MW |
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); | |
1366c37e | 238 | } |