[deliverable/linux.git] / fs / btrfs / random-test.c

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include "kerncompat.h"
#include "radix-tree.h"
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"

int keep_running = 1;

static int setup_key(struct radix_tree_root *root, struct key *key, int exists)
{
	int num = rand();
	unsigned long res[2];
	int ret;

	key->flags = 0;
	key->offset = 0;
again:
	ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
	if (exists) {
		if (ret == 0)
			return -1;
		num = res[0];
	} else if (ret != 0 && num == res[0]) {
		num++;
		if (ret > 1 && num == res[1]) {
			num++;
			goto again;
		}
	}
	key->objectid = num;
	return 0;
}

static int ins_one(struct ctree_root *root, struct radix_tree_root *radix)
{
	struct ctree_path path;
	struct key key;
	int ret;
	char buf[128];
	unsigned long oid;
	init_path(&path);
	ret = setup_key(radix, &key, 0);
	sprintf(buf, "str-%Lu\n", key.objectid);
	ret = insert_item(root, &key, buf, strlen(buf));
	if (ret)
		goto error;
	oid = (unsigned long)key.objectid;
	radix_tree_preload(GFP_KERNEL);
	ret = radix_tree_insert(radix, oid, (void *)oid);
	radix_tree_preload_end();
	if (ret)
		goto error;
	return ret;
error:
	printf("failed to insert %Lu\n", key.objectid);
	return -1;
}

static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix)
{
	struct ctree_path path;
	struct key key;
	int ret;
	char buf[128];
	init_path(&path);
	ret = setup_key(radix, &key, 1);
	if (ret < 0)
		return 0;
	sprintf(buf, "str-%Lu\n", key.objectid);
	ret = insert_item(root, &key, buf, strlen(buf));
	if (ret != -EEXIST) {
		printf("insert on %Lu gave us %d\n", key.objectid, ret);
		return 1;
	}
	return 0;
}

static int del_one(struct ctree_root *root, struct radix_tree_root *radix)
{
	struct ctree_path path;
	struct key key;
	int ret;
	unsigned long *ptr;
	init_path(&path);
	ret = setup_key(radix, &key, 1);
	if (ret < 0)
		return 0;
	ret = search_slot(root, &key, &path, -1);
	if (ret)
		goto error;
	ret = del_item(root, &path);
	release_path(root, &path);
	if (ret != 0)
		goto error;
	ptr = radix_tree_delete(radix, key.objectid);
	if (!ptr)
		goto error;
	return 0;
error:
	printf("failed to delete %Lu\n", key.objectid);
	return -1;
}

static int lookup_item(struct ctree_root *root, struct radix_tree_root *radix)
{
	struct ctree_path path;
	struct key key;
	int ret;
	init_path(&path);
	ret = setup_key(radix, &key, 1);
	if (ret < 0)
		return 0;
	ret = search_slot(root, &key, &path, 0);
	release_path(root, &path);
	if (ret)
		goto error;
	return 0;
error:
	printf("unable to find key %Lu\n", key.objectid);
	return -1;
}

static int lookup_enoent(struct ctree_root *root, struct radix_tree_root *radix)
{
	struct ctree_path path;
	struct key key;
	int ret;
	init_path(&path);
	ret = setup_key(radix, &key, 0);
	if (ret < 0)
		return ret;
	ret = search_slot(root, &key, &path, 0);
	release_path(root, &path);
	if (ret <= 0)
		goto error;
	return 0;
error:
	printf("able to find key that should not exist %Lu\n", key.objectid);
	return -1;
}

int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) =
{ ins_one, insert_dup, del_one, lookup_item, lookup_enoent };

