[fio.git] / t / dedupe.c

/*
 * Small tool to check for dedupable blocks in a file or device. Basically
 * just scans the filename for extents of the given size, checksums them,
 * and orders them up.
 */
#include <stdio.h>
#include <stdio.h>
#include <unistd.h>
#include <inttypes.h>
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <linux/fs.h>
#include <fcntl.h>
#include <string.h>

#include "../lib/rbtree.h"
#include "../flist.h"
#include "../log.h"
#include "../mutex.h"
#include "../smalloc.h"
#include "../minmax.h"
#include "../crc/md5.h"
#include "../memalign.h"
#include "../os/os.h"

FILE *f_err;
struct timeval *fio_tv = NULL;
unsigned int fio_debug = 0;

void __dprint(int type, const char *str, ...)
{
}

struct worker_thread {
	pthread_t thread;

	int fd;
	uint64_t cur_offset;
	uint64_t size;

	unsigned long items;
	int err;
};

struct extent {
	struct flist_head list;
	uint64_t offset;
};

struct chunk {
	struct rb_node rb_node;
	struct flist_head extent_list;
	uint64_t count;
	uint32_t hash[MD5_HASH_WORDS];
};

struct item {
	uint64_t offset;
	uint32_t hash[MD5_HASH_WORDS];
};

static struct rb_root rb_root;
static struct fio_mutex *rb_lock;

static unsigned int blocksize = 4096;
static unsigned int num_threads;
static unsigned int chunk_size = 1048576;
static unsigned int dump_output;
static unsigned int odirect;
static unsigned int collision_check;

static uint64_t total_size;
static uint64_t cur_offset;
static struct fio_mutex *size_lock;

static int dev_fd;

static uint64_t get_size(int fd, struct stat *sb)
{
	uint64_t ret;

	if (S_ISBLK(sb->st_mode)) {
		if (ioctl(fd, BLKGETSIZE64, &ret) < 0) {
			perror("ioctl");
			return 0;
		}
	} else
		ret = sb->st_size;

	return (ret & ~((uint64_t)blocksize - 1));
}

static int get_work(uint64_t *offset, uint64_t *size)
{
	uint64_t this_chunk;
	int ret = 1;

	fio_mutex_down(size_lock);

	if (cur_offset < total_size) {
		*offset = cur_offset;
		this_chunk = min((uint64_t)chunk_size, total_size - cur_offset);
		*size = this_chunk;
		cur_offset += this_chunk;
		ret = 0;
	}

	fio_mutex_up(size_lock);
	return ret;
}

static int read_block(int fd, void *buf, off_t offset)
{
	ssize_t ret;

	ret = pread(fd, buf, blocksize, offset);
	if (ret < 0) {
		perror("pread");
		return 1;
	} else if (!ret)
		return 1;
	else if (ret != blocksize) {
		log_err("dedupe: short read on block\n");
		return 1;
	}

	return 0;
}

static void add_item(struct chunk *c, struct item *i)
{
	struct extent *e;

	e = malloc(sizeof(*e));
	e->offset = i->offset;
	flist_add_tail(&e->list, &c->extent_list);
	c->count++;
}

static int col_check(struct chunk *c, struct item *i)
{
	struct extent *e;
	char *cbuf, *ibuf;
	int ret = 1;

	cbuf = fio_memalign(blocksize, blocksize);
	ibuf = fio_memalign(blocksize, blocksize);

	e = flist_entry(c->extent_list.next, struct extent, list);
	if (read_block(dev_fd, cbuf, e->offset))
		goto out;

	if (read_block(dev_fd, ibuf, i->offset))
		goto out;

	ret = memcmp(ibuf, cbuf, blocksize);
out:
	fio_memfree(cbuf, blocksize);
	fio_memfree(ibuf, blocksize);
	return ret;
}

