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 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
26 * Copyright (c) 2012, 2016 by Delphix. All rights reserved.
29 #include <sys/zfs_context.h>
32 #include <sys/dmu_tx.h>
33 #include <sys/dnode.h>
34 #include <sys/dsl_pool.h>
36 #include <sys/space_map.h>
37 #include <sys/refcount.h>
38 #include <sys/zfeature.h>
41 * The data for a given space map can be kept on blocks of any size.
42 * Larger blocks entail fewer i/o operations, but they also cause the
43 * DMU to keep more data in-core, and also to waste more i/o bandwidth
44 * when only a few blocks have changed since the last transaction group.
46 int space_map_blksz
= (1 << 12);
49 * Load the space map disk into the specified range tree. Segments of maptype
50 * are added to the range tree, other segment types are removed.
52 * Note: space_map_load() will drop sm_lock across dmu_read() calls.
53 * The caller must be OK with this.
56 space_map_load(space_map_t
*sm
, range_tree_t
*rt
, maptype_t maptype
)
58 uint64_t *entry
, *entry_map
, *entry_map_end
;
59 uint64_t bufsize
, size
, offset
, end
, space
;
62 ASSERT(MUTEX_HELD(sm
->sm_lock
));
64 end
= space_map_length(sm
);
65 space
= space_map_allocated(sm
);
67 VERIFY0(range_tree_space(rt
));
69 if (maptype
== SM_FREE
) {
70 range_tree_add(rt
, sm
->sm_start
, sm
->sm_size
);
71 space
= sm
->sm_size
- space
;
74 bufsize
= MAX(sm
->sm_blksz
, SPA_MINBLOCKSIZE
);
75 entry_map
= vmem_alloc(bufsize
, KM_SLEEP
);
77 mutex_exit(sm
->sm_lock
);
79 dmu_prefetch(sm
->sm_os
, space_map_object(sm
), 0, bufsize
,
80 end
- bufsize
, ZIO_PRIORITY_SYNC_READ
);
82 mutex_enter(sm
->sm_lock
);
84 for (offset
= 0; offset
< end
; offset
+= bufsize
) {
85 size
= MIN(end
- offset
, bufsize
);
86 VERIFY(P2PHASE(size
, sizeof (uint64_t)) == 0);
88 ASSERT3U(sm
->sm_blksz
, !=, 0);
90 dprintf("object=%llu offset=%llx size=%llx\n",
91 space_map_object(sm
), offset
, size
);
93 mutex_exit(sm
->sm_lock
);
94 error
= dmu_read(sm
->sm_os
, space_map_object(sm
), offset
, size
,
95 entry_map
, DMU_READ_PREFETCH
);
96 mutex_enter(sm
->sm_lock
);
100 entry_map_end
= entry_map
+ (size
/ sizeof (uint64_t));
101 for (entry
= entry_map
; entry
< entry_map_end
; entry
++) {
103 uint64_t offset
, size
;
105 if (SM_DEBUG_DECODE(e
)) /* Skip debug entries */
108 offset
= (SM_OFFSET_DECODE(e
) << sm
->sm_shift
) +
110 size
= SM_RUN_DECODE(e
) << sm
->sm_shift
;
112 VERIFY0(P2PHASE(offset
, 1ULL << sm
->sm_shift
));
113 VERIFY0(P2PHASE(size
, 1ULL << sm
->sm_shift
));
114 VERIFY3U(offset
, >=, sm
->sm_start
);
115 VERIFY3U(offset
+ size
, <=, sm
->sm_start
+ sm
->sm_size
);
116 if (SM_TYPE_DECODE(e
) == maptype
) {
117 VERIFY3U(range_tree_space(rt
) + size
, <=,
119 range_tree_add(rt
, offset
, size
);
121 range_tree_remove(rt
, offset
, size
);
127 VERIFY3U(range_tree_space(rt
), ==, space
);
129 range_tree_vacate(rt
, NULL
, NULL
);
131 vmem_free(entry_map
, bufsize
);
136 space_map_histogram_clear(space_map_t
*sm
)
138 if (sm
->sm_dbuf
->db_size
!= sizeof (space_map_phys_t
))
141 bzero(sm
->sm_phys
->smp_histogram
, sizeof (sm
->sm_phys
->smp_histogram
));
145 space_map_histogram_verify(space_map_t
*sm
, range_tree_t
*rt
)
150 * Verify that the in-core range tree does not have any
151 * ranges smaller than our sm_shift size.
153 for (i
= 0; i
< sm
->sm_shift
; i
++) {
154 if (rt
->rt_histogram
[i
] != 0)
161 space_map_histogram_add(space_map_t
*sm
, range_tree_t
*rt
, dmu_tx_t
*tx
)
166 ASSERT(MUTEX_HELD(rt
->rt_lock
));
167 ASSERT(dmu_tx_is_syncing(tx
));
168 VERIFY3U(space_map_object(sm
), !=, 0);
170 if (sm
->sm_dbuf
->db_size
!= sizeof (space_map_phys_t
))
173 dmu_buf_will_dirty(sm
->sm_dbuf
, tx
);
175 ASSERT(space_map_histogram_verify(sm
, rt
));
177 * Transfer the content of the range tree histogram to the space
178 * map histogram. The space map histogram contains 32 buckets ranging
179 * between 2^sm_shift to 2^(32+sm_shift-1). The range tree,
180 * however, can represent ranges from 2^0 to 2^63. Since the space
181 * map only cares about allocatable blocks (minimum of sm_shift) we
182 * can safely ignore all ranges in the range tree smaller than sm_shift.
184 for (i
= sm
->sm_shift
; i
< RANGE_TREE_HISTOGRAM_SIZE
; i
++) {
187 * Since the largest histogram bucket in the space map is
188 * 2^(32+sm_shift-1), we need to normalize the values in
189 * the range tree for any bucket larger than that size. For
190 * example given an sm_shift of 9, ranges larger than 2^40
191 * would get normalized as if they were 1TB ranges. Assume
192 * the range tree had a count of 5 in the 2^44 (16TB) bucket,
193 * the calculation below would normalize this to 5 * 2^4 (16).
195 ASSERT3U(i
, >=, idx
+ sm
->sm_shift
);
196 sm
->sm_phys
->smp_histogram
[idx
] +=
197 rt
->rt_histogram
[i
] << (i
- idx
- sm
->sm_shift
);
200 * Increment the space map's index as long as we haven't
201 * reached the maximum bucket size. Accumulate all ranges
202 * larger than the max bucket size into the last bucket.
204 if (idx
< SPACE_MAP_HISTOGRAM_SIZE
- 1) {
205 ASSERT3U(idx
+ sm
->sm_shift
, ==, i
);
207 ASSERT3U(idx
, <, SPACE_MAP_HISTOGRAM_SIZE
);
213 space_map_entries(space_map_t
*sm
, range_tree_t
*rt
)
215 avl_tree_t
*t
= &rt
->rt_root
;
217 uint64_t size
, entries
;
220 * All space_maps always have a debug entry so account for it here.
225 * Traverse the range tree and calculate the number of space map
226 * entries that would be required to write out the range tree.
228 for (rs
= avl_first(t
); rs
!= NULL
; rs
= AVL_NEXT(t
, rs
)) {
229 size
= (rs
->rs_end
- rs
->rs_start
) >> sm
->sm_shift
;
230 entries
+= howmany(size
, SM_RUN_MAX
);
236 * Note: space_map_write() will drop sm_lock across dmu_write() calls.
239 space_map_write(space_map_t
*sm
, range_tree_t
*rt
, maptype_t maptype
,
242 objset_t
*os
= sm
->sm_os
;
243 spa_t
*spa
= dmu_objset_spa(os
);
244 avl_tree_t
*t
= &rt
->rt_root
;
246 uint64_t size
, total
, rt_space
, nodes
;
247 uint64_t *entry
, *entry_map
, *entry_map_end
;
248 uint64_t expected_entries
, actual_entries
= 1;
250 ASSERT(MUTEX_HELD(rt
->rt_lock
));
251 ASSERT(dsl_pool_sync_context(dmu_objset_pool(os
)));
252 VERIFY3U(space_map_object(sm
), !=, 0);
253 dmu_buf_will_dirty(sm
->sm_dbuf
, tx
);
256 * This field is no longer necessary since the in-core space map
257 * now contains the object number but is maintained for backwards
260 sm
->sm_phys
->smp_object
= sm
->sm_object
;
262 if (range_tree_space(rt
) == 0) {
263 VERIFY3U(sm
->sm_object
, ==, sm
->sm_phys
->smp_object
);
267 if (maptype
== SM_ALLOC
)
268 sm
->sm_phys
->smp_alloc
+= range_tree_space(rt
);
270 sm
->sm_phys
->smp_alloc
-= range_tree_space(rt
);
272 expected_entries
= space_map_entries(sm
, rt
);
274 entry_map
= vmem_alloc(sm
->sm_blksz
, KM_SLEEP
);
275 entry_map_end
= entry_map
+ (sm
->sm_blksz
/ sizeof (uint64_t));
278 *entry
++ = SM_DEBUG_ENCODE(1) |
279 SM_DEBUG_ACTION_ENCODE(maptype
) |
280 SM_DEBUG_SYNCPASS_ENCODE(spa_sync_pass(spa
)) |
281 SM_DEBUG_TXG_ENCODE(dmu_tx_get_txg(tx
));
284 nodes
= avl_numnodes(&rt
->rt_root
);
285 rt_space
= range_tree_space(rt
);
286 for (rs
= avl_first(t
); rs
!= NULL
; rs
= AVL_NEXT(t
, rs
)) {
289 size
= (rs
->rs_end
- rs
->rs_start
) >> sm
->sm_shift
;
290 start
= (rs
->rs_start
- sm
->sm_start
) >> sm
->sm_shift
;
292 total
+= size
<< sm
->sm_shift
;
297 run_len
= MIN(size
, SM_RUN_MAX
);
299 if (entry
== entry_map_end
) {
300 mutex_exit(rt
->rt_lock
);
301 dmu_write(os
, space_map_object(sm
),
302 sm
->sm_phys
->smp_objsize
, sm
->sm_blksz
,
304 mutex_enter(rt
->rt_lock
);
305 sm
->sm_phys
->smp_objsize
+= sm
->sm_blksz
;
309 *entry
++ = SM_OFFSET_ENCODE(start
) |
310 SM_TYPE_ENCODE(maptype
) |
311 SM_RUN_ENCODE(run_len
);
319 if (entry
!= entry_map
) {
320 size
= (entry
- entry_map
) * sizeof (uint64_t);
321 mutex_exit(rt
->rt_lock
);
322 dmu_write(os
, space_map_object(sm
), sm
->sm_phys
->smp_objsize
,
323 size
, entry_map
, tx
);
324 mutex_enter(rt
->rt_lock
);
325 sm
->sm_phys
->smp_objsize
+= size
;
327 ASSERT3U(expected_entries
, ==, actual_entries
);
330 * Ensure that the space_map's accounting wasn't changed
331 * while we were in the middle of writing it out.
333 VERIFY3U(nodes
, ==, avl_numnodes(&rt
->rt_root
));
334 VERIFY3U(range_tree_space(rt
), ==, rt_space
);
335 VERIFY3U(range_tree_space(rt
), ==, total
);
337 vmem_free(entry_map
, sm
->sm_blksz
);
341 space_map_open_impl(space_map_t
*sm
)
346 error
= dmu_bonus_hold(sm
->sm_os
, sm
->sm_object
, sm
, &sm
->sm_dbuf
);
350 dmu_object_size_from_db(sm
->sm_dbuf
, &sm
->sm_blksz
, &blocks
);
351 sm
->sm_phys
= sm
->sm_dbuf
->db_data
;
356 space_map_open(space_map_t
**smp
, objset_t
*os
, uint64_t object
,
357 uint64_t start
, uint64_t size
, uint8_t shift
, kmutex_t
*lp
)
362 ASSERT(*smp
== NULL
);
366 sm
= kmem_alloc(sizeof (space_map_t
), KM_SLEEP
);
368 sm
->sm_start
= start
;
370 sm
->sm_shift
= shift
;
373 sm
->sm_object
= object
;
380 error
= space_map_open_impl(sm
);
392 space_map_close(space_map_t
*sm
)
397 if (sm
->sm_dbuf
!= NULL
)
398 dmu_buf_rele(sm
->sm_dbuf
, sm
);
402 kmem_free(sm
, sizeof (*sm
));
406 space_map_truncate(space_map_t
*sm
, dmu_tx_t
*tx
)
408 objset_t
*os
= sm
->sm_os
;
409 spa_t
*spa
= dmu_objset_spa(os
);
410 dmu_object_info_t doi
;
412 ASSERT(dsl_pool_sync_context(dmu_objset_pool(os
)));
413 ASSERT(dmu_tx_is_syncing(tx
));
414 VERIFY3U(dmu_tx_get_txg(tx
), <=, spa_final_dirty_txg(spa
));
416 dmu_object_info_from_db(sm
->sm_dbuf
, &doi
);
419 * If the space map has the wrong bonus size (because
420 * SPA_FEATURE_SPACEMAP_HISTOGRAM has recently been enabled), or
421 * the wrong block size (because space_map_blksz has changed),
422 * free and re-allocate its object with the updated sizes.
424 * Otherwise, just truncate the current object.
426 if ((spa_feature_is_enabled(spa
, SPA_FEATURE_SPACEMAP_HISTOGRAM
) &&
427 doi
.doi_bonus_size
!= sizeof (space_map_phys_t
)) ||
428 doi
.doi_data_block_size
!= space_map_blksz
) {
429 zfs_dbgmsg("txg %llu, spa %s, sm %p, reallocating "
430 "object[%llu]: old bonus %u, old blocksz %u",
431 dmu_tx_get_txg(tx
), spa_name(spa
), sm
, sm
->sm_object
,
432 doi
.doi_bonus_size
, doi
.doi_data_block_size
);
434 space_map_free(sm
, tx
);
435 dmu_buf_rele(sm
->sm_dbuf
, sm
);
437 sm
->sm_object
= space_map_alloc(sm
->sm_os
, tx
);
438 VERIFY0(space_map_open_impl(sm
));
440 VERIFY0(dmu_free_range(os
, space_map_object(sm
), 0, -1ULL, tx
));
443 * If the spacemap is reallocated, its histogram
444 * will be reset. Do the same in the common case so that
445 * bugs related to the uncommon case do not go unnoticed.
447 bzero(sm
->sm_phys
->smp_histogram
,
448 sizeof (sm
->sm_phys
->smp_histogram
));
451 dmu_buf_will_dirty(sm
->sm_dbuf
, tx
);
452 sm
->sm_phys
->smp_objsize
= 0;
453 sm
->sm_phys
->smp_alloc
= 0;
457 * Update the in-core space_map allocation and length values.
460 space_map_update(space_map_t
*sm
)
465 ASSERT(MUTEX_HELD(sm
->sm_lock
));
467 sm
->sm_alloc
= sm
->sm_phys
->smp_alloc
;
468 sm
->sm_length
= sm
->sm_phys
->smp_objsize
;
472 space_map_alloc(objset_t
*os
, dmu_tx_t
*tx
)
474 spa_t
*spa
= dmu_objset_spa(os
);
478 if (spa_feature_is_enabled(spa
, SPA_FEATURE_SPACEMAP_HISTOGRAM
)) {
479 spa_feature_incr(spa
, SPA_FEATURE_SPACEMAP_HISTOGRAM
, tx
);
480 bonuslen
= sizeof (space_map_phys_t
);
481 ASSERT3U(bonuslen
, <=, dmu_bonus_max());
483 bonuslen
= SPACE_MAP_SIZE_V0
;
486 object
= dmu_object_alloc(os
,
487 DMU_OT_SPACE_MAP
, space_map_blksz
,
488 DMU_OT_SPACE_MAP_HEADER
, bonuslen
, tx
);
494 space_map_free(space_map_t
*sm
, dmu_tx_t
*tx
)
501 spa
= dmu_objset_spa(sm
->sm_os
);
502 if (spa_feature_is_enabled(spa
, SPA_FEATURE_SPACEMAP_HISTOGRAM
)) {
503 dmu_object_info_t doi
;
505 dmu_object_info_from_db(sm
->sm_dbuf
, &doi
);
506 if (doi
.doi_bonus_size
!= SPACE_MAP_SIZE_V0
) {
507 VERIFY(spa_feature_is_active(spa
,
508 SPA_FEATURE_SPACEMAP_HISTOGRAM
));
509 spa_feature_decr(spa
,
510 SPA_FEATURE_SPACEMAP_HISTOGRAM
, tx
);
514 VERIFY3U(dmu_object_free(sm
->sm_os
, space_map_object(sm
), tx
), ==, 0);
519 space_map_object(space_map_t
*sm
)
521 return (sm
!= NULL
? sm
->sm_object
: 0);
525 * Returns the already synced, on-disk allocated space.
528 space_map_allocated(space_map_t
*sm
)
530 return (sm
!= NULL
? sm
->sm_alloc
: 0);
534 * Returns the already synced, on-disk length;
537 space_map_length(space_map_t
*sm
)
539 return (sm
!= NULL
? sm
->sm_length
: 0);
543 * Returns the allocated space that is currently syncing.
546 space_map_alloc_delta(space_map_t
*sm
)
550 ASSERT(sm
->sm_dbuf
!= NULL
);
551 return (sm
->sm_phys
->smp_alloc
- space_map_allocated(sm
));