parity_math_ut.c

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2021 Seagate Technology LLC and/or its Affiliates
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * For any questions about this software or licensing,
 * please email opensource@seagate.com or cortx-questions@seagate.com.
 *
 */


#include "lib/types.h"
#include "lib/assert.h"
#include "lib/memory.h"
#include "lib/errno.h"       /* EDOM */
#include "lib/arith.h"       /* m0_rnd64 */

#include "lib/ub.h"
#include "ut/ut.h"
#include "sns/parity_math.h"

#define KB(x)   ((x) * 1024)
#define MB(x)   (KB(x) * 1024)

enum {
        MAX_NUM_ROWS = 20,
};

enum {
        DATA_UNIT_COUNT_MAX      = 30,
        PARITY_UNIT_COUNT_MAX    = 12,
        DATA_TO_PRTY_RATIO_MAX   = DATA_UNIT_COUNT_MAX / PARITY_UNIT_COUNT_MAX,
        UNIT_BUFF_SIZE_MAX       = MB(1),
        DATA_UNIT_COUNT          = 15,
        PARITY_UNIT_COUNT        = 1,
        RS_MAX_PARITY_UNIT_COUNT = DATA_UNIT_COUNT - 1,
        NODES                    = 15,
};

enum {
        NUM_SEG  = 8,
        SEG_SIZE = 64,
};

static uint8_t expected[DATA_UNIT_COUNT_MAX][UNIT_BUFF_SIZE_MAX];
static uint8_t data    [DATA_UNIT_COUNT_MAX][UNIT_BUFF_SIZE_MAX];
static uint8_t parity  [DATA_UNIT_COUNT_MAX][UNIT_BUFF_SIZE_MAX];
static uint8_t fail    [DATA_UNIT_COUNT_MAX+PARITY_UNIT_COUNT_MAX];
static int32_t duc;
static int32_t puc;
static int32_t fuc;
static uint32_t UNIT_BUFF_SIZE;
static int32_t fail_index_xor;
static uint64_t seed;

struct mat_collection {
        struct m0_matrix mc_mat;
        struct m0_matrix mc_mat_inverse;
        struct m0_matrix mc_identity_mat;
        struct m0_matrix mc_mat_result;
};

enum recovery_type {
        FAIL_VECTOR,
        FAIL_INDEX,
};

struct sns_ir_node {
        struct m0_sns_ir  sin_ir;
        struct m0_bufvec *sin_recov_arr;
        struct m0_bitmap *sin_bitmap;
        uint32_t         *sin_alive;
        uint32_t          sin_alive_nr;
};

enum failure_type {
        ALL_DATA,
        ALL_PARITY,
        MIXED_FAILURE,
};

enum ir_matrix_type {
        /* Full rank Vandermonde matrix */
        IRM_VANDMAT,
        /* Matrix is generated by elementary row operations on IRM_VANDMAT. */
        IRM_NORM_VANDMAT,
        /* Singular matrix */
        IRM_SINGULAR_MAT,
};

static void test_matrix_inverse(void);
static void test_incr_recov_init(void);
static void test_incr_recov(void);
static void test_invalid_input(void);
static void test_init(void);
static int matrix_init(struct mat_collection*);
static void mat_fill(struct m0_matrix *mat, int N, int K,
                     enum ir_matrix_type mt);
static void identity_row_set(struct m0_matrix *mat, int row);
static void vandermonde_row_set(struct m0_matrix *mat, int row);
static void null_matrix_fill(struct m0_matrix *mat, int N);
static void invert(int N, int K, enum ir_matrix_type mt,
                   struct mat_collection *matrices);
static bool mat_compare(struct m0_matrix *mat1, struct m0_matrix *mat2);
static void matrix_fini(struct mat_collection *matrices);
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 direct_recover(struct m0_parity_math *math, struct m0_bufvec *x,
                           struct m0_bufvec *p);
static uint32_t *failure_setup(struct m0_parity_math *math,
                               uint32_t total_failures, enum failure_type ft);
static void array_randomly_fill(uint32_t *r_arr, uint32_t size,
                                uint32_t range);
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 reconstruct(const struct m0_sns_ir *ir, const struct m0_matvec *b,
                        struct m0_matvec *r);
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 incremental_recover(struct m0_parity_math *math,
                                struct m0_bufvec *x, struct m0_bufvec *p);

/* Initializes various objects for every member of array "nodes". */
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);
static void failure_register(struct m0_sns_ir *ir, struct m0_bufvec *recov_arr,
                             uint32_t *failed_arr, uint32_t total_failures);

static void alive_arrays_fill(struct m0_sns_ir *ir, uint32_t *alive_blocks,
                              uint32_t start_idx, uint32_t count);

/* Each node partially recovers blocks, using its own alive blocks. */
static void sns_ir_nodes_recover(struct sns_ir_node *node, uint32_t node_nr,
                                 struct m0_bufvec *x, struct m0_bufvec *p);

/* node[0] gathers partially recovered blocks from other nodes to produce the
 * final result. */
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);

/* node[0] compares the recovered blocks with original blocks. */
static void sns_ir_nodes_compare(struct sns_ir_node *node, struct m0_bufvec *x,
                                 struct m0_bufvec *p);
static void sns_ir_nodes_fini(struct sns_ir_node *node, uint32_t node_nr,
                              uint32_t total_failures);
static inline uint32_t block_nr(const struct m0_sns_ir *ir);

static void bufvec_initialize(struct m0_bufvec **bvec, uint32_t count,
                              uint32_t num_seg, uint32_t size);
static void bufvec_fill(struct m0_bufvec *x);
static void bufvec_fini(struct m0_bufvec *bvec, uint32_t count);
static bool bufvec_eq(struct m0_bufvec *bvec1, struct m0_bufvec *bvec2);
static void buf_initialize(struct m0_buf *buf, uint32_t size, uint32_t len);
static void buf_free(struct m0_buf *buf, uint32_t count);

/* Converts m0_bufvec to m0_buf and vice versa. Argument "dir" decides
 * direction of conversion. */
static void bufvec_buf(struct m0_bufvec *bvec, struct m0_buf *buf,
                       uint32_t count, bool dir);

static void unit_spoil(const uint32_t buff_size,
                       const uint32_t fail_count,
                       const uint32_t data_count)
{
        uint32_t i;

        for (i = 0; i < fail_count; ++i)
                if (fail[i]) {
                        if (i < data_count)
                                memset(data[i], 0xFF, buff_size);
                        else
                                memset(parity[i - data_count], 0xFF, buff_size);
                }
}

static bool expected_eq(const uint32_t data_count, const uint32_t buff_size)
{
        return m0_forall(i, data_count,
                         m0_forall(j, buff_size, expected[i][j] == data[i][j]));
}

