Commit | Line | Data |
---|---|---|
fec577fb CM |
1 | #include <stdio.h> |
2 | #include <stdlib.h> | |
3 | #include <signal.h> | |
4 | #include "kerncompat.h" | |
5 | #include "radix-tree.h" | |
6 | #include "ctree.h" | |
7 | #include "disk-io.h" | |
8 | #include "print-tree.h" | |
9 | ||
10 | int keep_running = 1; | |
11 | ||
12 | static int setup_key(struct radix_tree_root *root, struct key *key, int exists) | |
13 | { | |
14 | int num = rand(); | |
15 | unsigned long res[2]; | |
16 | int ret; | |
17 | ||
18 | key->flags = 0; | |
19 | key->offset = 0; | |
20 | again: | |
21 | ret = radix_tree_gang_lookup(root, (void **)res, num, 2); | |
22 | if (exists) { | |
23 | if (ret == 0) | |
24 | return -1; | |
25 | num = res[0]; | |
26 | } else if (ret != 0 && num == res[0]) { | |
27 | num++; | |
28 | if (ret > 1 && num == res[1]) { | |
29 | num++; | |
30 | goto again; | |
31 | } | |
32 | } | |
33 | key->objectid = num; | |
34 | return 0; | |
35 | } | |
36 | ||
37 | static int ins_one(struct ctree_root *root, struct radix_tree_root *radix) | |
38 | { | |
39 | struct ctree_path path; | |
40 | struct key key; | |
41 | int ret; | |
42 | char buf[128]; | |
41903fe6 | 43 | unsigned long oid; |
fec577fb CM |
44 | init_path(&path); |
45 | ret = setup_key(radix, &key, 0); | |
7cf75962 | 46 | sprintf(buf, "str-%Lu\n", key.objectid); |
fec577fb CM |
47 | ret = insert_item(root, &key, buf, strlen(buf)); |
48 | if (ret) | |
49 | goto error; | |
41903fe6 | 50 | oid = (unsigned long)key.objectid; |
fec577fb | 51 | radix_tree_preload(GFP_KERNEL); |
41903fe6 | 52 | ret = radix_tree_insert(radix, oid, (void *)oid); |
fec577fb CM |
53 | radix_tree_preload_end(); |
54 | if (ret) | |
55 | goto error; | |
56 | return ret; | |
57 | error: | |
7cf75962 | 58 | printf("failed to insert %Lu\n", key.objectid); |
fec577fb CM |
59 | return -1; |
60 | } | |
61 | ||
f0930a37 CM |
62 | static int run_commit(struct ctree_root *root, struct radix_tree_root *radix) |
63 | { | |
64 | return commit_transaction(root); | |
65 | } | |
66 | ||
fec577fb CM |
67 | static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix) |
68 | { | |
69 | struct ctree_path path; | |
70 | struct key key; | |
71 | int ret; | |
72 | char buf[128]; | |
73 | init_path(&path); | |
74 | ret = setup_key(radix, &key, 1); | |
75 | if (ret < 0) | |
76 | return 0; | |
7cf75962 | 77 | sprintf(buf, "str-%Lu\n", key.objectid); |
fec577fb CM |
78 | ret = insert_item(root, &key, buf, strlen(buf)); |
79 | if (ret != -EEXIST) { | |
7cf75962 | 80 | printf("insert on %Lu gave us %d\n", key.objectid, ret); |
fec577fb CM |
81 | return 1; |
82 | } | |
83 | return 0; | |
84 | } | |
85 | ||
86 | static int del_one(struct ctree_root *root, struct radix_tree_root *radix) | |
87 | { | |
88 | struct ctree_path path; | |
89 | struct key key; | |
90 | int ret; | |
91 | unsigned long *ptr; | |
92 | init_path(&path); | |
93 | ret = setup_key(radix, &key, 1); | |
94 | if (ret < 0) | |
95 | return 0; | |
02217ed2 | 96 | ret = search_slot(root, &key, &path, -1, 1); |
fec577fb CM |
97 | if (ret) |
98 | goto error; | |
99 | ret = del_item(root, &path); | |
100 | release_path(root, &path); | |
101 | if (ret != 0) | |
102 | goto error; | |
103 | ptr = radix_tree_delete(radix, key.objectid); | |
104 | if (!ptr) | |
105 | goto error; | |
106 | return 0; | |
107 | error: | |
7cf75962 | 108 | printf("failed to delete %Lu\n", key.objectid); |
fec577fb CM |
109 | return -1; |
110 | } | |
111 | ||
112 | static int lookup_item(struct ctree_root *root, struct radix_tree_root *radix) | |
113 | { | |
114 | struct ctree_path path; | |
115 | struct key key; | |
116 | int ret; | |
117 | init_path(&path); | |
118 | ret = setup_key(radix, &key, 1); | |
119 | if (ret < 0) | |
120 | return 0; | |
02217ed2 | 121 | ret = search_slot(root, &key, &path, 0, 1); |
fec577fb CM |
122 | release_path(root, &path); |
123 | if (ret) | |
124 | goto error; | |
125 | return 0; | |
126 | error: | |
7cf75962 | 127 | printf("unable to find key %Lu\n", key.objectid); |
fec577fb CM |
128 | return -1; |
129 | } | |
130 | ||
131 | static int lookup_enoent(struct ctree_root *root, struct radix_tree_root *radix) | |
132 | { | |
133 | struct ctree_path path; | |
134 | struct key key; | |
135 | int ret; | |
136 | init_path(&path); | |
137 | ret = setup_key(radix, &key, 0); | |
138 | if (ret < 0) | |
139 | return ret; | |
02217ed2 | 140 | ret = search_slot(root, &key, &path, 0, 0); |
fec577fb | 141 | release_path(root, &path); |
aa5d6bed | 142 | if (ret <= 0) |
fec577fb CM |
143 | goto error; |
144 | return 0; | |
145 | error: | |
7cf75962 | 146 | printf("able to find key that should not exist %Lu\n", key.objectid); |
fec577fb CM |
147 | return -1; |
148 | } | |
149 | ||
79f95c82 CM |
150 | static int empty_tree(struct ctree_root *root, struct radix_tree_root *radix, |
151 | int nr) | |
152 | { | |
153 | struct ctree_path path; | |
154 | struct key key; | |
155 | unsigned long found = 0; | |
156 | int ret; | |
157 | int slot; | |
158 | int *ptr; | |
159 | int count = 0; | |
160 | ||
161 | key.offset = 0; | |
162 | key.flags = 0; | |
163 | key.objectid = (unsigned long)-1; | |
164 | while(nr-- >= 0) { | |
165 | init_path(&path); | |
02217ed2 | 166 | ret = search_slot(root, &key, &path, -1, 1); |
79f95c82 CM |
167 | if (ret < 0) { |
168 | release_path(root, &path); | |
169 | return ret; | |
170 | } | |
171 | if (ret != 0) { | |
172 | if (path.slots[0] == 0) { | |
173 | release_path(root, &path); | |
174 | break; | |
175 | } | |
176 | path.slots[0] -= 1; | |
177 | } | |
178 | slot = path.slots[0]; | |
179 | found = path.nodes[0]->leaf.items[slot].key.objectid; | |
180 | ret = del_item(root, &path); | |
181 | count++; | |
182 | if (ret) { | |
183 | fprintf(stderr, | |
184 | "failed to remove %lu from tree\n", | |
185 | found); | |
186 | return -1; | |
187 | } | |
188 | release_path(root, &path); | |
189 | ptr = radix_tree_delete(radix, found); | |
190 | if (!ptr) | |
191 | goto error; | |
192 | if (!keep_running) | |
193 | break; | |
194 | } | |
195 | return 0; | |
196 | error: | |
197 | fprintf(stderr, "failed to delete from the radix %lu\n", found); | |
198 | return -1; | |
199 | } | |
200 | ||
201 | static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix, | |
202 | int count) | |
203 | { | |
204 | int i; | |
79f95c82 CM |
205 | int ret = 0; |
206 | for (i = 0; i < count; i++) { | |
207 | ret = ins_one(root, radix); | |
208 | if (ret) { | |
77ce6846 | 209 | fprintf(stderr, "fill failed\n"); |
79f95c82 CM |
210 | goto out; |
211 | } | |
77ce6846 CM |
212 | if (i % 1000 == 0) { |
213 | ret = commit_transaction(root); | |
214 | if (ret) { | |
215 | fprintf(stderr, "fill commit failed\n"); | |
216 | return ret; | |
217 | } | |
218 | } | |
02217ed2 | 219 | if (i && i % 10000 == 0) { |
77ce6846 CM |
220 | printf("bigfill %d\n", i); |
221 | } | |
79f95c82 CM |
222 | if (!keep_running) |
223 | break; | |
224 | } | |
225 | out: | |
226 | return ret; | |
227 | } | |
228 | ||
229 | static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix) | |
230 | { | |
231 | int ret; | |
232 | int nr = rand() % 20000; | |
233 | static int run_nr = 0; | |
234 | ||
235 | /* do the bulk op much less frequently */ | |
236 | if (run_nr++ % 100) | |
237 | return 0; | |
238 | ret = empty_tree(root, radix, nr); | |
239 | if (ret) | |
240 | return ret; | |
241 | ret = fill_tree(root, radix, nr); | |
242 | if (ret) | |
243 | return ret; | |
244 | return 0; | |
245 | } | |
246 | ||
247 | ||
fec577fb | 248 | int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) = |
f0930a37 CM |
249 | { ins_one, insert_dup, del_one, lookup_item, |
250 | lookup_enoent, bulk_op, run_commit }; | |
fec577fb CM |
251 | |
252 | static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix) | |
253 | { | |
254 | struct ctree_path path; | |
255 | struct key key; | |
7cf75962 | 256 | unsigned long found; |
fec577fb CM |
257 | int ret; |
258 | int slot; | |
259 | int i; | |
aa5d6bed | 260 | |
fec577fb CM |
261 | key.offset = 0; |
262 | key.flags = 0; | |
263 | key.objectid = (unsigned long)-1; | |
264 | while(1) { | |
265 | init_path(&path); | |
02217ed2 | 266 | ret = search_slot(root, &key, &path, 0, 0); |
aa5d6bed CM |
267 | if (ret < 0) { |
268 | release_path(root, &path); | |
269 | return ret; | |
270 | } | |
fec577fb CM |
271 | slot = path.slots[0]; |
272 | if (ret != 0) { | |
273 | if (slot == 0) { | |
274 | release_path(root, &path); | |
275 | break; | |
276 | } | |
277 | slot -= 1; | |
278 | } | |
279 | for (i = slot; i >= 0; i--) { | |
280 | found = path.nodes[0]->leaf.items[i].key.objectid; | |
281 | radix_tree_preload(GFP_KERNEL); | |
282 | ret = radix_tree_insert(radix, found, (void *)found); | |
283 | if (ret) { | |
284 | fprintf(stderr, | |
285 | "failed to insert %lu into radix\n", | |
286 | found); | |
287 | exit(1); | |
288 | } | |
289 | ||
290 | radix_tree_preload_end(); | |
291 | } | |
292 | release_path(root, &path); | |
293 | key.objectid = found - 1; | |
294 | if (key.objectid > found) | |
295 | break; | |
296 | } | |
297 | return 0; | |
298 | } | |
fec577fb CM |
299 | void sigstopper(int ignored) |
300 | { | |
301 | keep_running = 0; | |
302 | fprintf(stderr, "caught exit signal, stopping\n"); | |
303 | } | |
304 | ||
305 | int print_usage(void) | |
306 | { | |
307 | printf("usage: tester [-ih] [-c count] [-f count]\n"); | |
308 | printf("\t -c count -- iteration count after filling\n"); | |
309 | printf("\t -f count -- run this many random inserts before starting\n"); | |
310 | printf("\t -i -- only do initial fill\n"); | |
311 | printf("\t -h -- this help text\n"); | |
312 | exit(1); | |
313 | } | |
314 | int main(int ac, char **av) | |
315 | { | |
316 | RADIX_TREE(radix, GFP_KERNEL); | |
317 | struct ctree_super_block super; | |
318 | struct ctree_root *root; | |
319 | int i; | |
320 | int ret; | |
321 | int count; | |
322 | int op; | |
323 | int iterations = 20000; | |
324 | int init_fill_count = 800000; | |
325 | int err = 0; | |
326 | int initial_only = 0; | |
327 | radix_tree_init(); | |
328 | root = open_ctree("dbfile", &super); | |
329 | fill_radix(root, &radix); | |
330 | ||
331 | signal(SIGTERM, sigstopper); | |
332 | signal(SIGINT, sigstopper); | |
333 | ||
334 | for (i = 1 ; i < ac ; i++) { | |
335 | if (strcmp(av[i], "-i") == 0) { | |
336 | initial_only = 1; | |
337 | } else if (strcmp(av[i], "-c") == 0) { | |
338 | iterations = atoi(av[i+1]); | |
339 | i++; | |
340 | } else if (strcmp(av[i], "-f") == 0) { | |
341 | init_fill_count = atoi(av[i+1]); | |
342 | i++; | |
343 | } else { | |
344 | print_usage(); | |
345 | } | |
346 | } | |
79f95c82 CM |
347 | printf("initial fill\n"); |
348 | ret = fill_tree(root, &radix, init_fill_count); | |
349 | printf("starting run\n"); | |
350 | if (ret) { | |
351 | err = ret; | |
352 | goto out; | |
fec577fb CM |
353 | } |
354 | if (initial_only == 1) { | |
355 | goto out; | |
356 | } | |
357 | for (i = 0; i < iterations; i++) { | |
358 | op = rand() % ARRAY_SIZE(ops); | |
359 | count = rand() % 128; | |
360 | if (i % 2000 == 0) { | |
361 | printf("%d\n", i); | |
362 | fflush(stdout); | |
363 | } | |
364 | if (i && i % 5000 == 0) { | |
365 | printf("open & close, root level %d nritems %d\n", | |
366 | node_level(root->node->node.header.flags), | |
367 | root->node->node.header.nritems); | |
368 | write_ctree_super(root, &super); | |
369 | close_ctree(root); | |
370 | root = open_ctree("dbfile", &super); | |
371 | } | |
372 | while(count--) { | |
373 | ret = ops[op](root, &radix); | |
374 | if (ret) { | |
375 | fprintf(stderr, "op %d failed %d:%d\n", | |
376 | op, i, iterations); | |
377 | print_tree(root, root->node); | |
378 | fprintf(stderr, "op %d failed %d:%d\n", | |
379 | op, i, iterations); | |
380 | err = ret; | |
381 | goto out; | |
382 | } | |
f0930a37 | 383 | if (ops[op] == bulk_op || ops[op] == run_commit) |
79f95c82 | 384 | break; |
fec577fb CM |
385 | if (keep_running == 0) { |
386 | err = 0; | |
387 | goto out; | |
388 | } | |
389 | } | |
390 | } | |
391 | out: | |
392 | write_ctree_super(root, &super); | |
393 | close_ctree(root); | |
394 | return err; | |
395 | } | |
396 |