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, 2018 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>
40 SYSCTL_DECL(_vfs_zfs);
43 * Note on space map block size:
45 * The data for a given space map can be kept on blocks of any size.
46 * Larger blocks entail fewer I/O operations, but they also cause the
47 * DMU to keep more data in-core, and also to waste more I/O bandwidth
48 * when only a few blocks have changed since the last transaction group.
52 * Enabled whenever we want to stress test the use of double-word
55 boolean_t zfs_force_some_double_word_sm_entries = B_FALSE;
58 * Override the default indirect block size of 128K, instead using 16K for
59 * spacemaps (2^14 bytes). This dramatically reduces write inflation since
60 * appending to a spacemap typically has to write one data block (4KB) and one
61 * or two indirect blocks (16K-32K, rather than 128K).
63 int space_map_ibs = 14;
65 SYSCTL_INT(_vfs_zfs, OID_AUTO, space_map_ibs, CTLFLAG_RWTUN,
66 &space_map_ibs, 0, "Space map indirect block shift");
69 sm_entry_is_debug(uint64_t e)
71 return (SM_PREFIX_DECODE(e) == SM_DEBUG_PREFIX);
75 sm_entry_is_single_word(uint64_t e)
77 uint8_t prefix = SM_PREFIX_DECODE(e);
78 return (prefix != SM_DEBUG_PREFIX && prefix != SM2_PREFIX);
82 sm_entry_is_double_word(uint64_t e)
84 return (SM_PREFIX_DECODE(e) == SM2_PREFIX);
88 * Iterate through the space map, invoking the callback on each (non-debug)
89 * space map entry. Stop after reading 'end' bytes of the space map.
92 space_map_iterate(space_map_t *sm, uint64_t end, sm_cb_t callback, void *arg)
94 uint64_t blksz = sm->sm_blksz;
96 ASSERT3U(blksz, !=, 0);
97 ASSERT3U(end, <=, space_map_length(sm));
98 ASSERT0(P2PHASE(end, sizeof (uint64_t)));
100 dmu_prefetch(sm->sm_os, space_map_object(sm), 0, 0, end,
101 ZIO_PRIORITY_SYNC_READ);
104 for (uint64_t block_base = 0; block_base < end && error == 0;
105 block_base += blksz) {
107 error = dmu_buf_hold(sm->sm_os, space_map_object(sm),
108 block_base, FTAG, &db, DMU_READ_PREFETCH);
112 uint64_t *block_start = db->db_data;
113 uint64_t block_length = MIN(end - block_base, blksz);
114 uint64_t *block_end = block_start +
115 (block_length / sizeof (uint64_t));
117 VERIFY0(P2PHASE(block_length, sizeof (uint64_t)));
118 VERIFY3U(block_length, !=, 0);
119 ASSERT3U(blksz, ==, db->db_size);
121 for (uint64_t *block_cursor = block_start;
122 block_cursor < block_end && error == 0; block_cursor++) {
123 uint64_t e = *block_cursor;
125 if (sm_entry_is_debug(e)) /* Skip debug entries */
128 uint64_t raw_offset, raw_run, vdev_id;
130 if (sm_entry_is_single_word(e)) {
131 type = SM_TYPE_DECODE(e);
132 vdev_id = SM_NO_VDEVID;
133 raw_offset = SM_OFFSET_DECODE(e);
134 raw_run = SM_RUN_DECODE(e);
136 /* it is a two-word entry */
137 ASSERT(sm_entry_is_double_word(e));
138 raw_run = SM2_RUN_DECODE(e);
139 vdev_id = SM2_VDEV_DECODE(e);
141 /* move on to the second word */
144 VERIFY3P(block_cursor, <=, block_end);
146 type = SM2_TYPE_DECODE(e);
147 raw_offset = SM2_OFFSET_DECODE(e);
150 uint64_t entry_offset = (raw_offset << sm->sm_shift) +
152 uint64_t entry_run = raw_run << sm->sm_shift;
154 VERIFY0(P2PHASE(entry_offset, 1ULL << sm->sm_shift));
155 VERIFY0(P2PHASE(entry_run, 1ULL << sm->sm_shift));
156 ASSERT3U(entry_offset, >=, sm->sm_start);
157 ASSERT3U(entry_offset, <, sm->sm_start + sm->sm_size);
158 ASSERT3U(entry_run, <=, sm->sm_size);
159 ASSERT3U(entry_offset + entry_run, <=,
160 sm->sm_start + sm->sm_size);
162 space_map_entry_t sme = {
165 .sme_offset = entry_offset,
168 error = callback(&sme, arg);
170 dmu_buf_rele(db, FTAG);
176 * Reads the entries from the last block of the space map into
177 * buf in reverse order. Populates nwords with number of words
180 * Refer to block comment within space_map_incremental_destroy()
181 * to understand why this function is needed.
184 space_map_reversed_last_block_entries(space_map_t *sm, uint64_t *buf,
185 uint64_t bufsz, uint64_t *nwords)
191 * Find the offset of the last word in the space map and use
192 * that to read the last block of the space map with
195 uint64_t last_word_offset =
196 sm->sm_phys->smp_length - sizeof (uint64_t);
197 error = dmu_buf_hold(sm->sm_os, space_map_object(sm), last_word_offset,
198 FTAG, &db, DMU_READ_NO_PREFETCH);
202 ASSERT3U(sm->sm_object, ==, db->db_object);
203 ASSERT3U(sm->sm_blksz, ==, db->db_size);
204 ASSERT3U(bufsz, >=, db->db_size);
205 ASSERT(nwords != NULL);
207 uint64_t *words = db->db_data;
209 (sm->sm_phys->smp_length - db->db_offset) / sizeof (uint64_t);
211 ASSERT3U(*nwords, <=, bufsz / sizeof (uint64_t));
213 uint64_t n = *nwords;
215 for (uint64_t i = 0; i < n; i++) {
216 uint64_t entry = words[i];
217 if (sm_entry_is_double_word(entry)) {
219 * Since we are populating the buffer backwards
220 * we have to be extra careful and add the two
221 * words of the double-word entry in the right
233 ASSERT(sm_entry_is_debug(entry) ||
234 sm_entry_is_single_word(entry));
241 * Assert that we wrote backwards all the
242 * way to the beginning of the buffer.
246 dmu_buf_rele(db, FTAG);
251 * Note: This function performs destructive actions - specifically
252 * it deletes entries from the end of the space map. Thus, callers
253 * should ensure that they are holding the appropriate locks for
254 * the space map that they provide.
257 space_map_incremental_destroy(space_map_t *sm, sm_cb_t callback, void *arg,
260 uint64_t bufsz = MAX(sm->sm_blksz, SPA_MINBLOCKSIZE);
261 uint64_t *buf = zio_buf_alloc(bufsz);
263 dmu_buf_will_dirty(sm->sm_dbuf, tx);
266 * Ideally we would want to iterate from the beginning of the
267 * space map to the end in incremental steps. The issue with this
268 * approach is that we don't have any field on-disk that points
269 * us where to start between each step. We could try zeroing out
270 * entries that we've destroyed, but this doesn't work either as
271 * an entry that is 0 is a valid one (ALLOC for range [0x0:0x200]).
273 * As a result, we destroy its entries incrementally starting from
274 * the end after applying the callback to each of them.
276 * The problem with this approach is that we cannot literally
277 * iterate through the words in the space map backwards as we
278 * can't distinguish two-word space map entries from their second
279 * word. Thus we do the following:
281 * 1] We get all the entries from the last block of the space map
282 * and put them into a buffer in reverse order. This way the
283 * last entry comes first in the buffer, the second to last is
285 * 2] We iterate through the entries in the buffer and we apply
286 * the callback to each one. As we move from entry to entry we
287 * we decrease the size of the space map, deleting effectively
289 * 3] If there are no more entries in the space map or the callback
290 * returns a value other than 0, we stop iterating over the
291 * space map. If there are entries remaining and the callback
292 * returned 0, we go back to step [1].
295 while (space_map_length(sm) > 0 && error == 0) {
297 error = space_map_reversed_last_block_entries(sm, buf, bufsz,
302 ASSERT3U(nwords, <=, bufsz / sizeof (uint64_t));
304 for (uint64_t i = 0; i < nwords; i++) {
307 if (sm_entry_is_debug(e)) {
308 sm->sm_phys->smp_length -= sizeof (uint64_t);
313 uint64_t raw_offset, raw_run, vdev_id;
315 if (sm_entry_is_single_word(e)) {
316 type = SM_TYPE_DECODE(e);
317 vdev_id = SM_NO_VDEVID;
318 raw_offset = SM_OFFSET_DECODE(e);
319 raw_run = SM_RUN_DECODE(e);
321 ASSERT(sm_entry_is_double_word(e));
324 raw_run = SM2_RUN_DECODE(e);
325 vdev_id = SM2_VDEV_DECODE(e);
327 /* move to the second word */
331 ASSERT3P(i, <=, nwords);
333 type = SM2_TYPE_DECODE(e);
334 raw_offset = SM2_OFFSET_DECODE(e);
337 uint64_t entry_offset =
338 (raw_offset << sm->sm_shift) + sm->sm_start;
339 uint64_t entry_run = raw_run << sm->sm_shift;
341 VERIFY0(P2PHASE(entry_offset, 1ULL << sm->sm_shift));
342 VERIFY0(P2PHASE(entry_run, 1ULL << sm->sm_shift));
343 VERIFY3U(entry_offset, >=, sm->sm_start);
344 VERIFY3U(entry_offset, <, sm->sm_start + sm->sm_size);
345 VERIFY3U(entry_run, <=, sm->sm_size);
346 VERIFY3U(entry_offset + entry_run, <=,
347 sm->sm_start + sm->sm_size);
349 space_map_entry_t sme = {
352 .sme_offset = entry_offset,
355 error = callback(&sme, arg);
359 if (type == SM_ALLOC)
360 sm->sm_phys->smp_alloc -= entry_run;
362 sm->sm_phys->smp_alloc += entry_run;
363 sm->sm_phys->smp_length -= words * sizeof (uint64_t);
367 if (space_map_length(sm) == 0) {
369 ASSERT0(space_map_allocated(sm));
372 zio_buf_free(buf, bufsz);
376 typedef struct space_map_load_arg {
377 space_map_t *smla_sm;
378 range_tree_t *smla_rt;
380 } space_map_load_arg_t;
383 space_map_load_callback(space_map_entry_t *sme, void *arg)
385 space_map_load_arg_t *smla = arg;
386 if (sme->sme_type == smla->smla_type) {
387 VERIFY3U(range_tree_space(smla->smla_rt) + sme->sme_run, <=,
388 smla->smla_sm->sm_size);
389 range_tree_add(smla->smla_rt, sme->sme_offset, sme->sme_run);
391 range_tree_remove(smla->smla_rt, sme->sme_offset, sme->sme_run);
398 * Load the spacemap into the rangetree, like space_map_load. But only
399 * read the first 'length' bytes of the spacemap.
402 space_map_load_length(space_map_t *sm, range_tree_t *rt, maptype_t maptype,
405 space_map_load_arg_t smla;
407 VERIFY0(range_tree_space(rt));
409 if (maptype == SM_FREE)
410 range_tree_add(rt, sm->sm_start, sm->sm_size);
414 smla.smla_type = maptype;
415 int err = space_map_iterate(sm, length,
416 space_map_load_callback, &smla);
419 range_tree_vacate(rt, NULL, NULL);
425 * Load the space map disk into the specified range tree. Segments of maptype
426 * are added to the range tree, other segment types are removed.
429 space_map_load(space_map_t *sm, range_tree_t *rt, maptype_t maptype)
431 return (space_map_load_length(sm, rt, maptype, space_map_length(sm)));
435 space_map_histogram_clear(space_map_t *sm)
437 if (sm->sm_dbuf->db_size != sizeof (space_map_phys_t))
440 bzero(sm->sm_phys->smp_histogram, sizeof (sm->sm_phys->smp_histogram));
444 space_map_histogram_verify(space_map_t *sm, range_tree_t *rt)
447 * Verify that the in-core range tree does not have any
448 * ranges smaller than our sm_shift size.
450 for (int i = 0; i < sm->sm_shift; i++) {
451 if (rt->rt_histogram[i] != 0)
458 space_map_histogram_add(space_map_t *sm, range_tree_t *rt, dmu_tx_t *tx)
462 ASSERT(dmu_tx_is_syncing(tx));
463 VERIFY3U(space_map_object(sm), !=, 0);
465 if (sm->sm_dbuf->db_size != sizeof (space_map_phys_t))
468 dmu_buf_will_dirty(sm->sm_dbuf, tx);
470 ASSERT(space_map_histogram_verify(sm, rt));
472 * Transfer the content of the range tree histogram to the space
473 * map histogram. The space map histogram contains 32 buckets ranging
474 * between 2^sm_shift to 2^(32+sm_shift-1). The range tree,
475 * however, can represent ranges from 2^0 to 2^63. Since the space
476 * map only cares about allocatable blocks (minimum of sm_shift) we
477 * can safely ignore all ranges in the range tree smaller than sm_shift.
479 for (int i = sm->sm_shift; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
482 * Since the largest histogram bucket in the space map is
483 * 2^(32+sm_shift-1), we need to normalize the values in
484 * the range tree for any bucket larger than that size. For
485 * example given an sm_shift of 9, ranges larger than 2^40
486 * would get normalized as if they were 1TB ranges. Assume
487 * the range tree had a count of 5 in the 2^44 (16TB) bucket,
488 * the calculation below would normalize this to 5 * 2^4 (16).
490 ASSERT3U(i, >=, idx + sm->sm_shift);
491 sm->sm_phys->smp_histogram[idx] +=
492 rt->rt_histogram[i] << (i - idx - sm->sm_shift);
495 * Increment the space map's index as long as we haven't
496 * reached the maximum bucket size. Accumulate all ranges
497 * larger than the max bucket size into the last bucket.
499 if (idx < SPACE_MAP_HISTOGRAM_SIZE - 1) {
500 ASSERT3U(idx + sm->sm_shift, ==, i);
502 ASSERT3U(idx, <, SPACE_MAP_HISTOGRAM_SIZE);
508 space_map_write_intro_debug(space_map_t *sm, maptype_t maptype, dmu_tx_t *tx)
510 dmu_buf_will_dirty(sm->sm_dbuf, tx);
512 uint64_t dentry = SM_PREFIX_ENCODE(SM_DEBUG_PREFIX) |
513 SM_DEBUG_ACTION_ENCODE(maptype) |
514 SM_DEBUG_SYNCPASS_ENCODE(spa_sync_pass(tx->tx_pool->dp_spa)) |
515 SM_DEBUG_TXG_ENCODE(dmu_tx_get_txg(tx));
517 dmu_write(sm->sm_os, space_map_object(sm), sm->sm_phys->smp_length,
518 sizeof (dentry), &dentry, tx);
520 sm->sm_phys->smp_length += sizeof (dentry);
524 * Writes one or more entries given a segment.
526 * Note: The function may release the dbuf from the pointer initially
527 * passed to it, and return a different dbuf. Also, the space map's
528 * dbuf must be dirty for the changes in sm_phys to take effect.
531 space_map_write_seg(space_map_t *sm, range_seg_t *rs, maptype_t maptype,
532 uint64_t vdev_id, uint8_t words, dmu_buf_t **dbp, void *tag, dmu_tx_t *tx)
534 ASSERT3U(words, !=, 0);
535 ASSERT3U(words, <=, 2);
537 /* ensure the vdev_id can be represented by the space map */
538 ASSERT3U(vdev_id, <=, SM_NO_VDEVID);
541 * if this is a single word entry, ensure that no vdev was
544 IMPLY(words == 1, vdev_id == SM_NO_VDEVID);
546 dmu_buf_t *db = *dbp;
547 ASSERT3U(db->db_size, ==, sm->sm_blksz);
549 uint64_t *block_base = db->db_data;
550 uint64_t *block_end = block_base + (sm->sm_blksz / sizeof (uint64_t));
551 uint64_t *block_cursor = block_base +
552 (sm->sm_phys->smp_length - db->db_offset) / sizeof (uint64_t);
554 ASSERT3P(block_cursor, <=, block_end);
556 uint64_t size = (rs->rs_end - rs->rs_start) >> sm->sm_shift;
557 uint64_t start = (rs->rs_start - sm->sm_start) >> sm->sm_shift;
558 uint64_t run_max = (words == 2) ? SM2_RUN_MAX : SM_RUN_MAX;
560 ASSERT3U(rs->rs_start, >=, sm->sm_start);
561 ASSERT3U(rs->rs_start, <, sm->sm_start + sm->sm_size);
562 ASSERT3U(rs->rs_end - rs->rs_start, <=, sm->sm_size);
563 ASSERT3U(rs->rs_end, <=, sm->sm_start + sm->sm_size);
566 ASSERT3P(block_cursor, <=, block_end);
569 * If we are at the end of this block, flush it and start
570 * writing again from the beginning.
572 if (block_cursor == block_end) {
573 dmu_buf_rele(db, tag);
575 uint64_t next_word_offset = sm->sm_phys->smp_length;
576 VERIFY0(dmu_buf_hold(sm->sm_os,
577 space_map_object(sm), next_word_offset,
578 tag, &db, DMU_READ_PREFETCH));
579 dmu_buf_will_dirty(db, tx);
581 /* update caller's dbuf */
584 ASSERT3U(db->db_size, ==, sm->sm_blksz);
586 block_base = db->db_data;
587 block_cursor = block_base;
588 block_end = block_base +
589 (db->db_size / sizeof (uint64_t));
593 * If we are writing a two-word entry and we only have one
594 * word left on this block, just pad it with an empty debug
595 * entry and write the two-word entry in the next block.
597 uint64_t *next_entry = block_cursor + 1;
598 if (next_entry == block_end && words > 1) {
599 ASSERT3U(words, ==, 2);
600 *block_cursor = SM_PREFIX_ENCODE(SM_DEBUG_PREFIX) |
601 SM_DEBUG_ACTION_ENCODE(0) |
602 SM_DEBUG_SYNCPASS_ENCODE(0) |
603 SM_DEBUG_TXG_ENCODE(0);
605 sm->sm_phys->smp_length += sizeof (uint64_t);
606 ASSERT3P(block_cursor, ==, block_end);
610 uint64_t run_len = MIN(size, run_max);
613 *block_cursor = SM_OFFSET_ENCODE(start) |
614 SM_TYPE_ENCODE(maptype) |
615 SM_RUN_ENCODE(run_len);
619 /* write the first word of the entry */
620 *block_cursor = SM_PREFIX_ENCODE(SM2_PREFIX) |
621 SM2_RUN_ENCODE(run_len) |
622 SM2_VDEV_ENCODE(vdev_id);
625 /* move on to the second word of the entry */
626 ASSERT3P(block_cursor, <, block_end);
627 *block_cursor = SM2_TYPE_ENCODE(maptype) |
628 SM2_OFFSET_ENCODE(start);
632 panic("%d-word space map entries are not supported",
636 sm->sm_phys->smp_length += words * sizeof (uint64_t);
646 * Note: The space map's dbuf must be dirty for the changes in sm_phys to
650 space_map_write_impl(space_map_t *sm, range_tree_t *rt, maptype_t maptype,
651 uint64_t vdev_id, dmu_tx_t *tx)
653 spa_t *spa = tx->tx_pool->dp_spa;
656 space_map_write_intro_debug(sm, maptype, tx);
660 * We do this right after we write the intro debug entry
661 * because the estimate does not take it into account.
663 uint64_t initial_objsize = sm->sm_phys->smp_length;
664 uint64_t estimated_growth =
665 space_map_estimate_optimal_size(sm, rt, SM_NO_VDEVID);
666 uint64_t estimated_final_objsize = initial_objsize + estimated_growth;
670 * Find the offset right after the last word in the space map
671 * and use that to get a hold of the last block, so we can
672 * start appending to it.
674 uint64_t next_word_offset = sm->sm_phys->smp_length;
675 VERIFY0(dmu_buf_hold(sm->sm_os, space_map_object(sm),
676 next_word_offset, FTAG, &db, DMU_READ_PREFETCH));
677 ASSERT3U(db->db_size, ==, sm->sm_blksz);
679 dmu_buf_will_dirty(db, tx);
681 avl_tree_t *t = &rt->rt_root;
682 for (range_seg_t *rs = avl_first(t); rs != NULL; rs = AVL_NEXT(t, rs)) {
683 uint64_t offset = (rs->rs_start - sm->sm_start) >> sm->sm_shift;
684 uint64_t length = (rs->rs_end - rs->rs_start) >> sm->sm_shift;
688 * We only write two-word entries when both of the following
691 * [1] The feature is enabled.
692 * [2] The offset or run is too big for a single-word entry,
693 * or the vdev_id is set (meaning not equal to
696 * Note that for purposes of testing we've added the case that
697 * we write two-word entries occasionally when the feature is
698 * enabled and zfs_force_some_double_word_sm_entries has been
701 if (spa_feature_is_active(spa, SPA_FEATURE_SPACEMAP_V2) &&
702 (offset >= (1ULL << SM_OFFSET_BITS) ||
703 length > SM_RUN_MAX ||
704 vdev_id != SM_NO_VDEVID ||
705 (zfs_force_some_double_word_sm_entries &&
706 spa_get_random(100) == 0)))
709 space_map_write_seg(sm, rs, maptype, vdev_id, words,
713 dmu_buf_rele(db, FTAG);
717 * We expect our estimation to be based on the worst case
718 * scenario [see comment in space_map_estimate_optimal_size()].
719 * Therefore we expect the actual objsize to be equal or less
720 * than whatever we estimated it to be.
722 ASSERT3U(estimated_final_objsize, >=, sm->sm_phys->smp_length);
727 * Note: This function manipulates the state of the given space map but
728 * does not hold any locks implicitly. Thus the caller is responsible
729 * for synchronizing writes to the space map.
732 space_map_write(space_map_t *sm, range_tree_t *rt, maptype_t maptype,
733 uint64_t vdev_id, dmu_tx_t *tx)
735 objset_t *os = sm->sm_os;
737 ASSERT(dsl_pool_sync_context(dmu_objset_pool(os)));
738 VERIFY3U(space_map_object(sm), !=, 0);
740 dmu_buf_will_dirty(sm->sm_dbuf, tx);
743 * This field is no longer necessary since the in-core space map
744 * now contains the object number but is maintained for backwards
747 sm->sm_phys->smp_object = sm->sm_object;
749 if (range_tree_is_empty(rt)) {
750 VERIFY3U(sm->sm_object, ==, sm->sm_phys->smp_object);
754 if (maptype == SM_ALLOC)
755 sm->sm_phys->smp_alloc += range_tree_space(rt);
757 sm->sm_phys->smp_alloc -= range_tree_space(rt);
759 uint64_t nodes = avl_numnodes(&rt->rt_root);
760 uint64_t rt_space = range_tree_space(rt);
762 space_map_write_impl(sm, rt, maptype, vdev_id, tx);
765 * Ensure that the space_map's accounting wasn't changed
766 * while we were in the middle of writing it out.
768 VERIFY3U(nodes, ==, avl_numnodes(&rt->rt_root));
769 VERIFY3U(range_tree_space(rt), ==, rt_space);
773 space_map_open_impl(space_map_t *sm)
778 error = dmu_bonus_hold(sm->sm_os, sm->sm_object, sm, &sm->sm_dbuf);
782 dmu_object_size_from_db(sm->sm_dbuf, &sm->sm_blksz, &blocks);
783 sm->sm_phys = sm->sm_dbuf->db_data;
788 space_map_open(space_map_t **smp, objset_t *os, uint64_t object,
789 uint64_t start, uint64_t size, uint8_t shift)
794 ASSERT(*smp == NULL);
798 sm = kmem_zalloc(sizeof (space_map_t), KM_SLEEP);
800 sm->sm_start = start;
802 sm->sm_shift = shift;
804 sm->sm_object = object;
806 error = space_map_open_impl(sm);
817 space_map_close(space_map_t *sm)
822 if (sm->sm_dbuf != NULL)
823 dmu_buf_rele(sm->sm_dbuf, sm);
827 kmem_free(sm, sizeof (*sm));
831 space_map_truncate(space_map_t *sm, int blocksize, dmu_tx_t *tx)
833 objset_t *os = sm->sm_os;
834 spa_t *spa = dmu_objset_spa(os);
835 dmu_object_info_t doi;
837 ASSERT(dsl_pool_sync_context(dmu_objset_pool(os)));
838 ASSERT(dmu_tx_is_syncing(tx));
839 VERIFY3U(dmu_tx_get_txg(tx), <=, spa_final_dirty_txg(spa));
841 dmu_object_info_from_db(sm->sm_dbuf, &doi);
844 * If the space map has the wrong bonus size (because
845 * SPA_FEATURE_SPACEMAP_HISTOGRAM has recently been enabled), or
846 * the wrong block size (because space_map_blksz has changed),
847 * free and re-allocate its object with the updated sizes.
849 * Otherwise, just truncate the current object.
851 if ((spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM) &&
852 doi.doi_bonus_size != sizeof (space_map_phys_t)) ||
853 doi.doi_data_block_size != blocksize ||
854 doi.doi_metadata_block_size != 1 << space_map_ibs) {
855 zfs_dbgmsg("txg %llu, spa %s, sm %p, reallocating "
856 "object[%llu]: old bonus %u, old blocksz %u",
857 dmu_tx_get_txg(tx), spa_name(spa), sm, sm->sm_object,
858 doi.doi_bonus_size, doi.doi_data_block_size);
860 space_map_free(sm, tx);
861 dmu_buf_rele(sm->sm_dbuf, sm);
863 sm->sm_object = space_map_alloc(sm->sm_os, blocksize, tx);
864 VERIFY0(space_map_open_impl(sm));
866 VERIFY0(dmu_free_range(os, space_map_object(sm), 0, -1ULL, tx));
869 * If the spacemap is reallocated, its histogram
870 * will be reset. Do the same in the common case so that
871 * bugs related to the uncommon case do not go unnoticed.
873 bzero(sm->sm_phys->smp_histogram,
874 sizeof (sm->sm_phys->smp_histogram));
877 dmu_buf_will_dirty(sm->sm_dbuf, tx);
878 sm->sm_phys->smp_length = 0;
879 sm->sm_phys->smp_alloc = 0;
883 space_map_alloc(objset_t *os, int blocksize, dmu_tx_t *tx)
885 spa_t *spa = dmu_objset_spa(os);
889 if (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM)) {
890 spa_feature_incr(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM, tx);
891 bonuslen = sizeof (space_map_phys_t);
892 ASSERT3U(bonuslen, <=, dmu_bonus_max());
894 bonuslen = SPACE_MAP_SIZE_V0;
897 object = dmu_object_alloc_ibs(os, DMU_OT_SPACE_MAP, blocksize,
898 space_map_ibs, DMU_OT_SPACE_MAP_HEADER, bonuslen, tx);
904 space_map_free_obj(objset_t *os, uint64_t smobj, dmu_tx_t *tx)
906 spa_t *spa = dmu_objset_spa(os);
907 if (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_HISTOGRAM)) {
908 dmu_object_info_t doi;
910 VERIFY0(dmu_object_info(os, smobj, &doi));
911 if (doi.doi_bonus_size != SPACE_MAP_SIZE_V0) {
912 spa_feature_decr(spa,
913 SPA_FEATURE_SPACEMAP_HISTOGRAM, tx);
917 VERIFY0(dmu_object_free(os, smobj, tx));
921 space_map_free(space_map_t *sm, dmu_tx_t *tx)
926 space_map_free_obj(sm->sm_os, space_map_object(sm), tx);
931 * Given a range tree, it makes a worst-case estimate of how much
932 * space would the tree's segments take if they were written to
933 * the given space map.
936 space_map_estimate_optimal_size(space_map_t *sm, range_tree_t *rt,
939 spa_t *spa = dmu_objset_spa(sm->sm_os);
940 uint64_t shift = sm->sm_shift;
941 uint64_t *histogram = rt->rt_histogram;
942 uint64_t entries_for_seg = 0;
945 * In order to get a quick estimate of the optimal size that this
946 * range tree would have on-disk as a space map, we iterate through
947 * its histogram buckets instead of iterating through its nodes.
949 * Note that this is a highest-bound/worst-case estimate for the
952 * 1] We assume that we always add a debug padding for each block
953 * we write and we also assume that we start at the last word
954 * of a block attempting to write a two-word entry.
955 * 2] Rounding up errors due to the way segments are distributed
956 * in the buckets of the range tree's histogram.
957 * 3] The activation of zfs_force_some_double_word_sm_entries
958 * (tunable) when testing.
960 * = Math and Rounding Errors =
962 * rt_histogram[i] bucket of a range tree represents the number
963 * of entries in [2^i, (2^(i+1))-1] of that range_tree. Given
964 * that, we want to divide the buckets into groups: Buckets that
965 * can be represented using a single-word entry, ones that can
966 * be represented with a double-word entry, and ones that can
967 * only be represented with multiple two-word entries.
969 * [Note that if the new encoding feature is not enabled there
970 * are only two groups: single-word entry buckets and multiple
971 * single-word entry buckets. The information below assumes
972 * two-word entries enabled, but it can easily applied when
973 * the feature is not enabled]
975 * To find the highest bucket that can be represented with a
976 * single-word entry we look at the maximum run that such entry
977 * can have, which is 2^(SM_RUN_BITS + sm_shift) [remember that
978 * the run of a space map entry is shifted by sm_shift, thus we
979 * add it to the exponent]. This way, excluding the value of the
980 * maximum run that can be represented by a single-word entry,
981 * all runs that are smaller exist in buckets 0 to
982 * SM_RUN_BITS + shift - 1.
984 * To find the highest bucket that can be represented with a
985 * double-word entry, we follow the same approach. Finally, any
986 * bucket higher than that are represented with multiple two-word
987 * entries. To be more specific, if the highest bucket whose
988 * segments can be represented with a single two-word entry is X,
989 * then bucket X+1 will need 2 two-word entries for each of its
990 * segments, X+2 will need 4, X+3 will need 8, ...etc.
992 * With all of the above we make our estimation based on bucket
993 * groups. There is a rounding error though. As we mentioned in
994 * the example with the one-word entry, the maximum run that can
995 * be represented in a one-word entry 2^(SM_RUN_BITS + shift) is
996 * not part of bucket SM_RUN_BITS + shift - 1. Thus, segments of
997 * that length fall into the next bucket (and bucket group) where
998 * we start counting two-word entries and this is one more reason
999 * why the estimated size may end up being bigger than the actual
1005 if (!spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2) ||
1006 (vdev_id == SM_NO_VDEVID && sm->sm_size < SM_OFFSET_MAX)) {
1009 * If we are trying to force some double word entries just
1010 * assume the worst-case of every single word entry being
1011 * written as a double word entry.
1013 uint64_t entry_size =
1014 (spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2) &&
1015 zfs_force_some_double_word_sm_entries) ?
1016 (2 * sizeof (uint64_t)) : sizeof (uint64_t);
1018 uint64_t single_entry_max_bucket = SM_RUN_BITS + shift - 1;
1019 for (; idx <= single_entry_max_bucket; idx++)
1020 size += histogram[idx] * entry_size;
1022 if (!spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2)) {
1023 for (; idx < RANGE_TREE_HISTOGRAM_SIZE; idx++) {
1024 ASSERT3U(idx, >=, single_entry_max_bucket);
1026 1ULL << (idx - single_entry_max_bucket);
1027 size += histogram[idx] *
1028 entries_for_seg * entry_size;
1034 ASSERT(spa_feature_is_enabled(spa, SPA_FEATURE_SPACEMAP_V2));
1036 uint64_t double_entry_max_bucket = SM2_RUN_BITS + shift - 1;
1037 for (; idx <= double_entry_max_bucket; idx++)
1038 size += histogram[idx] * 2 * sizeof (uint64_t);
1040 for (; idx < RANGE_TREE_HISTOGRAM_SIZE; idx++) {
1041 ASSERT3U(idx, >=, double_entry_max_bucket);
1042 entries_for_seg = 1ULL << (idx - double_entry_max_bucket);
1043 size += histogram[idx] *
1044 entries_for_seg * 2 * sizeof (uint64_t);
1048 * Assume the worst case where we start with the padding at the end
1049 * of the current block and we add an extra padding entry at the end
1050 * of all subsequent blocks.
1052 size += ((size / sm->sm_blksz) + 1) * sizeof (uint64_t);
1058 space_map_object(space_map_t *sm)
1060 return (sm != NULL ? sm->sm_object : 0);
1064 space_map_allocated(space_map_t *sm)
1066 return (sm != NULL ? sm->sm_phys->smp_alloc : 0);
1070 space_map_length(space_map_t *sm)
1072 return (sm != NULL ? sm->sm_phys->smp_length : 0);