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 #include <boost/random/uniform_int.hpp>
18 typedef boost::mt11213b gen_type
;
20 class AllocTest
: public ::testing::TestWithParam
<const char*> {
23 boost::scoped_ptr
<Allocator
> alloc
;
24 AllocTest(): alloc(0) { }
25 void init_alloc(int64_t size
, uint64_t min_alloc_size
) {
26 std::cout
<< "Creating alloc type " << string(GetParam()) << " \n";
27 alloc
.reset(Allocator::create(g_ceph_context
, string(GetParam()), size
,
36 TEST_P(AllocTest
, test_alloc_init
)
39 init_alloc(blocks
, 1);
40 ASSERT_EQ(0U, alloc
->get_free());
42 blocks
= 1024 * 2 + 16;
43 init_alloc(blocks
, 1);
44 ASSERT_EQ(0U, alloc
->get_free());
47 init_alloc(blocks
, 1);
48 ASSERT_EQ(alloc
->get_free(), (uint64_t) 0);
51 TEST_P(AllocTest
, test_alloc_min_alloc
)
53 int64_t block_size
= 1024;
54 int64_t capacity
= 4 * 1024 * block_size
;
57 init_alloc(capacity
, block_size
);
59 alloc
->init_add_free(block_size
, block_size
);
60 PExtentVector extents
;
61 EXPECT_EQ(block_size
, alloc
->allocate(block_size
, block_size
,
62 0, (int64_t) 0, &extents
));
66 * Allocate extent and make sure all comes in single extent.
69 init_alloc(capacity
, block_size
);
70 alloc
->init_add_free(0, block_size
* 4);
71 PExtentVector extents
;
72 EXPECT_EQ(4*block_size
,
73 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
74 0, (int64_t) 0, &extents
));
75 EXPECT_EQ(1u, extents
.size());
76 EXPECT_EQ(extents
[0].length
, 4 * block_size
);
80 * Allocate extent and make sure we get two different extents.
83 init_alloc(capacity
, block_size
);
84 alloc
->init_add_free(0, block_size
* 2);
85 alloc
->init_add_free(3 * block_size
, block_size
* 2);
86 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(2u, extents
.size());
92 EXPECT_EQ(extents
[0].length
, 2 * block_size
);
93 EXPECT_EQ(extents
[1].length
, 2 * block_size
);
98 TEST_P(AllocTest
, test_alloc_min_max_alloc
)
100 int64_t block_size
= 1024;
102 int64_t capacity
= 4 * 1024 * block_size
;
103 init_alloc(capacity
, block_size
);
106 * Make sure we get all extents different when
107 * min_alloc_size == max_alloc_size
110 init_alloc(capacity
, block_size
);
111 alloc
->init_add_free(0, block_size
* 4);
112 PExtentVector extents
;
113 EXPECT_EQ(4*block_size
,
114 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
115 block_size
, (int64_t) 0, &extents
));
116 for (auto e
: extents
) {
117 EXPECT_EQ(e
.length
, block_size
);
119 EXPECT_EQ(4u, extents
.size());
124 * Make sure we get extents of length max_alloc size
125 * when max alloc size > min_alloc size
128 init_alloc(capacity
, block_size
);
129 alloc
->init_add_free(0, block_size
* 4);
130 PExtentVector extents
;
131 EXPECT_EQ(4*block_size
,
132 alloc
->allocate(4 * (uint64_t)block_size
, (uint64_t) block_size
,
133 2 * block_size
, (int64_t) 0, &extents
));
134 EXPECT_EQ(2u, extents
.size());
135 for (auto& e
: extents
) {
136 EXPECT_EQ(e
.length
, block_size
* 2);
141 * Make sure allocations are of min_alloc_size when min_alloc_size > block_size.
144 init_alloc(capacity
, block_size
);
145 alloc
->init_add_free(0, block_size
* 1024);
146 PExtentVector extents
;
147 EXPECT_EQ(1024 * block_size
,
148 alloc
->allocate(1024 * (uint64_t)block_size
,
149 (uint64_t) block_size
* 4,
150 block_size
* 4, (int64_t) 0, &extents
));
151 for (auto& e
: extents
) {
152 EXPECT_EQ(e
.length
, block_size
* 4);
154 EXPECT_EQ(1024u/4, extents
.size());
161 init_alloc(capacity
, block_size
);
162 alloc
->init_add_free(0, block_size
* 16);
163 PExtentVector extents
;
164 EXPECT_EQ(16 * block_size
,
165 alloc
->allocate(16 * (uint64_t)block_size
, (uint64_t) block_size
,
166 2 * block_size
, (int64_t) 0, &extents
));
168 EXPECT_EQ(extents
.size(), 8u);
169 for (auto& e
: extents
) {
170 EXPECT_EQ(e
.length
, 2 * block_size
);
175 TEST_P(AllocTest
, test_alloc_failure
)
177 int64_t block_size
= 1024;
178 int64_t capacity
= 4 * 1024 * block_size
;
181 init_alloc(capacity
, block_size
);
182 alloc
->init_add_free(0, block_size
* 256);
183 alloc
->init_add_free(block_size
* 512, block_size
* 256);
185 PExtentVector extents
;
186 EXPECT_EQ(512 * block_size
,
187 alloc
->allocate(512 * (uint64_t)block_size
,
188 (uint64_t) block_size
* 256,
189 block_size
* 256, (int64_t) 0, &extents
));
190 alloc
->init_add_free(0, block_size
* 256);
191 alloc
->init_add_free(block_size
* 512, block_size
* 256);
194 alloc
->allocate(512 * (uint64_t)block_size
,
195 (uint64_t) block_size
* 512,
196 block_size
* 512, (int64_t) 0, &extents
));
200 TEST_P(AllocTest
, test_alloc_big
)
202 int64_t block_size
= 4096;
203 int64_t blocks
= 104857600;
205 init_alloc(blocks
*block_size
, block_size
);
206 alloc
->init_add_free(2*block_size
, (blocks
-2)*block_size
);
207 for (int64_t big
= mas
; big
< 1048576*128; big
*=2) {
208 cout
<< big
<< std::endl
;
209 PExtentVector extents
;
211 alloc
->allocate(big
, mas
, 0, &extents
));
215 TEST_P(AllocTest
, test_alloc_non_aligned_len
)
217 int64_t block_size
= 1 << 12;
218 int64_t blocks
= (1 << 20) * 100;
219 int64_t want_size
= 1 << 22;
220 int64_t alloc_unit
= 1 << 20;
222 init_alloc(blocks
*block_size
, block_size
);
223 alloc
->init_add_free(0, 2097152);
224 alloc
->init_add_free(2097152, 1064960);
225 alloc
->init_add_free(3670016, 2097152);
227 PExtentVector extents
;
228 EXPECT_EQ(want_size
, alloc
->allocate(want_size
, alloc_unit
, 0, &extents
));
231 TEST_P(AllocTest
, test_alloc_39334
)
233 uint64_t block
= 0x4000;
234 uint64_t size
= 0x5d00000000;
236 init_alloc(size
, block
);
237 alloc
->init_add_free(0x4000, 0x5cffffc000);
238 EXPECT_EQ(size
- block
, alloc
->get_free());
241 TEST_P(AllocTest
, test_alloc_fragmentation
)
243 uint64_t capacity
= 4 * 1024 * 1024;
244 uint64_t alloc_unit
= 4096;
245 uint64_t want_size
= alloc_unit
;
246 PExtentVector allocated
, tmp
;
248 init_alloc(capacity
, alloc_unit
);
249 alloc
->init_add_free(0, capacity
);
250 bool bitmap_alloc
= GetParam() == std::string("bitmap");
252 EXPECT_EQ(0.0, alloc
->get_fragmentation());
254 for (size_t i
= 0; i
< capacity
/ alloc_unit
; ++i
)
257 EXPECT_EQ(static_cast<int64_t>(want_size
),
258 alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
));
259 allocated
.insert(allocated
.end(), tmp
.begin(), tmp
.end());
261 // bitmap fragmentation calculation doesn't provide such constant
264 EXPECT_EQ(0.0, alloc
->get_fragmentation());
267 EXPECT_EQ(-ENOSPC
, alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
));
269 if (GetParam() == string("avl")) {
270 // AVL allocator uses a different allocating strategy
271 GTEST_SKIP() << "skipping for AVL allocator";
274 for (size_t i
= 0; i
< allocated
.size(); i
+= 2)
276 interval_set
<uint64_t> release_set
;
277 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
278 alloc
->release(release_set
);
280 EXPECT_EQ(1.0, alloc
->get_fragmentation());
281 EXPECT_EQ(66u, uint64_t(alloc
->get_fragmentation_score() * 100));
283 for (size_t i
= 1; i
< allocated
.size() / 2; i
+= 2)
285 interval_set
<uint64_t> release_set
;
286 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
287 alloc
->release(release_set
);
290 // fragmentation = one l1 slot is free + one l1 slot is partial
291 EXPECT_EQ(50U, uint64_t(alloc
->get_fragmentation() * 100));
293 // fragmentation approx = 257 intervals / 768 max intervals
294 EXPECT_EQ(33u, uint64_t(alloc
->get_fragmentation() * 100));
296 EXPECT_EQ(27u, uint64_t(alloc
->get_fragmentation_score() * 100));
298 for (size_t i
= allocated
.size() / 2 + 1; i
< allocated
.size(); i
+= 2)
300 interval_set
<uint64_t> release_set
;
301 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
302 alloc
->release(release_set
);
304 // doing some rounding trick as stupid allocator doesn't merge all the
305 // extents that causes some minor fragmentation (minor bug or by-design behavior?).
306 // Hence leaving just two
307 // digits after decimal point due to this.
308 EXPECT_EQ(0u, uint64_t(alloc
->get_fragmentation() * 100));
310 EXPECT_EQ(0u, uint64_t(alloc
->get_fragmentation_score() * 100));
312 EXPECT_EQ(11u, uint64_t(alloc
->get_fragmentation_score() * 100));
316 TEST_P(AllocTest
, test_dump_fragmentation_score
)
318 uint64_t capacity
= 1024 * 1024 * 1024;
319 uint64_t one_alloc_max
= 2 * 1024 * 1024;
320 uint64_t alloc_unit
= 4096;
321 uint64_t want_size
= alloc_unit
;
322 uint64_t rounds
= 10;
323 uint64_t actions_per_round
= 1000;
324 PExtentVector allocated
, tmp
;
327 init_alloc(capacity
, alloc_unit
);
328 alloc
->init_add_free(0, capacity
);
330 EXPECT_EQ(0.0, alloc
->get_fragmentation());
331 EXPECT_EQ(0.0, alloc
->get_fragmentation_score());
333 uint64_t allocated_cnt
= 0;
334 for (size_t round
= 0; round
< rounds
; round
++) {
335 for (size_t j
= 0; j
< actions_per_round
; j
++) {
337 if ( rng() % capacity
>= allocated_cnt
) {
339 want_size
= ( rng() % one_alloc_max
) / alloc_unit
* alloc_unit
+ alloc_unit
;
341 uint64_t r
= alloc
->allocate(want_size
, alloc_unit
, 0, 0, &tmp
);
344 allocated
.push_back(t
);
349 ceph_assert(allocated
.size() > 0);
350 size_t item
= rng() % allocated
.size();
351 ceph_assert(allocated
[item
].length
> 0);
352 allocated_cnt
-= allocated
[item
].length
;
353 interval_set
<uint64_t> release_set
;
354 release_set
.insert(allocated
[item
].offset
, allocated
[item
].length
);
355 alloc
->release(release_set
);
356 std::swap(allocated
[item
], allocated
[allocated
.size() - 1]);
357 allocated
.resize(allocated
.size() - 1);
362 auto iterated_allocation
= [&](size_t off
, size_t len
) {
363 ceph_assert(len
> 0);
366 alloc
->dump(iterated_allocation
);
367 EXPECT_GT(1, alloc
->get_fragmentation_score());
368 EXPECT_EQ(capacity
, free_sum
+ allocated_cnt
);
371 for (size_t i
= 0; i
< allocated
.size(); i
++)
373 interval_set
<uint64_t> release_set
;
374 release_set
.insert(allocated
[i
].offset
, allocated
[i
].length
);
375 alloc
->release(release_set
);
379 TEST_P(AllocTest
, test_alloc_bug_24598
)
381 if (string(GetParam()) != "bitmap")
384 uint64_t capacity
= 0x2625a0000ull
;
385 uint64_t alloc_unit
= 0x4000;
386 uint64_t want_size
= 0x200000;
387 PExtentVector allocated
, tmp
;
389 init_alloc(capacity
, alloc_unit
);
391 alloc
->init_add_free(0x4800000, 0x100000);
392 alloc
->init_add_free(0x4a00000, 0x100000);
394 alloc
->init_rm_free(0x4800000, 0x100000);
395 alloc
->init_rm_free(0x4a00000, 0x100000);
397 alloc
->init_add_free(0x3f00000, 0x500000);
398 alloc
->init_add_free(0x4500000, 0x100000);
399 alloc
->init_add_free(0x4700000, 0x100000);
400 alloc
->init_add_free(0x4900000, 0x100000);
401 alloc
->init_add_free(0x4b00000, 0x200000);
403 EXPECT_EQ(static_cast<int64_t>(want_size
),
404 alloc
->allocate(want_size
, 0x100000, 0, 0, &tmp
));
405 EXPECT_EQ(1u, tmp
.size());
406 EXPECT_EQ(0x4b00000u
, tmp
[0].offset
);
407 EXPECT_EQ(0x200000u
, tmp
[0].length
);
410 //Verifies issue from
411 //http://tracker.ceph.com/issues/40703
413 TEST_P(AllocTest
, test_alloc_big2
)
415 int64_t block_size
= 4096;
416 int64_t blocks
= 1048576 * 2;
417 int64_t mas
= 1024*1024;
418 init_alloc(blocks
*block_size
, block_size
);
419 alloc
->init_add_free(0, blocks
* block_size
);
421 PExtentVector extents
;
422 uint64_t need
= block_size
* blocks
/ 4; // 2GB
424 alloc
->allocate(need
, mas
, 0, &extents
));
425 need
= block_size
* blocks
/ 4; // 2GB
427 alloc
->allocate(need
, mas
, 0, &extents
));
428 EXPECT_TRUE(extents
[0].length
> 0);
431 //Verifies stuck 4GB chunk allocation
434 TEST_P(AllocTest
, test_alloc_big3
)
436 int64_t block_size
= 4096;
437 int64_t blocks
= 1048576 * 2;
438 int64_t mas
= 1024*1024;
439 init_alloc(blocks
*block_size
, block_size
);
440 alloc
->init_add_free(0, blocks
* block_size
);
442 PExtentVector extents
;
443 uint64_t need
= block_size
* blocks
/ 2; // 4GB
445 alloc
->allocate(need
, mas
, 0, &extents
));
446 EXPECT_TRUE(extents
[0].length
> 0);
449 INSTANTIATE_TEST_SUITE_P(
452 ::testing::Values("stupid", "bitmap", "avl"));