4 #include "kerncompat.h"
5 #include "radix-tree.h"
8 #include "print-tree.h"
12 static int setup_key(struct radix_tree_root *root, struct key *key, int exists)
21 ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
26 } else if (ret != 0 && num == res[0]) {
28 if (ret > 1 && num == res[1]) {
37 static int ins_one(struct ctree_root *root, struct radix_tree_root *radix)
39 struct ctree_path path;
45 ret = setup_key(radix, &key, 0);
46 sprintf(buf, "str-%Lu\n", key.objectid);
47 ret = insert_item(root, &key, buf, strlen(buf));
50 oid = (unsigned long)key.objectid;
51 radix_tree_preload(GFP_KERNEL);
52 ret = radix_tree_insert(radix, oid, (void *)oid);
53 radix_tree_preload_end();
58 printf("failed to insert %Lu\n", key.objectid);
62 static int run_commit(struct ctree_root *root, struct radix_tree_root *radix)
64 return commit_transaction(root);
67 static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix)
69 struct ctree_path path;
74 ret = setup_key(radix, &key, 1);
77 sprintf(buf, "str-%Lu\n", key.objectid);
78 ret = insert_item(root, &key, buf, strlen(buf));
80 printf("insert on %Lu gave us %d\n", key.objectid, ret);
86 static int del_one(struct ctree_root *root, struct radix_tree_root *radix)
88 struct ctree_path path;
93 ret = setup_key(radix, &key, 1);
96 ret = search_slot(root, &key, &path, -1);
99 ret = del_item(root, &path);
100 release_path(root, &path);
103 ptr = radix_tree_delete(radix, key.objectid);
108 printf("failed to delete %Lu\n", key.objectid);
112 static int lookup_item(struct ctree_root *root, struct radix_tree_root *radix)
114 struct ctree_path path;
118 ret = setup_key(radix, &key, 1);
121 ret = search_slot(root, &key, &path, 0);
122 release_path(root, &path);
127 printf("unable to find key %Lu\n", key.objectid);
131 static int lookup_enoent(struct ctree_root *root, struct radix_tree_root *radix)
133 struct ctree_path path;
137 ret = setup_key(radix, &key, 0);
140 ret = search_slot(root, &key, &path, 0);
141 release_path(root, &path);
146 printf("able to find key that should not exist %Lu\n", key.objectid);
150 static int empty_tree(struct ctree_root *root, struct radix_tree_root *radix,
153 struct ctree_path path;
155 unsigned long found = 0;
163 key.objectid = (unsigned long)-1;
166 ret = search_slot(root, &key, &path, -1);
168 release_path(root, &path);
172 if (path.slots[0] == 0) {
173 release_path(root, &path);
178 slot = path.slots[0];
179 found = path.nodes[0]->leaf.items[slot].key.objectid;
180 ret = del_item(root, &path);
184 "failed to remove %lu from tree\n",
188 release_path(root, &path);
189 ptr = radix_tree_delete(radix, found);
197 fprintf(stderr, "failed to delete from the radix %lu\n", found);
201 static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix,
207 for (i = 0; i < count; i++) {
208 ret = ins_one(root, radix);
210 printf("fill failed\n");
221 static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix)
224 int nr = rand() % 20000;
225 static int run_nr = 0;
227 /* do the bulk op much less frequently */
230 ret = empty_tree(root, radix, nr);
233 ret = fill_tree(root, radix, nr);
240 int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) =
241 { ins_one, insert_dup, del_one, lookup_item,
242 lookup_enoent, bulk_op, run_commit };
244 static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix)
246 struct ctree_path path;
255 key.objectid = (unsigned long)-1;
258 ret = search_slot(root, &key, &path, 0);
260 release_path(root, &path);
263 slot = path.slots[0];
266 release_path(root, &path);
271 for (i = slot; i >= 0; i--) {
272 found = path.nodes[0]->leaf.items[i].key.objectid;
273 radix_tree_preload(GFP_KERNEL);
274 ret = radix_tree_insert(radix, found, (void *)found);
277 "failed to insert %lu into radix\n",
282 radix_tree_preload_end();
284 release_path(root, &path);
285 key.objectid = found - 1;
286 if (key.objectid > found)
291 void sigstopper(int ignored)
294 fprintf(stderr, "caught exit signal, stopping\n");
297 int print_usage(void)
299 printf("usage: tester [-ih] [-c count] [-f count]\n");
300 printf("\t -c count -- iteration count after filling\n");
301 printf("\t -f count -- run this many random inserts before starting\n");
302 printf("\t -i -- only do initial fill\n");
303 printf("\t -h -- this help text\n");
306 int main(int ac, char **av)
308 RADIX_TREE(radix, GFP_KERNEL);
309 struct ctree_super_block super;
310 struct ctree_root *root;
315 int iterations = 20000;
316 int init_fill_count = 800000;
318 int initial_only = 0;
320 root = open_ctree("dbfile", &super);
321 fill_radix(root, &radix);
323 signal(SIGTERM, sigstopper);
324 signal(SIGINT, sigstopper);
326 for (i = 1 ; i < ac ; i++) {
327 if (strcmp(av[i], "-i") == 0) {
329 } else if (strcmp(av[i], "-c") == 0) {
330 iterations = atoi(av[i+1]);
332 } else if (strcmp(av[i], "-f") == 0) {
333 init_fill_count = atoi(av[i+1]);
339 printf("initial fill\n");
340 ret = fill_tree(root, &radix, init_fill_count);
341 printf("starting run\n");
346 if (initial_only == 1) {
349 for (i = 0; i < iterations; i++) {
350 op = rand() % ARRAY_SIZE(ops);
351 count = rand() % 128;
356 if (i && i % 5000 == 0) {
357 printf("open & close, root level %d nritems %d\n",
358 node_level(root->node->node.header.flags),
359 root->node->node.header.nritems);
360 write_ctree_super(root, &super);
362 root = open_ctree("dbfile", &super);
365 ret = ops[op](root, &radix);
367 fprintf(stderr, "op %d failed %d:%d\n",
369 print_tree(root, root->node);
370 fprintf(stderr, "op %d failed %d:%d\n",
375 if (ops[op] == bulk_op || ops[op] == run_commit)
377 if (keep_running == 0) {
384 write_ctree_super(root, &super);