[mirror_zfs.git] / include / sys / vdev_raidz_impl.h

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright (C) 2016 Gvozden Nešković. All rights reserved.
 */

#ifndef _VDEV_RAIDZ_H
#define	_VDEV_RAIDZ_H

#include <sys/types.h>
#include <sys/debug.h>
#include <sys/kstat.h>
#include <sys/abd.h>

#ifdef  __cplusplus
extern "C" {
#endif

#define	CODE_P		(0U)
#define	CODE_Q		(1U)
#define	CODE_R		(2U)

#define	PARITY_P	(1U)
#define	PARITY_PQ	(2U)
#define	PARITY_PQR	(3U)

#define	TARGET_X	(0U)
#define	TARGET_Y	(1U)
#define	TARGET_Z	(2U)

/*
 * Parity generation methods indexes
 */
enum raidz_math_gen_op {
	RAIDZ_GEN_P = 0,
	RAIDZ_GEN_PQ,
	RAIDZ_GEN_PQR,
	RAIDZ_GEN_NUM = 3
};
/*
 * Data reconstruction methods indexes
 */
enum raidz_rec_op {
	RAIDZ_REC_P = 0,
	RAIDZ_REC_Q,
	RAIDZ_REC_R,
	RAIDZ_REC_PQ,
	RAIDZ_REC_PR,
	RAIDZ_REC_QR,
	RAIDZ_REC_PQR,
	RAIDZ_REC_NUM = 7
};

extern const char *raidz_gen_name[RAIDZ_GEN_NUM];
extern const char *raidz_rec_name[RAIDZ_REC_NUM];

/*
 * Methods used to define raidz implementation
 *
 * @raidz_gen_f	Parity generation function
 *     @par1	pointer to raidz_map
 * @raidz_rec_f	Data reconstruction function
 *     @par1	pointer to raidz_map
 *     @par2	array of reconstruction targets
 * @will_work_f Function returns TRUE if impl. is supported on the system
 * @init_impl_f Function is called once on init
 * @fini_impl_f Function is called once on fini
 */
typedef void		(*raidz_gen_f)(void *);
typedef int		(*raidz_rec_f)(void *, const int *);
typedef boolean_t	(*will_work_f)(void);
typedef void		(*init_impl_f)(void);
typedef void		(*fini_impl_f)(void);

#define	RAIDZ_IMPL_NAME_MAX	(16)

typedef struct raidz_impl_ops {
	init_impl_f init;
	fini_impl_f fini;
	raidz_gen_f gen[RAIDZ_GEN_NUM];	/* Parity generate functions */
	raidz_rec_f rec[RAIDZ_REC_NUM];	/* Data reconstruction functions */
	will_work_f is_supported;	/* Support check function */
	char name[RAIDZ_IMPL_NAME_MAX];	/* Name of the implementation */
} raidz_impl_ops_t;

typedef struct raidz_col {
	size_t rc_devidx;		/* child device index for I/O */
	size_t rc_offset;		/* device offset */
	size_t rc_size;			/* I/O size */
	abd_t *rc_abd;			/* I/O data */
	void *rc_gdata;			/* used to store the "good" version */
	int rc_error;			/* I/O error for this device */
	unsigned int rc_tried;		/* Did we attempt this I/O column? */
	unsigned int rc_skipped;	/* Did we skip this I/O column? */
} raidz_col_t;

typedef struct raidz_map {
	size_t rm_cols;			/* Regular column count */
	size_t rm_scols;		/* Count including skipped columns */
	size_t rm_bigcols;		/* Number of oversized columns */
	size_t rm_asize;		/* Actual total I/O size */
	size_t rm_missingdata;		/* Count of missing data devices */
	size_t rm_missingparity;	/* Count of missing parity devices */
	size_t rm_firstdatacol;		/* First data column/parity count */
	size_t rm_nskip;		/* Skipped sectors for padding */
	size_t rm_skipstart;		/* Column index of padding start */
	abd_t *rm_abd_copy;		/* rm_asize-buffer of copied data */
	size_t rm_reports;		/* # of referencing checksum reports */
	unsigned int rm_freed;		/* map no longer has referencing ZIO */
	unsigned int rm_ecksuminjected;	/* checksum error was injected */
	raidz_impl_ops_t *rm_ops;	/* RAIDZ math operations */
	raidz_col_t rm_col[1];		/* Flexible array of I/O columns */
} raidz_map_t;

#define	RAIDZ_ORIGINAL_IMPL	(INT_MAX)

extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
#if defined(__x86_64) && defined(HAVE_SSE2)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
#endif
#if defined(__x86_64) && defined(HAVE_SSSE3)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
#endif
#if defined(__x86_64) && defined(HAVE_AVX2)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
#endif
#if defined(__x86_64) && defined(HAVE_AVX512F)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_avx512f_impl;
#endif
#if defined(__x86_64) && defined(HAVE_AVX512BW)	/* only x86_64 for now */
extern const raidz_impl_ops_t vdev_raidz_avx512bw_impl;
#endif
#if defined(__aarch64__)
extern const raidz_impl_ops_t vdev_raidz_aarch64_neon_impl;
extern const raidz_impl_ops_t vdev_raidz_aarch64_neonx2_impl;
#endif

/*
 * Commonly used raidz_map helpers
 *
 * raidz_parity		Returns parity of the RAIDZ block
 * raidz_ncols		Returns number of columns the block spans
 * raidz_nbigcols	Returns number of big columns columns
 * raidz_col_p		Returns pointer to a column
 * raidz_col_size	Returns size of a column
 * raidz_big_size	Returns size of big columns
 * raidz_short_size	Returns size of short columns
 */
#define	raidz_parity(rm)	((rm)->rm_firstdatacol)
#define	raidz_ncols(rm)		((rm)->rm_cols)
#define	raidz_nbigcols(rm)	((rm)->rm_bigcols)
#define	raidz_col_p(rm, c)	((rm)->rm_col + (c))
#define	raidz_col_size(rm, c)	((rm)->rm_col[c].rc_size)
#define	raidz_big_size(rm)	(raidz_col_size(rm, CODE_P))
#define	raidz_short_size(rm)	(raidz_col_size(rm, raidz_ncols(rm)-1))

/*
 * Macro defines an RAIDZ parity generation method
 *
 * @code	parity the function produce
 * @impl	name of the implementation
 */
#define	_RAIDZ_GEN_WRAP(code, impl)					\
static void								\
impl ## _gen_ ## code(void *rmp)					\
{									\
	raidz_map_t *rm = (raidz_map_t *)rmp;				\
	raidz_generate_## code ## _impl(rm);				\
}

/*
 * Macro defines an RAIDZ data reconstruction method
 *
 * @code	parity the function produce
 * @impl	name of the implementation
 */
#define	_RAIDZ_REC_WRAP(code, impl)					\
static int								\
impl ## _rec_ ## code(void *rmp, const int *tgtidx)			\
{									\
	raidz_map_t *rm = (raidz_map_t *)rmp;				\
	return (raidz_reconstruct_## code ## _impl(rm, tgtidx));	\
}

/*
 * Define all gen methods for an implementation
 *
 * @impl	name of the implementation
 */
#define	DEFINE_GEN_METHODS(impl)					\
	_RAIDZ_GEN_WRAP(p, impl);					\
	_RAIDZ_GEN_WRAP(pq, impl);					\
	_RAIDZ_GEN_WRAP(pqr, impl)

/*
 * Define all rec functions for an implementation
 *
 * @impl	name of the implementation
 */
#define	DEFINE_REC_METHODS(impl)					\
	_RAIDZ_REC_WRAP(p, impl);					\
	_RAIDZ_REC_WRAP(q, impl);					\
	_RAIDZ_REC_WRAP(r, impl);					\
	_RAIDZ_REC_WRAP(pq, impl);					\
	_RAIDZ_REC_WRAP(pr, impl);					\
	_RAIDZ_REC_WRAP(qr, impl);					\
	_RAIDZ_REC_WRAP(pqr, impl)

#define	RAIDZ_GEN_METHODS(impl)						\
{									\
	[RAIDZ_GEN_P] = & impl ## _gen_p,				\
	[RAIDZ_GEN_PQ] = & impl ## _gen_pq,				\
	[RAIDZ_GEN_PQR] = & impl ## _gen_pqr				\
}

#define	RAIDZ_REC_METHODS(impl)						\
{									\
	[RAIDZ_REC_P] = & impl ## _rec_p,				\
	[RAIDZ_REC_Q] = & impl ## _rec_q,				\
	[RAIDZ_REC_R] = & impl ## _rec_r,				\
	[RAIDZ_REC_PQ] = & impl ## _rec_pq,				\
	[RAIDZ_REC_PR] = & impl ## _rec_pr,				\
	[RAIDZ_REC_QR] = & impl ## _rec_qr,				\
	[RAIDZ_REC_PQR] = & impl ## _rec_pqr				\
}


typedef struct raidz_impl_kstat {
	uint64_t gen[RAIDZ_GEN_NUM];	/* gen method speed B/s */
	uint64_t rec[RAIDZ_REC_NUM];	/* rec method speed B/s */
} raidz_impl_kstat_t;

/*
 * Enumerate various multiplication constants
 * used in reconstruction methods
 */
typedef enum raidz_mul_info {
	/* Reconstruct Q */
	MUL_Q_X		= 0,
	/* Reconstruct R */
	MUL_R_X		= 0,
	/* Reconstruct PQ */
	MUL_PQ_X	= 0,
	MUL_PQ_Y	= 1,
	/* Reconstruct PR */
	MUL_PR_X	= 0,
	MUL_PR_Y	= 1,
	/* Reconstruct QR */
	MUL_QR_XQ	= 0,
	MUL_QR_X	= 1,
	MUL_QR_YQ	= 2,
	MUL_QR_Y	= 3,
	/* Reconstruct PQR */
	MUL_PQR_XP	= 0,
	MUL_PQR_XQ	= 1,
	MUL_PQR_XR	= 2,
	MUL_PQR_YU	= 3,
	MUL_PQR_YP	= 4,
	MUL_PQR_YQ	= 5,

	MUL_CNT		= 6
} raidz_mul_info_t;

/*
 * Powers of 2 in the Galois field.
 */
extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
/* Logs of 2 in the Galois field defined above. */
extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));