static bool config_generate(uint32_t *data_count,
                            uint32_t *parity_count,
                            uint32_t *buff_size,
                            const enum m0_parity_cal_algo algo)
{
        int32_t  i;
        int32_t  j;
        int32_t  puc_max = PARITY_UNIT_COUNT_MAX;

        if (algo == M0_PARITY_CAL_ALGO_XOR) {
                fuc = 1;
                puc = 1;
                puc_max = 1;
                fail_index_xor--;
                if (fail_index_xor < 0) {
                        duc --;
                        fail_index_xor = duc;
                }
                if(duc < 1)
                        return false;
        } else if (algo == M0_PARITY_CAL_ALGO_REED_SOLOMON) {
                if (fuc <= 1) {
                        puc-=3;
                        if (puc <= 1) {
                                duc-=9;
                                puc = duc / DATA_TO_PRTY_RATIO_MAX;
                        }
                        fuc = puc+duc;
                }

                if (puc < 1)
                        return false;
        }
        memset(fail, 0, DATA_UNIT_COUNT_MAX + puc_max);

        for (i = 0; i < duc; ++i) {
                for (j = 0; j < UNIT_BUFF_SIZE; ++j) {
                        data[i][j] = (uint8_t) m0_rnd64(&seed);
                        expected[i][j] = data[i][j];
                }
        }

        j = 0;

        if (algo == M0_PARITY_CAL_ALGO_XOR)
                fail[fail_index_xor] = 1;
        else if (algo == M0_PARITY_CAL_ALGO_REED_SOLOMON) {
                for (i = 0; i < fuc; ++i) {
                        if (j >= puc)
                                break;
                        fail[i] = (data[i][0] & 1) || (data[i][0] & 2) ||
                                (data[i][0] & 3);
                        if (fail[i])
                                ++j;
                }

                if (!j) { /* at least one fail */
                        fail[fuc/2] = 1;
                }
        }

        *data_count = duc;
        *parity_count = puc;
        *buff_size = UNIT_BUFF_SIZE;

        if (algo == M0_PARITY_CAL_ALGO_REED_SOLOMON)
                fuc -= 3;

        return true;
}

static bool rand_rs_config_generate(uint32_t *data_count,
                                    uint32_t *parity_count,
                                    uint32_t *buff_size)
{
        int32_t  i;
        int32_t  j;
        int32_t  puc_max = PARITY_UNIT_COUNT_MAX;
        uint32_t failed_count = 0;

        if (fuc <= 1) {
                puc-=3;
                if (puc <= 1) {
                        duc-=9;
                        puc = duc / DATA_TO_PRTY_RATIO_MAX;
                }
                fuc = puc+duc;
        }

        if (puc < 1)
                return false;

        memset(fail, 0, DATA_UNIT_COUNT_MAX + puc_max);

        /* Fill random data and create back of the data */
        for (i = 0; i < duc; ++i) {
                for (j = 0; j < UNIT_BUFF_SIZE; ++j) {
                        data[i][j] = (uint8_t) m0_rnd64(&seed);
                        expected[i][j] = data[i][j];
                }
        }

        /* Fill failure array for random indices for mixed failures */
        failed_count = ((uint8_t)m0_rnd64(&seed) % puc) + 1;
        for (i = 0; i < failed_count; i++) {
                j = (uint8_t) m0_rnd64(&seed) % (duc + puc);
                fail[j] = 1;
        }

        *data_count = duc;
        *parity_count = puc;
        *buff_size = UNIT_BUFF_SIZE;

        fuc -= 3;

        return true;
}

static void test_recovery(const enum m0_parity_cal_algo algo,
                          const enum recovery_type rt)
{
        uint32_t              i;
        uint32_t              data_count;
        uint32_t              parity_count;
        uint32_t              buff_size;
        uint32_t              fail_count;
        struct m0_buf         data_buf[DATA_UNIT_COUNT_MAX];
        struct m0_buf         parity_buf[DATA_UNIT_COUNT_MAX];
        struct m0_buf         fail_buf;
        struct m0_parity_math *math;
        int                   ret;

        M0_ALLOC_PTR(math);
        M0_UT_ASSERT(math != NULL);

        while (config_generate(&data_count, &parity_count, &buff_size, algo)) {
                fail_count = data_count + parity_count;

                ret = m0_parity_math_init(math, data_count, parity_count);
                M0_UT_ASSERT(ret == 0);

                for (i = 0; i < data_count; ++i) {
                        m0_buf_init(&data_buf[i], data[i], buff_size);
                        m0_buf_init(&parity_buf[i], parity[i], buff_size);
                }

                m0_buf_init(&fail_buf, fail, buff_size);

                m0_parity_math_calculate(math, data_buf, parity_buf);

                unit_spoil(buff_size, fail_count, data_count);

                if (rt == FAIL_INDEX)
                        m0_parity_math_fail_index_recover(math, data_buf,
                                                          parity_buf,
                                                          fail_index_xor);
                else if (rt == FAIL_VECTOR) {
                        ret = m0_parity_math_recover(math, data_buf, parity_buf,
                                                     &fail_buf, 0);
                        M0_UT_ASSERT(ret == 0);
                }

                m0_parity_math_fini(math);

                M0_ASSERT_INFO(expected_eq(data_count, buff_size),
                               "Recovered data is unexpected");
        }

        m0_free(math);
}

static void test_rs_fv_recover(void)
{
        test_init();
        test_recovery(M0_PARITY_CAL_ALGO_REED_SOLOMON, FAIL_VECTOR);
}

static void test_rs_fv_rand_recover(void)
{
        uint32_t              i;
        uint32_t              data_count;
        uint32_t              parity_count;
        uint32_t              buff_size;
        uint32_t              fail_count;
        struct m0_buf         data_buf[DATA_UNIT_COUNT_MAX];
        struct m0_buf         parity_buf[DATA_UNIT_COUNT_MAX];
        struct m0_buf         fail_buf;
        struct m0_parity_math math;
        int                   ret;

        test_init();
        duc = DATA_UNIT_COUNT_MAX;
        puc = PARITY_UNIT_COUNT_MAX;
        fuc = PARITY_UNIT_COUNT_MAX;

        while (rand_rs_config_generate(&data_count, &parity_count, &buff_size)) {
                fail_count = data_count + parity_count;

                ret = m0_parity_math_init(&math, data_count, parity_count);
                M0_UT_ASSERT(ret == 0);

                for (i = 0; i < data_count; ++i) {
                        m0_buf_init(&data_buf[i], data[i], buff_size);
                        m0_buf_init(&parity_buf[i], parity[i], buff_size);
                }

                m0_buf_init(&fail_buf, fail, buff_size);

                m0_parity_math_calculate(&math, data_buf, parity_buf);

                unit_spoil(buff_size, fail_count, data_count);

                ret = m0_parity_math_recover(&math, data_buf, parity_buf,
                                             &fail_buf, 0);
                M0_UT_ASSERT(ret == 0);

                m0_parity_math_fini(&math);

                M0_ASSERT_INFO(expected_eq(data_count, buff_size),
                               "Recovered data is unexpected");
        }
}

static void test_xor_fv_recover(void)
{
        test_init();
        duc = DATA_UNIT_COUNT_MAX;
        fail_index_xor = DATA_UNIT_COUNT_MAX + 1;
        test_recovery(M0_PARITY_CAL_ALGO_XOR, FAIL_VECTOR);
}

static void test_xor_fail_idx_recover(void)
{
        test_init();
        duc = DATA_UNIT_COUNT_MAX;
        fail_index_xor = DATA_UNIT_COUNT_MAX + 1;
        test_recovery(M0_PARITY_CAL_ALGO_XOR, FAIL_INDEX);
}

