]>
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 | 17 | typedef boost::mt11213b gen_type; |
7c673cae | 18 | |
7c673cae | 19 | class AllocTest : public ::testing::TestWithParam<const char*> { |
a8e16298 | 20 | |
7c673cae | 21 | public: |
a8e16298 TL |
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, | |
27 | min_alloc_size)); | |
28 | } | |
7c673cae | 29 | |
a8e16298 TL |
30 | void init_close() { |
31 | alloc.reset(0); | |
32 | } | |
7c673cae FG |
33 | }; |
34 | ||
35 | TEST_P(AllocTest, test_alloc_init) | |
36 | { | |
a8e16298 | 37 | int64_t blocks = 64; |
7c673cae FG |
38 | init_alloc(blocks, 1); |
39 | ASSERT_EQ(0U, alloc->get_free()); | |
40 | alloc->shutdown(); | |
a8e16298 | 41 | blocks = 1024 * 2 + 16; |
7c673cae FG |
42 | init_alloc(blocks, 1); |
43 | ASSERT_EQ(0U, alloc->get_free()); | |
44 | alloc->shutdown(); | |
a8e16298 | 45 | blocks = 1024 * 2; |
7c673cae FG |
46 | init_alloc(blocks, 1); |
47 | ASSERT_EQ(alloc->get_free(), (uint64_t) 0); | |
48 | } | |
49 | ||
ec96510d FG |
50 | TEST_P(AllocTest, test_init_add_free) |
51 | { | |
52 | int64_t block_size = 1024; | |
53 | int64_t capacity = 4 * 1024 * block_size; | |
54 | ||
55 | { | |
56 | init_alloc(capacity, block_size); | |
57 | ||
58 | auto free = alloc->get_free(); | |
59 | alloc->init_add_free(block_size, 0); | |
60 | ASSERT_EQ(free, alloc->get_free()); | |
61 | ||
62 | alloc->init_rm_free(block_size, 0); | |
63 | ASSERT_EQ(free, alloc->get_free()); | |
64 | } | |
65 | } | |
66 | ||
7c673cae FG |
67 | TEST_P(AllocTest, test_alloc_min_alloc) |
68 | { | |
69 | int64_t block_size = 1024; | |
a8e16298 | 70 | int64_t capacity = 4 * 1024 * block_size; |
7c673cae FG |
71 | |
72 | { | |
a8e16298 TL |
73 | init_alloc(capacity, block_size); |
74 | ||
7c673cae | 75 | alloc->init_add_free(block_size, block_size); |
a8e16298 | 76 | PExtentVector extents; |
7c673cae FG |
77 | EXPECT_EQ(block_size, alloc->allocate(block_size, block_size, |
78 | 0, (int64_t) 0, &extents)); | |
79 | } | |
80 | ||
81 | /* | |
82 | * Allocate extent and make sure all comes in single extent. | |
83 | */ | |
84 | { | |
9f95a23c | 85 | init_alloc(capacity, block_size); |
7c673cae | 86 | alloc->init_add_free(0, block_size * 4); |
a8e16298 | 87 | PExtentVector extents; |
7c673cae FG |
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); | |
93 | } | |
94 | ||
95 | /* | |
96 | * Allocate extent and make sure we get two different extents. | |
97 | */ | |
98 | { | |
9f95a23c | 99 | init_alloc(capacity, block_size); |
7c673cae FG |
100 | alloc->init_add_free(0, block_size * 2); |
101 | alloc->init_add_free(3 * block_size, block_size * 2); | |
a8e16298 | 102 | PExtentVector extents; |
7c673cae FG |
103 | |
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); | |
110 | } | |
111 | alloc->shutdown(); | |
112 | } | |
113 | ||
114 | TEST_P(AllocTest, test_alloc_min_max_alloc) | |
115 | { | |
116 | int64_t block_size = 1024; | |
7c673cae | 117 | |
a8e16298 TL |
118 | int64_t capacity = 4 * 1024 * block_size; |
119 | init_alloc(capacity, block_size); | |
7c673cae FG |
120 | |
121 | /* | |
122 | * Make sure we get all extents different when | |
123 | * min_alloc_size == max_alloc_size | |
124 | */ | |
125 | { | |
9f95a23c | 126 | init_alloc(capacity, block_size); |
7c673cae | 127 | alloc->init_add_free(0, block_size * 4); |
a8e16298 | 128 | PExtentVector extents; |
7c673cae FG |
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); | |
134 | } | |
135 | EXPECT_EQ(4u, extents.size()); | |
136 | } | |
137 | ||
138 | ||
139 | /* | |
140 | * Make sure we get extents of length max_alloc size | |
141 | * when max alloc size > min_alloc size | |
142 | */ | |
143 | { | |
9f95a23c | 144 | init_alloc(capacity, block_size); |
7c673cae | 145 | alloc->init_add_free(0, block_size * 4); |
a8e16298 | 146 | PExtentVector extents; |
7c673cae FG |
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); | |
153 | } | |
154 | } | |
155 | ||
156 | /* | |
157 | * Make sure allocations are of min_alloc_size when min_alloc_size > block_size. | |
158 | */ | |
159 | { | |
9f95a23c | 160 | init_alloc(capacity, block_size); |
7c673cae | 161 | alloc->init_add_free(0, block_size * 1024); |
a8e16298 | 162 | PExtentVector extents; |
7c673cae FG |
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); | |
169 | } | |
170 | EXPECT_EQ(1024u/4, extents.size()); | |
171 | } | |
172 | ||
173 | /* | |
174 | * Allocate and free. | |
175 | */ | |
176 | { | |
9f95a23c | 177 | init_alloc(capacity, block_size); |
7c673cae | 178 | alloc->init_add_free(0, block_size * 16); |
a8e16298 | 179 | PExtentVector extents; |
7c673cae FG |
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)); | |
183 | ||
184 | EXPECT_EQ(extents.size(), 8u); | |
185 | for (auto& e : extents) { | |
186 | EXPECT_EQ(e.length, 2 * block_size); | |
187 | } | |
188 | } | |
189 | } | |
190 | ||
191 | TEST_P(AllocTest, test_alloc_failure) | |
192 | { | |
193 | int64_t block_size = 1024; | |
a8e16298 | 194 | int64_t capacity = 4 * 1024 * block_size; |
7c673cae | 195 | |
7c673cae | 196 | { |
9f95a23c | 197 | init_alloc(capacity, block_size); |
7c673cae FG |
198 | alloc->init_add_free(0, block_size * 256); |
199 | alloc->init_add_free(block_size * 512, block_size * 256); | |
200 | ||
a8e16298 | 201 | PExtentVector extents; |
7c673cae FG |
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); | |
208 | extents.clear(); | |
7c673cae FG |
209 | EXPECT_EQ(-ENOSPC, |
210 | alloc->allocate(512 * (uint64_t)block_size, | |
211 | (uint64_t) block_size * 512, | |
212 | block_size * 512, (int64_t) 0, &extents)); | |
213 | } | |
214 | } | |
215 | ||
216 | TEST_P(AllocTest, test_alloc_big) | |
217 | { | |
218 | int64_t block_size = 4096; | |
219 | int64_t blocks = 104857600; | |
220 | int64_t mas = 4096; | |
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; | |
a8e16298 | 225 | PExtentVector extents; |
7c673cae FG |
226 | EXPECT_EQ(big, |
227 | alloc->allocate(big, mas, 0, &extents)); | |
228 | } | |
229 | } | |
230 | ||
c07f9fc5 FG |
231 | TEST_P(AllocTest, test_alloc_non_aligned_len) |
232 | { | |
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; | |
237 | ||
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); | |
242 | ||
a8e16298 | 243 | PExtentVector extents; |
c07f9fc5 FG |
244 | EXPECT_EQ(want_size, alloc->allocate(want_size, alloc_unit, 0, &extents)); |
245 | } | |
246 | ||
9f95a23c TL |
247 | TEST_P(AllocTest, test_alloc_39334) |
248 | { | |
249 | uint64_t block = 0x4000; | |
250 | uint64_t size = 0x5d00000000; | |
251 | ||
252 | init_alloc(size, block); | |
253 | alloc->init_add_free(0x4000, 0x5cffffc000); | |
254 | EXPECT_EQ(size - block, alloc->get_free()); | |
255 | } | |
256 | ||
a8e16298 TL |
257 | TEST_P(AllocTest, test_alloc_fragmentation) |
258 | { | |
259 | uint64_t capacity = 4 * 1024 * 1024; | |
260 | uint64_t alloc_unit = 4096; | |
261 | uint64_t want_size = alloc_unit; | |
262 | PExtentVector allocated, tmp; | |
263 | ||
264 | init_alloc(capacity, alloc_unit); | |
265 | alloc->init_add_free(0, capacity); | |
266 | bool bitmap_alloc = GetParam() == std::string("bitmap"); | |
267 | ||
9f95a23c | 268 | EXPECT_EQ(0.0, alloc->get_fragmentation()); |
a8e16298 TL |
269 | |
270 | for (size_t i = 0; i < capacity / alloc_unit; ++i) | |
271 | { | |
272 | tmp.clear(); | |
11fdf7f2 TL |
273 | EXPECT_EQ(static_cast<int64_t>(want_size), |
274 | alloc->allocate(want_size, alloc_unit, 0, 0, &tmp)); | |
a8e16298 TL |
275 | allocated.insert(allocated.end(), tmp.begin(), tmp.end()); |
276 | ||
277 | // bitmap fragmentation calculation doesn't provide such constant | |
278 | // estimate | |
279 | if (!bitmap_alloc) { | |
9f95a23c | 280 | EXPECT_EQ(0.0, alloc->get_fragmentation()); |
a8e16298 TL |
281 | } |
282 | } | |
e306af50 | 283 | tmp.clear(); |
a8e16298 TL |
284 | EXPECT_EQ(-ENOSPC, alloc->allocate(want_size, alloc_unit, 0, 0, &tmp)); |
285 | ||
9f95a23c TL |
286 | if (GetParam() == string("avl")) { |
287 | // AVL allocator uses a different allocating strategy | |
288 | GTEST_SKIP() << "skipping for AVL allocator"; | |
e306af50 TL |
289 | } else if (GetParam() == string("hybrid")) { |
290 | // AVL allocator uses a different allocating strategy | |
291 | GTEST_SKIP() << "skipping for Hybrid allocator"; | |
9f95a23c TL |
292 | } |
293 | ||
a8e16298 TL |
294 | for (size_t i = 0; i < allocated.size(); i += 2) |
295 | { | |
296 | interval_set<uint64_t> release_set; | |
297 | release_set.insert(allocated[i].offset, allocated[i].length); | |
298 | alloc->release(release_set); | |
299 | } | |
9f95a23c TL |
300 | EXPECT_EQ(1.0, alloc->get_fragmentation()); |
301 | EXPECT_EQ(66u, uint64_t(alloc->get_fragmentation_score() * 100)); | |
302 | ||
a8e16298 TL |
303 | for (size_t i = 1; i < allocated.size() / 2; i += 2) |
304 | { | |
305 | interval_set<uint64_t> release_set; | |
306 | release_set.insert(allocated[i].offset, allocated[i].length); | |
307 | alloc->release(release_set); | |
308 | } | |
309 | if (bitmap_alloc) { | |
310 | // fragmentation = one l1 slot is free + one l1 slot is partial | |
9f95a23c | 311 | EXPECT_EQ(50U, uint64_t(alloc->get_fragmentation() * 100)); |
a8e16298 TL |
312 | } else { |
313 | // fragmentation approx = 257 intervals / 768 max intervals | |
9f95a23c | 314 | EXPECT_EQ(33u, uint64_t(alloc->get_fragmentation() * 100)); |
a8e16298 | 315 | } |
9f95a23c | 316 | EXPECT_EQ(27u, uint64_t(alloc->get_fragmentation_score() * 100)); |
a8e16298 TL |
317 | |
318 | for (size_t i = allocated.size() / 2 + 1; i < allocated.size(); i += 2) | |
319 | { | |
320 | interval_set<uint64_t> release_set; | |
321 | release_set.insert(allocated[i].offset, allocated[i].length); | |
322 | alloc->release(release_set); | |
323 | } | |
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. | |
9f95a23c TL |
328 | EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation() * 100)); |
329 | if (bitmap_alloc) { | |
330 | EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation_score() * 100)); | |
331 | } else { | |
332 | EXPECT_EQ(11u, uint64_t(alloc->get_fragmentation_score() * 100)); | |
333 | } | |
a8e16298 TL |
334 | } |
335 | ||
eafe8130 TL |
336 | TEST_P(AllocTest, test_dump_fragmentation_score) |
337 | { | |
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; | |
345 | gen_type rng; | |
346 | ||
347 | init_alloc(capacity, alloc_unit); | |
348 | alloc->init_add_free(0, capacity); | |
349 | ||
9f95a23c TL |
350 | EXPECT_EQ(0.0, alloc->get_fragmentation()); |
351 | EXPECT_EQ(0.0, alloc->get_fragmentation_score()); | |
eafe8130 TL |
352 | |
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++) { | |
356 | //free or allocate ? | |
357 | if ( rng() % capacity >= allocated_cnt ) { | |
358 | //allocate | |
359 | want_size = ( rng() % one_alloc_max ) / alloc_unit * alloc_unit + alloc_unit; | |
360 | tmp.clear(); | |
361 | uint64_t r = alloc->allocate(want_size, alloc_unit, 0, 0, &tmp); | |
362 | for (auto& t: tmp) { | |
363 | if (t.length > 0) | |
364 | allocated.push_back(t); | |
365 | } | |
366 | allocated_cnt += r; | |
367 | } else { | |
368 | //free | |
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); | |
378 | } | |
379 | } | |
380 | ||
381 | size_t free_sum = 0; | |
382 | auto iterated_allocation = [&](size_t off, size_t len) { | |
383 | ceph_assert(len > 0); | |
384 | free_sum += len; | |
385 | }; | |
386 | alloc->dump(iterated_allocation); | |
387 | EXPECT_GT(1, alloc->get_fragmentation_score()); | |
388 | EXPECT_EQ(capacity, free_sum + allocated_cnt); | |
389 | } | |
390 | ||
391 | for (size_t i = 0; i < allocated.size(); i ++) | |
392 | { | |
393 | interval_set<uint64_t> release_set; | |
394 | release_set.insert(allocated[i].offset, allocated[i].length); | |
395 | alloc->release(release_set); | |
396 | } | |
397 | } | |
398 | ||
a8e16298 TL |
399 | TEST_P(AllocTest, test_alloc_bug_24598) |
400 | { | |
401 | if (string(GetParam()) != "bitmap") | |
402 | return; | |
403 | ||
404 | uint64_t capacity = 0x2625a0000ull; | |
405 | uint64_t alloc_unit = 0x4000; | |
406 | uint64_t want_size = 0x200000; | |
407 | PExtentVector allocated, tmp; | |
408 | ||
409 | init_alloc(capacity, alloc_unit); | |
410 | ||
411 | alloc->init_add_free(0x4800000, 0x100000); | |
412 | alloc->init_add_free(0x4a00000, 0x100000); | |
413 | ||
414 | alloc->init_rm_free(0x4800000, 0x100000); | |
415 | alloc->init_rm_free(0x4a00000, 0x100000); | |
416 | ||
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); | |
422 | ||
11fdf7f2 TL |
423 | EXPECT_EQ(static_cast<int64_t>(want_size), |
424 | alloc->allocate(want_size, 0x100000, 0, 0, &tmp)); | |
9f95a23c | 425 | EXPECT_EQ(1u, tmp.size()); |
11fdf7f2 TL |
426 | EXPECT_EQ(0x4b00000u, tmp[0].offset); |
427 | EXPECT_EQ(0x200000u, tmp[0].length); | |
a8e16298 | 428 | } |
7c673cae | 429 | |
494da23a TL |
430 | //Verifies issue from |
431 | //http://tracker.ceph.com/issues/40703 | |
432 | // | |
433 | TEST_P(AllocTest, test_alloc_big2) | |
434 | { | |
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); | |
9f95a23c | 440 | |
494da23a TL |
441 | PExtentVector extents; |
442 | uint64_t need = block_size * blocks / 4; // 2GB | |
443 | EXPECT_EQ(need, | |
444 | alloc->allocate(need, mas, 0, &extents)); | |
445 | need = block_size * blocks / 4; // 2GB | |
e306af50 | 446 | extents.clear(); |
494da23a TL |
447 | EXPECT_EQ(need, |
448 | alloc->allocate(need, mas, 0, &extents)); | |
449 | EXPECT_TRUE(extents[0].length > 0); | |
450 | } | |
451 | ||
9f95a23c TL |
452 | //Verifies stuck 4GB chunk allocation |
453 | //in StupidAllocator | |
454 | // | |
455 | TEST_P(AllocTest, test_alloc_big3) | |
456 | { | |
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); | |
7c673cae | 462 | |
9f95a23c TL |
463 | PExtentVector extents; |
464 | uint64_t need = block_size * blocks / 2; // 4GB | |
465 | EXPECT_EQ(need, | |
466 | alloc->allocate(need, mas, 0, &extents)); | |
467 | EXPECT_TRUE(extents[0].length > 0); | |
468 | } | |
7c673cae | 469 | |
e306af50 TL |
470 | TEST_P(AllocTest, test_alloc_contiguous) |
471 | { | |
472 | int64_t block_size = 0x1000; | |
473 | int64_t capacity = block_size * 1024 * 1024; | |
474 | ||
475 | { | |
476 | init_alloc(capacity, block_size); | |
477 | ||
478 | alloc->init_add_free(0, capacity); | |
479 | PExtentVector extents; | |
480 | uint64_t need = 4 * block_size; | |
481 | EXPECT_EQ(need, | |
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); | |
487 | ||
488 | extents.clear(); | |
489 | EXPECT_EQ(need, | |
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); | |
495 | } | |
496 | ||
497 | alloc->shutdown(); | |
498 | } | |
499 | ||
adb31ebb TL |
500 | TEST_P(AllocTest, test_alloc_47883) |
501 | { | |
502 | uint64_t block = 0x1000; | |
503 | uint64_t size = 1599858540544ul; | |
504 | ||
505 | init_alloc(size, block); | |
506 | ||
507 | alloc->init_add_free(0x1b970000, 0x26000); | |
508 | alloc->init_add_free(0x1747e9d5000, 0x493000); | |
509 | alloc->init_add_free(0x1747ee6a000, 0x196000); | |
510 | ||
511 | PExtentVector extents; | |
512 | auto need = 0x3f980000; | |
513 | auto got = alloc->allocate(need, 0x10000, 0, (int64_t)0, &extents); | |
514 | EXPECT_GT(got, 0); | |
515 | EXPECT_EQ(got, 0x630000); | |
516 | } | |
517 | ||
ec96510d FG |
518 | TEST_P(AllocTest, test_alloc_50656_best_fit) |
519 | { | |
520 | uint64_t block = 0x1000; | |
521 | uint64_t size = 0x3b9e400000; | |
522 | ||
523 | init_alloc(size, block); | |
524 | ||
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); | |
528 | } | |
529 | ||
530 | alloc->init_add_free(0x1e1bd13000, 0x404000); | |
531 | ||
532 | PExtentVector extents; | |
533 | auto need = 0x400000; | |
534 | auto got = alloc->allocate(need, 0x10000, 0, (int64_t)0, &extents); | |
535 | EXPECT_GT(got, 0); | |
536 | EXPECT_EQ(got, 0x400000); | |
537 | } | |
538 | ||
539 | TEST_P(AllocTest, test_alloc_50656_first_fit) | |
540 | { | |
541 | uint64_t block = 0x1000; | |
542 | uint64_t size = 0x3b9e400000; | |
543 | ||
544 | init_alloc(size, block); | |
545 | ||
546 | for (size_t i = 0; i < 0x10000; i += 2) { | |
547 | alloc->init_add_free(i * 0x100000, 0x100000); | |
548 | } | |
549 | ||
550 | alloc->init_add_free(0x1e1bd13000, 0x404000); | |
551 | ||
552 | PExtentVector extents; | |
553 | auto need = 0x400000; | |
554 | auto got = alloc->allocate(need, 0x10000, 0, (int64_t)0, &extents); | |
555 | EXPECT_GT(got, 0); | |
556 | EXPECT_EQ(got, 0x400000); | |
557 | } | |
558 | ||
9f95a23c TL |
559 | INSTANTIATE_TEST_SUITE_P( |
560 | Allocator, | |
561 | AllocTest, | |
e306af50 | 562 | ::testing::Values("stupid", "bitmap", "avl", "hybrid")); |