1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
3 * Ceph - scalable distributed file system
5 * Copyright (C) 2014 CERN (Switzerland)
6 * Copyright (C) 2014 Red Hat <contact@redhat.com>
8 * Author: Andreas-Joachim Peters <Andreas.Joachim.Peters@cern.ch>
9 * Author: Loic Dachary <loic@dachary.org>
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.
21 #include "crush/CrushWrapper.h"
22 #include "include/stringify.h"
23 #include "erasure-code/isa/ErasureCodeIsa.h"
24 #include "erasure-code/isa/xor_op.h"
25 #include "global/global_context.h"
26 #include "common/config.h"
27 #include "gtest/gtest.h"
29 ErasureCodeIsaTableCache tcache;
31 class IsaErasureCodeTest : public ::testing::Test {
33 void compare_chunks(bufferlist &in, map<int, bufferlist> &encoded);
34 void encode_decode(unsigned object_size);
37 void IsaErasureCodeTest::compare_chunks(bufferlist &in, map<int, bufferlist> &encoded)
39 unsigned object_size = in.length();
40 unsigned chunk_size = encoded[0].length();
41 for (unsigned i = 0; i < encoded.size(); i++) {
42 if (i * chunk_size >= object_size)
44 int chunk_length = object_size > (i + 1) * chunk_size ? chunk_size : object_size - i * chunk_size;
45 EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + i * chunk_size, chunk_length));
49 void IsaErasureCodeTest::encode_decode(unsigned object_size)
51 ErasureCodeIsaDefault Isa(tcache);
53 ErasureCodeProfile profile;
56 Isa.init(profile, &cerr);
58 string payload(object_size, 'X');
60 // may be multiple bufferptr if object_size is larger than CEPH_PAGE_SIZE
61 in.append(payload.c_str(), payload.length());
62 int want_to_encode[] = {0, 1, 2, 3};
63 map<int, bufferlist> encoded;
64 EXPECT_EQ(0, Isa.encode(set<int>(want_to_encode, want_to_encode + 4),
67 EXPECT_EQ(4u, encoded.size());
68 unsigned chunk_size = encoded[0].length();
69 EXPECT_EQ(chunk_size, Isa.get_chunk_size(object_size));
70 compare_chunks(in, encoded);
72 // all chunks are available
74 int want_to_decode[] = {0, 1};
75 map<int, bufferlist> decoded;
76 EXPECT_EQ(0, Isa.decode(set<int>(want_to_decode, want_to_decode + 2),
79 EXPECT_EQ(2u, decoded.size());
80 EXPECT_EQ(chunk_size, decoded[0].length());
81 compare_chunks(in, decoded);
84 // one data chunk is missing
86 map<int, bufferlist> degraded = encoded;
88 string enc1(encoded[1].c_str(), chunk_size);
91 EXPECT_EQ(3u, degraded.size());
92 int want_to_decode[] = {1};
93 map<int, bufferlist> decoded;
94 EXPECT_EQ(0, Isa.decode(set<int>(want_to_decode, want_to_decode + 1),
97 // always decode all, regardless of want_to_decode
98 EXPECT_EQ(4u, decoded.size());
99 EXPECT_EQ(chunk_size, decoded[1].length());
100 EXPECT_EQ(0, memcmp(decoded[1].c_str(), enc1.c_str(), chunk_size));
103 // non-xor coding chunk is missing
105 map<int, bufferlist> degraded = encoded;
107 string enc3(encoded[3].c_str(), chunk_size);
110 EXPECT_EQ(3u, degraded.size());
111 int want_to_decode[] = {3};
112 map<int, bufferlist> decoded;
113 EXPECT_EQ(0, Isa.decode(set<int>(want_to_decode, want_to_decode + 1),
116 // always decode all, regardless of want_to_decode
117 EXPECT_EQ(4u, decoded.size());
118 EXPECT_EQ(chunk_size, decoded[3].length());
119 EXPECT_EQ(0, memcmp(decoded[3].c_str(), enc3.c_str(), chunk_size));
122 // xor coding chunk is missing
124 map<int, bufferlist> degraded = encoded;
126 string enc2(encoded[2].c_str(), chunk_size);
129 EXPECT_EQ(3u, degraded.size());
130 int want_to_decode[] = {2};
131 map<int, bufferlist> decoded;
132 EXPECT_EQ(0, Isa.decode(set<int>(want_to_decode, want_to_decode + 1),
135 // always decode all, regardless of want_to_decode
136 EXPECT_EQ(4u, decoded.size());
137 EXPECT_EQ(chunk_size, decoded[2].length());
138 EXPECT_EQ(0, memcmp(decoded[2].c_str(), enc2.c_str(), chunk_size));
141 // one data and one coding chunk is missing
143 map<int, bufferlist> degraded = encoded;
145 string enc3(encoded[3].c_str(), chunk_size);
149 EXPECT_EQ(2u, degraded.size());
150 int want_to_decode[] = {1, 3};
151 map<int, bufferlist> decoded;
152 EXPECT_EQ(0, Isa.decode(set<int>(want_to_decode, want_to_decode + 2),
155 // always decode all, regardless of want_to_decode
156 EXPECT_EQ(4u, decoded.size());
157 EXPECT_EQ(chunk_size, decoded[1].length());
158 EXPECT_EQ(0, memcmp(decoded[3].c_str(), enc3.c_str(), chunk_size));
161 // two data chunks are missing
163 map<int, bufferlist> degraded = encoded;
166 EXPECT_EQ(2u, degraded.size());
167 int want_to_decode[] = {0, 1};
168 map<int, bufferlist> decoded;
169 EXPECT_EQ(0, Isa.decode(set<int>(want_to_decode, want_to_decode + 2),
172 // always decode all, regardless of want_to_decode
173 EXPECT_EQ(4u, decoded.size());
174 EXPECT_EQ(chunk_size, decoded[0].length());
175 compare_chunks(in, decoded);
180 TEST_F(IsaErasureCodeTest, encode_decode)
183 encode_decode(EC_ISA_ADDRESS_ALIGNMENT);
184 encode_decode(EC_ISA_ADDRESS_ALIGNMENT + 1);
187 encode_decode(4096 + 1);
190 TEST_F(IsaErasureCodeTest, minimum_to_decode)
192 ErasureCodeIsaDefault Isa(tcache);
193 ErasureCodeProfile profile;
196 Isa.init(profile, &cerr);
199 // If trying to read nothing, the minimum is empty.
202 set<int> want_to_read;
203 set<int> available_chunks;
206 EXPECT_EQ(0, Isa.minimum_to_decode(want_to_read,
209 EXPECT_TRUE(minimum.empty());
212 // There is no way to read a chunk if none are available.
215 set<int> want_to_read;
216 set<int> available_chunks;
219 want_to_read.insert(0);
221 EXPECT_EQ(-EIO, Isa.minimum_to_decode(want_to_read,
226 // Reading a subset of the available chunks is always possible.
229 set<int> want_to_read;
230 set<int> available_chunks;
233 want_to_read.insert(0);
234 available_chunks.insert(0);
236 EXPECT_EQ(0, Isa.minimum_to_decode(want_to_read,
239 EXPECT_EQ(want_to_read, minimum);
242 // There is no way to read a missing chunk if there is less than k
246 set<int> want_to_read;
247 set<int> available_chunks;
250 want_to_read.insert(0);
251 want_to_read.insert(1);
252 available_chunks.insert(0);
254 EXPECT_EQ(-EIO, Isa.minimum_to_decode(want_to_read,
259 // When chunks are not available, the minimum can be made of any
260 // chunks. For instance, to read 1 and 3 below the minimum could be
261 // 2 and 3 which may seem better because it contains one of the
262 // chunks to be read. But it won't be more efficient than retrieving
263 // 0 and 2 instead because, in both cases, the decode function will
264 // need to run the same recovery operation and use the same amount
265 // of CPU and memory.
268 set<int> want_to_read;
269 set<int> available_chunks;
272 want_to_read.insert(1);
273 want_to_read.insert(3);
274 available_chunks.insert(0);
275 available_chunks.insert(2);
276 available_chunks.insert(3);
278 EXPECT_EQ(0, Isa.minimum_to_decode(want_to_read,
281 EXPECT_EQ(2u, minimum.size());
282 EXPECT_EQ(0u, minimum.count(3));
286 TEST_F(IsaErasureCodeTest, chunk_size)
289 ErasureCodeIsaDefault Isa(tcache);
290 ErasureCodeProfile profile;
293 Isa.init(profile, &cerr);
296 ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(1));
297 ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k - 1));
298 ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT * 2, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k + 1));
301 ErasureCodeIsaDefault Isa(tcache);
302 ErasureCodeProfile profile;
305 Isa.init(profile, &cerr);
308 ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(1));
309 ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k - 1));
310 ASSERT_EQ(EC_ISA_ADDRESS_ALIGNMENT * 2, Isa.get_chunk_size(EC_ISA_ADDRESS_ALIGNMENT * k + 1));
311 unsigned object_size = EC_ISA_ADDRESS_ALIGNMENT * k * 1024 + 1;
312 ASSERT_NE(0u, object_size % k);
313 ASSERT_NE(0u, object_size % EC_ISA_ADDRESS_ALIGNMENT);
314 unsigned chunk_size = Isa.get_chunk_size(object_size);
315 ASSERT_EQ(0u, chunk_size % EC_ISA_ADDRESS_ALIGNMENT);
316 ASSERT_GT(chunk_size, (chunk_size * k) - object_size);
320 TEST_F(IsaErasureCodeTest, encode)
322 ErasureCodeIsaDefault Isa(tcache);
323 ErasureCodeProfile profile;
326 Isa.init(profile, &cerr);
328 unsigned aligned_object_size = Isa.get_alignment() * 2;
331 // When the input bufferlist needs to be padded because
332 // it is not properly aligned, it is padded with zeros.
335 map<int,bufferlist> encoded;
336 int want_to_encode[] = { 0, 1, 2, 3 };
337 int trail_length = 1;
338 in.append(string(aligned_object_size + trail_length, 'X'));
339 EXPECT_EQ(0, Isa.encode(set<int>(want_to_encode, want_to_encode+4),
342 EXPECT_EQ(4u, encoded.size());
343 char *last_chunk = encoded[1].c_str();
344 int length =encoded[1].length();
345 EXPECT_EQ('X', last_chunk[0]);
346 EXPECT_EQ('\0', last_chunk[length - trail_length]);
351 // When only the first chunk is required, the encoded map only
352 // contains the first chunk. Although the Isa encode
353 // internally allocated a buffer because of padding requirements
354 // and also computes the coding chunks, they are released before
355 // the return of the method, as shown when running the tests thru
356 // valgrind (there is no leak).
359 map<int,bufferlist> encoded;
360 set<int> want_to_encode;
361 want_to_encode.insert(0);
362 int trail_length = 1;
363 in.append(string(aligned_object_size + trail_length, 'X'));
364 EXPECT_EQ(0, Isa.encode(want_to_encode, in, &encoded));
365 EXPECT_EQ(1u, encoded.size());
369 TEST_F(IsaErasureCodeTest, sanity_check_k)
371 ErasureCodeIsaDefault Isa(tcache);
372 ErasureCodeProfile profile;
375 ostringstream errors;
376 EXPECT_EQ(-EINVAL, Isa.init(profile, &errors));
377 EXPECT_NE(std::string::npos, errors.str().find("must be >= 2"));
381 DecodeAndVerify(ErasureCodeIsaDefault& Isa, map<int, bufferlist> °raded, set<int> want_to_decode, buffer::ptr* enc, int length)
383 map<int, bufferlist> decoded;
386 // decode as requested
387 ok = Isa.decode(want_to_decode,
391 for (int i = 0; i < (int) decoded.size(); i++) {
392 // compare all the buffers with their original
393 ok |= memcmp(decoded[i].c_str(), enc[i].c_str(), length);
399 TEST_F(IsaErasureCodeTest, isa_vandermonde_exhaustive)
401 // Test all possible failure scenarios and reconstruction cases for
402 // a (12,4) configuration using the vandermonde matrix
404 ErasureCodeIsaDefault Isa(tcache);
405 ErasureCodeProfile profile;
408 Isa.init(profile, &cerr);
413 #define LARGE_ENOUGH 2048
414 bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
416 in_ptr.set_length(0);
417 const char *payload =
418 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
419 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
420 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
421 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
422 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
423 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
424 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
425 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
426 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
427 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
428 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
429 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
430 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
431 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
432 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
433 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
434 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
435 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
436 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
437 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
438 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
439 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
440 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
441 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
442 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
443 in_ptr.append(payload, strlen(payload));
445 in.push_front(in_ptr);
447 set<int>want_to_encode;
449 map<int, bufferlist> encoded;
450 for (int i = 0; i < (k + m); i++) {
451 want_to_encode.insert(i);
455 EXPECT_EQ(0, Isa.encode(want_to_encode,
459 EXPECT_EQ((unsigned) (k + m), encoded.size());
461 unsigned length = encoded[0].length();
463 for (int i = 0; i < k; i++) {
464 EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
467 buffer::ptr enc[k + m];
468 // create buffers with a copy of the original data to be able to compare it after decoding
470 for (int i = 0; i < (k + m); i++) {
471 buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
474 enc[i].set_length(0);
475 enc[i].append(encoded[i].c_str(), length);
479 // loop through all possible loss scenarios
482 for (int l1 = 0; l1 < (k + m); l1++) {
483 map<int, bufferlist> degraded = encoded;
484 set<int> want_to_decode;
487 want_to_decode.insert(l1);
488 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
491 for (int l2 = l1 + 1; l2 < (k + m); l2++) {
493 want_to_decode.insert(l2);
494 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
497 for (int l3 = l2 + 1; l3 < (k + m); l3++) {
499 want_to_decode.insert(l3);
500 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
503 for (int l4 = l3 + 1; l4 < (k + m); l4++) {
505 want_to_decode.insert(l4);
506 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
508 degraded[l4] = encoded[l4];
509 want_to_decode.erase(l4);
512 degraded[l3] = encoded[l3];
513 want_to_decode.erase(l3);
515 degraded[l2] = encoded[l2];
516 want_to_decode.erase(l2);
518 degraded[l1] = encoded[l1];
519 want_to_decode.erase(l1);
521 EXPECT_EQ(2516, cnt_cf);
522 EXPECT_EQ(2506, tcache.getDecodingTableCacheSize()); // 3 entries from (2,2) test and 2503 from (12,4)
525 TEST_F(IsaErasureCodeTest, isa_cauchy_exhaustive)
527 // Test all possible failure scenarios and reconstruction cases for
528 // a (12,4) configuration using the cauchy matrix
529 ErasureCodeIsaDefault Isa(tcache,ErasureCodeIsaDefault::kCauchy);
530 ErasureCodeProfile profile;
533 profile["technique"] = "cauchy";
535 Isa.init(profile, &cerr);
540 #define LARGE_ENOUGH 2048
541 bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
543 in_ptr.set_length(0);
544 const char *payload =
545 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
546 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
547 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
548 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
549 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
550 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
551 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
552 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
553 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
554 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
555 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
556 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
557 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
558 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
559 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
560 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
561 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
562 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
563 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
564 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
565 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
566 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
567 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
568 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
569 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
570 in_ptr.append(payload, strlen(payload));
572 in.push_front(in_ptr);
574 set<int>want_to_encode;
576 map<int, bufferlist> encoded;
577 for (int i = 0; i < (k + m); i++) {
578 want_to_encode.insert(i);
582 EXPECT_EQ(0, Isa.encode(want_to_encode,
586 EXPECT_EQ((unsigned) (k + m), encoded.size());
588 unsigned length = encoded[0].length();
590 for (int i = 0; i < k; i++) {
591 EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
594 buffer::ptr enc[k + m];
595 // create buffers with a copy of the original data to be able to compare it after decoding
597 for (int i = 0; i < (k + m); i++) {
598 buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
601 enc[i].set_length(0);
602 enc[i].append(encoded[i].c_str(), length);
606 // loop through all possible loss scenarios
609 for (int l1 = 0; l1 < (k + m); l1++) {
610 map<int, bufferlist> degraded = encoded;
611 set<int> want_to_decode;
614 want_to_decode.insert(l1);
615 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
618 for (int l2 = l1 + 1; l2 < (k + m); l2++) {
620 want_to_decode.insert(l2);
621 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
624 for (int l3 = l2 + 1; l3 < (k + m); l3++) {
626 want_to_decode.insert(l3);
627 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
630 for (int l4 = l3 + 1; l4 < (k + m); l4++) {
632 want_to_decode.insert(l4);
633 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
635 degraded[l4] = encoded[l4];
636 want_to_decode.erase(l4);
639 degraded[l3] = encoded[l3];
640 want_to_decode.erase(l3);
642 degraded[l2] = encoded[l2];
643 want_to_decode.erase(l2);
645 degraded[l1] = encoded[l1];
646 want_to_decode.erase(l1);
648 EXPECT_EQ(2516, cnt_cf);
649 EXPECT_EQ(2516, tcache.getDecodingTableCacheSize(ErasureCodeIsaDefault::kCauchy));
652 TEST_F(IsaErasureCodeTest, isa_cauchy_cache_trash)
654 // Test all possible failure scenarios and reconstruction cases for
655 // a (12,4) configuration using the cauchy matrix
656 ErasureCodeIsaDefault Isa(tcache,ErasureCodeIsaDefault::kCauchy);
657 ErasureCodeProfile profile;
660 profile["technique"] = "cauchy";
662 Isa.init(profile, &cerr);
667 #define LARGE_ENOUGH 2048
668 bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
670 in_ptr.set_length(0);
671 const char *payload =
672 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
673 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
674 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
675 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
676 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
677 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
678 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
679 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
680 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
681 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
682 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
683 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
684 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
685 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
686 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
687 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
688 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
689 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
690 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
691 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
692 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
693 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
694 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
695 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
696 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
697 in_ptr.append(payload, strlen(payload));
699 in.push_front(in_ptr);
701 set<int>want_to_encode;
703 map<int, bufferlist> encoded;
704 for (int i = 0; i < (k + m); i++) {
705 want_to_encode.insert(i);
709 EXPECT_EQ(0, Isa.encode(want_to_encode,
713 EXPECT_EQ((unsigned) (k + m), encoded.size());
715 unsigned length = encoded[0].length();
717 for (int i = 0; i < k; i++) {
718 EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
721 buffer::ptr enc[k + m];
722 // create buffers with a copy of the original data to be able to compare it after decoding
724 for (int i = 0; i < (k + m); i++) {
725 buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
728 enc[i].set_length(0);
729 enc[i].append(encoded[i].c_str(), length);
733 // loop through all possible loss scenarios
736 for (int l1 = 0; l1 < (k + m); l1++) {
737 map<int, bufferlist> degraded = encoded;
738 set<int> want_to_decode;
741 want_to_decode.insert(l1);
742 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
745 for (int l2 = l1 + 1; l2 < (k + m); l2++) {
747 want_to_decode.insert(l2);
748 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
751 for (int l3 = l2 + 1; l3 < (k + m); l3++) {
753 want_to_decode.insert(l3);
754 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
757 for (int l4 = l3 + 1; l4 < (k + m); l4++) {
759 want_to_decode.insert(l4);
760 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
762 degraded[l4] = encoded[l4];
763 want_to_decode.erase(l4);
766 degraded[l3] = encoded[l3];
767 want_to_decode.erase(l3);
769 degraded[l2] = encoded[l2];
770 want_to_decode.erase(l2);
772 degraded[l1] = encoded[l1];
773 want_to_decode.erase(l1);
775 EXPECT_EQ(6195, cnt_cf);
776 EXPECT_EQ(2516, tcache.getDecodingTableCacheSize(ErasureCodeIsaDefault::kCauchy));
779 TEST_F(IsaErasureCodeTest, isa_xor_codec)
781 // Test all possible failure scenarios and reconstruction cases for
782 // a (4,1) RAID-5 like configuration
784 ErasureCodeIsaDefault Isa(tcache);
785 ErasureCodeProfile profile;
788 Isa.init(profile, &cerr);
793 #define LARGE_ENOUGH 2048
794 bufferptr in_ptr(buffer::create_page_aligned(LARGE_ENOUGH));
796 in_ptr.set_length(0);
797 const char *payload =
798 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
799 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
800 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
801 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
802 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
803 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
804 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
805 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
806 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
807 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
808 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
809 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
810 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
811 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
812 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
813 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
814 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
815 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
816 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
817 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
818 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
819 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
820 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
821 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
822 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
823 in_ptr.append(payload, strlen(payload));
825 in.push_front(in_ptr);
827 set<int>want_to_encode;
829 map<int, bufferlist> encoded;
830 for (int i = 0; i < (k + m); i++) {
831 want_to_encode.insert(i);
835 EXPECT_EQ(0, Isa.encode(want_to_encode,
839 EXPECT_EQ((unsigned) (k + m), encoded.size());
841 unsigned length = encoded[0].length();
843 for (int i = 0; i < k; i++) {
844 EXPECT_EQ(0, memcmp(encoded[i].c_str(), in.c_str() + (i * length), length));
847 buffer::ptr enc[k + m];
848 // create buffers with a copy of the original data to be able to compare it after decoding
850 for (int i = 0; i < (k + m); i++) {
851 buffer::ptr newenc(buffer::create_page_aligned(LARGE_ENOUGH));
854 enc[i].set_length(0);
855 enc[i].append(encoded[i].c_str(), length);
859 // loop through all possible loss scenarios
862 for (int l1 = 0; l1 < (k + m); l1++) {
863 map<int, bufferlist> degraded = encoded;
864 set<int> want_to_decode;
867 want_to_decode.insert(l1);
868 err = DecodeAndVerify(Isa, degraded, want_to_decode, enc, length);
871 degraded[l1] = encoded[l1];
872 want_to_decode.erase(l1);
874 EXPECT_EQ(5, cnt_cf);
877 TEST_F(IsaErasureCodeTest, create_rule)
879 CrushWrapper *c = new CrushWrapper;
882 c->set_type_name(root_type, "root");
884 c->set_type_name(host_type, "host");
886 c->set_type_name(osd_type, "osd");
889 c->add_bucket(0, CRUSH_BUCKET_STRAW, CRUSH_HASH_RJENKINS1,
890 root_type, 0, NULL, NULL, &rootno);
891 c->set_item_name(rootno, "default");
893 map<string,string> loc;
894 loc["root"] = "default";
899 for (int h=0; h<num_host; ++h) {
900 loc["host"] = string("host-") + stringify(h);
901 for (int o=0; o<num_osd; ++o, ++osd) {
902 c->insert_item(g_ceph_context, osd, 1.0, string("osd.") + stringify(osd), loc);
910 ErasureCodeIsaDefault isa(tcache);
911 ErasureCodeProfile profile;
915 isa.init(profile, &cerr);
916 int ruleset = isa.create_rule("myrule", *c, &ss);
917 EXPECT_EQ(0, ruleset);
918 EXPECT_EQ(-EEXIST, isa.create_rule("myrule", *c, &ss));
920 // the minimum that is expected from the created ruleset is to
921 // successfully map get_chunk_count() devices from the crushmap,
924 vector<__u32> weight(c->get_max_devices(), 0x10000);
927 c->do_rule(ruleset, x, out, isa.get_chunk_count(), weight, 0);
928 ASSERT_EQ(out.size(), isa.get_chunk_count());
929 for (unsigned i=0; i<out.size(); ++i)
930 ASSERT_NE(CRUSH_ITEM_NONE, out[i]);
934 ErasureCodeIsaDefault isa(tcache);
935 ErasureCodeProfile profile;
939 profile["crush-root"] = "BAD";
940 isa.init(profile, &cerr);
941 EXPECT_EQ(-ENOENT, isa.create_rule("otherrule", *c, &ss));
942 EXPECT_EQ("root item BAD does not exist", ss.str());
946 ErasureCodeIsaDefault isa(tcache);
947 ErasureCodeProfile profile;
951 profile["crush-failure-domain"] = "WORSE";
952 isa.init(profile, &cerr);
953 EXPECT_EQ(-EINVAL, isa.create_rule("otherrule", *c, &ss));
954 EXPECT_EQ("unknown type WORSE", ss.str());
960 * compile-command: "cd ../.. ; make -j4 unittest_erasure_code_isa &&
961 * libtool --mode=execute valgrind --tool=memcheck \
962 * ./unittest_erasure_code_isa \
963 * --gtest_filter=*.* --log-to-stderr=true --debug-osd=20"