static void insert_chunk(struct item *i)
{
	struct rb_node **p, *parent;
	struct chunk *c;
	int diff;

	p = &rb_root.rb_node;
	parent = NULL;
	while (*p) {
		parent = *p;

		c = rb_entry(parent, struct chunk, rb_node);
		diff = memcmp(i->hash, c->hash, sizeof(i->hash));
		if (diff < 0)
			p = &(*p)->rb_left;
		else if (diff > 0)
			p = &(*p)->rb_right;
		else {
			int ret;

			if (!collision_check)
				goto add;

			fio_mutex_up(rb_lock);
			ret = col_check(c, i);
			fio_mutex_down(rb_lock);

			if (!ret)
				goto add;

			p = &(*p)->rb_right;
		}
	}

	c = malloc(sizeof(*c));
	RB_CLEAR_NODE(&c->rb_node);
	INIT_FLIST_HEAD(&c->extent_list);
	c->count = 0;
	memcpy(c->hash, i->hash, sizeof(i->hash));
	rb_link_node(&c->rb_node, parent, p);
	rb_insert_color(&c->rb_node, &rb_root);
add:
	add_item(c, i);
}

static void insert_chunks(struct item *items, unsigned int nitems)
{
	int i;

	fio_mutex_down(rb_lock);

	for (i = 0; i < nitems; i++)
		insert_chunk(&items[i]);

	fio_mutex_up(rb_lock);
}

static void crc_buf(void *buf, uint32_t *hash)
{
	struct fio_md5_ctx ctx = { .hash = hash };

	fio_md5_init(&ctx);
	fio_md5_update(&ctx, buf, blocksize);
	fio_md5_final(&ctx);
}

static int do_work(struct worker_thread *thread, void *buf)
{
	unsigned int nblocks, i;
	off_t offset;
	int err = 0, nitems = 0;
	struct item *items;

	nblocks = thread->size / blocksize;
	offset = thread->cur_offset;
	items = malloc(sizeof(*items) * nblocks);

	for (i = 0; i < nblocks; i++) {
		if (read_block(thread->fd, buf, offset))
			break;
		items[i].offset = offset;
		crc_buf(buf, items[i].hash);
		offset += blocksize;
		nitems++;
	}

	insert_chunks(items, nitems);
	thread->items += nitems;
	free(items);
	return err;
}

static void *thread_fn(void *data)
{
	struct worker_thread *thread = data;
	void *buf;

	buf = fio_memalign(blocksize, blocksize);

	do {
		if (get_work(&thread->cur_offset, &thread->size)) {
			thread->err = 1;
			break;
		}
		if (do_work(thread, buf)) {
			thread->err = 1;
			break;
		}
	} while (1);

	fio_memfree(buf, blocksize);
	return NULL;
}

static int __dedupe_check(int fd, uint64_t dev_size)
{
	struct worker_thread *threads;
	unsigned long nitems;
	int i, err = 0;

	total_size = dev_size;
	cur_offset = 0;
	size_lock = fio_mutex_init(FIO_MUTEX_UNLOCKED);

	threads = malloc(num_threads * sizeof(struct worker_thread));
	for (i = 0; i < num_threads; i++) {
		threads[i].fd = fd;
		threads[i].items = 0;
		threads[i].err = 0;

		err = pthread_create(&threads[i].thread, NULL, thread_fn, &threads[i]);
		if (err) {
			log_err("fio: thread startup failed\n");
			break;
		}
	}

	nitems = 0;
	for (i = 0; i < num_threads; i++) {
		void *ret;
		pthread_join(threads[i].thread, &ret);
		nitems += threads[i].items;
	}

	printf("Threads(%u): %lu items processed\n", num_threads, nitems);

	fio_mutex_remove(size_lock);
	return err;
}

static int dedupe_check(const char *filename)
{
	uint64_t dev_size;
	struct stat sb;
	int flags;

	flags = O_RDONLY;
	if (odirect)
		flags |= O_DIRECT;

	dev_fd = open(filename, flags);
	if (dev_fd == -1) {
		perror("open");
		return 1;
	}

	if (fstat(dev_fd, &sb) < 0) {
		perror("fstat");
		close(dev_fd);
		return 1;
	}

	dev_size = get_size(dev_fd, &sb);
	if (!dev_size) {
		close(dev_fd);
		return 1;
	}

	printf("Will check <%s>, size <%lu>\n", filename, dev_size);

	return __dedupe_check(dev_fd, dev_size);
}

