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 *const raidz_gen_name[RAIDZ_GEN_NUM];
  74 extern const char *const 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_abdstruct;             /* rc_abd probably points here */
 110         abd_t *rc_abd;                  /* I/O data */
 111         abd_t *rc_orig_data;            /* pre-reconstruction */
 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_force_repair;        /* Write good data to this column */
 117         uint8_t rc_allow_repair;        /* Allow repair I/O to this column */
 118 } raidz_col_t;
 119
 120 typedef struct raidz_row {
 121         uint64_t rr_cols;               /* Regular column count */
 122         uint64_t rr_scols;              /* Count including skipped columns */
 123         uint64_t rr_bigcols;            /* Remainder data column count */
 124         uint64_t rr_missingdata;        /* Count of missing data devices */
 125         uint64_t rr_missingparity;      /* Count of missing parity devices */
 126         uint64_t rr_firstdatacol;       /* First data column/parity count */
 127         abd_t *rr_abd_empty;            /* dRAID empty sector buffer */
 128         int rr_nempty;                  /* empty sectors included in parity */
 129 #ifdef ZFS_DEBUG
 130         uint64_t rr_offset;             /* Logical offset for *_io_verify() */
 131         uint64_t rr_size;               /* Physical size for *_io_verify() */
 132 #endif
 133         raidz_col_t rr_col[0];          /* Flexible array of I/O columns */
 134 } raidz_row_t;
 135
 136 typedef struct raidz_map {
 137         boolean_t rm_ecksuminjected;    /* checksum error was injected */
 138         int rm_nrows;                   /* Regular row count */
 139         int rm_nskip;                   /* RAIDZ sectors skipped for padding */
 140         int rm_skipstart;               /* Column index of padding start */
 141         const raidz_impl_ops_t *rm_ops; /* RAIDZ math operations */
 142         raidz_row_t *rm_row[0];         /* flexible array of rows */
 143 } raidz_map_t;
 144
 145
 146 #define RAIDZ_ORIGINAL_IMPL     (INT_MAX)
 147
 148 extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
 149 extern boolean_t raidz_will_scalar_work(void);
 150
 151 #if defined(__x86_64) && defined(HAVE_SSE2)     /* only x86_64 for now */
 152 extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
 153 #endif
 154 #if defined(__x86_64) && defined(HAVE_SSSE3)    /* only x86_64 for now */
 155 extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
 156 #endif
 157 #if defined(__x86_64) && defined(HAVE_AVX2)     /* only x86_64 for now */
 158 extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
 159 #endif
 160 #if defined(__x86_64) && defined(HAVE_AVX512F)  /* only x86_64 for now */
 161 extern const raidz_impl_ops_t vdev_raidz_avx512f_impl;
 162 #endif
 163 #if defined(__x86_64) && defined(HAVE_AVX512BW) /* only x86_64 for now */
 164 extern const raidz_impl_ops_t vdev_raidz_avx512bw_impl;
 165 #endif
 166 #if defined(__aarch64__)
 167 extern const raidz_impl_ops_t vdev_raidz_aarch64_neon_impl;
 168 extern const raidz_impl_ops_t vdev_raidz_aarch64_neonx2_impl;
 169 #endif
 170 #if defined(__powerpc__)
 171 extern const raidz_impl_ops_t vdev_raidz_powerpc_altivec_impl;
 172 #endif
 173
 174 /*
 175  * Commonly used raidz_map helpers
 176  *
 177  * raidz_parity         Returns parity of the RAIDZ block
 178  * raidz_ncols          Returns number of columns the block spans
 179  *                      Note, all rows have the same number of columns.
 180  * raidz_nbigcols       Returns number of big columns
 181  * raidz_col_p          Returns pointer to a column
 182  * raidz_col_size       Returns size of a column
 183  * raidz_big_size       Returns size of big columns
 184  * raidz_short_size     Returns size of short columns
 185  */
 186 #define raidz_parity(rm)        ((rm)->rm_row[0]->rr_firstdatacol)
 187 #define raidz_ncols(rm)         ((rm)->rm_row[0]->rr_cols)
 188 #define raidz_nbigcols(rm)      ((rm)->rm_bigcols)
 189 #define raidz_col_p(rm, c)      ((rm)->rm_col + (c))
 190 #define raidz_col_size(rm, c)   ((rm)->rm_col[c].rc_size)
 191 #define raidz_big_size(rm)      (raidz_col_size(rm, CODE_P))
 192 #define raidz_short_size(rm)    (raidz_col_size(rm, raidz_ncols(rm)-1))
 193
 194 /*
 195  * Macro defines an RAIDZ parity generation method
 196  *
 197  * @code        parity the function produce
 198  * @impl        name of the implementation
 199  */
 200 #define _RAIDZ_GEN_WRAP(code, impl)                                     \
 201 static void                                                             \
 202 impl ## _gen_ ## code(void *rrp)                                        \
 203 {                                                                       \
 204         raidz_row_t *rr = (raidz_row_t *)rrp;                           \
 205         raidz_generate_## code ## _impl(rr);                            \
 206 }
 207
 208 /*
 209  * Macro defines an RAIDZ data reconstruction method
 210  *
 211  * @code        parity the function produce
 212  * @impl        name of the implementation
 213  */
 214 #define _RAIDZ_REC_WRAP(code, impl)                                     \
 215 static int                                                              \
 216 impl ## _rec_ ## code(void *rrp, const int *tgtidx)                     \
 217 {                                                                       \
 218         raidz_row_t *rr = (raidz_row_t *)rrp;                           \
 219         return (raidz_reconstruct_## code ## _impl(rr, tgtidx));        \
 220 }
 221
 222 /*
 223  * Define all gen methods for an implementation
 224  *
 225  * @impl        name of the implementation
 226  */
 227 #define DEFINE_GEN_METHODS(impl)                                        \
 228         _RAIDZ_GEN_WRAP(p, impl);                                       \
 229         _RAIDZ_GEN_WRAP(pq, impl);                                      \
 230         _RAIDZ_GEN_WRAP(pqr, impl)
 231
 232 /*
 233  * Define all rec functions for an implementation
 234  *
 235  * @impl        name of the implementation
 236  */
 237 #define DEFINE_REC_METHODS(impl)                                        \
 238         _RAIDZ_REC_WRAP(p, impl);                                       \
 239         _RAIDZ_REC_WRAP(q, impl);                                       \
 240         _RAIDZ_REC_WRAP(r, impl);                                       \
 241         _RAIDZ_REC_WRAP(pq, impl);                                      \
 242         _RAIDZ_REC_WRAP(pr, impl);                                      \
 243         _RAIDZ_REC_WRAP(qr, impl);                                      \
 244         _RAIDZ_REC_WRAP(pqr, impl)
 245
 246 #define RAIDZ_GEN_METHODS(impl)                                         \
 247 {                                                                       \
 248         [RAIDZ_GEN_P] = & impl ## _gen_p,                               \
 249         [RAIDZ_GEN_PQ] = & impl ## _gen_pq,                             \
 250         [RAIDZ_GEN_PQR] = & impl ## _gen_pqr                            \
 251 }
 252
 253 #define RAIDZ_REC_METHODS(impl)                                         \
 254 {                                                                       \
 255         [RAIDZ_REC_P] = & impl ## _rec_p,                               \
 256         [RAIDZ_REC_Q] = & impl ## _rec_q,                               \
 257         [RAIDZ_REC_R] = & impl ## _rec_r,                               \
 258         [RAIDZ_REC_PQ] = & impl ## _rec_pq,                             \
 259         [RAIDZ_REC_PR] = & impl ## _rec_pr,                             \
 260         [RAIDZ_REC_QR] = & impl ## _rec_qr,                             \
 261         [RAIDZ_REC_PQR] = & impl ## _rec_pqr                            \
 262 }
 263
 264
 265 typedef struct raidz_impl_kstat {
 266         uint64_t gen[RAIDZ_GEN_NUM];    /* gen method speed B/s */
 267         uint64_t rec[RAIDZ_REC_NUM];    /* rec method speed B/s */
 268 } raidz_impl_kstat_t;
 269
 270 /*
 271  * Enumerate various multiplication constants
 272  * used in reconstruction methods
 273  */
 274 typedef enum raidz_mul_info {
 275         /* Reconstruct Q */
 276         MUL_Q_X         = 0,
 277         /* Reconstruct R */
 278         MUL_R_X         = 0,
 279         /* Reconstruct PQ */
 280         MUL_PQ_X        = 0,
 281         MUL_PQ_Y        = 1,
 282         /* Reconstruct PR */
 283         MUL_PR_X        = 0,
 284         MUL_PR_Y        = 1,
 285         /* Reconstruct QR */
 286         MUL_QR_XQ       = 0,
 287         MUL_QR_X        = 1,
 288         MUL_QR_YQ       = 2,
 289         MUL_QR_Y        = 3,
 290         /* Reconstruct PQR */
 291         MUL_PQR_XP      = 0,
 292         MUL_PQR_XQ      = 1,
 293         MUL_PQR_XR      = 2,
 294         MUL_PQR_YU      = 3,
 295         MUL_PQR_YP      = 4,
 296         MUL_PQR_YQ      = 5,
 297
 298         MUL_CNT         = 6
 299 } raidz_mul_info_t;
 300
 301 /*
 302  * Powers of 2 in the Galois field.
 303  */
 304 extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
 305 /* Logs of 2 in the Galois field defined above. */
 306 extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));
 307
 308 /*
 309  * Multiply a given number by 2 raised to the given power.
 310  */
 311 static inline uint8_t
 312 vdev_raidz_exp2(const uint8_t a, const unsigned exp)
 313 {
 314         if (a == 0)
 315                 return (0);
 316
 317         return (vdev_raidz_pow2[(exp + (unsigned)vdev_raidz_log2[a]) % 255]);
 318 }
 319
 320 /*
 321  * Galois Field operations.
 322  *
 323  * gf_exp2      - computes 2 raised to the given power
 324  * gf_exp2      - computes 4 raised to the given power
 325  * gf_mul       - multiplication
 326  * gf_div       - division
 327  * gf_inv       - multiplicative inverse
 328  */
 329 typedef unsigned gf_t;
 330 typedef unsigned gf_log_t;
 331
 332 static inline gf_t
 333 gf_mul(const gf_t a, const gf_t b)
 334 {
 335         gf_log_t logsum;
 336
 337         if (a == 0 || b == 0)
 338                 return (0);
 339
 340         logsum = (gf_log_t)vdev_raidz_log2[a] + (gf_log_t)vdev_raidz_log2[b];
 341
 342         return ((gf_t)vdev_raidz_pow2[logsum % 255]);
 343 }
 344
 345 static inline gf_t
 346 gf_div(const gf_t  a, const gf_t b)
 347 {
 348         gf_log_t logsum;
 349
 350         ASSERT3U(b, >, 0);
 351         if (a == 0)
 352                 return (0);
 353
 354         logsum = (gf_log_t)255 + (gf_log_t)vdev_raidz_log2[a] -
 355             (gf_log_t)vdev_raidz_log2[b];
 356
 357         return ((gf_t)vdev_raidz_pow2[logsum % 255]);
 358 }
 359
 360 static inline gf_t
 361 gf_inv(const gf_t a)
 362 {
 363         gf_log_t logsum;
 364
 365         ASSERT3U(a, >, 0);
 366
 367         logsum = (gf_log_t)255 - (gf_log_t)vdev_raidz_log2[a];
 368
 369         return ((gf_t)vdev_raidz_pow2[logsum]);
 370 }
 371
 372 static inline gf_t
 373 gf_exp2(gf_log_t exp)
 374 {
 375         return (vdev_raidz_pow2[exp % 255]);
 376 }
 377
 378 static inline gf_t
 379 gf_exp4(gf_log_t exp)
 380 {
 381         ASSERT3U(exp, <=, 255);
 382         return ((gf_t)vdev_raidz_pow2[(2 * exp) % 255]);
 383 }
 384
 385 #ifdef  __cplusplus
 386 }
 387 #endif
 388
 389 #endif /* _VDEV_RAIDZ_H */