1bb29b5d8SMatthew Dillon /*
2bb29b5d8SMatthew Dillon * Copyright (c) 2010 The DragonFly Project. All rights reserved.
3bb29b5d8SMatthew Dillon *
4bb29b5d8SMatthew Dillon * This code is derived from software contributed to The DragonFly Project
5bb29b5d8SMatthew Dillon * by Ilya Dryomov <idryomov@gmail.com>
6bb29b5d8SMatthew Dillon *
7bb29b5d8SMatthew Dillon * Redistribution and use in source and binary forms, with or without
8bb29b5d8SMatthew Dillon * modification, are permitted provided that the following conditions
9bb29b5d8SMatthew Dillon * are met:
10bb29b5d8SMatthew Dillon *
11bb29b5d8SMatthew Dillon * 1. Redistributions of source code must retain the above copyright
12bb29b5d8SMatthew Dillon * notice, this list of conditions and the following disclaimer.
13bb29b5d8SMatthew Dillon * 2. Redistributions in binary form must reproduce the above copyright
14bb29b5d8SMatthew Dillon * notice, this list of conditions and the following disclaimer in
15bb29b5d8SMatthew Dillon * the documentation and/or other materials provided with the
16bb29b5d8SMatthew Dillon * distribution.
17bb29b5d8SMatthew Dillon * 3. Neither the name of The DragonFly Project nor the names of its
18bb29b5d8SMatthew Dillon * contributors may be used to endorse or promote products derived
19bb29b5d8SMatthew Dillon * from this software without specific, prior written permission.
20bb29b5d8SMatthew Dillon *
21bb29b5d8SMatthew Dillon * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22bb29b5d8SMatthew Dillon * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23bb29b5d8SMatthew Dillon * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24bb29b5d8SMatthew Dillon * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25bb29b5d8SMatthew Dillon * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26bb29b5d8SMatthew Dillon * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27bb29b5d8SMatthew Dillon * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28bb29b5d8SMatthew Dillon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29bb29b5d8SMatthew Dillon * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30bb29b5d8SMatthew Dillon * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31bb29b5d8SMatthew Dillon * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32bb29b5d8SMatthew Dillon * SUCH DAMAGE.
33bb29b5d8SMatthew Dillon */
34bb29b5d8SMatthew Dillon
3541ae0862STomohiro Kusumi #include "hammer.h"
3641ae0862STomohiro Kusumi
3741ae0862STomohiro Kusumi #include <sys/tree.h>
38bb29b5d8SMatthew Dillon #include <libutil.h>
39e0662909Szrj #include <openssl/sha.h>
40bb29b5d8SMatthew Dillon
41bb29b5d8SMatthew Dillon #define DEDUP_BUF (64 * 1024)
42bb29b5d8SMatthew Dillon
43bb29b5d8SMatthew Dillon /* Sorted list of block CRCs - light version for dedup-simulate */
44bb29b5d8SMatthew Dillon struct sim_dedup_entry_rb_tree;
45*d50f9ae3SSascha Wildner static RB_HEAD(sim_dedup_entry_rb_tree, sim_dedup_entry) sim_dedup_tree =
46bb29b5d8SMatthew Dillon RB_INITIALIZER(&sim_dedup_tree);
47bb29b5d8SMatthew Dillon RB_PROTOTYPE2(sim_dedup_entry_rb_tree, sim_dedup_entry, rb_entry,
48bb29b5d8SMatthew Dillon rb_sim_dedup_entry_compare, hammer_crc_t);
49bb29b5d8SMatthew Dillon
50bb29b5d8SMatthew Dillon struct sim_dedup_entry {
51bb29b5d8SMatthew Dillon hammer_crc_t crc;
5246137e17STomohiro Kusumi uint64_t ref_blks; /* number of blocks referenced */
5346137e17STomohiro Kusumi uint64_t ref_size; /* size of data referenced */
54bb29b5d8SMatthew Dillon RB_ENTRY(sim_dedup_entry) rb_entry;
55bb29b5d8SMatthew Dillon };
56bb29b5d8SMatthew Dillon
57bb29b5d8SMatthew Dillon struct dedup_entry {
58bb29b5d8SMatthew Dillon struct hammer_btree_leaf_elm leaf;
59bb29b5d8SMatthew Dillon union {
60bb29b5d8SMatthew Dillon struct {
6146137e17STomohiro Kusumi uint64_t ref_blks;
6246137e17STomohiro Kusumi uint64_t ref_size;
63bb29b5d8SMatthew Dillon } de;
64bb29b5d8SMatthew Dillon RB_HEAD(sha_dedup_entry_rb_tree, sha_dedup_entry) fict_root;
65bb29b5d8SMatthew Dillon } u;
6646137e17STomohiro Kusumi uint8_t flags;
67bb29b5d8SMatthew Dillon RB_ENTRY(dedup_entry) rb_entry;
68bb29b5d8SMatthew Dillon };
69bb29b5d8SMatthew Dillon
70bb29b5d8SMatthew Dillon #define HAMMER_DEDUP_ENTRY_FICTITIOUS 0x0001
71bb29b5d8SMatthew Dillon
72bb29b5d8SMatthew Dillon struct sha_dedup_entry {
73bb29b5d8SMatthew Dillon struct hammer_btree_leaf_elm leaf;
7446137e17STomohiro Kusumi uint64_t ref_blks;
7546137e17STomohiro Kusumi uint64_t ref_size;
7646137e17STomohiro Kusumi uint8_t sha_hash[SHA256_DIGEST_LENGTH];
77bb29b5d8SMatthew Dillon RB_ENTRY(sha_dedup_entry) fict_entry;
78bb29b5d8SMatthew Dillon };
79bb29b5d8SMatthew Dillon
804fd111b9SFrançois Tigeot /* Sorted list of HAMMER B-Tree keys */
814fd111b9SFrançois Tigeot struct dedup_entry_rb_tree;
824fd111b9SFrançois Tigeot struct sha_dedup_entry_rb_tree;
834fd111b9SFrançois Tigeot
84*d50f9ae3SSascha Wildner static RB_HEAD(dedup_entry_rb_tree, dedup_entry) dedup_tree =
854fd111b9SFrançois Tigeot RB_INITIALIZER(&dedup_tree);
864fd111b9SFrançois Tigeot RB_PROTOTYPE2(dedup_entry_rb_tree, dedup_entry, rb_entry,
874fd111b9SFrançois Tigeot rb_dedup_entry_compare, hammer_crc_t);
884fd111b9SFrançois Tigeot
894fd111b9SFrançois Tigeot RB_PROTOTYPE(sha_dedup_entry_rb_tree, sha_dedup_entry, fict_entry,
904fd111b9SFrançois Tigeot rb_sha_dedup_entry_compare);
914fd111b9SFrançois Tigeot
92bb29b5d8SMatthew Dillon /*
93bb29b5d8SMatthew Dillon * Pass2 list - contains entries that were not dedup'ed because ioctl failed
94bb29b5d8SMatthew Dillon */
95*d50f9ae3SSascha Wildner static STAILQ_HEAD(, pass2_dedup_entry) pass2_dedup_queue =
96bb29b5d8SMatthew Dillon STAILQ_HEAD_INITIALIZER(pass2_dedup_queue);
97bb29b5d8SMatthew Dillon
98bb29b5d8SMatthew Dillon struct pass2_dedup_entry {
99bb29b5d8SMatthew Dillon struct hammer_btree_leaf_elm leaf;
100bb29b5d8SMatthew Dillon STAILQ_ENTRY(pass2_dedup_entry) sq_entry;
101bb29b5d8SMatthew Dillon };
102bb29b5d8SMatthew Dillon
103bb29b5d8SMatthew Dillon #define DEDUP_PASS2 0x0001 /* process_btree_elm() mode */
104bb29b5d8SMatthew Dillon
105e9c8ad3dSMatthew Dillon static int SigInfoFlag;
1063a92efe3SAntonio Huete Jimenez static int SigAlrmFlag;
107e9c8ad3dSMatthew Dillon static int64_t DedupDataReads;
108e9c8ad3dSMatthew Dillon static int64_t DedupCurrentRecords;
109e9c8ad3dSMatthew Dillon static int64_t DedupTotalRecords;
11046137e17STomohiro Kusumi static uint32_t DedupCrcStart;
11146137e17STomohiro Kusumi static uint32_t DedupCrcEnd;
11246137e17STomohiro Kusumi static uint64_t MemoryUse;
113e9c8ad3dSMatthew Dillon
114bb29b5d8SMatthew Dillon /* PFS global ids - we deal with just one PFS at a run */
11507d6666fSTomohiro Kusumi static int glob_fd;
11607d6666fSTomohiro Kusumi static struct hammer_ioc_pseudofs_rw glob_pfs;
117bb29b5d8SMatthew Dillon
118bb29b5d8SMatthew Dillon /*
119bb29b5d8SMatthew Dillon * Global accounting variables
120bb29b5d8SMatthew Dillon *
121bb29b5d8SMatthew Dillon * Last three don't have to be 64-bit, just to be safe..
122bb29b5d8SMatthew Dillon */
12307d6666fSTomohiro Kusumi static uint64_t dedup_alloc_size;
12407d6666fSTomohiro Kusumi static uint64_t dedup_ref_size;
12507d6666fSTomohiro Kusumi static uint64_t dedup_skipped_size;
12607d6666fSTomohiro Kusumi static uint64_t dedup_crc_failures;
12707d6666fSTomohiro Kusumi static uint64_t dedup_sha_failures;
12807d6666fSTomohiro Kusumi static uint64_t dedup_underflows;
12907d6666fSTomohiro Kusumi static uint64_t dedup_successes_count;
13007d6666fSTomohiro Kusumi static uint64_t dedup_successes_bytes;
131bb29b5d8SMatthew Dillon
132bb29b5d8SMatthew Dillon static int rb_sim_dedup_entry_compare(struct sim_dedup_entry *sim_de1,
133bb29b5d8SMatthew Dillon struct sim_dedup_entry *sim_de2);
134bb29b5d8SMatthew Dillon static int rb_dedup_entry_compare(struct dedup_entry *de1,
135bb29b5d8SMatthew Dillon struct dedup_entry *de2);
136bb29b5d8SMatthew Dillon static int rb_sha_dedup_entry_compare(struct sha_dedup_entry *sha_de1,
137bb29b5d8SMatthew Dillon struct sha_dedup_entry *sha_de2);
138bb29b5d8SMatthew Dillon typedef int (*scan_pfs_cb_t)(hammer_btree_leaf_elm_t scan_leaf, int flags);
139e9c8ad3dSMatthew Dillon static void scan_pfs(char *filesystem, scan_pfs_cb_t func, const char *id);
140bb29b5d8SMatthew Dillon static int collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags);
141e9c8ad3dSMatthew Dillon static int count_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags);
142bb29b5d8SMatthew Dillon static int process_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags);
14346137e17STomohiro Kusumi static int upgrade_chksum(hammer_btree_leaf_elm_t leaf, uint8_t *sha_hash);
144bb29b5d8SMatthew Dillon static void dump_simulated_dedup(void);
145bb29b5d8SMatthew Dillon static void dump_real_dedup(void);
146bb29b5d8SMatthew Dillon static void dedup_usage(int code);
147bb29b5d8SMatthew Dillon
148bb29b5d8SMatthew Dillon RB_GENERATE2(sim_dedup_entry_rb_tree, sim_dedup_entry, rb_entry,
149bb29b5d8SMatthew Dillon rb_sim_dedup_entry_compare, hammer_crc_t, crc);
150bb29b5d8SMatthew Dillon RB_GENERATE2(dedup_entry_rb_tree, dedup_entry, rb_entry,
151bb29b5d8SMatthew Dillon rb_dedup_entry_compare, hammer_crc_t, leaf.data_crc);
152bb29b5d8SMatthew Dillon RB_GENERATE(sha_dedup_entry_rb_tree, sha_dedup_entry, fict_entry,
153bb29b5d8SMatthew Dillon rb_sha_dedup_entry_compare);
154bb29b5d8SMatthew Dillon
155005a4da7STomohiro Kusumi static
156005a4da7STomohiro Kusumi int
rb_sim_dedup_entry_compare(struct sim_dedup_entry * sim_de1,struct sim_dedup_entry * sim_de2)157bb29b5d8SMatthew Dillon rb_sim_dedup_entry_compare(struct sim_dedup_entry *sim_de1,
158bb29b5d8SMatthew Dillon struct sim_dedup_entry *sim_de2)
159bb29b5d8SMatthew Dillon {
160bb29b5d8SMatthew Dillon if (sim_de1->crc < sim_de2->crc)
161bb29b5d8SMatthew Dillon return (-1);
162bb29b5d8SMatthew Dillon if (sim_de1->crc > sim_de2->crc)
163bb29b5d8SMatthew Dillon return (1);
164bb29b5d8SMatthew Dillon
165bb29b5d8SMatthew Dillon return (0);
166bb29b5d8SMatthew Dillon }
167bb29b5d8SMatthew Dillon
168005a4da7STomohiro Kusumi static
169005a4da7STomohiro Kusumi int
rb_dedup_entry_compare(struct dedup_entry * de1,struct dedup_entry * de2)170bb29b5d8SMatthew Dillon rb_dedup_entry_compare(struct dedup_entry *de1, struct dedup_entry *de2)
171bb29b5d8SMatthew Dillon {
172bb29b5d8SMatthew Dillon if (de1->leaf.data_crc < de2->leaf.data_crc)
173bb29b5d8SMatthew Dillon return (-1);
174bb29b5d8SMatthew Dillon if (de1->leaf.data_crc > de2->leaf.data_crc)
175bb29b5d8SMatthew Dillon return (1);
176bb29b5d8SMatthew Dillon
177bb29b5d8SMatthew Dillon return (0);
178bb29b5d8SMatthew Dillon }
179bb29b5d8SMatthew Dillon
180005a4da7STomohiro Kusumi static
181005a4da7STomohiro Kusumi int
rb_sha_dedup_entry_compare(struct sha_dedup_entry * sha_de1,struct sha_dedup_entry * sha_de2)182bb29b5d8SMatthew Dillon rb_sha_dedup_entry_compare(struct sha_dedup_entry *sha_de1,
183bb29b5d8SMatthew Dillon struct sha_dedup_entry *sha_de2)
184bb29b5d8SMatthew Dillon {
185bb29b5d8SMatthew Dillon unsigned long *h1 = (unsigned long *)&sha_de1->sha_hash;
186bb29b5d8SMatthew Dillon unsigned long *h2 = (unsigned long *)&sha_de2->sha_hash;
187bb29b5d8SMatthew Dillon int i;
188bb29b5d8SMatthew Dillon
189bb29b5d8SMatthew Dillon for (i = 0; i < SHA256_DIGEST_LENGTH / (int)sizeof(unsigned long); ++i) {
190bb29b5d8SMatthew Dillon if (h1[i] < h2[i])
191bb29b5d8SMatthew Dillon return (-1);
192bb29b5d8SMatthew Dillon if (h1[i] > h2[i])
193bb29b5d8SMatthew Dillon return (1);
194bb29b5d8SMatthew Dillon }
195bb29b5d8SMatthew Dillon
196bb29b5d8SMatthew Dillon return (0);
197bb29b5d8SMatthew Dillon }
198bb29b5d8SMatthew Dillon
199bb29b5d8SMatthew Dillon /*
200bb29b5d8SMatthew Dillon * dedup-simulate <filesystem>
201bb29b5d8SMatthew Dillon */
202bb29b5d8SMatthew Dillon void
hammer_cmd_dedup_simulate(char ** av,int ac)203bb29b5d8SMatthew Dillon hammer_cmd_dedup_simulate(char **av, int ac)
204bb29b5d8SMatthew Dillon {
205bb29b5d8SMatthew Dillon struct sim_dedup_entry *sim_de;
206bb29b5d8SMatthew Dillon
20788cdee70STomohiro Kusumi if (ac != 1) {
208bb29b5d8SMatthew Dillon dedup_usage(1);
20988cdee70STomohiro Kusumi /* not reached */
21088cdee70STomohiro Kusumi }
211bb29b5d8SMatthew Dillon
212bb29b5d8SMatthew Dillon glob_fd = getpfs(&glob_pfs, av[0]);
213bb29b5d8SMatthew Dillon
214fbe1c665SMatthew Dillon /*
215fbe1c665SMatthew Dillon * Collection passes (memory limited)
216fbe1c665SMatthew Dillon */
217fbe1c665SMatthew Dillon printf("Dedup-simulate running\n");
218fbe1c665SMatthew Dillon do {
219fbe1c665SMatthew Dillon DedupCrcStart = DedupCrcEnd;
220fbe1c665SMatthew Dillon DedupCrcEnd = 0;
221fbe1c665SMatthew Dillon MemoryUse = 0;
222bb29b5d8SMatthew Dillon
223fbe1c665SMatthew Dillon if (VerboseOpt) {
22478c4be83STomohiro Kusumi printf("B-Tree pass crc-range %08x-max\n",
225fbe1c665SMatthew Dillon DedupCrcStart);
226fbe1c665SMatthew Dillon fflush(stdout);
227fbe1c665SMatthew Dillon }
228fbe1c665SMatthew Dillon scan_pfs(av[0], collect_btree_elm, "simu-pass");
229bb29b5d8SMatthew Dillon
230bb29b5d8SMatthew Dillon if (VerboseOpt >= 2)
231bb29b5d8SMatthew Dillon dump_simulated_dedup();
232bb29b5d8SMatthew Dillon
233bb29b5d8SMatthew Dillon /*
234bb29b5d8SMatthew Dillon * Calculate simulated dedup ratio and get rid of the tree
235bb29b5d8SMatthew Dillon */
236bb29b5d8SMatthew Dillon while ((sim_de = RB_ROOT(&sim_dedup_tree)) != NULL) {
237bb29b5d8SMatthew Dillon assert(sim_de->ref_blks != 0);
238bb29b5d8SMatthew Dillon dedup_ref_size += sim_de->ref_size;
239bb29b5d8SMatthew Dillon dedup_alloc_size += sim_de->ref_size / sim_de->ref_blks;
240bb29b5d8SMatthew Dillon
241bb29b5d8SMatthew Dillon RB_REMOVE(sim_dedup_entry_rb_tree, &sim_dedup_tree, sim_de);
242bb29b5d8SMatthew Dillon free(sim_de);
243bb29b5d8SMatthew Dillon }
244fbe1c665SMatthew Dillon if (DedupCrcEnd && VerboseOpt == 0)
245fbe1c665SMatthew Dillon printf(".");
246fbe1c665SMatthew Dillon } while (DedupCrcEnd);
247fbe1c665SMatthew Dillon
248fbe1c665SMatthew Dillon printf("Dedup-simulate %s succeeded\n", av[0]);
249fbe1c665SMatthew Dillon relpfs(glob_fd, &glob_pfs);
250bb29b5d8SMatthew Dillon
251bb29b5d8SMatthew Dillon printf("Simulated dedup ratio = %.2f\n",
252eae1bb35SIlya Dryomov (dedup_alloc_size != 0) ?
253eae1bb35SIlya Dryomov (double)dedup_ref_size / dedup_alloc_size : 0);
254bb29b5d8SMatthew Dillon }
255bb29b5d8SMatthew Dillon
256bb29b5d8SMatthew Dillon /*
257bb29b5d8SMatthew Dillon * dedup <filesystem>
258bb29b5d8SMatthew Dillon */
259bb29b5d8SMatthew Dillon void
hammer_cmd_dedup(char ** av,int ac)260bb29b5d8SMatthew Dillon hammer_cmd_dedup(char **av, int ac)
261bb29b5d8SMatthew Dillon {
262bb29b5d8SMatthew Dillon struct dedup_entry *de;
263bb29b5d8SMatthew Dillon struct sha_dedup_entry *sha_de;
264bb29b5d8SMatthew Dillon struct pass2_dedup_entry *pass2_de;
2653a92efe3SAntonio Huete Jimenez char *tmp;
266bb29b5d8SMatthew Dillon char buf[8];
2673a92efe3SAntonio Huete Jimenez int needfree = 0;
268bb29b5d8SMatthew Dillon
269bb29b5d8SMatthew Dillon if (TimeoutOpt > 0)
270bb29b5d8SMatthew Dillon alarm(TimeoutOpt);
271bb29b5d8SMatthew Dillon
27288cdee70STomohiro Kusumi if (ac != 1) {
273bb29b5d8SMatthew Dillon dedup_usage(1);
27488cdee70STomohiro Kusumi /* not reached */
27588cdee70STomohiro Kusumi }
276bb29b5d8SMatthew Dillon
277bb29b5d8SMatthew Dillon STAILQ_INIT(&pass2_dedup_queue);
278bb29b5d8SMatthew Dillon
279bb29b5d8SMatthew Dillon glob_fd = getpfs(&glob_pfs, av[0]);
280bb29b5d8SMatthew Dillon
281fbe1c665SMatthew Dillon /*
2823a92efe3SAntonio Huete Jimenez * A cycle file is _required_ for resuming dedup after the timeout
2833a92efe3SAntonio Huete Jimenez * specified with -t has expired. If no -c option, then place a
2843a92efe3SAntonio Huete Jimenez * .dedup.cycle file either in the PFS snapshots directory or in
2853a92efe3SAntonio Huete Jimenez * the default snapshots directory.
2863a92efe3SAntonio Huete Jimenez */
2873a92efe3SAntonio Huete Jimenez if (!CyclePath) {
2889930da22STomohiro Kusumi if (glob_pfs.ondisk->snapshots[0] != '/') {
2893a92efe3SAntonio Huete Jimenez asprintf(&tmp, "%s/%s/.dedup.cycle",
2903a92efe3SAntonio Huete Jimenez SNAPSHOTS_BASE, av[0]);
2919930da22STomohiro Kusumi } else {
2923a92efe3SAntonio Huete Jimenez asprintf(&tmp, "%s/.dedup.cycle",
2933a92efe3SAntonio Huete Jimenez glob_pfs.ondisk->snapshots);
2949930da22STomohiro Kusumi }
2953a92efe3SAntonio Huete Jimenez CyclePath = tmp;
2963a92efe3SAntonio Huete Jimenez needfree = 1;
2973a92efe3SAntonio Huete Jimenez }
2983a92efe3SAntonio Huete Jimenez
2993a92efe3SAntonio Huete Jimenez /*
300fbe1c665SMatthew Dillon * Pre-pass to cache the btree
301fbe1c665SMatthew Dillon */
302e9c8ad3dSMatthew Dillon scan_pfs(av[0], count_btree_elm, "pre-pass ");
303e9c8ad3dSMatthew Dillon DedupTotalRecords = DedupCurrentRecords;
304fbe1c665SMatthew Dillon
305fbe1c665SMatthew Dillon /*
306fbe1c665SMatthew Dillon * Collection passes (memory limited)
307fbe1c665SMatthew Dillon */
30851d59e22SSascha Wildner printf("Dedup running\n");
309fbe1c665SMatthew Dillon do {
310fbe1c665SMatthew Dillon DedupCrcStart = DedupCrcEnd;
311fbe1c665SMatthew Dillon DedupCrcEnd = 0;
312fbe1c665SMatthew Dillon MemoryUse = 0;
313fbe1c665SMatthew Dillon
314fbe1c665SMatthew Dillon if (VerboseOpt) {
31578c4be83STomohiro Kusumi printf("B-Tree pass crc-range %08x-max\n",
316fbe1c665SMatthew Dillon DedupCrcStart);
317fbe1c665SMatthew Dillon fflush(stdout);
318fbe1c665SMatthew Dillon }
319e9c8ad3dSMatthew Dillon scan_pfs(av[0], process_btree_elm, "main-pass");
320bb29b5d8SMatthew Dillon
321bb29b5d8SMatthew Dillon while ((pass2_de = STAILQ_FIRST(&pass2_dedup_queue)) != NULL) {
322bb29b5d8SMatthew Dillon if (process_btree_elm(&pass2_de->leaf, DEDUP_PASS2))
323bb29b5d8SMatthew Dillon dedup_skipped_size -= pass2_de->leaf.data_len;
324bb29b5d8SMatthew Dillon
325bb29b5d8SMatthew Dillon STAILQ_REMOVE_HEAD(&pass2_dedup_queue, sq_entry);
326bb29b5d8SMatthew Dillon free(pass2_de);
327bb29b5d8SMatthew Dillon }
328bb29b5d8SMatthew Dillon assert(STAILQ_EMPTY(&pass2_dedup_queue));
329bb29b5d8SMatthew Dillon
330bb29b5d8SMatthew Dillon if (VerboseOpt >= 2)
331bb29b5d8SMatthew Dillon dump_real_dedup();
332bb29b5d8SMatthew Dillon
333bb29b5d8SMatthew Dillon /*
334bb29b5d8SMatthew Dillon * Calculate dedup ratio and get rid of the trees
335bb29b5d8SMatthew Dillon */
336bb29b5d8SMatthew Dillon while ((de = RB_ROOT(&dedup_tree)) != NULL) {
337bb29b5d8SMatthew Dillon if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
338bb29b5d8SMatthew Dillon while ((sha_de = RB_ROOT(&de->u.fict_root)) != NULL) {
339bb29b5d8SMatthew Dillon assert(sha_de->ref_blks != 0);
340bb29b5d8SMatthew Dillon dedup_ref_size += sha_de->ref_size;
341bb29b5d8SMatthew Dillon dedup_alloc_size += sha_de->ref_size / sha_de->ref_blks;
342bb29b5d8SMatthew Dillon
343bb29b5d8SMatthew Dillon RB_REMOVE(sha_dedup_entry_rb_tree,
344bb29b5d8SMatthew Dillon &de->u.fict_root, sha_de);
345bb29b5d8SMatthew Dillon free(sha_de);
346bb29b5d8SMatthew Dillon }
347bb29b5d8SMatthew Dillon assert(RB_EMPTY(&de->u.fict_root));
348bb29b5d8SMatthew Dillon } else {
349bb29b5d8SMatthew Dillon assert(de->u.de.ref_blks != 0);
350bb29b5d8SMatthew Dillon dedup_ref_size += de->u.de.ref_size;
351bb29b5d8SMatthew Dillon dedup_alloc_size += de->u.de.ref_size / de->u.de.ref_blks;
352bb29b5d8SMatthew Dillon }
353bb29b5d8SMatthew Dillon
354bb29b5d8SMatthew Dillon RB_REMOVE(dedup_entry_rb_tree, &dedup_tree, de);
355bb29b5d8SMatthew Dillon free(de);
356bb29b5d8SMatthew Dillon }
357bb29b5d8SMatthew Dillon assert(RB_EMPTY(&dedup_tree));
358fbe1c665SMatthew Dillon if (DedupCrcEnd && VerboseOpt == 0)
359fbe1c665SMatthew Dillon printf(".");
360fbe1c665SMatthew Dillon } while (DedupCrcEnd);
361fbe1c665SMatthew Dillon
362fbe1c665SMatthew Dillon printf("Dedup %s succeeded\n", av[0]);
363fbe1c665SMatthew Dillon relpfs(glob_fd, &glob_pfs);
364bb29b5d8SMatthew Dillon
365bb29b5d8SMatthew Dillon humanize_unsigned(buf, sizeof(buf), dedup_ref_size, "B", 1024);
3663a92efe3SAntonio Huete Jimenez printf("Dedup ratio = %.2f (in this run)\n"
367bb29b5d8SMatthew Dillon " %8s referenced\n",
368eae1bb35SIlya Dryomov ((dedup_alloc_size != 0) ?
369eae1bb35SIlya Dryomov (double)dedup_ref_size / dedup_alloc_size : 0),
370bb29b5d8SMatthew Dillon buf
371bb29b5d8SMatthew Dillon );
372bb29b5d8SMatthew Dillon humanize_unsigned(buf, sizeof(buf), dedup_alloc_size, "B", 1024);
373bb29b5d8SMatthew Dillon printf(" %8s allocated\n", buf);
374bb29b5d8SMatthew Dillon humanize_unsigned(buf, sizeof(buf), dedup_skipped_size, "B", 1024);
375bb29b5d8SMatthew Dillon printf(" %8s skipped\n", buf);
376bb29b5d8SMatthew Dillon printf(" %8jd CRC collisions\n"
377bb29b5d8SMatthew Dillon " %8jd SHA collisions\n"
378a981af19STomohiro Kusumi " %8jd big-block underflows\n"
37917882027SMatthew Dillon " %8jd new dedup records\n"
38017882027SMatthew Dillon " %8jd new dedup bytes\n",
381bb29b5d8SMatthew Dillon (intmax_t)dedup_crc_failures,
382bb29b5d8SMatthew Dillon (intmax_t)dedup_sha_failures,
38317882027SMatthew Dillon (intmax_t)dedup_underflows,
38417882027SMatthew Dillon (intmax_t)dedup_successes_count,
38517882027SMatthew Dillon (intmax_t)dedup_successes_bytes
386bb29b5d8SMatthew Dillon );
3873a92efe3SAntonio Huete Jimenez
3883a92efe3SAntonio Huete Jimenez /* Once completed remove cycle file */
3893a92efe3SAntonio Huete Jimenez hammer_reset_cycle();
3903a92efe3SAntonio Huete Jimenez
3913a92efe3SAntonio Huete Jimenez /* We don't want to mess up with other directives */
3923a92efe3SAntonio Huete Jimenez if (needfree) {
3933a92efe3SAntonio Huete Jimenez free(tmp);
3943a92efe3SAntonio Huete Jimenez CyclePath = NULL;
3953a92efe3SAntonio Huete Jimenez }
396bb29b5d8SMatthew Dillon }
397bb29b5d8SMatthew Dillon
398005a4da7STomohiro Kusumi static
399005a4da7STomohiro Kusumi int
count_btree_elm(hammer_btree_leaf_elm_t scan_leaf __unused,int flags __unused)400e9c8ad3dSMatthew Dillon count_btree_elm(hammer_btree_leaf_elm_t scan_leaf __unused, int flags __unused)
401e9c8ad3dSMatthew Dillon {
402e9c8ad3dSMatthew Dillon return(1);
403e9c8ad3dSMatthew Dillon }
404e9c8ad3dSMatthew Dillon
405005a4da7STomohiro Kusumi static
406005a4da7STomohiro Kusumi int
collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf,int flags __unused)407bb29b5d8SMatthew Dillon collect_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags __unused)
408bb29b5d8SMatthew Dillon {
409bb29b5d8SMatthew Dillon struct sim_dedup_entry *sim_de;
410bb29b5d8SMatthew Dillon
411fbe1c665SMatthew Dillon /*
412fbe1c665SMatthew Dillon * If we are using too much memory we have to clean some out, which
413fbe1c665SMatthew Dillon * will cause the run to use multiple passes. Be careful of integer
414fbe1c665SMatthew Dillon * overflows!
415fbe1c665SMatthew Dillon */
416fbe1c665SMatthew Dillon if (MemoryUse > MemoryLimit) {
417fbe1c665SMatthew Dillon DedupCrcEnd = DedupCrcStart +
41846137e17STomohiro Kusumi (uint32_t)(DedupCrcEnd - DedupCrcStart - 1) / 2;
419fbe1c665SMatthew Dillon if (VerboseOpt) {
420fbe1c665SMatthew Dillon printf("memory limit crc-range %08x-%08x\n",
421fbe1c665SMatthew Dillon DedupCrcStart, DedupCrcEnd);
422fbe1c665SMatthew Dillon fflush(stdout);
423fbe1c665SMatthew Dillon }
424fbe1c665SMatthew Dillon for (;;) {
425fbe1c665SMatthew Dillon sim_de = RB_MAX(sim_dedup_entry_rb_tree,
426fbe1c665SMatthew Dillon &sim_dedup_tree);
427fbe1c665SMatthew Dillon if (sim_de == NULL || sim_de->crc < DedupCrcEnd)
428fbe1c665SMatthew Dillon break;
429fbe1c665SMatthew Dillon RB_REMOVE(sim_dedup_entry_rb_tree,
430fbe1c665SMatthew Dillon &sim_dedup_tree, sim_de);
431fbe1c665SMatthew Dillon MemoryUse -= sizeof(*sim_de);
432fbe1c665SMatthew Dillon free(sim_de);
433fbe1c665SMatthew Dillon }
434fbe1c665SMatthew Dillon }
435fbe1c665SMatthew Dillon
436fbe1c665SMatthew Dillon /*
437fbe1c665SMatthew Dillon * Collect statistics based on the CRC only, do not try to read
438fbe1c665SMatthew Dillon * any data blocks or run SHA hashes.
439fbe1c665SMatthew Dillon */
440e9c8ad3dSMatthew Dillon sim_de = RB_LOOKUP(sim_dedup_entry_rb_tree, &sim_dedup_tree,
441e9c8ad3dSMatthew Dillon scan_leaf->data_crc);
442bb29b5d8SMatthew Dillon
443bb29b5d8SMatthew Dillon if (sim_de == NULL) {
444c8f165e2STomohiro Kusumi sim_de = calloc(1, sizeof(*sim_de));
445bb29b5d8SMatthew Dillon sim_de->crc = scan_leaf->data_crc;
446bb29b5d8SMatthew Dillon RB_INSERT(sim_dedup_entry_rb_tree, &sim_dedup_tree, sim_de);
447fbe1c665SMatthew Dillon MemoryUse += sizeof(*sim_de);
448bb29b5d8SMatthew Dillon }
449bb29b5d8SMatthew Dillon
450bb29b5d8SMatthew Dillon sim_de->ref_blks += 1;
451bb29b5d8SMatthew Dillon sim_de->ref_size += scan_leaf->data_len;
452bb29b5d8SMatthew Dillon return (1);
453bb29b5d8SMatthew Dillon }
454bb29b5d8SMatthew Dillon
455005a4da7STomohiro Kusumi static __inline
456005a4da7STomohiro Kusumi int
validate_dedup_pair(hammer_btree_leaf_elm_t p,hammer_btree_leaf_elm_t q)457bb29b5d8SMatthew Dillon validate_dedup_pair(hammer_btree_leaf_elm_t p, hammer_btree_leaf_elm_t q)
458bb29b5d8SMatthew Dillon {
45952e2f1b5STomohiro Kusumi if (HAMMER_ZONE(p->data_offset) != HAMMER_ZONE(q->data_offset))
460bb29b5d8SMatthew Dillon return (1);
46152e2f1b5STomohiro Kusumi if (p->data_len != q->data_len)
462bb29b5d8SMatthew Dillon return (1);
463bb29b5d8SMatthew Dillon
464bb29b5d8SMatthew Dillon return (0);
465bb29b5d8SMatthew Dillon }
466bb29b5d8SMatthew Dillon
467bb29b5d8SMatthew Dillon #define DEDUP_TECH_FAILURE 1
468bb29b5d8SMatthew Dillon #define DEDUP_CMP_FAILURE 2
469bb29b5d8SMatthew Dillon #define DEDUP_INVALID_ZONE 3
470bb29b5d8SMatthew Dillon #define DEDUP_UNDERFLOW 4
471b9956a62SMatthew Dillon #define DEDUP_VERS_FAILURE 5
472bb29b5d8SMatthew Dillon
473005a4da7STomohiro Kusumi static __inline
474005a4da7STomohiro Kusumi int
deduplicate(hammer_btree_leaf_elm_t p,hammer_btree_leaf_elm_t q)475bb29b5d8SMatthew Dillon deduplicate(hammer_btree_leaf_elm_t p, hammer_btree_leaf_elm_t q)
476bb29b5d8SMatthew Dillon {
477bb29b5d8SMatthew Dillon struct hammer_ioc_dedup dedup;
478bb29b5d8SMatthew Dillon
479bb29b5d8SMatthew Dillon bzero(&dedup, sizeof(dedup));
480bb29b5d8SMatthew Dillon
481bb29b5d8SMatthew Dillon /*
482bb29b5d8SMatthew Dillon * If data_offset fields are the same there is no need to run ioctl,
483bb29b5d8SMatthew Dillon * candidate is already dedup'ed.
484bb29b5d8SMatthew Dillon */
48552e2f1b5STomohiro Kusumi if (p->data_offset == q->data_offset)
486bb29b5d8SMatthew Dillon return (0);
487bb29b5d8SMatthew Dillon
488bb29b5d8SMatthew Dillon dedup.elm1 = p->base;
489bb29b5d8SMatthew Dillon dedup.elm2 = q->base;
490bb29b5d8SMatthew Dillon RunningIoctl = 1;
491bb29b5d8SMatthew Dillon if (ioctl(glob_fd, HAMMERIOC_DEDUP, &dedup) < 0) {
49252e2f1b5STomohiro Kusumi if (errno == EOPNOTSUPP)
49352e2f1b5STomohiro Kusumi return (DEDUP_VERS_FAILURE); /* must be at least version 5 */
494bb29b5d8SMatthew Dillon /* Technical failure - locking or w/e */
495bb29b5d8SMatthew Dillon return (DEDUP_TECH_FAILURE);
496bb29b5d8SMatthew Dillon }
49752e2f1b5STomohiro Kusumi if (dedup.head.flags & HAMMER_IOC_DEDUP_CMP_FAILURE)
498bb29b5d8SMatthew Dillon return (DEDUP_CMP_FAILURE);
49952e2f1b5STomohiro Kusumi if (dedup.head.flags & HAMMER_IOC_DEDUP_INVALID_ZONE)
500bb29b5d8SMatthew Dillon return (DEDUP_INVALID_ZONE);
50152e2f1b5STomohiro Kusumi if (dedup.head.flags & HAMMER_IOC_DEDUP_UNDERFLOW)
502bb29b5d8SMatthew Dillon return (DEDUP_UNDERFLOW);
503bb29b5d8SMatthew Dillon RunningIoctl = 0;
50417882027SMatthew Dillon ++dedup_successes_count;
50517882027SMatthew Dillon dedup_successes_bytes += p->data_len;
506bb29b5d8SMatthew Dillon return (0);
507bb29b5d8SMatthew Dillon }
508bb29b5d8SMatthew Dillon
509005a4da7STomohiro Kusumi static
510005a4da7STomohiro Kusumi int
process_btree_elm(hammer_btree_leaf_elm_t scan_leaf,int flags)511bb29b5d8SMatthew Dillon process_btree_elm(hammer_btree_leaf_elm_t scan_leaf, int flags)
512bb29b5d8SMatthew Dillon {
513bb29b5d8SMatthew Dillon struct dedup_entry *de;
514bb29b5d8SMatthew Dillon struct sha_dedup_entry *sha_de, temp;
515bb29b5d8SMatthew Dillon struct pass2_dedup_entry *pass2_de;
516bb29b5d8SMatthew Dillon int error;
517bb29b5d8SMatthew Dillon
518fbe1c665SMatthew Dillon /*
519fbe1c665SMatthew Dillon * If we are using too much memory we have to clean some out, which
520fbe1c665SMatthew Dillon * will cause the run to use multiple passes. Be careful of integer
521fbe1c665SMatthew Dillon * overflows!
522fbe1c665SMatthew Dillon */
523fbe1c665SMatthew Dillon while (MemoryUse > MemoryLimit) {
524fbe1c665SMatthew Dillon DedupCrcEnd = DedupCrcStart +
52546137e17STomohiro Kusumi (uint32_t)(DedupCrcEnd - DedupCrcStart - 1) / 2;
526fbe1c665SMatthew Dillon if (VerboseOpt) {
527fbe1c665SMatthew Dillon printf("memory limit crc-range %08x-%08x\n",
528fbe1c665SMatthew Dillon DedupCrcStart, DedupCrcEnd);
529fbe1c665SMatthew Dillon fflush(stdout);
530fbe1c665SMatthew Dillon }
531fbe1c665SMatthew Dillon
532fbe1c665SMatthew Dillon for (;;) {
533fbe1c665SMatthew Dillon de = RB_MAX(dedup_entry_rb_tree, &dedup_tree);
534fbe1c665SMatthew Dillon if (de == NULL || de->leaf.data_crc < DedupCrcEnd)
535fbe1c665SMatthew Dillon break;
536f254e677STomohiro Kusumi if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
537fbe1c665SMatthew Dillon while ((sha_de = RB_ROOT(&de->u.fict_root)) !=
538fbe1c665SMatthew Dillon NULL) {
539fbe1c665SMatthew Dillon RB_REMOVE(sha_dedup_entry_rb_tree,
540fbe1c665SMatthew Dillon &de->u.fict_root, sha_de);
541fbe1c665SMatthew Dillon MemoryUse -= sizeof(*sha_de);
542fbe1c665SMatthew Dillon free(sha_de);
543fbe1c665SMatthew Dillon }
544f254e677STomohiro Kusumi }
545fbe1c665SMatthew Dillon RB_REMOVE(dedup_entry_rb_tree, &dedup_tree, de);
546fbe1c665SMatthew Dillon MemoryUse -= sizeof(*de);
547fbe1c665SMatthew Dillon free(de);
548fbe1c665SMatthew Dillon }
549fbe1c665SMatthew Dillon }
550fbe1c665SMatthew Dillon
551fbe1c665SMatthew Dillon /*
552fbe1c665SMatthew Dillon * Collect statistics based on the CRC. Colliding CRCs usually
553fbe1c665SMatthew Dillon * cause a SHA sub-tree to be created under the de.
554fbe1c665SMatthew Dillon *
555fbe1c665SMatthew Dillon * Trivial case if de not found.
556fbe1c665SMatthew Dillon */
557bb29b5d8SMatthew Dillon de = RB_LOOKUP(dedup_entry_rb_tree, &dedup_tree, scan_leaf->data_crc);
558bb29b5d8SMatthew Dillon if (de == NULL) {
559c8f165e2STomohiro Kusumi de = calloc(1, sizeof(*de));
560bb29b5d8SMatthew Dillon de->leaf = *scan_leaf;
561bb29b5d8SMatthew Dillon RB_INSERT(dedup_entry_rb_tree, &dedup_tree, de);
562fbe1c665SMatthew Dillon MemoryUse += sizeof(*de);
563bb29b5d8SMatthew Dillon goto upgrade_stats;
564bb29b5d8SMatthew Dillon }
565bb29b5d8SMatthew Dillon
566bb29b5d8SMatthew Dillon /*
567bb29b5d8SMatthew Dillon * Found entry in CRC tree
568bb29b5d8SMatthew Dillon */
569bb29b5d8SMatthew Dillon if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
570bb29b5d8SMatthew Dillon /*
57117882027SMatthew Dillon * Optimize the case where a CRC failure results in multiple
57217882027SMatthew Dillon * SHA entries. If we unconditionally issue a data-read a
57317882027SMatthew Dillon * degenerate situation where a colliding CRC's second SHA
57417882027SMatthew Dillon * entry contains the lion's share of the deduplication
57517882027SMatthew Dillon * candidates will result in excessive data block reads.
57617882027SMatthew Dillon *
57717882027SMatthew Dillon * Deal with the degenerate case by looking for a matching
57817882027SMatthew Dillon * data_offset/data_len in the SHA elements we already have
57917882027SMatthew Dillon * before reading the data block and generating a new SHA.
58017882027SMatthew Dillon */
581f254e677STomohiro Kusumi RB_FOREACH(sha_de, sha_dedup_entry_rb_tree, &de->u.fict_root) {
58217882027SMatthew Dillon if (sha_de->leaf.data_offset ==
58317882027SMatthew Dillon scan_leaf->data_offset &&
58417882027SMatthew Dillon sha_de->leaf.data_len == scan_leaf->data_len) {
58517882027SMatthew Dillon memcpy(temp.sha_hash, sha_de->sha_hash,
58617882027SMatthew Dillon SHA256_DIGEST_LENGTH);
58717882027SMatthew Dillon break;
58817882027SMatthew Dillon }
589f254e677STomohiro Kusumi }
59017882027SMatthew Dillon
59117882027SMatthew Dillon /*
592e8b22b55SSascha Wildner * Entry in CRC tree is fictitious, so we already had problems
593bb29b5d8SMatthew Dillon * with this CRC. Upgrade (compute SHA) the candidate and
594bb29b5d8SMatthew Dillon * dive into SHA subtree. If upgrade fails insert the candidate
595bb29b5d8SMatthew Dillon * into Pass2 list (it will be processed later).
596bb29b5d8SMatthew Dillon */
59717882027SMatthew Dillon if (sha_de == NULL) {
598bb29b5d8SMatthew Dillon if (upgrade_chksum(scan_leaf, temp.sha_hash))
599bb29b5d8SMatthew Dillon goto pass2_insert;
600bb29b5d8SMatthew Dillon
60117882027SMatthew Dillon sha_de = RB_FIND(sha_dedup_entry_rb_tree,
60217882027SMatthew Dillon &de->u.fict_root, &temp);
60317882027SMatthew Dillon }
60417882027SMatthew Dillon
605bb29b5d8SMatthew Dillon /*
606bb29b5d8SMatthew Dillon * Nothing in SHA subtree so far, so this is a new
607bb29b5d8SMatthew Dillon * 'dataset'. Insert new entry into SHA subtree.
608bb29b5d8SMatthew Dillon */
60917882027SMatthew Dillon if (sha_de == NULL) {
610c8f165e2STomohiro Kusumi sha_de = calloc(1, sizeof(*sha_de));
611bb29b5d8SMatthew Dillon sha_de->leaf = *scan_leaf;
61217882027SMatthew Dillon memcpy(sha_de->sha_hash, temp.sha_hash,
61317882027SMatthew Dillon SHA256_DIGEST_LENGTH);
61417882027SMatthew Dillon RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root,
61517882027SMatthew Dillon sha_de);
616fbe1c665SMatthew Dillon MemoryUse += sizeof(*sha_de);
617bb29b5d8SMatthew Dillon goto upgrade_stats_sha;
618bb29b5d8SMatthew Dillon }
619bb29b5d8SMatthew Dillon
620bb29b5d8SMatthew Dillon /*
621bb29b5d8SMatthew Dillon * Found entry in SHA subtree, it means we have a potential
622bb29b5d8SMatthew Dillon * dedup pair. Validate it (zones have to match and data_len
623bb29b5d8SMatthew Dillon * field have to be the same too. If validation fails, treat
624bb29b5d8SMatthew Dillon * it as a SHA collision (jump to sha256_failure).
625bb29b5d8SMatthew Dillon */
626bb29b5d8SMatthew Dillon if (validate_dedup_pair(&sha_de->leaf, scan_leaf))
627bb29b5d8SMatthew Dillon goto sha256_failure;
628bb29b5d8SMatthew Dillon
629bb29b5d8SMatthew Dillon /*
630bb29b5d8SMatthew Dillon * We have a valid dedup pair (SHA match, validated).
631bb29b5d8SMatthew Dillon *
632bb29b5d8SMatthew Dillon * In case of technical failure (dedup pair was good, but
633bb29b5d8SMatthew Dillon * ioctl failed anyways) insert the candidate into Pass2 list
634bb29b5d8SMatthew Dillon * (we will try to dedup it after we are done with the rest of
635bb29b5d8SMatthew Dillon * the tree).
636bb29b5d8SMatthew Dillon *
637bb29b5d8SMatthew Dillon * If ioctl fails because either of blocks is in the non-dedup
638bb29b5d8SMatthew Dillon * zone (we can dedup only in LARGE_DATA and SMALL_DATA) don't
639bb29b5d8SMatthew Dillon * bother with the candidate and terminate early.
640bb29b5d8SMatthew Dillon *
641a981af19STomohiro Kusumi * If ioctl fails because of big-block underflow replace the
642bb29b5d8SMatthew Dillon * leaf node that found dedup entry represents with scan_leaf.
643bb29b5d8SMatthew Dillon */
644bb29b5d8SMatthew Dillon error = deduplicate(&sha_de->leaf, scan_leaf);
645bb29b5d8SMatthew Dillon switch(error) {
646b9956a62SMatthew Dillon case 0:
647b9956a62SMatthew Dillon goto upgrade_stats_sha;
648bb29b5d8SMatthew Dillon case DEDUP_TECH_FAILURE:
649bb29b5d8SMatthew Dillon goto pass2_insert;
650bb29b5d8SMatthew Dillon case DEDUP_CMP_FAILURE:
651bb29b5d8SMatthew Dillon goto sha256_failure;
652bb29b5d8SMatthew Dillon case DEDUP_INVALID_ZONE:
653bb29b5d8SMatthew Dillon goto terminate_early;
654bb29b5d8SMatthew Dillon case DEDUP_UNDERFLOW:
655bb29b5d8SMatthew Dillon ++dedup_underflows;
656bb29b5d8SMatthew Dillon sha_de->leaf = *scan_leaf;
65717882027SMatthew Dillon memcpy(sha_de->sha_hash, temp.sha_hash,
65817882027SMatthew Dillon SHA256_DIGEST_LENGTH);
659bb29b5d8SMatthew Dillon goto upgrade_stats_sha;
660b9956a62SMatthew Dillon case DEDUP_VERS_FAILURE:
661f4bb1f26STomohiro Kusumi errx(1, "HAMMER filesystem must be at least "
662f4bb1f26STomohiro Kusumi "version 5 to dedup");
66373cca638STomohiro Kusumi /* not reached */
664bb29b5d8SMatthew Dillon default:
665b9956a62SMatthew Dillon fprintf(stderr, "Unknown error\n");
666b9956a62SMatthew Dillon goto terminate_early;
667bb29b5d8SMatthew Dillon }
668bb29b5d8SMatthew Dillon
669bb29b5d8SMatthew Dillon /*
670bb29b5d8SMatthew Dillon * Ooh la la.. SHA-256 collision. Terminate early, there's
671bb29b5d8SMatthew Dillon * nothing we can do here.
672bb29b5d8SMatthew Dillon */
673bb29b5d8SMatthew Dillon sha256_failure:
674bb29b5d8SMatthew Dillon ++dedup_sha_failures;
675bb29b5d8SMatthew Dillon goto terminate_early;
676bb29b5d8SMatthew Dillon } else {
677bb29b5d8SMatthew Dillon /*
678bb29b5d8SMatthew Dillon * Candidate CRC is good for now (we found an entry in CRC
679e8b22b55SSascha Wildner * tree and it's not fictitious). This means we have a
680bb29b5d8SMatthew Dillon * potential dedup pair.
681bb29b5d8SMatthew Dillon */
682bb29b5d8SMatthew Dillon if (validate_dedup_pair(&de->leaf, scan_leaf))
683bb29b5d8SMatthew Dillon goto crc_failure;
684bb29b5d8SMatthew Dillon
685bb29b5d8SMatthew Dillon /*
686bb29b5d8SMatthew Dillon * We have a valid dedup pair (CRC match, validated)
687bb29b5d8SMatthew Dillon */
688bb29b5d8SMatthew Dillon error = deduplicate(&de->leaf, scan_leaf);
689bb29b5d8SMatthew Dillon switch(error) {
690b9956a62SMatthew Dillon case 0:
691b9956a62SMatthew Dillon goto upgrade_stats;
692bb29b5d8SMatthew Dillon case DEDUP_TECH_FAILURE:
693bb29b5d8SMatthew Dillon goto pass2_insert;
694bb29b5d8SMatthew Dillon case DEDUP_CMP_FAILURE:
695bb29b5d8SMatthew Dillon goto crc_failure;
696bb29b5d8SMatthew Dillon case DEDUP_INVALID_ZONE:
697bb29b5d8SMatthew Dillon goto terminate_early;
698bb29b5d8SMatthew Dillon case DEDUP_UNDERFLOW:
699bb29b5d8SMatthew Dillon ++dedup_underflows;
700bb29b5d8SMatthew Dillon de->leaf = *scan_leaf;
701bb29b5d8SMatthew Dillon goto upgrade_stats;
702b9956a62SMatthew Dillon case DEDUP_VERS_FAILURE:
703f4bb1f26STomohiro Kusumi errx(1, "HAMMER filesystem must be at least "
704f4bb1f26STomohiro Kusumi "version 5 to dedup");
70573cca638STomohiro Kusumi /* not reached */
706bb29b5d8SMatthew Dillon default:
707b9956a62SMatthew Dillon fprintf(stderr, "Unknown error\n");
708b9956a62SMatthew Dillon goto terminate_early;
709bb29b5d8SMatthew Dillon }
710bb29b5d8SMatthew Dillon
711bb29b5d8SMatthew Dillon crc_failure:
712bb29b5d8SMatthew Dillon /*
713bb29b5d8SMatthew Dillon * We got a CRC collision - either ioctl failed because of
714bb29b5d8SMatthew Dillon * the comparison failure or validation of the potential
715bb29b5d8SMatthew Dillon * dedup pair went bad. In all cases insert both blocks
716bb29b5d8SMatthew Dillon * into SHA subtree (this requires checksum upgrade) and mark
717bb29b5d8SMatthew Dillon * entry that corresponds to this CRC in the CRC tree
718e8b22b55SSascha Wildner * fictitious, so that all futher operations with this CRC go
719bb29b5d8SMatthew Dillon * through SHA subtree.
720bb29b5d8SMatthew Dillon */
721bb29b5d8SMatthew Dillon ++dedup_crc_failures;
72217882027SMatthew Dillon
723bb29b5d8SMatthew Dillon /*
724e8b22b55SSascha Wildner * Insert block that was represented by now fictitious dedup
725bb29b5d8SMatthew Dillon * entry (create a new SHA entry and preserve stats of the
726bb29b5d8SMatthew Dillon * old CRC one). If checksum upgrade fails insert the
727bb29b5d8SMatthew Dillon * candidate into Pass2 list and return - keep both trees
728bb29b5d8SMatthew Dillon * unmodified.
729bb29b5d8SMatthew Dillon */
730c8f165e2STomohiro Kusumi sha_de = calloc(1, sizeof(*sha_de));
731bb29b5d8SMatthew Dillon sha_de->leaf = de->leaf;
732bb29b5d8SMatthew Dillon sha_de->ref_blks = de->u.de.ref_blks;
733bb29b5d8SMatthew Dillon sha_de->ref_size = de->u.de.ref_size;
734bb29b5d8SMatthew Dillon if (upgrade_chksum(&sha_de->leaf, sha_de->sha_hash)) {
735bb29b5d8SMatthew Dillon free(sha_de);
736bb29b5d8SMatthew Dillon goto pass2_insert;
737bb29b5d8SMatthew Dillon }
738fbe1c665SMatthew Dillon MemoryUse += sizeof(*sha_de);
739bb29b5d8SMatthew Dillon
740bb29b5d8SMatthew Dillon RB_INIT(&de->u.fict_root);
741bb29b5d8SMatthew Dillon /*
742bb29b5d8SMatthew Dillon * Here we can insert without prior checking because the tree
743bb29b5d8SMatthew Dillon * is empty at this point
744bb29b5d8SMatthew Dillon */
745bb29b5d8SMatthew Dillon RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de);
746bb29b5d8SMatthew Dillon
747bb29b5d8SMatthew Dillon /*
748e8b22b55SSascha Wildner * Mark entry in CRC tree fictitious
749bb29b5d8SMatthew Dillon */
750bb29b5d8SMatthew Dillon de->flags |= HAMMER_DEDUP_ENTRY_FICTITIOUS;
751bb29b5d8SMatthew Dillon
752bb29b5d8SMatthew Dillon /*
753bb29b5d8SMatthew Dillon * Upgrade checksum of the candidate and insert it into
754bb29b5d8SMatthew Dillon * SHA subtree. If upgrade fails insert the candidate into
755bb29b5d8SMatthew Dillon * Pass2 list.
756bb29b5d8SMatthew Dillon */
75752e2f1b5STomohiro Kusumi if (upgrade_chksum(scan_leaf, temp.sha_hash))
758bb29b5d8SMatthew Dillon goto pass2_insert;
75917882027SMatthew Dillon sha_de = RB_FIND(sha_dedup_entry_rb_tree, &de->u.fict_root,
76017882027SMatthew Dillon &temp);
7619930da22STomohiro Kusumi if (sha_de != NULL) {
762bb29b5d8SMatthew Dillon /* There is an entry with this SHA already, but the only
763bb29b5d8SMatthew Dillon * RB-tree element at this point is that entry we just
764bb29b5d8SMatthew Dillon * added. We know for sure these blocks are different
765bb29b5d8SMatthew Dillon * (this is crc_failure branch) so treat it as SHA
766bb29b5d8SMatthew Dillon * collision.
767bb29b5d8SMatthew Dillon */
768bb29b5d8SMatthew Dillon goto sha256_failure;
7699930da22STomohiro Kusumi }
770bb29b5d8SMatthew Dillon
771c8f165e2STomohiro Kusumi sha_de = calloc(1, sizeof(*sha_de));
772bb29b5d8SMatthew Dillon sha_de->leaf = *scan_leaf;
773bb29b5d8SMatthew Dillon memcpy(sha_de->sha_hash, temp.sha_hash, SHA256_DIGEST_LENGTH);
774bb29b5d8SMatthew Dillon RB_INSERT(sha_dedup_entry_rb_tree, &de->u.fict_root, sha_de);
775fbe1c665SMatthew Dillon MemoryUse += sizeof(*sha_de);
776bb29b5d8SMatthew Dillon goto upgrade_stats_sha;
777bb29b5d8SMatthew Dillon }
778bb29b5d8SMatthew Dillon
779bb29b5d8SMatthew Dillon upgrade_stats:
780bb29b5d8SMatthew Dillon de->u.de.ref_blks += 1;
781bb29b5d8SMatthew Dillon de->u.de.ref_size += scan_leaf->data_len;
782bb29b5d8SMatthew Dillon return (1);
783bb29b5d8SMatthew Dillon
784bb29b5d8SMatthew Dillon upgrade_stats_sha:
785bb29b5d8SMatthew Dillon sha_de->ref_blks += 1;
786bb29b5d8SMatthew Dillon sha_de->ref_size += scan_leaf->data_len;
787bb29b5d8SMatthew Dillon return (1);
788bb29b5d8SMatthew Dillon
789bb29b5d8SMatthew Dillon pass2_insert:
790bb29b5d8SMatthew Dillon /*
791bb29b5d8SMatthew Dillon * If in pass2 mode don't insert anything, fall through to
792bb29b5d8SMatthew Dillon * terminate_early
793bb29b5d8SMatthew Dillon */
794bb29b5d8SMatthew Dillon if ((flags & DEDUP_PASS2) == 0) {
795c8f165e2STomohiro Kusumi pass2_de = calloc(1, sizeof(*pass2_de));
796bb29b5d8SMatthew Dillon pass2_de->leaf = *scan_leaf;
797bb29b5d8SMatthew Dillon STAILQ_INSERT_TAIL(&pass2_dedup_queue, pass2_de, sq_entry);
798bb29b5d8SMatthew Dillon dedup_skipped_size += scan_leaf->data_len;
799bb29b5d8SMatthew Dillon return (1);
800bb29b5d8SMatthew Dillon }
801bb29b5d8SMatthew Dillon
802bb29b5d8SMatthew Dillon terminate_early:
803bb29b5d8SMatthew Dillon /*
804bb29b5d8SMatthew Dillon * Early termination path. Fixup stats.
805bb29b5d8SMatthew Dillon */
806bb29b5d8SMatthew Dillon dedup_alloc_size += scan_leaf->data_len;
807bb29b5d8SMatthew Dillon dedup_ref_size += scan_leaf->data_len;
808bb29b5d8SMatthew Dillon return (0);
809bb29b5d8SMatthew Dillon }
810bb29b5d8SMatthew Dillon
811005a4da7STomohiro Kusumi static
812005a4da7STomohiro Kusumi int
upgrade_chksum(hammer_btree_leaf_elm_t leaf,uint8_t * sha_hash)81346137e17STomohiro Kusumi upgrade_chksum(hammer_btree_leaf_elm_t leaf, uint8_t *sha_hash)
814bb29b5d8SMatthew Dillon {
815bb29b5d8SMatthew Dillon struct hammer_ioc_data data;
816bb29b5d8SMatthew Dillon char *buf = malloc(DEDUP_BUF);
817bb29b5d8SMatthew Dillon SHA256_CTX ctx;
818bb29b5d8SMatthew Dillon int error;
819bb29b5d8SMatthew Dillon
820bb29b5d8SMatthew Dillon bzero(&data, sizeof(data));
821bb29b5d8SMatthew Dillon data.elm = leaf->base;
822bb29b5d8SMatthew Dillon data.ubuf = buf;
823bb29b5d8SMatthew Dillon data.size = DEDUP_BUF;
824bb29b5d8SMatthew Dillon
825bb29b5d8SMatthew Dillon error = 0;
826bb29b5d8SMatthew Dillon if (ioctl(glob_fd, HAMMERIOC_GET_DATA, &data) < 0) {
827bb29b5d8SMatthew Dillon fprintf(stderr, "Get-data failed: %s\n", strerror(errno));
828bb29b5d8SMatthew Dillon error = 1;
829bb29b5d8SMatthew Dillon goto done;
830bb29b5d8SMatthew Dillon }
831e9c8ad3dSMatthew Dillon DedupDataReads += leaf->data_len;
832bb29b5d8SMatthew Dillon
833bb29b5d8SMatthew Dillon if (data.leaf.data_len != leaf->data_len) {
834bb29b5d8SMatthew Dillon error = 1;
835bb29b5d8SMatthew Dillon goto done;
836bb29b5d8SMatthew Dillon }
837bb29b5d8SMatthew Dillon
838bb29b5d8SMatthew Dillon if (data.leaf.base.btype == HAMMER_BTREE_TYPE_RECORD &&
839bb29b5d8SMatthew Dillon data.leaf.base.rec_type == HAMMER_RECTYPE_DATA) {
840bb29b5d8SMatthew Dillon SHA256_Init(&ctx);
841bb29b5d8SMatthew Dillon SHA256_Update(&ctx, (void *)buf, data.leaf.data_len);
842bb29b5d8SMatthew Dillon SHA256_Final(sha_hash, &ctx);
843bb29b5d8SMatthew Dillon }
844bb29b5d8SMatthew Dillon
845bb29b5d8SMatthew Dillon done:
846bb29b5d8SMatthew Dillon free(buf);
847bb29b5d8SMatthew Dillon return (error);
848bb29b5d8SMatthew Dillon }
849bb29b5d8SMatthew Dillon
850005a4da7STomohiro Kusumi static
851005a4da7STomohiro Kusumi void
sigAlrm(int signo __unused)8523a92efe3SAntonio Huete Jimenez sigAlrm(int signo __unused)
8533a92efe3SAntonio Huete Jimenez {
8543a92efe3SAntonio Huete Jimenez SigAlrmFlag = 1;
8553a92efe3SAntonio Huete Jimenez }
8563a92efe3SAntonio Huete Jimenez
857005a4da7STomohiro Kusumi static
858005a4da7STomohiro Kusumi void
sigInfo(int signo __unused)859e9c8ad3dSMatthew Dillon sigInfo(int signo __unused)
860e9c8ad3dSMatthew Dillon {
861e9c8ad3dSMatthew Dillon SigInfoFlag = 1;
862e9c8ad3dSMatthew Dillon }
863e9c8ad3dSMatthew Dillon
864005a4da7STomohiro Kusumi static
865005a4da7STomohiro Kusumi void
scan_pfs(char * filesystem,scan_pfs_cb_t func,const char * id)866e9c8ad3dSMatthew Dillon scan_pfs(char *filesystem, scan_pfs_cb_t func, const char *id)
867bb29b5d8SMatthew Dillon {
868bb29b5d8SMatthew Dillon struct hammer_ioc_mirror_rw mirror;
869bb29b5d8SMatthew Dillon hammer_ioc_mrecord_any_t mrec;
870bb29b5d8SMatthew Dillon struct hammer_btree_leaf_elm elm;
871bb29b5d8SMatthew Dillon char *buf = malloc(DEDUP_BUF);
872fbe1c665SMatthew Dillon char buf1[8];
873fbe1c665SMatthew Dillon char buf2[8];
874bb29b5d8SMatthew Dillon int offset, bytes;
875bb29b5d8SMatthew Dillon
876e9c8ad3dSMatthew Dillon SigInfoFlag = 0;
877e9c8ad3dSMatthew Dillon DedupDataReads = 0;
878e9c8ad3dSMatthew Dillon DedupCurrentRecords = 0;
879e9c8ad3dSMatthew Dillon signal(SIGINFO, sigInfo);
8803a92efe3SAntonio Huete Jimenez signal(SIGALRM, sigAlrm);
881e9c8ad3dSMatthew Dillon
8823a92efe3SAntonio Huete Jimenez /*
8833a92efe3SAntonio Huete Jimenez * Deduplication happens per element so hammer(8) is in full
8843a92efe3SAntonio Huete Jimenez * control of the ioctl()s to actually perform it. SIGALRM
8853a92efe3SAntonio Huete Jimenez * needs to be handled within hammer(8) but a checkpoint
8863a92efe3SAntonio Huete Jimenez * is needed for resuming. Use cycle file for that.
8873a92efe3SAntonio Huete Jimenez *
8883a92efe3SAntonio Huete Jimenez * Try to obtain the previous obj_id from the cycle file and
8893a92efe3SAntonio Huete Jimenez * if not available just start from the beginning.
8903a92efe3SAntonio Huete Jimenez */
891bb29b5d8SMatthew Dillon bzero(&mirror, sizeof(mirror));
892bb29b5d8SMatthew Dillon hammer_key_beg_init(&mirror.key_beg);
8933a92efe3SAntonio Huete Jimenez hammer_get_cycle(&mirror.key_beg, &mirror.tid_beg);
8943a92efe3SAntonio Huete Jimenez
895f254e677STomohiro Kusumi if (mirror.key_beg.obj_id != (int64_t)HAMMER_MIN_OBJID) {
8969930da22STomohiro Kusumi if (VerboseOpt) {
8973a92efe3SAntonio Huete Jimenez fprintf(stderr, "%s: mirror-read: Resuming at object %016jx\n",
8983a92efe3SAntonio Huete Jimenez id, (uintmax_t)mirror.key_beg.obj_id);
899f254e677STomohiro Kusumi }
9009930da22STomohiro Kusumi }
9013a92efe3SAntonio Huete Jimenez
902bb29b5d8SMatthew Dillon hammer_key_end_init(&mirror.key_end);
903bb29b5d8SMatthew Dillon
904bb29b5d8SMatthew Dillon mirror.tid_beg = glob_pfs.ondisk->sync_beg_tid;
905bb29b5d8SMatthew Dillon mirror.tid_end = glob_pfs.ondisk->sync_end_tid;
906bb29b5d8SMatthew Dillon mirror.head.flags |= HAMMER_IOC_MIRROR_NODATA; /* we want only keys */
907bb29b5d8SMatthew Dillon mirror.ubuf = buf;
908bb29b5d8SMatthew Dillon mirror.size = DEDUP_BUF;
909bb29b5d8SMatthew Dillon mirror.pfs_id = glob_pfs.pfs_id;
910bb29b5d8SMatthew Dillon mirror.shared_uuid = glob_pfs.ondisk->shared_uuid;
911bb29b5d8SMatthew Dillon
912fbe1c665SMatthew Dillon if (VerboseOpt && DedupCrcStart == 0) {
913fbe1c665SMatthew Dillon printf("%s %s: objspace %016jx:%04x %016jx:%04x\n",
914e9c8ad3dSMatthew Dillon id, filesystem,
915bb29b5d8SMatthew Dillon (uintmax_t)mirror.key_beg.obj_id,
916bb29b5d8SMatthew Dillon mirror.key_beg.localization,
917bb29b5d8SMatthew Dillon (uintmax_t)mirror.key_end.obj_id,
918fbe1c665SMatthew Dillon mirror.key_end.localization);
919fbe1c665SMatthew Dillon printf("%s %s: pfs_id %d\n",
920fbe1c665SMatthew Dillon id, filesystem, glob_pfs.pfs_id);
921fbe1c665SMatthew Dillon }
922bb29b5d8SMatthew Dillon fflush(stdout);
923fbe1c665SMatthew Dillon fflush(stderr);
924bb29b5d8SMatthew Dillon
925bb29b5d8SMatthew Dillon do {
926bb29b5d8SMatthew Dillon mirror.count = 0;
927bb29b5d8SMatthew Dillon mirror.pfs_id = glob_pfs.pfs_id;
928bb29b5d8SMatthew Dillon mirror.shared_uuid = glob_pfs.ondisk->shared_uuid;
929052fd72bSTomohiro Kusumi if (ioctl(glob_fd, HAMMERIOC_MIRROR_READ, &mirror) < 0) {
93002318f07STomohiro Kusumi err(1, "Mirror-read %s failed", filesystem);
931052fd72bSTomohiro Kusumi /* not reached */
932052fd72bSTomohiro Kusumi }
933052fd72bSTomohiro Kusumi if (mirror.head.flags & HAMMER_IOC_HEAD_ERROR) {
93402318f07STomohiro Kusumi errx(1, "Mirror-read %s fatal error %d",
935bb29b5d8SMatthew Dillon filesystem, mirror.head.error);
936052fd72bSTomohiro Kusumi /* not reached */
937052fd72bSTomohiro Kusumi }
938bb29b5d8SMatthew Dillon if (mirror.count) {
939bb29b5d8SMatthew Dillon offset = 0;
940bb29b5d8SMatthew Dillon while (offset < mirror.count) {
941bb29b5d8SMatthew Dillon mrec = (void *)((char *)buf + offset);
942bb29b5d8SMatthew Dillon bytes = HAMMER_HEAD_DOALIGN(mrec->head.rec_size);
94373cca638STomohiro Kusumi if (offset + bytes > mirror.count) {
94402318f07STomohiro Kusumi errx(1, "Misaligned record");
94573cca638STomohiro Kusumi /* not reached */
94673cca638STomohiro Kusumi }
947bb29b5d8SMatthew Dillon assert((mrec->head.type &
948fbe1c665SMatthew Dillon HAMMER_MRECF_TYPE_MASK) ==
949fbe1c665SMatthew Dillon HAMMER_MREC_TYPE_REC);
950bb29b5d8SMatthew Dillon offset += bytes;
951fbe1c665SMatthew Dillon elm = mrec->rec.leaf;
952fbe1c665SMatthew Dillon if (elm.base.btype != HAMMER_BTREE_TYPE_RECORD)
953fbe1c665SMatthew Dillon continue;
954fbe1c665SMatthew Dillon if (elm.base.rec_type != HAMMER_RECTYPE_DATA)
955fbe1c665SMatthew Dillon continue;
956fbe1c665SMatthew Dillon ++DedupCurrentRecords;
957fbe1c665SMatthew Dillon if (DedupCrcStart != DedupCrcEnd) {
958fbe1c665SMatthew Dillon if (elm.data_crc < DedupCrcStart)
959fbe1c665SMatthew Dillon continue;
960fbe1c665SMatthew Dillon if (DedupCrcEnd &&
961f254e677STomohiro Kusumi elm.data_crc >= DedupCrcEnd) {
962fbe1c665SMatthew Dillon continue;
963fbe1c665SMatthew Dillon }
964f254e677STomohiro Kusumi }
965fbe1c665SMatthew Dillon func(&elm, 0);
966bb29b5d8SMatthew Dillon }
967bb29b5d8SMatthew Dillon }
968bb29b5d8SMatthew Dillon mirror.key_beg = mirror.key_cur;
9693a92efe3SAntonio Huete Jimenez if (DidInterrupt || SigAlrmFlag) {
9709930da22STomohiro Kusumi if (VerboseOpt) {
9713a92efe3SAntonio Huete Jimenez fprintf(stderr, "%s\n",
9723a92efe3SAntonio Huete Jimenez (DidInterrupt ? "Interrupted" : "Timeout"));
9739930da22STomohiro Kusumi }
9743a92efe3SAntonio Huete Jimenez hammer_set_cycle(&mirror.key_cur, mirror.tid_beg);
9759930da22STomohiro Kusumi if (VerboseOpt) {
9763a92efe3SAntonio Huete Jimenez fprintf(stderr, "Cyclefile %s updated for "
9773a92efe3SAntonio Huete Jimenez "continuation\n", CyclePath);
9789930da22STomohiro Kusumi }
979e9c8ad3dSMatthew Dillon exit(1);
980e9c8ad3dSMatthew Dillon }
981e9c8ad3dSMatthew Dillon if (SigInfoFlag) {
982e9c8ad3dSMatthew Dillon if (DedupTotalRecords) {
983fbe1c665SMatthew Dillon humanize_unsigned(buf1, sizeof(buf1),
984fbe1c665SMatthew Dillon DedupDataReads,
985fbe1c665SMatthew Dillon "B", 1024);
986fbe1c665SMatthew Dillon humanize_unsigned(buf2, sizeof(buf2),
987fbe1c665SMatthew Dillon dedup_successes_bytes,
988fbe1c665SMatthew Dillon "B", 1024);
98917882027SMatthew Dillon fprintf(stderr, "%s count %7jd/%jd "
990e9c8ad3dSMatthew Dillon "(%02d.%02d%%) "
991fbe1c665SMatthew Dillon "ioread %s newddup %s\n",
992e9c8ad3dSMatthew Dillon id,
993e9c8ad3dSMatthew Dillon (intmax_t)DedupCurrentRecords,
994e9c8ad3dSMatthew Dillon (intmax_t)DedupTotalRecords,
995e9c8ad3dSMatthew Dillon (int)(DedupCurrentRecords * 100 /
996e9c8ad3dSMatthew Dillon DedupTotalRecords),
997e9c8ad3dSMatthew Dillon (int)(DedupCurrentRecords * 10000 /
998e9c8ad3dSMatthew Dillon DedupTotalRecords % 100),
999fbe1c665SMatthew Dillon buf1, buf2);
1000e9c8ad3dSMatthew Dillon } else {
100117882027SMatthew Dillon fprintf(stderr, "%s count %-7jd\n",
1002e9c8ad3dSMatthew Dillon id,
1003e9c8ad3dSMatthew Dillon (intmax_t)DedupCurrentRecords);
1004e9c8ad3dSMatthew Dillon }
1005e9c8ad3dSMatthew Dillon SigInfoFlag = 0;
1006e9c8ad3dSMatthew Dillon }
1007bb29b5d8SMatthew Dillon } while (mirror.count != 0);
1008bb29b5d8SMatthew Dillon
1009e9c8ad3dSMatthew Dillon signal(SIGINFO, SIG_IGN);
10103a92efe3SAntonio Huete Jimenez signal(SIGALRM, SIG_IGN);
1011e9c8ad3dSMatthew Dillon
1012bb29b5d8SMatthew Dillon free(buf);
1013bb29b5d8SMatthew Dillon }
1014bb29b5d8SMatthew Dillon
1015005a4da7STomohiro Kusumi static
1016005a4da7STomohiro Kusumi void
dump_simulated_dedup(void)1017bb29b5d8SMatthew Dillon dump_simulated_dedup(void)
1018bb29b5d8SMatthew Dillon {
1019bb29b5d8SMatthew Dillon struct sim_dedup_entry *sim_de;
1020bb29b5d8SMatthew Dillon
1021bb29b5d8SMatthew Dillon printf("=== Dumping simulated dedup entries:\n");
1022f254e677STomohiro Kusumi RB_FOREACH(sim_de, sim_dedup_entry_rb_tree, &sim_dedup_tree) {
10231477c82aSMatthew Dillon printf("\tcrc=%08x cnt=%ju size=%ju\n",
10241477c82aSMatthew Dillon sim_de->crc,
10251f5e0b99SSascha Wildner (uintmax_t)sim_de->ref_blks,
10261f5e0b99SSascha Wildner (uintmax_t)sim_de->ref_size);
1027f254e677STomohiro Kusumi }
1028bb29b5d8SMatthew Dillon printf("end of dump ===\n");
1029bb29b5d8SMatthew Dillon }
1030bb29b5d8SMatthew Dillon
1031005a4da7STomohiro Kusumi static
1032005a4da7STomohiro Kusumi void
dump_real_dedup(void)1033bb29b5d8SMatthew Dillon dump_real_dedup(void)
1034bb29b5d8SMatthew Dillon {
1035bb29b5d8SMatthew Dillon struct dedup_entry *de;
1036bb29b5d8SMatthew Dillon struct sha_dedup_entry *sha_de;
1037bb29b5d8SMatthew Dillon int i;
1038bb29b5d8SMatthew Dillon
1039bb29b5d8SMatthew Dillon printf("=== Dumping dedup entries:\n");
1040bb29b5d8SMatthew Dillon RB_FOREACH(de, dedup_entry_rb_tree, &dedup_tree) {
1041bb29b5d8SMatthew Dillon if (de->flags & HAMMER_DEDUP_ENTRY_FICTITIOUS) {
1042e8b22b55SSascha Wildner printf("\tcrc=%08x fictitious\n", de->leaf.data_crc);
1043bb29b5d8SMatthew Dillon
1044bb29b5d8SMatthew Dillon RB_FOREACH(sha_de, sha_dedup_entry_rb_tree, &de->u.fict_root) {
10451477c82aSMatthew Dillon printf("\t\tcrc=%08x cnt=%ju size=%ju\n\t"
10461477c82aSMatthew Dillon "\t\tsha=",
1047bb29b5d8SMatthew Dillon sha_de->leaf.data_crc,
10481f5e0b99SSascha Wildner (uintmax_t)sha_de->ref_blks,
10491f5e0b99SSascha Wildner (uintmax_t)sha_de->ref_size);
1050bb29b5d8SMatthew Dillon for (i = 0; i < SHA256_DIGEST_LENGTH; ++i)
1051bb29b5d8SMatthew Dillon printf("%02x", sha_de->sha_hash[i]);
1052bb29b5d8SMatthew Dillon printf("\n");
1053bb29b5d8SMatthew Dillon }
1054bb29b5d8SMatthew Dillon } else {
10551477c82aSMatthew Dillon printf("\tcrc=%08x cnt=%ju size=%ju\n",
1056bb29b5d8SMatthew Dillon de->leaf.data_crc,
10571f5e0b99SSascha Wildner (uintmax_t)de->u.de.ref_blks,
10581f5e0b99SSascha Wildner (uintmax_t)de->u.de.ref_size);
1059bb29b5d8SMatthew Dillon }
1060bb29b5d8SMatthew Dillon }
1061bb29b5d8SMatthew Dillon printf("end of dump ===\n");
1062bb29b5d8SMatthew Dillon }
1063bb29b5d8SMatthew Dillon
1064005a4da7STomohiro Kusumi static
1065005a4da7STomohiro Kusumi void
dedup_usage(int code)1066bb29b5d8SMatthew Dillon dedup_usage(int code)
1067bb29b5d8SMatthew Dillon {
1068bb29b5d8SMatthew Dillon fprintf(stderr,
1069bb29b5d8SMatthew Dillon "hammer dedup-simulate <filesystem>\n"
1070bb29b5d8SMatthew Dillon "hammer dedup <filesystem>\n"
1071bb29b5d8SMatthew Dillon );
1072bb29b5d8SMatthew Dillon exit(code);
1073bb29b5d8SMatthew Dillon }
1074