Uberblok

Room 9

Metaslabs and space maps

Copy-on-write never overwrites a block: every write allocates new space and every overwrite frees the old block. Allocation is on the path of every write, so it has to be fast, and what is free has to be recorded on disk, so that the pool still knows it after a reboot.

The obvious record is a bitmap of the whole pool, one bit per sector. A pool of 16 TiB with 4 KiB sectors has 232 of them: 512 MiB of bitmap to keep in memory, and it would have to be updated in place on every change, which is exactly what copy-on-write forbids. ZFS does something else. It cuts each vdev into a few hundred metaslabs, keeps the free space of a metaslab as a tree of free segments in memory, and records on disk only what changed, as a space map: a log of ALLOC and FREE extents that is only ever appended to, and rewritten short when it has grown too long.

1 Write, delete, sync

Below, a vdev of 8 GiB with 4 KiB sectors, cut into 16 metaslabs of 512 MiB; every write goes to metaslab 2, drawn underneath. Two files are already there: A, 32 MiB, written in txg 10, and B, 4 MiB, in txg 11. The tape is the metaslab’s space map, 64-bit words on disk; select an entry to see its bits.

Delete A and sync: a FREE entry joins the tape, but A’s space is deferred, not free, for two more txgs. Sync twice to get it back, then write 160 MiB: dynamic fit does not go back to A’s hole, and a run that long needs a two-word entry. Press Load to rebuild the free tree from the tape, and Condense: it is refused while the map is short. Rewrite the database until the test says yes, then condense.

  • free (ms_allocatable)
  • allocated, on the map
  • allocated in the open txg
  • freed in the open txg
  • freed, deferred
  • dynamic-fit cursor

In memory

  • ms_allocatable 476 MiB, 1 segment
  • ms_allocating[0] empty
  • ms_freeing empty
  • ms_defer[] empty
  • ms_lbas[17] 0x42400000 where the next 128 KiB block is looked for

Files

  • A 32 MiB · 1 extent · on the map
  • B 4 MiB · 1 extent · on the map

On disk: the space map of metaslab 2

smp_length 32 bytes (4 words, in 1 block of 16 KiB) · smp_alloc 36 MiB

  1. txg 10 ALLOC
  2. ALLOC 32 MiB
  3. txg 11 ALLOC
  4. ALLOC 4 MiB

ALLOC 4 MiB, at word 3, 1 word

word 3 0x00000000200003FF

prefixbits 63 (1)0offsetbits 62–16 (47)0x2000typebits 15 (1)0run − 1bits 14–0 (15)0x3FF

ALLOC: offset 0x2000, in units of 4 KiB from the start of the metaslab (32 MiB, vdev offset 0x42000000), run 1,024 units (4 MiB). The run fits in 15 bits (at most 32,768 units, 128 MiB): one word. code

Condense?

  • no At least twice the optimal size, 24 bytes (zfs_condense_pct 200): 32 bytes against 48
  • no Longer than four blocks of 16 KiB (zfs_metaslab_condense_block_threshold): 32 bytes against 65,536

metaslab_should_condense: no The map keeps growing. code

Text version of this figure

A vdev of 16 metaslabs; metaslab 2 starts at 0x40000000. Open txg: 12.

  • Free tree (ms_allocatable), 476 MiB: [0x42400000, 0x60000000).
  • Open txg 12: allocated none; freed none.
  • Nothing deferred.
  • Files: A (32 MiB: [0x40000000, 0x42000000)); B (4 MiB: [0x42000000, 0x42400000)).
  • Space map: smp_length 32 bytes (4 words, in 1 block of 16 KiB) · smp_alloc 36 MiB. Last words: 0x800400000000000A (txg 10 ALLOC, a debug word at word 0: ALLOC entries follow); 0x0000000000001FFF (ALLOC 32 MiB, at word 1, 1 word); 0x800400000000000B (txg 11 ALLOC, a debug word at word 2: ALLOC entries follow); 0x00000000200003FF (ALLOC 4 MiB, at word 3, 1 word).

