parity_math.c File Reference

#include "lib/arith.h"
#include "lib/assert.h"
#include "lib/errno.h"
#include "lib/memory.h"
#include "lib/misc.h"
#include "lib/types.h"
#include "sns/parity_ops.h"
#include "sns/parity_math.h"
#include "lib/trace.h"

Include dependency graph for parity_math.c:

Go to the source code of this file.

Macros
#define	M0_TRACE_SUBSYSTEM   M0_TRACE_SUBSYS_SNS
#define	BUF_ALLOC_ERR_INFO(ret, str, len)
#define	VALUE_ASSERT_INFO(cond, var)
#define	VALUE_MISMATCH_ASSERT_INFO(lhs, rhs)
#define	BLOCK_SIZE_ASSERT_INFO(blksz, index, block)
#define	MAT_INIT_ERR_INFO(ret, str, row, col)
#define	MATVEC_INIT_ERR_INFO(ret, str, size)

Enumerations
enum	{ SNS_PARITY_MATH_DATA_BLOCKS_MAX = 1 << (M0_PARITY_GALOIS_W - 1), BAD_FAIL_INDEX = -1, IR_INVALID_COL = UINT8_MAX, MIN_TABLE_LEN = 32 }

Functions
static void	xor_calculate (struct m0_parity_math *math, const struct m0_buf *data, struct m0_buf *parity)
static int	xor_diff (struct m0_parity_math *math, struct m0_buf *old, struct m0_buf *new, struct m0_buf *parity, uint32_t index)
static int	xor_recover (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, struct m0_buf *fails, enum m0_parity_linsys_algo algo)
static void	fail_idx_xor_recover (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, const uint32_t failure_index)
static int	reed_solomon_init (struct m0_parity_math *math)
static void	reed_solomon_fini (struct m0_parity_math *math)
static void	reed_solomon_encode (struct m0_parity_math *math, const struct m0_buf *data, struct m0_buf *parity)
static int	reed_solomon_diff (struct m0_parity_math *math, struct m0_buf *old, struct m0_buf *new, struct m0_buf *parity, uint32_t index)
static int	reed_solomon_recover (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, struct m0_buf *fails, enum m0_parity_linsys_algo algo)
static void	fail_idx_reed_solomon_recover (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, const uint32_t failure_index)
static void	ir_rs_init (const struct m0_parity_math *math, struct m0_sns_ir *ir)
static void	ir_failure_register (struct m0_sns_ir *ir, uint32_t failed_index)
static int	ir_mat_compute (struct m0_sns_ir *ir)
static int	ir_recover (struct m0_sns_ir *ir, struct m0_sns_ir_block *alive_block)
static uint32_t	last_usable_block_id (const struct m0_sns_ir *ir, uint32_t block_idx)
static bool	parity_math_invariant (const struct m0_parity_math *math)
static uint32_t	fails_count (uint8_t *fail, uint32_t unit_count)
static uint32_t	ir_blocks_count (const struct m0_sns_ir *ir)
static int	ir_si_blocks_init (struct m0_sns_ir *ir)
static void	gfaxpy (struct m0_bufvec *y, struct m0_bufvec *x, m0_parity_elem_t alpha)
static bool	is_usable (const struct m0_sns_ir *ir, const struct m0_bitmap *in_bmap, struct m0_sns_ir_block *failed_block)
static bool	is_valid_block_idx (const struct m0_sns_ir *ir, uint32_t block_idx)
static int	isal_encode_data_update (struct m0_buf *dest_bufs, struct m0_buf *src_buf, uint32_t vec_idx, uint8_t *g_tbls, uint32_t data_nr, uint32_t dest_nr)
static void	fails_sort (struct m0_reed_solomon *rs, uint8_t *fail, uint32_t total_count, uint32_t parity_count)
static void	buf_sort (struct m0_reed_solomon *rs, uint32_t total_count, uint32_t data_count, uint8_t *fail, struct m0_buf *data, struct m0_buf *parity)
static int	isal_gen_recov_coeff_tbl (uint32_t data_count, uint32_t parity_count, struct m0_reed_solomon *rs)
static void	dependency_bitmap_prepare (struct m0_sns_ir_block *f_block, struct m0_sns_ir *ir)
M0_INTERNAL void	m0_parity_math_fini (struct m0_parity_math *math)
M0_INTERNAL int	m0_parity_math_init (struct m0_parity_math *math, uint32_t data_count, uint32_t parity_count)
M0_INTERNAL void	m0_parity_math_calculate (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity)
M0_INTERNAL int	m0_parity_math_diff (struct m0_parity_math *math, struct m0_buf *old, struct m0_buf *new, struct m0_buf *parity, uint32_t index)
M0_INTERNAL int	m0_parity_math_recover (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, struct m0_buf *fails, enum m0_parity_linsys_algo algo)
M0_INTERNAL void	m0_parity_math_fail_index_recover (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, const uint32_t fidx)
M0_INTERNAL void	m0_parity_math_refine (struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, uint32_t data_ind_changed)
M0_INTERNAL void	m0_parity_math_buffer_xor (struct m0_buf *dest, const struct m0_buf *src)
M0_INTERNAL int	m0_sns_ir_init (const struct m0_parity_math *math, uint32_t local_nr, struct m0_sns_ir *ir)
M0_INTERNAL int	m0_sns_ir_failure_register (struct m0_bufvec *recov_addr, uint32_t failed_index, struct m0_sns_ir *ir)
M0_INTERNAL int	m0_sns_ir_mat_compute (struct m0_sns_ir *ir)
M0_INTERNAL void	m0_sns_ir_fini (struct m0_sns_ir *ir)
M0_INTERNAL int	m0_sns_ir_recover (struct m0_sns_ir *ir, struct m0_bufvec *bufvec, const struct m0_bitmap *bitmap, uint32_t failed_index, enum m0_sns_ir_block_type block_type)
static int	gadd (int x, int y)
static int	gmul (int x, int y)

