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 */
44int zfs_dedup_prefetch = 1;
45
46static const ddt_ops_t *ddt_ops[DDT_TYPES] = {
47	&ddt_zap_ops,
48};
49
50static const char *ddt_class_name[DDT_CLASSES] = {
51	"ditto",
52	"duplicate",
53	"unique",
54};
55
56static void
57ddt_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
81static void
82ddt_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
103static int
104ddt_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
135static void
136ddt_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
159static int
160ddt_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
170static void
171ddt_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
181int
182ddt_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
191static int
192ddt_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
201int
202ddt_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
211uint64_t
212ddt_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
220int
221ddt_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
231boolean_t
232ddt_object_exists(ddt_t *ddt, enum ddt_type type, enum ddt_class class)
233{
234	return (!!ddt->ddt_object[type][class]);
235}
236
237void
238ddt_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
246void
247ddt_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 */
260void
261ddt_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
283void
284ddt_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
297void
298ddt_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
307void
308ddt_phys_clear(ddt_phys_t *ddp)
309{
310	bzero(ddp, sizeof (*ddp));
311}
312
313void
314ddt_phys_addref(ddt_phys_t *ddp)
315{
316	ddp->ddp_refcnt++;
317}
318
319void
320ddt_phys_decref(ddt_phys_t *ddp)
321{
322	ASSERT((int64_t)ddp->ddp_refcnt > 0);
323	ddp->ddp_refcnt--;
324}
325
326void
327ddt_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
336ddt_phys_t *
337ddt_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
349uint64_t
350ddt_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
360static void
361ddt_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
393void
394ddt_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
406static void
407ddt_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
423void
424ddt_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
430void
431ddt_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
439boolean_t
440ddt_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
452void
453ddt_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
477void
478ddt_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
492void
493ddt_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
503uint64_t
504ddt_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
512uint64_t
513ddt_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
524int
525ddt_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
567int
568ddt_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
583size_t
584ddt_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
608void
609ddt_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
625ddt_t *
626ddt_select_by_checksum(spa_t *spa, enum zio_checksum c)
627{
628	return (spa->spa_ddt[c]);
629}
630
631ddt_t *
632ddt_select(spa_t *spa, const blkptr_t *bp)
633{
634	return (spa->spa_ddt[BP_GET_CHECKSUM(bp)]);
635}
636
637void
638ddt_enter(ddt_t *ddt)
639{
640	mutex_enter(&ddt->ddt_lock);
641}
642
643void
644ddt_exit(ddt_t *ddt)
645{
646	mutex_exit(&ddt->ddt_lock);
647}
648
649static ddt_entry_t *
650ddt_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
662static void
663ddt_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
677void
678ddt_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
686ddt_entry_t *
687ddt_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
749void
750ddt_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
778typedef struct ddt_key_cmp {
779	uint16_t	u16[DDT_KEY_CMP_LEN];
780} ddt_key_cmp_t;
781
782int
783ddt_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 (AVL_ISIGN(cmp));
798}
799
800static ddt_t *
801ddt_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
819static void
820ddt_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
830void
831ddt_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
839int
840ddt_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
874void
875ddt_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
885boolean_t
886ddt_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
909ddt_entry_t *
910ddt_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
937void
938ddt_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
953static void
954ddt_repair_entry_done(zio_t *zio)
955{
956	ddt_entry_t *rdde = zio->io_private;
957
958	ddt_free(rdde);
959}
960
961static void
962ddt_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
988static void
989ddt_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
1013static void
1014ddt_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
1080static void
1081ddt_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
1121void
1122ddt_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
1158int
1159ddt_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