static void test_buffer_xor(void)
{
        bool          generated;
        uint32_t      data_count;
        uint32_t      parity_count;
        uint32_t      buff_size;
        struct m0_buf buf1;
        struct m0_buf buf2;

        test_init();
        duc = 3;
        fail_index_xor = 0;
        generated = config_generate(&data_count, &parity_count, &buff_size,
                                    M0_PARITY_CAL_ALGO_XOR);
        M0_UT_ASSERT(generated);
        M0_UT_ASSERT(data_count == 2);

        m0_buf_init(&buf1, data[0], buff_size);
        m0_buf_init(&buf2, data[1], buff_size);

        /*
         * Swap 2 buffers and then swap them back, so at the end they must
         * contain the original values.
         */
        m0_parity_math_buffer_xor(&buf1, &buf2);
        m0_parity_math_buffer_xor(&buf2, &buf1);
        m0_parity_math_buffer_xor(&buf1, &buf2);
        m0_parity_math_buffer_xor(&buf2, &buf1);
        m0_parity_math_buffer_xor(&buf1, &buf2);
        m0_parity_math_buffer_xor(&buf2, &buf1);

        M0_ASSERT_INFO(expected_eq(data_count, buff_size),
                       "Recovered data is unexpected");
}

static void test_parity_math_diff(uint32_t parity_cnt)
{
        uint32_t              i;
        uint32_t              j;
        uint32_t              ret;
        uint8_t              *arr;
        struct m0_buf         data_buf_old[DATA_UNIT_COUNT];
        struct m0_buf         data_buf_new[DATA_UNIT_COUNT];
        struct m0_parity_math math;
        struct m0_buf        *p_old;
        struct m0_buf        *p_new;


        for (i = 0; i < DATA_UNIT_COUNT; ++i) {
                for (j = 0; j < UNIT_BUFF_SIZE; ++j) {
                        data[i][j] = (uint8_t) m0_rnd64(&seed);
                        if (i % 2)
                                data[i + DATA_UNIT_COUNT][j] =
                                        (uint8_t) m0_rnd64(&seed);
                        else
                                data[i + DATA_UNIT_COUNT][j] = data[i][j];
                }
        }

        for (i = 0; i < DATA_UNIT_COUNT; ++i) {
                m0_buf_init(&data_buf_old[i], data[i], UNIT_BUFF_SIZE);
                m0_buf_init(&data_buf_new[i], data[i + DATA_UNIT_COUNT],
                            UNIT_BUFF_SIZE);
        }

        ret = m0_parity_math_init(&math, DATA_UNIT_COUNT,
                                  parity_cnt);
        M0_UT_ASSERT(ret == 0);
        M0_ALLOC_ARR(p_old, parity_cnt);
        M0_UT_ASSERT(p_old != NULL);
        M0_ALLOC_ARR(p_new, parity_cnt);
        M0_UT_ASSERT(p_new != NULL);

        for(i = 0; i < parity_cnt; ++i) {
                M0_ALLOC_ARR(arr, UNIT_BUFF_SIZE);
                M0_UT_ASSERT(arr != NULL);
                m0_buf_init(&p_old[i], arr, UNIT_BUFF_SIZE);
                M0_ALLOC_ARR(arr, UNIT_BUFF_SIZE);
                M0_UT_ASSERT(arr != NULL);
                m0_buf_init(&p_new[i], arr, UNIT_BUFF_SIZE);
        }

        m0_parity_math_calculate(&math, data_buf_old, p_old);
        m0_parity_math_calculate(&math, data_buf_new, p_new);

        for (i = 0; i < DATA_UNIT_COUNT; ++i) {
                if (i % 2) {
                        ret = m0_parity_math_diff(&math, data_buf_old,
                                                  data_buf_new, p_old, i);
                        M0_UT_ASSERT(ret == 0);
                }
        }

        for(i = 0; i < parity_cnt; ++i) {
                M0_UT_ASSERT(m0_buf_eq(&p_old[i], &p_new[i]));
        }

        m0_parity_math_fini(&math);

        for(i = 0; i < parity_cnt; ++i) {
                m0_buf_free(&p_old[i]);
                m0_buf_free(&p_new[i]);
        }
        m0_free(p_old);
        m0_free(p_new);
}

static void test_parity_math_diff_xor(void)
{
        test_init();
        test_parity_math_diff(PARITY_UNIT_COUNT);
}

static void test_parity_math_diff_rs(void)
{
        uint32_t i;
        test_init();
        for (i = 2; i <= RS_MAX_PARITY_UNIT_COUNT; ++i) {
                test_parity_math_diff(i);
        }
}

static void test_incr_recov_rs(void)
{
        test_init();
        test_matrix_inverse();
        test_incr_recov_init();
        test_incr_recov();
        test_invalid_input();
}

static void test_matrix_inverse(void)
{
        uint32_t              i;
        uint32_t              j;
        uint32_t              k;
        uint32_t              N;
        struct mat_collection matrices;

        for (i = 0; i < 10; ++i) {
                N = matrix_init(&matrices);
                m0_identity_matrix_fill(&matrices.mc_identity_mat);
                for (j = IRM_VANDMAT; j <= IRM_SINGULAR_MAT; ++j) {
                        for (k = 1; k < N; ++k) {
                                invert(N, k, j, &matrices);
                                if (j == IRM_SINGULAR_MAT)
                                        continue;
                                m0_matrix_multiply(&matrices.mc_mat,
                                                   &matrices.mc_mat_inverse,
                                                   &matrices.mc_mat_result);
                                M0_UT_ASSERT(mat_compare(&matrices.mc_mat_result,
                                            &matrices.mc_identity_mat));
                        }
                }
                matrix_fini(&matrices);
        }
}

static int matrix_init(struct mat_collection *matrices)
{
        int N = 0;
        int ret;

        while (N == 0)
                N = m0_rnd64(&seed) % (MAX_NUM_ROWS + 1);

        ret = m0_matrix_init(&matrices->mc_mat, N, N);
        M0_UT_ASSERT(ret == 0);

        ret = m0_matrix_init(&matrices->mc_mat_inverse, N, N);
        M0_UT_ASSERT(ret == 0);

        ret = m0_matrix_init(&matrices->mc_identity_mat, N, N);
        M0_UT_ASSERT(ret == 0);

        ret = m0_matrix_init(&matrices->mc_mat_result, N, N);
        M0_UT_ASSERT(ret == 0);
        return N;
}

static void invert(int N, int K, enum ir_matrix_type mt,
                   struct mat_collection *matrices)
{
        int ret;

        mat_fill(&matrices->mc_mat, N, K, mt);
        null_matrix_fill(&matrices->mc_mat_result, N);

        ret = m0_matrix_invert(&matrices->mc_mat, &matrices->mc_mat_inverse);

        if (mt == IRM_SINGULAR_MAT)
                M0_UT_ASSERT(ret == -EDOM);
        else
                M0_UT_ASSERT(ret == 0);
}

static void mat_fill(struct m0_matrix *mat, int N, int K,
                     enum ir_matrix_type mt)
{
        m0_parity_elem_t  i;
        m0_parity_elem_t  j;
        m0_parity_elem_t *coeff_vec;

