ceph/src/isa-l/examples/ec/ec_simple_example.c

   1 /**********************************************************************
   2   Copyright(c) 2011-2018 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>
  33 #include <getopt.h>
  34 #include "erasure_code.h"       // use <isa-l.h> instead when linking against installed
  35
  36 #define MMAX 255
  37 #define KMAX 255
  38
  39 typedef unsigned char u8;
  40
  41 int usage(void)
  42 {
  43         fprintf(stderr,
  44                 "Usage: ec_simple_example [options]\n"
  45                 "  -h        Help\n"
  46                 "  -k <val>  Number of source fragments\n"
  47                 "  -p <val>  Number of parity fragments\n"
  48                 "  -l <val>  Length of fragments\n"
  49                 "  -e <val>  Simulate erasure on frag index val. Zero based. Can be repeated.\n"
  50                 "  -r <seed> Pick random (k, p) with seed\n");
  51         exit(0);
  52 }
  53
  54 static int gf_gen_decode_matrix_simple(u8 * encode_matrix,
  55                                        u8 * decode_matrix,
  56                                        u8 * invert_matrix,
  57                                        u8 * temp_matrix,
  58                                        u8 * decode_index,
  59                                        u8 * frag_err_list, int nerrs, int k, int m);
  60
  61 int main(int argc, char *argv[])
  62 {
  63         int i, j, m, c, e, ret;
  64         int k = 10, p = 4, len = 8 * 1024;      // Default params
  65         int nerrs = 0;
  66
  67         // Fragment buffer pointers
  68         u8 *frag_ptrs[MMAX];
  69         u8 *recover_srcs[KMAX];
  70         u8 *recover_outp[KMAX];
  71         u8 frag_err_list[MMAX];
  72
  73         // Coefficient matrices
  74         u8 *encode_matrix, *decode_matrix;
  75         u8 *invert_matrix, *temp_matrix;
  76         u8 *g_tbls;
  77         u8 decode_index[MMAX];
  78
  79         if (argc == 1)
  80                 for (i = 0; i < p; i++)
  81                         frag_err_list[nerrs++] = rand() % (k + p);
  82
  83         while ((c = getopt(argc, argv, "k:p:l:e:r:h")) != -1) {
  84                 switch (c) {
  85                 case 'k':
  86                         k = atoi(optarg);
  87                         break;
  88                 case 'p':
  89                         p = atoi(optarg);
  90                         break;
  91                 case 'l':
  92                         len = atoi(optarg);
  93                         if (len < 0)
  94                                 usage();
  95                         break;
  96                 case 'e':
  97                         e = atoi(optarg);
  98                         frag_err_list[nerrs++] = e;
  99                         break;
 100                 case 'r':
 101                         srand(atoi(optarg));
 102                         k = (rand() % (MMAX - 1)) + 1;  // Pick k {1 to MMAX - 1}
 103                         p = (rand() % (MMAX - k)) + 1;  // Pick p {1 to MMAX - k}
 104
 105                         for (i = 0; i < k + p && nerrs < p; i++)
 106                                 if (rand() & 1)
 107                                         frag_err_list[nerrs++] = i;
 108                         break;
 109                 case 'h':
 110                 default:
 111                         usage();
 112                         break;
 113                 }
 114         }
 115         m = k + p;
 116
 117         // Check for valid parameters
 118         if (m > MMAX || k > KMAX || m < 0 || p < 1 || k < 1) {
 119                 printf(" Input test parameter error m=%d, k=%d, p=%d, erasures=%d\n",
 120                        m, k, p, nerrs);
 121                 usage();
 122         }
 123         if (nerrs > p) {
 124                 printf(" Number of erasures chosen exceeds power of code erasures=%d p=%d\n",
 125                        nerrs, p);
 126                 usage();
 127         }
 128         for (i = 0; i < nerrs; i++) {
 129                 if (frag_err_list[i] >= m) {
 130                         printf(" fragment %d not in range\n", frag_err_list[i]);
 131                         usage();
 132                 }
 133         }
 134
 135         printf("ec_simple_example:\n");
 136
 137         // Allocate coding matrices
 138         encode_matrix = malloc(m * k);
 139         decode_matrix = malloc(m * k);
 140         invert_matrix = malloc(m * k);
 141         temp_matrix = malloc(m * k);
 142         g_tbls = malloc(k * p * 32);
 143
 144         if (encode_matrix == NULL || decode_matrix == NULL
 145             || invert_matrix == NULL || temp_matrix == NULL || g_tbls == NULL) {
 146                 printf("Test failure! Error with malloc\n");
 147                 return -1;
 148         }
 149         // Allocate the src & parity buffers
 150         for (i = 0; i < m; i++) {
 151                 if (NULL == (frag_ptrs[i] = malloc(len))) {
 152                         printf("alloc error: Fail\n");
 153                         return -1;
 154                 }
 155         }
 156
 157         // Allocate buffers for recovered data
 158         for (i = 0; i < p; i++) {
 159                 if (NULL == (recover_outp[i] = malloc(len))) {
 160                         printf("alloc error: Fail\n");
 161                         return -1;
 162                 }
 163         }
 164
 165         // Fill sources with random data
 166         for (i = 0; i < k; i++)
 167                 for (j = 0; j < len; j++)
 168                         frag_ptrs[i][j] = rand();
 169
 170         printf(" encode (m,k,p)=(%d,%d,%d) len=%d\n", m, k, p, len);
 171
 172         // Pick an encode matrix. A Cauchy matrix is a good choice as even
 173         // large k are always invertable keeping the recovery rule simple.
 174         gf_gen_cauchy1_matrix(encode_matrix, m, k);
 175
 176         // Initialize g_tbls from encode matrix
 177         ec_init_tables(k, p, &encode_matrix[k * k], g_tbls);
 178
 179         // Generate EC parity blocks from sources
 180         ec_encode_data(len, k, p, g_tbls, frag_ptrs, &frag_ptrs[k]);
 181
 182         if (nerrs <= 0)
 183                 return 0;
 184
 185         printf(" recover %d fragments\n", nerrs);
 186
 187         // Find a decode matrix to regenerate all erasures from remaining frags
 188         ret = gf_gen_decode_matrix_simple(encode_matrix, decode_matrix,
 189                                           invert_matrix, temp_matrix, decode_index,
 190                                           frag_err_list, nerrs, k, m);
 191         if (ret != 0) {
 192                 printf("Fail on generate decode matrix\n");
 193                 return -1;
 194         }
 195         // Pack recovery array pointers as list of valid fragments
 196         for (i = 0; i < k; i++)
 197                 recover_srcs[i] = frag_ptrs[decode_index[i]];
 198
 199         // Recover data
 200         ec_init_tables(k, nerrs, decode_matrix, g_tbls);
 201         ec_encode_data(len, k, nerrs, g_tbls, recover_srcs, recover_outp);
 202
 203         // Check that recovered buffers are the same as original
 204         printf(" check recovery of block {");
 205         for (i = 0; i < nerrs; i++) {
 206                 printf(" %d", frag_err_list[i]);
 207                 if (memcmp(recover_outp[i], frag_ptrs[frag_err_list[i]], len)) {
 208                         printf(" Fail erasure recovery %d, frag %d\n", i, frag_err_list[i]);
 209                         return -1;
 210                 }
 211         }
 212
 213         printf(" } done all: Pass\n");
 214         return 0;
 215 }
 216
 217 /*
 218  * Generate decode matrix from encode matrix and erasure list
 219  *
 220  */
 221
 222 static int gf_gen_decode_matrix_simple(u8 * encode_matrix,
 223                                        u8 * decode_matrix,
 224                                        u8 * invert_matrix,
 225                                        u8 * temp_matrix,
 226                                        u8 * decode_index, u8 * frag_err_list, int nerrs, int k,
 227                                        int m)
 228 {
 229         int i, j, p, r;
 230         int nsrcerrs = 0;
 231         u8 s, *b = temp_matrix;
 232         u8 frag_in_err[MMAX];
 233
 234         memset(frag_in_err, 0, sizeof(frag_in_err));
 235
 236         // Order the fragments in erasure for easier sorting
 237         for (i = 0; i < nerrs; i++) {
 238                 if (frag_err_list[i] < k)
 239                         nsrcerrs++;
 240                 frag_in_err[frag_err_list[i]] = 1;
 241         }
 242
 243         // Construct b (matrix that encoded remaining frags) by removing erased rows
 244         for (i = 0, r = 0; i < k; i++, r++) {
 245                 while (frag_in_err[r])
 246                         r++;
 247                 for (j = 0; j < k; j++)
 248                         b[k * i + j] = encode_matrix[k * r + j];
 249                 decode_index[i] = r;
 250         }
 251
 252         // Invert matrix to get recovery matrix
 253         if (gf_invert_matrix(b, invert_matrix, k) < 0)
 254                 return -1;
 255
 256         // Get decode matrix with only wanted recovery rows
 257         for (i = 0; i < nerrs; i++) {
 258                 if (frag_err_list[i] < k)       // A src err
 259                         for (j = 0; j < k; j++)
 260                                 decode_matrix[k * i + j] =
 261                                     invert_matrix[k * frag_err_list[i] + j];
 262         }
 263
 264         // For non-src (parity) erasures need to multiply encode matrix * invert
 265         for (p = 0; p < nerrs; p++) {
 266                 if (frag_err_list[p] >= k) {    // A parity err
 267                         for (i = 0; i < k; i++) {
 268                                 s = 0;
 269                                 for (j = 0; j < k; j++)
 270                                         s ^= gf_mul(invert_matrix[j * k + i],
 271                                                     encode_matrix[k * frag_err_list[p] + j]);
 272                                 decode_matrix[k * p + i] = s;
 273                         }
 274                 }
 275         }
 276         return 0;
 277 }