Uberblok

Room 11

send / receive

Keeping a copy of a filesystem on another machine looks simple: compare the two sides and copy what differs. But comparing means reading. To find the few blocks that changed since yesterday, a file-by-file tool reads or at least lists every file on both sides, every time, and it can only see a change through the contents it compares or the dates and sizes it trusts.

ZFS does not compare. Every block pointer records the txg in which its block was born, and a snapshot taken in txg F holds no block born after F. So the difference between two snapshots is the blocks of the newer one born after the older one’s txg. Copy-on-write rewrites every block above a changed one, so a subtree with an old root has not changed below: one comparison at its top skips it whole, unread. What the traversal finds becomes a stream of records, each but the first carrying a checksum of everything before it, which the receiving side checks record by record, before applying each one.

1 Send @s4, from the snapshot you choose

tank/fs has four snapshots, one per txg of its history. The figure sends the last one, @s4: its tree, every block pointer with its logical birth txg. Choose the from-snapshot the receiver already holds, or none for a full stream, then play the send step by step: at each block pointer the birth is compared with F, the from-snapshot’s txg, records drop into the stream with their checksums, and the receiver checks and applies them until its files are those of @s4. “Flip a bit” damages the stream on the way.

History of tank/fs
  1. txg 10 creates files a, b and c (objects 1 to 3), four 512-byte blocks each; snapshot @s1
  2. txg 20 rewrites block 2 of a; snapshot @s2
  3. txg 30 punches a hole in blocks 1 and 2 of b, creates d (object 4); snapshot @s3
  4. txg 40 deletes c; snapshot @s4

Sending side: the tree of @s4

12 block pointers visited3 skipped4 below them, never read15 records6,728 bytes

  • objset40> 20
    • meta-dnode L140> 20
      • dnode block 040> 200meta-dnode1a2b3free
        • a: L120≤ 20a010a110a2′20a310
        • b: L130> 20b010≤ 20hole30> 20hole30> 20b310≤ 20
      • dnode block 130> 204d5free6free7free
        • d: L130> 20d030> 20d130> 20d230> 20d330> 20

The stream

  1. 0BEGIN@s2 → @s4no checksum
  2. 1OBJECTobject 1, a50788f0f
  3. 2FREEa 2,048–end43af0187
  4. 3OBJECTobject 2, babe05a34
  5. 4FREEb 2,048–ende8b7bb43
  6. 5FREEb 512–1,5368c224c03
  7. 6FREEOBJECTSobject 3356ecbe7
  8. 7OBJECTobject 4, d21559e25
  9. 8FREEd 2,048–end7331f09e
  10. 9WRITEd @0 “d0”753d4dba
  11. 10WRITEd @512 “d1”c439bd12
  12. 11WRITEd @1,024 “d2”a695a488
  13. 12WRITEd @1,536 “d3”cc0bcf92
  14. 13FREEOBJECTSobjects 5–7d3567f4c
  15. 14ENDchecksum 58c87268b31db7bb

Receiving side

The receiver holds @s2 (txg 20).

  • aobject 1a0a1a2′a3
  • bobject 2b0holeholeb3
  • dobject 4d0d1d2d3

END checked (58c87268). The received files are those of @s4.

Sending @s4: the block pointers visited shrink as F grows
FromFVisitedSkipped + belowRecordsBytes
none (full)019 / 190 + 02111,672
@s11014 / 195 + 0167,552
@s22012 / 193 + 4156,728
@s3303 / 193 + 1372,184
Text version of this figure

Incremental stream from @s2 to @s4 (F = 20): 12 block pointers visited out of 19, 15 records, 6,728 bytes.

