6 #include <linux/slab.h>
7 #include <linux/radix-tree.h>
13 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag)
15 unsigned long first = 0;
18 item_check_absent(tree, index);
19 assert(item_tag_get(tree, index, tag) == 0);
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);
26 ret = tag_tagged_items(tree, NULL, first, ~0UL, 10, tag, !tag);
28 ret = item_tag_get(tree, index, !tag);
30 ret = item_delete(tree, index);
32 item_insert(tree, index);
33 ret = item_tag_get(tree, index, tag);
35 ret = item_delete(tree, index);
37 ret = item_delete(tree, index);
41 void simple_checks(void)
44 RADIX_TREE(tree, GFP_KERNEL);
46 for (index = 0; index < 10000; index++) {
47 __simple_checks(&tree, index, 0);
48 __simple_checks(&tree, index, 1);
50 verify_tag_consistency(&tree, 0);
51 verify_tag_consistency(&tree, 1);
52 printv(2, "before item_kill_tree: %d allocated\n", nr_allocated);
53 item_kill_tree(&tree);
55 printv(2, "after item_kill_tree: %d allocated\n", nr_allocated);
59 * Check that tags propagate correctly when extending a tree.
61 static void extend_checks(void)
63 RADIX_TREE(tree, GFP_KERNEL);
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);
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); /* crash */
78 assert(item_tag_get(&tree, 0, 0) == 1);
80 verify_tag_consistency(&tree, 0);
82 item_kill_tree(&tree);
86 * Check that tags propagate correctly when contracting a tree.
88 static void contract_checks(void)
92 RADIX_TREE(tree, GFP_KERNEL);
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);
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);
106 assert(item_tag_get(&tree, tmp, 0) == 1);
107 assert(item_tag_get(&tree, tmp, 1) == 0);
109 verify_tag_consistency(&tree, 0);
110 item_kill_tree(&tree);
114 * Stupid tag thrasher
116 * Create a large linear array corresponding to the tree. Each element in
117 * the array is coherent with each node in the tree
126 #define THRASH_SIZE (1000 * 1000)
130 static void gang_check(struct radix_tree_root *tree,
131 char *thrash_state, int tag)
133 struct item *items[BATCH];
135 unsigned long index = 0;
136 unsigned long last_index = 0;
138 while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
139 index, BATCH, tag))) {
142 for (i = 0; i < nr_found; i++) {
143 struct item *item = items[i];
145 while (last_index < item->index) {
146 assert(thrash_state[last_index] != NODE_TAGGED);
149 assert(thrash_state[last_index] == NODE_TAGGED);
152 index = items[nr_found - 1]->index + 1;
156 static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag)
162 int total_tagged = 0;
163 int total_present = 0;
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) {
175 int actual_total_tagged;
176 int actual_total_present;
178 for (i = 0; i < insert_chunk; i++) {
179 index = rand() % THRASH_SIZE;
180 if (thrash_state[index] != NODE_ABSENT)
182 item_check_absent(tree, index);
183 item_insert(tree, index);
184 assert(thrash_state[index] != NODE_PRESENT);
185 thrash_state[index] = NODE_PRESENT;
190 for (i = 0; i < delete_chunk; i++) {
191 index = rand() % THRASH_SIZE;
192 if (thrash_state[index] == NODE_ABSENT)
194 item_check_present(tree, index);
195 if (item_tag_get(tree, index, tag)) {
196 assert(thrash_state[index] == NODE_TAGGED);
199 assert(thrash_state[index] == NODE_PRESENT);
201 item_delete(tree, index);
202 assert(thrash_state[index] != NODE_ABSENT);
203 thrash_state[index] = NODE_ABSENT;
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));
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;
223 for (i = 0; i < untag_chunk; i++) {
224 index = rand() % THRASH_SIZE;
225 if (thrash_state[index] != NODE_TAGGED)
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;
237 actual_total_tagged = 0;
238 actual_total_present = 0;
239 for (index = 0; index < THRASH_SIZE; index++) {
240 switch (thrash_state[index]) {
242 item_check_absent(tree, index);
245 item_check_present(tree, index);
246 assert(!item_tag_get(tree, index, tag));
247 actual_total_present++;
250 item_check_present(tree, index);
251 assert(item_tag_get(tree, index, tag));
252 actual_total_present++;
253 actual_total_tagged++;
258 gang_check(tree, thrash_state, tag);
260 printv(2, "%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);
271 static void thrash_tags(void)
273 RADIX_TREE(tree, GFP_KERNEL);
276 thrash_state = malloc(THRASH_SIZE);
277 memset(thrash_state, 0, THRASH_SIZE);
279 do_thrash(&tree, thrash_state, 0);
281 verify_tag_consistency(&tree, 0);
282 item_kill_tree(&tree);
286 static void leak_check(void)
288 RADIX_TREE(tree, GFP_KERNEL);
290 item_insert(&tree, 1000000);
291 item_delete(&tree, 1000000);
292 item_kill_tree(&tree);
295 static void __leak_check(void)
297 RADIX_TREE(tree, GFP_KERNEL);
299 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
300 item_insert(&tree, 1000000);
301 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
302 item_delete(&tree, 1000000);
303 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
304 item_kill_tree(&tree);
305 printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated);
308 static void single_check(void)
310 struct item *items[BATCH];
311 RADIX_TREE(tree, GFP_KERNEL);
313 unsigned long first = 0;
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);
319 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 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);
325 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
327 item_tag_clear(&tree, 0, 0);
328 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
330 item_kill_tree(&tree);
339 printv(2, "after extend_checks: %d allocated\n", nr_allocated);
343 printv(2, "after leak_check: %d allocated\n", nr_allocated);
346 printv(2, "after simple_checks: %d allocated\n", nr_allocated);
349 printv(2, "after thrash_tags: %d allocated\n", nr_allocated);