]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - tools/testing/radix-tree/tag_check.c
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
);
333 void radix_tree_clear_tags_test(void)
336 struct radix_tree_node
*node
;
337 struct radix_tree_iter iter
;
340 RADIX_TREE(tree
, GFP_KERNEL
);
342 item_insert(&tree
, 0);
343 item_tag_set(&tree
, 0, 0);
344 __radix_tree_lookup(&tree
, 0, &node
, &slot
);
345 radix_tree_clear_tags(&tree
, node
, slot
);
346 assert(item_tag_get(&tree
, 0, 0) == 0);
348 for (index
= 0; index
< 1000; index
++) {
349 item_insert(&tree
, index
);
350 item_tag_set(&tree
, index
, 0);
353 radix_tree_for_each_slot(slot
, &tree
, &iter
, 0) {
354 radix_tree_clear_tags(&tree
, iter
.node
, slot
);
355 assert(item_tag_get(&tree
, iter
.index
, 0) == 0);
358 item_kill_tree(&tree
);
367 printv(2, "after extend_checks: %d allocated\n", nr_allocated
);
371 printv(2, "after leak_check: %d allocated\n", nr_allocated
);
374 printv(2, "after simple_checks: %d allocated\n", nr_allocated
);
377 printv(2, "after thrash_tags: %d allocated\n", nr_allocated
);
378 radix_tree_clear_tags_test();