The traversal

  1. objset, born in txg 40: 40 ≤ 20 is false, visited. send_cb makes no record; the block is read to reach what is below it.
  2. meta-dnode L1, born in txg 40: 40 ≤ 20 is false, visited. send_cb makes no record; the block is read to reach what is below it.
  3. dnode block 0, born in txg 40: 40 ≤ 20 is false, visited. send_cb makes an OBJECT_RANGE, written only in a raw stream.
  4. Dnode 0, the meta-dnode’s number: send_cb makes nothing.
  5. Dnode 1, file a: send_cb makes OBJECT; dump_dnode writes it, then a FREE from the end of the file. Written: OBJECT 1 (a), FREE a from 2,048 to the end.
  6. a: L1, born in txg 20: 20 ≤ 20, skipped. Never read, nor what is below it (4 block pointers).
  7. Dnode 2, file b: send_cb makes OBJECT; dump_dnode writes it, then a FREE from the end of the file. Written: OBJECT 2 (b), FREE b from 2,048 to the end.
  8. b: L1, born in txg 30: 30 ≤ 20 is false, visited. send_cb makes no record; the block is read to reach what is below it.
  9. b, block 0, born in txg 10: 10 ≤ 20, skipped. Never read.
  10. b, block 1 (hole), born in txg 30: 30 ≤ 20 is false, visited. send_cb makes HOLE: a FREE of its range. Kept pending: dump_free and dump_freeobjects merge what follows into it.
  11. b, block 2 (hole), born in txg 30: 30 ≤ 20 is false, visited. send_cb makes HOLE: a FREE of its range. Kept pending: dump_free and dump_freeobjects merge what follows into it.
  12. b, block 3, born in txg 10: 10 ≤ 20, skipped. Never read.
  13. Dnode 3, free: send_cb makes OBJECT; dump_dnode turns an empty dnode into FREEOBJECTS. Written: FREE b from 512, 1,024 bytes.
  14. dnode block 1, born in txg 30: 30 ≤ 20 is false, visited. send_cb makes an OBJECT_RANGE, written only in a raw stream.
  15. Dnode 4, file d: send_cb makes OBJECT; dump_dnode writes it, then a FREE from the end of the file. Written: FREEOBJECTS 3, OBJECT 4 (d), FREE d from 2,048 to the end.
  16. d: L1, born in txg 30: 30 ≤ 20 is false, visited. send_cb makes no record; the block is read to reach what is below it.
  17. d, block 0, born in txg 30: 30 ≤ 20 is false, visited. send_cb makes DATA: a WRITE with the block’s 512 bytes. Written: WRITE d at 0 (d0).
  18. d, block 1, born in txg 30: 30 ≤ 20 is false, visited. send_cb makes DATA: a WRITE with the block’s 512 bytes. Written: WRITE d at 512 (d1).
  19. d, block 2, born in txg 30: 30 ≤ 20 is false, visited. send_cb makes DATA: a WRITE with the block’s 512 bytes. Written: WRITE d at 1,024 (d2).
  20. d, block 3, born in txg 30: 30 ≤ 20 is false, visited. send_cb makes DATA: a WRITE with the block’s 512 bytes. Written: WRITE d at 1,536 (d3).
  21. Dnode 5, free: send_cb makes OBJECT; dump_dnode turns an empty dnode into FREEOBJECTS. Kept pending: dump_free and dump_freeobjects merge what follows into it.
  22. Dnode 6, free: send_cb makes OBJECT; dump_dnode turns an empty dnode into FREEOBJECTS. Kept pending: dump_free and dump_freeobjects merge what follows into it.
  23. Dnode 7, free: send_cb makes OBJECT; dump_dnode turns an empty dnode into FREEOBJECTS. Kept pending: dump_free and dump_freeobjects merge what follows into it.

The records

  1. BEGIN
  2. OBJECT 1 (a), drr_checksum 50788f0f
  3. FREE a from 2,048 to the end, drr_checksum 43af0187
  4. OBJECT 2 (b), drr_checksum abe05a34
  5. FREE b from 2,048 to the end, drr_checksum e8b7bb43
  6. FREE b from 512, 1,024 bytes, drr_checksum 8c224c03
  7. FREEOBJECTS 3, drr_checksum 356ecbe7
  8. OBJECT 4 (d), drr_checksum 21559e25
  9. FREE d from 2,048 to the end, drr_checksum 7331f09e
  10. WRITE d at 0 (d0), drr_checksum 753d4dba
  11. WRITE d at 512 (d1), drr_checksum c439bd12
  12. WRITE d at 1,024 (d2), drr_checksum a695a488
  13. WRITE d at 1,536 (d3), drr_checksum cc0bcf92
  14. FREEOBJECTS 5 to 7, drr_checksum d3567f4c
  15. END, drr_checksum b31db7bb

END checked (58c87268). The received files are those of @s4.

The idea, at three depths

