+++ /dev/null
-/*
- * Copyright (C) 2013 Andrea Mazzoleni
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- */
-
-#include "internal.h"
-#include "cpu.h"
-#include "combo.h"
-#include "memory.h"
-
-/**
- * Binomial coefficient of n over r.
- */
-static int ibc(int n, int r)
-{
- if (r == 0 || n == r)
- return 1;
- else
- return ibc(n - 1, r - 1) + ibc(n - 1, r);
-}
-
-/**
- * Power n ^ r;
- */
-static int ipow(int n, int r)
-{
- int v = 1;
-
- while (r) {
- v *= n;
- --r;
- }
- return v;
-}
-
-int raid_test_combo(void)
-{
- int r;
- int count;
- int p[RAID_PARITY_MAX];
-
- for (r = 1; r <= RAID_PARITY_MAX; ++r) {
- /* count combination (r of RAID_PARITY_MAX) elements */
- count = 0;
- combination_first(r, RAID_PARITY_MAX, p);
-
- do {
- ++count;
- } while (combination_next(r, RAID_PARITY_MAX, p));
-
- if (count != ibc(RAID_PARITY_MAX, r)) {
- /* LCOV_EXCL_START */
- return -1;
- /* LCOV_EXCL_STOP */
- }
- }
-
- for (r = 1; r <= RAID_PARITY_MAX; ++r) {
- /* count permutation (r of RAID_PARITY_MAX) elements */
- count = 0;
- permutation_first(r, RAID_PARITY_MAX, p);
-
- do {
- ++count;
- } while (permutation_next(r, RAID_PARITY_MAX, p));
-
- if (count != ipow(RAID_PARITY_MAX, r)) {
- /* LCOV_EXCL_START */
- return -1;
- /* LCOV_EXCL_STOP */
- }
- }
-
- return 0;
-}
-
-int raid_test_insert(void)
-{
- int p[RAID_PARITY_MAX];
- int r;
-
- for (r = 1; r <= RAID_PARITY_MAX; ++r) {
- permutation_first(r, RAID_PARITY_MAX, p);
- do {
- int i[RAID_PARITY_MAX];
- int j;
-
- /* insert in order */
- for (j = 0; j < r; ++j)
- raid_insert(j, i, p[j]);
-
- /* check order */
- for (j = 1; j < r; ++j) {
- if (i[j - 1] > i[j]) {
- /* LCOV_EXCL_START */
- return -1;
- /* LCOV_EXCL_STOP */
- }
- }
- } while (permutation_next(r, RAID_PARITY_MAX, p));
- }
-
- return 0;
-}
-
-int raid_test_sort(void)
-{
- int p[RAID_PARITY_MAX];
- int r;
-
- for (r = 1; r <= RAID_PARITY_MAX; ++r) {
- permutation_first(r, RAID_PARITY_MAX, p);
- do {
- int i[RAID_PARITY_MAX];
- int j;
-
- /* make a copy */
- for (j = 0; j < r; ++j)
- i[j] = p[j];
-
- raid_sort(r, i);
-
- /* check order */
- for (j = 1; j < r; ++j) {
- if (i[j - 1] > i[j]) {
- /* LCOV_EXCL_START */
- return -1;
- /* LCOV_EXCL_STOP */
- }
- }
- } while (permutation_next(r, RAID_PARITY_MAX, p));
- }
-
- return 0;
-}
-
-int raid_test_rec(int mode, int nd, size_t size)
-{
- void (*f[RAID_PARITY_MAX][4])(
- int nr, int *id, int *ip, int nd, size_t size, void **vbuf);
- void *v_alloc;
- void **v;
- void **data;
- void **parity;
- void **test;
- void *data_save[RAID_PARITY_MAX];
- void *parity_save[RAID_PARITY_MAX];
- void *waste;
- int nv;
- int id[RAID_PARITY_MAX];
- int ip[RAID_PARITY_MAX];
- int i;
- int j;
- int nr;
- int nf[RAID_PARITY_MAX];
- int np;
-
- raid_mode(mode);
- if (mode == RAID_MODE_CAUCHY)
- np = RAID_PARITY_MAX;
- else
- np = 3;
-
- nv = nd + np * 2 + 2;
-
- v = raid_malloc_vector(nd, nv, size, &v_alloc);
- if (!v) {
- /* LCOV_EXCL_START */
- return -1;
- /* LCOV_EXCL_STOP */
- }
-
- data = v;
- parity = v + nd;
- test = v + nd + np;
-
- for (i = 0; i < np; ++i)
- parity_save[i] = parity[i];
-
- memset(v[nv - 2], 0, size);
- raid_zero(v[nv - 2]);
-
- waste = v[nv - 1];
-
- /* fill with pseudo-random data with the arbitrary seed "1" */
- raid_mrand_vector(1, nd, size, v);
-
- /* setup recov functions */
- for (i = 0; i < np; ++i) {
- nf[i] = 0;
- if (i == 0) {
- f[i][nf[i]++] = raid_rec1_int8;
-#ifdef CONFIG_X86
-#ifdef CONFIG_SSSE3
- if (raid_cpu_has_ssse3())
- f[i][nf[i]++] = raid_rec1_ssse3;
-#endif
-#ifdef CONFIG_AVX2
- if (raid_cpu_has_avx2())
- f[i][nf[i]++] = raid_rec1_avx2;
-#endif
-#endif
- } else if (i == 1) {
- f[i][nf[i]++] = raid_rec2_int8;
-#ifdef CONFIG_X86
-#ifdef CONFIG_SSSE3
- if (raid_cpu_has_ssse3())
- f[i][nf[i]++] = raid_rec2_ssse3;
-#endif
-#ifdef CONFIG_AVX2
- if (raid_cpu_has_avx2())
- f[i][nf[i]++] = raid_rec2_avx2;
-#endif
-#endif
- } else {
- f[i][nf[i]++] = raid_recX_int8;
-#ifdef CONFIG_X86
-#ifdef CONFIG_SSSE3
- if (raid_cpu_has_ssse3())
- f[i][nf[i]++] = raid_recX_ssse3;
-#endif
-#ifdef CONFIG_AVX2
- if (raid_cpu_has_avx2())
- f[i][nf[i]++] = raid_recX_avx2;
-#endif
-#endif
- }
- }
-
- /* compute the parity */
- raid_gen_ref(nd, np, size, v);
-
- /* set all the parity to the waste v */
- for (i = 0; i < np; ++i)
- parity[i] = waste;
-
- /* all parity levels */
- for (nr = 1; nr <= np; ++nr) {
- /* all combinations (nr of nd) disks */
- combination_first(nr, nd, id);
- do {
- /* all combinations (nr of np) parities */
- combination_first(nr, np, ip);
- do {
- /* for each recover function */
- for (j = 0; j < nf[nr - 1]; ++j) {
- /* set */
- for (i = 0; i < nr; ++i) {
- /* remove the missing data */
- data_save[i] = data[id[i]];
- data[id[i]] = test[i];
- /* set the parity to use */
- parity[ip[i]] = parity_save[ip[i]];
- }
-
- /* recover */
- f[nr - 1][j](nr, id, ip, nd, size, v);
-
- /* check */
- for (i = 0; i < nr; ++i) {
- if (memcmp(test[i], data_save[i], size) != 0) {
- /* LCOV_EXCL_START */
- goto bail;
- /* LCOV_EXCL_STOP */
- }
- }
-
- /* restore */
- for (i = 0; i < nr; ++i) {
- /* restore the data */
- data[id[i]] = data_save[i];
- /* restore the parity */
- parity[ip[i]] = waste;
- }
- }
- } while (combination_next(nr, np, ip));
- } while (combination_next(nr, nd, id));
- }
-
- free(v_alloc);
- free(v);
- return 0;
-
-bail:
- /* LCOV_EXCL_START */
- free(v_alloc);
- free(v);
- return -1;
- /* LCOV_EXCL_STOP */
-}
-
-int raid_test_par(int mode, int nd, size_t size)
-{
- void (*f[64])(int nd, size_t size, void **vbuf);
- void *v_alloc;
- void **v;
- int nv;
- int i, j;
- int nf;
- int np;
-
- raid_mode(mode);
- if (mode == RAID_MODE_CAUCHY)
- np = RAID_PARITY_MAX;
- else
- np = 3;
-
- nv = nd + np * 2;
-
- v = raid_malloc_vector(nd, nv, size, &v_alloc);
- if (!v) {
- /* LCOV_EXCL_START */
- return -1;
- /* LCOV_EXCL_STOP */
- }
-
- /* check memory */
- if (raid_mtest_vector(nv, size, v) != 0) {
- /* LCOV_EXCL_START */
- goto bail;
- /* LCOV_EXCL_STOP */
- }
-
- /* fill with pseudo-random data with the arbitrary seed "2" */
- raid_mrand_vector(2, nv, size, v);
-
- /* compute the parity */
- raid_gen_ref(nd, np, size, v);
-
- /* copy in back buffers */
- for (i = 0; i < np; ++i)
- memcpy(v[nd + np + i], v[nd + i], size);
-
- /* load all the available functions */
- nf = 0;
-
- f[nf++] = raid_gen1_int32;
- f[nf++] = raid_gen1_int64;
- f[nf++] = raid_gen2_int32;
- f[nf++] = raid_gen2_int64;
-
-#ifdef CONFIG_X86
-#ifdef CONFIG_SSE2
- if (raid_cpu_has_sse2()) {
- f[nf++] = raid_gen1_sse2;
- f[nf++] = raid_gen2_sse2;
-#ifdef CONFIG_X86_64
- f[nf++] = raid_gen2_sse2ext;
-#endif
- }
-#endif
-
-#ifdef CONFIG_AVX2
- if (raid_cpu_has_avx2()) {
- f[nf++] = raid_gen1_avx2;
- f[nf++] = raid_gen2_avx2;
- }
-#endif
-#endif /* CONFIG_X86 */
-
- if (mode == RAID_MODE_CAUCHY) {
- f[nf++] = raid_gen3_int8;
- f[nf++] = raid_gen4_int8;
- f[nf++] = raid_gen5_int8;
- f[nf++] = raid_gen6_int8;
-
-#ifdef CONFIG_X86
-#ifdef CONFIG_SSSE3
- if (raid_cpu_has_ssse3()) {
- f[nf++] = raid_gen3_ssse3;
- f[nf++] = raid_gen4_ssse3;
- f[nf++] = raid_gen5_ssse3;
- f[nf++] = raid_gen6_ssse3;
-#ifdef CONFIG_X86_64
- f[nf++] = raid_gen3_ssse3ext;
- f[nf++] = raid_gen4_ssse3ext;
- f[nf++] = raid_gen5_ssse3ext;
- f[nf++] = raid_gen6_ssse3ext;
-#endif
- }
-#endif
-
-#ifdef CONFIG_AVX2
-#ifdef CONFIG_X86_64
- if (raid_cpu_has_avx2()) {
- f[nf++] = raid_gen3_avx2ext;
- f[nf++] = raid_gen4_avx2ext;
- f[nf++] = raid_gen5_avx2ext;
- f[nf++] = raid_gen6_avx2ext;
- }
-#endif
-#endif
-#endif /* CONFIG_X86 */
- } else {
- f[nf++] = raid_genz_int32;
- f[nf++] = raid_genz_int64;
-
-#ifdef CONFIG_X86
-#ifdef CONFIG_SSE2
- if (raid_cpu_has_sse2()) {
- f[nf++] = raid_genz_sse2;
-#ifdef CONFIG_X86_64
- f[nf++] = raid_genz_sse2ext;
-#endif
- }
-#endif
-
-#ifdef CONFIG_AVX2
-#ifdef CONFIG_X86_64
- if (raid_cpu_has_avx2())
- f[nf++] = raid_genz_avx2ext;
-#endif
-#endif
-#endif /* CONFIG_X86 */
- }
-
- /* check all the functions */
- for (j = 0; j < nf; ++j) {
- /* compute parity */
- f[j](nd, size, v);
-
- /* check it */
- for (i = 0; i < np; ++i) {
- if (memcmp(v[nd + np + i], v[nd + i], size) != 0) {
- /* LCOV_EXCL_START */
- goto bail;
- /* LCOV_EXCL_STOP */
- }
- }
- }
-
- free(v_alloc);
- free(v);
- return 0;
-
-bail:
- /* LCOV_EXCL_START */
- free(v_alloc);
- free(v);
- return -1;
- /* LCOV_EXCL_STOP */
-}
-
projects / bcachefs-tools-debian / blobdiff