/*
 * Multiply a given number by 2 raised to the given power.
 */
static inline uint8_t
vdev_raidz_exp2(const uint8_t a, const unsigned exp)
{
	if (a == 0)
		return (0);

	return (vdev_raidz_pow2[(exp + (unsigned)vdev_raidz_log2[a]) % 255]);
}

/*
 * Galois Field operations.
 *
 * gf_exp2	- computes 2 raised to the given power
 * gf_exp2	- computes 4 raised to the given power
 * gf_mul	- multiplication
 * gf_div	- division
 * gf_inv	- multiplicative inverse
 */
typedef unsigned gf_t;
typedef unsigned gf_log_t;

static inline gf_t
gf_mul(const gf_t a, const gf_t b)
{
	gf_log_t logsum;

	if (a == 0 || b == 0)
		return (0);

	logsum = (gf_log_t)vdev_raidz_log2[a] + (gf_log_t)vdev_raidz_log2[b];

	return ((gf_t)vdev_raidz_pow2[logsum % 255]);
}

static inline gf_t
gf_div(const gf_t  a, const gf_t b)
{
	gf_log_t logsum;

	ASSERT3U(b, >, 0);
	if (a == 0)
		return (0);

	logsum = (gf_log_t)255 + (gf_log_t)vdev_raidz_log2[a] -
	    (gf_log_t)vdev_raidz_log2[b];

	return ((gf_t)vdev_raidz_pow2[logsum % 255]);
}

