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 <%lu>\n", filename, 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], c->count);
 382         flist_for_each(n, &c->extent_list) {
 383                 e = flist_entry(n, struct extent, list);
 384                 printf("\toffset %lu\n", 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", nextents, 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 }