ceph/src/test/erasure-code/TestErasureCodeLrc.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) 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/lrc/ErasureCodeLrc.h"
  24 #include "global/global_context.h"
  25 #include "common/config_proxy.h"
  26 #include "gtest/gtest.h"
  27
  28 using namespace std;
  29
  30 TEST(ErasureCodeLrc, parse_rule)
  31 {
  32   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
  33   EXPECT_EQ("default", lrc.rule_root);
  34   EXPECT_EQ("host", lrc.rule_steps.front().type);
  35
  36   ErasureCodeProfile profile;
  37   profile["crush-root"] = "other";
  38   EXPECT_EQ(0, lrc.parse_rule(profile, &cerr));
  39   EXPECT_EQ("other", lrc.rule_root);
  40
  41   profile["crush-steps"] = "[]";
  42   EXPECT_EQ(0, lrc.parse_rule(profile, &cerr));
  43   EXPECT_TRUE(lrc.rule_steps.empty());
  44
  45   profile["crush-steps"] = "0";
  46   EXPECT_EQ(ERROR_LRC_ARRAY, lrc.parse_rule(profile, &cerr));
  47
  48   profile["crush-steps"] = "{";
  49   EXPECT_EQ(ERROR_LRC_PARSE_JSON, lrc.parse_rule(profile, &cerr));
  50
  51   profile["crush-steps"] = "[0]";
  52   EXPECT_EQ(ERROR_LRC_ARRAY, lrc.parse_rule(profile, &cerr));
  53
  54   profile["crush-steps"] = "[[0]]";
  55   EXPECT_EQ(ERROR_LRC_RULE_OP, lrc.parse_rule(profile, &cerr));
  56
  57   profile["crush-steps"] = "[[\"choose\", 0]]";
  58   EXPECT_EQ(ERROR_LRC_RULE_TYPE, lrc.parse_rule(profile, &cerr));
  59
  60   profile["crush-steps"] = "[[\"choose\", \"host\", []]]";
  61   EXPECT_EQ(ERROR_LRC_RULE_N, lrc.parse_rule(profile, &cerr));
  62
  63   profile["crush-steps"] = "[[\"choose\", \"host\", 2]]";
  64   EXPECT_EQ(0, lrc.parse_rule(profile, &cerr));
  65
  66   const ErasureCodeLrc::Step &step = lrc.rule_steps.front();
  67   EXPECT_EQ("choose", step.op);
  68   EXPECT_EQ("host", step.type);
  69   EXPECT_EQ(2, step.n);
  70
  71   profile["crush-steps"] =
  72     "["
  73     " [\"choose\", \"rack\", 2], "
  74     " [\"chooseleaf\", \"host\", 5], "
  75     "]";
  76   EXPECT_EQ(0, lrc.parse_rule(profile, &cerr));
  77   EXPECT_EQ(2U, lrc.rule_steps.size());
  78   {
  79     const ErasureCodeLrc::Step &step = lrc.rule_steps[0];
  80     EXPECT_EQ("choose", step.op);
  81     EXPECT_EQ("rack", step.type);
  82     EXPECT_EQ(2, step.n);
  83   }
  84   {
  85     const ErasureCodeLrc::Step &step = lrc.rule_steps[1];
  86     EXPECT_EQ("chooseleaf", step.op);
  87     EXPECT_EQ("host", step.type);
  88     EXPECT_EQ(5, step.n);
  89   }
  90 }
  91
  92 TEST(ErasureCodeTest, create_rule)
  93 {
  94   CrushWrapper *c = new CrushWrapper;
  95   c->create();
  96   int root_type = 3;
  97   c->set_type_name(root_type, "root");
  98   int rack_type = 2;
  99   c->set_type_name(rack_type, "rack");
 100   int host_type = 1;
 101   c->set_type_name(host_type, "host");
 102   int osd_type = 0;
 103   c->set_type_name(osd_type, "osd");
 104
 105   int rootno;
 106   c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
 107                 root_type, 0, NULL, NULL, &rootno);
 108   c->set_item_name(rootno, "default");
 109
 110   map<string,string> loc;
 111   loc["root"] = "default";
 112
 113   //
 114   // Set all to 10 so that the item number it trivial to decompose
 115   // into rack/host/osd.
 116   //
 117   int num_rack;
 118   int num_host;
 119   int num_osd;
 120   num_rack = num_host = num_osd = 10;
 121   int osd = 0;
 122   for (int r=0; r<num_rack; ++r) {
 123     loc["rack"] = string("rack-") + stringify(r);
 124     for (int h=0; h<num_host; ++h) {
 125       loc["host"] = string("host-") + stringify(r) + string("-") + stringify(h);
 126       for (int o=0; o<num_osd; ++o, ++osd) {
 127         c->insert_item(g_ceph_context, osd, 1.0, string("osd.") + stringify(osd), loc);
 128       }
 129     }
 130   }
 131
 132   c->finalize();
 133
 134   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 135   EXPECT_EQ(0, lrc.create_rule("rule1", *c, &cerr));
 136
 137   ErasureCodeProfile profile;
 138   unsigned int racks = 2;
 139   unsigned int hosts = 5;
 140   profile["crush-steps"] =
 141     "["
 142     " [\"choose\", \"rack\", " + stringify(racks) + "], "
 143     " [\"chooseleaf\", \"host\", " + stringify(hosts) + "], "
 144     "]";
 145   const char *rule_name = "rule2";
 146   EXPECT_EQ(0, lrc.parse_rule(profile, &cerr));
 147   EXPECT_EQ(1, lrc.create_rule(rule_name, *c, &cerr));
 148
 149   vector<__u32> weight;
 150   for (int o = 0; o < c->get_max_devices(); o++)
 151     weight.push_back(0x10000);
 152   int rule = c->get_rule_id(rule_name);
 153   vector<int> out;
 154   unsigned int n = racks * hosts;
 155   c->do_rule(rule, 1, out, n, weight, 0);
 156   EXPECT_EQ(n, out.size());
 157   //
 158   // check that the first five are in the same rack and the next five
 159   // in the same rack
 160   //
 161   int first_rack = out[0] / num_host / num_osd;
 162   EXPECT_EQ(first_rack, out[1] / num_host / num_osd);
 163   EXPECT_EQ(first_rack, out[2] / num_host / num_osd);
 164   EXPECT_EQ(first_rack, out[3] / num_host / num_osd);
 165   EXPECT_EQ(first_rack, out[4] / num_host / num_osd);
 166   int second_rack = out[5] / num_host / num_osd;
 167   EXPECT_EQ(second_rack, out[6] / num_host / num_osd);
 168   EXPECT_EQ(second_rack, out[7] / num_host / num_osd);
 169   EXPECT_EQ(second_rack, out[8] / num_host / num_osd);
 170   EXPECT_EQ(second_rack, out[9] / num_host / num_osd);
 171 }
 172
 173 TEST(ErasureCodeLrc, parse_kml)
 174 {
 175   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 176   ErasureCodeProfile profile;
 177   EXPECT_EQ(0, lrc.parse_kml(profile, &cerr));
 178   profile["k"] = "4";
 179   EXPECT_EQ(ERROR_LRC_ALL_OR_NOTHING, lrc.parse_kml(profile, &cerr));
 180   const char *generated[] = { "mapping",
 181                               "layers",
 182                               "crush-steps" };
 183   profile["m"] = "2";
 184   profile["l"] = "3";
 185
 186   for (int i = 0; i < 3; i++) {
 187     profile[generated[i]] = "SET";
 188     EXPECT_EQ(ERROR_LRC_GENERATED, lrc.parse_kml(profile, &cerr));
 189     profile.erase(profile.find(generated[i]));
 190   }
 191
 192   profile["k"] = "4";
 193   profile["m"] = "2";
 194   profile["l"] = "7";
 195   EXPECT_EQ(ERROR_LRC_K_M_MODULO, lrc.parse_kml(profile, &cerr));
 196
 197   profile["k"] = "3";
 198   profile["m"] = "3";
 199   profile["l"] = "3";
 200   EXPECT_EQ(ERROR_LRC_K_MODULO, lrc.parse_kml(profile, &cerr));
 201
 202   profile["k"] = "4";
 203   profile["m"] = "2";
 204   profile["l"] = "3";
 205   EXPECT_EQ(0, lrc.parse_kml(profile, &cerr));
 206   EXPECT_EQ("[ "
 207             " [ \"DDc_DDc_\", \"\" ],"
 208             " [ \"DDDc____\", \"\" ],"
 209             " [ \"____DDDc\", \"\" ],"
 210             "]", profile["layers"]);
 211   EXPECT_EQ("DD__DD__", profile["mapping"]);
 212   EXPECT_EQ("chooseleaf", lrc.rule_steps[0].op);
 213   EXPECT_EQ("host", lrc.rule_steps[0].type);
 214   EXPECT_EQ(0, lrc.rule_steps[0].n);
 215   EXPECT_EQ(1U, lrc.rule_steps.size());
 216   profile.erase(profile.find("mapping"));
 217   profile.erase(profile.find("layers"));
 218
 219   profile["k"] = "4";
 220   profile["m"] = "2";
 221   profile["l"] = "3";
 222   profile["crush-failure-domain"] = "osd";
 223   EXPECT_EQ(0, lrc.parse_kml(profile, &cerr));
 224   EXPECT_EQ("chooseleaf", lrc.rule_steps[0].op);
 225   EXPECT_EQ("osd", lrc.rule_steps[0].type);
 226   EXPECT_EQ(0, lrc.rule_steps[0].n);
 227   EXPECT_EQ(1U, lrc.rule_steps.size());
 228   profile.erase(profile.find("mapping"));
 229   profile.erase(profile.find("layers"));
 230
 231   profile["k"] = "4";
 232   profile["m"] = "2";
 233   profile["l"] = "3";
 234   profile["crush-failure-domain"] = "osd";
 235   profile["crush-locality"] = "rack";
 236   EXPECT_EQ(0, lrc.parse_kml(profile, &cerr));
 237   EXPECT_EQ("choose", lrc.rule_steps[0].op);
 238   EXPECT_EQ("rack", lrc.rule_steps[0].type);
 239   EXPECT_EQ(2, lrc.rule_steps[0].n);
 240   EXPECT_EQ("chooseleaf", lrc.rule_steps[1].op);
 241   EXPECT_EQ("osd", lrc.rule_steps[1].type);
 242   EXPECT_EQ(4, lrc.rule_steps[1].n);
 243   EXPECT_EQ(2U, lrc.rule_steps.size());
 244   profile.erase(profile.find("mapping"));
 245   profile.erase(profile.find("layers"));
 246 }
 247
 248 TEST(ErasureCodeLrc, layers_description)
 249 {
 250   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 251   ErasureCodeProfile profile;
 252
 253   json_spirit::mArray description;
 254   EXPECT_EQ(ERROR_LRC_DESCRIPTION,
 255             lrc.layers_description(profile, &description, &cerr));
 256
 257   {
 258     const char *description_string = "\"not an array\"";
 259     profile["layers"] = description_string;
 260     EXPECT_EQ(ERROR_LRC_ARRAY,
 261               lrc.layers_description(profile, &description, &cerr));
 262   }
 263   {
 264     const char *description_string = "invalid json";
 265     profile["layers"] = description_string;
 266     EXPECT_EQ(ERROR_LRC_PARSE_JSON,
 267               lrc.layers_description(profile, &description, &cerr));
 268   }
 269   {
 270     const char *description_string = "[]";
 271     profile["layers"] = description_string;
 272     EXPECT_EQ(0, lrc.layers_description(profile, &description, &cerr));
 273   }
 274 }
 275
 276 TEST(ErasureCodeLrc, layers_parse)
 277 {
 278   {
 279     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 280     ErasureCodeProfile profile;
 281
 282     const char *description_string ="[ 0 ]";
 283     profile["layers"] = description_string;
 284     json_spirit::mArray description;
 285     EXPECT_EQ(0, lrc.layers_description(profile, &description, &cerr));
 286     EXPECT_EQ(ERROR_LRC_ARRAY,
 287               lrc.layers_parse(description_string, description, &cerr));
 288   }
 289
 290   {
 291     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 292     ErasureCodeProfile profile;
 293
 294     const char *description_string ="[ [ 0 ] ]";
 295     profile["layers"] = description_string;
 296     json_spirit::mArray description;
 297     EXPECT_EQ(0, lrc.layers_description(profile, &description, &cerr));
 298     EXPECT_EQ(ERROR_LRC_STR,
 299               lrc.layers_parse(description_string, description, &cerr));
 300   }
 301
 302   {
 303     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 304     ErasureCodeProfile profile;
 305
 306     const char *description_string ="[ [ \"\", 0 ] ]";
 307     profile["layers"] = description_string;
 308     json_spirit::mArray description;
 309     EXPECT_EQ(0, lrc.layers_description(profile, &description, &cerr));
 310     EXPECT_EQ(ERROR_LRC_CONFIG_OPTIONS,
 311               lrc.layers_parse(description_string, description, &cerr));
 312   }
 313
 314   //
 315   // The second element can be an object describing the plugin
 316   // profile.
 317   //
 318   {
 319     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 320     ErasureCodeProfile profile;
 321
 322     const char *description_string ="[ [ \"\", { \"a\": \"b\" }, \"ignored\" ] ]";
 323     profile["layers"] = description_string;
 324     json_spirit::mArray description;
 325     EXPECT_EQ(0, lrc.layers_description(profile, &description, &cerr));
 326     EXPECT_EQ(0, lrc.layers_parse(description_string, description, &cerr));
 327     EXPECT_EQ("b", lrc.layers.front().profile["a"]);
 328   }
 329
 330   //
 331   // The second element can be a str_map parseable string describing the plugin
 332   // profile.
 333   //
 334   {
 335     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 336     ErasureCodeProfile profile;
 337
 338     const char *description_string ="[ [ \"\", \"a=b c=d\" ] ]";
 339     profile["layers"] = description_string;
 340     json_spirit::mArray description;
 341     EXPECT_EQ(0, lrc.layers_description(profile, &description, &cerr));
 342     EXPECT_EQ(0, lrc.layers_parse(description_string, description, &cerr));
 343     EXPECT_EQ("b", lrc.layers.front().profile["a"]);
 344     EXPECT_EQ("d", lrc.layers.front().profile["c"]);
 345   }
 346
 347 }
 348
 349 TEST(ErasureCodeLrc, layers_sanity_checks)
 350 {
 351   {
 352     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 353     ErasureCodeProfile profile;
 354     profile["mapping"] =
 355             "__DDD__DD";
 356     const char *description_string =
 357       "[ "
 358       "  [ \"_cDDD_cDD\", \"\" ],"
 359       "  [ \"c_DDD____\", \"\" ],"
 360       "  [ \"_____cDDD\", \"\" ],"
 361       "]";
 362     profile["layers"] = description_string;
 363     EXPECT_EQ(0, lrc.init(profile, &cerr));
 364   }
 365   {
 366     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 367     ErasureCodeProfile profile;
 368     const char *description_string =
 369       "[ "
 370       "]";
 371     profile["layers"] = description_string;
 372     EXPECT_EQ(ERROR_LRC_MAPPING, lrc.init(profile, &cerr));
 373   }
 374   {
 375     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 376     ErasureCodeProfile profile;
 377     profile["mapping"] = "";
 378     const char *description_string =
 379       "[ "
 380       "]";
 381     profile["layers"] = description_string;
 382     EXPECT_EQ(ERROR_LRC_LAYERS_COUNT, lrc.init(profile, &cerr));
 383   }
 384   {
 385     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 386     ErasureCodeProfile profile;
 387     profile["mapping"] =
 388             "DD";
 389     const char *description_string =
 390       "[ "
 391       "  [ \"DD??\", \"\" ], "
 392       "  [ \"DD\", \"\" ], "
 393       "  [ \"DD\", \"\" ], "
 394       "]";
 395     profile["layers"] = description_string;
 396     EXPECT_EQ(-EINVAL, lrc.init(profile, &cerr));
 397   }
 398 }
 399
 400 TEST(ErasureCodeLrc, layers_init)
 401 {
 402   {
 403     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 404     ErasureCodeProfile profile;
 405
 406     const char* env = getenv("CEPH_LIB");
 407     string directory(env ? env : "lib");
 408     string description_string =
 409       "[ "
 410       "  [ \"_cDDD_cDD_\", \"directory=" + directory + "\" ],"
 411       "]";
 412     profile["layers"] = description_string;
 413     json_spirit::mArray description;
 414     EXPECT_EQ(0, lrc.layers_description(profile, &description, &cerr));
 415     EXPECT_EQ(0, lrc.layers_parse(description_string, description, &cerr));
 416     EXPECT_EQ(0, lrc.layers_init(&cerr));
 417     EXPECT_EQ("5", lrc.layers.front().profile["k"]);
 418     EXPECT_EQ("2", lrc.layers.front().profile["m"]);
 419     EXPECT_EQ("jerasure", lrc.layers.front().profile["plugin"]);
 420     EXPECT_EQ("reed_sol_van", lrc.layers.front().profile["technique"]);
 421   }
 422 }
 423
 424 TEST(ErasureCodeLrc, init)
 425 {
 426   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 427   ErasureCodeProfile profile;
 428   profile["mapping"] =
 429     "__DDD__DD";
 430   const char *description_string =
 431     "[ "
 432     "  [ \"_cDDD_cDD\", \"\" ],"
 433     "  [ \"c_DDD____\", \"\" ],"
 434     "  [ \"_____cDDD\", \"\" ],"
 435     "]";
 436   profile["layers"] = description_string;
 437   EXPECT_EQ(0, lrc.init(profile, &cerr));
 438 }
 439
 440 TEST(ErasureCodeLrc, init_kml)
 441 {
 442   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 443   ErasureCodeProfile profile;
 444   profile["k"] = "4";
 445   profile["m"] = "2";
 446   profile["l"] = "3";
 447   EXPECT_EQ(0, lrc.init(profile, &cerr));
 448   EXPECT_EQ((unsigned int)(4 + 2 + (4 + 2) / 3), lrc.get_chunk_count());
 449 }
 450
 451 TEST(ErasureCodeLrc, minimum_to_decode)
 452 {
 453   // trivial : no erasures, the minimum is want_to_read
 454   {
 455     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 456     ErasureCodeProfile profile;
 457     profile["mapping"] =
 458       "__DDD__DD";
 459     const char *description_string =
 460       "[ "
 461       "  [ \"_cDDD_cDD\", \"\" ],"
 462       "  [ \"c_DDD____\", \"\" ],"
 463       "  [ \"_____cDDD\", \"\" ],"
 464       "]";
 465     profile["layers"] = description_string;
 466     EXPECT_EQ(0, lrc.init(profile, &cerr));
 467     set<int> want_to_read;
 468     want_to_read.insert(1);
 469     set<int> available_chunks;
 470     available_chunks.insert(1);
 471     available_chunks.insert(2);
 472     set<int> minimum;
 473     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 474     EXPECT_EQ(want_to_read, minimum);
 475   }
 476   // locally repairable erasure
 477   {
 478     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 479     ErasureCodeProfile profile;
 480     profile["mapping"] =
 481             "__DDD__DD_";
 482     const char *description_string =
 483       "[ "
 484       "  [ \"_cDDD_cDD_\", \"\" ],"
 485       "  [ \"c_DDD_____\", \"\" ],"
 486       "  [ \"_____cDDD_\", \"\" ],"
 487       "  [ \"_____DDDDc\", \"\" ],"
 488       "]";
 489     profile["layers"] = description_string;
 490     EXPECT_EQ(0, lrc.init(profile, &cerr));
 491     EXPECT_EQ(profile["mapping"].length(),
 492               lrc.get_chunk_count());
 493     {
 494       // want to read the last chunk
 495       set<int> want_to_read;
 496       want_to_read.insert(lrc.get_chunk_count() - 1);
 497       // all chunks are available except the last chunk
 498       set<int> available_chunks;
 499       for (int i = 0; i < (int)lrc.get_chunk_count() - 1; i++)
 500         available_chunks.insert(i);
 501       // _____DDDDc can recover c
 502       set<int> minimum;
 503       EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 504       set<int> expected_minimum;
 505       expected_minimum.insert(5);
 506       expected_minimum.insert(6);
 507       expected_minimum.insert(7);
 508       expected_minimum.insert(8);
 509       EXPECT_EQ(expected_minimum, minimum);
 510     }
 511     {
 512       set<int> want_to_read;
 513       want_to_read.insert(0);
 514       set<int> available_chunks;
 515       for (int i = 1; i < (int)lrc.get_chunk_count(); i++)
 516         available_chunks.insert(i);
 517       set<int> minimum;
 518       EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 519       set<int> expected_minimum;
 520       expected_minimum.insert(2);
 521       expected_minimum.insert(3);
 522       expected_minimum.insert(4);
 523       EXPECT_EQ(expected_minimum, minimum);
 524     }
 525   }
 526   // implicit parity required
 527   {
 528     ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 529     ErasureCodeProfile profile;
 530     profile["mapping"] =
 531             "__DDD__DD";
 532     const char *description_string =
 533       "[ "
 534       "  [ \"_cDDD_cDD\", \"\" ],"
 535       "  [ \"c_DDD____\", \"\" ],"
 536       "  [ \"_____cDDD\", \"\" ],"
 537       "]";
 538     profile["layers"] = description_string;
 539     EXPECT_EQ(0, lrc.init(profile, &cerr));
 540     EXPECT_EQ(profile["mapping"].length(),
 541               lrc.get_chunk_count());
 542     set<int> want_to_read;
 543     want_to_read.insert(8);
 544     //
 545     // unable to recover, too many chunks missing
 546     //
 547     {
 548       set<int> available_chunks;
 549       available_chunks.insert(0);
 550       available_chunks.insert(1);
 551       // missing             (2)
 552       // missing             (3)
 553       available_chunks.insert(4);
 554       available_chunks.insert(5);
 555       available_chunks.insert(6);
 556       // missing             (7)
 557       // missing             (8)
 558       set<int> minimum;
 559       EXPECT_EQ(-EIO, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 560     }
 561     //
 562     // We want to read chunk 8 and encoding was done with
 563     //
 564     //     _cDDD_cDD
 565     //     c_DDD____
 566     //     _____cDDD
 567     //
 568     // First strategy fails:
 569     //
 570     // 012345678
 571     // xxXXXxxXX  initial chunks
 572     // xx.XXxx..  missing (2, 7, 8)
 573     // _____cDDD  fail : can recover 1 but 2 are missing
 574     // c_DDD____  ignored because 8 is not used (i.e. _)
 575     // _cDDD_cDD  fail : can recover 2 but 3 are missing
 576     //
 577     // Second strategy succeeds:
 578     //
 579     // 012345678
 580     // xxXXXxxXX  initial chunks
 581     // xx.XXxx..  missing (2, 7, 8)
 582     // _____cDDD  fail : can recover 1 but 2 are missing
 583     // c_DDD____  success: recovers chunk 2
 584     // _cDDD_cDD  success: recovers chunk 7, 8
 585     //
 586     {
 587       set<int> available_chunks;
 588       available_chunks.insert(0);
 589       available_chunks.insert(1);
 590       // missing             (2)
 591       available_chunks.insert(3);
 592       available_chunks.insert(4);
 593       available_chunks.insert(5);
 594       available_chunks.insert(6);
 595       // missing             (7)
 596       // missing             (8)
 597       set<int> minimum;
 598       EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 599       EXPECT_EQ(available_chunks, minimum);
 600     }
 601   }
 602 }
 603
 604 TEST(ErasureCodeLrc, encode_decode)
 605 {
 606   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 607   ErasureCodeProfile profile;
 608   profile["mapping"] =
 609     "__DD__DD";
 610   const char *description_string =
 611     "[ "
 612     "  [ \"_cDD_cDD\", \"\" ]," // global layer
 613     "  [ \"c_DD____\", \"\" ]," // first local layer
 614     "  [ \"____cDDD\", \"\" ]," // second local layer
 615     "]";
 616   profile["layers"] = description_string;
 617   EXPECT_EQ(0, lrc.init(profile, &cerr));
 618   EXPECT_EQ(4U, lrc.get_data_chunk_count());
 619   unsigned int chunk_size = g_conf().get_val<Option::size_t>("osd_pool_erasure_code_stripe_unit");
 620   unsigned int stripe_width = lrc.get_data_chunk_count() * chunk_size;
 621   EXPECT_EQ(chunk_size, lrc.get_chunk_size(stripe_width));
 622   set<int> want_to_encode;
 623   map<int, bufferlist> encoded;
 624   for (unsigned int i = 0; i < lrc.get_chunk_count(); ++i) {
 625     want_to_encode.insert(i);
 626     bufferptr ptr(buffer::create_page_aligned(chunk_size));
 627     bufferlist tmp;
 628     tmp.push_back(ptr);
 629     tmp.claim_append(encoded[i]);
 630     encoded[i].swap(tmp);
 631   }
 632   const vector<int> &mapping = lrc.get_chunk_mapping();
 633   char c = 'A';
 634   for (unsigned int i = 0; i < lrc.get_data_chunk_count(); i++) {
 635     int j = mapping[i];
 636     string s(chunk_size, c);
 637     encoded[j].clear();
 638     encoded[j].append(s);
 639     c++;
 640   }
 641   EXPECT_EQ(0, lrc.encode_chunks(want_to_encode, &encoded));
 642
 643   {
 644     map<int, bufferlist> chunks;
 645     chunks[4] = encoded[4];
 646     chunks[5] = encoded[5];
 647     chunks[6] = encoded[6];
 648     set<int> want_to_read;
 649     want_to_read.insert(7);
 650     set<int> available_chunks;
 651     available_chunks.insert(4);
 652     available_chunks.insert(5);
 653     available_chunks.insert(6);
 654     set<int> minimum;
 655     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 656     // only need three chunks from the second local layer
 657     EXPECT_EQ(3U, minimum.size());
 658     EXPECT_EQ(1U, minimum.count(4));
 659     EXPECT_EQ(1U, minimum.count(5));
 660     EXPECT_EQ(1U, minimum.count(6));
 661     map<int, bufferlist> decoded;
 662     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 663     string s(chunk_size, 'D');
 664     EXPECT_EQ(s, string(decoded[7].c_str(), chunk_size));
 665   }
 666   {
 667     set<int> want_to_read;
 668     want_to_read.insert(2);
 669     map<int, bufferlist> chunks;
 670     chunks[1] = encoded[1];
 671     chunks[3] = encoded[3];
 672     chunks[5] = encoded[5];
 673     chunks[6] = encoded[6];
 674     chunks[7] = encoded[7];
 675     set<int> available_chunks;
 676     available_chunks.insert(1);
 677     available_chunks.insert(3);
 678     available_chunks.insert(5);
 679     available_chunks.insert(6);
 680     available_chunks.insert(7);
 681     set<int> minimum;
 682     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 683     EXPECT_EQ(5U, minimum.size());
 684     EXPECT_EQ(available_chunks, minimum);
 685
 686     map<int, bufferlist> decoded;
 687     EXPECT_EQ(0, lrc._decode(want_to_read, encoded, &decoded));
 688     string s(chunk_size, 'A');
 689     EXPECT_EQ(s, string(decoded[2].c_str(), chunk_size));
 690   }
 691   {
 692     set<int> want_to_read;
 693     want_to_read.insert(3);
 694     want_to_read.insert(6);
 695     want_to_read.insert(7);
 696     set<int> available_chunks;
 697     available_chunks.insert(0);
 698     available_chunks.insert(1);
 699     available_chunks.insert(2);
 700     // available_chunks.insert(3);
 701     available_chunks.insert(4);
 702     available_chunks.insert(5);
 703     // available_chunks.insert(6);
 704     // available_chunks.insert(7);
 705     encoded.erase(3);
 706     encoded.erase(6);
 707     set<int> minimum;
 708     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 709     EXPECT_EQ(4U, minimum.size());
 710     // only need two chunks from the first local layer
 711     EXPECT_EQ(1U, minimum.count(0));
 712     EXPECT_EQ(1U, minimum.count(2));
 713     // the above chunks will rebuild chunk 3 and the global layer only needs
 714     // three more chunks to reach the required amount of chunks (4) to recover
 715     // the last two
 716     EXPECT_EQ(1U, minimum.count(1));
 717     EXPECT_EQ(1U, minimum.count(2));
 718     EXPECT_EQ(1U, minimum.count(5));
 719
 720     map<int, bufferlist> decoded;
 721     EXPECT_EQ(0, lrc._decode(want_to_read, encoded, &decoded));
 722     {
 723       string s(chunk_size, 'B');
 724       EXPECT_EQ(s, string(decoded[3].c_str(), chunk_size));
 725     }
 726     {
 727       string s(chunk_size, 'C');
 728       EXPECT_EQ(s, string(decoded[6].c_str(), chunk_size));
 729     }
 730     {
 731       string s(chunk_size, 'D');
 732       EXPECT_EQ(s, string(decoded[7].c_str(), chunk_size));
 733     }
 734   }
 735 }
 736
 737 TEST(ErasureCodeLrc, encode_decode_2)
 738 {
 739   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 740   ErasureCodeProfile profile;
 741   profile["mapping"] =
 742     "DD__DD__";
 743   const char *description_string =
 744     "[ "
 745     " [ \"DDc_DDc_\", \"\" ],"
 746     " [ \"DDDc____\", \"\" ],"
 747     " [ \"____DDDc\", \"\" ],"
 748     "]";
 749   profile["layers"] = description_string;
 750   EXPECT_EQ(0, lrc.init(profile, &cerr));
 751   EXPECT_EQ(4U, lrc.get_data_chunk_count());
 752   unsigned int chunk_size = g_conf().get_val<Option::size_t>("osd_pool_erasure_code_stripe_unit");
 753   unsigned int stripe_width = lrc.get_data_chunk_count() * chunk_size;
 754   EXPECT_EQ(chunk_size, lrc.get_chunk_size(stripe_width));
 755   set<int> want_to_encode;
 756   map<int, bufferlist> encoded;
 757   for (unsigned int i = 0; i < lrc.get_chunk_count(); ++i) {
 758     want_to_encode.insert(i);
 759     bufferptr ptr(buffer::create_page_aligned(chunk_size));
 760     bufferlist tmp;
 761     tmp.push_back(ptr);
 762     tmp.claim_append(encoded[i]);
 763     encoded[i].swap(tmp);
 764   }
 765   const vector<int> &mapping = lrc.get_chunk_mapping();
 766   char c = 'A';
 767   for (unsigned int i = 0; i < lrc.get_data_chunk_count(); i++) {
 768     int j = mapping[i];
 769     string s(chunk_size, c);
 770     encoded[j].clear();
 771     encoded[j].append(s);
 772     c++;
 773   }
 774   EXPECT_EQ(0, lrc.encode_chunks(want_to_encode, &encoded));
 775
 776   {
 777     set<int> want_to_read;
 778     want_to_read.insert(0);
 779     map<int, bufferlist> chunks;
 780     chunks[1] = encoded[1];
 781     chunks[3] = encoded[3];
 782     chunks[4] = encoded[4];
 783     chunks[5] = encoded[5];
 784     chunks[6] = encoded[6];
 785     chunks[7] = encoded[7];
 786     set<int> available_chunks;
 787     available_chunks.insert(1);
 788     available_chunks.insert(3);
 789     available_chunks.insert(4);
 790     available_chunks.insert(5);
 791     available_chunks.insert(6);
 792     available_chunks.insert(7);
 793     set<int> minimum;
 794     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 795     EXPECT_EQ(4U, minimum.size());
 796     EXPECT_EQ(1U, minimum.count(1));
 797     EXPECT_EQ(1U, minimum.count(4));
 798     EXPECT_EQ(1U, minimum.count(5));
 799     EXPECT_EQ(1U, minimum.count(6));
 800
 801     map<int, bufferlist> decoded;
 802     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 803     string s(chunk_size, 'A');
 804     EXPECT_EQ(s, string(decoded[0].c_str(), chunk_size));
 805   }
 806   {
 807     set<int> want_to_read;
 808     for (unsigned int i = 0; i < lrc.get_chunk_count(); i++)
 809       want_to_read.insert(i);
 810     map<int, bufferlist> chunks;
 811     chunks[1] = encoded[1];
 812     chunks[3] = encoded[3];
 813     chunks[5] = encoded[5];
 814     chunks[6] = encoded[6];
 815     chunks[7] = encoded[7];
 816     set<int> available_chunks;
 817     available_chunks.insert(1);
 818     available_chunks.insert(3);
 819     available_chunks.insert(5);
 820     available_chunks.insert(6);
 821     available_chunks.insert(7);
 822     set<int> minimum;
 823     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 824     EXPECT_EQ(5U, minimum.size());
 825     EXPECT_EQ(1U, minimum.count(1));
 826     EXPECT_EQ(1U, minimum.count(3));
 827     EXPECT_EQ(1U, minimum.count(5));
 828     EXPECT_EQ(1U, minimum.count(6));
 829     EXPECT_EQ(1U, minimum.count(7));
 830
 831     map<int, bufferlist> decoded;
 832     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 833     {
 834       string s(chunk_size, 'A');
 835       EXPECT_EQ(s, string(decoded[0].c_str(), chunk_size));
 836     }
 837     {
 838       string s(chunk_size, 'B');
 839       EXPECT_EQ(s, string(decoded[1].c_str(), chunk_size));
 840     }
 841     {
 842       string s(chunk_size, 'C');
 843       EXPECT_EQ(s, string(decoded[4].c_str(), chunk_size));
 844     }
 845     {
 846       string s(chunk_size, 'D');
 847       EXPECT_EQ(s, string(decoded[5].c_str(), chunk_size));
 848     }
 849   }
 850   {
 851     set<int> want_to_read;
 852     for (unsigned int i = 0; i < lrc.get_chunk_count(); i++)
 853       want_to_read.insert(i);
 854     map<int, bufferlist> chunks;
 855     chunks[1] = encoded[1];
 856     chunks[3] = encoded[3];
 857     chunks[5] = encoded[5];
 858     chunks[6] = encoded[6];
 859     chunks[7] = encoded[7];
 860     set<int> available_chunks;
 861     available_chunks.insert(1);
 862     available_chunks.insert(3);
 863     available_chunks.insert(5);
 864     available_chunks.insert(6);
 865     available_chunks.insert(7);
 866     set<int> minimum;
 867     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 868     EXPECT_EQ(5U, minimum.size());
 869     EXPECT_EQ(1U, minimum.count(1));
 870     EXPECT_EQ(1U, minimum.count(3));
 871     EXPECT_EQ(1U, minimum.count(5));
 872     EXPECT_EQ(1U, minimum.count(6));
 873     EXPECT_EQ(1U, minimum.count(7));
 874
 875     map<int, bufferlist> decoded;
 876     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 877     {
 878       string s(chunk_size, 'A');
 879       EXPECT_EQ(s, string(decoded[0].c_str(), chunk_size));
 880     }
 881     {
 882       string s(chunk_size, 'B');
 883       EXPECT_EQ(s, string(decoded[1].c_str(), chunk_size));
 884     }
 885     {
 886       string s(chunk_size, 'C');
 887       EXPECT_EQ(s, string(decoded[4].c_str(), chunk_size));
 888     }
 889     {
 890       string s(chunk_size, 'D');
 891       EXPECT_EQ(s, string(decoded[5].c_str(), chunk_size));
 892     }
 893   }
 894   {
 895     set<int> want_to_read;
 896     want_to_read.insert(6);
 897     map<int, bufferlist> chunks;
 898     chunks[0] = encoded[0];
 899     chunks[1] = encoded[1];
 900     chunks[3] = encoded[3];
 901     chunks[5] = encoded[5];
 902     chunks[7] = encoded[7];
 903     set<int> available_chunks;
 904     available_chunks.insert(0);
 905     available_chunks.insert(1);
 906     available_chunks.insert(3);
 907     available_chunks.insert(5);
 908     available_chunks.insert(7);
 909     set<int> minimum;
 910     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 911     EXPECT_EQ(available_chunks, minimum);
 912
 913     map<int, bufferlist> decoded;
 914     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 915   }
 916 }
 917
 918 /*
 919  * Local Variables:
 920  * compile-command: "cd ../.. ;
 921  *   make -j4 unittest_erasure_code_lrc && valgrind --tool=memcheck \
 922  *      ./unittest_erasure_code_lrc \
 923  *      --gtest_filter=*.* --log-to-stderr=true --debug-osd=20"
 924  * End:
 925  */