src/ceph/src/test/erasure-code/TestErasureCodeShec_arguments.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2015 FUJITSU LIMITED
   7  *
   8  * Author: Shotaro Kawaguchi <kawaguchi.s@jp.fujitsu.com>
   9  * Author: Takanori Nakao <nakao.takanori@jp.fujitsu.com>
  10  * Author: Takeshi Miyamae <miyamae.takeshi@jp.fujitsu.com>
  11  *
  12  *  This library is free software; you can redistribute it and/or
  13  *  modify it under the terms of the GNU Lesser General Public
  14  *  License as published by the Free Software Foundation; either
  15  *  version 2.1 of the License, or (at your option) any later version.
  16  *
  17  */
  18
  19 // SUMMARY: shec's gtest for each argument of minimum_to_decode()/decode()
  20
  21 #include <errno.h>
  22 #include <stdlib.h>
  23
  24 #include "crush/CrushWrapper.h"
  25 #include "osd/osd_types.h"
  26 #include "include/stringify.h"
  27 #include "global/global_init.h"
  28 #include "erasure-code/shec/ErasureCodeShec.h"
  29 #include "erasure-code/ErasureCodePlugin.h"
  30 #include "common/ceph_argparse.h"
  31 #include "global/global_context.h"
  32 #include "gtest/gtest.h"
  33
  34 unsigned int count_num = 0;
  35 unsigned int unexpected_count = 0;
  36 unsigned int value_count = 0;
  37
  38 map<set<int>,set<set<int> > > shec_table;
  39
  40 int getint(int a, int b) {
  41   return ((1 << a) | (1 << b));
  42 }
  43
  44 int getint(int a, int b, int c) {
  45   return ((1 << a) | (1 << b) | (1 << c));
  46 }
  47
  48 int getint(int a, int b, int c, int d) {
  49   return ((1 << a) | (1 << b) | (1 << c) | (1 << d));
  50 }
  51
  52 void create_table_shec432() {
  53   set<int> table_key,vec_avails;
  54   set<set<int> > table_value;
  55
  56   for (int want_count = 0; want_count < 7; ++want_count) {
  57     for (int want = 1; want < (1<<7); ++want) {
  58       table_key.clear();
  59       table_value.clear();
  60       if (__builtin_popcount(want) != want_count) {
  61         continue;
  62       }
  63       {
  64         for (int i = 0; i < 7; ++i) {
  65           if (want & (1 << i)) {
  66             table_key.insert(i);
  67           }
  68         }
  69       }
  70       vector<int> vec;
  71       for (int avails = 0; avails < (1<<7); ++avails) {
  72         if (want & avails) {
  73           continue;
  74         }
  75         if (__builtin_popcount(avails) == 2 &&
  76             __builtin_popcount(want) == 1) {
  77           if ((want | avails) == getint(0,1,5) ||
  78               (want | avails) == getint(2,3,6)) {
  79             vec.push_back(avails);
  80           }
  81         }
  82       }
  83
  84       for (int avails = 0; avails < (1<<7); ++avails) {
  85         if (want & avails) {
  86           continue;
  87         }
  88         if (__builtin_popcount(avails) == 4) {
  89           if ((avails) == getint(0,1,2,3) ||
  90               (avails) == getint(0,1,2,4) ||
  91               (avails) == getint(0,1,2,6) ||
  92               (avails) == getint(0,1,3,4) ||
  93               (avails) == getint(0,1,3,6) ||
  94               (avails) == getint(0,1,4,6) ||
  95               (avails) == getint(0,2,3,4) ||
  96               (avails) == getint(0,2,3,5) ||
  97               (avails) == getint(0,2,4,5) ||
  98               (avails) == getint(0,2,4,6) ||
  99               (avails) == getint(0,2,5,6) ||
 100               (avails) == getint(0,3,4,5) ||
 101               (avails) == getint(0,3,4,6) ||
 102               (avails) == getint(0,3,5,6) ||
 103               (avails) == getint(0,4,5,6) ||
 104               (avails) == getint(1,2,3,4) ||
 105               (avails) == getint(1,2,3,5) ||
 106               (avails) == getint(1,2,4,5) ||
 107               (avails) == getint(1,2,4,6) ||
 108               (avails) == getint(1,2,5,6) ||
 109               (avails) == getint(1,3,4,5) ||
 110               (avails) == getint(1,3,4,6) ||
 111               (avails) == getint(1,3,5,6) ||
 112               (avails) == getint(1,4,5,6) ||
 113               (avails) == getint(2,3,4,5) ||
 114               (avails) == getint(2,4,5,6) ||
 115               (avails) == getint(3,4,5,6)) {
 116             vec.push_back(avails);
 117           }
 118         }
 119       }
 120       for (int i = 0; i < (int)vec.size(); ++i) {
 121         for (int j = i + 1; j < (int)vec.size(); ++j) {
 122           if ((vec[i] & vec[j]) == vec[i]) {
 123             vec.erase(vec.begin() + j);
 124             --j;
 125           }
 126         }
 127       }
 128       for (int i = 0; i < (int)vec.size(); ++i) {
 129         vec_avails.clear();
 130         for (int j = 0; j < 7; ++j) {
 131           if (vec[i] & (1 << j)) {
 132             vec_avails.insert(j);
 133           }
 134         }
 135         table_value.insert(vec_avails);
 136       }
 137       shec_table.insert(std::make_pair(table_key,table_value));
 138     }
 139   }
 140 }
 141
 142 bool search_table_shec432(set<int> want_to_read, set<int> available_chunks) {
 143   set<set<int> > tmp;
 144   set<int> settmp;
 145   bool found;
 146
 147   tmp = shec_table.find(want_to_read)->second;
 148   for (set<set<int> >::iterator itr = tmp.begin();itr != tmp.end(); ++itr) {
 149     found = true;
 150     value_count = 0;
 151     settmp = *itr;
 152     for (set<int>::iterator setitr = settmp.begin();setitr != settmp.end(); ++setitr) {
 153       if (!available_chunks.count(*setitr)) {
 154         found = false;
 155       }
 156       ++value_count;
 157     }
 158     if (found) {
 159       return true;
 160     }
 161   }
 162   return false;
 163 }
 164
 165 TEST(ParameterTest, combination_all)
 166 {
 167   int result;
 168   unsigned alignment, tail, padded_length;
 169   const unsigned int kObjectSize = 128;
 170
 171   //get profile
 172   char* k = (char*)"4";
 173   char* m = (char*)"3";
 174   char* c = (char*)"2";
 175   int i_k = atoi(k);
 176   int i_m = atoi(m);
 177   int i_c = atoi(c);
 178   alignment = i_k * 8 * sizeof(int);
 179   tail = kObjectSize % alignment;
 180   padded_length = kObjectSize + (tail ? (alignment - tail) : 0);
 181   unsigned c_size = padded_length / i_k;
 182
 183   //init
 184   ErasureCodeShecTableCache tcache;
 185   ErasureCodeShec* shec = new ErasureCodeShecReedSolomonVandermonde(
 186                                   tcache,
 187                                   ErasureCodeShec::MULTIPLE);
 188   map < std::string, std::string > *profile = new map<std::string,
 189                                                          std::string>();
 190   (*profile)["plugin"] = "shec";
 191   (*profile)["technique"] = "";
 192   (*profile)["crush-failure-domain"] = "osd";
 193   (*profile)["k"] = k;
 194   (*profile)["m"] = m;
 195   (*profile)["c"] = c;
 196
 197   result = shec->init(*profile, &cerr);
 198
 199   //check profile
 200   EXPECT_EQ(i_k, shec->k);
 201   EXPECT_EQ(i_m, shec->m);
 202   EXPECT_EQ(i_c, shec->c);
 203   EXPECT_EQ(8, shec->w);
 204   EXPECT_EQ(ErasureCodeShec::MULTIPLE, shec->technique);
 205   EXPECT_STREQ("default", shec->rule_root.c_str());
 206   EXPECT_STREQ("osd", shec->rule_failure_domain.c_str());
 207   EXPECT_TRUE(shec->matrix != NULL);
 208   EXPECT_EQ(0, result);
 209
 210   //encode
 211   bufferlist in,out1;
 212   set<int> want_to_encode;
 213   map<int, bufferlist> encoded;
 214
 215   in.append("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//length = 62
 216             "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//124
 217             "0123"//128
 218   );
 219   for (unsigned int i = 0; i < shec->get_chunk_count(); ++i) {
 220     want_to_encode.insert(i);
 221   }
 222
 223   result = shec->encode(want_to_encode, in, &encoded);
 224   EXPECT_EQ(0, result);
 225   EXPECT_EQ(i_k+i_m, (int)encoded.size());
 226   EXPECT_EQ(c_size, encoded[0].length());
 227   //out1 is "encoded"
 228   for (unsigned int i = 0; i < encoded.size(); ++i) {
 229     out1.append(encoded[i]);
 230   }
 231   EXPECT_FALSE(out1 == in);
 232
 233   set<int> want_to_read, available_chunks, minimum_chunks, want_to_read_without_avails;
 234   set<int>::iterator itr;
 235   int array_want_to_read[shec->get_chunk_count()];
 236   int array_available_chunks[shec->get_chunk_count()];
 237   int dresult,cmp;
 238   map<int, bufferlist> inchunks,decoded;
 239   bufferlist usable;
 240   unsigned int minimum_count;
 241
 242   for (unsigned int w1 = 0; w1 <= shec->get_chunk_count(); ++w1) {
 243     const unsigned int r1 = w1;         // combination(k+m,r1)
 244
 245     for (unsigned int i = 0; i < r1; ++i) {
 246       array_want_to_read[i] = 1;
 247     }
 248     for (unsigned int i = r1; i < shec->get_chunk_count(); ++i) {
 249       array_want_to_read[i] = 0;
 250     }
 251
 252     for (unsigned w2 = 0; w2 <= shec->get_chunk_count(); ++w2) {
 253       const unsigned int r2 = w2;       // combination(k+m,r2)
 254
 255       for (unsigned int i = 0; i < r2; ++i ) {
 256         array_available_chunks[i] = 1;
 257       }
 258       for (unsigned int i = r2; i < shec->get_chunk_count(); ++i ) {
 259         array_available_chunks[i] = 0;
 260       }
 261
 262       do {
 263         do {
 264           for (unsigned int i = 0; i < shec->get_chunk_count(); ++i) {
 265             if (array_want_to_read[i]) {
 266               want_to_read.insert(i);
 267             }
 268             if (array_available_chunks[i]) {
 269               available_chunks.insert(i);
 270               inchunks.insert(make_pair(i,encoded[i]));
 271             }
 272           }
 273
 274           result = shec->minimum_to_decode(want_to_read, available_chunks,
 275                                            &minimum_chunks);
 276           dresult = shec->decode(want_to_read, inchunks, &decoded);
 277           ++count_num;
 278           minimum_count = 0;
 279
 280           if (want_to_read.size() == 0) {
 281             EXPECT_EQ(0, result);
 282             EXPECT_EQ(0u, minimum_chunks.size());
 283             EXPECT_EQ(0, dresult);
 284             EXPECT_EQ(0u, decoded.size());
 285             EXPECT_EQ(0u, decoded[0].length());
 286             if (result != 0 || dresult != 0) {
 287               ++unexpected_count;
 288             }
 289           } else {
 290             // want - avail
 291             for (itr = want_to_read.begin();itr != want_to_read.end(); ++itr) {
 292               if (!available_chunks.count(*itr)) {
 293                 want_to_read_without_avails.insert(*itr);
 294               } else {
 295                 ++minimum_count;
 296               }
 297             }
 298
 299             if (want_to_read_without_avails.size() == 0) {
 300               EXPECT_EQ(0, result);
 301               EXPECT_LT(0u, minimum_chunks.size());
 302               EXPECT_GE(minimum_count, minimum_chunks.size());
 303               EXPECT_EQ(0, dresult);
 304               EXPECT_NE(0u, decoded.size());
 305               for (unsigned int i = 0; i < shec->get_data_chunk_count(); ++i) {
 306                 if (array_want_to_read[i]) {
 307                   usable.clear();
 308                   usable.substr_of(in, c_size * i, c_size);
 309                   cmp = memcmp(decoded[i].c_str(), usable.c_str(), c_size);
 310                   EXPECT_EQ(c_size, decoded[i].length());
 311                   EXPECT_EQ(0, cmp);
 312                   if (cmp != 0) {
 313                     ++unexpected_count;
 314                   }
 315                 }
 316               }
 317               if (result != 0 || dresult != 0) {
 318                 ++unexpected_count;
 319               }
 320             } else if (want_to_read_without_avails.size() > 3) {
 321               EXPECT_EQ(-EIO, result);
 322               EXPECT_EQ(0u, minimum_chunks.size());
 323               EXPECT_EQ(-1, dresult);
 324               EXPECT_EQ(shec->get_chunk_count(), decoded.size());
 325               if (result != -EIO || dresult != -1) {
 326                 ++unexpected_count;
 327               }
 328             } else {
 329               // search
 330               if (search_table_shec432(want_to_read_without_avails,available_chunks)) {
 331                 EXPECT_EQ(0, result);
 332                 EXPECT_LT(0u, minimum_chunks.size());
 333                 EXPECT_GE(value_count + minimum_count, minimum_chunks.size());
 334                 EXPECT_EQ(0, dresult);
 335                 EXPECT_NE(0u, decoded.size());
 336                 for (unsigned int i = 0; i < shec->get_data_chunk_count(); ++i) {
 337                   if (array_want_to_read[i]) {
 338                     usable.clear();
 339                     usable.substr_of(in, c_size * i, c_size);
 340                     cmp = memcmp(decoded[i].c_str(), usable.c_str(), c_size);
 341                     EXPECT_EQ(c_size, decoded[i].length());
 342                     EXPECT_EQ(0, cmp);
 343                     if (cmp != 0) {
 344                       ++unexpected_count;
 345                       std::cout << "decoded[" << i << "] = " << decoded[i].c_str() << std::endl;
 346                       std::cout << "usable = " << usable.c_str() << std::endl;
 347                       std::cout << "want_to_read    :" << want_to_read << std::endl;
 348                       std::cout << "available_chunks:" << available_chunks << std::endl;
 349                       std::cout << "minimum_chunks  :" << minimum_chunks << std::endl;
 350                     }
 351                   }
 352                 }
 353                 if (result != 0 || dresult != 0) {
 354                   ++unexpected_count;
 355                 }
 356               } else {
 357                 EXPECT_EQ(-EIO, result);
 358                 EXPECT_EQ(0u, minimum_chunks.size());
 359                 EXPECT_EQ(-1, dresult);
 360                 EXPECT_EQ(shec->get_chunk_count(), decoded.size());
 361                 if (result != -EIO || dresult != -1) {
 362                   ++unexpected_count;
 363                 }
 364               }
 365             }
 366           }
 367
 368           want_to_read.clear();
 369           want_to_read_without_avails.clear();
 370           available_chunks.clear();
 371           minimum_chunks.clear();
 372           inchunks.clear();
 373           decoded.clear();
 374           usable.clear();
 375         } while (std::prev_permutation(
 376                    array_want_to_read,
 377                    array_want_to_read + shec->get_chunk_count()));
 378
 379       } while (std::prev_permutation(
 380                  array_available_chunks,
 381                  array_available_chunks + shec->get_chunk_count()));
 382     }
 383   }
 384
 385   delete shec;
 386   delete profile;
 387 }
 388
 389 int main(int argc, char **argv)
 390 {
 391   int r;
 392
 393   vector<const char*> args;
 394   argv_to_vec(argc, (const char **) argv, args);
 395
 396   auto cct = global_init(NULL, args, CEPH_ENTITY_TYPE_CLIENT,
 397                          CODE_ENVIRONMENT_UTILITY, 0);
 398   common_init_finish(g_ceph_context);
 399
 400   const char* env = getenv("CEPH_LIB");
 401   std::string directory(env ? env : ".libs");
 402   g_conf->set_val_or_die("erasure_code_dir", directory, false);
 403
 404   ::testing::InitGoogleTest(&argc, argv);
 405
 406   create_table_shec432();
 407
 408   r = RUN_ALL_TESTS();
 409
 410   std::cout << "minimum_to_decode:total_num = " << count_num
 411       << std::endl;
 412   std::cout << "minimum_to_decode:unexpected_num = " << unexpected_count
 413       << std::endl;
 414
 415   return r;
 416 }