Room 7

Snapshots and clones

A snapshot has to freeze a whole filesystem at once, a terabyte as easily as a kilobyte, and must not slow the writes that follow. Taking it is the easy half. The hard half comes at every later overwrite and every delete in the live filesystem: is the old block still needed by a snapshot, or can its space be reused? Asking every snapshot would mean scanning them. A reference count on every block would mean updating counters for every block at every snapshot.

ZFS does neither. Every block pointer records the txg in which the block was born. The live filesystem remembers the txg of its latest snapshot. A block born after that snapshot cannot be in any snapshot, so it is freed; a block born at or before it may be, so it is kept, on a deadlist. One comparison of two numbers.

1 Write, snapshot, sync

fs is a filesystem of four data blocks, A to D, under one root block, the objset its ds_bp points to. Each block shows its birth txg: A₈ was born in txg 8. The figure opens after three txgs: A, B and C written in txg 8, the snapshot fs@s1 taken in txg 9, A overwritten in txg 10. Queue changes in the open txg, take a snapshot, clone one or destroy one, then sync: every block the sync lets go of shows the comparison and where it goes. Select any block to see which snapshots hold it.

`fs`

head, writableds_prev_snap_txg 9 (fs@s1)

ds_bp →R₁₀A₁₀B₈C₈D: empty

deadlist

> 0empty
> 1A₈R₈

`fs@s1`

snapshot of txg 9ds_prev_snap_txg 1 ($ORIGIN)

ds_bp →R₈A₈B₈C₈D: empty

deadlist

> 0empty

Text version of this figure

The open txg is 11. The datasets, in order:

fs, head, writable: ds_prev_snap_txg 9; ds_bp points to the R10, the root, born in txg 10; data blocks: A10, born in txg 10, B8, born in txg 8, C8, born in txg 8, D: empty. Deadlist: entry > 0: empty; entry > 1: A8, born in txg 8 and R8, the root, born in txg 8.
fs@s1, snapshot of txg 9: ds_prev_snap_txg 1; ds_bp points to the R8, the root, born in txg 8; data blocks: A8, born in txg 8, B8, born in txg 8, C8, born in txg 8, D: empty. Deadlist: entry > 0: empty.

Freed so far: R7, the root, born in txg 7 (in txg 8).

The idea, at three depths

In one sentence

Every block carries the txg of its birth, so when the live filesystem lets go of a block, one comparison with the txg of its latest snapshot decides: free it, or keep it on a deadlist for the snapshots that still hold it.

In one paragraph

A snapshot is a new dataset record that copies one block pointer, ds_bp, the root of the filesystem’s tree, and nothing else: every block below is now shared. Copy-on-write never modifies those blocks again; it writes new ones, born in later txgs, and kills the old ones. dsl_dataset_block_kill compares the old block’s birth with the filesystem’s ds_prev_snap_txg, the txg of its latest snapshot. Born later, the block belongs to the live filesystem alone and is freed. Born at or before, the latest snapshot holds it, and it goes on the deadlist. The deadlist is cut into entries by the txgs of earlier snapshots, so it says between which two snapshots each dead block was born. That makes destroying a snapshot cheap: the blocks only it held are whole entries of the next dataset’s deadlist, freed without reading one block pointer. A clone is a writable dataset that starts from a snapshot’s ds_bp, with that snapshot’s txg as its own ds_prev_snap_txg: the same comparison keeps the blocks it shares with its origin and frees its own.

In detail

Birth. A block’s birth txg is set when it is allocated: metaslab_alloc ends with BP_SET_BIRTH(bp, txg, 0), and the write passes it the txg it belongs to. A block pointer has two birth words, logical and physical; they differ only for dedup, block cloning and rewritten blocks, and the value compared below is BP_GET_BIRTH, the logical birth for an ordinary block.

Free now, or deadlist. Here is the whole decision.