static inline gf_t
gf_inv(const gf_t a)
{
	gf_log_t logsum;

	ASSERT3U(a, >, 0);

	logsum = (gf_log_t)255 - (gf_log_t)vdev_raidz_log2[a];

	return ((gf_t)vdev_raidz_pow2[logsum]);
}

static inline gf_t
gf_exp2(gf_log_t exp)
{
	return (vdev_raidz_pow2[exp % 255]);
}

static inline gf_t
gf_exp4(gf_log_t exp)
{
	ASSERT3U(exp, <=, 255);
	return ((gf_t)vdev_raidz_pow2[(2 * exp) % 255]);
}

#ifdef  __cplusplus
}
#endif

#endif /* _VDEV_RAIDZ_H */
Commit	Line	Data
ab9f4b0b GN	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>
a6255b7f	31	#include <sys/abd.h>
ab9f4b0b GN	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
c9187d86 GN	93	#define RAIDZ_IMPL_NAME_MAX (16)
c9187d86 GN	94
ab9f4b0b GN	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 */
c9187d86	101	char name[RAIDZ_IMPL_NAME_MAX]; /* Name of the implementation */
ab9f4b0b GN	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 */
a6255b7f	108	abd_t rc_abd; / I/O data */
ab9f4b0b GN	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 */
a6255b7f	125	abd_t rm_abd_copy; / rm_asize-buffer of copied data */
ab9f4b0b GN	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	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
c9187d86 GN	133	#define RAIDZ_ORIGINAL_IMPL (INT_MAX)
c9187d86 GN	134
ae25d222 GN	135	extern const raidz_impl_ops_t vdev_raidz_scalar_impl;
	136	#if defined(__x86_64) && defined(HAVE_SSE2) /* only x86_64 for now */
	137	extern const raidz_impl_ops_t vdev_raidz_sse2_impl;
	138	#endif
	139	#if defined(__x86_64) && defined(HAVE_SSSE3) /* only x86_64 for now */
	140	extern const raidz_impl_ops_t vdev_raidz_ssse3_impl;
	141	#endif
	142	#if defined(__x86_64) && defined(HAVE_AVX2) /* only x86_64 for now */
	143	extern const raidz_impl_ops_t vdev_raidz_avx2_impl;
	144	#endif
