1#include <stdlib.h>
2#include <assert.h>
3#include <stdio.h>
4#include <string.h>
5
6#include <linux/slab.h>
7#include <linux/radix-tree.h>
8
9#include "test.h"
10
11
12static void
13__simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
14{
15 unsigned long first = 0;
16 int ret;
17
18 item_check_absent(tree, index);
19 assert(item_tag_get(tree, index, tag) == 0);
20
21 item_insert(tree, index);
22 assert(item_tag_get(tree, index, tag) == 0);
23 item_tag_set(tree, index, tag);
24 ret = item_tag_get(tree, index, tag);
25 assert(ret != 0);
26 ret = tag_tagged_items(tree, NULL, first, ~0UL, 10, tag, !tag);
27 assert(ret == 1);
28 ret = item_tag_get(tree, index, !tag);
29 assert(ret != 0);
30 ret = item_delete(tree, index);
31 assert(ret != 0);
32 item_insert(tree, index);
33 ret = item_tag_get(tree, index, tag);
34 assert(ret == 0);
35 ret = item_delete(tree, index);
36 assert(ret != 0);
37 ret = item_delete(tree, index);
38 assert(ret == 0);
39}
40
41void simple_checks(void)
42{
43 unsigned long index;
44 RADIX_TREE(tree, GFP_KERNEL);
45
46 for (index = 0; index < 10000; index++) {
47 __simple_checks(&tree, index, 0);
48 __simple_checks(&tree, index, 1);
49 }
50 verify_tag_consistency(&tree, 0);
51 verify_tag_consistency(&tree, 1);
52 printf("before item_kill_tree: %d allocated\n", nr_allocated);
53 item_kill_tree(&tree);
54 rcu_barrier();
55 printf("after item_kill_tree: %d allocated\n", nr_allocated);
56}
57
58
59
60
61static void extend_checks(void)
62{
63 RADIX_TREE(tree, GFP_KERNEL);
64
65 item_insert(&tree, 43);
66 assert(item_tag_get(&tree, 43, 0) == 0);
67 item_tag_set(&tree, 43, 0);
68 assert(item_tag_get(&tree, 43, 0) == 1);
69 item_insert(&tree, 1000000);
70 assert(item_tag_get(&tree, 43, 0) == 1);
71
72 item_insert(&tree, 0);
73 item_tag_set(&tree, 0, 0);
74 item_delete(&tree, 1000000);
75 assert(item_tag_get(&tree, 43, 0) != 0);
76 item_delete(&tree, 43);
77 assert(item_tag_get(&tree, 43, 0) == 0);
78 assert(item_tag_get(&tree, 0, 0) == 1);
79
80 verify_tag_consistency(&tree, 0);
81
82 item_kill_tree(&tree);
83}
84
85
86
87
88static void contract_checks(void)
89{
90 struct item *item;
91 int tmp;
92 RADIX_TREE(tree, GFP_KERNEL);
93
94 tmp = 1<<RADIX_TREE_MAP_SHIFT;
95 item_insert(&tree, tmp);
96 item_insert(&tree, tmp+1);
97 item_tag_set(&tree, tmp, 0);
98 item_tag_set(&tree, tmp, 1);
99 item_tag_set(&tree, tmp+1, 0);
100 item_delete(&tree, tmp+1);
101 item_tag_clear(&tree, tmp, 1);
102
103 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1);
104 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0);
105
106 assert(item_tag_get(&tree, tmp, 0) == 1);
107 assert(item_tag_get(&tree, tmp, 1) == 0);
108
109 verify_tag_consistency(&tree, 0);
110 item_kill_tree(&tree);
111}
112
113
114
115
116
117
118
119
120enum {
121 NODE_ABSENT = 0,
122 NODE_PRESENT = 1,
123 NODE_TAGGED = 2,
124};
125
126#define THRASH_SIZE (1000 * 1000)
127#define N 127
128#define BATCH 33
129
130static void gang_check(struct radix_tree_root *tree,
131 char *thrash_state, int tag)
132{
133 struct item *items[BATCH];
134 int nr_found;
135 unsigned long index = 0;
136 unsigned long last_index = 0;
137
138 while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
139 index, BATCH, tag))) {
140 int i;
141
142 for (i = 0; i < nr_found; i++) {
143 struct item *item = items[i];
144
145 while (last_index < item->index) {
146 assert(thrash_state[last_index] != NODE_TAGGED);
147 last_index++;
148 }
149 assert(thrash_state[last_index] == NODE_TAGGED);
150 last_index++;
151 }
152 index = items[nr_found - 1]->index + 1;
153 }
154}
155
156static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag)
157{
158 int insert_chunk;
159 int delete_chunk;
160 int tag_chunk;
161 int untag_chunk;
162 int total_tagged = 0;
163 int total_present = 0;
164
165 for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N)
166 for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N)
167 for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N)
168 for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) {
169 int i;
170 unsigned long index;
171 int nr_inserted = 0;
172 int nr_deleted = 0;
173 int nr_tagged = 0;
174 int nr_untagged = 0;
175 int actual_total_tagged;
176 int actual_total_present;
177
178 for (i = 0; i < insert_chunk; i++) {
179 index = rand() % THRASH_SIZE;
180 if (thrash_state[index] != NODE_ABSENT)
181 continue;
182 item_check_absent(tree, index);
183 item_insert(tree, index);
184 assert(thrash_state[index] != NODE_PRESENT);
185 thrash_state[index] = NODE_PRESENT;
186 nr_inserted++;
187 total_present++;
188 }
189
190 for (i = 0; i < delete_chunk; i++) {
191 index = rand() % THRASH_SIZE;
192 if (thrash_state[index] == NODE_ABSENT)
193 continue;
194 item_check_present(tree, index);
195 if (item_tag_get(tree, index, tag)) {
196 assert(thrash_state[index] == NODE_TAGGED);
197 total_tagged--;
198 } else {
199 assert(thrash_state[index] == NODE_PRESENT);
200 }
201 item_delete(tree, index);
202 assert(thrash_state[index] != NODE_ABSENT);
203 thrash_state[index] = NODE_ABSENT;
204 nr_deleted++;
205 total_present--;
206 }
207
208 for (i = 0; i < tag_chunk; i++) {
209 index = rand() % THRASH_SIZE;
210 if (thrash_state[index] != NODE_PRESENT) {
211 if (item_lookup(tree, index))
212 assert(item_tag_get(tree, index, tag));
213 continue;
214 }
215 item_tag_set(tree, index, tag);
216 item_tag_set(tree, index, tag);
217 assert(thrash_state[index] != NODE_TAGGED);
218 thrash_state[index] = NODE_TAGGED;
219 nr_tagged++;
220 total_tagged++;
221 }
222
223 for (i = 0; i < untag_chunk; i++) {
224 index = rand() % THRASH_SIZE;
225 if (thrash_state[index] != NODE_TAGGED)
226 continue;
227 item_check_present(tree, index);
228 assert(item_tag_get(tree, index, tag));
229 item_tag_clear(tree, index, tag);
230 item_tag_clear(tree, index, tag);
231 assert(thrash_state[index] != NODE_PRESENT);
232 thrash_state[index] = NODE_PRESENT;
233 nr_untagged++;
234 total_tagged--;
235 }
236
237 actual_total_tagged = 0;
238 actual_total_present = 0;
239 for (index = 0; index < THRASH_SIZE; index++) {
240 switch (thrash_state[index]) {
241 case NODE_ABSENT:
242 item_check_absent(tree, index);
243 break;
244 case NODE_PRESENT:
245 item_check_present(tree, index);
246 assert(!item_tag_get(tree, index, tag));
247 actual_total_present++;
248 break;
249 case NODE_TAGGED:
250 item_check_present(tree, index);
251 assert(item_tag_get(tree, index, tag));
252 actual_total_present++;
253 actual_total_tagged++;
254 break;
255 }
256 }
257
258 gang_check(tree, thrash_state, tag);
259
260 printf("%d(%d) %d(%d) %d(%d) %d(%d) / "
261 "%d(%d) present, %d(%d) tagged\n",
262 insert_chunk, nr_inserted,
263 delete_chunk, nr_deleted,
264 tag_chunk, nr_tagged,
265 untag_chunk, nr_untagged,
266 total_present, actual_total_present,
267 total_tagged, actual_total_tagged);
268 }
269}
270
271static void thrash_tags(void)
272{
273 RADIX_TREE(tree, GFP_KERNEL);
274 char *thrash_state;
275
276 thrash_state = malloc(THRASH_SIZE);
277 memset(thrash_state, 0, THRASH_SIZE);
278
279 do_thrash(&tree, thrash_state, 0);
280
281 verify_tag_consistency(&tree, 0);
282 item_kill_tree(&tree);
283 free(thrash_state);
284}
285
286static void leak_check(void)
287{
288 RADIX_TREE(tree, GFP_KERNEL);
289
290 item_insert(&tree, 1000000);
291 item_delete(&tree, 1000000);
292 item_kill_tree(&tree);
293}
294
295static void __leak_check(void)
296{
297 RADIX_TREE(tree, GFP_KERNEL);
298
299 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
300 item_insert(&tree, 1000000);
301 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
302 item_delete(&tree, 1000000);
303 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
304 item_kill_tree(&tree);
305 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
306}
307
308static void single_check(void)
309{
310 struct item *items[BATCH];
311 RADIX_TREE(tree, GFP_KERNEL);
312 int ret;
313 unsigned long first = 0;
314
315 item_insert(&tree, 0);
316 item_tag_set(&tree, 0, 0);
317 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
318 assert(ret == 1);
319 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0);
320 assert(ret == 0);
321 verify_tag_consistency(&tree, 0);
322 verify_tag_consistency(&tree, 1);
323 ret = tag_tagged_items(&tree, NULL, first, 10, 10, 0, 1);
324 assert(ret == 1);
325 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
326 assert(ret == 1);
327 item_tag_clear(&tree, 0, 0);
328 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
329 assert(ret == 0);
330 item_kill_tree(&tree);
331}
332
333void tag_check(void)
334{
335 single_check();
336 extend_checks();
337 contract_checks();
338 rcu_barrier();
339 printf("after extend_checks: %d allocated\n", nr_allocated);
340 __leak_check();
341 leak_check();
342 rcu_barrier();
343 printf("after leak_check: %d allocated\n", nr_allocated);
344 simple_checks();
345 rcu_barrier();
346 printf("after simple_checks: %d allocated\n", nr_allocated);
347 thrash_tags();
348 rcu_barrier();
349 printf("after thrash_tags: %d allocated\n", nr_allocated);
350}
351