static void show_chunk(struct chunk *c)
{
	struct flist_head *n;
	struct extent *e;

	printf("c hash %8x %8x %8x %8x, count %lu\n", c->hash[0], c->hash[1], c->hash[2], c->hash[3], c->count);
	flist_for_each(n, &c->extent_list) {
		e = flist_entry(n, struct extent, list);
		printf("\toffset %lu\n", e->offset);
	}
}

static void iter_rb_tree(void)
{
	struct rb_node *n;
	uint64_t nchunks;
	uint64_t nextents;
	double perc;

	nchunks = nextents = 0;

	n = rb_first(&rb_root);
	if (!n)
		return;

	do {
		struct chunk *c;

		c = rb_entry(n, struct chunk, rb_node);
		nchunks++;
		nextents += c->count;

		if (dump_output)
			show_chunk(c);

	} while ((n = rb_next(n)) != NULL);

	printf("Extents=%lu, Unique extents=%lu\n", nextents, nchunks);
	printf("De-dupe factor: %3.2f\n", (double) nextents / (double) nchunks);

	perc = 1.00 - ((double) nchunks / (double) nextents);
	perc *= 100.0;
	printf("Fio setting: dedupe_percentage=%u\n", (int) (perc + 0.50));
}

static int usage(char *argv[])
{
	log_err("Check for dedupable blocks on a device/file\n\n");
	log_err("%s: [options] <device or file>\n", argv[0]);
	log_err("\t-b\tChunk size to use\n");
	log_err("\t-t\tNumber of threads to use\n");
	log_err("\t-d\tFull extent/chunk debug output\n");
	log_err("\t-o\tUse O_DIRECT\n");
	log_err("\t-c\tFull collision check\n");
	return 1;
}

