1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
5 #include <gtest/gtest.h>
7 #include "os/bluestore/fastbmap_allocator_impl.h"
9 class TestAllocatorLevel01
: public AllocatorLevel01Loose
12 void init(uint64_t capacity
, uint64_t alloc_unit
)
14 _init(capacity
, alloc_unit
);
16 interval_t
allocate_l1_cont(uint64_t length
, uint64_t min_length
,
17 uint64_t pos_start
, uint64_t pos_end
)
19 return _allocate_l1_contiguous(length
, min_length
, 0, pos_start
, pos_end
);
21 void free_l1(const interval_t
& r
)
23 _free_l1(r
.offset
, r
.length
);
27 class TestAllocatorLevel02
: public AllocatorLevel02
<AllocatorLevel01Loose
>
30 void init(uint64_t capacity
, uint64_t alloc_unit
)
32 _init(capacity
, alloc_unit
);
34 void allocate_l2(uint64_t length
, uint64_t min_length
,
36 interval_vector_t
* res
)
38 uint64_t allocated
= 0;
39 uint64_t hint
= 0; // trigger internal l2 hint support
40 _allocate_l2(length
, min_length
, 0, hint
, &allocated
, res
);
41 *allocated0
+= allocated
;
43 void free_l2(const interval_vector_t
& r
)
49 const uint64_t _1m
= 1024 * 1024;
50 const uint64_t _2m
= 2 * 1024 * 1024;
52 TEST(TestAllocatorLevel01
, test_l1
)
54 TestAllocatorLevel01 al1
;
55 uint64_t num_l1_entries
= 3 * 256;
56 uint64_t capacity
= num_l1_entries
* 512 * 4096;
57 al1
.init(capacity
, 0x1000);
58 ASSERT_EQ(capacity
, al1
.debug_get_free());
60 auto i1
= al1
.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries
);
61 ASSERT_EQ(i1
.offset
, 0u);
62 ASSERT_EQ(i1
.length
, 0x1000u
);
63 ASSERT_EQ(capacity
- 0x1000, al1
.debug_get_free());
65 auto i2
= al1
.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries
);
66 ASSERT_EQ(i2
.offset
, 0x1000u
);
67 ASSERT_EQ(i2
.length
, 0x1000u
);
70 i1
= al1
.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries
);
71 ASSERT_EQ(i1
.offset
, 0u);
72 ASSERT_EQ(i1
.length
, 0x1000u
);
73 i2
= al1
.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries
);
74 ASSERT_EQ(i2
.offset
, 0x1000u
);
75 ASSERT_EQ(i2
.length
, 0x1000u
);
79 i1
= al1
.allocate_l1_cont(0x2000, 0x1000, 0, num_l1_entries
);
80 ASSERT_EQ(i1
.offset
, 0u);
81 ASSERT_EQ(i1
.length
, 0x2000u
);
83 i2
= al1
.allocate_l1_cont(0x3000, 0x1000, 0, num_l1_entries
);
84 ASSERT_EQ(i2
.offset
, 0x2000u
);
85 ASSERT_EQ(i2
.length
, 0x3000u
);
90 i1
= al1
.allocate_l1_cont(0x2000, 0x1000, 0, num_l1_entries
);
91 ASSERT_EQ(i1
.offset
, 0u);
92 ASSERT_EQ(i1
.length
, 0x2000u
);
94 i2
= al1
.allocate_l1_cont(2 * 1024 * 1024, 0x1000, 0, num_l1_entries
);
95 ASSERT_EQ(i2
.offset
, 2u * 1024u * 1024u);
96 ASSERT_EQ(i2
.length
, 2u * 1024u * 1024u);
99 i1
= al1
.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries
);
100 ASSERT_EQ(i1
.offset
, 0u);
101 ASSERT_EQ(i1
.length
, 1024u * 1024u);
103 auto i3
= al1
.allocate_l1_cont(1024 * 1024 + 0x1000, 0x1000, 0, num_l1_entries
);
104 ASSERT_EQ(i3
.offset
, 2u * 2u * 1024u * 1024u);
105 ASSERT_EQ(i3
.length
, 1024u * 1024u + 0x1000u
);
107 // here we have the following layout:
108 // Alloc: 0~1M, 2M~2M, 4M~1M+4K
109 // Free: 1M~1M, 4M+4K ~ 2M-4K, 6M ~...
111 auto i4
= al1
.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries
);
112 ASSERT_EQ(1 * 1024 * 1024u, i4
.offset
);
113 ASSERT_EQ(1024 * 1024u, i4
.length
);
116 i4
= al1
.allocate_l1_cont(1024 * 1024 - 0x1000, 0x1000, 0, num_l1_entries
);
117 ASSERT_EQ(i4
.offset
, 5u * 1024u * 1024u + 0x1000u
);
118 ASSERT_EQ(i4
.length
, 1024u * 1024u - 0x1000u
);
121 i4
= al1
.allocate_l1_cont(1024 * 1024 + 0x1000, 0x1000, 0, num_l1_entries
);
122 ASSERT_EQ(i4
.offset
, 6u * 1024u * 1024u);
123 //ASSERT_EQ(i4.offset, 5 * 1024 * 1024 + 0x1000);
124 ASSERT_EQ(i4
.length
, 1024u * 1024u + 0x1000u
);
131 i1
= al1
.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries
);
132 ASSERT_EQ(i1
.offset
, 0u);
133 ASSERT_EQ(i1
.length
, 1024u * 1024u);
135 i2
= al1
.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries
);
136 ASSERT_EQ(i2
.offset
, 1u * 1024u * 1024u);
137 ASSERT_EQ(i2
.length
, 1024u * 1024u);
139 i3
= al1
.allocate_l1_cont(512 * 1024, 0x1000, 0, num_l1_entries
);
140 ASSERT_EQ(i3
.offset
, 2u * 1024u * 1024u);
141 ASSERT_EQ(i3
.length
, 512u * 1024u);
143 i4
= al1
.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries
);
144 ASSERT_EQ(i4
.offset
, (2u * 1024u + 512u) * 1024u);
145 ASSERT_EQ(i4
.length
, 1536u * 1024u);
146 // making a hole 1.5 Mb length
149 // and trying to fill it
150 i2
= al1
.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries
);
151 ASSERT_EQ(i2
.offset
, 1024u * 1024u);
152 ASSERT_EQ(i2
.length
, 1536u * 1024u);
155 // and trying to fill it partially
156 i2
= al1
.allocate_l1_cont(1528 * 1024, 0x1000, 0, num_l1_entries
);
157 ASSERT_EQ(i2
.offset
, 1024u * 1024u);
158 ASSERT_EQ(i2
.length
, 1528u * 1024u);
160 i3
= al1
.allocate_l1_cont(8 * 1024, 0x1000, 0, num_l1_entries
);
161 ASSERT_EQ(i3
.offset
, 2552u * 1024u);
162 ASSERT_EQ(i3
.length
, 8u * 1024u);
165 // here we have the following layout:
166 // Alloc: 0~1M, 2552K~8K, num_l1_entries0K~1.5M
167 // Free: 1M~1528K, 4M ~...
169 i2
= al1
.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries
);
170 ASSERT_EQ(i2
.offset
, 4u * 1024u * 1024u);
171 ASSERT_EQ(i2
.length
, 1536u * 1024u);
177 ASSERT_EQ(capacity
, al1
.debug_get_free());
179 for (uint64_t i
= 0; i
< capacity
; i
+= _2m
) {
180 i1
= al1
.allocate_l1_cont(_2m
, _2m
, 0, num_l1_entries
);
181 ASSERT_EQ(i1
.offset
, i
);
182 ASSERT_EQ(i1
.length
, _2m
);
184 ASSERT_EQ(0u, al1
.debug_get_free());
185 i2
= al1
.allocate_l1_cont(_2m
, _2m
, 0, num_l1_entries
);
186 ASSERT_EQ(i2
.length
, 0u);
187 ASSERT_EQ(0u, al1
.debug_get_free());
190 i2
= al1
.allocate_l1_cont(_2m
, _2m
, 0, num_l1_entries
);
193 i2
= al1
.allocate_l1_cont(_1m
, _1m
, 0, num_l1_entries
);
194 ASSERT_EQ(i2
.offset
, i1
.offset
);
195 ASSERT_EQ(i2
.length
, _1m
);
197 i3
= al1
.allocate_l1_cont(_2m
, _2m
, 0, num_l1_entries
);
198 ASSERT_EQ(i3
.length
, 0u);
200 i3
= al1
.allocate_l1_cont(_2m
, _1m
, 0, num_l1_entries
);
201 ASSERT_EQ(i3
.length
, _1m
);
203 i4
= al1
.allocate_l1_cont(_2m
, _1m
, 0, num_l1_entries
);
204 ASSERT_EQ(i4
.length
, 0u);
207 i2
= al1
.allocate_l1_cont(_2m
, _2m
, 0, num_l1_entries
);
208 ASSERT_EQ(i2
.length
, 0u);
210 i2
= al1
.allocate_l1_cont(_2m
, 0x1000, 0, num_l1_entries
);
211 ASSERT_EQ(i2
.length
, _1m
);
215 ASSERT_EQ(_2m
, al1
.debug_get_free());
217 i1
= al1
.allocate_l1_cont(_2m
- 3 * 0x1000, 0x1000, 0, num_l1_entries
);
218 i2
= al1
.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries
);
219 i3
= al1
.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries
);
220 i4
= al1
.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries
);
221 ASSERT_EQ(0u, al1
.debug_get_free());
226 i2
= al1
.allocate_l1_cont(0x4000, 0x2000, 0, num_l1_entries
);
227 ASSERT_EQ(i2
.length
, 0u);
228 i2
= al1
.allocate_l1_cont(0x4000, 0x1000, 0, num_l1_entries
);
229 ASSERT_EQ(i2
.length
, 0x1000u
);
232 i3
= al1
.allocate_l1_cont(0x6000, 0x3000, 0, num_l1_entries
);
233 ASSERT_EQ(i3
.length
, 0u);
234 i3
= al1
.allocate_l1_cont(0x6000, 0x1000, 0, num_l1_entries
);
235 ASSERT_EQ(i3
.length
, 0x2000u
);
236 ASSERT_EQ(0u, al1
.debug_get_free());
238 std::cout
<< "Done L1" << std::endl
;
241 TEST(TestAllocatorLevel01
, test_l2
)
243 TestAllocatorLevel02 al2
;
244 uint64_t num_l2_entries
= 64;// *512;
245 uint64_t capacity
= num_l2_entries
* 256 * 512 * 4096;
246 al2
.init(capacity
, 0x1000);
247 std::cout
<< "Init L2" << std::endl
;
249 uint64_t allocated1
= 0;
250 interval_vector_t a1
;
251 al2
.allocate_l2(0x2000, 0x2000, &allocated1
, &a1
);
252 ASSERT_EQ(allocated1
, 0x2000u
);
253 ASSERT_EQ(a1
[0].offset
, 0u);
254 ASSERT_EQ(a1
[0].length
, 0x2000u
);
256 // limit query range in debug_get_free for the sake of performance
257 ASSERT_EQ(0x2000u
, al2
.debug_get_allocated(0, 1));
258 ASSERT_EQ(0u, al2
.debug_get_allocated(1, 2));
260 uint64_t allocated2
= 0;
261 interval_vector_t a2
;
262 al2
.allocate_l2(0x2000, 0x2000, &allocated2
, &a2
);
263 ASSERT_EQ(allocated2
, 0x2000u
);
264 ASSERT_EQ(a2
[0].offset
, 0x2000u
);
265 ASSERT_EQ(a2
[0].length
, 0x2000u
);
266 // limit query range in debug_get_free for the sake of performance
267 ASSERT_EQ(0x4000u
, al2
.debug_get_allocated(0, 1));
268 ASSERT_EQ(0u, al2
.debug_get_allocated(1, 2));
274 al2
.allocate_l2(0x1000, 0x1000, &allocated2
, &a2
);
275 ASSERT_EQ(allocated2
, 0x1000u
);
276 ASSERT_EQ(a2
[0].offset
, 0x0000u
);
277 ASSERT_EQ(a2
[0].length
, 0x1000u
);
278 // limit query range in debug_get_free for the sake of performance
279 ASSERT_EQ(0x3000u
, al2
.debug_get_allocated(0, 1));
280 ASSERT_EQ(0u, al2
.debug_get_allocated(1, 2));
282 uint64_t allocated3
= 0;
283 interval_vector_t a3
;
284 al2
.allocate_l2(0x2000, 0x1000, &allocated3
, &a3
);
285 ASSERT_EQ(allocated3
, 0x2000u
);
286 ASSERT_EQ(a3
.size(), 2u);
287 ASSERT_EQ(a3
[0].offset
, 0x1000u
);
288 ASSERT_EQ(a3
[0].length
, 0x1000u
);
289 ASSERT_EQ(a3
[1].offset
, 0x4000u
);
290 ASSERT_EQ(a3
[1].length
, 0x1000u
);
291 // limit query range in debug_get_free for the sake of performance
292 ASSERT_EQ(0x5000u
, al2
.debug_get_allocated(0, 1));
293 ASSERT_EQ(0u, al2
.debug_get_allocated(1, 2));
296 r
.emplace_back(0x0, 0x5000);
302 al2
.allocate_l2(_1m
, _1m
, &allocated3
, &a3
);
303 ASSERT_EQ(a3
.size(), 1u);
304 ASSERT_EQ(a3
[0].offset
, 0u);
305 ASSERT_EQ(a3
[0].length
, _1m
);
311 al2
.allocate_l2(4 * _1m
, _1m
, &allocated3
, &a3
);
312 ASSERT_EQ(a3
.size(), 1u);
313 ASSERT_EQ(a3
[0].offset
, 0u);
314 ASSERT_EQ(a3
[0].length
, 4 * _1m
);
319 for (uint64_t i
= 0; i
< capacity
; i
+= 0x1000) {
320 uint64_t allocated4
= 0;
321 interval_vector_t a4
;
322 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
323 ASSERT_EQ(a4
.size(), 1u);
324 ASSERT_EQ(a4
[0].offset
, i
);
325 ASSERT_EQ(a4
[0].length
, 0x1000u
);
326 if (0 == (i
% (1 * 1024 * _1m
))) {
327 std::cout
<< "alloc1 " << i
/ 1024 / 1024 << " mb of "
328 << capacity
/ 1024 / 1024 << std::endl
;
332 for (uint64_t i
= 0; i
< capacity
; i
+= _2m
) {
333 uint64_t allocated4
= 0;
334 interval_vector_t a4
;
335 al2
.allocate_l2(_2m
, _2m
, &allocated4
, &a4
);
336 ASSERT_EQ(a4
.size(), 1);
337 ASSERT_EQ(a4
[0].offset
, i
);
338 ASSERT_EQ(a4
[0].length
, _2m
);
339 if (0 == (i
% (1 * 1024 * _1m
))) {
340 std::cout
<< "alloc1 " << i
/ 1024 / 1024 << " mb of "
341 << capacity
/ 1024 / 1024 << std::endl
;
346 ASSERT_EQ(0u, al2
.debug_get_free());
347 for (uint64_t i
= 0; i
< capacity
; i
+= _1m
) {
349 r
.emplace_back(i
, _1m
);
351 if (0 == (i
% (1 * 1024 * _1m
))) {
352 std::cout
<< "free1 " << i
/ 1024 / 1024 << " mb of "
353 << capacity
/ 1024 / 1024 << std::endl
;
356 ASSERT_EQ(capacity
, al2
.debug_get_free());
358 for (uint64_t i
= 0; i
< capacity
; i
+= _1m
) {
359 uint64_t allocated4
= 0;
360 interval_vector_t a4
;
361 al2
.allocate_l2(_1m
, _1m
, &allocated4
, &a4
);
362 ASSERT_EQ(a4
.size(), 1u);
363 ASSERT_EQ(allocated4
, _1m
);
364 ASSERT_EQ(a4
[0].offset
, i
);
365 ASSERT_EQ(a4
[0].length
, _1m
);
366 if (0 == (i
% (1 * 1024 * _1m
))) {
367 std::cout
<< "alloc2 " << i
/ 1024 / 1024 << " mb of "
368 << capacity
/ 1024 / 1024 << std::endl
;
371 ASSERT_EQ(0u, al2
.debug_get_free());
372 uint64_t allocated4
= 0;
373 interval_vector_t a4
;
374 al2
.allocate_l2(_1m
, _1m
, &allocated4
, &a4
);
375 ASSERT_EQ(a4
.size(), 0u);
376 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
377 ASSERT_EQ(a4
.size(), 0u);
379 for (uint64_t i
= 0; i
< capacity
; i
+= 0x2000) {
381 r
.emplace_back(i
, 0x1000);
383 if (0 == (i
% (1 * 1024 * _1m
))) {
384 std::cout
<< "free2 " << i
/ 1024 / 1024 << " mb of "
385 << capacity
/ 1024 / 1024 << std::endl
;
388 ASSERT_EQ(capacity
/ 2, al2
.debug_get_free());
390 // unable to allocate due to fragmentation
391 al2
.allocate_l2(_1m
, _1m
, &allocated4
, &a4
);
392 ASSERT_EQ(a4
.size(), 0u);
394 for (uint64_t i
= 0; i
< capacity
; i
+= 2 * _1m
) {
397 al2
.allocate_l2(_1m
, 0x1000, &allocated4
, &a4
);
398 ASSERT_EQ(a4
.size(), _1m
/ 0x1000);
399 ASSERT_EQ(allocated4
, _1m
);
400 ASSERT_EQ(a4
[0].offset
, i
);
401 ASSERT_EQ(a4
[0].length
, 0x1000u
);
402 if (0 == (i
% (1 * 1024 * _1m
))) {
403 std::cout
<< "alloc3 " << i
/ 1024 / 1024 << " mb of "
404 << capacity
/ 1024 / 1024 << std::endl
;
407 ASSERT_EQ(0u, al2
.debug_get_free());
409 std::cout
<< "Done L2" << std::endl
;
412 TEST(TestAllocatorLevel01
, test_l2_huge
)
414 TestAllocatorLevel02 al2
;
415 uint64_t num_l2_entries
= 4 * 512;
416 uint64_t capacity
= num_l2_entries
* 256 * 512 * 4096; // 1 TB
417 al2
.init(capacity
, 0x1000);
418 std::cout
<< "Init L2 Huge" << std::endl
;
420 for (uint64_t i
= 0; i
< capacity
; i
+= _1m
) {
421 uint64_t allocated4
= 0;
422 interval_vector_t a4
;
423 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
424 ASSERT_EQ(a4
.size(), 1u);
425 ASSERT_EQ(allocated4
, 0x1000u
);
426 ASSERT_EQ(a4
[0].offset
, i
);
427 ASSERT_EQ(a4
[0].length
, 0x1000u
);
431 al2
.allocate_l2(_1m
- 0x1000, 0x1000, &allocated4
, &a4
);
432 ASSERT_EQ(a4
.size(), 1u);
433 ASSERT_EQ(allocated4
, _1m
- 0x1000);
434 ASSERT_EQ(a4
[0].offset
, i
+ 0x1000);
435 ASSERT_EQ(a4
[0].length
, _1m
- 0x1000);
436 if (0 == (i
% (1 * 1024 * _1m
))) {
437 std::cout
<< "allocH " << i
/ 1024 / 1024 << " mb of "
438 << capacity
/ 1024 / 1024 << std::endl
;
441 for (uint64_t i
= 0; i
< capacity
; i
+= _1m
) {
442 interval_vector_t a4
;
443 a4
.emplace_back(i
, 0x1000);
445 if (0 == (i
% (1 * 1024 * _1m
))) {
446 std::cout
<< "freeH1 " << i
/ 1024 / 1024 << " mb of "
447 << capacity
/ 1024 / 1024 << std::endl
;
451 std::cout
<< "Try" << std::endl
;
452 time_t t
= time(NULL
);
453 for (int i
= 0; i
< 10; ++i
) {
454 uint64_t allocated
= 0;
456 al2
.allocate_l2(0x2000, 0x2000, &allocated
, &a
);
457 ASSERT_EQ(a
.size(), 0u);
459 std::cout
<< "End try in " << time(NULL
) - t
<< " seconds" << std::endl
;
462 std::cout
<< "Try" << std::endl
;
463 time_t t
= time(NULL
);
464 for (int i
= 0; i
< 10; ++i
) {
465 uint64_t allocated
= 0;
467 al2
.allocate_l2(_2m
, _2m
, &allocated
, &a
);
468 ASSERT_EQ(a
.size(), 0u);
470 std::cout
<< "End try in " << time(NULL
) - t
<< " seconds" << std::endl
;
473 ASSERT_EQ((capacity
/ _1m
) * 0x1000, al2
.debug_get_free());
475 std::cout
<< "Done L2 Huge" << std::endl
;
478 TEST(TestAllocatorLevel01
, test_l2_unaligned
)
481 TestAllocatorLevel02 al2
;
482 uint64_t num_l2_entries
= 3;
483 uint64_t capacity
= num_l2_entries
* 256 * 512 * 4096; // 3x512 MB
484 al2
.init(capacity
, 0x1000);
485 std::cout
<< "Init L2 Unaligned" << std::endl
;
487 for (uint64_t i
= 0; i
< capacity
; i
+= _1m
/ 2) {
488 uint64_t allocated4
= 0;
489 interval_vector_t a4
;
490 al2
.allocate_l2(_1m
/ 2, _1m
/ 2, &allocated4
, &a4
);
491 ASSERT_EQ(a4
.size(), 1u);
492 ASSERT_EQ(allocated4
, _1m
/ 2);
493 ASSERT_EQ(a4
[0].offset
, i
);
494 ASSERT_EQ(a4
[0].length
, _1m
/ 2);
495 if (0 == (i
% (1 * 1024 * _1m
))) {
496 std::cout
<< "allocU " << i
/ 1024 / 1024 << " mb of "
497 << capacity
/ 1024 / 1024 << std::endl
;
500 ASSERT_EQ(0u, al2
.debug_get_free());
502 // no space to allocate
503 uint64_t allocated4
= 0;
504 interval_vector_t a4
;
505 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
506 ASSERT_EQ(a4
.size(), 0u);
510 TestAllocatorLevel02 al2
;
511 uint64_t capacity
= 500 * 512 * 4096; // 500x2 MB
512 al2
.init(capacity
, 0x1000);
513 std::cout
<< ("Init L2 Unaligned2\n");
514 for (uint64_t i
= 0; i
< capacity
; i
+= _1m
/ 2) {
515 uint64_t allocated4
= 0;
516 interval_vector_t a4
;
517 al2
.allocate_l2(_1m
/ 2, _1m
/ 2, &allocated4
, &a4
);
518 ASSERT_EQ(a4
.size(), 1u);
519 ASSERT_EQ(allocated4
, _1m
/ 2);
520 ASSERT_EQ(a4
[0].offset
, i
);
521 ASSERT_EQ(a4
[0].length
, _1m
/ 2);
522 if (0 == (i
% (1 * 1024 * _1m
))) {
523 std::cout
<< "allocU2 " << i
/ 1024 / 1024 << " mb of "
524 << capacity
/ 1024 / 1024 << std::endl
;
527 ASSERT_EQ(0u, al2
.debug_get_free());
529 // no space to allocate
530 uint64_t allocated4
= 0;
531 interval_vector_t a4
;
532 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
533 ASSERT_EQ(a4
.size(), 0u);
538 TestAllocatorLevel02 al2
;
539 uint64_t capacity
= 100 * 512 * 4096 + 127 * 4096;
540 al2
.init(capacity
, 0x1000);
541 std::cout
<< "Init L2 Unaligned2" << std::endl
;
542 for (uint64_t i
= 0; i
< capacity
; i
+= 0x1000) {
543 uint64_t allocated4
= 0;
544 interval_vector_t a4
;
545 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
546 ASSERT_EQ(a4
.size(), 1u);
547 ASSERT_EQ(allocated4
, 0x1000u
);
548 ASSERT_EQ(a4
[0].offset
, i
);
549 ASSERT_EQ(a4
[0].length
, 0x1000u
);
551 ASSERT_EQ(0u, al2
.debug_get_free());
553 // no space to allocate
554 uint64_t allocated4
= 0;
555 interval_vector_t a4
;
556 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
557 ASSERT_EQ(a4
.size(), 0u);
561 TestAllocatorLevel02 al2
;
562 uint64_t capacity
= 3 * 4096;
563 al2
.init(capacity
, 0x1000);
564 std::cout
<< "Init L2 Unaligned2" << std::endl
;
565 for (uint64_t i
= 0; i
< capacity
; i
+= 0x1000) {
566 uint64_t allocated4
= 0;
567 interval_vector_t a4
;
568 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
569 ASSERT_EQ(a4
.size(), 1u);
570 ASSERT_EQ(allocated4
, 0x1000u
);
571 ASSERT_EQ(a4
[0].offset
, i
);
572 ASSERT_EQ(a4
[0].length
, 0x1000u
);
574 ASSERT_EQ(0u, al2
.debug_get_free());
576 // no space to allocate
577 uint64_t allocated4
= 0;
578 interval_vector_t a4
;
579 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
580 ASSERT_EQ(a4
.size(), 0u);
584 std::cout
<< "Done L2 Unaligned" << std::endl
;
587 TEST(TestAllocatorLevel01
, test_l2_contiguous_alignment
)
590 TestAllocatorLevel02 al2
;
591 uint64_t num_l2_entries
= 3;
592 uint64_t capacity
= num_l2_entries
* 256 * 512 * 4096; // 3x512 MB
593 uint64_t num_chunks
= capacity
/ 4096;
594 al2
.init(capacity
, 4096);
595 std::cout
<< "Init L2 cont aligned" << std::endl
;
597 std::map
<size_t, size_t> bins_overall
;
598 al2
.collect_stats(bins_overall
);
599 ASSERT_EQ(bins_overall
.size(), 1u);
600 // std::cout<<bins_overall.begin()->first << std::endl;
601 ASSERT_EQ(bins_overall
[cbits(num_chunks
) - 1], 1u);
603 for (uint64_t i
= 0; i
< capacity
/ 2; i
+= _1m
) {
604 uint64_t allocated4
= 0;
605 interval_vector_t a4
;
606 al2
.allocate_l2(_1m
, _1m
, &allocated4
, &a4
);
607 ASSERT_EQ(a4
.size(), 1u);
608 ASSERT_EQ(allocated4
, _1m
);
609 ASSERT_EQ(a4
[0].offset
, i
);
610 ASSERT_EQ(a4
[0].length
, _1m
);
612 ASSERT_EQ(capacity
/ 2, al2
.debug_get_free());
614 bins_overall
.clear();
615 al2
.collect_stats(bins_overall
);
616 ASSERT_EQ(bins_overall
.size(), 1u);
617 ASSERT_EQ(bins_overall
[cbits(num_chunks
/ 2) - 1], 1u);
620 size_t to_release
= 2 * _1m
+ 0x1000;
621 // release 2M + 4K at the beginning
623 r
.emplace_back(0, to_release
);
625 bins_overall
.clear();
626 al2
.collect_stats(bins_overall
);
627 ASSERT_EQ(bins_overall
.size(), 2u);
628 ASSERT_EQ(bins_overall
[cbits(to_release
/ 0x1000) - 1], 1u);
629 ASSERT_EQ(bins_overall
[cbits(num_chunks
/ 2) - 1], 1u);
632 // allocate 4K within the deallocated range
633 uint64_t allocated4
= 0;
634 interval_vector_t a4
;
635 al2
.allocate_l2(0x1000, 0x1000, &allocated4
, &a4
);
636 ASSERT_EQ(a4
.size(), 1u);
637 ASSERT_EQ(allocated4
, 0x1000u
);
638 ASSERT_EQ(a4
[0].offset
, 0u);
639 ASSERT_EQ(a4
[0].length
, 0x1000u
);
640 bins_overall
.clear();
641 al2
.collect_stats(bins_overall
);
642 ASSERT_EQ(bins_overall
.size(), 2u);
643 ASSERT_EQ(bins_overall
[cbits(2 * _1m
/ 0x1000) - 1], 1u);
644 ASSERT_EQ(bins_overall
[cbits(num_chunks
/ 2) - 1], 1u);
647 // allocate 1M - should go to the second 1M chunk
648 uint64_t allocated4
= 0;
649 interval_vector_t a4
;
650 al2
.allocate_l2(_1m
, _1m
, &allocated4
, &a4
);
651 ASSERT_EQ(a4
.size(), 1u);
652 ASSERT_EQ(allocated4
, _1m
);
653 ASSERT_EQ(a4
[0].offset
, _1m
);
654 ASSERT_EQ(a4
[0].length
, _1m
);
655 bins_overall
.clear();
656 al2
.collect_stats(bins_overall
);
657 ASSERT_EQ(bins_overall
.size(), 3u);
658 ASSERT_EQ(bins_overall
[0], 1u);
659 ASSERT_EQ(bins_overall
[cbits((_1m
- 0x1000) / 0x1000) - 1], 1u);
660 ASSERT_EQ(bins_overall
[cbits(num_chunks
/ 2) - 1], 1u);
663 // and allocate yet another 8K within the deallocated range
664 uint64_t allocated4
= 0;
665 interval_vector_t a4
;
666 al2
.allocate_l2(0x2000, 0x1000, &allocated4
, &a4
);
667 ASSERT_EQ(a4
.size(), 1u);
668 ASSERT_EQ(allocated4
, 0x2000u
);
669 ASSERT_EQ(a4
[0].offset
, 0x1000u
);
670 ASSERT_EQ(a4
[0].length
, 0x2000u
);
671 bins_overall
.clear();
672 al2
.collect_stats(bins_overall
);
673 ASSERT_EQ(bins_overall
[0], 1u);
674 ASSERT_EQ(bins_overall
[cbits((_1m
- 0x3000) / 0x1000) - 1], 1u);
675 ASSERT_EQ(bins_overall
[cbits(num_chunks
/ 2) - 1], 1u);
678 // release just allocated 1M
680 r
.emplace_back(_1m
, _1m
);
682 bins_overall
.clear();
683 al2
.collect_stats(bins_overall
);
684 ASSERT_EQ(bins_overall
.size(), 2u);
685 ASSERT_EQ(bins_overall
[cbits((2 * _1m
- 0x3000) / 0x1000) - 1], 1u);
686 ASSERT_EQ(bins_overall
[cbits(num_chunks
/ 2) - 1], 1u);
689 // allocate 3M - should go to the second 1M chunk and @capacity/2
690 uint64_t allocated4
= 0;
691 interval_vector_t a4
;
692 al2
.allocate_l2(3 * _1m
, _1m
, &allocated4
, &a4
);
693 ASSERT_EQ(a4
.size(), 2u);
694 ASSERT_EQ(allocated4
, 3 * _1m
);
695 ASSERT_EQ(a4
[0].offset
, _1m
);
696 ASSERT_EQ(a4
[0].length
, _1m
);
697 ASSERT_EQ(a4
[1].offset
, capacity
/ 2);
698 ASSERT_EQ(a4
[1].length
, 2 * _1m
);
699 bins_overall
.clear();
700 al2
.collect_stats(bins_overall
);
701 ASSERT_EQ(bins_overall
.size(), 3u);
702 ASSERT_EQ(bins_overall
[0], 1u);
703 ASSERT_EQ(bins_overall
[cbits((_1m
- 0x3000) / 0x1000) - 1], 1u);
704 ASSERT_EQ(bins_overall
[cbits((num_chunks
- 512) / 2) - 1], 1u);
707 // release allocated 1M in the second meg chunk except
708 // the first 4K chunk
710 r
.emplace_back(_1m
+ 0x1000, _1m
);
712 bins_overall
.clear();
713 al2
.collect_stats(bins_overall
);
714 ASSERT_EQ(bins_overall
.size(), 3u);
715 ASSERT_EQ(bins_overall
[cbits(_1m
/ 0x1000) - 1], 1u);
716 ASSERT_EQ(bins_overall
[cbits((_1m
- 0x3000) / 0x1000) - 1], 1u);
717 ASSERT_EQ(bins_overall
[cbits((num_chunks
- 512) / 2) - 1], 1u);
720 // release 2M @(capacity / 2)
722 r
.emplace_back(capacity
/ 2, 2 * _1m
);
724 bins_overall
.clear();
725 al2
.collect_stats(bins_overall
);
726 ASSERT_EQ(bins_overall
.size(), 3u);
727 ASSERT_EQ(bins_overall
[cbits(_1m
/ 0x1000) - 1], 1u);
728 ASSERT_EQ(bins_overall
[cbits((_1m
- 0x3000) / 0x1000) - 1], 1u);
729 ASSERT_EQ(bins_overall
[cbits((num_chunks
) / 2) - 1], 1u);
732 // allocate 4x512K - should go to the second halves of
733 // the first and second 1M chunks and @(capacity / 2)
734 uint64_t allocated4
= 0;
735 interval_vector_t a4
;
736 al2
.allocate_l2(2 * _1m
, _1m
/ 2, &allocated4
, &a4
);
737 ASSERT_EQ(a4
.size(), 3u);
738 ASSERT_EQ(allocated4
, 2 * _1m
);
739 ASSERT_EQ(a4
[0].offset
, _1m
/ 2);
740 ASSERT_EQ(a4
[0].length
, _1m
/ 2);
741 ASSERT_EQ(a4
[1].offset
, _1m
+ _1m
/ 2);
742 ASSERT_EQ(a4
[1].length
, _1m
/ 2);
743 ASSERT_EQ(a4
[2].offset
, capacity
/ 2);
744 ASSERT_EQ(a4
[2].length
, _1m
);
746 bins_overall
.clear();
747 al2
.collect_stats(bins_overall
);
748 ASSERT_EQ(bins_overall
.size(), 3u);
749 ASSERT_EQ(bins_overall
[0], 1u);
750 // below we have 512K - 4K & 512K - 12K chunks which both fit into
752 ASSERT_EQ(bins_overall
[6], 2u);
753 ASSERT_EQ(bins_overall
[cbits((num_chunks
- 256) / 2) - 1], 1u);
757 // cleanup first 2M except except the last 4K chunk
759 r
.emplace_back(0, 2 * _1m
- 0x1000);
761 bins_overall
.clear();
762 al2
.collect_stats(bins_overall
);
764 ASSERT_EQ(bins_overall
.size(), 3u);
765 ASSERT_EQ(bins_overall
[0], 1u);
766 ASSERT_EQ(bins_overall
[cbits((_2m
- 0x1000) / 0x1000) - 1], 1u);
767 ASSERT_EQ(bins_overall
[cbits((num_chunks
- 256) / 2) - 1], 1u);
770 // release 2M @(capacity / 2)
772 r
.emplace_back(capacity
/ 2, 2 * _1m
);
774 bins_overall
.clear();
775 al2
.collect_stats(bins_overall
);
777 ASSERT_EQ(bins_overall
.size(), 3u);
778 ASSERT_EQ(bins_overall
[0], 1u);
779 ASSERT_EQ(bins_overall
[cbits((_2m
- 0x1000) / 0x1000) - 1], 1u);
780 ASSERT_EQ(bins_overall
[cbits(num_chunks
/ 2) - 1], 1u);
783 // allocate 132M using 4M granularity should go to (capacity / 2)
784 uint64_t allocated4
= 0;
785 interval_vector_t a4
;
786 al2
.allocate_l2(132 * _1m
, 4 * _1m
, &allocated4
, &a4
);
787 ASSERT_EQ(a4
.size(), 1u);
788 ASSERT_EQ(a4
[0].offset
, capacity
/ 2);
789 ASSERT_EQ(a4
[0].length
, 132 * _1m
);
791 bins_overall
.clear();
792 al2
.collect_stats(bins_overall
);
793 ASSERT_EQ(bins_overall
.size(), 3u);
796 // cleanup left 4K chunk in the first 2M
798 r
.emplace_back(2 * _1m
- 0x1000, 0x1000);
800 bins_overall
.clear();
801 al2
.collect_stats(bins_overall
);
803 ASSERT_EQ(bins_overall
.size(), 2u);
806 // release 132M @(capacity / 2)
808 r
.emplace_back(capacity
/ 2, 132 * _1m
);
812 // allocate 132M using 2M granularity should go to the first chunk and to
814 uint64_t allocated4
= 0;
815 interval_vector_t a4
;
816 al2
.allocate_l2(132 * _1m
, 2 * _1m
, &allocated4
, &a4
);
817 ASSERT_EQ(a4
.size(), 2u);
818 ASSERT_EQ(a4
[0].offset
, 0u);
819 ASSERT_EQ(a4
[0].length
, 2 * _1m
);
820 ASSERT_EQ(a4
[1].offset
, capacity
/ 2);
821 ASSERT_EQ(a4
[1].length
, 130 * _1m
);
824 // release 130M @(capacity / 2)
826 r
.emplace_back(capacity
/ 2, 132 * _1m
);
834 r
.emplace_back(0x1000, 0x4000);
835 r
.emplace_back(0x7000, 0x8000);
836 r
.emplace_back(0x11000, 0x6000);
840 // allocate 32K using 16K granularity - should bypass the first
841 // unaligned extent, use the second free extent partially given
842 // the 16K alignment and then fallback to capacity / 2
843 uint64_t allocated4
= 0;
844 interval_vector_t a4
;
845 al2
.allocate_l2(0x8000, 0x4000, &allocated4
, &a4
);
846 ASSERT_EQ(a4
.size(), 2u);
847 ASSERT_EQ(a4
[0].offset
, 0x8000u
);
848 ASSERT_EQ(a4
[0].length
, 0x4000u
);
849 ASSERT_EQ(a4
[1].offset
, capacity
/ 2);
850 ASSERT_EQ(a4
[1].length
, 0x4000u
);
854 std::cout
<< "Done L2 cont aligned" << std::endl
;
857 TEST(TestAllocatorLevel01
, test_4G_alloc_bug
)
860 TestAllocatorLevel02 al2
;
861 uint64_t capacity
= 0x8000 * _1m
; // = 32GB
862 al2
.init(capacity
, 0x10000);
863 std::cout
<< "Init L2 cont aligned" << std::endl
;
865 uint64_t allocated4
= 0;
866 interval_vector_t a4
;
867 al2
.allocate_l2(_1m
, _1m
, &allocated4
, &a4
);
868 ASSERT_EQ(a4
.size(), 1u); // the bug caused no allocations here
869 ASSERT_EQ(allocated4
, _1m
);
870 ASSERT_EQ(a4
[0].offset
, 0u);
871 ASSERT_EQ(a4
[0].length
, _1m
);
875 TEST(TestAllocatorLevel01
, test_4G_alloc_bug2
)
878 TestAllocatorLevel02 al2
;
879 uint64_t capacity
= 0x8000 * _1m
; // = 32GB
880 al2
.init(capacity
, 0x10000);
882 for (uint64_t i
= 0; i
< capacity
; i
+= _1m
) {
883 uint64_t allocated4
= 0;
884 interval_vector_t a4
;
885 al2
.allocate_l2(_1m
, _1m
, &allocated4
, &a4
);
886 ASSERT_EQ(a4
.size(), 1u);
887 ASSERT_EQ(allocated4
, _1m
);
888 ASSERT_EQ(a4
[0].offset
, i
);
889 ASSERT_EQ(a4
[0].length
, _1m
);
891 ASSERT_EQ(0u , al2
.debug_get_free());
894 r
.emplace_back(0x5fec30000, 0x13d0000);
895 r
.emplace_back(0x628000000, 0x80000000);
896 r
.emplace_back(0x6a8000000, 0x80000000);
897 r
.emplace_back(0x728100000, 0x70000);
900 std::map
<size_t, size_t> bins_overall
;
901 al2
.collect_stats(bins_overall
);
903 uint64_t allocated4
= 0;
904 interval_vector_t a4
;
905 al2
.allocate_l2(0x3e000000, _1m
, &allocated4
, &a4
);
906 ASSERT_EQ(a4
.size(), 2u);
907 ASSERT_EQ(allocated4
, 0x3e000000u
);
908 ASSERT_EQ(a4
[0].offset
, 0x5fed00000u
);
909 ASSERT_EQ(a4
[0].length
, 0x1300000u
);
910 ASSERT_EQ(a4
[1].offset
, 0x628000000u
);
911 ASSERT_EQ(a4
[1].length
, 0x3cd00000u
);
915 TEST(TestAllocatorLevel01
, test_4G_alloc_bug3
)
918 TestAllocatorLevel02 al2
;
919 uint64_t capacity
= 0x8000 * _1m
; // = 32GB
920 al2
.init(capacity
, 0x10000);
921 std::cout
<< "Init L2 cont aligned" << std::endl
;
923 uint64_t allocated4
= 0;
924 interval_vector_t a4
;
925 al2
.allocate_l2(4096ull * _1m
, _1m
, &allocated4
, &a4
);
926 ASSERT_EQ(a4
.size(), 2u); // allocator has to split into 2 allocations
927 ASSERT_EQ(allocated4
, 4096ull * _1m
);
928 ASSERT_EQ(a4
[0].offset
, 0u);
929 ASSERT_EQ(a4
[0].length
, 2048ull * _1m
);
930 ASSERT_EQ(a4
[1].offset
, 2048ull * _1m
);
931 ASSERT_EQ(a4
[1].length
, 2048ull * _1m
);