        switch (mt) {
        case IRM_VANDMAT:
                for (i = 0; i < N; ++i) {
                        vandermonde_row_set(mat, i);
                }
                break;
        case IRM_NORM_VANDMAT:
                for (i = 0; i < N - K; ++i) {
                        identity_row_set(mat, i);
                }

                for (; i < N; ++i) {
                        vandermonde_row_set(mat, i);
                }
                break;
        case IRM_SINGULAR_MAT:
                /* First N - K  rows are linearly independent, rest are within
                 * the span of first N - K rows. */
                M0_ALLOC_ARR(coeff_vec, N - K);
                M0_UT_ASSERT(coeff_vec != NULL);

                for (i = 0; i < N - K; ++i) {
                        coeff_vec[i] = m0_rnd64(&seed)%N;
                        vandermonde_row_set(mat, i);
                }
                for (; i < N; ++i) {
                        m0_matrix_row_operate(mat, i, 0, m0_parity_mul);
                        for (j = 0; j < N - K; ++j) {
                                m0_matrix_rows_operate(mat, i, j,
                                                       m0_parity_mul,
                                                       1, m0_parity_mul,
                                                       coeff_vec[j],
                                                       m0_parity_add);
                        }
                }
                m0_free(coeff_vec);
                break;
        }
}

static void identity_row_set(struct m0_matrix *mat, int row)
{
        uint32_t i;

        M0_UT_ASSERT(mat != NULL);
        M0_UT_ASSERT(mat->m_width != 0);
        M0_UT_ASSERT(mat->m_width == mat->m_height);
        M0_UT_ASSERT(row < mat->m_height);

        for (i = 0; i < mat->m_width; ++i) {
                *m0_matrix_elem_get(mat, row, i) = !! (i == row);
        }

}

static void vandermonde_row_set(struct m0_matrix *mat, int row)
{
        uint32_t i;

        M0_UT_ASSERT(m0_matrix_is_init(mat));
        M0_UT_ASSERT(row < mat->m_height);

        for (i = 0; i < mat->m_width; ++i) {
                *m0_matrix_elem_get(mat, row, i) = m0_parity_pow(row, i);
        }
}

static void null_matrix_fill(struct m0_matrix *mat, int N)
{
        uint32_t i;

        for (i = 0; i < N; ++i) {
                m0_matrix_row_operate(mat, i, 0, m0_parity_mul);
        }
}

static bool mat_compare(struct m0_matrix *mat1, struct m0_matrix *mat2)
{
        M0_UT_ASSERT(mat1 != NULL);
        M0_UT_ASSERT(mat2 != NULL);
        M0_UT_ASSERT(mat1->m_width == mat2->m_width);
        M0_UT_ASSERT(mat1->m_height == mat2->m_height);

        return m0_forall(i, mat1->m_width,
                         m0_forall(j, mat1->m_height,
                                   *m0_matrix_elem_get(mat1, j, i) ==
                                   *m0_matrix_elem_get(mat2, j, i)));
}

static void matrix_fini(struct mat_collection *matrices)
{
        m0_matrix_fini(&matrices->mc_mat);
        m0_matrix_fini(&matrices->mc_mat_inverse);
        m0_matrix_fini(&matrices->mc_identity_mat);
        m0_matrix_fini(&matrices->mc_mat_result);

}

/* Recovery mechanism solves a system of equations of the form Vx = b, where
 * x is a vector of lost blocks, V is a matrix of coefficients and b is a
 * vector of available blocks. During test_incr_recov_init(), we solve the
 * system by computing V^{-1}.b *directly* rather than *incrementally* In test
 * incr_recov() we solve this system incrementally. */
static void test_incr_recov_init(void)
{
        uint32_t               parity_cnt;
        uint32_t               i;
        int                    ret;
        struct m0_bufvec      *x;
        struct m0_bufvec      *p;
        struct m0_parity_math  math;

        /* m0_parity_math_init() switches to XOR algorithm when parity_cnt = 1,
         * hence we start with parity_cnt = 2. */
        for (parity_cnt = 2; parity_cnt < RS_MAX_PARITY_UNIT_COUNT;
             ++parity_cnt) {
                ret = m0_parity_math_init(&math, DATA_UNIT_COUNT, parity_cnt);
                M0_UT_ASSERT(ret == 0);

                bufvec_initialize(&x, math.pmi_data_count, 1, 1);
                bufvec_initialize(&p, math.pmi_parity_count, 1, 1);
                for (i = 0; i < DATA_UNIT_COUNT; ++i) {
                        bufvec_fill(&x[i]);
                }

                parity_calculate(&math, x, p, 1, 1);
                direct_recover(&math, x, p);
                bufvec_fini(x, math.pmi_data_count);
                bufvec_fini(p, parity_cnt);
                m0_parity_math_fini(&math);
        }
}

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)
{
        struct m0_buf *x_ser;
        struct m0_buf *p_ser;

        M0_ALLOC_ARR(x_ser, math->pmi_data_count);
        M0_UT_ASSERT(x_ser != NULL);
        M0_ALLOC_ARR(p_ser, math->pmi_parity_count);
        M0_UT_ASSERT(p_ser != NULL);

        buf_initialize(p_ser, math->pmi_parity_count, num_seg * seg_size);
        buf_initialize(x_ser, math->pmi_data_count, num_seg * seg_size);
        bufvec_buf(x, x_ser, math->pmi_data_count, true);
        m0_parity_math_calculate(math, x_ser, p_ser);
        bufvec_buf(p, p_ser, math->pmi_parity_count, false);

        buf_free(x_ser, math->pmi_data_count);
        buf_free(p_ser, math->pmi_parity_count);

        m0_free(x_ser);
        m0_free(p_ser);
}

static void direct_recover(struct m0_parity_math *math,  struct m0_bufvec *x,
                           struct m0_bufvec *p)
{
        uint32_t         i;
        uint32_t         total_failures = 0;
        uint32_t        *failed_arr;
        int              ret;
        struct m0_matvec b;
        struct m0_matvec r;
        struct m0_sns_ir ir;
        struct m0_bufvec recov_arr;

        while (total_failures == 0)
                total_failures =
                        m0_rnd64(&seed) % (math->pmi_parity_count + 1);

        failed_arr = failure_setup(math, total_failures, MIXED_FAILURE);
        ret = m0_sns_ir_init(math, 0, &ir);
        M0_UT_ASSERT(ret == 0);

        ret = m0_matvec_init(&b, ir.si_data_nr);
        M0_UT_ASSERT(ret == 0);

        rhs_prepare(&ir, &b, x, p, failed_arr, total_failures);

        for (i = 0; i < total_failures; ++i) {
                ret = m0_sns_ir_failure_register(&recov_arr,
                                                 failed_arr[i], &ir);
                M0_UT_ASSERT(ret == 0);
        }

        ret = m0_sns_ir_mat_compute(&ir);
        M0_UT_ASSERT(ret == 0);

        ret = m0_matvec_init(&r, ir.si_rs.rs_failed_nr);
        M0_UT_ASSERT(ret == 0);

        reconstruct(&ir, &b, &r);
        M0_UT_ASSERT(compare(&ir, failed_arr, x, &r));

        m0_free(failed_arr);
        m0_matvec_fini(&r);
        m0_matvec_fini(&b);
        m0_sns_ir_fini(&ir);
}

