]> git.proxmox.com Git - ceph.git/blame - ceph/src/test/objectstore/fastbmap_allocator_test.cc
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
d/control: depend on python3-yaml for ceph-mgr
[ceph.git] / ceph / src / test / objectstore / fastbmap_allocator_test.cc
CommitLineData
a8e16298
TL		 1// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2// vim: ts=8 sw=2 smarttab
3
4#include <iostream>
5#include <gtest/gtest.h>
6
7#include "os/bluestore/fastbmap_allocator_impl.h"
8
9class TestAllocatorLevel01 : public AllocatorLevel01Loose
10{
11public:
12 void init(uint64_t capacity, uint64_t alloc_unit)
13 {
14 _init(capacity, alloc_unit);
15 }
16 interval_t allocate_l1_cont(uint64_t length, uint64_t min_length,
17 uint64_t pos_start, uint64_t pos_end)
18 {
19 return _allocate_l1_contiguous(length, min_length, 0, pos_start, pos_end);
20 }
21 void free_l1(const interval_t& r)
22 {
23 _free_l1(r.offset, r.length);
24 }
25};
26
27class TestAllocatorLevel02 : public AllocatorLevel02<AllocatorLevel01Loose>
28{
29public:
30 void init(uint64_t capacity, uint64_t alloc_unit)
31 {
32 _init(capacity, alloc_unit);
33 }
34 void allocate_l2(uint64_t length, uint64_t min_length,
35 uint64_t* allocated0,
36 interval_vector_t* res)
37 {
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;
42 }
43 void free_l2(const interval_vector_t& r)
44 {
45 _free_l2(r);
46 }
47};
48
49const uint64_t _1m = 1024 * 1024;
50const uint64_t _2m = 2 * 1024 * 1024;
51
52TEST(TestAllocatorLevel01, test_l1)
53{
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());
59
60 auto i1 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 61 ASSERT_EQ(i1.offset, 0u);
62 ASSERT_EQ(i1.length, 0x1000u);
a8e16298
TL		 63 ASSERT_EQ(capacity - 0x1000, al1.debug_get_free());
64
65 auto i2 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 66 ASSERT_EQ(i2.offset, 0x1000u);
67 ASSERT_EQ(i2.length, 0x1000u);
a8e16298
TL		 68 al1.free_l1(i2);
69 al1.free_l1(i1);
70 i1 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 71 ASSERT_EQ(i1.offset, 0u);
72 ASSERT_EQ(i1.length, 0x1000u);
a8e16298 73 i2 = al1.allocate_l1_cont(0x1000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 74 ASSERT_EQ(i2.offset, 0x1000u);
75 ASSERT_EQ(i2.length, 0x1000u);
a8e16298
TL		 76 al1.free_l1(i1);
77 al1.free_l1(i2);
78
79 i1 = al1.allocate_l1_cont(0x2000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 80 ASSERT_EQ(i1.offset, 0u);
81 ASSERT_EQ(i1.length, 0x2000u);
a8e16298
TL		 82
83 i2 = al1.allocate_l1_cont(0x3000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 84 ASSERT_EQ(i2.offset, 0x2000u);
85 ASSERT_EQ(i2.length, 0x3000u);
a8e16298
TL		 86
87 al1.free_l1(i1);
88 al1.free_l1(i2);
89
90 i1 = al1.allocate_l1_cont(0x2000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 91 ASSERT_EQ(i1.offset, 0u);
92 ASSERT_EQ(i1.length, 0x2000u);
a8e16298
TL		 93
94 i2 = al1.allocate_l1_cont(2 * 1024 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 95 ASSERT_EQ(i2.offset, 2u * 1024u * 1024u);
96 ASSERT_EQ(i2.length, 2u * 1024u * 1024u);
a8e16298
TL		 97
98 al1.free_l1(i1);
99 i1 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 100 ASSERT_EQ(i1.offset, 0u);
101 ASSERT_EQ(i1.length, 1024u * 1024u);
a8e16298
TL		 102
103 auto i3 = al1.allocate_l1_cont(1024 * 1024 + 0x1000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 104 ASSERT_EQ(i3.offset, 2u * 2u * 1024u * 1024u);
105 ASSERT_EQ(i3.length, 1024u * 1024u + 0x1000u);
a8e16298
TL		 106
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 ~...
110 //
111 auto i4 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 112 ASSERT_EQ(1 * 1024 * 1024u, i4.offset);
113 ASSERT_EQ(1024 * 1024u, i4.length);
a8e16298
TL		 114 al1.free_l1(i4);
115
116 i4 = al1.allocate_l1_cont(1024 * 1024 - 0x1000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 117 ASSERT_EQ(i4.offset, 5u * 1024u * 1024u + 0x1000u);
118 ASSERT_EQ(i4.length, 1024u * 1024u - 0x1000u);
a8e16298
TL		 119 al1.free_l1(i4);
120
121 i4 = al1.allocate_l1_cont(1024 * 1024 + 0x1000, 0x1000, 0, num_l1_entries);
11fdf7f2 122 ASSERT_EQ(i4.offset, 6u * 1024u * 1024u);
a8e16298 123 //ASSERT_EQ(i4.offset, 5 * 1024 * 1024 + 0x1000);
11fdf7f2 124 ASSERT_EQ(i4.length, 1024u * 1024u + 0x1000u);
a8e16298
TL		 125
126 al1.free_l1(i1);
127 al1.free_l1(i2);
128 al1.free_l1(i3);
129 al1.free_l1(i4);
130
131 i1 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 132 ASSERT_EQ(i1.offset, 0u);
133 ASSERT_EQ(i1.length, 1024u * 1024u);
a8e16298
TL		 134
135 i2 = al1.allocate_l1_cont(1024 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 136 ASSERT_EQ(i2.offset, 1u * 1024u * 1024u);
137 ASSERT_EQ(i2.length, 1024u * 1024u);
a8e16298
TL		 138
139 i3 = al1.allocate_l1_cont(512 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 140 ASSERT_EQ(i3.offset, 2u * 1024u * 1024u);
141 ASSERT_EQ(i3.length, 512u * 1024u);
a8e16298
TL		 142
143 i4 = al1.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 144 ASSERT_EQ(i4.offset, (2u * 1024u + 512u) * 1024u);
145 ASSERT_EQ(i4.length, 1536u * 1024u);
a8e16298
TL		 146 // making a hole 1.5 Mb length
147 al1.free_l1(i2);
148 al1.free_l1(i3);
149 // and trying to fill it
150 i2 = al1.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 151 ASSERT_EQ(i2.offset, 1024u * 1024u);
152 ASSERT_EQ(i2.length, 1536u * 1024u);
a8e16298
TL		 153
154 al1.free_l1(i2);
155 // and trying to fill it partially
156 i2 = al1.allocate_l1_cont(1528 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 157 ASSERT_EQ(i2.offset, 1024u * 1024u);
158 ASSERT_EQ(i2.length, 1528u * 1024u);
a8e16298
TL		 159
160 i3 = al1.allocate_l1_cont(8 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 161 ASSERT_EQ(i3.offset, 2552u * 1024u);
162 ASSERT_EQ(i3.length, 8u * 1024u);
a8e16298
TL		 163
164 al1.free_l1(i2);
165 // here we have the following layout:
166 // Alloc: 0~1M, 2552K~8K, num_l1_entries0K~1.5M
167 // Free: 1M~1528K, 4M ~...
168 //
169 i2 = al1.allocate_l1_cont(1536 * 1024, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 170 ASSERT_EQ(i2.offset, 4u * 1024u * 1024u);
171 ASSERT_EQ(i2.length, 1536u * 1024u);
a8e16298
TL		 172
173 al1.free_l1(i1);
174 al1.free_l1(i2);
175 al1.free_l1(i3);
176 al1.free_l1(i4);
177 ASSERT_EQ(capacity, al1.debug_get_free());
178
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);
183 }
11fdf7f2 184 ASSERT_EQ(0u, al1.debug_get_free());
a8e16298 185 i2 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
11fdf7f2
TL		 186 ASSERT_EQ(i2.length, 0u);
187 ASSERT_EQ(0u, al1.debug_get_free());
a8e16298
TL		 188
189 al1.free_l1(i1);
190 i2 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
191 ASSERT_EQ(i2, i1);
192 al1.free_l1(i2);
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);
196
197 i3 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
11fdf7f2 198 ASSERT_EQ(i3.length, 0u);
a8e16298
TL		 199
200 i3 = al1.allocate_l1_cont(_2m, _1m, 0, num_l1_entries);
201 ASSERT_EQ(i3.length, _1m);
202
203 i4 = al1.allocate_l1_cont(_2m, _1m, 0, num_l1_entries);
11fdf7f2 204 ASSERT_EQ(i4.length, 0u);
a8e16298
TL		 205
206 al1.free_l1(i2);
207 i2 = al1.allocate_l1_cont(_2m, _2m, 0, num_l1_entries);
11fdf7f2 208 ASSERT_EQ(i2.length, 0u);
a8e16298
TL		 209
210 i2 = al1.allocate_l1_cont(_2m, 0x1000, 0, num_l1_entries);
211 ASSERT_EQ(i2.length, _1m);
212
213 al1.free_l1(i2);
214 al1.free_l1(i3);
215 ASSERT_EQ(_2m, al1.debug_get_free());
216
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);
11fdf7f2 221 ASSERT_EQ(0u, al1.debug_get_free());
a8e16298
TL		 222
223 al1.free_l1(i2);
224 al1.free_l1(i4);
225
226 i2 = al1.allocate_l1_cont(0x4000, 0x2000, 0, num_l1_entries);
11fdf7f2 227 ASSERT_EQ(i2.length, 0u);
a8e16298 228 i2 = al1.allocate_l1_cont(0x4000, 0x1000, 0, num_l1_entries);
11fdf7f2 229 ASSERT_EQ(i2.length, 0x1000u);
a8e16298
TL		 230
231 al1.free_l1(i3);
232 i3 = al1.allocate_l1_cont(0x6000, 0x3000, 0, num_l1_entries);
11fdf7f2 233 ASSERT_EQ(i3.length, 0u);
a8e16298 234 i3 = al1.allocate_l1_cont(0x6000, 0x1000, 0, num_l1_entries);
11fdf7f2
TL		 235 ASSERT_EQ(i3.length, 0x2000u);
236 ASSERT_EQ(0u, al1.debug_get_free());
a8e16298
TL		 237
238 std::cout << "Done L1" << std::endl;
239}
240
241TEST(TestAllocatorLevel01, test_l2)
242{
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;
248
249 uint64_t allocated1 = 0;
250 interval_vector_t a1;
251 al2.allocate_l2(0x2000, 0x2000, &allocated1, &a1);
11fdf7f2
TL		 252 ASSERT_EQ(allocated1, 0x2000u);
253 ASSERT_EQ(a1[0].offset, 0u);
254 ASSERT_EQ(a1[0].length, 0x2000u);
a8e16298
TL		 255
256 // limit query range in debug_get_free for the sake of performance
11fdf7f2
TL		 257 ASSERT_EQ(0x2000u, al2.debug_get_allocated(0, 1));
258 ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
a8e16298
TL		 259
260 uint64_t allocated2 = 0;
261 interval_vector_t a2;
262 al2.allocate_l2(0x2000, 0x2000, &allocated2, &a2);
11fdf7f2
TL		 263 ASSERT_EQ(allocated2, 0x2000u);
264 ASSERT_EQ(a2[0].offset, 0x2000u);
265 ASSERT_EQ(a2[0].length, 0x2000u);
a8e16298 266 // limit query range in debug_get_free for the sake of performance
11fdf7f2
TL		 267 ASSERT_EQ(0x4000u, al2.debug_get_allocated(0, 1));
268 ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
a8e16298
TL		 269
270 al2.free_l2(a1);
271
272 allocated2 = 0;
273 a2.clear();
274 al2.allocate_l2(0x1000, 0x1000, &allocated2, &a2);
11fdf7f2
TL		 275 ASSERT_EQ(allocated2, 0x1000u);
276 ASSERT_EQ(a2[0].offset, 0x0000u);
277 ASSERT_EQ(a2[0].length, 0x1000u);
a8e16298 278 // limit query range in debug_get_free for the sake of performance
11fdf7f2
TL		 279 ASSERT_EQ(0x3000u, al2.debug_get_allocated(0, 1));
280 ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
a8e16298
TL		 281
282 uint64_t allocated3 = 0;
283 interval_vector_t a3;
284 al2.allocate_l2(0x2000, 0x1000, &allocated3, &a3);
11fdf7f2
TL		 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);
a8e16298 291 // limit query range in debug_get_free for the sake of performance
11fdf7f2
TL		 292 ASSERT_EQ(0x5000u, al2.debug_get_allocated(0, 1));
293 ASSERT_EQ(0u, al2.debug_get_allocated(1, 2));
a8e16298
TL		 294 {
295 interval_vector_t r;
296 r.emplace_back(0x0, 0x5000);
297 al2.free_l2(r);
298 }
299
300 a3.clear();
301 allocated3 = 0;
302 al2.allocate_l2(_1m, _1m, &allocated3, &a3);
11fdf7f2
TL		 303 ASSERT_EQ(a3.size(), 1u);
304 ASSERT_EQ(a3[0].offset, 0u);
a8e16298
TL		 305 ASSERT_EQ(a3[0].length, _1m);
306
307 al2.free_l2(a3);
308
309 a3.clear();
310 allocated3 = 0;
311 al2.allocate_l2(4 * _1m, _1m, &allocated3, &a3);
11fdf7f2
TL		 312 ASSERT_EQ(a3.size(), 1u);
313 ASSERT_EQ(a3[0].offset, 0u);
a8e16298
TL		 314 ASSERT_EQ(a3[0].length, 4 * _1m);
315
316 al2.free_l2(a3);
317
318#ifndef _DEBUG
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);
11fdf7f2 323 ASSERT_EQ(a4.size(), 1u);
a8e16298 324 ASSERT_EQ(a4[0].offset, i);
11fdf7f2 325 ASSERT_EQ(a4[0].length, 0x1000u);
a8e16298
TL		 326 if (0 == (i % (1 * 1024 * _1m))) {
327 std::cout << "alloc1 " << i / 1024 / 1024 << " mb of "
328 << capacity / 1024 / 1024 << std::endl;
329 }
330 }
331#else
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;
342 }
343 }
344#endif
345
11fdf7f2 346 ASSERT_EQ(0u, al2.debug_get_free());
a8e16298
TL		 347 for (uint64_t i = 0; i < capacity; i += _1m) {
348 interval_vector_t r;
349 r.emplace_back(i, _1m);
350 al2.free_l2(r);
351 if (0 == (i % (1 * 1024 * _1m))) {
352 std::cout << "free1 " << i / 1024 / 1024 << " mb of "
353 << capacity / 1024 / 1024 << std::endl;
354 }
355 }
356 ASSERT_EQ(capacity, al2.debug_get_free());
357
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);
11fdf7f2 362 ASSERT_EQ(a4.size(), 1u);
a8e16298
TL		 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;
369 }
370 }
11fdf7f2 371 ASSERT_EQ(0u, al2.debug_get_free());
a8e16298
TL		 372 uint64_t allocated4 = 0;
373 interval_vector_t a4;
374 al2.allocate_l2(_1m, _1m, &allocated4, &a4);
11fdf7f2 375 ASSERT_EQ(a4.size(), 0u);
a8e16298 376 al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
11fdf7f2 377 ASSERT_EQ(a4.size(), 0u);
a8e16298
TL		 378
379 for (uint64_t i = 0; i < capacity; i += 0x2000) {
380 interval_vector_t r;
381 r.emplace_back(i, 0x1000);
382 al2.free_l2(r);
383 if (0 == (i % (1 * 1024 * _1m))) {
384 std::cout << "free2 " << i / 1024 / 1024 << " mb of "
385 << capacity / 1024 / 1024 << std::endl;
386 }
387 }
388 ASSERT_EQ(capacity / 2, al2.debug_get_free());
389
390 // unable to allocate due to fragmentation
391 al2.allocate_l2(_1m, _1m, &allocated4, &a4);
11fdf7f2 392 ASSERT_EQ(a4.size(), 0u);
a8e16298
TL		 393
394 for (uint64_t i = 0; i < capacity; i += 2 * _1m) {
395 a4.clear();
396 allocated4 = 0;
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);
11fdf7f2 401 ASSERT_EQ(a4[0].length, 0x1000u);
a8e16298
TL		 402 if (0 == (i % (1 * 1024 * _1m))) {
403 std::cout << "alloc3 " << i / 1024 / 1024 << " mb of "
404 << capacity / 1024 / 1024 << std::endl;
405 }
406 }
11fdf7f2 407 ASSERT_EQ(0u, al2.debug_get_free());
a8e16298
TL		 408
409 std::cout << "Done L2" << std::endl;
410}
411
412TEST(TestAllocatorLevel01, test_l2_huge)
413{
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;
419
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);
11fdf7f2
TL		 424 ASSERT_EQ(a4.size(), 1u);
425 ASSERT_EQ(allocated4, 0x1000u);
a8e16298 426 ASSERT_EQ(a4[0].offset, i);
11fdf7f2 427 ASSERT_EQ(a4[0].length, 0x1000u);
a8e16298
TL		 428
429 allocated4 = 0;
430 a4.clear();
431 al2.allocate_l2(_1m - 0x1000, 0x1000, &allocated4, &a4);
11fdf7f2 432 ASSERT_EQ(a4.size(), 1u);
a8e16298
TL		 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;
439 }
440 }
441 for (uint64_t i = 0; i < capacity; i += _1m) {
442 interval_vector_t a4;
443 a4.emplace_back(i, 0x1000);
444 al2.free_l2(a4);
445 if (0 == (i % (1 * 1024 * _1m))) {
446 std::cout << "freeH1 " << i / 1024 / 1024 << " mb of "
447 << capacity / 1024 / 1024 << std::endl;
448 }
449 }
450 {
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;
455 interval_vector_t a;
456 al2.allocate_l2(0x2000, 0x2000, &allocated, &a);
11fdf7f2 457 ASSERT_EQ(a.size(), 0u);
a8e16298
TL		 458 }
459 std::cout << "End try in " << time(NULL) - t << " seconds" << std::endl;
460 }
461 {
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;
466 interval_vector_t a;
467 al2.allocate_l2(_2m, _2m, &allocated, &a);
11fdf7f2 468 ASSERT_EQ(a.size(), 0u);
a8e16298
TL		 469 }
470 std::cout << "End try in " << time(NULL) - t << " seconds" << std::endl;
471 }
472
473 ASSERT_EQ((capacity / _1m) * 0x1000, al2.debug_get_free());
474
475 std::cout << "Done L2 Huge" << std::endl;
476}
477
478TEST(TestAllocatorLevel01, test_l2_unaligned)
479{
480 {
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;
486
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);
11fdf7f2 491 ASSERT_EQ(a4.size(), 1u);
a8e16298
TL		 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;
498 }
499 }
11fdf7f2 500 ASSERT_EQ(0u, al2.debug_get_free());
a8e16298
TL		 501 {
502 // no space to allocate
503 uint64_t allocated4 = 0;
504 interval_vector_t a4;
505 al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
11fdf7f2 506 ASSERT_EQ(a4.size(), 0u);
a8e16298
TL		 507 }
508 }
509 {
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);
11fdf7f2 518 ASSERT_EQ(a4.size(), 1u);
a8e16298
TL		 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;
525 }
526 }
11fdf7f2 527 ASSERT_EQ(0u, al2.debug_get_free());
a8e16298
TL		 528 {
529 // no space to allocate
530 uint64_t allocated4 = 0;
531 interval_vector_t a4;
532 al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
11fdf7f2 533 ASSERT_EQ(a4.size(), 0u);
a8e16298
TL		 534 }
535 }
536
537 {
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);
11fdf7f2
TL		 546 ASSERT_EQ(a4.size(), 1u);
547 ASSERT_EQ(allocated4, 0x1000u);
a8e16298 548 ASSERT_EQ(a4[0].offset, i);
11fdf7f2 549 ASSERT_EQ(a4[0].length, 0x1000u);
a8e16298 550 }
11fdf7f2 551 ASSERT_EQ(0u, al2.debug_get_free());
a8e16298
TL		 552 {
553 // no space to allocate
554 uint64_t allocated4 = 0;
555 interval_vector_t a4;
556 al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
11fdf7f2 557 ASSERT_EQ(a4.size(), 0u);
a8e16298
TL		 558 }
559 }
560 {
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);
11fdf7f2
TL		 569 ASSERT_EQ(a4.size(), 1u);
570 ASSERT_EQ(allocated4, 0x1000u);
a8e16298 571 ASSERT_EQ(a4[0].offset, i);
11fdf7f2 572 ASSERT_EQ(a4[0].length, 0x1000u);
a8e16298 573 }
11fdf7f2 574 ASSERT_EQ(0u, al2.debug_get_free());
a8e16298
TL		 575 {
576 // no space to allocate
577 uint64_t allocated4 = 0;
578 interval_vector_t a4;
579 al2.allocate_l2(0x1000, 0x1000, &allocated4, &a4);
11fdf7f2 580 ASSERT_EQ(a4.size(), 0u);
a8e16298
TL		 581 }
582 }
583
584 std::cout << "Done L2 Unaligned" << std::endl;
585}
586
587TEST(TestAllocatorLevel01, test_l2_contiguous_alignment)
588{
589 {
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;
596
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);
602
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);
11fdf7f2 607 ASSERT_EQ(a4.size(), 1u);
a8e16298
TL		 608 ASSERT_EQ(allocated4, _1m);
609 ASSERT_EQ(a4[0].offset, i);
610 ASSERT_EQ(a4[0].length, _1m);
611 }
612 ASSERT_EQ(capacity / 2, al2.debug_get_free());
613
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);
618
619 {
620 size_t to_release = 2 * _1m + 0x1000;
621 // release 2M + 4K at the beginning
622 interval_vector_t r;
623 r.emplace_back(0, to_release);
624 al2.free_l2(r);
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);
630 }
631 {
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);
645 }
646 {
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);
11fdf7f2 651 ASSERT_EQ(a4.size(), 1u);
a8e16298
TL		 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);
661 }
662 {
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);
676 }
677 {
678 // release just allocated 1M
679 interval_vector_t r;
680 r.emplace_back(_1m, _1m);
681 al2.free_l2(r);
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);
687 }
688 {
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);
11fdf7f2 693 ASSERT_EQ(a4.size(), 2u);
a8e16298
TL		 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);
705 }
706 {
707 // release allocated 1M in the second meg chunk except
708 // the first 4K chunk
709 interval_vector_t r;
710 r.emplace_back(_1m + 0x1000, _1m);
711 al2.free_l2(r);
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);
718 }
719 {
720 // release 2M @(capacity / 2)
721 interval_vector_t r;
722 r.emplace_back(capacity / 2, 2 * _1m);
723 al2.free_l2(r);
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);
730 }
731 {
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);
11fdf7f2 737 ASSERT_EQ(a4.size(), 3u);
a8e16298
TL		 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);
745
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
751 // the same bin = 6
752 ASSERT_EQ(bins_overall[6], 2u);
753 ASSERT_EQ(bins_overall[cbits((num_chunks - 256) / 2) - 1], 1u);
754
755 }
756 {
757 // cleanup first 2M except except the last 4K chunk
758 interval_vector_t r;
759 r.emplace_back(0, 2 * _1m - 0x1000);
760 al2.free_l2(r);
761 bins_overall.clear();
762 al2.collect_stats(bins_overall);
763
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);
768 }
769 {
770 // release 2M @(capacity / 2)
771 interval_vector_t r;
772 r.emplace_back(capacity / 2, 2 * _1m);
773 al2.free_l2(r);
774 bins_overall.clear();
775 al2.collect_stats(bins_overall);
776
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);
781 }
782 {
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);
11fdf7f2 787 ASSERT_EQ(a4.size(), 1u);
a8e16298
TL		 788 ASSERT_EQ(a4[0].offset, capacity / 2);
789 ASSERT_EQ(a4[0].length, 132 * _1m);
790
791 bins_overall.clear();
792 al2.collect_stats(bins_overall);
793 ASSERT_EQ(bins_overall.size(), 3u);
794 }
795 {
796 // cleanup left 4K chunk in the first 2M
797 interval_vector_t r;
798 r.emplace_back(2 * _1m - 0x1000, 0x1000);
799 al2.free_l2(r);
800 bins_overall.clear();
801 al2.collect_stats(bins_overall);
802
803 ASSERT_EQ(bins_overall.size(), 2u);
804 }
805 {
806 // release 132M @(capacity / 2)
807 interval_vector_t r;
808 r.emplace_back(capacity / 2, 132 * _1m);
809 al2.free_l2(r);
810 }
811 {
812 // allocate 132M using 2M granularity should go to the first chunk and to
813 // (capacity / 2)
814 uint64_t allocated4 = 0;
815 interval_vector_t a4;
816 al2.allocate_l2(132 * _1m, 2 * _1m , &allocated4, &a4);
11fdf7f2
TL		 817 ASSERT_EQ(a4.size(), 2u);
818 ASSERT_EQ(a4[0].offset, 0u);
a8e16298
TL		 819 ASSERT_EQ(a4[0].length, 2 * _1m);
820 ASSERT_EQ(a4[1].offset, capacity / 2);
821 ASSERT_EQ(a4[1].length, 130 * _1m);
822 }
823 {
824 // release 130M @(capacity / 2)
825 interval_vector_t r;
826 r.emplace_back(capacity / 2, 132 * _1m);
827 al2.free_l2(r);
828 }
829 {
830 // release 4K~16K
831 // release 28K~32K
832 // release 68K~24K
833 interval_vector_t r;
834 r.emplace_back(0x1000, 0x4000);
835 r.emplace_back(0x7000, 0x8000);
836 r.emplace_back(0x11000, 0x6000);
837 al2.free_l2(r);
838 }
839 {
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);
11fdf7f2
TL		 846 ASSERT_EQ(a4.size(), 2u);
847 ASSERT_EQ(a4[0].offset, 0x8000u);
848 ASSERT_EQ(a4[0].length, 0x4000u);
a8e16298 849 ASSERT_EQ(a4[1].offset, capacity / 2);
11fdf7f2 850 ASSERT_EQ(a4[1].length, 0x4000u);
a8e16298
TL		 851 }
852
853 }
854 std::cout << "Done L2 cont aligned" << std::endl;
855}
856
857TEST(TestAllocatorLevel01, test_4G_alloc_bug)
858{
859 {
860 TestAllocatorLevel02 al2;
861 uint64_t capacity = 0x8000 * _1m; // = 32GB
862 al2.init(capacity, 0x10000);
863 std::cout << "Init L2 cont aligned" << std::endl;
864
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);
872 }
873}
874
875TEST(TestAllocatorLevel01, test_4G_alloc_bug2)
876{
877 {
878 TestAllocatorLevel02 al2;
879 uint64_t capacity = 0x8000 * _1m; // = 32GB
880 al2.init(capacity, 0x10000);
881
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);
890 }
891 ASSERT_EQ(0u , al2.debug_get_free());
892
893 interval_vector_t r;
894 r.emplace_back(0x5fec30000, 0x13d0000);
895 r.emplace_back(0x628000000, 0x80000000);
896 r.emplace_back(0x6a8000000, 0x80000000);
897 r.emplace_back(0x728100000, 0x70000);
898 al2.free_l2(r);
899
900 std::map<size_t, size_t> bins_overall;
901 al2.collect_stats(bins_overall);
902
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);
912 }
913}
914
915TEST(TestAllocatorLevel01, test_4G_alloc_bug3)
916{
917 {
918 TestAllocatorLevel02 al2;
919 uint64_t capacity = 0x8000 * _1m; // = 32GB
920 al2.init(capacity, 0x10000);
921 std::cout << "Init L2 cont aligned" << std::endl;
922
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);
932 }
933}
Ceph