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 <libutil.h> 36 #include <crypto/sha2/sha2.h> 37 38 #include "hammer.h" 39 40 #define DEDUP_BUF (64 * 1024) 41 42 /* Sorted list of block CRCs - light version for dedup-simulate */ 43 struct sim_dedup_entry_rb_tree; 44 RB_HEAD(sim_dedup_entry_rb_tree, sim_dedup_entry) sim_dedup_tree = 45 RB_INITIALIZER(&sim_dedup_tree); 46 RB_PROTOTYPE2(sim_dedup_entry_rb_tree, sim_dedup_entry, rb_entry, 47 rb_sim_dedup_entry_compare, hammer_crc_t); 48 49 struct sim_dedup_entry { 50 hammer_crc_t crc; 51 uint64_t ref_blks; /* number of blocks referenced */ 52 uint64_t ref_size; /* size of data referenced */ 53 RB_ENTRY(sim_dedup_entry) rb_entry; 54 }; 55 56 struct dedup_entry { 57 struct hammer_btree_leaf_elm leaf; 58 union { 59 struct { 60 uint64_t ref_blks; 61 uint64_t ref_size; 62 } de; 63 RB_HEAD(sha_dedup_entry_rb_tree, sha_dedup_entry) fict_root; 64 } u; 65 uint8_t flags; 66 RB_ENTRY(dedup_entry) rb_entry; 67 }; 68 69 #define HAMMER_DEDUP_ENTRY_FICTITIOUS 0x0001 70 71 struct sha_dedup_entry { 72 struct hammer_btree_leaf_elm leaf; 73 uint64_t ref_blks; 74 uint64_t ref_size; 75 uint8_t sha_hash[SHA256_DIGEST_LENGTH]; 76 RB_ENTRY(sha_dedup_entry) fict_entry; 77 }; 78 79 /* Sorted list of HAMMER B-Tree keys */ 80 struct dedup_entry_rb_tree; 81 struct sha_dedup_entry_rb_tree; 82 83 RB_HEAD(dedup_entry_rb_tree, dedup_entry) dedup_tree = 84 RB_INITIALIZER(&dedup_tree); 85 RB_PROTOTYPE2(dedup_entry_rb_tree, dedup_entry, rb_entry, 86 rb_dedup_entry_compare, hammer_crc_t); 87 88 RB_PROTOTYPE(sha_dedup_entry_rb_tree, sha_dedup_entry, fict_entry, 89 rb_sha_dedup_entry_compare); 90 91 /* 92 * Pass2 list - contains entries that were not dedup'ed because ioctl failed 93 */ 94 STAILQ_HEAD(, pass2_dedup_entry) pass2_dedup_queue = 95 STAILQ_HEAD_INITIALIZER(pass2_dedup_queue); 96 97 struct pass2_dedup_entry { 98 struct hammer_btree_leaf_elm leaf; 99 STAILQ_ENTRY(pass2_dedup_entry) sq_entry; 100 }; 101 102 #define DEDUP_PASS2 0x0001 /* process_btree_elm() mode */ 103 104 static int SigInfoFlag; 105 static int SigAlrmFlag; 106 static int64_t DedupDataReads; 107 static int64_t DedupCurrentRecords; 108 static int64_t DedupTotalRecords; 109 static uint32_t DedupCrcStart; 110 static uint32_t DedupCrcEnd; 111 static uint64_t MemoryUse; 112 113 /* PFS global ids - we deal with just one PFS at a run */ 114 static int glob_fd; 115 static struct hammer_ioc_pseudofs_rw glob_pfs; 116 117 /* 118 * Global accounting variables 119 * 120 * Last three don't have to be 64-bit, just to be safe.. 121 */ 122 static uint64_t dedup_alloc_size; 123 static uint64_t dedup_ref_size; 124 static uint64_t dedup_skipped_size; 125 static uint64_t dedup_crc_failures; 126 static uint64_t dedup_sha_failures; 127 static uint64_t dedup_underflows; 128 static uint64_t dedup_successes_count; 129 static uint64_t dedup_successes_bytes; 130 131 static int rb_sim_dedup_entry_compare(struct sim_dedup_entry *sim_de1, 132 struct sim_dedup_entry *sim_de2); 133 static int rb_dedup_entry_compare(struct dedup_entry *de1, 134 struct dedup_entry *de2); 135 static int rb_sha_dedup_entry_compare(struct sha_dedup_entry *sha_de1, 136 struct sha_dedup_entry *sha_de2); 137 typedef int (*scan_pfs_cb_t)(hammer_btree_leaf_elm_t scan_leaf, int flags); 138 static void scan_pfs(char *filesystem, scan_pfs_cb_t func, const char *id); 139 static int collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags); 140 static int count_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags); 141 static int process_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags); 142 static int upgrade_chksum(hammer_btree_leaf_elm_t leaf, uint8_t *sha_hash); 143 static void dump_simulated_dedup(void); 144 static void dump_real_dedup(void); 145 static void dedup_usage(int code); 146 147 RB_GENERATE2(sim_dedup_entry_rb_tree, sim_dedup_entry, rb_entry, 148 rb_sim_dedup_entry_compare, hammer_crc_t, crc); 149 RB_GENERATE2(dedup_entry_rb_tree, dedup_entry, rb_entry, 150 rb_dedup_entry_compare, hammer_crc_t, leaf.data_crc); 151 RB_GENERATE(sha_dedup_entry_rb_tree, sha_dedup_entry, fict_entry, 152 rb_sha_dedup_entry_compare); 153 154 static int 155 rb_sim_dedup_entry_compare(struct sim_dedup_entry *sim_de1, 156 struct sim_dedup_entry *sim_de2) 157 { 158 if (sim_de1->crc < sim_de2->crc) 159 return (-1); 160 if (sim_de1->crc > sim_de2->crc) 161 return (1); 162 163 return (0); 164 } 165 166 static int 167 rb_dedup_entry_compare(struct dedup_entry *de1, struct dedup_entry *de2) 168 { 169 if (de1->leaf.data_crc < de2->leaf.data_crc) 170 return (-1); 171 if (de1->leaf.data_crc > de2->leaf.data_crc) 172 return (1); 173 174 return (0); 175 } 176 177 static int 178 rb_sha_dedup_entry_compare(struct sha_dedup_entry *sha_de1, 179 struct sha_dedup_entry *sha_de2) 180 { 181 unsigned long *h1 = (unsigned long *)&sha_de1->sha_hash; 182 unsigned long *h2 = (unsigned long *)&sha_de2->sha_hash; 183 int i; 184 185 for (i = 0; i < SHA256_DIGEST_LENGTH / (int)sizeof(unsigned long); ++i) { 186 if (h1[i] < h2[i]) 187 return (-1); 188 if (h1[i] > h2[i]) 189 return (1); 190 } 191 192 return (0); 193 } 194 195 /* 196 * dedup-simulate <filesystem> 197 */ 198 void 199 hammer_cmd_dedup_simulate(char **av, int ac) 200 { 201 struct sim_dedup_entry *sim_de; 202 203 if (ac != 1) 204 dedup_usage(1); 205 206 glob_fd = getpfs(&glob_pfs, av[0]); 207 208 /* 209 * Collection passes (memory limited) 210 */ 211 printf("Dedup-simulate running\n"); 212 do { 213 DedupCrcStart = DedupCrcEnd; 214 DedupCrcEnd = 0; 215 MemoryUse = 0; 216 217 if (VerboseOpt) { 218 printf("B-Tree pass crc-range %08x-max\n", 219 DedupCrcStart); 220 fflush(stdout); 221 } 222 scan_pfs(av[0], collect_btree_elm, "simu-pass"); 223 224 if (VerboseOpt >= 2) 225 dump_simulated_dedup(); 226 227 /* 228 * Calculate simulated dedup ratio and get rid of the tree 229 */ 230 while ((sim_de = RB_ROOT(&sim_dedup_tree)) != NULL) { 231 assert(sim_de->ref_blks != 0); 232 dedup_ref_size += sim_de->ref_size; 233 dedup_alloc_size += sim_de->ref_size / sim_de->ref_blks; 234 235 RB_REMOVE(sim_dedup_entry_rb_tree, &sim_dedup_tree, sim_de); 236 free(sim_de); 237 } 238 if (DedupCrcEnd && VerboseOpt == 0) 239 printf("."); 240 } while (DedupCrcEnd); 241 242 printf("Dedup-simulate %s succeeded\n", av[0]); 243 relpfs(glob_fd, &glob_pfs); 244 245 printf("Simulated dedup ratio = %.2f\n", 246 (dedup_alloc_size != 0) ? 247 (double)dedup_ref_size / dedup_alloc_size : 0); 248 } 249 250 /* 251 * dedup <filesystem> 252 */ 253 void 254 hammer_cmd_dedup(char **av, int ac) 255 { 256 struct dedup_entry *de; 257 struct sha_dedup_entry *sha_de; 258 struct pass2_dedup_entry *pass2_de; 259 char *tmp; 260 char buf[8]; 261 int needfree = 0; 262 263 if (TimeoutOpt > 0) 264 alarm(TimeoutOpt); 265 266 if (ac != 1) 267 dedup_usage(1); 268 269 STAILQ_INIT(&pass2_dedup_queue); 270 271 glob_fd = getpfs(&glob_pfs, av[0]); 272 273 /* 274 * A cycle file is _required_ for resuming dedup after the timeout 275 * specified with -t has expired. If no -c option, then place a 276 * .dedup.cycle file either in the PFS snapshots directory or in 277 * the default snapshots directory. 278 */ 279 if (!CyclePath) { 280 if (glob_pfs.ondisk->snapshots[0] != '/') 281 asprintf(&tmp, "%s/%s/.dedup.cycle", 282 SNAPSHOTS_BASE, av[0]); 283 else 284 asprintf(&tmp, "%s/.dedup.cycle", 285 glob_pfs.ondisk->snapshots); 286 CyclePath = tmp; 287 needfree = 1; 288 } 289 290 /* 291 * Pre-pass to cache the btree 292 */ 293 scan_pfs(av[0], count_btree_elm, "pre-pass "); 294 DedupTotalRecords = DedupCurrentRecords; 295 296 /* 297 * Collection passes (memory limited) 298 */ 299 printf("Dedup running\n"); 300 do { 301 DedupCrcStart = DedupCrcEnd; 302 DedupCrcEnd = 0; 303 MemoryUse = 0; 304 305 if (VerboseOpt) { 306 printf("B-Tree pass crc-range %08x-max\n", 307 DedupCrcStart); 308 fflush(stdout); 309 } 310 scan_pfs(av[0], process_btree_elm, "main-pass"); 311 312 while ((pass2_de = STAILQ_FIRST(&pass2_dedup_queue)) != NULL) { 313 if (process_btree_elm(&pass2_de->leaf, DEDUP_PASS2)) 314 dedup_skipped_size -= pass2_de->leaf.data_len; 315 316 STAILQ_REMOVE_HEAD(&pass2_dedup_queue, sq_entry); 317 free(pass2_de); 318 } 319 assert(STAILQ_EMPTY(&pass2_dedup_queue)); 320 321 if (VerboseOpt >= 2) 322 dump_real_dedup(); 323 324 /* 325 * Calculate dedup ratio and get rid of the trees 326 */ 327 while ((de = RB_ROOT(&dedup_tree)) != NULL) { 328 if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) { 329 while ((sha_de = RB_ROOT(&de->u.fict_root)) != NULL) { 330 assert(sha_de->ref_blks != 0); 331 dedup_ref_size += sha_de->ref_size; 332 dedup_alloc_size += sha_de->ref_size / sha_de->ref_blks; 333 334 RB_REMOVE(sha_dedup_entry_rb_tree, 335 &de->u.fict_root, sha_de); 336 free(sha_de); 337 } 338 assert(RB_EMPTY(&de->u.fict_root)); 339 } else { 340 assert(de->u.de.ref_blks != 0); 341 dedup_ref_size += de->u.de.ref_size; 342 dedup_alloc_size += de->u.de.ref_size / de->u.de.ref_blks; 343 } 344 345 RB_REMOVE(dedup_entry_rb_tree, &dedup_tree, de); 346 free(de); 347 } 348 assert(RB_EMPTY(&dedup_tree)); 349 if (DedupCrcEnd && VerboseOpt == 0) 350 printf("."); 351 } while (DedupCrcEnd); 352 353 printf("Dedup %s succeeded\n", av[0]); 354 relpfs(glob_fd, &glob_pfs); 355 356 humanize_unsigned(buf, sizeof(buf), dedup_ref_size, "B", 1024); 357 printf("Dedup ratio = %.2f (in this run)\n" 358 " %8s referenced\n", 359 ((dedup_alloc_size != 0) ? 360 (double)dedup_ref_size / dedup_alloc_size : 0), 361 buf 362 ); 363 humanize_unsigned(buf, sizeof(buf), dedup_alloc_size, "B", 1024); 364 printf(" %8s allocated\n", buf); 365 humanize_unsigned(buf, sizeof(buf), dedup_skipped_size, "B", 1024); 366 printf(" %8s skipped\n", buf); 367 printf(" %8jd CRC collisions\n" 368 " %8jd SHA collisions\n" 369 " %8jd big-block underflows\n" 370 " %8jd new dedup records\n" 371 " %8jd new dedup bytes\n", 372 (intmax_t)dedup_crc_failures, 373 (intmax_t)dedup_sha_failures, 374 (intmax_t)dedup_underflows, 375 (intmax_t)dedup_successes_count, 376 (intmax_t)dedup_successes_bytes 377 ); 378 379 /* Once completed remove cycle file */ 380 hammer_reset_cycle(); 381 382 /* We don't want to mess up with other directives */ 383 if (needfree) { 384 free(tmp); 385 CyclePath = NULL; 386 } 387 } 388 389 static int 390 count_btree_elm(hammer_btree_leaf_elm_t scan_leaf __unused, int flags __unused) 391 { 392 return(1); 393 } 394 395 static int 396 collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags __unused) 397 { 398 struct sim_dedup_entry *sim_de; 399 400 /* 401 * If we are using too much memory we have to clean some out, which 402 * will cause the run to use multiple passes. Be careful of integer 403 * overflows! 404 */ 405 if (MemoryUse > MemoryLimit) { 406 DedupCrcEnd = DedupCrcStart + 407 (uint32_t)(DedupCrcEnd - DedupCrcStart - 1) / 2; 408 if (VerboseOpt) { 409 printf("memory limit crc-range %08x-%08x\n", 410 DedupCrcStart, DedupCrcEnd); 411 fflush(stdout); 412 } 413 for (;;) { 414 sim_de = RB_MAX(sim_dedup_entry_rb_tree, 415 &sim_dedup_tree); 416 if (sim_de == NULL || sim_de->crc < DedupCrcEnd) 417 break; 418 RB_REMOVE(sim_dedup_entry_rb_tree, 419 &sim_dedup_tree, sim_de); 420 MemoryUse -= sizeof(*sim_de); 421 free(sim_de); 422 } 423 } 424 425 /* 426 * Collect statistics based on the CRC only, do not try to read 427 * any data blocks or run SHA hashes. 428 */ 429 sim_de = RB_LOOKUP(sim_dedup_entry_rb_tree, &sim_dedup_tree, 430 scan_leaf->data_crc); 431 432 if (sim_de == NULL) { 433 sim_de = calloc(1, sizeof(*sim_de)); 434 sim_de->crc = scan_leaf->data_crc; 435 RB_INSERT(sim_dedup_entry_rb_tree, &sim_dedup_tree, sim_de); 436 MemoryUse += sizeof(*sim_de); 437 } 438 439 sim_de->ref_blks += 1; 440 sim_de->ref_size += scan_leaf->data_len; 441 return (1); 442 } 443 444 static __inline int 445 validate_dedup_pair(hammer_btree_leaf_elm_t p, hammer_btree_leaf_elm_t q) 446 { 447 if (HAMMER_ZONE(p->data_offset) != HAMMER_ZONE(q->data_offset)) { 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 (uint32_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(1, sizeof(*de)); 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(1, sizeof(*sha_de)); 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 big-block 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 errx(1, "HAMMER filesystem must be at least " 656 "version 5 to dedup"); 657 default: 658 fprintf(stderr, "Unknown error\n"); 659 goto terminate_early; 660 } 661 662 /* 663 * Ooh la la.. SHA-256 collision. Terminate early, there's 664 * nothing we can do here. 665 */ 666 sha256_failure: 667 ++dedup_sha_failures; 668 goto terminate_early; 669 } else { 670 /* 671 * Candidate CRC is good for now (we found an entry in CRC 672 * tree and it's not fictitious). This means we have a 673 * potential dedup pair. 674 */ 675 if (validate_dedup_pair(&de->leaf, scan_leaf)) 676 goto crc_failure; 677 678 /* 679 * We have a valid dedup pair (CRC match, validated) 680 */ 681 error = deduplicate(&de->leaf, scan_leaf); 682 switch(error) { 683 case 0: 684 goto upgrade_stats; 685 case DEDUP_TECH_FAILURE: 686 goto pass2_insert; 687 case DEDUP_CMP_FAILURE: 688 goto crc_failure; 689 case DEDUP_INVALID_ZONE: 690 goto terminate_early; 691 case DEDUP_UNDERFLOW: 692 ++dedup_underflows; 693 de->leaf = *scan_leaf; 694 goto upgrade_stats; 695 case DEDUP_VERS_FAILURE: 696 errx(1, "HAMMER filesystem must be at least " 697 "version 5 to dedup"); 698 default: 699 fprintf(stderr, "Unknown error\n"); 700 goto terminate_early; 701 } 702 703 crc_failure: 704 /* 705 * We got a CRC collision - either ioctl failed because of 706 * the comparison failure or validation of the potential 707 * dedup pair went bad. In all cases insert both blocks 708 * into SHA subtree (this requires checksum upgrade) and mark 709 * entry that corresponds to this CRC in the CRC tree 710 * fictitious, so that all futher operations with this CRC go 711 * through SHA subtree. 712 */ 713 ++dedup_crc_failures; 714 715 /* 716 * Insert block that was represented by now fictitious dedup 717 * entry (create a new SHA entry and preserve stats of the 718 * old CRC one). If checksum upgrade fails insert the 719 * candidate into Pass2 list and return - keep both trees 720 * unmodified. 721 */ 722 sha_de = calloc(1, sizeof(*sha_de)); 723 sha_de->leaf = de->leaf; 724 sha_de->ref_blks = de->u.de.ref_blks; 725 sha_de->ref_size = de->u.de.ref_size; 726 if (upgrade_chksum(&sha_de->leaf, sha_de->sha_hash)) { 727 free(sha_de); 728 goto pass2_insert; 729 } 730 MemoryUse += sizeof(*sha_de); 731 732 RB_INIT(&de->u.fict_root); 733 /* 734 * Here we can insert without prior checking because the tree 735 * is empty at this point 736 */ 737 RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de); 738 739 /* 740 * Mark entry in CRC tree fictitious 741 */ 742 de->flags |= HAMMER_DEDUP_ENTRY_FICTITIOUS; 743 744 /* 745 * Upgrade checksum of the candidate and insert it into 746 * SHA subtree. If upgrade fails insert the candidate into 747 * Pass2 list. 748 */ 749 if (upgrade_chksum(scan_leaf, temp.sha_hash)) { 750 goto pass2_insert; 751 } 752 sha_de = RB_FIND(sha_dedup_entry_rb_tree, &de->u.fict_root, 753 &temp); 754 if (sha_de != NULL) 755 /* There is an entry with this SHA already, but the only 756 * RB-tree element at this point is that entry we just 757 * added. We know for sure these blocks are different 758 * (this is crc_failure branch) so treat it as SHA 759 * collision. 760 */ 761 goto sha256_failure; 762 763 sha_de = calloc(1, sizeof(*sha_de)); 764 sha_de->leaf = *scan_leaf; 765 memcpy(sha_de->sha_hash, temp.sha_hash, SHA256_DIGEST_LENGTH); 766 RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de); 767 MemoryUse += sizeof(*sha_de); 768 goto upgrade_stats_sha; 769 } 770 771 upgrade_stats: 772 de->u.de.ref_blks += 1; 773 de->u.de.ref_size += scan_leaf->data_len; 774 return (1); 775 776 upgrade_stats_sha: 777 sha_de->ref_blks += 1; 778 sha_de->ref_size += scan_leaf->data_len; 779 return (1); 780 781 pass2_insert: 782 /* 783 * If in pass2 mode don't insert anything, fall through to 784 * terminate_early 785 */ 786 if ((flags & DEDUP_PASS2) == 0) { 787 pass2_de = calloc(1, sizeof(*pass2_de)); 788 pass2_de->leaf = *scan_leaf; 789 STAILQ_INSERT_TAIL(&pass2_dedup_queue, pass2_de, sq_entry); 790 dedup_skipped_size += scan_leaf->data_len; 791 return (1); 792 } 793 794 terminate_early: 795 /* 796 * Early termination path. Fixup stats. 797 */ 798 dedup_alloc_size += scan_leaf->data_len; 799 dedup_ref_size += scan_leaf->data_len; 800 return (0); 801 } 802 803 static int 804 upgrade_chksum(hammer_btree_leaf_elm_t leaf, uint8_t *sha_hash) 805 { 806 struct hammer_ioc_data data; 807 char *buf = malloc(DEDUP_BUF); 808 SHA256_CTX ctx; 809 int error; 810 811 bzero(&data, sizeof(data)); 812 data.elm = leaf->base; 813 data.ubuf = buf; 814 data.size = DEDUP_BUF; 815 816 error = 0; 817 if (ioctl(glob_fd, HAMMERIOC_GET_DATA, &data) < 0) { 818 fprintf(stderr, "Get-data failed: %s\n", strerror(errno)); 819 error = 1; 820 goto done; 821 } 822 DedupDataReads += leaf->data_len; 823 824 if (data.leaf.data_len != leaf->data_len) { 825 error = 1; 826 goto done; 827 } 828 829 if (data.leaf.base.btype == HAMMER_BTREE_TYPE_RECORD && 830 data.leaf.base.rec_type == HAMMER_RECTYPE_DATA) { 831 SHA256_Init(&ctx); 832 SHA256_Update(&ctx, (void *)buf, data.leaf.data_len); 833 SHA256_Final(sha_hash, &ctx); 834 } 835 836 done: 837 free(buf); 838 return (error); 839 } 840 841 static void 842 sigAlrm(int signo __unused) 843 { 844 SigAlrmFlag = 1; 845 } 846 847 static void 848 sigInfo(int signo __unused) 849 { 850 SigInfoFlag = 1; 851 } 852 853 static void 854 scan_pfs(char *filesystem, scan_pfs_cb_t func, const char *id) 855 { 856 struct hammer_ioc_mirror_rw mirror; 857 hammer_ioc_mrecord_any_t mrec; 858 struct hammer_btree_leaf_elm elm; 859 char *buf = malloc(DEDUP_BUF); 860 char buf1[8]; 861 char buf2[8]; 862 int offset, bytes; 863 864 SigInfoFlag = 0; 865 DedupDataReads = 0; 866 DedupCurrentRecords = 0; 867 signal(SIGINFO, sigInfo); 868 signal(SIGALRM, sigAlrm); 869 870 /* 871 * Deduplication happens per element so hammer(8) is in full 872 * control of the ioctl()s to actually perform it. SIGALRM 873 * needs to be handled within hammer(8) but a checkpoint 874 * is needed for resuming. Use cycle file for that. 875 * 876 * Try to obtain the previous obj_id from the cycle file and 877 * if not available just start from the beginning. 878 */ 879 bzero(&mirror, sizeof(mirror)); 880 hammer_key_beg_init(&mirror.key_beg); 881 hammer_get_cycle(&mirror.key_beg, &mirror.tid_beg); 882 883 if (mirror.key_beg.obj_id != (int64_t)HAMMER_MIN_OBJID) { 884 if (VerboseOpt) 885 fprintf(stderr, "%s: mirror-read: Resuming at object %016jx\n", 886 id, (uintmax_t)mirror.key_beg.obj_id); 887 } 888 889 hammer_key_end_init(&mirror.key_end); 890 891 mirror.tid_beg = glob_pfs.ondisk->sync_beg_tid; 892 mirror.tid_end = glob_pfs.ondisk->sync_end_tid; 893 mirror.head.flags |= HAMMER_IOC_MIRROR_NODATA; /* we want only keys */ 894 mirror.ubuf = buf; 895 mirror.size = DEDUP_BUF; 896 mirror.pfs_id = glob_pfs.pfs_id; 897 mirror.shared_uuid = glob_pfs.ondisk->shared_uuid; 898 899 if (VerboseOpt && DedupCrcStart == 0) { 900 printf("%s %s: objspace %016jx:%04x %016jx:%04x\n", 901 id, filesystem, 902 (uintmax_t)mirror.key_beg.obj_id, 903 mirror.key_beg.localization, 904 (uintmax_t)mirror.key_end.obj_id, 905 mirror.key_end.localization); 906 printf("%s %s: pfs_id %d\n", 907 id, filesystem, glob_pfs.pfs_id); 908 } 909 fflush(stdout); 910 fflush(stderr); 911 912 do { 913 mirror.count = 0; 914 mirror.pfs_id = glob_pfs.pfs_id; 915 mirror.shared_uuid = glob_pfs.ondisk->shared_uuid; 916 if (ioctl(glob_fd, HAMMERIOC_MIRROR_READ, &mirror) < 0) 917 err(1, "Mirror-read %s failed", filesystem); 918 if (mirror.head.flags & HAMMER_IOC_HEAD_ERROR) 919 errx(1, "Mirror-read %s fatal error %d", 920 filesystem, mirror.head.error); 921 if (mirror.count) { 922 offset = 0; 923 while (offset < mirror.count) { 924 mrec = (void *)((char *)buf + offset); 925 bytes = HAMMER_HEAD_DOALIGN(mrec->head.rec_size); 926 if (offset + bytes > mirror.count) 927 errx(1, "Misaligned record"); 928 assert((mrec->head.type & 929 HAMMER_MRECF_TYPE_MASK) == 930 HAMMER_MREC_TYPE_REC); 931 offset += bytes; 932 elm = mrec->rec.leaf; 933 if (elm.base.btype != HAMMER_BTREE_TYPE_RECORD) 934 continue; 935 if (elm.base.rec_type != HAMMER_RECTYPE_DATA) 936 continue; 937 ++DedupCurrentRecords; 938 if (DedupCrcStart != DedupCrcEnd) { 939 if (elm.data_crc < DedupCrcStart) 940 continue; 941 if (DedupCrcEnd && 942 elm.data_crc >= DedupCrcEnd) { 943 continue; 944 } 945 } 946 func(&elm, 0); 947 } 948 } 949 mirror.key_beg = mirror.key_cur; 950 if (DidInterrupt || SigAlrmFlag) { 951 if (VerboseOpt) 952 fprintf(stderr, "%s\n", 953 (DidInterrupt ? "Interrupted" : "Timeout")); 954 hammer_set_cycle(&mirror.key_cur, mirror.tid_beg); 955 if (VerboseOpt) 956 fprintf(stderr, "Cyclefile %s updated for " 957 "continuation\n", CyclePath); 958 exit(1); 959 } 960 if (SigInfoFlag) { 961 if (DedupTotalRecords) { 962 humanize_unsigned(buf1, sizeof(buf1), 963 DedupDataReads, 964 "B", 1024); 965 humanize_unsigned(buf2, sizeof(buf2), 966 dedup_successes_bytes, 967 "B", 1024); 968 fprintf(stderr, "%s count %7jd/%jd " 969 "(%02d.%02d%%) " 970 "ioread %s newddup %s\n", 971 id, 972 (intmax_t)DedupCurrentRecords, 973 (intmax_t)DedupTotalRecords, 974 (int)(DedupCurrentRecords * 100 / 975 DedupTotalRecords), 976 (int)(DedupCurrentRecords * 10000 / 977 DedupTotalRecords % 100), 978 buf1, buf2); 979 } else { 980 fprintf(stderr, "%s count %-7jd\n", 981 id, 982 (intmax_t)DedupCurrentRecords); 983 } 984 SigInfoFlag = 0; 985 } 986 } while (mirror.count != 0); 987 988 signal(SIGINFO, SIG_IGN); 989 signal(SIGALRM, SIG_IGN); 990 991 free(buf); 992 } 993 994 static void 995 dump_simulated_dedup(void) 996 { 997 struct sim_dedup_entry *sim_de; 998 999 printf("=== Dumping simulated dedup entries:\n"); 1000 RB_FOREACH(sim_de, sim_dedup_entry_rb_tree, &sim_dedup_tree) { 1001 printf("\tcrc=%08x cnt=%ju size=%ju\n", 1002 sim_de->crc, 1003 (intmax_t)sim_de->ref_blks, 1004 (intmax_t)sim_de->ref_size); 1005 } 1006 printf("end of dump ===\n"); 1007 } 1008 1009 static void 1010 dump_real_dedup(void) 1011 { 1012 struct dedup_entry *de; 1013 struct sha_dedup_entry *sha_de; 1014 int i; 1015 1016 printf("=== Dumping dedup entries:\n"); 1017 RB_FOREACH(de, dedup_entry_rb_tree, &dedup_tree) { 1018 if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) { 1019 printf("\tcrc=%08x fictitious\n", de->leaf.data_crc); 1020 1021 RB_FOREACH(sha_de, sha_dedup_entry_rb_tree, &de->u.fict_root) { 1022 printf("\t\tcrc=%08x cnt=%ju size=%ju\n\t" 1023 "\t\tsha=", 1024 sha_de->leaf.data_crc, 1025 (intmax_t)sha_de->ref_blks, 1026 (intmax_t)sha_de->ref_size); 1027 for (i = 0; i < SHA256_DIGEST_LENGTH; ++i) 1028 printf("%02x", sha_de->sha_hash[i]); 1029 printf("\n"); 1030 } 1031 } else { 1032 printf("\tcrc=%08x cnt=%ju size=%ju\n", 1033 de->leaf.data_crc, 1034 (intmax_t)de->u.de.ref_blks, 1035 (intmax_t)de->u.de.ref_size); 1036 } 1037 } 1038 printf("end of dump ===\n"); 1039 } 1040 1041 static void 1042 dedup_usage(int code) 1043 { 1044 fprintf(stderr, 1045 "hammer dedup-simulate <filesystem>\n" 1046 "hammer dedup <filesystem>\n" 1047 ); 1048 exit(code); 1049 } 1050