static uint32_t  *failure_setup(struct m0_parity_math *math,
                                uint32_t total_failures, enum failure_type ft)
{
        uint32_t *failed_arr;
        uint32_t  i;
        uint32_t  range = math->pmi_data_count;

        M0_ALLOC_ARR(failed_arr, total_failures);
        M0_UT_ASSERT(failed_arr != NULL);
        if (ft == MIXED_FAILURE)
                range = math->pmi_data_count + math->pmi_parity_count;
        else if (ft == ALL_DATA)
                range = math->pmi_data_count;
        else if (ft == ALL_PARITY)
                range = math->pmi_parity_count;
        array_randomly_fill(failed_arr, total_failures, range);
        if (ft == ALL_PARITY) {
                for (i = 0; i < total_failures; ++i) {
                        failed_arr[i] += math->pmi_data_count;
                }
        }

        return failed_arr;
}

static void array_randomly_fill(uint32_t *r_arr, uint32_t size,
                                uint32_t range)
{
        uint32_t interval;
        uint32_t i;

        M0_UT_ASSERT(size != 0);
        M0_UT_ASSERT(size <= range);

        interval = range/size;
        for (i = 0; i < size; ++i)
                r_arr[i] = m0_rnd64(&seed) % interval + i * interval;
        if (r_arr[size - 1] > range - 1)
                r_arr[size - 1] = m0_rnd64(&seed) % (range % interval) + (size - 1) *
                        interval;
}

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)
{
        uint32_t i;
        uint32_t j;
        uint32_t k;

        for (i = 0, j = 0, k = 0; i < ir->si_data_nr; ++i) {
                if (failed_arr[j] != i)
                        des->mv_vector[k++] = (((uint8_t **)x[i].ov_buf)[0])[0];
                else if (j < total_failures - 1)
                        ++j;
        }
        for (i = 0; i < ir->si_parity_nr && k < des->mv_size; ++i) {
                if (failed_arr[j] != i + ir->si_data_nr)
                        des->mv_vector[k++] = (((uint8_t **)p[i].ov_buf)[0])[0];
                else if (j < total_failures - 1)
                        ++j;
        }
}

static void reconstruct(const struct m0_sns_ir *ir, const struct m0_matvec *b,
                        struct m0_matvec *r)
{
        uint8_t **src;
        uint8_t **dest;
        uint32_t i;

        M0_ALLOC_ARR(src, b->mv_size);
        M0_UT_ASSERT(src != NULL);

        M0_ALLOC_ARR(dest, r->mv_size);
        M0_UT_ASSERT(dest != NULL);

        for (i = 0; i < b->mv_size; i++)
                src[i] = (uint8_t *)&b->mv_vector[i];

        for (i = 0; i < r->mv_size; i++)
                dest[i] = (uint8_t *)&r->mv_vector[i];

        ec_encode_data(1, b->mv_size, r->mv_size,
                       ir->si_rs.rs_decode_tbls, src, dest);

        m0_free(src);
        m0_free(dest);
}

static bool compare(const struct m0_sns_ir *ir, const uint32_t *failed_arr,
                    const struct m0_bufvec *x, const struct m0_matvec *r)
{
        uint32_t i;
        uint32_t j;

        for (j = 0; j < ir->si_rs.rs_failed_nr; j++) {
                i = failed_arr[j];
                if (i < ir->si_data_nr)
                        if ((uint8_t)*m0_matvec_elem_get(r, j) !=
                                (((uint8_t **)x[i].ov_buf)[0])[0])
                                return false;
        }

        return true;
}

static void test_incr_recov(void)
{
        uint32_t               parity_cnt;
        uint32_t               i;
        int                    ret;
        struct m0_bufvec      *x;
        struct m0_bufvec      *p;
        struct m0_parity_math  math;

        for (parity_cnt = 2; parity_cnt < RS_MAX_PARITY_UNIT_COUNT;
             ++parity_cnt) {
                ret = m0_parity_math_init(&math, DATA_UNIT_COUNT, parity_cnt);
                M0_UT_ASSERT(ret == 0);
                bufvec_initialize(&x, math.pmi_data_count, NUM_SEG, SEG_SIZE);
                bufvec_initialize(&p, math.pmi_parity_count, NUM_SEG, SEG_SIZE);
                for (i = 0; i < DATA_UNIT_COUNT; ++i) {
                        bufvec_fill(&x[i]);
                }
                parity_calculate(&math, x, p, NUM_SEG, SEG_SIZE);
                incremental_recover(&math, x, p);
                bufvec_fini(x, math.pmi_data_count);
                bufvec_fini(p, math.pmi_parity_count);
                m0_parity_math_fini(&math);
        }
}

static void incremental_recover(struct m0_parity_math *math,
                                struct m0_bufvec *x, struct m0_bufvec *p)
{
        uint32_t           *failed_arr;
        uint32_t            total_failures = 0;
        uint32_t            alive_nr;
        uint32_t            node_nr;
        uint32_t            ft;
        struct sns_ir_node *node;

        /* Alive blocks are distributed over all nodes. Each node maintains its
         * context of recovery using its private struct m0_sns_ir. In the end,
         * node0 gathers partial results from all other nodes and completes the
         * recovery. */
        for (ft = ALL_DATA; ft <= MIXED_FAILURE; ++ft) {
                for (node_nr = 4; node_nr < NODES; ++node_nr) {
                        M0_ALLOC_ARR(node, node_nr);
                        M0_UT_ASSERT(node != NULL);
                        while (total_failures == 0)
                                total_failures =
                                        m0_rnd64(&seed) % (math->pmi_parity_count + 1);
                        alive_nr = math->pmi_data_count +
                                math->pmi_parity_count - total_failures;
                        failed_arr = failure_setup(math, total_failures,
                                                   ft);
                        sns_ir_nodes_init(math, node, failed_arr, node_nr,
                                          alive_nr);
                        sns_ir_nodes_recover(node, node_nr, x, p);
                        sns_ir_nodes_gather(node, node_nr, x, p, failed_arr);
                        sns_ir_nodes_compare(node, x, p);
                        sns_ir_nodes_fini(node, node_nr, total_failures);
                        m0_free(node);
                        m0_free(failed_arr);
                }
        }
}

static void sns_ir_nodes_init(struct m0_parity_math *math,
                              struct sns_ir_node *node, uint32_t *failed_arr,
                              uint32_t node_nr, uint32_t alive_nr)
{
        uint32_t i;
        uint32_t j;
        /* ID for the first alive block to go to a node. */
        uint32_t start_idx;
        uint32_t total_failures;
        uint32_t alive_bpn;
        int      ret;

        total_failures = math->pmi_data_count + math->pmi_parity_count -
                alive_nr;
        alive_bpn = alive_nr/node_nr;
        for (i = 0, start_idx = 0; i < node_nr; ++i) {
                if (i != 0)
                        node[i].sin_alive_nr = alive_bpn;
                else
                        node[i].sin_alive_nr = alive_bpn + alive_nr % node_nr;
                ret = m0_sns_ir_init(math, node[i].sin_alive_nr, &node[i].sin_ir);
                M0_UT_ASSERT(ret == 0);
                M0_ALLOC_ARR(node[i].sin_alive, node[i].sin_alive_nr);
                M0_UT_ASSERT(node[i].sin_alive != NULL);
                /* Each node has as many accumulator buffers as
                 * total failures. */
                bufvec_initialize(&node[i].sin_recov_arr, total_failures,
                                  NUM_SEG, SEG_SIZE);
                /* A bitmap is associated with every accumulator buffer to
                 * indicate indices of blocks that have contributed to the
                 * given buffer. */
                M0_ALLOC_ARR(node[i].sin_bitmap, total_failures);
                M0_UT_ASSERT(node[i].sin_bitmap != NULL);

                for (j = 0; j < total_failures; ++j) {
                        ret = m0_bitmap_init(&node[i].sin_bitmap[j],
                                             math->pmi_data_count +
                                             math->pmi_parity_count);
                        M0_UT_ASSERT(ret == 0);
                }
                failure_register(&node[i].sin_ir, node[i].sin_recov_arr,
                                 failed_arr, total_failures);
                alive_arrays_fill(&node[i].sin_ir, node[i].sin_alive,
                                      start_idx, node[i].sin_alive_nr);
                ret = m0_sns_ir_mat_compute(&node[i].sin_ir);
                M0_UT_ASSERT(ret == 0);
                start_idx += node[i].sin_alive_nr;
        }
}

