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