xref: /illumos-gate/usr/src/uts/common/fs/zfs/ddt.c (revision 4d7988d6)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
24  * Copyright (c) 2012, 2016 by Delphix. All rights reserved.
25  */
26 
27 #include <sys/zfs_context.h>
28 #include <sys/spa.h>
29 #include <sys/spa_impl.h>
30 #include <sys/zio.h>
31 #include <sys/ddt.h>
32 #include <sys/zap.h>
33 #include <sys/dmu_tx.h>
34 #include <sys/arc.h>
35 #include <sys/dsl_pool.h>
36 #include <sys/zio_checksum.h>
37 #include <sys/zio_compress.h>
38 #include <sys/dsl_scan.h>
39 #include <sys/abd.h>
40 
41 /*
42  * Enable/disable prefetching of dedup-ed blocks which are going to be freed.
43  */
44 int zfs_dedup_prefetch = 1;
45 
46 static const ddt_ops_t *ddt_ops[DDT_TYPES] = {
47 	&ddt_zap_ops,
48 };
49 
50 static const char *ddt_class_name[DDT_CLASSES] = {
51 	"ditto",
52 	"duplicate",
53 	"unique",
54 };
55 
56 static void
ddt_object_create(ddt_t * ddt,enum ddt_type type,enum ddt_class class,dmu_tx_t * tx)57 ddt_object_create(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
58     dmu_tx_t *tx)
59 {
60 	spa_t *spa = ddt->ddt_spa;
61 	objset_t *os = ddt->ddt_os;
62 	uint64_t *objectp = &ddt->ddt_object[type][class];
63 	boolean_t prehash = zio_checksum_table[ddt->ddt_checksum].ci_flags &
64 	    ZCHECKSUM_FLAG_DEDUP;
65 	char name[DDT_NAMELEN];
66 
67 	ddt_object_name(ddt, type, class, name);
68 
69 	ASSERT(*objectp == 0);
70 	VERIFY(ddt_ops[type]->ddt_op_create(os, objectp, tx, prehash) == 0);
71 	ASSERT(*objectp != 0);
72 
73 	VERIFY(zap_add(os, DMU_POOL_DIRECTORY_OBJECT, name,
74 	    sizeof (uint64_t), 1, objectp, tx) == 0);
75 
76 	VERIFY(zap_add(os, spa->spa_ddt_stat_object, name,
77 	    sizeof (uint64_t), sizeof (ddt_histogram_t) / sizeof (uint64_t),
78 	    &ddt->ddt_histogram[type][class], tx) == 0);
79 }
80 
81 static void
ddt_object_destroy(ddt_t * ddt,enum ddt_type type,enum ddt_class class,dmu_tx_t * tx)82 ddt_object_destroy(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
83     dmu_tx_t *tx)
84 {
85 	spa_t *spa = ddt->ddt_spa;
86 	objset_t *os = ddt->ddt_os;
87 	uint64_t *objectp = &ddt->ddt_object[type][class];
88 	char name[DDT_NAMELEN];
89 
90 	ddt_object_name(ddt, type, class, name);
91 
92 	ASSERT(*objectp != 0);
93 	ASSERT(ddt_object_count(ddt, type, class) == 0);
94 	ASSERT(ddt_histogram_empty(&ddt->ddt_histogram[type][class]));
95 	VERIFY(zap_remove(os, DMU_POOL_DIRECTORY_OBJECT, name, tx) == 0);
96 	VERIFY(zap_remove(os, spa->spa_ddt_stat_object, name, tx) == 0);
97 	VERIFY(ddt_ops[type]->ddt_op_destroy(os, *objectp, tx) == 0);
98 	bzero(&ddt->ddt_object_stats[type][class], sizeof (ddt_object_t));
99 
100 	*objectp = 0;
101 }
102 
103 static int
ddt_object_load(ddt_t * ddt,enum ddt_type type,enum ddt_class class)104 ddt_object_load(ddt_t *ddt, enum ddt_type type, enum ddt_class class)
105 {
106 	ddt_object_t *ddo = &ddt->ddt_object_stats[type][class];
107 	dmu_object_info_t doi;
108 	char name[DDT_NAMELEN];
109 	int error;
110 
111 	ddt_object_name(ddt, type, class, name);
112 
113 	error = zap_lookup(ddt->ddt_os, DMU_POOL_DIRECTORY_OBJECT, name,
114 	    sizeof (uint64_t), 1, &ddt->ddt_object[type][class]);
115 
116 	if (error != 0)
117 		return (error);
118 
119 	VERIFY0(zap_lookup(ddt->ddt_os, ddt->ddt_spa->spa_ddt_stat_object, name,
120 	    sizeof (uint64_t), sizeof (ddt_histogram_t) / sizeof (uint64_t),
121 	    &ddt->ddt_histogram[type][class]));
122 
123 	/*
124 	 * Seed the cached statistics.
125 	 */
126 	VERIFY(ddt_object_info(ddt, type, class, &doi) == 0);
127 
128 	ddo->ddo_count = ddt_object_count(ddt, type, class);
129 	ddo->ddo_dspace = doi.doi_physical_blocks_512 << 9;
130 	ddo->ddo_mspace = doi.doi_fill_count * doi.doi_data_block_size;
131 
132 	return (0);
133 }
134 
135 static void
ddt_object_sync(ddt_t * ddt,enum ddt_type type,enum ddt_class class,dmu_tx_t * tx)136 ddt_object_sync(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
137     dmu_tx_t *tx)
138 {
139 	ddt_object_t *ddo = &ddt->ddt_object_stats[type][class];
140 	dmu_object_info_t doi;
141 	char name[DDT_NAMELEN];
142 
143 	ddt_object_name(ddt, type, class, name);
144 
145 	VERIFY(zap_update(ddt->ddt_os, ddt->ddt_spa->spa_ddt_stat_object, name,
146 	    sizeof (uint64_t), sizeof (ddt_histogram_t) / sizeof (uint64_t),
147 	    &ddt->ddt_histogram[type][class], tx) == 0);
148 
149 	/*
150 	 * Cache DDT statistics; this is the only time they'll change.
151 	 */
152 	VERIFY(ddt_object_info(ddt, type, class, &doi) == 0);
153 
154 	ddo->ddo_count = ddt_object_count(ddt, type, class);
155 	ddo->ddo_dspace = doi.doi_physical_blocks_512 << 9;
156 	ddo->ddo_mspace = doi.doi_fill_count * doi.doi_data_block_size;
157 }
158 
159 static int
ddt_object_lookup(ddt_t * ddt,enum ddt_type type,enum ddt_class class,ddt_entry_t * dde)160 ddt_object_lookup(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
161     ddt_entry_t *dde)
162 {
163 	if (!ddt_object_exists(ddt, type, class))
164 		return (SET_ERROR(ENOENT));
165 
166 	return (ddt_ops[type]->ddt_op_lookup(ddt->ddt_os,
167 	    ddt->ddt_object[type][class], dde));
168 }
169 
170 static void
ddt_object_prefetch(ddt_t * ddt,enum ddt_type type,enum ddt_class class,ddt_entry_t * dde)171 ddt_object_prefetch(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
172     ddt_entry_t *dde)
173 {
174 	if (!ddt_object_exists(ddt, type, class))
175 		return;
176 
177 	ddt_ops[type]->ddt_op_prefetch(ddt->ddt_os,
178 	    ddt->ddt_object[type][class], dde);
179 }
180 
181 int
ddt_object_update(ddt_t * ddt,enum ddt_type type,enum ddt_class class,ddt_entry_t * dde,dmu_tx_t * tx)182 ddt_object_update(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
183     ddt_entry_t *dde, dmu_tx_t *tx)
184 {
185 	ASSERT(ddt_object_exists(ddt, type, class));
186 
187 	return (ddt_ops[type]->ddt_op_update(ddt->ddt_os,
188 	    ddt->ddt_object[type][class], dde, tx));
189 }
190 
191 static int
ddt_object_remove(ddt_t * ddt,enum ddt_type type,enum ddt_class class,ddt_entry_t * dde,dmu_tx_t * tx)192 ddt_object_remove(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
193     ddt_entry_t *dde, dmu_tx_t *tx)
194 {
195 	ASSERT(ddt_object_exists(ddt, type, class));
196 
197 	return (ddt_ops[type]->ddt_op_remove(ddt->ddt_os,
198 	    ddt->ddt_object[type][class], dde, tx));
199 }
200 
201 int
ddt_object_walk(ddt_t * ddt,enum ddt_type type,enum ddt_class class,uint64_t * walk,ddt_entry_t * dde)202 ddt_object_walk(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
203     uint64_t *walk, ddt_entry_t *dde)
204 {
205 	ASSERT(ddt_object_exists(ddt, type, class));
206 
207 	return (ddt_ops[type]->ddt_op_walk(ddt->ddt_os,
208 	    ddt->ddt_object[type][class], dde, walk));
209 }
210 
211 uint64_t
ddt_object_count(ddt_t * ddt,enum ddt_type type,enum ddt_class class)212 ddt_object_count(ddt_t *ddt, enum ddt_type type, enum ddt_class class)
213 {
214 	ASSERT(ddt_object_exists(ddt, type, class));
215 
216 	return (ddt_ops[type]->ddt_op_count(ddt->ddt_os,
217 	    ddt->ddt_object[type][class]));
218 }
219 
220 int
ddt_object_info(ddt_t * ddt,enum ddt_type type,enum ddt_class class,dmu_object_info_t * doi)221 ddt_object_info(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
222     dmu_object_info_t *doi)
223 {
224 	if (!ddt_object_exists(ddt, type, class))
225 		return (SET_ERROR(ENOENT));
226 
227 	return (dmu_object_info(ddt->ddt_os, ddt->ddt_object[type][class],
228 	    doi));
229 }
230 
231 boolean_t
ddt_object_exists(ddt_t * ddt,enum ddt_type type,enum ddt_class class)232 ddt_object_exists(ddt_t *ddt, enum ddt_type type, enum ddt_class class)
233 {
234 	return (!!ddt->ddt_object[type][class]);
235 }
236 
237 void
ddt_object_name(ddt_t * ddt,enum ddt_type type,enum ddt_class class,char * name)238 ddt_object_name(ddt_t *ddt, enum ddt_type type, enum ddt_class class,
239     char *name)
240 {
241 	(void) sprintf(name, DMU_POOL_DDT,
242 	    zio_checksum_table[ddt->ddt_checksum].ci_name,
243 	    ddt_ops[type]->ddt_op_name, ddt_class_name[class]);
244 }
245 
246 void
ddt_bp_fill(const ddt_phys_t * ddp,blkptr_t * bp,uint64_t txg)247 ddt_bp_fill(const ddt_phys_t *ddp, blkptr_t *bp, uint64_t txg)
248 {
249 	ASSERT(txg != 0);
250 
251 	for (int d = 0; d < SPA_DVAS_PER_BP; d++)
252 		bp->blk_dva[d] = ddp->ddp_dva[d];
253 	BP_SET_BIRTH(bp, txg, ddp->ddp_phys_birth);
254 }
255 
256 /*
257  * The bp created via this function may be used for repairs and scrub, but it
258  * will be missing the salt / IV required to do a full decrypting read.
259  */
260 void
ddt_bp_create(enum zio_checksum checksum,const ddt_key_t * ddk,const ddt_phys_t * ddp,blkptr_t * bp)261 ddt_bp_create(enum zio_checksum checksum,
262     const ddt_key_t *ddk, const ddt_phys_t *ddp, blkptr_t *bp)
263 {
264 	BP_ZERO(bp);
265 
266 	if (ddp != NULL)
267 		ddt_bp_fill(ddp, bp, ddp->ddp_phys_birth);
268 
269 	bp->blk_cksum = ddk->ddk_cksum;
270 
271 	BP_SET_LSIZE(bp, DDK_GET_LSIZE(ddk));
272 	BP_SET_PSIZE(bp, DDK_GET_PSIZE(ddk));
273 	BP_SET_COMPRESS(bp, DDK_GET_COMPRESS(ddk));
274 	BP_SET_CRYPT(bp, DDK_GET_CRYPT(ddk));
275 	BP_SET_FILL(bp, 1);
276 	BP_SET_CHECKSUM(bp, checksum);
277 	BP_SET_TYPE(bp, DMU_OT_DEDUP);
278 	BP_SET_LEVEL(bp, 0);
279 	BP_SET_DEDUP(bp, 0);
280 	BP_SET_BYTEORDER(bp, ZFS_HOST_BYTEORDER);
281 }
282 
283 void
ddt_key_fill(ddt_key_t * ddk,const blkptr_t * bp)284 ddt_key_fill(ddt_key_t *ddk, const blkptr_t *bp)
285 {
286 	ddk->ddk_cksum = bp->blk_cksum;
287 	ddk->ddk_prop = 0;
288 
289 	ASSERT(BP_IS_ENCRYPTED(bp) || !BP_USES_CRYPT(bp));
290 
291 	DDK_SET_LSIZE(ddk, BP_GET_LSIZE(bp));
292 	DDK_SET_PSIZE(ddk, BP_GET_PSIZE(bp));
293 	DDK_SET_COMPRESS(ddk, BP_GET_COMPRESS(bp));
294 	DDK_SET_CRYPT(ddk, BP_USES_CRYPT(bp));
295 }
296 
297 void
ddt_phys_fill(ddt_phys_t * ddp,const blkptr_t * bp)298 ddt_phys_fill(ddt_phys_t *ddp, const blkptr_t *bp)
299 {
300 	ASSERT(ddp->ddp_phys_birth == 0);
301 
302 	for (int d = 0; d < SPA_DVAS_PER_BP; d++)
303 		ddp->ddp_dva[d] = bp->blk_dva[d];
304 	ddp->ddp_phys_birth = BP_PHYSICAL_BIRTH(bp);
305 }
306 
307 void
ddt_phys_clear(ddt_phys_t * ddp)308 ddt_phys_clear(ddt_phys_t *ddp)
309 {
310 	bzero(ddp, sizeof (*ddp));
311 }
312 
313 void
ddt_phys_addref(ddt_phys_t * ddp)314 ddt_phys_addref(ddt_phys_t *ddp)
315 {
316 	ddp->ddp_refcnt++;
317 }
318 
319 void
ddt_phys_decref(ddt_phys_t * ddp)320 ddt_phys_decref(ddt_phys_t *ddp)
321 {
322 	ASSERT((int64_t)ddp->ddp_refcnt > 0);
323 	ddp->ddp_refcnt--;
324 }
325 
326 void
ddt_phys_free(ddt_t * ddt,ddt_key_t * ddk,ddt_phys_t * ddp,uint64_t txg)327 ddt_phys_free(ddt_t *ddt, ddt_key_t *ddk, ddt_phys_t *ddp, uint64_t txg)
328 {
329 	blkptr_t blk;
330 
331 	ddt_bp_create(ddt->ddt_checksum, ddk, ddp, &blk);
332 	ddt_phys_clear(ddp);
333 	zio_free(ddt->ddt_spa, txg, &blk);
334 }
335 
336 ddt_phys_t *
ddt_phys_select(const ddt_entry_t * dde,const blkptr_t * bp)337 ddt_phys_select(const ddt_entry_t *dde, const blkptr_t *bp)
338 {
339 	ddt_phys_t *ddp = (ddt_phys_t *)dde->dde_phys;
340 
341 	for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) {
342 		if (DVA_EQUAL(BP_IDENTITY(bp), &ddp->ddp_dva[0]) &&
343 		    BP_PHYSICAL_BIRTH(bp) == ddp->ddp_phys_birth)
344 			return (ddp);
345 	}
346 	return (NULL);
347 }
348 
349 uint64_t
ddt_phys_total_refcnt(const ddt_entry_t * dde)350 ddt_phys_total_refcnt(const ddt_entry_t *dde)
351 {
352 	uint64_t refcnt = 0;
353 
354 	for (int p = DDT_PHYS_SINGLE; p <= DDT_PHYS_TRIPLE; p++)
355 		refcnt += dde->dde_phys[p].ddp_refcnt;
356 
357 	return (refcnt);
358 }
359 
360 static void
ddt_stat_generate(ddt_t * ddt,ddt_entry_t * dde,ddt_stat_t * dds)361 ddt_stat_generate(ddt_t *ddt, ddt_entry_t *dde, ddt_stat_t *dds)
362 {
363 	spa_t *spa = ddt->ddt_spa;
364 	ddt_phys_t *ddp = dde->dde_phys;
365 	ddt_key_t *ddk = &dde->dde_key;
366 	uint64_t lsize = DDK_GET_LSIZE(ddk);
367 	uint64_t psize = DDK_GET_PSIZE(ddk);
368 
369 	bzero(dds, sizeof (*dds));
370 
371 	for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) {
372 		uint64_t dsize = 0;
373 		uint64_t refcnt = ddp->ddp_refcnt;
374 
375 		if (ddp->ddp_phys_birth == 0)
376 			continue;
377 
378 		for (int d = 0; d < DDE_GET_NDVAS(dde); d++)
379 			dsize += dva_get_dsize_sync(spa, &ddp->ddp_dva[d]);
380 
381 		dds->dds_blocks += 1;
382 		dds->dds_lsize += lsize;
383 		dds->dds_psize += psize;
384 		dds->dds_dsize += dsize;
385 
386 		dds->dds_ref_blocks += refcnt;
387 		dds->dds_ref_lsize += lsize * refcnt;
388 		dds->dds_ref_psize += psize * refcnt;
389 		dds->dds_ref_dsize += dsize * refcnt;
390 	}
391 }
392 
393 void
ddt_stat_add(ddt_stat_t * dst,const ddt_stat_t * src,uint64_t neg)394 ddt_stat_add(ddt_stat_t *dst, const ddt_stat_t *src, uint64_t neg)
395 {
396 	const uint64_t *s = (const uint64_t *)src;
397 	uint64_t *d = (uint64_t *)dst;
398 	uint64_t *d_end = (uint64_t *)(dst + 1);
399 
400 	ASSERT(neg == 0 || neg == -1ULL);	/* add or subtract */
401 
402 	while (d < d_end)
403 		*d++ += (*s++ ^ neg) - neg;
404 }
405 
406 static void
ddt_stat_update(ddt_t * ddt,ddt_entry_t * dde,uint64_t neg)407 ddt_stat_update(ddt_t *ddt, ddt_entry_t *dde, uint64_t neg)
408 {
409 	ddt_stat_t dds;
410 	ddt_histogram_t *ddh;
411 	int bucket;
412 
413 	ddt_stat_generate(ddt, dde, &dds);
414 
415 	bucket = highbit64(dds.dds_ref_blocks) - 1;
416 	ASSERT(bucket >= 0);
417 
418 	ddh = &ddt->ddt_histogram[dde->dde_type][dde->dde_class];
419 
420 	ddt_stat_add(&ddh->ddh_stat[bucket], &dds, neg);
421 }
422 
423 void
ddt_histogram_add(ddt_histogram_t * dst,const ddt_histogram_t * src)424 ddt_histogram_add(ddt_histogram_t *dst, const ddt_histogram_t *src)
425 {
426 	for (int h = 0; h < 64; h++)
427 		ddt_stat_add(&dst->ddh_stat[h], &src->ddh_stat[h], 0);
428 }
429 
430 void
ddt_histogram_stat(ddt_stat_t * dds,const ddt_histogram_t * ddh)431 ddt_histogram_stat(ddt_stat_t *dds, const ddt_histogram_t *ddh)
432 {
433 	bzero(dds, sizeof (*dds));
434 
435 	for (int h = 0; h < 64; h++)
436 		ddt_stat_add(dds, &ddh->ddh_stat[h], 0);
437 }
438 
439 boolean_t
ddt_histogram_empty(const ddt_histogram_t * ddh)440 ddt_histogram_empty(const ddt_histogram_t *ddh)
441 {
442 	const uint64_t *s = (const uint64_t *)ddh;
443 	const uint64_t *s_end = (const uint64_t *)(ddh + 1);
444 
445 	while (s < s_end)
446 		if (*s++ != 0)
447 			return (B_FALSE);
448 
449 	return (B_TRUE);
450 }
451 
452 void
ddt_get_dedup_object_stats(spa_t * spa,ddt_object_t * ddo_total)453 ddt_get_dedup_object_stats(spa_t *spa, ddt_object_t *ddo_total)
454 {
455 	/* Sum the statistics we cached in ddt_object_sync(). */
456 	for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
457 		ddt_t *ddt = spa->spa_ddt[c];
458 		for (enum ddt_type type = 0; type < DDT_TYPES; type++) {
459 			for (enum ddt_class class = 0; class < DDT_CLASSES;
460 			    class++) {
461 				ddt_object_t *ddo =
462 				    &ddt->ddt_object_stats[type][class];
463 				ddo_total->ddo_count += ddo->ddo_count;
464 				ddo_total->ddo_dspace += ddo->ddo_dspace;
465 				ddo_total->ddo_mspace += ddo->ddo_mspace;
466 			}
467 		}
468 	}
469 
470 	/* ... and compute the averages. */
471 	if (ddo_total->ddo_count != 0) {
472 		ddo_total->ddo_dspace /= ddo_total->ddo_count;
473 		ddo_total->ddo_mspace /= ddo_total->ddo_count;
474 	}
475 }
476 
477 void
ddt_get_dedup_histogram(spa_t * spa,ddt_histogram_t * ddh)478 ddt_get_dedup_histogram(spa_t *spa, ddt_histogram_t *ddh)
479 {
480 	for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
481 		ddt_t *ddt = spa->spa_ddt[c];
482 		for (enum ddt_type type = 0; type < DDT_TYPES; type++) {
483 			for (enum ddt_class class = 0; class < DDT_CLASSES;
484 			    class++) {
485 				ddt_histogram_add(ddh,
486 				    &ddt->ddt_histogram_cache[type][class]);
487 			}
488 		}
489 	}
490 }
491 
492 void
ddt_get_dedup_stats(spa_t * spa,ddt_stat_t * dds_total)493 ddt_get_dedup_stats(spa_t *spa, ddt_stat_t *dds_total)
494 {
495 	ddt_histogram_t *ddh_total;
496 
497 	ddh_total = kmem_zalloc(sizeof (ddt_histogram_t), KM_SLEEP);
498 	ddt_get_dedup_histogram(spa, ddh_total);
499 	ddt_histogram_stat(dds_total, ddh_total);
500 	kmem_free(ddh_total, sizeof (ddt_histogram_t));
501 }
502 
503 uint64_t
ddt_get_dedup_dspace(spa_t * spa)504 ddt_get_dedup_dspace(spa_t *spa)
505 {
506 	ddt_stat_t dds_total = { 0 };
507 
508 	ddt_get_dedup_stats(spa, &dds_total);
509 	return (dds_total.dds_ref_dsize - dds_total.dds_dsize);
510 }
511 
512 uint64_t
ddt_get_pool_dedup_ratio(spa_t * spa)513 ddt_get_pool_dedup_ratio(spa_t *spa)
514 {
515 	ddt_stat_t dds_total = { 0 };
516 
517 	ddt_get_dedup_stats(spa, &dds_total);
518 	if (dds_total.dds_dsize == 0)
519 		return (100);
520 
521 	return (dds_total.dds_ref_dsize * 100 / dds_total.dds_dsize);
522 }
523 
524 int
ddt_ditto_copies_needed(ddt_t * ddt,ddt_entry_t * dde,ddt_phys_t * ddp_willref)525 ddt_ditto_copies_needed(ddt_t *ddt, ddt_entry_t *dde, ddt_phys_t *ddp_willref)
526 {
527 	spa_t *spa = ddt->ddt_spa;
528 	uint64_t total_refcnt = 0;
529 	uint64_t ditto = spa->spa_dedup_ditto;
530 	int total_copies = 0;
531 	int desired_copies = 0;
532 	int copies_needed = 0;
533 
534 	for (int p = DDT_PHYS_SINGLE; p <= DDT_PHYS_TRIPLE; p++) {
535 		ddt_phys_t *ddp = &dde->dde_phys[p];
536 		zio_t *zio = dde->dde_lead_zio[p];
537 		uint64_t refcnt = ddp->ddp_refcnt;	/* committed refs */
538 		if (zio != NULL)
539 			refcnt += zio->io_parent_count;	/* pending refs */
540 		if (ddp == ddp_willref)
541 			refcnt++;			/* caller's ref */
542 		if (refcnt != 0) {
543 			total_refcnt += refcnt;
544 			total_copies += p;
545 		}
546 	}
547 
548 	if (ditto == 0 || ditto > UINT32_MAX)
549 		ditto = UINT32_MAX;
550 
551 	if (total_refcnt >= 1)
552 		desired_copies++;
553 	if (total_refcnt >= ditto)
554 		desired_copies++;
555 	if (total_refcnt >= ditto * ditto)
556 		desired_copies++;
557 
558 	copies_needed = MAX(desired_copies, total_copies) - total_copies;
559 
560 	/* encrypted blocks store their IV in DVA[2] */
561 	if (DDK_GET_CRYPT(&dde->dde_key))
562 		copies_needed = MIN(copies_needed, SPA_DVAS_PER_BP - 1);
563 
564 	return (copies_needed);
565 }
566 
567 int
ddt_ditto_copies_present(ddt_entry_t * dde)568 ddt_ditto_copies_present(ddt_entry_t *dde)
569 {
570 	ddt_phys_t *ddp = &dde->dde_phys[DDT_PHYS_DITTO];
571 	dva_t *dva = ddp->ddp_dva;
572 	int copies = 0 - DVA_GET_GANG(dva);
573 
574 	for (int d = 0; d < DDE_GET_NDVAS(dde); d++, dva++)
575 		if (DVA_IS_VALID(dva))
576 			copies++;
577 
578 	ASSERT(copies >= 0 && copies < SPA_DVAS_PER_BP);
579 
580 	return (copies);
581 }
582 
583 size_t
ddt_compress(void * src,uchar_t * dst,size_t s_len,size_t d_len)584 ddt_compress(void *src, uchar_t *dst, size_t s_len, size_t d_len)
585 {
586 	uchar_t *version = dst++;
587 	int cpfunc = ZIO_COMPRESS_ZLE;
588 	zio_compress_info_t *ci = &zio_compress_table[cpfunc];
589 	size_t c_len;
590 
591 	ASSERT(d_len >= s_len + 1);	/* no compression plus version byte */
592 
593 	c_len = ci->ci_compress(src, dst, s_len, d_len - 1, ci->ci_level);
594 
595 	if (c_len == s_len) {
596 		cpfunc = ZIO_COMPRESS_OFF;
597 		bcopy(src, dst, s_len);
598 	}
599 
600 	*version = cpfunc;
601 	/* CONSTCOND */
602 	if (ZFS_HOST_BYTEORDER)
603 		*version |= DDT_COMPRESS_BYTEORDER_MASK;
604 
605 	return (c_len + 1);
606 }
607 
608 void
ddt_decompress(uchar_t * src,void * dst,size_t s_len,size_t d_len)609 ddt_decompress(uchar_t *src, void *dst, size_t s_len, size_t d_len)
610 {
611 	uchar_t version = *src++;
612 	int cpfunc = version & DDT_COMPRESS_FUNCTION_MASK;
613 	zio_compress_info_t *ci = &zio_compress_table[cpfunc];
614 
615 	if (ci->ci_decompress != NULL)
616 		(void) ci->ci_decompress(src, dst, s_len, d_len, ci->ci_level);
617 	else
618 		bcopy(src, dst, d_len);
619 
620 	if (((version & DDT_COMPRESS_BYTEORDER_MASK) != 0) !=
621 	    (ZFS_HOST_BYTEORDER != 0))
622 		byteswap_uint64_array(dst, d_len);
623 }
624 
625 ddt_t *
ddt_select_by_checksum(spa_t * spa,enum zio_checksum c)626 ddt_select_by_checksum(spa_t *spa, enum zio_checksum c)
627 {
628 	return (spa->spa_ddt[c]);
629 }
630 
631 ddt_t *
ddt_select(spa_t * spa,const blkptr_t * bp)632 ddt_select(spa_t *spa, const blkptr_t *bp)
633 {
634 	return (spa->spa_ddt[BP_GET_CHECKSUM(bp)]);
635 }
636 
637 void
ddt_enter(ddt_t * ddt)638 ddt_enter(ddt_t *ddt)
639 {
640 	mutex_enter(&ddt->ddt_lock);
641 }
642 
643 void
ddt_exit(ddt_t * ddt)644 ddt_exit(ddt_t *ddt)
645 {
646 	mutex_exit(&ddt->ddt_lock);
647 }
648 
649 static ddt_entry_t *
ddt_alloc(const ddt_key_t * ddk)650 ddt_alloc(const ddt_key_t *ddk)
651 {
652 	ddt_entry_t *dde;
653 
654 	dde = kmem_zalloc(sizeof (ddt_entry_t), KM_SLEEP);
655 	cv_init(&dde->dde_cv, NULL, CV_DEFAULT, NULL);
656 
657 	dde->dde_key = *ddk;
658 
659 	return (dde);
660 }
661 
662 static void
ddt_free(ddt_entry_t * dde)663 ddt_free(ddt_entry_t *dde)
664 {
665 	ASSERT(!dde->dde_loading);
666 
667 	for (int p = 0; p < DDT_PHYS_TYPES; p++)
668 		ASSERT(dde->dde_lead_zio[p] == NULL);
669 
670 	if (dde->dde_repair_abd != NULL)
671 		abd_free(dde->dde_repair_abd);
672 
673 	cv_destroy(&dde->dde_cv);
674 	kmem_free(dde, sizeof (*dde));
675 }
676 
677 void
ddt_remove(ddt_t * ddt,ddt_entry_t * dde)678 ddt_remove(ddt_t *ddt, ddt_entry_t *dde)
679 {
680 	ASSERT(MUTEX_HELD(&ddt->ddt_lock));
681 
682 	avl_remove(&ddt->ddt_tree, dde);
683 	ddt_free(dde);
684 }
685 
686 ddt_entry_t *
ddt_lookup(ddt_t * ddt,const blkptr_t * bp,boolean_t add)687 ddt_lookup(ddt_t *ddt, const blkptr_t *bp, boolean_t add)
688 {
689 	ddt_entry_t *dde, dde_search;
690 	enum ddt_type type;
691 	enum ddt_class class;
692 	avl_index_t where;
693 	int error;
694 
695 	ASSERT(MUTEX_HELD(&ddt->ddt_lock));
696 
697 	ddt_key_fill(&dde_search.dde_key, bp);
698 
699 	dde = avl_find(&ddt->ddt_tree, &dde_search, &where);
700 	if (dde == NULL) {
701 		if (!add)
702 			return (NULL);
703 		dde = ddt_alloc(&dde_search.dde_key);
704 		avl_insert(&ddt->ddt_tree, dde, where);
705 	}
706 
707 	while (dde->dde_loading)
708 		cv_wait(&dde->dde_cv, &ddt->ddt_lock);
709 
710 	if (dde->dde_loaded)
711 		return (dde);
712 
713 	dde->dde_loading = B_TRUE;
714 
715 	ddt_exit(ddt);
716 
717 	error = ENOENT;
718 
719 	for (type = 0; type < DDT_TYPES; type++) {
720 		for (class = 0; class < DDT_CLASSES; class++) {
721 			error = ddt_object_lookup(ddt, type, class, dde);
722 			if (error != ENOENT) {
723 				ASSERT0(error);
724 				break;
725 			}
726 		}
727 		if (error != ENOENT)
728 			break;
729 	}
730 
731 	ddt_enter(ddt);
732 
733 	ASSERT(dde->dde_loaded == B_FALSE);
734 	ASSERT(dde->dde_loading == B_TRUE);
735 
736 	dde->dde_type = type;	/* will be DDT_TYPES if no entry found */
737 	dde->dde_class = class;	/* will be DDT_CLASSES if no entry found */
738 	dde->dde_loaded = B_TRUE;
739 	dde->dde_loading = B_FALSE;
740 
741 	if (error == 0)
742 		ddt_stat_update(ddt, dde, -1ULL);
743 
744 	cv_broadcast(&dde->dde_cv);
745 
746 	return (dde);
747 }
748 
749 void
ddt_prefetch(spa_t * spa,const blkptr_t * bp)750 ddt_prefetch(spa_t *spa, const blkptr_t *bp)
751 {
752 	ddt_t *ddt;
753 	ddt_entry_t dde;
754 
755 	if (!zfs_dedup_prefetch || bp == NULL || !BP_GET_DEDUP(bp))
756 		return;
757 
758 	/*
759 	 * We only remove the DDT once all tables are empty and only
760 	 * prefetch dedup blocks when there are entries in the DDT.
761 	 * Thus no locking is required as the DDT can't disappear on us.
762 	 */
763 	ddt = ddt_select(spa, bp);
764 	ddt_key_fill(&dde.dde_key, bp);
765 
766 	for (enum ddt_type type = 0; type < DDT_TYPES; type++) {
767 		for (enum ddt_class class = 0; class < DDT_CLASSES; class++) {
768 			ddt_object_prefetch(ddt, type, class, &dde);
769 		}
770 	}
771 }
772 
773 /*
774  * Opaque struct used for ddt_key comparison
775  */
776 #define	DDT_KEY_CMP_LEN	(sizeof (ddt_key_t) / sizeof (uint16_t))
777 
778 typedef struct ddt_key_cmp {
779 	uint16_t	u16[DDT_KEY_CMP_LEN];
780 } ddt_key_cmp_t;
781 
782 int
ddt_entry_compare(const void * x1,const void * x2)783 ddt_entry_compare(const void *x1, const void *x2)
784 {
785 	const ddt_entry_t *dde1 = x1;
786 	const ddt_entry_t *dde2 = x2;
787 	const ddt_key_cmp_t *k1 = (const ddt_key_cmp_t *)&dde1->dde_key;
788 	const ddt_key_cmp_t *k2 = (const ddt_key_cmp_t *)&dde2->dde_key;
789 	int32_t cmp = 0;
790 
791 	for (int i = 0; i < DDT_KEY_CMP_LEN; i++) {
792 		cmp = (int32_t)k1->u16[i] - (int32_t)k2->u16[i];
793 		if (likely(cmp))
794 			break;
795 	}
796 
797 	return (TREE_ISIGN(cmp));
798 }
799 
800 static ddt_t *
ddt_table_alloc(spa_t * spa,enum zio_checksum c)801 ddt_table_alloc(spa_t *spa, enum zio_checksum c)
802 {
803 	ddt_t *ddt;
804 
805 	ddt = kmem_zalloc(sizeof (*ddt), KM_SLEEP);
806 
807 	mutex_init(&ddt->ddt_lock, NULL, MUTEX_DEFAULT, NULL);
808 	avl_create(&ddt->ddt_tree, ddt_entry_compare,
809 	    sizeof (ddt_entry_t), offsetof(ddt_entry_t, dde_node));
810 	avl_create(&ddt->ddt_repair_tree, ddt_entry_compare,
811 	    sizeof (ddt_entry_t), offsetof(ddt_entry_t, dde_node));
812 	ddt->ddt_checksum = c;
813 	ddt->ddt_spa = spa;
814 	ddt->ddt_os = spa->spa_meta_objset;
815 
816 	return (ddt);
817 }
818 
819 static void
ddt_table_free(ddt_t * ddt)820 ddt_table_free(ddt_t *ddt)
821 {
822 	ASSERT(avl_numnodes(&ddt->ddt_tree) == 0);
823 	ASSERT(avl_numnodes(&ddt->ddt_repair_tree) == 0);
824 	avl_destroy(&ddt->ddt_tree);
825 	avl_destroy(&ddt->ddt_repair_tree);
826 	mutex_destroy(&ddt->ddt_lock);
827 	kmem_free(ddt, sizeof (*ddt));
828 }
829 
830 void
ddt_create(spa_t * spa)831 ddt_create(spa_t *spa)
832 {
833 	spa->spa_dedup_checksum = ZIO_DEDUPCHECKSUM;
834 
835 	for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++)
836 		spa->spa_ddt[c] = ddt_table_alloc(spa, c);
837 }
838 
839 int
ddt_load(spa_t * spa)840 ddt_load(spa_t *spa)
841 {
842 	int error;
843 
844 	ddt_create(spa);
845 
846 	error = zap_lookup(spa->spa_meta_objset, DMU_POOL_DIRECTORY_OBJECT,
847 	    DMU_POOL_DDT_STATS, sizeof (uint64_t), 1,
848 	    &spa->spa_ddt_stat_object);
849 
850 	if (error)
851 		return (error == ENOENT ? 0 : error);
852 
853 	for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
854 		ddt_t *ddt = spa->spa_ddt[c];
855 		for (enum ddt_type type = 0; type < DDT_TYPES; type++) {
856 			for (enum ddt_class class = 0; class < DDT_CLASSES;
857 			    class++) {
858 				error = ddt_object_load(ddt, type, class);
859 				if (error != 0 && error != ENOENT)
860 					return (error);
861 			}
862 		}
863 
864 		/*
865 		 * Seed the cached histograms.
866 		 */
867 		bcopy(ddt->ddt_histogram, &ddt->ddt_histogram_cache,
868 		    sizeof (ddt->ddt_histogram));
869 	}
870 
871 	return (0);
872 }
873 
874 void
ddt_unload(spa_t * spa)875 ddt_unload(spa_t *spa)
876 {
877 	for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
878 		if (spa->spa_ddt[c]) {
879 			ddt_table_free(spa->spa_ddt[c]);
880 			spa->spa_ddt[c] = NULL;
881 		}
882 	}
883 }
884 
885 boolean_t
ddt_class_contains(spa_t * spa,enum ddt_class max_class,const blkptr_t * bp)886 ddt_class_contains(spa_t *spa, enum ddt_class max_class, const blkptr_t *bp)
887 {
888 	ddt_t *ddt;
889 	ddt_entry_t dde;
890 
891 	if (!BP_GET_DEDUP(bp))
892 		return (B_FALSE);
893 
894 	if (max_class == DDT_CLASS_UNIQUE)
895 		return (B_TRUE);
896 
897 	ddt = spa->spa_ddt[BP_GET_CHECKSUM(bp)];
898 
899 	ddt_key_fill(&dde.dde_key, bp);
900 
901 	for (enum ddt_type type = 0; type < DDT_TYPES; type++)
902 		for (enum ddt_class class = 0; class <= max_class; class++)
903 			if (ddt_object_lookup(ddt, type, class, &dde) == 0)
904 				return (B_TRUE);
905 
906 	return (B_FALSE);
907 }
908 
909 ddt_entry_t *
ddt_repair_start(ddt_t * ddt,const blkptr_t * bp)910 ddt_repair_start(ddt_t *ddt, const blkptr_t *bp)
911 {
912 	ddt_key_t ddk;
913 	ddt_entry_t *dde;
914 
915 	ddt_key_fill(&ddk, bp);
916 
917 	dde = ddt_alloc(&ddk);
918 
919 	for (enum ddt_type type = 0; type < DDT_TYPES; type++) {
920 		for (enum ddt_class class = 0; class < DDT_CLASSES; class++) {
921 			/*
922 			 * We can only do repair if there are multiple copies
923 			 * of the block.  For anything in the UNIQUE class,
924 			 * there's definitely only one copy, so don't even try.
925 			 */
926 			if (class != DDT_CLASS_UNIQUE &&
927 			    ddt_object_lookup(ddt, type, class, dde) == 0)
928 				return (dde);
929 		}
930 	}
931 
932 	bzero(dde->dde_phys, sizeof (dde->dde_phys));
933 
934 	return (dde);
935 }
936 
937 void
ddt_repair_done(ddt_t * ddt,ddt_entry_t * dde)938 ddt_repair_done(ddt_t *ddt, ddt_entry_t *dde)
939 {
940 	avl_index_t where;
941 
942 	ddt_enter(ddt);
943 
944 	if (dde->dde_repair_abd != NULL && spa_writeable(ddt->ddt_spa) &&
945 	    avl_find(&ddt->ddt_repair_tree, dde, &where) == NULL)
946 		avl_insert(&ddt->ddt_repair_tree, dde, where);
947 	else
948 		ddt_free(dde);
949 
950 	ddt_exit(ddt);
951 }
952 
953 static void
ddt_repair_entry_done(zio_t * zio)954 ddt_repair_entry_done(zio_t *zio)
955 {
956 	ddt_entry_t *rdde = zio->io_private;
957 
958 	ddt_free(rdde);
959 }
960 
961 static void
ddt_repair_entry(ddt_t * ddt,ddt_entry_t * dde,ddt_entry_t * rdde,zio_t * rio)962 ddt_repair_entry(ddt_t *ddt, ddt_entry_t *dde, ddt_entry_t *rdde, zio_t *rio)
963 {
964 	ddt_phys_t *ddp = dde->dde_phys;
965 	ddt_phys_t *rddp = rdde->dde_phys;
966 	ddt_key_t *ddk = &dde->dde_key;
967 	ddt_key_t *rddk = &rdde->dde_key;
968 	zio_t *zio;
969 	blkptr_t blk;
970 
971 	zio = zio_null(rio, rio->io_spa, NULL,
972 	    ddt_repair_entry_done, rdde, rio->io_flags);
973 
974 	for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++, rddp++) {
975 		if (ddp->ddp_phys_birth == 0 ||
976 		    ddp->ddp_phys_birth != rddp->ddp_phys_birth ||
977 		    bcmp(ddp->ddp_dva, rddp->ddp_dva, sizeof (ddp->ddp_dva)))
978 			continue;
979 		ddt_bp_create(ddt->ddt_checksum, ddk, ddp, &blk);
980 		zio_nowait(zio_rewrite(zio, zio->io_spa, 0, &blk,
981 		    rdde->dde_repair_abd, DDK_GET_PSIZE(rddk), NULL, NULL,
982 		    ZIO_PRIORITY_SYNC_WRITE, ZIO_DDT_CHILD_FLAGS(zio), NULL));
983 	}
984 
985 	zio_nowait(zio);
986 }
987 
988 static void
ddt_repair_table(ddt_t * ddt,zio_t * rio)989 ddt_repair_table(ddt_t *ddt, zio_t *rio)
990 {
991 	spa_t *spa = ddt->ddt_spa;
992 	ddt_entry_t *dde, *rdde_next, *rdde;
993 	avl_tree_t *t = &ddt->ddt_repair_tree;
994 	blkptr_t blk;
995 
996 	if (spa_sync_pass(spa) > 1)
997 		return;
998 
999 	ddt_enter(ddt);
1000 	for (rdde = avl_first(t); rdde != NULL; rdde = rdde_next) {
1001 		rdde_next = AVL_NEXT(t, rdde);
1002 		avl_remove(&ddt->ddt_repair_tree, rdde);
1003 		ddt_exit(ddt);
1004 		ddt_bp_create(ddt->ddt_checksum, &rdde->dde_key, NULL, &blk);
1005 		dde = ddt_repair_start(ddt, &blk);
1006 		ddt_repair_entry(ddt, dde, rdde, rio);
1007 		ddt_repair_done(ddt, dde);
1008 		ddt_enter(ddt);
1009 	}
1010 	ddt_exit(ddt);
1011 }
1012 
1013 static void
ddt_sync_entry(ddt_t * ddt,ddt_entry_t * dde,dmu_tx_t * tx,uint64_t txg)1014 ddt_sync_entry(ddt_t *ddt, ddt_entry_t *dde, dmu_tx_t *tx, uint64_t txg)
1015 {
1016 	dsl_pool_t *dp = ddt->ddt_spa->spa_dsl_pool;
1017 	ddt_phys_t *ddp = dde->dde_phys;
1018 	ddt_key_t *ddk = &dde->dde_key;
1019 	enum ddt_type otype = dde->dde_type;
1020 	enum ddt_type ntype = DDT_TYPE_CURRENT;
1021 	enum ddt_class oclass = dde->dde_class;
1022 	enum ddt_class nclass;
1023 	uint64_t total_refcnt = 0;
1024 
1025 	ASSERT(dde->dde_loaded);
1026 	ASSERT(!dde->dde_loading);
1027 
1028 	for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) {
1029 		ASSERT(dde->dde_lead_zio[p] == NULL);
1030 		ASSERT((int64_t)ddp->ddp_refcnt >= 0);
1031 		if (ddp->ddp_phys_birth == 0) {
1032 			ASSERT(ddp->ddp_refcnt == 0);
1033 			continue;
1034 		}
1035 		if (p == DDT_PHYS_DITTO) {
1036 			if (ddt_ditto_copies_needed(ddt, dde, NULL) == 0)
1037 				ddt_phys_free(ddt, ddk, ddp, txg);
1038 			continue;
1039 		}
1040 		if (ddp->ddp_refcnt == 0)
1041 			ddt_phys_free(ddt, ddk, ddp, txg);
1042 		total_refcnt += ddp->ddp_refcnt;
1043 	}
1044 
1045 	if (dde->dde_phys[DDT_PHYS_DITTO].ddp_phys_birth != 0)
1046 		nclass = DDT_CLASS_DITTO;
1047 	else if (total_refcnt > 1)
1048 		nclass = DDT_CLASS_DUPLICATE;
1049 	else
1050 		nclass = DDT_CLASS_UNIQUE;
1051 
1052 	if (otype != DDT_TYPES &&
1053 	    (otype != ntype || oclass != nclass || total_refcnt == 0)) {
1054 		VERIFY(ddt_object_remove(ddt, otype, oclass, dde, tx) == 0);
1055 		ASSERT(ddt_object_lookup(ddt, otype, oclass, dde) == ENOENT);
1056 	}
1057 
1058 	if (total_refcnt != 0) {
1059 		dde->dde_type = ntype;
1060 		dde->dde_class = nclass;
1061 		ddt_stat_update(ddt, dde, 0);
1062 		if (!ddt_object_exists(ddt, ntype, nclass))
1063 			ddt_object_create(ddt, ntype, nclass, tx);
1064 		VERIFY(ddt_object_update(ddt, ntype, nclass, dde, tx) == 0);
1065 
1066 		/*
1067 		 * If the class changes, the order that we scan this bp
1068 		 * changes.  If it decreases, we could miss it, so
1069 		 * scan it right now.  (This covers both class changing
1070 		 * while we are doing ddt_walk(), and when we are
1071 		 * traversing.)
1072 		 */
1073 		if (nclass < oclass) {
1074 			dsl_scan_ddt_entry(dp->dp_scan,
1075 			    ddt->ddt_checksum, dde, tx);
1076 		}
1077 	}
1078 }
1079 
1080 static void
ddt_sync_table(ddt_t * ddt,dmu_tx_t * tx,uint64_t txg)1081 ddt_sync_table(ddt_t *ddt, dmu_tx_t *tx, uint64_t txg)
1082 {
1083 	spa_t *spa = ddt->ddt_spa;
1084 	ddt_entry_t *dde;
1085 	void *cookie = NULL;
1086 
1087 	if (avl_numnodes(&ddt->ddt_tree) == 0)
1088 		return;
1089 
1090 	ASSERT(spa->spa_uberblock.ub_version >= SPA_VERSION_DEDUP);
1091 
1092 	if (spa->spa_ddt_stat_object == 0) {
1093 		spa->spa_ddt_stat_object = zap_create_link(ddt->ddt_os,
1094 		    DMU_OT_DDT_STATS, DMU_POOL_DIRECTORY_OBJECT,
1095 		    DMU_POOL_DDT_STATS, tx);
1096 	}
1097 
1098 	while ((dde = avl_destroy_nodes(&ddt->ddt_tree, &cookie)) != NULL) {
1099 		ddt_sync_entry(ddt, dde, tx, txg);
1100 		ddt_free(dde);
1101 	}
1102 
1103 	for (enum ddt_type type = 0; type < DDT_TYPES; type++) {
1104 		uint64_t count = 0;
1105 		for (enum ddt_class class = 0; class < DDT_CLASSES; class++) {
1106 			if (ddt_object_exists(ddt, type, class)) {
1107 				ddt_object_sync(ddt, type, class, tx);
1108 				count += ddt_object_count(ddt, type, class);
1109 			}
1110 		}
1111 		for (enum ddt_class class = 0; class < DDT_CLASSES; class++) {
1112 			if (count == 0 && ddt_object_exists(ddt, type, class))
1113 				ddt_object_destroy(ddt, type, class, tx);
1114 		}
1115 	}
1116 
1117 	bcopy(ddt->ddt_histogram, &ddt->ddt_histogram_cache,
1118 	    sizeof (ddt->ddt_histogram));
1119 }
1120 
1121 void
ddt_sync(spa_t * spa,uint64_t txg)1122 ddt_sync(spa_t *spa, uint64_t txg)
1123 {
1124 	dsl_scan_t *scn = spa->spa_dsl_pool->dp_scan;
1125 	dmu_tx_t *tx;
1126 	zio_t *rio;
1127 
1128 	ASSERT(spa_syncing_txg(spa) == txg);
1129 
1130 	tx = dmu_tx_create_assigned(spa->spa_dsl_pool, txg);
1131 
1132 	rio = zio_root(spa, NULL, NULL,
1133 	    ZIO_FLAG_CANFAIL | ZIO_FLAG_SPECULATIVE | ZIO_FLAG_SELF_HEAL);
1134 
1135 	/*
1136 	 * This function may cause an immediate scan of ddt blocks (see
1137 	 * the comment above dsl_scan_ddt() for details). We set the
1138 	 * scan's root zio here so that we can wait for any scan IOs in
1139 	 * addition to the regular ddt IOs.
1140 	 */
1141 	ASSERT3P(scn->scn_zio_root, ==, NULL);
1142 	scn->scn_zio_root = rio;
1143 
1144 	for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
1145 		ddt_t *ddt = spa->spa_ddt[c];
1146 		if (ddt == NULL)
1147 			continue;
1148 		ddt_sync_table(ddt, tx, txg);
1149 		ddt_repair_table(ddt, rio);
1150 	}
1151 
1152 	(void) zio_wait(rio);
1153 	scn->scn_zio_root = NULL;
1154 
1155 	dmu_tx_commit(tx);
1156 }
1157 
1158 int
ddt_walk(spa_t * spa,ddt_bookmark_t * ddb,ddt_entry_t * dde)1159 ddt_walk(spa_t *spa, ddt_bookmark_t *ddb, ddt_entry_t *dde)
1160 {
1161 	do {
1162 		do {
1163 			do {
1164 				ddt_t *ddt = spa->spa_ddt[ddb->ddb_checksum];
1165 				int error = ENOENT;
1166 				if (ddt_object_exists(ddt, ddb->ddb_type,
1167 				    ddb->ddb_class)) {
1168 					error = ddt_object_walk(ddt,
1169 					    ddb->ddb_type, ddb->ddb_class,
1170 					    &ddb->ddb_cursor, dde);
1171 				}
1172 				dde->dde_type = ddb->ddb_type;
1173 				dde->dde_class = ddb->ddb_class;
1174 				if (error == 0)
1175 					return (0);
1176 				if (error != ENOENT)
1177 					return (error);
1178 				ddb->ddb_cursor = 0;
1179 			} while (++ddb->ddb_checksum < ZIO_CHECKSUM_FUNCTIONS);
1180 			ddb->ddb_checksum = 0;
1181 		} while (++ddb->ddb_type < DDT_TYPES);
1182 		ddb->ddb_type = 0;
1183 	} while (++ddb->ddb_class < DDT_CLASSES);
1184 
1185 	return (SET_ERROR(ENOENT));
1186 }
1187