[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;
struct ctree_super_block super;

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, 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, &super);
			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() % 5000;
	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 };

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_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);
			close_ctree(root, &super);
			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)
				break;
			if (keep_running == 0) {
				err = 0;
				goto out;
			}
		}
	}
out:
	close_ctree(root, &super);
	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;
a28ec197	11	struct ctree_super_block super;
fec577fb CM	12
	13	static int setup_key(struct radix_tree_root root, struct key key, int exists)
	14	{
	15	int num = rand();
	16	unsigned long res[2];
	17	int ret;
	18
	19	key->flags = 0;
	20	key->offset = 0;
	21	again:
	22	ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
	23	if (exists) {
	24	if (ret == 0)
	25	return -1;
	26	num = res[0];
	27	} else if (ret != 0 && num == res[0]) {
	28	num++;
	29	if (ret > 1 && num == res[1]) {
	30	num++;
	31	goto again;
	32	}
	33	}
	34	key->objectid = num;
	35	return 0;
	36	}
	37
	38	static int ins_one(struct ctree_root root, struct radix_tree_root radix)
	39	{
	40	struct ctree_path path;
	41	struct key key;
	42	int ret;
	43	char buf[128];
41903fe6	44	unsigned long oid;
fec577fb CM	45	init_path(&path);
fec577fb CM	46	ret = setup_key(radix, &key, 0);
7cf75962	47	sprintf(buf, "str-%Lu\n", key.objectid);
fec577fb CM	48	ret = insert_item(root, &key, buf, strlen(buf));
	49	if (ret)
	50	goto error;
41903fe6	51	oid = (unsigned long)key.objectid;
fec577fb	52	radix_tree_preload(GFP_KERNEL);
41903fe6	53	ret = radix_tree_insert(radix, oid, (void *)oid);
fec577fb CM	54	radix_tree_preload_end();
	55	if (ret)
	56	goto error;
	57	return ret;
	58	error:
7cf75962	59	printf("failed to insert %Lu\n", key.objectid);
fec577fb CM	60	return -1;
	61	}
	62
	63	static int insert_dup(struct ctree_root root, struct radix_tree_root radix)
	64	{
	65	struct ctree_path path;
	66	struct key key;
	67	int ret;
	68	char buf[128];
	69	init_path(&path);
	70	ret = setup_key(radix, &key, 1);
	71	if (ret < 0)
	72	return 0;
7cf75962	73	sprintf(buf, "str-%Lu\n", key.objectid);
fec577fb CM	74	ret = insert_item(root, &key, buf, strlen(buf));
fec577fb CM	75	if (ret != -EEXIST) {
7cf75962	76	printf("insert on %Lu gave us %d\n", key.objectid, ret);
fec577fb CM	77	return 1;
	78	}
	79	return 0;
	80	}
	81
	82	static int del_one(struct ctree_root root, struct radix_tree_root radix)
	83	{
	84	struct ctree_path path;
	85	struct key key;
	86	int ret;
	87	unsigned long *ptr;
	88	init_path(&path);
	89	ret = setup_key(radix, &key, 1);
	90	if (ret < 0)
	91	return 0;
02217ed2	92	ret = search_slot(root, &key, &path, -1, 1);
fec577fb CM	93	if (ret)
	94	goto error;
	95	ret = del_item(root, &path);
	96	release_path(root, &path);
	97	if (ret != 0)
	98	goto error;
	99	ptr = radix_tree_delete(radix, key.objectid);
	100	if (!ptr)
	101	goto error;
	102	return 0;
	103	error:
7cf75962	104	printf("failed to delete %Lu\n", key.objectid);
fec577fb CM	105	return -1;
	106	}
	107
	108	static int lookup_item(struct ctree_root root, struct radix_tree_root radix)
	109	{
	110	struct ctree_path path;
	111	struct key key;
	112	int ret;
	113	init_path(&path);
	114	ret = setup_key(radix, &key, 1);
	115	if (ret < 0)
	116	return 0;
02217ed2	117	ret = search_slot(root, &key, &path, 0, 1);
fec577fb CM	118	release_path(root, &path);
	119	if (ret)
	120	goto error;
	121	return 0;
	122	error:
7cf75962	123	printf("unable to find key %Lu\n", key.objectid);
fec577fb CM	124	return -1;
	125	}
	126
	127	static int lookup_enoent(struct ctree_root root, struct radix_tree_root radix)
	128	{
	129	struct ctree_path path;
	130	struct key key;
	131	int ret;
	132	init_path(&path);
	133	ret = setup_key(radix, &key, 0);
	134	if (ret < 0)
	135	return ret;
02217ed2	136	ret = search_slot(root, &key, &path, 0, 0);
fec577fb	137	release_path(root, &path);
aa5d6bed	138	if (ret <= 0)
fec577fb CM	139	goto error;
	140	return 0;
	141	error:
7cf75962	142	printf("able to find key that should not exist %Lu\n", key.objectid);
fec577fb CM	143	return -1;
	144	}
	145
