src/ceph/src/test/erasure-code/TestErasureCodeJerasure.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 distributed storage system
   5  *
   6  * Copyright (C) 2013,2014 Cloudwatt <libre.licensing@cloudwatt.com>
   7  * Copyright (C) 2014 Red Hat <contact@redhat.com>
   8  *
   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/jerasure/ErasureCodeJerasure.h"
  24 #include "global/global_context.h"
  25 #include "common/config.h"
  26 #include "gtest/gtest.h"
  27
  28
  29 template <typename T>
  30 class ErasureCodeTest : public ::testing::Test {
  31  public:
  32 };
  33
  34 typedef ::testing::Types<
  35   ErasureCodeJerasureReedSolomonVandermonde,
  36   ErasureCodeJerasureReedSolomonRAID6,
  37   ErasureCodeJerasureCauchyOrig,
  38   ErasureCodeJerasureCauchyGood,
  39   ErasureCodeJerasureLiberation,
  40   ErasureCodeJerasureBlaumRoth,
  41   ErasureCodeJerasureLiber8tion
  42 > JerasureTypes;
  43 TYPED_TEST_CASE(ErasureCodeTest, JerasureTypes);
  44
  45 TYPED_TEST(ErasureCodeTest, sanity_check_k)
  46 {
  47   TypeParam jerasure;
  48   ErasureCodeProfile profile;
  49   profile["k"] = "1";
  50   profile["m"] = "1";
  51   profile["packetsize"] = "8";
  52   ostringstream errors;
  53   EXPECT_EQ(-EINVAL, jerasure.init(profile, &errors));
  54   EXPECT_NE(std::string::npos, errors.str().find("must be >= 2"));
  55 }
  56
  57 TYPED_TEST(ErasureCodeTest, encode_decode)
  58 {
  59   const char *per_chunk_alignments[] = { "false", "true" };
  60   for (int per_chunk_alignment = 0 ;
  61        per_chunk_alignment < 2;
  62        per_chunk_alignment++) {
  63     TypeParam jerasure;
  64     ErasureCodeProfile profile;
  65     profile["k"] = "2";
  66     profile["m"] = "2";
  67     profile["packetsize"] = "8";
  68     profile["jerasure-per-chunk-alignment"] =
  69       per_chunk_alignments[per_chunk_alignment];
  70     jerasure.init(profile, &cerr);
  71
  72 #define LARGE_ENOUGH 2048
  73     bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
  74     in_ptr.zero();
  75     in_ptr.set_length(0);
  76     const char *payload =
  77       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
  78       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
  79       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
  80       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
  81       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
  82     in_ptr.append(payload, strlen(payload));
  83     bufferlist in;
  84     in.push_front(in_ptr);
  85     int want_to_encode[] = { 0, 1, 2, 3 };
  86     map<int, bufferlist> encoded;
  87     EXPECT_EQ(0, jerasure.encode(set<int>(want_to_encode, want_to_encode+4),
  88                                  in,
  89                                  &encoded));
  90     EXPECT_EQ(4u, encoded.size());
  91     unsigned length =  encoded[0].length();
  92     EXPECT_EQ(0, memcmp(encoded[0].c_str(), in.c_str(), length));
  93     EXPECT_EQ(0, memcmp(encoded[1].c_str(), in.c_str() + length,
  94                         in.length() - length));
  95
  96
  97     // all chunks are available
  98     {
  99       int want_to_decode[] = { 0, 1 };
 100       map<int, bufferlist> decoded;
 101       EXPECT_EQ(0, jerasure.decode(set<int>(want_to_decode, want_to_decode+2),
 102                                    encoded,
 103                                    &decoded));
 104       EXPECT_EQ(2u, decoded.size());
 105       EXPECT_EQ(length, decoded[0].length());
 106       EXPECT_EQ(0, memcmp(decoded[0].c_str(), in.c_str(), length));
 107       EXPECT_EQ(0, memcmp(decoded[1].c_str(), in.c_str() + length,
 108                           in.length() - length));
 109     }
 110
 111     // two chunks are missing
 112     {
 113       map<int, bufferlist> degraded = encoded;
 114       degraded.erase(0);
 115       degraded.erase(1);
 116       EXPECT_EQ(2u, degraded.size());
 117       int want_to_decode[] = { 0, 1 };
 118       map<int, bufferlist> decoded;
 119       EXPECT_EQ(0, jerasure.decode(set<int>(want_to_decode, want_to_decode+2),
 120                                    degraded,
 121                                    &decoded));
 122       // always decode all, regardless of want_to_decode
 123       EXPECT_EQ(4u, decoded.size());
 124       EXPECT_EQ(length, decoded[0].length());
 125       EXPECT_EQ(0, memcmp(decoded[0].c_str(), in.c_str(), length));
 126       EXPECT_EQ(0, memcmp(decoded[1].c_str(), in.c_str() + length,
 127                           in.length() - length));
 128     }
 129   }
 130 }
 131
 132 TYPED_TEST(ErasureCodeTest, minimum_to_decode)
 133 {
 134   TypeParam jerasure;
 135   ErasureCodeProfile profile;
 136   profile["k"] = "2";
 137   profile["m"] = "2";
 138   profile["w"] = "7";
 139   profile["packetsize"] = "8";
 140   jerasure.init(profile, &cerr);
 141
 142   //
 143   // If trying to read nothing, the minimum is empty.
 144   //
 145   {
 146     set<int> want_to_read;
 147     set<int> available_chunks;
 148     set<int> minimum;
 149
 150     EXPECT_EQ(0, jerasure.minimum_to_decode(want_to_read,
 151                                             available_chunks,
 152                                             &minimum));
 153     EXPECT_TRUE(minimum.empty());
 154   }
 155   //
 156   // There is no way to read a chunk if none are available.
 157   //
 158   {
 159     set<int> want_to_read;
 160     set<int> available_chunks;
 161     set<int> minimum;
 162
 163     want_to_read.insert(0);
 164
 165     EXPECT_EQ(-EIO, jerasure.minimum_to_decode(want_to_read,
 166                                                available_chunks,
 167                                                &minimum));
 168   }
 169   //
 170   // Reading a subset of the available chunks is always possible.
 171   //
 172   {
 173     set<int> want_to_read;
 174     set<int> available_chunks;
 175     set<int> minimum;
 176
 177     want_to_read.insert(0);
 178     available_chunks.insert(0);
 179
 180     EXPECT_EQ(0, jerasure.minimum_to_decode(want_to_read,
 181                                             available_chunks,
 182                                             &minimum));
 183     EXPECT_EQ(want_to_read, minimum);
 184   }
 185   //
 186   // There is no way to read a missing chunk if there is less than k
 187   // chunks available.
 188   //
 189   {
 190     set<int> want_to_read;
 191     set<int> available_chunks;
 192     set<int> minimum;
 193
 194     want_to_read.insert(0);
 195     want_to_read.insert(1);
 196     available_chunks.insert(0);
 197
 198     EXPECT_EQ(-EIO, jerasure.minimum_to_decode(want_to_read,
 199                                                available_chunks,
 200                                                &minimum));
 201   }
 202   //
 203   // When chunks are not available, the minimum can be made of any
 204   // chunks. For instance, to read 1 and 3 below the minimum could be
 205   // 2 and 3 which may seem better because it contains one of the
 206   // chunks to be read. But it won't be more efficient than retrieving
 207   // 0 and 2 instead because, in both cases, the decode function will
 208   // need to run the same recovery operation and use the same amount
 209   // of CPU and memory.
 210   //
 211   {
 212     set<int> want_to_read;
 213     set<int> available_chunks;
 214     set<int> minimum;
 215
 216     want_to_read.insert(1);
 217     want_to_read.insert(3);
 218     available_chunks.insert(0);
 219     available_chunks.insert(2);
 220     available_chunks.insert(3);
 221
 222     EXPECT_EQ(0, jerasure.minimum_to_decode(want_to_read,
 223                                             available_chunks,
 224                                             &minimum));
 225     EXPECT_EQ(2u, minimum.size());
 226     EXPECT_EQ(0u, minimum.count(3));
 227   }
 228 }
 229
 230 TEST(ErasureCodeTest, encode)
 231 {
 232   ErasureCodeJerasureReedSolomonVandermonde jerasure;
 233   ErasureCodeProfile profile;
 234   profile["k"] = "2";
 235   profile["m"] = "2";
 236   profile["w"] = "8";
 237   jerasure.init(profile, &cerr);
 238
 239   unsigned aligned_object_size = jerasure.get_alignment() * 2;
 240   {
 241     //
 242     // When the input bufferlist needs to be padded because
 243     // it is not properly aligned, it is padded with zeros.
 244     //
 245     bufferlist in;
 246     map<int,bufferlist> encoded;
 247     int want_to_encode[] = { 0, 1, 2, 3 };
 248     int trail_length = 1;
 249     in.append(string(aligned_object_size + trail_length, 'X'));
 250     EXPECT_EQ(0, jerasure.encode(set<int>(want_to_encode, want_to_encode+4),
 251                                  in,
 252                                  &encoded));
 253     EXPECT_EQ(4u, encoded.size());
 254     char *last_chunk = encoded[1].c_str();
 255     int length =encoded[1].length();
 256     EXPECT_EQ('X', last_chunk[0]);
 257     EXPECT_EQ('\0', last_chunk[length - trail_length]);
 258   }
 259
 260   {
 261     //
 262     // When only the first chunk is required, the encoded map only
 263     // contains the first chunk. Although the jerasure encode
 264     // internally allocated a buffer because of padding requirements
 265     // and also computes the coding chunks, they are released before
 266     // the return of the method, as shown when running the tests thru
 267     // valgrind (there is no leak).
 268     //
 269     bufferlist in;
 270     map<int,bufferlist> encoded;
 271     set<int> want_to_encode;
 272     want_to_encode.insert(0);
 273     int trail_length = 1;
 274     in.append(string(aligned_object_size + trail_length, 'X'));
 275     EXPECT_EQ(0, jerasure.encode(want_to_encode, in, &encoded));
 276     EXPECT_EQ(1u, encoded.size());
 277   }
 278 }
 279
 280 TEST(ErasureCodeTest, create_rule)
 281 {
 282   CrushWrapper *c = new CrushWrapper;
 283   c->create();
 284   int root_type = 2;
 285   c->set_type_name(root_type, "root");
 286   int host_type = 1;
 287   c->set_type_name(host_type, "host");
 288   int osd_type = 0;
 289   c->set_type_name(osd_type, "osd");
 290
 291   int rootno;
 292   c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
 293                 root_type, 0, NULL, NULL, &rootno);
 294   c->set_item_name(rootno, "default");
 295
 296   map<string,string> loc;
 297   loc["root"] = "default";
 298
 299   int num_host = 4;
 300   int num_osd = 5;
 301   int osd = 0;
 302   for (int h=0; h<num_host; ++h) {
 303     loc["host"] = string("host-") + stringify(h);
 304     for (int o=0; o<num_osd; ++o, ++osd) {
 305       c->insert_item(g_ceph_context, osd, 1.0, string("osd.") + stringify(osd), loc);
 306     }
 307   }
 308
 309   c->finalize();
 310
 311   {
 312     stringstream ss;
 313     ErasureCodeJerasureReedSolomonVandermonde jerasure;
 314     ErasureCodeProfile profile;
 315     profile["k"] = "2";
 316     profile["m"] = "2";
 317     profile["w"] = "8";
 318     jerasure.init(profile, &cerr);
 319     int ruleset = jerasure.create_rule("myrule", *c, &ss);
 320     EXPECT_EQ(0, ruleset);
 321     EXPECT_EQ(-EEXIST, jerasure.create_rule("myrule", *c, &ss));
 322     //
 323     // the minimum that is expected from the created ruleset is to
 324     // successfully map get_chunk_count() devices from the crushmap,
 325     // at least once.
 326     //
 327     vector<__u32> weight(c->get_max_devices(), 0x10000);
 328     vector<int> out;
 329     int x = 0;
 330     c->do_rule(ruleset, x, out, jerasure.get_chunk_count(), weight, 0);
 331     ASSERT_EQ(out.size(), jerasure.get_chunk_count());
 332     for (unsigned i=0; i<out.size(); ++i)
 333       ASSERT_NE(CRUSH_ITEM_NONE, out[i]);
 334   }
 335   {
 336     stringstream ss;
 337     ErasureCodeJerasureReedSolomonVandermonde jerasure;
 338     ErasureCodeProfile profile;
 339     profile["k"] = "2";
 340     profile["m"] = "2";
 341     profile["w"] = "8";
 342     profile["crush-root"] = "BAD";
 343     jerasure.init(profile, &cerr);
 344     EXPECT_EQ(-ENOENT, jerasure.create_rule("otherrule", *c, &ss));
 345     EXPECT_EQ("root item BAD does not exist", ss.str());
 346   }
 347   {
 348     stringstream ss;
 349     ErasureCodeJerasureReedSolomonVandermonde jerasure;
 350     ErasureCodeProfile profile;
 351     profile["k"] = "2";
 352     profile["m"] = "2";
 353     profile["w"] = "8";
 354     profile["crush-failure-domain"] = "WORSE";
 355     jerasure.init(profile, &cerr);
 356     EXPECT_EQ(-EINVAL, jerasure.create_rule("otherrule", *c, &ss));
 357     EXPECT_EQ("unknown type WORSE", ss.str());
 358   }
 359 }
 360
 361 /*
 362  * Local Variables:
 363  * compile-command: "cd ../.. ;
 364  *   make -j4 unittest_erasure_code_jerasure &&
 365  *   valgrind --tool=memcheck \
 366  *      ./unittest_erasure_code_jerasure \
 367  *      --gtest_filter=*.* --log-to-stderr=true --debug-osd=20"
 368  * End:
 369  */