Variables
static void(*	calculate [M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, const struct m0_buf *data, struct m0_buf *parity)
static int(*	diff [M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, struct m0_buf *old, struct m0_buf *new, struct m0_buf *parity, uint32_t index)
static int(*	recover [M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, struct m0_buf *fails, enum m0_parity_linsys_algo algo)
static void(*	fidx_recover [M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, const uint32_t fidx)

Macro Definition Documentation

BLOCK_SIZE_ASSERT_INFO

#define BLOCK_SIZE_ASSERT_INFO	(		blksz,
			index,
			block
	)

Value:

({              \
        VALUE_MISMATCH_ASSERT_INFO(blksz, block[index].b_nob);  \
})

Definition at line 52 of file parity_math.c.

BUF_ALLOC_ERR_INFO

#define BUF_ALLOC_ERR_INFO	(		ret,
			str,
			len
	)

Value:

({                      \
        M0_ERR_INFO(ret, "Failed to allocate memory for "       \
                    str " buffer of length = %u",               \
                    (uint32_t)len);                             \
})

Definition at line 35 of file parity_math.c.

M0_TRACE_SUBSYSTEM

#define M0_TRACE_SUBSYSTEM   M0_TRACE_SUBSYS_SNS

Definition at line 32 of file parity_math.c.

MAT_INIT_ERR_INFO

#define MAT_INIT_ERR_INFO	(		ret,
			str,
			row,
			col
	)

Value:

({              \
        M0_ERR_INFO(ret, "Failed to initialize %ux%u "          \
                    str " matrix.", (uint32_t)row,              \
                    (uint32_t)col);                             \
})

Definition at line 56 of file parity_math.c.

MATVEC_INIT_ERR_INFO

#define MATVEC_INIT_ERR_INFO	(		ret,
			str,
			size
	)

Value:

({                      \
        M0_ERR_INFO(ret, "Failed to initialize " str " matrix " \
                    "vector of size=%u", (uint32_t)size);       \
})

Definition at line 62 of file parity_math.c.

VALUE_ASSERT_INFO

#define VALUE_ASSERT_INFO	(		cond,
			var
	)

