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