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 http://www.opensolaris.org/os/licensing.
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.
27 #include <sys/zfs_context.h>
29 #include <sys/spa_impl.h>
33 #include <sys/dmu_tx.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>
41 static kmem_cache_t
*ddt_cache
;
42 static kmem_cache_t
*ddt_entry_cache
;
45 * Enable/disable prefetching of dedup-ed blocks which are going to be freed.
47 int zfs_dedup_prefetch
= 0;
49 static const ddt_ops_t
*ddt_ops
[DDT_TYPES
] = {
53 static const char *ddt_class_name
[DDT_CLASSES
] = {
60 ddt_object_create(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
63 spa_t
*spa
= ddt
->ddt_spa
;
64 objset_t
*os
= ddt
->ddt_os
;
65 uint64_t *objectp
= &ddt
->ddt_object
[type
][class];
66 boolean_t prehash
= zio_checksum_table
[ddt
->ddt_checksum
].ci_flags
&
68 char name
[DDT_NAMELEN
];
70 ddt_object_name(ddt
, type
, class, name
);
72 ASSERT(*objectp
== 0);
73 VERIFY(ddt_ops
[type
]->ddt_op_create(os
, objectp
, tx
, prehash
) == 0);
74 ASSERT(*objectp
!= 0);
76 VERIFY(zap_add(os
, DMU_POOL_DIRECTORY_OBJECT
, name
,
77 sizeof (uint64_t), 1, objectp
, tx
) == 0);
79 VERIFY(zap_add(os
, spa
->spa_ddt_stat_object
, name
,
80 sizeof (uint64_t), sizeof (ddt_histogram_t
) / sizeof (uint64_t),
81 &ddt
->ddt_histogram
[type
][class], tx
) == 0);
85 ddt_object_destroy(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
88 spa_t
*spa
= ddt
->ddt_spa
;
89 objset_t
*os
= ddt
->ddt_os
;
90 uint64_t *objectp
= &ddt
->ddt_object
[type
][class];
92 char name
[DDT_NAMELEN
];
94 ddt_object_name(ddt
, type
, class, name
);
96 ASSERT(*objectp
!= 0);
97 ASSERT(ddt_histogram_empty(&ddt
->ddt_histogram
[type
][class]));
98 VERIFY(ddt_object_count(ddt
, type
, class, &count
) == 0 && count
== 0);
99 VERIFY(zap_remove(os
, DMU_POOL_DIRECTORY_OBJECT
, name
, tx
) == 0);
100 VERIFY(zap_remove(os
, spa
->spa_ddt_stat_object
, name
, tx
) == 0);
101 VERIFY(ddt_ops
[type
]->ddt_op_destroy(os
, *objectp
, tx
) == 0);
102 bzero(&ddt
->ddt_object_stats
[type
][class], sizeof (ddt_object_t
));
108 ddt_object_load(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class)
110 ddt_object_t
*ddo
= &ddt
->ddt_object_stats
[type
][class];
111 dmu_object_info_t doi
;
113 char name
[DDT_NAMELEN
];
116 ddt_object_name(ddt
, type
, class, name
);
118 error
= zap_lookup(ddt
->ddt_os
, DMU_POOL_DIRECTORY_OBJECT
, name
,
119 sizeof (uint64_t), 1, &ddt
->ddt_object
[type
][class]);
123 error
= zap_lookup(ddt
->ddt_os
, ddt
->ddt_spa
->spa_ddt_stat_object
, name
,
124 sizeof (uint64_t), sizeof (ddt_histogram_t
) / sizeof (uint64_t),
125 &ddt
->ddt_histogram
[type
][class]);
130 * Seed the cached statistics.
132 error
= ddt_object_info(ddt
, type
, class, &doi
);
136 error
= ddt_object_count(ddt
, type
, class, &count
);
140 ddo
->ddo_count
= count
;
141 ddo
->ddo_dspace
= doi
.doi_physical_blocks_512
<< 9;
142 ddo
->ddo_mspace
= doi
.doi_fill_count
* doi
.doi_data_block_size
;
148 ddt_object_sync(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
151 ddt_object_t
*ddo
= &ddt
->ddt_object_stats
[type
][class];
152 dmu_object_info_t doi
;
154 char name
[DDT_NAMELEN
];
156 ddt_object_name(ddt
, type
, class, name
);
158 VERIFY(zap_update(ddt
->ddt_os
, ddt
->ddt_spa
->spa_ddt_stat_object
, name
,
159 sizeof (uint64_t), sizeof (ddt_histogram_t
) / sizeof (uint64_t),
160 &ddt
->ddt_histogram
[type
][class], tx
) == 0);
163 * Cache DDT statistics; this is the only time they'll change.
165 VERIFY(ddt_object_info(ddt
, type
, class, &doi
) == 0);
166 VERIFY(ddt_object_count(ddt
, type
, class, &count
) == 0);
168 ddo
->ddo_count
= count
;
169 ddo
->ddo_dspace
= doi
.doi_physical_blocks_512
<< 9;
170 ddo
->ddo_mspace
= doi
.doi_fill_count
* doi
.doi_data_block_size
;
174 ddt_object_lookup(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
177 if (!ddt_object_exists(ddt
, type
, class))
178 return (SET_ERROR(ENOENT
));
180 return (ddt_ops
[type
]->ddt_op_lookup(ddt
->ddt_os
,
181 ddt
->ddt_object
[type
][class], dde
));
185 ddt_object_prefetch(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
188 if (!ddt_object_exists(ddt
, type
, class))
191 ddt_ops
[type
]->ddt_op_prefetch(ddt
->ddt_os
,
192 ddt
->ddt_object
[type
][class], dde
);
196 ddt_object_update(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
197 ddt_entry_t
*dde
, dmu_tx_t
*tx
)
199 ASSERT(ddt_object_exists(ddt
, type
, class));
201 return (ddt_ops
[type
]->ddt_op_update(ddt
->ddt_os
,
202 ddt
->ddt_object
[type
][class], dde
, tx
));
206 ddt_object_remove(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
207 ddt_entry_t
*dde
, dmu_tx_t
*tx
)
209 ASSERT(ddt_object_exists(ddt
, type
, class));
211 return (ddt_ops
[type
]->ddt_op_remove(ddt
->ddt_os
,
212 ddt
->ddt_object
[type
][class], dde
, tx
));
216 ddt_object_walk(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
217 uint64_t *walk
, ddt_entry_t
*dde
)
219 ASSERT(ddt_object_exists(ddt
, type
, class));
221 return (ddt_ops
[type
]->ddt_op_walk(ddt
->ddt_os
,
222 ddt
->ddt_object
[type
][class], dde
, walk
));
226 ddt_object_count(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
229 ASSERT(ddt_object_exists(ddt
, type
, class));
231 return (ddt_ops
[type
]->ddt_op_count(ddt
->ddt_os
,
232 ddt
->ddt_object
[type
][class], count
));
236 ddt_object_info(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
237 dmu_object_info_t
*doi
)
239 if (!ddt_object_exists(ddt
, type
, class))
240 return (SET_ERROR(ENOENT
));
242 return (dmu_object_info(ddt
->ddt_os
, ddt
->ddt_object
[type
][class],
247 ddt_object_exists(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class)
249 return (!!ddt
->ddt_object
[type
][class]);
253 ddt_object_name(ddt_t
*ddt
, enum ddt_type type
, enum ddt_class
class,
256 (void) sprintf(name
, DMU_POOL_DDT
,
257 zio_checksum_table
[ddt
->ddt_checksum
].ci_name
,
258 ddt_ops
[type
]->ddt_op_name
, ddt_class_name
[class]);
262 ddt_bp_fill(const ddt_phys_t
*ddp
, blkptr_t
*bp
, uint64_t txg
)
266 for (int d
= 0; d
< SPA_DVAS_PER_BP
; d
++)
267 bp
->blk_dva
[d
] = ddp
->ddp_dva
[d
];
268 BP_SET_BIRTH(bp
, txg
, ddp
->ddp_phys_birth
);
272 * The bp created via this function may be used for repairs and scrub, but it
273 * will be missing the salt / IV required to do a full decrypting read.
276 ddt_bp_create(enum zio_checksum checksum
,
277 const ddt_key_t
*ddk
, const ddt_phys_t
*ddp
, blkptr_t
*bp
)
282 ddt_bp_fill(ddp
, bp
, ddp
->ddp_phys_birth
);
284 bp
->blk_cksum
= ddk
->ddk_cksum
;
286 BP_SET_LSIZE(bp
, DDK_GET_LSIZE(ddk
));
287 BP_SET_PSIZE(bp
, DDK_GET_PSIZE(ddk
));
288 BP_SET_COMPRESS(bp
, DDK_GET_COMPRESS(ddk
));
289 BP_SET_CRYPT(bp
, DDK_GET_CRYPT(ddk
));
291 BP_SET_CHECKSUM(bp
, checksum
);
292 BP_SET_TYPE(bp
, DMU_OT_DEDUP
);
295 BP_SET_BYTEORDER(bp
, ZFS_HOST_BYTEORDER
);
299 ddt_key_fill(ddt_key_t
*ddk
, const blkptr_t
*bp
)
301 ddk
->ddk_cksum
= bp
->blk_cksum
;
304 ASSERT(BP_IS_ENCRYPTED(bp
) || !BP_USES_CRYPT(bp
));
306 DDK_SET_LSIZE(ddk
, BP_GET_LSIZE(bp
));
307 DDK_SET_PSIZE(ddk
, BP_GET_PSIZE(bp
));
308 DDK_SET_COMPRESS(ddk
, BP_GET_COMPRESS(bp
));
309 DDK_SET_CRYPT(ddk
, BP_USES_CRYPT(bp
));
313 ddt_phys_fill(ddt_phys_t
*ddp
, const blkptr_t
*bp
)
315 ASSERT(ddp
->ddp_phys_birth
== 0);
317 for (int d
= 0; d
< SPA_DVAS_PER_BP
; d
++)
318 ddp
->ddp_dva
[d
] = bp
->blk_dva
[d
];
319 ddp
->ddp_phys_birth
= BP_PHYSICAL_BIRTH(bp
);
323 ddt_phys_clear(ddt_phys_t
*ddp
)
325 bzero(ddp
, sizeof (*ddp
));
329 ddt_phys_addref(ddt_phys_t
*ddp
)
335 ddt_phys_decref(ddt_phys_t
*ddp
)
338 ASSERT(ddp
->ddp_refcnt
> 0);
344 ddt_phys_free(ddt_t
*ddt
, ddt_key_t
*ddk
, ddt_phys_t
*ddp
, uint64_t txg
)
348 ddt_bp_create(ddt
->ddt_checksum
, ddk
, ddp
, &blk
);
350 zio_free(ddt
->ddt_spa
, txg
, &blk
);
354 ddt_phys_select(const ddt_entry_t
*dde
, const blkptr_t
*bp
)
356 ddt_phys_t
*ddp
= (ddt_phys_t
*)dde
->dde_phys
;
358 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++) {
359 if (DVA_EQUAL(BP_IDENTITY(bp
), &ddp
->ddp_dva
[0]) &&
360 BP_PHYSICAL_BIRTH(bp
) == ddp
->ddp_phys_birth
)
367 ddt_phys_total_refcnt(const ddt_entry_t
*dde
)
371 for (int p
= DDT_PHYS_SINGLE
; p
<= DDT_PHYS_TRIPLE
; p
++)
372 refcnt
+= dde
->dde_phys
[p
].ddp_refcnt
;
378 ddt_stat_generate(ddt_t
*ddt
, ddt_entry_t
*dde
, ddt_stat_t
*dds
)
380 spa_t
*spa
= ddt
->ddt_spa
;
381 ddt_phys_t
*ddp
= dde
->dde_phys
;
382 ddt_key_t
*ddk
= &dde
->dde_key
;
383 uint64_t lsize
= DDK_GET_LSIZE(ddk
);
384 uint64_t psize
= DDK_GET_PSIZE(ddk
);
386 bzero(dds
, sizeof (*dds
));
388 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++) {
390 uint64_t refcnt
= ddp
->ddp_refcnt
;
392 if (ddp
->ddp_phys_birth
== 0)
395 for (int d
= 0; d
< DDE_GET_NDVAS(dde
); d
++)
396 dsize
+= dva_get_dsize_sync(spa
, &ddp
->ddp_dva
[d
]);
398 dds
->dds_blocks
+= 1;
399 dds
->dds_lsize
+= lsize
;
400 dds
->dds_psize
+= psize
;
401 dds
->dds_dsize
+= dsize
;
403 dds
->dds_ref_blocks
+= refcnt
;
404 dds
->dds_ref_lsize
+= lsize
* refcnt
;
405 dds
->dds_ref_psize
+= psize
* refcnt
;
406 dds
->dds_ref_dsize
+= dsize
* refcnt
;
411 ddt_stat_add(ddt_stat_t
*dst
, const ddt_stat_t
*src
, uint64_t neg
)
413 const uint64_t *s
= (const uint64_t *)src
;
414 uint64_t *d
= (uint64_t *)dst
;
415 uint64_t *d_end
= (uint64_t *)(dst
+ 1);
417 ASSERT(neg
== 0 || neg
== -1ULL); /* add or subtract */
420 *d
++ += (*s
++ ^ neg
) - neg
;
424 ddt_stat_update(ddt_t
*ddt
, ddt_entry_t
*dde
, uint64_t neg
)
427 ddt_histogram_t
*ddh
;
430 ddt_stat_generate(ddt
, dde
, &dds
);
432 bucket
= highbit64(dds
.dds_ref_blocks
) - 1;
435 ddh
= &ddt
->ddt_histogram
[dde
->dde_type
][dde
->dde_class
];
437 ddt_stat_add(&ddh
->ddh_stat
[bucket
], &dds
, neg
);
441 ddt_histogram_add(ddt_histogram_t
*dst
, const ddt_histogram_t
*src
)
443 for (int h
= 0; h
< 64; h
++)
444 ddt_stat_add(&dst
->ddh_stat
[h
], &src
->ddh_stat
[h
], 0);
448 ddt_histogram_stat(ddt_stat_t
*dds
, const ddt_histogram_t
*ddh
)
450 bzero(dds
, sizeof (*dds
));
452 for (int h
= 0; h
< 64; h
++)
453 ddt_stat_add(dds
, &ddh
->ddh_stat
[h
], 0);
457 ddt_histogram_empty(const ddt_histogram_t
*ddh
)
459 const uint64_t *s
= (const uint64_t *)ddh
;
460 const uint64_t *s_end
= (const uint64_t *)(ddh
+ 1);
470 ddt_get_dedup_object_stats(spa_t
*spa
, ddt_object_t
*ddo_total
)
472 /* Sum the statistics we cached in ddt_object_sync(). */
473 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
474 ddt_t
*ddt
= spa
->spa_ddt
[c
];
475 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
476 for (enum ddt_class
class = 0; class < DDT_CLASSES
;
479 &ddt
->ddt_object_stats
[type
][class];
480 ddo_total
->ddo_count
+= ddo
->ddo_count
;
481 ddo_total
->ddo_dspace
+= ddo
->ddo_dspace
;
482 ddo_total
->ddo_mspace
+= ddo
->ddo_mspace
;
487 /* ... and compute the averages. */
488 if (ddo_total
->ddo_count
!= 0) {
489 ddo_total
->ddo_dspace
/= ddo_total
->ddo_count
;
490 ddo_total
->ddo_mspace
/= ddo_total
->ddo_count
;
495 ddt_get_dedup_histogram(spa_t
*spa
, ddt_histogram_t
*ddh
)
497 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
498 ddt_t
*ddt
= spa
->spa_ddt
[c
];
499 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
500 for (enum ddt_class
class = 0; class < DDT_CLASSES
;
502 ddt_histogram_add(ddh
,
503 &ddt
->ddt_histogram_cache
[type
][class]);
510 ddt_get_dedup_stats(spa_t
*spa
, ddt_stat_t
*dds_total
)
512 ddt_histogram_t
*ddh_total
;
514 ddh_total
= kmem_zalloc(sizeof (ddt_histogram_t
), KM_SLEEP
);
515 ddt_get_dedup_histogram(spa
, ddh_total
);
516 ddt_histogram_stat(dds_total
, ddh_total
);
517 kmem_free(ddh_total
, sizeof (ddt_histogram_t
));
521 ddt_get_dedup_dspace(spa_t
*spa
)
523 ddt_stat_t dds_total
;
525 if (spa
->spa_dedup_dspace
!= ~0ULL)
526 return (spa
->spa_dedup_dspace
);
528 bzero(&dds_total
, sizeof (ddt_stat_t
));
530 /* Calculate and cache the stats */
531 ddt_get_dedup_stats(spa
, &dds_total
);
532 spa
->spa_dedup_dspace
= dds_total
.dds_ref_dsize
- dds_total
.dds_dsize
;
533 return (spa
->spa_dedup_dspace
);
537 ddt_get_pool_dedup_ratio(spa_t
*spa
)
539 ddt_stat_t dds_total
= { 0 };
541 ddt_get_dedup_stats(spa
, &dds_total
);
542 if (dds_total
.dds_dsize
== 0)
545 return (dds_total
.dds_ref_dsize
* 100 / dds_total
.dds_dsize
);
549 ddt_ditto_copies_needed(ddt_t
*ddt
, ddt_entry_t
*dde
, ddt_phys_t
*ddp_willref
)
551 spa_t
*spa
= ddt
->ddt_spa
;
552 uint64_t total_refcnt
= 0;
553 uint64_t ditto
= spa
->spa_dedup_ditto
;
554 int total_copies
= 0;
555 int desired_copies
= 0;
556 int copies_needed
= 0;
558 for (int p
= DDT_PHYS_SINGLE
; p
<= DDT_PHYS_TRIPLE
; p
++) {
559 ddt_phys_t
*ddp
= &dde
->dde_phys
[p
];
560 zio_t
*zio
= dde
->dde_lead_zio
[p
];
561 uint64_t refcnt
= ddp
->ddp_refcnt
; /* committed refs */
563 refcnt
+= zio
->io_parent_count
; /* pending refs */
564 if (ddp
== ddp_willref
)
565 refcnt
++; /* caller's ref */
567 total_refcnt
+= refcnt
;
572 if (ditto
== 0 || ditto
> UINT32_MAX
)
575 if (total_refcnt
>= 1)
577 if (total_refcnt
>= ditto
)
579 if (total_refcnt
>= ditto
* ditto
)
582 copies_needed
= MAX(desired_copies
, total_copies
) - total_copies
;
584 /* encrypted blocks store their IV in DVA[2] */
585 if (DDK_GET_CRYPT(&dde
->dde_key
))
586 copies_needed
= MIN(copies_needed
, SPA_DVAS_PER_BP
- 1);
588 return (copies_needed
);
592 ddt_ditto_copies_present(ddt_entry_t
*dde
)
594 ddt_phys_t
*ddp
= &dde
->dde_phys
[DDT_PHYS_DITTO
];
595 dva_t
*dva
= ddp
->ddp_dva
;
596 int copies
= 0 - DVA_GET_GANG(dva
);
598 for (int d
= 0; d
< DDE_GET_NDVAS(dde
); d
++, dva
++)
599 if (DVA_IS_VALID(dva
))
602 ASSERT(copies
>= 0 && copies
< SPA_DVAS_PER_BP
);
608 ddt_compress(void *src
, uchar_t
*dst
, size_t s_len
, size_t d_len
)
610 uchar_t
*version
= dst
++;
611 int cpfunc
= ZIO_COMPRESS_ZLE
;
612 zio_compress_info_t
*ci
= &zio_compress_table
[cpfunc
];
615 ASSERT(d_len
>= s_len
+ 1); /* no compression plus version byte */
617 c_len
= ci
->ci_compress(src
, dst
, s_len
, d_len
- 1, ci
->ci_level
);
619 if (c_len
== s_len
) {
620 cpfunc
= ZIO_COMPRESS_OFF
;
621 bcopy(src
, dst
, s_len
);
626 if (ZFS_HOST_BYTEORDER
)
627 *version
|= DDT_COMPRESS_BYTEORDER_MASK
;
633 ddt_decompress(uchar_t
*src
, void *dst
, size_t s_len
, size_t d_len
)
635 uchar_t version
= *src
++;
636 int cpfunc
= version
& DDT_COMPRESS_FUNCTION_MASK
;
637 zio_compress_info_t
*ci
= &zio_compress_table
[cpfunc
];
639 if (ci
->ci_decompress
!= NULL
)
640 (void) ci
->ci_decompress(src
, dst
, s_len
, d_len
, ci
->ci_level
);
642 bcopy(src
, dst
, d_len
);
644 if (((version
& DDT_COMPRESS_BYTEORDER_MASK
) != 0) !=
645 (ZFS_HOST_BYTEORDER
!= 0))
646 byteswap_uint64_array(dst
, d_len
);
650 ddt_select_by_checksum(spa_t
*spa
, enum zio_checksum c
)
652 return (spa
->spa_ddt
[c
]);
656 ddt_select(spa_t
*spa
, const blkptr_t
*bp
)
658 return (spa
->spa_ddt
[BP_GET_CHECKSUM(bp
)]);
662 ddt_enter(ddt_t
*ddt
)
664 mutex_enter(&ddt
->ddt_lock
);
670 mutex_exit(&ddt
->ddt_lock
);
676 ddt_cache
= kmem_cache_create("ddt_cache",
677 sizeof (ddt_t
), 0, NULL
, NULL
, NULL
, NULL
, NULL
, 0);
678 ddt_entry_cache
= kmem_cache_create("ddt_entry_cache",
679 sizeof (ddt_entry_t
), 0, NULL
, NULL
, NULL
, NULL
, NULL
, 0);
685 kmem_cache_destroy(ddt_entry_cache
);
686 kmem_cache_destroy(ddt_cache
);
690 ddt_alloc(const ddt_key_t
*ddk
)
694 dde
= kmem_cache_alloc(ddt_entry_cache
, KM_SLEEP
);
695 bzero(dde
, sizeof (ddt_entry_t
));
696 cv_init(&dde
->dde_cv
, NULL
, CV_DEFAULT
, NULL
);
704 ddt_free(ddt_entry_t
*dde
)
706 ASSERT(!dde
->dde_loading
);
708 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++)
709 ASSERT(dde
->dde_lead_zio
[p
] == NULL
);
711 if (dde
->dde_repair_abd
!= NULL
)
712 abd_free(dde
->dde_repair_abd
);
714 cv_destroy(&dde
->dde_cv
);
715 kmem_cache_free(ddt_entry_cache
, dde
);
719 ddt_remove(ddt_t
*ddt
, ddt_entry_t
*dde
)
721 ASSERT(MUTEX_HELD(&ddt
->ddt_lock
));
723 avl_remove(&ddt
->ddt_tree
, dde
);
728 ddt_lookup(ddt_t
*ddt
, const blkptr_t
*bp
, boolean_t add
)
730 ddt_entry_t
*dde
, dde_search
;
732 enum ddt_class
class;
736 ASSERT(MUTEX_HELD(&ddt
->ddt_lock
));
738 ddt_key_fill(&dde_search
.dde_key
, bp
);
740 dde
= avl_find(&ddt
->ddt_tree
, &dde_search
, &where
);
744 dde
= ddt_alloc(&dde_search
.dde_key
);
745 avl_insert(&ddt
->ddt_tree
, dde
, where
);
748 while (dde
->dde_loading
)
749 cv_wait(&dde
->dde_cv
, &ddt
->ddt_lock
);
754 dde
->dde_loading
= B_TRUE
;
760 for (type
= 0; type
< DDT_TYPES
; type
++) {
761 for (class = 0; class < DDT_CLASSES
; class++) {
762 error
= ddt_object_lookup(ddt
, type
, class, dde
);
763 if (error
!= ENOENT
) {
774 ASSERT(dde
->dde_loaded
== B_FALSE
);
775 ASSERT(dde
->dde_loading
== B_TRUE
);
777 dde
->dde_type
= type
; /* will be DDT_TYPES if no entry found */
778 dde
->dde_class
= class; /* will be DDT_CLASSES if no entry found */
779 dde
->dde_loaded
= B_TRUE
;
780 dde
->dde_loading
= B_FALSE
;
783 ddt_stat_update(ddt
, dde
, -1ULL);
785 cv_broadcast(&dde
->dde_cv
);
791 ddt_prefetch(spa_t
*spa
, const blkptr_t
*bp
)
796 if (!zfs_dedup_prefetch
|| bp
== NULL
|| !BP_GET_DEDUP(bp
))
800 * We only remove the DDT once all tables are empty and only
801 * prefetch dedup blocks when there are entries in the DDT.
802 * Thus no locking is required as the DDT can't disappear on us.
804 ddt
= ddt_select(spa
, bp
);
805 ddt_key_fill(&dde
.dde_key
, bp
);
807 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
808 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
809 ddt_object_prefetch(ddt
, type
, class, &dde
);
815 * Opaque struct used for ddt_key comparison
817 #define DDT_KEY_CMP_LEN (sizeof (ddt_key_t) / sizeof (uint16_t))
819 typedef struct ddt_key_cmp
{
820 uint16_t u16
[DDT_KEY_CMP_LEN
];
824 ddt_entry_compare(const void *x1
, const void *x2
)
826 const ddt_entry_t
*dde1
= x1
;
827 const ddt_entry_t
*dde2
= x2
;
828 const ddt_key_cmp_t
*k1
= (const ddt_key_cmp_t
*)&dde1
->dde_key
;
829 const ddt_key_cmp_t
*k2
= (const ddt_key_cmp_t
*)&dde2
->dde_key
;
832 for (int i
= 0; i
< DDT_KEY_CMP_LEN
; i
++) {
833 cmp
= (int32_t)k1
->u16
[i
] - (int32_t)k2
->u16
[i
];
838 return (AVL_ISIGN(cmp
));
842 ddt_table_alloc(spa_t
*spa
, enum zio_checksum c
)
846 ddt
= kmem_cache_alloc(ddt_cache
, KM_SLEEP
);
847 bzero(ddt
, sizeof (ddt_t
));
849 mutex_init(&ddt
->ddt_lock
, NULL
, MUTEX_DEFAULT
, NULL
);
850 avl_create(&ddt
->ddt_tree
, ddt_entry_compare
,
851 sizeof (ddt_entry_t
), offsetof(ddt_entry_t
, dde_node
));
852 avl_create(&ddt
->ddt_repair_tree
, ddt_entry_compare
,
853 sizeof (ddt_entry_t
), offsetof(ddt_entry_t
, dde_node
));
854 ddt
->ddt_checksum
= c
;
856 ddt
->ddt_os
= spa
->spa_meta_objset
;
862 ddt_table_free(ddt_t
*ddt
)
864 ASSERT(avl_numnodes(&ddt
->ddt_tree
) == 0);
865 ASSERT(avl_numnodes(&ddt
->ddt_repair_tree
) == 0);
866 avl_destroy(&ddt
->ddt_tree
);
867 avl_destroy(&ddt
->ddt_repair_tree
);
868 mutex_destroy(&ddt
->ddt_lock
);
869 kmem_cache_free(ddt_cache
, ddt
);
873 ddt_create(spa_t
*spa
)
875 spa
->spa_dedup_checksum
= ZIO_DEDUPCHECKSUM
;
877 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++)
878 spa
->spa_ddt
[c
] = ddt_table_alloc(spa
, c
);
888 error
= zap_lookup(spa
->spa_meta_objset
, DMU_POOL_DIRECTORY_OBJECT
,
889 DMU_POOL_DDT_STATS
, sizeof (uint64_t), 1,
890 &spa
->spa_ddt_stat_object
);
893 return (error
== ENOENT
? 0 : error
);
895 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
896 ddt_t
*ddt
= spa
->spa_ddt
[c
];
897 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
898 for (enum ddt_class
class = 0; class < DDT_CLASSES
;
900 error
= ddt_object_load(ddt
, type
, class);
901 if (error
!= 0 && error
!= ENOENT
)
907 * Seed the cached histograms.
909 bcopy(ddt
->ddt_histogram
, &ddt
->ddt_histogram_cache
,
910 sizeof (ddt
->ddt_histogram
));
911 spa
->spa_dedup_dspace
= ~0ULL;
918 ddt_unload(spa_t
*spa
)
920 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
921 if (spa
->spa_ddt
[c
]) {
922 ddt_table_free(spa
->spa_ddt
[c
]);
923 spa
->spa_ddt
[c
] = NULL
;
929 ddt_class_contains(spa_t
*spa
, enum ddt_class max_class
, const blkptr_t
*bp
)
934 if (!BP_GET_DEDUP(bp
))
937 if (max_class
== DDT_CLASS_UNIQUE
)
940 ddt
= spa
->spa_ddt
[BP_GET_CHECKSUM(bp
)];
941 dde
= kmem_cache_alloc(ddt_entry_cache
, KM_SLEEP
);
943 ddt_key_fill(&(dde
->dde_key
), bp
);
945 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
946 for (enum ddt_class
class = 0; class <= max_class
; class++) {
947 if (ddt_object_lookup(ddt
, type
, class, dde
) == 0) {
948 kmem_cache_free(ddt_entry_cache
, dde
);
954 kmem_cache_free(ddt_entry_cache
, dde
);
959 ddt_repair_start(ddt_t
*ddt
, const blkptr_t
*bp
)
964 ddt_key_fill(&ddk
, bp
);
966 dde
= ddt_alloc(&ddk
);
968 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
969 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
971 * We can only do repair if there are multiple copies
972 * of the block. For anything in the UNIQUE class,
973 * there's definitely only one copy, so don't even try.
975 if (class != DDT_CLASS_UNIQUE
&&
976 ddt_object_lookup(ddt
, type
, class, dde
) == 0)
981 bzero(dde
->dde_phys
, sizeof (dde
->dde_phys
));
987 ddt_repair_done(ddt_t
*ddt
, ddt_entry_t
*dde
)
993 if (dde
->dde_repair_abd
!= NULL
&& spa_writeable(ddt
->ddt_spa
) &&
994 avl_find(&ddt
->ddt_repair_tree
, dde
, &where
) == NULL
)
995 avl_insert(&ddt
->ddt_repair_tree
, dde
, where
);
1003 ddt_repair_entry_done(zio_t
*zio
)
1005 ddt_entry_t
*rdde
= zio
->io_private
;
1011 ddt_repair_entry(ddt_t
*ddt
, ddt_entry_t
*dde
, ddt_entry_t
*rdde
, zio_t
*rio
)
1013 ddt_phys_t
*ddp
= dde
->dde_phys
;
1014 ddt_phys_t
*rddp
= rdde
->dde_phys
;
1015 ddt_key_t
*ddk
= &dde
->dde_key
;
1016 ddt_key_t
*rddk
= &rdde
->dde_key
;
1020 zio
= zio_null(rio
, rio
->io_spa
, NULL
,
1021 ddt_repair_entry_done
, rdde
, rio
->io_flags
);
1023 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++, rddp
++) {
1024 if (ddp
->ddp_phys_birth
== 0 ||
1025 ddp
->ddp_phys_birth
!= rddp
->ddp_phys_birth
||
1026 bcmp(ddp
->ddp_dva
, rddp
->ddp_dva
, sizeof (ddp
->ddp_dva
)))
1028 ddt_bp_create(ddt
->ddt_checksum
, ddk
, ddp
, &blk
);
1029 zio_nowait(zio_rewrite(zio
, zio
->io_spa
, 0, &blk
,
1030 rdde
->dde_repair_abd
, DDK_GET_PSIZE(rddk
), NULL
, NULL
,
1031 ZIO_PRIORITY_SYNC_WRITE
, ZIO_DDT_CHILD_FLAGS(zio
), NULL
));
1038 ddt_repair_table(ddt_t
*ddt
, zio_t
*rio
)
1040 spa_t
*spa
= ddt
->ddt_spa
;
1041 ddt_entry_t
*dde
, *rdde_next
, *rdde
;
1042 avl_tree_t
*t
= &ddt
->ddt_repair_tree
;
1045 if (spa_sync_pass(spa
) > 1)
1049 for (rdde
= avl_first(t
); rdde
!= NULL
; rdde
= rdde_next
) {
1050 rdde_next
= AVL_NEXT(t
, rdde
);
1051 avl_remove(&ddt
->ddt_repair_tree
, rdde
);
1053 ddt_bp_create(ddt
->ddt_checksum
, &rdde
->dde_key
, NULL
, &blk
);
1054 dde
= ddt_repair_start(ddt
, &blk
);
1055 ddt_repair_entry(ddt
, dde
, rdde
, rio
);
1056 ddt_repair_done(ddt
, dde
);
1063 ddt_sync_entry(ddt_t
*ddt
, ddt_entry_t
*dde
, dmu_tx_t
*tx
, uint64_t txg
)
1065 dsl_pool_t
*dp
= ddt
->ddt_spa
->spa_dsl_pool
;
1066 ddt_phys_t
*ddp
= dde
->dde_phys
;
1067 ddt_key_t
*ddk
= &dde
->dde_key
;
1068 enum ddt_type otype
= dde
->dde_type
;
1069 enum ddt_type ntype
= DDT_TYPE_CURRENT
;
1070 enum ddt_class oclass
= dde
->dde_class
;
1071 enum ddt_class nclass
;
1072 uint64_t total_refcnt
= 0;
1074 ASSERT(dde
->dde_loaded
);
1075 ASSERT(!dde
->dde_loading
);
1077 for (int p
= 0; p
< DDT_PHYS_TYPES
; p
++, ddp
++) {
1078 ASSERT(dde
->dde_lead_zio
[p
] == NULL
);
1079 if (ddp
->ddp_phys_birth
== 0) {
1080 ASSERT(ddp
->ddp_refcnt
== 0);
1083 if (p
== DDT_PHYS_DITTO
) {
1084 if (ddt_ditto_copies_needed(ddt
, dde
, NULL
) == 0)
1085 ddt_phys_free(ddt
, ddk
, ddp
, txg
);
1088 if (ddp
->ddp_refcnt
== 0)
1089 ddt_phys_free(ddt
, ddk
, ddp
, txg
);
1090 total_refcnt
+= ddp
->ddp_refcnt
;
1093 if (dde
->dde_phys
[DDT_PHYS_DITTO
].ddp_phys_birth
!= 0)
1094 nclass
= DDT_CLASS_DITTO
;
1095 else if (total_refcnt
> 1)
1096 nclass
= DDT_CLASS_DUPLICATE
;
1098 nclass
= DDT_CLASS_UNIQUE
;
1100 if (otype
!= DDT_TYPES
&&
1101 (otype
!= ntype
|| oclass
!= nclass
|| total_refcnt
== 0)) {
1102 VERIFY(ddt_object_remove(ddt
, otype
, oclass
, dde
, tx
) == 0);
1103 ASSERT(ddt_object_lookup(ddt
, otype
, oclass
, dde
) == ENOENT
);
1106 if (total_refcnt
!= 0) {
1107 dde
->dde_type
= ntype
;
1108 dde
->dde_class
= nclass
;
1109 ddt_stat_update(ddt
, dde
, 0);
1110 if (!ddt_object_exists(ddt
, ntype
, nclass
))
1111 ddt_object_create(ddt
, ntype
, nclass
, tx
);
1112 VERIFY(ddt_object_update(ddt
, ntype
, nclass
, dde
, tx
) == 0);
1115 * If the class changes, the order that we scan this bp
1116 * changes. If it decreases, we could miss it, so
1117 * scan it right now. (This covers both class changing
1118 * while we are doing ddt_walk(), and when we are
1121 if (nclass
< oclass
) {
1122 dsl_scan_ddt_entry(dp
->dp_scan
,
1123 ddt
->ddt_checksum
, dde
, tx
);
1129 ddt_sync_table(ddt_t
*ddt
, dmu_tx_t
*tx
, uint64_t txg
)
1131 spa_t
*spa
= ddt
->ddt_spa
;
1133 void *cookie
= NULL
;
1135 if (avl_numnodes(&ddt
->ddt_tree
) == 0)
1138 ASSERT(spa
->spa_uberblock
.ub_version
>= SPA_VERSION_DEDUP
);
1140 if (spa
->spa_ddt_stat_object
== 0) {
1141 spa
->spa_ddt_stat_object
= zap_create_link(ddt
->ddt_os
,
1142 DMU_OT_DDT_STATS
, DMU_POOL_DIRECTORY_OBJECT
,
1143 DMU_POOL_DDT_STATS
, tx
);
1146 while ((dde
= avl_destroy_nodes(&ddt
->ddt_tree
, &cookie
)) != NULL
) {
1147 ddt_sync_entry(ddt
, dde
, tx
, txg
);
1151 for (enum ddt_type type
= 0; type
< DDT_TYPES
; type
++) {
1152 uint64_t add
, count
= 0;
1153 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
1154 if (ddt_object_exists(ddt
, type
, class)) {
1155 ddt_object_sync(ddt
, type
, class, tx
);
1156 VERIFY(ddt_object_count(ddt
, type
, class,
1161 for (enum ddt_class
class = 0; class < DDT_CLASSES
; class++) {
1162 if (count
== 0 && ddt_object_exists(ddt
, type
, class))
1163 ddt_object_destroy(ddt
, type
, class, tx
);
1167 bcopy(ddt
->ddt_histogram
, &ddt
->ddt_histogram_cache
,
1168 sizeof (ddt
->ddt_histogram
));
1169 spa
->spa_dedup_dspace
= ~0ULL;
1173 ddt_sync(spa_t
*spa
, uint64_t txg
)
1175 dsl_scan_t
*scn
= spa
->spa_dsl_pool
->dp_scan
;
1179 ASSERT(spa_syncing_txg(spa
) == txg
);
1181 tx
= dmu_tx_create_assigned(spa
->spa_dsl_pool
, txg
);
1183 rio
= zio_root(spa
, NULL
, NULL
,
1184 ZIO_FLAG_CANFAIL
| ZIO_FLAG_SPECULATIVE
| ZIO_FLAG_SELF_HEAL
);
1187 * This function may cause an immediate scan of ddt blocks (see
1188 * the comment above dsl_scan_ddt() for details). We set the
1189 * scan's root zio here so that we can wait for any scan IOs in
1190 * addition to the regular ddt IOs.
1192 ASSERT3P(scn
->scn_zio_root
, ==, NULL
);
1193 scn
->scn_zio_root
= rio
;
1195 for (enum zio_checksum c
= 0; c
< ZIO_CHECKSUM_FUNCTIONS
; c
++) {
1196 ddt_t
*ddt
= spa
->spa_ddt
[c
];
1199 ddt_sync_table(ddt
, tx
, txg
);
1200 ddt_repair_table(ddt
, rio
);
1203 (void) zio_wait(rio
);
1204 scn
->scn_zio_root
= NULL
;
1210 ddt_walk(spa_t
*spa
, ddt_bookmark_t
*ddb
, ddt_entry_t
*dde
)
1215 ddt_t
*ddt
= spa
->spa_ddt
[ddb
->ddb_checksum
];
1217 if (ddt_object_exists(ddt
, ddb
->ddb_type
,
1219 error
= ddt_object_walk(ddt
,
1220 ddb
->ddb_type
, ddb
->ddb_class
,
1221 &ddb
->ddb_cursor
, dde
);
1223 dde
->dde_type
= ddb
->ddb_type
;
1224 dde
->dde_class
= ddb
->ddb_class
;
1227 if (error
!= ENOENT
)
1229 ddb
->ddb_cursor
= 0;
1230 } while (++ddb
->ddb_checksum
< ZIO_CHECKSUM_FUNCTIONS
);
1231 ddb
->ddb_checksum
= 0;
1232 } while (++ddb
->ddb_type
< DDT_TYPES
);
1234 } while (++ddb
->ddb_class
< DDT_CLASSES
);
1236 return (SET_ERROR(ENOENT
));
1239 #if defined(_KERNEL)
1240 module_param(zfs_dedup_prefetch
, int, 0644);
1241 MODULE_PARM_DESC(zfs_dedup_prefetch
, "Enable prefetching dedup-ed blks");