[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 run_commit(struct ctree_root *root, struct radix_tree_root *radix)
{
	return commit_transaction(root);
}

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, 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, 1);
	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, 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;
}

static int empty_tree(struct ctree_root *root, struct radix_tree_root *radix,
		      int nr)
{
	struct ctree_path path;
	struct key key;
	unsigned long found = 0;
	int ret;
	int slot;
	int *ptr;
	int count = 0;

	key.offset = 0;
	key.flags = 0;
	key.objectid = (unsigned long)-1;
	while(nr-- >= 0) {
		init_path(&path);
		ret = search_slot(root, &key, &path, -1, 1);
		if (ret < 0) {
			release_path(root, &path);
			return ret;
		}
		if (ret != 0) {
			if (path.slots[0] == 0) {
				release_path(root, &path);
				break;
			}
			path.slots[0] -= 1;
		}
		slot = path.slots[0];
		found = path.nodes[0]->leaf.items[slot].key.objectid;
		ret = del_item(root, &path);
		count++;
		if (ret) {
			fprintf(stderr,
				"failed to remove %lu from tree\n",
				found);
			return -1;
		}
		release_path(root, &path);
		ptr = radix_tree_delete(radix, found);
		if (!ptr)
			goto error;
		if (!keep_running)
			break;
	}
	return 0;
error:
	fprintf(stderr, "failed to delete from the radix %lu\n", found);
	return -1;
}

static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix,
		     int count)
{
	int i;
	int ret = 0;
	for (i = 0; i < count; i++) {
		ret = ins_one(root, radix);
		if (ret) {
			fprintf(stderr, "fill failed\n");
			goto out;
		}
		if (i % 1000 == 0) {
			ret = commit_transaction(root);
			if (ret) {
				fprintf(stderr, "fill commit failed\n");
				return ret;
			}
		}
		if (i && i % 10000 == 0) {
			printf("bigfill %d\n", i);
		}
		if (!keep_running)
			break;
	}
out:
	return ret;
}

static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix)
{
	int ret;
	int nr = rand() % 20000;
	static int run_nr = 0;

	/* do the bulk op much less frequently */
	if (run_nr++ % 100)
		return 0;
	ret = empty_tree(root, radix, nr);
	if (ret)
		return ret;
	ret = fill_tree(root, radix, nr);
	if (ret)
		return ret;
	return 0;
}


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

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, 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();
		}
	}
	printf("initial fill\n");
	ret = fill_tree(root, &radix, init_fill_count);
	printf("starting run\n");
	if (ret) {
		err = ret;
		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 (ops[op] == bulk_op || ops[op] == run_commit)
				break;
			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
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));
fec577fb CM	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;
79f95c82 CM	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);
77ce6846 CM	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,
f0930a37 CM	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