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

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 /*
   3  * Ceph - scalable distributed file system
   4  *
   5  * Copyright (C) 2014 CERN (Switzerland)
   6  * Copyright (C) 2014 Red Hat <contact@redhat.com>
   7  *
   8  * Author: Andreas-Joachim Peters <Andreas.Joachim.Peters@cern.ch>
   9  * Author: Loic Dachary <loic@dachary.org>
  10  *
  11  *  This library is free software; you can redistribute it and/or
  12  *  modify it under the terms of the GNU Lesser General Public
  13  *  License as published by the Free Software Foundation; either
  14  *  version 2.1 of the License, or (at your option) any later version.
  15  *
  16  */
  17
  18 #include <errno.h>
  19 #include <stdlib.h>
  20
  21 #include "crush/CrushWrapper.h"
  22 #include "include/stringify.h"
  23 #include "erasure-code/isa/ErasureCodeIsa.h"
  24 #include "erasure-code/isa/xor_op.h"
  25 #include "global/global_context.h"
  26 #include "common/config.h"
  27 #include "gtest/gtest.h"
  28
  29 using namespace std;
  30
  31 ErasureCodeIsaTableCache tcache;
  32
  33 class IsaErasureCodeTest : public ::testing::Test {
  34 public:
  35   void compare_chunks(bufferlist &in, map<int, bufferlist> &encoded);
  36   void encode_decode(unsigned object_size);
  37 };
  38
  39 void IsaErasureCodeTest::compare_chunks(bufferlist &in, map<int, bufferlist> &encoded)
  40 {
  41   unsigned object_size = in.length();
  42   unsigned chunk_size = encoded[0].length();
  43   for (unsigned i = 0; i < encoded.size(); i++) {
  44     if (i * chunk_size >= object_size)
  45       break;
  46     int chunk_length = object_size > (i + 1) * chunk_size ? chunk_size : object_size - i * chunk_size;
  47     EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + i * chunk_size, chunk_length));
  48   }
  49 }
  50
  51 void IsaErasureCodeTest::encode_decode(unsigned object_size)
  52 {
  53   ErasureCodeIsaDefault Isa(tcache);
  54
  55   ErasureCodeProfile profile;
  56   profile["k"] = "2";
  57   profile["m"] = "2";
  58   Isa.init(profile, &cerr);
  59
  60   string payload(object_size, 'X');
  61   bufferlist in;
  62   // may be multiple bufferptr if object_size is larger than CEPH_PAGE_SIZE
  63   in.append(payload.c_str(), payload.length());
  64   int want_to_encode[] = {0, 1, 2, 3};
  65   map<int, bufferlist> encoded;
  66   EXPECT_EQ(0, Isa.encode(set<int>(want_to_encode, want_to_encode + 4),
  67                           in,
  68                           &encoded));
  69   EXPECT_EQ(4u, encoded.size());
  70   unsigned chunk_size = encoded[0].length();
  71   EXPECT_EQ(chunk_size, Isa.get_chunk_size(object_size));
  72   compare_chunks(in, encoded);
  73
  74   // all chunks are available
  75   {
  76     int want_to_decode[] = {0, 1};
  77     map<int, bufferlist> decoded;
  78     EXPECT_EQ(0, Isa._decode(set<int>(want_to_decode, want_to_decode + 2),
  79                              encoded,
  80                              &decoded));
  81     EXPECT_EQ(2u, decoded.size());
  82     EXPECT_EQ(chunk_size, decoded[0].length());
  83     compare_chunks(in, decoded);
  84   }
  85
  86   // one data chunk is missing
  87   {
  88     map<int, bufferlist> degraded = encoded;
  89
  90     string enc1(encoded[1].c_str(), chunk_size);
  91
  92     degraded.erase(1);
  93     EXPECT_EQ(3u, degraded.size());
  94     int want_to_decode[] = {1};
  95     map<int, bufferlist> decoded;
  96     EXPECT_EQ(0, Isa._decode(set<int>(want_to_decode, want_to_decode + 1),
  97                              degraded,
  98                              &decoded));
  99     // always decode all, regardless of want_to_decode
 100     EXPECT_EQ(4u, decoded.size());
 101     EXPECT_EQ(chunk_size, decoded[1].length());
 102     EXPECT_EQ(0, memcmp(decoded[1].c_str(), enc1.c_str(), chunk_size));
 103   }
 104
 105   // non-xor coding chunk is missing
 106   {
 107     map<int, bufferlist> degraded = encoded;
 108
 109     string enc3(encoded[3].c_str(), chunk_size);
 110
 111     degraded.erase(3);
 112     EXPECT_EQ(3u, degraded.size());
 113     int want_to_decode[] = {3};
 114     map<int, bufferlist> decoded;
 115     EXPECT_EQ(0, Isa._decode(set<int>(want_to_decode, want_to_decode + 1),
 116                             degraded,
 117                             &decoded));
 118     // always decode all, regardless of want_to_decode
 119     EXPECT_EQ(4u, decoded.size());
 120     EXPECT_EQ(chunk_size, decoded[3].length());
 121     EXPECT_EQ(0, memcmp(decoded[3].c_str(), enc3.c_str(), chunk_size));
 122   }
 123
 124   // xor coding chunk is missing
 125   {
 126     map<int, bufferlist> degraded = encoded;
 127
 128     string enc2(encoded[2].c_str(), chunk_size);
 129
 130     degraded.erase(2);
 131     EXPECT_EQ(3u, degraded.size());
 132     int want_to_decode[] = {2};
 133     map<int, bufferlist> decoded;
 134     EXPECT_EQ(0, Isa._decode(set<int>(want_to_decode, want_to_decode + 1),
 135                              degraded,
 136                              &decoded));
 137     // always decode all, regardless of want_to_decode
 138     EXPECT_EQ(4u, decoded.size());
 139     EXPECT_EQ(chunk_size, decoded[2].length());
 140     EXPECT_EQ(0, memcmp(decoded[2].c_str(), enc2.c_str(), chunk_size));
 141   }
 142
 143   // one data and one coding chunk is missing
 144   {
 145     map<int, bufferlist> degraded = encoded;
 146
 147     string enc3(encoded[3].c_str(), chunk_size);
 148
 149     degraded.erase(1);
 150     degraded.erase(3);
 151     EXPECT_EQ(2u, degraded.size());
 152     int want_to_decode[] = {1, 3};
 153     map<int, bufferlist> decoded;
 154     EXPECT_EQ(0, Isa._decode(set<int>(want_to_decode, want_to_decode + 2),
 155                              degraded,
 156                              &decoded));
 157     // always decode all, regardless of want_to_decode
 158     EXPECT_EQ(4u, decoded.size());
 159     EXPECT_EQ(chunk_size, decoded[1].length());
 160     EXPECT_EQ(0, memcmp(decoded[3].c_str(), enc3.c_str(), chunk_size));
 161   }
 162
 163   // two data chunks are missing
 164   {
 165     map<int, bufferlist> degraded = encoded;
 166     degraded.erase(0);
 167     degraded.erase(1);
 168     EXPECT_EQ(2u, degraded.size());
 169     int want_to_decode[] = {0, 1};
 170     map<int, bufferlist> decoded;
 171     EXPECT_EQ(0, Isa._decode(set<int>(want_to_decode, want_to_decode + 2),
 172                              degraded,
 173                              &decoded));
 174     // always decode all, regardless of want_to_decode
 175     EXPECT_EQ(4u, decoded.size());
 176     EXPECT_EQ(chunk_size, decoded[0].length());
 177     compare_chunks(in, decoded);
 178   }
 179
 180 }
 181
 182 TEST_F(IsaErasureCodeTest, encode_decode)
 183 {
 184   encode_decode(1);
 185   encode_decode(EC_ISA_ADDRESS_ALIGNMENT);
 186   encode_decode(EC_ISA_ADDRESS_ALIGNMENT + 1);
 187   encode_decode(2048);
 188   encode_decode(4096);
 189   encode_decode(4096 + 1);
 190 }
 191
 192 TEST_F(IsaErasureCodeTest, minimum_to_decode)
 193 {
 194   ErasureCodeIsaDefault Isa(tcache);
 195   ErasureCodeProfile profile;
 196   profile["k"] = "2";
 197   profile["m"] = "2";
 198   Isa.init(profile, &cerr);
 199
 200   //
 201   // If trying to read nothing, the minimum is empty.
 202   //
 203   {
 204     set<int> want_to_read;
 205     set<int> available_chunks;
 206     set<int> minimum;
 207
 208     EXPECT_EQ(0, Isa._minimum_to_decode(want_to_read,
 209                                         available_chunks,
 210                                         &minimum));
 211     EXPECT_TRUE(minimum.empty());
 212   }
 213   //
 214   // There is no way to read a chunk if none are available.
 215   //
 216   {
 217     set<int> want_to_read;
 218     set<int> available_chunks;
 219     set<int> minimum;
 220
 221     want_to_read.insert(0);
 222
 223     EXPECT_EQ(-EIO, Isa._minimum_to_decode(want_to_read,
 224                                            available_chunks,
 225                                            &minimum));
 226   }
 227   //
 228   // Reading a subset of the available chunks is always possible.
 229   //
 230   {
 231     set<int> want_to_read;
 232     set<int> available_chunks;
 233     set<int> minimum;
 234
 235     want_to_read.insert(0);
 236     available_chunks.insert(0);
 237
 238     EXPECT_EQ(0, Isa._minimum_to_decode(want_to_read,
 239                                         available_chunks,
 240                                         &minimum));
 241     EXPECT_EQ(want_to_read, minimum);
 242   }
 243   //
 244   // There is no way to read a missing chunk if there is less than k
 245   // chunks available.
 246   //
 247   {
 248     set<int> want_to_read;
 249     set<int> available_chunks;
 250     set<int> minimum;
 251
 252     want_to_read.insert(0);
 253     want_to_read.insert(1);
 254     available_chunks.insert(0);
 255
 256     EXPECT_EQ(-EIO, Isa._minimum_to_decode(want_to_read,
 257                                            available_chunks,
 258                                            &minimum));
 259   }
 260   //
 261   // When chunks are not available, the minimum can be made of any
 262   // chunks. For instance, to read 1 and 3 below the minimum could be
 263   // 2 and 3 which may seem better because it contains one of the
 264   // chunks to be read. But it won't be more efficient than retrieving
 265   // 0 and 2 instead because, in both cases, the decode function will
 266   // need to run the same recovery operation and use the same amount
 267   // of CPU and memory.
 268   //
 269   {
 270     set<int> want_to_read;
 271     set<int> available_chunks;
 272     set<int> minimum;
 273
 274     want_to_read.insert(1);
 275     want_to_read.insert(3);
 276     available_chunks.insert(0);
 277     available_chunks.insert(2);
 278     available_chunks.insert(3);
 279
 280     EXPECT_EQ(0, Isa._minimum_to_decode(want_to_read,
 281                                         available_chunks,
 282                                         &minimum));
 283     EXPECT_EQ(2u, minimum.size());
 284     EXPECT_EQ(0u, minimum.count(3));
 285   }
 286 }
 287
 288 TEST_F(IsaErasureCodeTest, chunk_size)
 289 {
 290   {
 291     ErasureCodeIsaDefault Isa(tcache);
 292     ErasureCodeProfile profile;
 293     profile["k"] = "2";
 294     profile["m"] = "1";
 295     Isa.init(profile, &cerr);
 296     const int k = 2;
 297
 298     ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(1));
 299     ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k - 1));
 300     ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT * 2, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k + 1));
 301   }
 302   {
 303     ErasureCodeIsaDefault Isa(tcache);
 304     ErasureCodeProfile profile;
 305     profile["k"] = "3";
 306     profile["m"] = "1";
 307     Isa.init(profile, &cerr);
 308     const int k = 3;
 309
 310     ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(1));
 311     ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k - 1));
 312     ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT * 2, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k + 1));
 313     unsigned object_size = EC_ISA_ADDRESS_ALIGNMENT * k * 1024 + 1;
 314     ASSERT_NE(0u, object_size % k);
 315     ASSERT_NE(0u, object_size % EC_ISA_ADDRESS_ALIGNMENT);
 316     unsigned chunk_size = Isa.get_chunk_size(object_size);
 317     ASSERT_EQ(0u, chunk_size % EC_ISA_ADDRESS_ALIGNMENT);
 318     ASSERT_GT(chunk_size, (chunk_size * k) - object_size);
 319   }
 320 }
 321
 322 TEST_F(IsaErasureCodeTest, encode)
 323 {
 324   ErasureCodeIsaDefault Isa(tcache);
 325   ErasureCodeProfile profile;
 326   profile["k"] = "2";
 327   profile["m"] = "2";
 328   Isa.init(profile, &cerr);
 329
 330   unsigned aligned_object_size = Isa.get_alignment() * 2;
 331   {
 332     //
 333     // When the input bufferlist needs to be padded because
 334     // it is not properly aligned, it is padded with zeros.
 335     //
 336     bufferlist in;
 337     map<int,bufferlist> encoded;
 338     int want_to_encode[] = { 0, 1, 2, 3 };
 339     int trail_length = 1;
 340     in.append(string(aligned_object_size + trail_length, 'X'));
 341     EXPECT_EQ(0, Isa.encode(set<int>(want_to_encode, want_to_encode+4),
 342                                  in,
 343                                  &encoded));
 344     EXPECT_EQ(4u, encoded.size());
 345     char *last_chunk = encoded[1].c_str();
 346     int length =encoded[1].length();
 347     EXPECT_EQ('X', last_chunk[0]);
 348     EXPECT_EQ('\0', last_chunk[length - trail_length]);
 349   }
 350
 351   {
 352     //
 353     // When only the first chunk is required, the encoded map only
 354     // contains the first chunk. Although the Isa encode
 355     // internally allocated a buffer because of padding requirements
 356     // and also computes the coding chunks, they are released before
 357     // the return of the method, as shown when running the tests thru
 358     // valgrind (there is no leak).
 359     //
 360     bufferlist in;
 361     map<int,bufferlist> encoded;
 362     set<int> want_to_encode;
 363     want_to_encode.insert(0);
 364     int trail_length = 1;
 365     in.append(string(aligned_object_size + trail_length, 'X'));
 366     EXPECT_EQ(0, Isa.encode(want_to_encode, in, &encoded));
 367     EXPECT_EQ(1u, encoded.size());
 368   }
 369 }
 370
 371 TEST_F(IsaErasureCodeTest, sanity_check_k)
 372 {
 373   ErasureCodeIsaDefault Isa(tcache);
 374   ErasureCodeProfile profile;
 375   profile["k"] = "1";
 376   profile["m"] = "1";
 377   ostringstream errors;
 378   EXPECT_EQ(-EINVAL, Isa.init(profile, &errors));
 379   EXPECT_NE(std::string::npos, errors.str().find("must be >= 2"));
 380 }
 381
 382 bool
 383 DecodeAndVerify(ErasureCodeIsaDefault& Isa, map<int, bufferlist> &degraded, set<int> want_to_decode, buffer::ptr* enc, int length)
 384 {
 385   map<int, bufferlist> decoded;
 386   bool ok;
 387
 388   // decode as requested
 389   ok = Isa._decode(want_to_decode,
 390                    degraded,
 391                    &decoded);
 392
 393   for (int i = 0; i < (int) decoded.size(); i++) {
 394     // compare all the buffers with their original
 395     ok |= memcmp(decoded[i].c_str(), enc[i].c_str(), length);
 396   }
 397
 398   return ok;
 399 }
 400
 401 TEST_F(IsaErasureCodeTest, isa_vandermonde_exhaustive)
 402 {
 403   // Test all possible failure scenarios and reconstruction cases for
 404   // a (12,4) configuration using the vandermonde matrix
 405
 406   ErasureCodeIsaDefault Isa(tcache);
 407   ErasureCodeProfile profile;
 408   profile["k"] = "12";
 409   profile["m"] = "4";
 410   Isa.init(profile, &cerr);
 411
 412   const int k = 12;
 413   const int m = 4;
 414
 415 #define LARGE_ENOUGH 2048
 416   bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
 417   in_ptr.zero();
 418   in_ptr.set_length(0);
 419   const char *payload =
 420     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 421     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 422     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 423     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 424     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 425     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 426     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 427     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 428     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 429     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 430     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 431     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 432     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 433     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 434     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 435     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 436     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 437     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 438     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 439     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 440     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 441     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 442     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 443     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 444     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
 445   in_ptr.append(payload, strlen(payload));
 446   bufferlist in;
 447   in.push_back(in_ptr);
 448
 449   set<int>want_to_encode;
 450
 451   map<int, bufferlist> encoded;
 452   for (int i = 0; i < (k + m); i++) {
 453     want_to_encode.insert(i);
 454   }
 455
 456
 457   EXPECT_EQ(0, Isa.encode(want_to_encode,
 458                           in,
 459                           &encoded));
 460
 461   EXPECT_EQ((unsigned) (k + m), encoded.size());
 462
 463   unsigned length = encoded[0].length();
 464
 465   for (int i = 0; i < k; i++) {
 466     EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
 467   }
 468
 469   buffer::ptr enc[k + m];
 470   // create buffers with a copy of the original data to be able to compare it after decoding
 471   {
 472     for (int i = 0; i < (k + m); i++) {
 473       buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
 474       enc[i] = newenc;
 475       enc[i].zero();
 476       enc[i].set_length(0);
 477       enc[i].append(encoded[i].c_str(), length);
 478     }
 479   }
 480
 481   // loop through all possible loss scenarios
 482   int cnt_cf = 0;
 483
 484   for (int l1 = 0; l1 < (k + m); l1++) {
 485     map<int, bufferlist> degraded = encoded;
 486     set<int> want_to_decode;
 487     bool err;
 488     degraded.erase(l1);
 489     want_to_decode.insert(l1);
 490     err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 491     EXPECT_EQ(0, err);
 492     cnt_cf++;
 493     for (int l2 = l1 + 1; l2 < (k + m); l2++) {
 494       degraded.erase(l2);
 495       want_to_decode.insert(l2);
 496       err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 497       EXPECT_EQ(0, err);
 498       cnt_cf++;
 499       for (int l3 = l2 + 1; l3 < (k + m); l3++) {
 500         degraded.erase(l3);
 501         want_to_decode.insert(l3);
 502         err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 503         EXPECT_EQ(0, err);
 504         cnt_cf++;
 505         for (int l4 = l3 + 1; l4 < (k + m); l4++) {
 506           degraded.erase(l4);
 507           want_to_decode.insert(l4);
 508           err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 509           EXPECT_EQ(0, err);
 510           degraded[l4] = encoded[l4];
 511           want_to_decode.erase(l4);
 512           cnt_cf++;
 513         }
 514         degraded[l3] = encoded[l3];
 515         want_to_decode.erase(l3);
 516       }
 517       degraded[l2] = encoded[l2];
 518       want_to_decode.erase(l2);
 519     }
 520     degraded[l1] = encoded[l1];
 521     want_to_decode.erase(l1);
 522   }
 523   EXPECT_EQ(2516, cnt_cf);
 524   EXPECT_EQ(2506, tcache.getDecodingTableCacheSize()); // 3 entries from (2,2) test and 2503 from (12,4)
 525 }
 526
 527 TEST_F(IsaErasureCodeTest, isa_cauchy_exhaustive)
 528 {
 529   // Test all possible failure scenarios and reconstruction cases for
 530   // a (12,4) configuration using the cauchy matrix
 531   ErasureCodeIsaDefault Isa(tcache,ErasureCodeIsaDefault::kCauchy);
 532   ErasureCodeProfile profile;
 533   profile["k"] = "12";
 534   profile["m"] = "4";
 535   profile["technique"] = "cauchy";
 536
 537   Isa.init(profile, &cerr);
 538
 539   const int k = 12;
 540   const int m = 4;
 541
 542 #define LARGE_ENOUGH 2048
 543   bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
 544   in_ptr.zero();
 545   in_ptr.set_length(0);
 546   const char *payload =
 547     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 548     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 549     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 550     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 551     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 552     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 553     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 554     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 555     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 556     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 557     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 558     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 559     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 560     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 561     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 562     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 563     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 564     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 565     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 566     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 567     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 568     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 569     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 570     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 571     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
 572   in_ptr.append(payload, strlen(payload));
 573   bufferlist in;
 574   in.push_back(in_ptr);
 575
 576   set<int>want_to_encode;
 577
 578   map<int, bufferlist> encoded;
 579   for (int i = 0; i < (k + m); i++) {
 580     want_to_encode.insert(i);
 581   }
 582
 583
 584   EXPECT_EQ(0, Isa.encode(want_to_encode,
 585                           in,
 586                           &encoded));
 587
 588   EXPECT_EQ((unsigned) (k + m), encoded.size());
 589
 590   unsigned length = encoded[0].length();
 591
 592   for (int i = 0; i < k; i++) {
 593     EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
 594   }
 595
 596   buffer::ptr enc[k + m];
 597   // create buffers with a copy of the original data to be able to compare it after decoding
 598   {
 599     for (int i = 0; i < (k + m); i++) {
 600       buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
 601       enc[i] = newenc;
 602       enc[i].zero();
 603       enc[i].set_length(0);
 604       enc[i].append(encoded[i].c_str(), length);
 605     }
 606   }
 607
 608   // loop through all possible loss scenarios
 609   int cnt_cf = 0;
 610
 611   for (int l1 = 0; l1 < (k + m); l1++) {
 612     map<int, bufferlist> degraded = encoded;
 613     set<int> want_to_decode;
 614     bool err;
 615     degraded.erase(l1);
 616     want_to_decode.insert(l1);
 617     err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 618     EXPECT_EQ(0, err);
 619     cnt_cf++;
 620     for (int l2 = l1 + 1; l2 < (k + m); l2++) {
 621       degraded.erase(l2);
 622       want_to_decode.insert(l2);
 623       err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 624       EXPECT_EQ(0, err);
 625       cnt_cf++;
 626       for (int l3 = l2 + 1; l3 < (k + m); l3++) {
 627         degraded.erase(l3);
 628         want_to_decode.insert(l3);
 629         err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 630         EXPECT_EQ(0, err);
 631         cnt_cf++;
 632         for (int l4 = l3 + 1; l4 < (k + m); l4++) {
 633           degraded.erase(l4);
 634           want_to_decode.insert(l4);
 635           err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 636           EXPECT_EQ(0, err);
 637           degraded[l4] = encoded[l4];
 638           want_to_decode.erase(l4);
 639           cnt_cf++;
 640         }
 641         degraded[l3] = encoded[l3];
 642         want_to_decode.erase(l3);
 643       }
 644       degraded[l2] = encoded[l2];
 645       want_to_decode.erase(l2);
 646     }
 647     degraded[l1] = encoded[l1];
 648     want_to_decode.erase(l1);
 649   }
 650   EXPECT_EQ(2516, cnt_cf);
 651   EXPECT_EQ(2516, tcache.getDecodingTableCacheSize(ErasureCodeIsaDefault::kCauchy));
 652 }
 653
 654 TEST_F(IsaErasureCodeTest, isa_cauchy_cache_trash)
 655 {
 656   // Test all possible failure scenarios and reconstruction cases for
 657   // a (12,4) configuration using the cauchy matrix
 658   ErasureCodeIsaDefault Isa(tcache,ErasureCodeIsaDefault::kCauchy);
 659   ErasureCodeProfile profile;
 660   profile["k"] = "16";
 661   profile["m"] = "4";
 662   profile["technique"] = "cauchy";
 663
 664   Isa.init(profile, &cerr);
 665
 666   const int k = 16;
 667   const int m = 4;
 668
 669 #define LARGE_ENOUGH 2048
 670   bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
 671   in_ptr.zero();
 672   in_ptr.set_length(0);
 673   const char *payload =
 674     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 675     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 676     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 677     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 678     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 679     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 680     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 681     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 682     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 683     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 684     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 685     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 686     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 687     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 688     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 689     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 690     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 691     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 692     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 693     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 694     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 695     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 696     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 697     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 698     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
 699   in_ptr.append(payload, strlen(payload));
 700   bufferlist in;
 701   in.push_back(in_ptr);
 702
 703   set<int>want_to_encode;
 704
 705   map<int, bufferlist> encoded;
 706   for (int i = 0; i < (k + m); i++) {
 707     want_to_encode.insert(i);
 708   }
 709
 710
 711   EXPECT_EQ(0, Isa.encode(want_to_encode,
 712                           in,
 713                           &encoded));
 714
 715   EXPECT_EQ((unsigned) (k + m), encoded.size());
 716
 717   unsigned length = encoded[0].length();
 718
 719   for (int i = 0; i < k; i++) {
 720     EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
 721   }
 722
 723   buffer::ptr enc[k + m];
 724   // create buffers with a copy of the original data to be able to compare it after decoding
 725   {
 726     for (int i = 0; i < (k + m); i++) {
 727       buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
 728       enc[i] = newenc;
 729       enc[i].zero();
 730       enc[i].set_length(0);
 731       enc[i].append(encoded[i].c_str(), length);
 732     }
 733   }
 734
 735   // loop through all possible loss scenarios
 736   int cnt_cf = 0;
 737
 738   for (int l1 = 0; l1 < (k + m); l1++) {
 739     map<int, bufferlist> degraded = encoded;
 740     set<int> want_to_decode;
 741     bool err;
 742     degraded.erase(l1);
 743     want_to_decode.insert(l1);
 744     err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 745     EXPECT_EQ(0, err);
 746     cnt_cf++;
 747     for (int l2 = l1 + 1; l2 < (k + m); l2++) {
 748       degraded.erase(l2);
 749       want_to_decode.insert(l2);
 750       err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 751       EXPECT_EQ(0, err);
 752       cnt_cf++;
 753       for (int l3 = l2 + 1; l3 < (k + m); l3++) {
 754         degraded.erase(l3);
 755         want_to_decode.insert(l3);
 756         err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 757         EXPECT_EQ(0, err);
 758         cnt_cf++;
 759         for (int l4 = l3 + 1; l4 < (k + m); l4++) {
 760           degraded.erase(l4);
 761           want_to_decode.insert(l4);
 762           err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 763           EXPECT_EQ(0, err);
 764           degraded[l4] = encoded[l4];
 765           want_to_decode.erase(l4);
 766           cnt_cf++;
 767         }
 768         degraded[l3] = encoded[l3];
 769         want_to_decode.erase(l3);
 770       }
 771       degraded[l2] = encoded[l2];
 772       want_to_decode.erase(l2);
 773     }
 774     degraded[l1] = encoded[l1];
 775     want_to_decode.erase(l1);
 776   }
 777   EXPECT_EQ(6195, cnt_cf);
 778   EXPECT_EQ(2516, tcache.getDecodingTableCacheSize(ErasureCodeIsaDefault::kCauchy));
 779 }
 780
 781 TEST_F(IsaErasureCodeTest, isa_xor_codec)
 782 {
 783   // Test all possible failure scenarios and reconstruction cases for
 784   // a (4,1) RAID-5 like configuration
 785
 786   ErasureCodeIsaDefault Isa(tcache);
 787   ErasureCodeProfile profile;
 788   profile["k"] = "4";
 789   profile["m"] = "1";
 790   Isa.init(profile, &cerr);
 791
 792   const int k = 4;
 793   const int m = 1;
 794
 795 #define LARGE_ENOUGH 2048
 796   bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
 797   in_ptr.zero();
 798   in_ptr.set_length(0);
 799   const char *payload =
 800     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 801     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 802     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 803     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 804     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 805     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 806     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 807     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 808     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 809     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 810     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 811     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 812     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 813     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 814     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 815     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 816     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 817     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 818     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 819     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 820     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 821     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 822     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 823     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
 824     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
 825   in_ptr.append(payload, strlen(payload));
 826   bufferlist in;
 827   in.push_back(in_ptr);
 828
 829   set<int>want_to_encode;
 830
 831   map<int, bufferlist> encoded;
 832   for (int i = 0; i < (k + m); i++) {
 833     want_to_encode.insert(i);
 834   }
 835
 836
 837   EXPECT_EQ(0, Isa.encode(want_to_encode,
 838                           in,
 839                           &encoded));
 840
 841   EXPECT_EQ((unsigned) (k + m), encoded.size());
 842
 843   unsigned length = encoded[0].length();
 844
 845   for (int i = 0; i < k; i++) {
 846     EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
 847   }
 848
 849   buffer::ptr enc[k + m];
 850   // create buffers with a copy of the original data to be able to compare it after decoding
 851   {
 852     for (int i = 0; i < (k + m); i++) {
 853       buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
 854       enc[i] = newenc;
 855       enc[i].zero();
 856       enc[i].set_length(0);
 857       enc[i].append(encoded[i].c_str(), length);
 858     }
 859   }
 860
 861   // loop through all possible loss scenarios
 862   int cnt_cf = 0;
 863
 864   for (int l1 = 0; l1 < (k + m); l1++) {
 865     map<int, bufferlist> degraded = encoded;
 866     set<int> want_to_decode;
 867     bool err;
 868     degraded.erase(l1);
 869     want_to_decode.insert(l1);
 870     err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
 871     EXPECT_EQ(0, err);
 872     cnt_cf++;
 873     degraded[l1] = encoded[l1];
 874     want_to_decode.erase(l1);
 875   }
 876   EXPECT_EQ(5, cnt_cf);
 877 }
 878
 879 TEST_F(IsaErasureCodeTest, create_rule)
 880 {
 881   std::unique_ptr<CrushWrapper> c = std::make_unique<CrushWrapper>();
 882   c->create();
 883   int root_type = 2;
 884   c->set_type_name(root_type, "root");
 885   int host_type = 1;
 886   c->set_type_name(host_type, "host");
 887   int osd_type = 0;
 888   c->set_type_name(osd_type, "osd");
 889
 890   int rootno;
 891   c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
 892                 root_type, 0, NULL, NULL, &rootno);
 893   c->set_item_name(rootno, "default");
 894
 895   map<string,string> loc;
 896   loc["root"] = "default";
 897
 898   int num_host = 4;
 899   int num_osd = 5;
 900   int osd = 0;
 901   for (int h=0; h<num_host; ++h) {
 902     loc["host"] = string("host-") + stringify(h);
 903     for (int o=0; o<num_osd; ++o, ++osd) {
 904       c->insert_item(g_ceph_context, osd, 1.0, string("osd.") + stringify(osd), loc);
 905     }
 906   }
 907
 908   c->finalize();
 909
 910   {
 911     stringstream ss;
 912     ErasureCodeIsaDefault isa(tcache);
 913     ErasureCodeProfile profile;
 914     profile["k"] = "2";
 915     profile["m"] = "2";
 916     profile["w"] = "8";
 917     isa.init(profile, &cerr);
 918     int rule = isa.create_rule("myrule", *c, &ss);
 919     EXPECT_EQ(0, rule);
 920     EXPECT_EQ(-EEXIST, isa.create_rule("myrule", *c, &ss));
 921     //
 922     // the minimum that is expected from the created rule is to
 923     // successfully map get_chunk_count() devices from the crushmap,
 924     // at least once.
 925     //
 926     vector<__u32> weight(c->get_max_devices(), 0x10000);
 927     vector<int> out;
 928     int x = 0;
 929     c->do_rule(rule, x, out, isa.get_chunk_count(), weight, 0);
 930     ASSERT_EQ(out.size(), isa.get_chunk_count());
 931     for (unsigned i=0; i<out.size(); ++i)
 932       ASSERT_NE(CRUSH_ITEM_NONE, out[i]);
 933   }
 934   {
 935     stringstream ss;
 936     ErasureCodeIsaDefault isa(tcache);
 937     ErasureCodeProfile profile;
 938     profile["k"] = "2";
 939     profile["m"] = "2";
 940     profile["w"] = "8";
 941     profile["crush-root"] = "BAD";
 942     isa.init(profile, &cerr);
 943     EXPECT_EQ(-ENOENT, isa.create_rule("otherrule", *c, &ss));
 944     EXPECT_EQ("root item BAD does not exist", ss.str());
 945   }
 946   {
 947     stringstream ss;
 948     ErasureCodeIsaDefault isa(tcache);
 949     ErasureCodeProfile profile;
 950     profile["k"] = "2";
 951     profile["m"] = "2";
 952     profile["w"] = "8";
 953     profile["crush-failure-domain"] = "WORSE";
 954     isa.init(profile, &cerr);
 955     EXPECT_EQ(-EINVAL, isa.create_rule("otherrule", *c, &ss));
 956     EXPECT_EQ("unknown type WORSE", ss.str());
 957   }
 958 }
 959
 960 /*
 961  * Local Variables:
 962  * compile-command: "cd ../.. ; make -j4 unittest_erasure_code_isa &&
 963  *   libtool --mode=execute valgrind --tool=memcheck \
 964  *      ./unittest_erasure_code_isa \
 965  *      --gtest_filter=*.* --log-to-stderr=true --debug-osd=20"
 966  * End:
 967  */