Open txg 12. Free: 476 MiB in 1 segment. Space map: 32 bytes, 2 entries. Condense: no.

The idea, at three depths

In one sentence

ZFS keeps free space per metaslab, as a tree in memory and an append-only log on disk that, replayed, rebuilds the tree, and it rewrites the log from the tree when the log has grown much longer than the tree.

In one paragraph

A top-level vdev is cut into metaslabs, about 200 by default, from 512 MiB to 16 GiB each (fewer and smaller on small vdevs). A loaded metaslab has its free segments in a range tree, ms_allocatable. An allocation takes a segment from that tree, by default with the dynamic-fit allocator, which searches forward from where the last allocation of that size ended, and puts it in a per-txg tree, ms_allocating; a free goes to ms_freeing. Nothing reaches the disk until the txg syncs: then the txg’s allocations and frees are appended to the metaslab’s space map, a debug word and ALLOC entries, a debug word and FREE entries, one or two 64-bit words per extent. Freed space becomes allocatable again only two txgs later, so that the pool can be rolled back to an older uberblock without finding its blocks reused. Loading a metaslab replays its map, adding FREE and removing ALLOC extents. And when the map is at least twice as long as the free tree would be written alone, and longer than four blocks, the next sync condenses it if the metaslab is loaded: the map is truncated and rewritten from the tree.

In detail

Metaslabs. A metaslab, struct metaslab, is a range of a vdev with its in-core trees: ms_allocatable, the free tree, ms_allocating[], one per txg in flight, ms_freeing, ms_freed and ms_defer[]; a comment in the header draws their life cycle. Their size comes from vdev_metaslab_set_size: it aims at 200 metaslabs, within 512 MiB and 16 GiB, and at least 16 on a small vdev. The figure’s vdev, 8 GiB, gets 16 metaslabs of 512 MiB. A metaslab’s map counts in sectors: its shift is the vdev’s ashift, so a unit is 4 KiB here.

Taking a block. Allocating from a metaslab:

metaslab_block_alloc Excerpt of module/zfs/metaslab.c, lines 4863–4890, OpenZFS zfs-2.4.4. View on GitHub 
	ASSERT(MUTEX_HELD(&msp->ms_lock));
	VERIFY(!msp->ms_condensing);
	VERIFY0(msp->ms_disabled);
	VERIFY0(msp->ms_new);

	start = mc->mc_ops->msop_alloc(msp, size, max_size, actual_size);
	if (start != -1ULL) {
		size = *actual_size;
		metaslab_group_t *mg = msp->ms_group;
		vdev_t *vd = mg->mg_vd;

		VERIFY0(P2PHASE(start, 1ULL << vd->vdev_ashift));
		VERIFY0(P2PHASE(size, 1ULL << vd->vdev_ashift));
		VERIFY3U(zfs_range_tree_space(rt) - size, <=, msp->ms_size);
		zfs_range_tree_remove(rt, start, size);
		zfs_range_tree_clear(msp->ms_trim, start, size);

		if (zfs_range_tree_is_empty(msp->ms_allocating[txg & TXG_MASK]))
			vdev_dirty(mg->mg_vd, VDD_METASLAB, msp, txg);

		zfs_range_tree_add(msp->ms_allocating[txg & TXG_MASK], start,
		    size);
		msp->ms_allocating_total += size;

		/* Track the last successful allocation */
		msp->ms_alloc_txg = txg;
		metaslab_verify_space(msp, txg);
	}
  1. L4864 No allocation from a metaslab whose map is being condensed: its free tree is being written out.
  2. L4868 The class’s allocator, dynamic fit by default, returns an offset in this metaslab.
  3. L4877 The extent leaves the free tree.
  4. L4880–L4881 The first allocation of a txg marks the metaslab dirty, so the sync will visit it.
  5. L4883–L4884 The extent goes into ms_allocating for this txg. Nothing is written to disk yet. In the figure, the orange extents.

