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"
17 typedef boost::mt11213b gen_type
;
19 class AllocTest
: public ::testing::TestWithParam
<const char*> {
22 boost::scoped_ptr
<Allocator
> alloc
;
23 AllocTest(): alloc(0) { }
24 void init_alloc(int64_t size
, uint64_t min_alloc_size
) {
25 std::cout
<< "Creating alloc type " << string(GetParam()) << " \n";
26 alloc
.reset(Allocator::create(g_ceph_context
, string(GetParam()), size
,
35 TEST_P(AllocTest
, test_alloc_init
)
38 init_alloc(blocks
, 1);
39 ASSERT_EQ(0U, alloc
->get_free());
41 blocks
= 1024 * 2 + 16;
42 init_alloc(blocks
, 1);
43 ASSERT_EQ(0U, alloc
->get_free());
46 init_alloc(blocks
, 1);
47 ASSERT_EQ(alloc
->get_free(), (uint64_t) 0);
50 TEST_P(AllocTest
, test_init_add_free
)
52 int64_t block_size
= 1024;
53 int64_t capacity
= 4 * 1024 * block_size
;
56 init_alloc(capacity
, block_size
);
58 auto free
= alloc
->get_free();
59 alloc
->init_add_free(block_size
, 0);
60 ASSERT_EQ(free
, alloc
->get_free());
62 alloc
->init_rm_free(block_size
, 0);
63 ASSERT_EQ(free
, alloc
->get_free());
67 TEST_P(AllocTest
, test_alloc_min_alloc
)
69 int64_t block_size
= 1024;
70 int64_t capacity
= 4 * 1024 * block_size
;
73 init_alloc(capacity
, block_size
);
75 alloc
->init_add_free(block_size
, block_size
);
76 PExtentVector extents
;
77 EXPECT_EQ(block_size
, alloc
->allocate(block_size
, block_size
,
78 0, (int64_t) 0, &extents
));
82 * Allocate extent and make sure all comes in single extent.
85 init_alloc(capacity
, block_size
);
86 alloc
->init_add_free(0, block_size
* 4);
87 PExtentVector extents
;
88 EXPECT_EQ(4*block_size
,
89 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
90 0, (int64_t) 0, &extents
));
91 EXPECT_EQ(1u, extents
.size());
92 EXPECT_EQ(extents
[0].length
, 4 * block_size
);
96 * Allocate extent and make sure we get two different extents.
99 init_alloc(capacity
, block_size
);
100 alloc
->init_add_free(0, block_size
* 2);
101 alloc
->init_add_free(3 * block_size
, block_size
* 2);
102 PExtentVector extents
;
104 EXPECT_EQ(4*block_size
,
105 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
106 0, (int64_t) 0, &extents
));
107 EXPECT_EQ(2u, extents
.size());
108 EXPECT_EQ(extents
[0].length
, 2 * block_size
);
109 EXPECT_EQ(extents
[1].length
, 2 * block_size
);
114 TEST_P(AllocTest
, test_alloc_min_max_alloc
)
116 int64_t block_size
= 1024;
118 int64_t capacity
= 4 * 1024 * block_size
;
119 init_alloc(capacity
, block_size
);
122 * Make sure we get all extents different when
123 * min_alloc_size == max_alloc_size
126 init_alloc(capacity
, block_size
);
127 alloc
->init_add_free(0, block_size
* 4);
128 PExtentVector extents
;
129 EXPECT_EQ(4*block_size
,
130 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
131 block_size
, (int64_t) 0, &extents
));
132 for (auto e
: extents
) {
133 EXPECT_EQ(e
.length
, block_size
);
135 EXPECT_EQ(4u, extents
.size());
140 * Make sure we get extents of length max_alloc size
141 * when max alloc size > min_alloc size
144 init_alloc(capacity
, block_size
);
145 alloc
->init_add_free(0, block_size
* 4);
146 PExtentVector extents
;
147 EXPECT_EQ(4*block_size
,
148 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
149 2 * block_size
, (int64_t) 0, &extents
));
150 EXPECT_EQ(2u, extents
.size());
151 for (auto& e
: extents
) {
152 EXPECT_EQ(e
.length
, block_size
* 2);
157 * Make sure allocations are of min_alloc_size when min_alloc_size > block_size.
160 init_alloc(capacity
, block_size
);
161 alloc
->init_add_free(0, block_size
* 1024);
162 PExtentVector extents
;
163 EXPECT_EQ(1024 * block_size
,
164 alloc
->allocate(1024 * (uint64_t)block_size
,
165 (uint64_t) block_size
* 4,
166 block_size
* 4, (int64_t) 0, &extents
));
167 for (auto& e
: extents
) {
168 EXPECT_EQ(e
.length
, block_size
* 4);
170 EXPECT_EQ(1024u/4, extents
.size());
177 init_alloc(capacity
, block_size
);
178 alloc
->init_add_free(0, block_size
* 16);
179 PExtentVector extents
;
180 EXPECT_EQ(16 * block_size
,
181 alloc
->allocate(16 * (uint64_t)block_size
, (uint64_t) block_size
,
182 2 * block_size
, (int64_t) 0, &extents
));
184 EXPECT_EQ(extents
.size(), 8u);
185 for (auto& e
: extents
) {
186 EXPECT_EQ(e
.length
, 2 * block_size
);
191 TEST_P(AllocTest
, test_alloc_failure
)
193 int64_t block_size
= 1024;
194 int64_t capacity
= 4 * 1024 * block_size
;
197 init_alloc(capacity
, block_size
);
198 alloc
->init_add_free(0, block_size
* 256);
199 alloc
->init_add_free(block_size
* 512, block_size
* 256);
201 PExtentVector extents
;
202 EXPECT_EQ(512 * block_size
,
203 alloc
->allocate(512 * (uint64_t)block_size
,
204 (uint64_t) block_size
* 256,
205 block_size
* 256, (int64_t) 0, &extents
));
206 alloc
->init_add_free(0, block_size
* 256);
207 alloc
->init_add_free(block_size
* 512, block_size
* 256);
210 alloc
->allocate(512 * (uint64_t)block_size
,
211 (uint64_t) block_size
* 512,
212 block_size
* 512, (int64_t) 0, &extents
));
216 TEST_P(AllocTest
, test_alloc_big
)
218 int64_t block_size
= 4096;
219 int64_t blocks
= 104857600;
221 init_alloc(blocks
*block_size
, block_size
);
222 alloc
->init_add_free(2*block_size
, (blocks
-2)*block_size
);
223 for (int64_t big
= mas
; big
< 1048576*128; big
*=2) {
224 cout
<< big
<< std::endl
;
225 PExtentVector extents
;
227 alloc
->allocate(big
, mas
, 0, &extents
));
231 TEST_P(AllocTest
, test_alloc_non_aligned_len
)
233 int64_t block_size
= 1 << 12;
234 int64_t blocks
= (1 << 20) * 100;
235 int64_t want_size
= 1 << 22;
236 int64_t alloc_unit
= 1 << 20;
238 init_alloc(blocks
*block_size
, block_size
);
239 alloc
->init_add_free(0, 2097152);
240 alloc
->init_add_free(2097152, 1064960);
241 alloc
->init_add_free(3670016, 2097152);
243 PExtentVector extents
;
244 EXPECT_EQ(want_size
, alloc
->allocate(want_size
, alloc_unit
, 0, &extents
));
247 TEST_P(AllocTest
, test_alloc_39334
)
249 uint64_t block
= 0x4000;
250 uint64_t size
= 0x5d00000000;
252 init_alloc(size
, block
);
253 alloc
->init_add_free(0x4000, 0x5cffffc000);
254 EXPECT_EQ(size
- block
, alloc
->get_free());
257 TEST_P(AllocTest
, test_alloc_fragmentation
)
259 uint64_t capacity
= 4 * 1024 * 1024;
260 uint64_t alloc_unit
= 4096;
261 uint64_t want_size
= alloc_unit
;
262 PExtentVector allocated
, tmp
;
264 init_alloc(capacity
, alloc_unit
);
265 alloc
->init_add_free(0, capacity
);
266 bool bitmap_alloc
= GetParam() == std::string("bitmap");
268 EXPECT_EQ(0.0, alloc
->get_fragmentation());
270 for (size_t i
= 0; i
< capacity
/ alloc_unit
; ++i
)
273 EXPECT_EQ(static_cast<int64_t>(want_size
),
274 alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
));
275 allocated
.insert(allocated
.end(), tmp
.begin(), tmp
.end());
277 // bitmap fragmentation calculation doesn't provide such constant
280 EXPECT_EQ(0.0, alloc
->get_fragmentation());
284 EXPECT_EQ(-ENOSPC
, alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
));
286 if (GetParam() == string("avl")) {
287 // AVL allocator uses a different allocating strategy
288 GTEST_SKIP() << "skipping for AVL allocator";
289 } else if (GetParam() == string("hybrid")) {
290 // AVL allocator uses a different allocating strategy
291 GTEST_SKIP() << "skipping for Hybrid allocator";
294 for (size_t i
= 0; i
< allocated
.size(); i
+= 2)
296 interval_set
<uint64_t> release_set
;
297 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
298 alloc
->release(release_set
);
300 EXPECT_EQ(1.0, alloc
->get_fragmentation());
301 EXPECT_EQ(66u, uint64_t(alloc
->get_fragmentation_score() * 100));
303 for (size_t i
= 1; i
< allocated
.size() / 2; i
+= 2)
305 interval_set
<uint64_t> release_set
;
306 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
307 alloc
->release(release_set
);
310 // fragmentation = one l1 slot is free + one l1 slot is partial
311 EXPECT_EQ(50U, uint64_t(alloc
->get_fragmentation() * 100));
313 // fragmentation approx = 257 intervals / 768 max intervals
314 EXPECT_EQ(33u, uint64_t(alloc
->get_fragmentation() * 100));
316 EXPECT_EQ(27u, uint64_t(alloc
->get_fragmentation_score() * 100));
318 for (size_t i
= allocated
.size() / 2 + 1; i
< allocated
.size(); i
+= 2)
320 interval_set
<uint64_t> release_set
;
321 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
322 alloc
->release(release_set
);
324 // doing some rounding trick as stupid allocator doesn't merge all the
325 // extents that causes some minor fragmentation (minor bug or by-design behavior?).
326 // Hence leaving just two
327 // digits after decimal point due to this.
328 EXPECT_EQ(0u, uint64_t(alloc
->get_fragmentation() * 100));
330 EXPECT_EQ(0u, uint64_t(alloc
->get_fragmentation_score() * 100));
332 EXPECT_EQ(11u, uint64_t(alloc
->get_fragmentation_score() * 100));
336 TEST_P(AllocTest
, test_dump_fragmentation_score
)
338 uint64_t capacity
= 1024 * 1024 * 1024;
339 uint64_t one_alloc_max
= 2 * 1024 * 1024;
340 uint64_t alloc_unit
= 4096;
341 uint64_t want_size
= alloc_unit
;
342 uint64_t rounds
= 10;
343 uint64_t actions_per_round
= 1000;
344 PExtentVector allocated
, tmp
;
347 init_alloc(capacity
, alloc_unit
);
348 alloc
->init_add_free(0, capacity
);
350 EXPECT_EQ(0.0, alloc
->get_fragmentation());
351 EXPECT_EQ(0.0, alloc
->get_fragmentation_score());
353 uint64_t allocated_cnt
= 0;
354 for (size_t round
= 0; round
< rounds
; round
++) {
355 for (size_t j
= 0; j
< actions_per_round
; j
++) {
357 if ( rng() % capacity
>= allocated_cnt
) {
359 want_size
= ( rng() % one_alloc_max
) / alloc_unit
* alloc_unit
+ alloc_unit
;
361 uint64_t r
= alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
);
364 allocated
.push_back(t
);
369 ceph_assert(allocated
.size() > 0);
370 size_t item
= rng() % allocated
.size();
371 ceph_assert(allocated
[item
].length
> 0);
372 allocated_cnt
-= allocated
[item
].length
;
373 interval_set
<uint64_t> release_set
;
374 release_set
.insert(allocated
[item
].offset
, allocated
[item
].length
);
375 alloc
->release(release_set
);
376 std::swap(allocated
[item
], allocated
[allocated
.size() - 1]);
377 allocated
.resize(allocated
.size() - 1);
382 auto iterated_allocation
= [&](size_t off
, size_t len
) {
383 ceph_assert(len
> 0);
386 alloc
->dump(iterated_allocation
);
387 EXPECT_GT(1, alloc
->get_fragmentation_score());
388 EXPECT_EQ(capacity
, free_sum
+ allocated_cnt
);
391 for (size_t i
= 0; i
< allocated
.size(); i
++)
393 interval_set
<uint64_t> release_set
;
394 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
395 alloc
->release(release_set
);
399 TEST_P(AllocTest
, test_alloc_bug_24598
)
401 if (string(GetParam()) != "bitmap")
404 uint64_t capacity
= 0x2625a0000ull
;
405 uint64_t alloc_unit
= 0x4000;
406 uint64_t want_size
= 0x200000;
407 PExtentVector allocated
, tmp
;
409 init_alloc(capacity
, alloc_unit
);
411 alloc
->init_add_free(0x4800000, 0x100000);
412 alloc
->init_add_free(0x4a00000, 0x100000);
414 alloc
->init_rm_free(0x4800000, 0x100000);
415 alloc
->init_rm_free(0x4a00000, 0x100000);
417 alloc
->init_add_free(0x3f00000, 0x500000);
418 alloc
->init_add_free(0x4500000, 0x100000);
419 alloc
->init_add_free(0x4700000, 0x100000);
420 alloc
->init_add_free(0x4900000, 0x100000);
421 alloc
->init_add_free(0x4b00000, 0x200000);
423 EXPECT_EQ(static_cast<int64_t>(want_size
),
424 alloc
->allocate(want_size
, 0x100000, 0, 0, &tmp
));
425 EXPECT_EQ(1u, tmp
.size());
426 EXPECT_EQ(0x4b00000u
, tmp
[0].offset
);
427 EXPECT_EQ(0x200000u
, tmp
[0].length
);
430 //Verifies issue from
431 //http://tracker.ceph.com/issues/40703
433 TEST_P(AllocTest
, test_alloc_big2
)
435 int64_t block_size
= 4096;
436 int64_t blocks
= 1048576 * 2;
437 int64_t mas
= 1024*1024;
438 init_alloc(blocks
*block_size
, block_size
);
439 alloc
->init_add_free(0, blocks
* block_size
);
441 PExtentVector extents
;
442 uint64_t need
= block_size
* blocks
/ 4; // 2GB
444 alloc
->allocate(need
, mas
, 0, &extents
));
445 need
= block_size
* blocks
/ 4; // 2GB
448 alloc
->allocate(need
, mas
, 0, &extents
));
449 EXPECT_TRUE(extents
[0].length
> 0);
452 //Verifies stuck 4GB chunk allocation
455 TEST_P(AllocTest
, test_alloc_big3
)
457 int64_t block_size
= 4096;
458 int64_t blocks
= 1048576 * 2;
459 int64_t mas
= 1024*1024;
460 init_alloc(blocks
*block_size
, block_size
);
461 alloc
->init_add_free(0, blocks
* block_size
);
463 PExtentVector extents
;
464 uint64_t need
= block_size
* blocks
/ 2; // 4GB
466 alloc
->allocate(need
, mas
, 0, &extents
));
467 EXPECT_TRUE(extents
[0].length
> 0);
470 TEST_P(AllocTest
, test_alloc_contiguous
)
472 int64_t block_size
= 0x1000;
473 int64_t capacity
= block_size
* 1024 * 1024;
476 init_alloc(capacity
, block_size
);
478 alloc
->init_add_free(0, capacity
);
479 PExtentVector extents
;
480 uint64_t need
= 4 * block_size
;
482 alloc
->allocate(need
, need
,
483 0, (int64_t)0, &extents
));
484 EXPECT_EQ(1u, extents
.size());
485 EXPECT_EQ(extents
[0].offset
, 0);
486 EXPECT_EQ(extents
[0].length
, 4 * block_size
);
490 alloc
->allocate(need
, need
,
491 0, (int64_t)0, &extents
));
492 EXPECT_EQ(1u, extents
.size());
493 EXPECT_EQ(extents
[0].offset
, 4 * block_size
);
494 EXPECT_EQ(extents
[0].length
, 4 * block_size
);
500 TEST_P(AllocTest
, test_alloc_47883
)
502 uint64_t block
= 0x1000;
503 uint64_t size
= 1599858540544ul;
505 init_alloc(size
, block
);
507 alloc
->init_add_free(0x1b970000, 0x26000);
508 alloc
->init_add_free(0x1747e9d5000, 0x493000);
509 alloc
->init_add_free(0x1747ee6a000, 0x196000);
511 PExtentVector extents
;
512 auto need
= 0x3f980000;
513 auto got
= alloc
->allocate(need
, 0x10000, 0, (int64_t)0, &extents
);
515 EXPECT_EQ(got
, 0x630000);
518 TEST_P(AllocTest
, test_alloc_50656_best_fit
)
520 uint64_t block
= 0x1000;
521 uint64_t size
= 0x3b9e400000;
523 init_alloc(size
, block
);
525 // too few free extents - causes best fit mode for avls
526 for (size_t i
= 0; i
< 0x10; i
++) {
527 alloc
->init_add_free(i
* 2 * 0x100000, 0x100000);
530 alloc
->init_add_free(0x1e1bd13000, 0x404000);
532 PExtentVector extents
;
533 auto need
= 0x400000;
534 auto got
= alloc
->allocate(need
, 0x10000, 0, (int64_t)0, &extents
);
536 EXPECT_EQ(got
, 0x400000);
539 TEST_P(AllocTest
, test_alloc_50656_first_fit
)
541 uint64_t block
= 0x1000;
542 uint64_t size
= 0x3b9e400000;
544 init_alloc(size
, block
);
546 for (size_t i
= 0; i
< 0x10000; i
+= 2) {
547 alloc
->init_add_free(i
* 0x100000, 0x100000);
550 alloc
->init_add_free(0x1e1bd13000, 0x404000);
552 PExtentVector extents
;
553 auto need
= 0x400000;
554 auto got
= alloc
->allocate(need
, 0x10000, 0, (int64_t)0, &extents
);
556 EXPECT_EQ(got
, 0x400000);
559 INSTANTIATE_TEST_SUITE_P(
562 ::testing::Values("stupid", "bitmap", "avl", "hybrid"));