1 // SPDX-License-Identifier: CDDL-1.0
2 /*
3 * This file and its contents are supplied under the terms of the
4 * Common Development and Distribution License ("CDDL"), version 1.0.
5 * You may only use this file in accordance with the terms of version
6 * 1.0 of the CDDL.
7 *
8 * A full copy of the text of the CDDL should have accompanied this
9 * source. A copy of the CDDL is also available via the Internet at
10 * https://opensource.org/license/CDDL-1.0.
11 */
12
13 /*
14 * Copyright (c) 2026 by Garth Snyder. All rights reserved.
15 */
16
17 #include <assert.h>
18 #include <stddef.h>
19 #include <stdint.h>
20 #include <stdlib.h>
21 #include <sys/byteorder.h>
22 #include <sys/param.h>
23 #include <sys/spa_checksum.h>
24 #include <sys/stdtypes.h>
25 #include <sys/sysmacros.h>
26 #include <sys/types.h>
27 #include <sys/zfs_ioctl.h>
28 #include <zfs_fletcher.h>
29
30 #include "zstream_fletcher4.h"
31 #include "zstream_modules.h"
32 #include "zstream_queue.h"
33 #include "zstream_util.h"
34
35 #define CK_OFFSET offsetof(dmu_replay_record_t, drr_u.drr_checksum.drr_checksum)
36 #define END_CK_OFFSET offsetof(dmu_replay_record_t, drr_u.drr_end.drr_checksum)
37
38 /*
39 * Copied from zfs_fletcher.c. See comments below regarding the
40 * fletcher_4_incremental_combine() function.
41 */
42 #define MAX_FLETCHER_BLOCK (8ULL << 20)
43
44 typedef enum { F4_SET, F4_VALIDATE } fletcher4_op_t;
45
46 typedef struct {
47 zio_cksum_t fc_stream_cksum;
48 fletcher4_op_t fc_operation;
49 } fletcher4_context_t;
50
51 static fletcher4_context_t fletcher4_contexts[MAX_FLETCHER_4];
52 static int next_context = 0;
53
54 static inline int
fletcher_4_incremental(boolean_t swap,void * buff,size_t size,void * cksum)55 fletcher_4_incremental(boolean_t swap, void *buff, size_t size, void *cksum)
56 {
57 if (swap) {
58 return (fletcher_4_incremental_byteswap(buff, size, cksum));
59 } else {
60 return (fletcher_4_incremental_native(buff, size, cksum));
61 }
62 }
63
64 static inline void
fletcher_4(boolean_t swap,void * buff,size_t size,void * cksum)65 fletcher_4(boolean_t swap, void *buff, size_t size, void *cksum)
66 {
67 if (swap) {
68 fletcher_4_byteswap(buff, size, NULL, cksum);
69 } else {
70 fletcher_4_native(buff, size, NULL, cksum);
71 }
72 }
73
74 /*
75 * The function below and the MAX_FLETCHER_BLOCK define are copied from
76 * zfs_fletcher.c, where they're internal.
77 *
78 * Fletcher checksums CAN be computed in parallel, with the segments later
79 * being reassembled. However, the combine function needs to know the
80 * original length of each segment, and there's a hard limit as to how long
81 * any given segment can be because 64-bit coefficients used in the combine
82 * operation may overflow if the size is larger than 8MB.
83 *
84 * My understanding of this is that the checksum fields themselves can and
85 * will overflow for long hash texts. However, they still function properly
86 * as checksums when this happens. But overflow has to be handled correctly
87 * in a structured fashion, not by allowing intermediate calculations to
88 * overflow.
89 */
90 static inline void
fletcher4_incremental_combine(zio_cksum_t * zcp,const uint64_t size,const zio_cksum_t * nzcp)91 fletcher4_incremental_combine(zio_cksum_t *zcp, const uint64_t size,
92 const zio_cksum_t *nzcp)
93 {
94 const uint64_t c1 = size / sizeof (uint32_t);
95 const uint64_t c2 = c1 * (c1 + 1) / 2;
96 const uint64_t c3 = c2 * (c1 + 2) / 3;
97
98 /*
99 * Value of 'c3' overflows on buffer sizes close to 16MiB. For that
100 * reason we split incremental fletcher4 computation of large buffers
101 * to steps of (MAX_FLETCHER_BLOCK) size.
102 */
103 ASSERT3U(size, <=, MAX_FLETCHER_BLOCK);
104
105 zcp->zc_word[3] += nzcp->zc_word[3] + c1 * zcp->zc_word[2] +
106 c2 * zcp->zc_word[1] + c3 * zcp->zc_word[0];
107 zcp->zc_word[2] += nzcp->zc_word[2] + c1 * zcp->zc_word[1] +
108 c2 * zcp->zc_word[0];
109 zcp->zc_word[1] += nzcp->zc_word[1] + c1 * zcp->zc_word[0];
110 zcp->zc_word[0] += nzcp->zc_word[0];
111 }
112
113 /*
114 * This is the parallel portion of checksum calculation. We calculate only
115 * the checksum blocks for payloads. The records themselves are summed in
116 * the serial step.
117 *
118 * Because MAX_FLETCHER_BLOCK is 8MB, the great majority of payloads need
119 * only a single checksum calculation. The drr_fletcher4_t struct has both a
120 * first-block checksum field and a pointer to an overflow block on the
121 * heap. The overflow block is not allocated unless the payload size is
122 * greater than MAX_FLETCHER_BLOCK.
123 */
124 static void
chain_calc_fletcher4(queue_item_t * item_in,void * context)125 chain_calc_fletcher4(queue_item_t *item_in, void *context)
126 {
127 (void) context;
128 drr_fletcher4_t *item = (drr_fletcher4_t *)item_in;
129
130 VERIFY3U(item->dp_base.dp_payload_size, >, 0);
131
132 ssize_t remaining = item->dp_base.dp_payload_size;
133 uint8_t *data = item->dp_base.dp_payload;
134 size_t write_size = MIN(remaining, MAX_FLETCHER_BLOCK);
135 int num_overflow = DIV_ROUND_UP(remaining, MAX_FLETCHER_BLOCK) - 1;
136 zio_cksum_t *fragment = &item->dp_fletcher4_payload;
137 boolean_t swap = ATTR_IS_SET(CA_BYTESWAPPED);
138
139 fletcher_4(swap, data, write_size, fragment);
140 if (num_overflow) {
141 fragment = safe_calloc(num_overflow * sizeof (zio_cksum_t));
142 item->dp_fletcher4_overflow = fragment;
143 } else {
144 item->dp_fletcher4_overflow = NULL;
145 }
146 while (remaining -= write_size) {
147 data += write_size;
148 write_size = MIN(remaining, MAX_FLETCHER_BLOCK);
149 fletcher_4(swap, data, write_size, fragment);
150 fragment++;
151 }
152 }
153
154 /*
155 * Combine the payload checksum(s) produced by the parallel phase into the
156 * stream checksum. Used by the serial validation or inscription step.
157 */
158 static void
assemble_payload_cksum(drr_fletcher4_t * item,zio_cksum_t * stream_ck)159 assemble_payload_cksum(drr_fletcher4_t *item, zio_cksum_t *stream_ck)
160 {
161 ssize_t remaining = item->dp_base.dp_payload_size;
162 size_t read_size = MIN(remaining, MAX_FLETCHER_BLOCK);
163 zio_cksum_t *fragment = item->dp_fletcher4_overflow;
164
165 if (remaining == 0)
166 return;
167 fletcher4_incremental_combine(stream_ck, read_size,
168 &item->dp_fletcher4_payload);
169 while (remaining -= read_size) {
170 read_size = MIN(remaining, MAX_FLETCHER_BLOCK);
171 fletcher4_incremental_combine(stream_ck, read_size, fragment);
172 fragment++;
173 }
174 if (item->dp_fletcher4_overflow != NULL) {
175 free(item->dp_fletcher4_overflow);
176 item->dp_fletcher4_overflow = NULL;
177 }
178 }
179
180 /*
181 * This function implements the serial portions of both validation and
182 * inscription, based on the fc_operation field of the context struct.
183 * Checksumming is either very early in a chain or very late, so records
184 * are potentially in non-native endianness in either mode.
185 *
186 * This function emits or validates a replay record with proper checksums
187 * and with proper maintenance of the stream checksum. That is:
188 *
189 * 1) Update stream checksum with the record header up to drr_checksum.
190 * 2) Update drr_checksum field in the record header from stream checksum.
191 * 3) Update stream checksum with the checksum field in the record header.
192 * 4) Update stream checksum with the contents of the payload.
193 *
194 * DRR_BEGIN records do not have record checksums. They can't, because the
195 * drr_begin struct overlaps with space that would otherwise be used for the
196 * end-record checksum.
197 *
198 * DRR_END records normally do have end-record checksums. However, records
199 * emitted by send_conclusion_record() in libzfs_sendrecv.c have the
200 * checksum set to zero. zfs receive ignores those checksums. DRR_END records
201 * also have an internal checksum that applies to the stream-to-date since the
202 * most recent DRR_BEGIN.
203 *
204 * Null zstream transformations should be idempotent. E.g., a zstream redup
205 * that does not redup anything should yield a stream that is bit-for-bit
206 * identical to the original stream. So, it's helpful to emulate zfs send's
207 * checksumming pattern just to minimize spurious differences between
208 * input and output streams.
209 */
210 static disposition_t
chain_fletcher4(queue_item_t * item_in,void * context_in)211 chain_fletcher4(queue_item_t *item_in, void *context_in)
212 {
213 drr_fletcher4_t *item = (drr_fletcher4_t *)item_in;
214 fletcher4_context_t *context = (fletcher4_context_t *)context_in;
215
216 if (item == NULL || (context->fc_operation == F4_VALIDATE &&
217 OPTION_ENABLED(CA_IGNORE_CKSUMS))) {
218 return (D_OK);
219 }
220
221 zio_cksum_t *stream_cksum = &context->fc_stream_cksum;
222 dmu_replay_record_t *drr = &item->dp_base.dp_drr;
223 struct drr_end *drre = &drr->drr_u.drr_end;
224 zio_cksum_t *record_cksum = &drr->drr_u.drr_checksum.drr_checksum;
225 zio_cksum_t *end_cksum = &drre->drr_checksum;
226
227 boolean_t swap = (context->fc_operation == F4_VALIDATE &&
228 ATTR_IS_SET(CA_BYTESWAPPED)) || (context->fc_operation == F4_SET &&
229 OPTION_ENABLED(CA_BYTESWAP_ON_OUTPUT));
230 uint32_t drr_type = swap ? BSWAP_32(drr->drr_type) : drr->drr_type;
231 off_t ck_offset = offsetof(dmu_replay_record_t,
232 drr_u.drr_checksum.drr_checksum);
233
234 if (item->dp_base.dp_stream_offset == 0) {
235 VERIFY3U(ck_offset, ==, sizeof (dmu_replay_record_t) -
236 sizeof (zio_cksum_t));
237 }
238 if (drr_type == DRR_BEGIN) {
239 ZIO_SET_CHECKSUM(stream_cksum, 0, 0, 0, 0);
240 } else if (drr_type == DRR_END) {
241 if (context->fc_operation == F4_VALIDATE) {
242 off_t stream_offset = item->dp_base.dp_stream_offset +
243 offsetof(dmu_replay_record_t,
244 drr_u.drr_end.drr_checksum);
245 validate_or_exit(stream_cksum, end_cksum, swap,
246 "in DRR_END record", stream_offset);
247 } else {
248 *end_cksum = *stream_cksum;
249 if (swap)
250 ZIO_CHECKSUM_BSWAP(end_cksum);
251 }
252 }
253 fletcher_4_incremental(swap, drr, ck_offset, stream_cksum);
254 if (drr_type != DRR_BEGIN && !IS_CONCLUSION(drr, drr_type)) {
255 if (context->fc_operation == F4_VALIDATE) {
256 off_t stream_offset =
257 item->dp_base.dp_stream_offset + ck_offset;
258 validate_or_exit(stream_cksum, record_cksum,
259 swap, "at DRR record end", stream_offset);
260 } else {
261 *record_cksum = *stream_cksum;
262 if (swap)
263 ZIO_CHECKSUM_BSWAP(record_cksum);
264 }
265 }
266 if (drr_type == DRR_END) {
267 ZIO_SET_CHECKSUM(stream_cksum, 0, 0, 0, 0);
268 } else {
269 fletcher_4_incremental(swap, record_cksum,
270 sizeof (drr->drr_u.drr_checksum.drr_checksum),
271 stream_cksum);
272 assemble_payload_cksum(item, stream_cksum);
273 }
274 return (D_OK);
275 }
276
277 /*
278 * Since checksumming is either very early or very late in the chain, these
279 * queues effectively double as I/O buffers. Ergo, the default queue length
280 * is long. The batch budget is also large because Fletcher 4 calculations
281 * are fast.
282 */
283 chain_step_t
parallel_calc_fletcher4(int queue_length)284 parallel_calc_fletcher4(int queue_length)
285 {
286 chain_step_t step = {
287 .cs_type = CS_PARALLEL,
288 .cs_in_size = sizeof (drr_packet_t),
289 .cs_out_size = sizeof (drr_fletcher4_t),
290 .cs_parallel = {
291 .queue_length = queue_length,
292 .batch_budget = 256 * 1024,
293 .process = chain_calc_fletcher4,
294 .cost = payload_size_as_cost
295 }
296 };
297 return (step);
298 }
299
300 static chain_step_t
fletcher4_serial_step(fletcher4_op_t operation)301 fletcher4_serial_step(fletcher4_op_t operation)
302 {
303 int context_ix = next_context++ % MAX_FLETCHER_4;
304 fletcher4_context_t *context = &fletcher4_contexts[context_ix];
305
306 context->fc_operation = operation;
307 ZIO_SET_CHECKSUM(&context->fc_stream_cksum, 0, 0, 0, 0);
308
309 chain_step_t step = {
310 .cs_type = CS_SERIAL,
311 .cs_in_size = sizeof (drr_fletcher4_t),
312 .cs_out_size = sizeof (drr_packet_t),
313 .cs_context = context,
314 .cs_serial = {
315 .process = chain_fletcher4,
316 }
317 };
318 return (step);
319 }
320
321 chain_step_t
serial_add_fletcher4(void)322 serial_add_fletcher4(void)
323 {
324 return (fletcher4_serial_step(F4_SET));
325 }
326
327 chain_step_t
serial_validate_fletcher4(void)328 serial_validate_fletcher4(void)
329 {
330 return (fletcher4_serial_step(F4_VALIDATE));
331 }
332