From 89e8b8be2fbfea065defba39ee2d2a620b21a11f Mon Sep 17 00:00:00 2001 From: Loic Dachary Date: Tue, 17 Sep 2013 10:50:58 +0200 Subject: [PATCH] ErasureCode: improve API implementation example * minimum_to_decode and minimum_to_decode_with_cost are replaced with meaningfull examples instead of placeholders * encode and decode are commented and hard coded constants are replaced by defines for readability * run against valgrind Signed-off-by: Loic Dachary --- src/test/osd/ErasureCodeExample.h | 85 +++++++++++++++++++++----- src/test/osd/TestErasureCodeExample.cc | 46 +++++++++++++- 2 files changed, 116 insertions(+), 15 deletions(-) diff --git a/src/test/osd/ErasureCodeExample.h b/src/test/osd/ErasureCodeExample.h index 896e614c6b5fd..95d79feb923f6 100644 --- a/src/test/osd/ErasureCodeExample.h +++ b/src/test/osd/ErasureCodeExample.h @@ -19,12 +19,19 @@ #include #include +#include #include #include "osd/ErasureCodeInterface.h" +#define FIRST_DATA_CHUNK 0 +#define SECOND_DATA_CHUNK 1 #define DATA_CHUNKS 2u + +#define CODING_CHUNK 2 #define CODING_CHUNKS 1u +#define MINIMUM_TO_RECOVER 2u + class ErasureCodeExample : public ErasureCodeInterface { public: useconds_t delay; @@ -43,21 +50,43 @@ public: virtual int minimum_to_decode(const set &want_to_read, const set &available_chunks, set *minimum) { - if (available_chunks.size() < DATA_CHUNKS) + if (includes(available_chunks.begin(), available_chunks.end(), + want_to_read.begin(), want_to_read.end())) { + *minimum = want_to_read; + return 0; + } else if (available_chunks.size() >= MINIMUM_TO_RECOVER) { + *minimum = available_chunks; + return 0; + } else { return -EIO; - set::iterator i; - unsigned j; - for (i = available_chunks.begin(), j = 0; j < DATA_CHUNKS; i++, j++) - minimum->insert(*i); - return 0; + } } virtual int minimum_to_decode_with_cost(const set &want_to_read, const map &available, set *minimum) { + // + // If one chunk is more expensive to fetch than the others, + // recover it instead. For instance, if the cost reflects the + // time it takes for a chunk to be retrieved from a remote + // OSD and if CPU is cheap, it could make sense to recover + // instead of fetching the chunk. + // + map c2c(available); + if (c2c.size() > DATA_CHUNKS) { + if (c2c[FIRST_DATA_CHUNK] > c2c[SECOND_DATA_CHUNK] && + c2c[FIRST_DATA_CHUNK] > c2c[CODING_CHUNK]) + c2c.erase(FIRST_DATA_CHUNK); + else if(c2c[SECOND_DATA_CHUNK] > c2c[FIRST_DATA_CHUNK] && + c2c[SECOND_DATA_CHUNK] > c2c[CODING_CHUNK]) + c2c.erase(SECOND_DATA_CHUNK); + else if(c2c[CODING_CHUNK] > c2c[FIRST_DATA_CHUNK] && + c2c[CODING_CHUNK] > c2c[SECOND_DATA_CHUNK]) + c2c.erase(CODING_CHUNK); + } set available_chunks; - for (map::const_iterator i = available.begin(); - i != available.end(); + for (map::const_iterator i = c2c.begin(); + i != c2c.end(); i++) available_chunks.insert(i->first); return minimum_to_decode(want_to_read, available_chunks, minimum); @@ -66,16 +95,28 @@ public: virtual int encode(const set &want_to_encode, const bufferlist &in, map *encoded) { + // + // make sure all data chunks have the same length, allocating + // padding if necessary. + // unsigned chunk_length = ( in.length() / DATA_CHUNKS ) + 1; unsigned length = chunk_length * ( DATA_CHUNKS + CODING_CHUNKS ); bufferlist out(in); bufferptr pad(length - in.length()); pad.zero(0, DATA_CHUNKS); out.push_back(pad); + // + // compute the coding chunk with first chunk ^ second chunk + // char *p = out.c_str(); - for (unsigned i = 0; i < chunk_length * DATA_CHUNKS; i++) - p[i + 2 * chunk_length] = - p[i + 0 * chunk_length] ^ p[i + 1 * chunk_length]; + for (unsigned i = 0; i < chunk_length; i++) + p[i + CODING_CHUNK * chunk_length] = + p[i + FIRST_DATA_CHUNK * chunk_length] ^ + p[i + SECOND_DATA_CHUNK * chunk_length]; + // + // populate the bufferlist with bufferptr pointing + // to chunk boundaries + // const bufferptr ptr = out.buffers().front(); for (set::iterator j = want_to_encode.begin(); j != want_to_encode.end(); @@ -89,14 +130,30 @@ public: virtual int decode(const set &want_to_read, const map &chunks, map *decoded) { - + // + // All chunks have the same size + // unsigned chunk_length = (*chunks.begin()).second.length(); for (set::iterator i = want_to_read.begin(); i != want_to_read.end(); i++) { - if (chunks.find(*i) != chunks.end()) + if (chunks.find(*i) != chunks.end()) { + // + // If the chunk is available, just copy the bufferptr pointer + // to the decoded argument. + // (*decoded)[*i] = chunks.find(*i)->second; - else { + } else if(chunks.size() != 2) { + // + // If a chunk is missing and there are not enough chunks + // to recover, abort. + // + return -ERANGE; + } else { + // + // No matter what the missing chunk is, XOR of the other + // two recovers it. + // bufferptr chunk(chunk_length); map::const_iterator k = chunks.begin(); const char *a = k->second.buffers().front().c_str(); diff --git a/src/test/osd/TestErasureCodeExample.cc b/src/test/osd/TestErasureCodeExample.cc index 66f521d7863d3..6866dfdbb9ff1 100644 --- a/src/test/osd/TestErasureCodeExample.cc +++ b/src/test/osd/TestErasureCodeExample.cc @@ -65,10 +65,54 @@ TEST(ErasureCodeExample, minimum_to_decode) EXPECT_EQ(0, example.minimum_to_decode(want_to_read, available_chunks, &minimum)); + EXPECT_EQ(1u, minimum.size()); + EXPECT_EQ(1u, minimum.count(1)); + } +} + +TEST(ErasureCodeExample, minimum_to_decode_with_cost) +{ + map parameters; + ErasureCodeExample example(parameters); + map available; + set want_to_read; + want_to_read.insert(1); + { + set minimum; + EXPECT_EQ(-EIO, example.minimum_to_decode_with_cost(want_to_read, + available, + &minimum)); + } + available[0] = 1; + available[2] = 1; + { + set minimum; + EXPECT_EQ(0, example.minimum_to_decode_with_cost(want_to_read, + available, + &minimum)); EXPECT_EQ(2u, minimum.size()); EXPECT_EQ(1u, minimum.count(0)); + EXPECT_EQ(1u, minimum.count(2)); + } + { + set minimum; + available[1] = 1; + EXPECT_EQ(0, example.minimum_to_decode_with_cost(want_to_read, + available, + &minimum)); + EXPECT_EQ(1u, minimum.size()); EXPECT_EQ(1u, minimum.count(1)); } + { + set minimum; + available[1] = 2; + EXPECT_EQ(0, example.minimum_to_decode_with_cost(want_to_read, + available, + &minimum)); + EXPECT_EQ(2u, minimum.size()); + EXPECT_EQ(1u, minimum.count(0)); + EXPECT_EQ(1u, minimum.count(2)); + } } TEST(ErasureCodeExample, encode_decode) @@ -142,5 +186,5 @@ int main(int argc, char **argv) { } // Local Variables: -// compile-command: "cd ../.. ; make -j4 && make unittest_erasure_code_example && ./unittest_erasure_code_example --gtest_filter=*.* --log-to-stderr=true --debug-osd=20" +// compile-command: "cd ../.. ; make -j4 && make unittest_erasure_code_example && valgrind --leak-check=full --tool=memcheck ./unittest_erasure_code_example --gtest_filter=*.* --log-to-stderr=true --debug-osd=20" // End: -- 2.39.5