]>
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); | |
070c5ac2 MW |
26 | ret = radix_tree_range_tag_if_tagged(tree, &first, ~0UL, 10, tag, !tag); |
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); | |
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); | |
55 | } | |
56 | ||
57 | /* | |
58 | * Check that tags propagate correctly when extending a tree. | |
59 | */ | |
60 | static void extend_checks(void) | |
61 | { | |
62 | RADIX_TREE(tree, GFP_KERNEL); | |
63 | ||
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); | |
70 | ||
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); | |
78 | ||
79 | verify_tag_consistency(&tree, 0); | |
80 | ||
81 | item_kill_tree(&tree); | |
82 | } | |
83 | ||
84 | /* | |
85 | * Check that tags propagate correctly when contracting a tree. | |
86 | */ | |
87 | static void contract_checks(void) | |
88 | { | |
89 | struct item *item; | |
90 | int tmp; | |
91 | RADIX_TREE(tree, GFP_KERNEL); | |
92 | ||
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); | |
101 | ||
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); | |
104 | ||
105 | assert(item_tag_get(&tree, tmp, 0) == 1); | |
106 | assert(item_tag_get(&tree, tmp, 1) == 0); | |
107 | ||
108 | verify_tag_consistency(&tree, 0); | |
109 | item_kill_tree(&tree); | |
110 | } | |
111 | ||
112 | /* | |
113 | * Stupid tag thrasher | |
114 | * | |
115 | * Create a large linear array corresponding to the tree. Each element in | |
116 | * the array is coherent with each node in the tree | |
117 | */ | |
118 | ||
119 | enum { | |
120 | NODE_ABSENT = 0, | |
121 | NODE_PRESENT = 1, | |
122 | NODE_TAGGED = 2, | |
123 | }; | |
124 | ||
b301aac5 | 125 | #define THRASH_SIZE (1000 * 1000) |
1366c37e MW |
126 | #define N 127 |
127 | #define BATCH 33 | |
128 | ||
129 | static void gang_check(struct radix_tree_root *tree, | |
130 | char *thrash_state, int tag) | |
131 | { | |
132 | struct item *items[BATCH]; | |
133 | int nr_found; | |
134 | unsigned long index = 0; | |
135 | unsigned long last_index = 0; | |
136 | ||
137 | while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items, | |
138 | index, BATCH, tag))) { | |
139 | int i; | |
140 | ||
141 | for (i = 0; i < nr_found; i++) { | |
142 | struct item *item = items[i]; | |
143 | ||
144 | while (last_index < item->index) { | |
145 | assert(thrash_state[last_index] != NODE_TAGGED); | |
146 | last_index++; | |
147 | } | |
148 | assert(thrash_state[last_index] == NODE_TAGGED); | |
149 | last_index++; | |
150 | } | |
151 | index = items[nr_found - 1]->index + 1; | |
152 | } | |
153 | } | |
154 | ||
155 | static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag) | |
156 | { | |
157 | int insert_chunk; | |
158 | int delete_chunk; | |
159 | int tag_chunk; | |
160 | int untag_chunk; | |
161 | int total_tagged = 0; | |
162 | int total_present = 0; | |
163 | ||
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) { | |
168 | int i; | |
169 | unsigned long index; | |
170 | int nr_inserted = 0; | |
171 | int nr_deleted = 0; | |
172 | int nr_tagged = 0; | |
173 | int nr_untagged = 0; | |
174 | int actual_total_tagged; | |
175 | int actual_total_present; | |
176 | ||
177 | for (i = 0; i < insert_chunk; i++) { | |
178 | index = rand() % THRASH_SIZE; | |
179 | if (thrash_state[index] != NODE_ABSENT) | |
180 | continue; | |
181 | item_check_absent(tree, index); | |
182 | item_insert(tree, index); | |
183 | assert(thrash_state[index] != NODE_PRESENT); | |
184 | thrash_state[index] = NODE_PRESENT; | |
185 | nr_inserted++; | |
186 | total_present++; | |
187 | } | |
188 | ||
189 | for (i = 0; i < delete_chunk; i++) { | |
190 | index = rand() % THRASH_SIZE; | |
191 | if (thrash_state[index] == NODE_ABSENT) | |
192 | continue; | |
193 | item_check_present(tree, index); | |
194 | if (item_tag_get(tree, index, tag)) { | |
195 | assert(thrash_state[index] == NODE_TAGGED); | |
196 | total_tagged--; | |
197 | } else { | |
198 | assert(thrash_state[index] == NODE_PRESENT); | |
199 | } | |
200 | item_delete(tree, index); | |
201 | assert(thrash_state[index] != NODE_ABSENT); | |
202 | thrash_state[index] = NODE_ABSENT; | |
203 | nr_deleted++; | |
204 | total_present--; | |
205 | } | |
206 | ||
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)); | |
212 | continue; | |
213 | } | |
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; | |
218 | nr_tagged++; | |
219 | total_tagged++; | |
220 | } | |
221 | ||
222 | for (i = 0; i < untag_chunk; i++) { | |
223 | index = rand() % THRASH_SIZE; | |
224 | if (thrash_state[index] != NODE_TAGGED) | |
225 | continue; | |
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; | |
232 | nr_untagged++; | |
233 | total_tagged--; | |
234 | } | |
235 | ||
236 | actual_total_tagged = 0; | |
237 | actual_total_present = 0; | |
238 | for (index = 0; index < THRASH_SIZE; index++) { | |
239 | switch (thrash_state[index]) { | |
240 | case NODE_ABSENT: | |
241 | item_check_absent(tree, index); | |
242 | break; | |
243 | case NODE_PRESENT: | |
244 | item_check_present(tree, index); | |
245 | assert(!item_tag_get(tree, index, tag)); | |
246 | actual_total_present++; | |
247 | break; | |
248 | case NODE_TAGGED: | |
249 | item_check_present(tree, index); | |
250 | assert(item_tag_get(tree, index, tag)); | |
251 | actual_total_present++; | |
252 | actual_total_tagged++; | |
253 | break; | |
254 | } | |
255 | } | |
256 | ||
257 | gang_check(tree, thrash_state, tag); | |
258 | ||
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); | |
267 | } | |
268 | } | |
269 | ||
270 | static void thrash_tags(void) | |
271 | { | |
272 | RADIX_TREE(tree, GFP_KERNEL); | |
273 | char *thrash_state; | |
274 | ||
275 | thrash_state = malloc(THRASH_SIZE); | |
276 | memset(thrash_state, 0, THRASH_SIZE); | |
277 | ||
278 | do_thrash(&tree, thrash_state, 0); | |
279 | ||
280 | verify_tag_consistency(&tree, 0); | |
281 | item_kill_tree(&tree); | |
282 | free(thrash_state); | |
283 | } | |
284 | ||
285 | static void leak_check(void) | |
286 | { | |
287 | RADIX_TREE(tree, GFP_KERNEL); | |
288 | ||
289 | item_insert(&tree, 1000000); | |
290 | item_delete(&tree, 1000000); | |
291 | item_kill_tree(&tree); | |
292 | } | |
293 | ||
294 | static void __leak_check(void) | |
295 | { | |
296 | RADIX_TREE(tree, GFP_KERNEL); | |
297 | ||
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); | |
305 | } | |
306 | ||
307 | static void single_check(void) | |
308 | { | |
309 | struct item *items[BATCH]; | |
310 | RADIX_TREE(tree, GFP_KERNEL); | |
311 | int ret; | |
070c5ac2 | 312 | unsigned long first = 0; |
1366c37e MW |
313 | |
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); | |
317 | assert(ret == 1); | |
318 | ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0); | |
319 | assert(ret == 0); | |
320 | verify_tag_consistency(&tree, 0); | |
321 | verify_tag_consistency(&tree, 1); | |
070c5ac2 MW |
322 | ret = radix_tree_range_tag_if_tagged(&tree, &first, 10, 10, 0, 1); |
323 | assert(ret == 1); | |
324 | ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1); | |
325 | assert(ret == 1); | |
1366c37e MW |
326 | item_kill_tree(&tree); |
327 | } | |
328 | ||
329 | void tag_check(void) | |
330 | { | |
331 | single_check(); | |
332 | extend_checks(); | |
333 | contract_checks(); | |
334 | printf("after extend_checks: %d allocated\n", nr_allocated); | |
335 | __leak_check(); | |
336 | leak_check(); | |
337 | printf("after leak_check: %d allocated\n", nr_allocated); | |
338 | simple_checks(); | |
339 | printf("after simple_checks: %d allocated\n", nr_allocated); | |
340 | thrash_tags(); | |
341 | printf("after thrash_tags: %d allocated\n", nr_allocated); | |
342 | } |