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()
24 #include "crush/CrushWrapper.h"
25 #include "osd/osd_types.h"
26 #include "include/stringify.h"
27 #include "global/global_init.h"
28 #include "erasure-code/shec/ErasureCodeShec.h"
29 #include "erasure-code/ErasureCodePlugin.h"
30 #include "common/ceph_argparse.h"
31 #include "global/global_context.h"
32 #include "gtest/gtest.h"
34 unsigned int count_num
= 0;
35 unsigned int unexpected_count
= 0;
36 unsigned int value_count
= 0;
38 map
<set
<int>,set
<set
<int> > > shec_table
;
40 int getint(int a
, int b
) {
41 return ((1 << a
) | (1 << b
));
44 int getint(int a
, int b
, int c
) {
45 return ((1 << a
) | (1 << b
) | (1 << c
));
48 int getint(int a
, int b
, int c
, int d
) {
49 return ((1 << a
) | (1 << b
) | (1 << c
) | (1 << d
));
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 (int want
= 1; want
< (1<<7); ++want
) {
60 if (__builtin_popcount(want
) != want_count
) {
64 for (int i
= 0; i
< 7; ++i
) {
65 if (want
& (1 << i
)) {
71 for (int avails
= 0; avails
< (1<<7); ++avails
) {
75 if (__builtin_popcount(avails
) == 2 &&
76 __builtin_popcount(want
) == 1) {
77 if ((want
| avails
) == getint(0,1,5) ||
78 (want
| avails
) == getint(2,3,6)) {
79 vec
.push_back(avails
);
84 for (int avails
= 0; avails
< (1<<7); ++avails
) {
88 if (__builtin_popcount(avails
) == 4) {
89 if ((avails
) == getint(0,1,2,3) ||
90 (avails
) == getint(0,1,2,4) ||
91 (avails
) == getint(0,1,2,6) ||
92 (avails
) == getint(0,1,3,4) ||
93 (avails
) == getint(0,1,3,6) ||
94 (avails
) == getint(0,1,4,6) ||
95 (avails
) == getint(0,2,3,4) ||
96 (avails
) == getint(0,2,3,5) ||
97 (avails
) == getint(0,2,4,5) ||
98 (avails
) == getint(0,2,4,6) ||
99 (avails
) == getint(0,2,5,6) ||
100 (avails
) == getint(0,3,4,5) ||
101 (avails
) == getint(0,3,4,6) ||
102 (avails
) == getint(0,3,5,6) ||
103 (avails
) == getint(0,4,5,6) ||
104 (avails
) == getint(1,2,3,4) ||
105 (avails
) == getint(1,2,3,5) ||
106 (avails
) == getint(1,2,4,5) ||
107 (avails
) == getint(1,2,4,6) ||
108 (avails
) == getint(1,2,5,6) ||
109 (avails
) == getint(1,3,4,5) ||
110 (avails
) == getint(1,3,4,6) ||
111 (avails
) == getint(1,3,5,6) ||
112 (avails
) == getint(1,4,5,6) ||
113 (avails
) == getint(2,3,4,5) ||
114 (avails
) == getint(2,4,5,6) ||
115 (avails
) == getint(3,4,5,6)) {
116 vec
.push_back(avails
);
120 for (int i
= 0; i
< (int)vec
.size(); ++i
) {
121 for (int j
= i
+ 1; j
< (int)vec
.size(); ++j
) {
122 if ((vec
[i
] & vec
[j
]) == vec
[i
]) {
123 vec
.erase(vec
.begin() + j
);
128 for (int i
= 0; i
< (int)vec
.size(); ++i
) {
130 for (int j
= 0; j
< 7; ++j
) {
131 if (vec
[i
] & (1 << j
)) {
132 vec_avails
.insert(j
);
135 table_value
.insert(vec_avails
);
137 shec_table
.insert(std::make_pair(table_key
,table_value
));
142 bool search_table_shec432(set
<int> want_to_read
, set
<int> available_chunks
) {
147 tmp
= shec_table
.find(want_to_read
)->second
;
148 for (set
<set
<int> >::iterator itr
= tmp
.begin();itr
!= tmp
.end(); ++itr
) {
152 for (set
<int>::iterator setitr
= settmp
.begin();setitr
!= settmp
.end(); ++setitr
) {
153 if (!available_chunks
.count(*setitr
)) {
165 TEST(ParameterTest
, combination_all
)
168 unsigned alignment
, tail
, padded_length
;
169 const unsigned int kObjectSize
= 128;
172 char* k
= (char*)"4";
173 char* m
= (char*)"3";
174 char* c
= (char*)"2";
178 alignment
= i_k
* 8 * sizeof(int);
179 tail
= kObjectSize
% alignment
;
180 padded_length
= kObjectSize
+ (tail
? (alignment
- tail
) : 0);
181 unsigned c_size
= padded_length
/ i_k
;
184 ErasureCodeShecTableCache tcache
;
185 ErasureCodeShec
* shec
= new ErasureCodeShecReedSolomonVandermonde(
187 ErasureCodeShec::MULTIPLE
);
188 map
< std::string
, std::string
> *profile
= new map
<std::string
,
190 (*profile
)["plugin"] = "shec";
191 (*profile
)["technique"] = "";
192 (*profile
)["crush-failure-domain"] = "osd";
197 result
= shec
->init(*profile
, &cerr
);
200 EXPECT_EQ(i_k
, shec
->k
);
201 EXPECT_EQ(i_m
, shec
->m
);
202 EXPECT_EQ(i_c
, shec
->c
);
203 EXPECT_EQ(8, shec
->w
);
204 EXPECT_EQ(ErasureCodeShec::MULTIPLE
, shec
->technique
);
205 EXPECT_STREQ("default", shec
->rule_root
.c_str());
206 EXPECT_STREQ("osd", shec
->rule_failure_domain
.c_str());
207 EXPECT_TRUE(shec
->matrix
!= NULL
);
208 EXPECT_EQ(0, result
);
212 set
<int> want_to_encode
;
213 map
<int, bufferlist
> encoded
;
215 in
.append("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//length = 62
216 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//124
219 for (unsigned int i
= 0; i
< shec
->get_chunk_count(); ++i
) {
220 want_to_encode
.insert(i
);
223 result
= shec
->encode(want_to_encode
, in
, &encoded
);
224 EXPECT_EQ(0, result
);
225 EXPECT_EQ(i_k
+i_m
, (int)encoded
.size());
226 EXPECT_EQ(c_size
, encoded
[0].length());
228 for (unsigned int i
= 0; i
< encoded
.size(); ++i
) {
229 out1
.append(encoded
[i
]);
231 EXPECT_FALSE(out1
== in
);
233 set
<int> want_to_read
, available_chunks
, minimum_chunks
, want_to_read_without_avails
;
234 set
<int>::iterator itr
;
235 int array_want_to_read
[shec
->get_chunk_count()];
236 int array_available_chunks
[shec
->get_chunk_count()];
238 map
<int, bufferlist
> inchunks
,decoded
;
240 unsigned int minimum_count
;
242 for (unsigned int w1
= 0; w1
<= shec
->get_chunk_count(); ++w1
) {
243 const unsigned int r1
= w1
; // combination(k+m,r1)
245 for (unsigned int i
= 0; i
< r1
; ++i
) {
246 array_want_to_read
[i
] = 1;
248 for (unsigned int i
= r1
; i
< shec
->get_chunk_count(); ++i
) {
249 array_want_to_read
[i
] = 0;
252 for (unsigned w2
= 0; w2
<= shec
->get_chunk_count(); ++w2
) {
253 const unsigned int r2
= w2
; // combination(k+m,r2)
255 for (unsigned int i
= 0; i
< r2
; ++i
) {
256 array_available_chunks
[i
] = 1;
258 for (unsigned int i
= r2
; i
< shec
->get_chunk_count(); ++i
) {
259 array_available_chunks
[i
] = 0;
264 for (unsigned int i
= 0; i
< shec
->get_chunk_count(); ++i
) {
265 if (array_want_to_read
[i
]) {
266 want_to_read
.insert(i
);
268 if (array_available_chunks
[i
]) {
269 available_chunks
.insert(i
);
270 inchunks
.insert(make_pair(i
,encoded
[i
]));
274 result
= shec
->minimum_to_decode(want_to_read
, available_chunks
,
276 dresult
= shec
->decode(want_to_read
, inchunks
, &decoded
);
280 if (want_to_read
.size() == 0) {
281 EXPECT_EQ(0, result
);
282 EXPECT_EQ(0u, minimum_chunks
.size());
283 EXPECT_EQ(0, dresult
);
284 EXPECT_EQ(0u, decoded
.size());
285 EXPECT_EQ(0u, decoded
[0].length());
286 if (result
!= 0 || dresult
!= 0) {
291 for (itr
= want_to_read
.begin();itr
!= want_to_read
.end(); ++itr
) {
292 if (!available_chunks
.count(*itr
)) {
293 want_to_read_without_avails
.insert(*itr
);
299 if (want_to_read_without_avails
.size() == 0) {
300 EXPECT_EQ(0, result
);
301 EXPECT_LT(0u, minimum_chunks
.size());
302 EXPECT_GE(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 cmp
= memcmp(decoded
[i
].c_str(), usable
.c_str(), c_size
);
310 EXPECT_EQ(c_size
, decoded
[i
].length());
317 if (result
!= 0 || dresult
!= 0) {
320 } else if (want_to_read_without_avails
.size() > 3) {
321 EXPECT_EQ(-EIO
, result
);
322 EXPECT_EQ(0u, minimum_chunks
.size());
323 EXPECT_EQ(-1, dresult
);
324 EXPECT_EQ(shec
->get_chunk_count(), decoded
.size());
325 if (result
!= -EIO
|| dresult
!= -1) {
330 if (search_table_shec432(want_to_read_without_avails
,available_chunks
)) {
331 EXPECT_EQ(0, result
);
332 EXPECT_LT(0u, minimum_chunks
.size());
333 EXPECT_GE(value_count
+ minimum_count
, minimum_chunks
.size());
334 EXPECT_EQ(0, dresult
);
335 EXPECT_NE(0u, decoded
.size());
336 for (unsigned int i
= 0; i
< shec
->get_data_chunk_count(); ++i
) {
337 if (array_want_to_read
[i
]) {
339 usable
.substr_of(in
, c_size
* i
, c_size
);
340 cmp
= memcmp(decoded
[i
].c_str(), usable
.c_str(), c_size
);
341 EXPECT_EQ(c_size
, decoded
[i
].length());
345 std::cout
<< "decoded[" << i
<< "] = " << decoded
[i
].c_str() << std::endl
;
346 std::cout
<< "usable = " << usable
.c_str() << std::endl
;
347 std::cout
<< "want_to_read :" << want_to_read
<< std::endl
;
348 std::cout
<< "available_chunks:" << available_chunks
<< std::endl
;
349 std::cout
<< "minimum_chunks :" << minimum_chunks
<< std::endl
;
353 if (result
!= 0 || dresult
!= 0) {
357 EXPECT_EQ(-EIO
, result
);
358 EXPECT_EQ(0u, minimum_chunks
.size());
359 EXPECT_EQ(-1, dresult
);
360 EXPECT_EQ(shec
->get_chunk_count(), decoded
.size());
361 if (result
!= -EIO
|| dresult
!= -1) {
368 want_to_read
.clear();
369 want_to_read_without_avails
.clear();
370 available_chunks
.clear();
371 minimum_chunks
.clear();
375 } while (std::prev_permutation(
377 array_want_to_read
+ shec
->get_chunk_count()));
379 } while (std::prev_permutation(
380 array_available_chunks
,
381 array_available_chunks
+ shec
->get_chunk_count()));
389 int main(int argc
, char **argv
)
393 vector
<const char*> args
;
394 argv_to_vec(argc
, (const char **) argv
, args
);
396 auto cct
= global_init(NULL
, args
, CEPH_ENTITY_TYPE_CLIENT
,
397 CODE_ENVIRONMENT_UTILITY
, 0);
398 common_init_finish(g_ceph_context
);
400 const char* env
= getenv("CEPH_LIB");
401 std::string
directory(env
? env
: ".libs");
402 g_conf
->set_val_or_die("erasure_code_dir", directory
, false);
404 ::testing::InitGoogleTest(&argc
, argv
);
406 create_table_shec432();
410 std::cout
<< "minimum_to_decode:total_num = " << count_num
412 std::cout
<< "minimum_to_decode:unexpected_num = " << unexpected_count