Value:

({                              \
        M0_ASSERT_INFO(cond, "Invalid "#var" value. "           \
                       #var" = %u.", (uint32_t)var);            \
})

Definition at line 41 of file parity_math.c.

VALUE_MISMATCH_ASSERT_INFO

#define VALUE_MISMATCH_ASSERT_INFO	(		lhs,
			rhs
	)

Value:

({                      \
        M0_ASSERT_INFO(lhs == rhs, #lhs" Value mismatch. "      \
                       #lhs" = %u, "#rhs"=%u",                  \
                       (uint32_t)lhs, (uint32_t)rhs);           \
})

Definition at line 46 of file parity_math.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
SNS_PARITY_MATH_DATA_BLOCKS_MAX
BAD_FAIL_INDEX
IR_INVALID_COL
MIN_TABLE_LEN

Definition at line 316 of file parity_math.c.

Function Documentation

buf_sort()

static void buf_sort ( struct m0_reed_solomon *  rs, uint32_t  total_count, uint32_t  data_count, uint8_t *  fail, struct m0_buf *  data, struct m0_buf *  parity  )

static

Sorts the data and parity buffers based on input fail buffer. If buffer is marked as failed, its pointer will be added in rs_bufs_out buffer array. If buffer is not marked as failed in fail buffer, its pointer will be added in rs_bufs_in buffer array. Buffer array rs_bufs_in will be used as source buffers for recovery. Buffer array rs_bufs_out will be used as buffers to be recovered.

Parameters

[in,out]	rs	- Pointer to Reed Solomon structure.
[in]	total_count	- Total count of buffers i.e. data_count + parity_count
[in]	data_count	- count of SNS data units used in system.
[in]	fail	- block with flags, treated as uint8_t block with b_nob elements, if element is '1' then data or parity block with given index is treated as broken.
[in]	data	- data block, treated as uint8_t block with b_nob elements.
[in]	parity	- parity block, treated as uint8_t block with b_nob elements.

Definition at line 1314 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

dependency_bitmap_prepare()

static void dependency_bitmap_prepare ( struct m0_sns_ir_block *  f_block, struct m0_sns_ir *  ir  )

static

Recovery of each failed block depends upon subset of alive blocks. This routine prepares a bitmap indicating this dependency. If a bit at location 'x' is set 'true' then it implies that f_block has no dependency on block with index 'x'.

Definition at line 1443 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fail_idx_reed_solomon_recover()

static void fail_idx_reed_solomon_recover ( struct m0_parity_math *  math, struct m0_buf *  data, struct m0_buf *  parity, const uint32_t  failure_index  )

static

Recovers data or parity units partially or fully depending on the parity calculation algorithm, given the failure index.

Todo:

Iterative reed-solomon decode to be implemented.

Definition at line 727 of file parity_math.c.

fail_idx_xor_recover()

static void fail_idx_xor_recover ( struct m0_parity_math *  math, struct m0_buf *  data, struct m0_buf *  parity, const uint32_t  failure_index  )

static

Definition at line 692 of file parity_math.c.

fails_count()

static uint32_t fails_count ( uint8_t *  fail, uint32_t  unit_count  )

static

Definition at line 578 of file parity_math.c.

Here is the caller graph for this function:

fails_sort()

static void fails_sort ( struct m0_reed_solomon *  rs, uint8_t *  fail, uint32_t  total_count, uint32_t  parity_count  )

static

Sorts the indices for failed and non-failed data and parity blocks.

Parameters

[in,out]	rs	- Pointer to Reed Solomon structure.
[in]	fail	- block with flags, if element is '1' then data or parity block with given index is treated as broken.
[in]	total_count	- Total count of buffers i.e. data_count + parity_count
[in]	parity_count	- Count of SNS parity units used in system.

Definition at line 1289 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

gadd()

static int gadd ( int  x, int  y  )

static

Definition at line 568 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

gfaxpy()

static void gfaxpy ( struct m0_bufvec *  y, struct m0_bufvec *  x, m0_parity_elem_t  alpha  )

static

