]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2015 FUJITSU LIMITED | |
7 | * | |
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> | |
11 | * | |
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. | |
16 | * | |
17 | */ | |
18 | ||
19 | // SUMMARY: shec's gtest for each argument of minimum_to_decode()/decode() | |
20 | ||
1e59de90 TL |
21 | #include <algorithm> |
22 | #include <bit> | |
23 | #include <cerrno> | |
24 | #include <cstdlib> | |
7c673cae FG |
25 | |
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" | |
35 | ||
20effc67 TL |
36 | using namespace std; |
37 | ||
7c673cae FG |
38 | unsigned int count_num = 0; |
39 | unsigned int unexpected_count = 0; | |
40 | unsigned int value_count = 0; | |
41 | ||
42 | map<set<int>,set<set<int> > > shec_table; | |
43 | ||
1e59de90 TL |
44 | constexpr int getint(std::initializer_list<int> is) { |
45 | int a = 0; | |
46 | for (const auto i : is) { | |
47 | a |= 1 << i; | |
48 | } | |
49 | return a; | |
7c673cae FG |
50 | } |
51 | ||
52 | void create_table_shec432() { | |
53 | set<int> table_key,vec_avails; | |
54 | set<set<int> > table_value; | |
55 | ||
56 | for (int want_count = 0; want_count < 7; ++want_count) { | |
1e59de90 | 57 | for (unsigned want = 1; want < (1<<7); ++want) { |
7c673cae FG |
58 | table_key.clear(); |
59 | table_value.clear(); | |
1e59de90 | 60 | if (std::popcount(want) != want_count) { |
7c673cae FG |
61 | continue; |
62 | } | |
63 | { | |
64 | for (int i = 0; i < 7; ++i) { | |
65 | if (want & (1 << i)) { | |
66 | table_key.insert(i); | |
67 | } | |
68 | } | |
69 | } | |
70 | vector<int> vec; | |
1e59de90 | 71 | for (unsigned avails = 0; avails < (1<<7); ++avails) { |
7c673cae FG |
72 | if (want & avails) { |
73 | continue; | |
74 | } | |
1e59de90 TL |
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}))) { | |
7c673cae FG |
79 | vec.push_back(avails); |
80 | } | |
81 | } | |
82 | } | |
1e59de90 TL |
83 | |
84 | for (unsigned avails = 0; avails < (1<<7); ++avails) { | |
7c673cae FG |
85 | if (want & avails) { |
86 | continue; | |
87 | } | |
1e59de90 TL |
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), | |
96 | getint)) { | |
97 | vec.push_back(avails); | |
98 | } | |
99 | } | |
7c673cae FG |
100 | } |
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); | |
105 | --j; | |
106 | } | |
107 | } | |
108 | } | |
109 | for (int i = 0; i < (int)vec.size(); ++i) { | |
110 | vec_avails.clear(); | |
111 | for (int j = 0; j < 7; ++j) { | |
112 | if (vec[i] & (1 << j)) { | |
113 | vec_avails.insert(j); | |
114 | } | |
115 | } | |
116 | table_value.insert(vec_avails); | |
117 | } | |
118 | shec_table.insert(std::make_pair(table_key,table_value)); | |
119 | } | |
120 | } | |
121 | } | |
122 | ||
123 | bool search_table_shec432(set<int> want_to_read, set<int> available_chunks) { | |
124 | set<set<int> > tmp; | |
125 | set<int> settmp; | |
126 | bool found; | |
127 | ||
128 | tmp = shec_table.find(want_to_read)->second; | |
129 | for (set<set<int> >::iterator itr = tmp.begin();itr != tmp.end(); ++itr) { | |
130 | found = true; | |
131 | value_count = 0; | |
132 | settmp = *itr; | |
133 | for (set<int>::iterator setitr = settmp.begin();setitr != settmp.end(); ++setitr) { | |
134 | if (!available_chunks.count(*setitr)) { | |
135 | found = false; | |
136 | } | |
137 | ++value_count; | |
138 | } | |
139 | if (found) { | |
140 | return true; | |
141 | } | |
142 | } | |
143 | return false; | |
144 | } | |
145 | ||
146 | TEST(ParameterTest, combination_all) | |
147 | { | |
7c673cae FG |
148 | const unsigned int kObjectSize = 128; |
149 | ||
150 | //get profile | |
151 | char* k = (char*)"4"; | |
152 | char* m = (char*)"3"; | |
153 | char* c = (char*)"2"; | |
154 | int i_k = atoi(k); | |
155 | int i_m = atoi(m); | |
156 | int i_c = atoi(c); | |
f67539c2 TL |
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; | |
7c673cae FG |
161 | |
162 | //init | |
163 | ErasureCodeShecTableCache tcache; | |
164 | ErasureCodeShec* shec = new ErasureCodeShecReedSolomonVandermonde( | |
165 | tcache, | |
166 | ErasureCodeShec::MULTIPLE); | |
167 | map < std::string, std::string > *profile = new map<std::string, | |
168 | std::string>(); | |
169 | (*profile)["plugin"] = "shec"; | |
170 | (*profile)["technique"] = ""; | |
224ce89b | 171 | (*profile)["crush-failure-domain"] = "osd"; |
7c673cae FG |
172 | (*profile)["k"] = k; |
173 | (*profile)["m"] = m; | |
174 | (*profile)["c"] = c; | |
175 | ||
f67539c2 | 176 | int result = shec->init(*profile, &cerr); |
7c673cae FG |
177 | |
178 | //check profile | |
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); | |
224ce89b WB |
184 | EXPECT_STREQ("default", shec->rule_root.c_str()); |
185 | EXPECT_STREQ("osd", shec->rule_failure_domain.c_str()); | |
7c673cae FG |
186 | EXPECT_TRUE(shec->matrix != NULL); |
187 | EXPECT_EQ(0, result); | |
188 | ||
189 | //encode | |
f67539c2 | 190 | bufferlist in; |
7c673cae FG |
191 | in.append("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//length = 62 |
192 | "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"//124 | |
193 | "0123"//128 | |
194 | ); | |
f67539c2 | 195 | set<int> want_to_encode; |
7c673cae FG |
196 | for (unsigned int i = 0; i < shec->get_chunk_count(); ++i) { |
197 | want_to_encode.insert(i); | |
198 | } | |
199 | ||
f67539c2 | 200 | map<int, bufferlist> encoded; |
7c673cae FG |
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()); | |
f67539c2 | 205 | bufferlist out1; |
7c673cae FG |
206 | //out1 is "encoded" |
207 | for (unsigned int i = 0; i < encoded.size(); ++i) { | |
208 | out1.append(encoded[i]); | |
209 | } | |
210 | EXPECT_FALSE(out1 == in); | |
211 | ||
7c673cae | 212 | for (unsigned int w1 = 0; w1 <= shec->get_chunk_count(); ++w1) { |
f67539c2 TL |
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; | |
7c673cae FG |
217 | } |
218 | ||
219 | for (unsigned w2 = 0; w2 <= shec->get_chunk_count(); ++w2) { | |
f67539c2 TL |
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; | |
7c673cae FG |
224 | } |
225 | ||
226 | do { | |
227 | do { | |
f67539c2 TL |
228 | set<int> want_to_read, available_chunks; |
229 | map<int, bufferlist> inchunks; | |
7c673cae FG |
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); | |
233 | } | |
234 | if (array_available_chunks[i]) { | |
235 | available_chunks.insert(i); | |
236 | inchunks.insert(make_pair(i,encoded[i])); | |
237 | } | |
238 | } | |
239 | ||
f67539c2 TL |
240 | map<int, vector<pair<int,int>>> minimum_chunks; |
241 | map<int, bufferlist> decoded; | |
7c673cae FG |
242 | result = shec->minimum_to_decode(want_to_read, available_chunks, |
243 | &minimum_chunks); | |
f67539c2 TL |
244 | int dresult = shec->decode(want_to_read, inchunks, &decoded, |
245 | shec->get_chunk_size(kObjectSize)); | |
7c673cae | 246 | ++count_num; |
f67539c2 | 247 | unsigned int minimum_count = 0; |
7c673cae FG |
248 | |
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) { | |
256 | ++unexpected_count; | |
257 | } | |
258 | } else { | |
259 | // want - avail | |
f67539c2 TL |
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); | |
7c673cae FG |
264 | } else { |
265 | ++minimum_count; | |
266 | } | |
267 | } | |
268 | ||
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]) { | |
f67539c2 | 277 | bufferlist usable; |
7c673cae | 278 | usable.substr_of(in, c_size * i, c_size); |
f67539c2 | 279 | int cmp = memcmp(decoded[i].c_str(), usable.c_str(), c_size); |
7c673cae FG |
280 | EXPECT_EQ(c_size, decoded[i].length()); |
281 | EXPECT_EQ(0, cmp); | |
282 | if (cmp != 0) { | |
283 | ++unexpected_count; | |
284 | } | |
285 | } | |
286 | } | |
287 | if (result != 0 || dresult != 0) { | |
288 | ++unexpected_count; | |
289 | } | |
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); | |
7c673cae FG |
294 | if (result != -EIO || dresult != -1) { |
295 | ++unexpected_count; | |
296 | } | |
297 | } else { | |
298 | // search | |
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]) { | |
f67539c2 | 307 | bufferlist usable; |
7c673cae | 308 | usable.substr_of(in, c_size * i, c_size); |
f67539c2 | 309 | int cmp = memcmp(decoded[i].c_str(), usable.c_str(), c_size); |
7c673cae FG |
310 | EXPECT_EQ(c_size, decoded[i].length()); |
311 | EXPECT_EQ(0, cmp); | |
312 | if (cmp != 0) { | |
313 | ++unexpected_count; | |
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; | |
319 | } | |
320 | } | |
321 | } | |
322 | if (result != 0 || dresult != 0) { | |
323 | ++unexpected_count; | |
324 | } | |
325 | } else { | |
326 | EXPECT_EQ(-EIO, result); | |
327 | EXPECT_EQ(0u, minimum_chunks.size()); | |
328 | EXPECT_EQ(-1, dresult); | |
7c673cae FG |
329 | if (result != -EIO || dresult != -1) { |
330 | ++unexpected_count; | |
331 | } | |
332 | } | |
333 | } | |
334 | } | |
7c673cae FG |
335 | } while (std::prev_permutation( |
336 | array_want_to_read, | |
337 | array_want_to_read + shec->get_chunk_count())); | |
338 | ||
339 | } while (std::prev_permutation( | |
340 | array_available_chunks, | |
341 | array_available_chunks + shec->get_chunk_count())); | |
342 | } | |
343 | } | |
344 | ||
345 | delete shec; | |
346 | delete profile; | |
347 | } | |
348 | ||
349 | int main(int argc, char **argv) | |
350 | { | |
20effc67 | 351 | auto args = argv_to_vec(argc, argv); |
7c673cae FG |
352 | |
353 | auto cct = global_init(NULL, args, CEPH_ENTITY_TYPE_CLIENT, | |
11fdf7f2 TL |
354 | CODE_ENVIRONMENT_UTILITY, |
355 | CINIT_FLAG_NO_MON_CONFIG); | |
7c673cae FG |
356 | common_init_finish(g_ceph_context); |
357 | ||
7c673cae FG |
358 | ::testing::InitGoogleTest(&argc, argv); |
359 | ||
360 | create_table_shec432(); | |
361 | ||
20effc67 | 362 | int r = RUN_ALL_TESTS(); |
7c673cae FG |
363 | |
364 | std::cout << "minimum_to_decode:total_num = " << count_num | |
365 | << std::endl; | |
366 | std::cout << "minimum_to_decode:unexpected_num = " << unexpected_count | |
367 | << std::endl; | |
368 | ||
369 | return r; | |
370 | } |