]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * In memory space allocator test cases. | |
5 | * Author: Ramesh Chander, Ramesh.Chander@sandisk.com | |
6 | */ | |
7 | #include <iostream> | |
8 | #include <boost/scoped_ptr.hpp> | |
9 | #include <gtest/gtest.h> | |
10 | ||
7c673cae FG |
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" | |
7c673cae | 16 | |
a8e16298 TL |
17 | #include <boost/random/uniform_int.hpp> |
18 | typedef boost::mt11213b gen_type; | |
7c673cae | 19 | |
7c673cae | 20 | class AllocTest : public ::testing::TestWithParam<const char*> { |
a8e16298 | 21 | |
7c673cae | 22 | public: |
a8e16298 TL |
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, | |
28 | min_alloc_size)); | |
29 | } | |
7c673cae | 30 | |
a8e16298 TL |
31 | void init_close() { |
32 | alloc.reset(0); | |
33 | } | |
7c673cae FG |
34 | }; |
35 | ||
36 | TEST_P(AllocTest, test_alloc_init) | |
37 | { | |
a8e16298 | 38 | int64_t blocks = 64; |
7c673cae FG |
39 | init_alloc(blocks, 1); |
40 | ASSERT_EQ(0U, alloc->get_free()); | |
41 | alloc->shutdown(); | |
a8e16298 | 42 | blocks = 1024 * 2 + 16; |
7c673cae FG |
43 | init_alloc(blocks, 1); |
44 | ASSERT_EQ(0U, alloc->get_free()); | |
45 | alloc->shutdown(); | |
a8e16298 | 46 | blocks = 1024 * 2; |
7c673cae FG |
47 | init_alloc(blocks, 1); |
48 | ASSERT_EQ(alloc->get_free(), (uint64_t) 0); | |
49 | } | |
50 | ||
51 | TEST_P(AllocTest, test_alloc_min_alloc) | |
52 | { | |
53 | int64_t block_size = 1024; | |
a8e16298 | 54 | int64_t capacity = 4 * 1024 * block_size; |
7c673cae FG |
55 | |
56 | { | |
a8e16298 TL |
57 | init_alloc(capacity, block_size); |
58 | ||
7c673cae | 59 | alloc->init_add_free(block_size, block_size); |
a8e16298 | 60 | PExtentVector extents; |
7c673cae FG |
61 | EXPECT_EQ(block_size, alloc->allocate(block_size, block_size, |
62 | 0, (int64_t) 0, &extents)); | |
63 | } | |
64 | ||
65 | /* | |
66 | * Allocate extent and make sure all comes in single extent. | |
67 | */ | |
68 | { | |
9f95a23c | 69 | init_alloc(capacity, block_size); |
7c673cae | 70 | alloc->init_add_free(0, block_size * 4); |
a8e16298 | 71 | PExtentVector extents; |
7c673cae FG |
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); | |
77 | } | |
78 | ||
79 | /* | |
80 | * Allocate extent and make sure we get two different extents. | |
81 | */ | |
82 | { | |
9f95a23c | 83 | init_alloc(capacity, block_size); |
7c673cae FG |
84 | alloc->init_add_free(0, block_size * 2); |
85 | alloc->init_add_free(3 * block_size, block_size * 2); | |
a8e16298 | 86 | PExtentVector extents; |
7c673cae FG |
87 | |
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); | |
94 | } | |
95 | alloc->shutdown(); | |
96 | } | |
97 | ||
98 | TEST_P(AllocTest, test_alloc_min_max_alloc) | |
99 | { | |
100 | int64_t block_size = 1024; | |
7c673cae | 101 | |
a8e16298 TL |
102 | int64_t capacity = 4 * 1024 * block_size; |
103 | init_alloc(capacity, block_size); | |
7c673cae FG |
104 | |
105 | /* | |
106 | * Make sure we get all extents different when | |
107 | * min_alloc_size == max_alloc_size | |
108 | */ | |
109 | { | |
9f95a23c | 110 | init_alloc(capacity, block_size); |
7c673cae | 111 | alloc->init_add_free(0, block_size * 4); |
a8e16298 | 112 | PExtentVector extents; |
7c673cae FG |
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); | |
118 | } | |
119 | EXPECT_EQ(4u, extents.size()); | |
120 | } | |
121 | ||
122 | ||
123 | /* | |
124 | * Make sure we get extents of length max_alloc size | |
125 | * when max alloc size > min_alloc size | |
126 | */ | |
127 | { | |
9f95a23c | 128 | init_alloc(capacity, block_size); |
7c673cae | 129 | alloc->init_add_free(0, block_size * 4); |
a8e16298 | 130 | PExtentVector extents; |
7c673cae FG |
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); | |
137 | } | |
138 | } | |
139 | ||
140 | /* | |
141 | * Make sure allocations are of min_alloc_size when min_alloc_size > block_size. | |
142 | */ | |
143 | { | |
9f95a23c | 144 | init_alloc(capacity, block_size); |
7c673cae | 145 | alloc->init_add_free(0, block_size * 1024); |
a8e16298 | 146 | PExtentVector extents; |
7c673cae FG |
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); | |
153 | } | |
154 | EXPECT_EQ(1024u/4, extents.size()); | |
155 | } | |
156 | ||
157 | /* | |
158 | * Allocate and free. | |
159 | */ | |
160 | { | |
9f95a23c | 161 | init_alloc(capacity, block_size); |
7c673cae | 162 | alloc->init_add_free(0, block_size * 16); |
a8e16298 | 163 | PExtentVector extents; |
7c673cae FG |
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)); | |
167 | ||
168 | EXPECT_EQ(extents.size(), 8u); | |
169 | for (auto& e : extents) { | |
170 | EXPECT_EQ(e.length, 2 * block_size); | |
171 | } | |
172 | } | |
173 | } | |
174 | ||
175 | TEST_P(AllocTest, test_alloc_failure) | |
176 | { | |
177 | int64_t block_size = 1024; | |
a8e16298 | 178 | int64_t capacity = 4 * 1024 * block_size; |
7c673cae | 179 | |
7c673cae | 180 | { |
9f95a23c | 181 | init_alloc(capacity, block_size); |
7c673cae FG |
182 | alloc->init_add_free(0, block_size * 256); |
183 | alloc->init_add_free(block_size * 512, block_size * 256); | |
184 | ||
a8e16298 | 185 | PExtentVector extents; |
7c673cae FG |
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); | |
192 | extents.clear(); | |
7c673cae FG |
193 | EXPECT_EQ(-ENOSPC, |
194 | alloc->allocate(512 * (uint64_t)block_size, | |
195 | (uint64_t) block_size * 512, | |
196 | block_size * 512, (int64_t) 0, &extents)); | |
197 | } | |
198 | } | |
199 | ||
200 | TEST_P(AllocTest, test_alloc_big) | |
201 | { | |
202 | int64_t block_size = 4096; | |
203 | int64_t blocks = 104857600; | |
204 | int64_t mas = 4096; | |
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; | |
a8e16298 | 209 | PExtentVector extents; |
7c673cae FG |
210 | EXPECT_EQ(big, |
211 | alloc->allocate(big, mas, 0, &extents)); | |
212 | } | |
213 | } | |
214 | ||
c07f9fc5 FG |
215 | TEST_P(AllocTest, test_alloc_non_aligned_len) |
216 | { | |
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; | |
221 | ||
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); | |
226 | ||
a8e16298 | 227 | PExtentVector extents; |
c07f9fc5 FG |
228 | EXPECT_EQ(want_size, alloc->allocate(want_size, alloc_unit, 0, &extents)); |
229 | } | |
230 | ||
9f95a23c TL |
231 | TEST_P(AllocTest, test_alloc_39334) |
232 | { | |
233 | uint64_t block = 0x4000; | |
234 | uint64_t size = 0x5d00000000; | |
235 | ||
236 | init_alloc(size, block); | |
237 | alloc->init_add_free(0x4000, 0x5cffffc000); | |
238 | EXPECT_EQ(size - block, alloc->get_free()); | |
239 | } | |
240 | ||
a8e16298 TL |
241 | TEST_P(AllocTest, test_alloc_fragmentation) |
242 | { | |
243 | uint64_t capacity = 4 * 1024 * 1024; | |
244 | uint64_t alloc_unit = 4096; | |
245 | uint64_t want_size = alloc_unit; | |
246 | PExtentVector allocated, tmp; | |
247 | ||
248 | init_alloc(capacity, alloc_unit); | |
249 | alloc->init_add_free(0, capacity); | |
250 | bool bitmap_alloc = GetParam() == std::string("bitmap"); | |
251 | ||
9f95a23c | 252 | EXPECT_EQ(0.0, alloc->get_fragmentation()); |
a8e16298 TL |
253 | |
254 | for (size_t i = 0; i < capacity / alloc_unit; ++i) | |
255 | { | |
256 | tmp.clear(); | |
11fdf7f2 TL |
257 | EXPECT_EQ(static_cast<int64_t>(want_size), |
258 | alloc->allocate(want_size, alloc_unit, 0, 0, &tmp)); | |
a8e16298 TL |
259 | allocated.insert(allocated.end(), tmp.begin(), tmp.end()); |
260 | ||
261 | // bitmap fragmentation calculation doesn't provide such constant | |
262 | // estimate | |
263 | if (!bitmap_alloc) { | |
9f95a23c | 264 | EXPECT_EQ(0.0, alloc->get_fragmentation()); |
a8e16298 TL |
265 | } |
266 | } | |
267 | EXPECT_EQ(-ENOSPC, alloc->allocate(want_size, alloc_unit, 0, 0, &tmp)); | |
268 | ||
9f95a23c TL |
269 | if (GetParam() == string("avl")) { |
270 | // AVL allocator uses a different allocating strategy | |
271 | GTEST_SKIP() << "skipping for AVL allocator"; | |
272 | } | |
273 | ||
a8e16298 TL |
274 | for (size_t i = 0; i < allocated.size(); i += 2) |
275 | { | |
276 | interval_set<uint64_t> release_set; | |
277 | release_set.insert(allocated[i].offset, allocated[i].length); | |
278 | alloc->release(release_set); | |
279 | } | |
9f95a23c TL |
280 | EXPECT_EQ(1.0, alloc->get_fragmentation()); |
281 | EXPECT_EQ(66u, uint64_t(alloc->get_fragmentation_score() * 100)); | |
282 | ||
a8e16298 TL |
283 | for (size_t i = 1; i < allocated.size() / 2; i += 2) |
284 | { | |
285 | interval_set<uint64_t> release_set; | |
286 | release_set.insert(allocated[i].offset, allocated[i].length); | |
287 | alloc->release(release_set); | |
288 | } | |
289 | if (bitmap_alloc) { | |
290 | // fragmentation = one l1 slot is free + one l1 slot is partial | |
9f95a23c | 291 | EXPECT_EQ(50U, uint64_t(alloc->get_fragmentation() * 100)); |
a8e16298 TL |
292 | } else { |
293 | // fragmentation approx = 257 intervals / 768 max intervals | |
9f95a23c | 294 | EXPECT_EQ(33u, uint64_t(alloc->get_fragmentation() * 100)); |
a8e16298 | 295 | } |
9f95a23c | 296 | EXPECT_EQ(27u, uint64_t(alloc->get_fragmentation_score() * 100)); |
a8e16298 TL |
297 | |
298 | for (size_t i = allocated.size() / 2 + 1; i < allocated.size(); i += 2) | |
299 | { | |
300 | interval_set<uint64_t> release_set; | |
301 | release_set.insert(allocated[i].offset, allocated[i].length); | |
302 | alloc->release(release_set); | |
303 | } | |
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. | |
9f95a23c TL |
308 | EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation() * 100)); |
309 | if (bitmap_alloc) { | |
310 | EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation_score() * 100)); | |
311 | } else { | |
312 | EXPECT_EQ(11u, uint64_t(alloc->get_fragmentation_score() * 100)); | |
313 | } | |
a8e16298 TL |
314 | } |
315 | ||
eafe8130 TL |
316 | TEST_P(AllocTest, test_dump_fragmentation_score) |
317 | { | |
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; | |
325 | gen_type rng; | |
326 | ||
327 | init_alloc(capacity, alloc_unit); | |
328 | alloc->init_add_free(0, capacity); | |
329 | ||
9f95a23c TL |
330 | EXPECT_EQ(0.0, alloc->get_fragmentation()); |
331 | EXPECT_EQ(0.0, alloc->get_fragmentation_score()); | |
eafe8130 TL |
332 | |
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++) { | |
336 | //free or allocate ? | |
337 | if ( rng() % capacity >= allocated_cnt ) { | |
338 | //allocate | |
339 | want_size = ( rng() % one_alloc_max ) / alloc_unit * alloc_unit + alloc_unit; | |
340 | tmp.clear(); | |
341 | uint64_t r = alloc->allocate(want_size, alloc_unit, 0, 0, &tmp); | |
342 | for (auto& t: tmp) { | |
343 | if (t.length > 0) | |
344 | allocated.push_back(t); | |
345 | } | |
346 | allocated_cnt += r; | |
347 | } else { | |
348 | //free | |
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); | |
358 | } | |
359 | } | |
360 | ||
361 | size_t free_sum = 0; | |
362 | auto iterated_allocation = [&](size_t off, size_t len) { | |
363 | ceph_assert(len > 0); | |
364 | free_sum += len; | |
365 | }; | |
366 | alloc->dump(iterated_allocation); | |
367 | EXPECT_GT(1, alloc->get_fragmentation_score()); | |
368 | EXPECT_EQ(capacity, free_sum + allocated_cnt); | |
369 | } | |
370 | ||
371 | for (size_t i = 0; i < allocated.size(); i ++) | |
372 | { | |
373 | interval_set<uint64_t> release_set; | |
374 | release_set.insert(allocated[i].offset, allocated[i].length); | |
375 | alloc->release(release_set); | |
376 | } | |
377 | } | |
378 | ||
a8e16298 TL |
379 | TEST_P(AllocTest, test_alloc_bug_24598) |
380 | { | |
381 | if (string(GetParam()) != "bitmap") | |
382 | return; | |
383 | ||
384 | uint64_t capacity = 0x2625a0000ull; | |
385 | uint64_t alloc_unit = 0x4000; | |
386 | uint64_t want_size = 0x200000; | |
387 | PExtentVector allocated, tmp; | |
388 | ||
389 | init_alloc(capacity, alloc_unit); | |
390 | ||
391 | alloc->init_add_free(0x4800000, 0x100000); | |
392 | alloc->init_add_free(0x4a00000, 0x100000); | |
393 | ||
394 | alloc->init_rm_free(0x4800000, 0x100000); | |
395 | alloc->init_rm_free(0x4a00000, 0x100000); | |
396 | ||
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); | |
402 | ||
11fdf7f2 TL |
403 | EXPECT_EQ(static_cast<int64_t>(want_size), |
404 | alloc->allocate(want_size, 0x100000, 0, 0, &tmp)); | |
9f95a23c | 405 | EXPECT_EQ(1u, tmp.size()); |
11fdf7f2 TL |
406 | EXPECT_EQ(0x4b00000u, tmp[0].offset); |
407 | EXPECT_EQ(0x200000u, tmp[0].length); | |
a8e16298 | 408 | } |
7c673cae | 409 | |
494da23a TL |
410 | //Verifies issue from |
411 | //http://tracker.ceph.com/issues/40703 | |
412 | // | |
413 | TEST_P(AllocTest, test_alloc_big2) | |
414 | { | |
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); | |
9f95a23c | 420 | |
494da23a TL |
421 | PExtentVector extents; |
422 | uint64_t need = block_size * blocks / 4; // 2GB | |
423 | EXPECT_EQ(need, | |
424 | alloc->allocate(need, mas, 0, &extents)); | |
425 | need = block_size * blocks / 4; // 2GB | |
426 | EXPECT_EQ(need, | |
427 | alloc->allocate(need, mas, 0, &extents)); | |
428 | EXPECT_TRUE(extents[0].length > 0); | |
429 | } | |
430 | ||
9f95a23c TL |
431 | //Verifies stuck 4GB chunk allocation |
432 | //in StupidAllocator | |
433 | // | |
434 | TEST_P(AllocTest, test_alloc_big3) | |
435 | { | |
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); | |
7c673cae | 441 | |
9f95a23c TL |
442 | PExtentVector extents; |
443 | uint64_t need = block_size * blocks / 2; // 4GB | |
444 | EXPECT_EQ(need, | |
445 | alloc->allocate(need, mas, 0, &extents)); | |
446 | EXPECT_TRUE(extents[0].length > 0); | |
447 | } | |
7c673cae | 448 | |
9f95a23c TL |
449 | INSTANTIATE_TEST_SUITE_P( |
450 | Allocator, | |
451 | AllocTest, | |
452 | ::testing::Values("stupid", "bitmap", "avl")); |