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