Dynamic fit. Which offset the allocator returns:

metaslab_df_alloc Excerpt of module/zfs/metaslab.c, lines 1905–1931, OpenZFS zfs-2.4.4. View on GitHub 
	uint64_t align = max_size & -max_size;
	uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1];
	zfs_range_tree_t *rt = msp->ms_allocatable;
	uint_t free_pct = zfs_range_tree_space(rt) * 100 / msp->ms_size;
	uint64_t offset;

	ASSERT(MUTEX_HELD(&msp->ms_lock));

	/*
	 * If we're running low on space, find a segment based on size,
	 * rather than iterating based on offset.
	 */
	if (metaslab_largest_allocatable(msp) < metaslab_df_alloc_threshold ||
	    free_pct < metaslab_df_free_pct) {
		align = size & -size;
		cursor = &msp->ms_lbas[highbit64(align) - 1];
		offset = -1;
	} else {
		offset = metaslab_block_picker(rt, cursor, size, max_size,
		    metaslab_df_max_search, found_size);
		if (max_size != size && offset == -1) {
			align = size & -size;
			cursor = &msp->ms_lbas[highbit64(align) - 1];
			offset = metaslab_block_picker(rt, cursor, size,
			    max_size, metaslab_df_max_search, found_size);
		}
	}
  1. L1905–L1906 One cursor per power-of-two alignment, ms_lbas[]. Every block in the figure is 128 KiB, so one cursor, ms_lbas[17], the black mark above the metaslab.
  2. L1917–L1921 Under 4% free, or when no free segment is as large as 128 KiB, no forward search.
  3. L1923–L1924 Otherwise metaslab_block_picker: the first free segment at or after the cursor that fits, searched at most 16 MiB past the first candidate, and always at least 100 segments; the cursor moves to the end of what was taken.

If that finds nothing, the fallback takes, from a tree of the same free segments sorted by size, a segment of exactly the size asked or the next larger one, and moves the cursor there. So space freed behind the cursor is not reused until the cursor reaches the end of the metaslab, or the metaslab runs low: in the figure, the 160 MiB file lands after B, not in A’s hole. Blocks taken one after the other are adjacent, and the range tree merges adjacent segments, so a file written in one txg is one extent, and one entry on the map.

Freeing. A free goes to ms_freeing, in syncing context. The block stays allocated until the sync is over.

Syncing: appending to the map. In metaslab_sync:

metaslab_sync Excerpt of module/zfs/metaslab.c, lines 4367–4405, OpenZFS zfs-2.4.4. View on GitHub 
	/*
	 * We'll be going to disk to sync our space accounting, thus we
	 * drop the ms_lock during that time so allocations coming from
	 * open-context (ZIL) for future TXGs do not block.
	 */
	mutex_exit(&msp->ms_lock);
	space_map_t *log_sm = spa_syncing_log_sm(spa);
	if (log_sm != NULL) {
		ASSERT(spa_feature_is_enabled(spa, SPA_FEATURE_LOG_SPACEMAP));
		if (metaslab_unflushed_txg(msp) == 0)
			metaslab_unflushed_add(msp, tx);
		else if (!metaslab_unflushed_dirty(msp))
			metaslab_unflushed_bump(msp, tx, B_TRUE);

		space_map_write(log_sm, alloctree, SM_ALLOC,
		    vd->vdev_id, tx);
		space_map_write(log_sm, msp->ms_freeing, SM_FREE,
		    vd->vdev_id, tx);
		mutex_enter(&msp->ms_lock);

		ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=,
		    metaslab_unflushed_changes_memused(msp));
		spa->spa_unflushed_stats.sus_memused -=
		    metaslab_unflushed_changes_memused(msp);
		zfs_range_tree_remove_xor_add(alloctree,
		    msp->ms_unflushed_frees, msp->ms_unflushed_allocs);
		zfs_range_tree_remove_xor_add(msp->ms_freeing,
		    msp->ms_unflushed_allocs, msp->ms_unflushed_frees);
		spa->spa_unflushed_stats.sus_memused +=
		    metaslab_unflushed_changes_memused(msp);
	} else {
		ASSERT(!spa_feature_is_enabled(spa, SPA_FEATURE_LOG_SPACEMAP));

		space_map_write(msp->ms_sm, alloctree, SM_ALLOC,
		    SM_NO_VDEVID, tx);
		space_map_write(msp->ms_sm, msp->ms_freeing, SM_FREE,
		    SM_NO_VDEVID, tx);
		mutex_enter(&msp->ms_lock);
	}
  1. L4373–L4396 With a log space map, the txg’s allocations and frees go to one pool-wide log instead, with the vdev’s id. See below; the figure takes the other branch.
  2. L4400–L4403 The txg’s allocation tree is appended as ALLOC entries, then ms_freeing as FREE entries, to the metaslab’s own map, without a vdev id. Nothing already on disk is rewritten.