static void failure_register(struct m0_sns_ir *ir, struct m0_bufvec *recov_arr,
                             uint32_t *failed_arr, uint32_t total_failures)
{
        uint32_t j;
        int      ret;

        for (j = 0; j < total_failures; ++j) {
                ret = m0_sns_ir_failure_register(&recov_arr[j],
                                                 failed_arr[j],
                                                 ir);
                M0_UT_ASSERT(ir->si_blocks[failed_arr[j]].sib_status ==
                             M0_SI_BLOCK_FAILED);
                M0_UT_ASSERT(ret == 0);
        }
}

static void alive_arrays_fill(struct m0_sns_ir *ir, uint32_t *alive_blocks,
                              uint32_t start_idx, uint32_t count)
{
        uint32_t i = 0;
        uint32_t j = 0;

        /* get the start_index^{th} alive block. */
        while (i < start_idx) {
                if (ir->si_blocks[j].sib_status == M0_SI_BLOCK_ALIVE)
                        ++i;
                ++j;
        }
        /* collect next 'count' number of alive blocks. */
        for (i = 0; j < ir->si_data_nr + ir->si_parity_nr && i < count; ++j) {
                if (ir->si_blocks[j].sib_status == M0_SI_BLOCK_ALIVE) {
                        alive_blocks[i] = ir->si_blocks[j].sib_idx;
                        ++i;
                }
        }
}

static void sns_ir_nodes_recover(struct sns_ir_node *node, uint32_t node_nr,
                                 struct m0_bufvec *x, struct m0_bufvec *p)
{
        uint32_t         i;
        uint32_t         j;
        uint32_t         k;
        uint32_t         alive_idx;
        uint32_t         total_failures;
        struct m0_bitmap alive_bitmap;
        int              ret;
        struct m0_sns_ir ir;

        ret = m0_bitmap_init(&alive_bitmap,
                             node[0].sin_ir.si_data_nr +
                             node[0].sin_ir.si_parity_nr);
        M0_UT_ASSERT(ret == 0);
        total_failures = block_nr(&node[0].sin_ir) -
                node[0].sin_ir.si_alive_nr;
        for (i = 1; i < node_nr; ++i) {
                ir = node[i].sin_ir;
                for (j = 0; j < node[i].sin_alive_nr; ++j) {
                        m0_bitmap_set(&alive_bitmap, node[i].sin_alive[j],
                                      true);
                        alive_idx = node[i].sin_alive[j];
                        if (alive_idx < ir.si_data_nr) {
                                ret = m0_sns_ir_recover(&node[i].sin_ir,
                                                        &x[alive_idx],
                                                        &alive_bitmap, 0,
                                                        M0_SI_BLOCK_LOCAL);
                                M0_UT_ASSERT(ret == 0);
                        }
                        else if (alive_idx >= ir.si_data_nr &&
                                 alive_idx < ir.si_data_nr + ir.si_parity_nr) {
                                ret = m0_sns_ir_recover(&node[i].sin_ir,
                                                        &p[alive_idx -
                                                        ir.si_data_nr],
                                                        &alive_bitmap, 0,
                                                        M0_SI_BLOCK_LOCAL);
                                M0_UT_ASSERT(ret == 0);
                        }
                        for (k = 0; k < total_failures; ++k) {
                                m0_bitmap_set(&node[i].sin_bitmap[k],
                                              node[i].sin_alive[j], true);
                        }
                        m0_bitmap_set(&alive_bitmap, node[i].sin_alive[j],
                                      false);
                }
        }
        m0_bitmap_fini(&alive_bitmap);
}

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)
{
        uint32_t         i;
        uint32_t         j;
        uint32_t         k;
        uint32_t         total_failures;
        struct m0_bitmap alive_bitmap;
        uint32_t         alive_idx;
        struct m0_sns_ir ir;
        int              ret;

        total_failures = block_nr(&node[0].sin_ir) - node[0].sin_ir.si_alive_nr;
        ir = node[0].sin_ir;
        ret = m0_bitmap_init(&alive_bitmap,
                             node[0].sin_ir.si_data_nr +
                             node[0].sin_ir.si_parity_nr);
        M0_UT_ASSERT(ret == 0);

        /* Add remote blocks */
        for (i = 1; i < node_nr - 2; ++i) {
                for (k = 0; k < total_failures; ++k) {
                        ret = m0_sns_ir_recover(&node[0].sin_ir,
                                                &node[i].sin_recov_arr[k],
                                                &node[i].sin_bitmap[k],
                                                failed_arr[k], M0_SI_BLOCK_REMOTE);
                        M0_UT_ASSERT(ret == 0);
                }
        }

        /* Add local blocks */
        for (j = 0; j < node[0].sin_alive_nr; ++j) {
                        m0_bitmap_set(&alive_bitmap, node[0].sin_alive[j],
                                      true);
                        alive_idx = node[0].sin_alive[j];
                        if (alive_idx < ir.si_data_nr) {
                                ret = m0_sns_ir_recover(&node[0].sin_ir,
                                                        &x[alive_idx],
                                                        &alive_bitmap, 0,
                                                        M0_SI_BLOCK_LOCAL);
                                M0_UT_ASSERT(ret == 0);
                        }
                        else if (alive_idx >= ir.si_data_nr &&
                                 alive_idx < ir.si_data_nr + ir.si_parity_nr) {
                                ret = m0_sns_ir_recover(&node[0].sin_ir,
                                                        &p[alive_idx -
                                                        ir.si_data_nr],
                                                        &alive_bitmap, 0,
                                                        M0_SI_BLOCK_LOCAL);
                                M0_UT_ASSERT(ret == 0);
                        }
                        for (k = 0; k < total_failures; ++k) {
                                m0_bitmap_set(&node[0].sin_bitmap[k],
                                              node[0].sin_alive[j], true);
                        }
                        m0_bitmap_set(&alive_bitmap, node[0].sin_alive[j],
                                      false);
        }
        /* Add remote blocks */
        for (i = node_nr - 2; i < node_nr; ++i) {
                for (k = 0; k < total_failures; ++k) {
                        ret = m0_sns_ir_recover(&node[0].sin_ir,
                                                &node[i].sin_recov_arr[k],
                                                &node[i].sin_bitmap[k],
                                                failed_arr[k], M0_SI_BLOCK_REMOTE);
                        M0_UT_ASSERT(ret == 0);
                }
        }
        m0_bitmap_fini(&alive_bitmap);
}

