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> 27199767f8SToomas Soome 28199767f8SToomas Soome static uint64_t zfs_crc64_table[256]; 29199767f8SToomas Soome 30199767f8SToomas Soome #define ECKSUM 666 31199767f8SToomas Soome 32199767f8SToomas Soome #define ASSERT3S(x, y, z) ((void)0) 33199767f8SToomas Soome #define ASSERT3U(x, y, z) ((void)0) 34199767f8SToomas Soome #define ASSERT3P(x, y, z) ((void)0) 35199767f8SToomas Soome #define ASSERT0(x) ((void)0) 36199767f8SToomas Soome #define ASSERT(x) ((void)0) 37199767f8SToomas Soome 38199767f8SToomas Soome #define panic(...) do { \ 39199767f8SToomas Soome printf(__VA_ARGS__); \ 40199767f8SToomas Soome for (;;) ; \ 41199767f8SToomas Soome } while (0) 42199767f8SToomas Soome 43199767f8SToomas Soome #define kmem_alloc(size, flag) zfs_alloc((size)) 44199767f8SToomas Soome #define kmem_free(ptr, size) zfs_free((ptr), (size)) 45199767f8SToomas Soome 46199767f8SToomas Soome static void 47199767f8SToomas Soome zfs_init_crc(void) 48199767f8SToomas Soome { 49199767f8SToomas Soome int i, j; 50199767f8SToomas Soome uint64_t *ct; 51199767f8SToomas Soome 52199767f8SToomas Soome /* 53199767f8SToomas Soome * Calculate the crc64 table (used for the zap hash 54199767f8SToomas Soome * function). 55199767f8SToomas Soome */ 56199767f8SToomas Soome if (zfs_crc64_table[128] != ZFS_CRC64_POLY) { 57199767f8SToomas Soome memset(zfs_crc64_table, 0, sizeof(zfs_crc64_table)); 58199767f8SToomas Soome for (i = 0; i < 256; i++) 59199767f8SToomas Soome for (ct = zfs_crc64_table + i, *ct = i, j = 8; j > 0; j--) 60199767f8SToomas Soome *ct = (*ct >> 1) ^ (-(*ct & 1) & ZFS_CRC64_POLY); 61199767f8SToomas Soome } 62199767f8SToomas Soome } 63199767f8SToomas Soome 64199767f8SToomas Soome static void 65199767f8SToomas Soome zio_checksum_off(const void *buf, uint64_t size, 66199767f8SToomas Soome const void *ctx_template, zio_cksum_t *zcp) 67199767f8SToomas Soome { 68199767f8SToomas Soome ZIO_SET_CHECKSUM(zcp, 0, 0, 0, 0); 69199767f8SToomas Soome } 70199767f8SToomas Soome 71199767f8SToomas Soome /* 72199767f8SToomas Soome * Signature for checksum functions. 73199767f8SToomas Soome */ 74199767f8SToomas Soome typedef void zio_checksum_t(const void *data, uint64_t size, 75199767f8SToomas Soome const void *ctx_template, zio_cksum_t *zcp); 76199767f8SToomas Soome typedef void *zio_checksum_tmpl_init_t(const zio_cksum_salt_t *salt); 77199767f8SToomas Soome typedef void zio_checksum_tmpl_free_t(void *ctx_template); 78199767f8SToomas Soome 79199767f8SToomas Soome typedef enum zio_checksum_flags { 80199767f8SToomas Soome /* Strong enough for metadata? */ 81199767f8SToomas Soome ZCHECKSUM_FLAG_METADATA = (1 << 1), 82199767f8SToomas Soome /* ZIO embedded checksum */ 83199767f8SToomas Soome ZCHECKSUM_FLAG_EMBEDDED = (1 << 2), 84199767f8SToomas Soome /* Strong enough for dedup (without verification)? */ 85199767f8SToomas Soome ZCHECKSUM_FLAG_DEDUP = (1 << 3), 86199767f8SToomas Soome /* Uses salt value */ 87199767f8SToomas Soome ZCHECKSUM_FLAG_SALTED = (1 << 4), 88199767f8SToomas Soome /* Strong enough for nopwrite? */ 89199767f8SToomas Soome ZCHECKSUM_FLAG_NOPWRITE = (1 << 5) 90199767f8SToomas Soome } zio_checksum_flags_t; 91199767f8SToomas Soome 92199767f8SToomas Soome /* 93199767f8SToomas Soome * Information about each checksum function. 94199767f8SToomas Soome */ 95199767f8SToomas Soome typedef struct zio_checksum_info { 96199767f8SToomas Soome /* checksum function for each byteorder */ 97199767f8SToomas Soome zio_checksum_t *ci_func[2]; 98199767f8SToomas Soome zio_checksum_tmpl_init_t *ci_tmpl_init; 99199767f8SToomas Soome zio_checksum_tmpl_free_t *ci_tmpl_free; 100199767f8SToomas Soome zio_checksum_flags_t ci_flags; 101199767f8SToomas Soome const char *ci_name; /* descriptive name */ 102199767f8SToomas Soome } zio_checksum_info_t; 103199767f8SToomas Soome 104199767f8SToomas Soome #include "blkptr.c" 105199767f8SToomas Soome 106199767f8SToomas Soome #include "fletcher.c" 107199767f8SToomas Soome #include "sha256.c" 108*4a04e8dbSToomas Soome #include "skein_zfs.c" 109*4a04e8dbSToomas Soome #include "edonr_zfs.c" 110199767f8SToomas Soome 111199767f8SToomas Soome static zio_checksum_info_t zio_checksum_table[ZIO_CHECKSUM_FUNCTIONS] = { 112199767f8SToomas Soome {{NULL, NULL}, NULL, NULL, 0, "inherit"}, 113199767f8SToomas Soome {{NULL, NULL}, NULL, NULL, 0, "on"}, 114199767f8SToomas Soome {{zio_checksum_off, zio_checksum_off}, NULL, NULL, 0, "off"}, 115199767f8SToomas Soome {{zio_checksum_SHA256, zio_checksum_SHA256}, NULL, NULL, 116199767f8SToomas Soome ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_EMBEDDED, "label"}, 117199767f8SToomas Soome {{zio_checksum_SHA256, zio_checksum_SHA256}, NULL, NULL, 118199767f8SToomas Soome ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_EMBEDDED, "gang_header"}, 119199767f8SToomas Soome {{fletcher_2_native, fletcher_2_byteswap}, NULL, NULL, 120199767f8SToomas Soome ZCHECKSUM_FLAG_EMBEDDED, "zilog"}, 121199767f8SToomas Soome {{fletcher_2_native, fletcher_2_byteswap}, NULL, NULL, 122199767f8SToomas Soome 0, "fletcher2"}, 123199767f8SToomas Soome {{fletcher_4_native, fletcher_4_byteswap}, NULL, NULL, 124199767f8SToomas Soome ZCHECKSUM_FLAG_METADATA, "fletcher4"}, 125199767f8SToomas Soome {{zio_checksum_SHA256, zio_checksum_SHA256}, NULL, NULL, 126199767f8SToomas Soome ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_DEDUP | 127199767f8SToomas Soome ZCHECKSUM_FLAG_NOPWRITE, "SHA256"}, 128199767f8SToomas Soome {{fletcher_4_native, fletcher_4_byteswap}, NULL, NULL, 129199767f8SToomas Soome ZCHECKSUM_FLAG_EMBEDDED, "zillog2"}, 130199767f8SToomas Soome {{zio_checksum_off, zio_checksum_off}, NULL, NULL, 131199767f8SToomas Soome 0, "noparity"}, 132199767f8SToomas Soome {{zio_checksum_SHA512_native, zio_checksum_SHA512_byteswap}, 133199767f8SToomas Soome NULL, NULL, ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_DEDUP | 134199767f8SToomas Soome ZCHECKSUM_FLAG_NOPWRITE, "SHA512"}, 135199767f8SToomas Soome /* no skein and edonr for now */ 136*4a04e8dbSToomas Soome {{zio_checksum_skein_native, zio_checksum_skein_byteswap}, 137*4a04e8dbSToomas Soome zio_checksum_skein_tmpl_init, zio_checksum_skein_tmpl_free, 138*4a04e8dbSToomas Soome ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_DEDUP | 139*4a04e8dbSToomas Soome ZCHECKSUM_FLAG_SALTED | ZCHECKSUM_FLAG_NOPWRITE, "skein"}, 140*4a04e8dbSToomas Soome {{zio_checksum_edonr_native, zio_checksum_edonr_byteswap}, 141*4a04e8dbSToomas Soome zio_checksum_edonr_tmpl_init, zio_checksum_edonr_tmpl_free, 142*4a04e8dbSToomas Soome ZCHECKSUM_FLAG_METADATA | ZCHECKSUM_FLAG_SALTED | 143*4a04e8dbSToomas Soome ZCHECKSUM_FLAG_NOPWRITE, "edonr"}, 144199767f8SToomas Soome }; 145199767f8SToomas Soome 146199767f8SToomas Soome /* 147199767f8SToomas Soome * Common signature for all zio compress/decompress functions. 148199767f8SToomas Soome */ 149199767f8SToomas Soome typedef size_t zio_compress_func_t(void *src, void *dst, 150199767f8SToomas Soome size_t s_len, size_t d_len, int); 151199767f8SToomas Soome typedef int zio_decompress_func_t(void *src, void *dst, 152199767f8SToomas Soome size_t s_len, size_t d_len, int); 153199767f8SToomas Soome 154199767f8SToomas Soome extern int gzip_decompress(void *src, void *dst, 155199767f8SToomas Soome size_t s_len, size_t d_len, int); 156199767f8SToomas Soome /* 157199767f8SToomas Soome * Information about each compression function. 158199767f8SToomas Soome */ 159199767f8SToomas Soome typedef struct zio_compress_info { 160199767f8SToomas Soome zio_compress_func_t *ci_compress; /* compression function */ 161199767f8SToomas Soome zio_decompress_func_t *ci_decompress; /* decompression function */ 162199767f8SToomas Soome int ci_level; /* level parameter */ 163199767f8SToomas Soome const char *ci_name; /* algorithm name */ 164199767f8SToomas Soome } zio_compress_info_t; 165199767f8SToomas Soome 166199767f8SToomas Soome #include "lzjb.c" 167199767f8SToomas Soome #include "zle.c" 168199767f8SToomas Soome #include "lz4.c" 169199767f8SToomas Soome 170199767f8SToomas Soome /* 171199767f8SToomas Soome * Compression vectors. 172199767f8SToomas Soome */ 173199767f8SToomas Soome static zio_compress_info_t zio_compress_table[ZIO_COMPRESS_FUNCTIONS] = { 174199767f8SToomas Soome {NULL, NULL, 0, "inherit"}, 175199767f8SToomas Soome {NULL, NULL, 0, "on"}, 176199767f8SToomas Soome {NULL, NULL, 0, "uncompressed"}, 177199767f8SToomas Soome {NULL, lzjb_decompress, 0, "lzjb"}, 178199767f8SToomas Soome {NULL, NULL, 0, "empty"}, 179199767f8SToomas Soome {NULL, gzip_decompress, 1, "gzip-1"}, 180199767f8SToomas Soome {NULL, gzip_decompress, 2, "gzip-2"}, 181199767f8SToomas Soome {NULL, gzip_decompress, 3, "gzip-3"}, 182199767f8SToomas Soome {NULL, gzip_decompress, 4, "gzip-4"}, 183199767f8SToomas Soome {NULL, gzip_decompress, 5, "gzip-5"}, 184199767f8SToomas Soome {NULL, gzip_decompress, 6, "gzip-6"}, 185199767f8SToomas Soome {NULL, gzip_decompress, 7, "gzip-7"}, 186199767f8SToomas Soome {NULL, gzip_decompress, 8, "gzip-8"}, 187199767f8SToomas Soome {NULL, gzip_decompress, 9, "gzip-9"}, 188199767f8SToomas Soome {NULL, zle_decompress, 64, "zle"}, 189199767f8SToomas Soome {NULL, lz4_decompress, 0, "lz4"}, 190199767f8SToomas Soome }; 191199767f8SToomas Soome 192199767f8SToomas Soome static void 193199767f8SToomas Soome byteswap_uint64_array(void *vbuf, size_t size) 194199767f8SToomas Soome { 195199767f8SToomas Soome uint64_t *buf = vbuf; 196199767f8SToomas Soome size_t count = size >> 3; 197199767f8SToomas Soome int i; 198199767f8SToomas Soome 199199767f8SToomas Soome ASSERT((size & 7) == 0); 200199767f8SToomas Soome 201199767f8SToomas Soome for (i = 0; i < count; i++) 202199767f8SToomas Soome buf[i] = BSWAP_64(buf[i]); 203199767f8SToomas Soome } 204199767f8SToomas Soome 205199767f8SToomas Soome /* 206199767f8SToomas Soome * Set the external verifier for a gang block based on <vdev, offset, txg>, 207199767f8SToomas Soome * a tuple which is guaranteed to be unique for the life of the pool. 208199767f8SToomas Soome */ 209199767f8SToomas Soome static void 210199767f8SToomas Soome zio_checksum_gang_verifier(zio_cksum_t *zcp, const blkptr_t *bp) 211199767f8SToomas Soome { 212199767f8SToomas Soome const dva_t *dva = BP_IDENTITY(bp); 213199767f8SToomas Soome uint64_t txg = BP_PHYSICAL_BIRTH(bp); 214199767f8SToomas Soome 215199767f8SToomas Soome ASSERT(BP_IS_GANG(bp)); 216199767f8SToomas Soome 217199767f8SToomas Soome ZIO_SET_CHECKSUM(zcp, DVA_GET_VDEV(dva), DVA_GET_OFFSET(dva), txg, 0); 218199767f8SToomas Soome } 219199767f8SToomas Soome 220199767f8SToomas Soome /* 221199767f8SToomas Soome * Set the external verifier for a label block based on its offset. 222199767f8SToomas Soome * The vdev is implicit, and the txg is unknowable at pool open time -- 223199767f8SToomas Soome * hence the logic in vdev_uberblock_load() to find the most recent copy. 224199767f8SToomas Soome */ 225199767f8SToomas Soome static void 226199767f8SToomas Soome zio_checksum_label_verifier(zio_cksum_t *zcp, uint64_t offset) 227199767f8SToomas Soome { 228199767f8SToomas Soome ZIO_SET_CHECKSUM(zcp, offset, 0, 0, 0); 229199767f8SToomas Soome } 230199767f8SToomas Soome 231199767f8SToomas Soome /* 232199767f8SToomas Soome * Calls the template init function of a checksum which supports context 233199767f8SToomas Soome * templates and installs the template into the spa_t. 234199767f8SToomas Soome */ 235199767f8SToomas Soome static void 236*4a04e8dbSToomas Soome zio_checksum_template_init(enum zio_checksum checksum, spa_t *spa) 237199767f8SToomas Soome { 238199767f8SToomas Soome zio_checksum_info_t *ci = &zio_checksum_table[checksum]; 239199767f8SToomas Soome 240199767f8SToomas Soome if (ci->ci_tmpl_init == NULL) 241199767f8SToomas Soome return; 242*4a04e8dbSToomas Soome 243199767f8SToomas Soome if (spa->spa_cksum_tmpls[checksum] != NULL) 244199767f8SToomas Soome return; 245199767f8SToomas Soome 246199767f8SToomas Soome if (spa->spa_cksum_tmpls[checksum] == NULL) { 247199767f8SToomas Soome spa->spa_cksum_tmpls[checksum] = 248199767f8SToomas Soome ci->ci_tmpl_init(&spa->spa_cksum_salt); 249199767f8SToomas Soome } 250*4a04e8dbSToomas Soome } 251*4a04e8dbSToomas Soome 252*4a04e8dbSToomas Soome /* 253*4a04e8dbSToomas Soome * Called by a spa_t that's about to be deallocated. This steps through 254*4a04e8dbSToomas Soome * all of the checksum context templates and deallocates any that were 255*4a04e8dbSToomas Soome * initialized using the algorithm-specific template init function. 256*4a04e8dbSToomas Soome */ 257*4a04e8dbSToomas Soome void 258*4a04e8dbSToomas Soome zio_checksum_templates_free(spa_t *spa) 259*4a04e8dbSToomas Soome { 260*4a04e8dbSToomas Soome for (enum zio_checksum checksum = 0; 261*4a04e8dbSToomas Soome checksum < ZIO_CHECKSUM_FUNCTIONS; checksum++) { 262*4a04e8dbSToomas Soome if (spa->spa_cksum_tmpls[checksum] != NULL) { 263*4a04e8dbSToomas Soome zio_checksum_info_t *ci = &zio_checksum_table[checksum]; 264*4a04e8dbSToomas Soome 265*4a04e8dbSToomas Soome ci->ci_tmpl_free(spa->spa_cksum_tmpls[checksum]); 266*4a04e8dbSToomas Soome spa->spa_cksum_tmpls[checksum] = NULL; 267*4a04e8dbSToomas Soome } 268*4a04e8dbSToomas Soome } 269199767f8SToomas Soome } 270199767f8SToomas Soome 271199767f8SToomas Soome static int 272*4a04e8dbSToomas Soome zio_checksum_verify(const spa_t *spa, const blkptr_t *bp, void *data) 273199767f8SToomas Soome { 274199767f8SToomas Soome uint64_t size; 275199767f8SToomas Soome unsigned int checksum; 276199767f8SToomas Soome zio_checksum_info_t *ci; 277*4a04e8dbSToomas Soome void *ctx = NULL; 278199767f8SToomas Soome zio_cksum_t actual_cksum, expected_cksum, verifier; 279199767f8SToomas Soome int byteswap; 280199767f8SToomas Soome 281199767f8SToomas Soome checksum = BP_GET_CHECKSUM(bp); 282199767f8SToomas Soome size = BP_GET_PSIZE(bp); 283199767f8SToomas Soome 284199767f8SToomas Soome if (checksum >= ZIO_CHECKSUM_FUNCTIONS) 285199767f8SToomas Soome return (EINVAL); 286199767f8SToomas Soome ci = &zio_checksum_table[checksum]; 287199767f8SToomas Soome if (ci->ci_func[0] == NULL || ci->ci_func[1] == NULL) 288199767f8SToomas Soome return (EINVAL); 289199767f8SToomas Soome 290*4a04e8dbSToomas Soome if (spa != NULL) { 291*4a04e8dbSToomas Soome zio_checksum_template_init(checksum, (spa_t *) spa); 292*4a04e8dbSToomas Soome ctx = spa->spa_cksum_tmpls[checksum]; 293*4a04e8dbSToomas Soome } 294*4a04e8dbSToomas Soome 295199767f8SToomas Soome if (ci->ci_flags & ZCHECKSUM_FLAG_EMBEDDED) { 296199767f8SToomas Soome zio_eck_t *eck; 297199767f8SToomas Soome 298199767f8SToomas Soome ASSERT(checksum == ZIO_CHECKSUM_GANG_HEADER || 299199767f8SToomas Soome checksum == ZIO_CHECKSUM_LABEL); 300199767f8SToomas Soome 301199767f8SToomas Soome eck = (zio_eck_t *)((char *)data + size) - 1; 302199767f8SToomas Soome 303199767f8SToomas Soome if (checksum == ZIO_CHECKSUM_GANG_HEADER) 304199767f8SToomas Soome zio_checksum_gang_verifier(&verifier, bp); 305199767f8SToomas Soome else if (checksum == ZIO_CHECKSUM_LABEL) 306199767f8SToomas Soome zio_checksum_label_verifier(&verifier, 307199767f8SToomas Soome DVA_GET_OFFSET(BP_IDENTITY(bp))); 308199767f8SToomas Soome else 309199767f8SToomas Soome verifier = bp->blk_cksum; 310199767f8SToomas Soome 311199767f8SToomas Soome byteswap = (eck->zec_magic == BSWAP_64(ZEC_MAGIC)); 312199767f8SToomas Soome 313199767f8SToomas Soome if (byteswap) 314199767f8SToomas Soome byteswap_uint64_array(&verifier, sizeof (zio_cksum_t)); 315199767f8SToomas Soome 316199767f8SToomas Soome expected_cksum = eck->zec_cksum; 317199767f8SToomas Soome eck->zec_cksum = verifier; 318*4a04e8dbSToomas Soome ci->ci_func[byteswap](data, size, ctx, &actual_cksum); 319199767f8SToomas Soome eck->zec_cksum = expected_cksum; 320199767f8SToomas Soome 321199767f8SToomas Soome if (byteswap) 322199767f8SToomas Soome byteswap_uint64_array(&expected_cksum, 323199767f8SToomas Soome sizeof (zio_cksum_t)); 324199767f8SToomas Soome } else { 325199767f8SToomas Soome expected_cksum = bp->blk_cksum; 326*4a04e8dbSToomas Soome ci->ci_func[0](data, size, ctx, &actual_cksum); 327199767f8SToomas Soome } 328199767f8SToomas Soome 329199767f8SToomas Soome if (!ZIO_CHECKSUM_EQUAL(actual_cksum, expected_cksum)) { 330*4a04e8dbSToomas Soome /* printf("ZFS: read checksum %s failed\n", ci->ci_name); */ 331199767f8SToomas Soome return (EIO); 332199767f8SToomas Soome } 333199767f8SToomas Soome 334199767f8SToomas Soome return (0); 335199767f8SToomas Soome } 336199767f8SToomas Soome 337199767f8SToomas Soome static int 338199767f8SToomas Soome zio_decompress_data(int cpfunc, void *src, uint64_t srcsize, 339199767f8SToomas Soome void *dest, uint64_t destsize) 340199767f8SToomas Soome { 341199767f8SToomas Soome zio_compress_info_t *ci; 342199767f8SToomas Soome 343199767f8SToomas Soome if (cpfunc >= ZIO_COMPRESS_FUNCTIONS) { 344199767f8SToomas Soome printf("ZFS: unsupported compression algorithm %u\n", cpfunc); 345199767f8SToomas Soome return (EIO); 346199767f8SToomas Soome } 347199767f8SToomas Soome 348199767f8SToomas Soome ci = &zio_compress_table[cpfunc]; 349199767f8SToomas Soome if (!ci->ci_decompress) { 350199767f8SToomas Soome printf("ZFS: unsupported compression algorithm %s\n", 351199767f8SToomas Soome ci->ci_name); 352199767f8SToomas Soome return (EIO); 353199767f8SToomas Soome } 354199767f8SToomas Soome 355199767f8SToomas Soome return (ci->ci_decompress(src, dest, srcsize, destsize, ci->ci_level)); 356199767f8SToomas Soome } 357199767f8SToomas Soome 358199767f8SToomas Soome static uint64_t 359199767f8SToomas Soome zap_hash(uint64_t salt, const char *name) 360199767f8SToomas Soome { 361199767f8SToomas Soome const uint8_t *cp; 362199767f8SToomas Soome uint8_t c; 363199767f8SToomas Soome uint64_t crc = salt; 364199767f8SToomas Soome 365199767f8SToomas Soome ASSERT(crc != 0); 366199767f8SToomas Soome ASSERT(zfs_crc64_table[128] == ZFS_CRC64_POLY); 367199767f8SToomas Soome for (cp = (const uint8_t *)name; (c = *cp) != '\0'; cp++) 368199767f8SToomas Soome crc = (crc >> 8) ^ zfs_crc64_table[(crc ^ c) & 0xFF]; 369199767f8SToomas Soome 370199767f8SToomas Soome /* 371199767f8SToomas Soome * Only use 28 bits, since we need 4 bits in the cookie for the 372199767f8SToomas Soome * collision differentiator. We MUST use the high bits, since 373199767f8SToomas Soome * those are the onces that we first pay attention to when 374199767f8SToomas Soome * chosing the bucket. 375199767f8SToomas Soome */ 376199767f8SToomas Soome crc &= ~((1ULL << (64 - ZAP_HASHBITS)) - 1); 377199767f8SToomas Soome 378199767f8SToomas Soome return (crc); 379199767f8SToomas Soome } 380199767f8SToomas Soome 381199767f8SToomas Soome static void *zfs_alloc(size_t size); 382199767f8SToomas Soome static void zfs_free(void *ptr, size_t size); 383199767f8SToomas Soome 384199767f8SToomas Soome typedef struct raidz_col { 385199767f8SToomas Soome uint64_t rc_devidx; /* child device index for I/O */ 386199767f8SToomas Soome uint64_t rc_offset; /* device offset */ 387199767f8SToomas Soome uint64_t rc_size; /* I/O size */ 388199767f8SToomas Soome void *rc_data; /* I/O data */ 389199767f8SToomas Soome int rc_error; /* I/O error for this device */ 390199767f8SToomas Soome uint8_t rc_tried; /* Did we attempt this I/O column? */ 391199767f8SToomas Soome uint8_t rc_skipped; /* Did we skip this I/O column? */ 392199767f8SToomas Soome } raidz_col_t; 393199767f8SToomas Soome 394199767f8SToomas Soome typedef struct raidz_map { 395199767f8SToomas Soome uint64_t rm_cols; /* Regular column count */ 396199767f8SToomas Soome uint64_t rm_scols; /* Count including skipped columns */ 397199767f8SToomas Soome uint64_t rm_bigcols; /* Number of oversized columns */ 398199767f8SToomas Soome uint64_t rm_asize; /* Actual total I/O size */ 399199767f8SToomas Soome uint64_t rm_missingdata; /* Count of missing data devices */ 400199767f8SToomas Soome uint64_t rm_missingparity; /* Count of missing parity devices */ 401199767f8SToomas Soome uint64_t rm_firstdatacol; /* First data column/parity count */ 402199767f8SToomas Soome uint64_t rm_nskip; /* Skipped sectors for padding */ 403199767f8SToomas Soome uint64_t rm_skipstart; /* Column index of padding start */ 404199767f8SToomas Soome uintptr_t rm_reports; /* # of referencing checksum reports */ 405199767f8SToomas Soome uint8_t rm_freed; /* map no longer has referencing ZIO */ 406199767f8SToomas Soome uint8_t rm_ecksuminjected; /* checksum error was injected */ 407199767f8SToomas Soome raidz_col_t rm_col[1]; /* Flexible array of I/O columns */ 408199767f8SToomas Soome } raidz_map_t; 409199767f8SToomas Soome 410199767f8SToomas Soome #define VDEV_RAIDZ_P 0 411199767f8SToomas Soome #define VDEV_RAIDZ_Q 1 412199767f8SToomas Soome #define VDEV_RAIDZ_R 2 413199767f8SToomas Soome 414199767f8SToomas Soome #define VDEV_RAIDZ_MUL_2(x) (((x) << 1) ^ (((x) & 0x80) ? 0x1d : 0)) 415199767f8SToomas Soome #define VDEV_RAIDZ_MUL_4(x) (VDEV_RAIDZ_MUL_2(VDEV_RAIDZ_MUL_2(x))) 416199767f8SToomas Soome 417199767f8SToomas Soome /* 418199767f8SToomas Soome * We provide a mechanism to perform the field multiplication operation on a 419199767f8SToomas Soome * 64-bit value all at once rather than a byte at a time. This works by 420199767f8SToomas Soome * creating a mask from the top bit in each byte and using that to 421199767f8SToomas Soome * conditionally apply the XOR of 0x1d. 422199767f8SToomas Soome */ 423199767f8SToomas Soome #define VDEV_RAIDZ_64MUL_2(x, mask) \ 424199767f8SToomas Soome { \ 425199767f8SToomas Soome (mask) = (x) & 0x8080808080808080ULL; \ 426199767f8SToomas Soome (mask) = ((mask) << 1) - ((mask) >> 7); \ 427199767f8SToomas Soome (x) = (((x) << 1) & 0xfefefefefefefefeULL) ^ \ 428199767f8SToomas Soome ((mask) & 0x1d1d1d1d1d1d1d1dULL); \ 429199767f8SToomas Soome } 430199767f8SToomas Soome 431199767f8SToomas Soome #define VDEV_RAIDZ_64MUL_4(x, mask) \ 432199767f8SToomas Soome { \ 433199767f8SToomas Soome VDEV_RAIDZ_64MUL_2((x), mask); \ 434199767f8SToomas Soome VDEV_RAIDZ_64MUL_2((x), mask); \ 435199767f8SToomas Soome } 436199767f8SToomas Soome 437199767f8SToomas Soome /* 438199767f8SToomas Soome * These two tables represent powers and logs of 2 in the Galois field defined 439199767f8SToomas Soome * above. These values were computed by repeatedly multiplying by 2 as above. 440199767f8SToomas Soome */ 441199767f8SToomas Soome static const uint8_t vdev_raidz_pow2[256] = { 442199767f8SToomas Soome 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 443199767f8SToomas Soome 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26, 444199767f8SToomas Soome 0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 445199767f8SToomas Soome 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0, 446199767f8SToomas Soome 0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 447199767f8SToomas Soome 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23, 448199767f8SToomas Soome 0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 449199767f8SToomas Soome 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1, 450199767f8SToomas Soome 0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 451199767f8SToomas Soome 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0, 452199767f8SToomas Soome 0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 453199767f8SToomas Soome 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2, 454199767f8SToomas Soome 0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 455199767f8SToomas Soome 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce, 456199767f8SToomas Soome 0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 457199767f8SToomas Soome 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc, 458199767f8SToomas Soome 0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 459199767f8SToomas Soome 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54, 460199767f8SToomas Soome 0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 461199767f8SToomas Soome 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73, 462199767f8SToomas Soome 0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 463199767f8SToomas Soome 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff, 464199767f8SToomas Soome 0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 465199767f8SToomas Soome 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41, 466199767f8SToomas Soome 0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 467199767f8SToomas Soome 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6, 468199767f8SToomas Soome 0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 469199767f8SToomas Soome 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09, 470199767f8SToomas Soome 0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 471199767f8SToomas Soome 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16, 472199767f8SToomas Soome 0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 473199767f8SToomas Soome 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01 474199767f8SToomas Soome }; 475199767f8SToomas Soome static const uint8_t vdev_raidz_log2[256] = { 476199767f8SToomas Soome 0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6, 477199767f8SToomas Soome 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b, 478199767f8SToomas Soome 0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81, 479199767f8SToomas Soome 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71, 480199767f8SToomas Soome 0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21, 481199767f8SToomas Soome 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45, 482199767f8SToomas Soome 0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9, 483199767f8SToomas Soome 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6, 484199767f8SToomas Soome 0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd, 485199767f8SToomas Soome 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88, 486199767f8SToomas Soome 0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd, 487199767f8SToomas Soome 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40, 488199767f8SToomas Soome 0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e, 489199767f8SToomas Soome 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d, 490199767f8SToomas Soome 0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b, 491199767f8SToomas Soome 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57, 492199767f8SToomas Soome 0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d, 493199767f8SToomas Soome 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18, 494199767f8SToomas Soome 0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c, 495199767f8SToomas Soome 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e, 496199767f8SToomas Soome 0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd, 497199767f8SToomas Soome 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61, 498199767f8SToomas Soome 0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e, 499199767f8SToomas Soome 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2, 500199767f8SToomas Soome 0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76, 501199767f8SToomas Soome 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6, 502199767f8SToomas Soome 0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa, 503199767f8SToomas Soome 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a, 504199767f8SToomas Soome 0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51, 505199767f8SToomas Soome 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7, 506199767f8SToomas Soome 0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8, 507199767f8SToomas Soome 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf, 508199767f8SToomas Soome }; 509199767f8SToomas Soome 510199767f8SToomas Soome /* 511199767f8SToomas Soome * Multiply a given number by 2 raised to the given power. 512199767f8SToomas Soome */ 513199767f8SToomas Soome static uint8_t 514199767f8SToomas Soome vdev_raidz_exp2(uint8_t a, int exp) 515199767f8SToomas Soome { 516199767f8SToomas Soome if (a == 0) 517199767f8SToomas Soome return (0); 518199767f8SToomas Soome 519199767f8SToomas Soome ASSERT(exp >= 0); 520199767f8SToomas Soome ASSERT(vdev_raidz_log2[a] > 0 || a == 1); 521199767f8SToomas Soome 522199767f8SToomas Soome exp += vdev_raidz_log2[a]; 523199767f8SToomas Soome if (exp > 255) 524199767f8SToomas Soome exp -= 255; 525199767f8SToomas Soome 526199767f8SToomas Soome return (vdev_raidz_pow2[exp]); 527199767f8SToomas Soome } 528199767f8SToomas Soome 529199767f8SToomas Soome static void 530199767f8SToomas Soome vdev_raidz_generate_parity_p(raidz_map_t *rm) 531199767f8SToomas Soome { 532199767f8SToomas Soome uint64_t *p, *src, pcount __attribute__((unused)), ccount, i; 533199767f8SToomas Soome int c; 534199767f8SToomas Soome 535199767f8SToomas Soome pcount = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]); 536199767f8SToomas Soome 537199767f8SToomas Soome for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) { 538199767f8SToomas Soome src = rm->rm_col[c].rc_data; 539199767f8SToomas Soome p = rm->rm_col[VDEV_RAIDZ_P].rc_data; 540199767f8SToomas Soome ccount = rm->rm_col[c].rc_size / sizeof (src[0]); 541199767f8SToomas Soome 542199767f8SToomas Soome if (c == rm->rm_firstdatacol) { 543199767f8SToomas Soome ASSERT(ccount == pcount); 544199767f8SToomas Soome for (i = 0; i < ccount; i++, src++, p++) { 545199767f8SToomas Soome *p = *src; 546199767f8SToomas Soome } 547199767f8SToomas Soome } else { 548199767f8SToomas Soome ASSERT(ccount <= pcount); 549199767f8SToomas Soome for (i = 0; i < ccount; i++, src++, p++) { 550199767f8SToomas Soome *p ^= *src; 551199767f8SToomas Soome } 552199767f8SToomas Soome } 553199767f8SToomas Soome } 554199767f8SToomas Soome } 555199767f8SToomas Soome 556199767f8SToomas Soome static void 557199767f8SToomas Soome vdev_raidz_generate_parity_pq(raidz_map_t *rm) 558199767f8SToomas Soome { 559199767f8SToomas Soome uint64_t *p, *q, *src, pcnt, ccnt, mask, i; 560199767f8SToomas Soome int c; 561199767f8SToomas Soome 562199767f8SToomas Soome pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]); 563199767f8SToomas Soome ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size == 564199767f8SToomas Soome rm->rm_col[VDEV_RAIDZ_Q].rc_size); 565199767f8SToomas Soome 566199767f8SToomas Soome for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) { 567199767f8SToomas Soome src = rm->rm_col[c].rc_data; 568199767f8SToomas Soome p = rm->rm_col[VDEV_RAIDZ_P].rc_data; 569199767f8SToomas Soome q = rm->rm_col[VDEV_RAIDZ_Q].rc_data; 570199767f8SToomas Soome 571199767f8SToomas Soome ccnt = rm->rm_col[c].rc_size / sizeof (src[0]); 572199767f8SToomas Soome 573199767f8SToomas Soome if (c == rm->rm_firstdatacol) { 574199767f8SToomas Soome ASSERT(ccnt == pcnt || ccnt == 0); 575199767f8SToomas Soome for (i = 0; i < ccnt; i++, src++, p++, q++) { 576199767f8SToomas Soome *p = *src; 577199767f8SToomas Soome *q = *src; 578199767f8SToomas Soome } 579199767f8SToomas Soome for (; i < pcnt; i++, src++, p++, q++) { 580199767f8SToomas Soome *p = 0; 581199767f8SToomas Soome *q = 0; 582199767f8SToomas Soome } 583199767f8SToomas Soome } else { 584199767f8SToomas Soome ASSERT(ccnt <= pcnt); 585199767f8SToomas Soome 586199767f8SToomas Soome /* 587199767f8SToomas Soome * Apply the algorithm described above by multiplying 588199767f8SToomas Soome * the previous result and adding in the new value. 589199767f8SToomas Soome */ 590199767f8SToomas Soome for (i = 0; i < ccnt; i++, src++, p++, q++) { 591199767f8SToomas Soome *p ^= *src; 592199767f8SToomas Soome 593199767f8SToomas Soome VDEV_RAIDZ_64MUL_2(*q, mask); 594199767f8SToomas Soome *q ^= *src; 595199767f8SToomas Soome } 596199767f8SToomas Soome 597199767f8SToomas Soome /* 598199767f8SToomas Soome * Treat short columns as though they are full of 0s. 599199767f8SToomas Soome * Note that there's therefore nothing needed for P. 600199767f8SToomas Soome */ 601199767f8SToomas Soome for (; i < pcnt; i++, q++) { 602199767f8SToomas Soome VDEV_RAIDZ_64MUL_2(*q, mask); 603199767f8SToomas Soome } 604199767f8SToomas Soome } 605199767f8SToomas Soome } 606199767f8SToomas Soome } 607199767f8SToomas Soome 608199767f8SToomas Soome static void 609199767f8SToomas Soome vdev_raidz_generate_parity_pqr(raidz_map_t *rm) 610199767f8SToomas Soome { 611199767f8SToomas Soome uint64_t *p, *q, *r, *src, pcnt, ccnt, mask, i; 612199767f8SToomas Soome int c; 613199767f8SToomas Soome 614199767f8SToomas Soome pcnt = rm->rm_col[VDEV_RAIDZ_P].rc_size / sizeof (src[0]); 615199767f8SToomas Soome ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size == 616199767f8SToomas Soome rm->rm_col[VDEV_RAIDZ_Q].rc_size); 617199767f8SToomas Soome ASSERT(rm->rm_col[VDEV_RAIDZ_P].rc_size == 618199767f8SToomas Soome rm->rm_col[VDEV_RAIDZ_R].rc_size); 619199767f8SToomas Soome 620199767f8SToomas Soome for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) { 621199767f8SToomas Soome src = rm->rm_col[c].rc_data; 622199767f8SToomas Soome p = rm->rm_col[VDEV_RAIDZ_P].rc_data; 623199767f8SToomas Soome q = rm->rm_col[VDEV_RAIDZ_Q].rc_data; 624199767f8SToomas Soome r = rm->rm_col[VDEV_RAIDZ_R].rc_data; 625199767f8SToomas Soome 626199767f8SToomas Soome ccnt = rm->rm_col[c].rc_size / sizeof (src[0]); 627199767f8SToomas Soome 628199767f8SToomas Soome if (c == rm->rm_firstdatacol) { 629199767f8SToomas Soome ASSERT(ccnt == pcnt || ccnt == 0); 630199767f8SToomas Soome for (i = 0; i < ccnt; i++, src++, p++, q++, r++) { 631199767f8SToomas Soome *p = *src; 632199767f8SToomas Soome *q = *src; 633199767f8SToomas Soome *r = *src; 634199767f8SToomas Soome } 635199767f8SToomas Soome for (; i < pcnt; i++, src++, p++, q++, r++) { 636199767f8SToomas Soome *p = 0; 637199767f8SToomas Soome *q = 0; 638199767f8SToomas Soome *r = 0; 639199767f8SToomas Soome } 640199767f8SToomas Soome } else { 641199767f8SToomas Soome ASSERT(ccnt <= pcnt); 642199767f8SToomas Soome 643199767f8SToomas Soome /* 644199767f8SToomas Soome * Apply the algorithm described above by multiplying 645199767f8SToomas Soome * the previous result and adding in the new value. 646199767f8SToomas Soome */ 647199767f8SToomas Soome for (i = 0; i < ccnt; i++, src++, p++, q++, r++) { 648199767f8SToomas Soome *p ^= *src; 649199767f8SToomas Soome 650199767f8SToomas Soome VDEV_RAIDZ_64MUL_2(*q, mask); 651199767f8SToomas Soome *q ^= *src; 652199767f8SToomas Soome 653199767f8SToomas Soome VDEV_RAIDZ_64MUL_4(*r, mask); 654199767f8SToomas Soome *r ^= *src; 655199767f8SToomas Soome } 656199767f8SToomas Soome 657199767f8SToomas Soome /* 658199767f8SToomas Soome * Treat short columns as though they are full of 0s. 659199767f8SToomas Soome * Note that there's therefore nothing needed for P. 660199767f8SToomas Soome */ 661199767f8SToomas Soome for (; i < pcnt; i++, q++, r++) { 662199767f8SToomas Soome VDEV_RAIDZ_64MUL_2(*q, mask); 663199767f8SToomas Soome VDEV_RAIDZ_64MUL_4(*r, mask); 664199767f8SToomas Soome } 665199767f8SToomas Soome } 666199767f8SToomas Soome } 667199767f8SToomas Soome } 668199767f8SToomas Soome 669199767f8SToomas Soome /* 670199767f8SToomas Soome * Generate RAID parity in the first virtual columns according to the number of 671199767f8SToomas Soome * parity columns available. 672199767f8SToomas Soome */ 673199767f8SToomas Soome static void 674199767f8SToomas Soome vdev_raidz_generate_parity(raidz_map_t *rm) 675199767f8SToomas Soome { 676199767f8SToomas Soome switch (rm->rm_firstdatacol) { 677199767f8SToomas Soome case 1: 678199767f8SToomas Soome vdev_raidz_generate_parity_p(rm); 679199767f8SToomas Soome break; 680199767f8SToomas Soome case 2: 681199767f8SToomas Soome vdev_raidz_generate_parity_pq(rm); 682199767f8SToomas Soome break; 683199767f8SToomas Soome case 3: 684199767f8SToomas Soome vdev_raidz_generate_parity_pqr(rm); 685199767f8SToomas Soome break; 686199767f8SToomas Soome default: 687199767f8SToomas Soome panic("invalid RAID-Z configuration"); 688199767f8SToomas Soome } 689199767f8SToomas Soome } 690199767f8SToomas Soome 691199767f8SToomas Soome /* BEGIN CSTYLED */ 692199767f8SToomas Soome /* 693199767f8SToomas Soome * In the general case of reconstruction, we must solve the system of linear 694199767f8SToomas Soome * equations defined by the coeffecients used to generate parity as well as 695199767f8SToomas Soome * the contents of the data and parity disks. This can be expressed with 696199767f8SToomas Soome * vectors for the original data (D) and the actual data (d) and parity (p) 697199767f8SToomas Soome * and a matrix composed of the identity matrix (I) and a dispersal matrix (V): 698199767f8SToomas Soome * 699199767f8SToomas Soome * __ __ __ __ 700199767f8SToomas Soome * | | __ __ | p_0 | 701199767f8SToomas Soome * | V | | D_0 | | p_m-1 | 702199767f8SToomas Soome * | | x | : | = | d_0 | 703199767f8SToomas Soome * | I | | D_n-1 | | : | 704199767f8SToomas Soome * | | ~~ ~~ | d_n-1 | 705199767f8SToomas Soome * ~~ ~~ ~~ ~~ 706199767f8SToomas Soome * 707199767f8SToomas Soome * I is simply a square identity matrix of size n, and V is a vandermonde 708199767f8SToomas Soome * matrix defined by the coeffecients we chose for the various parity columns 709199767f8SToomas Soome * (1, 2, 4). Note that these values were chosen both for simplicity, speedy 710199767f8SToomas Soome * computation as well as linear separability. 711199767f8SToomas Soome * 712199767f8SToomas Soome * __ __ __ __ 713199767f8SToomas Soome * | 1 .. 1 1 1 | | p_0 | 714199767f8SToomas Soome * | 2^n-1 .. 4 2 1 | __ __ | : | 715199767f8SToomas Soome * | 4^n-1 .. 16 4 1 | | D_0 | | p_m-1 | 716199767f8SToomas Soome * | 1 .. 0 0 0 | | D_1 | | d_0 | 717199767f8SToomas Soome * | 0 .. 0 0 0 | x | D_2 | = | d_1 | 718199767f8SToomas Soome * | : : : : | | : | | d_2 | 719199767f8SToomas Soome * | 0 .. 1 0 0 | | D_n-1 | | : | 720199767f8SToomas Soome * | 0 .. 0 1 0 | ~~ ~~ | : | 721199767f8SToomas Soome * | 0 .. 0 0 1 | | d_n-1 | 722199767f8SToomas Soome * ~~ ~~ ~~ ~~ 723199767f8SToomas Soome * 724199767f8SToomas Soome * Note that I, V, d, and p are known. To compute D, we must invert the 725199767f8SToomas Soome * matrix and use the known data and parity values to reconstruct the unknown 726199767f8SToomas Soome * data values. We begin by removing the rows in V|I and d|p that correspond 727199767f8SToomas Soome * to failed or missing columns; we then make V|I square (n x n) and d|p 728199767f8SToomas Soome * sized n by removing rows corresponding to unused parity from the bottom up 729199767f8SToomas Soome * to generate (V|I)' and (d|p)'. We can then generate the inverse of (V|I)' 730199767f8SToomas Soome * using Gauss-Jordan elimination. In the example below we use m=3 parity 731199767f8SToomas Soome * columns, n=8 data columns, with errors in d_1, d_2, and p_1: 732199767f8SToomas Soome * __ __ 733199767f8SToomas Soome * | 1 1 1 1 1 1 1 1 | 734199767f8SToomas Soome * | 128 64 32 16 8 4 2 1 | <-----+-+-- missing disks 735199767f8SToomas Soome * | 19 205 116 29 64 16 4 1 | / / 736199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 | / / 737199767f8SToomas Soome * | 0 1 0 0 0 0 0 0 | <--' / 738199767f8SToomas Soome * (V|I) = | 0 0 1 0 0 0 0 0 | <---' 739199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 | 740199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 | 741199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 | 742199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 | 743199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 | 744199767f8SToomas Soome * ~~ ~~ 745199767f8SToomas Soome * __ __ 746199767f8SToomas Soome * | 1 1 1 1 1 1 1 1 | 747199767f8SToomas Soome * | 128 64 32 16 8 4 2 1 | 748199767f8SToomas Soome * | 19 205 116 29 64 16 4 1 | 749199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 | 750199767f8SToomas Soome * | 0 1 0 0 0 0 0 0 | 751199767f8SToomas Soome * (V|I)' = | 0 0 1 0 0 0 0 0 | 752199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 | 753199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 | 754199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 | 755199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 | 756199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 | 757199767f8SToomas Soome * ~~ ~~ 758199767f8SToomas Soome * 759199767f8SToomas Soome * Here we employ Gauss-Jordan elimination to find the inverse of (V|I)'. We 760199767f8SToomas Soome * have carefully chosen the seed values 1, 2, and 4 to ensure that this 761199767f8SToomas Soome * matrix is not singular. 762199767f8SToomas Soome * __ __ 763199767f8SToomas Soome * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 | 764199767f8SToomas Soome * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 | 765199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 766199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 | 767199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 | 768199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 | 769199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 | 770199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 | 771199767f8SToomas Soome * ~~ ~~ 772199767f8SToomas Soome * __ __ 773199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 774199767f8SToomas Soome * | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 | 775199767f8SToomas Soome * | 19 205 116 29 64 16 4 1 0 1 0 0 0 0 0 0 | 776199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 | 777199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 | 778199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 | 779199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 | 780199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 | 781199767f8SToomas Soome * ~~ ~~ 782199767f8SToomas Soome * __ __ 783199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 784199767f8SToomas Soome * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 | 785199767f8SToomas Soome * | 0 205 116 0 0 0 0 0 0 1 19 29 64 16 4 1 | 786199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 | 787199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 | 788199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 | 789199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 | 790199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 | 791199767f8SToomas Soome * ~~ ~~ 792199767f8SToomas Soome * __ __ 793199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 794199767f8SToomas Soome * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 | 795199767f8SToomas Soome * | 0 0 185 0 0 0 0 0 205 1 222 208 141 221 201 204 | 796199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 | 797199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 | 798199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 | 799199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 | 800199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 | 801199767f8SToomas Soome * ~~ ~~ 802199767f8SToomas Soome * __ __ 803199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 804199767f8SToomas Soome * | 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 | 805199767f8SToomas Soome * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 | 806199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 | 807199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 | 808199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 | 809199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 | 810199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 | 811199767f8SToomas Soome * ~~ ~~ 812199767f8SToomas Soome * __ __ 813199767f8SToomas Soome * | 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 814199767f8SToomas Soome * | 0 1 0 0 0 0 0 0 167 100 5 41 159 169 217 208 | 815199767f8SToomas Soome * | 0 0 1 0 0 0 0 0 166 100 4 40 158 168 216 209 | 816199767f8SToomas Soome * | 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 | 817199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 | 818199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 | 819199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 | 820199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 | 821199767f8SToomas Soome * ~~ ~~ 822199767f8SToomas Soome * __ __ 823199767f8SToomas Soome * | 0 0 1 0 0 0 0 0 | 824199767f8SToomas Soome * | 167 100 5 41 159 169 217 208 | 825199767f8SToomas Soome * | 166 100 4 40 158 168 216 209 | 826199767f8SToomas Soome * (V|I)'^-1 = | 0 0 0 1 0 0 0 0 | 827199767f8SToomas Soome * | 0 0 0 0 1 0 0 0 | 828199767f8SToomas Soome * | 0 0 0 0 0 1 0 0 | 829199767f8SToomas Soome * | 0 0 0 0 0 0 1 0 | 830199767f8SToomas Soome * | 0 0 0 0 0 0 0 1 | 831199767f8SToomas Soome * ~~ ~~ 832199767f8SToomas Soome * 833199767f8SToomas Soome * We can then simply compute D = (V|I)'^-1 x (d|p)' to discover the values 834199767f8SToomas Soome * of the missing data. 835199767f8SToomas Soome * 836199767f8SToomas Soome * As is apparent from the example above, the only non-trivial rows in the 837199767f8SToomas Soome * inverse matrix correspond to the data disks that we're trying to 838199767f8SToomas Soome * reconstruct. Indeed, those are the only rows we need as the others would 839199767f8SToomas Soome * only be useful for reconstructing data known or assumed to be valid. For 840199767f8SToomas Soome * that reason, we only build the coefficients in the rows that correspond to 841199767f8SToomas Soome * targeted columns. 842199767f8SToomas Soome */ 843199767f8SToomas Soome /* END CSTYLED */ 844199767f8SToomas Soome 845199767f8SToomas Soome static void 846199767f8SToomas Soome vdev_raidz_matrix_init(raidz_map_t *rm, int n, int nmap, int *map, 847199767f8SToomas Soome uint8_t **rows) 848199767f8SToomas Soome { 849199767f8SToomas Soome int i, j; 850199767f8SToomas Soome int pow; 851199767f8SToomas Soome 852199767f8SToomas Soome ASSERT(n == rm->rm_cols - rm->rm_firstdatacol); 853199767f8SToomas Soome 854199767f8SToomas Soome /* 855199767f8SToomas Soome * Fill in the missing rows of interest. 856199767f8SToomas Soome */ 857199767f8SToomas Soome for (i = 0; i < nmap; i++) { 858199767f8SToomas Soome ASSERT3S(0, <=, map[i]); 859199767f8SToomas Soome ASSERT3S(map[i], <=, 2); 860199767f8SToomas Soome 861199767f8SToomas Soome pow = map[i] * n; 862199767f8SToomas Soome if (pow > 255) 863199767f8SToomas Soome pow -= 255; 864199767f8SToomas Soome ASSERT(pow <= 255); 865199767f8SToomas Soome 866199767f8SToomas Soome for (j = 0; j < n; j++) { 867199767f8SToomas Soome pow -= map[i]; 868199767f8SToomas Soome if (pow < 0) 869199767f8SToomas Soome pow += 255; 870199767f8SToomas Soome rows[i][j] = vdev_raidz_pow2[pow]; 871199767f8SToomas Soome } 872199767f8SToomas Soome } 873199767f8SToomas Soome } 874199767f8SToomas Soome 875199767f8SToomas Soome static void 876199767f8SToomas Soome vdev_raidz_matrix_invert(raidz_map_t *rm, int n, int nmissing, int *missing, 877199767f8SToomas Soome uint8_t **rows, uint8_t **invrows, const uint8_t *used) 878199767f8SToomas Soome { 879199767f8SToomas Soome int i, j, ii, jj; 880199767f8SToomas Soome uint8_t log; 881199767f8SToomas Soome 882199767f8SToomas Soome /* 883199767f8SToomas Soome * Assert that the first nmissing entries from the array of used 884199767f8SToomas Soome * columns correspond to parity columns and that subsequent entries 885199767f8SToomas Soome * correspond to data columns. 886199767f8SToomas Soome */ 887199767f8SToomas Soome for (i = 0; i < nmissing; i++) { 888199767f8SToomas Soome ASSERT3S(used[i], <, rm->rm_firstdatacol); 889199767f8SToomas Soome } 890199767f8SToomas Soome for (; i < n; i++) { 891199767f8SToomas Soome ASSERT3S(used[i], >=, rm->rm_firstdatacol); 892199767f8SToomas Soome } 893199767f8SToomas Soome 894199767f8SToomas Soome /* 895199767f8SToomas Soome * First initialize the storage where we'll compute the inverse rows. 896199767f8SToomas Soome */ 897199767f8SToomas Soome for (i = 0; i < nmissing; i++) { 898199767f8SToomas Soome for (j = 0; j < n; j++) { 899199767f8SToomas Soome invrows[i][j] = (i == j) ? 1 : 0; 900199767f8SToomas Soome } 901199767f8SToomas Soome } 902199767f8SToomas Soome 903199767f8SToomas Soome /* 904199767f8SToomas Soome * Subtract all trivial rows from the rows of consequence. 905199767f8SToomas Soome */ 906199767f8SToomas Soome for (i = 0; i < nmissing; i++) { 907199767f8SToomas Soome for (j = nmissing; j < n; j++) { 908199767f8SToomas Soome ASSERT3U(used[j], >=, rm->rm_firstdatacol); 909199767f8SToomas Soome jj = used[j] - rm->rm_firstdatacol; 910199767f8SToomas Soome ASSERT3S(jj, <, n); 911199767f8SToomas Soome invrows[i][j] = rows[i][jj]; 912199767f8SToomas Soome rows[i][jj] = 0; 913199767f8SToomas Soome } 914199767f8SToomas Soome } 915199767f8SToomas Soome 916199767f8SToomas Soome /* 917199767f8SToomas Soome * For each of the rows of interest, we must normalize it and subtract 918199767f8SToomas Soome * a multiple of it from the other rows. 919199767f8SToomas Soome */ 920199767f8SToomas Soome for (i = 0; i < nmissing; i++) { 921199767f8SToomas Soome for (j = 0; j < missing[i]; j++) { 922199767f8SToomas Soome ASSERT3U(rows[i][j], ==, 0); 923199767f8SToomas Soome } 924199767f8SToomas Soome ASSERT3U(rows[i][missing[i]], !=, 0); 925199767f8SToomas Soome 926199767f8SToomas Soome /* 927199767f8SToomas Soome * Compute the inverse of the first element and multiply each 928199767f8SToomas Soome * element in the row by that value. 929199767f8SToomas Soome */ 930199767f8SToomas Soome log = 255 - vdev_raidz_log2[rows[i][missing[i]]]; 931199767f8SToomas Soome 932199767f8SToomas Soome for (j = 0; j < n; j++) { 933199767f8SToomas Soome rows[i][j] = vdev_raidz_exp2(rows[i][j], log); 934199767f8SToomas Soome invrows[i][j] = vdev_raidz_exp2(invrows[i][j], log); 935199767f8SToomas Soome } 936199767f8SToomas Soome 937199767f8SToomas Soome for (ii = 0; ii < nmissing; ii++) { 938199767f8SToomas Soome if (i == ii) 939199767f8SToomas Soome continue; 940199767f8SToomas Soome 941199767f8SToomas Soome ASSERT3U(rows[ii][missing[i]], !=, 0); 942199767f8SToomas Soome 943199767f8SToomas Soome log = vdev_raidz_log2[rows[ii][missing[i]]]; 944199767f8SToomas Soome 945199767f8SToomas Soome for (j = 0; j < n; j++) { 946199767f8SToomas Soome rows[ii][j] ^= 947199767f8SToomas Soome vdev_raidz_exp2(rows[i][j], log); 948199767f8SToomas Soome invrows[ii][j] ^= 949199767f8SToomas Soome vdev_raidz_exp2(invrows[i][j], log); 950199767f8SToomas Soome } 951199767f8SToomas Soome } 952199767f8SToomas Soome } 953199767f8SToomas Soome 954199767f8SToomas Soome /* 955199767f8SToomas Soome * Verify that the data that is left in the rows are properly part of 956199767f8SToomas Soome * an identity matrix. 957199767f8SToomas Soome */ 958199767f8SToomas Soome for (i = 0; i < nmissing; i++) { 959199767f8SToomas Soome for (j = 0; j < n; j++) { 960199767f8SToomas Soome if (j == missing[i]) { 961199767f8SToomas Soome ASSERT3U(rows[i][j], ==, 1); 962199767f8SToomas Soome } else { 963199767f8SToomas Soome ASSERT3U(rows[i][j], ==, 0); 964199767f8SToomas Soome } 965199767f8SToomas Soome } 966199767f8SToomas Soome } 967199767f8SToomas Soome } 968199767f8SToomas Soome 969199767f8SToomas Soome static void 970199767f8SToomas Soome vdev_raidz_matrix_reconstruct(raidz_map_t *rm, int n, int nmissing, 971199767f8SToomas Soome int *missing, uint8_t **invrows, const uint8_t *used) 972199767f8SToomas Soome { 973199767f8SToomas Soome int i, j, x, cc, c; 974199767f8SToomas Soome uint8_t *src; 975199767f8SToomas Soome uint64_t ccount; 976199767f8SToomas Soome uint8_t *dst[VDEV_RAIDZ_MAXPARITY]; 977199767f8SToomas Soome uint64_t dcount[VDEV_RAIDZ_MAXPARITY]; 978199767f8SToomas Soome uint8_t log, val; 979199767f8SToomas Soome int ll; 980199767f8SToomas Soome uint8_t *invlog[VDEV_RAIDZ_MAXPARITY]; 981199767f8SToomas Soome uint8_t *p, *pp; 982199767f8SToomas Soome size_t psize; 983199767f8SToomas Soome 984199767f8SToomas Soome log = 0; /* gcc */ 985199767f8SToomas Soome psize = sizeof (invlog[0][0]) * n * nmissing; 986199767f8SToomas Soome p = zfs_alloc(psize); 987199767f8SToomas Soome 988199767f8SToomas Soome for (pp = p, i = 0; i < nmissing; i++) { 989199767f8SToomas Soome invlog[i] = pp; 990199767f8SToomas Soome pp += n; 991199767f8SToomas Soome } 992199767f8SToomas Soome 993199767f8SToomas Soome for (i = 0; i < nmissing; i++) { 994199767f8SToomas Soome for (j = 0; j < n; j++) { 995199767f8SToomas Soome ASSERT3U(invrows[i][j], !=, 0); 996199767f8SToomas Soome invlog[i][j] = vdev_raidz_log2[invrows[i][j]]; 997199767f8SToomas Soome } 998199767f8SToomas Soome } 999199767f8SToomas Soome 1000199767f8SToomas Soome for (i = 0; i < n; i++) { 1001199767f8SToomas Soome c = used[i]; 1002199767f8SToomas Soome ASSERT3U(c, <, rm->rm_cols); 1003199767f8SToomas Soome 1004199767f8SToomas Soome src = rm->rm_col[c].rc_data; 1005199767f8SToomas Soome ccount = rm->rm_col[c].rc_size; 1006199767f8SToomas Soome for (j = 0; j < nmissing; j++) { 1007199767f8SToomas Soome cc = missing[j] + rm->rm_firstdatacol; 1008199767f8SToomas Soome ASSERT3U(cc, >=, rm->rm_firstdatacol); 1009199767f8SToomas Soome ASSERT3U(cc, <, rm->rm_cols); 1010199767f8SToomas Soome ASSERT3U(cc, !=, c); 1011199767f8SToomas Soome 1012199767f8SToomas Soome dst[j] = rm->rm_col[cc].rc_data; 1013199767f8SToomas Soome dcount[j] = rm->rm_col[cc].rc_size; 1014199767f8SToomas Soome } 1015199767f8SToomas Soome 1016199767f8SToomas Soome ASSERT(ccount >= rm->rm_col[missing[0]].rc_size || i > 0); 1017199767f8SToomas Soome 1018199767f8SToomas Soome for (x = 0; x < ccount; x++, src++) { 1019199767f8SToomas Soome if (*src != 0) 1020199767f8SToomas Soome log = vdev_raidz_log2[*src]; 1021199767f8SToomas Soome 1022199767f8SToomas Soome for (cc = 0; cc < nmissing; cc++) { 1023199767f8SToomas Soome if (x >= dcount[cc]) 1024199767f8SToomas Soome continue; 1025199767f8SToomas Soome 1026199767f8SToomas Soome if (*src == 0) { 1027199767f8SToomas Soome val = 0; 1028199767f8SToomas Soome } else { 1029199767f8SToomas Soome if ((ll = log + invlog[cc][i]) >= 255) 1030199767f8SToomas Soome ll -= 255; 1031199767f8SToomas Soome val = vdev_raidz_pow2[ll]; 1032199767f8SToomas Soome } 1033199767f8SToomas Soome 1034199767f8SToomas Soome if (i == 0) 1035199767f8SToomas Soome dst[cc][x] = val; 1036199767f8SToomas Soome else 1037199767f8SToomas Soome dst[cc][x] ^= val; 1038199767f8SToomas Soome } 1039199767f8SToomas Soome } 1040199767f8SToomas Soome } 1041199767f8SToomas Soome 1042199767f8SToomas Soome zfs_free(p, psize); 1043199767f8SToomas Soome } 1044199767f8SToomas Soome 1045199767f8SToomas Soome static int 1046199767f8SToomas Soome vdev_raidz_reconstruct_general(raidz_map_t *rm, int *tgts, int ntgts) 1047199767f8SToomas Soome { 1048199767f8SToomas Soome int n, i, c, t, tt; 1049199767f8SToomas Soome int nmissing_rows; 1050199767f8SToomas Soome int missing_rows[VDEV_RAIDZ_MAXPARITY]; 1051199767f8SToomas Soome int parity_map[VDEV_RAIDZ_MAXPARITY]; 1052199767f8SToomas Soome 1053199767f8SToomas Soome uint8_t *p, *pp; 1054199767f8SToomas Soome size_t psize; 1055199767f8SToomas Soome 1056199767f8SToomas Soome uint8_t *rows[VDEV_RAIDZ_MAXPARITY]; 1057199767f8SToomas Soome uint8_t *invrows[VDEV_RAIDZ_MAXPARITY]; 1058199767f8SToomas Soome uint8_t *used; 1059199767f8SToomas Soome 1060199767f8SToomas Soome int code = 0; 1061199767f8SToomas Soome 1062199767f8SToomas Soome 1063199767f8SToomas Soome n = rm->rm_cols - rm->rm_firstdatacol; 1064199767f8SToomas Soome 1065199767f8SToomas Soome /* 1066199767f8SToomas Soome * Figure out which data columns are missing. 1067199767f8SToomas Soome */ 1068199767f8SToomas Soome nmissing_rows = 0; 1069199767f8SToomas Soome for (t = 0; t < ntgts; t++) { 1070199767f8SToomas Soome if (tgts[t] >= rm->rm_firstdatacol) { 1071199767f8SToomas Soome missing_rows[nmissing_rows++] = 1072199767f8SToomas Soome tgts[t] - rm->rm_firstdatacol; 1073199767f8SToomas Soome } 1074199767f8SToomas Soome } 1075199767f8SToomas Soome 1076199767f8SToomas Soome /* 1077199767f8SToomas Soome * Figure out which parity columns to use to help generate the missing 1078199767f8SToomas Soome * data columns. 1079199767f8SToomas Soome */ 1080199767f8SToomas Soome for (tt = 0, c = 0, i = 0; i < nmissing_rows; c++) { 1081199767f8SToomas Soome ASSERT(tt < ntgts); 1082199767f8SToomas Soome ASSERT(c < rm->rm_firstdatacol); 1083199767f8SToomas Soome 1084199767f8SToomas Soome /* 1085199767f8SToomas Soome * Skip any targeted parity columns. 1086199767f8SToomas Soome */ 1087199767f8SToomas Soome if (c == tgts[tt]) { 1088199767f8SToomas Soome tt++; 1089199767f8SToomas Soome continue; 1090199767f8SToomas Soome } 1091199767f8SToomas Soome 1092199767f8SToomas Soome code |= 1 << c; 1093199767f8SToomas Soome 1094199767f8SToomas Soome parity_map[i] = c; 1095199767f8SToomas Soome i++; 1096199767f8SToomas Soome } 1097199767f8SToomas Soome 1098199767f8SToomas Soome ASSERT(code != 0); 1099199767f8SToomas Soome ASSERT3U(code, <, 1 << VDEV_RAIDZ_MAXPARITY); 1100199767f8SToomas Soome 1101199767f8SToomas Soome psize = (sizeof (rows[0][0]) + sizeof (invrows[0][0])) * 1102199767f8SToomas Soome nmissing_rows * n + sizeof (used[0]) * n; 1103199767f8SToomas Soome p = kmem_alloc(psize, KM_SLEEP); 1104199767f8SToomas Soome 1105199767f8SToomas Soome for (pp = p, i = 0; i < nmissing_rows; i++) { 1106199767f8SToomas Soome rows[i] = pp; 1107199767f8SToomas Soome pp += n; 1108199767f8SToomas Soome invrows[i] = pp; 1109199767f8SToomas Soome pp += n; 1110199767f8SToomas Soome } 1111199767f8SToomas Soome used = pp; 1112199767f8SToomas Soome 1113199767f8SToomas Soome for (i = 0; i < nmissing_rows; i++) { 1114199767f8SToomas Soome used[i] = parity_map[i]; 1115199767f8SToomas Soome } 1116199767f8SToomas Soome 1117199767f8SToomas Soome for (tt = 0, c = rm->rm_firstdatacol; c < rm->rm_cols; c++) { 1118199767f8SToomas Soome if (tt < nmissing_rows && 1119199767f8SToomas Soome c == missing_rows[tt] + rm->rm_firstdatacol) { 1120199767f8SToomas Soome tt++; 1121199767f8SToomas Soome continue; 1122199767f8SToomas Soome } 1123199767f8SToomas Soome 1124199767f8SToomas Soome ASSERT3S(i, <, n); 1125199767f8SToomas Soome used[i] = c; 1126199767f8SToomas Soome i++; 1127199767f8SToomas Soome } 1128199767f8SToomas Soome 1129199767f8SToomas Soome /* 1130199767f8SToomas Soome * Initialize the interesting rows of the matrix. 1131199767f8SToomas Soome */ 1132199767f8SToomas Soome vdev_raidz_matrix_init(rm, n, nmissing_rows, parity_map, rows); 1133199767f8SToomas Soome 1134199767f8SToomas Soome /* 1135199767f8SToomas Soome * Invert the matrix. 1136199767f8SToomas Soome */ 1137199767f8SToomas Soome vdev_raidz_matrix_invert(rm, n, nmissing_rows, missing_rows, rows, 1138199767f8SToomas Soome invrows, used); 1139199767f8SToomas Soome 1140199767f8SToomas Soome /* 1141199767f8SToomas Soome * Reconstruct the missing data using the generated matrix. 1142199767f8SToomas Soome */ 1143199767f8SToomas Soome vdev_raidz_matrix_reconstruct(rm, n, nmissing_rows, missing_rows, 1144199767f8SToomas Soome invrows, used); 1145199767f8SToomas Soome 1146199767f8SToomas Soome kmem_free(p, psize); 1147199767f8SToomas Soome 1148199767f8SToomas Soome return (code); 1149199767f8SToomas Soome } 1150199767f8SToomas Soome 1151199767f8SToomas Soome static int 1152199767f8SToomas Soome vdev_raidz_reconstruct(raidz_map_t *rm, int *t, int nt) 1153199767f8SToomas Soome { 1154199767f8SToomas Soome int tgts[VDEV_RAIDZ_MAXPARITY]; 1155199767f8SToomas Soome int ntgts; 1156199767f8SToomas Soome int i, c; 1157199767f8SToomas Soome int code; 1158199767f8SToomas Soome int nbadparity, nbaddata; 1159199767f8SToomas Soome 1160199767f8SToomas Soome /* 1161199767f8SToomas Soome * The tgts list must already be sorted. 1162199767f8SToomas Soome */ 1163199767f8SToomas Soome for (i = 1; i < nt; i++) { 1164199767f8SToomas Soome ASSERT(t[i] > t[i - 1]); 1165199767f8SToomas Soome } 1166199767f8SToomas Soome 1167199767f8SToomas Soome nbadparity = rm->rm_firstdatacol; 1168199767f8SToomas Soome nbaddata = rm->rm_cols - nbadparity; 1169199767f8SToomas Soome ntgts = 0; 1170199767f8SToomas Soome for (i = 0, c = 0; c < rm->rm_cols; c++) { 1171199767f8SToomas Soome if (i < nt && c == t[i]) { 1172199767f8SToomas Soome tgts[ntgts++] = c; 1173199767f8SToomas Soome i++; 1174199767f8SToomas Soome } else if (rm->rm_col[c].rc_error != 0) { 1175199767f8SToomas Soome tgts[ntgts++] = c; 1176199767f8SToomas Soome } else if (c >= rm->rm_firstdatacol) { 1177199767f8SToomas Soome nbaddata--; 1178199767f8SToomas Soome } else { 1179199767f8SToomas Soome nbadparity--; 1180199767f8SToomas Soome } 1181199767f8SToomas Soome } 1182199767f8SToomas Soome 1183199767f8SToomas Soome ASSERT(ntgts >= nt); 1184199767f8SToomas Soome ASSERT(nbaddata >= 0); 1185199767f8SToomas Soome ASSERT(nbaddata + nbadparity == ntgts); 1186199767f8SToomas Soome 1187199767f8SToomas Soome code = vdev_raidz_reconstruct_general(rm, tgts, ntgts); 1188199767f8SToomas Soome ASSERT(code < (1 << VDEV_RAIDZ_MAXPARITY)); 1189199767f8SToomas Soome ASSERT(code > 0); 1190199767f8SToomas Soome return (code); 1191199767f8SToomas Soome } 1192199767f8SToomas Soome 1193199767f8SToomas Soome static raidz_map_t * 1194199767f8SToomas Soome vdev_raidz_map_alloc(void *data, off_t offset, size_t size, uint64_t unit_shift, 1195199767f8SToomas Soome uint64_t dcols, uint64_t nparity) 1196199767f8SToomas Soome { 1197199767f8SToomas Soome raidz_map_t *rm; 1198199767f8SToomas Soome uint64_t b = offset >> unit_shift; 1199199767f8SToomas Soome uint64_t s = size >> unit_shift; 1200199767f8SToomas Soome uint64_t f = b % dcols; 1201199767f8SToomas Soome uint64_t o = (b / dcols) << unit_shift; 1202199767f8SToomas Soome uint64_t q, r, c, bc, col, acols, scols, coff, devidx, asize, tot; 1203199767f8SToomas Soome 1204199767f8SToomas Soome q = s / (dcols - nparity); 1205199767f8SToomas Soome r = s - q * (dcols - nparity); 1206199767f8SToomas Soome bc = (r == 0 ? 0 : r + nparity); 1207199767f8SToomas Soome tot = s + nparity * (q + (r == 0 ? 0 : 1)); 1208199767f8SToomas Soome 1209199767f8SToomas Soome if (q == 0) { 1210199767f8SToomas Soome acols = bc; 1211199767f8SToomas Soome scols = MIN(dcols, roundup(bc, nparity + 1)); 1212199767f8SToomas Soome } else { 1213199767f8SToomas Soome acols = dcols; 1214199767f8SToomas Soome scols = dcols; 1215199767f8SToomas Soome } 1216199767f8SToomas Soome 1217199767f8SToomas Soome ASSERT3U(acols, <=, scols); 1218199767f8SToomas Soome 1219199767f8SToomas Soome rm = zfs_alloc(offsetof(raidz_map_t, rm_col[scols])); 1220199767f8SToomas Soome 1221199767f8SToomas Soome rm->rm_cols = acols; 1222199767f8SToomas Soome rm->rm_scols = scols; 1223199767f8SToomas Soome rm->rm_bigcols = bc; 1224199767f8SToomas Soome rm->rm_skipstart = bc; 1225199767f8SToomas Soome rm->rm_missingdata = 0; 1226199767f8SToomas Soome rm->rm_missingparity = 0; 1227199767f8SToomas Soome rm->rm_firstdatacol = nparity; 1228199767f8SToomas Soome rm->rm_reports = 0; 1229199767f8SToomas Soome rm->rm_freed = 0; 1230199767f8SToomas Soome rm->rm_ecksuminjected = 0; 1231199767f8SToomas Soome 1232199767f8SToomas Soome asize = 0; 1233199767f8SToomas Soome 1234199767f8SToomas Soome for (c = 0; c < scols; c++) { 1235199767f8SToomas Soome col = f + c; 1236199767f8SToomas Soome coff = o; 1237199767f8SToomas Soome if (col >= dcols) { 1238199767f8SToomas Soome col -= dcols; 1239199767f8SToomas Soome coff += 1ULL << unit_shift; 1240199767f8SToomas Soome } 1241199767f8SToomas Soome rm->rm_col[c].rc_devidx = col; 1242199767f8SToomas Soome rm->rm_col[c].rc_offset = coff; 1243199767f8SToomas Soome rm->rm_col[c].rc_data = NULL; 1244199767f8SToomas Soome rm->rm_col[c].rc_error = 0; 1245199767f8SToomas Soome rm->rm_col[c].rc_tried = 0; 1246199767f8SToomas Soome rm->rm_col[c].rc_skipped = 0; 1247199767f8SToomas Soome 1248199767f8SToomas Soome if (c >= acols) 1249199767f8SToomas Soome rm->rm_col[c].rc_size = 0; 1250199767f8SToomas Soome else if (c < bc) 1251199767f8SToomas Soome rm->rm_col[c].rc_size = (q + 1) << unit_shift; 1252199767f8SToomas Soome else 1253199767f8SToomas Soome rm->rm_col[c].rc_size = q << unit_shift; 1254199767f8SToomas Soome 1255199767f8SToomas Soome asize += rm->rm_col[c].rc_size; 1256199767f8SToomas Soome } 1257199767f8SToomas Soome 1258199767f8SToomas Soome ASSERT3U(asize, ==, tot << unit_shift); 1259199767f8SToomas Soome rm->rm_asize = roundup(asize, (nparity + 1) << unit_shift); 1260199767f8SToomas Soome rm->rm_nskip = roundup(tot, nparity + 1) - tot; 1261199767f8SToomas Soome ASSERT3U(rm->rm_asize - asize, ==, rm->rm_nskip << unit_shift); 1262199767f8SToomas Soome ASSERT3U(rm->rm_nskip, <=, nparity); 1263199767f8SToomas Soome 1264199767f8SToomas Soome for (c = 0; c < rm->rm_firstdatacol; c++) 1265199767f8SToomas Soome rm->rm_col[c].rc_data = zfs_alloc(rm->rm_col[c].rc_size); 1266199767f8SToomas Soome 1267199767f8SToomas Soome rm->rm_col[c].rc_data = data; 1268199767f8SToomas Soome 1269199767f8SToomas Soome for (c = c + 1; c < acols; c++) 1270199767f8SToomas Soome rm->rm_col[c].rc_data = (char *)rm->rm_col[c - 1].rc_data + 1271199767f8SToomas Soome rm->rm_col[c - 1].rc_size; 1272199767f8SToomas Soome 1273199767f8SToomas Soome /* 1274199767f8SToomas Soome * If all data stored spans all columns, there's a danger that parity 1275199767f8SToomas Soome * will always be on the same device and, since parity isn't read 1276199767f8SToomas Soome * during normal operation, that that device's I/O bandwidth won't be 1277199767f8SToomas Soome * used effectively. We therefore switch the parity every 1MB. 1278199767f8SToomas Soome * 1279199767f8SToomas Soome * ... at least that was, ostensibly, the theory. As a practical 1280199767f8SToomas Soome * matter unless we juggle the parity between all devices evenly, we 1281199767f8SToomas Soome * won't see any benefit. Further, occasional writes that aren't a 1282199767f8SToomas Soome * multiple of the LCM of the number of children and the minimum 1283199767f8SToomas Soome * stripe width are sufficient to avoid pessimal behavior. 1284199767f8SToomas Soome * Unfortunately, this decision created an implicit on-disk format 1285199767f8SToomas Soome * requirement that we need to support for all eternity, but only 1286199767f8SToomas Soome * for single-parity RAID-Z. 1287199767f8SToomas Soome * 1288199767f8SToomas Soome * If we intend to skip a sector in the zeroth column for padding 1289199767f8SToomas Soome * we must make sure to note this swap. We will never intend to 1290199767f8SToomas Soome * skip the first column since at least one data and one parity 1291199767f8SToomas Soome * column must appear in each row. 1292199767f8SToomas Soome */ 1293199767f8SToomas Soome ASSERT(rm->rm_cols >= 2); 1294199767f8SToomas Soome ASSERT(rm->rm_col[0].rc_size == rm->rm_col[1].rc_size); 1295199767f8SToomas Soome 1296199767f8SToomas Soome if (rm->rm_firstdatacol == 1 && (offset & (1ULL << 20))) { 1297199767f8SToomas Soome devidx = rm->rm_col[0].rc_devidx; 1298199767f8SToomas Soome o = rm->rm_col[0].rc_offset; 1299199767f8SToomas Soome rm->rm_col[0].rc_devidx = rm->rm_col[1].rc_devidx; 1300199767f8SToomas Soome rm->rm_col[0].rc_offset = rm->rm_col[1].rc_offset; 1301199767f8SToomas Soome rm->rm_col[1].rc_devidx = devidx; 1302199767f8SToomas Soome rm->rm_col[1].rc_offset = o; 1303199767f8SToomas Soome 1304199767f8SToomas Soome if (rm->rm_skipstart == 0) 1305199767f8SToomas Soome rm->rm_skipstart = 1; 1306199767f8SToomas Soome } 1307199767f8SToomas Soome 1308199767f8SToomas Soome return (rm); 1309199767f8SToomas Soome } 1310199767f8SToomas Soome 1311199767f8SToomas Soome static void 1312199767f8SToomas Soome vdev_raidz_map_free(raidz_map_t *rm) 1313199767f8SToomas Soome { 1314199767f8SToomas Soome int c; 1315199767f8SToomas Soome 1316199767f8SToomas Soome for (c = rm->rm_firstdatacol - 1; c >= 0; c--) 1317199767f8SToomas Soome zfs_free(rm->rm_col[c].rc_data, rm->rm_col[c].rc_size); 1318199767f8SToomas Soome 1319199767f8SToomas Soome zfs_free(rm, offsetof(raidz_map_t, rm_col[rm->rm_scols])); 1320199767f8SToomas Soome } 1321199767f8SToomas Soome 1322199767f8SToomas Soome static vdev_t * 1323199767f8SToomas Soome vdev_child(vdev_t *pvd, uint64_t devidx) 1324199767f8SToomas Soome { 1325199767f8SToomas Soome vdev_t *cvd; 1326199767f8SToomas Soome 1327199767f8SToomas Soome STAILQ_FOREACH(cvd, &pvd->v_children, v_childlink) { 1328199767f8SToomas Soome if (cvd->v_id == devidx) 1329199767f8SToomas Soome break; 1330199767f8SToomas Soome } 1331199767f8SToomas Soome 1332199767f8SToomas Soome return (cvd); 1333199767f8SToomas Soome } 1334199767f8SToomas Soome 1335199767f8SToomas Soome /* 1336199767f8SToomas Soome * We keep track of whether or not there were any injected errors, so that 1337199767f8SToomas Soome * any ereports we generate can note it. 1338199767f8SToomas Soome */ 1339199767f8SToomas Soome static int 1340*4a04e8dbSToomas Soome raidz_checksum_verify(const spa_t *spa, const blkptr_t *bp, void *data, 1341*4a04e8dbSToomas Soome uint64_t size) 1342199767f8SToomas Soome { 1343199767f8SToomas Soome 1344*4a04e8dbSToomas Soome return (zio_checksum_verify(spa, bp, data)); 1345199767f8SToomas Soome } 1346199767f8SToomas Soome 1347199767f8SToomas Soome /* 1348199767f8SToomas Soome * Generate the parity from the data columns. If we tried and were able to 1349199767f8SToomas Soome * read the parity without error, verify that the generated parity matches the 1350199767f8SToomas Soome * data we read. If it doesn't, we fire off a checksum error. Return the 1351199767f8SToomas Soome * number such failures. 1352199767f8SToomas Soome */ 1353199767f8SToomas Soome static int 1354199767f8SToomas Soome raidz_parity_verify(raidz_map_t *rm) 1355199767f8SToomas Soome { 1356199767f8SToomas Soome void *orig[VDEV_RAIDZ_MAXPARITY]; 1357199767f8SToomas Soome int c, ret = 0; 1358199767f8SToomas Soome raidz_col_t *rc; 1359199767f8SToomas Soome 1360199767f8SToomas Soome for (c = 0; c < rm->rm_firstdatacol; c++) { 1361199767f8SToomas Soome rc = &rm->rm_col[c]; 1362199767f8SToomas Soome if (!rc->rc_tried || rc->rc_error != 0) 1363199767f8SToomas Soome continue; 1364199767f8SToomas Soome orig[c] = zfs_alloc(rc->rc_size); 1365199767f8SToomas Soome bcopy(rc->rc_data, orig[c], rc->rc_size); 1366199767f8SToomas Soome } 1367199767f8SToomas Soome 1368199767f8SToomas Soome vdev_raidz_generate_parity(rm); 1369199767f8SToomas Soome 1370199767f8SToomas Soome for (c = rm->rm_firstdatacol - 1; c >= 0; c--) { 1371199767f8SToomas Soome rc = &rm->rm_col[c]; 1372199767f8SToomas Soome if (!rc->rc_tried || rc->rc_error != 0) 1373199767f8SToomas Soome continue; 1374199767f8SToomas Soome if (bcmp(orig[c], rc->rc_data, rc->rc_size) != 0) { 1375199767f8SToomas Soome rc->rc_error = ECKSUM; 1376199767f8SToomas Soome ret++; 1377199767f8SToomas Soome } 1378199767f8SToomas Soome zfs_free(orig[c], rc->rc_size); 1379199767f8SToomas Soome } 1380199767f8SToomas Soome 1381199767f8SToomas Soome return (ret); 1382199767f8SToomas Soome } 1383199767f8SToomas Soome 1384199767f8SToomas Soome /* 1385199767f8SToomas Soome * Iterate over all combinations of bad data and attempt a reconstruction. 1386199767f8SToomas Soome * Note that the algorithm below is non-optimal because it doesn't take into 1387199767f8SToomas Soome * account how reconstruction is actually performed. For example, with 1388199767f8SToomas Soome * triple-parity RAID-Z the reconstruction procedure is the same if column 4 1389199767f8SToomas Soome * is targeted as invalid as if columns 1 and 4 are targeted since in both 1390199767f8SToomas Soome * cases we'd only use parity information in column 0. 1391199767f8SToomas Soome */ 1392199767f8SToomas Soome static int 1393*4a04e8dbSToomas Soome vdev_raidz_combrec(const spa_t *spa, raidz_map_t *rm, const blkptr_t *bp, 1394*4a04e8dbSToomas Soome void *data, off_t offset, uint64_t bytes, int total_errors, int data_errors) 1395199767f8SToomas Soome { 1396199767f8SToomas Soome raidz_col_t *rc; 1397199767f8SToomas Soome void *orig[VDEV_RAIDZ_MAXPARITY]; 1398199767f8SToomas Soome int tstore[VDEV_RAIDZ_MAXPARITY + 2]; 1399199767f8SToomas Soome int *tgts = &tstore[1]; 1400199767f8SToomas Soome int current, next, i, c, n; 1401199767f8SToomas Soome int code, ret = 0; 1402199767f8SToomas Soome 1403199767f8SToomas Soome ASSERT(total_errors < rm->rm_firstdatacol); 1404199767f8SToomas Soome 1405199767f8SToomas Soome /* 1406199767f8SToomas Soome * This simplifies one edge condition. 1407199767f8SToomas Soome */ 1408199767f8SToomas Soome tgts[-1] = -1; 1409199767f8SToomas Soome 1410199767f8SToomas Soome for (n = 1; n <= rm->rm_firstdatacol - total_errors; n++) { 1411199767f8SToomas Soome /* 1412199767f8SToomas Soome * Initialize the targets array by finding the first n columns 1413199767f8SToomas Soome * that contain no error. 1414199767f8SToomas Soome * 1415199767f8SToomas Soome * If there were no data errors, we need to ensure that we're 1416199767f8SToomas Soome * always explicitly attempting to reconstruct at least one 1417199767f8SToomas Soome * data column. To do this, we simply push the highest target 1418199767f8SToomas Soome * up into the data columns. 1419199767f8SToomas Soome */ 1420199767f8SToomas Soome for (c = 0, i = 0; i < n; i++) { 1421199767f8SToomas Soome if (i == n - 1 && data_errors == 0 && 1422199767f8SToomas Soome c < rm->rm_firstdatacol) { 1423199767f8SToomas Soome c = rm->rm_firstdatacol; 1424199767f8SToomas Soome } 1425199767f8SToomas Soome 1426199767f8SToomas Soome while (rm->rm_col[c].rc_error != 0) { 1427199767f8SToomas Soome c++; 1428199767f8SToomas Soome ASSERT3S(c, <, rm->rm_cols); 1429199767f8SToomas Soome } 1430199767f8SToomas Soome 1431199767f8SToomas Soome tgts[i] = c++; 1432199767f8SToomas Soome } 1433199767f8SToomas Soome 1434199767f8SToomas Soome /* 1435199767f8SToomas Soome * Setting tgts[n] simplifies the other edge condition. 1436199767f8SToomas Soome */ 1437199767f8SToomas Soome tgts[n] = rm->rm_cols; 1438199767f8SToomas Soome 1439199767f8SToomas Soome /* 1440199767f8SToomas Soome * These buffers were allocated in previous iterations. 1441199767f8SToomas Soome */ 1442199767f8SToomas Soome for (i = 0; i < n - 1; i++) { 1443199767f8SToomas Soome ASSERT(orig[i] != NULL); 1444199767f8SToomas Soome } 1445199767f8SToomas Soome 1446199767f8SToomas Soome orig[n - 1] = zfs_alloc(rm->rm_col[0].rc_size); 1447199767f8SToomas Soome 1448199767f8SToomas Soome current = 0; 1449199767f8SToomas Soome next = tgts[current]; 1450199767f8SToomas Soome 1451199767f8SToomas Soome while (current != n) { 1452199767f8SToomas Soome tgts[current] = next; 1453199767f8SToomas Soome current = 0; 1454199767f8SToomas Soome 1455199767f8SToomas Soome /* 1456199767f8SToomas Soome * Save off the original data that we're going to 1457199767f8SToomas Soome * attempt to reconstruct. 1458199767f8SToomas Soome */ 1459199767f8SToomas Soome for (i = 0; i < n; i++) { 1460199767f8SToomas Soome ASSERT(orig[i] != NULL); 1461199767f8SToomas Soome c = tgts[i]; 1462199767f8SToomas Soome ASSERT3S(c, >=, 0); 1463199767f8SToomas Soome ASSERT3S(c, <, rm->rm_cols); 1464199767f8SToomas Soome rc = &rm->rm_col[c]; 1465199767f8SToomas Soome bcopy(rc->rc_data, orig[i], rc->rc_size); 1466199767f8SToomas Soome } 1467199767f8SToomas Soome 1468199767f8SToomas Soome /* 1469199767f8SToomas Soome * Attempt a reconstruction and exit the outer loop on 1470199767f8SToomas Soome * success. 1471199767f8SToomas Soome */ 1472199767f8SToomas Soome code = vdev_raidz_reconstruct(rm, tgts, n); 1473*4a04e8dbSToomas Soome if (raidz_checksum_verify(spa, bp, data, bytes) == 0) { 1474199767f8SToomas Soome for (i = 0; i < n; i++) { 1475199767f8SToomas Soome c = tgts[i]; 1476199767f8SToomas Soome rc = &rm->rm_col[c]; 1477199767f8SToomas Soome ASSERT(rc->rc_error == 0); 1478199767f8SToomas Soome rc->rc_error = ECKSUM; 1479199767f8SToomas Soome } 1480199767f8SToomas Soome 1481199767f8SToomas Soome ret = code; 1482199767f8SToomas Soome goto done; 1483199767f8SToomas Soome } 1484199767f8SToomas Soome 1485199767f8SToomas Soome /* 1486199767f8SToomas Soome * Restore the original data. 1487199767f8SToomas Soome */ 1488199767f8SToomas Soome for (i = 0; i < n; i++) { 1489199767f8SToomas Soome c = tgts[i]; 1490199767f8SToomas Soome rc = &rm->rm_col[c]; 1491199767f8SToomas Soome bcopy(orig[i], rc->rc_data, rc->rc_size); 1492199767f8SToomas Soome } 1493199767f8SToomas Soome 1494199767f8SToomas Soome do { 1495199767f8SToomas Soome /* 1496199767f8SToomas Soome * Find the next valid column after the current 1497199767f8SToomas Soome * position.. 1498199767f8SToomas Soome */ 1499199767f8SToomas Soome for (next = tgts[current] + 1; 1500199767f8SToomas Soome next < rm->rm_cols && 1501199767f8SToomas Soome rm->rm_col[next].rc_error != 0; next++) 1502199767f8SToomas Soome continue; 1503199767f8SToomas Soome 1504199767f8SToomas Soome ASSERT(next <= tgts[current + 1]); 1505199767f8SToomas Soome 1506199767f8SToomas Soome /* 1507199767f8SToomas Soome * If that spot is available, we're done here. 1508199767f8SToomas Soome */ 1509199767f8SToomas Soome if (next != tgts[current + 1]) 1510199767f8SToomas Soome break; 1511199767f8SToomas Soome 1512199767f8SToomas Soome /* 1513199767f8SToomas Soome * Otherwise, find the next valid column after 1514199767f8SToomas Soome * the previous position. 1515199767f8SToomas Soome */ 1516199767f8SToomas Soome for (c = tgts[current - 1] + 1; 1517199767f8SToomas Soome rm->rm_col[c].rc_error != 0; c++) 1518199767f8SToomas Soome continue; 1519199767f8SToomas Soome 1520199767f8SToomas Soome tgts[current] = c; 1521199767f8SToomas Soome current++; 1522199767f8SToomas Soome 1523199767f8SToomas Soome } while (current != n); 1524199767f8SToomas Soome } 1525199767f8SToomas Soome } 1526199767f8SToomas Soome n--; 1527199767f8SToomas Soome done: 1528199767f8SToomas Soome for (i = n - 1; i >= 0; i--) { 1529199767f8SToomas Soome zfs_free(orig[i], rm->rm_col[0].rc_size); 1530199767f8SToomas Soome } 1531199767f8SToomas Soome 1532199767f8SToomas Soome return (ret); 1533199767f8SToomas Soome } 1534199767f8SToomas Soome 1535199767f8SToomas Soome static int 1536199767f8SToomas Soome vdev_raidz_read(vdev_t *vd, const blkptr_t *bp, void *data, 1537199767f8SToomas Soome off_t offset, size_t bytes) 1538199767f8SToomas Soome { 1539199767f8SToomas Soome vdev_t *tvd = vd->v_top; 1540199767f8SToomas Soome vdev_t *cvd; 1541199767f8SToomas Soome raidz_map_t *rm; 1542199767f8SToomas Soome raidz_col_t *rc; 1543199767f8SToomas Soome int c, error; 1544199767f8SToomas Soome int unexpected_errors; 1545199767f8SToomas Soome int parity_errors; 1546199767f8SToomas Soome int parity_untried; 1547199767f8SToomas Soome int data_errors; 1548199767f8SToomas Soome int total_errors; 1549199767f8SToomas Soome int n; 1550199767f8SToomas Soome int tgts[VDEV_RAIDZ_MAXPARITY]; 1551199767f8SToomas Soome int code; 1552199767f8SToomas Soome 1553199767f8SToomas Soome rc = NULL; /* gcc */ 1554199767f8SToomas Soome error = 0; 1555199767f8SToomas Soome 1556199767f8SToomas Soome rm = vdev_raidz_map_alloc(data, offset, bytes, tvd->v_ashift, 1557199767f8SToomas Soome vd->v_nchildren, vd->v_nparity); 1558199767f8SToomas Soome 1559199767f8SToomas Soome /* 1560199767f8SToomas Soome * Iterate over the columns in reverse order so that we hit the parity 1561199767f8SToomas Soome * last -- any errors along the way will force us to read the parity. 1562199767f8SToomas Soome */ 1563199767f8SToomas Soome for (c = rm->rm_cols - 1; c >= 0; c--) { 1564199767f8SToomas Soome rc = &rm->rm_col[c]; 1565199767f8SToomas Soome cvd = vdev_child(vd, rc->rc_devidx); 1566199767f8SToomas Soome if (cvd == NULL || cvd->v_state != VDEV_STATE_HEALTHY) { 1567199767f8SToomas Soome if (c >= rm->rm_firstdatacol) 1568199767f8SToomas Soome rm->rm_missingdata++; 1569199767f8SToomas Soome else 1570199767f8SToomas Soome rm->rm_missingparity++; 1571199767f8SToomas Soome rc->rc_error = ENXIO; 1572199767f8SToomas Soome rc->rc_tried = 1; /* don't even try */ 1573199767f8SToomas Soome rc->rc_skipped = 1; 1574199767f8SToomas Soome continue; 1575199767f8SToomas Soome } 1576199767f8SToomas Soome #if 0 /* XXX: Too hard for the boot code. */ 1577199767f8SToomas Soome if (vdev_dtl_contains(cvd, DTL_MISSING, zio->io_txg, 1)) { 1578199767f8SToomas Soome if (c >= rm->rm_firstdatacol) 1579199767f8SToomas Soome rm->rm_missingdata++; 1580199767f8SToomas Soome else 1581199767f8SToomas Soome rm->rm_missingparity++; 1582199767f8SToomas Soome rc->rc_error = ESTALE; 1583199767f8SToomas Soome rc->rc_skipped = 1; 1584199767f8SToomas Soome continue; 1585199767f8SToomas Soome } 1586199767f8SToomas Soome #endif 1587199767f8SToomas Soome if (c >= rm->rm_firstdatacol || rm->rm_missingdata > 0) { 1588199767f8SToomas Soome rc->rc_error = cvd->v_read(cvd, NULL, rc->rc_data, 1589199767f8SToomas Soome rc->rc_offset, rc->rc_size); 1590199767f8SToomas Soome rc->rc_tried = 1; 1591199767f8SToomas Soome rc->rc_skipped = 0; 1592199767f8SToomas Soome } 1593199767f8SToomas Soome } 1594199767f8SToomas Soome 1595199767f8SToomas Soome reconstruct: 1596199767f8SToomas Soome unexpected_errors = 0; 1597199767f8SToomas Soome parity_errors = 0; 1598199767f8SToomas Soome parity_untried = 0; 1599199767f8SToomas Soome data_errors = 0; 1600199767f8SToomas Soome total_errors = 0; 1601199767f8SToomas Soome 1602199767f8SToomas Soome ASSERT(rm->rm_missingparity <= rm->rm_firstdatacol); 1603199767f8SToomas Soome ASSERT(rm->rm_missingdata <= rm->rm_cols - rm->rm_firstdatacol); 1604199767f8SToomas Soome 1605199767f8SToomas Soome for (c = 0; c < rm->rm_cols; c++) { 1606199767f8SToomas Soome rc = &rm->rm_col[c]; 1607199767f8SToomas Soome 1608199767f8SToomas Soome if (rc->rc_error) { 1609199767f8SToomas Soome ASSERT(rc->rc_error != ECKSUM); /* child has no bp */ 1610199767f8SToomas Soome 1611199767f8SToomas Soome if (c < rm->rm_firstdatacol) 1612199767f8SToomas Soome parity_errors++; 1613199767f8SToomas Soome else 1614199767f8SToomas Soome data_errors++; 1615199767f8SToomas Soome 1616199767f8SToomas Soome if (!rc->rc_skipped) 1617199767f8SToomas Soome unexpected_errors++; 1618199767f8SToomas Soome 1619199767f8SToomas Soome total_errors++; 1620199767f8SToomas Soome } else if (c < rm->rm_firstdatacol && !rc->rc_tried) { 1621199767f8SToomas Soome parity_untried++; 1622199767f8SToomas Soome } 1623199767f8SToomas Soome } 1624199767f8SToomas Soome 1625199767f8SToomas Soome /* 1626199767f8SToomas Soome * There are three potential phases for a read: 1627199767f8SToomas Soome * 1. produce valid data from the columns read 1628199767f8SToomas Soome * 2. read all disks and try again 1629199767f8SToomas Soome * 3. perform combinatorial reconstruction 1630199767f8SToomas Soome * 1631199767f8SToomas Soome * Each phase is progressively both more expensive and less likely to 1632199767f8SToomas Soome * occur. If we encounter more errors than we can repair or all phases 1633199767f8SToomas Soome * fail, we have no choice but to return an error. 1634199767f8SToomas Soome */ 1635199767f8SToomas Soome 1636199767f8SToomas Soome /* 1637199767f8SToomas Soome * If the number of errors we saw was correctable -- less than or equal 1638199767f8SToomas Soome * to the number of parity disks read -- attempt to produce data that 1639199767f8SToomas Soome * has a valid checksum. Naturally, this case applies in the absence of 1640199767f8SToomas Soome * any errors. 1641199767f8SToomas Soome */ 1642199767f8SToomas Soome if (total_errors <= rm->rm_firstdatacol - parity_untried) { 1643199767f8SToomas Soome if (data_errors == 0) { 1644*4a04e8dbSToomas Soome if (raidz_checksum_verify(vd->spa, bp, data, bytes) == 0) { 1645199767f8SToomas Soome /* 1646199767f8SToomas Soome * If we read parity information (unnecessarily 1647199767f8SToomas Soome * as it happens since no reconstruction was 1648199767f8SToomas Soome * needed) regenerate and verify the parity. 1649199767f8SToomas Soome * We also regenerate parity when resilvering 1650199767f8SToomas Soome * so we can write it out to the failed device 1651199767f8SToomas Soome * later. 1652199767f8SToomas Soome */ 1653199767f8SToomas Soome if (parity_errors + parity_untried < 1654199767f8SToomas Soome rm->rm_firstdatacol) { 1655199767f8SToomas Soome n = raidz_parity_verify(rm); 1656199767f8SToomas Soome unexpected_errors += n; 1657199767f8SToomas Soome ASSERT(parity_errors + n <= 1658199767f8SToomas Soome rm->rm_firstdatacol); 1659199767f8SToomas Soome } 1660199767f8SToomas Soome goto done; 1661199767f8SToomas Soome } 1662199767f8SToomas Soome } else { 1663199767f8SToomas Soome /* 1664199767f8SToomas Soome * We either attempt to read all the parity columns or 1665199767f8SToomas Soome * none of them. If we didn't try to read parity, we 1666199767f8SToomas Soome * wouldn't be here in the correctable case. There must 1667199767f8SToomas Soome * also have been fewer parity errors than parity 1668199767f8SToomas Soome * columns or, again, we wouldn't be in this code path. 1669199767f8SToomas Soome */ 1670199767f8SToomas Soome ASSERT(parity_untried == 0); 1671199767f8SToomas Soome ASSERT(parity_errors < rm->rm_firstdatacol); 1672199767f8SToomas Soome 1673199767f8SToomas Soome /* 1674199767f8SToomas Soome * Identify the data columns that reported an error. 1675199767f8SToomas Soome */ 1676199767f8SToomas Soome n = 0; 1677199767f8SToomas Soome for (c = rm->rm_firstdatacol; c < rm->rm_cols; c++) { 1678199767f8SToomas Soome rc = &rm->rm_col[c]; 1679199767f8SToomas Soome if (rc->rc_error != 0) { 1680199767f8SToomas Soome ASSERT(n < VDEV_RAIDZ_MAXPARITY); 1681199767f8SToomas Soome tgts[n++] = c; 1682199767f8SToomas Soome } 1683199767f8SToomas Soome } 1684199767f8SToomas Soome 1685199767f8SToomas Soome ASSERT(rm->rm_firstdatacol >= n); 1686199767f8SToomas Soome 1687199767f8SToomas Soome code = vdev_raidz_reconstruct(rm, tgts, n); 1688199767f8SToomas Soome 1689*4a04e8dbSToomas Soome if (raidz_checksum_verify(vd->spa, bp, data, bytes) == 0) { 1690199767f8SToomas Soome /* 1691199767f8SToomas Soome * If we read more parity disks than were used 1692199767f8SToomas Soome * for reconstruction, confirm that the other 1693199767f8SToomas Soome * parity disks produced correct data. This 1694199767f8SToomas Soome * routine is suboptimal in that it regenerates 1695199767f8SToomas Soome * the parity that we already used in addition 1696199767f8SToomas Soome * to the parity that we're attempting to 1697199767f8SToomas Soome * verify, but this should be a relatively 1698199767f8SToomas Soome * uncommon case, and can be optimized if it 1699199767f8SToomas Soome * becomes a problem. Note that we regenerate 1700199767f8SToomas Soome * parity when resilvering so we can write it 1701199767f8SToomas Soome * out to failed devices later. 1702199767f8SToomas Soome */ 1703199767f8SToomas Soome if (parity_errors < rm->rm_firstdatacol - n) { 1704199767f8SToomas Soome n = raidz_parity_verify(rm); 1705199767f8SToomas Soome unexpected_errors += n; 1706199767f8SToomas Soome ASSERT(parity_errors + n <= 1707199767f8SToomas Soome rm->rm_firstdatacol); 1708199767f8SToomas Soome } 1709199767f8SToomas Soome 1710199767f8SToomas Soome goto done; 1711199767f8SToomas Soome } 1712199767f8SToomas Soome } 1713199767f8SToomas Soome } 1714199767f8SToomas Soome 1715199767f8SToomas Soome /* 1716199767f8SToomas Soome * This isn't a typical situation -- either we got a read 1717199767f8SToomas Soome * error or a child silently returned bad data. Read every 1718199767f8SToomas Soome * block so we can try again with as much data and parity as 1719199767f8SToomas Soome * we can track down. If we've already been through once 1720199767f8SToomas Soome * before, all children will be marked as tried so we'll 1721199767f8SToomas Soome * proceed to combinatorial reconstruction. 1722199767f8SToomas Soome */ 1723199767f8SToomas Soome unexpected_errors = 1; 1724199767f8SToomas Soome rm->rm_missingdata = 0; 1725199767f8SToomas Soome rm->rm_missingparity = 0; 1726199767f8SToomas Soome 1727199767f8SToomas Soome n = 0; 1728199767f8SToomas Soome for (c = 0; c < rm->rm_cols; c++) { 1729199767f8SToomas Soome rc = &rm->rm_col[c]; 1730199767f8SToomas Soome 1731199767f8SToomas Soome if (rc->rc_tried) 1732199767f8SToomas Soome continue; 1733199767f8SToomas Soome 1734199767f8SToomas Soome cvd = vdev_child(vd, rc->rc_devidx); 1735199767f8SToomas Soome ASSERT(cvd != NULL); 1736199767f8SToomas Soome rc->rc_error = cvd->v_read(cvd, NULL, 1737199767f8SToomas Soome rc->rc_data, rc->rc_offset, rc->rc_size); 1738199767f8SToomas Soome if (rc->rc_error == 0) 1739199767f8SToomas Soome n++; 1740199767f8SToomas Soome rc->rc_tried = 1; 1741199767f8SToomas Soome rc->rc_skipped = 0; 1742199767f8SToomas Soome } 1743199767f8SToomas Soome /* 1744199767f8SToomas Soome * If we managed to read anything more, retry the 1745199767f8SToomas Soome * reconstruction. 1746199767f8SToomas Soome */ 1747199767f8SToomas Soome if (n > 0) 1748199767f8SToomas Soome goto reconstruct; 1749199767f8SToomas Soome 1750199767f8SToomas Soome /* 1751199767f8SToomas Soome * At this point we've attempted to reconstruct the data given the 1752199767f8SToomas Soome * errors we detected, and we've attempted to read all columns. There 1753199767f8SToomas Soome * must, therefore, be one or more additional problems -- silent errors 1754199767f8SToomas Soome * resulting in invalid data rather than explicit I/O errors resulting 1755199767f8SToomas Soome * in absent data. We check if there is enough additional data to 1756199767f8SToomas Soome * possibly reconstruct the data and then perform combinatorial 1757199767f8SToomas Soome * reconstruction over all possible combinations. If that fails, 1758199767f8SToomas Soome * we're cooked. 1759199767f8SToomas Soome */ 1760199767f8SToomas Soome if (total_errors > rm->rm_firstdatacol) { 1761199767f8SToomas Soome error = EIO; 1762199767f8SToomas Soome } else if (total_errors < rm->rm_firstdatacol && 1763*4a04e8dbSToomas Soome (code = vdev_raidz_combrec(vd->spa, rm, bp, data, offset, bytes, 1764199767f8SToomas Soome total_errors, data_errors)) != 0) { 1765199767f8SToomas Soome /* 1766199767f8SToomas Soome * If we didn't use all the available parity for the 1767199767f8SToomas Soome * combinatorial reconstruction, verify that the remaining 1768199767f8SToomas Soome * parity is correct. 1769199767f8SToomas Soome */ 1770199767f8SToomas Soome if (code != (1 << rm->rm_firstdatacol) - 1) 1771199767f8SToomas Soome (void) raidz_parity_verify(rm); 1772199767f8SToomas Soome } else { 1773199767f8SToomas Soome /* 1774199767f8SToomas Soome * We're here because either: 1775199767f8SToomas Soome * 1776199767f8SToomas Soome * total_errors == rm_first_datacol, or 1777199767f8SToomas Soome * vdev_raidz_combrec() failed 1778199767f8SToomas Soome * 1779199767f8SToomas Soome * In either case, there is enough bad data to prevent 1780199767f8SToomas Soome * reconstruction. 1781199767f8SToomas Soome * 1782199767f8SToomas Soome * Start checksum ereports for all children which haven't 1783199767f8SToomas Soome * failed, and the IO wasn't speculative. 1784199767f8SToomas Soome */ 1785199767f8SToomas Soome error = ECKSUM; 1786199767f8SToomas Soome } 1787199767f8SToomas Soome 1788199767f8SToomas Soome done: 1789199767f8SToomas Soome vdev_raidz_map_free(rm); 1790199767f8SToomas Soome 1791199767f8SToomas Soome return (error); 1792199767f8SToomas Soome } 1793