include/sys/vdev_raidz_impl.h

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
  23  */
  24
  25 #ifndef _VDEV_RAIDZ_H
  26 #define _VDEV_RAIDZ_H
  27
  28 #include <sys/types.h>
  29 #include <sys/debug.h>
  30 #include <sys/kstat.h>
  31 #include <sys/abd.h>
  32 #include <sys/vdev_impl.h>
  33
  34 #ifdef  __cplusplus
  35 extern "C" {
  36 #endif
  37
  38 #define CODE_P          (0U)
  39 #define CODE_Q          (1U)
  40 #define CODE_R          (2U)
  41
  42 #define PARITY_P        (1U)
  43 #define PARITY_PQ       (2U)
  44 #define PARITY_PQR      (3U)
  45
  46 #define TARGET_X        (0U)
  47 #define TARGET_Y        (1U)
  48 #define TARGET_Z        (2U)
  49
  50 /*
  51  * Parity generation methods indexes
  52  */
  53 enum raidz_math_gen_op {
  54         RAIDZ_GEN_P = 0,
  55         RAIDZ_GEN_PQ,
  56         RAIDZ_GEN_PQR,
  57         RAIDZ_GEN_NUM = 3
  58 };
  59 /*
  60  * Data reconstruction methods indexes
  61  */
  62 enum raidz_rec_op {
  63         RAIDZ_REC_P = 0,
  64         RAIDZ_REC_Q,
  65         RAIDZ_REC_R,
  66         RAIDZ_REC_PQ,
  67         RAIDZ_REC_PR,
  68         RAIDZ_REC_QR,
  69         RAIDZ_REC_PQR,
  70         RAIDZ_REC_NUM = 7
  71 };
  72
  73 extern const char *raidz_gen_name[RAIDZ_GEN_NUM];
  74 extern const char *raidz_rec_name[RAIDZ_REC_NUM];
  75
  76 /*
  77  * Methods used to define raidz implementation
  78  *
  79  * @raidz_gen_f Parity generation function
  80  *     @par1    pointer to raidz_map
  81  * @raidz_rec_f Data reconstruction function
  82  *     @par1    pointer to raidz_map
  83  *     @par2    array of reconstruction targets
  84  * @will_work_f Function returns TRUE if impl. is supported on the system
  85  * @init_impl_f Function is called once on init
  86  * @fini_impl_f Function is called once on fini
  87  */
  88 typedef void            (*raidz_gen_f)(void *);
  89 typedef int             (*raidz_rec_f)(void *, const int *);
  90 typedef boolean_t       (*will_work_f)(void);
  91 typedef void            (*init_impl_f)(void);
  92 typedef void            (*fini_impl_f)(void);
  93
  94 #define RAIDZ_IMPL_NAME_MAX     (20)
  95
  96 typedef struct raidz_impl_ops {
  97         init_impl_f init;
  98         fini_impl_f fini;
  99         raidz_gen_f gen[RAIDZ_GEN_NUM]; /* Parity generate functions */
 100         raidz_rec_f rec[RAIDZ_REC_NUM]; /* Data reconstruction functions */
 101         will_work_f is_supported;       /* Support check function */
 102         char name[RAIDZ_IMPL_NAME_MAX]; /* Name of the implementation */
 103 } raidz_impl_ops_t;
 104
 105 typedef struct raidz_col {
 106         uint64_t rc_devidx;             /* child device index for I/O */
 107         uint64_t rc_offset;             /* device offset */
 108         uint64_t rc_size;               /* I/O size */
 109         abd_t *rc_abd;                  /* I/O data */
 110         void *rc_orig_data;             /* pre-reconstruction */
 111         abd_t *rc_gdata;                /* used to store the "good" version */
 112         int rc_error;                   /* I/O error for this device */
 113         uint8_t rc_tried;               /* Did we attempt this I/O column? */
 114         uint8_t rc_skipped;             /* Did we skip this I/O column? */
 115         uint8_t rc_need_orig_restore;   /* need to restore from orig_data? */
 116         uint8_t rc_repair;              /* Write good data to this column */
 117 } raidz_col_t;
 118
 119 typedef struct raidz_row {
 120         uint64_t rr_cols;               /* Regular column count */
 121         uint64_t rr_scols;              /* Count including skipped columns */
 122         uint64_t rr_bigcols;            /* Remainder data column count */
 123         uint64_t rr_missingdata;        /* Count of missing data devices */
 124         uint64_t rr_missingparity;      /* Count of missing parity devices */
 125         uint64_t rr_firstdatacol;       /* First data column/parity count */
 126         abd_t *rr_abd_copy;             /* rm_asize-buffer of copied data */
 127         abd_t *rr_abd_empty;            /* dRAID empty sector buffer */
 128         int rr_nempty;                  /* empty sectors included in parity */
 129         int rr_code;                    /* reconstruction code (unused) */
 130 #ifdef ZFS_DEBUG
 131         uint64_t rr_offset;             /* Logical offset for *_io_verify() */
 132         uint64_t rr_size;               /* Physical size for *_io_verify() */
 133 #endif
 134         raidz_col_t rr_col[0];          /* Flexible array of I/O columns */
 135 } raidz_row_t;
 136
 137 typedef struct raidz_map {
 138         uintptr_t rm_reports;           /* # of referencing checksum reports */
 139         boolean_t rm_freed;             /* map no longer has referencing ZIO */
 140         boolean_t rm_ecksuminjected;    /* checksum error was injected */
 141         int rm_nrows;                   /* Regular row count */
 142         int rm_nskip;                   /* RAIDZ sectors skipped for padding */
 143         int rm_skipstart;               /* Column index of padding start */
 144         const raidz_impl_ops_t *rm_ops; /* RAIDZ math operations */
 145         raidz_row_t *rm_row[0];         /* flexible array of rows */
 146 } raidz_map_t;
 147
 148
 149 #define RAIDZ_ORIGINAL_IMPL     (INT_MAX)
 150
 151 extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
 152 extern boolean_t raidz_will_scalar_work(void);
 153
 154 #if defined(__x86_64) && defined(HAVE_SSE2)     /* only x86_64 for now */
 155 extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
 156 #endif
 157 #if defined(__x86_64) && defined(HAVE_SSSE3)    /* only x86_64 for now */
 158 extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
 159 #endif
 160 #if defined(__x86_64) && defined(HAVE_AVX2)     /* only x86_64 for now */
 161 extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
 162 #endif
 163 #if defined(__x86_64) && defined(HAVE_AVX512F)  /* only x86_64 for now */
 164 extern const raidz_impl_ops_t vdev_raidz_avx512f_impl;
 165 #endif
 166 #if defined(__x86_64) && defined(HAVE_AVX512BW) /* only x86_64 for now */
 167 extern const raidz_impl_ops_t vdev_raidz_avx512bw_impl;
 168 #endif
 169 #if defined(__aarch64__)
 170 extern const raidz_impl_ops_t vdev_raidz_aarch64_neon_impl;
 171 extern const raidz_impl_ops_t vdev_raidz_aarch64_neonx2_impl;
 172 #endif
 173 #if defined(__powerpc__)
 174 extern const raidz_impl_ops_t vdev_raidz_powerpc_altivec_impl;
 175 #endif
 176
 177 /*
 178  * Commonly used raidz_map helpers
 179  *
 180  * raidz_parity         Returns parity of the RAIDZ block
 181  * raidz_ncols          Returns number of columns the block spans
 182  *                      Note, all rows have the same number of columns.
 183  * raidz_nbigcols       Returns number of big columns
 184  * raidz_col_p          Returns pointer to a column
 185  * raidz_col_size       Returns size of a column
 186  * raidz_big_size       Returns size of big columns
 187  * raidz_short_size     Returns size of short columns
 188  */
 189 #define raidz_parity(rm)        ((rm)->rm_row[0]->rr_firstdatacol)
 190 #define raidz_ncols(rm)         ((rm)->rm_row[0]->rr_cols)
 191 #define raidz_nbigcols(rm)      ((rm)->rm_bigcols)
 192 #define raidz_col_p(rm, c)      ((rm)->rm_col + (c))
 193 #define raidz_col_size(rm, c)   ((rm)->rm_col[c].rc_size)
 194 #define raidz_big_size(rm)      (raidz_col_size(rm, CODE_P))
 195 #define raidz_short_size(rm)    (raidz_col_size(rm, raidz_ncols(rm)-1))
 196
 197 /*
 198  * Macro defines an RAIDZ parity generation method
 199  *
 200  * @code        parity the function produce
 201  * @impl        name of the implementation
 202  */
 203 #define _RAIDZ_GEN_WRAP(code, impl)                                     \
 204 static void                                                             \
 205 impl ## _gen_ ## code(void *rrp)                                        \
 206 {                                                                       \
 207         raidz_row_t *rr = (raidz_row_t *)rrp;                           \
 208         raidz_generate_## code ## _impl(rr);                            \
 209 }
 210
 211 /*
 212  * Macro defines an RAIDZ data reconstruction method
 213  *
 214  * @code        parity the function produce
 215  * @impl        name of the implementation
 216  */
 217 #define _RAIDZ_REC_WRAP(code, impl)                                     \
 218 static int                                                              \
 219 impl ## _rec_ ## code(void *rrp, const int *tgtidx)                     \
 220 {                                                                       \
 221         raidz_row_t *rr = (raidz_row_t *)rrp;                           \
 222         return (raidz_reconstruct_## code ## _impl(rr, tgtidx));        \
 223 }
 224
 225 /*
 226  * Define all gen methods for an implementation
 227  *
 228  * @impl        name of the implementation
 229  */
 230 #define DEFINE_GEN_METHODS(impl)                                        \
 231         _RAIDZ_GEN_WRAP(p, impl);                                       \
 232         _RAIDZ_GEN_WRAP(pq, impl);                                      \
 233         _RAIDZ_GEN_WRAP(pqr, impl)
 234
 235 /*
 236  * Define all rec functions for an implementation
 237  *
 238  * @impl        name of the implementation
 239  */
 240 #define DEFINE_REC_METHODS(impl)                                        \
 241         _RAIDZ_REC_WRAP(p, impl);                                       \
 242         _RAIDZ_REC_WRAP(q, impl);                                       \
 243         _RAIDZ_REC_WRAP(r, impl);                                       \
 244         _RAIDZ_REC_WRAP(pq, impl);                                      \
 245         _RAIDZ_REC_WRAP(pr, impl);                                      \
 246         _RAIDZ_REC_WRAP(qr, impl);                                      \
 247         _RAIDZ_REC_WRAP(pqr, impl)
 248
 249 #define RAIDZ_GEN_METHODS(impl)                                         \
 250 {                                                                       \
 251         [RAIDZ_GEN_P] = & impl ## _gen_p,                               \
 252         [RAIDZ_GEN_PQ] = & impl ## _gen_pq,                             \
 253         [RAIDZ_GEN_PQR] = & impl ## _gen_pqr                            \
 254 }
 255
 256 #define RAIDZ_REC_METHODS(impl)                                         \
 257 {                                                                       \
 258         [RAIDZ_REC_P] = & impl ## _rec_p,                               \
 259         [RAIDZ_REC_Q] = & impl ## _rec_q,                               \
 260         [RAIDZ_REC_R] = & impl ## _rec_r,                               \
 261         [RAIDZ_REC_PQ] = & impl ## _rec_pq,                             \
 262         [RAIDZ_REC_PR] = & impl ## _rec_pr,                             \
 263         [RAIDZ_REC_QR] = & impl ## _rec_qr,                             \
 264         [RAIDZ_REC_PQR] = & impl ## _rec_pqr                            \
 265 }
 266
 267
 268 typedef struct raidz_impl_kstat {
 269         uint64_t gen[RAIDZ_GEN_NUM];    /* gen method speed B/s */
 270         uint64_t rec[RAIDZ_REC_NUM];    /* rec method speed B/s */
 271 } raidz_impl_kstat_t;
 272
 273 /*
 274  * Enumerate various multiplication constants
 275  * used in reconstruction methods
 276  */
 277 typedef enum raidz_mul_info {
 278         /* Reconstruct Q */
 279         MUL_Q_X         = 0,
 280         /* Reconstruct R */
 281         MUL_R_X         = 0,
 282         /* Reconstruct PQ */
 283         MUL_PQ_X        = 0,
 284         MUL_PQ_Y        = 1,
 285         /* Reconstruct PR */
 286         MUL_PR_X        = 0,
 287         MUL_PR_Y        = 1,
 288         /* Reconstruct QR */
 289         MUL_QR_XQ       = 0,
 290         MUL_QR_X        = 1,
 291         MUL_QR_YQ       = 2,
 292         MUL_QR_Y        = 3,
 293         /* Reconstruct PQR */
 294         MUL_PQR_XP      = 0,
 295         MUL_PQR_XQ      = 1,
 296         MUL_PQR_XR      = 2,
 297         MUL_PQR_YU      = 3,
 298         MUL_PQR_YP      = 4,
 299         MUL_PQR_YQ      = 5,
 300
 301         MUL_CNT         = 6
 302 } raidz_mul_info_t;
 303
 304 /*
 305  * Powers of 2 in the Galois field.
 306  */
 307 extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
 308 /* Logs of 2 in the Galois field defined above. */
 309 extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));
 310
 311 /*
 312  * Multiply a given number by 2 raised to the given power.
 313  */
 314 static inline uint8_t
 315 vdev_raidz_exp2(const uint8_t a, const unsigned exp)
 316 {
 317         if (a == 0)
 318                 return (0);
 319
 320         return (vdev_raidz_pow2[(exp + (unsigned)vdev_raidz_log2[a]) % 255]);
 321 }
 322
 323 /*
 324  * Galois Field operations.
 325  *
 326  * gf_exp2      - computes 2 raised to the given power
 327  * gf_exp2      - computes 4 raised to the given power
 328  * gf_mul       - multiplication
 329  * gf_div       - division
 330  * gf_inv       - multiplicative inverse
 331  */
 332 typedef unsigned gf_t;
 333 typedef unsigned gf_log_t;
 334
 335 static inline gf_t
 336 gf_mul(const gf_t a, const gf_t b)
 337 {
 338         gf_log_t logsum;
 339
 340         if (a == 0 || b == 0)
 341                 return (0);
 342
 343         logsum = (gf_log_t)vdev_raidz_log2[a] + (gf_log_t)vdev_raidz_log2[b];
 344
 345         return ((gf_t)vdev_raidz_pow2[logsum % 255]);
 346 }
 347
 348 static inline gf_t
 349 gf_div(const gf_t  a, const gf_t b)
 350 {
 351         gf_log_t logsum;
 352
 353         ASSERT3U(b, >, 0);
 354         if (a == 0)
 355                 return (0);
 356
 357         logsum = (gf_log_t)255 + (gf_log_t)vdev_raidz_log2[a] -
 358             (gf_log_t)vdev_raidz_log2[b];
 359
 360         return ((gf_t)vdev_raidz_pow2[logsum % 255]);
 361 }
 362
 363 static inline gf_t
 364 gf_inv(const gf_t a)
 365 {
 366         gf_log_t logsum;
 367
 368         ASSERT3U(a, >, 0);
 369
 370         logsum = (gf_log_t)255 - (gf_log_t)vdev_raidz_log2[a];
 371
 372         return ((gf_t)vdev_raidz_pow2[logsum]);
 373 }
 374
 375 static inline gf_t
 376 gf_exp2(gf_log_t exp)
 377 {
 378         return (vdev_raidz_pow2[exp % 255]);
 379 }
 380
 381 static inline gf_t
 382 gf_exp4(gf_log_t exp)
 383 {
 384         ASSERT3U(exp, <=, 255);
 385         return ((gf_t)vdev_raidz_pow2[(2 * exp) % 255]);
 386 }
 387
 388 #ifdef  __cplusplus
 389 }
 390 #endif
 391
 392 #endif /* _VDEV_RAIDZ_H */