]>
Commit | Line | Data |
---|---|---|
1366c37e MW |
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 | ||
12 | static void | |
13 | __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag) | |
14 | { | |
070c5ac2 | 15 | unsigned long first = 0; |
1366c37e MW |
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); | |
268f42de | 26 | ret = tag_tagged_items(tree, NULL, first, ~0UL, 10, tag, !tag); |
070c5ac2 MW |
27 | assert(ret == 1); |
28 | ret = item_tag_get(tree, index, !tag); | |
29 | assert(ret != 0); | |
1366c37e MW |
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 | ||
41 | void 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); | |
73bc029b | 52 | printv(2, "before item_kill_tree: %d allocated\n", nr_allocated); |
1366c37e | 53 | item_kill_tree(&tree); |
af1c5cca | 54 | rcu_barrier(); |
73bc029b | 55 | printv(2, "after item_kill_tree: %d allocated\n", nr_allocated); |
1366c37e MW |
56 | } |
57 | ||
58 | /* | |
59 | * Check that tags propagate correctly when extending a tree. | |
60 | */ | |
61 | static 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); /* crash */ | |
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 | * Check that tags propagate correctly when contracting a tree. | |
87 | */ | |
88 | static 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 | * Stupid tag thrasher | |
115 | * | |
116 | * Create a large linear array corresponding to the tree. Each element in | |
117 | * the array is coherent with each node in the tree | |
118 | */ | |
119 | ||
120 | enum { | |
121 | NODE_ABSENT = 0, | |
122 | NODE_PRESENT = 1, | |
123 | NODE_TAGGED = 2, | |
124 | }; | |
125 | ||
b301aac5 | 126 | #define THRASH_SIZE (1000 * 1000) |
1366c37e MW |
127 | #define N 127 |
128 | #define BATCH 33 | |
129 | ||
130 | static 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 | ||
156 | static 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 | ||
73bc029b | 260 | printv(2, "%d(%d) %d(%d) %d(%d) %d(%d) / " |
1366c37e MW |
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 | ||
271 | static 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 | ||
286 | static 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 | ||
295 | static void __leak_check(void) | |
296 | { | |
297 | RADIX_TREE(tree, GFP_KERNEL); | |
298 | ||
73bc029b | 299 | printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); |
1366c37e | 300 | item_insert(&tree, 1000000); |
73bc029b | 301 | printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); |
1366c37e | 302 | item_delete(&tree, 1000000); |
73bc029b | 303 | printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); |
1366c37e | 304 | item_kill_tree(&tree); |
73bc029b | 305 | printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); |
1366c37e MW |
306 | } |
307 | ||
308 | static void single_check(void) | |
309 | { | |
310 | struct item *items[BATCH]; | |
311 | RADIX_TREE(tree, GFP_KERNEL); | |
312 | int ret; | |
070c5ac2 | 313 | unsigned long first = 0; |
1366c37e MW |
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); | |
268f42de | 323 | ret = tag_tagged_items(&tree, NULL, first, 10, 10, 0, 1); |
070c5ac2 MW |
324 | assert(ret == 1); |
325 | ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1); | |
326 | assert(ret == 1); | |
092bc0b2 MW |
327 | item_tag_clear(&tree, 0, 0); |
328 | ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0); | |
329 | assert(ret == 0); | |
1366c37e MW |
330 | item_kill_tree(&tree); |
331 | } | |
332 | ||
c629a344 RS |
333 | void radix_tree_clear_tags_test(void) |
334 | { | |
335 | unsigned long index; | |
336 | struct radix_tree_node *node; | |
337 | struct radix_tree_iter iter; | |
338 | void **slot; | |
339 | ||
340 | RADIX_TREE(tree, GFP_KERNEL); | |
341 | ||
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); | |
347 | ||
348 | for (index = 0; index < 1000; index++) { | |
349 | item_insert(&tree, index); | |
350 | item_tag_set(&tree, index, 0); | |
351 | } | |
352 | ||
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); | |
356 | } | |
357 | ||
358 | item_kill_tree(&tree); | |
359 | } | |
360 | ||
1366c37e MW |
361 | void tag_check(void) |
362 | { | |
363 | single_check(); | |
364 | extend_checks(); | |
365 | contract_checks(); | |
af1c5cca | 366 | rcu_barrier(); |
73bc029b | 367 | printv(2, "after extend_checks: %d allocated\n", nr_allocated); |
1366c37e MW |
368 | __leak_check(); |
369 | leak_check(); | |
af1c5cca | 370 | rcu_barrier(); |
73bc029b | 371 | printv(2, "after leak_check: %d allocated\n", nr_allocated); |
1366c37e | 372 | simple_checks(); |
af1c5cca | 373 | rcu_barrier(); |
73bc029b | 374 | printv(2, "after simple_checks: %d allocated\n", nr_allocated); |
1366c37e | 375 | thrash_tags(); |
af1c5cca | 376 | rcu_barrier(); |
73bc029b | 377 | printv(2, "after thrash_tags: %d allocated\n", nr_allocated); |
c629a344 | 378 | radix_tree_clear_tags_test(); |
1366c37e | 379 | } |