static void sns_ir_nodes_compare(struct sns_ir_node *node, struct m0_bufvec *x,
                                 struct m0_bufvec *p)
{
        uint32_t         i;
        struct m0_sns_ir ir;

        ir = node[0].sin_ir;
        for (i = 0; i < ir.si_data_nr; ++i) {
                if (node[0].sin_ir.si_blocks[i].sib_status ==
                    M0_SI_BLOCK_FAILED) {
                        M0_UT_ASSERT(bufvec_eq(node[0].sin_ir.si_blocks[i].
                                               sib_addr, &x[i]));
                }
        }
        for (; i < ir.si_data_nr + ir.si_parity_nr; ++i) {
                if (node[0].sin_ir.si_blocks[i].sib_status ==
                    M0_SI_BLOCK_FAILED) {
                        M0_UT_ASSERT(bufvec_eq(node[0].sin_ir.si_blocks[i].
                                               sib_addr, &p[i -
                                                            ir.si_data_nr]));
                }
        }
}

static void sns_ir_nodes_fini(struct sns_ir_node *node, uint32_t node_nr,
                              uint32_t total_failures)
{
        uint32_t i;
        uint32_t j;

        for (i = 0; i < node_nr; ++i) {
                m0_sns_ir_fini(&node[i].sin_ir);
                bufvec_fini(node[i].sin_recov_arr, total_failures);
                for (j = 0; j < total_failures; ++j)
                        m0_bitmap_fini(&node[i].sin_bitmap[j]);
                m0_free(node[i].sin_bitmap);
                m0_free(node[i].sin_alive);
        }
}

static void test_invalid_input(void)
{
        uint32_t              i;
        uint32_t              parity_cnt = 2;
        uint32_t              total_failures;
        uint32_t             *failed_arr;
        int                   ret;
        struct m0_bufvec      recov_arr;
        struct m0_parity_math math;
        struct m0_sns_ir      ir;

        ret = m0_parity_math_init(&math, DATA_UNIT_COUNT, parity_cnt);
        M0_UT_ASSERT(ret == 0);
        total_failures = math.pmi_parity_count + 1;
        failed_arr = failure_setup(&math, total_failures, MIXED_FAILURE);
        ret = m0_sns_ir_init(&math, 0, &ir);
        for (i = 0; i < total_failures - 1; ++i) {
                ret = m0_sns_ir_failure_register(&recov_arr,
                                                 failed_arr[i],
                                                 &ir);
                M0_UT_ASSERT(ret == 0);
        }
        ret = m0_sns_ir_failure_register(&recov_arr,
                                         failed_arr[i],
                                         &ir);
        M0_UT_ASSERT(ret == -ERANGE);
        m0_free(failed_arr);
        m0_sns_ir_fini(&ir);
        m0_parity_math_fini(&math);
}

static void bufvec_initialize(struct m0_bufvec **bvec, uint32_t count,
                              uint32_t num_seg, uint32_t seg_size)
{
        uint32_t i;
        int      ret;

        M0_ALLOC_ARR(*bvec, count);
        M0_UT_ASSERT(*bvec != NULL);

        for (i = 0; i < count; ++i) {
                ret = m0_bufvec_alloc(&bvec[0][i], num_seg, seg_size);
                M0_UT_ASSERT(ret == 0);
        }
}

static void bufvec_fini(struct m0_bufvec *bvec, uint32_t count)
{
        uint32_t i;

        for (i = 0; i < count; ++i) {
                m0_bufvec_free(&bvec[i]);
        }
        m0_free(bvec);
}

static void bufvec_fill(struct m0_bufvec *x)
{

        uint8_t                *x_buf;
        struct m0_bufvec_cursor x_cursor;
        m0_bcount_t             step;
        uint32_t                i;

        m0_bufvec_cursor_init(&x_cursor, x);
        do {
                x_buf  = m0_bufvec_cursor_addr(&x_cursor);
                for (i = 0; i < x->ov_vec.v_count[0]; ++i)
                        x_buf[i] = (uint8_t)m0_rnd64(&seed);
                step = m0_bufvec_cursor_step(&x_cursor);
        } while (!m0_bufvec_cursor_move(&x_cursor, step));
}

static void bufvec_buf(struct m0_bufvec *bvec, struct m0_buf *buf,
                       uint32_t count, bool dir)
{
        struct m0_bufvec_cursor cursor;
        m0_bcount_t             step;
        uint32_t                i;
        uint32_t                j;
        uint8_t                *buf_data;

        for (j = 0, i = 0; j < count; ++j, i = 0) {
                m0_bufvec_cursor_init(&cursor, &bvec[j]);
                buf_data = (uint8_t *)buf[j].b_addr;
                do {
                        if (dir)
                                memcpy(&buf_data[i * bvec[j].ov_vec.v_count[i]],
                                       m0_bufvec_cursor_addr(&cursor),
                                       bvec[j].ov_vec.v_count[i]);
                        else
                                memcpy(m0_bufvec_cursor_addr(&cursor),
                                       &buf_data[i * bvec[j].ov_vec.v_count[i]],
                                       bvec[j].ov_vec.v_count[i]);
                        ++i;
                        step = m0_bufvec_cursor_step(&cursor);
                } while (!m0_bufvec_cursor_move(&cursor, step));
        }
}

static void _buf_free(struct m0_buf *buf)
{
        m0_free_aligned(buf->b_addr, buf->b_nob, 12);
        buf->b_nob = 0;
}

static void buf_initialize(struct m0_buf *buf, uint32_t size, uint32_t len)
{
        uint32_t j;
        uint8_t *arr;

        for (j = 0; j < size; ++j) {
                M0_ALLOC_ARR_ALIGNED(arr, len, 12);
                M0_UT_ASSERT(arr != NULL);
                m0_buf_init(&buf[j], arr, len);
        }
}

static void buf_free(struct m0_buf *buf, uint32_t count)
{
        uint32_t i;

        for (i = 0; i < count; ++i) {
                _buf_free(&buf[i]);
        }
}

static bool bufvec_eq(struct m0_bufvec *bvec_1, struct m0_bufvec *bvec_2)
{
        struct m0_bufvec_cursor bvec_1_cursor;
        struct m0_bufvec_cursor bvec_2_cursor;
        m0_bcount_t             step;
        int                     ret;

        M0_UT_ASSERT(bvec_1->ov_vec.v_nr == bvec_2->ov_vec.v_nr);
        m0_bufvec_cursor_init(&bvec_1_cursor, bvec_1);
        m0_bufvec_cursor_init(&bvec_2_cursor, bvec_2);
        do {
                ret = memcmp(m0_bufvec_cursor_addr(&bvec_1_cursor),
                             m0_bufvec_cursor_addr(&bvec_2_cursor),
                             bvec_1->ov_vec.v_count[0]);
                step = m0_bufvec_cursor_step(&bvec_1_cursor);
        } while (ret == 0 && !m0_bufvec_cursor_move(&bvec_1_cursor, step) &&
                 !m0_bufvec_cursor_move(&bvec_2_cursor, step));
        return ret == 0;
}

static inline uint32_t block_nr(const struct m0_sns_ir *ir)
{
        return ir->si_data_nr + ir->si_parity_nr;
}

