1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Bitmap allocator fragmentation benchmarks.
5 * Author: Adam Kupczyk, akupczyk@redhat.com
8 #include <boost/scoped_ptr.hpp>
9 #include <gtest/gtest.h>
10 #include <boost/random/triangle_distribution.hpp>
12 #include "common/ceph_mutex.h"
13 #include "common/Cond.h"
14 #include "common/errno.h"
15 #include "global/global_init.h"
16 #include "include/stringify.h"
17 #include "include/Context.h"
18 #include "os/bluestore/Allocator.h"
20 #include <boost/random/uniform_int.hpp>
22 typedef boost::mt11213b gen_type
;
24 #include "common/debug.h"
25 #define dout_context cct
26 #define dout_subsys ceph_subsys_
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}
62 void PrintTo(const Scenario
& s
, ::std::ostream
* os
)
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
<< ")";
71 bool verbose
= getenv("VERBOSE") != nullptr;
74 class AllocTest
: public ::testing::TestWithParam
<std::string
> {
76 boost::scoped_ptr
<AllocTracker
> at
;
78 static boost::intrusive_ptr
<CephContext
> cct
;
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
);
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);
94 uint64_t fragmented
= 0;
95 uint64_t fragments
= 0;
96 uint64_t total_fragments
= 0;
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();
102 void TearDown() final
;
103 static void SetUpTestSuite();
104 static void TearDownTestSuite();
108 uint64_t tests_cnt
= 0;
109 double fragmented_percent
= 0;
110 double fragments_count
= 0;
112 double frag_score
= 0;
115 std::map
<std::string
, test_result
> results_per_allocator
;
117 const uint64_t _1m
= 1024 * 1024;
118 const uint64_t _1G
= 1024 * 1024 * 1024;
120 const uint64_t _2m
= 2 * 1024 * 1024;
124 std::vector
<bluestore_pextent_t
> allocations
;
128 bool push(uint64_t offs
, uint32_t len
)
131 if (size
+ 1 > allocations
.size())
132 allocations
.resize(size
+ 100);
133 allocations
[size
++] = bluestore_pextent_t(offs
, len
);
137 bool pop_random(gen_type
& rng
, uint64_t* offs
, uint32_t* len
,
138 uint32_t max_len
= 0)
142 uint64_t pos
= rng() % size
;
143 *len
= allocations
[pos
].length
;
144 *offs
= allocations
[pos
].offset
;
146 if (max_len
&& *len
> max_len
) {
147 allocations
[pos
].length
= *len
- max_len
;
148 allocations
[pos
].offset
= *offs
+ max_len
;
151 allocations
[pos
] = allocations
[size
-1];
158 boost::intrusive_ptr
<CephContext
> AllocTest::cct
;
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
;
164 alloc
.reset(Allocator::create(cct
.get(), allocator_name
, size
,
166 at
.reset(new AllocTracker());
169 void AllocTest::init_close() {
174 uint32_t AllocTest::free_random() {
177 interval_set
<uint64_t> release_set
;
178 if (!at
->pop_random(rng
, &o
, &l
)) {
182 release_set
.insert(o
, l
);
183 alloc
->release(release_set
);
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();
194 while (level
< high_mark
)
196 uint32_t want
= size_generator();
198 auto r
= alloc
->allocate(want
, alloc_unit
, 0, 0, &tmp
);
204 bool full
= !at
->push(a
.offset
, a
.length
);
205 EXPECT_EQ(full
, false);
208 if (tmp
.size() > 1) {
210 total_fragments
+= r
;
211 fragments
+= tmp
.size();
213 if (leak_level
> 0) {
214 for (size_t i
=0; i
<tmp
.size(); i
++) {
215 if (uint32_t(rng()) < leak_level
) {
223 void AllocTest::do_free(uint64_t low_mark
) {
224 while (level
> low_mark
)
226 if (free_random() == 0)
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
)
237 assert(isp2(alloc_unit
));
238 cct
->_conf
->bdev_block_size
= alloc_unit
;
239 PExtentVector allocated
, tmp
;
240 init_alloc(allocator_name
, capacity
, alloc_unit
);
241 alloc
->init_add_free(0, capacity
);
243 utime_t start
= ceph_clock_now();
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
;
255 for (uint32_t i
=0; i
< iterations
; i
++)
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
;
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
;
278 double frag_score
= alloc
->get_fragmentation_score();
280 double free_frag_score
= alloc
->get_fragmentation_score();
281 ASSERT_EQ(alloc
->get_free(), capacity
);
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
;
290 auto list_free
= [&](size_t off
, size_t len
) {
294 alloc
->dump(list_free
);
295 ASSERT_EQ(sum
, capacity
);
297 std::cout
<< "free chunks sum=" << sum
<< " free chunks count=" << cnt
<< std::endl
;
300 test_result
&r
= results_per_allocator
[allocator_name
];
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
;
308 void AllocTest::SetUpTestSuite()
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());
318 void AllocTest::TearDown()
324 void AllocTest::TearDownTestSuite()
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
;
339 TEST_P(AllocTest
, test_alloc_triangle_0_8M_16M
)
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
;
348 auto size_generator
= [&]() -> uint32_t {
349 return (uint32_t(D(rng
)) + s
.alloc_unit
) & ~(s
.alloc_unit
- 1);
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
);
359 TEST_P(AllocTest
, test_alloc_8M_and_64K
)
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);
370 auto size_generator
= [&]() -> uint32_t {
372 return max_chunk_size
;
374 return min_chunk_size
;
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
);
384 TEST_P(AllocTest
, test_alloc_fragmentation_max_chunk_8M
)
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
);
395 uint32_t object_size
= 0;
397 auto size_generator
= [&]() -> uint32_t {
399 if (object_size
== 0)
400 object_size
= (uint32_t(D(rng
))* s
.alloc_unit
);
401 if (object_size
> max_chunk_size
)
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
);
416 TEST_P(AllocTest
, test_bonus_empty_fragmented
)
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
);
425 for (size_t i
= 0; i
< capacity
/ (1024 * 1024); i
++) {
427 uint32_t want
= 1024 * 1024;
428 int r
= alloc
->allocate(want
, alloc_unit
, 0, 0, &tmp
);
430 if (tmp
.size() > 1) {
431 interval_set
<uint64_t> release_set
;
433 release_set
.insert(t
.offset
, t
.length
);
435 alloc
->release(release_set
);
437 interval_set
<uint64_t> release_set
;
438 uint64_t offset
= tmp
[0].offset
;
439 uint64_t length
= tmp
[0].length
;
441 release_set
.insert(offset
+ alloc_unit
, length
- 3 * alloc_unit
);
442 alloc
->release(release_set
);
445 release_set
.insert(offset
, alloc_unit
);
446 alloc
->release(release_set
);
449 release_set
.insert(offset
+ length
- 2 * alloc_unit
, 2 * alloc_unit
);
450 alloc
->release(release_set
);
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
;
459 INSTANTIATE_TEST_SUITE_P(
462 ::testing::Values("stupid", "bitmap", "avl", "btree"));