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