4 #include "kerncompat.h"
5 #include "radix-tree.h"
8 #include "print-tree.h"
11 struct ctree_super_block super;
13 static int setup_key(struct radix_tree_root *root, struct key *key, int exists)
22 ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
27 } else if (ret != 0 && num == res[0]) {
29 if (ret > 1 && num == res[1]) {
38 static int ins_one(struct ctree_root *root, struct radix_tree_root *radix)
40 struct ctree_path path;
46 ret = setup_key(radix, &key, 0);
47 sprintf(buf, "str-%Lu\n", key.objectid);
48 ret = insert_item(root, &key, buf, strlen(buf));
51 oid = (unsigned long)key.objectid;
52 radix_tree_preload(GFP_KERNEL);
53 ret = radix_tree_insert(radix, oid, (void *)oid);
54 radix_tree_preload_end();
59 printf("failed to insert %Lu\n", key.objectid);
63 static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix)
65 struct ctree_path path;
70 ret = setup_key(radix, &key, 1);
73 sprintf(buf, "str-%Lu\n", key.objectid);
74 ret = insert_item(root, &key, buf, strlen(buf));
76 printf("insert on %Lu gave us %d\n", key.objectid, ret);
82 static int del_one(struct ctree_root *root, struct radix_tree_root *radix)
84 struct ctree_path path;
89 ret = setup_key(radix, &key, 1);
92 ret = search_slot(root, &key, &path, -1, 1);
95 ret = del_item(root, &path);
96 release_path(root, &path);
99 ptr = radix_tree_delete(radix, key.objectid);
104 printf("failed to delete %Lu\n", key.objectid);
108 static int lookup_item(struct ctree_root *root, struct radix_tree_root *radix)
110 struct ctree_path path;
114 ret = setup_key(radix, &key, 1);
117 ret = search_slot(root, &key, &path, 0, 1);
118 release_path(root, &path);
123 printf("unable to find key %Lu\n", key.objectid);
127 static int lookup_enoent(struct ctree_root *root, struct radix_tree_root *radix)
129 struct ctree_path path;
133 ret = setup_key(radix, &key, 0);
136 ret = search_slot(root, &key, &path, 0, 0);
137 release_path(root, &path);
142 printf("able to find key that should not exist %Lu\n", key.objectid);
146 static int empty_tree(struct ctree_root *root, struct radix_tree_root *radix,
149 struct ctree_path path;
151 unsigned long found = 0;
159 key.objectid = (unsigned long)-1;
162 ret = search_slot(root, &key, &path, -1, 1);
164 release_path(root, &path);
168 if (path.slots[0] == 0) {
169 release_path(root, &path);
174 slot = path.slots[0];
175 found = path.nodes[0]->leaf.items[slot].key.objectid;
176 ret = del_item(root, &path);
180 "failed to remove %lu from tree\n",
184 release_path(root, &path);
185 ptr = radix_tree_delete(radix, found);
193 fprintf(stderr, "failed to delete from the radix %lu\n", found);
197 static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix,
202 for (i = 0; i < count; i++) {
203 ret = ins_one(root, radix);
205 fprintf(stderr, "fill failed\n");
209 ret = commit_transaction(root, &super);
211 fprintf(stderr, "fill commit failed\n");
215 if (i && i % 10000 == 0) {
216 printf("bigfill %d\n", i);
225 static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix)
228 int nr = rand() % 5000;
229 static int run_nr = 0;
231 /* do the bulk op much less frequently */
234 ret = empty_tree(root, radix, nr);
237 ret = fill_tree(root, radix, nr);
244 int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) =
245 { ins_one, insert_dup, del_one, lookup_item,
246 lookup_enoent, bulk_op };
248 static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix)
250 struct ctree_path path;
259 key.objectid = (unsigned long)-1;
262 ret = search_slot(root, &key, &path, 0, 0);
264 release_path(root, &path);
267 slot = path.slots[0];
270 release_path(root, &path);
275 for (i = slot; i >= 0; i--) {
276 found = path.nodes[0]->leaf.items[i].key.objectid;
277 radix_tree_preload(GFP_KERNEL);
278 ret = radix_tree_insert(radix, found, (void *)found);
281 "failed to insert %lu into radix\n",
286 radix_tree_preload_end();
288 release_path(root, &path);
289 key.objectid = found - 1;
290 if (key.objectid > found)
295 void sigstopper(int ignored)
298 fprintf(stderr, "caught exit signal, stopping\n");
301 int print_usage(void)
303 printf("usage: tester [-ih] [-c count] [-f count]\n");
304 printf("\t -c count -- iteration count after filling\n");
305 printf("\t -f count -- run this many random inserts before starting\n");
306 printf("\t -i -- only do initial fill\n");
307 printf("\t -h -- this help text\n");
310 int main(int ac, char **av)
312 RADIX_TREE(radix, GFP_KERNEL);
313 struct ctree_root *root;
318 int iterations = 20000;
319 int init_fill_count = 800000;
321 int initial_only = 0;
323 root = open_ctree("dbfile", &super);
324 fill_radix(root, &radix);
326 signal(SIGTERM, sigstopper);
327 signal(SIGINT, sigstopper);
329 for (i = 1 ; i < ac ; i++) {
330 if (strcmp(av[i], "-i") == 0) {
332 } else if (strcmp(av[i], "-c") == 0) {
333 iterations = atoi(av[i+1]);
335 } else if (strcmp(av[i], "-f") == 0) {
336 init_fill_count = atoi(av[i+1]);
342 printf("initial fill\n");
343 ret = fill_tree(root, &radix, init_fill_count);
344 printf("starting run\n");
349 if (initial_only == 1) {
352 for (i = 0; i < iterations; i++) {
353 op = rand() % ARRAY_SIZE(ops);
354 count = rand() % 128;
359 if (i && i % 5000 == 0) {
360 printf("open & close, root level %d nritems %d\n",
361 node_level(root->node->node.header.flags),
362 root->node->node.header.nritems);
363 close_ctree(root, &super);
364 root = open_ctree("dbfile", &super);
367 ret = ops[op](root, &radix);
369 fprintf(stderr, "op %d failed %d:%d\n",
371 print_tree(root, root->node);
372 fprintf(stderr, "op %d failed %d:%d\n",
377 if (ops[op] == bulk_op)
379 if (keep_running == 0) {
386 close_ctree(root, &super);