79f95c82 CM	146	static int empty_tree(struct ctree_root root, struct radix_tree_root radix,
	147	int nr)
	148	{
	149	struct ctree_path path;
	150	struct key key;
	151	unsigned long found = 0;
	152	int ret;
	153	int slot;
	154	int *ptr;
	155	int count = 0;
	156
	157	key.offset = 0;
	158	key.flags = 0;
	159	key.objectid = (unsigned long)-1;
	160	while(nr-- >= 0) {
	161	init_path(&path);
02217ed2	162	ret = search_slot(root, &key, &path, -1, 1);
79f95c82 CM	163	if (ret < 0) {
	164	release_path(root, &path);
	165	return ret;
	166	}
	167	if (ret != 0) {
	168	if (path.slots[0] == 0) {
	169	release_path(root, &path);
	170	break;
	171	}
	172	path.slots[0] -= 1;
	173	}
	174	slot = path.slots[0];
	175	found = path.nodes[0]->leaf.items[slot].key.objectid;
	176	ret = del_item(root, &path);
	177	count++;
	178	if (ret) {
	179	fprintf(stderr,
	180	"failed to remove %lu from tree\n",
	181	found);
	182	return -1;
	183	}
	184	release_path(root, &path);
	185	ptr = radix_tree_delete(radix, found);
	186	if (!ptr)
	187	goto error;
	188	if (!keep_running)
	189	break;
	190	}
	191	return 0;
	192	error:
	193	fprintf(stderr, "failed to delete from the radix %lu\n", found);
	194	return -1;
	195	}
	196
	197	static int fill_tree(struct ctree_root root, struct radix_tree_root radix,
	198	int count)
	199	{
	200	int i;
79f95c82 CM	201	int ret = 0;
	202	for (i = 0; i < count; i++) {
	203	ret = ins_one(root, radix);
	204	if (ret) {
77ce6846	205	fprintf(stderr, "fill failed\n");
79f95c82 CM	206	goto out;
79f95c82 CM	207	}
77ce6846	208	if (i % 1000 == 0) {
a28ec197	209	ret = commit_transaction(root, &super);
77ce6846 CM	210	if (ret) {
	211	fprintf(stderr, "fill commit failed\n");
	212	return ret;
	213	}
	214	}
02217ed2	215	if (i && i % 10000 == 0) {
77ce6846 CM	216	printf("bigfill %d\n", i);
77ce6846 CM	217	}
79f95c82 CM	218	if (!keep_running)
	219	break;
	220	}
	221	out:
	222	return ret;
	223	}
	224
	225	static int bulk_op(struct ctree_root root, struct radix_tree_root radix)
	226	{
	227	int ret;
a28ec197	228	int nr = rand() % 5000;
79f95c82 CM	229	static int run_nr = 0;
	230
	231	/* do the bulk op much less frequently */
	232	if (run_nr++ % 100)
	233	return 0;
	234	ret = empty_tree(root, radix, nr);
	235	if (ret)
	236	return ret;
	237	ret = fill_tree(root, radix, nr);
	238	if (ret)
	239	return ret;
	240	return 0;
	241	}
	242
	243
