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