]>
Commit | Line | Data |
---|---|---|
9f95a23c TL |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Bitmap allocator fragmentation benchmarks. | |
5 | * Author: Adam Kupczyk, akupczyk@redhat.com | |
6 | */ | |
7 | #include <iostream> | |
8 | #include <boost/scoped_ptr.hpp> | |
9 | #include <gtest/gtest.h> | |
10 | #include <boost/random/triangle_distribution.hpp> | |
11 | ||
12 | #include "common/ceph_mutex.h" | |
13 | #include "common/Cond.h" | |
14 | #include "common/errno.h" | |
20effc67 | 15 | #include "global/global_init.h" |
9f95a23c TL |
16 | #include "include/stringify.h" |
17 | #include "include/Context.h" | |
18 | #include "os/bluestore/Allocator.h" | |
19 | ||
20 | #include <boost/random/uniform_int.hpp> | |
21 | ||
22 | typedef boost::mt11213b gen_type; | |
23 | ||
24 | #include "common/debug.h" | |
20effc67 | 25 | #define dout_context cct |
9f95a23c TL |
26 | #define dout_subsys ceph_subsys_ |
27 | ||
28 | struct Scenario { | |
29 | uint64_t capacity; | |
30 | uint64_t alloc_unit; | |
31 | double high_mark; | |
32 | double low_mark; | |
33 | double leakness; | |
34 | uint32_t repeats; | |
35 | }; | |
36 | ||
37 | std::vector<Scenario> scenarios{ | |
38 | Scenario{512, 65536, 0.8, 0.6, 0.1, 3}, | |
39 | Scenario{512, 65536, 0.9, 0.7, 0.0, 3}, | |
40 | Scenario{512, 65536, 0.9, 0.7, 0.1, 3}, | |
41 | Scenario{512, 65536, 0.8, 0.6, 0.5, 3}, | |
42 | Scenario{512, 65536, 0.9, 0.7, 0.5, 3}, | |
43 | Scenario{1024, 65536, 0.8, 0.6, 0.1, 3}, | |
44 | Scenario{1024, 65536, 0.9, 0.7, 0.0, 3}, | |
45 | Scenario{1024, 65536, 0.9, 0.7, 0.1, 3}, | |
46 | Scenario{1024*2, 65536, 0.8, 0.6, 0.3, 3}, | |
47 | Scenario{1024*2, 65536, 0.9, 0.7, 0.0, 3}, | |
48 | Scenario{1024*2, 65536, 0.9, 0.7, 0.3, 3}, | |
49 | Scenario{512, 65536/16, 0.8, 0.6, 0.1, 3}, | |
50 | Scenario{512, 65536/16, 0.9, 0.7, 0.0, 3}, | |
51 | Scenario{512, 65536/16, 0.9, 0.7, 0.1, 3}, | |
52 | Scenario{512, 65536/16, 0.8, 0.6, 0.5, 3}, | |
53 | Scenario{512, 65536/16, 0.9, 0.7, 0.5, 3}, | |
54 | Scenario{1024, 65536/16, 0.8, 0.6, 0.1, 3}, | |
55 | Scenario{1024, 65536/16, 0.9, 0.7, 0.0, 3}, | |
56 | Scenario{1024, 65536/16, 0.9, 0.7, 0.1, 3}, | |
57 | Scenario{1024*2, 65536/16, 0.8, 0.6, 0.3, 3}, | |
58 | Scenario{1024*2, 65536/16, 0.9, 0.7, 0.0, 3}, | |
59 | Scenario{1024*2, 65536/16, 0.9, 0.7, 0.3, 3} | |
60 | }; | |
61 | ||
62 | void PrintTo(const Scenario& s, ::std::ostream* os) | |
63 | { | |
64 | *os << "(capacity=" << s.capacity; | |
65 | *os << "G, alloc_unit=" << s.alloc_unit; | |
66 | *os << ", high_mark=" << s.high_mark; | |
67 | *os << ", low_mark=" << s.low_mark; | |
68 | *os << ", leakness=" << s.leakness; | |
69 | *os << ", repeats=" << s.repeats << ")"; | |
70 | } | |
71 | bool verbose = getenv("VERBOSE") != nullptr; | |
72 | ||
73 | class AllocTracker; | |
74 | class AllocTest : public ::testing::TestWithParam<std::string> { | |
75 | protected: | |
76 | boost::scoped_ptr<AllocTracker> at; | |
77 | gen_type rng; | |
20effc67 TL |
78 | static boost::intrusive_ptr<CephContext> cct; |
79 | ||
9f95a23c TL |
80 | public: |
81 | boost::scoped_ptr<Allocator> alloc; | |
82 | AllocTest(): alloc(nullptr) {} | |
83 | void init_alloc(const std::string& alloc_name, int64_t size, uint64_t min_alloc_size); | |
84 | void init_close(); | |
85 | void doAgingTest(std::function<uint32_t()> size_generator, | |
86 | const std::string& alloc_name, uint64_t capacity, uint32_t alloc_unit, | |
87 | uint64_t high_mark, uint64_t low_mark, uint32_t iterations, double leak_factor = 0); | |
88 | ||
89 | uint64_t capacity; | |
90 | uint32_t alloc_unit; | |
91 | ||
92 | uint64_t level = 0; | |
93 | uint64_t allocs = 0; | |
94 | uint64_t fragmented = 0; | |
95 | uint64_t fragments = 0; | |
96 | uint64_t total_fragments = 0; | |
97 | ||
98 | void do_fill(uint64_t high_mark, std::function<uint32_t()> size_generator, double leak_factor = 0); | |
99 | void do_free(uint64_t low_mark); | |
100 | uint32_t free_random(); | |
101 | ||
20effc67 TL |
102 | void TearDown() final; |
103 | static void SetUpTestSuite(); | |
104 | static void TearDownTestSuite(); | |
9f95a23c TL |
105 | }; |
106 | ||
107 | struct test_result { | |
108 | uint64_t tests_cnt = 0; | |
109 | double fragmented_percent = 0; | |
110 | double fragments_count = 0; | |
111 | double time = 0; | |
112 | double frag_score = 0; | |
113 | }; | |
114 | ||
115 | std::map<std::string, test_result> results_per_allocator; | |
116 | ||
117 | const uint64_t _1m = 1024 * 1024; | |
118 | const uint64_t _1G = 1024 * 1024 * 1024; | |
119 | ||
120 | const uint64_t _2m = 2 * 1024 * 1024; | |
121 | ||
122 | class AllocTracker | |
123 | { | |
124 | std::vector<bluestore_pextent_t> allocations; | |
125 | uint64_t size = 0; | |
126 | ||
127 | public: | |
128 | bool push(uint64_t offs, uint32_t len) | |
129 | { | |
130 | assert(len != 0); | |
131 | if (size + 1 > allocations.size()) | |
132 | allocations.resize(size + 100); | |
133 | allocations[size++] = bluestore_pextent_t(offs, len); | |
134 | return true; | |
135 | } | |
136 | ||
137 | bool pop_random(gen_type& rng, uint64_t* offs, uint32_t* len, | |
138 | uint32_t max_len = 0) | |
139 | { | |
140 | if (size == 0) | |
141 | return false; | |
142 | uint64_t pos = rng() % size; | |
143 | *len = allocations[pos].length; | |
144 | *offs = allocations[pos].offset; | |
145 | ||
146 | if (max_len && *len > max_len) { | |
147 | allocations[pos].length = *len - max_len; | |
148 | allocations[pos].offset = *offs + max_len; | |
149 | *len = max_len; | |
150 | } else { | |
151 | allocations[pos] = allocations[size-1]; | |
152 | --size; | |
153 | } | |
154 | return true; | |
155 | } | |
156 | }; | |
157 | ||
20effc67 | 158 | boost::intrusive_ptr<CephContext> AllocTest::cct; |
9f95a23c TL |
159 | |
160 | void AllocTest::init_alloc(const std::string& allocator_name, int64_t size, uint64_t min_alloc_size) { | |
161 | this->capacity = size; | |
162 | this->alloc_unit = min_alloc_size; | |
163 | rng.seed(0); | |
20effc67 | 164 | alloc.reset(Allocator::create(cct.get(), allocator_name, size, |
9f95a23c TL |
165 | min_alloc_size)); |
166 | at.reset(new AllocTracker()); | |
167 | } | |
168 | ||
169 | void AllocTest::init_close() { | |
170 | alloc.reset(0); | |
171 | at.reset(nullptr); | |
172 | } | |
173 | ||
174 | uint32_t AllocTest::free_random() { | |
175 | uint64_t o = 0; | |
176 | uint32_t l = 0; | |
177 | interval_set<uint64_t> release_set; | |
178 | if (!at->pop_random(rng, &o, &l)) { | |
179 | //empty? | |
180 | return 0; | |
181 | } | |
182 | release_set.insert(o, l); | |
183 | alloc->release(release_set); | |
184 | level -= l; | |
185 | return l; | |
186 | } | |
187 | ||
188 | ||
189 | void AllocTest::do_fill(uint64_t high_mark, std::function<uint32_t()> size_generator, double leak_factor) { | |
190 | assert (leak_factor >= 0); | |
191 | assert (leak_factor < 1); | |
192 | uint32_t leak_level = leak_factor * std::numeric_limits<uint32_t>::max(); | |
193 | PExtentVector tmp; | |
194 | while (level < high_mark) | |
195 | { | |
196 | uint32_t want = size_generator(); | |
197 | tmp.clear(); | |
198 | auto r = alloc->allocate(want, alloc_unit, 0, 0, &tmp); | |
199 | if (r < want) { | |
200 | break; | |
201 | } | |
202 | level += r; | |
203 | for(auto a : tmp) { | |
204 | bool full = !at->push(a.offset, a.length); | |
205 | EXPECT_EQ(full, false); | |
206 | } | |
207 | allocs++; | |
208 | if (tmp.size() > 1) { | |
209 | fragmented ++; | |
210 | total_fragments += r; | |
211 | fragments += tmp.size(); | |
212 | } | |
213 | if (leak_level > 0) { | |
214 | for (size_t i=0; i<tmp.size(); i++) { | |
215 | if (uint32_t(rng()) < leak_level) { | |
216 | free_random(); | |
217 | } | |
218 | } | |
219 | } | |
220 | } | |
221 | } | |
222 | ||
223 | void AllocTest::do_free(uint64_t low_mark) { | |
224 | while (level > low_mark) | |
225 | { | |
226 | if (free_random() == 0) | |
227 | break; | |
228 | } | |
229 | } | |
230 | ||
231 | void AllocTest::doAgingTest( | |
232 | std::function<uint32_t()> size_generator, | |
233 | const std::string& allocator_name, | |
234 | uint64_t capacity, uint32_t alloc_unit, | |
235 | uint64_t high_mark, uint64_t low_mark, uint32_t iterations, double leak_factor) | |
236 | { | |
237 | assert(isp2(alloc_unit)); | |
20effc67 | 238 | cct->_conf->bdev_block_size = alloc_unit; |
9f95a23c TL |
239 | PExtentVector allocated, tmp; |
240 | init_alloc(allocator_name, capacity, alloc_unit); | |
241 | alloc->init_add_free(0, capacity); | |
242 | ||
243 | utime_t start = ceph_clock_now(); | |
244 | level = 0; | |
245 | allocs = 0; | |
246 | fragmented = 0; | |
247 | fragments = 0; | |
248 | total_fragments = 0; | |
249 | if (verbose) std::cout << "INITIAL FILL" << std::endl; | |
250 | do_fill(high_mark, size_generator, leak_factor); //initial fill with data | |
251 | if (verbose) std::cout << " fragmented allocs=" << 100.0 * fragmented / allocs << "%" << | |
252 | " #frags=" << ( fragmented != 0 ? double(fragments) / fragmented : 0 )<< | |
253 | " time=" << (ceph_clock_now() - start) * 1000 << "ms" << std::endl; | |
254 | ||
255 | for (uint32_t i=0; i < iterations; i++) | |
256 | { | |
257 | allocs = 0; | |
258 | fragmented = 0; | |
259 | fragments = 0; | |
260 | total_fragments = 0; | |
261 | ||
262 | uint64_t level_previous = level; | |
263 | start = ceph_clock_now(); | |
264 | if (verbose) std::cout << "ADDING CAPACITY " << i + 1 << std::endl; | |
265 | do_free(low_mark); //simulates adding new capacity to cluster | |
266 | if (verbose) std::cout << " level change: " << | |
267 | double(level_previous) / capacity * 100 << "% -> " << | |
268 | double(level) / capacity * 100 << "% time=" << | |
269 | (ceph_clock_now() - start) * 1000 << "ms" << std::endl; | |
270 | ||
271 | start = ceph_clock_now(); | |
272 | if (verbose) std::cout << "APPENDING " << i + 1 << std::endl; | |
273 | do_fill(high_mark, size_generator, leak_factor); //only creating elements | |
274 | if (verbose) std::cout << " fragmented allocs=" << 100.0 * fragmented / allocs << "%" << | |
275 | " #frags=" << ( fragmented != 0 ? double(fragments) / fragmented : 0 ) << | |
276 | " time=" << (ceph_clock_now() - start) * 1000 << "ms" << std::endl; | |
277 | } | |
278 | double frag_score = alloc->get_fragmentation_score(); | |
279 | do_free(0); | |
280 | double free_frag_score = alloc->get_fragmentation_score(); | |
281 | ASSERT_EQ(alloc->get_free(), capacity); | |
282 | ||
283 | std::cout << " fragmented allocs=" << 100.0 * fragmented / allocs << "%" << | |
284 | " #frags=" << ( fragmented != 0 ? double(fragments) / fragmented : 0 ) << | |
285 | " time=" << (ceph_clock_now() - start) * 1000 << "ms" << | |
286 | " frag.score=" << frag_score << " after free frag.score=" << free_frag_score << std::endl; | |
287 | ||
288 | uint64_t sum = 0; | |
289 | uint64_t cnt = 0; | |
290 | auto list_free = [&](size_t off, size_t len) { | |
291 | cnt++; | |
292 | sum+=len; | |
293 | }; | |
294 | alloc->dump(list_free); | |
295 | ASSERT_EQ(sum, capacity); | |
296 | if (verbose) | |
297 | std::cout << "free chunks sum=" << sum << " free chunks count=" << cnt << std::endl; | |
298 | ||
299 | //adding to totals | |
300 | test_result &r = results_per_allocator[allocator_name]; | |
301 | r.tests_cnt ++; | |
302 | r.fragmented_percent += 100.0 * fragmented / allocs; | |
303 | r.fragments_count += ( fragmented != 0 ? double(fragments) / fragmented : 2 ); | |
304 | r.time += ceph_clock_now() - start; | |
305 | r.frag_score += frag_score; | |
306 | } | |
307 | ||
20effc67 TL |
308 | void AllocTest::SetUpTestSuite() |
309 | { | |
310 | vector<const char*> args; | |
311 | cct = global_init(NULL, args, | |
312 | CEPH_ENTITY_TYPE_CLIENT, | |
313 | CODE_ENVIRONMENT_UTILITY, | |
314 | CINIT_FLAG_NO_DEFAULT_CONFIG_FILE); | |
315 | common_init_finish(cct.get()); | |
316 | } | |
317 | ||
318 | void AllocTest::TearDown() | |
319 | { | |
320 | at.reset(); | |
321 | alloc.reset(); | |
322 | } | |
323 | ||
324 | void AllocTest::TearDownTestSuite() | |
325 | { | |
326 | cct.reset(); | |
327 | ||
9f95a23c TL |
328 | std::cout << "Summary: " << std::endl; |
329 | for (auto& r: results_per_allocator) { | |
330 | std::cout << r.first << | |
331 | " fragmented allocs=" << r.second.fragmented_percent / r.second.tests_cnt << "%" << | |
332 | " #frags=" << r.second.fragments_count / r.second.tests_cnt << | |
333 | " free_score=" << r.second.frag_score / r.second.tests_cnt << | |
334 | " time=" << r.second.time * 1000 << "ms" << std::endl; | |
335 | } | |
336 | } | |
337 | ||
338 | ||
339 | TEST_P(AllocTest, test_alloc_triangle_0_8M_16M) | |
340 | { | |
341 | std::string allocator_name = GetParam(); | |
342 | boost::triangle_distribution<double> D(1, (8 * 1024 * 1024) , (16 * 1024 * 1024) ); | |
343 | for (auto& s:scenarios) { | |
344 | std::cout << "Allocator: " << allocator_name << ", "; | |
345 | PrintTo(s, &std::cout); | |
346 | std::cout << std::endl; | |
347 | ||
348 | auto size_generator = [&]() -> uint32_t { | |
349 | return (uint32_t(D(rng)) + s.alloc_unit) & ~(s.alloc_unit - 1); | |
350 | }; | |
351 | ||
352 | doAgingTest(size_generator, allocator_name, s.capacity * _1G, s.alloc_unit, | |
353 | s.high_mark * s.capacity * _1G, | |
354 | s.low_mark * s.capacity * _1G, | |
355 | s.repeats, s.leakness); | |
356 | } | |
357 | } | |
358 | ||
359 | TEST_P(AllocTest, test_alloc_8M_and_64K) | |
360 | { | |
361 | std::string allocator_name = GetParam(); | |
362 | constexpr uint32_t max_chunk_size = 8*1024*1024; | |
363 | constexpr uint32_t min_chunk_size = 64*1024; | |
364 | for (auto& s:scenarios) { | |
365 | std::cout << "Allocator: " << allocator_name << ", "; | |
366 | PrintTo(s, &std::cout); | |
367 | std::cout << std::endl; | |
368 | boost::uniform_int<> D(0, 1); | |
369 | ||
370 | auto size_generator = [&]() -> uint32_t { | |
371 | if (D(rng) == 0) | |
372 | return max_chunk_size; | |
373 | else | |
374 | return min_chunk_size; | |
375 | }; | |
376 | ||
377 | doAgingTest(size_generator, allocator_name, s.capacity * _1G, s.alloc_unit, | |
378 | s.high_mark * s.capacity * _1G, | |
379 | s.low_mark * s.capacity * _1G, | |
380 | s.repeats, s.leakness); | |
381 | } | |
382 | } | |
383 | ||
384 | TEST_P(AllocTest, test_alloc_fragmentation_max_chunk_8M) | |
385 | { | |
386 | std::string allocator_name = GetParam(); | |
387 | constexpr uint32_t max_object_size = 150*1000*1000; | |
388 | constexpr uint32_t max_chunk_size = 8*1024*1024; | |
389 | for (auto& s:scenarios) { | |
390 | std::cout << "Allocator: " << allocator_name << ", "; | |
391 | PrintTo(s, &std::cout); | |
392 | std::cout << std::endl; | |
393 | boost::uniform_int<> D(1, max_object_size / s.alloc_unit); | |
394 | ||
395 | uint32_t object_size = 0; | |
396 | ||
397 | auto size_generator = [&]() -> uint32_t { | |
398 | uint32_t c; | |
399 | if (object_size == 0) | |
400 | object_size = (uint32_t(D(rng))* s.alloc_unit); | |
401 | if (object_size > max_chunk_size) | |
402 | c = max_chunk_size; | |
403 | else | |
404 | c = object_size; | |
405 | object_size -= c; | |
406 | return c; | |
407 | }; | |
408 | ||
409 | doAgingTest(size_generator, allocator_name, s.capacity * _1G, s.alloc_unit, | |
410 | s.high_mark * s.capacity * _1G, | |
411 | s.low_mark * s.capacity * _1G, | |
412 | s.repeats, s.leakness); | |
413 | } | |
414 | } | |
415 | ||
416 | TEST_P(AllocTest, test_bonus_empty_fragmented) | |
417 | { | |
418 | uint64_t capacity = uint64_t(512) * 1024 * 1024 * 1024; //512 G | |
419 | uint64_t alloc_unit = 64 * 1024; | |
420 | std::string allocator_name = GetParam(); | |
421 | std::cout << "Allocator: " << allocator_name << std::endl; | |
422 | init_alloc(allocator_name, capacity, alloc_unit); | |
423 | alloc->init_add_free(0, capacity); | |
424 | PExtentVector tmp; | |
425 | for (size_t i = 0; i < capacity / (1024 * 1024); i++) { | |
426 | tmp.clear(); | |
427 | uint32_t want = 1024 * 1024; | |
428 | int r = alloc->allocate(want, alloc_unit, 0, 0, &tmp); | |
429 | ASSERT_EQ(r, want); | |
430 | if (tmp.size() > 1) { | |
431 | interval_set<uint64_t> release_set; | |
432 | for (auto& t: tmp) { | |
433 | release_set.insert(t.offset, t.length); | |
434 | } | |
435 | alloc->release(release_set); | |
436 | } else { | |
437 | interval_set<uint64_t> release_set; | |
438 | uint64_t offset = tmp[0].offset; | |
439 | uint64_t length = tmp[0].length; | |
440 | ||
441 | release_set.insert(offset + alloc_unit, length - 3 * alloc_unit); | |
442 | alloc->release(release_set); | |
443 | release_set.clear(); | |
444 | ||
445 | release_set.insert(offset , alloc_unit); | |
446 | alloc->release(release_set); | |
447 | release_set.clear(); | |
448 | ||
449 | release_set.insert(offset + length - 2 * alloc_unit, 2 * alloc_unit); | |
450 | alloc->release(release_set); | |
451 | release_set.clear(); | |
452 | } | |
453 | } | |
454 | double frag_score = alloc->get_fragmentation_score(); | |
455 | ASSERT_EQ(alloc->get_free(), capacity); | |
456 | std::cout << " empty storage frag.score=" << frag_score << std::endl; | |
457 | } | |
458 | ||
20effc67 | 459 | INSTANTIATE_TEST_SUITE_P( |
9f95a23c TL |
460 | Allocator, |
461 | AllocTest, | |
20effc67 | 462 | ::testing::Values("stupid", "bitmap", "avl", "btree")); |