Each append starts with a debug word, which records the txg and the sync pass, and an empty tree appends nothing; ALLOC adds to the map’s allocated total, smp_alloc, and FREE subtracts from it (L780–L783). A metaslab without any allocation or free in a txg is left alone. Then ms_freeing becomes ms_freed. How many words an extent takes:

space_map_write_impl Excerpt of module/zfs/space_map.c, lines 704–739, OpenZFS zfs-2.4.4. View on GitHub 
	zfs_btree_t *t = &rt->rt_root;
	zfs_btree_index_t where;
	for (zfs_range_seg_t *rs = zfs_btree_first(t, &where); rs != NULL;
	    rs = zfs_btree_next(t, &where, &where)) {
		uint64_t offset = (zfs_rs_get_start(rs, rt) - sm->sm_start) >>
		    sm->sm_shift;
		uint64_t length = (zfs_rs_get_end(rs, rt) -
		    zfs_rs_get_start(rs, rt)) >> sm->sm_shift;
		uint8_t words = 1;

		/*
		 * We only write two-word entries when both of the following
		 * are true:
		 *
		 * [1] The feature is enabled.
		 * [2] The offset or run is too big for a single-word entry,
		 *	or the vdev_id is set (meaning not equal to
		 *	SM_NO_VDEVID).
		 *
		 * Note that for purposes of testing we've added the case that
		 * we write two-word entries occasionally when the feature is
		 * enabled and zfs_force_some_double_word_sm_entries has been
		 * set.
		 */
		if (spa_feature_is_active(spa, SPA_FEATURE_SPACEMAP_V2) &&
		    (offset >= (1ULL << SM_OFFSET_BITS) ||
		    length > SM_RUN_MAX ||
		    vdev_id != SM_NO_VDEVID ||
		    (zfs_force_some_double_word_sm_entries &&
		    random_in_range(100) == 0)))
			words = 2;

		space_map_write_seg(sm, zfs_rs_get_start(rs, rt),
		    zfs_rs_get_end(rs, rt), maptype, vdev_id, words, &db,
		    FTAG, tx);
	}
  1. L708–L711 Offset and length in units of 4 KiB, from the start of the metaslab.
  2. L728–L734 Two words when the offset does not fit in 47 bits, the run is longer than SM_RUN_MAX, 215 units (128 MiB here), or a vdev id must be stored, and the spacemap_v2 feature is active. It is activated as soon as it is enabled, which a new pool does.
  3. L732–L733 A test tunable, off by default.

The words. The layout, as the header draws it:

space map entries Excerpt of include/sys/space_map.h, lines 104–140, OpenZFS zfs-2.4.4. View on GitHub 
/*
 * debug entry
 *
 *     2     2        10                     50
 *  +-----+-----+------------+----------------------------------+
 *  | 1 0 | act |  syncpass  |        txg (lower bits)          |
 *  +-----+-----+------------+----------------------------------+
 *   63 62 61 60 59        50 49                                0
 *
 *
 * one-word entry
 *
 *    1               47                   1           15
 *  +-----------------------------------------------------------+
 *  | 0 |   offset (sm_shift units)    | type |       run       |
 *  +-----------------------------------------------------------+
 *   63  62                          16   15   14               0
 *
 *
 * two-word entry
 *
 *     2     2               36                      24
 *  +-----+-----+---------------------------+-------------------+
 *  | 1 1 | pad |            run            |       vdev        |
 *  +-----+-----+---------------------------+-------------------+
 *   63 62 61 60 59                       24 23                 0
 *
 *     1                            63
 *  +------+----------------------------------------------------+
 *  | type |                      offset                        |
 *  +------+----------------------------------------------------+
 *     63   62                                                  0
 *
 * Note that a two-word entry will not straddle a block boundary.
 * If necessary, the last word of a block will be padded with a
 * debug entry (with act = syncpass = txg = 0).
 */
  1. L104–L111 A debug word: prefix 10, the action (0 ALLOC, 1 FREE), the sync pass, the txg.
  2. L114–L120 A one-word entry: top bit 0, a 47-bit offset, a type bit and a 15-bit run. The run is stored minus one, so it goes from 1 to 215.
  3. L123–L135 A two-word entry: prefix 11, a 36-bit run and a 24-bit vdev id, then the type and a 63-bit offset.
  4. L137–L139 In the figure, a pad word appears when a two-word entry would start on the last word of a 16 KiB block.

The three kinds are told apart by their top bits. The figure encodes every word with the header’s macros, BF64_ENCODE masking then shifting: A’s ALLOC entry, offset 0 and 8192 units, is 0x0000000000001FFF; the 160 MiB extent, offset 0x2400 and 40960 units, is 0xC000009FFF000000 then 0x0000000000002400. The vdev field of that first word is 0: SM_NO_VDEVID is 1 << 24, and the 24-bit mask drops it. The words are written here:

space_map_write_seg Excerpt of module/zfs/space_map.c, lines 633–663, OpenZFS zfs-2.4.4. View on GitHub 
		uint64_t run_len = MIN(size, run_max);
		switch (words) {
		case 1:
			*block_cursor = SM_OFFSET_ENCODE(start) |
			    SM_TYPE_ENCODE(maptype) |
			    SM_RUN_ENCODE(run_len);
			block_cursor++;
			break;
		case 2:
			/* write the first word of the entry */
			*block_cursor = SM_PREFIX_ENCODE(SM2_PREFIX) |
			    SM2_RUN_ENCODE(run_len) |
			    SM2_VDEV_ENCODE(vdev_id);
			block_cursor++;

			/* move on to the second word of the entry */
			ASSERT3P(block_cursor, <, block_end);
			*block_cursor = SM2_TYPE_ENCODE(maptype) |
			    SM2_OFFSET_ENCODE(start);
			block_cursor++;
			break;
		default:
			panic("%d-word space map entries are not supported",
			    words);
			break;
		}
		sm->sm_phys->smp_length += words * sizeof (uint64_t);

		start += run_len;
		size -= run_len;
	}
  1. L633 A run longer than the format allows is cut; with two-word entries that is 236 units, never reached in a metaslab.
  2. L636–L638 One word: offset, type, run.
  3. L643–L651 Two words: prefix, run and vdev; then type and offset.
  4. L659 The map grows by one or two words. It only ever grows, until it is condensed.

Before a two-word entry, the last word of a block is padded with an empty debug word, which loading skips.

Two txgs of grace. At the end of each txg’s sync:

