1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2015 FUJITSU LIMITED
8 * Author: Shotaro Kawaguchi <kawaguchi.s@jp.fujitsu.com>
9 * Author: Takanori Nakao <nakao.takanori@jp.fujitsu.com>
10 * Author: Takeshi Miyamae <miyamae.takeshi@jp.fujitsu.com>
12 * This library is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public
14 * License as published by the Free Software Foundation; either
15 * version 2.1 of the License, or (at your option) any later version.
19 // SUMMARY: shec's gtest for each argument of minimum_to_decode()/decode()
26 #include "crush/CrushWrapper.h"
27 #include "osd/osd_types.h"
28 #include "include/stringify.h"
29 #include "global/global_init.h"
30 #include "erasure-code/shec/ErasureCodeShec.h"
31 #include "erasure-code/ErasureCodePlugin.h"
32 #include "common/ceph_argparse.h"
33 #include "global/global_context.h"
34 #include "gtest/gtest.h"
38 unsigned int count_num
= 0;
39 unsigned int unexpected_count
= 0;
40 unsigned int value_count
= 0;
42 map
<set
<int>,set
<set
<int> > > shec_table
;
44 constexpr int getint(std::initializer_list
<int> is
) {
46 for (const auto i
: is
) {
52 void create_table_shec432() {
53 set
<int> table_key
,vec_avails
;
54 set
<set
<int> > table_value
;
56 for (int want_count
= 0; want_count
< 7; ++want_count
) {
57 for (unsigned want
= 1; want
< (1<<7); ++want
) {
60 if (std::popcount(want
) != want_count
) {
64 for (int i
= 0; i
< 7; ++i
) {
65 if (want
& (1 << i
)) {
71 for (unsigned avails
= 0; avails
< (1<<7); ++avails
) {
75 if (std::popcount(avails
) == 2 &&
76 std::popcount(want
) == 1) {
77 if (std::cmp_equal(want
| avails
, getint({0,1,5})) ||
78 std::cmp_equal(want
| avails
, getint({2,3,6}))) {
79 vec
.push_back(avails
);
84 for (unsigned avails
= 0; avails
< (1<<7); ++avails
) {
88 if (std::popcount(avails
) == 4) {
89 auto a
= to_array
<std::initializer_list
<int>>({
90 {0,1,2,3}, {0,1,2,4}, {0,1,2,6}, {0,1,3,4}, {0,1,3,6}, {0,1,4,6},
91 {0,2,3,4}, {0,2,3,5}, {0,2,4,5}, {0,2,4,6}, {0,2,5,6}, {0,3,4,5},
92 {0,3,4,6}, {0,3,5,6}, {0,4,5,6}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5},
93 {1,2,4,6}, {1,2,5,6}, {1,3,4,5}, {1,3,4,6}, {1,3,5,6}, {1,4,5,6},
94 {2,3,4,5}, {2,4,5,6}, {3,4,5,6}});
95 if (ranges::any_of(a
, std::bind_front(cmp_equal
<uint
, int>, avails
),
97 vec
.push_back(avails
);
101 for (int i
= 0; i
< (int)vec
.size(); ++i
) {
102 for (int j
= i
+ 1; j
< (int)vec
.size(); ++j
) {
103 if ((vec
[i
] & vec
[j
]) == vec
[i
]) {
104 vec
.erase(vec
.begin() + j
);
109 for (int i
= 0; i
< (int)vec
.size(); ++i
) {
111 for (int j
= 0; j
< 7; ++j
) {
112 if (vec
[i
] & (1 << j
)) {
113 vec_avails
.insert(j
);
116 table_value
.insert(vec_avails
);
118 shec_table
.insert(std::make_pair(table_key
,table_value
));
123 bool search_table_shec432(set
<int> want_to_read
, set
<int> available_chunks
) {
128 tmp
= shec_table
.find(want_to_read
)->second
;
129 for (set
<set
<int> >::iterator itr
= tmp
.begin();itr
!= tmp
.end(); ++itr
) {
133 for (set
<int>::iterator setitr
= settmp
.begin();setitr
!= settmp
.end(); ++setitr
) {
134 if (!available_chunks
.count(*setitr
)) {
146 TEST(ParameterTest
, combination_all
)
148 const unsigned int kObjectSize
= 128;
151 char* k
= (char*)"4";
152 char* m
= (char*)"3";
153 char* c
= (char*)"2";
157 const unsigned alignment
= i_k
* 8 * sizeof(int);
158 const unsigned tail
= kObjectSize
% alignment
;
159 const unsigned padded_length
= kObjectSize
+ (tail
? (alignment
- tail
) : 0);
160 const unsigned c_size
= padded_length
/ i_k
;
163 ErasureCodeShecTableCache tcache
;
164 ErasureCodeShec
* shec
= new ErasureCodeShecReedSolomonVandermonde(
166 ErasureCodeShec::MULTIPLE
);
167 map
< std::string
, std::string
> *profile
= new map
<std::string
,
169 (*profile
)["plugin"] = "shec";
170 (*profile
)["technique"] = "";
171 (*profile
)["crush-failure-domain"] = "osd";
176 int result
= shec
->init(*profile
, &cerr
);
179 EXPECT_EQ(i_k
, shec
->k
);
180 EXPECT_EQ(i_m
, shec
->m
);
181 EXPECT_EQ(i_c
, shec
->c
);
182 EXPECT_EQ(8, shec
->w
);
183 EXPECT_EQ(ErasureCodeShec::MULTIPLE
, shec
->technique
);
184 EXPECT_STREQ("default", shec
->rule_root
.c_str());
185 EXPECT_STREQ("osd", shec
->rule_failure_domain
.c_str());
186 EXPECT_TRUE(shec
->matrix
!= NULL
);
187 EXPECT_EQ(0, result
);
191 in
.append("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//length = 62
192 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//124
195 set
<int> want_to_encode
;
196 for (unsigned int i
= 0; i
< shec
->get_chunk_count(); ++i
) {
197 want_to_encode
.insert(i
);
200 map
<int, bufferlist
> encoded
;
201 result
= shec
->encode(want_to_encode
, in
, &encoded
);
202 EXPECT_EQ(0, result
);
203 EXPECT_EQ(i_k
+i_m
, (int)encoded
.size());
204 EXPECT_EQ(c_size
, encoded
[0].length());
207 for (unsigned int i
= 0; i
< encoded
.size(); ++i
) {
208 out1
.append(encoded
[i
]);
210 EXPECT_FALSE(out1
== in
);
212 for (unsigned int w1
= 0; w1
<= shec
->get_chunk_count(); ++w1
) {
213 // combination(k+m,w1)
214 int array_want_to_read
[shec
->get_chunk_count()];
215 for (unsigned int i
= 0; i
< shec
->get_chunk_count(); ++i
) {
216 array_want_to_read
[i
] = i
< w1
? 1 : 0;
219 for (unsigned w2
= 0; w2
<= shec
->get_chunk_count(); ++w2
) {
220 // combination(k+m,w2)
221 int array_available_chunks
[shec
->get_chunk_count()];
222 for (unsigned int i
= 0; i
< shec
->get_chunk_count(); ++i
) {
223 array_available_chunks
[i
] = i
< w2
? 1 : 0;
228 set
<int> want_to_read
, available_chunks
;
229 map
<int, bufferlist
> inchunks
;
230 for (unsigned int i
= 0; i
< shec
->get_chunk_count(); ++i
) {
231 if (array_want_to_read
[i
]) {
232 want_to_read
.insert(i
);
234 if (array_available_chunks
[i
]) {
235 available_chunks
.insert(i
);
236 inchunks
.insert(make_pair(i
,encoded
[i
]));
240 map
<int, vector
<pair
<int,int>>> minimum_chunks
;
241 map
<int, bufferlist
> decoded
;
242 result
= shec
->minimum_to_decode(want_to_read
, available_chunks
,
244 int dresult
= shec
->decode(want_to_read
, inchunks
, &decoded
,
245 shec
->get_chunk_size(kObjectSize
));
247 unsigned int minimum_count
= 0;
249 if (want_to_read
.size() == 0) {
250 EXPECT_EQ(0, result
);
251 EXPECT_EQ(0u, minimum_chunks
.size());
252 EXPECT_EQ(0, dresult
);
253 EXPECT_EQ(0u, decoded
.size());
254 EXPECT_EQ(0u, decoded
[0].length());
255 if (result
!= 0 || dresult
!= 0) {
260 set
<int> want_to_read_without_avails
;
261 for (auto chunk
: want_to_read
) {
262 if (!available_chunks
.count(chunk
)) {
263 want_to_read_without_avails
.insert(chunk
);
269 if (want_to_read_without_avails
.size() == 0) {
270 EXPECT_EQ(0, result
);
271 EXPECT_LT(0u, minimum_chunks
.size());
272 EXPECT_GE(minimum_count
, minimum_chunks
.size());
273 EXPECT_EQ(0, dresult
);
274 EXPECT_NE(0u, decoded
.size());
275 for (unsigned int i
= 0; i
< shec
->get_data_chunk_count(); ++i
) {
276 if (array_want_to_read
[i
]) {
278 usable
.substr_of(in
, c_size
* i
, c_size
);
279 int cmp
= memcmp(decoded
[i
].c_str(), usable
.c_str(), c_size
);
280 EXPECT_EQ(c_size
, decoded
[i
].length());
287 if (result
!= 0 || dresult
!= 0) {
290 } else if (want_to_read_without_avails
.size() > 3) {
291 EXPECT_EQ(-EIO
, result
);
292 EXPECT_EQ(0u, minimum_chunks
.size());
293 EXPECT_EQ(-1, dresult
);
294 if (result
!= -EIO
|| dresult
!= -1) {
299 if (search_table_shec432(want_to_read_without_avails
,available_chunks
)) {
300 EXPECT_EQ(0, result
);
301 EXPECT_LT(0u, minimum_chunks
.size());
302 EXPECT_GE(value_count
+ minimum_count
, minimum_chunks
.size());
303 EXPECT_EQ(0, dresult
);
304 EXPECT_NE(0u, decoded
.size());
305 for (unsigned int i
= 0; i
< shec
->get_data_chunk_count(); ++i
) {
306 if (array_want_to_read
[i
]) {
308 usable
.substr_of(in
, c_size
* i
, c_size
);
309 int cmp
= memcmp(decoded
[i
].c_str(), usable
.c_str(), c_size
);
310 EXPECT_EQ(c_size
, decoded
[i
].length());
314 std::cout
<< "decoded[" << i
<< "] = " << decoded
[i
].c_str() << std::endl
;
315 std::cout
<< "usable = " << usable
.c_str() << std::endl
;
316 std::cout
<< "want_to_read :" << want_to_read
<< std::endl
;
317 std::cout
<< "available_chunks:" << available_chunks
<< std::endl
;
318 std::cout
<< "minimum_chunks :" << minimum_chunks
<< std::endl
;
322 if (result
!= 0 || dresult
!= 0) {
326 EXPECT_EQ(-EIO
, result
);
327 EXPECT_EQ(0u, minimum_chunks
.size());
328 EXPECT_EQ(-1, dresult
);
329 if (result
!= -EIO
|| dresult
!= -1) {
335 } while (std::prev_permutation(
337 array_want_to_read
+ shec
->get_chunk_count()));
339 } while (std::prev_permutation(
340 array_available_chunks
,
341 array_available_chunks
+ shec
->get_chunk_count()));
349 int main(int argc
, char **argv
)
351 auto args
= argv_to_vec(argc
, argv
);
353 auto cct
= global_init(NULL
, args
, CEPH_ENTITY_TYPE_CLIENT
,
354 CODE_ENVIRONMENT_UTILITY
,
355 CINIT_FLAG_NO_MON_CONFIG
);
356 common_init_finish(g_ceph_context
);
358 ::testing::InitGoogleTest(&argc
, argv
);
360 create_table_shec432();
362 int r
= RUN_ALL_TESTS();
364 std::cout
<< "minimum_to_decode:total_num = " << count_num
366 std::cout
<< "minimum_to_decode:unexpected_num = " << unexpected_count