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.
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or https://opensource.org/licenses/CDDL-1.0.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
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]
23 * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Copyright (c) 2012, 2016 by Delphix. All rights reserved.
25 * Copyright (c) 2022 by Pawel Jakub Dawidek
28 #include <sys/zfs_context.h>
30 #include <sys/spa_impl.h>
34 #include <sys/dmu_tx.h>
36 #include <sys/dsl_pool.h>
37 #include <sys/zio_checksum.h>
38 #include <sys/zio_compress.h>
39 #include <sys/dsl_scan.h>
42 static kmem_cache_t
*ddt_cache
;
43 static kmem_cache_t
*ddt_entry_cache
;
46 * Enable/disable prefetching of dedup-ed blocks which are going to be freed.
48 int zfs_dedup_prefetch
= 0;
50 static const ddt_ops_t
*const ddt_ops
[DDT_TYPES
] = {
54 static const char *const ddt_class_name
[DDT_CLASSES
] = {
61 ddt_object_create(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
64 spa_t
*spa
= ddt
->ddt_spa
;
65 objset_t
*os
= ddt
->ddt_os
;
66 uint64_t *objectp
= &ddt
->ddt_object
[type
][class];
67 boolean_t prehash
= zio_checksum_table
[ddt
->ddt_checksum
].ci_flags
&
69 char name
[DDT_NAMELEN
];
71 ddt_object_name(ddt
, type
, class, name
);
73 ASSERT3U(*objectp
, ==, 0);
74 VERIFY0(ddt_ops
[type
]->ddt_op_create(os
, objectp
, tx
, prehash
));
75 ASSERT3U(*objectp
, !=, 0);
77 VERIFY0(zap_add(os
, DMU_POOL_DIRECTORY_OBJECT
, name
,
78 sizeof (uint64_t), 1, objectp
, tx
));
80 VERIFY0(zap_add(os
, spa
->spa_ddt_stat_object
, name
,
81 sizeof (uint64_t), sizeof (ddt_histogram_t
) / sizeof (uint64_t),
82 &ddt
->ddt_histogram
[type
][class], tx
));
86 ddt_object_destroy(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
89 spa_t
*spa
= ddt
->ddt_spa
;
90 objset_t
*os
= ddt
->ddt_os
;
91 uint64_t *objectp
= &ddt
->ddt_object
[type
][class];
93 char name
[DDT_NAMELEN
];
95 ddt_object_name(ddt
, type
, class, name
);
97 ASSERT3U(*objectp
, !=, 0);
98 ASSERT(ddt_histogram_empty(&ddt
->ddt_histogram
[type
][class]));
99 VERIFY0(ddt_object_count(ddt
, type
, class, &count
));
101 VERIFY0(zap_remove(os
, DMU_POOL_DIRECTORY_OBJECT
, name
, tx
));
102 VERIFY0(zap_remove(os
, spa
->spa_ddt_stat_object
, name
, tx
));
103 VERIFY0(ddt_ops
[type
]->ddt_op_destroy(os
, *objectp
, tx
));
104 memset(&ddt
->ddt_object_stats
[type
][class], 0, sizeof (ddt_object_t
));
110 ddt_object_load(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class)
112 ddt_object_t
*ddo
= &ddt
->ddt_object_stats
[type
][class];
113 dmu_object_info_t doi
;
115 char name
[DDT_NAMELEN
];
118 ddt_object_name(ddt
, type
, class, name
);
120 error
= zap_lookup(ddt
->ddt_os
, DMU_POOL_DIRECTORY_OBJECT
, name
,
121 sizeof (uint64_t), 1, &ddt
->ddt_object
[type
][class]);
125 error
= zap_lookup(ddt
->ddt_os
, ddt
->ddt_spa
->spa_ddt_stat_object
, name
,
126 sizeof (uint64_t), sizeof (ddt_histogram_t
) / sizeof (uint64_t),
127 &ddt
->ddt_histogram
[type
][class]);
132 * Seed the cached statistics.
134 error
= ddt_object_info(ddt
, type
, class, &doi
);
138 error
= ddt_object_count(ddt
, type
, class, &count
);
142 ddo
->ddo_count
= count
;
143 ddo
->ddo_dspace
= doi
.doi_physical_blocks_512
<< 9;
144 ddo
->ddo_mspace
= doi
.doi_fill_count
* doi
.doi_data_block_size
;
150 ddt_object_sync(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
153 ddt_object_t
*ddo
= &ddt
->ddt_object_stats
[type
][class];
154 dmu_object_info_t doi
;
156 char name
[DDT_NAMELEN
];
158 ddt_object_name(ddt
, type
, class, name
);
160 VERIFY0(zap_update(ddt
->ddt_os
, ddt
->ddt_spa
->spa_ddt_stat_object
, name
,
161 sizeof (uint64_t), sizeof (ddt_histogram_t
) / sizeof (uint64_t),
162 &ddt
->ddt_histogram
[type
][class], tx
));
165 * Cache DDT statistics; this is the only time they'll change.
167 VERIFY0(ddt_object_info(ddt
, type
, class, &doi
));
168 VERIFY0(ddt_object_count(ddt
, type
, class, &count
));
170 ddo
->ddo_count
= count
;
171 ddo
->ddo_dspace
= doi
.doi_physical_blocks_512
<< 9;
172 ddo
->ddo_mspace
= doi
.doi_fill_count
* doi
.doi_data_block_size
;
176 ddt_object_lookup(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
179 if (!ddt_object_exists(ddt
, type
, class))
180 return (SET_ERROR(ENOENT
));
182 return (ddt_ops
[type
]->ddt_op_lookup(ddt
->ddt_os
,
183 ddt
->ddt_object
[type
][class], dde
));
187 ddt_object_prefetch(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
190 if (!ddt_object_exists(ddt
, type
, class))
193 ddt_ops
[type
]->ddt_op_prefetch(ddt
->ddt_os
,
194 ddt
->ddt_object
[type
][class], dde
);
198 ddt_object_update(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
199 ddt_entry_t
*dde
, dmu_tx_t
*tx
)
201 ASSERT(ddt_object_exists(ddt
, type
, class));
203 return (ddt_ops
[type
]->ddt_op_update(ddt
->ddt_os
,
204 ddt
->ddt_object
[type
][class], dde
, tx
));
208 ddt_object_remove(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
209 ddt_entry_t
*dde
, dmu_tx_t
*tx
)
211 ASSERT(ddt_object_exists(ddt
, type
, class));
213 return (ddt_ops
[type
]->ddt_op_remove(ddt
->ddt_os
,
214 ddt
->ddt_object
[type
][class], dde
, tx
));
218 ddt_object_walk(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
219 uint64_t *walk
, ddt_entry_t
*dde
)
221 ASSERT(ddt_object_exists(ddt
, type
, class));
223 return (ddt_ops
[type
]->ddt_op_walk(ddt
->ddt_os
,
224 ddt
->ddt_object
[type
][class], dde
, walk
));
228 ddt_object_count(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
231 ASSERT(ddt_object_exists(ddt
, type
, class));
233 return (ddt_ops
[type
]->ddt_op_count(ddt
->ddt_os
,
234 ddt
->ddt_object
[type
][class], count
));
238 ddt_object_info(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
239 dmu_object_info_t
*doi
)
241 if (!ddt_object_exists(ddt
, type
, class))
242 return (SET_ERROR(ENOENT
));
244 return (dmu_object_info(ddt
->ddt_os
, ddt
->ddt_object
[type
][class],
249 ddt_object_exists(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class)
251 return (!!ddt
->ddt_object
[type
][class]);
255 ddt_object_name(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
258 (void) snprintf(name
, DDT_NAMELEN
, DMU_POOL_DDT
,
259 zio_checksum_table
[ddt
->ddt_checksum
].ci_name
,
260 ddt_ops
[type
]->ddt_op_name
, ddt_class_name
[class]);
264 ddt_bp_fill(const ddt_phys_t
*ddp
, blkptr_t
*bp
, uint64_t txg
)
266 ASSERT3U(txg
, !=, 0);
268 for (int d
= 0; d
< SPA_DVAS_PER_BP
; d
++)
269 bp
->blk_dva
[d
] = ddp
->ddp_dva
[d
];
270 BP_SET_BIRTH(bp
, txg
, ddp
->ddp_phys_birth
);
274 * The bp created via this function may be used for repairs and scrub, but it
275 * will be missing the salt / IV required to do a full decrypting read.
278 ddt_bp_create(enum zio_checksum checksum
,
279 const ddt_key_t
*ddk
, const ddt_phys_t
*ddp
, blkptr_t
*bp
)
284 ddt_bp_fill(ddp
, bp
, ddp
->ddp_phys_birth
);
286 bp
->blk_cksum
= ddk
->ddk_cksum
;
288 BP_SET_LSIZE(bp
, DDK_GET_LSIZE(ddk
));
289 BP_SET_PSIZE(bp
, DDK_GET_PSIZE(ddk
));
290 BP_SET_COMPRESS(bp
, DDK_GET_COMPRESS(ddk
));
291 BP_SET_CRYPT(bp
, DDK_GET_CRYPT(ddk
));
293 BP_SET_CHECKSUM(bp
, checksum
);
294 BP_SET_TYPE(bp
, DMU_OT_DEDUP
);
297 BP_SET_BYTEORDER(bp
, ZFS_HOST_BYTEORDER
);
301 ddt_key_fill(ddt_key_t
*ddk
, const blkptr_t
*bp
)
303 ddk
->ddk_cksum
= bp
->blk_cksum
;
306 ASSERT(BP_IS_ENCRYPTED(bp
) || !BP_USES_CRYPT(bp
));
308 DDK_SET_LSIZE(ddk
, BP_GET_LSIZE(bp
));
309 DDK_SET_PSIZE(ddk
, BP_GET_PSIZE(bp
));
310 DDK_SET_COMPRESS(ddk
, BP_GET_COMPRESS(bp
));
311 DDK_SET_CRYPT(ddk
, BP_USES_CRYPT(bp
));
315 ddt_phys_fill(ddt_phys_t
*ddp
, const blkptr_t
*bp
)
317 ASSERT0(ddp
->ddp_phys_birth
);
319 for (int d
= 0; d
< SPA_DVAS_PER_BP
; d
++)
320 ddp
->ddp_dva
[d
] = bp
->blk_dva
[d
];
321 ddp
->ddp_phys_birth
= BP_PHYSICAL_BIRTH(bp
);
325 ddt_phys_clear(ddt_phys_t
*ddp
)
327 memset(ddp
, 0, sizeof (*ddp
));
331 ddt_phys_addref(ddt_phys_t
*ddp
)
337 ddt_phys_decref(ddt_phys_t
*ddp
)
340 ASSERT3U(ddp
->ddp_refcnt
, >, 0);
346 ddt_phys_free(ddt_t
*ddt
, ddt_key_t
*ddk
, ddt_phys_t
*ddp
, uint64_t txg
)
350 ddt_bp_create(ddt
->ddt_checksum
, ddk
, ddp
, &blk
);
353 * We clear the dedup bit so that zio_free() will actually free the
354 * space, rather than just decrementing the refcount in the DDT.
356 BP_SET_DEDUP(&blk
, 0);
359 zio_free(ddt
->ddt_spa
, txg
, &blk
);
363 ddt_phys_select(const ddt_entry_t
*dde
, const blkptr_t
*bp
)
365 ddt_phys_t
*ddp
= (ddt_phys_t
*)dde
->dde_phys
;
367 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++) {
368 if (DVA_EQUAL(BP_IDENTITY(bp
), &ddp
->ddp_dva
[0]) &&
369 BP_PHYSICAL_BIRTH(bp
) == ddp
->ddp_phys_birth
)
376 ddt_phys_total_refcnt(const ddt_entry_t
*dde
)
380 for (int p
= DDT_PHYS_SINGLE
; p
<= DDT_PHYS_TRIPLE
; p
++)
381 refcnt
+= dde
->dde_phys
[p
].ddp_refcnt
;
387 ddt_stat_generate(ddt_t
*ddt
, ddt_entry_t
*dde
, ddt_stat_t
*dds
)
389 spa_t
*spa
= ddt
->ddt_spa
;
390 ddt_phys_t
*ddp
= dde
->dde_phys
;
391 ddt_key_t
*ddk
= &dde
->dde_key
;
392 uint64_t lsize
= DDK_GET_LSIZE(ddk
);
393 uint64_t psize
= DDK_GET_PSIZE(ddk
);
395 memset(dds
, 0, sizeof (*dds
));
397 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++) {
399 uint64_t refcnt
= ddp
->ddp_refcnt
;
401 if (ddp
->ddp_phys_birth
== 0)
404 for (int d
= 0; d
< DDE_GET_NDVAS(dde
); d
++)
405 dsize
+= dva_get_dsize_sync(spa
, &ddp
->ddp_dva
[d
]);
407 dds
->dds_blocks
+= 1;
408 dds
->dds_lsize
+= lsize
;
409 dds
->dds_psize
+= psize
;
410 dds
->dds_dsize
+= dsize
;
412 dds
->dds_ref_blocks
+= refcnt
;
413 dds
->dds_ref_lsize
+= lsize
* refcnt
;
414 dds
->dds_ref_psize
+= psize
* refcnt
;
415 dds
->dds_ref_dsize
+= dsize
* refcnt
;
420 ddt_stat_add(ddt_stat_t
*dst
, const ddt_stat_t
*src
, uint64_t neg
)
422 const uint64_t *s
= (const uint64_t *)src
;
423 uint64_t *d
= (uint64_t *)dst
;
424 uint64_t *d_end
= (uint64_t *)(dst
+ 1);
426 ASSERT(neg
== 0 || neg
== -1ULL); /* add or subtract */
428 for (int i
= 0; i
< d_end
- d
; i
++)
429 d
[i
] += (s
[i
] ^ neg
) - neg
;
433 ddt_stat_update(ddt_t
*ddt
, ddt_entry_t
*dde
, uint64_t neg
)
436 ddt_histogram_t
*ddh
;
439 ddt_stat_generate(ddt
, dde
, &dds
);
441 bucket
= highbit64(dds
.dds_ref_blocks
) - 1;
442 ASSERT3U(bucket
, >=, 0);
444 ddh
= &ddt
->ddt_histogram
[dde
->dde_type
][dde
->dde_class
];
446 ddt_stat_add(&ddh
->ddh_stat
[bucket
], &dds
, neg
);
450 ddt_histogram_add(ddt_histogram_t
*dst
, const ddt_histogram_t
*src
)
452 for (int h
= 0; h
< 64; h
++)
453 ddt_stat_add(&dst
->ddh_stat
[h
], &src
->ddh_stat
[h
], 0);
457 ddt_histogram_stat(ddt_stat_t
*dds
, const ddt_histogram_t
*ddh
)
459 memset(dds
, 0, sizeof (*dds
));
461 for (int h
= 0; h
< 64; h
++)
462 ddt_stat_add(dds
, &ddh
->ddh_stat
[h
], 0);
466 ddt_histogram_empty(const ddt_histogram_t
*ddh
)
468 const uint64_t *s
= (const uint64_t *)ddh
;
469 const uint64_t *s_end
= (const uint64_t *)(ddh
+ 1);
479 ddt_get_dedup_object_stats(spa_t
*spa
, ddt_object_t
*ddo_total
)
481 /* Sum the statistics we cached in ddt_object_sync(). */
482 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
483 ddt_t
*ddt
= spa
->spa_ddt
[c
];
484 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
485 for (enum ddt_class
class = 0; class < DDT_CLASSES
;
488 &ddt
->ddt_object_stats
[type
][class];
489 ddo_total
->ddo_count
+= ddo
->ddo_count
;
490 ddo_total
->ddo_dspace
+= ddo
->ddo_dspace
;
491 ddo_total
->ddo_mspace
+= ddo
->ddo_mspace
;
496 /* ... and compute the averages. */
497 if (ddo_total
->ddo_count
!= 0) {
498 ddo_total
->ddo_dspace
/= ddo_total
->ddo_count
;
499 ddo_total
->ddo_mspace
/= ddo_total
->ddo_count
;
504 ddt_get_dedup_histogram(spa_t
*spa
, ddt_histogram_t
*ddh
)
506 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
507 ddt_t
*ddt
= spa
->spa_ddt
[c
];
508 for (enum ddt_type type
= 0; type
< DDT_TYPES
&& ddt
; type
++) {
509 for (enum ddt_class
class = 0; class < DDT_CLASSES
;
511 ddt_histogram_add(ddh
,
512 &ddt
->ddt_histogram_cache
[type
][class]);
519 ddt_get_dedup_stats(spa_t
*spa
, ddt_stat_t
*dds_total
)
521 ddt_histogram_t
*ddh_total
;
523 ddh_total
= kmem_zalloc(sizeof (ddt_histogram_t
), KM_SLEEP
);
524 ddt_get_dedup_histogram(spa
, ddh_total
);
525 ddt_histogram_stat(dds_total
, ddh_total
);
526 kmem_free(ddh_total
, sizeof (ddt_histogram_t
));
530 ddt_get_dedup_dspace(spa_t
*spa
)
532 ddt_stat_t dds_total
;
534 if (spa
->spa_dedup_dspace
!= ~0ULL)
535 return (spa
->spa_dedup_dspace
);
537 memset(&dds_total
, 0, sizeof (ddt_stat_t
));
539 /* Calculate and cache the stats */
540 ddt_get_dedup_stats(spa
, &dds_total
);
541 spa
->spa_dedup_dspace
= dds_total
.dds_ref_dsize
- dds_total
.dds_dsize
;
542 return (spa
->spa_dedup_dspace
);
546 ddt_get_pool_dedup_ratio(spa_t
*spa
)
548 ddt_stat_t dds_total
= { 0 };
550 ddt_get_dedup_stats(spa
, &dds_total
);
551 if (dds_total
.dds_dsize
== 0)
554 return (dds_total
.dds_ref_dsize
* 100 / dds_total
.dds_dsize
);
558 ddt_compress(void *src
, uchar_t
*dst
, size_t s_len
, size_t d_len
)
560 uchar_t
*version
= dst
++;
561 int cpfunc
= ZIO_COMPRESS_ZLE
;
562 zio_compress_info_t
*ci
= &zio_compress_table
[cpfunc
];
565 ASSERT3U(d_len
, >=, s_len
+ 1); /* no compression plus version byte */
567 c_len
= ci
->ci_compress(src
, dst
, s_len
, d_len
- 1, ci
->ci_level
);
569 if (c_len
== s_len
) {
570 cpfunc
= ZIO_COMPRESS_OFF
;
571 memcpy(dst
, src
, s_len
);
575 if (ZFS_HOST_BYTEORDER
)
576 *version
|= DDT_COMPRESS_BYTEORDER_MASK
;
582 ddt_decompress(uchar_t
*src
, void *dst
, size_t s_len
, size_t d_len
)
584 uchar_t version
= *src
++;
585 int cpfunc
= version
& DDT_COMPRESS_FUNCTION_MASK
;
586 zio_compress_info_t
*ci
= &zio_compress_table
[cpfunc
];
588 if (ci
->ci_decompress
!= NULL
)
589 (void) ci
->ci_decompress(src
, dst
, s_len
, d_len
, ci
->ci_level
);
591 memcpy(dst
, src
, d_len
);
593 if (((version
& DDT_COMPRESS_BYTEORDER_MASK
) != 0) !=
594 (ZFS_HOST_BYTEORDER
!= 0))
595 byteswap_uint64_array(dst
, d_len
);
599 ddt_select(spa_t
*spa
, const blkptr_t
*bp
)
601 return (spa
->spa_ddt
[BP_GET_CHECKSUM(bp
)]);
605 ddt_enter(ddt_t
*ddt
)
607 mutex_enter(&ddt
->ddt_lock
);
613 mutex_exit(&ddt
->ddt_lock
);
619 ddt_cache
= kmem_cache_create("ddt_cache",
620 sizeof (ddt_t
), 0, NULL
, NULL
, NULL
, NULL
, NULL
, 0);
621 ddt_entry_cache
= kmem_cache_create("ddt_entry_cache",
622 sizeof (ddt_entry_t
), 0, NULL
, NULL
, NULL
, NULL
, NULL
, 0);
628 kmem_cache_destroy(ddt_entry_cache
);
629 kmem_cache_destroy(ddt_cache
);
633 ddt_alloc(const ddt_key_t
*ddk
)
637 dde
= kmem_cache_alloc(ddt_entry_cache
, KM_SLEEP
);
638 memset(dde
, 0, sizeof (ddt_entry_t
));
639 cv_init(&dde
->dde_cv
, NULL
, CV_DEFAULT
, NULL
);
647 ddt_free(ddt_entry_t
*dde
)
649 ASSERT(!dde
->dde_loading
);
651 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++)
652 ASSERT3P(dde
->dde_lead_zio
[p
], ==, NULL
);
654 if (dde
->dde_repair_abd
!= NULL
)
655 abd_free(dde
->dde_repair_abd
);
657 cv_destroy(&dde
->dde_cv
);
658 kmem_cache_free(ddt_entry_cache
, dde
);
662 ddt_remove(ddt_t
*ddt
, ddt_entry_t
*dde
)
664 ASSERT(MUTEX_HELD(&ddt
->ddt_lock
));
666 avl_remove(&ddt
->ddt_tree
, dde
);
671 ddt_lookup(ddt_t
*ddt
, const blkptr_t
*bp
, boolean_t add
)
673 ddt_entry_t
*dde
, dde_search
;
675 enum ddt_class
class;
679 ASSERT(MUTEX_HELD(&ddt
->ddt_lock
));
681 ddt_key_fill(&dde_search
.dde_key
, bp
);
683 dde
= avl_find(&ddt
->ddt_tree
, &dde_search
, &where
);
687 dde
= ddt_alloc(&dde_search
.dde_key
);
688 avl_insert(&ddt
->ddt_tree
, dde
, where
);
691 while (dde
->dde_loading
)
692 cv_wait(&dde
->dde_cv
, &ddt
->ddt_lock
);
697 dde
->dde_loading
= B_TRUE
;
703 for (type
= 0; type
< DDT_TYPES
; type
++) {
704 for (class = 0; class < DDT_CLASSES
; class++) {
705 error
= ddt_object_lookup(ddt
, type
, class, dde
);
706 if (error
!= ENOENT
) {
717 ASSERT(!dde
->dde_loaded
);
718 ASSERT(dde
->dde_loading
);
720 dde
->dde_type
= type
; /* will be DDT_TYPES if no entry found */
721 dde
->dde_class
= class; /* will be DDT_CLASSES if no entry found */
722 dde
->dde_loaded
= B_TRUE
;
723 dde
->dde_loading
= B_FALSE
;
726 ddt_stat_update(ddt
, dde
, -1ULL);
728 cv_broadcast(&dde
->dde_cv
);
734 ddt_prefetch(spa_t
*spa
, const blkptr_t
*bp
)
739 if (!zfs_dedup_prefetch
|| bp
== NULL
|| !BP_GET_DEDUP(bp
))
743 * We only remove the DDT once all tables are empty and only
744 * prefetch dedup blocks when there are entries in the DDT.
745 * Thus no locking is required as the DDT can't disappear on us.
747 ddt
= ddt_select(spa
, bp
);
748 ddt_key_fill(&dde
.dde_key
, bp
);
750 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
751 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
752 ddt_object_prefetch(ddt
, type
, class, &dde
);
758 * Opaque struct used for ddt_key comparison
760 #define DDT_KEY_CMP_LEN (sizeof (ddt_key_t) / sizeof (uint16_t))
762 typedef struct ddt_key_cmp
{
763 uint16_t u16
[DDT_KEY_CMP_LEN
];
767 ddt_entry_compare(const void *x1
, const void *x2
)
769 const ddt_entry_t
*dde1
= x1
;
770 const ddt_entry_t
*dde2
= x2
;
771 const ddt_key_cmp_t
*k1
= (const ddt_key_cmp_t
*)&dde1
->dde_key
;
772 const ddt_key_cmp_t
*k2
= (const ddt_key_cmp_t
*)&dde2
->dde_key
;
775 for (int i
= 0; i
< DDT_KEY_CMP_LEN
; i
++) {
776 cmp
= (int32_t)k1
->u16
[i
] - (int32_t)k2
->u16
[i
];
781 return (TREE_ISIGN(cmp
));
785 ddt_table_alloc(spa_t
*spa
, enum zio_checksum c
)
789 ddt
= kmem_cache_alloc(ddt_cache
, KM_SLEEP
);
790 memset(ddt
, 0, sizeof (ddt_t
));
792 mutex_init(&ddt
->ddt_lock
, NULL
, MUTEX_DEFAULT
, NULL
);
793 avl_create(&ddt
->ddt_tree
, ddt_entry_compare
,
794 sizeof (ddt_entry_t
), offsetof(ddt_entry_t
, dde_node
));
795 avl_create(&ddt
->ddt_repair_tree
, ddt_entry_compare
,
796 sizeof (ddt_entry_t
), offsetof(ddt_entry_t
, dde_node
));
797 ddt
->ddt_checksum
= c
;
799 ddt
->ddt_os
= spa
->spa_meta_objset
;
805 ddt_table_free(ddt_t
*ddt
)
807 ASSERT0(avl_numnodes(&ddt
->ddt_tree
));
808 ASSERT0(avl_numnodes(&ddt
->ddt_repair_tree
));
809 avl_destroy(&ddt
->ddt_tree
);
810 avl_destroy(&ddt
->ddt_repair_tree
);
811 mutex_destroy(&ddt
->ddt_lock
);
812 kmem_cache_free(ddt_cache
, ddt
);
816 ddt_create(spa_t
*spa
)
818 spa
->spa_dedup_checksum
= ZIO_DEDUPCHECKSUM
;
820 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++)
821 spa
->spa_ddt
[c
] = ddt_table_alloc(spa
, c
);
831 error
= zap_lookup(spa
->spa_meta_objset
, DMU_POOL_DIRECTORY_OBJECT
,
832 DMU_POOL_DDT_STATS
, sizeof (uint64_t), 1,
833 &spa
->spa_ddt_stat_object
);
836 return (error
== ENOENT
? 0 : error
);
838 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
839 ddt_t
*ddt
= spa
->spa_ddt
[c
];
840 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
841 for (enum ddt_class
class = 0; class < DDT_CLASSES
;
843 error
= ddt_object_load(ddt
, type
, class);
844 if (error
!= 0 && error
!= ENOENT
)
850 * Seed the cached histograms.
852 memcpy(&ddt
->ddt_histogram_cache
, ddt
->ddt_histogram
,
853 sizeof (ddt
->ddt_histogram
));
854 spa
->spa_dedup_dspace
= ~0ULL;
861 ddt_unload(spa_t
*spa
)
863 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
864 if (spa
->spa_ddt
[c
]) {
865 ddt_table_free(spa
->spa_ddt
[c
]);
866 spa
->spa_ddt
[c
] = NULL
;
872 ddt_class_contains(spa_t
*spa
, enum ddt_class max_class
, const blkptr_t
*bp
)
877 if (!BP_GET_DEDUP(bp
))
880 if (max_class
== DDT_CLASS_UNIQUE
)
883 ddt
= spa
->spa_ddt
[BP_GET_CHECKSUM(bp
)];
884 dde
= kmem_cache_alloc(ddt_entry_cache
, KM_SLEEP
);
886 ddt_key_fill(&(dde
->dde_key
), bp
);
888 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
889 for (enum ddt_class
class = 0; class <= max_class
; class++) {
890 if (ddt_object_lookup(ddt
, type
, class, dde
) == 0) {
891 kmem_cache_free(ddt_entry_cache
, dde
);
897 kmem_cache_free(ddt_entry_cache
, dde
);
902 ddt_repair_start(ddt_t
*ddt
, const blkptr_t
*bp
)
907 ddt_key_fill(&ddk
, bp
);
909 dde
= ddt_alloc(&ddk
);
911 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
912 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
914 * We can only do repair if there are multiple copies
915 * of the block. For anything in the UNIQUE class,
916 * there's definitely only one copy, so don't even try.
918 if (class != DDT_CLASS_UNIQUE
&&
919 ddt_object_lookup(ddt
, type
, class, dde
) == 0)
924 memset(dde
->dde_phys
, 0, sizeof (dde
->dde_phys
));
930 ddt_repair_done(ddt_t
*ddt
, ddt_entry_t
*dde
)
936 if (dde
->dde_repair_abd
!= NULL
&& spa_writeable(ddt
->ddt_spa
) &&
937 avl_find(&ddt
->ddt_repair_tree
, dde
, &where
) == NULL
)
938 avl_insert(&ddt
->ddt_repair_tree
, dde
, where
);
946 ddt_repair_entry_done(zio_t
*zio
)
948 ddt_entry_t
*rdde
= zio
->io_private
;
954 ddt_repair_entry(ddt_t
*ddt
, ddt_entry_t
*dde
, ddt_entry_t
*rdde
, zio_t
*rio
)
956 ddt_phys_t
*ddp
= dde
->dde_phys
;
957 ddt_phys_t
*rddp
= rdde
->dde_phys
;
958 ddt_key_t
*ddk
= &dde
->dde_key
;
959 ddt_key_t
*rddk
= &rdde
->dde_key
;
963 zio
= zio_null(rio
, rio
->io_spa
, NULL
,
964 ddt_repair_entry_done
, rdde
, rio
->io_flags
);
966 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++, rddp
++) {
967 if (ddp
->ddp_phys_birth
== 0 ||
968 ddp
->ddp_phys_birth
!= rddp
->ddp_phys_birth
||
969 memcmp(ddp
->ddp_dva
, rddp
->ddp_dva
, sizeof (ddp
->ddp_dva
)))
971 ddt_bp_create(ddt
->ddt_checksum
, ddk
, ddp
, &blk
);
972 zio_nowait(zio_rewrite(zio
, zio
->io_spa
, 0, &blk
,
973 rdde
->dde_repair_abd
, DDK_GET_PSIZE(rddk
), NULL
, NULL
,
974 ZIO_PRIORITY_SYNC_WRITE
, ZIO_DDT_CHILD_FLAGS(zio
), NULL
));
981 ddt_repair_table(ddt_t
*ddt
, zio_t
*rio
)
983 spa_t
*spa
= ddt
->ddt_spa
;
984 ddt_entry_t
*dde
, *rdde_next
, *rdde
;
985 avl_tree_t
*t
= &ddt
->ddt_repair_tree
;
988 if (spa_sync_pass(spa
) > 1)
992 for (rdde
= avl_first(t
); rdde
!= NULL
; rdde
= rdde_next
) {
993 rdde_next
= AVL_NEXT(t
, rdde
);
994 avl_remove(&ddt
->ddt_repair_tree
, rdde
);
996 ddt_bp_create(ddt
->ddt_checksum
, &rdde
->dde_key
, NULL
, &blk
);
997 dde
= ddt_repair_start(ddt
, &blk
);
998 ddt_repair_entry(ddt
, dde
, rdde
, rio
);
999 ddt_repair_done(ddt
, dde
);
1006 ddt_sync_entry(ddt_t
*ddt
, ddt_entry_t
*dde
, dmu_tx_t
*tx
, uint64_t txg
)
1008 dsl_pool_t
*dp
= ddt
->ddt_spa
->spa_dsl_pool
;
1009 ddt_phys_t
*ddp
= dde
->dde_phys
;
1010 ddt_key_t
*ddk
= &dde
->dde_key
;
1011 enum ddt_type otype
= dde
->dde_type
;
1012 enum ddt_type ntype
= DDT_TYPE_CURRENT
;
1013 enum ddt_class oclass
= dde
->dde_class
;
1014 enum ddt_class nclass
;
1015 uint64_t total_refcnt
= 0;
1017 ASSERT(dde
->dde_loaded
);
1018 ASSERT(!dde
->dde_loading
);
1020 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++) {
1021 ASSERT3P(dde
->dde_lead_zio
[p
], ==, NULL
);
1022 if (ddp
->ddp_phys_birth
== 0) {
1023 ASSERT0(ddp
->ddp_refcnt
);
1026 if (p
== DDT_PHYS_DITTO
) {
1028 * Note, we no longer create DDT-DITTO blocks, but we
1029 * don't want to leak any written by older software.
1031 ddt_phys_free(ddt
, ddk
, ddp
, txg
);
1034 if (ddp
->ddp_refcnt
== 0)
1035 ddt_phys_free(ddt
, ddk
, ddp
, txg
);
1036 total_refcnt
+= ddp
->ddp_refcnt
;
1039 /* We do not create new DDT-DITTO blocks. */
1040 ASSERT0(dde
->dde_phys
[DDT_PHYS_DITTO
].ddp_phys_birth
);
1041 if (total_refcnt
> 1)
1042 nclass
= DDT_CLASS_DUPLICATE
;
1044 nclass
= DDT_CLASS_UNIQUE
;
1046 if (otype
!= DDT_TYPES
&&
1047 (otype
!= ntype
|| oclass
!= nclass
|| total_refcnt
== 0)) {
1048 VERIFY0(ddt_object_remove(ddt
, otype
, oclass
, dde
, tx
));
1050 ddt_object_lookup(ddt
, otype
, oclass
, dde
), ==, ENOENT
);
1053 if (total_refcnt
!= 0) {
1054 dde
->dde_type
= ntype
;
1055 dde
->dde_class
= nclass
;
1056 ddt_stat_update(ddt
, dde
, 0);
1057 if (!ddt_object_exists(ddt
, ntype
, nclass
))
1058 ddt_object_create(ddt
, ntype
, nclass
, tx
);
1059 VERIFY0(ddt_object_update(ddt
, ntype
, nclass
, dde
, tx
));
1062 * If the class changes, the order that we scan this bp
1063 * changes. If it decreases, we could miss it, so
1064 * scan it right now. (This covers both class changing
1065 * while we are doing ddt_walk(), and when we are
1068 if (nclass
< oclass
) {
1069 dsl_scan_ddt_entry(dp
->dp_scan
,
1070 ddt
->ddt_checksum
, dde
, tx
);
1076 ddt_sync_table(ddt_t
*ddt
, dmu_tx_t
*tx
, uint64_t txg
)
1078 spa_t
*spa
= ddt
->ddt_spa
;
1080 void *cookie
= NULL
;
1082 if (avl_numnodes(&ddt
->ddt_tree
) == 0)
1085 ASSERT3U(spa
->spa_uberblock
.ub_version
, >=, SPA_VERSION_DEDUP
);
1087 if (spa
->spa_ddt_stat_object
== 0) {
1088 spa
->spa_ddt_stat_object
= zap_create_link(ddt
->ddt_os
,
1089 DMU_OT_DDT_STATS
, DMU_POOL_DIRECTORY_OBJECT
,
1090 DMU_POOL_DDT_STATS
, tx
);
1093 while ((dde
= avl_destroy_nodes(&ddt
->ddt_tree
, &cookie
)) != NULL
) {
1094 ddt_sync_entry(ddt
, dde
, tx
, txg
);
1098 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
1099 uint64_t add
, count
= 0;
1100 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
1101 if (ddt_object_exists(ddt
, type
, class)) {
1102 ddt_object_sync(ddt
, type
, class, tx
);
1103 VERIFY0(ddt_object_count(ddt
, type
, class,
1108 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
1109 if (count
== 0 && ddt_object_exists(ddt
, type
, class))
1110 ddt_object_destroy(ddt
, type
, class, tx
);
1114 memcpy(&ddt
->ddt_histogram_cache
, ddt
->ddt_histogram
,
1115 sizeof (ddt
->ddt_histogram
));
1116 spa
->spa_dedup_dspace
= ~0ULL;
1120 ddt_sync(spa_t
*spa
, uint64_t txg
)
1122 dsl_scan_t
*scn
= spa
->spa_dsl_pool
->dp_scan
;
1126 ASSERT3U(spa_syncing_txg(spa
), ==, txg
);
1128 tx
= dmu_tx_create_assigned(spa
->spa_dsl_pool
, txg
);
1130 rio
= zio_root(spa
, NULL
, NULL
,
1131 ZIO_FLAG_CANFAIL
| ZIO_FLAG_SPECULATIVE
| ZIO_FLAG_SELF_HEAL
);
1134 * This function may cause an immediate scan of ddt blocks (see
1135 * the comment above dsl_scan_ddt() for details). We set the
1136 * scan's root zio here so that we can wait for any scan IOs in
1137 * addition to the regular ddt IOs.
1139 ASSERT3P(scn
->scn_zio_root
, ==, NULL
);
1140 scn
->scn_zio_root
= rio
;
1142 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
1143 ddt_t
*ddt
= spa
->spa_ddt
[c
];
1146 ddt_sync_table(ddt
, tx
, txg
);
1147 ddt_repair_table(ddt
, rio
);
1150 (void) zio_wait(rio
);
1151 scn
->scn_zio_root
= NULL
;
1157 ddt_walk(spa_t
*spa
, ddt_bookmark_t
*ddb
, ddt_entry_t
*dde
)
1162 ddt_t
*ddt
= spa
->spa_ddt
[ddb
->ddb_checksum
];
1164 if (ddt_object_exists(ddt
, ddb
->ddb_type
,
1166 error
= ddt_object_walk(ddt
,
1167 ddb
->ddb_type
, ddb
->ddb_class
,
1168 &ddb
->ddb_cursor
, dde
);
1170 dde
->dde_type
= ddb
->ddb_type
;
1171 dde
->dde_class
= ddb
->ddb_class
;
1174 if (error
!= ENOENT
)
1176 ddb
->ddb_cursor
= 0;
1177 } while (++ddb
->ddb_checksum
< ZIO_CHECKSUM_FUNCTIONS
);
1178 ddb
->ddb_checksum
= 0;
1179 } while (++ddb
->ddb_type
< DDT_TYPES
);
1181 } while (++ddb
->ddb_class
< DDT_CLASSES
);
1183 return (SET_ERROR(ENOENT
));
1187 * This function is used by Block Cloning (brt.c) to increase reference
1188 * counter for the DDT entry if the block is already in DDT.
1190 * Return false if the block, despite having the D bit set, is not present
1191 * in the DDT. Currently this is not possible but might be in the future.
1192 * See the comment below.
1195 ddt_addref(spa_t
*spa
, const blkptr_t
*bp
)
1201 spa_config_enter(spa
, SCL_ZIO
, FTAG
, RW_READER
);
1202 ddt
= ddt_select(spa
, bp
);
1205 dde
= ddt_lookup(ddt
, bp
, B_TRUE
);
1206 ASSERT3P(dde
, !=, NULL
);
1208 if (dde
->dde_type
< DDT_TYPES
) {
1211 ASSERT3S(dde
->dde_class
, <, DDT_CLASSES
);
1213 ddp
= &dde
->dde_phys
[BP_GET_NDVAS(bp
)];
1216 * This entry already existed (dde_type is real), so it must
1217 * have refcnt >0 at the start of this txg. We are called from
1218 * brt_pending_apply(), before frees are issued, so the refcnt
1219 * can't be lowered yet. Therefore, it must be >0. We assert
1220 * this because if the order of BRT and DDT interactions were
1221 * ever to change and the refcnt was ever zero here, then
1222 * likely further action is required to fill out the DDT entry,
1223 * and this is a place that is likely to be missed in testing.
1225 ASSERT3U(ddp
->ddp_refcnt
, >, 0);
1227 ddt_phys_addref(ddp
);
1231 * At the time of implementating this if the block has the
1232 * DEDUP flag set it must exist in the DEDUP table, but
1233 * there are many advocates that want ability to remove
1234 * entries from DDT with refcnt=1. If this will happen,
1235 * we may have a block with the DEDUP set, but which doesn't
1236 * have a corresponding entry in the DDT. Be ready.
1238 ASSERT3S(dde
->dde_class
, ==, DDT_CLASSES
);
1239 ddt_remove(ddt
, dde
);
1244 spa_config_exit(spa
, SCL_ZIO
, FTAG
);
1249 ZFS_MODULE_PARAM(zfs_dedup
, zfs_dedup_
, prefetch
, INT
, ZMOD_RW
,
1250 "Enable prefetching dedup-ed blks");