fec577fb	244	int (ops[])(struct ctree_root root, struct radix_tree_root *radix) =
f0930a37	245	{ ins_one, insert_dup, del_one, lookup_item,
a28ec197	246	lookup_enoent, bulk_op };
fec577fb CM	247
	248	static int fill_radix(struct ctree_root root, struct radix_tree_root radix)
	249	{
	250	struct ctree_path path;
	251	struct key key;
7cf75962	252	unsigned long found;
fec577fb CM	253	int ret;
	254	int slot;
	255	int i;
aa5d6bed	256
fec577fb CM	257	key.offset = 0;
	258	key.flags = 0;
	259	key.objectid = (unsigned long)-1;
	260	while(1) {
	261	init_path(&path);
02217ed2	262	ret = search_slot(root, &key, &path, 0, 0);
aa5d6bed CM	263	if (ret < 0) {
	264	release_path(root, &path);
	265	return ret;
	266	}
fec577fb CM	267	slot = path.slots[0];
	268	if (ret != 0) {
	269	if (slot == 0) {
	270	release_path(root, &path);
	271	break;
	272	}
	273	slot -= 1;
	274	}
	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);
	279	if (ret) {
	280	fprintf(stderr,
	281	"failed to insert %lu into radix\n",
	282	found);
	283	exit(1);
	284	}
	285
	286	radix_tree_preload_end();
	287	}
	288	release_path(root, &path);
	289	key.objectid = found - 1;
	290	if (key.objectid > found)
	291	break;
	292	}
	293	return 0;
	294	}
fec577fb CM	295	void sigstopper(int ignored)
	296	{
	297	keep_running = 0;
	298	fprintf(stderr, "caught exit signal, stopping\n");
	299	}
	300
	301	int print_usage(void)
	302	{
	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");
	308	exit(1);
	309	}
	310	int main(int ac, char **av)
	311	{
	312	RADIX_TREE(radix, GFP_KERNEL);
fec577fb CM	313	struct ctree_root *root;
	314	int i;
	315	int ret;
	316	int count;
	317	int op;
	318	int iterations = 20000;
	319	int init_fill_count = 800000;
	320	int err = 0;
	321	int initial_only = 0;
	322	radix_tree_init();
	323	root = open_ctree("dbfile", &super);
	324	fill_radix(root, &radix);
	325
	326	signal(SIGTERM, sigstopper);
	327	signal(SIGINT, sigstopper);
	328
	329	for (i = 1 ; i < ac ; i++) {
	330	if (strcmp(av[i], "-i") == 0) {
	331	initial_only = 1;
	332	} else if (strcmp(av[i], "-c") == 0) {
	333	iterations = atoi(av[i+1]);
	334	i++;
	335	} else if (strcmp(av[i], "-f") == 0) {
	336	init_fill_count = atoi(av[i+1]);
	337	i++;
	338	} else {
	339	print_usage();
	340	}
	341	}
79f95c82 CM	342	printf("initial fill\n");
	343	ret = fill_tree(root, &radix, init_fill_count);
	344	printf("starting run\n");
	345	if (ret) {
	346	err = ret;
	347	goto out;
fec577fb CM	348	}
	349	if (initial_only == 1) {
	350	goto out;
	351	}
	352	for (i = 0; i < iterations; i++) {
	353	op = rand() % ARRAY_SIZE(ops);
	354	count = rand() % 128;
	355	if (i % 2000 == 0) {
	356	printf("%d\n", i);
	357	fflush(stdout);
	358	}
	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);
a28ec197	363	close_ctree(root, &super);
fec577fb CM	364	root = open_ctree("dbfile", &super);
	365	}
	366	while(count--) {
	367	ret = ops[op](root, &radix);
	368	if (ret) {
	369	fprintf(stderr, "op %d failed %d:%d\n",
	370	op, i, iterations);
	371	print_tree(root, root->node);
	372	fprintf(stderr, "op %d failed %d:%d\n",
	373	op, i, iterations);
	374	err = ret;
	375	goto out;
	376	}
a28ec197	377	if (ops[op] == bulk_op)
79f95c82	378	break;
fec577fb CM	379	if (keep_running == 0) {
	380	err = 0;
	381	goto out;
	382	}
	383	}
	384	}
	385	out:
a28ec197	386	close_ctree(root, &super);
fec577fb CM	387	return err;
	388	}
	389