7f547f85 RD	145	#if defined(__x86_64) && defined(HAVE_AVX512F) /* only x86_64 for now */
	146	extern const raidz_impl_ops_t vdev_raidz_avx512f_impl;
	147	#endif
	148	#if defined(__x86_64) && defined(HAVE_AVX512BW) /* only x86_64 for now */
	149	extern const raidz_impl_ops_t vdev_raidz_avx512bw_impl;
	150	#endif
62a65a65 RD	151	#if defined(__aarch64__)
	152	extern const raidz_impl_ops_t vdev_raidz_aarch64_neon_impl;
	153	extern const raidz_impl_ops_t vdev_raidz_aarch64_neonx2_impl;
	154	#endif
ae25d222	155
ab9f4b0b GN	156	/*
	157	* Commonly used raidz_map helpers
	158	*
	159	* raidz_parity Returns parity of the RAIDZ block
	160	* raidz_ncols Returns number of columns the block spans
	161	* raidz_nbigcols Returns number of big columns columns
	162	* raidz_col_p Returns pointer to a column
	163	* raidz_col_size Returns size of a column
	164	* raidz_big_size Returns size of big columns
	165	* raidz_short_size Returns size of short columns
	166	*/
	167	#define raidz_parity(rm) ((rm)->rm_firstdatacol)
	168	#define raidz_ncols(rm) ((rm)->rm_cols)
	169	#define raidz_nbigcols(rm) ((rm)->rm_bigcols)
	170	#define raidz_col_p(rm, c) ((rm)->rm_col + (c))
	171	#define raidz_col_size(rm, c) ((rm)->rm_col[c].rc_size)
	172	#define raidz_big_size(rm) (raidz_col_size(rm, CODE_P))
	173	#define raidz_short_size(rm) (raidz_col_size(rm, raidz_ncols(rm)-1))
	174
	175	/*
	176	* Macro defines an RAIDZ parity generation method
	177	*
	178	* @code parity the function produce
	179	* @impl name of the implementation
	180	*/
