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 /*
23 * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
24 */
25
26 #include <sys/vdev_raidz_impl.h>
27
28 /*
29 * Provide native CPU scalar routines.
30 * Support 32bit and 64bit CPUs.
31 */
32 #if ((~(0x0ULL)) >> 24) == 0xffULL
33 #define ELEM_SIZE 4
34 typedef uint32_t iv_t;
35 #elif ((~(0x0ULL)) >> 56) == 0xffULL
36 #define ELEM_SIZE 8
37 typedef uint64_t iv_t;
38 #endif
39
40 /*
41 * Vector type used in scalar implementation
42 *
43 * The union is expected to be of native CPU register size. Since addition
44 * uses XOR operation, it can be performed an all byte elements at once.
45 * Multiplication requires per byte access.
46 */
47 typedef union {
48 iv_t e;
49 uint8_t b[ELEM_SIZE];
50 } v_t;
51
52 /*
53 * Precomputed lookup tables for multiplication by a constant
54 *
55 * Reconstruction path requires multiplication by a constant factors. Instead of
56 * performing two step lookup (log & exp tables), a direct lookup can be used
57 * instead. Multiplication of element 'a' by a constant 'c' is obtained as:
58 *
59 * r = vdev_raidz_mul_lt[c_log][a];
60 *
61 * where c_log = vdev_raidz_log2[c]. Log of coefficient factors is used because
62 * they are faster to obtain while solving the syndrome equations.
63 *
64 * PERFORMANCE NOTE:
65 * Even though the complete lookup table uses 64kiB, only relatively small
66 * portion of it is used at the same time. Following shows number of accessed
67 * bytes for different cases:
68 * - 1 failed disk: 256B (1 mul. coefficient)
69 * - 2 failed disks: 512B (2 mul. coefficients)
70 * - 3 failed disks: 1536B (6 mul. coefficients)
71 *
72 * Size of actually accessed lookup table regions is only larger for
73 * reconstruction of 3 failed disks, when compared to traditional log/exp
74 * method. But since the result is obtained in one lookup step performance is
75 * doubled.
76 */
77 static uint8_t vdev_raidz_mul_lt[256][256] __attribute__((aligned(256)));
78
79 static void
raidz_init_scalar(void)80 raidz_init_scalar(void)
81 {
82 int c, i;
83 for (c = 0; c < 256; c++)
84 for (i = 0; i < 256; i++)
85 vdev_raidz_mul_lt[c][i] = gf_mul(c, i);
86
87 }
88
89 #define PREFETCHNTA(ptr, offset) {}
90 #define PREFETCH(ptr, offset) {}
91
92 #define XOR_ACC(src, acc) acc.e ^= ((v_t *)src)[0].e
93 #define XOR(src, acc) acc.e ^= src.e
94 #define ZERO(acc) acc.e = 0
95 #define COPY(src, dst) dst = src
96 #define LOAD(src, val) val = ((v_t *)src)[0]
97 #define STORE(dst, val) ((v_t *)dst)[0] = val
98
99 /*
100 * Constants used for optimized multiplication by 2.
101 */
102 static const struct {
103 iv_t mod;
104 iv_t mask;
105 iv_t msb;
106 } scalar_mul2_consts = {
107 #if ELEM_SIZE == 8
108 .mod = 0x1d1d1d1d1d1d1d1dULL,
109 .mask = 0xfefefefefefefefeULL,
110 .msb = 0x8080808080808080ULL,
111 #else
112 .mod = 0x1d1d1d1dULL,
113 .mask = 0xfefefefeULL,
114 .msb = 0x80808080ULL,
115 #endif
116 };
117
118 #define MUL2_SETUP() {}
119
120 #define MUL2(a) \
121 { \
122 iv_t _mask; \
123 \
124 _mask = (a).e & scalar_mul2_consts.msb; \
125 _mask = (_mask << 1) - (_mask >> 7); \
126 (a).e = ((a).e << 1) & scalar_mul2_consts.mask; \
127 (a).e = (a).e ^ (_mask & scalar_mul2_consts.mod); \
128 }
129
130 #define MUL4(a) \
131 { \
132 MUL2(a); \
133 MUL2(a); \
134 }
135
136 #define MUL(c, a) \
137 { \
138 const uint8_t *mul_lt = vdev_raidz_mul_lt[c]; \
139 switch (ELEM_SIZE) { \
140 case 8: \
141 a.b[7] = mul_lt[a.b[7]]; \
142 a.b[6] = mul_lt[a.b[6]]; \
143 a.b[5] = mul_lt[a.b[5]]; \
144 a.b[4] = mul_lt[a.b[4]]; \
145 /* falls through */ \
146 case 4: \
147 a.b[3] = mul_lt[a.b[3]]; \
148 a.b[2] = mul_lt[a.b[2]]; \
149 a.b[1] = mul_lt[a.b[1]]; \
150 a.b[0] = mul_lt[a.b[0]]; \
151 break; \
152 } \
153 }
154
155 #define raidz_math_begin() {}
156 #define raidz_math_end() {}
157
158 #define SYN_STRIDE 1
159
160 #define ZERO_DEFINE() v_t d0
161 #define ZERO_STRIDE 1
162 #define ZERO_D d0
163
164 #define COPY_DEFINE() v_t d0
165 #define COPY_STRIDE 1
166 #define COPY_D d0
167
168 #define ADD_DEFINE() v_t d0
169 #define ADD_STRIDE 1
170 #define ADD_D d0
171
172 #define MUL_DEFINE() v_t d0
173 #define MUL_STRIDE 1
174 #define MUL_D d0
175
176 #define GEN_P_STRIDE 1
177 #define GEN_P_DEFINE() v_t p0
178 #define GEN_P_P p0
179
180 #define GEN_PQ_STRIDE 1
181 #define GEN_PQ_DEFINE() v_t d0, c0
182 #define GEN_PQ_D d0
183 #define GEN_PQ_C c0
184
185 #define GEN_PQR_STRIDE 1
186 #define GEN_PQR_DEFINE() v_t d0, c0
187 #define GEN_PQR_D d0
188 #define GEN_PQR_C c0
189
190 #define SYN_Q_DEFINE() v_t d0, x0
191 #define SYN_Q_D d0
192 #define SYN_Q_X x0
193
194
195 #define SYN_R_DEFINE() v_t d0, x0
196 #define SYN_R_D d0
197 #define SYN_R_X x0
198
199
200 #define SYN_PQ_DEFINE() v_t d0, x0
201 #define SYN_PQ_D d0
202 #define SYN_PQ_X x0
203
204
205 #define REC_PQ_STRIDE 1
206 #define REC_PQ_DEFINE() v_t x0, y0, t0
207 #define REC_PQ_X x0
208 #define REC_PQ_Y y0
209 #define REC_PQ_T t0
210
211
212 #define SYN_PR_DEFINE() v_t d0, x0
213 #define SYN_PR_D d0
214 #define SYN_PR_X x0
215
216 #define REC_PR_STRIDE 1
217 #define REC_PR_DEFINE() v_t x0, y0, t0
218 #define REC_PR_X x0
219 #define REC_PR_Y y0
220 #define REC_PR_T t0
221
222
223 #define SYN_QR_DEFINE() v_t d0, x0
224 #define SYN_QR_D d0
225 #define SYN_QR_X x0
226
227
228 #define REC_QR_STRIDE 1
229 #define REC_QR_DEFINE() v_t x0, y0, t0
230 #define REC_QR_X x0
231 #define REC_QR_Y y0
232 #define REC_QR_T t0
233
234
235 #define SYN_PQR_DEFINE() v_t d0, x0
236 #define SYN_PQR_D d0
237 #define SYN_PQR_X x0
238
239 #define REC_PQR_STRIDE 1
240 #define REC_PQR_DEFINE() v_t x0, y0, z0, xs0, ys0
241 #define REC_PQR_X x0
242 #define REC_PQR_Y y0
243 #define REC_PQR_Z z0
244 #define REC_PQR_XS xs0
245 #define REC_PQR_YS ys0
246
247 #include "vdev_raidz_math_impl.h"
248
249 DEFINE_GEN_METHODS(scalar);
250 DEFINE_REC_METHODS(scalar);
251
252 boolean_t
raidz_will_scalar_work(void)253 raidz_will_scalar_work(void)
254 {
255 return (B_TRUE); /* always */
256 }
257
258 const raidz_impl_ops_t vdev_raidz_scalar_impl = {
259 .init = raidz_init_scalar,
260 .fini = NULL,
261 .gen = RAIDZ_GEN_METHODS(scalar),
262 .rec = RAIDZ_REC_METHODS(scalar),
263 .is_supported = &raidz_will_scalar_work,
264 .name = "scalar"
265 };
266
267 /* Powers of 2 in the RAID-Z Galois field. */
268 const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256))) = {
269 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
270 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
271 0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9,
272 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
273 0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35,
274 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
275 0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0,
276 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
277 0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc,
278 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
279 0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f,
280 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
281 0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88,
282 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
283 0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93,
284 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
285 0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9,
286 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
287 0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa,
288 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
289 0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e,
290 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
291 0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4,
292 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
293 0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e,
294 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
295 0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef,
296 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
297 0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5,
298 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
299 0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83,
300 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01
301 };
302
303 /* Logs of 2 in the RAID-Z Galois field. */
304 const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256))) = {
305 0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6,
306 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
307 0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81,
308 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
309 0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21,
310 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
311 0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9,
312 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
313 0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd,
314 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
315 0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd,
316 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
317 0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e,
318 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
319 0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b,
320 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
321 0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d,
322 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
323 0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c,
324 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
325 0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd,
326 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
327 0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e,
328 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
329 0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76,
330 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
331 0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa,
332 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
333 0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51,
334 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
335 0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8,
336 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf,
337 };
338