Constant times x plus y, over galois field. Naming convention for this function is borrowed from BLAS routines.

Definition at line 765 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

gmul()

static int gmul ( int  x, int  y  )

static

Definition at line 573 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ir_blocks_count()

static uint32_t ir_blocks_count ( const struct m0_sns_ir *  ir )

inlinestatic

Definition at line 760 of file parity_math.c.

Here is the caller graph for this function:

ir_failure_register()

static void ir_failure_register ( struct m0_sns_ir *  ir, uint32_t  failed_index  )

static

This function registers failed index.

Parameters

[in,out]	ir	- pointer to incremental recovery structure.
[in]	failed_index	- index of the failed block in a parity group.

Definition at line 1098 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ir_mat_compute()

static int ir_mat_compute ( struct m0_sns_ir *  ir )

static

Computes data-recovery matrix. Populates dependency bitmaps for failed blocks.

Parameters

[in,out]

ir

- pointer to incremental recovery structure.

Return values

0	on success.
-ENOMEM	on failure to acquire memory.
-EDOM	when input matrix is singular.

Definition at line 1111 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ir_recover()

static int ir_recover ( struct m0_sns_ir *  ir, struct m0_sns_ir_block *  alive_block  )

static

Core routine to recover failed block using current alive block.

Parameters

[in]	ir	- Pointer to incremental recovery structure.
[in]	alive_block	- Pointer to the alive block.

Return values

0	- success otherwise failure

Definition at line 1143 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ir_rs_init()

static void ir_rs_init ( const struct m0_parity_math *  math, struct m0_sns_ir *  ir  )

static

Initialize fields, specific to Reed Solomon implementation, which are required for incremental recovery.

Parameters

[in]	math	- Pointer to parity math structure.
[out]	ir	- Pointer to incremental recovery structure.

Definition at line 1083 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

ir_si_blocks_init()

static int ir_si_blocks_init ( struct m0_sns_ir *  ir )

static

Initialize si_block structures.

Parameters

ir	- pointer to incremental recovery structure.

Definition at line 734 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

is_usable()

static bool is_usable ( const struct m0_sns_ir *  ir, const struct m0_bitmap *  in_bmap, struct m0_sns_ir_block *  failed_block  )

static

Definition at line 812 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

is_valid_block_idx()

static bool is_valid_block_idx ( const struct m0_sns_ir *  ir, uint32_t  block_idx  )

inlinestatic

Definition at line 833 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

isal_encode_data_update()

static int isal_encode_data_update ( struct m0_buf *  dest_bufs, struct m0_buf *  src_buf, uint32_t  vec_idx, uint8_t *  g_tbls, uint32_t  data_nr, uint32_t  dest_nr  )

static

This is wrapper function for Intel ISA API ec_encode_data_update().

Parameters

[out]	dest_bufs	- Array of coded output buffers i.e. struct m0_buf
[in]	src_buf	- Pointer to single input source (struct m0_buf) used to update output parity.
[in]	vec_idx	- The vector index corresponding to the single input source.
[in]	g_tbls	- Pointer to array of input tables generated from coding coefficients in ec_init_tables(). Must be of size 32*data_nr*dest_nr
[in]	data_nr	- The number of data blocks for coding.
[in]	dest_nr	- The number of output blocks to concurrently encode/decode.

Return values

0	on success.
-ENOMEM	on failure to acquire memory.

Definition at line 1254 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

isal_gen_recov_coeff_tbl()

static int isal_gen_recov_coeff_tbl ( uint32_t  data_count, uint32_t  parity_count, struct m0_reed_solomon *  rs  )

static

Inverts the encoding matrix and generates tables of recovery coefficient codes for lost data.

Parameters

[in]	data_count	- count of SNS data units used in system.
[in]	parity_count	- count of SNS parity units used in system.
[in,out]	rs	- Pointer to reed solomon structure.

Return values

0	- success otherwise failure

Definition at line 1348 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

last_usable_block_id()

static uint32_t last_usable_block_id ( const struct m0_sns_ir *  ir, uint32_t  block_idx  )

static

Returns last usable block index.