static void test_init(void)
{
        M0_SET_ARR0(expected);
        M0_SET_ARR0(data);
        M0_SET_ARR0(parity);
        M0_SET_ARR0(fail);
        duc = DATA_UNIT_COUNT_MAX;
        puc = PARITY_UNIT_COUNT_MAX;
        fuc = PARITY_UNIT_COUNT_MAX;
        UNIT_BUFF_SIZE = 256;
        fail_index_xor = 0;
        seed = 42;
}

#define _TESTS                                                                  \
        { "reed_solomon_recover_with_fail_vec", test_rs_fv_recover },           \
        { "reed_solomon_recover_with_fail_vec_rand", test_rs_fv_rand_recover }, \
        { "xor_recover_with_fail_vec", test_xor_fv_recover },                   \
        { "xor_recover_with_fail_index", test_xor_fail_idx_recover },           \
        { "buffer_xor", test_buffer_xor },                                      \
        { "parity_math_diff_xor", test_parity_math_diff_xor },                  \
        { "parity_math_diff_rs", test_parity_math_diff_rs },                    \
        { "incr_recov_rs", test_incr_recov_rs },                                \
        { NULL, NULL }

struct m0_ut_suite parity_math_ut = {
        .ts_name = "parity_math-ut",
        .ts_init = NULL,
        .ts_fini = NULL,
        .ts_tests = { _TESTS }
};
M0_EXPORTED(parity_math_ut);

struct m0_ut_suite parity_math_ssse3_ut = {
        .ts_name = "parity_math_ssse3-ut",
        .ts_tests = { _TESTS }
};
M0_EXPORTED(parity_math_ssse3_ut);

#undef _TESTS

static int ub_init(const char *opts M0_UNUSED)
{
        return 0;
}

void parity_math_tb(void)
{
        int ret = 0;
        uint32_t i = 0;
        struct m0_parity_math *math;
        uint32_t data_count = 0;
        uint32_t parity_count = 0;
        uint32_t buff_size = 0;
        uint32_t fail_count = 0;
        struct m0_buf data_buf[DATA_UNIT_COUNT_MAX];
        struct m0_buf parity_buf[DATA_UNIT_COUNT_MAX];
        struct m0_buf fail_buf;

        M0_ALLOC_PTR(math);
        M0_UT_ASSERT(math != NULL);

        config_generate(&data_count, &parity_count, &buff_size,
                        M0_PARITY_CAL_ALGO_REED_SOLOMON);
        {
                fail_count = data_count + parity_count;

                ret = m0_parity_math_init(math, data_count, parity_count);
                M0_ASSERT(ret == 0);

                for (i = 0; i < data_count; ++i) {
                        m0_buf_init(&data_buf  [i], data  [i], buff_size);
                        m0_buf_init(&parity_buf[i], parity[i], buff_size);
                }

                m0_buf_init(&fail_buf, fail, buff_size);

                m0_parity_math_calculate(math, data_buf, parity_buf);

                unit_spoil(buff_size, fail_count, data_count);

                ret = m0_parity_math_recover(math, data_buf, parity_buf,
                                             &fail_buf, 0);
                M0_UT_ASSERT(ret == 0);

                m0_parity_math_fini(math);
        }

        m0_free(math);
}

static void ub_small_4K(int iter)
{
        UNIT_BUFF_SIZE = KB(4);
        duc = 10;
        puc = 5;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_medium_4K(int iter)
{
        UNIT_BUFF_SIZE = KB(4);
        duc = 20;
        puc = 6;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_large_4K(int iter)
{
        UNIT_BUFF_SIZE = KB(4);
        duc = 30;
        puc = 12;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_small_1M(int iter)
{
        UNIT_BUFF_SIZE = MB(1);
        duc = 3;
        puc = 2;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_medium_1M(int iter)
{
        UNIT_BUFF_SIZE = MB(1);
        duc = 6;
        puc = 3;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_large_1M(int iter)
{
        UNIT_BUFF_SIZE = MB(1);
        duc = 8;
        puc = 4;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_small_32K(int iter)
{
        UNIT_BUFF_SIZE = KB(32);
        duc = 10;
        puc = 5;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_medium_32K(int iter)
{
        UNIT_BUFF_SIZE = KB(32);
        duc = 20;
        puc = 6;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_large_32K(int iter)
{
        UNIT_BUFF_SIZE = KB(32);
        duc = 30;
        puc = 12;
        fuc = duc+puc;
        parity_math_tb();
}
static void ub_small_4_2_4K(int iter)
{
        UNIT_BUFF_SIZE = KB(4);
        duc = 4;
        puc = 2;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_small_4_2_256K(int iter)
{
        UNIT_BUFF_SIZE = KB(256);
        duc = 4;
        puc = 2;
        fuc = duc+puc;
        parity_math_tb();
}

static void ub_small_4_2_1M(int iter)
{
        UNIT_BUFF_SIZE = MB(1);
        duc = 4;
        puc = 2;
        fuc = duc+puc;
        parity_math_tb();
}

enum { UB_ITER = 100 };

struct m0_ub_set m0_parity_math_ub = {
        .us_name = "parity-math-ub",
        .us_init = ub_init,
        .us_fini = NULL,
        .us_run  = {
                { .ub_name  = "s 10/05/  4K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_small_4K,
                  .ub_block_size = KB(4),
                  .ub_blocks_per_op = 15 },

                { .ub_name  = "m 20/06/  4K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_medium_4K,
                  .ub_block_size = KB(4),
                  .ub_blocks_per_op = 26 },

                { .ub_name  = "l 30/12/  4K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_large_4K,
                  .ub_block_size = KB(4),
                  .ub_blocks_per_op = 42 },

                { .ub_name  = "s 10/05/ 32K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_small_32K,
                  .ub_block_size = KB(32),
                  .ub_blocks_per_op = 15 },

                { .ub_name  = "m 20/06/ 32K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_medium_32K,
                  .ub_block_size = KB(32),
                  .ub_blocks_per_op = 26 },

                { .ub_name  = "l 30/12/ 32K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_large_32K,
                  .ub_block_size = KB(32),
                  .ub_blocks_per_op = 42 },

                { .ub_name  = "s 03/02/  1M",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_small_1M,
                  .ub_block_size = MB(1),
                  .ub_blocks_per_op = 5 },

                { .ub_name  = "m 06/03/  1M",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_medium_1M,
                  .ub_block_size = MB(1),
                  .ub_blocks_per_op = 9 },

                { .ub_name  = "l 08/04/  1M",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_large_1M,
                  .ub_block_size = MB(1),
                  .ub_blocks_per_op = 12 },

                { .ub_name  = "s 04/02/  4K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_small_4_2_4K,
                  .ub_block_size = KB(4),
                  .ub_blocks_per_op = 6 },

                { .ub_name  = "m 04/02/256K",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_small_4_2_256K,
                  .ub_block_size = KB(256),
                  .ub_blocks_per_op = 6 },

                { .ub_name  = "l 04/02/  1M",
                  .ub_iter  = UB_ITER,
                  .ub_round = ub_small_4_2_1M,
                  .ub_block_size = MB(1),
                  .ub_blocks_per_op = 6 },

                { .ub_name = NULL}
        }
};

/*
 *  Local variables:
 *  c-indentation-style: "K&R"
 *  c-basic-offset: 8
 *  tab-width: 8
 *  fill-column: 80
 *  scroll-step: 1
 *  End:
 */