sbin/hammer/cmd_dedup.c

   1 /*
   2  * Copyright (c) 2010 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Ilya Dryomov <idryomov@gmail.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include "hammer.h"
  36 #include <libutil.h>
  37 #include <crypto/sha2/sha2.h>
  38
  39 #define DEDUP_BUF (64 * 1024)
  40
  41 /* Sorted list of block CRCs - light version for dedup-simulate */
  42 struct sim_dedup_entry_rb_tree;
  43 RB_HEAD(sim_dedup_entry_rb_tree, sim_dedup_entry) sim_dedup_tree =
  44                                         RB_INITIALIZER(&sim_dedup_tree);
  45 RB_PROTOTYPE2(sim_dedup_entry_rb_tree, sim_dedup_entry, rb_entry,
  46                 rb_sim_dedup_entry_compare, hammer_crc_t);
  47
  48 struct sim_dedup_entry {
  49         hammer_crc_t    crc;
  50         u_int64_t       ref_blks; /* number of blocks referenced */
  51         u_int64_t       ref_size; /* size of data referenced */
  52         RB_ENTRY(sim_dedup_entry) rb_entry;
  53 };
  54
  55 struct dedup_entry {
  56         struct hammer_btree_leaf_elm leaf;
  57         union {
  58                 struct {
  59                         u_int64_t ref_blks;
  60                         u_int64_t ref_size;
  61                 } de;
  62                 RB_HEAD(sha_dedup_entry_rb_tree, sha_dedup_entry) fict_root;
  63         } u;
  64         u_int8_t flags;
  65         RB_ENTRY(dedup_entry) rb_entry;
  66 };
  67
  68 #define HAMMER_DEDUP_ENTRY_FICTITIOUS   0x0001
  69
  70 struct sha_dedup_entry {
  71         struct hammer_btree_leaf_elm    leaf;
  72         u_int64_t                       ref_blks;
  73         u_int64_t                       ref_size;
  74         u_int8_t                        sha_hash[SHA256_DIGEST_LENGTH];
  75         RB_ENTRY(sha_dedup_entry)       fict_entry;
  76 };
  77
  78 /* Sorted list of HAMMER B-Tree keys */
  79 struct dedup_entry_rb_tree;
  80 struct sha_dedup_entry_rb_tree;
  81
  82 RB_HEAD(dedup_entry_rb_tree, dedup_entry) dedup_tree =
  83                                         RB_INITIALIZER(&dedup_tree);
  84 RB_PROTOTYPE2(dedup_entry_rb_tree, dedup_entry, rb_entry,
  85                 rb_dedup_entry_compare, hammer_crc_t);
  86
  87 RB_PROTOTYPE(sha_dedup_entry_rb_tree, sha_dedup_entry, fict_entry,
  88                 rb_sha_dedup_entry_compare);
  89
  90 /*
  91  * Pass2 list - contains entries that were not dedup'ed because ioctl failed
  92  */
  93 STAILQ_HEAD(, pass2_dedup_entry) pass2_dedup_queue =
  94                                 STAILQ_HEAD_INITIALIZER(pass2_dedup_queue);
  95
  96 struct pass2_dedup_entry {
  97         struct hammer_btree_leaf_elm    leaf;
  98         STAILQ_ENTRY(pass2_dedup_entry) sq_entry;
  99 };
 100
 101 #define DEDUP_PASS2     0x0001 /* process_btree_elm() mode */
 102
 103 static int SigInfoFlag;
 104 static int64_t DedupDataReads;
 105 static int64_t DedupCurrentRecords;
 106 static int64_t DedupTotalRecords;
 107 static u_int32_t DedupCrcStart;
 108 static u_int32_t DedupCrcEnd;
 109 static u_int64_t MemoryUse;
 110
 111 /* PFS global ids - we deal with just one PFS at a run */
 112 int glob_fd;
 113 struct hammer_ioc_pseudofs_rw glob_pfs;
 114
 115 /*
 116  * Global accounting variables
 117  *
 118  * Last three don't have to be 64-bit, just to be safe..
 119  */
 120 u_int64_t dedup_alloc_size = 0;
 121 u_int64_t dedup_ref_size = 0;
 122 u_int64_t dedup_skipped_size = 0;
 123 u_int64_t dedup_crc_failures = 0;
 124 u_int64_t dedup_sha_failures = 0;
 125 u_int64_t dedup_underflows = 0;
 126 u_int64_t dedup_successes_count = 0;
 127 u_int64_t dedup_successes_bytes = 0;
 128
 129 static int rb_sim_dedup_entry_compare(struct sim_dedup_entry *sim_de1,
 130                                 struct sim_dedup_entry *sim_de2);
 131 static int rb_dedup_entry_compare(struct dedup_entry *de1,
 132                                 struct dedup_entry *de2);
 133 static int rb_sha_dedup_entry_compare(struct sha_dedup_entry *sha_de1,
 134                                 struct sha_dedup_entry *sha_de2);
 135 typedef int (*scan_pfs_cb_t)(hammer_btree_leaf_elm_t scan_leaf, int flags);
 136 static void scan_pfs(char *filesystem, scan_pfs_cb_t func, const char *id);
 137 static int collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags);
 138 static int count_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags);
 139 static int process_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags);
 140 static int upgrade_chksum(hammer_btree_leaf_elm_t leaf, u_int8_t *sha_hash);
 141 static void dump_simulated_dedup(void);
 142 static void dump_real_dedup(void);
 143 static void dedup_usage(int code);
 144
 145 RB_GENERATE2(sim_dedup_entry_rb_tree, sim_dedup_entry, rb_entry,
 146                 rb_sim_dedup_entry_compare, hammer_crc_t, crc);
 147 RB_GENERATE2(dedup_entry_rb_tree, dedup_entry, rb_entry,
 148                 rb_dedup_entry_compare, hammer_crc_t, leaf.data_crc);
 149 RB_GENERATE(sha_dedup_entry_rb_tree, sha_dedup_entry, fict_entry,
 150                 rb_sha_dedup_entry_compare);
 151
 152 static int
 153 rb_sim_dedup_entry_compare(struct sim_dedup_entry *sim_de1,
 154                         struct sim_dedup_entry *sim_de2)
 155 {
 156         if (sim_de1->crc < sim_de2->crc)
 157                 return (-1);
 158         if (sim_de1->crc > sim_de2->crc)
 159                 return (1);
 160
 161         return (0);
 162 }
 163
 164 static int
 165 rb_dedup_entry_compare(struct dedup_entry *de1, struct dedup_entry *de2)
 166 {
 167         if (de1->leaf.data_crc < de2->leaf.data_crc)
 168                 return (-1);
 169         if (de1->leaf.data_crc > de2->leaf.data_crc)
 170                 return (1);
 171
 172         return (0);
 173 }
 174
 175 static int
 176 rb_sha_dedup_entry_compare(struct sha_dedup_entry *sha_de1,
 177                         struct sha_dedup_entry *sha_de2)
 178 {
 179         unsigned long *h1 = (unsigned long *)&sha_de1->sha_hash;
 180         unsigned long *h2 = (unsigned long *)&sha_de2->sha_hash;
 181         int i;
 182
 183         for (i = 0; i < SHA256_DIGEST_LENGTH / (int)sizeof(unsigned long); ++i) {
 184                 if (h1[i] < h2[i])
 185                         return (-1);
 186                 if (h1[i] > h2[i])
 187                         return (1);
 188         }
 189
 190         return (0);
 191 }
 192
 193 /*
 194  * dedup-simulate <filesystem>
 195  */
 196 void
 197 hammer_cmd_dedup_simulate(char **av, int ac)
 198 {
 199         struct sim_dedup_entry *sim_de;
 200
 201         if (ac != 1)
 202                 dedup_usage(1);
 203
 204         glob_fd = getpfs(&glob_pfs, av[0]);
 205
 206         /*
 207          * Collection passes (memory limited)
 208          */
 209         printf("Dedup-simulate running\n");
 210         do {
 211                 DedupCrcStart = DedupCrcEnd;
 212                 DedupCrcEnd = 0;
 213                 MemoryUse = 0;
 214
 215                 if (VerboseOpt) {
 216                         printf("b-tree pass  crc-range %08x-max\n",
 217                                 DedupCrcStart);
 218                         fflush(stdout);
 219                 }
 220                 scan_pfs(av[0], collect_btree_elm, "simu-pass");
 221
 222                 if (VerboseOpt >= 2)
 223                         dump_simulated_dedup();
 224
 225                 /*
 226                  * Calculate simulated dedup ratio and get rid of the tree
 227                  */
 228                 while ((sim_de = RB_ROOT(&sim_dedup_tree)) != NULL) {
 229                         assert(sim_de->ref_blks != 0);
 230                         dedup_ref_size += sim_de->ref_size;
 231                         dedup_alloc_size += sim_de->ref_size / sim_de->ref_blks;
 232
 233                         RB_REMOVE(sim_dedup_entry_rb_tree, &sim_dedup_tree, sim_de);
 234                         free(sim_de);
 235                 }
 236                 if (DedupCrcEnd && VerboseOpt == 0)
 237                         printf(".");
 238         } while (DedupCrcEnd);
 239
 240         printf("Dedup-simulate %s succeeded\n", av[0]);
 241         relpfs(glob_fd, &glob_pfs);
 242
 243         printf("Simulated dedup ratio = %.2f\n",
 244             (dedup_alloc_size != 0) ?
 245                 (double)dedup_ref_size / dedup_alloc_size : 0);
 246 }
 247
 248 /*
 249  * dedup <filesystem>
 250  */
 251 void
 252 hammer_cmd_dedup(char **av, int ac)
 253 {
 254         struct dedup_entry *de;
 255         struct sha_dedup_entry *sha_de;
 256         struct pass2_dedup_entry *pass2_de;
 257         char buf[8];
 258
 259         if (TimeoutOpt > 0)
 260                 alarm(TimeoutOpt);
 261
 262         if (ac != 1)
 263                 dedup_usage(1);
 264
 265         STAILQ_INIT(&pass2_dedup_queue);
 266
 267         glob_fd = getpfs(&glob_pfs, av[0]);
 268
 269         /*
 270          * Pre-pass to cache the btree
 271          */
 272         scan_pfs(av[0], count_btree_elm, "pre-pass ");
 273         DedupTotalRecords = DedupCurrentRecords;
 274
 275         /*
 276          * Collection passes (memory limited)
 277          */
 278         printf("Dedup running\n");
 279         do {
 280                 DedupCrcStart = DedupCrcEnd;
 281                 DedupCrcEnd = 0;
 282                 MemoryUse = 0;
 283
 284                 if (VerboseOpt) {
 285                         printf("b-tree pass  crc-range %08x-max\n",
 286                                 DedupCrcStart);
 287                         fflush(stdout);
 288                 }
 289                 scan_pfs(av[0], process_btree_elm, "main-pass");
 290
 291                 while ((pass2_de = STAILQ_FIRST(&pass2_dedup_queue)) != NULL) {
 292                         if (process_btree_elm(&pass2_de->leaf, DEDUP_PASS2))
 293                                 dedup_skipped_size -= pass2_de->leaf.data_len;
 294
 295                         STAILQ_REMOVE_HEAD(&pass2_dedup_queue, sq_entry);
 296                         free(pass2_de);
 297                 }
 298                 assert(STAILQ_EMPTY(&pass2_dedup_queue));
 299
 300                 if (VerboseOpt >= 2)
 301                         dump_real_dedup();
 302
 303                 /*
 304                  * Calculate dedup ratio and get rid of the trees
 305                  */
 306                 while ((de = RB_ROOT(&dedup_tree)) != NULL) {
 307                         if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
 308                                 while ((sha_de = RB_ROOT(&de->u.fict_root)) != NULL) {
 309                                         assert(sha_de->ref_blks != 0);
 310                                         dedup_ref_size += sha_de->ref_size;
 311                                         dedup_alloc_size += sha_de->ref_size / sha_de->ref_blks;
 312
 313                                         RB_REMOVE(sha_dedup_entry_rb_tree,
 314                                                         &de->u.fict_root, sha_de);
 315                                         free(sha_de);
 316                                 }
 317                                 assert(RB_EMPTY(&de->u.fict_root));
 318                         } else {
 319                                 assert(de->u.de.ref_blks != 0);
 320                                 dedup_ref_size += de->u.de.ref_size;
 321                                 dedup_alloc_size += de->u.de.ref_size / de->u.de.ref_blks;
 322                         }
 323
 324                         RB_REMOVE(dedup_entry_rb_tree, &dedup_tree, de);
 325                         free(de);
 326                 }
 327                 assert(RB_EMPTY(&dedup_tree));
 328                 if (DedupCrcEnd && VerboseOpt == 0)
 329                         printf(".");
 330         } while (DedupCrcEnd);
 331
 332         printf("Dedup %s succeeded\n", av[0]);
 333         relpfs(glob_fd, &glob_pfs);
 334
 335         humanize_unsigned(buf, sizeof(buf), dedup_ref_size, "B", 1024);
 336         printf("Dedup ratio = %.2f\n"
 337                "    %8s referenced\n",
 338                ((dedup_alloc_size != 0) ?
 339                         (double)dedup_ref_size / dedup_alloc_size : 0),
 340                buf
 341         );
 342         humanize_unsigned(buf, sizeof(buf), dedup_alloc_size, "B", 1024);
 343         printf("    %8s allocated\n", buf);
 344         humanize_unsigned(buf, sizeof(buf), dedup_skipped_size, "B", 1024);
 345         printf("    %8s skipped\n", buf);
 346         printf("    %8jd CRC collisions\n"
 347                "    %8jd SHA collisions\n"
 348                "    %8jd bigblock underflows\n"
 349                "    %8jd new dedup records\n"
 350                "    %8jd new dedup bytes\n",
 351                (intmax_t)dedup_crc_failures,
 352                (intmax_t)dedup_sha_failures,
 353                (intmax_t)dedup_underflows,
 354                (intmax_t)dedup_successes_count,
 355                (intmax_t)dedup_successes_bytes
 356         );
 357 }
 358
 359 static int
 360 count_btree_elm(hammer_btree_leaf_elm_t scan_leaf __unused, int flags __unused)
 361 {
 362         return(1);
 363 }
 364
 365 static int
 366 collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags __unused)
 367 {
 368         struct sim_dedup_entry *sim_de;
 369
 370         /*
 371          * If we are using too much memory we have to clean some out, which
 372          * will cause the run to use multiple passes.  Be careful of integer
 373          * overflows!
 374          */
 375         if (MemoryUse > MemoryLimit) {
 376                 DedupCrcEnd = DedupCrcStart +
 377                               (u_int32_t)(DedupCrcEnd - DedupCrcStart - 1) / 2;
 378                 if (VerboseOpt) {
 379                         printf("memory limit  crc-range %08x-%08x\n",
 380                                 DedupCrcStart, DedupCrcEnd);
 381                         fflush(stdout);
 382                 }
 383                 for (;;) {
 384                         sim_de = RB_MAX(sim_dedup_entry_rb_tree,
 385                                         &sim_dedup_tree);
 386                         if (sim_de == NULL || sim_de->crc < DedupCrcEnd)
 387                                 break;
 388                         RB_REMOVE(sim_dedup_entry_rb_tree,
 389                                   &sim_dedup_tree, sim_de);
 390                         MemoryUse -= sizeof(*sim_de);
 391                         free(sim_de);
 392                 }
 393         }
 394
 395         /*
 396          * Collect statistics based on the CRC only, do not try to read
 397          * any data blocks or run SHA hashes.
 398          */
 399         sim_de = RB_LOOKUP(sim_dedup_entry_rb_tree, &sim_dedup_tree,
 400                            scan_leaf->data_crc);
 401
 402         if (sim_de == NULL) {
 403                 sim_de = calloc(sizeof(*sim_de), 1);
 404                 sim_de->crc = scan_leaf->data_crc;
 405                 RB_INSERT(sim_dedup_entry_rb_tree, &sim_dedup_tree, sim_de);
 406                 MemoryUse += sizeof(*sim_de);
 407         }
 408
 409         sim_de->ref_blks += 1;
 410         sim_de->ref_size += scan_leaf->data_len;
 411         return (1);
 412 }
 413
 414 static __inline int
 415 validate_dedup_pair(hammer_btree_leaf_elm_t p, hammer_btree_leaf_elm_t q)
 416 {
 417         if ((p->data_offset & HAMMER_OFF_ZONE_MASK) !=
 418             (q->data_offset & HAMMER_OFF_ZONE_MASK)) {
 419                 return (1);
 420         }
 421         if (p->data_len != q->data_len) {
 422                 return (1);
 423         }
 424
 425         return (0);
 426 }
 427
 428 #define DEDUP_TECH_FAILURE      1
 429 #define DEDUP_CMP_FAILURE       2
 430 #define DEDUP_INVALID_ZONE      3
 431 #define DEDUP_UNDERFLOW         4
 432 #define DEDUP_VERS_FAILURE      5
 433
 434 static __inline int
 435 deduplicate(hammer_btree_leaf_elm_t p, hammer_btree_leaf_elm_t q)
 436 {
 437         struct hammer_ioc_dedup dedup;
 438
 439         bzero(&dedup, sizeof(dedup));
 440
 441         /*
 442          * If data_offset fields are the same there is no need to run ioctl,
 443          * candidate is already dedup'ed.
 444          */
 445         if (p->data_offset == q->data_offset) {
 446                 return (0);
 447         }
 448
 449         dedup.elm1 = p->base;
 450         dedup.elm2 = q->base;
 451         RunningIoctl = 1;
 452         if (ioctl(glob_fd, HAMMERIOC_DEDUP, &dedup) < 0) {
 453                 if (errno == EOPNOTSUPP) {
 454                         /* must be at least version 5 */
 455                         return (DEDUP_VERS_FAILURE);
 456                 }
 457                 /* Technical failure - locking or w/e */
 458                 return (DEDUP_TECH_FAILURE);
 459         }
 460         if (dedup.head.flags & HAMMER_IOC_DEDUP_CMP_FAILURE) {
 461                 return (DEDUP_CMP_FAILURE);
 462         }
 463         if (dedup.head.flags & HAMMER_IOC_DEDUP_INVALID_ZONE) {
 464                 return (DEDUP_INVALID_ZONE);
 465         }
 466         if (dedup.head.flags & HAMMER_IOC_DEDUP_UNDERFLOW) {
 467                 return (DEDUP_UNDERFLOW);
 468         }
 469         RunningIoctl = 0;
 470         ++dedup_successes_count;
 471         dedup_successes_bytes += p->data_len;
 472         return (0);
 473 }
 474
 475 static int
 476 process_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags)
 477 {
 478         struct dedup_entry *de;
 479         struct sha_dedup_entry *sha_de, temp;
 480         struct pass2_dedup_entry *pass2_de;
 481         int error;
 482
 483         /*
 484          * If we are using too much memory we have to clean some out, which
 485          * will cause the run to use multiple passes.  Be careful of integer
 486          * overflows!
 487          */
 488         while (MemoryUse > MemoryLimit) {
 489                 DedupCrcEnd = DedupCrcStart +
 490                               (u_int32_t)(DedupCrcEnd - DedupCrcStart - 1) / 2;
 491                 if (VerboseOpt) {
 492                         printf("memory limit  crc-range %08x-%08x\n",
 493                                 DedupCrcStart, DedupCrcEnd);
 494                         fflush(stdout);
 495                 }
 496
 497                 for (;;) {
 498                         de = RB_MAX(dedup_entry_rb_tree, &dedup_tree);
 499                         if (de == NULL || de->leaf.data_crc < DedupCrcEnd)
 500                                 break;
 501                         if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
 502                                 while ((sha_de = RB_ROOT(&de->u.fict_root)) !=
 503                                        NULL) {
 504                                         RB_REMOVE(sha_dedup_entry_rb_tree,
 505                                                   &de->u.fict_root, sha_de);
 506                                         MemoryUse -= sizeof(*sha_de);
 507                                         free(sha_de);
 508                                 }
 509                         }
 510                         RB_REMOVE(dedup_entry_rb_tree, &dedup_tree, de);
 511                         MemoryUse -= sizeof(*de);
 512                         free(de);
 513                 }
 514         }
 515
 516         /*
 517          * Collect statistics based on the CRC.  Colliding CRCs usually
 518          * cause a SHA sub-tree to be created under the de.
 519          *
 520          * Trivial case if de not found.
 521          */
 522         de = RB_LOOKUP(dedup_entry_rb_tree, &dedup_tree, scan_leaf->data_crc);
 523         if (de == NULL) {
 524                 de = calloc(sizeof(*de), 1);
 525                 de->leaf = *scan_leaf;
 526                 RB_INSERT(dedup_entry_rb_tree, &dedup_tree, de);
 527                 MemoryUse += sizeof(*de);
 528                 goto upgrade_stats;
 529         }
 530
 531         /*
 532          * Found entry in CRC tree
 533          */
 534         if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
 535                 /*
 536                  * Optimize the case where a CRC failure results in multiple
 537                  * SHA entries.  If we unconditionally issue a data-read a
 538                  * degenerate situation where a colliding CRC's second SHA
 539                  * entry contains the lion's share of the deduplication
 540                  * candidates will result in excessive data block reads.
 541                  *
 542                  * Deal with the degenerate case by looking for a matching
 543                  * data_offset/data_len in the SHA elements we already have
 544                  * before reading the data block and generating a new SHA.
 545                  */
 546                 RB_FOREACH(sha_de, sha_dedup_entry_rb_tree, &de->u.fict_root) {
 547                         if (sha_de->leaf.data_offset ==
 548                                                 scan_leaf->data_offset &&
 549                             sha_de->leaf.data_len == scan_leaf->data_len) {
 550                                 memcpy(temp.sha_hash, sha_de->sha_hash,
 551                                         SHA256_DIGEST_LENGTH);
 552                                 break;
 553                         }
 554                 }
 555
 556                 /*
 557                  * Entry in CRC tree is fictitious, so we already had problems
 558                  * with this CRC. Upgrade (compute SHA) the candidate and
 559                  * dive into SHA subtree. If upgrade fails insert the candidate
 560                  * into Pass2 list (it will be processed later).
 561                  */
 562                 if (sha_de == NULL) {
 563                         if (upgrade_chksum(scan_leaf, temp.sha_hash))
 564                                 goto pass2_insert;
 565
 566                         sha_de = RB_FIND(sha_dedup_entry_rb_tree,
 567                                          &de->u.fict_root, &temp);
 568                 }
 569
 570                 /*
 571                  * Nothing in SHA subtree so far, so this is a new
 572                  * 'dataset'. Insert new entry into SHA subtree.
 573                  */
 574                 if (sha_de == NULL) {
 575                         sha_de = calloc(sizeof(*sha_de), 1);
 576                         sha_de->leaf = *scan_leaf;
 577                         memcpy(sha_de->sha_hash, temp.sha_hash,
 578                                SHA256_DIGEST_LENGTH);
 579                         RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root,
 580                                   sha_de);
 581                         MemoryUse += sizeof(*sha_de);
 582                         goto upgrade_stats_sha;
 583                 }
 584
 585                 /*
 586                  * Found entry in SHA subtree, it means we have a potential
 587                  * dedup pair. Validate it (zones have to match and data_len
 588                  * field have to be the same too. If validation fails, treat
 589                  * it as a SHA collision (jump to sha256_failure).
 590                  */
 591                 if (validate_dedup_pair(&sha_de->leaf, scan_leaf))
 592                         goto sha256_failure;
 593
 594                 /*
 595                  * We have a valid dedup pair (SHA match, validated).
 596                  *
 597                  * In case of technical failure (dedup pair was good, but
 598                  * ioctl failed anyways) insert the candidate into Pass2 list
 599                  * (we will try to dedup it after we are done with the rest of
 600                  * the tree).
 601                  *
 602                  * If ioctl fails because either of blocks is in the non-dedup
 603                  * zone (we can dedup only in LARGE_DATA and SMALL_DATA) don't
 604                  * bother with the candidate and terminate early.
 605                  *
 606                  * If ioctl fails because of bigblock underflow replace the
 607                  * leaf node that found dedup entry represents with scan_leaf.
 608                  */
 609                 error = deduplicate(&sha_de->leaf, scan_leaf);
 610                 switch(error) {
 611                 case 0:
 612                         goto upgrade_stats_sha;
 613                 case DEDUP_TECH_FAILURE:
 614                         goto pass2_insert;
 615                 case DEDUP_CMP_FAILURE:
 616                         goto sha256_failure;
 617                 case DEDUP_INVALID_ZONE:
 618                         goto terminate_early;
 619                 case DEDUP_UNDERFLOW:
 620                         ++dedup_underflows;
 621                         sha_de->leaf = *scan_leaf;
 622                         memcpy(sha_de->sha_hash, temp.sha_hash,
 623                                 SHA256_DIGEST_LENGTH);
 624                         goto upgrade_stats_sha;
 625                 case DEDUP_VERS_FAILURE:
 626                         fprintf(stderr,
 627                                 "HAMMER filesystem must be at least "
 628                                 "version 5 to dedup\n");
 629                         exit (1);
 630                 default:
 631                         fprintf(stderr, "Unknown error\n");
 632                         goto terminate_early;
 633                 }
 634
 635                 /*
 636                  * Ooh la la.. SHA-256 collision. Terminate early, there's
 637                  * nothing we can do here.
 638                  */
 639 sha256_failure:
 640                 ++dedup_sha_failures;
 641                 goto terminate_early;
 642         } else {
 643                 /*
 644                  * Candidate CRC is good for now (we found an entry in CRC
 645                  * tree and it's not fictitious). This means we have a
 646                  * potential dedup pair.
 647                  */
 648                 if (validate_dedup_pair(&de->leaf, scan_leaf))
 649                         goto crc_failure;
 650
 651                 /*
 652                  * We have a valid dedup pair (CRC match, validated)
 653                  */
 654                 error = deduplicate(&de->leaf, scan_leaf);
 655                 switch(error) {
 656                 case 0:
 657                         goto upgrade_stats;
 658                 case DEDUP_TECH_FAILURE:
 659                         goto pass2_insert;
 660                 case DEDUP_CMP_FAILURE:
 661                         goto crc_failure;
 662                 case DEDUP_INVALID_ZONE:
 663                         goto terminate_early;
 664                 case DEDUP_UNDERFLOW:
 665                         ++dedup_underflows;
 666                         de->leaf = *scan_leaf;
 667                         goto upgrade_stats;
 668                 case DEDUP_VERS_FAILURE:
 669                         fprintf(stderr,
 670                                 "HAMMER filesystem must be at least "
 671                                 "version 5 to dedup\n");
 672                         exit (1);
 673                 default:
 674                         fprintf(stderr, "Unknown error\n");
 675                         goto terminate_early;
 676                 }
 677
 678 crc_failure:
 679                 /*
 680                  * We got a CRC collision - either ioctl failed because of
 681                  * the comparison failure or validation of the potential
 682                  * dedup pair went bad. In all cases insert both blocks
 683                  * into SHA subtree (this requires checksum upgrade) and mark
 684                  * entry that corresponds to this CRC in the CRC tree
 685                  * fictitious, so that all futher operations with this CRC go
 686                  * through SHA subtree.
 687                  */
 688                 ++dedup_crc_failures;
 689
 690                 /*
 691                  * Insert block that was represented by now fictitious dedup
 692                  * entry (create a new SHA entry and preserve stats of the
 693                  * old CRC one). If checksum upgrade fails insert the
 694                  * candidate into Pass2 list and return - keep both trees
 695                  * unmodified.
 696                  */
 697                 sha_de = calloc(sizeof(*sha_de), 1);
 698                 sha_de->leaf = de->leaf;
 699                 sha_de->ref_blks = de->u.de.ref_blks;
 700                 sha_de->ref_size = de->u.de.ref_size;
 701                 if (upgrade_chksum(&sha_de->leaf, sha_de->sha_hash)) {
 702                         free(sha_de);
 703                         goto pass2_insert;
 704                 }
 705                 MemoryUse += sizeof(*sha_de);
 706
 707                 RB_INIT(&de->u.fict_root);
 708                 /*
 709                  * Here we can insert without prior checking because the tree
 710                  * is empty at this point
 711                  */
 712                 RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de);
 713
 714                 /*
 715                  * Mark entry in CRC tree fictitious
 716                  */
 717                 de->flags |= HAMMER_DEDUP_ENTRY_FICTITIOUS;
 718
 719                 /*
 720                  * Upgrade checksum of the candidate and insert it into
 721                  * SHA subtree. If upgrade fails insert the candidate into
 722                  * Pass2 list.
 723                  */
 724                 if (upgrade_chksum(scan_leaf, temp.sha_hash)) {
 725                         goto pass2_insert;
 726                 }
 727                 sha_de = RB_FIND(sha_dedup_entry_rb_tree, &de->u.fict_root,
 728                                  &temp);
 729                 if (sha_de != NULL)
 730                         /* There is an entry with this SHA already, but the only
 731                          * RB-tree element at this point is that entry we just
 732                          * added. We know for sure these blocks are different
 733                          * (this is crc_failure branch) so treat it as SHA
 734                          * collision.
 735                          */
 736                         goto sha256_failure;
 737
 738                 sha_de = calloc(sizeof(*sha_de), 1);
 739                 sha_de->leaf = *scan_leaf;
 740                 memcpy(sha_de->sha_hash, temp.sha_hash, SHA256_DIGEST_LENGTH);
 741                 RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de);
 742                 MemoryUse += sizeof(*sha_de);
 743                 goto upgrade_stats_sha;
 744         }
 745
 746 upgrade_stats:
 747         de->u.de.ref_blks += 1;
 748         de->u.de.ref_size += scan_leaf->data_len;
 749         return (1);
 750
 751 upgrade_stats_sha:
 752         sha_de->ref_blks += 1;
 753         sha_de->ref_size += scan_leaf->data_len;
 754         return (1);
 755
 756 pass2_insert:
 757         /*
 758          * If in pass2 mode don't insert anything, fall through to
 759          * terminate_early
 760          */
 761         if ((flags & DEDUP_PASS2) == 0) {
 762                 pass2_de = calloc(sizeof(*pass2_de), 1);
 763                 pass2_de->leaf = *scan_leaf;
 764                 STAILQ_INSERT_TAIL(&pass2_dedup_queue, pass2_de, sq_entry);
 765                 dedup_skipped_size += scan_leaf->data_len;
 766                 return (1);
 767         }
 768
 769 terminate_early:
 770         /*
 771          * Early termination path. Fixup stats.
 772          */
 773         dedup_alloc_size += scan_leaf->data_len;
 774         dedup_ref_size += scan_leaf->data_len;
 775         return (0);
 776 }
 777
 778 static int
 779 upgrade_chksum(hammer_btree_leaf_elm_t leaf, u_int8_t *sha_hash)
 780 {
 781         struct hammer_ioc_data data;
 782         char *buf = malloc(DEDUP_BUF);
 783         SHA256_CTX ctx;
 784         int error;
 785
 786         bzero(&data, sizeof(data));
 787         data.elm = leaf->base;
 788         data.ubuf = buf;
 789         data.size = DEDUP_BUF;
 790
 791         error = 0;
 792         if (ioctl(glob_fd, HAMMERIOC_GET_DATA, &data) < 0) {
 793                 fprintf(stderr, "Get-data failed: %s\n", strerror(errno));
 794                 error = 1;
 795                 goto done;
 796         }
 797         DedupDataReads += leaf->data_len;
 798
 799         if (data.leaf.data_len != leaf->data_len) {
 800                 error = 1;
 801                 goto done;
 802         }
 803
 804         if (data.leaf.base.btype == HAMMER_BTREE_TYPE_RECORD &&
 805             data.leaf.base.rec_type == HAMMER_RECTYPE_DATA) {
 806                 SHA256_Init(&ctx);
 807                 SHA256_Update(&ctx, (void *)buf, data.leaf.data_len);
 808                 SHA256_Final(sha_hash, &ctx);
 809         }
 810
 811 done:
 812         free(buf);
 813         return (error);
 814 }
 815
 816 static void
 817 sigInfo(int signo __unused)
 818 {
 819         SigInfoFlag = 1;
 820 }
 821
 822 static void
 823 scan_pfs(char *filesystem, scan_pfs_cb_t func, const char *id)
 824 {
 825         struct hammer_ioc_mirror_rw mirror;
 826         hammer_ioc_mrecord_any_t mrec;
 827         struct hammer_btree_leaf_elm elm;
 828         char *buf = malloc(DEDUP_BUF);
 829         char buf1[8];
 830         char buf2[8];
 831         int offset, bytes;
 832
 833         SigInfoFlag = 0;
 834         DedupDataReads = 0;
 835         DedupCurrentRecords = 0;
 836         signal(SIGINFO, sigInfo);
 837
 838         bzero(&mirror, sizeof(mirror));
 839         hammer_key_beg_init(&mirror.key_beg);
 840         hammer_key_end_init(&mirror.key_end);
 841
 842         mirror.tid_beg = glob_pfs.ondisk->sync_beg_tid;
 843         mirror.tid_end = glob_pfs.ondisk->sync_end_tid;
 844         mirror.head.flags |= HAMMER_IOC_MIRROR_NODATA; /* we want only keys */
 845         mirror.ubuf = buf;
 846         mirror.size = DEDUP_BUF;
 847         mirror.pfs_id = glob_pfs.pfs_id;
 848         mirror.shared_uuid = glob_pfs.ondisk->shared_uuid;
 849
 850         if (VerboseOpt && DedupCrcStart == 0) {
 851                 printf("%s %s: objspace %016jx:%04x %016jx:%04x\n",
 852                         id, filesystem,
 853                         (uintmax_t)mirror.key_beg.obj_id,
 854                         mirror.key_beg.localization,
 855                         (uintmax_t)mirror.key_end.obj_id,
 856                         mirror.key_end.localization);
 857                 printf("%s %s: pfs_id %d\n",
 858                         id, filesystem, glob_pfs.pfs_id);
 859         }
 860         fflush(stdout);
 861         fflush(stderr);
 862
 863         do {
 864                 mirror.count = 0;
 865                 mirror.pfs_id = glob_pfs.pfs_id;
 866                 mirror.shared_uuid = glob_pfs.ondisk->shared_uuid;
 867                 if (ioctl(glob_fd, HAMMERIOC_MIRROR_READ, &mirror) < 0) {
 868                         fprintf(stderr, "Mirror-read %s failed: %s\n",
 869                                 filesystem, strerror(errno));
 870                         exit(1);
 871                 }
 872                 if (mirror.head.flags & HAMMER_IOC_HEAD_ERROR) {
 873                         fprintf(stderr, "Mirror-read %s fatal error %d\n",
 874                                 filesystem, mirror.head.error);
 875                         exit(1);
 876                 }
 877                 if (mirror.count) {
 878                         offset = 0;
 879                         while (offset < mirror.count) {
 880                                 mrec = (void *)((char *)buf + offset);
 881                                 bytes = HAMMER_HEAD_DOALIGN(mrec->head.rec_size);
 882                                 if (offset + bytes > mirror.count) {
 883                                         fprintf(stderr, "Misaligned record\n");
 884                                         exit(1);
 885                                 }
 886                                 assert((mrec->head.type &
 887                                        HAMMER_MRECF_TYPE_MASK) ==
 888                                        HAMMER_MREC_TYPE_REC);
 889                                 offset += bytes;
 890                                 elm = mrec->rec.leaf;
 891                                 if (elm.base.btype != HAMMER_BTREE_TYPE_RECORD)
 892                                         continue;
 893                                 if (elm.base.rec_type != HAMMER_RECTYPE_DATA)
 894                                         continue;
 895                                 ++DedupCurrentRecords;
 896                                 if (DedupCrcStart != DedupCrcEnd) {
 897                                         if (elm.data_crc < DedupCrcStart)
 898                                                 continue;
 899                                         if (DedupCrcEnd &&
 900                                             elm.data_crc >= DedupCrcEnd) {
 901                                                 continue;
 902                                         }
 903                                 }
 904                                 func(&elm, 0);
 905                         }
 906                 }
 907                 mirror.key_beg = mirror.key_cur;
 908                 if (DidInterrupt) {
 909                         fprintf(stderr, "Interrupted\n");
 910                         exit(1);
 911                 }
 912                 if (SigInfoFlag) {
 913                         if (DedupTotalRecords) {
 914                                 humanize_unsigned(buf1, sizeof(buf1),
 915                                                   DedupDataReads,
 916                                                   "B", 1024);
 917                                 humanize_unsigned(buf2, sizeof(buf2),
 918                                                   dedup_successes_bytes,
 919                                                   "B", 1024);
 920                                 fprintf(stderr, "%s count %7jd/%jd "
 921                                                 "(%02d.%02d%%) "
 922                                                 "ioread %s newddup %s\n",
 923                                         id,
 924                                         (intmax_t)DedupCurrentRecords,
 925                                         (intmax_t)DedupTotalRecords,
 926                                         (int)(DedupCurrentRecords * 100 /
 927                                                 DedupTotalRecords),
 928                                         (int)(DedupCurrentRecords * 10000 /
 929                                                 DedupTotalRecords % 100),
 930                                         buf1, buf2);
 931                         } else {
 932                                 fprintf(stderr, "%s count %-7jd\n",
 933                                         id,
 934                                         (intmax_t)DedupCurrentRecords);
 935                         }
 936                         SigInfoFlag = 0;
 937                 }
 938         } while (mirror.count != 0);
 939
 940         signal(SIGINFO, SIG_IGN);
 941
 942         free(buf);
 943 }
 944
 945 static void
 946 dump_simulated_dedup(void)
 947 {
 948         struct sim_dedup_entry *sim_de;
 949
 950         printf("=== Dumping simulated dedup entries:\n");
 951         RB_FOREACH(sim_de, sim_dedup_entry_rb_tree, &sim_dedup_tree) {
 952                 printf("\tcrc=%08x cnt=%ju size=%ju\n",
 953                         sim_de->crc,
 954                         (intmax_t)sim_de->ref_blks,
 955                         (intmax_t)sim_de->ref_size);
 956         }
 957         printf("end of dump ===\n");
 958 }
 959
 960 static void
 961 dump_real_dedup(void)
 962 {
 963         struct dedup_entry *de;
 964         struct sha_dedup_entry *sha_de;
 965         int i;
 966
 967         printf("=== Dumping dedup entries:\n");
 968         RB_FOREACH(de, dedup_entry_rb_tree, &dedup_tree) {
 969                 if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
 970                         printf("\tcrc=%08x fictitious\n", de->leaf.data_crc);
 971
 972                         RB_FOREACH(sha_de, sha_dedup_entry_rb_tree, &de->u.fict_root) {
 973                                 printf("\t\tcrc=%08x cnt=%ju size=%ju\n\t"
 974                                        "\t\tsha=",
 975                                        sha_de->leaf.data_crc,
 976                                        (intmax_t)sha_de->ref_blks,
 977                                        (intmax_t)sha_de->ref_size);
 978                                 for (i = 0; i < SHA256_DIGEST_LENGTH; ++i)
 979                                         printf("%02x", sha_de->sha_hash[i]);
 980                                 printf("\n");
 981                         }
 982                 } else {
 983                         printf("\tcrc=%08x cnt=%ju size=%ju\n",
 984                                de->leaf.data_crc,
 985                                (intmax_t)de->u.de.ref_blks,
 986                                (intmax_t)de->u.de.ref_size);
 987                 }
 988         }
 989         printf("end of dump ===\n");
 990 }
 991
 992 static void
 993 dedup_usage(int code)
 994 {
 995         fprintf(stderr,
 996                 "hammer dedup-simulate <filesystem>\n"
 997                 "hammer dedup <filesystem>\n"
 998         );
 999         exit(code);
1000 }