ceph/src/isa-l/erasure_code/gf_vect_dot_prod_base_test.c

   1 /**********************************************************************
   2   Copyright(c) 2011-2015 Intel Corporation All rights reserved.
   3
   4   Redistribution and use in source and binary forms, with or without
   5   modification, are permitted provided that the following conditions
   6   are met:
   7     * Redistributions of source code must retain the above copyright
   8       notice, this list of conditions and the following disclaimer.
   9     * Redistributions in binary form must reproduce the above copyright
  10       notice, this list of conditions and the following disclaimer in
  11       the documentation and/or other materials provided with the
  12       distribution.
  13     * Neither the name of Intel Corporation nor the names of its
  14       contributors may be used to endorse or promote products derived
  15       from this software without specific prior written permission.
  16
  17   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28 **********************************************************************/
  29
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>             // for memset, memcmp
  33 #include "erasure_code.h"
  34 #include "types.h"
  35
  36 #define TEST_LEN 8192
  37 #define TEST_SIZE (TEST_LEN/2)
  38
  39 #ifndef TEST_SOURCES
  40 # define TEST_SOURCES  250
  41 #endif
  42 #ifndef RANDOMS
  43 # define RANDOMS 20
  44 #endif
  45
  46 #define MMAX TEST_SOURCES
  47 #define KMAX TEST_SOURCES
  48
  49 typedef unsigned char u8;
  50
  51 void dump(unsigned char *buf, int len)
  52 {
  53         int i;
  54         for (i = 0; i < len;) {
  55                 printf(" %2x", 0xff & buf[i++]);
  56                 if (i % 32 == 0)
  57                         printf("\n");
  58         }
  59         printf("\n");
  60 }
  61
  62 void dump_matrix(unsigned char **s, int k, int m)
  63 {
  64         int i, j;
  65         for (i = 0; i < k; i++) {
  66                 for (j = 0; j < m; j++) {
  67                         printf(" %2x", s[i][j]);
  68                 }
  69                 printf("\n");
  70         }
  71         printf("\n");
  72 }
  73
  74 void dump_u8xu8(unsigned char *s, int k, int m)
  75 {
  76         int i, j;
  77         for (i = 0; i < k; i++) {
  78                 for (j = 0; j < m; j++) {
  79                         printf(" %2x", 0xff & s[j + (i * m)]);
  80                 }
  81                 printf("\n");
  82         }
  83         printf("\n");
  84 }
  85
  86 int main(int argc, char *argv[])
  87 {
  88         int i, j, rtest, m, k, nerrs, r, err;
  89         void *buf;
  90         u8 g[TEST_SOURCES], g_tbls[TEST_SOURCES * 32], src_in_err[TEST_SOURCES];
  91         u8 *dest, *dest_ref, *temp_buff, *buffs[TEST_SOURCES];
  92         u8 a[MMAX * KMAX], b[MMAX * KMAX], d[MMAX * KMAX];
  93         u8 src_err_list[TEST_SOURCES], *recov[TEST_SOURCES];
  94
  95         printf("gf_vect_dot_prod_base: %dx%d ", TEST_SOURCES, TEST_LEN);
  96
  97         // Allocate the arrays
  98         for (i = 0; i < TEST_SOURCES; i++) {
  99                 if (posix_memalign(&buf, 64, TEST_LEN)) {
 100                         printf("alloc error: Fail");
 101                         return -1;
 102                 }
 103                 buffs[i] = buf;
 104         }
 105
 106         if (posix_memalign(&buf, 64, TEST_LEN)) {
 107                 printf("alloc error: Fail");
 108                 return -1;
 109         }
 110         dest = buf;
 111
 112         if (posix_memalign(&buf, 64, TEST_LEN)) {
 113                 printf("alloc error: Fail");
 114                 return -1;
 115         }
 116         dest_ref = buf;
 117
 118         if (posix_memalign(&buf, 64, TEST_LEN)) {
 119                 printf("alloc error: Fail");
 120                 return -1;
 121         }
 122         temp_buff = buf;
 123
 124         // Init
 125         for (i = 0; i < TEST_SOURCES; i++)
 126                 memset(buffs[i], 0, TEST_LEN);
 127
 128         memset(dest, 0, TEST_LEN);
 129         memset(temp_buff, 0, TEST_LEN);
 130         memset(dest_ref, 0, TEST_LEN);
 131         memset(g, 0, TEST_SOURCES);
 132
 133         // Test erasure code using gf_vect_dot_prod
 134         // Pick a first test
 135         m = 9;
 136         k = 5;
 137         if (m > MMAX || k > KMAX)
 138                 return -1;
 139
 140         gf_gen_cauchy1_matrix(a, m, k);
 141
 142         // Make random data
 143         for (i = 0; i < k; i++)
 144                 for (j = 0; j < TEST_LEN; j++)
 145                         buffs[i][j] = rand();
 146
 147         // Make parity vects
 148         for (i = k; i < m; i++) {
 149                 for (j = 0; j < k; j++)
 150                         gf_vect_mul_init(a[k * i + j], &g_tbls[j * 32]);
 151
 152                 gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, buffs, buffs[i]);
 153         }
 154
 155         // Random buffers in erasure
 156         memset(src_in_err, 0, TEST_SOURCES);
 157         for (i = 0, nerrs = 0; i < k && nerrs < m - k; i++) {
 158                 err = 1 & rand();
 159                 src_in_err[i] = err;
 160                 if (err)
 161                         src_err_list[nerrs++] = i;
 162         }
 163
 164         // construct b by removing error rows
 165         for (i = 0, r = 0; i < k; i++, r++) {
 166                 while (src_in_err[r]) {
 167                         r++;
 168                         continue;
 169                 }
 170                 for (j = 0; j < k; j++)
 171                         b[k * i + j] = a[k * r + j];
 172         }
 173
 174         if (gf_invert_matrix((u8 *) b, (u8 *) d, k) < 0)
 175                 printf("BAD MATRIX\n");
 176
 177         for (i = 0, r = 0; i < k; i++, r++) {
 178                 while (src_in_err[r]) {
 179                         r++;
 180                         continue;
 181                 }
 182                 recov[i] = buffs[r];
 183         }
 184
 185         // Recover data
 186         for (i = 0; i < nerrs; i++) {
 187                 for (j = 0; j < k; j++)
 188                         gf_vect_mul_init(d[k * src_err_list[i] + j], &g_tbls[j * 32]);
 189
 190                 gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, recov, temp_buff);
 191
 192                 if (0 != memcmp(temp_buff, buffs[src_err_list[i]], TEST_LEN)) {
 193                         printf("Fail error recovery (%d, %d, %d)\n", m, k, nerrs);
 194                         printf("recov %d:", src_err_list[i]);
 195                         dump(temp_buff, 25);
 196                         printf("orig   :");
 197                         dump(buffs[src_err_list[i]], 25);
 198                         return -1;
 199                 }
 200         }
 201
 202         // Do more random tests
 203
 204         for (rtest = 0; rtest < RANDOMS; rtest++) {
 205                 while ((m = (rand() % MMAX)) < 2) ;
 206                 while ((k = (rand() % KMAX)) >= m || k < 1) ;
 207
 208                 if (m > MMAX || k > KMAX)
 209                         continue;
 210
 211                 gf_gen_cauchy1_matrix(a, m, k);
 212
 213                 // Make random data
 214                 for (i = 0; i < k; i++)
 215                         for (j = 0; j < TEST_LEN; j++)
 216                                 buffs[i][j] = rand();
 217
 218                 // Make parity vects
 219                 for (i = k; i < m; i++) {
 220                         for (j = 0; j < k; j++)
 221                                 gf_vect_mul_init(a[k * i + j], &g_tbls[j * 32]);
 222
 223                         gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, buffs, buffs[i]);
 224                 }
 225
 226                 // Random errors
 227                 memset(src_in_err, 0, TEST_SOURCES);
 228                 for (i = 0, nerrs = 0; i < k && nerrs < m - k; i++) {
 229                         err = 1 & rand();
 230                         src_in_err[i] = err;
 231                         if (err)
 232                                 src_err_list[nerrs++] = i;
 233                 }
 234                 if (nerrs == 0) {       // should have at least one error
 235                         while ((err = (rand() % KMAX)) >= k) ;
 236                         src_err_list[nerrs++] = err;
 237                         src_in_err[err] = 1;
 238                 }
 239                 // construct b by removing error rows
 240                 for (i = 0, r = 0; i < k; i++, r++) {
 241                         while (src_in_err[r]) {
 242                                 r++;
 243                                 continue;
 244                         }
 245                         for (j = 0; j < k; j++)
 246                                 b[k * i + j] = a[k * r + j];
 247                 }
 248
 249                 if (gf_invert_matrix((u8 *) b, (u8 *) d, k) < 0)
 250                         printf("BAD MATRIX\n");
 251
 252                 for (i = 0, r = 0; i < k; i++, r++) {
 253                         while (src_in_err[r]) {
 254                                 r++;
 255                                 continue;
 256                         }
 257                         recov[i] = buffs[r];
 258                 }
 259
 260                 // Recover data
 261                 for (i = 0; i < nerrs; i++) {
 262                         for (j = 0; j < k; j++)
 263                                 gf_vect_mul_init(d[k * src_err_list[i] + j], &g_tbls[j * 32]);
 264
 265                         gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, recov, temp_buff);
 266
 267                         if (0 != memcmp(temp_buff, buffs[src_err_list[i]], TEST_LEN)) {
 268                                 printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs);
 269                                 printf(" - erase list = ");
 270                                 for (i = 0; i < nerrs; i++)
 271                                         printf(" %d", src_err_list[i]);
 272                                 printf("\na:\n");
 273                                 dump_u8xu8((u8 *) a, m, k);
 274                                 printf("inv b:\n");
 275                                 dump_u8xu8((u8 *) d, k, k);
 276                                 printf("orig data:\n");
 277                                 dump_matrix(buffs, m, 25);
 278                                 printf("orig   :");
 279                                 dump(buffs[src_err_list[i]], 25);
 280                                 printf("recov %d:", src_err_list[i]);
 281                                 dump(temp_buff, 25);
 282                                 return -1;
 283                         }
 284                 }
 285                 putchar('.');
 286         }
 287
 288         printf("done all: Pass\n");
 289         return 0;
 290 }