Definition at line 1455 of file parity_math.c.

Here is the caller graph for this function:

parity_math_invariant()

static bool parity_math_invariant ( const struct m0_parity_math *  math )

static

Definition at line 589 of file parity_math.c.

Here is the caller graph for this function:

reed_solomon_diff()

static int reed_solomon_diff ( struct m0_parity_math *  math, struct m0_buf *  old, struct m0_buf *  new, struct m0_buf *  parity, uint32_t  index  )

static

This function calculates differential parity using Reed Solomon algorithm.

Definition at line 957 of file parity_math.c.

Here is the call graph for this function:

reed_solomon_encode()

static void reed_solomon_encode ( struct m0_parity_math *  math, const struct m0_buf *  data, struct m0_buf *  parity  )

static

This function calculates parity fields using Reed Solomon algorithm.

Definition at line 921 of file parity_math.c.

Here is the call graph for this function:

reed_solomon_fini()

static void reed_solomon_fini ( struct m0_parity_math *  math )

static

This function clears fields used by Reed Solomon algorithm.

Definition at line 840 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

reed_solomon_init()

static int reed_solomon_init ( struct m0_parity_math *  math )

static

This function initializes fields required to use Reed Solomon algorithm.

Definition at line 853 of file parity_math.c.

Here is the call graph for this function:

Here is the caller graph for this function:

reed_solomon_recover()

static int reed_solomon_recover ( struct m0_parity_math *  math, struct m0_buf *  data, struct m0_buf *  parity, struct m0_buf *  fails, enum m0_parity_linsys_algo  algo  )

static

This function recovers failed data and/or parity using Reed Solomon algorithm.

Definition at line 1019 of file parity_math.c.

Here is the call graph for this function:

xor_calculate()

static void xor_calculate ( struct m0_parity_math *  math, const struct m0_buf *  data, struct m0_buf *  parity  )

static

Definition at line 597 of file parity_math.c.

Here is the call graph for this function:

xor_diff()

static int xor_diff ( struct m0_parity_math *  math, struct m0_buf *  old, struct m0_buf *  new, struct m0_buf *  parity, uint32_t  index  )

static

Definition at line 621 of file parity_math.c.

Here is the call graph for this function:

xor_recover()

static int xor_recover ( struct m0_parity_math *  math, struct m0_buf *  data, struct m0_buf *  parity, struct m0_buf *  fails, enum m0_parity_linsys_algo  algo  )

static

Definition at line 646 of file parity_math.c.

Here is the call graph for this function:

Variable Documentation

calculate

void(* calculate[M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, const struct m0_buf *data, struct m0_buf *parity)

static

Initial value:

= {
        [M0_PARITY_CAL_ALGO_XOR] = xor_calculate,
        [M0_PARITY_CAL_ALGO_REED_SOLOMON] = reed_solomon_encode,
}

Definition at line 283 of file parity_math.c.

diff

int(* diff[M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, struct m0_buf *old, struct m0_buf *new, struct m0_buf *parity, uint32_t index)

static

Initial value:

= {
        [M0_PARITY_CAL_ALGO_XOR]          = xor_diff,
        [M0_PARITY_CAL_ALGO_REED_SOLOMON] = reed_solomon_diff,
}

Definition at line 290 of file parity_math.c.

fidx_recover

void(* fidx_recover[M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, const uint32_t fidx)

static

Initial value:

= {
        [M0_PARITY_CAL_ALGO_XOR] = fail_idx_xor_recover,
        [M0_PARITY_CAL_ALGO_REED_SOLOMON] = fail_idx_reed_solomon_recover,
}

Definition at line 308 of file parity_math.c.

recover

int(* recover[M0_PARITY_CAL_ALGO_NR])(struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity, struct m0_buf *fails, enum m0_parity_linsys_algo algo)

static

Initial value:

= {
        [M0_PARITY_CAL_ALGO_XOR] = xor_recover,
        [M0_PARITY_CAL_ALGO_REED_SOLOMON] = reed_solomon_recover,
}

Definition at line 299 of file parity_math.c.