02730c33	181	#define _RAIDZ_GEN_WRAP(code, impl) \
ab9f4b0b GN	182	static void \
	183	impl ## _gen_ ## code(void *rmp) \
	184	{ \
02730c33 BB	185	raidz_map_t rm = (raidz_map_t )rmp; \
02730c33 BB	186	raidz_generate_## code ## _impl(rm); \
ab9f4b0b GN	187	}
	188
	189	/*
	190	* Macro defines an RAIDZ data reconstruction method
	191	*
	192	* @code parity the function produce
	193	* @impl name of the implementation
	194	*/
02730c33 BB	195	#define _RAIDZ_REC_WRAP(code, impl) \
02730c33 BB	196	static int \
ab9f4b0b GN	197	impl ## _rec_ ## code(void rmp, const int tgtidx) \
ab9f4b0b GN	198	{ \
02730c33	199	raidz_map_t rm = (raidz_map_t )rmp; \
ab9f4b0b GN	200	return (raidz_reconstruct_## code ## _impl(rm, tgtidx)); \
	201	}
	202
	203	/*
	204	* Define all gen methods for an implementation
	205	*
	206	* @impl name of the implementation
	207	*/
	208	#define DEFINE_GEN_METHODS(impl) \
	209	_RAIDZ_GEN_WRAP(p, impl); \
	210	_RAIDZ_GEN_WRAP(pq, impl); \
	211	_RAIDZ_GEN_WRAP(pqr, impl)
	212
	213	/*
	214	* Define all rec functions for an implementation
	215	*
	216	* @impl name of the implementation
	217	*/
	218	#define DEFINE_REC_METHODS(impl) \
	219	_RAIDZ_REC_WRAP(p, impl); \
	220	_RAIDZ_REC_WRAP(q, impl); \
	221	_RAIDZ_REC_WRAP(r, impl); \
	222	_RAIDZ_REC_WRAP(pq, impl); \
	223	_RAIDZ_REC_WRAP(pr, impl); \
	224	_RAIDZ_REC_WRAP(qr, impl); \
	225	_RAIDZ_REC_WRAP(pqr, impl)
	226
	227	#define RAIDZ_GEN_METHODS(impl) \
	228	{ \
	229	[RAIDZ_GEN_P] = & impl ## _gen_p, \
	230	[RAIDZ_GEN_PQ] = & impl ## _gen_pq, \
	231	[RAIDZ_GEN_PQR] = & impl ## _gen_pqr \
	232	}
	233
	234	#define RAIDZ_REC_METHODS(impl) \
	235	{ \
	236	[RAIDZ_REC_P] = & impl ## _rec_p, \
	237	[RAIDZ_REC_Q] = & impl ## _rec_q, \
	238	[RAIDZ_REC_R] = & impl ## _rec_r, \
	239	[RAIDZ_REC_PQ] = & impl ## _rec_pq, \
	240	[RAIDZ_REC_PR] = & impl ## _rec_pr, \
	241	[RAIDZ_REC_QR] = & impl ## _rec_qr, \
	242	[RAIDZ_REC_PQR] = & impl ## _rec_pqr \
	243	}
	244
	245
	246	typedef struct raidz_impl_kstat {
26a08b5c GN	247	uint64_t gen[RAIDZ_GEN_NUM]; /* gen method speed B/s */
26a08b5c GN	248	uint64_t rec[RAIDZ_REC_NUM]; /* rec method speed B/s */
ab9f4b0b GN	249	} raidz_impl_kstat_t;
	250
	251	/*
	252	* Enumerate various multiplication constants
	253	* used in reconstruction methods
	254	*/
	255	typedef enum raidz_mul_info {
	256	/* Reconstruct Q */
	257	MUL_Q_X = 0,
	258	/* Reconstruct R */
	259	MUL_R_X = 0,
	260	/* Reconstruct PQ */
	261	MUL_PQ_X = 0,
	262	MUL_PQ_Y = 1,
	263	/* Reconstruct PR */
	264	MUL_PR_X = 0,
	265	MUL_PR_Y = 1,
	266	/* Reconstruct QR */
	267	MUL_QR_XQ = 0,
	268	MUL_QR_X = 1,
	269	MUL_QR_YQ = 2,
	270	MUL_QR_Y = 3,
	271	/* Reconstruct PQR */
	272	MUL_PQR_XP = 0,
	273	MUL_PQR_XQ = 1,
	274	MUL_PQR_XR = 2,
	275	MUL_PQR_YU = 3,
	276	MUL_PQR_YP = 4,
	277	MUL_PQR_YQ = 5,
	278
	279	MUL_CNT = 6
	280	} raidz_mul_info_t;
	281
	282	/*
	283	* Powers of 2 in the Galois field.
	284	*/
	285	extern const uint8_t vdev_raidz_pow2[256] __attribute__((aligned(256)));
	286	/* Logs of 2 in the Galois field defined above. */
	287	extern const uint8_t vdev_raidz_log2[256] __attribute__((aligned(256)));
	288
	289	/*
	290	* Multiply a given number by 2 raised to the given power.
	291	*/
	292	static inline uint8_t
	293	vdev_raidz_exp2(const uint8_t a, const unsigned exp)
	294	{
	295	if (a == 0)
	296	return (0);
	297
02730c33	298	return (vdev_raidz_pow2[(exp + (unsigned)vdev_raidz_log2[a]) % 255]);
ab9f4b0b GN	299	}
	300
	301	/*
	302	* Galois Field operations.
	303	*
	304	* gf_exp2 - computes 2 raised to the given power
	305	* gf_exp2 - computes 4 raised to the given power
	306	* gf_mul - multiplication
	307	* gf_div - division
	308	* gf_inv - multiplicative inverse
	309	*/
	310	typedef unsigned gf_t;
	311	typedef unsigned gf_log_t;
	312
	313	static inline gf_t
	314	gf_mul(const gf_t a, const gf_t b)
	315	{
	316	gf_log_t logsum;
	317
	318	if (a == 0 \|\| b == 0)
	319	return (0);
	320
02730c33	321	logsum = (gf_log_t)vdev_raidz_log2[a] + (gf_log_t)vdev_raidz_log2[b];
ab9f4b0b	322
02730c33	323	return ((gf_t)vdev_raidz_pow2[logsum % 255]);
ab9f4b0b GN	324	}
	325
	326	static inline gf_t
	327	gf_div(const gf_t a, const gf_t b)
	328	{
	329	gf_log_t logsum;
	330
	331	ASSERT3U(b, >, 0);
	332	if (a == 0)
	333	return (0);
	334
02730c33 BB	335	logsum = (gf_log_t)255 + (gf_log_t)vdev_raidz_log2[a] -
02730c33 BB	336	(gf_log_t)vdev_raidz_log2[b];
ab9f4b0b	337
02730c33	338	return ((gf_t)vdev_raidz_pow2[logsum % 255]);
ab9f4b0b GN	339	}
	340
	341	static inline gf_t
	342	gf_inv(const gf_t a)
	343	{
	344	gf_log_t logsum;
	345
	346	ASSERT3U(a, >, 0);
	347
02730c33	348	logsum = (gf_log_t)255 - (gf_log_t)vdev_raidz_log2[a];
ab9f4b0b	349
02730c33	350	return ((gf_t)vdev_raidz_pow2[logsum]);
ab9f4b0b GN	351	}
	352
	353	static inline gf_t
	354	gf_exp2(gf_log_t exp)
	355	{
	356	return (vdev_raidz_pow2[exp % 255]);
	357	}
	358
	359	static inline gf_t
	360	gf_exp4(gf_log_t exp)
	361	{
	362	ASSERT3U(exp, <=, 255);
02730c33	363	return ((gf_t)vdev_raidz_pow2[(2 * exp) % 255]);
ab9f4b0b GN	364	}
	365
	366	#ifdef __cplusplus
	367	}
	368	#endif
	369
	370	#endif /* _VDEV_RAIDZ_H */