int main(int argc, char *argv[])
{
	int c, ret;

	while ((c = getopt(argc, argv, "b:t:d:o:c:")) != -1) {
		switch (c) {
		case 'b':
			blocksize = atoi(optarg);
			break;
		case 't':
			num_threads = atoi(optarg);
			break;
		case 'd':
			dump_output = atoi(optarg);
			break;
		case 'o':
			odirect = atoi(optarg);
			break;
		case 'c':
			collision_check = atoi(optarg);
			break;
		case '?':
		default:
			return usage(argv);
		}
	}

	if (!num_threads)
		num_threads = cpus_online();

	if (argc == optind)
		return usage(argv);

	sinit();

	rb_root = RB_ROOT;
	rb_lock = fio_mutex_init(FIO_MUTEX_UNLOCKED);

	ret = dedupe_check(argv[optind]);

	iter_rb_tree();

	scleanup();
	return ret;
}
Commit	Line	Data
	1	/*
	2	* Small tool to check for dedupable blocks in a file or device. Basically
	3	* just scans the filename for extents of the given size, checksums them,
	4	* and orders them up.
	5	*/
	6	#include <stdio.h>
	7	#include <stdio.h>
	8	#include <unistd.h>
	9	#include <inttypes.h>
	10	#include <assert.h>
	11	#include <sys/types.h>
	12	#include <sys/stat.h>
	13	#include <sys/ioctl.h>
	14	#include <linux/fs.h>
	15	#include <fcntl.h>
	16	#include <string.h>
	17
	18	#include "../lib/rbtree.h"
	19	#include "../flist.h"
	20	#include "../log.h"
	21	#include "../mutex.h"
	22	#include "../smalloc.h"
	23	#include "../minmax.h"
	24	#include "../crc/md5.h"
	25	#include "../memalign.h"
	26	#include "../os/os.h"
	27
	28	FILE *f_err;
	29	struct timeval *fio_tv = NULL;
	30	unsigned int fio_debug = 0;
	31
	32	void __dprint(int type, const char *str, ...)
	33	{
	34	}
	35
	36	struct worker_thread {
	37	pthread_t thread;
	38
	39	int fd;
	40	uint64_t cur_offset;
	41	uint64_t size;
	42
	43	unsigned long items;
	44	int err;
	45	};
	46
	47	struct extent {
	48	struct flist_head list;
	49	uint64_t offset;
	50	};
	51
	52	struct chunk {
	53	struct rb_node rb_node;
	54	struct flist_head extent_list;
	55	uint64_t count;
	56	uint32_t hash[MD5_HASH_WORDS];
	57	};
	58
	59	struct item {
	60	uint64_t offset;
	61	uint32_t hash[MD5_HASH_WORDS];
	62	};
	63
	64	static struct rb_root rb_root;
	65	static struct fio_mutex *rb_lock;
	66
	67	static unsigned int blocksize = 4096;
	68	static unsigned int num_threads;
	69	static unsigned int chunk_size = 1048576;
	70	static unsigned int dump_output;
	71	static unsigned int odirect;
	72	static unsigned int collision_check;
	73
	74	static uint64_t total_size;
	75	static uint64_t cur_offset;
	76	static struct fio_mutex *size_lock;
	77
	78	static int dev_fd;
	79
	80	static uint64_t get_size(int fd, struct stat *sb)
	81	{
	82	uint64_t ret;
	83
	84	if (S_ISBLK(sb->st_mode)) {
	85	if (ioctl(fd, BLKGETSIZE64, &ret) < 0) {
	86	perror("ioctl");
	87	return 0;
	88	}
	89	} else
	90	ret = sb->st_size;
	91
	92	return (ret & ~((uint64_t)blocksize - 1));
	93	}
	94
	95	static int get_work(uint64_t offset, uint64_t size)
	96	{
	97	uint64_t this_chunk;
	98	int ret = 1;
	99
	100	fio_mutex_down(size_lock);
	101
	102	if (cur_offset < total_size) {
	103	*offset = cur_offset;
	104	this_chunk = min((uint64_t)chunk_size, total_size - cur_offset);
	105	*size = this_chunk;
	106	cur_offset += this_chunk;
	107	ret = 0;
	108	}
	109
	110	fio_mutex_up(size_lock);
	111	return ret;
	112	}
	113
	114	static int read_block(int fd, void *buf, off_t offset)
	115	{
	116	ssize_t ret;
	117
	118	ret = pread(fd, buf, blocksize, offset);
	119	if (ret < 0) {
	120	perror("pread");
	121	return 1;
	122	} else if (!ret)
	123	return 1;
	124	else if (ret != blocksize) {
	125	log_err("dedupe: short read on block\n");
	126	return 1;
	127	}
	128
	129	return 0;
	130	}
	131
	132	static void add_item(struct chunk c, struct item i)
	133	{
	134	struct extent *e;
	135
	136	e = malloc(sizeof(*e));
	137	e->offset = i->offset;
	138	flist_add_tail(&e->list, &c->extent_list);
	139	c->count++;
	140	}
	141
	142	static int col_check(struct chunk c, struct item i)
	143	{
	144	struct extent *e;
	145	char cbuf, ibuf;
	146	int ret = 1;
	147
	148	cbuf = fio_memalign(blocksize, blocksize);
	149	ibuf = fio_memalign(blocksize, blocksize);
	150
	151	e = flist_entry(c->extent_list.next, struct extent, list);
	152	if (read_block(dev_fd, cbuf, e->offset))
	153	goto out;
	154
	155	if (read_block(dev_fd, ibuf, i->offset))
	156	goto out;
	157
	158	ret = memcmp(ibuf, cbuf, blocksize);
	159	out:
	160	fio_memfree(cbuf, blocksize);
	161	fio_memfree(ibuf, blocksize);
	162	return ret;
	163	}
	164
	165	static void insert_chunk(struct item *i)
	166	{
	167	struct rb_node *p, parent;
	168	struct chunk *c;
	169	int diff;
	170
	171	p = &rb_root.rb_node;
	172	parent = NULL;
	173	while (*p) {
	174	parent = *p;
	175
	176	c = rb_entry(parent, struct chunk, rb_node);
	177	diff = memcmp(i->hash, c->hash, sizeof(i->hash));
	178	if (diff < 0)
	179	p = &(*p)->rb_left;
	180	else if (diff > 0)
	181	p = &(*p)->rb_right;
	182	else {
	183	int ret;
	184
	185	if (!collision_check)
	186	goto add;
	187
	188	fio_mutex_up(rb_lock);
	189	ret = col_check(c, i);
	190	fio_mutex_down(rb_lock);
	191
	192	if (!ret)
	193	goto add;
	194
	195	p = &(*p)->rb_right;
	196	}
	197	}
	198
	199	c = malloc(sizeof(*c));
	200	RB_CLEAR_NODE(&c->rb_node);
	201	INIT_FLIST_HEAD(&c->extent_list);
	202	c->count = 0;
	203	memcpy(c->hash, i->hash, sizeof(i->hash));
	204	rb_link_node(&c->rb_node, parent, p);
	205	rb_insert_color(&c->rb_node, &rb_root);
	206	add:
	207	add_item(c, i);
	208	}
	209
	210	static void insert_chunks(struct item *items, unsigned int nitems)
	211	{
	212	int i;
	213
	214	fio_mutex_down(rb_lock);
	215
	216	for (i = 0; i < nitems; i++)
	217	insert_chunk(&items[i]);
	218
	219	fio_mutex_up(rb_lock);
	220	}
	221
	222	static void crc_buf(void buf, uint32_t hash)
	223	{
	224	struct fio_md5_ctx ctx = { .hash = hash };
	225
	226	fio_md5_init(&ctx);
	227	fio_md5_update(&ctx, buf, blocksize);
	228	fio_md5_final(&ctx);
	229	}
	230
	231	static int do_work(struct worker_thread thread, void buf)
	232	{
	233	unsigned int nblocks, i;
	234	off_t offset;
	235	int err = 0, nitems = 0;
	236	struct item *items;
	237
	238	nblocks = thread->size / blocksize;
	239	offset = thread->cur_offset;
	240	items = malloc(sizeof(items) nblocks);
	241
	242	for (i = 0; i < nblocks; i++) {
	243	if (read_block(thread->fd, buf, offset))
	244	break;
	245	items[i].offset = offset;
	246	crc_buf(buf, items[i].hash);
	247	offset += blocksize;
	248	nitems++;
	249	}
	250
	251	insert_chunks(items, nitems);
	252	thread->items += nitems;
	253	free(items);
	254	return err;
	255	}
	256
	257	static void thread_fn(void data)
	258	{
	259	struct worker_thread *thread = data;
	260	void *buf;
	261
	262	buf = fio_memalign(blocksize, blocksize);
	263
	264	do {
	265	if (get_work(&thread->cur_offset, &thread->size)) {
	266	thread->err = 1;
	267	break;
	268	}
	269	if (do_work(thread, buf)) {
	270	thread->err = 1;
	271	break;
	272	}
	273	} while (1);
	274
	275	fio_memfree(buf, blocksize);
	276	return NULL;
	277	}
	278
	279	static int __dedupe_check(int fd, uint64_t dev_size)
	280	{
	281	struct worker_thread *threads;
	282	unsigned long nitems;
	283	int i, err = 0;
	284
	285	total_size = dev_size;
	286	cur_offset = 0;
	287	size_lock = fio_mutex_init(FIO_MUTEX_UNLOCKED);
	288
	289	threads = malloc(num_threads * sizeof(struct worker_thread));
	290	for (i = 0; i < num_threads; i++) {
	291	threads[i].fd = fd;
	292	threads[i].items = 0;
	293	threads[i].err = 0;
	294
	295	err = pthread_create(&threads[i].thread, NULL, thread_fn, &threads[i]);
	296	if (err) {
	297	log_err("fio: thread startup failed\n");
	298	break;
	299	}
	300	}
	301
	302	nitems = 0;
	303	for (i = 0; i < num_threads; i++) {
	304	void *ret;
	305	pthread_join(threads[i].thread, &ret);
	306	nitems += threads[i].items;
	307	}
	308
	309	printf("Threads(%u): %lu items processed\n", num_threads, nitems);
	310
	311	fio_mutex_remove(size_lock);
	312	return err;
	313	}
	314
	315	static int dedupe_check(const char *filename)
	316	{
	317	uint64_t dev_size;
	318	struct stat sb;
	319	int flags;
	320
	321	flags = O_RDONLY;
	322	if (odirect)
	323	flags \|= O_DIRECT;
	324
	325	dev_fd = open(filename, flags);
	326	if (dev_fd == -1) {
	327	perror("open");
	328	return 1;
	329	}
	330
	331	if (fstat(dev_fd, &sb) < 0) {
	332	perror("fstat");
	333	close(dev_fd);
	334	return 1;
	335	}
	336
	337	dev_size = get_size(dev_fd, &sb);
	338	if (!dev_size) {
	339	close(dev_fd);
	340	return 1;
	341	}
	342
	343	printf("Will check <%s>, size <%lu>\n", filename, dev_size);
	344
	345	return __dedupe_check(dev_fd, dev_size);
	346	}
	347
	348	static void show_chunk(struct chunk *c)
	349	{
	350	struct flist_head *n;
	351	struct extent *e;
	352
	353	printf("c hash %8x %8x %8x %8x, count %lu\n", c->hash[0], c->hash[1], c->hash[2], c->hash[3], c->count);
	354	flist_for_each(n, &c->extent_list) {
	355	e = flist_entry(n, struct extent, list);
	356	printf("\toffset %lu\n", e->offset);
	357	}
	358	}
	359
	360	static void iter_rb_tree(void)
	361	{
	362	struct rb_node *n;
	363	uint64_t nchunks;
	364	uint64_t nextents;
	365	double perc;
	366
	367	nchunks = nextents = 0;
	368
	369	n = rb_first(&rb_root);
	370	if (!n)
	371	return;
	372
	373	do {
	374	struct chunk *c;
	375
	376	c = rb_entry(n, struct chunk, rb_node);
	377	nchunks++;
	378	nextents += c->count;
	379
	380	if (dump_output)
	381	show_chunk(c);
	382
	383	} while ((n = rb_next(n)) != NULL);
	384
	385	printf("Extents=%lu, Unique extents=%lu\n", nextents, nchunks);
	386	printf("De-dupe factor: %3.2f\n", (double) nextents / (double) nchunks);
	387
	388	perc = 1.00 - ((double) nchunks / (double) nextents);
	389	perc *= 100.0;
	390	printf("Fio setting: dedupe_percentage=%u\n", (int) (perc + 0.50));
	391	}
	392
	393	static int usage(char *argv[])
	394	{
	395	log_err("Check for dedupable blocks on a device/file\n\n");
	396	log_err("%s: [options] <device or file>\n", argv[0]);
	397	log_err("\t-b\tChunk size to use\n");
	398	log_err("\t-t\tNumber of threads to use\n");
	399	log_err("\t-d\tFull extent/chunk debug output\n");
	400	log_err("\t-o\tUse O_DIRECT\n");
	401	log_err("\t-c\tFull collision check\n");
	402	return 1;
	403	}
	404
	405	int main(int argc, char *argv[])
	406	{
	407	int c, ret;
	408
	409	while ((c = getopt(argc, argv, "b:t:d:o:c:")) != -1) {
	410	switch (c) {
	411	case 'b':
	412	blocksize = atoi(optarg);
	413	break;
	414	case 't':
	415	num_threads = atoi(optarg);
	416	break;
	417	case 'd':
	418	dump_output = atoi(optarg);
	419	break;
	420	case 'o':
	421	odirect = atoi(optarg);
	422	break;
	423	case 'c':
	424	collision_check = atoi(optarg);
	425	break;
	426	case '?':
	427	default:
	428	return usage(argv);
	429	}
	430	}
	431
	432	if (!num_threads)
	433	num_threads = cpus_online();
	434
	435	if (argc == optind)
	436	return usage(argv);
	437
	438	sinit();
	439
	440	rb_root = RB_ROOT;
	441	rb_lock = fio_mutex_init(FIO_MUTEX_UNLOCKED);
	442
	443	ret = dedupe_check(argv[optind]);
	444
	445	iter_rb_tree();
	446
	447	scleanup();
	448	return ret;
	449	}