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
  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(-EINVAL, 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 : "lib");
 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().get_val<Option::size_t>("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     bufferlist tmp;
 627     tmp.push_back(ptr);
 628     tmp.claim_append(encoded[i]);
 629     encoded[i].swap(tmp);
 630   }
 631   const vector<int> &mapping = lrc.get_chunk_mapping();
 632   char c = 'A';
 633   for (unsigned int i = 0; i < lrc.get_data_chunk_count(); i++) {
 634     int j = mapping[i];
 635     string s(chunk_size, c);
 636     encoded[j].clear();
 637     encoded[j].append(s);
 638     c++;
 639   }
 640   EXPECT_EQ(0, lrc.encode_chunks(want_to_encode, &encoded));
 641
 642   {
 643     map<int, bufferlist> chunks;
 644     chunks[4] = encoded[4];
 645     chunks[5] = encoded[5];
 646     chunks[6] = encoded[6];
 647     set<int> want_to_read;
 648     want_to_read.insert(7);
 649     set<int> available_chunks;
 650     available_chunks.insert(4);
 651     available_chunks.insert(5);
 652     available_chunks.insert(6);
 653     set<int> minimum;
 654     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 655     // only need three chunks from the second local layer
 656     EXPECT_EQ(3U, minimum.size());
 657     EXPECT_EQ(1U, minimum.count(4));
 658     EXPECT_EQ(1U, minimum.count(5));
 659     EXPECT_EQ(1U, minimum.count(6));
 660     map<int, bufferlist> decoded;
 661     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 662     string s(chunk_size, 'D');
 663     EXPECT_EQ(s, string(decoded[7].c_str(), chunk_size));
 664   }
 665   {
 666     set<int> want_to_read;
 667     want_to_read.insert(2);
 668     map<int, bufferlist> chunks;
 669     chunks[1] = encoded[1];
 670     chunks[3] = encoded[3];
 671     chunks[5] = encoded[5];
 672     chunks[6] = encoded[6];
 673     chunks[7] = encoded[7];
 674     set<int> available_chunks;
 675     available_chunks.insert(1);
 676     available_chunks.insert(3);
 677     available_chunks.insert(5);
 678     available_chunks.insert(6);
 679     available_chunks.insert(7);
 680     set<int> minimum;
 681     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 682     EXPECT_EQ(5U, minimum.size());
 683     EXPECT_EQ(available_chunks, minimum);
 684
 685     map<int, bufferlist> decoded;
 686     EXPECT_EQ(0, lrc._decode(want_to_read, encoded, &decoded));
 687     string s(chunk_size, 'A');
 688     EXPECT_EQ(s, string(decoded[2].c_str(), chunk_size));
 689   }
 690   {
 691     set<int> want_to_read;
 692     want_to_read.insert(3);
 693     want_to_read.insert(6);
 694     want_to_read.insert(7);
 695     set<int> available_chunks;
 696     available_chunks.insert(0);
 697     available_chunks.insert(1);
 698     available_chunks.insert(2);
 699     // available_chunks.insert(3);
 700     available_chunks.insert(4);
 701     available_chunks.insert(5);
 702     // available_chunks.insert(6);
 703     // available_chunks.insert(7);
 704     encoded.erase(3);
 705     encoded.erase(6);
 706     set<int> minimum;
 707     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 708     EXPECT_EQ(4U, minimum.size());
 709     // only need two chunks from the first local layer
 710     EXPECT_EQ(1U, minimum.count(0));
 711     EXPECT_EQ(1U, minimum.count(2));
 712     // the above chunks will rebuild chunk 3 and the global layer only needs
 713     // three more chunks to reach the required amount of chunks (4) to recover
 714     // the last two
 715     EXPECT_EQ(1U, minimum.count(1));
 716     EXPECT_EQ(1U, minimum.count(2));
 717     EXPECT_EQ(1U, minimum.count(5));
 718
 719     map<int, bufferlist> decoded;
 720     EXPECT_EQ(0, lrc._decode(want_to_read, encoded, &decoded));
 721     {
 722       string s(chunk_size, 'B');
 723       EXPECT_EQ(s, string(decoded[3].c_str(), chunk_size));
 724     }
 725     {
 726       string s(chunk_size, 'C');
 727       EXPECT_EQ(s, string(decoded[6].c_str(), chunk_size));
 728     }
 729     {
 730       string s(chunk_size, 'D');
 731       EXPECT_EQ(s, string(decoded[7].c_str(), chunk_size));
 732     }
 733   }
 734 }
 735
 736 TEST(ErasureCodeLrc, encode_decode_2)
 737 {
 738   ErasureCodeLrc lrc(g_conf().get_val<std::string>("erasure_code_dir"));
 739   ErasureCodeProfile profile;
 740   profile["mapping"] =
 741     "DD__DD__";
 742   const char *description_string =
 743     "[ "
 744     " [ \"DDc_DDc_\", \"\" ],"
 745     " [ \"DDDc____\", \"\" ],"
 746     " [ \"____DDDc\", \"\" ],"
 747     "]";
 748   profile["layers"] = description_string;
 749   EXPECT_EQ(0, lrc.init(profile, &cerr));
 750   EXPECT_EQ(4U, lrc.get_data_chunk_count());
 751   unsigned int chunk_size = g_conf().get_val<Option::size_t>("osd_pool_erasure_code_stripe_unit");
 752   unsigned int stripe_width = lrc.get_data_chunk_count() * chunk_size;
 753   EXPECT_EQ(chunk_size, lrc.get_chunk_size(stripe_width));
 754   set<int> want_to_encode;
 755   map<int, bufferlist> encoded;
 756   for (unsigned int i = 0; i < lrc.get_chunk_count(); ++i) {
 757     want_to_encode.insert(i);
 758     bufferptr ptr(buffer::create_page_aligned(chunk_size));
 759     bufferlist tmp;
 760     tmp.push_back(ptr);
 761     tmp.claim_append(encoded[i]);
 762     encoded[i].swap(tmp);
 763   }
 764   const vector<int> &mapping = lrc.get_chunk_mapping();
 765   char c = 'A';
 766   for (unsigned int i = 0; i < lrc.get_data_chunk_count(); i++) {
 767     int j = mapping[i];
 768     string s(chunk_size, c);
 769     encoded[j].clear();
 770     encoded[j].append(s);
 771     c++;
 772   }
 773   EXPECT_EQ(0, lrc.encode_chunks(want_to_encode, &encoded));
 774
 775   {
 776     set<int> want_to_read;
 777     want_to_read.insert(0);
 778     map<int, bufferlist> chunks;
 779     chunks[1] = encoded[1];
 780     chunks[3] = encoded[3];
 781     chunks[4] = encoded[4];
 782     chunks[5] = encoded[5];
 783     chunks[6] = encoded[6];
 784     chunks[7] = encoded[7];
 785     set<int> available_chunks;
 786     available_chunks.insert(1);
 787     available_chunks.insert(3);
 788     available_chunks.insert(4);
 789     available_chunks.insert(5);
 790     available_chunks.insert(6);
 791     available_chunks.insert(7);
 792     set<int> minimum;
 793     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 794     EXPECT_EQ(4U, minimum.size());
 795     EXPECT_EQ(1U, minimum.count(1));
 796     EXPECT_EQ(1U, minimum.count(4));
 797     EXPECT_EQ(1U, minimum.count(5));
 798     EXPECT_EQ(1U, minimum.count(6));
 799
 800     map<int, bufferlist> decoded;
 801     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 802     string s(chunk_size, 'A');
 803     EXPECT_EQ(s, string(decoded[0].c_str(), chunk_size));
 804   }
 805   {
 806     set<int> want_to_read;
 807     for (unsigned int i = 0; i < lrc.get_chunk_count(); i++)
 808       want_to_read.insert(i);
 809     map<int, bufferlist> chunks;
 810     chunks[1] = encoded[1];
 811     chunks[3] = encoded[3];
 812     chunks[5] = encoded[5];
 813     chunks[6] = encoded[6];
 814     chunks[7] = encoded[7];
 815     set<int> available_chunks;
 816     available_chunks.insert(1);
 817     available_chunks.insert(3);
 818     available_chunks.insert(5);
 819     available_chunks.insert(6);
 820     available_chunks.insert(7);
 821     set<int> minimum;
 822     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 823     EXPECT_EQ(5U, minimum.size());
 824     EXPECT_EQ(1U, minimum.count(1));
 825     EXPECT_EQ(1U, minimum.count(3));
 826     EXPECT_EQ(1U, minimum.count(5));
 827     EXPECT_EQ(1U, minimum.count(6));
 828     EXPECT_EQ(1U, minimum.count(7));
 829
 830     map<int, bufferlist> decoded;
 831     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 832     {
 833       string s(chunk_size, 'A');
 834       EXPECT_EQ(s, string(decoded[0].c_str(), chunk_size));
 835     }
 836     {
 837       string s(chunk_size, 'B');
 838       EXPECT_EQ(s, string(decoded[1].c_str(), chunk_size));
 839     }
 840     {
 841       string s(chunk_size, 'C');
 842       EXPECT_EQ(s, string(decoded[4].c_str(), chunk_size));
 843     }
 844     {
 845       string s(chunk_size, 'D');
 846       EXPECT_EQ(s, string(decoded[5].c_str(), chunk_size));
 847     }
 848   }
 849   {
 850     set<int> want_to_read;
 851     for (unsigned int i = 0; i < lrc.get_chunk_count(); i++)
 852       want_to_read.insert(i);
 853     map<int, bufferlist> chunks;
 854     chunks[1] = encoded[1];
 855     chunks[3] = encoded[3];
 856     chunks[5] = encoded[5];
 857     chunks[6] = encoded[6];
 858     chunks[7] = encoded[7];
 859     set<int> available_chunks;
 860     available_chunks.insert(1);
 861     available_chunks.insert(3);
 862     available_chunks.insert(5);
 863     available_chunks.insert(6);
 864     available_chunks.insert(7);
 865     set<int> minimum;
 866     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 867     EXPECT_EQ(5U, minimum.size());
 868     EXPECT_EQ(1U, minimum.count(1));
 869     EXPECT_EQ(1U, minimum.count(3));
 870     EXPECT_EQ(1U, minimum.count(5));
 871     EXPECT_EQ(1U, minimum.count(6));
 872     EXPECT_EQ(1U, minimum.count(7));
 873
 874     map<int, bufferlist> decoded;
 875     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 876     {
 877       string s(chunk_size, 'A');
 878       EXPECT_EQ(s, string(decoded[0].c_str(), chunk_size));
 879     }
 880     {
 881       string s(chunk_size, 'B');
 882       EXPECT_EQ(s, string(decoded[1].c_str(), chunk_size));
 883     }
 884     {
 885       string s(chunk_size, 'C');
 886       EXPECT_EQ(s, string(decoded[4].c_str(), chunk_size));
 887     }
 888     {
 889       string s(chunk_size, 'D');
 890       EXPECT_EQ(s, string(decoded[5].c_str(), chunk_size));
 891     }
 892   }
 893   {
 894     set<int> want_to_read;
 895     want_to_read.insert(6);
 896     map<int, bufferlist> chunks;
 897     chunks[0] = encoded[0];
 898     chunks[1] = encoded[1];
 899     chunks[3] = encoded[3];
 900     chunks[5] = encoded[5];
 901     chunks[7] = encoded[7];
 902     set<int> available_chunks;
 903     available_chunks.insert(0);
 904     available_chunks.insert(1);
 905     available_chunks.insert(3);
 906     available_chunks.insert(5);
 907     available_chunks.insert(7);
 908     set<int> minimum;
 909     EXPECT_EQ(0, lrc._minimum_to_decode(want_to_read, available_chunks, &minimum));
 910     EXPECT_EQ(available_chunks, minimum);
 911
 912     map<int, bufferlist> decoded;
 913     EXPECT_EQ(0, lrc._decode(want_to_read, chunks, &decoded));
 914   }
 915 }
 916
 917 /*
 918  * Local Variables:
 919  * compile-command: "cd ../.. ;
 920  *   make -j4 unittest_erasure_code_lrc && valgrind --tool=memcheck \
 921  *      ./unittest_erasure_code_lrc \
 922  *      --gtest_filter=*.* --log-to-stderr=true --debug-osd=20"
 923  * End:
 924  */