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, 2014 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
= zio_buf_alloc(bufsize
);
77 mutex_exit(sm
->sm_lock
);
79 dmu_prefetch(sm
->sm_os
, space_map_object(sm
), bufsize
,
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 zio_buf_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
));
178 * Transfer the content of the range tree histogram to the space
179 * map histogram. The space map histogram contains 32 buckets ranging
180 * between 2^sm_shift to 2^(32+sm_shift-1). The range tree,
181 * however, can represent ranges from 2^0 to 2^63. Since the space
182 * map only cares about allocatable blocks (minimum of sm_shift) we
183 * can safely ignore all ranges in the range tree smaller than sm_shift.
185 for (i
= sm
->sm_shift
; i
< RANGE_TREE_HISTOGRAM_SIZE
; i
++) {
188 * Since the largest histogram bucket in the space map is
189 * 2^(32+sm_shift-1), we need to normalize the values in
190 * the range tree for any bucket larger than that size. For
191 * example given an sm_shift of 9, ranges larger than 2^40
192 * would get normalized as if they were 1TB ranges. Assume
193 * the range tree had a count of 5 in the 2^44 (16TB) bucket,
194 * the calculation below would normalize this to 5 * 2^4 (16).
196 ASSERT3U(i
, >=, idx
+ sm
->sm_shift
);
197 sm
->sm_phys
->smp_histogram
[idx
] +=
198 rt
->rt_histogram
[i
] << (i
- idx
- sm
->sm_shift
);
201 * Increment the space map's index as long as we haven't
202 * reached the maximum bucket size. Accumulate all ranges
203 * larger than the max bucket size into the last bucket.
205 if (idx
< SPACE_MAP_HISTOGRAM_SIZE
- 1) {
206 ASSERT3U(idx
+ sm
->sm_shift
, ==, i
);
208 ASSERT3U(idx
, <, SPACE_MAP_HISTOGRAM_SIZE
);
214 space_map_entries(space_map_t
*sm
, range_tree_t
*rt
)
216 avl_tree_t
*t
= &rt
->rt_root
;
218 uint64_t size
, entries
;
221 * All space_maps always have a debug entry so account for it here.
226 * Traverse the range tree and calculate the number of space map
227 * entries that would be required to write out the range tree.
229 for (rs
= avl_first(t
); rs
!= NULL
; rs
= AVL_NEXT(t
, rs
)) {
230 size
= (rs
->rs_end
- rs
->rs_start
) >> sm
->sm_shift
;
231 entries
+= howmany(size
, SM_RUN_MAX
);
237 * Note: space_map_write() will drop sm_lock across dmu_write() calls.
240 space_map_write(space_map_t
*sm
, range_tree_t
*rt
, maptype_t maptype
,
243 objset_t
*os
= sm
->sm_os
;
244 spa_t
*spa
= dmu_objset_spa(os
);
245 avl_tree_t
*t
= &rt
->rt_root
;
247 uint64_t size
, total
, rt_space
, nodes
;
248 uint64_t *entry
, *entry_map
, *entry_map_end
;
249 uint64_t expected_entries
, actual_entries
= 1;
251 ASSERT(MUTEX_HELD(rt
->rt_lock
));
252 ASSERT(dsl_pool_sync_context(dmu_objset_pool(os
)));
253 VERIFY3U(space_map_object(sm
), !=, 0);
254 dmu_buf_will_dirty(sm
->sm_dbuf
, tx
);
257 * This field is no longer necessary since the in-core space map
258 * now contains the object number but is maintained for backwards
261 sm
->sm_phys
->smp_object
= sm
->sm_object
;
263 if (range_tree_space(rt
) == 0) {
264 VERIFY3U(sm
->sm_object
, ==, sm
->sm_phys
->smp_object
);
268 if (maptype
== SM_ALLOC
)
269 sm
->sm_phys
->smp_alloc
+= range_tree_space(rt
);
271 sm
->sm_phys
->smp_alloc
-= range_tree_space(rt
);
273 expected_entries
= space_map_entries(sm
, rt
);
275 entry_map
= zio_buf_alloc(sm
->sm_blksz
);
276 entry_map_end
= entry_map
+ (sm
->sm_blksz
/ sizeof (uint64_t));
279 *entry
++ = SM_DEBUG_ENCODE(1) |
280 SM_DEBUG_ACTION_ENCODE(maptype
) |
281 SM_DEBUG_SYNCPASS_ENCODE(spa_sync_pass(spa
)) |
282 SM_DEBUG_TXG_ENCODE(dmu_tx_get_txg(tx
));
285 nodes
= avl_numnodes(&rt
->rt_root
);
286 rt_space
= range_tree_space(rt
);
287 for (rs
= avl_first(t
); rs
!= NULL
; rs
= AVL_NEXT(t
, rs
)) {
290 size
= (rs
->rs_end
- rs
->rs_start
) >> sm
->sm_shift
;
291 start
= (rs
->rs_start
- sm
->sm_start
) >> sm
->sm_shift
;
293 total
+= size
<< sm
->sm_shift
;
298 run_len
= MIN(size
, SM_RUN_MAX
);
300 if (entry
== entry_map_end
) {
301 mutex_exit(rt
->rt_lock
);
302 dmu_write(os
, space_map_object(sm
),
303 sm
->sm_phys
->smp_objsize
, sm
->sm_blksz
,
305 mutex_enter(rt
->rt_lock
);
306 sm
->sm_phys
->smp_objsize
+= sm
->sm_blksz
;
310 *entry
++ = SM_OFFSET_ENCODE(start
) |
311 SM_TYPE_ENCODE(maptype
) |
312 SM_RUN_ENCODE(run_len
);
320 if (entry
!= entry_map
) {
321 size
= (entry
- entry_map
) * sizeof (uint64_t);
322 mutex_exit(rt
->rt_lock
);
323 dmu_write(os
, space_map_object(sm
), sm
->sm_phys
->smp_objsize
,
324 size
, entry_map
, tx
);
325 mutex_enter(rt
->rt_lock
);
326 sm
->sm_phys
->smp_objsize
+= size
;
328 ASSERT3U(expected_entries
, ==, actual_entries
);
331 * Ensure that the space_map's accounting wasn't changed
332 * while we were in the middle of writing it out.
334 VERIFY3U(nodes
, ==, avl_numnodes(&rt
->rt_root
));
335 VERIFY3U(range_tree_space(rt
), ==, rt_space
);
336 VERIFY3U(range_tree_space(rt
), ==, total
);
338 zio_buf_free(entry_map
, sm
->sm_blksz
);
342 space_map_open_impl(space_map_t
*sm
)
347 error
= dmu_bonus_hold(sm
->sm_os
, sm
->sm_object
, sm
, &sm
->sm_dbuf
);
351 dmu_object_size_from_db(sm
->sm_dbuf
, &sm
->sm_blksz
, &blocks
);
352 sm
->sm_phys
= sm
->sm_dbuf
->db_data
;
357 space_map_open(space_map_t
**smp
, objset_t
*os
, uint64_t object
,
358 uint64_t start
, uint64_t size
, uint8_t shift
, kmutex_t
*lp
)
363 ASSERT(*smp
== NULL
);
367 sm
= kmem_alloc(sizeof (space_map_t
), KM_SLEEP
);
369 sm
->sm_start
= start
;
371 sm
->sm_shift
= shift
;
374 sm
->sm_object
= object
;
381 error
= space_map_open_impl(sm
);
393 space_map_close(space_map_t
*sm
)
398 if (sm
->sm_dbuf
!= NULL
)
399 dmu_buf_rele(sm
->sm_dbuf
, sm
);
403 kmem_free(sm
, sizeof (*sm
));
407 space_map_truncate(space_map_t
*sm
, dmu_tx_t
*tx
)
409 objset_t
*os
= sm
->sm_os
;
410 spa_t
*spa
= dmu_objset_spa(os
);
411 dmu_object_info_t doi
;
413 ASSERT(dsl_pool_sync_context(dmu_objset_pool(os
)));
414 ASSERT(dmu_tx_is_syncing(tx
));
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, reallocating: "
430 "old bonus %llu, old blocksz %u", dmu_tx_get_txg(tx
),
431 spa_name(spa
), doi
.doi_bonus_size
, doi
.doi_data_block_size
);
433 space_map_free(sm
, tx
);
434 dmu_buf_rele(sm
->sm_dbuf
, sm
);
436 sm
->sm_object
= space_map_alloc(sm
->sm_os
, tx
);
437 VERIFY0(space_map_open_impl(sm
));
439 VERIFY0(dmu_free_range(os
, space_map_object(sm
), 0, -1ULL, tx
));
442 * If the spacemap is reallocated, its histogram
443 * will be reset. Do the same in the common case so that
444 * bugs related to the uncommon case do not go unnoticed.
446 bzero(sm
->sm_phys
->smp_histogram
,
447 sizeof (sm
->sm_phys
->smp_histogram
));
450 dmu_buf_will_dirty(sm
->sm_dbuf
, tx
);
451 sm
->sm_phys
->smp_objsize
= 0;
452 sm
->sm_phys
->smp_alloc
= 0;
456 * Update the in-core space_map allocation and length values.
459 space_map_update(space_map_t
*sm
)
464 ASSERT(MUTEX_HELD(sm
->sm_lock
));
466 sm
->sm_alloc
= sm
->sm_phys
->smp_alloc
;
467 sm
->sm_length
= sm
->sm_phys
->smp_objsize
;
471 space_map_alloc(objset_t
*os
, dmu_tx_t
*tx
)
473 spa_t
*spa
= dmu_objset_spa(os
);
477 if (spa_feature_is_enabled(spa
, SPA_FEATURE_SPACEMAP_HISTOGRAM
)) {
478 spa_feature_incr(spa
, SPA_FEATURE_SPACEMAP_HISTOGRAM
, tx
);
479 bonuslen
= sizeof (space_map_phys_t
);
480 ASSERT3U(bonuslen
, <=, dmu_bonus_max());
482 bonuslen
= SPACE_MAP_SIZE_V0
;
485 object
= dmu_object_alloc(os
,
486 DMU_OT_SPACE_MAP
, space_map_blksz
,
487 DMU_OT_SPACE_MAP_HEADER
, bonuslen
, tx
);
493 space_map_free(space_map_t
*sm
, dmu_tx_t
*tx
)
500 spa
= dmu_objset_spa(sm
->sm_os
);
501 if (spa_feature_is_enabled(spa
, SPA_FEATURE_SPACEMAP_HISTOGRAM
)) {
502 dmu_object_info_t doi
;
504 dmu_object_info_from_db(sm
->sm_dbuf
, &doi
);
505 if (doi
.doi_bonus_size
!= SPACE_MAP_SIZE_V0
) {
506 VERIFY(spa_feature_is_active(spa
,
507 SPA_FEATURE_SPACEMAP_HISTOGRAM
));
508 spa_feature_decr(spa
,
509 SPA_FEATURE_SPACEMAP_HISTOGRAM
, tx
);
513 VERIFY3U(dmu_object_free(sm
->sm_os
, space_map_object(sm
), tx
), ==, 0);
518 space_map_object(space_map_t
*sm
)
520 return (sm
!= NULL
? sm
->sm_object
: 0);
524 * Returns the already synced, on-disk allocated space.
527 space_map_allocated(space_map_t
*sm
)
529 return (sm
!= NULL
? sm
->sm_alloc
: 0);
533 * Returns the already synced, on-disk length;
536 space_map_length(space_map_t
*sm
)
538 return (sm
!= NULL
? sm
->sm_length
: 0);
542 * Returns the allocated space that is currently syncing.
545 space_map_alloc_delta(space_map_t
*sm
)
549 ASSERT(sm
->sm_dbuf
!= NULL
);
550 return (sm
->sm_phys
->smp_alloc
- space_map_allocated(sm
));