In one sentence

An incremental send walks the newer snapshot’s tree and skips every block pointer born at or before the older snapshot’s txg, with everything below it, and writes what is left as a stream of records whose running checksum the receiver verifies before replaying them.

In one paragraph

zfs send -i @from @to traverses the tree of @to with a lower bound, F, the txg in which @from was created. A block pointer born at or before F was already in @from, and so was the whole subtree under it, since copy-on-write gives a new birth to every block above a change: the traversal returns without reading it. Everything it does visit becomes records: an OBJECT for each dnode it meets, a WRITE for each data block, a FREE for each hole, FREEOBJECTS for each empty dnode slot. The stream starts with BEGIN, which names both snapshots by GUID, and ends with END. Every record but BEGIN carries the fletcher-4 checksum of every byte of the stream up to that checksum; the receiver keeps the same sum and refuses the stream at the first header that disagrees, before applying the record it follows. With no from-snapshot, F is 0, every block is visited, and the stream rebuilds the whole filesystem.

In detail

A stream of records. A send stream is a sequence of dmu_replay_record_t, each a 312-byte header with one of eleven types, sometimes followed by a payload: the data of a WRITE follows its header. BEGIN carries the magic number 0x2F5bacbacULL, the GUID of the snapshot sent and of the one it starts from.

The bound. The traversal that feeds a send starts here.

send_traverse_thread Excerpt of module/zfs/dmu_send.c, lines 1203–1221, OpenZFS zfs-2.4.4. View on GitHub 
static __attribute__((noreturn)) void
send_traverse_thread(void *arg)
{
	struct send_thread_arg *st_arg = arg;
	int err = 0;
	struct send_range *data;
	fstrans_cookie_t cookie = spl_fstrans_mark();

	err = traverse_dataset_resume(st_arg->os->os_dsl_dataset,
	    st_arg->fromtxg, &st_arg->resume,
	    st_arg->flags | TRAVERSE_LOGICAL, send_cb, st_arg);

	if (err != EINTR)
		st_arg->error_code = err;
	data = range_alloc(DATA, 0, 0, 0, B_TRUE);
	bqueue_enqueue_flush(&st_arg->q, data, sizeof (*data));
	spl_fstrans_unmark(cookie);
	thread_exit();
}
  1. L1211–L1213 The dataset is traversed from fromtxg, the from-snapshot’s creation txg, 0 for a full stream. TRAVERSE_LOGICAL joins the flags of the send, among them TRAVERSE_PRE: a block’s callback runs before its children.
  2. L1217–L1218 An end-of-stream marker follows the last range. The ranges send_cb queues reach the main thread through more queues, in order, and become records there.

The test that skips a subtree. Every block pointer of the snapshot goes through this.

traverse_visitbp Excerpt of module/zfs/dmu_traverse.c, lines 249–279, OpenZFS zfs-2.4.4. View on GitHub 
	if (BP_GET_LOGICAL_BIRTH(bp) == 0) {
		/*
		 * Since this block has a birth time of 0 it must be one of
		 * two things: a hole created before the
		 * SPA_FEATURE_HOLE_BIRTH feature was enabled, or a hole
		 * which has always been a hole in an object.
		 *
		 * If a file is written sparsely, then the unwritten parts of
		 * the file were "always holes" -- that is, they have been
		 * holes since this object was allocated.  However, we (and
		 * our callers) can not necessarily tell when an object was
		 * allocated.  Therefore, if it's possible that this object
		 * was freed and then its object number reused, we need to
		 * visit all the holes with birth==0.
		 *
		 * If it isn't possible that the object number was reused,
		 * then if SPA_FEATURE_HOLE_BIRTH was enabled before we wrote
		 * all the blocks we will visit as part of this traversal,
		 * then this hole must have always existed, so we can skip
		 * it.  We visit blocks born after (exclusive) td_min_txg.
		 *
		 * Note that the meta-dnode cannot be reallocated.
		 */
		if (!send_holes_without_birth_time &&
		    (!td->td_realloc_possible ||
		    zb->zb_object == DMU_META_DNODE_OBJECT) &&
		    td->td_hole_birth_enabled_txg <= td->td_min_txg)
			return (0);
	} else if (get_birth_time(td, bp) <= td->td_min_txg) {
		return (0);
	}
  1. L249–L276 A hole of birth 0 was never written, or was made before the hole_birth feature. These lines would skip it in some cases, but only when send_holes_without_birth_time is 0, and it is 1 by default: such holes are visited. The figure has none; a hole punched in b carries the txg of the free, and goes through the test below.
  2. L277–L278 The rule. td_min_txg is the bound, F. Born at or before it, the block is in the from-snapshot: the function returns before reading it or calling the callback, so nothing below it is reached. In the figure the chip turns dashed and its subtree fades.