static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix)
{
	struct ctree_path path;
	struct key key;
	unsigned long found;
	int ret;
	int slot;
	int i;

	key.offset = 0;
	key.flags = 0;
	key.objectid = (unsigned long)-1;
	while(1) {
		init_path(&path);
		ret = search_slot(root, &key, &path, 0);
		if (ret < 0) {
			release_path(root, &path);
			return ret;
		}
		slot = path.slots[0];
		if (ret != 0) {
			if (slot == 0) {
				release_path(root, &path);
				break;
			}
			slot -= 1;
		}
		for (i = slot; i >= 0; i--) {
			found = path.nodes[0]->leaf.items[i].key.objectid;
			radix_tree_preload(GFP_KERNEL);
			ret = radix_tree_insert(radix, found, (void *)found);
			if (ret) {
				fprintf(stderr,
					"failed to insert %lu into radix\n",
					found);
				exit(1);
			}

			radix_tree_preload_end();
		}
		release_path(root, &path);
		key.objectid = found - 1;
		if (key.objectid > found)
			break;
	}
	return 0;
}

void sigstopper(int ignored)
{
	keep_running = 0;
	fprintf(stderr, "caught exit signal, stopping\n");
}

int print_usage(void)
{
	printf("usage: tester [-ih] [-c count] [-f count]\n");
	printf("\t -c count -- iteration count after filling\n");
	printf("\t -f count -- run this many random inserts before starting\n");
	printf("\t -i       -- only do initial fill\n");
	printf("\t -h       -- this help text\n");
	exit(1);
}
int main(int ac, char **av)
{
	RADIX_TREE(radix, GFP_KERNEL);
	struct ctree_super_block super;
	struct ctree_root *root;
	int i;
	int ret;
	int count;
	int op;
	int iterations = 20000;
	int init_fill_count = 800000;
	int err = 0;
	int initial_only = 0;
	radix_tree_init();
	root = open_ctree("dbfile", &super);
	fill_radix(root, &radix);

	signal(SIGTERM, sigstopper);
	signal(SIGINT, sigstopper);

	for (i = 1 ; i < ac ; i++) {
		if (strcmp(av[i], "-i") == 0) {
			initial_only = 1;
		} else if (strcmp(av[i], "-c") == 0) {
			iterations = atoi(av[i+1]);
			i++;
		} else if (strcmp(av[i], "-f") == 0) {
			init_fill_count = atoi(av[i+1]);
			i++;
		} else {
			print_usage();
		}
	}
	for (i = 0; i < init_fill_count; i++) {
		ret = ins_one(root, &radix);
		if (ret) {
			printf("initial fill failed\n");
			err = ret;
			goto out;
		}
		if (i % 10000 == 0) {
			printf("initial fill %d level %d count %d\n", i,
				node_level(root->node->node.header.flags),
				root->node->node.header.nritems);
		}
		if (keep_running == 0) {
			err = 0;
			goto out;
		}
	}
	if (initial_only == 1) {
		goto out;
	}
	for (i = 0; i < iterations; i++) {
		op = rand() % ARRAY_SIZE(ops);
		count = rand() % 128;
		if (i % 2000 == 0) {
			printf("%d\n", i);
			fflush(stdout);
		}
		if (i && i % 5000 == 0) {
			printf("open & close, root level %d nritems %d\n",
				node_level(root->node->node.header.flags),
				root->node->node.header.nritems);
			write_ctree_super(root, &super);
			close_ctree(root);
			root = open_ctree("dbfile", &super);
		}
		while(count--) {
			ret = ops[op](root, &radix);
			if (ret) {
				fprintf(stderr, "op %d failed %d:%d\n",
					op, i, iterations);
				print_tree(root, root->node);
				fprintf(stderr, "op %d failed %d:%d\n",
					op, i, iterations);
				err = ret;
				goto out;
			}
			if (keep_running == 0) {
				err = 0;
				goto out;
			}
		}
	}
out:
	write_ctree_super(root, &super);
	close_ctree(root);
	return err;
}
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);
fec577fb CM	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
	62	static int insert_dup(struct ctree_root root, struct radix_tree_root radix)
	63	{
	64	struct ctree_path path;
	65	struct key key;
	66	int ret;
	67	char buf[128];
	68	init_path(&path);
	69	ret = setup_key(radix, &key, 1);
	70	if (ret < 0)
	71	return 0;
7cf75962	72	sprintf(buf, "str-%Lu\n", key.objectid);
fec577fb CM	73	ret = insert_item(root, &key, buf, strlen(buf));
fec577fb CM	74	if (ret != -EEXIST) {
7cf75962	75	printf("insert on %Lu gave us %d\n", key.objectid, ret);
fec577fb CM	76	return 1;
	77	}
	78	return 0;
	79	}
	80
	81	static int del_one(struct ctree_root root, struct radix_tree_root radix)
	82	{
	83	struct ctree_path path;
	84	struct key key;
	85	int ret;
	86	unsigned long *ptr;
	87	init_path(&path);
	88	ret = setup_key(radix, &key, 1);
	89	if (ret < 0)
	90	return 0;
	91	ret = search_slot(root, &key, &path, -1);
	92	if (ret)
	93	goto error;
	94	ret = del_item(root, &path);
	95	release_path(root, &path);
	96	if (ret != 0)
	97	goto error;
	98	ptr = radix_tree_delete(radix, key.objectid);
	99	if (!ptr)
	100	goto error;
	101	return 0;
	102	error:
7cf75962	103	printf("failed to delete %Lu\n", key.objectid);
fec577fb CM	104	return -1;
	105	}
	106
	107	static int lookup_item(struct ctree_root root, struct radix_tree_root radix)
	108	{
	109	struct ctree_path path;
	110	struct key key;
	111	int ret;
	112	init_path(&path);
	113	ret = setup_key(radix, &key, 1);
	114	if (ret < 0)
	115	return 0;
	116	ret = search_slot(root, &key, &path, 0);
	117	release_path(root, &path);
	118	if (ret)
	119	goto error;
	120	return 0;
	121	error:
7cf75962	122	printf("unable to find key %Lu\n", key.objectid);
fec577fb CM	123	return -1;
	124	}
	125
	126	static int lookup_enoent(struct ctree_root root, struct radix_tree_root radix)
	127	{
	128	struct ctree_path path;
	129	struct key key;
	130	int ret;
	131	init_path(&path);
	132	ret = setup_key(radix, &key, 0);
	133	if (ret < 0)
	134	return ret;
	135	ret = search_slot(root, &key, &path, 0);
	136	release_path(root, &path);
aa5d6bed	137	if (ret <= 0)
fec577fb CM	138	goto error;
	139	return 0;
	140	error:
7cf75962	141	printf("able to find key that should not exist %Lu\n", key.objectid);
fec577fb CM	142	return -1;
	143	}
	144
	145	int (ops[])(struct ctree_root root, struct radix_tree_root *radix) =
	146	{ ins_one, insert_dup, del_one, lookup_item, lookup_enoent };
	147
	148	static int fill_radix(struct ctree_root root, struct radix_tree_root radix)
	149	{
	150	struct ctree_path path;
	151	struct key key;
7cf75962	152	unsigned long found;
fec577fb CM	153	int ret;
	154	int slot;
	155	int i;
aa5d6bed	156
fec577fb CM	157	key.offset = 0;
	158	key.flags = 0;
	159	key.objectid = (unsigned long)-1;
	160	while(1) {
	161	init_path(&path);
	162	ret = search_slot(root, &key, &path, 0);
aa5d6bed CM	163	if (ret < 0) {
	164	release_path(root, &path);
	165	return ret;
	166	}
fec577fb CM	167	slot = path.slots[0];
	168	if (ret != 0) {
	169	if (slot == 0) {
	170	release_path(root, &path);
	171	break;
	172	}
	173	slot -= 1;
	174	}
	175	for (i = slot; i >= 0; i--) {
	176	found = path.nodes[0]->leaf.items[i].key.objectid;
	177	radix_tree_preload(GFP_KERNEL);
	178	ret = radix_tree_insert(radix, found, (void *)found);
	179	if (ret) {
	180	fprintf(stderr,
	181	"failed to insert %lu into radix\n",
	182	found);
	183	exit(1);
	184	}
	185
	186	radix_tree_preload_end();
	187	}
	188	release_path(root, &path);
	189	key.objectid = found - 1;
	190	if (key.objectid > found)
	191	break;
	192	}
	193	return 0;
	194	}
	195
	196	void sigstopper(int ignored)
	197	{
	198	keep_running = 0;
	199	fprintf(stderr, "caught exit signal, stopping\n");
	200	}
	201
	202	int print_usage(void)
	203	{
	204	printf("usage: tester [-ih] [-c count] [-f count]\n");
	205	printf("\t -c count -- iteration count after filling\n");
	206	printf("\t -f count -- run this many random inserts before starting\n");
	207	printf("\t -i -- only do initial fill\n");
	208	printf("\t -h -- this help text\n");
	209	exit(1);
	210	}
	211	int main(int ac, char **av)
	212	{
	213	RADIX_TREE(radix, GFP_KERNEL);
	214	struct ctree_super_block super;
	215	struct ctree_root *root;
	216	int i;
	217	int ret;
	218	int count;
	219	int op;
	220	int iterations = 20000;
	221	int init_fill_count = 800000;
	222	int err = 0;
	223	int initial_only = 0;
	224	radix_tree_init();
	225	root = open_ctree("dbfile", &super);
	226	fill_radix(root, &radix);
	227
	228	signal(SIGTERM, sigstopper);
	229	signal(SIGINT, sigstopper);
	230
231	for (i = 1 ; i < ac ; i++) {
232	if (strcmp(av[i], "-i") == 0) {
233	initial_only = 1;
234	} else if (strcmp(av[i], "-c") == 0) {
235	iterations = atoi(av[i+1]);
236	i++;
237	} else if (strcmp(av[i], "-f") == 0) {
238	init_fill_count = atoi(av[i+1]);
239	i++;
240	} else {
241	print_usage();
242	}
243	}
244	for (i = 0; i < init_fill_count; i++) {
245	ret = ins_one(root, &radix);
246	if (ret) {
247	printf("initial fill failed\n");
248	err = ret;
249	goto out;
250	}
251	if (i % 10000 == 0) {
252	printf("initial fill %d level %d count %d\n", i,
253	node_level(root->node->node.header.flags),
254	root->node->node.header.nritems);
255	}
256	if (keep_running == 0) {
257	err = 0;
258	goto out;
259	}
260	}
261	if (initial_only == 1) {
262	goto out;
263	}
264	for (i = 0; i < iterations; i++) {
265	op = rand() % ARRAY_SIZE(ops);
266	count = rand() % 128;
267	if (i % 2000 == 0) {
268	printf("%d\n", i);
269	fflush(stdout);
270	}
271	if (i && i % 5000 == 0) {
272	printf("open & close, root level %d nritems %d\n",
273	node_level(root->node->node.header.flags),
274	root->node->node.header.nritems);
275	write_ctree_super(root, &super);
276	close_ctree(root);
277	root = open_ctree("dbfile", &super);
278	}
279	while(count--) {
280	ret = ops[op](root, &radix);
281	if (ret) {
282	fprintf(stderr, "op %d failed %d:%d\n",
283	op, i, iterations);
284	print_tree(root, root->node);
285	fprintf(stderr, "op %d failed %d:%d\n",
286	op, i, iterations);
287	err = ret;
288	goto out;
289	}
290	if (keep_running == 0) {
291	err = 0;
292	goto out;
293	}
294	}
295	}
296	out:
297	write_ctree_super(root, &super);
298	close_ctree(root);
299	return err;
300	}
301