xref: /freebsd/sys/contrib/openzfs/module/zcommon/zfs_fletcher.c (revision fe815331bb40604ba31312acf7e4619674631777)
1 /*
2  * CDDL HEADER START
3  *
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.
7  *
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.
12  *
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]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
25  */
26 /*
27  * Copyright 2013 Saso Kiselkov. All rights reserved.
28  */
29 
30 /*
31  * Copyright (c) 2016 by Delphix. All rights reserved.
32  */
33 
34 /*
35  * Fletcher Checksums
36  * ------------------
37  *
38  * ZFS's 2nd and 4th order Fletcher checksums are defined by the following
39  * recurrence relations:
40  *
41  *	a  = a    + f
42  *	 i    i-1    i-1
43  *
44  *	b  = b    + a
45  *	 i    i-1    i
46  *
47  *	c  = c    + b		(fletcher-4 only)
48  *	 i    i-1    i
49  *
50  *	d  = d    + c		(fletcher-4 only)
51  *	 i    i-1    i
52  *
53  * Where
54  *	a_0 = b_0 = c_0 = d_0 = 0
55  * and
56  *	f_0 .. f_(n-1) are the input data.
57  *
58  * Using standard techniques, these translate into the following series:
59  *
60  *	     __n_			     __n_
61  *	     \   |			     \   |
62  *	a  =  >     f			b  =  >     i * f
63  *	 n   /___|   n - i		 n   /___|	 n - i
64  *	     i = 1			     i = 1
65  *
66  *
67  *	     __n_			     __n_
68  *	     \   |  i*(i+1)		     \   |  i*(i+1)*(i+2)
69  *	c  =  >     ------- f		d  =  >     ------------- f
70  *	 n   /___|     2     n - i	 n   /___|	  6	   n - i
71  *	     i = 1			     i = 1
72  *
73  * For fletcher-2, the f_is are 64-bit, and [ab]_i are 64-bit accumulators.
74  * Since the additions are done mod (2^64), errors in the high bits may not
75  * be noticed.  For this reason, fletcher-2 is deprecated.
76  *
77  * For fletcher-4, the f_is are 32-bit, and [abcd]_i are 64-bit accumulators.
78  * A conservative estimate of how big the buffer can get before we overflow
79  * can be estimated using f_i = 0xffffffff for all i:
80  *
81  * % bc
82  *  f=2^32-1;d=0; for (i = 1; d<2^64; i++) { d += f*i*(i+1)*(i+2)/6 }; (i-1)*4
83  * 2264
84  *  quit
85  * %
86  *
87  * So blocks of up to 2k will not overflow.  Our largest block size is
88  * 128k, which has 32k 4-byte words, so we can compute the largest possible
89  * accumulators, then divide by 2^64 to figure the max amount of overflow:
90  *
91  * % bc
92  *  a=b=c=d=0; f=2^32-1; for (i=1; i<=32*1024; i++) { a+=f; b+=a; c+=b; d+=c }
93  *  a/2^64;b/2^64;c/2^64;d/2^64
94  * 0
95  * 0
96  * 1365
97  * 11186858
98  *  quit
99  * %
100  *
101  * So a and b cannot overflow.  To make sure each bit of input has some
102  * effect on the contents of c and d, we can look at what the factors of
103  * the coefficients in the equations for c_n and d_n are.  The number of 2s
104  * in the factors determines the lowest set bit in the multiplier.  Running
105  * through the cases for n*(n+1)/2 reveals that the highest power of 2 is
106  * 2^14, and for n*(n+1)*(n+2)/6 it is 2^15.  So while some data may overflow
107  * the 64-bit accumulators, every bit of every f_i effects every accumulator,
108  * even for 128k blocks.
109  *
110  * If we wanted to make a stronger version of fletcher4 (fletcher4c?),
111  * we could do our calculations mod (2^32 - 1) by adding in the carries
112  * periodically, and store the number of carries in the top 32-bits.
113  *
114  * --------------------
115  * Checksum Performance
116  * --------------------
117  *
118  * There are two interesting components to checksum performance: cached and
119  * uncached performance.  With cached data, fletcher-2 is about four times
120  * faster than fletcher-4.  With uncached data, the performance difference is
121  * negligible, since the cost of a cache fill dominates the processing time.
122  * Even though fletcher-4 is slower than fletcher-2, it is still a pretty
123  * efficient pass over the data.
124  *
125  * In normal operation, the data which is being checksummed is in a buffer
126  * which has been filled either by:
127  *
128  *	1. a compression step, which will be mostly cached, or
129  *	2. a bcopy() or copyin(), which will be uncached (because the
130  *	   copy is cache-bypassing).
131  *
132  * For both cached and uncached data, both fletcher checksums are much faster
133  * than sha-256, and slower than 'off', which doesn't touch the data at all.
134  */
135 
136 #include <sys/types.h>
137 #include <sys/sysmacros.h>
138 #include <sys/byteorder.h>
139 #include <sys/spa.h>
140 #include <sys/simd.h>
141 #include <sys/zio_checksum.h>
142 #include <sys/zfs_context.h>
143 #include <zfs_fletcher.h>
144 
145 #define	FLETCHER_MIN_SIMD_SIZE	64
146 
147 static void fletcher_4_scalar_init(fletcher_4_ctx_t *ctx);
148 static void fletcher_4_scalar_fini(fletcher_4_ctx_t *ctx, zio_cksum_t *zcp);
149 static void fletcher_4_scalar_native(fletcher_4_ctx_t *ctx,
150     const void *buf, uint64_t size);
151 static void fletcher_4_scalar_byteswap(fletcher_4_ctx_t *ctx,
152     const void *buf, uint64_t size);
153 static boolean_t fletcher_4_scalar_valid(void);
154 
155 static const fletcher_4_ops_t fletcher_4_scalar_ops = {
156 	.init_native = fletcher_4_scalar_init,
157 	.fini_native = fletcher_4_scalar_fini,
158 	.compute_native = fletcher_4_scalar_native,
159 	.init_byteswap = fletcher_4_scalar_init,
160 	.fini_byteswap = fletcher_4_scalar_fini,
161 	.compute_byteswap = fletcher_4_scalar_byteswap,
162 	.valid = fletcher_4_scalar_valid,
163 	.name = "scalar"
164 };
165 
166 static fletcher_4_ops_t fletcher_4_fastest_impl = {
167 	.name = "fastest",
168 	.valid = fletcher_4_scalar_valid
169 };
170 
171 static const fletcher_4_ops_t *fletcher_4_impls[] = {
172 	&fletcher_4_scalar_ops,
173 	&fletcher_4_superscalar_ops,
174 	&fletcher_4_superscalar4_ops,
175 #if defined(HAVE_SSE2)
176 	&fletcher_4_sse2_ops,
177 #endif
178 #if defined(HAVE_SSE2) && defined(HAVE_SSSE3)
179 	&fletcher_4_ssse3_ops,
180 #endif
181 #if defined(HAVE_AVX) && defined(HAVE_AVX2)
182 	&fletcher_4_avx2_ops,
183 #endif
184 #if defined(__x86_64) && defined(HAVE_AVX512F)
185 	&fletcher_4_avx512f_ops,
186 #endif
187 #if defined(__x86_64) && defined(HAVE_AVX512BW)
188 	&fletcher_4_avx512bw_ops,
189 #endif
190 #if defined(__aarch64__) && !defined(__FreeBSD__)
191 	&fletcher_4_aarch64_neon_ops,
192 #endif
193 };
194 
195 /* Hold all supported implementations */
196 static uint32_t fletcher_4_supp_impls_cnt = 0;
197 static fletcher_4_ops_t *fletcher_4_supp_impls[ARRAY_SIZE(fletcher_4_impls)];
198 
199 /* Select fletcher4 implementation */
200 #define	IMPL_FASTEST	(UINT32_MAX)
201 #define	IMPL_CYCLE	(UINT32_MAX - 1)
202 #define	IMPL_SCALAR	(0)
203 
204 static uint32_t fletcher_4_impl_chosen = IMPL_FASTEST;
205 
206 #define	IMPL_READ(i)	(*(volatile uint32_t *) &(i))
207 
208 static struct fletcher_4_impl_selector {
209 	const char	*fis_name;
210 	uint32_t	fis_sel;
211 } fletcher_4_impl_selectors[] = {
212 	{ "cycle",	IMPL_CYCLE },
213 	{ "fastest",	IMPL_FASTEST },
214 	{ "scalar",	IMPL_SCALAR }
215 };
216 
217 #if defined(_KERNEL)
218 static kstat_t *fletcher_4_kstat;
219 
220 static struct fletcher_4_kstat {
221 	uint64_t native;
222 	uint64_t byteswap;
223 } fletcher_4_stat_data[ARRAY_SIZE(fletcher_4_impls) + 1];
224 #endif
225 
226 /* Indicate that benchmark has been completed */
227 static boolean_t fletcher_4_initialized = B_FALSE;
228 
229 /*ARGSUSED*/
230 void
231 fletcher_init(zio_cksum_t *zcp)
232 {
233 	ZIO_SET_CHECKSUM(zcp, 0, 0, 0, 0);
234 }
235 
236 int
237 fletcher_2_incremental_native(void *buf, size_t size, void *data)
238 {
239 	zio_cksum_t *zcp = data;
240 
241 	const uint64_t *ip = buf;
242 	const uint64_t *ipend = ip + (size / sizeof (uint64_t));
243 	uint64_t a0, b0, a1, b1;
244 
245 	a0 = zcp->zc_word[0];
246 	a1 = zcp->zc_word[1];
247 	b0 = zcp->zc_word[2];
248 	b1 = zcp->zc_word[3];
249 
250 	for (; ip < ipend; ip += 2) {
251 		a0 += ip[0];
252 		a1 += ip[1];
253 		b0 += a0;
254 		b1 += a1;
255 	}
256 
257 	ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
258 	return (0);
259 }
260 
261 /*ARGSUSED*/
262 void
263 fletcher_2_native(const void *buf, uint64_t size,
264     const void *ctx_template, zio_cksum_t *zcp)
265 {
266 	fletcher_init(zcp);
267 	(void) fletcher_2_incremental_native((void *) buf, size, zcp);
268 }
269 
270 int
271 fletcher_2_incremental_byteswap(void *buf, size_t size, void *data)
272 {
273 	zio_cksum_t *zcp = data;
274 
275 	const uint64_t *ip = buf;
276 	const uint64_t *ipend = ip + (size / sizeof (uint64_t));
277 	uint64_t a0, b0, a1, b1;
278 
279 	a0 = zcp->zc_word[0];
280 	a1 = zcp->zc_word[1];
281 	b0 = zcp->zc_word[2];
282 	b1 = zcp->zc_word[3];
283 
284 	for (; ip < ipend; ip += 2) {
285 		a0 += BSWAP_64(ip[0]);
286 		a1 += BSWAP_64(ip[1]);
287 		b0 += a0;
288 		b1 += a1;
289 	}
290 
291 	ZIO_SET_CHECKSUM(zcp, a0, a1, b0, b1);
292 	return (0);
293 }
294 
295 /*ARGSUSED*/
296 void
297 fletcher_2_byteswap(const void *buf, uint64_t size,
298     const void *ctx_template, zio_cksum_t *zcp)
299 {
300 	fletcher_init(zcp);
301 	(void) fletcher_2_incremental_byteswap((void *) buf, size, zcp);
302 }
303 
304 static void
305 fletcher_4_scalar_init(fletcher_4_ctx_t *ctx)
306 {
307 	ZIO_SET_CHECKSUM(&ctx->scalar, 0, 0, 0, 0);
308 }
309 
310 static void
311 fletcher_4_scalar_fini(fletcher_4_ctx_t *ctx, zio_cksum_t *zcp)
312 {
313 	memcpy(zcp, &ctx->scalar, sizeof (zio_cksum_t));
314 }
315 
316 static void
317 fletcher_4_scalar_native(fletcher_4_ctx_t *ctx, const void *buf,
318     uint64_t size)
319 {
320 	const uint32_t *ip = buf;
321 	const uint32_t *ipend = ip + (size / sizeof (uint32_t));
322 	uint64_t a, b, c, d;
323 
324 	a = ctx->scalar.zc_word[0];
325 	b = ctx->scalar.zc_word[1];
326 	c = ctx->scalar.zc_word[2];
327 	d = ctx->scalar.zc_word[3];
328 
329 	for (; ip < ipend; ip++) {
330 		a += ip[0];
331 		b += a;
332 		c += b;
333 		d += c;
334 	}
335 
336 	ZIO_SET_CHECKSUM(&ctx->scalar, a, b, c, d);
337 }
338 
339 static void
340 fletcher_4_scalar_byteswap(fletcher_4_ctx_t *ctx, const void *buf,
341     uint64_t size)
342 {
343 	const uint32_t *ip = buf;
344 	const uint32_t *ipend = ip + (size / sizeof (uint32_t));
345 	uint64_t a, b, c, d;
346 
347 	a = ctx->scalar.zc_word[0];
348 	b = ctx->scalar.zc_word[1];
349 	c = ctx->scalar.zc_word[2];
350 	d = ctx->scalar.zc_word[3];
351 
352 	for (; ip < ipend; ip++) {
353 		a += BSWAP_32(ip[0]);
354 		b += a;
355 		c += b;
356 		d += c;
357 	}
358 
359 	ZIO_SET_CHECKSUM(&ctx->scalar, a, b, c, d);
360 }
361 
362 static boolean_t
363 fletcher_4_scalar_valid(void)
364 {
365 	return (B_TRUE);
366 }
367 
368 int
369 fletcher_4_impl_set(const char *val)
370 {
371 	int err = -EINVAL;
372 	uint32_t impl = IMPL_READ(fletcher_4_impl_chosen);
373 	size_t i, val_len;
374 
375 	val_len = strlen(val);
376 	while ((val_len > 0) && !!isspace(val[val_len-1])) /* trim '\n' */
377 		val_len--;
378 
379 	/* check mandatory implementations */
380 	for (i = 0; i < ARRAY_SIZE(fletcher_4_impl_selectors); i++) {
381 		const char *name = fletcher_4_impl_selectors[i].fis_name;
382 
383 		if (val_len == strlen(name) &&
384 		    strncmp(val, name, val_len) == 0) {
385 			impl = fletcher_4_impl_selectors[i].fis_sel;
386 			err = 0;
387 			break;
388 		}
389 	}
390 
391 	if (err != 0 && fletcher_4_initialized) {
392 		/* check all supported implementations */
393 		for (i = 0; i < fletcher_4_supp_impls_cnt; i++) {
394 			const char *name = fletcher_4_supp_impls[i]->name;
395 
396 			if (val_len == strlen(name) &&
397 			    strncmp(val, name, val_len) == 0) {
398 				impl = i;
399 				err = 0;
400 				break;
401 			}
402 		}
403 	}
404 
405 	if (err == 0) {
406 		atomic_swap_32(&fletcher_4_impl_chosen, impl);
407 		membar_producer();
408 	}
409 
410 	return (err);
411 }
412 
413 /*
414  * Returns the Fletcher 4 operations for checksums.   When a SIMD
415  * implementation is not allowed in the current context, then fallback
416  * to the fastest generic implementation.
417  */
418 static inline const fletcher_4_ops_t *
419 fletcher_4_impl_get(void)
420 {
421 	if (!kfpu_allowed())
422 		return (&fletcher_4_superscalar4_ops);
423 
424 	const fletcher_4_ops_t *ops = NULL;
425 	uint32_t impl = IMPL_READ(fletcher_4_impl_chosen);
426 
427 	switch (impl) {
428 	case IMPL_FASTEST:
429 		ASSERT(fletcher_4_initialized);
430 		ops = &fletcher_4_fastest_impl;
431 		break;
432 	case IMPL_CYCLE:
433 		/* Cycle through supported implementations */
434 		ASSERT(fletcher_4_initialized);
435 		ASSERT3U(fletcher_4_supp_impls_cnt, >, 0);
436 		static uint32_t cycle_count = 0;
437 		uint32_t idx = (++cycle_count) % fletcher_4_supp_impls_cnt;
438 		ops = fletcher_4_supp_impls[idx];
439 		break;
440 	default:
441 		ASSERT3U(fletcher_4_supp_impls_cnt, >, 0);
442 		ASSERT3U(impl, <, fletcher_4_supp_impls_cnt);
443 		ops = fletcher_4_supp_impls[impl];
444 		break;
445 	}
446 
447 	ASSERT3P(ops, !=, NULL);
448 
449 	return (ops);
450 }
451 
452 static inline void
453 fletcher_4_native_impl(const void *buf, uint64_t size, zio_cksum_t *zcp)
454 {
455 	fletcher_4_ctx_t ctx;
456 	const fletcher_4_ops_t *ops = fletcher_4_impl_get();
457 
458 	ops->init_native(&ctx);
459 	ops->compute_native(&ctx, buf, size);
460 	ops->fini_native(&ctx, zcp);
461 }
462 
463 /*ARGSUSED*/
464 void
465 fletcher_4_native(const void *buf, uint64_t size,
466     const void *ctx_template, zio_cksum_t *zcp)
467 {
468 	const uint64_t p2size = P2ALIGN(size, FLETCHER_MIN_SIMD_SIZE);
469 
470 	ASSERT(IS_P2ALIGNED(size, sizeof (uint32_t)));
471 
472 	if (size == 0 || p2size == 0) {
473 		ZIO_SET_CHECKSUM(zcp, 0, 0, 0, 0);
474 
475 		if (size > 0)
476 			fletcher_4_scalar_native((fletcher_4_ctx_t *)zcp,
477 			    buf, size);
478 	} else {
479 		fletcher_4_native_impl(buf, p2size, zcp);
480 
481 		if (p2size < size)
482 			fletcher_4_scalar_native((fletcher_4_ctx_t *)zcp,
483 			    (char *)buf + p2size, size - p2size);
484 	}
485 }
486 
487 void
488 fletcher_4_native_varsize(const void *buf, uint64_t size, zio_cksum_t *zcp)
489 {
490 	ZIO_SET_CHECKSUM(zcp, 0, 0, 0, 0);
491 	fletcher_4_scalar_native((fletcher_4_ctx_t *)zcp, buf, size);
492 }
493 
494 static inline void
495 fletcher_4_byteswap_impl(const void *buf, uint64_t size, zio_cksum_t *zcp)
496 {
497 	fletcher_4_ctx_t ctx;
498 	const fletcher_4_ops_t *ops = fletcher_4_impl_get();
499 
500 	ops->init_byteswap(&ctx);
501 	ops->compute_byteswap(&ctx, buf, size);
502 	ops->fini_byteswap(&ctx, zcp);
503 }
504 
505 /*ARGSUSED*/
506 void
507 fletcher_4_byteswap(const void *buf, uint64_t size,
508     const void *ctx_template, zio_cksum_t *zcp)
509 {
510 	const uint64_t p2size = P2ALIGN(size, FLETCHER_MIN_SIMD_SIZE);
511 
512 	ASSERT(IS_P2ALIGNED(size, sizeof (uint32_t)));
513 
514 	if (size == 0 || p2size == 0) {
515 		ZIO_SET_CHECKSUM(zcp, 0, 0, 0, 0);
516 
517 		if (size > 0)
518 			fletcher_4_scalar_byteswap((fletcher_4_ctx_t *)zcp,
519 			    buf, size);
520 	} else {
521 		fletcher_4_byteswap_impl(buf, p2size, zcp);
522 
523 		if (p2size < size)
524 			fletcher_4_scalar_byteswap((fletcher_4_ctx_t *)zcp,
525 			    (char *)buf + p2size, size - p2size);
526 	}
527 }
528 
529 /* Incremental Fletcher 4 */
530 
531 #define	ZFS_FLETCHER_4_INC_MAX_SIZE	(8ULL << 20)
532 
533 static inline void
534 fletcher_4_incremental_combine(zio_cksum_t *zcp, const uint64_t size,
535     const zio_cksum_t *nzcp)
536 {
537 	const uint64_t c1 = size / sizeof (uint32_t);
538 	const uint64_t c2 = c1 * (c1 + 1) / 2;
539 	const uint64_t c3 = c2 * (c1 + 2) / 3;
540 
541 	/*
542 	 * Value of 'c3' overflows on buffer sizes close to 16MiB. For that
543 	 * reason we split incremental fletcher4 computation of large buffers
544 	 * to steps of (ZFS_FLETCHER_4_INC_MAX_SIZE) size.
545 	 */
546 	ASSERT3U(size, <=, ZFS_FLETCHER_4_INC_MAX_SIZE);
547 
548 	zcp->zc_word[3] += nzcp->zc_word[3] + c1 * zcp->zc_word[2] +
549 	    c2 * zcp->zc_word[1] + c3 * zcp->zc_word[0];
550 	zcp->zc_word[2] += nzcp->zc_word[2] + c1 * zcp->zc_word[1] +
551 	    c2 * zcp->zc_word[0];
552 	zcp->zc_word[1] += nzcp->zc_word[1] + c1 * zcp->zc_word[0];
553 	zcp->zc_word[0] += nzcp->zc_word[0];
554 }
555 
556 static inline void
557 fletcher_4_incremental_impl(boolean_t native, const void *buf, uint64_t size,
558     zio_cksum_t *zcp)
559 {
560 	while (size > 0) {
561 		zio_cksum_t nzc;
562 		uint64_t len = MIN(size, ZFS_FLETCHER_4_INC_MAX_SIZE);
563 
564 		if (native)
565 			fletcher_4_native(buf, len, NULL, &nzc);
566 		else
567 			fletcher_4_byteswap(buf, len, NULL, &nzc);
568 
569 		fletcher_4_incremental_combine(zcp, len, &nzc);
570 
571 		size -= len;
572 		buf += len;
573 	}
574 }
575 
576 int
577 fletcher_4_incremental_native(void *buf, size_t size, void *data)
578 {
579 	zio_cksum_t *zcp = data;
580 	/* Use scalar impl to directly update cksum of small blocks */
581 	if (size < SPA_MINBLOCKSIZE)
582 		fletcher_4_scalar_native((fletcher_4_ctx_t *)zcp, buf, size);
583 	else
584 		fletcher_4_incremental_impl(B_TRUE, buf, size, zcp);
585 	return (0);
586 }
587 
588 int
589 fletcher_4_incremental_byteswap(void *buf, size_t size, void *data)
590 {
591 	zio_cksum_t *zcp = data;
592 	/* Use scalar impl to directly update cksum of small blocks */
593 	if (size < SPA_MINBLOCKSIZE)
594 		fletcher_4_scalar_byteswap((fletcher_4_ctx_t *)zcp, buf, size);
595 	else
596 		fletcher_4_incremental_impl(B_FALSE, buf, size, zcp);
597 	return (0);
598 }
599 
600 #if defined(_KERNEL)
601 /*
602  * Fletcher 4 kstats
603  */
604 static int
605 fletcher_4_kstat_headers(char *buf, size_t size)
606 {
607 	ssize_t off = 0;
608 
609 	off += snprintf(buf + off, size, "%-17s", "implementation");
610 	off += snprintf(buf + off, size - off, "%-15s", "native");
611 	(void) snprintf(buf + off, size - off, "%-15s\n", "byteswap");
612 
613 	return (0);
614 }
615 
616 static int
617 fletcher_4_kstat_data(char *buf, size_t size, void *data)
618 {
619 	struct fletcher_4_kstat *fastest_stat =
620 	    &fletcher_4_stat_data[fletcher_4_supp_impls_cnt];
621 	struct fletcher_4_kstat *curr_stat = (struct fletcher_4_kstat *)data;
622 	ssize_t off = 0;
623 
624 	if (curr_stat == fastest_stat) {
625 		off += snprintf(buf + off, size - off, "%-17s", "fastest");
626 		off += snprintf(buf + off, size - off, "%-15s",
627 		    fletcher_4_supp_impls[fastest_stat->native]->name);
628 		off += snprintf(buf + off, size - off, "%-15s\n",
629 		    fletcher_4_supp_impls[fastest_stat->byteswap]->name);
630 	} else {
631 		ptrdiff_t id = curr_stat - fletcher_4_stat_data;
632 
633 		off += snprintf(buf + off, size - off, "%-17s",
634 		    fletcher_4_supp_impls[id]->name);
635 		off += snprintf(buf + off, size - off, "%-15llu",
636 		    (u_longlong_t)curr_stat->native);
637 		off += snprintf(buf + off, size - off, "%-15llu\n",
638 		    (u_longlong_t)curr_stat->byteswap);
639 	}
640 
641 	return (0);
642 }
643 
644 static void *
645 fletcher_4_kstat_addr(kstat_t *ksp, loff_t n)
646 {
647 	if (n <= fletcher_4_supp_impls_cnt)
648 		ksp->ks_private = (void *) (fletcher_4_stat_data + n);
649 	else
650 		ksp->ks_private = NULL;
651 
652 	return (ksp->ks_private);
653 }
654 #endif
655 
656 #define	FLETCHER_4_FASTEST_FN_COPY(type, src)				  \
657 {									  \
658 	fletcher_4_fastest_impl.init_ ## type = src->init_ ## type;	  \
659 	fletcher_4_fastest_impl.fini_ ## type = src->fini_ ## type;	  \
660 	fletcher_4_fastest_impl.compute_ ## type = src->compute_ ## type; \
661 }
662 
663 #define	FLETCHER_4_BENCH_NS	(MSEC2NSEC(50))		/* 50ms */
664 
665 typedef void fletcher_checksum_func_t(const void *, uint64_t, const void *,
666 					zio_cksum_t *);
667 
668 #if defined(_KERNEL)
669 static void
670 fletcher_4_benchmark_impl(boolean_t native, char *data, uint64_t data_size)
671 {
672 
673 	struct fletcher_4_kstat *fastest_stat =
674 	    &fletcher_4_stat_data[fletcher_4_supp_impls_cnt];
675 	hrtime_t start;
676 	uint64_t run_bw, run_time_ns, best_run = 0;
677 	zio_cksum_t zc;
678 	uint32_t i, l, sel_save = IMPL_READ(fletcher_4_impl_chosen);
679 
680 	fletcher_checksum_func_t *fletcher_4_test = native ?
681 	    fletcher_4_native : fletcher_4_byteswap;
682 
683 	for (i = 0; i < fletcher_4_supp_impls_cnt; i++) {
684 		struct fletcher_4_kstat *stat = &fletcher_4_stat_data[i];
685 		uint64_t run_count = 0;
686 
687 		/* temporary set an implementation */
688 		fletcher_4_impl_chosen = i;
689 
690 		kpreempt_disable();
691 		start = gethrtime();
692 		do {
693 			for (l = 0; l < 32; l++, run_count++)
694 				fletcher_4_test(data, data_size, NULL, &zc);
695 
696 			run_time_ns = gethrtime() - start;
697 		} while (run_time_ns < FLETCHER_4_BENCH_NS);
698 		kpreempt_enable();
699 
700 		run_bw = data_size * run_count * NANOSEC;
701 		run_bw /= run_time_ns;	/* B/s */
702 
703 		if (native)
704 			stat->native = run_bw;
705 		else
706 			stat->byteswap = run_bw;
707 
708 		if (run_bw > best_run) {
709 			best_run = run_bw;
710 
711 			if (native) {
712 				fastest_stat->native = i;
713 				FLETCHER_4_FASTEST_FN_COPY(native,
714 				    fletcher_4_supp_impls[i]);
715 			} else {
716 				fastest_stat->byteswap = i;
717 				FLETCHER_4_FASTEST_FN_COPY(byteswap,
718 				    fletcher_4_supp_impls[i]);
719 			}
720 		}
721 	}
722 
723 	/* restore original selection */
724 	atomic_swap_32(&fletcher_4_impl_chosen, sel_save);
725 }
726 #endif /* _KERNEL */
727 
728 /*
729  * Initialize and benchmark all supported implementations.
730  */
731 static void
732 fletcher_4_benchmark(void)
733 {
734 	fletcher_4_ops_t *curr_impl;
735 	int i, c;
736 
737 	/* Move supported implementations into fletcher_4_supp_impls */
738 	for (i = 0, c = 0; i < ARRAY_SIZE(fletcher_4_impls); i++) {
739 		curr_impl = (fletcher_4_ops_t *)fletcher_4_impls[i];
740 
741 		if (curr_impl->valid && curr_impl->valid())
742 			fletcher_4_supp_impls[c++] = curr_impl;
743 	}
744 	membar_producer();	/* complete fletcher_4_supp_impls[] init */
745 	fletcher_4_supp_impls_cnt = c;	/* number of supported impl */
746 
747 #if defined(_KERNEL)
748 	static const size_t data_size = 1 << SPA_OLD_MAXBLOCKSHIFT; /* 128kiB */
749 	char *databuf = vmem_alloc(data_size, KM_SLEEP);
750 
751 	for (i = 0; i < data_size / sizeof (uint64_t); i++)
752 		((uint64_t *)databuf)[i] = (uintptr_t)(databuf+i); /* warm-up */
753 
754 	fletcher_4_benchmark_impl(B_FALSE, databuf, data_size);
755 	fletcher_4_benchmark_impl(B_TRUE, databuf, data_size);
756 
757 	vmem_free(databuf, data_size);
758 #else
759 	/*
760 	 * Skip the benchmark in user space to avoid impacting libzpool
761 	 * consumers (zdb, zhack, zinject, ztest).  The last implementation
762 	 * is assumed to be the fastest and used by default.
763 	 */
764 	memcpy(&fletcher_4_fastest_impl,
765 	    fletcher_4_supp_impls[fletcher_4_supp_impls_cnt - 1],
766 	    sizeof (fletcher_4_fastest_impl));
767 	fletcher_4_fastest_impl.name = "fastest";
768 	membar_producer();
769 #endif /* _KERNEL */
770 }
771 
772 void
773 fletcher_4_init(void)
774 {
775 	/* Determine the fastest available implementation. */
776 	fletcher_4_benchmark();
777 
778 #if defined(_KERNEL)
779 	/* Install kstats for all implementations */
780 	fletcher_4_kstat = kstat_create("zfs", 0, "fletcher_4_bench", "misc",
781 	    KSTAT_TYPE_RAW, 0, KSTAT_FLAG_VIRTUAL);
782 	if (fletcher_4_kstat != NULL) {
783 		fletcher_4_kstat->ks_data = NULL;
784 		fletcher_4_kstat->ks_ndata = UINT32_MAX;
785 		kstat_set_raw_ops(fletcher_4_kstat,
786 		    fletcher_4_kstat_headers,
787 		    fletcher_4_kstat_data,
788 		    fletcher_4_kstat_addr);
789 		kstat_install(fletcher_4_kstat);
790 	}
791 #endif
792 
793 	/* Finish initialization */
794 	fletcher_4_initialized = B_TRUE;
795 }
796 
797 void
798 fletcher_4_fini(void)
799 {
800 #if defined(_KERNEL)
801 	if (fletcher_4_kstat != NULL) {
802 		kstat_delete(fletcher_4_kstat);
803 		fletcher_4_kstat = NULL;
804 	}
805 #endif
806 }
807 
808 /* ABD adapters */
809 
810 static void
811 abd_fletcher_4_init(zio_abd_checksum_data_t *cdp)
812 {
813 	const fletcher_4_ops_t *ops = fletcher_4_impl_get();
814 	cdp->acd_private = (void *) ops;
815 
816 	if (cdp->acd_byteorder == ZIO_CHECKSUM_NATIVE)
817 		ops->init_native(cdp->acd_ctx);
818 	else
819 		ops->init_byteswap(cdp->acd_ctx);
820 }
821 
822 static void
823 abd_fletcher_4_fini(zio_abd_checksum_data_t *cdp)
824 {
825 	fletcher_4_ops_t *ops = (fletcher_4_ops_t *)cdp->acd_private;
826 
827 	ASSERT(ops);
828 
829 	if (cdp->acd_byteorder == ZIO_CHECKSUM_NATIVE)
830 		ops->fini_native(cdp->acd_ctx, cdp->acd_zcp);
831 	else
832 		ops->fini_byteswap(cdp->acd_ctx, cdp->acd_zcp);
833 }
834 
835 static void
836 abd_fletcher_4_simd2scalar(boolean_t native, void *data, size_t size,
837     zio_abd_checksum_data_t *cdp)
838 {
839 	zio_cksum_t *zcp = cdp->acd_zcp;
840 
841 	ASSERT3U(size, <, FLETCHER_MIN_SIMD_SIZE);
842 
843 	abd_fletcher_4_fini(cdp);
844 	cdp->acd_private = (void *)&fletcher_4_scalar_ops;
845 
846 	if (native)
847 		fletcher_4_incremental_native(data, size, zcp);
848 	else
849 		fletcher_4_incremental_byteswap(data, size, zcp);
850 }
851 
852 static int
853 abd_fletcher_4_iter(void *data, size_t size, void *private)
854 {
855 	zio_abd_checksum_data_t *cdp = (zio_abd_checksum_data_t *)private;
856 	fletcher_4_ctx_t *ctx = cdp->acd_ctx;
857 	fletcher_4_ops_t *ops = (fletcher_4_ops_t *)cdp->acd_private;
858 	boolean_t native = cdp->acd_byteorder == ZIO_CHECKSUM_NATIVE;
859 	uint64_t asize = P2ALIGN(size, FLETCHER_MIN_SIMD_SIZE);
860 
861 	ASSERT(IS_P2ALIGNED(size, sizeof (uint32_t)));
862 
863 	if (asize > 0) {
864 		if (native)
865 			ops->compute_native(ctx, data, asize);
866 		else
867 			ops->compute_byteswap(ctx, data, asize);
868 
869 		size -= asize;
870 		data = (char *)data + asize;
871 	}
872 
873 	if (size > 0) {
874 		ASSERT3U(size, <, FLETCHER_MIN_SIMD_SIZE);
875 		/* At this point we have to switch to scalar impl */
876 		abd_fletcher_4_simd2scalar(native, data, size, cdp);
877 	}
878 
879 	return (0);
880 }
881 
882 zio_abd_checksum_func_t fletcher_4_abd_ops = {
883 	.acf_init = abd_fletcher_4_init,
884 	.acf_fini = abd_fletcher_4_fini,
885 	.acf_iter = abd_fletcher_4_iter
886 };
887 
888 
889 #if defined(_KERNEL) && defined(__linux__)
890 
891 static int
892 fletcher_4_param_get(char *buffer, zfs_kernel_param_t *unused)
893 {
894 	const uint32_t impl = IMPL_READ(fletcher_4_impl_chosen);
895 	char *fmt;
896 	int i, cnt = 0;
897 
898 	/* list fastest */
899 	fmt = (impl == IMPL_FASTEST) ? "[%s] " : "%s ";
900 	cnt += sprintf(buffer + cnt, fmt, "fastest");
901 
902 	/* list all supported implementations */
903 	for (i = 0; i < fletcher_4_supp_impls_cnt; i++) {
904 		fmt = (i == impl) ? "[%s] " : "%s ";
905 		cnt += sprintf(buffer + cnt, fmt,
906 		    fletcher_4_supp_impls[i]->name);
907 	}
908 
909 	return (cnt);
910 }
911 
912 static int
913 fletcher_4_param_set(const char *val, zfs_kernel_param_t *unused)
914 {
915 	return (fletcher_4_impl_set(val));
916 }
917 
918 /*
919  * Choose a fletcher 4 implementation in ZFS.
920  * Users can choose "cycle" to exercise all implementations, but this is
921  * for testing purpose therefore it can only be set in user space.
922  */
923 module_param_call(zfs_fletcher_4_impl,
924     fletcher_4_param_set, fletcher_4_param_get, NULL, 0644);
925 MODULE_PARM_DESC(zfs_fletcher_4_impl, "Select fletcher 4 implementation.");
926 
927 EXPORT_SYMBOL(fletcher_init);
928 EXPORT_SYMBOL(fletcher_2_incremental_native);
929 EXPORT_SYMBOL(fletcher_2_incremental_byteswap);
930 EXPORT_SYMBOL(fletcher_4_init);
931 EXPORT_SYMBOL(fletcher_4_fini);
932 EXPORT_SYMBOL(fletcher_2_native);
933 EXPORT_SYMBOL(fletcher_2_byteswap);
934 EXPORT_SYMBOL(fletcher_4_native);
935 EXPORT_SYMBOL(fletcher_4_native_varsize);
936 EXPORT_SYMBOL(fletcher_4_byteswap);
937 EXPORT_SYMBOL(fletcher_4_incremental_native);
938 EXPORT_SYMBOL(fletcher_4_incremental_byteswap);
939 EXPORT_SYMBOL(fletcher_4_abd_ops);
940 #endif
941