dsl_dataset_block_kill Excerpt of module/zfs/dsl_dataset.c, lines 294–316, OpenZFS zfs-2.4.4. View on GitHub

	if (BP_GET_BIRTH(bp) > dsl_dataset_phys(ds)->ds_prev_snap_txg) {
		int64_t delta;

		/*
		 * Put blocks that would create IO on the pool's deadlist for
		 * dsl_process_async_destroys() to find. This is to prevent
		 * zio_free() from creating a ZIO_TYPE_FREE IO for them, which
		 * are very heavy and can lead to out-of-memory conditions if
		 * something tries to free millions of blocks on the same txg.
		 */
		boolean_t defer = spa_version(spa) >= SPA_VERSION_DEADLISTS &&
		    (BP_IS_GANG(bp) || BP_GET_DEDUP(bp) ||
		    brt_maybe_exists(spa, bp));

		if (defer) {
			dprintf_bp(bp, "putting on free list: %s", "");
			bpobj_enqueue(&ds->ds_dir->dd_pool->dp_free_bpobj,
			    bp, B_FALSE, tx);
		} else {
			dprintf_bp(bp, "freeing ds=%llu",
			    (u_longlong_t)ds->ds_object);
			dsl_free(tx->tx_pool, tx->tx_txg, bp);
		}

L294 The comparison. ds_prev_snap_txg is the txg of the dataset’s latest snapshot. The test is strict: a block born in that very txg is held by that snapshot.
L304–L311 Gang, dedup and possibly cloned blocks are queued on the pool’s free list instead of being freed inline, because freeing them costs I/O. The outcome is the same: no snapshot holds them.
L312–L315 The ordinary case: dsl_free, in this txg. The figure greys the block out under “Freed”.

Otherwise, in the else branch, the block goes onto the deadlist. Three callers kill blocks, all while a txg syncs: dbuf_write_done when a data or indirect block was rewritten, dmu_objset_write_done for the objset block that ds_bp points to, rewritten in every txg in which the dataset changes, and free_blocks for a delete or a truncation. The figure draws that objset and the indirect blocks as one root, killed by the same rule. The two write callbacks park a deadlist-bound block on a pending list that dsl_dataset_sync_done empties before the txg’s sync tasks: same outcome, a few lines later.

A snapshot copies one block pointer.

dsl_dataset_snapshot_sync_impl Excerpt of module/zfs/dsl_dataset.c, lines 1760–1785, OpenZFS zfs-2.4.4. View on GitHub

	dsobj = dmu_object_alloc(mos, DMU_OT_DSL_DATASET, 0,
	    DMU_OT_DSL_DATASET, sizeof (dsl_dataset_phys_t), tx);
	VERIFY0(dmu_bonus_hold(mos, dsobj, FTAG, &dbuf));
	dmu_buf_will_dirty(dbuf, tx);
	dsphys = dbuf->db_data;
	memset(dsphys, 0, sizeof (dsl_dataset_phys_t));
	dsphys->ds_dir_obj = ds->ds_dir->dd_object;
	dsphys->ds_fsid_guid = unique_create();
	(void) random_get_pseudo_bytes((void*)&dsphys->ds_guid,
	    sizeof (dsphys->ds_guid));
	dsphys->ds_prev_snap_obj = dsl_dataset_phys(ds)->ds_prev_snap_obj;
	dsphys->ds_prev_snap_txg = dsl_dataset_phys(ds)->ds_prev_snap_txg;
	dsphys->ds_next_snap_obj = ds->ds_object;
	dsphys->ds_num_children = 1;
	dsphys->ds_creation_time = gethrestime_sec();
	dsphys->ds_creation_txg = crtxg;
	dsphys->ds_deadlist_obj = dsl_dataset_phys(ds)->ds_deadlist_obj;
	dsphys->ds_referenced_bytes = dsl_dataset_phys(ds)->ds_referenced_bytes;
	dsphys->ds_compressed_bytes = dsl_dataset_phys(ds)->ds_compressed_bytes;
	dsphys->ds_uncompressed_bytes =
	    dsl_dataset_phys(ds)->ds_uncompressed_bytes;
	dsphys->ds_flags = dsl_dataset_phys(ds)->ds_flags;
	rrw_enter(&ds->ds_bp_rwlock, RW_READER, FTAG);
	dsphys->ds_bp = dsl_dataset_phys(ds)->ds_bp;
	rrw_exit(&ds->ds_bp_rwlock, FTAG);
	dmu_buf_rele(dbuf, FTAG);

L1760–L1761 One new object in the MOS, the pool’s own metadata: the snapshot’s dataset record.
L1770–L1773 It takes the head’s link to the previous snapshot and its ds_prev_snap_txg, points forward to the head, and starts with one child, its successor.
L1775 Its creation txg is the txg being synced.
L1776 The head’s deadlist becomes the snapshot’s, as it is.
L1783 The root block pointer is copied. That one copy is what makes the snapshot share every block with the head. Nothing in the tree is read or written: the figure shows no new block for a snapshot.

The head’s new deadlist. Further down the same function, the head gets a deadlist of its own.

dsl_dataset_snapshot_sync_impl Excerpt of module/zfs/dsl_dataset.c, lines 1830–1839, OpenZFS zfs-2.4.4. View on GitHub

	dmu_buf_will_dirty(ds->ds_dbuf, tx);
	dsl_dataset_phys(ds)->ds_deadlist_obj =
	    dsl_deadlist_clone(&ds->ds_deadlist, UINT64_MAX,
	    dsl_dataset_phys(ds)->ds_prev_snap_obj, tx);
	dsl_deadlist_close(&ds->ds_deadlist);
	VERIFY0(dsl_deadlist_open(&ds->ds_deadlist, mos,
	    dsl_dataset_phys(ds)->ds_deadlist_obj));
	dsl_deadlist_add_key(&ds->ds_deadlist,
	    dsl_dataset_phys(ds)->ds_prev_snap_txg, tx);
	dsl_bookmark_snapshotted(ds, tx);

L1831–L1833 dsl_deadlist_clone with no limit: one empty entry for every key of the deadlist the snapshot just took.
L1837–L1838 Plus one key: the head’s ds_prev_snap_txg, which here is still the txg of the previous snapshot. It is set to this snapshot’s txg only afterwards.

So after snapshots in txgs t1 < t2 < … < tn, the head’s deadlist has its starting keys plus t1 to t(n−1), and its ds_prev_snap_txg is tn. Each snapshot keeps the deadlist the head had until it was taken: the blocks killed between the previous snapshot and this one. That is, blocks the previous snapshot holds and this one does not; a snapshot’s deadlist is not “the blocks only it owns”.

Where a dead block goes.

dsl_deadlist_insert Excerpt of module/zfs/dsl_deadlist.c, lines 487–501, OpenZFS zfs-2.4.4. View on GitHub

	dle_tofind.dle_mintxg = BP_GET_BIRTH(bp);
	dle = avl_find(&dl->dl_tree, &dle_tofind, &where);
	if (dle == NULL)
		dle = avl_nearest(&dl->dl_tree, where, AVL_BEFORE);
	else
		dle = AVL_PREV(&dl->dl_tree, dle);

	if (dle == NULL) {
		zfs_panic_recover("blkptr at %p has invalid BLK_BIRTH %llu",
		    bp, (longlong_t)BP_GET_BIRTH(bp));
		dle = avl_first(&dl->dl_tree);
	}

	ASSERT3P(dle, !=, NULL);
	dle_enqueue(dl, dle, bp, bp_freed, tx);

L487–L492 A deadlist is a tree of entries, each a list of block pointers stored under a key, a txg that “is not inclusive”. Look the birth up: on an exact match take the entry before it, otherwise the nearest entry before. Either way, the entry with the largest key strictly below the birth.
L494–L498 A birth at or below every key cannot happen on a sound pool: it is reported, and the block goes to the first entry.

Where the keys start. A filesystem is made from the pool’s $ORIGIN snapshot, created from an empty dataset with creation txg 1. Traced through the excerpts, a new filesystem starts with ds_prev_snap_txg 1 and a deadlist with one key, 0, and its first snapshot adds key 1. Every block a user writes is born after txg 1: entry 0 stays empty, entry 1 collects what was born before the first snapshot. These are the > 0 and > 1 entries of the figure.

The same txg. A snapshot is a sync task, and the txg writes its data first.

dsl_pool_sync Excerpt of module/zfs/dsl_pool.c, lines 747–760, OpenZFS zfs-2.4.4. View on GitHub

	/*
	 * Sync the datasets again to push out the changes due to
	 * userspace updates.  This must be done before we process the
	 * sync tasks, so that any snapshots will have the correct
	 * user accounting information (and we won't get confused
	 * about which blocks are part of the snapshot).
	 */
	rio = zio_root(dp->dp_spa, NULL, NULL, ZIO_FLAG_MUSTSUCCEED);
	while ((ds = txg_list_remove(&dp->dp_dirty_datasets, txg)) != NULL) {
		objset_t *os = ds->ds_objset;

		ASSERT(list_link_active(&ds->ds_synced_link));
		dmu_buf_rele(ds->ds_dbuf, ds);
		dsl_dataset_sync(ds, rio, tx);

L747–L753 Every dirty dataset is written out before the sync tasks run, “so that … we won’t get confused about which blocks are part of the snapshot”. The tasks run at the end.

Two consequences, both in the figure. A block written in the same txg as a snapshot is in that snapshot: born in txg T, held by the snapshot of txg T, which is why the test is strict. And a block killed in the txg of a snapshot is not in it: the kill was decided against the previous snapshot. One snapshot of a dataset per txg: a second one is refused, EAGAIN.

A clone starts from a snapshot’s block pointer.

dsl_dataset_create_sync_dd Excerpt of module/zfs/dsl_dataset.c, lines 1213–1227, OpenZFS zfs-2.4.4. View on GitHub

	} else {
		dsl_dataset_t *ohds; /* head of the origin snapshot */

		dsphys->ds_prev_snap_obj = origin->ds_object;
		dsphys->ds_prev_snap_txg =
		    dsl_dataset_phys(origin)->ds_creation_txg;
		dsphys->ds_referenced_bytes =
		    dsl_dataset_phys(origin)->ds_referenced_bytes;
		dsphys->ds_compressed_bytes =
		    dsl_dataset_phys(origin)->ds_compressed_bytes;
		dsphys->ds_uncompressed_bytes =
		    dsl_dataset_phys(origin)->ds_uncompressed_bytes;
		rrw_enter(&origin->ds_bp_rwlock, RW_READER, FTAG);
		dsphys->ds_bp = dsl_dataset_phys(origin)->ds_bp;
		rrw_exit(&origin->ds_bp_rwlock, FTAG);

L1216–L1218 The clone’s previous snapshot is its origin, and its ds_prev_snap_txg the origin’s creation txg.
L1225–L1227 Its ds_bp is the origin’s: like a snapshot, a clone starts as one copied block pointer.

Then the origin gains a child, the clone’s deadlist starts with the keys below the origin’s txg, and the origin is recorded in the clone’s directory (in memory, dd_origin_txg). A write in the clone goes through the same dsl_dataset_block_kill, against the clone’s own ds_prev_snap_txg: a block the clone wrote is born after the origin and freed when the clone lets go of it; a block born at or before the origin is shared with it and goes on the clone’s deadlist. The clone diverges by birth txg, and nothing is copied.

Destroying a snapshot.

dsl_destroy_snapshot_sync_impl Excerpt of module/zfs/dsl_destroy.c, lines 387–424, OpenZFS zfs-2.4.4. View on GitHub

	dmu_buf_will_dirty(ds_next->ds_dbuf, tx);
	dsl_dataset_phys(ds_next)->ds_prev_snap_obj =
	    dsl_dataset_phys(ds)->ds_prev_snap_obj;
	dsl_dataset_phys(ds_next)->ds_prev_snap_txg =
	    dsl_dataset_phys(ds)->ds_prev_snap_txg;
	ASSERT3U(dsl_dataset_phys(ds)->ds_prev_snap_txg, ==,
	    ds_prev ? dsl_dataset_phys(ds_prev)->ds_creation_txg : 0);

	if (ds_next->ds_deadlist.dl_oldfmt) {
		process_old_deadlist(ds, ds_prev, ds_next,
		    after_branch_point, tx);
	} else {
		/* Adjust prev's unique space. */
		if (ds_prev && !after_branch_point) {
			dsl_deadlist_space_range(&ds_next->ds_deadlist,
			    dsl_dataset_phys(ds_prev)->ds_prev_snap_txg,
			    dsl_dataset_phys(ds)->ds_prev_snap_txg,
			    &used, &comp, &uncomp);
			dsl_dataset_phys(ds_prev)->ds_unique_bytes += used;
		}

		/* Adjust snapused. */
		dsl_deadlist_space_range(&ds_next->ds_deadlist,
		    dsl_dataset_phys(ds)->ds_prev_snap_txg, UINT64_MAX,
		    &used, &comp, &uncomp);
		dsl_dir_diduse_space(ds->ds_dir, DD_USED_SNAP,
		    -used, -comp, -uncomp, tx);

		/* Move blocks to be freed to pool's free list. */
		dsl_deadlist_move_bpobj(&ds_next->ds_deadlist,
		    &dp->dp_free_bpobj, dsl_dataset_phys(ds)->ds_prev_snap_txg,
		    tx);
		dsl_dir_diduse_space(tx->tx_pool->dp_free_dir,
		    DD_USED_HEAD, used, comp, uncomp, tx);

		/* Merge our deadlist into next's and free it. */
		dsl_deadlist_merge(&ds_next->ds_deadlist,
		    dsl_dataset_phys(ds)->ds_deadlist_obj, tx);

L387–L391 The next dataset, the next snapshot or the head, inherits the destroyed snapshot’s previous snapshot and ds_prev_snap_txg.
L395–L397 Pools that predate keyed deadlists apply the same test to each block. The figure follows the keyed path.
L399–L413 Space accounting, not drawn.
L415–L418 Every entry of the next deadlist at or above the snapshot’s ds_prev_snap_txg goes to the pool’s free list. Those blocks were born after the snapshot before it and killed before the next one: only this snapshot held them. The keys alone say so. The sync thread frees that list in later txgs; the figure frees them at once.
L422–L424 The snapshot’s own deadlist, blocks the snapshot before it still holds, joins the next one, entry by entry, and is then freed.

Last, the key of the snapshot’s txg is removed, its entry merged into the one before: from the head when the next dataset is a snapshot, and, through dsl_dir_remove_clones_key, from every clone whose origin is younger than the snapshot. A snapshot with a clone has more than one child and cannot be destroyed, EEXIST: “Can’t delete a branch point”.

Which snapshot owns this block. Nothing in ZFS stores that answer: it follows from birth txgs. A block of fs born in txg B and killed in txg K is held by the snapshots of fs taken from txg B to txg K − 1: those taken before B were frozen before it existed, those taken in K or later after it was gone. A block still live is held by every snapshot taken since B. The figure computes that range from the numbers, and its tests check it against which dataset’s tree actually holds the block, over thousands of random sequences.

What the figure leaves out

The figure runs the functions above over one filesystem with four data blocks and up to four snapshots, and one clone that cannot itself be snapshotted or destroyed. The objset, dnodes and indirect blocks are one root block. Deferred frees of gang, dedup and cloned blocks, space accounting, and the clone’s livelist are left out; none changes whether a block is freed or kept. Blocks on the pool’s free list are drawn as freed at once. Holds, deferred destroy and old-format deadlists are not shown. Bookmarks (dsl_bookmark.c) and zfs promote, which swaps a clone and its origin’s filesystem, are other rooms’ business.