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]
22 * Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
23 * Copyright (c) 2012, 2019 by Delphix. All rights reserved.
24 * Copyright (c) 2014 Spectra Logic Corporation, All rights reserved.
28 #include <sys/refcount.h>
30 #include <sys/zfs_context.h>
31 #include <sys/dsl_pool.h>
32 #include <sys/dsl_dataset.h>
35 * Deadlist concurrency:
37 * Deadlists can only be modified from the syncing thread.
39 * Except for dsl_deadlist_insert(), it can only be modified with the
40 * dp_config_rwlock held with RW_WRITER.
42 * The accessors (dsl_deadlist_space() and dsl_deadlist_space_range()) can
43 * be called concurrently, from open context, with the dl_config_rwlock held
46 * Therefore, we only need to provide locking between dsl_deadlist_insert() and
47 * the accessors, protecting:
48 * dl_phys->dl_used,comp,uncomp
49 * and protecting the dl_tree from being loaded.
50 * The locking is provided by dl_lock. Note that locking on the bpobj_t
51 * provides its own locking, and dl_oldfmt is immutable.
58 * Livelists use the same 'deadlist_t' struct as deadlists and are also used
59 * to track blkptrs over the lifetime of a dataset. Livelists however, belong
60 * to clones and track the blkptrs that are clone-specific (were born after
61 * the clone's creation). The exception is embedded block pointers which are
62 * not included in livelists because they do not need to be freed.
64 * When it comes time to delete the clone, the livelist provides a quick
65 * reference as to what needs to be freed. For this reason, livelists also track
66 * when clone-specific blkptrs are freed before deletion to prevent double
67 * frees. Each blkptr in a livelist is marked as a FREE or an ALLOC and the
68 * deletion algorithm iterates backwards over the livelist, matching
69 * FREE/ALLOC pairs and then freeing those ALLOCs which remain. livelists
70 * are also updated in the case when blkptrs are remapped: the old version
71 * of the blkptr is cancelled out with a FREE and the new version is tracked
74 * To bound the amount of memory required for deletion, livelists over a
75 * certain size are spread over multiple entries. Entries are grouped by
76 * birth txg so we can be sure the ALLOC/FREE pair for a given blkptr will
77 * be in the same entry. This allows us to delete livelists incrementally
78 * over multiple syncs, one entry at a time.
80 * During the lifetime of the clone, livelists can get extremely large.
81 * Their size is managed by periodic condensing (preemptively cancelling out
82 * FREE/ALLOC pairs). Livelists are disabled when a clone is promoted or when
83 * the shared space between the clone and its origin is so small that it
84 * doesn't make sense to use livelists anymore.
88 * The threshold sublist size at which we create a new sub-livelist for the
89 * next txg. However, since blkptrs of the same transaction group must be in
90 * the same sub-list, the actual sublist size may exceed this. When picking the
91 * size we had to balance the fact that larger sublists mean fewer sublists
92 * (decreasing the cost of insertion) against the consideration that sublists
93 * will be loaded into memory and shouldn't take up an inordinate amount of
94 * space. We settled on ~500000 entries, corresponding to roughly 128M.
96 unsigned long zfs_livelist_max_entries
= 500000;
99 * We can approximate how much of a performance gain a livelist will give us
100 * based on the percentage of blocks shared between the clone and its origin.
101 * 0 percent shared means that the clone has completely diverged and that the
102 * old method is maximally effective: every read from the block tree will
103 * result in lots of frees. Livelists give us gains when they track blocks
104 * scattered across the tree, when one read in the old method might only
105 * result in a few frees. Once the clone has been overwritten enough,
106 * writes are no longer sparse and we'll no longer get much of a benefit from
107 * tracking them with a livelist. We chose a lower limit of 75 percent shared
108 * (25 percent overwritten). This means that 1/4 of all block pointers will be
109 * freed (e.g. each read frees 256, out of a max of 1024) so we expect livelists
110 * to make deletion 4x faster. Once the amount of shared space drops below this
111 * threshold, the clone will revert to the old deletion method.
113 int zfs_livelist_min_percent_shared
= 75;
116 dsl_deadlist_compare(const void *arg1
, const void *arg2
)
118 const dsl_deadlist_entry_t
*dle1
= arg1
;
119 const dsl_deadlist_entry_t
*dle2
= arg2
;
121 return (AVL_CMP(dle1
->dle_mintxg
, dle2
->dle_mintxg
));
125 dsl_deadlist_cache_compare(const void *arg1
, const void *arg2
)
127 const dsl_deadlist_cache_entry_t
*dlce1
= arg1
;
128 const dsl_deadlist_cache_entry_t
*dlce2
= arg2
;
130 return (AVL_CMP(dlce1
->dlce_mintxg
, dlce2
->dlce_mintxg
));
134 dsl_deadlist_load_tree(dsl_deadlist_t
*dl
)
139 ASSERT(MUTEX_HELD(&dl
->dl_lock
));
141 ASSERT(!dl
->dl_oldfmt
);
142 if (dl
->dl_havecache
) {
144 * After loading the tree, the caller may modify the tree,
145 * e.g. to add or remove nodes, or to make a node no longer
146 * refer to the empty_bpobj. These changes would make the
147 * dl_cache incorrect. Therefore we discard the cache here,
148 * so that it can't become incorrect.
150 dsl_deadlist_cache_entry_t
*dlce
;
152 while ((dlce
= avl_destroy_nodes(&dl
->dl_cache
, &cookie
))
154 kmem_free(dlce
, sizeof (*dlce
));
156 avl_destroy(&dl
->dl_cache
);
157 dl
->dl_havecache
= B_FALSE
;
162 avl_create(&dl
->dl_tree
, dsl_deadlist_compare
,
163 sizeof (dsl_deadlist_entry_t
),
164 offsetof(dsl_deadlist_entry_t
, dle_node
));
165 for (zap_cursor_init(&zc
, dl
->dl_os
, dl
->dl_object
);
166 zap_cursor_retrieve(&zc
, &za
) == 0;
167 zap_cursor_advance(&zc
)) {
168 dsl_deadlist_entry_t
*dle
= kmem_alloc(sizeof (*dle
), KM_SLEEP
);
169 dle
->dle_mintxg
= zfs_strtonum(za
.za_name
, NULL
);
172 * Prefetch all the bpobj's so that we do that i/o
173 * in parallel. Then open them all in a second pass.
175 dle
->dle_bpobj
.bpo_object
= za
.za_first_integer
;
176 dmu_prefetch(dl
->dl_os
, dle
->dle_bpobj
.bpo_object
,
177 0, 0, 0, ZIO_PRIORITY_SYNC_READ
);
179 avl_add(&dl
->dl_tree
, dle
);
181 zap_cursor_fini(&zc
);
183 for (dsl_deadlist_entry_t
*dle
= avl_first(&dl
->dl_tree
);
184 dle
!= NULL
; dle
= AVL_NEXT(&dl
->dl_tree
, dle
)) {
185 VERIFY0(bpobj_open(&dle
->dle_bpobj
, dl
->dl_os
,
186 dle
->dle_bpobj
.bpo_object
));
188 dl
->dl_havetree
= B_TRUE
;
192 * Load only the non-empty bpobj's into the dl_cache. The cache is an analog
193 * of the dl_tree, but contains only non-empty_bpobj nodes from the ZAP. It
194 * is used only for gathering space statistics. The dl_cache has two
195 * advantages over the dl_tree:
197 * 1. Loading the dl_cache is ~5x faster than loading the dl_tree (if it's
198 * mostly empty_bpobj's), due to less CPU overhead to open the empty_bpobj
199 * many times and to inquire about its (zero) space stats many times.
201 * 2. The dl_cache uses less memory than the dl_tree. We only need to load
202 * the dl_tree of snapshots when deleting a snapshot, after which we free the
203 * dl_tree with dsl_deadlist_discard_tree
206 dsl_deadlist_load_cache(dsl_deadlist_t
*dl
)
211 ASSERT(MUTEX_HELD(&dl
->dl_lock
));
213 ASSERT(!dl
->dl_oldfmt
);
214 if (dl
->dl_havecache
)
217 uint64_t empty_bpobj
= dmu_objset_pool(dl
->dl_os
)->dp_empty_bpobj
;
219 avl_create(&dl
->dl_cache
, dsl_deadlist_cache_compare
,
220 sizeof (dsl_deadlist_cache_entry_t
),
221 offsetof(dsl_deadlist_cache_entry_t
, dlce_node
));
222 for (zap_cursor_init(&zc
, dl
->dl_os
, dl
->dl_object
);
223 zap_cursor_retrieve(&zc
, &za
) == 0;
224 zap_cursor_advance(&zc
)) {
225 if (za
.za_first_integer
== empty_bpobj
)
227 dsl_deadlist_cache_entry_t
*dlce
=
228 kmem_zalloc(sizeof (*dlce
), KM_SLEEP
);
229 dlce
->dlce_mintxg
= zfs_strtonum(za
.za_name
, NULL
);
232 * Prefetch all the bpobj's so that we do that i/o
233 * in parallel. Then open them all in a second pass.
235 dlce
->dlce_bpobj
= za
.za_first_integer
;
236 dmu_prefetch(dl
->dl_os
, dlce
->dlce_bpobj
,
237 0, 0, 0, ZIO_PRIORITY_SYNC_READ
);
238 avl_add(&dl
->dl_cache
, dlce
);
240 zap_cursor_fini(&zc
);
242 for (dsl_deadlist_cache_entry_t
*dlce
= avl_first(&dl
->dl_cache
);
243 dlce
!= NULL
; dlce
= AVL_NEXT(&dl
->dl_cache
, dlce
)) {
245 VERIFY0(bpobj_open(&bpo
, dl
->dl_os
, dlce
->dlce_bpobj
));
247 VERIFY0(bpobj_space(&bpo
,
248 &dlce
->dlce_bytes
, &dlce
->dlce_comp
, &dlce
->dlce_uncomp
));
251 dl
->dl_havecache
= B_TRUE
;
255 * Discard the tree to save memory.
258 dsl_deadlist_discard_tree(dsl_deadlist_t
*dl
)
260 mutex_enter(&dl
->dl_lock
);
262 if (!dl
->dl_havetree
) {
263 mutex_exit(&dl
->dl_lock
);
266 dsl_deadlist_entry_t
*dle
;
268 while ((dle
= avl_destroy_nodes(&dl
->dl_tree
, &cookie
)) != NULL
) {
269 bpobj_close(&dle
->dle_bpobj
);
270 kmem_free(dle
, sizeof (*dle
));
272 avl_destroy(&dl
->dl_tree
);
274 dl
->dl_havetree
= B_FALSE
;
275 mutex_exit(&dl
->dl_lock
);
279 dsl_deadlist_iterate(dsl_deadlist_t
*dl
, deadlist_iter_t func
, void *args
)
281 dsl_deadlist_entry_t
*dle
;
283 ASSERT(dsl_deadlist_is_open(dl
));
285 mutex_enter(&dl
->dl_lock
);
286 dsl_deadlist_load_tree(dl
);
287 mutex_exit(&dl
->dl_lock
);
288 for (dle
= avl_first(&dl
->dl_tree
); dle
!= NULL
;
289 dle
= AVL_NEXT(&dl
->dl_tree
, dle
)) {
290 if (func(args
, dle
) != 0)
296 dsl_deadlist_open(dsl_deadlist_t
*dl
, objset_t
*os
, uint64_t object
)
298 dmu_object_info_t doi
;
300 ASSERT(!dsl_deadlist_is_open(dl
));
302 mutex_init(&dl
->dl_lock
, NULL
, MUTEX_DEFAULT
, NULL
);
304 dl
->dl_object
= object
;
305 VERIFY0(dmu_bonus_hold(os
, object
, dl
, &dl
->dl_dbuf
));
306 dmu_object_info_from_db(dl
->dl_dbuf
, &doi
);
307 if (doi
.doi_type
== DMU_OT_BPOBJ
) {
308 dmu_buf_rele(dl
->dl_dbuf
, dl
);
310 dl
->dl_oldfmt
= B_TRUE
;
311 VERIFY0(bpobj_open(&dl
->dl_bpobj
, os
, object
));
315 dl
->dl_oldfmt
= B_FALSE
;
316 dl
->dl_phys
= dl
->dl_dbuf
->db_data
;
317 dl
->dl_havetree
= B_FALSE
;
318 dl
->dl_havecache
= B_FALSE
;
322 dsl_deadlist_is_open(dsl_deadlist_t
*dl
)
324 return (dl
->dl_os
!= NULL
);
328 dsl_deadlist_close(dsl_deadlist_t
*dl
)
330 ASSERT(dsl_deadlist_is_open(dl
));
331 mutex_destroy(&dl
->dl_lock
);
334 dl
->dl_oldfmt
= B_FALSE
;
335 bpobj_close(&dl
->dl_bpobj
);
341 if (dl
->dl_havetree
) {
342 dsl_deadlist_entry_t
*dle
;
344 while ((dle
= avl_destroy_nodes(&dl
->dl_tree
, &cookie
))
346 bpobj_close(&dle
->dle_bpobj
);
347 kmem_free(dle
, sizeof (*dle
));
349 avl_destroy(&dl
->dl_tree
);
351 if (dl
->dl_havecache
) {
352 dsl_deadlist_cache_entry_t
*dlce
;
354 while ((dlce
= avl_destroy_nodes(&dl
->dl_cache
, &cookie
))
356 kmem_free(dlce
, sizeof (*dlce
));
358 avl_destroy(&dl
->dl_cache
);
360 dmu_buf_rele(dl
->dl_dbuf
, dl
);
368 dsl_deadlist_alloc(objset_t
*os
, dmu_tx_t
*tx
)
370 if (spa_version(dmu_objset_spa(os
)) < SPA_VERSION_DEADLISTS
)
371 return (bpobj_alloc(os
, SPA_OLD_MAXBLOCKSIZE
, tx
));
372 return (zap_create(os
, DMU_OT_DEADLIST
, DMU_OT_DEADLIST_HDR
,
373 sizeof (dsl_deadlist_phys_t
), tx
));
377 dsl_deadlist_free(objset_t
*os
, uint64_t dlobj
, dmu_tx_t
*tx
)
379 dmu_object_info_t doi
;
383 VERIFY0(dmu_object_info(os
, dlobj
, &doi
));
384 if (doi
.doi_type
== DMU_OT_BPOBJ
) {
385 bpobj_free(os
, dlobj
, tx
);
389 for (zap_cursor_init(&zc
, os
, dlobj
);
390 zap_cursor_retrieve(&zc
, &za
) == 0;
391 zap_cursor_advance(&zc
)) {
392 uint64_t obj
= za
.za_first_integer
;
393 if (obj
== dmu_objset_pool(os
)->dp_empty_bpobj
)
394 bpobj_decr_empty(os
, tx
);
396 bpobj_free(os
, obj
, tx
);
398 zap_cursor_fini(&zc
);
399 VERIFY0(dmu_object_free(os
, dlobj
, tx
));
403 dle_enqueue(dsl_deadlist_t
*dl
, dsl_deadlist_entry_t
*dle
,
404 const blkptr_t
*bp
, boolean_t bp_freed
, dmu_tx_t
*tx
)
406 ASSERT(MUTEX_HELD(&dl
->dl_lock
));
407 if (dle
->dle_bpobj
.bpo_object
==
408 dmu_objset_pool(dl
->dl_os
)->dp_empty_bpobj
) {
409 uint64_t obj
= bpobj_alloc(dl
->dl_os
, SPA_OLD_MAXBLOCKSIZE
, tx
);
410 bpobj_close(&dle
->dle_bpobj
);
411 bpobj_decr_empty(dl
->dl_os
, tx
);
412 VERIFY0(bpobj_open(&dle
->dle_bpobj
, dl
->dl_os
, obj
));
413 VERIFY0(zap_update_int_key(dl
->dl_os
, dl
->dl_object
,
414 dle
->dle_mintxg
, obj
, tx
));
416 bpobj_enqueue(&dle
->dle_bpobj
, bp
, bp_freed
, tx
);
420 dle_enqueue_subobj(dsl_deadlist_t
*dl
, dsl_deadlist_entry_t
*dle
,
421 uint64_t obj
, dmu_tx_t
*tx
)
423 ASSERT(MUTEX_HELD(&dl
->dl_lock
));
424 if (dle
->dle_bpobj
.bpo_object
!=
425 dmu_objset_pool(dl
->dl_os
)->dp_empty_bpobj
) {
426 bpobj_enqueue_subobj(&dle
->dle_bpobj
, obj
, tx
);
428 bpobj_close(&dle
->dle_bpobj
);
429 bpobj_decr_empty(dl
->dl_os
, tx
);
430 VERIFY0(bpobj_open(&dle
->dle_bpobj
, dl
->dl_os
, obj
));
431 VERIFY0(zap_update_int_key(dl
->dl_os
, dl
->dl_object
,
432 dle
->dle_mintxg
, obj
, tx
));
437 dsl_deadlist_insert(dsl_deadlist_t
*dl
, const blkptr_t
*bp
, boolean_t bp_freed
,
440 dsl_deadlist_entry_t dle_tofind
;
441 dsl_deadlist_entry_t
*dle
;
445 bpobj_enqueue(&dl
->dl_bpobj
, bp
, bp_freed
, tx
);
449 mutex_enter(&dl
->dl_lock
);
450 dsl_deadlist_load_tree(dl
);
452 dmu_buf_will_dirty(dl
->dl_dbuf
, tx
);
454 int sign
= bp_freed
? -1 : +1;
455 dl
->dl_phys
->dl_used
+=
456 sign
* bp_get_dsize_sync(dmu_objset_spa(dl
->dl_os
), bp
);
457 dl
->dl_phys
->dl_comp
+= sign
* BP_GET_PSIZE(bp
);
458 dl
->dl_phys
->dl_uncomp
+= sign
* BP_GET_UCSIZE(bp
);
460 dle_tofind
.dle_mintxg
= bp
->blk_birth
;
461 dle
= avl_find(&dl
->dl_tree
, &dle_tofind
, &where
);
463 dle
= avl_nearest(&dl
->dl_tree
, where
, AVL_BEFORE
);
465 dle
= AVL_PREV(&dl
->dl_tree
, dle
);
468 zfs_panic_recover("blkptr at %p has invalid BLK_BIRTH %llu",
469 bp
, (longlong_t
)bp
->blk_birth
);
470 dle
= avl_first(&dl
->dl_tree
);
473 ASSERT3P(dle
, !=, NULL
);
474 dle_enqueue(dl
, dle
, bp
, bp_freed
, tx
);
475 mutex_exit(&dl
->dl_lock
);
479 dsl_deadlist_insert_alloc_cb(void *arg
, const blkptr_t
*bp
, dmu_tx_t
*tx
)
481 dsl_deadlist_t
*dl
= arg
;
482 dsl_deadlist_insert(dl
, bp
, B_FALSE
, tx
);
487 dsl_deadlist_insert_free_cb(void *arg
, const blkptr_t
*bp
, dmu_tx_t
*tx
)
489 dsl_deadlist_t
*dl
= arg
;
490 dsl_deadlist_insert(dl
, bp
, B_TRUE
, tx
);
495 * Insert new key in deadlist, which must be > all current entries.
496 * mintxg is not inclusive.
499 dsl_deadlist_add_key(dsl_deadlist_t
*dl
, uint64_t mintxg
, dmu_tx_t
*tx
)
502 dsl_deadlist_entry_t
*dle
;
507 dle
= kmem_alloc(sizeof (*dle
), KM_SLEEP
);
508 dle
->dle_mintxg
= mintxg
;
510 mutex_enter(&dl
->dl_lock
);
511 dsl_deadlist_load_tree(dl
);
513 obj
= bpobj_alloc_empty(dl
->dl_os
, SPA_OLD_MAXBLOCKSIZE
, tx
);
514 VERIFY0(bpobj_open(&dle
->dle_bpobj
, dl
->dl_os
, obj
));
515 avl_add(&dl
->dl_tree
, dle
);
517 VERIFY0(zap_add_int_key(dl
->dl_os
, dl
->dl_object
,
519 mutex_exit(&dl
->dl_lock
);
523 * Remove this key, merging its entries into the previous key.
526 dsl_deadlist_remove_key(dsl_deadlist_t
*dl
, uint64_t mintxg
, dmu_tx_t
*tx
)
528 dsl_deadlist_entry_t dle_tofind
;
529 dsl_deadlist_entry_t
*dle
, *dle_prev
;
533 mutex_enter(&dl
->dl_lock
);
534 dsl_deadlist_load_tree(dl
);
536 dle_tofind
.dle_mintxg
= mintxg
;
537 dle
= avl_find(&dl
->dl_tree
, &dle_tofind
, NULL
);
538 ASSERT3P(dle
, !=, NULL
);
539 dle_prev
= AVL_PREV(&dl
->dl_tree
, dle
);
541 dle_enqueue_subobj(dl
, dle_prev
, dle
->dle_bpobj
.bpo_object
, tx
);
543 avl_remove(&dl
->dl_tree
, dle
);
544 bpobj_close(&dle
->dle_bpobj
);
545 kmem_free(dle
, sizeof (*dle
));
547 VERIFY0(zap_remove_int(dl
->dl_os
, dl
->dl_object
, mintxg
, tx
));
548 mutex_exit(&dl
->dl_lock
);
552 * Remove a deadlist entry and all of its contents by removing the entry from
553 * the deadlist's avl tree, freeing the entry's bpobj and adjusting the
554 * deadlist's space accounting accordingly.
557 dsl_deadlist_remove_entry(dsl_deadlist_t
*dl
, uint64_t mintxg
, dmu_tx_t
*tx
)
559 uint64_t used
, comp
, uncomp
;
560 dsl_deadlist_entry_t dle_tofind
;
561 dsl_deadlist_entry_t
*dle
;
562 objset_t
*os
= dl
->dl_os
;
567 mutex_enter(&dl
->dl_lock
);
568 dsl_deadlist_load_tree(dl
);
570 dle_tofind
.dle_mintxg
= mintxg
;
571 dle
= avl_find(&dl
->dl_tree
, &dle_tofind
, NULL
);
572 VERIFY3P(dle
, !=, NULL
);
574 avl_remove(&dl
->dl_tree
, dle
);
575 VERIFY0(zap_remove_int(os
, dl
->dl_object
, mintxg
, tx
));
576 VERIFY0(bpobj_space(&dle
->dle_bpobj
, &used
, &comp
, &uncomp
));
577 dmu_buf_will_dirty(dl
->dl_dbuf
, tx
);
578 dl
->dl_phys
->dl_used
-= used
;
579 dl
->dl_phys
->dl_comp
-= comp
;
580 dl
->dl_phys
->dl_uncomp
-= uncomp
;
581 if (dle
->dle_bpobj
.bpo_object
== dmu_objset_pool(os
)->dp_empty_bpobj
) {
582 bpobj_decr_empty(os
, tx
);
584 bpobj_free(os
, dle
->dle_bpobj
.bpo_object
, tx
);
586 bpobj_close(&dle
->dle_bpobj
);
587 kmem_free(dle
, sizeof (*dle
));
588 mutex_exit(&dl
->dl_lock
);
592 * Clear out the contents of a deadlist_entry by freeing its bpobj,
593 * replacing it with an empty bpobj and adjusting the deadlist's
597 dsl_deadlist_clear_entry(dsl_deadlist_entry_t
*dle
, dsl_deadlist_t
*dl
,
600 uint64_t new_obj
, used
, comp
, uncomp
;
601 objset_t
*os
= dl
->dl_os
;
603 mutex_enter(&dl
->dl_lock
);
604 VERIFY0(zap_remove_int(os
, dl
->dl_object
, dle
->dle_mintxg
, tx
));
605 VERIFY0(bpobj_space(&dle
->dle_bpobj
, &used
, &comp
, &uncomp
));
606 dmu_buf_will_dirty(dl
->dl_dbuf
, tx
);
607 dl
->dl_phys
->dl_used
-= used
;
608 dl
->dl_phys
->dl_comp
-= comp
;
609 dl
->dl_phys
->dl_uncomp
-= uncomp
;
610 if (dle
->dle_bpobj
.bpo_object
== dmu_objset_pool(os
)->dp_empty_bpobj
)
611 bpobj_decr_empty(os
, tx
);
613 bpobj_free(os
, dle
->dle_bpobj
.bpo_object
, tx
);
614 bpobj_close(&dle
->dle_bpobj
);
615 new_obj
= bpobj_alloc_empty(os
, SPA_OLD_MAXBLOCKSIZE
, tx
);
616 VERIFY0(bpobj_open(&dle
->dle_bpobj
, os
, new_obj
));
617 VERIFY0(zap_add_int_key(os
, dl
->dl_object
, dle
->dle_mintxg
,
619 ASSERT(bpobj_is_empty(&dle
->dle_bpobj
));
620 mutex_exit(&dl
->dl_lock
);
624 * Return the first entry in deadlist's avl tree
626 dsl_deadlist_entry_t
*
627 dsl_deadlist_first(dsl_deadlist_t
*dl
)
629 dsl_deadlist_entry_t
*dle
;
631 mutex_enter(&dl
->dl_lock
);
632 dsl_deadlist_load_tree(dl
);
633 dle
= avl_first(&dl
->dl_tree
);
634 mutex_exit(&dl
->dl_lock
);
640 * Return the last entry in deadlist's avl tree
642 dsl_deadlist_entry_t
*
643 dsl_deadlist_last(dsl_deadlist_t
*dl
)
645 dsl_deadlist_entry_t
*dle
;
647 mutex_enter(&dl
->dl_lock
);
648 dsl_deadlist_load_tree(dl
);
649 dle
= avl_last(&dl
->dl_tree
);
650 mutex_exit(&dl
->dl_lock
);
656 * Walk ds's snapshots to regenerate generate ZAP & AVL.
659 dsl_deadlist_regenerate(objset_t
*os
, uint64_t dlobj
,
660 uint64_t mrs_obj
, dmu_tx_t
*tx
)
662 dsl_deadlist_t dl
= { 0 };
663 dsl_pool_t
*dp
= dmu_objset_pool(os
);
665 dsl_deadlist_open(&dl
, os
, dlobj
);
667 dsl_deadlist_close(&dl
);
671 while (mrs_obj
!= 0) {
673 VERIFY0(dsl_dataset_hold_obj(dp
, mrs_obj
, FTAG
, &ds
));
674 dsl_deadlist_add_key(&dl
,
675 dsl_dataset_phys(ds
)->ds_prev_snap_txg
, tx
);
676 mrs_obj
= dsl_dataset_phys(ds
)->ds_prev_snap_obj
;
677 dsl_dataset_rele(ds
, FTAG
);
679 dsl_deadlist_close(&dl
);
683 dsl_deadlist_clone(dsl_deadlist_t
*dl
, uint64_t maxtxg
,
684 uint64_t mrs_obj
, dmu_tx_t
*tx
)
686 dsl_deadlist_entry_t
*dle
;
689 newobj
= dsl_deadlist_alloc(dl
->dl_os
, tx
);
692 dsl_deadlist_regenerate(dl
->dl_os
, newobj
, mrs_obj
, tx
);
696 mutex_enter(&dl
->dl_lock
);
697 dsl_deadlist_load_tree(dl
);
699 for (dle
= avl_first(&dl
->dl_tree
); dle
;
700 dle
= AVL_NEXT(&dl
->dl_tree
, dle
)) {
703 if (dle
->dle_mintxg
>= maxtxg
)
706 obj
= bpobj_alloc_empty(dl
->dl_os
, SPA_OLD_MAXBLOCKSIZE
, tx
);
707 VERIFY0(zap_add_int_key(dl
->dl_os
, newobj
,
708 dle
->dle_mintxg
, obj
, tx
));
710 mutex_exit(&dl
->dl_lock
);
715 dsl_deadlist_space(dsl_deadlist_t
*dl
,
716 uint64_t *usedp
, uint64_t *compp
, uint64_t *uncompp
)
718 ASSERT(dsl_deadlist_is_open(dl
));
720 VERIFY0(bpobj_space(&dl
->dl_bpobj
,
721 usedp
, compp
, uncompp
));
725 mutex_enter(&dl
->dl_lock
);
726 *usedp
= dl
->dl_phys
->dl_used
;
727 *compp
= dl
->dl_phys
->dl_comp
;
728 *uncompp
= dl
->dl_phys
->dl_uncomp
;
729 mutex_exit(&dl
->dl_lock
);
733 * return space used in the range (mintxg, maxtxg].
734 * Includes maxtxg, does not include mintxg.
735 * mintxg and maxtxg must both be keys in the deadlist (unless maxtxg is
739 dsl_deadlist_space_range(dsl_deadlist_t
*dl
, uint64_t mintxg
, uint64_t maxtxg
,
740 uint64_t *usedp
, uint64_t *compp
, uint64_t *uncompp
)
742 dsl_deadlist_cache_entry_t
*dlce
;
743 dsl_deadlist_cache_entry_t dlce_tofind
;
747 VERIFY0(bpobj_space_range(&dl
->dl_bpobj
,
748 mintxg
, maxtxg
, usedp
, compp
, uncompp
));
752 *usedp
= *compp
= *uncompp
= 0;
754 mutex_enter(&dl
->dl_lock
);
755 dsl_deadlist_load_cache(dl
);
756 dlce_tofind
.dlce_mintxg
= mintxg
;
757 dlce
= avl_find(&dl
->dl_cache
, &dlce_tofind
, &where
);
760 * If this mintxg doesn't exist, it may be an empty_bpobj which
761 * is omitted from the sparse tree. Start at the next non-empty
765 dlce
= avl_nearest(&dl
->dl_cache
, where
, AVL_AFTER
);
767 for (; dlce
&& dlce
->dlce_mintxg
< maxtxg
;
768 dlce
= AVL_NEXT(&dl
->dl_tree
, dlce
)) {
769 *usedp
+= dlce
->dlce_bytes
;
770 *compp
+= dlce
->dlce_comp
;
771 *uncompp
+= dlce
->dlce_uncomp
;
774 mutex_exit(&dl
->dl_lock
);
778 dsl_deadlist_insert_bpobj(dsl_deadlist_t
*dl
, uint64_t obj
, uint64_t birth
,
781 dsl_deadlist_entry_t dle_tofind
;
782 dsl_deadlist_entry_t
*dle
;
784 uint64_t used
, comp
, uncomp
;
787 ASSERT(MUTEX_HELD(&dl
->dl_lock
));
789 VERIFY0(bpobj_open(&bpo
, dl
->dl_os
, obj
));
790 VERIFY0(bpobj_space(&bpo
, &used
, &comp
, &uncomp
));
793 dsl_deadlist_load_tree(dl
);
795 dmu_buf_will_dirty(dl
->dl_dbuf
, tx
);
796 dl
->dl_phys
->dl_used
+= used
;
797 dl
->dl_phys
->dl_comp
+= comp
;
798 dl
->dl_phys
->dl_uncomp
+= uncomp
;
800 dle_tofind
.dle_mintxg
= birth
;
801 dle
= avl_find(&dl
->dl_tree
, &dle_tofind
, &where
);
803 dle
= avl_nearest(&dl
->dl_tree
, where
, AVL_BEFORE
);
804 dle_enqueue_subobj(dl
, dle
, obj
, tx
);
808 dsl_deadlist_insert_cb(void *arg
, const blkptr_t
*bp
, boolean_t bp_freed
,
811 dsl_deadlist_t
*dl
= arg
;
812 dsl_deadlist_insert(dl
, bp
, bp_freed
, tx
);
817 * Merge the deadlist pointed to by 'obj' into dl. obj will be left as
821 dsl_deadlist_merge(dsl_deadlist_t
*dl
, uint64_t obj
, dmu_tx_t
*tx
)
826 dsl_deadlist_phys_t
*dlp
;
827 dmu_object_info_t doi
;
829 VERIFY0(dmu_object_info(dl
->dl_os
, obj
, &doi
));
830 if (doi
.doi_type
== DMU_OT_BPOBJ
) {
832 VERIFY0(bpobj_open(&bpo
, dl
->dl_os
, obj
));
833 VERIFY0(bpobj_iterate(&bpo
, dsl_deadlist_insert_cb
, dl
, tx
));
838 mutex_enter(&dl
->dl_lock
);
839 for (zap_cursor_init(&zc
, dl
->dl_os
, obj
);
840 zap_cursor_retrieve(&zc
, &za
) == 0;
841 zap_cursor_advance(&zc
)) {
842 uint64_t mintxg
= zfs_strtonum(za
.za_name
, NULL
);
843 dsl_deadlist_insert_bpobj(dl
, za
.za_first_integer
, mintxg
, tx
);
844 VERIFY0(zap_remove_int(dl
->dl_os
, obj
, mintxg
, tx
));
846 zap_cursor_fini(&zc
);
848 VERIFY0(dmu_bonus_hold(dl
->dl_os
, obj
, FTAG
, &bonus
));
849 dlp
= bonus
->db_data
;
850 dmu_buf_will_dirty(bonus
, tx
);
851 bzero(dlp
, sizeof (*dlp
));
852 dmu_buf_rele(bonus
, FTAG
);
853 mutex_exit(&dl
->dl_lock
);
857 * Remove entries on dl that are born > mintxg, and put them on the bpobj.
860 dsl_deadlist_move_bpobj(dsl_deadlist_t
*dl
, bpobj_t
*bpo
, uint64_t mintxg
,
863 dsl_deadlist_entry_t dle_tofind
;
864 dsl_deadlist_entry_t
*dle
;
867 ASSERT(!dl
->dl_oldfmt
);
869 mutex_enter(&dl
->dl_lock
);
870 dmu_buf_will_dirty(dl
->dl_dbuf
, tx
);
871 dsl_deadlist_load_tree(dl
);
873 dle_tofind
.dle_mintxg
= mintxg
;
874 dle
= avl_find(&dl
->dl_tree
, &dle_tofind
, &where
);
876 dle
= avl_nearest(&dl
->dl_tree
, where
, AVL_AFTER
);
878 uint64_t used
, comp
, uncomp
;
879 dsl_deadlist_entry_t
*dle_next
;
881 bpobj_enqueue_subobj(bpo
, dle
->dle_bpobj
.bpo_object
, tx
);
883 VERIFY0(bpobj_space(&dle
->dle_bpobj
,
884 &used
, &comp
, &uncomp
));
885 ASSERT3U(dl
->dl_phys
->dl_used
, >=, used
);
886 ASSERT3U(dl
->dl_phys
->dl_comp
, >=, comp
);
887 ASSERT3U(dl
->dl_phys
->dl_uncomp
, >=, uncomp
);
888 dl
->dl_phys
->dl_used
-= used
;
889 dl
->dl_phys
->dl_comp
-= comp
;
890 dl
->dl_phys
->dl_uncomp
-= uncomp
;
892 VERIFY0(zap_remove_int(dl
->dl_os
, dl
->dl_object
,
893 dle
->dle_mintxg
, tx
));
895 dle_next
= AVL_NEXT(&dl
->dl_tree
, dle
);
896 avl_remove(&dl
->dl_tree
, dle
);
897 bpobj_close(&dle
->dle_bpobj
);
898 kmem_free(dle
, sizeof (*dle
));
901 mutex_exit(&dl
->dl_lock
);
904 typedef struct livelist_entry
{
905 const blkptr_t
*le_bp
;
910 livelist_compare(const void *larg
, const void *rarg
)
912 const blkptr_t
*l
= ((livelist_entry_t
*)larg
)->le_bp
;
913 const blkptr_t
*r
= ((livelist_entry_t
*)rarg
)->le_bp
;
915 /* Sort them according to dva[0] */
916 uint64_t l_dva0_vdev
= DVA_GET_VDEV(&l
->blk_dva
[0]);
917 uint64_t r_dva0_vdev
= DVA_GET_VDEV(&r
->blk_dva
[0]);
919 if (l_dva0_vdev
!= r_dva0_vdev
)
920 return (AVL_CMP(l_dva0_vdev
, r_dva0_vdev
));
922 /* if vdevs are equal, sort by offsets. */
923 uint64_t l_dva0_offset
= DVA_GET_OFFSET(&l
->blk_dva
[0]);
924 uint64_t r_dva0_offset
= DVA_GET_OFFSET(&r
->blk_dva
[0]);
925 if (l_dva0_offset
== r_dva0_offset
)
926 ASSERT3U(l
->blk_birth
, ==, r
->blk_birth
);
927 return (AVL_CMP(l_dva0_offset
, r_dva0_offset
));
930 struct livelist_iter_arg
{
937 * Expects an AVL tree which is incrementally filled will FREE blkptrs
938 * and used to match up ALLOC/FREE pairs. ALLOC'd blkptrs without a
939 * corresponding FREE are stored in the supplied bplist.
942 dsl_livelist_iterate(void *arg
, const blkptr_t
*bp
, boolean_t bp_freed
,
945 struct livelist_iter_arg
*lia
= arg
;
946 avl_tree_t
*avl
= lia
->avl
;
947 bplist_t
*to_free
= lia
->to_free
;
951 if ((t
!= NULL
) && (zthr_has_waiters(t
) || zthr_iscancelled(t
)))
952 return (SET_ERROR(EINTR
));
954 livelist_entry_t
*node
= kmem_alloc(sizeof (livelist_entry_t
),
956 blkptr_t
*temp_bp
= kmem_alloc(sizeof (blkptr_t
), KM_SLEEP
);
958 node
->le_bp
= temp_bp
;
961 livelist_entry_t node
;
963 livelist_entry_t
*found
= avl_find(avl
, &node
, NULL
);
965 avl_remove(avl
, found
);
966 kmem_free((blkptr_t
*)found
->le_bp
, sizeof (blkptr_t
));
967 kmem_free(found
, sizeof (livelist_entry_t
));
969 bplist_append(to_free
, bp
);
976 * Accepts a bpobj and a bplist. Will insert into the bplist the blkptrs
977 * which have an ALLOC entry but no matching FREE
980 dsl_process_sub_livelist(bpobj_t
*bpobj
, bplist_t
*to_free
, zthr_t
*t
,
984 avl_create(&avl
, livelist_compare
, sizeof (livelist_entry_t
),
985 offsetof(livelist_entry_t
, le_node
));
987 /* process the sublist */
988 struct livelist_iter_arg arg
= {
993 int err
= bpobj_iterate_nofree(bpobj
, dsl_livelist_iterate
, &arg
, size
);
1000 ZFS_MODULE_PARAM(zfs_livelist
, zfs_livelist_
, max_entries
, ULONG
, ZMOD_RW
,
1001 "Size to start the next sub-livelist in a livelist");
1003 ZFS_MODULE_PARAM(zfs_livelist
, zfs_livelist_
, min_percent_shared
, INT
, ZMOD_RW
,
1004 "Threshold at which livelist is disabled");