]>
Commit | Line | Data |
---|---|---|
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 | * Bitmap based in-memory allocator implementation. | |
5 | * Author: Igor Fedotov, ifedotov@suse.com | |
6 | * | |
7 | */ | |
8 | ||
9 | #ifndef __FAST_BITMAP_ALLOCATOR_IMPL_H | |
10 | #define __FAST_BITMAP_ALLOCATOR_IMPL_H | |
11 | #include <type_traits> | |
12 | #include "include/intarith.h" | |
13 | ||
14 | #include <vector> | |
15 | #include <algorithm> | |
16 | #include <mutex> | |
17 | ||
18 | typedef uint64_t slot_t; | |
19 | ||
20 | #ifdef NON_CEPH_BUILD | |
21 | #include <assert.h> | |
22 | struct interval_t | |
23 | { | |
24 | uint64_t offset = 0; | |
25 | uint64_t length = 0; | |
26 | ||
27 | interval_t() {} | |
28 | interval_t(uint64_t o, uint64_t l) : offset(o), length(l) {} | |
29 | interval_t(const interval_t &ext) : | |
30 | offset(ext.offset), length(ext.length) {} | |
31 | }; | |
32 | typedef std::vector<interval_t> interval_vector_t; | |
33 | typedef std::vector<slot_t> slot_vector_t; | |
34 | #else | |
35 | #include "include/assert.h" | |
36 | #include "common/likely.h" | |
37 | #include "os/bluestore/bluestore_types.h" | |
38 | #include "include/mempool.h" | |
39 | ||
40 | typedef bluestore_interval_t<uint64_t, uint64_t> interval_t; | |
41 | typedef PExtentVector interval_vector_t; | |
42 | ||
43 | typedef mempool::bluestore_alloc::vector<slot_t> slot_vector_t; | |
44 | ||
45 | #endif | |
46 | ||
47 | // fitting into cache line on x86_64 | |
48 | static const size_t slotset_width = 8; // 8 slots per set | |
b9c3bfeb | 49 | static const size_t slots_per_slotset = 8; |
a8e16298 TL |
50 | static const size_t slotset_bytes = sizeof(slot_t) * slotset_width; |
51 | static const size_t bits_per_slot = sizeof(slot_t) * 8; | |
52 | static const size_t bits_per_slotset = slotset_bytes * 8; | |
53 | static const slot_t all_slot_set = 0xffffffffffffffff; | |
54 | static const slot_t all_slot_clear = 0; | |
55 | ||
56 | inline size_t find_next_set_bit(slot_t slot_val, size_t start_pos) | |
57 | { | |
58 | #ifdef __GNUC__ | |
59 | if (start_pos == 0) { | |
60 | start_pos = __builtin_ffsll(slot_val); | |
61 | return start_pos ? start_pos - 1 : bits_per_slot; | |
62 | } | |
63 | #endif | |
64 | slot_t mask = slot_t(1) << start_pos; | |
65 | while (start_pos < bits_per_slot && !(slot_val & mask)) { | |
66 | mask <<= 1; | |
67 | ++start_pos; | |
68 | } | |
69 | return start_pos; | |
70 | } | |
71 | ||
72 | ||
73 | class AllocatorLevel | |
74 | { | |
75 | protected: | |
76 | ||
77 | virtual uint64_t _children_per_slot() const = 0; | |
78 | virtual uint64_t _level_granularity() const = 0; | |
79 | ||
80 | public: | |
81 | static uint64_t l0_dives; | |
82 | static uint64_t l0_iterations; | |
83 | static uint64_t l0_inner_iterations; | |
84 | static uint64_t alloc_fragments; | |
85 | static uint64_t alloc_fragments_fast; | |
86 | static uint64_t l2_allocs; | |
87 | ||
88 | virtual ~AllocatorLevel() | |
89 | {} | |
90 | ||
91 | virtual void collect_stats( | |
92 | std::map<size_t, size_t>& bins_overall) = 0; | |
93 | ||
94 | }; | |
95 | ||
96 | class AllocatorLevel01 : public AllocatorLevel | |
97 | { | |
98 | protected: | |
99 | slot_vector_t l0; // set bit means free entry | |
100 | slot_vector_t l1; | |
101 | uint64_t l0_granularity = 0; // space per entry | |
102 | uint64_t l1_granularity = 0; // space per entry | |
103 | ||
104 | size_t partial_l1_count = 0; | |
105 | size_t unalloc_l1_count = 0; | |
106 | ||
107 | double get_fragmentation() const { | |
108 | double res = 0.0; | |
109 | auto total = unalloc_l1_count + partial_l1_count; | |
110 | if (total) { | |
111 | res = double(partial_l1_count) / double(total); | |
112 | } | |
113 | return res; | |
114 | } | |
115 | ||
116 | uint64_t _level_granularity() const override | |
117 | { | |
118 | return l1_granularity; | |
119 | } | |
120 | ||
121 | inline bool _is_slot_fully_allocated(uint64_t idx) const { | |
122 | return l1[idx] == all_slot_clear; | |
123 | } | |
124 | public: | |
125 | inline uint64_t get_min_alloc_size() const | |
126 | { | |
127 | return l0_granularity; | |
128 | } | |
129 | ||
130 | }; | |
131 | ||
132 | template <class T> | |
133 | class AllocatorLevel02; | |
134 | ||
135 | class AllocatorLevel01Loose : public AllocatorLevel01 | |
136 | { | |
137 | enum { | |
138 | L1_ENTRY_WIDTH = 2, | |
139 | L1_ENTRY_MASK = (1 << L1_ENTRY_WIDTH) - 1, | |
140 | L1_ENTRY_FULL = 0x00, | |
141 | L1_ENTRY_PARTIAL = 0x01, | |
142 | L1_ENTRY_NOT_USED = 0x02, | |
143 | L1_ENTRY_FREE = 0x03, | |
144 | CHILD_PER_SLOT = bits_per_slot / L1_ENTRY_WIDTH, // 32 | |
b9c3bfeb | 145 | L1_ENTRIES_PER_SLOT = bits_per_slot / L1_ENTRY_WIDTH, //32 |
a8e16298 TL |
146 | CHILD_PER_SLOT_L0 = bits_per_slot, // 64 |
147 | }; | |
148 | uint64_t _children_per_slot() const override | |
149 | { | |
150 | return CHILD_PER_SLOT; | |
151 | } | |
152 | ||
153 | interval_t _get_longest_from_l0(uint64_t pos0, uint64_t pos1, | |
154 | uint64_t min_length, interval_t* tail) const; | |
155 | ||
156 | inline void _fragment_and_emplace(uint64_t max_length, uint64_t offset, | |
157 | uint64_t len, | |
158 | interval_vector_t* res) | |
159 | { | |
160 | auto it = res->rbegin(); | |
161 | if (max_length) { | |
162 | if (it != res->rend() && it->offset + it->length == offset) { | |
163 | auto l = max_length - it->length; | |
164 | if (l >= len) { | |
165 | it->length += len; | |
166 | return; | |
167 | } else { | |
168 | offset += l; | |
169 | len -= l; | |
170 | it->length += l; | |
171 | } | |
172 | } | |
173 | ||
174 | while (len > max_length) { | |
175 | res->emplace_back(offset, max_length); | |
176 | offset += max_length; | |
177 | len -= max_length; | |
178 | } | |
179 | res->emplace_back(offset, len); | |
180 | return; | |
181 | } | |
182 | ||
183 | if (it != res->rend() && it->offset + it->length == offset) { | |
184 | it->length += len; | |
185 | } else { | |
186 | res->emplace_back(offset, len); | |
187 | } | |
188 | } | |
189 | ||
190 | bool _allocate_l0(uint64_t length, | |
191 | uint64_t max_length, | |
192 | uint64_t l0_pos0, uint64_t l0_pos1, | |
193 | uint64_t* allocated, | |
194 | interval_vector_t* res) | |
195 | { | |
196 | uint64_t d0 = CHILD_PER_SLOT_L0; | |
197 | ||
198 | ++l0_dives; | |
199 | ||
200 | assert(l0_pos0 < l0_pos1); | |
201 | assert(length > *allocated); | |
202 | assert(0 == (l0_pos0 % (slotset_width * d0))); | |
203 | assert(0 == (l0_pos1 % (slotset_width * d0))); | |
204 | assert(((length - *allocated) % l0_granularity) == 0); | |
205 | ||
206 | uint64_t need_entries = (length - *allocated) / l0_granularity; | |
207 | ||
208 | for (auto idx = l0_pos0 / d0; (idx < l0_pos1 / d0) && (length > *allocated); | |
209 | ++idx) { | |
210 | ++l0_iterations; | |
211 | slot_t& slot_val = l0[idx]; | |
212 | auto base = idx * d0; | |
213 | if (slot_val == all_slot_clear) { | |
214 | continue; | |
215 | } else if (slot_val == all_slot_set) { | |
216 | uint64_t to_alloc = std::min(need_entries, d0); | |
217 | *allocated += to_alloc * l0_granularity; | |
218 | ++alloc_fragments; | |
219 | need_entries -= to_alloc; | |
220 | ||
221 | _fragment_and_emplace(max_length, base * l0_granularity, | |
222 | to_alloc * l0_granularity, res); | |
223 | ||
224 | if (to_alloc == d0) { | |
225 | slot_val = all_slot_clear; | |
226 | } else { | |
227 | _mark_alloc_l0(base, base + to_alloc); | |
228 | } | |
229 | continue; | |
230 | } | |
231 | ||
232 | auto free_pos = find_next_set_bit(slot_val, 0); | |
233 | assert(free_pos < bits_per_slot); | |
234 | auto next_pos = free_pos + 1; | |
235 | while (next_pos < bits_per_slot && | |
236 | (next_pos - free_pos) < need_entries) { | |
237 | ++l0_inner_iterations; | |
238 | ||
239 | if (0 == (slot_val & (slot_t(1) << next_pos))) { | |
240 | auto to_alloc = (next_pos - free_pos); | |
241 | *allocated += to_alloc * l0_granularity; | |
242 | ++alloc_fragments; | |
243 | need_entries -= to_alloc; | |
244 | _fragment_and_emplace(max_length, (base + free_pos) * l0_granularity, | |
245 | to_alloc * l0_granularity, res); | |
246 | _mark_alloc_l0(base + free_pos, base + next_pos); | |
247 | free_pos = find_next_set_bit(slot_val, next_pos + 1); | |
248 | next_pos = free_pos + 1; | |
249 | } else { | |
250 | ++next_pos; | |
251 | } | |
252 | } | |
253 | if (need_entries && free_pos < bits_per_slot) { | |
254 | auto to_alloc = std::min(need_entries, d0 - free_pos); | |
255 | *allocated += to_alloc * l0_granularity; | |
256 | ++alloc_fragments; | |
257 | need_entries -= to_alloc; | |
258 | _fragment_and_emplace(max_length, (base + free_pos) * l0_granularity, | |
259 | to_alloc * l0_granularity, res); | |
260 | _mark_alloc_l0(base + free_pos, base + free_pos + to_alloc); | |
261 | } | |
262 | } | |
263 | return _is_empty_l0(l0_pos0, l0_pos1); | |
264 | } | |
265 | ||
266 | protected: | |
267 | ||
268 | friend class AllocatorLevel02<AllocatorLevel01Loose>; | |
269 | ||
270 | void _init(uint64_t capacity, uint64_t _alloc_unit, bool mark_as_free = true) | |
271 | { | |
272 | l0_granularity = _alloc_unit; | |
273 | // 512 bits at L0 mapped to L1 entry | |
274 | l1_granularity = l0_granularity * bits_per_slotset; | |
275 | ||
276 | // capacity to have slot alignment at l1 | |
277 | auto aligned_capacity = | |
278 | P2ROUNDUP((int64_t)capacity, | |
279 | int64_t(l1_granularity * slotset_width * _children_per_slot())); | |
280 | size_t slot_count = | |
281 | aligned_capacity / l1_granularity / _children_per_slot(); | |
282 | // we use set bit(s) as a marker for (partially) free entry | |
283 | l1.resize(slot_count, mark_as_free ? all_slot_set : all_slot_clear); | |
284 | ||
285 | // l0 slot count | |
286 | size_t slot_count_l0 = aligned_capacity / _alloc_unit / bits_per_slot; | |
287 | // we use set bit(s) as a marker for (partially) free entry | |
288 | l0.resize(slot_count_l0, mark_as_free ? all_slot_set : all_slot_clear); | |
289 | ||
290 | partial_l1_count = unalloc_l1_count = 0; | |
291 | if (mark_as_free) { | |
292 | unalloc_l1_count = slot_count * _children_per_slot(); | |
293 | auto l0_pos_no_use = P2ROUNDUP((int64_t)capacity, (int64_t)l0_granularity) / l0_granularity; | |
294 | _mark_alloc_l1_l0(l0_pos_no_use, aligned_capacity / l0_granularity); | |
295 | } | |
296 | } | |
297 | ||
298 | struct search_ctx_t | |
299 | { | |
300 | size_t partial_count = 0; | |
301 | size_t free_count = 0; | |
302 | uint64_t free_l1_pos = 0; | |
303 | ||
304 | uint64_t min_affordable_len = 0; | |
305 | uint64_t min_affordable_offs = 0; | |
306 | uint64_t affordable_len = 0; | |
307 | uint64_t affordable_offs = 0; | |
308 | ||
309 | bool fully_processed = false; | |
310 | ||
311 | void reset() | |
312 | { | |
313 | *this = search_ctx_t(); | |
314 | } | |
315 | }; | |
316 | enum { | |
317 | NO_STOP, | |
318 | STOP_ON_EMPTY, | |
319 | STOP_ON_PARTIAL, | |
320 | }; | |
321 | void _analyze_partials(uint64_t pos_start, uint64_t pos_end, | |
322 | uint64_t length, uint64_t min_length, int mode, | |
323 | search_ctx_t* ctx); | |
324 | ||
325 | void _mark_l1_on_l0(int64_t l0_pos, int64_t l0_pos_end); | |
326 | void _mark_alloc_l0(int64_t l0_pos_start, int64_t l0_pos_end); | |
327 | ||
328 | void _mark_alloc_l1_l0(int64_t l0_pos_start, int64_t l0_pos_end) | |
329 | { | |
330 | _mark_alloc_l0(l0_pos_start, l0_pos_end); | |
331 | l0_pos_start = P2ALIGN(l0_pos_start, int64_t(bits_per_slotset)); | |
332 | l0_pos_end = P2ROUNDUP(l0_pos_end, int64_t(bits_per_slotset)); | |
333 | _mark_l1_on_l0(l0_pos_start, l0_pos_end); | |
334 | } | |
335 | ||
336 | void _mark_free_l0(int64_t l0_pos_start, int64_t l0_pos_end) | |
337 | { | |
338 | auto d0 = CHILD_PER_SLOT_L0; | |
339 | ||
340 | auto pos = l0_pos_start; | |
341 | slot_t bits = (slot_t)1 << (l0_pos_start % d0); | |
b9c3bfeb TL |
342 | slot_t* val_s = &l0[pos / d0]; |
343 | int64_t pos_e = std::min(l0_pos_end, | |
344 | P2ROUNDUP(l0_pos_start + 1, d0)); | |
a8e16298 | 345 | while (pos < pos_e) { |
b9c3bfeb | 346 | *val_s |= bits; |
a8e16298 TL |
347 | bits <<= 1; |
348 | pos++; | |
349 | } | |
b9c3bfeb | 350 | pos_e = std::min(l0_pos_end, P2ALIGN(l0_pos_end, d0)); |
a8e16298 | 351 | while (pos < pos_e) { |
b9c3bfeb | 352 | *(++val_s) = all_slot_set; |
a8e16298 TL |
353 | pos += d0; |
354 | } | |
355 | bits = 1; | |
b9c3bfeb | 356 | ++val_s; |
a8e16298 | 357 | while (pos < l0_pos_end) { |
b9c3bfeb | 358 | *val_s |= bits; |
a8e16298 TL |
359 | bits <<= 1; |
360 | pos++; | |
361 | } | |
362 | } | |
363 | ||
364 | void _mark_free_l1_l0(int64_t l0_pos_start, int64_t l0_pos_end) | |
365 | { | |
366 | _mark_free_l0(l0_pos_start, l0_pos_end); | |
367 | l0_pos_start = P2ALIGN(l0_pos_start, int64_t(bits_per_slotset)); | |
368 | l0_pos_end = P2ROUNDUP(l0_pos_end, int64_t(bits_per_slotset)); | |
369 | _mark_l1_on_l0(l0_pos_start, l0_pos_end); | |
370 | } | |
371 | ||
372 | bool _is_empty_l0(uint64_t l0_pos, uint64_t l0_pos_end) | |
373 | { | |
374 | bool no_free = true; | |
375 | uint64_t d = slotset_width * CHILD_PER_SLOT_L0; | |
376 | assert(0 == (l0_pos % d)); | |
377 | assert(0 == (l0_pos_end % d)); | |
378 | ||
379 | auto idx = l0_pos / CHILD_PER_SLOT_L0; | |
380 | auto idx_end = l0_pos_end / CHILD_PER_SLOT_L0; | |
381 | while (idx < idx_end && no_free) { | |
382 | no_free = l0[idx] == all_slot_clear; | |
383 | ++idx; | |
384 | } | |
385 | return no_free; | |
386 | } | |
387 | bool _is_empty_l1(uint64_t l1_pos, uint64_t l1_pos_end) | |
388 | { | |
389 | bool no_free = true; | |
390 | uint64_t d = slotset_width * _children_per_slot(); | |
391 | assert(0 == (l1_pos % d)); | |
392 | assert(0 == (l1_pos_end % d)); | |
393 | ||
394 | auto idx = l1_pos / CHILD_PER_SLOT; | |
395 | auto idx_end = l1_pos_end / CHILD_PER_SLOT; | |
396 | while (idx < idx_end && no_free) { | |
397 | no_free = _is_slot_fully_allocated(idx); | |
398 | ++idx; | |
399 | } | |
400 | return no_free; | |
401 | } | |
402 | ||
403 | interval_t _allocate_l1_contiguous(uint64_t length, | |
404 | uint64_t min_length, uint64_t max_length, | |
405 | uint64_t pos_start, uint64_t pos_end); | |
406 | ||
407 | bool _allocate_l1(uint64_t length, | |
408 | uint64_t min_length, uint64_t max_length, | |
409 | uint64_t l1_pos_start, uint64_t l1_pos_end, | |
410 | uint64_t* allocated, | |
411 | interval_vector_t* res); | |
412 | ||
b9c3bfeb | 413 | uint64_t _mark_alloc_l1(uint64_t offset, uint64_t length) |
a8e16298 | 414 | { |
b9c3bfeb TL |
415 | uint64_t l0_pos_start = offset / l0_granularity; |
416 | uint64_t l0_pos_end = P2ROUNDUP(offset + length, l0_granularity) / l0_granularity; | |
a8e16298 TL |
417 | _mark_alloc_l1_l0(l0_pos_start, l0_pos_end); |
418 | return l0_granularity * (l0_pos_end - l0_pos_start); | |
419 | } | |
420 | ||
421 | uint64_t _free_l1(uint64_t offs, uint64_t len) | |
422 | { | |
423 | uint64_t l0_pos_start = offs / l0_granularity; | |
424 | uint64_t l0_pos_end = P2ROUNDUP(offs + len, l0_granularity) / l0_granularity; | |
425 | _mark_free_l1_l0(l0_pos_start, l0_pos_end); | |
426 | return l0_granularity * (l0_pos_end - l0_pos_start); | |
427 | } | |
428 | ||
429 | public: | |
430 | uint64_t debug_get_allocated(uint64_t pos0 = 0, uint64_t pos1 = 0) | |
431 | { | |
432 | if (pos1 == 0) { | |
433 | pos1 = l1.size() * CHILD_PER_SLOT; | |
434 | } | |
435 | auto avail = debug_get_free(pos0, pos1); | |
436 | return (pos1 - pos0) * l1_granularity - avail; | |
437 | } | |
438 | ||
439 | uint64_t debug_get_free(uint64_t l1_pos0 = 0, uint64_t l1_pos1 = 0) | |
440 | { | |
441 | assert(0 == (l1_pos0 % CHILD_PER_SLOT)); | |
442 | assert(0 == (l1_pos1 % CHILD_PER_SLOT)); | |
443 | ||
444 | auto idx0 = l1_pos0 * slotset_width; | |
445 | auto idx1 = l1_pos1 * slotset_width; | |
446 | ||
447 | if (idx1 == 0) { | |
448 | idx1 = l0.size(); | |
449 | } | |
450 | ||
451 | uint64_t res = 0; | |
452 | for (uint64_t i = idx0; i < idx1; ++i) { | |
453 | auto v = l0[i]; | |
454 | if (v == all_slot_set) { | |
455 | res += CHILD_PER_SLOT_L0; | |
456 | } else if (v != all_slot_clear) { | |
457 | size_t cnt = 0; | |
458 | #ifdef __GNUC__ | |
459 | cnt = __builtin_popcountll(v); | |
460 | #else | |
461 | // Kernighan's Alg to count set bits | |
462 | while (v) { | |
463 | v &= (v - 1); | |
464 | cnt++; | |
465 | } | |
466 | #endif | |
467 | res += cnt; | |
468 | } | |
469 | } | |
470 | return res * l0_granularity; | |
471 | } | |
472 | void collect_stats( | |
473 | std::map<size_t, size_t>& bins_overall) override; | |
b9c3bfeb TL |
474 | |
475 | static inline ssize_t count_0s(slot_t slot_val, size_t start_pos); | |
476 | static inline ssize_t count_1s(slot_t slot_val, size_t start_pos); | |
477 | void dump(std::function<void(uint64_t offset, uint64_t length)> notify); | |
a8e16298 TL |
478 | }; |
479 | ||
b9c3bfeb | 480 | |
a8e16298 TL |
481 | class AllocatorLevel01Compact : public AllocatorLevel01 |
482 | { | |
483 | uint64_t _children_per_slot() const override | |
484 | { | |
485 | return 8; | |
486 | } | |
487 | public: | |
488 | void collect_stats( | |
489 | std::map<size_t, size_t>& bins_overall) override | |
490 | { | |
491 | // not implemented | |
492 | } | |
493 | }; | |
494 | ||
495 | template <class L1> | |
496 | class AllocatorLevel02 : public AllocatorLevel | |
497 | { | |
498 | public: | |
499 | uint64_t debug_get_free(uint64_t pos0 = 0, uint64_t pos1 = 0) | |
500 | { | |
501 | std::lock_guard<std::mutex> l(lock); | |
502 | return l1.debug_get_free(pos0 * l1._children_per_slot() * bits_per_slot, | |
503 | pos1 * l1._children_per_slot() * bits_per_slot); | |
504 | } | |
505 | uint64_t debug_get_allocated(uint64_t pos0 = 0, uint64_t pos1 = 0) | |
506 | { | |
507 | std::lock_guard<std::mutex> l(lock); | |
508 | return l1.debug_get_allocated(pos0 * l1._children_per_slot() * bits_per_slot, | |
509 | pos1 * l1._children_per_slot() * bits_per_slot); | |
510 | } | |
511 | ||
512 | uint64_t get_available() | |
513 | { | |
514 | std::lock_guard<std::mutex> l(lock); | |
515 | return available; | |
516 | } | |
517 | inline uint64_t get_min_alloc_size() const | |
518 | { | |
519 | return l1.get_min_alloc_size(); | |
520 | } | |
521 | void collect_stats( | |
522 | std::map<size_t, size_t>& bins_overall) override { | |
523 | ||
524 | std::lock_guard<std::mutex> l(lock); | |
525 | l1.collect_stats(bins_overall); | |
526 | } | |
527 | ||
528 | protected: | |
529 | std::mutex lock; | |
530 | L1 l1; | |
531 | slot_vector_t l2; | |
532 | uint64_t l2_granularity = 0; // space per entry | |
533 | uint64_t available = 0; | |
534 | uint64_t last_pos = 0; | |
535 | ||
536 | enum { | |
537 | CHILD_PER_SLOT = bits_per_slot, // 64 | |
538 | }; | |
539 | ||
540 | uint64_t _children_per_slot() const override | |
541 | { | |
542 | return CHILD_PER_SLOT; | |
543 | } | |
544 | uint64_t _level_granularity() const override | |
545 | { | |
546 | return l2_granularity; | |
547 | } | |
548 | ||
549 | void _init(uint64_t capacity, uint64_t _alloc_unit, bool mark_as_free = true) | |
550 | { | |
551 | assert(ISP2(_alloc_unit)); | |
552 | l1._init(capacity, _alloc_unit, mark_as_free); | |
553 | ||
554 | l2_granularity = | |
555 | l1._level_granularity() * l1._children_per_slot() * slotset_width; | |
556 | ||
557 | // capacity to have slot alignment at l2 | |
558 | auto aligned_capacity = | |
559 | P2ROUNDUP((int64_t)capacity, (int64_t)l2_granularity * CHILD_PER_SLOT); | |
560 | size_t elem_count = aligned_capacity / l2_granularity / CHILD_PER_SLOT; | |
561 | // we use set bit(s) as a marker for (partially) free entry | |
562 | l2.resize(elem_count, mark_as_free ? all_slot_set : all_slot_clear); | |
563 | ||
564 | if (mark_as_free) { | |
565 | // capacity to have slotset alignment at l1 | |
566 | auto l2_pos_no_use = | |
567 | P2ROUNDUP((int64_t)capacity, (int64_t)l2_granularity) / l2_granularity; | |
568 | _mark_l2_allocated(l2_pos_no_use, aligned_capacity / l2_granularity); | |
569 | available = P2ALIGN(capacity, _alloc_unit); | |
570 | } else { | |
571 | available = 0; | |
572 | } | |
573 | } | |
574 | ||
575 | void _mark_l2_allocated(int64_t l2_pos, int64_t l2_pos_end) | |
576 | { | |
577 | auto d = CHILD_PER_SLOT; | |
578 | assert(0 <= l2_pos_end); | |
579 | assert((int64_t)l2.size() >= (l2_pos_end / d)); | |
580 | ||
581 | while (l2_pos < l2_pos_end) { | |
582 | l2[l2_pos / d] &= ~(slot_t(1) << (l2_pos % d)); | |
583 | ++l2_pos; | |
584 | } | |
585 | } | |
586 | ||
587 | void _mark_l2_free(int64_t l2_pos, int64_t l2_pos_end) | |
588 | { | |
589 | auto d = CHILD_PER_SLOT; | |
590 | assert(0 <= l2_pos_end); | |
591 | assert((int64_t)l2.size() >= (l2_pos_end / d)); | |
592 | ||
593 | while (l2_pos < l2_pos_end) { | |
594 | l2[l2_pos / d] |= (slot_t(1) << (l2_pos % d)); | |
595 | ++l2_pos; | |
596 | } | |
597 | } | |
598 | ||
599 | void _mark_l2_on_l1(int64_t l2_pos, int64_t l2_pos_end) | |
600 | { | |
601 | auto d = CHILD_PER_SLOT; | |
602 | assert(0 <= l2_pos_end); | |
603 | assert((int64_t)l2.size() >= (l2_pos_end / d)); | |
604 | ||
605 | auto idx = l2_pos * slotset_width; | |
606 | auto idx_end = l2_pos_end * slotset_width; | |
607 | bool all_allocated = true; | |
608 | while (idx < idx_end) { | |
609 | if (!l1._is_slot_fully_allocated(idx)) { | |
610 | all_allocated = false; | |
611 | idx = P2ROUNDUP(int64_t(++idx), int64_t(slotset_width)); | |
612 | } | |
613 | else { | |
614 | ++idx; | |
615 | } | |
616 | if ((idx % slotset_width) == 0) { | |
617 | if (all_allocated) { | |
618 | l2[l2_pos / d] &= ~(slot_t(1) << (l2_pos % d)); | |
619 | } | |
620 | else { | |
621 | l2[l2_pos / d] |= (slot_t(1) << (l2_pos % d)); | |
622 | } | |
623 | all_allocated = true; | |
624 | ++l2_pos; | |
625 | } | |
626 | } | |
627 | } | |
628 | ||
629 | void _allocate_l2(uint64_t length, | |
630 | uint64_t min_length, | |
631 | uint64_t max_length, | |
632 | uint64_t hint, | |
633 | ||
634 | uint64_t* allocated, | |
635 | interval_vector_t* res) | |
636 | { | |
637 | uint64_t prev_allocated = *allocated; | |
638 | uint64_t d = CHILD_PER_SLOT; | |
639 | assert(ISP2(min_length)); | |
640 | assert(min_length <= l2_granularity); | |
641 | assert(max_length == 0 || max_length >= min_length); | |
642 | assert(max_length == 0 || (max_length % min_length) == 0); | |
643 | assert(length >= min_length); | |
644 | assert((length % min_length) == 0); | |
645 | ||
646 | uint64_t cap = 1ull << 31; | |
647 | if (max_length == 0 || max_length >= cap) { | |
648 | max_length = cap; | |
649 | } | |
650 | ||
651 | uint64_t l1_w = slotset_width * l1._children_per_slot(); | |
652 | ||
653 | std::lock_guard<std::mutex> l(lock); | |
654 | ||
655 | if (available < min_length) { | |
656 | return; | |
657 | } | |
658 | if (hint != 0) { | |
659 | last_pos = (hint / d) < l2.size() ? P2ALIGN(hint, d) : 0; | |
660 | } | |
661 | auto l2_pos = last_pos; | |
662 | auto last_pos0 = last_pos; | |
663 | auto pos = last_pos / d; | |
664 | auto pos_end = l2.size(); | |
665 | // outer loop below is intended to optimize the performance by | |
666 | // avoiding 'modulo' operations inside the internal loop. | |
667 | // Looks like they have negative impact on the performance | |
668 | for (auto i = 0; i < 2; ++i) { | |
669 | for(; length > *allocated && pos < pos_end; ++pos) { | |
670 | slot_t& slot_val = l2[pos]; | |
671 | size_t free_pos = 0; | |
672 | bool all_set = false; | |
673 | if (slot_val == all_slot_clear) { | |
674 | l2_pos += d; | |
675 | last_pos = l2_pos; | |
676 | continue; | |
677 | } else if (slot_val == all_slot_set) { | |
678 | free_pos = 0; | |
679 | all_set = true; | |
680 | } else { | |
681 | free_pos = find_next_set_bit(slot_val, 0); | |
682 | assert(free_pos < bits_per_slot); | |
683 | } | |
684 | do { | |
685 | assert(length > *allocated); | |
686 | bool empty = l1._allocate_l1(length, | |
687 | min_length, | |
688 | max_length, | |
689 | (l2_pos + free_pos) * l1_w, | |
690 | (l2_pos + free_pos + 1) * l1_w, | |
691 | allocated, | |
692 | res); | |
693 | if (empty) { | |
694 | slot_val &= ~(slot_t(1) << free_pos); | |
695 | } | |
696 | if (length <= *allocated || slot_val == all_slot_clear) { | |
697 | break; | |
698 | } | |
699 | ++free_pos; | |
700 | if (!all_set) { | |
701 | free_pos = find_next_set_bit(slot_val, free_pos); | |
702 | } | |
703 | } while (free_pos < bits_per_slot); | |
704 | last_pos = l2_pos; | |
705 | l2_pos += d; | |
706 | } | |
707 | l2_pos = 0; | |
708 | pos = 0; | |
709 | pos_end = last_pos0 / d; | |
710 | } | |
711 | ||
712 | ++l2_allocs; | |
713 | auto allocated_here = *allocated - prev_allocated; | |
714 | assert(available >= allocated_here); | |
715 | available -= allocated_here; | |
716 | } | |
717 | ||
718 | #ifndef NON_CEPH_BUILD | |
719 | // to provide compatibility with BlueStore's allocator interface | |
720 | void _free_l2(const interval_set<uint64_t> & rr) | |
721 | { | |
722 | uint64_t released = 0; | |
723 | std::lock_guard<std::mutex> l(lock); | |
724 | for (auto r : rr) { | |
725 | released += l1._free_l1(r.first, r.second); | |
726 | uint64_t l2_pos = r.first / l2_granularity; | |
727 | uint64_t l2_pos_end = P2ROUNDUP(int64_t(r.first + r.second), int64_t(l2_granularity)) / l2_granularity; | |
728 | ||
729 | _mark_l2_free(l2_pos, l2_pos_end); | |
730 | } | |
731 | available += released; | |
732 | } | |
733 | #endif | |
734 | ||
735 | template <typename T> | |
736 | void _free_l2(const T& rr) | |
737 | { | |
738 | uint64_t released = 0; | |
739 | std::lock_guard<std::mutex> l(lock); | |
740 | for (auto r : rr) { | |
741 | released += l1._free_l1(r.offset, r.length); | |
742 | uint64_t l2_pos = r.offset / l2_granularity; | |
743 | uint64_t l2_pos_end = P2ROUNDUP(int64_t(r.offset + r.length), int64_t(l2_granularity)) / l2_granularity; | |
744 | ||
745 | _mark_l2_free(l2_pos, l2_pos_end); | |
746 | } | |
747 | available += released; | |
748 | } | |
749 | ||
750 | void _mark_allocated(uint64_t o, uint64_t len) | |
751 | { | |
752 | uint64_t l2_pos = o / l2_granularity; | |
753 | uint64_t l2_pos_end = P2ROUNDUP(int64_t(o + len), int64_t(l2_granularity)) / l2_granularity; | |
754 | ||
755 | std::lock_guard<std::mutex> l(lock); | |
b9c3bfeb | 756 | auto allocated = l1._mark_alloc_l1(o, len); |
a8e16298 TL |
757 | assert(available >= allocated); |
758 | available -= allocated; | |
759 | _mark_l2_on_l1(l2_pos, l2_pos_end); | |
760 | } | |
761 | ||
762 | void _mark_free(uint64_t o, uint64_t len) | |
763 | { | |
764 | uint64_t l2_pos = o / l2_granularity; | |
765 | uint64_t l2_pos_end = P2ROUNDUP(int64_t(o + len), int64_t(l2_granularity)) / l2_granularity; | |
766 | ||
767 | std::lock_guard<std::mutex> l(lock); | |
768 | available += l1._free_l1(o, len); | |
769 | _mark_l2_free(l2_pos, l2_pos_end); | |
770 | } | |
771 | void _shutdown() | |
772 | { | |
773 | last_pos = 0; | |
774 | } | |
775 | double _get_fragmentation() { | |
776 | std::lock_guard<std::mutex> l(lock); | |
777 | return l1.get_fragmentation(); | |
778 | } | |
779 | }; | |
780 | ||
781 | #endif |