32 #define KB(x) ((x) * 1024) 33 #define MB(x) (KB(x) * 1024) 126 const uint32_t *failed_arr, uint32_t total_failures);
137 uint32_t node_nr, uint32_t alive_nr);
139 uint32_t *failed_arr, uint32_t total_failures);
142 uint32_t start_idx, uint32_t
count);
152 uint32_t *failed_arr);
158 uint32_t total_failures);
162 uint32_t num_seg, uint32_t
size);
175 const uint32_t fail_count,
176 const uint32_t data_count)
180 for (
i = 0;
i < fail_count; ++
i)
183 memset(
data[
i], 0xFF, buff_size);
185 memset(
parity[
i - data_count], 0xFF, buff_size);
189 static bool expected_eq(
const uint32_t data_count,
const uint32_t buff_size)
196 uint32_t *parity_count,
230 for (
i = 0;
i <
duc; ++
i) {
242 for (
i = 0;
i <
fuc; ++
i) {
267 uint32_t *parity_count,
273 uint32_t failed_count = 0;
290 for (
i = 0;
i <
duc; ++
i) {
299 for (
i = 0;
i < failed_count;
i++) {
318 uint32_t parity_count;
330 while (
config_generate(&data_count, &parity_count, &buff_size, algo)) {
331 fail_count = data_count + parity_count;
336 for (
i = 0;
i < data_count; ++
i) {
345 unit_spoil(buff_size, fail_count, data_count);
360 "Recovered data is unexpected");
375 uint32_t parity_count;
389 fail_count = data_count + parity_count;
394 for (
i = 0;
i < data_count; ++
i) {
403 unit_spoil(buff_size, fail_count, data_count);
412 "Recovered data is unexpected");
434 uint32_t parity_count;
461 "Recovered data is unexpected");
502 for(
i = 0;
i < parity_cnt; ++
i) {
517 data_buf_new, p_old,
i);
522 for(
i = 0;
i < parity_cnt; ++
i) {
528 for(
i = 0;
i < parity_cnt; ++
i) {
565 for (
i = 0;
i < 10; ++
i) {
569 for (k = 1; k <
N; ++k) {
631 for (
i = 0;
i <
N; ++
i) {
636 for (
i = 0;
i <
N - K; ++
i) {
650 for (
i = 0;
i <
N - K; ++
i) {
656 for (j = 0; j <
N - K; ++j) {
700 for (
i = 0;
i <
N; ++
i) {
791 uint32_t total_failures = 0;
792 uint32_t *failed_arr;
799 while (total_failures == 0)
812 for (
i = 0;
i < total_failures; ++
i) {
836 uint32_t *failed_arr;
850 for (
i = 0;
i < total_failures; ++
i) {
867 interval = range/
size;
870 if (r_arr[
size - 1] > range - 1)
877 const uint32_t *failed_arr, uint32_t total_failures)
884 if (failed_arr[j] !=
i)
886 else if (j < total_failures - 1)
892 else if (j < total_failures - 1)
913 for (
i = 0;
i <
r->mv_size;
i++)
914 dest[
i] = (uint8_t *)&
r->mv_vector[
i];
916 ec_encode_data(1, b->
mv_size,
r->mv_size,
931 if (i < ir->si_data_nr)
969 uint32_t *failed_arr;
970 uint32_t total_failures = 0;
981 for (node_nr = 4; node_nr <
NODES; ++node_nr) {
984 while (total_failures == 0)
1005 uint32_t node_nr, uint32_t alive_nr)
1011 uint32_t total_failures;
1017 alive_bpn = alive_nr/node_nr;
1018 for (
i = 0, start_idx = 0;
i < node_nr; ++
i) {
1020 node[
i].sin_alive_nr = alive_bpn;
1022 node[
i].sin_alive_nr = alive_bpn + alive_nr % node_nr;
1037 for (j = 0; j < total_failures; ++j) {
1044 failed_arr, total_failures);
1049 start_idx +=
node[
i].sin_alive_nr;
1054 uint32_t *failed_arr, uint32_t total_failures)
1059 for (j = 0; j < total_failures; ++j) {
1070 uint32_t start_idx, uint32_t
count)
1076 while (
i < start_idx) {
1097 uint32_t total_failures;
1103 node[0].sin_ir.si_data_nr +
1104 node[0].sin_ir.si_parity_nr);
1107 node[0].sin_ir.si_alive_nr;
1108 for (
i = 1;
i < node_nr; ++
i) {
1109 ir =
node[
i].sin_ir;
1110 for (j = 0; j <
node[
i].sin_alive_nr; ++j) {
1113 alive_idx =
node[
i].sin_alive[j];
1130 for (k = 0; k < total_failures; ++k) {
1132 node[
i].sin_alive[j],
true);
1143 uint32_t *failed_arr)
1148 uint32_t total_failures;
1155 ir =
node[0].sin_ir;
1157 node[0].sin_ir.si_data_nr +
1158 node[0].sin_ir.si_parity_nr);
1162 for (
i = 1;
i < node_nr - 2; ++
i) {
1163 for (k = 0; k < total_failures; ++k) {
1165 &
node[
i].sin_recov_arr[k],
1166 &
node[
i].sin_bitmap[k],
1173 for (j = 0; j <
node[0].sin_alive_nr; ++j) {
1176 alive_idx =
node[0].sin_alive[j];
1193 for (k = 0; k < total_failures; ++k) {
1195 node[0].sin_alive[j],
true);
1201 for (
i = node_nr - 2;
i < node_nr; ++
i) {
1202 for (k = 0; k < total_failures; ++k) {
1204 &
node[
i].sin_recov_arr[k],
1205 &
node[
i].sin_bitmap[k],
1219 ir =
node[0].sin_ir;
1220 for (
i = 0;
i < ir.si_data_nr; ++
i) {
1221 if (
node[0].sin_ir.si_blocks[
i].sib_status ==
1227 for (;
i < ir.si_data_nr + ir.si_parity_nr; ++
i) {
1228 if (
node[0].sin_ir.si_blocks[
i].sib_status ==
1238 uint32_t total_failures)
1243 for (
i = 0;
i < node_nr; ++
i) {
1246 for (j = 0; j < total_failures; ++j)
1256 uint32_t parity_cnt = 2;
1257 uint32_t total_failures;
1258 uint32_t *failed_arr;
1269 for (
i = 0;
i < total_failures - 1; ++
i) {
1285 uint32_t num_seg, uint32_t
seg_size)
1320 for (
i = 0;
i <
x->ov_vec.v_count[0]; ++
i)
1335 for (j = 0,
i = 0; j <
count; ++j,
i = 0) {
1340 memcpy(&buf_data[
i *
bvec[j].ov_vec.v_count[
i]],
1342 bvec[j].ov_vec.v_count[
i]);
1345 &buf_data[
i *
bvec[j].ov_vec.v_count[
i]],
1364 for (j = 0; j <
size; ++j) {
1406 { "reed_solomon_recover_with_fail_vec", test_rs_fv_recover }, \ 1407 { "reed_solomon_recover_with_fail_vec_rand", test_rs_fv_rand_recover }, \ 1408 { "xor_recover_with_fail_vec", test_xor_fv_recover }, \ 1409 { "xor_recover_with_fail_index", test_xor_fail_idx_recover }, \ 1410 { "buffer_xor", test_buffer_xor }, \ 1411 { "parity_math_diff_xor", test_parity_math_diff_xor }, \ 1412 { "parity_math_diff_rs", test_parity_math_diff_rs }, \ 1413 { "incr_recov_rs", test_incr_recov_rs }, \ 1425 .
ts_name =
"parity_math_ssse3-ut",
1442 uint32_t data_count = 0;
1443 uint32_t parity_count = 0;
1444 uint32_t buff_size = 0;
1445 uint32_t fail_count = 0;
1456 fail_count = data_count + parity_count;
1461 for (
i = 0;
i < data_count; ++
i) {
1470 unit_spoil(buff_size, fail_count, data_count);
1596 { .ub_name =
"s 10/05/ 4K",
1599 .ub_block_size =
KB(4),
1600 .ub_blocks_per_op = 15 },
1602 { .ub_name =
"m 20/06/ 4K",
1605 .ub_block_size =
KB(4),
1606 .ub_blocks_per_op = 26 },
1608 { .ub_name =
"l 30/12/ 4K",
1611 .ub_block_size =
KB(4),
1612 .ub_blocks_per_op = 42 },
1614 { .ub_name =
"s 10/05/ 32K",
1617 .ub_block_size =
KB(32),
1618 .ub_blocks_per_op = 15 },
1620 { .ub_name =
"m 20/06/ 32K",
1623 .ub_block_size =
KB(32),
1624 .ub_blocks_per_op = 26 },
1626 { .ub_name =
"l 30/12/ 32K",
1629 .ub_block_size =
KB(32),
1630 .ub_blocks_per_op = 42 },
1632 { .ub_name =
"s 03/02/ 1M",
1635 .ub_block_size =
MB(1),
1636 .ub_blocks_per_op = 5 },
1638 { .ub_name =
"m 06/03/ 1M",
1641 .ub_block_size =
MB(1),
1642 .ub_blocks_per_op = 9 },
1644 { .ub_name =
"l 08/04/ 1M",
1647 .ub_block_size =
MB(1),
1648 .ub_blocks_per_op = 12 },
1650 { .ub_name =
"s 04/02/ 4K",
1653 .ub_block_size =
KB(4),
1654 .ub_blocks_per_op = 6 },
1656 { .ub_name =
"m 04/02/256K",
1659 .ub_block_size =
KB(256),
1660 .ub_blocks_per_op = 6 },
1662 { .ub_name =
"l 04/02/ 1M",
1665 .ub_block_size =
MB(1),
1666 .ub_blocks_per_op = 6 },
static void test_matrix_inverse(void)
static m0_bcount_t seg_size
enum m0_sns_ir_block_status sib_status
struct m0_bitmap * sin_bitmap
static m0_parity_elem_t m0_parity_add(m0_parity_elem_t x, m0_parity_elem_t y)
static struct m0_addb2_philter p
static void ub_large_1M(int iter)
static void bufvec_initialize(struct m0_bufvec **bvec, uint32_t count, uint32_t num_seg, uint32_t size)
static void incremental_recover(struct m0_parity_math *math, struct m0_bufvec *x, struct m0_bufvec *p)
M0_INTERNAL void m0_parity_math_fini(struct m0_parity_math *math)
static void unit_spoil(const uint32_t buff_size, const uint32_t fail_count, const uint32_t data_count)
#define M0_ALLOC_ARR(arr, nr)
M0_INTERNAL int m0_bitmap_init(struct m0_bitmap *map, size_t nr)
M0_INTERNAL void m0_bitmap_fini(struct m0_bitmap *map)
static bool expected_eq(const uint32_t data_count, const uint32_t buff_size)
static void mat_fill(struct m0_matrix *mat, int N, int K, enum ir_matrix_type mt)
static void ub_small_4_2_4K(int iter)
static void test_xor_fail_idx_recover(void)
static void sns_ir_nodes_gather(struct sns_ir_node *node, uint32_t node_nr, struct m0_bufvec *x, struct m0_bufvec *p, uint32_t *failed_arr)
M0_INTERNAL bool m0_buf_eq(const struct m0_buf *x, const struct m0_buf *y)
static void test_invalid_input(void)
static void _buf_free(struct m0_buf *buf)
struct m0_matrix mc_mat_result
static bool config_generate(uint32_t *data_count, uint32_t *parity_count, uint32_t *buff_size, const enum m0_parity_cal_algo algo)
static struct net_test_cmd_node * node
M0_INTERNAL void m0_parity_math_buffer_xor(struct m0_buf *dest, const struct m0_buf *src)
static void direct_recover(struct m0_parity_math *math, struct m0_bufvec *x, struct m0_bufvec *p)
static void buf_free(struct m0_buf *buf, uint32_t count)
M0_INTERNAL void m0_buf_init(struct m0_buf *buf, void *data, uint32_t nob)
M0_INTERNAL bool m0_matrix_is_init(const struct m0_matrix *mat)
M0_INTERNAL void m0_free_aligned(void *data, size_t size, unsigned shift)
void parity_math_tb(void)
static void rhs_prepare(const struct m0_sns_ir *ir, struct m0_matvec *des, const struct m0_bufvec *x, const struct m0_bufvec *p, const uint32_t *failed_arr, uint32_t total_failures)
static void vandermonde_row_set(struct m0_matrix *mat, int row)
M0_INTERNAL void * m0_bufvec_cursor_addr(struct m0_bufvec_cursor *cur)
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_sns_ir_fini(struct m0_sns_ir *ir)
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)
static bool rand_rs_config_generate(uint32_t *data_count, uint32_t *parity_count, uint32_t *buff_size)
struct m0_sns_ir_block * si_blocks
static void test_parity_math_diff_xor(void)
static void ub_medium_4K(int iter)
static void test_parity_math_diff_rs(void)
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_init(const struct m0_parity_math *math, uint32_t local_nr, struct m0_sns_ir *ir)
M0_INTERNAL int m0_bufvec_alloc(struct m0_bufvec *bufvec, uint32_t num_segs, m0_bcount_t seg_size)
M0_INTERNAL void m0_parity_math_calculate(struct m0_parity_math *math, struct m0_buf *data, struct m0_buf *parity)
static void bufvec_fini(struct m0_bufvec *bvec, uint32_t count)
M0_INTERNAL void m0_bufvec_free(struct m0_bufvec *bufvec)
static void test_recovery(const enum m0_parity_cal_algo algo, const enum recovery_type rt)
M0_INTERNAL bool m0_bufvec_cursor_move(struct m0_bufvec_cursor *cur, m0_bcount_t count)
static void test_parity_math_diff(uint32_t parity_cnt)
M0_INTERNAL void m0_matrix_row_operate(struct m0_matrix *m, uint32_t row, m0_parity_elem_t c, m0_matvec_matrix_binary_operator_t f)
static void test_incr_recov_rs(void)
static void sns_ir_nodes_recover(struct sns_ir_node *node, uint32_t node_nr, struct m0_bufvec *x, struct m0_bufvec *p)
static void ub_small_4_2_256K(int iter)
static uint8_t data[DATA_UNIT_COUNT_MAX][UNIT_BUFF_SIZE_MAX]
m0_parity_elem_t * mv_vector
static void test_xor_fv_recover(void)
M0_INTERNAL m0_bcount_t m0_bufvec_cursor_step(const struct m0_bufvec_cursor *cur)
static void ub_small_4_2_1M(int iter)
static void null_matrix_fill(struct m0_matrix *mat, int N)
static void ub_medium_32K(int iter)
M0_INTERNAL void m0_matrix_rows_operate(struct m0_matrix *m, uint32_t row0, uint32_t row1, m0_matvec_matrix_binary_operator_t f0, m0_parity_elem_t c0, m0_matvec_matrix_binary_operator_t f1, m0_parity_elem_t c1, m0_matvec_matrix_binary_operator_t f)
static int32_t fail_index_xor
static int matrix_init(struct mat_collection *)
static struct net_test_cmd_node nodes[NTC_MULTIPLE_NODES]
static void test_rs_fv_rand_recover(void)
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 struct m0_bufvec bvec
static void bufvec_buf(struct m0_bufvec *bvec, struct m0_buf *buf, uint32_t count, bool dir)
M0_INTERNAL void m0_bufvec_cursor_init(struct m0_bufvec_cursor *cur, const struct m0_bufvec *bvec)
static struct rectype rt[]
struct m0_matrix mc_identity_mat
static bool bufvec_eq(struct m0_bufvec *bvec1, struct m0_bufvec *bvec2)
M0_INTERNAL int m0_sns_ir_mat_compute(struct m0_sns_ir *ir)
struct m0_matrix mc_mat_inverse
M0_INTERNAL int m0_parity_math_init(struct m0_parity_math *math, uint32_t data_count, uint32_t parity_count)
static void matrix_fini(struct mat_collection *matrices)
struct m0_reed_solomon si_rs
static uint32_t * failure_setup(struct m0_parity_math *math, uint32_t total_failures, enum failure_type ft)
static void test_incr_recov(void)
static void parity_calculate(struct m0_parity_math *math, struct m0_bufvec *x, struct m0_bufvec *p, uint32_t num_seg, uint32_t seg_size)
static void failure_register(struct m0_sns_ir *ir, struct m0_bufvec *recov_arr, uint32_t *failed_arr, uint32_t total_failures)
M0_INTERNAL void m0_bitmap_set(struct m0_bitmap *map, size_t idx, bool val)
M0_INTERNAL void m0_matrix_multiply(const struct m0_matrix *ma, const struct m0_matrix *mb, struct m0_matrix *mc)
static void ub_small_4K(int iter)
static void ub_large_4K(int iter)
M0_INTERNAL void m0_buf_free(struct m0_buf *buf)
static void ub_large_32K(int iter)
struct m0_ut_suite parity_math_ut
m0_parity_elem_t * m0_matrix_elem_get(const struct m0_matrix *m, uint32_t x, uint32_t y)
m0_parity_elem_t * m0_matvec_elem_get(const struct m0_matvec *v, uint32_t x)
static void bufvec_fill(struct m0_bufvec *x)
static void sns_ir_nodes_compare(struct sns_ir_node *node, struct m0_bufvec *x, struct m0_bufvec *p)
static void array_randomly_fill(uint32_t *r_arr, uint32_t size, uint32_t range)
static uint8_t expected[DATA_UNIT_COUNT_MAX][UNIT_BUFF_SIZE_MAX]
static bool compare(const struct m0_sns_ir *ir, const uint32_t *failed_arr, const struct m0_bufvec *x, const struct m0_matvec *r)
static void ub_small_1M(int iter)
#define m0_forall(var, nr,...)
static bool mat_compare(struct m0_matrix *mat1, struct m0_matrix *mat2)
M0_INTERNAL void m0_matrix_fini(struct m0_matrix *m)
M0_INTERNAL void m0_identity_matrix_fill(struct m0_matrix *identity_mat)
static uint8_t fail[DATA_UNIT_COUNT_MAX+PARITY_UNIT_COUNT_MAX]
M0_INTERNAL uint64_t m0_rnd64(uint64_t *seed)
M0_INTERNAL int m0_matrix_init(struct m0_matrix *m, uint32_t w, uint32_t h)
static void sns_ir_nodes_init(struct m0_parity_math *math, struct sns_ir_node *nodes, uint32_t *failed_arr, uint32_t node_nr, uint32_t alive_nr)
#define M0_ALLOC_PTR(ptr)
static void invert(int N, int K, enum ir_matrix_type mt, struct mat_collection *matrices)
M0_INTERNAL m0_parity_elem_t m0_parity_pow(m0_parity_elem_t x, m0_parity_elem_t p)
struct m0_ut_suite parity_math_ssse3_ut
static void test_rs_fv_recover(void)
#define M0_ALLOC_ARR_ALIGNED(arr, nr, shift)
struct m0_bufvec * sin_recov_arr
static void buf_initialize(struct m0_buf *buf, uint32_t size, uint32_t len)
#define M0_ASSERT_INFO(cond, fmt,...)
struct m0_ub_set m0_parity_math_ub
static struct m0_fop_type * ft[]
M0_INTERNAL int m0_matvec_init(struct m0_matvec *v, uint32_t sz)
static void sns_ir_nodes_fini(struct sns_ir_node *node, uint32_t node_nr, uint32_t total_failures)
static void test_buffer_xor(void)
M0_INTERNAL int m0_matrix_invert(const struct m0_matrix *in_mat, struct m0_matrix *mat_inverse)
static m0_parity_elem_t m0_parity_mul(m0_parity_elem_t x, m0_parity_elem_t y)
M0_INTERNAL void m0_matvec_fini(struct m0_matvec *v)
static void reconstruct(const struct m0_sns_ir *ir, const struct m0_matvec *b, struct m0_matvec *r)
static void alive_arrays_fill(struct m0_sns_ir *ir, uint32_t *alive_blocks, uint32_t start_idx, uint32_t count)
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)
static uint32_t UNIT_BUFF_SIZE
struct m0_pdclust_src_addr src
static uint32_t block_nr(const struct m0_sns_ir *ir)
static void identity_row_set(struct m0_matrix *mat, int row)
uint32_t pmi_parity_count
static uint8_t parity[DATA_UNIT_COUNT_MAX][UNIT_BUFF_SIZE_MAX]
static void ub_small_32K(int iter)
static int ub_init(const char *opts M0_UNUSED)
static void test_incr_recov_init(void)
static void ub_medium_1M(int iter)