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         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("Chunks=%lu, Extents=%lu\n", nchunks, nextents);
 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("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 }