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