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 = radix_tree_range_tag_if_tagged(tree, &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 printf("before item_kill_tree: %d allocated\n", nr_allocated);
53 item_kill_tree(&tree);
54 printf("after item_kill_tree: %d allocated\n", nr_allocated);
58 * Check that tags propagate correctly when extending a tree.
60 static void extend_checks(void)
62 RADIX_TREE(tree, GFP_KERNEL);
64 item_insert(&tree, 43);
65 assert(item_tag_get(&tree, 43, 0) == 0);
66 item_tag_set(&tree, 43, 0);
67 assert(item_tag_get(&tree, 43, 0) == 1);
68 item_insert(&tree, 1000000);
69 assert(item_tag_get(&tree, 43, 0) == 1);
71 item_insert(&tree, 0);
72 item_tag_set(&tree, 0, 0);
73 item_delete(&tree, 1000000);
74 assert(item_tag_get(&tree, 43, 0) != 0);
75 item_delete(&tree, 43);
76 assert(item_tag_get(&tree, 43, 0) == 0); /* crash */
77 assert(item_tag_get(&tree, 0, 0) == 1);
79 verify_tag_consistency(&tree, 0);
81 item_kill_tree(&tree);
85 * Check that tags propagate correctly when contracting a tree.
87 static void contract_checks(void)
91 RADIX_TREE(tree, GFP_KERNEL);
93 tmp = 1<<RADIX_TREE_MAP_SHIFT;
94 item_insert(&tree, tmp);
95 item_insert(&tree, tmp+1);
96 item_tag_set(&tree, tmp, 0);
97 item_tag_set(&tree, tmp, 1);
98 item_tag_set(&tree, tmp+1, 0);
99 item_delete(&tree, tmp+1);
100 item_tag_clear(&tree, tmp, 1);
102 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1);
103 assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0);
105 assert(item_tag_get(&tree, tmp, 0) == 1);
106 assert(item_tag_get(&tree, tmp, 1) == 0);
108 verify_tag_consistency(&tree, 0);
109 item_kill_tree(&tree);
113 * Stupid tag thrasher
115 * Create a large linear array corresponding to the tree. Each element in
116 * the array is coherent with each node in the tree
125 #define THRASH_SIZE 1000 * 1000
129 static void gang_check(struct radix_tree_root *tree,
130 char *thrash_state, int tag)
132 struct item *items[BATCH];
134 unsigned long index = 0;
135 unsigned long last_index = 0;
137 while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items,
138 index, BATCH, tag))) {
141 for (i = 0; i < nr_found; i++) {
142 struct item *item = items[i];
144 while (last_index < item->index) {
145 assert(thrash_state[last_index] != NODE_TAGGED);
148 assert(thrash_state[last_index] == NODE_TAGGED);
151 index = items[nr_found - 1]->index + 1;
155 static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag)
161 int total_tagged = 0;
162 int total_present = 0;
164 for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N)
165 for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N)
166 for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N)
167 for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) {
174 int actual_total_tagged;
175 int actual_total_present;
177 for (i = 0; i < insert_chunk; i++) {
178 index = rand() % THRASH_SIZE;
179 if (thrash_state[index] != NODE_ABSENT)
181 item_check_absent(tree, index);
182 item_insert(tree, index);
183 assert(thrash_state[index] != NODE_PRESENT);
184 thrash_state[index] = NODE_PRESENT;
189 for (i = 0; i < delete_chunk; i++) {
190 index = rand() % THRASH_SIZE;
191 if (thrash_state[index] == NODE_ABSENT)
193 item_check_present(tree, index);
194 if (item_tag_get(tree, index, tag)) {
195 assert(thrash_state[index] == NODE_TAGGED);
198 assert(thrash_state[index] == NODE_PRESENT);
200 item_delete(tree, index);
201 assert(thrash_state[index] != NODE_ABSENT);
202 thrash_state[index] = NODE_ABSENT;
207 for (i = 0; i < tag_chunk; i++) {
208 index = rand() % THRASH_SIZE;
209 if (thrash_state[index] != NODE_PRESENT) {
210 if (item_lookup(tree, index))
211 assert(item_tag_get(tree, index, tag));
214 item_tag_set(tree, index, tag);
215 item_tag_set(tree, index, tag);
216 assert(thrash_state[index] != NODE_TAGGED);
217 thrash_state[index] = NODE_TAGGED;
222 for (i = 0; i < untag_chunk; i++) {
223 index = rand() % THRASH_SIZE;
224 if (thrash_state[index] != NODE_TAGGED)
226 item_check_present(tree, index);
227 assert(item_tag_get(tree, index, tag));
228 item_tag_clear(tree, index, tag);
229 item_tag_clear(tree, index, tag);
230 assert(thrash_state[index] != NODE_PRESENT);
231 thrash_state[index] = NODE_PRESENT;
236 actual_total_tagged = 0;
237 actual_total_present = 0;
238 for (index = 0; index < THRASH_SIZE; index++) {
239 switch (thrash_state[index]) {
241 item_check_absent(tree, index);
244 item_check_present(tree, index);
245 assert(!item_tag_get(tree, index, tag));
246 actual_total_present++;
249 item_check_present(tree, index);
250 assert(item_tag_get(tree, index, tag));
251 actual_total_present++;
252 actual_total_tagged++;
257 gang_check(tree, thrash_state, tag);
259 printf("%d(%d) %d(%d) %d(%d) %d(%d) / "
260 "%d(%d) present, %d(%d) tagged\n",
261 insert_chunk, nr_inserted,
262 delete_chunk, nr_deleted,
263 tag_chunk, nr_tagged,
264 untag_chunk, nr_untagged,
265 total_present, actual_total_present,
266 total_tagged, actual_total_tagged);
270 static void thrash_tags(void)
272 RADIX_TREE(tree, GFP_KERNEL);
275 thrash_state = malloc(THRASH_SIZE);
276 memset(thrash_state, 0, THRASH_SIZE);
278 do_thrash(&tree, thrash_state, 0);
280 verify_tag_consistency(&tree, 0);
281 item_kill_tree(&tree);
285 static void leak_check(void)
287 RADIX_TREE(tree, GFP_KERNEL);
289 item_insert(&tree, 1000000);
290 item_delete(&tree, 1000000);
291 item_kill_tree(&tree);
294 static void __leak_check(void)
296 RADIX_TREE(tree, GFP_KERNEL);
298 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
299 item_insert(&tree, 1000000);
300 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
301 item_delete(&tree, 1000000);
302 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
303 item_kill_tree(&tree);
304 printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated);
307 static void single_check(void)
309 struct item *items[BATCH];
310 RADIX_TREE(tree, GFP_KERNEL);
312 unsigned long first = 0;
314 item_insert(&tree, 0);
315 item_tag_set(&tree, 0, 0);
316 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0);
318 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0);
320 verify_tag_consistency(&tree, 0);
321 verify_tag_consistency(&tree, 1);
322 ret = radix_tree_range_tag_if_tagged(&tree, &first, 10, 10, 0, 1);
324 ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1);
326 item_kill_tree(&tree);
334 printf("after extend_checks: %d allocated\n", nr_allocated);
337 printf("after leak_check: %d allocated\n", nr_allocated);
339 printf("after simple_checks: %d allocated\n", nr_allocated);
341 printf("after thrash_tags: %d allocated\n", nr_allocated);