Logical birth. get_birth_time returns the logical birth when TRAVERSE_LOGICAL is set, as it is for a send. A block pointer has two births, and the comment that defines them says the physical one can be smaller than the logical one for dedup and block cloning, and bigger for remapped and rewritten blocks, and that the logical one is the one for incremental replication. Send compares the logical one, the txg in which the user changed the data: a block deduplicated or cloned onto an older copy is still sent, since the user wrote it after F, and a block that was only rewritten or remapped on disk is not resent.

Every dnode of a dnode block. When a dnode block is visited, each of its dnodes is handed to this.

traverse_dnode Excerpt of module/zfs/dmu_traverse.c, lines 534–550, OpenZFS zfs-2.4.4. View on GitHub 
	if (td->td_flags & TRAVERSE_PRE) {
		SET_BOOKMARK(&czb, objset, object, ZB_DNODE_LEVEL,
		    ZB_DNODE_BLKID);
		err = td->td_func(td->td_spa, NULL, bp, &czb, dnp,
		    td->td_arg);
		if (err == TRAVERSE_VISIT_NO_CHILDREN)
			return (0);
		if (err != 0)
			return (err);
	}

	for (j = 0; j < dnp->dn_nblkptr; j++) {
		SET_BOOKMARK(&czb, objset, object, dnp->dn_nlevels - 1, j);
		err = traverse_visitbp(td, dnp, &dnp->dn_blkptr[j], &czb);
		if (err != 0)
			break;
	}
  1. L534–L543 The callback runs for the dnode itself. No birth is tested here: every dnode of a visited dnode block reaches send_cb, changed or not.
  2. L545–L550 Then each of the dnode’s block pointers goes through traverse_visitbp, and its test.

That is why, sending @s4 from @s3, the stream holds OBJECT records for a and b, whose data did not change: deleting c rewrote the dnode block they share with it. Their data blocks are still skipped, one level down.

From visited blocks to records. The callback decides what each visit produces.

send_cb Excerpt of module/zfs/dmu_send.c, lines 1098–1120, OpenZFS zfs-2.4.4. View on GitHub 
	if (zb->zb_level == ZB_DNODE_LEVEL) {
		if (zb->zb_object == DMU_META_DNODE_OBJECT)
			return (0);
		record = range_alloc(OBJECT, zb->zb_object, 0, 0, B_FALSE);
		record->sru.object.bp = *bp;
		size_t size  = sizeof (*dnp) * (dnp->dn_extra_slots + 1);
		record->sru.object.dnp = kmem_alloc(size, KM_SLEEP);
		memcpy(record->sru.object.dnp, dnp, size);
		bqueue_enqueue(&sta->q, record, sizeof (*record));
		return (0);
	}
	if (zb->zb_level == 0 && zb->zb_object == DMU_META_DNODE_OBJECT &&
	    !BP_IS_HOLE(bp)) {
		record = range_alloc(OBJECT_RANGE, 0, zb->zb_blkid,
		    zb->zb_blkid + 1, B_FALSE);
		record->sru.object_range.bp = *bp;
		bqueue_enqueue(&sta->q, record, sizeof (*record));
		return (0);
	}
	if (zb->zb_level < 0 || (zb->zb_level > 0 && !BP_IS_HOLE(bp)))
		return (0);
	if (zb->zb_object == DMU_META_DNODE_OBJECT && !BP_IS_HOLE(bp))
		return (0);
  1. L1098–L1108 A dnode becomes an OBJECT range, except the meta-dnode, object 0.
  2. L1109–L1116 A dnode block becomes an OBJECT_RANGE, which only a raw stream writes.
  3. L1117–L1120 The objset block and every indirect block that is not a hole make no record: they are read only to reach what is below them.
