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
  32 #ifdef  __cplusplus
  33 extern "C" {
  34 #endif
  35
  36 #define CODE_P          (0U)
  37 #define CODE_Q          (1U)
  38 #define CODE_R          (2U)
  39
  40 #define PARITY_P        (1U)
  41 #define PARITY_PQ       (2U)
  42 #define PARITY_PQR      (3U)
  43
  44 #define TARGET_X        (0U)
  45 #define TARGET_Y        (1U)
  46 #define TARGET_Z        (2U)
  47
  48 /*
  49  * Parity generation methods indexes
  50  */
  51 enum raidz_math_gen_op {
  52         RAIDZ_GEN_P = 0,
  53         RAIDZ_GEN_PQ,
  54         RAIDZ_GEN_PQR,
  55         RAIDZ_GEN_NUM = 3
  56 };
  57 /*
  58  * Data reconstruction methods indexes
  59  */
  60 enum raidz_rec_op {
  61         RAIDZ_REC_P = 0,
  62         RAIDZ_REC_Q,
  63         RAIDZ_REC_R,
  64         RAIDZ_REC_PQ,
  65         RAIDZ_REC_PR,
  66         RAIDZ_REC_QR,
  67         RAIDZ_REC_PQR,
  68         RAIDZ_REC_NUM = 7
  69 };
  70
  71 extern const char *raidz_gen_name[RAIDZ_GEN_NUM];
  72 extern const char *raidz_rec_name[RAIDZ_REC_NUM];
  73
  74 /*
  75  * Methods used to define raidz implementation
  76  *
  77  * @raidz_gen_f Parity generation function
  78  *     @par1    pointer to raidz_map
  79  * @raidz_rec_f Data reconstruction function
  80  *     @par1    pointer to raidz_map
  81  *     @par2    array of reconstruction targets
  82  * @will_work_f Function returns TRUE if impl. is supported on the system
  83  * @init_impl_f Function is called once on init
  84  * @fini_impl_f Function is called once on fini
  85  */
  86 typedef void            (*raidz_gen_f)(void *);
  87 typedef int             (*raidz_rec_f)(void *, const int *);
  88 typedef boolean_t       (*will_work_f)(void);
  89 typedef void            (*init_impl_f)(void);
  90 typedef void            (*fini_impl_f)(void);
  91
  92 #define RAIDZ_IMPL_NAME_MAX     (16)
  93
  94 typedef struct raidz_impl_ops {
  95         init_impl_f init;
  96         fini_impl_f fini;
  97         raidz_gen_f gen[RAIDZ_GEN_NUM]; /* Parity generate functions */
  98         raidz_rec_f rec[RAIDZ_REC_NUM]; /* Data reconstruction functions */
  99         will_work_f is_supported;       /* Support check function */
 100         char name[RAIDZ_IMPL_NAME_MAX]; /* Name of the implementation */
 101 } raidz_impl_ops_t;
 102
 103 typedef struct raidz_col {
 104         size_t rc_devidx;               /* child device index for I/O */
 105         size_t rc_offset;               /* device offset */
 106         size_t rc_size;                 /* I/O size */
 107         void *rc_data;                  /* I/O data */
 108         void *rc_gdata;                 /* used to store the "good" version */
 109         int rc_error;                   /* I/O error for this device */
 110         unsigned int rc_tried;          /* Did we attempt this I/O column? */
 111         unsigned int rc_skipped;        /* Did we skip this I/O column? */
 112 } raidz_col_t;
 113
 114 typedef struct raidz_map {
 115         size_t rm_cols;                 /* Regular column count */
 116         size_t rm_scols;                /* Count including skipped columns */
 117         size_t rm_bigcols;              /* Number of oversized columns */
 118         size_t rm_asize;                /* Actual total I/O size */
 119         size_t rm_missingdata;          /* Count of missing data devices */
 120         size_t rm_missingparity;        /* Count of missing parity devices */
 121         size_t rm_firstdatacol;         /* First data column/parity count */
 122         size_t rm_nskip;                /* Skipped sectors for padding */
 123         size_t rm_skipstart;            /* Column index of padding start */
 124         void *rm_datacopy;              /* rm_asize-buffer of copied data */
 125         size_t rm_reports;              /* # of referencing checksum reports */
 126         unsigned int rm_freed;          /* map no longer has referencing ZIO */
 127         unsigned int rm_ecksuminjected; /* checksum error was injected */
 128         raidz_impl_ops_t *rm_ops;       /* RAIDZ math operations */
 129         raidz_col_t rm_col[1];          /* Flexible array of I/O columns */
 130 } raidz_map_t;
 131
 132 #define RAIDZ_ORIGINAL_IMPL     (INT_MAX)
 133
 134 extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
 135 #if defined(__x86_64) && defined(HAVE_SSE2)     /* only x86_64 for now */
 136 extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
 137 #endif
 138 #if defined(__x86_64) && defined(HAVE_SSSE3)    /* only x86_64 for now */
 139 extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
 140 #endif
 141 #if defined(__x86_64) && defined(HAVE_AVX2)     /* only x86_64 for now */
 142 extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
 143 #endif
 144 #if defined(__aarch64__)
 145 extern const raidz_impl_ops_t vdev_raidz_aarch64_neon_impl;
 146 extern const raidz_impl_ops_t vdev_raidz_aarch64_neonx2_impl;
 147 #endif
 148
 149 /*
 150  * Commonly used raidz_map helpers
 151  *
 152  * raidz_parity         Returns parity of the RAIDZ block
 153  * raidz_ncols          Returns number of columns the block spans
 154  * raidz_nbigcols       Returns number of big columns columns
 155  * raidz_col_p          Returns pointer to a column
 156  * raidz_col_size       Returns size of a column
 157  * raidz_big_size       Returns size of big columns
 158  * raidz_short_size     Returns size of short columns
 159  */
 160 #define raidz_parity(rm)        ((rm)->rm_firstdatacol)
 161 #define raidz_ncols(rm)         ((rm)->rm_cols)
 162 #define raidz_nbigcols(rm)      ((rm)->rm_bigcols)
 163 #define raidz_col_p(rm, c)      ((rm)->rm_col + (c))
 164 #define raidz_col_size(rm, c)   ((rm)->rm_col[c].rc_size)
 165 #define raidz_big_size(rm)      (raidz_col_size(rm, CODE_P))
 166 #define raidz_short_size(rm)    (raidz_col_size(rm, raidz_ncols(rm)-1))
 167
 168 /*
 169  * Macro defines an RAIDZ parity generation method
 170  *
 171  * @code        parity the function produce
 172  * @impl        name of the implementation
 173  */
 174 #define _RAIDZ_GEN_WRAP(code, impl)                                     \
 175 static void                                                             \
 176 impl ## _gen_ ## code(void *rmp)                                        \
 177 {                                                                       \
 178         raidz_map_t *rm = (raidz_map_t *) rmp;                          \
 179         raidz_generate_## code ## _impl(rm);                            \
 180 }
 181
 182 /*
 183  * Macro defines an RAIDZ data reconstruction method
 184  *
 185  * @code        parity the function produce
 186  * @impl        name of the implementation
 187  */
 188 #define _RAIDZ_REC_WRAP(code, impl)                                     \
 189 static int                                                              \
 190 impl ## _rec_ ## code(void *rmp, const int *tgtidx)                     \
 191 {                                                                       \
 192         raidz_map_t *rm = (raidz_map_t *) rmp;                          \
 193         return (raidz_reconstruct_## code ## _impl(rm, tgtidx));        \
 194 }
 195
 196 /*
 197  * Define all gen methods for an implementation
 198  *
 199  * @impl        name of the implementation
 200  */
 201 #define DEFINE_GEN_METHODS(impl)                                        \
 202         _RAIDZ_GEN_WRAP(p, impl);                                       \
 203         _RAIDZ_GEN_WRAP(pq, impl);                                      \
 204         _RAIDZ_GEN_WRAP(pqr, impl)
 205
 206 /*
 207  * Define all rec functions for an implementation
 208  *
 209  * @impl        name of the implementation
 210  */
 211 #define DEFINE_REC_METHODS(impl)                                        \
 212         _RAIDZ_REC_WRAP(p, impl);                                       \
 213         _RAIDZ_REC_WRAP(q, impl);                                       \
 214         _RAIDZ_REC_WRAP(r, impl);                                       \
 215         _RAIDZ_REC_WRAP(pq, impl);                                      \
 216         _RAIDZ_REC_WRAP(pr, impl);                                      \
 217         _RAIDZ_REC_WRAP(qr, impl);                                      \
 218         _RAIDZ_REC_WRAP(pqr, impl)
 219
 220 #define RAIDZ_GEN_METHODS(impl)                                         \
 221 {                                                                       \
 222         [RAIDZ_GEN_P] = & impl ## _gen_p,                               \
 223         [RAIDZ_GEN_PQ] = & impl ## _gen_pq,                             \
 224         [RAIDZ_GEN_PQR] = & impl ## _gen_pqr                            \
 225 }
 226
 227 #define RAIDZ_REC_METHODS(impl)                                         \
 228 {                                                                       \
 229         [RAIDZ_REC_P] = & impl ## _rec_p,                               \
 230         [RAIDZ_REC_Q] = & impl ## _rec_q,                               \
 231         [RAIDZ_REC_R] = & impl ## _rec_r,                               \
 232         [RAIDZ_REC_PQ] = & impl ## _rec_pq,                             \
 233         [RAIDZ_REC_PR] = & impl ## _rec_pr,                             \
 234         [RAIDZ_REC_QR] = & impl ## _rec_qr,                             \
 235         [RAIDZ_REC_PQR] = & impl ## _rec_pqr                            \
 236 }
 237
 238
 239 typedef struct raidz_impl_kstat {
 240         uint64_t gen[RAIDZ_GEN_NUM];    /* gen method speed B/s */
 241         uint64_t rec[RAIDZ_REC_NUM];    /* rec method speed B/s */
 242 } raidz_impl_kstat_t;
 243
 244 /*
 245  * Enumerate various multiplication constants
 246  * used in reconstruction methods
 247  */
 248 typedef enum raidz_mul_info {
 249         /* Reconstruct Q */
 250         MUL_Q_X         = 0,
 251         /* Reconstruct R */
 252         MUL_R_X         = 0,
 253         /* Reconstruct PQ */
 254         MUL_PQ_X        = 0,
 255         MUL_PQ_Y        = 1,
 256         /* Reconstruct PR */
 257         MUL_PR_X        = 0,
 258         MUL_PR_Y        = 1,
 259         /* Reconstruct QR */
 260         MUL_QR_XQ       = 0,
 261         MUL_QR_X        = 1,
 262         MUL_QR_YQ       = 2,
 263         MUL_QR_Y        = 3,
 264         /* Reconstruct PQR */
 265         MUL_PQR_XP      = 0,
 266         MUL_PQR_XQ      = 1,
 267         MUL_PQR_XR      = 2,
 268         MUL_PQR_YU      = 3,
 269         MUL_PQR_YP      = 4,
 270         MUL_PQR_YQ      = 5,
 271
 272         MUL_CNT         = 6
 273 } raidz_mul_info_t;
 274
 275 /*
 276  * Powers of 2 in the Galois field.
 277  */
 278 extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
 279 /* Logs of 2 in the Galois field defined above. */
 280 extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));
 281
 282 /*
 283  * Multiply a given number by 2 raised to the given power.
 284  */
 285 static inline uint8_t
 286 vdev_raidz_exp2(const uint8_t a, const unsigned exp)
 287 {
 288         if (a == 0)
 289                 return (0);
 290
 291         return (vdev_raidz_pow2[(exp + (unsigned) vdev_raidz_log2[a]) % 255]);
 292 }
 293
 294 /*
 295  * Galois Field operations.
 296  *
 297  * gf_exp2      - computes 2 raised to the given power
 298  * gf_exp2      - computes 4 raised to the given power
 299  * gf_mul       - multiplication
 300  * gf_div       - division
 301  * gf_inv       - multiplicative inverse
 302  */
 303 typedef unsigned gf_t;
 304 typedef unsigned gf_log_t;
 305
 306 static inline gf_t
 307 gf_mul(const gf_t a, const gf_t b)
 308 {
 309         gf_log_t logsum;
 310
 311         if (a == 0 || b == 0)
 312                 return (0);
 313
 314         logsum = (gf_log_t) vdev_raidz_log2[a] + (gf_log_t) vdev_raidz_log2[b];
 315
 316         return ((gf_t) vdev_raidz_pow2[logsum % 255]);
 317 }
 318
 319 static inline gf_t
 320 gf_div(const gf_t  a, const gf_t b)
 321 {
 322         gf_log_t logsum;
 323
 324         ASSERT3U(b, >, 0);
 325         if (a == 0)
 326                 return (0);
 327
 328         logsum = (gf_log_t) 255 + (gf_log_t) vdev_raidz_log2[a] -
 329             (gf_log_t) vdev_raidz_log2[b];
 330
 331         return ((gf_t) vdev_raidz_pow2[logsum % 255]);
 332 }
 333
 334 static inline gf_t
 335 gf_inv(const gf_t a)
 336 {
 337         gf_log_t logsum;
 338
 339         ASSERT3U(a, >, 0);
 340
 341         logsum = (gf_log_t) 255 - (gf_log_t) vdev_raidz_log2[a];
 342
 343         return ((gf_t) vdev_raidz_pow2[logsum]);
 344 }
 345
 346 static inline gf_t
 347 gf_exp2(gf_log_t exp)
 348 {
 349         return (vdev_raidz_pow2[exp % 255]);
 350 }
 351
 352 static inline gf_t
 353 gf_exp4(gf_log_t exp)
 354 {
 355         ASSERT3U(exp, <=, 255);
 356         return ((gf_t) vdev_raidz_pow2[(2 * exp) % 255]);
 357 }
 358
 359 #ifdef  __cplusplus
 360 }
 361 #endif
 362
 363 #endif /* _VDEV_RAIDZ_H */