xref: /illumos-gate/usr/src/boot/sys/cddl/boot/zfs/zfssubr.c (revision 3e8c7f16)
1199767f8SToomas Soome /*
2199767f8SToomas Soome  * CDDL HEADER START
3199767f8SToomas Soome  *
4199767f8SToomas Soome  * The contents of this file are subject to the terms of the
5199767f8SToomas Soome  * Common Development and Distribution License (the "License").
6199767f8SToomas Soome  * You may not use this file except in compliance with the License.
7199767f8SToomas Soome  *
8199767f8SToomas Soome  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9199767f8SToomas Soome  * or http://www.opensolaris.org/os/licensing.
10199767f8SToomas Soome  * See the License for the specific language governing permissions
11199767f8SToomas Soome  * and limitations under the License.
12199767f8SToomas Soome  *
13199767f8SToomas Soome  * When distributing Covered Code, include this CDDL HEADER in each
14199767f8SToomas Soome  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15199767f8SToomas Soome  * If applicable, add the following below this CDDL HEADER, with the
16199767f8SToomas Soome  * fields enclosed by brackets "[]" replaced with your own identifying
17199767f8SToomas Soome  * information: Portions Copyright [yyyy] [name of copyright owner]
18199767f8SToomas Soome  *
19199767f8SToomas Soome  * CDDL HEADER END
20199767f8SToomas Soome  */
21199767f8SToomas Soome /*
22199767f8SToomas Soome  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
23199767f8SToomas Soome  * Use is subject to license terms.
24199767f8SToomas Soome  */
25199767f8SToomas Soome 
26199767f8SToomas Soome #include <sys/cdefs.h>
2710ae99eeSToomas Soome #include <lz4.h>
28199767f8SToomas Soome 
29199767f8SToomas Soome static uint64_t zfs_crc64_table[256];
30199767f8SToomas Soome 
31199767f8SToomas Soome #define	ECKSUM	666
32199767f8SToomas Soome 
33199767f8SToomas Soome #define	ASSERT3S(x, y, z)	((void)0)
34199767f8SToomas Soome #define	ASSERT3U(x, y, z)	((void)0)
35199767f8SToomas Soome #define	ASSERT3P(x, y, z)	((void)0)
36199767f8SToomas Soome #define	ASSERT0(x)		((void)0)
37199767f8SToomas Soome #define	ASSERT(x)		((void)0)
38199767f8SToomas Soome 
39199767f8SToomas Soome static void
zfs_init_crc(void)40199767f8SToomas Soome zfs_init_crc(void)
41199767f8SToomas Soome {
42199767f8SToomas Soome 	int i, j;
43199767f8SToomas Soome 	uint64_t *ct;
44199767f8SToomas Soome 
45199767f8SToomas Soome 	/*
46199767f8SToomas Soome 	 * Calculate the crc64 table (used for the zap hash
47199767f8SToomas Soome 	 * function).
48199767f8SToomas Soome 	 */
49199767f8SToomas Soome 	if (zfs_crc64_table[128] != ZFS_CRC64_POLY) {
507bbcfb41SToomas Soome 		memset(zfs_crc64_table, 0, sizeof (zfs_crc64_table));
517bbcfb41SToomas Soome 		for (i = 0; i < 256; i++) {
527bbcfb41SToomas Soome 			ct = zfs_crc64_table + i;
537bbcfb41SToomas Soome 			for (*ct = i, j = 8; j > 0; j--)
547bbcfb41SToomas Soome 				*ct = (*ct >> 1) ^
557bbcfb41SToomas Soome 				    (-(*ct & 1) & ZFS_CRC64_POLY);
567bbcfb41SToomas Soome 		}
57199767f8SToomas Soome 	}
58199767f8SToomas Soome }
59199767f8SToomas Soome 
60199767f8SToomas Soome static void
zio_checksum_off(const void * buf __unused,uint64_t size __unused,const void * ctx_template __unused,zio_cksum_t * zcp)618eef2ab6SToomas Soome zio_checksum_off(const void *buf __unused, uint64_t size __unused,
628eef2ab6SToomas Soome     const void *ctx_template __unused, zio_cksum_t *zcp)
63199767f8SToomas Soome {
64199767f8SToomas Soome 	ZIO_SET_CHECKSUM(zcp, 0, 0, 0, 0);
65199767f8SToomas Soome }
66199767f8SToomas Soome 
67199767f8SToomas Soome /*
68199767f8SToomas Soome  * Signature for checksum functions.
69199767f8SToomas Soome  */
70199767f8SToomas Soome typedef void zio_checksum_t(const void *data, uint64_t size,
71199767f8SToomas Soome     const void *ctx_template, zio_cksum_t *zcp);
72199767f8SToomas Soome typedef void *zio_checksum_tmpl_init_t(const zio_cksum_salt_t *salt);
73199767f8SToomas Soome typedef void zio_checksum_tmpl_free_t(void *ctx_template);
74199767f8SToomas Soome 
75199767f8SToomas Soome typedef enum zio_checksum_flags {
76199767f8SToomas Soome 	/* Strong enough for metadata? */
77199767f8SToomas Soome 	ZCHECKSUM_FLAG_METADATA = (1 << 1),
78199767f8SToomas Soome 	/* ZIO embedded checksum */
79199767f8SToomas Soome 	ZCHECKSUM_FLAG_EMBEDDED = (1 << 2),
80199767f8SToomas Soome 	/* Strong enough for dedup (without verification)? */
81199767f8SToomas Soome 	ZCHECKSUM_FLAG_DEDUP = (1 << 3),
82199767f8SToomas Soome 	/* Uses salt value */
83199767f8SToomas Soome 	ZCHECKSUM_FLAG_SALTED = (1 << 4),
84199767f8SToomas Soome 	/* Strong enough for nopwrite? */
85199767f8SToomas Soome 	ZCHECKSUM_FLAG_NOPWRITE = (1 << 5)
86199767f8SToomas Soome } zio_checksum_flags_t;
87199767f8SToomas Soome 
88199767f8SToomas Soome /*
89199767f8SToomas Soome  * Information about each checksum function.
90199767f8SToomas Soome  */
91199767f8SToomas Soome typedef struct zio_checksum_info {
92199767f8SToomas Soome 	/* checksum function for each byteorder */
93199767f8SToomas Soome 	zio_checksum_t			*ci_func[2];
94199767f8SToomas Soome 	zio_checksum_tmpl_init_t	*ci_tmpl_init;
95199767f8SToomas Soome 	zio_checksum_tmpl_free_t	*ci_tmpl_free;
96199767f8SToomas Soome 	zio_checksum_flags_t		ci_flags;
97199767f8SToomas Soome 	const char			*ci_name;	/* descriptive name */
98199767f8SToomas Soome } zio_checksum_info_t;
99199767f8SToomas Soome 
100199767f8SToomas Soome #include "blkptr.c"
101199767f8SToomas Soome 
102199767f8SToomas Soome #include "fletcher.c"
103199767f8SToomas Soome #include "sha256.c"
1044a04e8dbSToomas Soome #include "skein_zfs.c"
1054a04e8dbSToomas Soome #include "edonr_zfs.c"
106199767f8SToomas Soome 
107199767f8SToomas Soome static zio_checksum_info_t zio_checksum_table[ZIO_CHECKSUM_FUNCTIONS] = {
108199767f8SToomas Soome 	{{NULL, NULL}, NULL, NULL, 0, "inherit"},
109199767f8SToomas Soome 	{{NULL, NULL}, NULL, NULL, 0, "on"},
110199767f8SToomas Soome 	{{zio_checksum_off,	zio_checksum_off}, NULL, NULL, 0, "off"},
111199767f8SToomas Soome 	{{zio_checksum_SHA256,	zio_checksum_SHA256}, NULL, NULL,
112199767f8SToomas Soome 	    ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_EMBEDDED, "label"},
113199767f8SToomas Soome 	{{zio_checksum_SHA256,	zio_checksum_SHA256}, NULL, NULL,
114199767f8SToomas Soome 	    ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_EMBEDDED, "gang_header"},
115199767f8SToomas Soome 	{{fletcher_2_native,	fletcher_2_byteswap}, NULL, NULL,
116199767f8SToomas Soome 	    ZCHECKSUM_FLAG_EMBEDDED, "zilog"},
117199767f8SToomas Soome 	{{fletcher_2_native,	fletcher_2_byteswap}, NULL, NULL,
118199767f8SToomas Soome 	    0, "fletcher2"},
119199767f8SToomas Soome 	{{fletcher_4_native,	fletcher_4_byteswap}, NULL, NULL,
120199767f8SToomas Soome 	    ZCHECKSUM_FLAG_METADATA, "fletcher4"},
121199767f8SToomas Soome 	{{zio_checksum_SHA256,	zio_checksum_SHA256}, NULL, NULL,
122199767f8SToomas Soome 	    ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_DEDUP |
123199767f8SToomas Soome 	    ZCHECKSUM_FLAG_NOPWRITE, "SHA256"},
124199767f8SToomas Soome 	{{fletcher_4_native,	fletcher_4_byteswap}, NULL, NULL,
125199767f8SToomas Soome 	    ZCHECKSUM_FLAG_EMBEDDED, "zillog2"},
126199767f8SToomas Soome 	{{zio_checksum_off,	zio_checksum_off}, NULL, NULL,
127199767f8SToomas Soome 	    0, "noparity"},
128199767f8SToomas Soome 	{{zio_checksum_SHA512_native,	zio_checksum_SHA512_byteswap},
129199767f8SToomas Soome 	    NULL, NULL, ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_DEDUP |
130199767f8SToomas Soome 	    ZCHECKSUM_FLAG_NOPWRITE, "SHA512"},
131199767f8SToomas Soome 	/* no skein and edonr for now */
1324a04e8dbSToomas Soome 	{{zio_checksum_skein_native, zio_checksum_skein_byteswap},
1334a04e8dbSToomas Soome 	    zio_checksum_skein_tmpl_init, zio_checksum_skein_tmpl_free,
1344a04e8dbSToomas Soome 	    ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_DEDUP |
1354a04e8dbSToomas Soome 	    ZCHECKSUM_FLAG_SALTED | ZCHECKSUM_FLAG_NOPWRITE, "skein"},
1364a04e8dbSToomas Soome 	{{zio_checksum_edonr_native, zio_checksum_edonr_byteswap},
1374a04e8dbSToomas Soome 	    zio_checksum_edonr_tmpl_init, zio_checksum_edonr_tmpl_free,
1384a04e8dbSToomas Soome 	    ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_SALTED |
1394a04e8dbSToomas Soome 	    ZCHECKSUM_FLAG_NOPWRITE, "edonr"},
140199767f8SToomas Soome };
141199767f8SToomas Soome 
142199767f8SToomas Soome /*
143199767f8SToomas Soome  * Common signature for all zio compress/decompress functions.
144199767f8SToomas Soome  */
145199767f8SToomas Soome typedef size_t zio_compress_func_t(void *src, void *dst,
146199767f8SToomas Soome     size_t s_len, size_t d_len, int);
147199767f8SToomas Soome typedef int zio_decompress_func_t(void *src, void *dst,
148199767f8SToomas Soome     size_t s_len, size_t d_len, int);
149199767f8SToomas Soome 
150199767f8SToomas Soome extern int gzip_decompress(void *src, void *dst,
151199767f8SToomas Soome     size_t s_len, size_t d_len, int);
152199767f8SToomas Soome /*
153199767f8SToomas Soome  * Information about each compression function.
154199767f8SToomas Soome  */
155199767f8SToomas Soome typedef struct zio_compress_info {
156199767f8SToomas Soome 	zio_compress_func_t	*ci_compress;	/* compression function */
157199767f8SToomas Soome 	zio_decompress_func_t	*ci_decompress;	/* decompression function */
158199767f8SToomas Soome 	int			ci_level;	/* level parameter */
159199767f8SToomas Soome 	const char		*ci_name;	/* algorithm name */
160199767f8SToomas Soome } zio_compress_info_t;
161199767f8SToomas Soome 
162199767f8SToomas Soome #include "lzjb.c"
163199767f8SToomas Soome #include "zle.c"
164199767f8SToomas Soome 
165199767f8SToomas Soome /*
166199767f8SToomas Soome  * Compression vectors.
167199767f8SToomas Soome  */
168199767f8SToomas Soome static zio_compress_info_t zio_compress_table[ZIO_COMPRESS_FUNCTIONS] = {
169199767f8SToomas Soome 	{NULL,			NULL,			0,	"inherit"},
170199767f8SToomas Soome 	{NULL,			NULL,			0,	"on"},
171199767f8SToomas Soome 	{NULL,			NULL,			0,	"uncompressed"},
172199767f8SToomas Soome 	{NULL,			lzjb_decompress,	0,	"lzjb"},
173199767f8SToomas Soome 	{NULL,			NULL,			0,	"empty"},
174199767f8SToomas Soome 	{NULL,			gzip_decompress,	1,	"gzip-1"},
175199767f8SToomas Soome 	{NULL,			gzip_decompress,	2,	"gzip-2"},
176199767f8SToomas Soome 	{NULL,			gzip_decompress,	3,	"gzip-3"},
177199767f8SToomas Soome 	{NULL,			gzip_decompress,	4,	"gzip-4"},
178199767f8SToomas Soome 	{NULL,			gzip_decompress,	5,	"gzip-5"},
179199767f8SToomas Soome 	{NULL,			gzip_decompress,	6,	"gzip-6"},
180199767f8SToomas Soome 	{NULL,			gzip_decompress,	7,	"gzip-7"},
181199767f8SToomas Soome 	{NULL,			gzip_decompress,	8,	"gzip-8"},
182199767f8SToomas Soome 	{NULL,			gzip_decompress,	9,	"gzip-9"},
183199767f8SToomas Soome 	{NULL,			zle_decompress,		64,	"zle"},
184199767f8SToomas Soome 	{NULL,			lz4_decompress,		0,	"lz4"},
185199767f8SToomas Soome };
186199767f8SToomas Soome 
187199767f8SToomas Soome static void
byteswap_uint64_array(void * vbuf,size_t size)188199767f8SToomas Soome byteswap_uint64_array(void *vbuf, size_t size)
189199767f8SToomas Soome {
190199767f8SToomas Soome 	uint64_t *buf = vbuf;
191199767f8SToomas Soome 	size_t count = size >> 3;
192199767f8SToomas Soome 	int i;
193199767f8SToomas Soome 
194199767f8SToomas Soome 	ASSERT((size & 7) == 0);
195199767f8SToomas Soome 
196199767f8SToomas Soome 	for (i = 0; i < count; i++)
197199767f8SToomas Soome 		buf[i] = BSWAP_64(buf[i]);
198199767f8SToomas Soome }
199199767f8SToomas Soome 
200199767f8SToomas Soome /*
201199767f8SToomas Soome  * Set the external verifier for a gang block based on <vdev, offset, txg>,
202199767f8SToomas Soome  * a tuple which is guaranteed to be unique for the life of the pool.
203199767f8SToomas Soome  */
204199767f8SToomas Soome static void
zio_checksum_gang_verifier(zio_cksum_t * zcp,const blkptr_t * bp)205199767f8SToomas Soome zio_checksum_gang_verifier(zio_cksum_t *zcp, const blkptr_t *bp)
206199767f8SToomas Soome {
207199767f8SToomas Soome 	const dva_t *dva = BP_IDENTITY(bp);
208199767f8SToomas Soome 	uint64_t txg = BP_PHYSICAL_BIRTH(bp);
209199767f8SToomas Soome 
210199767f8SToomas Soome 	ASSERT(BP_IS_GANG(bp));
211199767f8SToomas Soome 
212199767f8SToomas Soome 	ZIO_SET_CHECKSUM(zcp, DVA_GET_VDEV(dva), DVA_GET_OFFSET(dva), txg, 0);
213199767f8SToomas Soome }
214199767f8SToomas Soome 
215199767f8SToomas Soome /*
216199767f8SToomas Soome  * Set the external verifier for a label block based on its offset.
217199767f8SToomas Soome  * The vdev is implicit, and the txg is unknowable at pool open time --
218199767f8SToomas Soome  * hence the logic in vdev_uberblock_load() to find the most recent copy.
219199767f8SToomas Soome  */
220199767f8SToomas Soome static void
zio_checksum_label_verifier(zio_cksum_t * zcp,uint64_t offset)221199767f8SToomas Soome zio_checksum_label_verifier(zio_cksum_t *zcp, uint64_t offset)
222199767f8SToomas Soome {
223199767f8SToomas Soome 	ZIO_SET_CHECKSUM(zcp, offset, 0, 0, 0);
224199767f8SToomas Soome }
225199767f8SToomas Soome 
226199767f8SToomas Soome /*
227199767f8SToomas Soome  * Calls the template init function of a checksum which supports context
228199767f8SToomas Soome  * templates and installs the template into the spa_t.
229199767f8SToomas Soome  */
230199767f8SToomas Soome static void
zio_checksum_template_init(enum zio_checksum checksum,spa_t * spa)2314a04e8dbSToomas Soome zio_checksum_template_init(enum zio_checksum checksum, spa_t *spa)
232199767f8SToomas Soome {
233199767f8SToomas Soome 	zio_checksum_info_t *ci = &zio_checksum_table[checksum];
234199767f8SToomas Soome 
235199767f8SToomas Soome 	if (ci->ci_tmpl_init == NULL)
236199767f8SToomas Soome 		return;
2374a04e8dbSToomas Soome 
238199767f8SToomas Soome 	if (spa->spa_cksum_tmpls[checksum] != NULL)
239199767f8SToomas Soome 		return;
240199767f8SToomas Soome 
241199767f8SToomas Soome 	if (spa->spa_cksum_tmpls[checksum] == NULL) {
242199767f8SToomas Soome 		spa->spa_cksum_tmpls[checksum] =
243199767f8SToomas Soome 		    ci->ci_tmpl_init(&spa->spa_cksum_salt);
244199767f8SToomas Soome 	}
2454a04e8dbSToomas Soome }
2464a04e8dbSToomas Soome 
2474a04e8dbSToomas Soome /*
2484a04e8dbSToomas Soome  * Called by a spa_t that's about to be deallocated. This steps through
2494a04e8dbSToomas Soome  * all of the checksum context templates and deallocates any that were
2504a04e8dbSToomas Soome  * initialized using the algorithm-specific template init function.
2514a04e8dbSToomas Soome  */
2524a04e8dbSToomas Soome void
zio_checksum_templates_free(spa_t * spa)2534a04e8dbSToomas Soome zio_checksum_templates_free(spa_t *spa)
2544a04e8dbSToomas Soome {
2554a04e8dbSToomas Soome 	for (enum zio_checksum checksum = 0;
2564a04e8dbSToomas Soome 	    checksum < ZIO_CHECKSUM_FUNCTIONS; checksum++) {
2574a04e8dbSToomas Soome 		if (spa->spa_cksum_tmpls[checksum] != NULL) {
2584a04e8dbSToomas Soome 			zio_checksum_info_t *ci = &zio_checksum_table[checksum];
2594a04e8dbSToomas Soome 
2604a04e8dbSToomas Soome 			ci->ci_tmpl_free(spa->spa_cksum_tmpls[checksum]);
2614a04e8dbSToomas Soome 			spa->spa_cksum_tmpls[checksum] = NULL;
2624a04e8dbSToomas Soome 		}
2634a04e8dbSToomas Soome 	}
264199767f8SToomas Soome }
265199767f8SToomas Soome 
266199767f8SToomas Soome static int
zio_checksum_verify(const spa_t * spa,const blkptr_t * bp,void * data)2674a04e8dbSToomas Soome zio_checksum_verify(const spa_t *spa, const blkptr_t *bp, void *data)
268199767f8SToomas Soome {
269199767f8SToomas Soome 	uint64_t size;
270199767f8SToomas Soome 	unsigned int checksum;
271199767f8SToomas Soome 	zio_checksum_info_t *ci;
2724a04e8dbSToomas Soome 	void *ctx = NULL;
273199767f8SToomas Soome 	zio_cksum_t actual_cksum, expected_cksum, verifier;
274199767f8SToomas Soome 	int byteswap;
275199767f8SToomas Soome 
276199767f8SToomas Soome 	checksum = BP_GET_CHECKSUM(bp);
277199767f8SToomas Soome 	size = BP_GET_PSIZE(bp);
278199767f8SToomas Soome 
279199767f8SToomas Soome 	if (checksum >= ZIO_CHECKSUM_FUNCTIONS)
280199767f8SToomas Soome 		return (EINVAL);
281199767f8SToomas Soome 	ci = &zio_checksum_table[checksum];
282199767f8SToomas Soome 	if (ci->ci_func[0] == NULL || ci->ci_func[1] == NULL)
283199767f8SToomas Soome 		return (EINVAL);
284199767f8SToomas Soome 
2854a04e8dbSToomas Soome 	if (spa != NULL) {
2867bbcfb41SToomas Soome 		zio_checksum_template_init(checksum, (spa_t *)spa);
2874a04e8dbSToomas Soome 		ctx = spa->spa_cksum_tmpls[checksum];
2884a04e8dbSToomas Soome 	}
2894a04e8dbSToomas Soome 
290199767f8SToomas Soome 	if (ci->ci_flags & ZCHECKSUM_FLAG_EMBEDDED) {
291199767f8SToomas Soome 		zio_eck_t *eck;
292199767f8SToomas Soome 
293199767f8SToomas Soome 		ASSERT(checksum == ZIO_CHECKSUM_GANG_HEADER ||
294199767f8SToomas Soome 		    checksum == ZIO_CHECKSUM_LABEL);
295199767f8SToomas Soome 
296199767f8SToomas Soome 		eck = (zio_eck_t *)((char *)data + size) - 1;
297199767f8SToomas Soome 
298199767f8SToomas Soome 		if (checksum == ZIO_CHECKSUM_GANG_HEADER)
299199767f8SToomas Soome 			zio_checksum_gang_verifier(&verifier, bp);
300199767f8SToomas Soome 		else if (checksum == ZIO_CHECKSUM_LABEL)
301199767f8SToomas Soome 			zio_checksum_label_verifier(&verifier,
302199767f8SToomas Soome 			    DVA_GET_OFFSET(BP_IDENTITY(bp)));
303199767f8SToomas Soome 		else
304199767f8SToomas Soome 			verifier = bp->blk_cksum;
305199767f8SToomas Soome 
306199767f8SToomas Soome 		byteswap = (eck->zec_magic == BSWAP_64(ZEC_MAGIC));
307199767f8SToomas Soome 
308199767f8SToomas Soome 		if (byteswap)
309199767f8SToomas Soome 			byteswap_uint64_array(&verifier, sizeof (zio_cksum_t));
310199767f8SToomas Soome 
311199767f8SToomas Soome 		expected_cksum = eck->zec_cksum;
312199767f8SToomas Soome 		eck->zec_cksum = verifier;
3134a04e8dbSToomas Soome 		ci->ci_func[byteswap](data, size, ctx, &actual_cksum);
314199767f8SToomas Soome 		eck->zec_cksum = expected_cksum;
315199767f8SToomas Soome 
316199767f8SToomas Soome 		if (byteswap)
317199767f8SToomas Soome 			byteswap_uint64_array(&expected_cksum,
318199767f8SToomas Soome 			    sizeof (zio_cksum_t));
319199767f8SToomas Soome 	} else {
320ece0bc84SToomas Soome 		byteswap = BP_SHOULD_BYTESWAP(bp);
321199767f8SToomas Soome 		expected_cksum = bp->blk_cksum;
322ece0bc84SToomas Soome 		ci->ci_func[byteswap](data, size, ctx, &actual_cksum);
323199767f8SToomas Soome 	}
324199767f8SToomas Soome 
325199767f8SToomas Soome 	if (!ZIO_CHECKSUM_EQUAL(actual_cksum, expected_cksum)) {
3264a04e8dbSToomas Soome 		/* printf("ZFS: read checksum %s failed\n", ci->ci_name); */
327199767f8SToomas Soome 		return (EIO);
328199767f8SToomas Soome 	}
329199767f8SToomas Soome 
330199767f8SToomas Soome 	return (0);
331199767f8SToomas Soome }
332199767f8SToomas Soome 
333199767f8SToomas Soome static int
zio_decompress_data(int cpfunc,void * src,uint64_t srcsize,void * dest,uint64_t destsize)334199767f8SToomas Soome zio_decompress_data(int cpfunc, void *src, uint64_t srcsize,
3357bbcfb41SToomas Soome     void *dest, uint64_t destsize)
336199767f8SToomas Soome {
337199767f8SToomas Soome 	zio_compress_info_t *ci;
338199767f8SToomas Soome 
339199767f8SToomas Soome 	if (cpfunc >= ZIO_COMPRESS_FUNCTIONS) {
340199767f8SToomas Soome 		printf("ZFS: unsupported compression algorithm %u\n", cpfunc);
341199767f8SToomas Soome 		return (EIO);
342199767f8SToomas Soome 	}
343199767f8SToomas Soome 
344199767f8SToomas Soome 	ci = &zio_compress_table[cpfunc];
345199767f8SToomas Soome 	if (!ci->ci_decompress) {
346199767f8SToomas Soome 		printf("ZFS: unsupported compression algorithm %s\n",
347199767f8SToomas Soome 		    ci->ci_name);
348199767f8SToomas Soome 		return (EIO);
349199767f8SToomas Soome 	}
350199767f8SToomas Soome 
351199767f8SToomas Soome 	return (ci->ci_decompress(src, dest, srcsize, destsize, ci->ci_level));
352199767f8SToomas Soome }
353199767f8SToomas Soome 
354199767f8SToomas Soome static uint64_t
zap_hash(uint64_t salt,const char * name)355199767f8SToomas Soome zap_hash(uint64_t salt, const char *name)
356199767f8SToomas Soome {
357199767f8SToomas Soome 	const uint8_t *cp;
358199767f8SToomas Soome 	uint8_t c;
359199767f8SToomas Soome 	uint64_t crc = salt;
360199767f8SToomas Soome 
361199767f8SToomas Soome 	ASSERT(crc != 0);
362199767f8SToomas Soome 	ASSERT(zfs_crc64_table[128] == ZFS_CRC64_POLY);
363199767f8SToomas Soome 	for (cp = (const uint8_t *)name; (c = *cp) != '\0'; cp++)
364199767f8SToomas Soome 		crc = (crc >> 8) ^ zfs_crc64_table[(crc ^ c) & 0xFF];
365199767f8SToomas Soome 
366199767f8SToomas Soome 	/*
367199767f8SToomas Soome 	 * Only use 28 bits, since we need 4 bits in the cookie for the
368199767f8SToomas Soome 	 * collision differentiator.  We MUST use the high bits, since
369199767f8SToomas Soome 	 * those are the onces that we first pay attention to when
370199767f8SToomas Soome 	 * chosing the bucket.
371199767f8SToomas Soome 	 */
372199767f8SToomas Soome 	crc &= ~((1ULL << (64 - ZAP_HASHBITS)) - 1);
373199767f8SToomas Soome 
374199767f8SToomas Soome 	return (crc);
375199767f8SToomas Soome }
376199767f8SToomas Soome 
377199767f8SToomas Soome typedef struct raidz_col {
378199767f8SToomas Soome 	uint64_t rc_devidx;		/* child device index for I/O */
379199767f8SToomas Soome 	uint64_t rc_offset;		/* device offset */
380199767f8SToomas Soome 	uint64_t rc_size;		/* I/O size */
381199767f8SToomas Soome 	void *rc_data;			/* I/O data */
382199767f8SToomas Soome 	int rc_error;			/* I/O error for this device */
383199767f8SToomas Soome 	uint8_t rc_tried;		/* Did we attempt this I/O column? */
384199767f8SToomas Soome 	uint8_t rc_skipped;		/* Did we skip this I/O column? */
385199767f8SToomas Soome } raidz_col_t;
386199767f8SToomas Soome 
387199767f8SToomas Soome typedef struct raidz_map {
388199767f8SToomas Soome 	uint64_t rm_cols;		/* Regular column count */
389199767f8SToomas Soome 	uint64_t rm_scols;		/* Count including skipped columns */
390199767f8SToomas Soome 	uint64_t rm_bigcols;		/* Number of oversized columns */
391199767f8SToomas Soome 	uint64_t rm_asize;		/* Actual total I/O size */
392199767f8SToomas Soome 	uint64_t rm_missingdata;	/* Count of missing data devices */
393199767f8SToomas Soome 	uint64_t rm_missingparity;	/* Count of missing parity devices */
394199767f8SToomas Soome 	uint64_t rm_firstdatacol;	/* First data column/parity count */
395199767f8SToomas Soome 	uint64_t rm_nskip;		/* Skipped sectors for padding */
396199767f8SToomas Soome 	uint64_t rm_skipstart;		/* Column index of padding start */
397199767f8SToomas Soome 	uintptr_t rm_reports;		/* # of referencing checksum reports */
398199767f8SToomas Soome 	uint8_t	rm_freed;		/* map no longer has referencing ZIO */
399199767f8SToomas Soome 	uint8_t	rm_ecksuminjected;	/* checksum error was injected */
400199767f8SToomas Soome 	raidz_col_t rm_col[1];		/* Flexible array of I/O columns */
401199767f8SToomas Soome } raidz_map_t;
402199767f8SToomas Soome 
403199767f8SToomas Soome #define	VDEV_RAIDZ_P		0
404199767f8SToomas Soome #define	VDEV_RAIDZ_Q		1
405199767f8SToomas Soome #define	VDEV_RAIDZ_R		2
406199767f8SToomas Soome 
407199767f8SToomas Soome #define	VDEV_RAIDZ_MUL_2(x)	(((x) << 1) ^ (((x) & 0x80) ? 0x1d : 0))
408199767f8SToomas Soome #define	VDEV_RAIDZ_MUL_4(x)	(VDEV_RAIDZ_MUL_2(VDEV_RAIDZ_MUL_2(x)))
409199767f8SToomas Soome 
410199767f8SToomas Soome /*
411199767f8SToomas Soome  * We provide a mechanism to perform the field multiplication operation on a
412199767f8SToomas Soome  * 64-bit value all at once rather than a byte at a time. This works by
413199767f8SToomas Soome  * creating a mask from the top bit in each byte and using that to
414199767f8SToomas Soome  * conditionally apply the XOR of 0x1d.
415199767f8SToomas Soome  */
416199767f8SToomas Soome #define	VDEV_RAIDZ_64MUL_2(x, mask) \
417199767f8SToomas Soome { \
418199767f8SToomas Soome 	(mask) = (x) & 0x8080808080808080ULL; \
419199767f8SToomas Soome 	(mask) = ((mask) << 1) - ((mask) >> 7); \
420199767f8SToomas Soome 	(x) = (((x) << 1) & 0xfefefefefefefefeULL) ^ \
421199767f8SToomas Soome 	    ((mask) & 0x1d1d1d1d1d1d1d1dULL); \
422199767f8SToomas Soome }
423199767f8SToomas Soome 
424199767f8SToomas Soome #define	VDEV_RAIDZ_64MUL_4(x, mask) \
425199767f8SToomas Soome { \
426199767f8SToomas Soome 	VDEV_RAIDZ_64MUL_2((x), mask); \
427199767f8SToomas Soome 	VDEV_RAIDZ_64MUL_2((x), mask); \
428199767f8SToomas Soome }
429199767f8SToomas Soome 
430199767f8SToomas Soome /*
431199767f8SToomas Soome  * These two tables represent powers and logs of 2 in the Galois field defined
432199767f8SToomas Soome  * above. These values were computed by repeatedly multiplying by 2 as above.
433199767f8SToomas Soome  */
434199767f8SToomas Soome static const uint8_t vdev_raidz_pow2[256] = {
435199767f8SToomas Soome 	0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
436199767f8SToomas Soome 	0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
437199767f8SToomas Soome 	0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9,
438199767f8SToomas Soome 	0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
439199767f8SToomas Soome 	0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35,
440199767f8SToomas Soome 	0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
441199767f8SToomas Soome 	0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0,
442199767f8SToomas Soome 	0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
443199767f8SToomas Soome 	0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc,
444199767f8SToomas Soome 	0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
445199767f8SToomas Soome 	0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f,
446199767f8SToomas Soome 	0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
447199767f8SToomas Soome 	0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88,
448199767f8SToomas Soome 	0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
449199767f8SToomas Soome 	0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93,
450199767f8SToomas Soome 	0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
451199767f8SToomas Soome 	0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9,
452199767f8SToomas Soome 	0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
453199767f8SToomas Soome 	0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa,
454199767f8SToomas Soome 	0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
455199767f8SToomas Soome 	0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e,
456199767f8SToomas Soome 	0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
457199767f8SToomas Soome 	0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4,
458199767f8SToomas Soome 	0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
459199767f8SToomas Soome 	0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e,
460199767f8SToomas Soome 	0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
461199767f8SToomas Soome 	0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef,
462199767f8SToomas Soome 	0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
463199767f8SToomas Soome 	0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5,
464199767f8SToomas Soome 	0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
465199767f8SToomas Soome 	0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83,
466199767f8SToomas Soome 	0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01
467199767f8SToomas Soome };
468199767f8SToomas Soome static const uint8_t vdev_raidz_log2[256] = {
469199767f8SToomas Soome 	0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6,
470199767f8SToomas Soome 	0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
471199767f8SToomas Soome 	0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81,
472199767f8SToomas Soome 	0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
473199767f8SToomas Soome 	0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21,
474199767f8SToomas Soome 	0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
475199767f8SToomas Soome 	0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9,
476199767f8SToomas Soome 	0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
477199767f8SToomas Soome 	0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd,
478199767f8SToomas Soome 	0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
479199767f8SToomas Soome 	0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd,
480199767f8SToomas Soome 	0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
481199767f8SToomas Soome 	0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e,
482199767f8SToomas Soome 	0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
483199767f8SToomas Soome 	0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b,
484199767f8SToomas Soome 	0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
485199767f8SToomas Soome 	0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d,
486199767f8SToomas Soome 	0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
487199767f8SToomas Soome 	0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c,
488199767f8SToomas Soome 	0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
489199767f8SToomas Soome 	0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd,
490199767f8SToomas Soome 	0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
491199767f8SToomas Soome 	0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e,
492199767f8SToomas Soome 	0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
493199767f8SToomas Soome 	0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76,
494199767f8SToomas Soome 	0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
495199767f8SToomas Soome 	0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa,
496199767f8SToomas Soome 	0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
497199767f8SToomas Soome 	0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51,
498199767f8SToomas Soome 	0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
499199767f8SToomas Soome 	0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8,
500199767f8SToomas Soome 	0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf,
501199767f8SToomas Soome };
502199767f8SToomas Soome 
503199767f8SToomas Soome /*
504199767f8SToomas Soome  * Multiply a given number by 2 raised to the given power.
505199767f8SToomas Soome  */
506199767f8SToomas Soome static uint8_t
vdev_raidz_exp2(uint8_t a,int exp)507199767f8SToomas Soome vdev_raidz_exp2(uint8_t a, int exp)
508199767f8SToomas Soome {
509199767f8SToomas Soome 	if (a == 0)
510199767f8SToomas Soome 		return (0);
511199767f8SToomas Soome 
512199767f8SToomas Soome 	ASSERT(exp >= 0);
513199767f8SToomas Soome 	ASSERT(vdev_raidz_log2[a] > 0 || a == 1);
514199767f8SToomas Soome 
515199767f8SToomas Soome 	exp += vdev_raidz_log2[a];
516199767f8SToomas Soome 	if (exp > 255)
517199767f8SToomas Soome 		exp -= 255;
518199767f8SToomas Soome 
519199767f8SToomas Soome 	return (vdev_raidz_pow2[exp]);
520199767f8SToomas Soome }
521199767f8SToomas Soome 
522199767f8SToomas Soome static void
vdev_raidz_generate_parity_p(raidz_map_t * rm)523199767f8SToomas Soome vdev_raidz_generate_parity_p(raidz_map_t *rm)
524199767f8SToomas Soome {
525199767f8SToomas Soome 	uint64_t *p, *src, pcount __attribute__((unused)), ccount, i;
526199767f8SToomas Soome 	int c;
527199767f8SToomas Soome 
528199767f8SToomas Soome 	pcount = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]);
529199767f8SToomas Soome 
530199767f8SToomas Soome 	for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
531199767f8SToomas Soome 		src = rm->rm_col[c].rc_data;
532199767f8SToomas Soome 		p = rm->rm_col[VDEV_RAIDZ_P].rc_data;
533199767f8SToomas Soome 		ccount = rm->rm_col[c].rc_size / sizeof (src[0]);
534199767f8SToomas Soome 
535199767f8SToomas Soome 		if (c == rm->rm_firstdatacol) {
536199767f8SToomas Soome 			ASSERT(ccount == pcount);
537199767f8SToomas Soome 			for (i = 0; i < ccount; i++, src++, p++) {
538199767f8SToomas Soome 				*p = *src;
539199767f8SToomas Soome 			}
540199767f8SToomas Soome 		} else {
541199767f8SToomas Soome 			ASSERT(ccount <= pcount);
542199767f8SToomas Soome 			for (i = 0; i < ccount; i++, src++, p++) {
543199767f8SToomas Soome 				*p ^= *src;
544199767f8SToomas Soome 			}
545199767f8SToomas Soome 		}
546199767f8SToomas Soome 	}
547199767f8SToomas Soome }
548199767f8SToomas Soome 
549199767f8SToomas Soome static void
vdev_raidz_generate_parity_pq(raidz_map_t * rm)550199767f8SToomas Soome vdev_raidz_generate_parity_pq(raidz_map_t *rm)
551199767f8SToomas Soome {
552199767f8SToomas Soome 	uint64_t *p, *q, *src, pcnt, ccnt, mask, i;
553199767f8SToomas Soome 	int c;
554199767f8SToomas Soome 
555199767f8SToomas Soome 	pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]);
556199767f8SToomas Soome 	ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
557199767f8SToomas Soome 	    rm->rm_col[VDEV_RAIDZ_Q].rc_size);
558199767f8SToomas Soome 
559199767f8SToomas Soome 	for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
560199767f8SToomas Soome 		src = rm->rm_col[c].rc_data;
561199767f8SToomas Soome 		p = rm->rm_col[VDEV_RAIDZ_P].rc_data;
562199767f8SToomas Soome 		q = rm->rm_col[VDEV_RAIDZ_Q].rc_data;
563199767f8SToomas Soome 
564199767f8SToomas Soome 		ccnt = rm->rm_col[c].rc_size / sizeof (src[0]);
565199767f8SToomas Soome 
566199767f8SToomas Soome 		if (c == rm->rm_firstdatacol) {
567199767f8SToomas Soome 			ASSERT(ccnt == pcnt || ccnt == 0);
568199767f8SToomas Soome 			for (i = 0; i < ccnt; i++, src++, p++, q++) {
569199767f8SToomas Soome 				*p = *src;
570199767f8SToomas Soome 				*q = *src;
571199767f8SToomas Soome 			}
572199767f8SToomas Soome 			for (; i < pcnt; i++, src++, p++, q++) {
573199767f8SToomas Soome 				*p = 0;
574199767f8SToomas Soome 				*q = 0;
575199767f8SToomas Soome 			}
576199767f8SToomas Soome 		} else {
577199767f8SToomas Soome 			ASSERT(ccnt <= pcnt);
578199767f8SToomas Soome 
579199767f8SToomas Soome 			/*
580199767f8SToomas Soome 			 * Apply the algorithm described above by multiplying
581199767f8SToomas Soome 			 * the previous result and adding in the new value.
582199767f8SToomas Soome 			 */
583199767f8SToomas Soome 			for (i = 0; i < ccnt; i++, src++, p++, q++) {
584199767f8SToomas Soome 				*p ^= *src;
585199767f8SToomas Soome 
586199767f8SToomas Soome 				VDEV_RAIDZ_64MUL_2(*q, mask);
587199767f8SToomas Soome 				*q ^= *src;
588199767f8SToomas Soome 			}
589199767f8SToomas Soome 
590199767f8SToomas Soome 			/*
591199767f8SToomas Soome 			 * Treat short columns as though they are full of 0s.
592199767f8SToomas Soome 			 * Note that there's therefore nothing needed for P.
593199767f8SToomas Soome 			 */
594199767f8SToomas Soome 			for (; i < pcnt; i++, q++) {
595199767f8SToomas Soome 				VDEV_RAIDZ_64MUL_2(*q, mask);
596199767f8SToomas Soome 			}
597199767f8SToomas Soome 		}
598199767f8SToomas Soome 	}
599199767f8SToomas Soome }
600199767f8SToomas Soome 
601199767f8SToomas Soome static void
vdev_raidz_generate_parity_pqr(raidz_map_t * rm)602199767f8SToomas Soome vdev_raidz_generate_parity_pqr(raidz_map_t *rm)
603199767f8SToomas Soome {
604199767f8SToomas Soome 	uint64_t *p, *q, *r, *src, pcnt, ccnt, mask, i;
605199767f8SToomas Soome 	int c;
606199767f8SToomas Soome 
607199767f8SToomas Soome 	pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]);
608199767f8SToomas Soome 	ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
609199767f8SToomas Soome 	    rm->rm_col[VDEV_RAIDZ_Q].rc_size);
610199767f8SToomas Soome 	ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size ==
611199767f8SToomas Soome 	    rm->rm_col[VDEV_RAIDZ_R].rc_size);
612199767f8SToomas Soome 
613199767f8SToomas Soome 	for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) {
614199767f8SToomas Soome 		src = rm->rm_col[c].rc_data;
615199767f8SToomas Soome 		p = rm->rm_col[VDEV_RAIDZ_P].rc_data;
616199767f8SToomas Soome 		q = rm->rm_col[VDEV_RAIDZ_Q].rc_data;
617199767f8SToomas Soome 		r = rm->rm_col[VDEV_RAIDZ_R].rc_data;
618199767f8SToomas Soome 
619199767f8SToomas Soome 		ccnt = rm->rm_col[c].rc_size / sizeof (src[0]);
620199767f8SToomas Soome 
621199767f8SToomas Soome 		if (c == rm->rm_firstdatacol) {
622199767f8SToomas Soome 			ASSERT(ccnt == pcnt || ccnt == 0);
623199767f8SToomas Soome 			for (i = 0; i < ccnt; i++, src++, p++, q++, r++) {
624199767f8SToomas Soome 				*p = *src;
625199767f8SToomas Soome 				*q = *src;
626199767f8SToomas Soome 				*r = *src;
627199767f8SToomas Soome 			}
628199767f8SToomas Soome 			for (; i < pcnt; i++, src++, p++, q++, r++) {
629199767f8SToomas Soome 				*p = 0;
630199767f8SToomas Soome 				*q = 0;
631199767f8SToomas Soome 				*r = 0;
632199767f8SToomas Soome 			}
633199767f8SToomas Soome 		} else {
634199767f8SToomas Soome 			ASSERT(ccnt <= pcnt);
635199767f8SToomas Soome 
636199767f8SToomas Soome 			/*
637199767f8SToomas Soome 			 * Apply the algorithm described above by multiplying
638199767f8SToomas Soome 			 * the previous result and adding in the new value.
639199767f8SToomas Soome 			 */
640199767f8SToomas Soome 			for (i = 0; i < ccnt; i++, src++, p++, q++, r++) {
641199767f8SToomas Soome 				*p ^= *src;
642199767f8SToomas Soome 
643199767f8SToomas Soome 				VDEV_RAIDZ_64MUL_2(*q, mask);
644199767f8SToomas Soome 				*q ^= *src;
645199767f8SToomas Soome 
646199767f8SToomas Soome 				VDEV_RAIDZ_64MUL_4(*r, mask);
647199767f8SToomas Soome 				*r ^= *src;
648199767f8SToomas Soome 			}
649199767f8SToomas Soome 
650199767f8SToomas Soome 			/*
651199767f8SToomas Soome 			 * Treat short columns as though they are full of 0s.
652199767f8SToomas Soome 			 * Note that there's therefore nothing needed for P.
653199767f8SToomas Soome 			 */
654199767f8SToomas Soome 			for (; i < pcnt; i++, q++, r++) {
655199767f8SToomas Soome 				VDEV_RAIDZ_64MUL_2(*q, mask);
656199767f8SToomas Soome 				VDEV_RAIDZ_64MUL_4(*r, mask);
657199767f8SToomas Soome 			}
658199767f8SToomas Soome 		}
659199767f8SToomas Soome 	}
660199767f8SToomas Soome }
661199767f8SToomas Soome 
662199767f8SToomas Soome /*
663199767f8SToomas Soome  * Generate RAID parity in the first virtual columns according to the number of
664199767f8SToomas Soome  * parity columns available.
665199767f8SToomas Soome  */
666199767f8SToomas Soome static void
vdev_raidz_generate_parity(raidz_map_t * rm)667199767f8SToomas Soome vdev_raidz_generate_parity(raidz_map_t *rm)
668199767f8SToomas Soome {
669199767f8SToomas Soome 	switch (rm->rm_firstdatacol) {
670199767f8SToomas Soome 	case 1:
671199767f8SToomas Soome 		vdev_raidz_generate_parity_p(rm);
672199767f8SToomas Soome 		break;
673199767f8SToomas Soome 	case 2:
674199767f8SToomas Soome 		vdev_raidz_generate_parity_pq(rm);
675199767f8SToomas Soome 		break;
676199767f8SToomas Soome 	case 3:
677199767f8SToomas Soome 		vdev_raidz_generate_parity_pqr(rm);
678199767f8SToomas Soome 		break;
679199767f8SToomas Soome 	default:
680199767f8SToomas Soome 		panic("invalid RAID-Z configuration");
681199767f8SToomas Soome 	}
682199767f8SToomas Soome }
683199767f8SToomas Soome 
684199767f8SToomas Soome /* BEGIN CSTYLED */
685199767f8SToomas Soome /*
686199767f8SToomas Soome  * In the general case of reconstruction, we must solve the system of linear
687199767f8SToomas Soome  * equations defined by the coeffecients used to generate parity as well as
688199767f8SToomas Soome  * the contents of the data and parity disks. This can be expressed with
689199767f8SToomas Soome  * vectors for the original data (D) and the actual data (d) and parity (p)
690199767f8SToomas Soome  * and a matrix composed of the identity matrix (I) and a dispersal matrix (V):
691199767f8SToomas Soome  *
692199767f8SToomas Soome  *            __   __                     __     __
693199767f8SToomas Soome  *            |     |         __     __   |  p_0  |
694199767f8SToomas Soome  *            |  V  |         |  D_0  |   | p_m-1 |
695199767f8SToomas Soome  *            |     |    x    |   :   | = |  d_0  |
696199767f8SToomas Soome  *            |  I  |         | D_n-1 |   |   :   |
697199767f8SToomas Soome  *            |     |         ~~     ~~   | d_n-1 |
698199767f8SToomas Soome  *            ~~   ~~                     ~~     ~~
699199767f8SToomas Soome  *
700199767f8SToomas Soome  * I is simply a square identity matrix of size n, and V is a vandermonde
701199767f8SToomas Soome  * matrix defined by the coeffecients we chose for the various parity columns
702199767f8SToomas Soome  * (1, 2, 4). Note that these values were chosen both for simplicity, speedy
703199767f8SToomas Soome  * computation as well as linear separability.
704199767f8SToomas Soome  *
705199767f8SToomas Soome  *      __               __               __     __
706199767f8SToomas Soome  *      |   1   ..  1 1 1 |               |  p_0  |
707199767f8SToomas Soome  *      | 2^n-1 ..  4 2 1 |   __     __   |   :   |
708199767f8SToomas Soome  *      | 4^n-1 .. 16 4 1 |   |  D_0  |   | p_m-1 |
709199767f8SToomas Soome  *      |   1   ..  0 0 0 |   |  D_1  |   |  d_0  |
710199767f8SToomas Soome  *      |   0   ..  0 0 0 | x |  D_2  | = |  d_1  |
711199767f8SToomas Soome  *      |   :       : : : |   |   :   |   |  d_2  |
712199767f8SToomas Soome  *      |   0   ..  1 0 0 |   | D_n-1 |   |   :   |
713199767f8SToomas Soome  *      |   0   ..  0 1 0 |   ~~     ~~   |   :   |
714199767f8SToomas Soome  *      |   0   ..  0 0 1 |               | d_n-1 |
715199767f8SToomas Soome  *      ~~               ~~               ~~     ~~
716199767f8SToomas Soome  *
717199767f8SToomas Soome  * Note that I, V, d, and p are known. To compute D, we must invert the
718199767f8SToomas Soome  * matrix and use the known data and parity values to reconstruct the unknown
719199767f8SToomas Soome  * data values. We begin by removing the rows in V|I and d|p that correspond
720199767f8SToomas Soome  * to failed or missing columns; we then make V|I square (n x n) and d|p
721199767f8SToomas Soome  * sized n by removing rows corresponding to unused parity from the bottom up
722199767f8SToomas Soome  * to generate (V|I)' and (d|p)'. We can then generate the inverse of (V|I)'
723199767f8SToomas Soome  * using Gauss-Jordan elimination. In the example below we use m=3 parity
724199767f8SToomas Soome  * columns, n=8 data columns, with errors in d_1, d_2, and p_1:
725199767f8SToomas Soome  *           __                               __
726199767f8SToomas Soome  *           |  1   1   1   1   1   1   1   1  |
727199767f8SToomas Soome  *           | 128  64  32  16  8   4   2   1  | <-----+-+-- missing disks
728199767f8SToomas Soome  *           |  19 205 116  29  64  16  4   1  |      / /
729199767f8SToomas Soome  *           |  1   0   0   0   0   0   0   0  |     / /
730199767f8SToomas Soome  *           |  0   1   0   0   0   0   0   0  | <--' /
731199767f8SToomas Soome  *  (V|I)  = |  0   0   1   0   0   0   0   0  | <---'
732199767f8SToomas Soome  *           |  0   0   0   1   0   0   0   0  |
733199767f8SToomas Soome  *           |  0   0   0   0   1   0   0   0  |
734199767f8SToomas Soome  *           |  0   0   0   0   0   1   0   0  |
735199767f8SToomas Soome  *           |  0   0   0   0   0   0   1   0  |
736199767f8SToomas Soome  *           |  0   0   0   0   0   0   0   1  |
737199767f8SToomas Soome  *           ~~                               ~~
738199767f8SToomas Soome  *           __                               __
739199767f8SToomas Soome  *           |  1   1   1   1   1   1   1   1  |
740199767f8SToomas Soome  *           | 128  64  32  16  8   4   2   1  |
741199767f8SToomas Soome  *           |  19 205 116  29  64  16  4   1  |
742199767f8SToomas Soome  *           |  1   0   0   0   0   0   0   0  |
743199767f8SToomas Soome  *           |  0   1   0   0   0   0   0   0  |
744199767f8SToomas Soome  *  (V|I)' = |  0   0   1   0   0   0   0   0  |
745199767f8SToomas Soome  *           |  0   0   0   1   0   0   0   0  |
746199767f8SToomas Soome  *           |  0   0   0   0   1   0   0   0  |
747199767f8SToomas Soome  *           |  0   0   0   0   0   1   0   0  |
748199767f8SToomas Soome  *           |  0   0   0   0   0   0   1   0  |
749199767f8SToomas Soome  *           |  0   0   0   0   0   0   0   1  |
750199767f8SToomas Soome  *           ~~                               ~~
751199767f8SToomas Soome  *
752199767f8SToomas Soome  * Here we employ Gauss-Jordan elimination to find the inverse of (V|I)'. We
753199767f8SToomas Soome  * have carefully chosen the seed values 1, 2, and 4 to ensure that this
754199767f8SToomas Soome  * matrix is not singular.
755199767f8SToomas Soome  * __                                                                 __
756199767f8SToomas Soome  * |  1   1   1   1   1   1   1   1     1   0   0   0   0   0   0   0  |
757199767f8SToomas Soome  * |  19 205 116  29  64  16  4   1     0   1   0   0   0   0   0   0  |
758199767f8SToomas Soome  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
759199767f8SToomas Soome  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
760199767f8SToomas Soome  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
761199767f8SToomas Soome  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
762199767f8SToomas Soome  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
763199767f8SToomas Soome  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
764199767f8SToomas Soome  * ~~                                                                 ~~
765199767f8SToomas Soome  * __                                                                 __
766199767f8SToomas Soome  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
767199767f8SToomas Soome  * |  1   1   1   1   1   1   1   1     1   0   0   0   0   0   0   0  |
768199767f8SToomas Soome  * |  19 205 116  29  64  16  4   1     0   1   0   0   0   0   0   0  |
769199767f8SToomas Soome  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
770199767f8SToomas Soome  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
771199767f8SToomas Soome  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
772199767f8SToomas Soome  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
773199767f8SToomas Soome  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
774199767f8SToomas Soome  * ~~                                                                 ~~
775199767f8SToomas Soome  * __                                                                 __
776199767f8SToomas Soome  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
777199767f8SToomas Soome  * |  0   1   1   0   0   0   0   0     1   0   1   1   1   1   1   1  |
778199767f8SToomas Soome  * |  0  205 116  0   0   0   0   0     0   1   19  29  64  16  4   1  |
779199767f8SToomas Soome  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
780199767f8SToomas Soome  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
781199767f8SToomas Soome  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
782199767f8SToomas Soome  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
783199767f8SToomas Soome  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
784199767f8SToomas Soome  * ~~                                                                 ~~
785199767f8SToomas Soome  * __                                                                 __
786199767f8SToomas Soome  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
787199767f8SToomas Soome  * |  0   1   1   0   0   0   0   0     1   0   1   1   1   1   1   1  |
788199767f8SToomas Soome  * |  0   0  185  0   0   0   0   0    205  1  222 208 141 221 201 204 |
789199767f8SToomas Soome  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
790199767f8SToomas Soome  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
791199767f8SToomas Soome  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
792199767f8SToomas Soome  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
793199767f8SToomas Soome  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
794199767f8SToomas Soome  * ~~                                                                 ~~
795199767f8SToomas Soome  * __                                                                 __
796199767f8SToomas Soome  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
797199767f8SToomas Soome  * |  0   1   1   0   0   0   0   0     1   0   1   1   1   1   1   1  |
798199767f8SToomas Soome  * |  0   0   1   0   0   0   0   0    166 100  4   40 158 168 216 209 |
799199767f8SToomas Soome  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
800199767f8SToomas Soome  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
801199767f8SToomas Soome  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
802199767f8SToomas Soome  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
803199767f8SToomas Soome  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
804199767f8SToomas Soome  * ~~                                                                 ~~
805199767f8SToomas Soome  * __                                                                 __
806199767f8SToomas Soome  * |  1   0   0   0   0   0   0   0     0   0   1   0   0   0   0   0  |
807199767f8SToomas Soome  * |  0   1   0   0   0   0   0   0    167 100  5   41 159 169 217 208 |
808199767f8SToomas Soome  * |  0   0   1   0   0   0   0   0    166 100  4   40 158 168 216 209 |
809199767f8SToomas Soome  * |  0   0   0   1   0   0   0   0     0   0   0   1   0   0   0   0  |
810199767f8SToomas Soome  * |  0   0   0   0   1   0   0   0     0   0   0   0   1   0   0   0  |
811199767f8SToomas Soome  * |  0   0   0   0   0   1   0   0     0   0   0   0   0   1   0   0  |
812199767f8SToomas Soome  * |  0   0   0   0   0   0   1   0     0   0   0   0   0   0   1   0  |
813199767f8SToomas Soome  * |  0   0   0   0   0   0   0   1     0   0   0   0   0   0   0   1  |
814199767f8SToomas Soome  * ~~                                                                 ~~
815199767f8SToomas Soome  *                   __                               __
816199767f8SToomas Soome  *                   |  0   0   1   0   0   0   0   0  |
817199767f8SToomas Soome  *                   | 167 100  5   41 159 169 217 208 |
818199767f8SToomas Soome  *                   | 166 100  4   40 158 168 216 209 |
819199767f8</