send_cb Excerpt of module/zfs/dmu_send.c, lines 1130–1146, OpenZFS zfs-2.4.4. View on GitHub 
	if (!overflow_multiply(span, zb->zb_blkid, &start) || (!(zb->zb_blkid ==
	    DMU_SPILL_BLKID || DMU_OT_IS_METADATA(dnp->dn_type)) &&
	    span * zb->zb_blkid > dnp->dn_maxblkid)) {
		ASSERT(BP_IS_HOLE(bp));
		return (0);
	}

	if (zb->zb_blkid == DMU_SPILL_BLKID)
		ASSERT3U(BP_GET_TYPE(bp), ==, DMU_OT_SA);

	enum type record_type = DATA;
	if (BP_IS_HOLE(bp))
		record_type = HOLE;
	else if (BP_IS_REDACTED(bp))
		record_type = REDACT;
	else
		record_type = DATA;
  1. L1130–L1135 Nothing past the end of the object.
  2. L1140–L1146 What is left is a data block (a WRITE) or a hole (a FREE of its range; a hole among the dnode blocks frees objects). REDACT belongs to redacted sends.

An OBJECT range goes to dump_dnode. A dnode slot with no object in it becomes FREEOBJECTS; a file becomes OBJECT, with its bonus buffer as payload, followed at once by a FREE from the file’s end to DMU_OBJECT_END, so that a receiver whose copy was longer cuts it. dump_free keeps a FREE pending and merges the next one into it when it continues it, which is why the two holes of b travel as one FREE; a FREE to the end is written at once, and any other record writes the pending one first. FREEOBJECTS are merged the same way, and objects past the last dnode block are dropped. A full stream carries frees too, so that it can be received as a clone.

The checksum that runs through the stream.

dump_record Excerpt of module/zfs/dmu_send.c, lines 257–283, OpenZFS zfs-2.4.4. View on GitHub 
/*
 * For all record types except BEGIN, fill in the checksum (overlaid in
 * drr_u.drr_checksum.drr_checksum).  The checksum verifies everything
 * up to the start of the checksum itself.
 */
