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, 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, 1);
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, 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, 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
,
206 for (i
= 0; i
< count
; i
++) {
207 ret
= ins_one(root
, radix
);
209 fprintf(stderr
, "fill failed\n");
213 ret
= commit_transaction(root
);
215 fprintf(stderr
, "fill commit failed\n");
219 if (i
&& i
% 10000 == 0) {
220 printf("bigfill %d\n", i
);
229 static int bulk_op(struct ctree_root
*root
, struct radix_tree_root
*radix
)
232 int nr
= rand() % 20000;
233 static int run_nr
= 0;
235 /* do the bulk op much less frequently */
238 ret
= empty_tree(root
, radix
, nr
);
241 ret
= fill_tree(root
, radix
, nr
);
248 int (*ops
[])(struct ctree_root
*root
, struct radix_tree_root
*radix
) =
249 { ins_one
, insert_dup
, del_one
, lookup_item
,
250 lookup_enoent
, bulk_op
, run_commit
};
252 static int fill_radix(struct ctree_root
*root
, struct radix_tree_root
*radix
)
254 struct ctree_path path
;
263 key
.objectid
= (unsigned long)-1;
266 ret
= search_slot(root
, &key
, &path
, 0, 0);
268 release_path(root
, &path
);
271 slot
= path
.slots
[0];
274 release_path(root
, &path
);
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
);
285 "failed to insert %lu into radix\n",
290 radix_tree_preload_end();
292 release_path(root
, &path
);
293 key
.objectid
= found
- 1;
294 if (key
.objectid
> found
)
299 void sigstopper(int ignored
)
302 fprintf(stderr
, "caught exit signal, stopping\n");
305 int print_usage(void)
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");
314 int main(int ac
, char **av
)
316 RADIX_TREE(radix
, GFP_KERNEL
);
317 struct ctree_super_block super
;
318 struct ctree_root
*root
;
323 int iterations
= 20000;
324 int init_fill_count
= 800000;
326 int initial_only
= 0;
328 root
= open_ctree("dbfile", &super
);
329 fill_radix(root
, &radix
);
331 signal(SIGTERM
, sigstopper
);
332 signal(SIGINT
, sigstopper
);
334 for (i
= 1 ; i
< ac
; i
++) {
335 if (strcmp(av
[i
], "-i") == 0) {
337 } else if (strcmp(av
[i
], "-c") == 0) {
338 iterations
= atoi(av
[i
+1]);
340 } else if (strcmp(av
[i
], "-f") == 0) {
341 init_fill_count
= atoi(av
[i
+1]);
347 printf("initial fill\n");
348 ret
= fill_tree(root
, &radix
, init_fill_count
);
349 printf("starting run\n");
354 if (initial_only
== 1) {
357 for (i
= 0; i
< iterations
; i
++) {
358 op
= rand() % ARRAY_SIZE(ops
);
359 count
= rand() % 128;
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
);
370 root
= open_ctree("dbfile", &super
);
373 ret
= ops
[op
](root
, &radix
);
375 fprintf(stderr
, "op %d failed %d:%d\n",
377 print_tree(root
, root
->node
);
378 fprintf(stderr
, "op %d failed %d:%d\n",
383 if (ops
[op
] == bulk_op
|| ops
[op
] == run_commit
)
385 if (keep_running
== 0) {
392 write_ctree_super(root
, &super
);