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