sbin/hammer: Partly bring back removed braces from 52e2f1b5
[dragonfly.git] / sbin / hammer / cmd_dedup.c
blobc18ac3851fd425e2809302d7cc02caaf6c673610
1 /*
2 * Copyright (c) 2010 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Ilya Dryomov <idryomov@gmail.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
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.
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.
35 #include <libutil.h>
36 #include <crypto/sha2/sha2.h>
38 #include "hammer.h"
40 #define DEDUP_BUF (64 * 1024)
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);
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;
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;
69 #define HAMMER_DEDUP_ENTRY_FICTITIOUS 0x0001
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;
79 /* Sorted list of HAMMER B-Tree keys */
80 struct dedup_entry_rb_tree;
81 struct sha_dedup_entry_rb_tree;
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);
88 RB_PROTOTYPE(sha_dedup_entry_rb_tree, sha_dedup_entry, fict_entry,
89 rb_sha_dedup_entry_compare);
92 * Pass2 list - contains entries that were not dedup'ed because ioctl failed
94 STAILQ_HEAD(, pass2_dedup_entry) pass2_dedup_queue =
95 STAILQ_HEAD_INITIALIZER(pass2_dedup_queue);
97 struct pass2_dedup_entry {
98 struct hammer_btree_leaf_elm leaf;
99 STAILQ_ENTRY(pass2_dedup_entry) sq_entry;
102 #define DEDUP_PASS2 0x0001 /* process_btree_elm() mode */
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;
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;
118 * Global accounting variables
120 * Last three don't have to be 64-bit, just to be safe..
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;
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);
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);
154 static int
155 rb_sim_dedup_entry_compare(struct sim_dedup_entry *sim_de1,
156 struct sim_dedup_entry *sim_de2)
158 if (sim_de1->crc < sim_de2->crc)
159 return (-1);
160 if (sim_de1->crc > sim_de2->crc)
161 return (1);
163 return (0);
166 static int
167 rb_dedup_entry_compare(struct dedup_entry *de1, struct dedup_entry *de2)
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);
174 return (0);
177 static int
178 rb_sha_dedup_entry_compare(struct sha_dedup_entry *sha_de1,
179 struct sha_dedup_entry *sha_de2)
181 unsigned long *h1 = (unsigned long *)&sha_de1->sha_hash;
182 unsigned long *h2 = (unsigned long *)&sha_de2->sha_hash;
183 int i;
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);
192 return (0);
196 * dedup-simulate <filesystem>
198 void
199 hammer_cmd_dedup_simulate(char **av, int ac)
201 struct sim_dedup_entry *sim_de;
203 if (ac != 1)
204 dedup_usage(1);
206 glob_fd = getpfs(&glob_pfs, av[0]);
209 * Collection passes (memory limited)
211 printf("Dedup-simulate running\n");
212 do {
213 DedupCrcStart = DedupCrcEnd;
214 DedupCrcEnd = 0;
215 MemoryUse = 0;
217 if (VerboseOpt) {
218 printf("B-Tree pass crc-range %08x-max\n",
219 DedupCrcStart);
220 fflush(stdout);
222 scan_pfs(av[0], collect_btree_elm, "simu-pass");
224 if (VerboseOpt >= 2)
225 dump_simulated_dedup();
228 * Calculate simulated dedup ratio and get rid of the tree
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;
235 RB_REMOVE(sim_dedup_entry_rb_tree, &sim_dedup_tree, sim_de);
236 free(sim_de);
238 if (DedupCrcEnd && VerboseOpt == 0)
239 printf(".");
240 } while (DedupCrcEnd);
242 printf("Dedup-simulate %s succeeded\n", av[0]);
243 relpfs(glob_fd, &glob_pfs);
245 printf("Simulated dedup ratio = %.2f\n",
246 (dedup_alloc_size != 0) ?
247 (double)dedup_ref_size / dedup_alloc_size : 0);
251 * dedup <filesystem>
253 void
254 hammer_cmd_dedup(char **av, int ac)
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;
263 if (TimeoutOpt > 0)
264 alarm(TimeoutOpt);
266 if (ac != 1)
267 dedup_usage(1);
269 STAILQ_INIT(&pass2_dedup_queue);
271 glob_fd = getpfs(&glob_pfs, av[0]);
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.
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;
291 * Pre-pass to cache the btree
293 scan_pfs(av[0], count_btree_elm, "pre-pass ");
294 DedupTotalRecords = DedupCurrentRecords;
297 * Collection passes (memory limited)
299 printf("Dedup running\n");
300 do {
301 DedupCrcStart = DedupCrcEnd;
302 DedupCrcEnd = 0;
303 MemoryUse = 0;
305 if (VerboseOpt) {
306 printf("B-Tree pass crc-range %08x-max\n",
307 DedupCrcStart);
308 fflush(stdout);
310 scan_pfs(av[0], process_btree_elm, "main-pass");
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;
316 STAILQ_REMOVE_HEAD(&pass2_dedup_queue, sq_entry);
317 free(pass2_de);
319 assert(STAILQ_EMPTY(&pass2_dedup_queue));
321 if (VerboseOpt >= 2)
322 dump_real_dedup();
325 * Calculate dedup ratio and get rid of the trees
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;
334 RB_REMOVE(sha_dedup_entry_rb_tree,
335 &de->u.fict_root, sha_de);
336 free(sha_de);
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;
345 RB_REMOVE(dedup_entry_rb_tree, &dedup_tree, de);
346 free(de);
348 assert(RB_EMPTY(&dedup_tree));
349 if (DedupCrcEnd && VerboseOpt == 0)
350 printf(".");
351 } while (DedupCrcEnd);
353 printf("Dedup %s succeeded\n", av[0]);
354 relpfs(glob_fd, &glob_pfs);
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),
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
379 /* Once completed remove cycle file */
380 hammer_reset_cycle();
382 /* We don't want to mess up with other directives */
383 if (needfree) {
384 free(tmp);
385 CyclePath = NULL;
389 static int
390 count_btree_elm(hammer_btree_leaf_elm_t scan_leaf __unused, int flags __unused)
392 return(1);
395 static int
396 collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags __unused)
398 struct sim_dedup_entry *sim_de;
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!
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);
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);
426 * Collect statistics based on the CRC only, do not try to read
427 * any data blocks or run SHA hashes.
429 sim_de = RB_LOOKUP(sim_dedup_entry_rb_tree, &sim_dedup_tree,
430 scan_leaf->data_crc);
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);
439 sim_de->ref_blks += 1;
440 sim_de->ref_size += scan_leaf->data_len;
441 return (1);
444 static __inline int
445 validate_dedup_pair(hammer_btree_leaf_elm_t p, hammer_btree_leaf_elm_t q)
447 if (HAMMER_ZONE(p->data_offset) != HAMMER_ZONE(q->data_offset))
448 return (1);
449 if (p->data_len != q->data_len)
450 return (1);
452 return (0);
455 #define DEDUP_TECH_FAILURE 1
456 #define DEDUP_CMP_FAILURE 2
457 #define DEDUP_INVALID_ZONE 3
458 #define DEDUP_UNDERFLOW 4
459 #define DEDUP_VERS_FAILURE 5
461 static __inline int
462 deduplicate(hammer_btree_leaf_elm_t p, hammer_btree_leaf_elm_t q)
464 struct hammer_ioc_dedup dedup;
466 bzero(&dedup, sizeof(dedup));
469 * If data_offset fields are the same there is no need to run ioctl,
470 * candidate is already dedup'ed.
472 if (p->data_offset == q->data_offset)
473 return (0);
475 dedup.elm1 = p->base;
476 dedup.elm2 = q->base;
477 RunningIoctl = 1;
478 if (ioctl(glob_fd, HAMMERIOC_DEDUP, &dedup) < 0) {
479 if (errno == EOPNOTSUPP)
480 return (DEDUP_VERS_FAILURE); /* must be at least version 5 */
481 /* Technical failure - locking or w/e */
482 return (DEDUP_TECH_FAILURE);
484 if (dedup.head.flags & HAMMER_IOC_DEDUP_CMP_FAILURE)
485 return (DEDUP_CMP_FAILURE);
486 if (dedup.head.flags & HAMMER_IOC_DEDUP_INVALID_ZONE)
487 return (DEDUP_INVALID_ZONE);
488 if (dedup.head.flags & HAMMER_IOC_DEDUP_UNDERFLOW)
489 return (DEDUP_UNDERFLOW);
490 RunningIoctl = 0;
491 ++dedup_successes_count;
492 dedup_successes_bytes += p->data_len;
493 return (0);
496 static int
497 process_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags)
499 struct dedup_entry *de;
500 struct sha_dedup_entry *sha_de, temp;
501 struct pass2_dedup_entry *pass2_de;
502 int error;
505 * If we are using too much memory we have to clean some out, which
506 * will cause the run to use multiple passes. Be careful of integer
507 * overflows!
509 while (MemoryUse > MemoryLimit) {
510 DedupCrcEnd = DedupCrcStart +
511 (uint32_t)(DedupCrcEnd - DedupCrcStart - 1) / 2;
512 if (VerboseOpt) {
513 printf("memory limit crc-range %08x-%08x\n",
514 DedupCrcStart, DedupCrcEnd);
515 fflush(stdout);
518 for (;;) {
519 de = RB_MAX(dedup_entry_rb_tree, &dedup_tree);
520 if (de == NULL || de->leaf.data_crc < DedupCrcEnd)
521 break;
522 if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
523 while ((sha_de = RB_ROOT(&de->u.fict_root)) !=
524 NULL) {
525 RB_REMOVE(sha_dedup_entry_rb_tree,
526 &de->u.fict_root, sha_de);
527 MemoryUse -= sizeof(*sha_de);
528 free(sha_de);
531 RB_REMOVE(dedup_entry_rb_tree, &dedup_tree, de);
532 MemoryUse -= sizeof(*de);
533 free(de);
538 * Collect statistics based on the CRC. Colliding CRCs usually
539 * cause a SHA sub-tree to be created under the de.
541 * Trivial case if de not found.
543 de = RB_LOOKUP(dedup_entry_rb_tree, &dedup_tree, scan_leaf->data_crc);
544 if (de == NULL) {
545 de = calloc(1, sizeof(*de));
546 de->leaf = *scan_leaf;
547 RB_INSERT(dedup_entry_rb_tree, &dedup_tree, de);
548 MemoryUse += sizeof(*de);
549 goto upgrade_stats;
553 * Found entry in CRC tree
555 if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
557 * Optimize the case where a CRC failure results in multiple
558 * SHA entries. If we unconditionally issue a data-read a
559 * degenerate situation where a colliding CRC's second SHA
560 * entry contains the lion's share of the deduplication
561 * candidates will result in excessive data block reads.
563 * Deal with the degenerate case by looking for a matching
564 * data_offset/data_len in the SHA elements we already have
565 * before reading the data block and generating a new SHA.
567 RB_FOREACH(sha_de, sha_dedup_entry_rb_tree, &de->u.fict_root) {
568 if (sha_de->leaf.data_offset ==
569 scan_leaf->data_offset &&
570 sha_de->leaf.data_len == scan_leaf->data_len) {
571 memcpy(temp.sha_hash, sha_de->sha_hash,
572 SHA256_DIGEST_LENGTH);
573 break;
578 * Entry in CRC tree is fictitious, so we already had problems
579 * with this CRC. Upgrade (compute SHA) the candidate and
580 * dive into SHA subtree. If upgrade fails insert the candidate
581 * into Pass2 list (it will be processed later).
583 if (sha_de == NULL) {
584 if (upgrade_chksum(scan_leaf, temp.sha_hash))
585 goto pass2_insert;
587 sha_de = RB_FIND(sha_dedup_entry_rb_tree,
588 &de->u.fict_root, &temp);
592 * Nothing in SHA subtree so far, so this is a new
593 * 'dataset'. Insert new entry into SHA subtree.
595 if (sha_de == NULL) {
596 sha_de = calloc(1, sizeof(*sha_de));
597 sha_de->leaf = *scan_leaf;
598 memcpy(sha_de->sha_hash, temp.sha_hash,
599 SHA256_DIGEST_LENGTH);
600 RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root,
601 sha_de);
602 MemoryUse += sizeof(*sha_de);
603 goto upgrade_stats_sha;
607 * Found entry in SHA subtree, it means we have a potential
608 * dedup pair. Validate it (zones have to match and data_len
609 * field have to be the same too. If validation fails, treat
610 * it as a SHA collision (jump to sha256_failure).
612 if (validate_dedup_pair(&sha_de->leaf, scan_leaf))
613 goto sha256_failure;
616 * We have a valid dedup pair (SHA match, validated).
618 * In case of technical failure (dedup pair was good, but
619 * ioctl failed anyways) insert the candidate into Pass2 list
620 * (we will try to dedup it after we are done with the rest of
621 * the tree).
623 * If ioctl fails because either of blocks is in the non-dedup
624 * zone (we can dedup only in LARGE_DATA and SMALL_DATA) don't
625 * bother with the candidate and terminate early.
627 * If ioctl fails because of big-block underflow replace the
628 * leaf node that found dedup entry represents with scan_leaf.
630 error = deduplicate(&sha_de->leaf, scan_leaf);
631 switch(error) {
632 case 0:
633 goto upgrade_stats_sha;
634 case DEDUP_TECH_FAILURE:
635 goto pass2_insert;
636 case DEDUP_CMP_FAILURE:
637 goto sha256_failure;
638 case DEDUP_INVALID_ZONE:
639 goto terminate_early;
640 case DEDUP_UNDERFLOW:
641 ++dedup_underflows;
642 sha_de->leaf = *scan_leaf;
643 memcpy(sha_de->sha_hash, temp.sha_hash,
644 SHA256_DIGEST_LENGTH);
645 goto upgrade_stats_sha;
646 case DEDUP_VERS_FAILURE:
647 errx(1, "HAMMER filesystem must be at least "
648 "version 5 to dedup");
649 default:
650 fprintf(stderr, "Unknown error\n");
651 goto terminate_early;
655 * Ooh la la.. SHA-256 collision. Terminate early, there's
656 * nothing we can do here.
658 sha256_failure:
659 ++dedup_sha_failures;
660 goto terminate_early;
661 } else {
663 * Candidate CRC is good for now (we found an entry in CRC
664 * tree and it's not fictitious). This means we have a
665 * potential dedup pair.
667 if (validate_dedup_pair(&de->leaf, scan_leaf))
668 goto crc_failure;
671 * We have a valid dedup pair (CRC match, validated)
673 error = deduplicate(&de->leaf, scan_leaf);
674 switch(error) {
675 case 0:
676 goto upgrade_stats;
677 case DEDUP_TECH_FAILURE:
678 goto pass2_insert;
679 case DEDUP_CMP_FAILURE:
680 goto crc_failure;
681 case DEDUP_INVALID_ZONE:
682 goto terminate_early;
683 case DEDUP_UNDERFLOW:
684 ++dedup_underflows;
685 de->leaf = *scan_leaf;
686 goto upgrade_stats;
687 case DEDUP_VERS_FAILURE:
688 errx(1, "HAMMER filesystem must be at least "
689 "version 5 to dedup");
690 default:
691 fprintf(stderr, "Unknown error\n");
692 goto terminate_early;
695 crc_failure:
697 * We got a CRC collision - either ioctl failed because of
698 * the comparison failure or validation of the potential
699 * dedup pair went bad. In all cases insert both blocks
700 * into SHA subtree (this requires checksum upgrade) and mark
701 * entry that corresponds to this CRC in the CRC tree
702 * fictitious, so that all futher operations with this CRC go
703 * through SHA subtree.
705 ++dedup_crc_failures;
708 * Insert block that was represented by now fictitious dedup
709 * entry (create a new SHA entry and preserve stats of the
710 * old CRC one). If checksum upgrade fails insert the
711 * candidate into Pass2 list and return - keep both trees
712 * unmodified.
714 sha_de = calloc(1, sizeof(*sha_de));
715 sha_de->leaf = de->leaf;
716 sha_de->ref_blks = de->u.de.ref_blks;
717 sha_de->ref_size = de->u.de.ref_size;
718 if (upgrade_chksum(&sha_de->leaf, sha_de->sha_hash)) {
719 free(sha_de);
720 goto pass2_insert;
722 MemoryUse += sizeof(*sha_de);
724 RB_INIT(&de->u.fict_root);
726 * Here we can insert without prior checking because the tree
727 * is empty at this point
729 RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de);
732 * Mark entry in CRC tree fictitious
734 de->flags |= HAMMER_DEDUP_ENTRY_FICTITIOUS;
737 * Upgrade checksum of the candidate and insert it into
738 * SHA subtree. If upgrade fails insert the candidate into
739 * Pass2 list.
741 if (upgrade_chksum(scan_leaf, temp.sha_hash))
742 goto pass2_insert;
743 sha_de = RB_FIND(sha_dedup_entry_rb_tree, &de->u.fict_root,
744 &temp);
745 if (sha_de != NULL)
746 /* There is an entry with this SHA already, but the only
747 * RB-tree element at this point is that entry we just
748 * added. We know for sure these blocks are different
749 * (this is crc_failure branch) so treat it as SHA
750 * collision.
752 goto sha256_failure;
754 sha_de = calloc(1, sizeof(*sha_de));
755 sha_de->leaf = *scan_leaf;
756 memcpy(sha_de->sha_hash, temp.sha_hash, SHA256_DIGEST_LENGTH);
757 RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de);
758 MemoryUse += sizeof(*sha_de);
759 goto upgrade_stats_sha;
762 upgrade_stats:
763 de->u.de.ref_blks += 1;
764 de->u.de.ref_size += scan_leaf->data_len;
765 return (1);
767 upgrade_stats_sha:
768 sha_de->ref_blks += 1;
769 sha_de->ref_size += scan_leaf->data_len;
770 return (1);
772 pass2_insert:
774 * If in pass2 mode don't insert anything, fall through to
775 * terminate_early
777 if ((flags & DEDUP_PASS2) == 0) {
778 pass2_de = calloc(1, sizeof(*pass2_de));
779 pass2_de->leaf = *scan_leaf;
780 STAILQ_INSERT_TAIL(&pass2_dedup_queue, pass2_de, sq_entry);
781 dedup_skipped_size += scan_leaf->data_len;
782 return (1);
785 terminate_early:
787 * Early termination path. Fixup stats.
789 dedup_alloc_size += scan_leaf->data_len;
790 dedup_ref_size += scan_leaf->data_len;
791 return (0);
794 static int
795 upgrade_chksum(hammer_btree_leaf_elm_t leaf, uint8_t *sha_hash)
797 struct hammer_ioc_data data;
798 char *buf = malloc(DEDUP_BUF);
799 SHA256_CTX ctx;
800 int error;
802 bzero(&data, sizeof(data));
803 data.elm = leaf->base;
804 data.ubuf = buf;
805 data.size = DEDUP_BUF;
807 error = 0;
808 if (ioctl(glob_fd, HAMMERIOC_GET_DATA, &data) < 0) {
809 fprintf(stderr, "Get-data failed: %s\n", strerror(errno));
810 error = 1;
811 goto done;
813 DedupDataReads += leaf->data_len;
815 if (data.leaf.data_len != leaf->data_len) {
816 error = 1;
817 goto done;
820 if (data.leaf.base.btype == HAMMER_BTREE_TYPE_RECORD &&
821 data.leaf.base.rec_type == HAMMER_RECTYPE_DATA) {
822 SHA256_Init(&ctx);
823 SHA256_Update(&ctx, (void *)buf, data.leaf.data_len);
824 SHA256_Final(sha_hash, &ctx);
827 done:
828 free(buf);
829 return (error);
832 static void
833 sigAlrm(int signo __unused)
835 SigAlrmFlag = 1;
838 static void
839 sigInfo(int signo __unused)
841 SigInfoFlag = 1;
844 static void
845 scan_pfs(char *filesystem, scan_pfs_cb_t func, const char *id)
847 struct hammer_ioc_mirror_rw mirror;
848 hammer_ioc_mrecord_any_t mrec;
849 struct hammer_btree_leaf_elm elm;
850 char *buf = malloc(DEDUP_BUF);
851 char buf1[8];
852 char buf2[8];
853 int offset, bytes;
855 SigInfoFlag = 0;
856 DedupDataReads = 0;
857 DedupCurrentRecords = 0;
858 signal(SIGINFO, sigInfo);
859 signal(SIGALRM, sigAlrm);
862 * Deduplication happens per element so hammer(8) is in full
863 * control of the ioctl()s to actually perform it. SIGALRM
864 * needs to be handled within hammer(8) but a checkpoint
865 * is needed for resuming. Use cycle file for that.
867 * Try to obtain the previous obj_id from the cycle file and
868 * if not available just start from the beginning.
870 bzero(&mirror, sizeof(mirror));
871 hammer_key_beg_init(&mirror.key_beg);
872 hammer_get_cycle(&mirror.key_beg, &mirror.tid_beg);
874 if (mirror.key_beg.obj_id != (int64_t)HAMMER_MIN_OBJID) {
875 if (VerboseOpt)
876 fprintf(stderr, "%s: mirror-read: Resuming at object %016jx\n",
877 id, (uintmax_t)mirror.key_beg.obj_id);
880 hammer_key_end_init(&mirror.key_end);
882 mirror.tid_beg = glob_pfs.ondisk->sync_beg_tid;
883 mirror.tid_end = glob_pfs.ondisk->sync_end_tid;
884 mirror.head.flags |= HAMMER_IOC_MIRROR_NODATA; /* we want only keys */
885 mirror.ubuf = buf;
886 mirror.size = DEDUP_BUF;
887 mirror.pfs_id = glob_pfs.pfs_id;
888 mirror.shared_uuid = glob_pfs.ondisk->shared_uuid;
890 if (VerboseOpt && DedupCrcStart == 0) {
891 printf("%s %s: objspace %016jx:%04x %016jx:%04x\n",
892 id, filesystem,
893 (uintmax_t)mirror.key_beg.obj_id,
894 mirror.key_beg.localization,
895 (uintmax_t)mirror.key_end.obj_id,
896 mirror.key_end.localization);
897 printf("%s %s: pfs_id %d\n",
898 id, filesystem, glob_pfs.pfs_id);
900 fflush(stdout);
901 fflush(stderr);
903 do {
904 mirror.count = 0;
905 mirror.pfs_id = glob_pfs.pfs_id;
906 mirror.shared_uuid = glob_pfs.ondisk->shared_uuid;
907 if (ioctl(glob_fd, HAMMERIOC_MIRROR_READ, &mirror) < 0)
908 err(1, "Mirror-read %s failed", filesystem);
909 if (mirror.head.flags & HAMMER_IOC_HEAD_ERROR)
910 errx(1, "Mirror-read %s fatal error %d",
911 filesystem, mirror.head.error);
912 if (mirror.count) {
913 offset = 0;
914 while (offset < mirror.count) {
915 mrec = (void *)((char *)buf + offset);
916 bytes = HAMMER_HEAD_DOALIGN(mrec->head.rec_size);
917 if (offset + bytes > mirror.count)
918 errx(1, "Misaligned record");
919 assert((mrec->head.type &
920 HAMMER_MRECF_TYPE_MASK) ==
921 HAMMER_MREC_TYPE_REC);
922 offset += bytes;
923 elm = mrec->rec.leaf;
924 if (elm.base.btype != HAMMER_BTREE_TYPE_RECORD)
925 continue;
926 if (elm.base.rec_type != HAMMER_RECTYPE_DATA)
927 continue;
928 ++DedupCurrentRecords;
929 if (DedupCrcStart != DedupCrcEnd) {
930 if (elm.data_crc < DedupCrcStart)
931 continue;
932 if (DedupCrcEnd &&
933 elm.data_crc >= DedupCrcEnd) {
934 continue;
937 func(&elm, 0);
940 mirror.key_beg = mirror.key_cur;
941 if (DidInterrupt || SigAlrmFlag) {
942 if (VerboseOpt)
943 fprintf(stderr, "%s\n",
944 (DidInterrupt ? "Interrupted" : "Timeout"));
945 hammer_set_cycle(&mirror.key_cur, mirror.tid_beg);
946 if (VerboseOpt)
947 fprintf(stderr, "Cyclefile %s updated for "
948 "continuation\n", CyclePath);
949 exit(1);
951 if (SigInfoFlag) {
952 if (DedupTotalRecords) {
953 humanize_unsigned(buf1, sizeof(buf1),
954 DedupDataReads,
955 "B", 1024);
956 humanize_unsigned(buf2, sizeof(buf2),
957 dedup_successes_bytes,
958 "B", 1024);
959 fprintf(stderr, "%s count %7jd/%jd "
960 "(%02d.%02d%%) "
961 "ioread %s newddup %s\n",
963 (intmax_t)DedupCurrentRecords,
964 (intmax_t)DedupTotalRecords,
965 (int)(DedupCurrentRecords * 100 /
966 DedupTotalRecords),
967 (int)(DedupCurrentRecords * 10000 /
968 DedupTotalRecords % 100),
969 buf1, buf2);
970 } else {
971 fprintf(stderr, "%s count %-7jd\n",
973 (intmax_t)DedupCurrentRecords);
975 SigInfoFlag = 0;
977 } while (mirror.count != 0);
979 signal(SIGINFO, SIG_IGN);
980 signal(SIGALRM, SIG_IGN);
982 free(buf);
985 static void
986 dump_simulated_dedup(void)
988 struct sim_dedup_entry *sim_de;
990 printf("=== Dumping simulated dedup entries:\n");
991 RB_FOREACH(sim_de, sim_dedup_entry_rb_tree, &sim_dedup_tree) {
992 printf("\tcrc=%08x cnt=%ju size=%ju\n",
993 sim_de->crc,
994 (intmax_t)sim_de->ref_blks,
995 (intmax_t)sim_de->ref_size);
997 printf("end of dump ===\n");
1000 static void
1001 dump_real_dedup(void)
1003 struct dedup_entry *de;
1004 struct sha_dedup_entry *sha_de;
1005 int i;
1007 printf("=== Dumping dedup entries:\n");
1008 RB_FOREACH(de, dedup_entry_rb_tree, &dedup_tree) {
1009 if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
1010 printf("\tcrc=%08x fictitious\n", de->leaf.data_crc);
1012 RB_FOREACH(sha_de, sha_dedup_entry_rb_tree, &de->u.fict_root) {
1013 printf("\t\tcrc=%08x cnt=%ju size=%ju\n\t"
1014 "\t\tsha=",
1015 sha_de->leaf.data_crc,
1016 (intmax_t)sha_de->ref_blks,
1017 (intmax_t)sha_de->ref_size);
1018 for (i = 0; i < SHA256_DIGEST_LENGTH; ++i)
1019 printf("%02x", sha_de->sha_hash[i]);
1020 printf("\n");
1022 } else {
1023 printf("\tcrc=%08x cnt=%ju size=%ju\n",
1024 de->leaf.data_crc,
1025 (intmax_t)de->u.de.ref_blks,
1026 (intmax_t)de->u.de.ref_size);
1029 printf("end of dump ===\n");
1032 static void
1033 dedup_usage(int code)
1035 fprintf(stderr,
1036 "hammer dedup-simulate <filesystem>\n"
1037 "hammer dedup <filesystem>\n"
1039 exit(code);