metaslab_sync_done Excerpt of module/zfs/metaslab.c, lines 4624–4638, OpenZFS zfs-2.4.4. View on GitHub 
	/*
	 * Move the frees from the defer_tree back to the free
	 * range tree (if it's loaded). Swap the freed_tree and
	 * the defer_tree -- this is safe to do because we've
	 * just emptied out the defer_tree.
	 */
	zfs_range_tree_vacate(*defer_tree,
	    msp->ms_loaded ? zfs_range_tree_add : NULL, msp->ms_allocatable);
	if (defer_allowed) {
		zfs_range_tree_swap(&msp->ms_freed, defer_tree);
	} else {
		zfs_range_tree_vacate(msp->ms_freed,
		    msp->ms_loaded ? zfs_range_tree_add : NULL,
		    msp->ms_allocatable);
	}
  1. L4630–L4631 The frees deferred two txgs ago go back into the free tree: defer_tree is ms_defer[txg % TXG_DEFER_SIZE].
  2. L4632–L4633 This txg’s frees take their place.
  3. L4634–L4637 Not deferred only when the pool is almost full, or a vdev is being removed or expanded.

TXG_DEFER_SIZE is 2: a block freed in txg T is on the map as FREE after the sync of T, but allocatable only after the sync of T + 2. The header says why: “a safety net for uberblock rollback”; the pool can be rolled back two txgs and find none of its blocks reused. A metaslab with deferred space stays dirty until the frees are back.

Loading: replaying the log. Each entry of the map, in order:

space_map_load_callback Excerpt of module/zfs/space_map.c, lines 401–416, OpenZFS zfs-2.4.4. View on GitHub 
static int
space_map_load_callback(space_map_entry_t *sme, void *arg)
{
	space_map_load_arg_t *smla = arg;
	if (sme->sme_type == smla->smla_type) {
		VERIFY3U(zfs_range_tree_space(smla->smla_rt) + sme->sme_run, <=,
		    smla->smla_sm->sm_size);
		zfs_range_tree_add(smla->smla_rt, sme->sme_offset,
		    sme->sme_run);
	} else {
		zfs_range_tree_remove(smla->smla_rt, sme->sme_offset,
		    sme->sme_run);
	}

	return (0);
}
  1. L405–L409 Loading free space: a FREE entry is added to the tree.
  2. L410–L413 An ALLOC entry is removed from it.

The tree starts as the whole metaslab, so replaying the log from the start leaves exactly the free space. metaslab_load replays up to the length at the last sync and then removes the deferred trees, which are FREE on the map but not allocatable yet. A metaslab whose map was never written loads as free. The figure’s Load does exactly this and compares the result with the tree it had.

When to condense. At each sync, in its first pass, if the metaslab is loaded, metaslab_sync asks:

