1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * In memory space allocator test cases.
5 * Author: Ramesh Chander, Ramesh.Chander@sandisk.com
8 #include <boost/scoped_ptr.hpp>
9 #include <gtest/gtest.h>
11 #include "common/Cond.h"
12 #include "common/errno.h"
13 #include "include/stringify.h"
14 #include "include/Context.h"
15 #include "os/bluestore/Allocator.h"
19 typedef boost::mt11213b gen_type
;
21 class AllocTest
: public ::testing::TestWithParam
<const char*> {
24 boost::scoped_ptr
<Allocator
> alloc
;
25 AllocTest(): alloc(0) { }
26 void init_alloc(int64_t size
, uint64_t min_alloc_size
) {
27 std::cout
<< "Creating alloc type " << string(GetParam()) << " \n";
28 alloc
.reset(Allocator::create(g_ceph_context
, GetParam(), size
,
30 256*1048576, 100*256*1048576ull));
38 TEST_P(AllocTest
, test_alloc_init
)
41 init_alloc(blocks
, 1);
42 ASSERT_EQ(0U, alloc
->get_free());
44 blocks
= 1024 * 2 + 16;
45 init_alloc(blocks
, 1);
46 ASSERT_EQ(0U, alloc
->get_free());
49 init_alloc(blocks
, 1);
50 ASSERT_EQ(alloc
->get_free(), (uint64_t) 0);
53 TEST_P(AllocTest
, test_init_add_free
)
55 int64_t block_size
= 1024;
56 int64_t capacity
= 4 * 1024 * block_size
;
59 init_alloc(capacity
, block_size
);
61 auto free
= alloc
->get_free();
62 alloc
->init_add_free(block_size
, 0);
63 ASSERT_EQ(free
, alloc
->get_free());
65 alloc
->init_rm_free(block_size
, 0);
66 ASSERT_EQ(free
, alloc
->get_free());
70 TEST_P(AllocTest
, test_alloc_min_alloc
)
72 int64_t block_size
= 1024;
73 int64_t capacity
= 4 * 1024 * block_size
;
76 init_alloc(capacity
, block_size
);
78 alloc
->init_add_free(block_size
, block_size
);
79 PExtentVector extents
;
80 EXPECT_EQ(block_size
, alloc
->allocate(block_size
, block_size
,
81 0, (int64_t) 0, &extents
));
85 * Allocate extent and make sure all comes in single extent.
88 init_alloc(capacity
, block_size
);
89 alloc
->init_add_free(0, block_size
* 4);
90 PExtentVector extents
;
91 EXPECT_EQ(4*block_size
,
92 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
93 0, (int64_t) 0, &extents
));
94 EXPECT_EQ(1u, extents
.size());
95 EXPECT_EQ(extents
[0].length
, 4 * block_size
);
99 * Allocate extent and make sure we get two different extents.
102 init_alloc(capacity
, block_size
);
103 alloc
->init_add_free(0, block_size
* 2);
104 alloc
->init_add_free(3 * block_size
, block_size
* 2);
105 PExtentVector extents
;
107 EXPECT_EQ(4*block_size
,
108 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
109 0, (int64_t) 0, &extents
));
110 EXPECT_EQ(2u, extents
.size());
111 EXPECT_EQ(extents
[0].length
, 2 * block_size
);
112 EXPECT_EQ(extents
[1].length
, 2 * block_size
);
117 TEST_P(AllocTest
, test_alloc_min_max_alloc
)
119 int64_t block_size
= 1024;
121 int64_t capacity
= 4 * 1024 * block_size
;
122 init_alloc(capacity
, block_size
);
125 * Make sure we get all extents different when
126 * min_alloc_size == max_alloc_size
129 init_alloc(capacity
, block_size
);
130 alloc
->init_add_free(0, block_size
* 4);
131 PExtentVector extents
;
132 EXPECT_EQ(4*block_size
,
133 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
134 block_size
, (int64_t) 0, &extents
));
135 for (auto e
: extents
) {
136 EXPECT_EQ(e
.length
, block_size
);
138 EXPECT_EQ(4u, extents
.size());
143 * Make sure we get extents of length max_alloc size
144 * when max alloc size > min_alloc size
147 init_alloc(capacity
, block_size
);
148 alloc
->init_add_free(0, block_size
* 4);
149 PExtentVector extents
;
150 EXPECT_EQ(4*block_size
,
151 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
152 2 * block_size
, (int64_t) 0, &extents
));
153 EXPECT_EQ(2u, extents
.size());
154 for (auto& e
: extents
) {
155 EXPECT_EQ(e
.length
, block_size
* 2);
160 * Make sure allocations are of min_alloc_size when min_alloc_size > block_size.
163 init_alloc(capacity
, block_size
);
164 alloc
->init_add_free(0, block_size
* 1024);
165 PExtentVector extents
;
166 EXPECT_EQ(1024 * block_size
,
167 alloc
->allocate(1024 * (uint64_t)block_size
,
168 (uint64_t) block_size
* 4,
169 block_size
* 4, (int64_t) 0, &extents
));
170 for (auto& e
: extents
) {
171 EXPECT_EQ(e
.length
, block_size
* 4);
173 EXPECT_EQ(1024u/4, extents
.size());
180 init_alloc(capacity
, block_size
);
181 alloc
->init_add_free(0, block_size
* 16);
182 PExtentVector extents
;
183 EXPECT_EQ(16 * block_size
,
184 alloc
->allocate(16 * (uint64_t)block_size
, (uint64_t) block_size
,
185 2 * block_size
, (int64_t) 0, &extents
));
187 EXPECT_EQ(extents
.size(), 8u);
188 for (auto& e
: extents
) {
189 EXPECT_EQ(e
.length
, 2 * block_size
);
194 TEST_P(AllocTest
, test_alloc_failure
)
196 int64_t block_size
= 1024;
197 int64_t capacity
= 4 * 1024 * block_size
;
200 init_alloc(capacity
, block_size
);
201 alloc
->init_add_free(0, block_size
* 256);
202 alloc
->init_add_free(block_size
* 512, block_size
* 256);
204 PExtentVector extents
;
205 EXPECT_EQ(512 * block_size
,
206 alloc
->allocate(512 * (uint64_t)block_size
,
207 (uint64_t) block_size
* 256,
208 block_size
* 256, (int64_t) 0, &extents
));
209 alloc
->init_add_free(0, block_size
* 256);
210 alloc
->init_add_free(block_size
* 512, block_size
* 256);
213 alloc
->allocate(512 * (uint64_t)block_size
,
214 (uint64_t) block_size
* 512,
215 block_size
* 512, (int64_t) 0, &extents
));
219 TEST_P(AllocTest
, test_alloc_big
)
221 int64_t block_size
= 4096;
222 int64_t blocks
= 104857600;
224 init_alloc(blocks
*block_size
, block_size
);
225 alloc
->init_add_free(2*block_size
, (blocks
-2)*block_size
);
226 for (int64_t big
= mas
; big
< 1048576*128; big
*=2) {
227 cout
<< big
<< std::endl
;
228 PExtentVector extents
;
230 alloc
->allocate(big
, mas
, 0, &extents
));
234 TEST_P(AllocTest
, test_alloc_non_aligned_len
)
236 int64_t block_size
= 1 << 12;
237 int64_t blocks
= (1 << 20) * 100;
238 int64_t want_size
= 1 << 22;
239 int64_t alloc_unit
= 1 << 20;
241 init_alloc(blocks
*block_size
, block_size
);
242 alloc
->init_add_free(0, 2097152);
243 alloc
->init_add_free(2097152, 1064960);
244 alloc
->init_add_free(3670016, 2097152);
246 PExtentVector extents
;
247 EXPECT_EQ(want_size
, alloc
->allocate(want_size
, alloc_unit
, 0, &extents
));
250 TEST_P(AllocTest
, test_alloc_39334
)
252 uint64_t block
= 0x4000;
253 uint64_t size
= 0x5d00000000;
255 init_alloc(size
, block
);
256 alloc
->init_add_free(0x4000, 0x5cffffc000);
257 EXPECT_EQ(size
- block
, alloc
->get_free());
260 TEST_P(AllocTest
, test_alloc_fragmentation
)
262 uint64_t capacity
= 4 * 1024 * 1024;
263 uint64_t alloc_unit
= 4096;
264 uint64_t want_size
= alloc_unit
;
265 PExtentVector allocated
, tmp
;
267 init_alloc(capacity
, alloc_unit
);
268 alloc
->init_add_free(0, capacity
);
269 bool bitmap_alloc
= GetParam() == std::string("bitmap");
271 EXPECT_EQ(0.0, alloc
->get_fragmentation());
273 for (size_t i
= 0; i
< capacity
/ alloc_unit
; ++i
)
276 EXPECT_EQ(static_cast<int64_t>(want_size
),
277 alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
));
278 allocated
.insert(allocated
.end(), tmp
.begin(), tmp
.end());
280 // bitmap fragmentation calculation doesn't provide such constant
283 EXPECT_EQ(0.0, alloc
->get_fragmentation());
287 EXPECT_EQ(-ENOSPC
, alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
));
289 if (GetParam() == string("avl")) {
290 // AVL allocator uses a different allocating strategy
291 GTEST_SKIP() << "skipping for AVL allocator";
292 } else if (GetParam() == string("hybrid")) {
293 // AVL allocator uses a different allocating strategy
294 GTEST_SKIP() << "skipping for Hybrid allocator";
297 for (size_t i
= 0; i
< allocated
.size(); i
+= 2)
299 interval_set
<uint64_t> release_set
;
300 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
301 alloc
->release(release_set
);
303 EXPECT_EQ(1.0, alloc
->get_fragmentation());
304 EXPECT_EQ(66u, uint64_t(alloc
->get_fragmentation_score() * 100));
306 for (size_t i
= 1; i
< allocated
.size() / 2; i
+= 2)
308 interval_set
<uint64_t> release_set
;
309 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
310 alloc
->release(release_set
);
313 // fragmentation = one l1 slot is free + one l1 slot is partial
314 EXPECT_EQ(50U, uint64_t(alloc
->get_fragmentation() * 100));
316 // fragmentation approx = 257 intervals / 768 max intervals
317 EXPECT_EQ(33u, uint64_t(alloc
->get_fragmentation() * 100));
319 EXPECT_EQ(27u, uint64_t(alloc
->get_fragmentation_score() * 100));
321 for (size_t i
= allocated
.size() / 2 + 1; i
< allocated
.size(); i
+= 2)
323 interval_set
<uint64_t> release_set
;
324 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
325 alloc
->release(release_set
);
327 // doing some rounding trick as stupid allocator doesn't merge all the
328 // extents that causes some minor fragmentation (minor bug or by-design behavior?).
329 // Hence leaving just two
330 // digits after decimal point due to this.
331 EXPECT_EQ(0u, uint64_t(alloc
->get_fragmentation() * 100));
333 EXPECT_EQ(0u, uint64_t(alloc
->get_fragmentation_score() * 100));
335 EXPECT_EQ(11u, uint64_t(alloc
->get_fragmentation_score() * 100));
339 TEST_P(AllocTest
, test_dump_fragmentation_score
)
341 uint64_t capacity
= 1024 * 1024 * 1024;
342 uint64_t one_alloc_max
= 2 * 1024 * 1024;
343 uint64_t alloc_unit
= 4096;
344 uint64_t want_size
= alloc_unit
;
345 uint64_t rounds
= 10;
346 uint64_t actions_per_round
= 1000;
347 PExtentVector allocated
, tmp
;
350 init_alloc(capacity
, alloc_unit
);
351 alloc
->init_add_free(0, capacity
);
353 EXPECT_EQ(0.0, alloc
->get_fragmentation());
354 EXPECT_EQ(0.0, alloc
->get_fragmentation_score());
356 uint64_t allocated_cnt
= 0;
357 for (size_t round
= 0; round
< rounds
; round
++) {
358 for (size_t j
= 0; j
< actions_per_round
; j
++) {
360 if ( rng() % capacity
>= allocated_cnt
) {
362 want_size
= ( rng() % one_alloc_max
) / alloc_unit
* alloc_unit
+ alloc_unit
;
364 int64_t r
= alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
);
368 allocated
.push_back(t
);
374 ceph_assert(allocated
.size() > 0);
375 size_t item
= rng() % allocated
.size();
376 ceph_assert(allocated
[item
].length
> 0);
377 allocated_cnt
-= allocated
[item
].length
;
378 interval_set
<uint64_t> release_set
;
379 release_set
.insert(allocated
[item
].offset
, allocated
[item
].length
);
380 alloc
->release(release_set
);
381 std::swap(allocated
[item
], allocated
[allocated
.size() - 1]);
382 allocated
.resize(allocated
.size() - 1);
387 auto iterated_allocation
= [&](size_t off
, size_t len
) {
388 ceph_assert(len
> 0);
391 alloc
->dump(iterated_allocation
);
392 EXPECT_GT(1, alloc
->get_fragmentation_score());
393 EXPECT_EQ(capacity
, free_sum
+ allocated_cnt
);
396 for (size_t i
= 0; i
< allocated
.size(); i
++)
398 interval_set
<uint64_t> release_set
;
399 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
400 alloc
->release(release_set
);
404 TEST_P(AllocTest
, test_alloc_bug_24598
)
406 if (string(GetParam()) != "bitmap")
409 uint64_t capacity
= 0x2625a0000ull
;
410 uint64_t alloc_unit
= 0x4000;
411 uint64_t want_size
= 0x200000;
412 PExtentVector allocated
, tmp
;
414 init_alloc(capacity
, alloc_unit
);
416 alloc
->init_add_free(0x4800000, 0x100000);
417 alloc
->init_add_free(0x4a00000, 0x100000);
419 alloc
->init_rm_free(0x4800000, 0x100000);
420 alloc
->init_rm_free(0x4a00000, 0x100000);
422 alloc
->init_add_free(0x3f00000, 0x500000);
423 alloc
->init_add_free(0x4500000, 0x100000);
424 alloc
->init_add_free(0x4700000, 0x100000);
425 alloc
->init_add_free(0x4900000, 0x100000);
426 alloc
->init_add_free(0x4b00000, 0x200000);
428 EXPECT_EQ(static_cast<int64_t>(want_size
),
429 alloc
->allocate(want_size
, 0x100000, 0, 0, &tmp
));
430 EXPECT_EQ(1u, tmp
.size());
431 EXPECT_EQ(0x4b00000u
, tmp
[0].offset
);
432 EXPECT_EQ(0x200000u
, tmp
[0].length
);
435 //Verifies issue from
436 //http://tracker.ceph.com/issues/40703
438 TEST_P(AllocTest
, test_alloc_big2
)
440 int64_t block_size
= 4096;
441 int64_t blocks
= 1048576 * 2;
442 int64_t mas
= 1024*1024;
443 init_alloc(blocks
*block_size
, block_size
);
444 alloc
->init_add_free(0, blocks
* block_size
);
446 PExtentVector extents
;
447 uint64_t need
= block_size
* blocks
/ 4; // 2GB
449 alloc
->allocate(need
, mas
, 0, &extents
));
450 need
= block_size
* blocks
/ 4; // 2GB
453 alloc
->allocate(need
, mas
, 0, &extents
));
454 EXPECT_TRUE(extents
[0].length
> 0);
457 //Verifies stuck 4GB chunk allocation
460 TEST_P(AllocTest
, test_alloc_big3
)
462 int64_t block_size
= 4096;
463 int64_t blocks
= 1048576 * 2;
464 int64_t mas
= 1024*1024;
465 init_alloc(blocks
*block_size
, block_size
);
466 alloc
->init_add_free(0, blocks
* block_size
);
468 PExtentVector extents
;
469 uint64_t need
= block_size
* blocks
/ 2; // 4GB
471 alloc
->allocate(need
, mas
, 0, &extents
));
472 EXPECT_TRUE(extents
[0].length
> 0);
475 TEST_P(AllocTest
, test_alloc_contiguous
)
477 int64_t block_size
= 0x1000;
478 int64_t capacity
= block_size
* 1024 * 1024;
481 init_alloc(capacity
, block_size
);
483 alloc
->init_add_free(0, capacity
);
484 PExtentVector extents
;
485 uint64_t need
= 4 * block_size
;
487 alloc
->allocate(need
, need
,
488 0, (int64_t)0, &extents
));
489 EXPECT_EQ(1u, extents
.size());
490 EXPECT_EQ(extents
[0].offset
, 0);
491 EXPECT_EQ(extents
[0].length
, 4 * block_size
);
495 alloc
->allocate(need
, need
,
496 0, (int64_t)0, &extents
));
497 EXPECT_EQ(1u, extents
.size());
498 EXPECT_EQ(extents
[0].offset
, 4 * block_size
);
499 EXPECT_EQ(extents
[0].length
, 4 * block_size
);
505 TEST_P(AllocTest
, test_alloc_47883
)
507 uint64_t block
= 0x1000;
508 uint64_t size
= 1599858540544ul;
510 init_alloc(size
, block
);
512 alloc
->init_add_free(0x1b970000, 0x26000);
513 alloc
->init_add_free(0x1747e9d5000, 0x493000);
514 alloc
->init_add_free(0x1747ee6a000, 0x196000);
516 PExtentVector extents
;
517 auto need
= 0x3f980000;
518 auto got
= alloc
->allocate(need
, 0x10000, 0, (int64_t)0, &extents
);
520 EXPECT_EQ(got
, 0x630000);
523 TEST_P(AllocTest
, test_alloc_50656_best_fit
)
525 uint64_t block
= 0x1000;
526 uint64_t size
= 0x3b9e400000;
528 init_alloc(size
, block
);
530 // too few free extents - causes best fit mode for avls
531 for (size_t i
= 0; i
< 0x10; i
++) {
532 alloc
->init_add_free(i
* 2 * 0x100000, 0x100000);
535 alloc
->init_add_free(0x1e1bd13000, 0x404000);
537 PExtentVector extents
;
538 auto need
= 0x400000;
539 auto got
= alloc
->allocate(need
, 0x10000, 0, (int64_t)0, &extents
);
541 EXPECT_EQ(got
, 0x400000);
544 TEST_P(AllocTest
, test_alloc_50656_first_fit
)
546 uint64_t block
= 0x1000;
547 uint64_t size
= 0x3b9e400000;
549 init_alloc(size
, block
);
551 for (size_t i
= 0; i
< 0x10000; i
+= 2) {
552 alloc
->init_add_free(i
* 0x100000, 0x100000);
555 alloc
->init_add_free(0x1e1bd13000, 0x404000);
557 PExtentVector extents
;
558 auto need
= 0x400000;
559 auto got
= alloc
->allocate(need
, 0x10000, 0, (int64_t)0, &extents
);
561 EXPECT_EQ(got
, 0x400000);
564 INSTANTIATE_TEST_SUITE_P(
567 ::testing::Values("stupid", "bitmap", "avl", "hybrid"));