static int
dump_record(dmu_send_cookie_t *dscp, void *payload, int payload_len)
{
	dmu_send_outparams_t *dso = dscp->dsc_dso;
	ASSERT3U(offsetof(dmu_replay_record_t, drr_u.drr_checksum.drr_checksum),
	    ==, sizeof (dmu_replay_record_t) - sizeof (zio_cksum_t));
	(void) fletcher_4_incremental_native(dscp->dsc_drr,
	    offsetof(dmu_replay_record_t, drr_u.drr_checksum.drr_checksum),
	    &dscp->dsc_zc);
	if (dscp->dsc_drr->drr_type == DRR_BEGIN) {
		dscp->dsc_sent_begin = B_TRUE;
	} else {
		ASSERT(ZIO_CHECKSUM_IS_ZERO(&dscp->dsc_drr->drr_u.
		    drr_checksum.drr_checksum));
		dscp->dsc_drr->drr_u.drr_checksum.drr_checksum = dscp->dsc_zc;
	}
	if (dscp->dsc_drr->drr_type == DRR_END) {
		dscp->dsc_sent_end = B_TRUE;
	}
	(void) fletcher_4_incremental_native(&dscp->dsc_drr->
	    drr_u.drr_checksum.drr_checksum,
	    sizeof (zio_cksum_t), &dscp->dsc_zc);
  1. L268–L270 The running fletcher-4 sum is carried on over the record, up to its last 32 bytes.
  2. L271–L277 Except for BEGIN, that value goes into those 32 bytes, drr_checksum, overlaid on every record type.
  3. L281–L283 Then the 32 bytes are summed, and the payload after them. So each record’s drr_checksum is the fletcher-4 of every byte of the stream before it, its own header up to the checksum included. The figure shows the low 32 bits of its last word.

END carries one more: drr_end.drr_checksum, the checksum of everything before it.

The receiving side checks before it applies.

receive_read_payload_and_next_header Excerpt of module/zfs/dmu_recv.c, lines 2843–2868, OpenZFS zfs-2.4.4. View on GitHub 
	/*
	 * Note: checksum is of everything up to but not including the
	 * checksum itself.
	 */
	ASSERT3U(offsetof(dmu_replay_record_t, drr_u.drr_checksum.drr_checksum),
	    ==, sizeof (dmu_replay_record_t) - sizeof (zio_cksum_t));
	receive_cksum(drc,
	    offsetof(dmu_replay_record_t, drr_u.drr_checksum.drr_checksum),
	    &drc->drc_next_rrd->header);

	zio_cksum_t cksum_orig =
	    drc->drc_next_rrd->header.drr_u.drr_checksum.drr_checksum;
	zio_cksum_t *cksump =
	    &drc->drc_next_rrd->header.drr_u.drr_checksum.drr_checksum;

	if (drc->drc_byteswap)
		byteswap_record(&drc->drc_next_rrd->header);

	if ((!ZIO_CHECKSUM_IS_ZERO(cksump)) &&
	    !ZIO_CHECKSUM_EQUAL(drc->drc_cksum, *cksump)) {
		kmem_free(drc->drc_next_rrd, sizeof (*drc->drc_next_rrd));
		drc->drc_next_rrd = NULL;
		return (SET_ERROR(ECKSUM));
	}

	receive_cksum(drc, sizeof (cksum_orig), &cksum_orig);
  1. L2843–L2851 The receiver keeps its own sum: it starts over the whole BEGIN record, goes on over each payload, and here over the next header, up to its checksum.
  2. L2861–L2866 A header whose drr_checksum disagrees stops the receive: ECKSUM. A checksum of all zeros is not checked.
  3. L2868 The stored value is then summed, as the sender did.

This runs when a record’s payload and the header after it have been read, and only then is the record queued for the writer: a record whose bytes were damaged is never applied. END is checked once more, its drr_end.drr_checksum against the sum before it. On an error, what the receive created is destroyed: the receiver still holds the from-snapshot. Before any of this, an incremental stream’s BEGIN names the from-snapshot by GUID, and the receiver refuses it (ENODEV) unless it holds a snapshot with that GUID.

Records dispatched by type. The writer thread takes each record off the queue and hands it here.

receive_process_record Excerpt of module/zfs/dmu_recv.c, lines 3188–3213, OpenZFS zfs-2.4.4. View on GitHub 
	switch (rrd->header.drr_type) {
	case DRR_OBJECT:
	{
		struct drr_object *drro = &rrd->header.drr_u.drr_object;
		err = receive_object(rwa, drro, rrd->payload);
		vmem_free(rrd->payload, rrd->payload_size);
		rrd->payload = NULL;
		break;
	}
	case DRR_FREEOBJECTS:
	{
		struct drr_freeobjects *drrfo =
		    &rrd->header.drr_u.drr_freeobjects;
		err = receive_freeobjects(rwa, drrfo);
		break;
	}
	case DRR_WRITE:
	{
		err = receive_process_write_record(rwa, rrd);
		if (rwa->heal) {
			/*
			 * If healing - always free the abd after processing
			 */
			abd_free(rrd->abd);
			rrd->abd = NULL;
		} else if (err != EAGAIN) {
  1. L3189–L3196 OBJECT goes to receive_object, which creates the object, or keeps one that exists.
  2. L3197–L3203 FREEOBJECTS goes to receive_freeobjects, which frees each object of the range that exists: c disappears.
  3. L3204–L3206 WRITE goes to receive_process_write_record. FREE, further down, goes to receive_free, which frees the range in the object.

What the receiver ends with. Starting from the from-snapshot’s files, the records of the stream bring back exactly @s4: the figure compares the two at the end, for every from-snapshot, and its tests check it against the hand-worked records of each stream.

What the figure leaves out

The figure is small: files of four 512-byte blocks under one indirect block, dnode blocks of four dnodes (a real 16 KiB dnode block holds 32), a meta-dnode drawn with its two dnode blocks, no bonus buffer. The send runs as one sequence where the code joins several threads (traversal, merge, reader, the main thread) by queues that keep the order, and the receiver starts once the stream is complete, where the code receives through a pipe as the stream is written. Record headers are laid out as dmu_replay_record_t, with only the fields the figure uses filled in. Redacted, raw (encrypted), compressed and resumable streams, embedded data, WRITE_BYREF and spill blocks are not shown; neither are throughput figures, which depend on the disks and the network, not on this code.