metaslab_should_condense Excerpt of module/zfs/metaslab.c, lines 3835–3861, OpenZFS zfs-2.4.4. View on GitHub 
static boolean_t
metaslab_should_condense(metaslab_t *msp)
{
	space_map_t *sm = msp->ms_sm;
	vdev_t *vd = msp->ms_group->mg_vd;
	uint64_t vdev_blocksize = 1ULL << vd->vdev_ashift;

	ASSERT(MUTEX_HELD(&msp->ms_lock));
	ASSERT(msp->ms_loaded);
	ASSERT(sm != NULL);
	ASSERT3U(spa_sync_pass(vd->vdev_spa), ==, 1);

	/*
	 * We always condense metaslabs that are empty and metaslabs for
	 * which a condense request has been made.
	 */
	if (zfs_range_tree_numsegs(msp->ms_allocatable) == 0 ||
	    msp->ms_condense_wanted)
		return (B_TRUE);

	uint64_t record_size = MAX(sm->sm_blksz, vdev_blocksize);
	uint64_t object_size = space_map_length(sm);
	uint64_t optimal_size = space_map_estimate_optimal_size(sm,
	    msp->ms_allocatable, SM_NO_VDEVID);

	return (object_size >= (optimal_size * zfs_condense_pct / 100) &&
	    object_size > zfs_metaslab_condense_block_threshold * record_size);
  1. L3851–L3853 An empty free tree, or a requested condense: always.
  2. L3855 A record is the larger of the map’s block size and a sector.
  3. L3857–L3858 The optimal size: an estimate of the free tree written alone, from its histogram of segment sizes, one word per segment under 128 MiB, two above, plus padding (space_map.c L1033–L1085).
  4. L3860–L3861 Condense when the map is at least 200% of that, and longer than 4 records. Without a log space map, a block is 16 KiB: 64 KiB. In the figure, the two tests under the tape.

In the figure, A, B and a deleted C make a map of 96 bytes against an optimal 32: twice as long, but far from 64 KiB, so no. The rewrites of a 64 MiB database, 128 random blocks per txg, append a FREE entry for almost every old block; after about 70 txgs the map passes 64 KiB, while the free tree, about two hundred segments, would take under 2 KiB.

Condensing. The map is rewritten from the tree:

metaslab_condense Excerpt of module/zfs/metaslab.c, lines 3994–4013, OpenZFS zfs-2.4.4. View on GitHub 
	/*
	 * Note:
	 * When the log space map feature is enabled, each space map will
	 * always have ALLOCS followed by FREES for each sync pass. This is
	 * typically true even when the log space map feature is disabled,
	 * except from the case where a metaslab goes through metaslab_sync()
	 * and gets condensed. In that case the metaslab's space map will have
	 * ALLOCS followed by FREES (due to condensing) followed by ALLOCS
	 * followed by FREES (due to space_map_write() in metaslab_sync()) for
	 * sync pass 1.
	 */
	zfs_range_tree_t *tmp_tree = zfs_range_tree_create_flags(
	    NULL, type, NULL, start, shift,
	    ZFS_RT_F_DYN_NAME,
	    metaslab_rt_name(msp->ms_group, msp, "tmp_tree"));
	zfs_range_tree_add(tmp_tree, msp->ms_start, msp->ms_size);
	space_map_write(sm, tmp_tree, SM_ALLOC, SM_NO_VDEVID, tx);
	space_map_write(sm, msp->ms_allocatable, SM_FREE, SM_NO_VDEVID, tx);
	space_map_write(sm, condense_tree, SM_FREE, SM_NO_VDEVID, tx);
  1. L3994–L4003 This txg’s own entries are still appended after the condensed map, as usual.
  2. L4009–L4010 One ALLOC entry for the whole metaslab: 217 units, a two-word entry.
  3. L4011 One FREE entry per free segment.
  4. L4012 Then the condense tree: the deferred frees and the allocations of the txgs in flight, which are free as far as the old map knows.

Before writing, the metaslab is marked as condensing, so nothing is allocated from it meanwhile, and the map is truncated to length 0. Replaying the short map gives the same tree as replaying the long one: the figure’s Load, after a condense, says so.

Coda: the log space map

zpool create enables every feature unless told otherwise, among them log_spacemap, and then metaslab_sync takes the other branch: each txg’s allocations and frees, for every metaslab, are appended to one log for the whole pool, as two-word entries that carry the vdev’s id, and each metaslab keeps them in memory as unflushed changes. Every txg, a selected group of metaslabs is flushed: their changes are written to their own maps, the same entries as in the figure, in blocks of 128 KiB rather than 16 KiB. The design comment names the workload it is for: random writes, which free a little everywhere and would otherwise touch many metaslabs’ maps every txg. The figure shows a metaslab’s own map, written at every sync, because that is where the idea is: the log delays the same entries and gathers them.

What the figure leaves out

The figure runs the functions above on one metaslab of one vdev, with 4 KiB sectors and no log space map. Every block is 128 KiB, so one cursor; there is one txg in flight, synced at once in one pass, without quiescing, so ms_allocating has one tree in use. Which metaslab an allocation goes to, by weight and through the rotor over vdevs, is left out: everything goes to metaslab 2, and a write that does not fit is refused instead of moving on. So are allocation throttling, gang blocks, ditto copies, checkpoints, trim and the space map’s histogram. Condensing follows metaslab_should_condense, at the sync that writes to the map, as metaslab_sync does; the rewrites stop just before such a sync, so it can be watched. Load is shown on a txg with nothing pending. The rest of the visit is in Transaction groups for when a txg syncs, and in Snapshots and clones for when a block is freed at all.