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,
11 #include <sys/types.h>
13 #include <sys/ioctl.h>
18 #include "../lib/rbtree.h"
22 #include "../smalloc.h"
23 #include "../minmax.h"
24 #include "../crc/md5.h"
25 #include "../memalign.h"
29 struct timeval *fio_tv = NULL;
30 unsigned int fio_debug = 0;
32 void __dprint(int type, const char *str, ...)
36 struct worker_thread {
48 struct flist_head list;
53 struct rb_node rb_node;
54 struct flist_head extent_list;
56 uint32_t hash[MD5_HASH_WORDS];
61 uint32_t hash[MD5_HASH_WORDS];
64 static struct rb_root rb_root;
65 static struct fio_mutex *rb_lock;
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;
74 static uint64_t total_size;
75 static uint64_t cur_offset;
76 static struct fio_mutex *size_lock;
80 static uint64_t get_size(int fd, struct stat *sb)
84 if (S_ISBLK(sb->st_mode)) {
85 if (ioctl(fd, BLKGETSIZE64, &ret) < 0) {
92 return (ret & ~((uint64_t)blocksize - 1));
95 static int get_work(uint64_t *offset, uint64_t *size)
100 fio_mutex_down(size_lock);
102 if (cur_offset < total_size) {
103 *offset = cur_offset;
104 this_chunk = min((uint64_t)chunk_size, total_size - cur_offset);
106 cur_offset += this_chunk;
110 fio_mutex_up(size_lock);
114 static int read_block(int fd, void *buf, off_t offset)
118 ret = pread(fd, buf, blocksize, offset);
124 else if (ret != blocksize) {
125 log_err("dedupe: short read on block\n");
132 static void add_item(struct chunk *c, struct item *i)
136 e = malloc(sizeof(*e));
137 e->offset = i->offset;
138 flist_add_tail(&e->list, &c->extent_list);
142 static int col_check(struct chunk *c, struct item *i)
148 cbuf = fio_memalign(blocksize, blocksize);
149 ibuf = fio_memalign(blocksize, blocksize);
151 e = flist_entry(c->extent_list.next, struct extent, list);
152 if (read_block(dev_fd, cbuf, e->offset))
155 if (read_block(dev_fd, ibuf, i->offset))
158 ret = memcmp(ibuf, cbuf, blocksize);
160 fio_memfree(cbuf, blocksize);
161 fio_memfree(ibuf, blocksize);
165 static void insert_chunk(struct item *i)
167 struct rb_node **p, *parent;
171 p = &rb_root.rb_node;
176 c = rb_entry(parent, struct chunk, rb_node);
177 diff = memcmp(i->hash, c->hash, sizeof(i->hash));
185 if (!collision_check)
188 fio_mutex_up(rb_lock);
189 ret = col_check(c, i);
190 fio_mutex_down(rb_lock);
199 c = malloc(sizeof(*c));
200 RB_CLEAR_NODE(&c->rb_node);
201 INIT_FLIST_HEAD(&c->extent_list);
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);
210 static void insert_chunks(struct item *items, unsigned int nitems)
214 fio_mutex_down(rb_lock);
216 for (i = 0; i < nitems; i++)
217 insert_chunk(&items[i]);
219 fio_mutex_up(rb_lock);
222 static void crc_buf(void *buf, uint32_t *hash)
224 struct fio_md5_ctx ctx = { .hash = hash };
227 fio_md5_update(&ctx, buf, blocksize);
231 static int do_work(struct worker_thread *thread, void *buf)
233 unsigned int nblocks, i;
235 int err = 0, nitems = 0;
238 nblocks = thread->size / blocksize;
239 offset = thread->cur_offset;
240 items = malloc(sizeof(*items) * nblocks);
242 for (i = 0; i < nblocks; i++) {
243 if (read_block(thread->fd, buf, offset))
245 items[i].offset = offset;
246 crc_buf(buf, items[i].hash);
251 insert_chunks(items, nitems);
252 thread->items += nitems;
257 static void *thread_fn(void *data)
259 struct worker_thread *thread = data;
262 buf = fio_memalign(blocksize, blocksize);
265 if (get_work(&thread->cur_offset, &thread->size)) {
269 if (do_work(thread, buf)) {
275 fio_memfree(buf, blocksize);
279 static int __dedupe_check(int fd, uint64_t dev_size)
281 struct worker_thread *threads;
282 unsigned long nitems;
285 total_size = dev_size;
287 size_lock = fio_mutex_init(FIO_MUTEX_UNLOCKED);
289 threads = malloc(num_threads * sizeof(struct worker_thread));
290 for (i = 0; i < num_threads; i++) {
292 threads[i].items = 0;
295 err = pthread_create(&threads[i].thread, NULL, thread_fn, &threads[i]);
297 log_err("fio: thread startup failed\n");
303 for (i = 0; i < num_threads; i++) {
305 pthread_join(threads[i].thread, &ret);
306 nitems += threads[i].items;
309 printf("Threads(%u): %lu items processed\n", num_threads, nitems);
311 fio_mutex_remove(size_lock);
315 static int dedupe_check(const char *filename)
325 dev_fd = open(filename, flags);
331 if (fstat(dev_fd, &sb) < 0) {
337 dev_size = get_size(dev_fd, &sb);
343 printf("Will check <%s>, size <%lu>\n", filename, dev_size);
345 return __dedupe_check(dev_fd, dev_size);
348 static void show_chunk(struct chunk *c)
350 struct flist_head *n;
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);
360 static void iter_rb_tree(void)
367 nchunks = nextents = 0;
369 n = rb_first(&rb_root);
376 c = rb_entry(n, struct chunk, rb_node);
378 nextents += c->count;
383 } while ((n = rb_next(n)) != NULL);
385 printf("Extents=%lu, Unique extents=%lu\n", nextents, nchunks);
386 printf("De-dupe factor: %3.2f\n", (double) nextents / (double) nchunks);
388 perc = 1.00 - ((double) nchunks / (double) nextents);
390 printf("Fio setting: dedupe_percentage=%u\n", (int) (perc + 0.50));
393 static int usage(char *argv[])
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");
405 int main(int argc, char *argv[])
409 while ((c = getopt(argc, argv, "b:t:d:o:c:")) != -1) {
412 blocksize = atoi(optarg);
415 num_threads = atoi(optarg);
418 dump_output = atoi(optarg);
421 odirect = atoi(optarg);
424 collision_check = atoi(optarg);
433 num_threads = cpus_online();
441 rb_lock = fio_mutex_init(FIO_MUTEX_UNLOCKED);
443 ret = dedupe_check(argv[optind]);