Branch data Line data Source code
1 : : /*
2 : : * Copyright (C) 2026 by Thun Lu. All rights reserved.
3 : : * Author: Thun Lu <thun.lu@zohomail.cn>
4 : : * Repo: https://github.com/thun-res/vlink
5 : : * _ __ __ _ __
6 : : * | | / / / / (_) ____ / /__
7 : : * | | / / / / / / / __ \ / //_/
8 : : * | |/ / / /___ / / / / / / / ,<
9 : : * |___/ /_____/ /_/ /_/ /_/ /_/|_|
10 : : *
11 : : * Licensed under the Apache License, Version 2.0 (the "License");
12 : : * you may not use this file except in compliance with the License.
13 : : * You may obtain a copy of the License at
14 : : *
15 : : * http://www.apache.org/licenses/LICENSE-2.0
16 : : *
17 : : * Unless required by applicable law or agreed to in writing, software
18 : : * distributed under the License is distributed on an "AS IS" BASIS,
19 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20 : : * See the License for the specific language governing permissions and
21 : : * limitations under the License.
22 : : */
23 : :
24 : : #include "./base/memory_pool.h"
25 : :
26 : : #include <algorithm>
27 : : #include <atomic>
28 : : #include <charconv>
29 : : #include <cstddef>
30 : : #include <cstdint>
31 : : #include <cstdio>
32 : : #include <exception>
33 : : #include <mutex>
34 : : #include <new>
35 : : #include <string>
36 : : #include <system_error>
37 : : #include <thread>
38 : : #include <utility>
39 : : #include <vector>
40 : :
41 : : #include "./base/spin_lock.h"
42 : : #include "./base/utils.h"
43 : :
44 : : #define MEMORY_POOL_NEVER_DELETE 0
45 : :
46 : : #define MEMORY_POOL_LOG(format, ...) \
47 : : do { \
48 : : std::fprintf(stderr, format "\n", __VA_ARGS__); \
49 : : std::fflush(stderr); \
50 : : } while (false)
51 : :
52 : : namespace vlink {
53 : :
54 : : static constexpr int kMinMemoryLevel = 0;
55 : : static constexpr int kMaxMemoryLevel = 9;
56 : : static constexpr int kDefaultMemoryLevel = 3;
57 : : static constexpr size_t kMaxTierCount = 20U;
58 : : static constexpr size_t kMaxLevelCount = 10U;
59 : : static constexpr size_t kInitialBlocksPerChunk = 1U;
60 : : static constexpr size_t kInitialChunksReserve = 16U;
61 : : static constexpr size_t kInitialChunkBytesTarget = 64U * 1024U;
62 : : static constexpr size_t kMaxLazyChunkBytes = 64U * 1024U;
63 : : static constexpr size_t kMinLazyChunkBytes = 32U * 1024U;
64 : : static constexpr size_t kLazyChunkQuotaDivisor = 16U;
65 : : static constexpr size_t kMinTierShardCount = 8U;
66 : : static constexpr size_t kMaxTierShardCount = 64U;
67 : : static constexpr size_t kDefaultBatchSize = 16U;
68 : : static constexpr uint32_t kShardingContentionThreshold = 8U;
69 : :
70 : : static_assert(__STDCPP_DEFAULT_NEW_ALIGNMENT__ >= MemoryPool::kBlockAlignment,
71 : : "MemoryPool: plain operator new must satisfy kBlockAlignment");
72 : :
73 : : // clang-format off
74 : : static constexpr MemoryPool::Tier kDefaultTierTable[kMaxLevelCount][kMaxTierCount] = {
75 : : // L0 ~ 0 MiB. (bypass; all entries are sentinels)
76 : : {
77 : : {32U, 0U},
78 : : {64U, 0U},
79 : : {128U, 0U},
80 : : {256U, 0U},
81 : : {512U, 0U},
82 : : {1U * 1024U, 0U},
83 : : {2U * 1024U, 0U},
84 : : {4U * 1024U, 0U},
85 : : {8U * 1024U, 0U},
86 : : {16U * 1024U, 0U},
87 : : {32U * 1024U, 0U},
88 : : {64U * 1024U, 0U},
89 : : {128U * 1024U, 0U},
90 : : {256U * 1024U, 0U},
91 : : {512U * 1024U, 0U},
92 : : {1U * 1024U * 1024U, 0U},
93 : : {4U * 1024U * 1024U, 0U},
94 : : {8U * 1024U * 1024U, 0U},
95 : : {16U * 1024U * 1024U, 0U},
96 : : },
97 : : // L1 ~ 4 MiB.
98 : : {
99 : : {32U, 8U * 1024U},
100 : : {64U, 4U * 1024U},
101 : : {128U, 2U * 1024U},
102 : : {256U, 1U * 1024U},
103 : : {512U, 512U},
104 : : {1U * 1024U, 256U},
105 : : {2U * 1024U, 128U},
106 : : {4U * 1024U, 64U},
107 : : {8U * 1024U, 32U},
108 : : {16U * 1024U, 16U},
109 : : {32U * 1024U, 8U},
110 : : {64U * 1024U, 4U},
111 : : {128U * 1024U, 2U},
112 : : {256U * 1024U, 1U},
113 : : {512U * 1024U, 1U},
114 : : {1U * 1024U * 1024U, 0U},
115 : : {4U * 1024U * 1024U, 0U},
116 : : {8U * 1024U * 1024U, 0U},
117 : : {16U * 1024U * 1024U, 0U},
118 : : },
119 : : // L2 ~ 8.5 MiB.
120 : : {
121 : : {32U, 16U * 1024U},
122 : : {64U, 8U * 1024U},
123 : : {128U, 4U * 1024U},
124 : : {256U, 2U * 1024U},
125 : : {512U, 1U * 1024U},
126 : : {1U * 1024U, 512U},
127 : : {2U * 1024U, 256U},
128 : : {4U * 1024U, 128U},
129 : : {8U * 1024U, 64U},
130 : : {16U * 1024U, 32U},
131 : : {32U * 1024U, 16U},
132 : : {64U * 1024U, 8U},
133 : : {128U * 1024U, 4U},
134 : : {256U * 1024U, 2U},
135 : : {512U * 1024U, 1U},
136 : : {1U * 1024U * 1024U, 1U},
137 : : {4U * 1024U * 1024U, 0U},
138 : : {8U * 1024U * 1024U, 0U},
139 : : {16U * 1024U * 1024U, 0U},
140 : : },
141 : : // L3 ~ 16 MiB. (Default)
142 : : {
143 : : {32U, 32U * 1024U},
144 : : {64U, 16U * 1024U},
145 : : {128U, 8U * 1024U},
146 : : {256U, 4U * 1024U},
147 : : {512U, 2U * 1024U},
148 : : {1U * 1024U, 1U * 1024U},
149 : : {2U * 1024U, 512U},
150 : : {4U * 1024U, 256U},
151 : : {8U * 1024U, 128U},
152 : : {16U * 1024U, 64U},
153 : : {32U * 1024U, 32U},
154 : : {64U * 1024U, 16U},
155 : : {128U * 1024U, 8U},
156 : : {256U * 1024U, 4U},
157 : : {512U * 1024U, 2U},
158 : : {1U * 1024U * 1024U, 1U},
159 : : {4U * 1024U * 1024U, 0U},
160 : : {8U * 1024U * 1024U, 0U},
161 : : {16U * 1024U * 1024U, 0U},
162 : : },
163 : : // L4 ~ 42 MiB.
164 : : {
165 : : {32U, 64U * 1024U},
166 : : {64U, 32U * 1024U},
167 : : {128U, 16U * 1024U},
168 : : {256U, 8U * 1024U},
169 : : {512U, 4U * 1024U},
170 : : {1U * 1024U, 2U * 1024U},
171 : : {2U * 1024U, 1U * 1024U},
172 : : {4U * 1024U, 512U},
173 : : {8U * 1024U, 256U},
174 : : {16U * 1024U, 128U},
175 : : {32U * 1024U, 64U},
176 : : {64U * 1024U, 32U},
177 : : {128U * 1024U, 16U},
178 : : {256U * 1024U, 8U},
179 : : {512U * 1024U, 4U},
180 : : {1U * 1024U * 1024U, 4U},
181 : : {4U * 1024U * 1024U, 2U},
182 : : {8U * 1024U * 1024U, 0U},
183 : : {16U * 1024U * 1024U, 0U},
184 : : },
185 : : // L5 ~ 92 MiB.
186 : : {
187 : : {32U, 128U * 1024U},
188 : : {64U, 64U * 1024U},
189 : : {128U, 32U * 1024U},
190 : : {256U, 16U * 1024U},
191 : : {512U, 8U * 1024U},
192 : : {1U * 1024U, 4U * 1024U},
193 : : {2U * 1024U, 2U * 1024U},
194 : : {4U * 1024U, 1U * 1024U},
195 : : {8U * 1024U, 512U},
196 : : {16U * 1024U, 256U},
197 : : {32U * 1024U, 128U},
198 : : {64U * 1024U, 64U},
199 : : {128U * 1024U, 32U},
200 : : {256U * 1024U, 16U},
201 : : {512U * 1024U, 8U},
202 : : {1U * 1024U * 1024U, 8U},
203 : : {4U * 1024U * 1024U, 4U},
204 : : {8U * 1024U * 1024U, 1U},
205 : : {16U * 1024U * 1024U, 0U},
206 : : },
207 : : // L6 ~ 200 MiB.
208 : : {
209 : : {32U, 256U * 1024U},
210 : : {64U, 128U * 1024U},
211 : : {128U, 64U * 1024U},
212 : : {256U, 32U * 1024U},
213 : : {512U, 16U * 1024U},
214 : : {1U * 1024U, 8U * 1024U},
215 : : {2U * 1024U, 4U * 1024U},
216 : : {4U * 1024U, 2U * 1024U},
217 : : {8U * 1024U, 1U * 1024U},
218 : : {16U * 1024U, 512U},
219 : : {32U * 1024U, 256U},
220 : : {64U * 1024U, 128U},
221 : : {128U * 1024U, 64U},
222 : : {256U * 1024U, 32U},
223 : : {512U * 1024U, 16U},
224 : : {1U * 1024U * 1024U, 16U},
225 : : {4U * 1024U * 1024U, 8U},
226 : : {8U * 1024U * 1024U, 2U},
227 : : {16U * 1024U * 1024U, 1U},
228 : : },
229 : : // L7 ~ 264 MiB.
230 : : {
231 : : {32U, 256U * 1024U},
232 : : {64U, 128U * 1024U},
233 : : {128U, 64U * 1024U},
234 : : {256U, 32U * 1024U},
235 : : {512U, 16U * 1024U},
236 : : {1U * 1024U, 8U * 1024U},
237 : : {2U * 1024U, 4U * 1024U},
238 : : {4U * 1024U, 2U * 1024U},
239 : : {8U * 1024U, 1U * 1024U},
240 : : {16U * 1024U, 512U},
241 : : {32U * 1024U, 256U},
242 : : {64U * 1024U, 128U},
243 : : {128U * 1024U, 64U},
244 : : {256U * 1024U, 32U},
245 : : {512U * 1024U, 16U},
246 : : {1U * 1024U * 1024U, 16U},
247 : : {4U * 1024U * 1024U, 16U},
248 : : {8U * 1024U * 1024U, 4U},
249 : : {16U * 1024U * 1024U, 2U},
250 : : },
251 : : // L8 ~ 528 MiB.
252 : : {
253 : : {32U, 512U * 1024U},
254 : : {64U, 256U * 1024U},
255 : : {128U, 128U * 1024U},
256 : : {256U, 64U * 1024U},
257 : : {512U, 32U * 1024U},
258 : : {1U * 1024U, 16U * 1024U},
259 : : {2U * 1024U, 8U * 1024U},
260 : : {4U * 1024U, 4U * 1024U},
261 : : {8U * 1024U, 2U * 1024U},
262 : : {16U * 1024U, 1U * 1024U},
263 : : {32U * 1024U, 512U},
264 : : {64U * 1024U, 256U},
265 : : {128U * 1024U, 128U},
266 : : {256U * 1024U, 64U},
267 : : {512U * 1024U, 32U},
268 : : {1U * 1024U * 1024U, 32U},
269 : : {4U * 1024U * 1024U, 32U},
270 : : {8U * 1024U * 1024U, 8U},
271 : : {16U * 1024U * 1024U, 4U},
272 : : },
273 : : // L9 ~ 656 MiB.
274 : : {
275 : : {32U, 512U * 1024U},
276 : : {64U, 256U * 1024U},
277 : : {128U, 128U * 1024U},
278 : : {256U, 64U * 1024U},
279 : : {512U, 32U * 1024U},
280 : : {1U * 1024U, 16U * 1024U},
281 : : {2U * 1024U, 8U * 1024U},
282 : : {4U * 1024U, 4U * 1024U},
283 : : {8U * 1024U, 2U * 1024U},
284 : : {16U * 1024U, 1U * 1024U},
285 : : {32U * 1024U, 512U},
286 : : {64U * 1024U, 256U},
287 : : {128U * 1024U, 128U},
288 : : {256U * 1024U, 64U},
289 : : {512U * 1024U, 32U},
290 : : {1U * 1024U * 1024U, 32U},
291 : : {4U * 1024U * 1024U, 32U},
292 : : {8U * 1024U * 1024U, 16U},
293 : : {16U * 1024U * 1024U, 8U},
294 : : }
295 : : };
296 : : // clang-format on
297 : :
298 : : struct MemoryFreeNode final {
299 : : MemoryFreeNode* next{nullptr};
300 : : };
301 : :
302 : : struct MemoryChunk final {
303 : : void* ptr{nullptr};
304 : : size_t bytes{0};
305 : : };
306 : :
307 : : struct alignas(64) MemoryTierShard final {
308 : : SpinLock mtx;
309 : : std::atomic<MemoryFreeNode*> free_list_head{nullptr};
310 : : std::atomic<uint64_t> hit_count{0};
311 : : std::atomic<uint64_t> deallocate_count{0};
312 : : };
313 : :
314 : : struct MemoryChunkTally final {
315 : : MemoryChunk chunk;
316 : : size_t free_nodes{0};
317 : : };
318 : :
319 : : // NOLINTNEXTLINE(clang-analyzer-optin.performance.Padding)
320 : : struct alignas(64) MemoryTierState final {
321 : : size_t max_size{0};
322 : : size_t block_size{0};
323 : : size_t blocks_per_chunk{0};
324 : : size_t next_chunk_blocks{0};
325 : : size_t initial_chunk_blocks{0};
326 : : size_t lazy_chunk_blocks{0};
327 : : size_t batch_size{kDefaultBatchSize};
328 : :
329 : : MemoryTierShard* shards{nullptr};
330 : : size_t shard_count{0};
331 : : std::vector<MemoryChunk> chunks;
332 : : std::mutex grow_mtx;
333 : : std::mutex clear_mtx;
334 : : std::atomic<bool> sharded{false};
335 : : std::atomic<uint32_t> contention_count{0U};
336 : :
337 : : std::atomic<uint64_t> chunk_count{0};
338 : : std::atomic<uint64_t> upstream_alloc_count{0};
339 : : std::atomic<uint64_t> upstream_alloc_bytes{0};
340 : : };
341 : :
342 : : struct alignas(64) MemoryOversizedCounters final {
343 : : std::atomic<uint64_t> alloc_count{0};
344 : : std::atomic<uint64_t> alloc_bytes{0};
345 : : std::atomic<uint64_t> dealloc_count{0};
346 : : };
347 : :
348 [ + # + # ]: 716399 : static constexpr bool is_power_of_two(size_t x) noexcept { return x != 0 && ((x & (x - 1U)) == 0U); }
349 : :
350 : 3944 : static constexpr size_t round_up(size_t value, size_t alignment) noexcept {
351 : 3944 : return (value + alignment - 1U) & ~(alignment - 1U);
352 : : }
353 : :
354 : : static constexpr bool default_tier_table_well_formed() noexcept {
355 : : // NOLINTNEXTLINE(modernize-loop-convert)
356 : : for (size_t level = 0; level < kMaxLevelCount; ++level) {
357 : : size_t prev_max_size = 0U;
358 : :
359 : : for (size_t t = 0; t < kMaxTierCount; ++t) {
360 : : const size_t max_size = kDefaultTierTable[level][t].max_size;
361 : :
362 : : if (max_size == 0U) {
363 : : break;
364 : : }
365 : :
366 : : if (max_size < sizeof(MemoryFreeNode)) {
367 : : return false;
368 : : }
369 : :
370 : : if (t > 0U && max_size <= prev_max_size) {
371 : : return false;
372 : : }
373 : :
374 : : prev_max_size = max_size;
375 : : }
376 : : }
377 : :
378 : : return true;
379 : : }
380 : :
381 : : static_assert(default_tier_table_well_formed(),
382 : : "MemoryPool: kDefaultTierTable contains a malformed row "
383 : : "(undersized tier or non-monotonic max_size)");
384 : :
385 : : static std::atomic<size_t> next_thread_slot{0U};
386 : : static thread_local size_t current_thread_slot_plus_one = 0U;
387 : :
388 : 147949 : static size_t current_thread_slot() noexcept {
389 [ + + ]: 147949 : if VUNLIKELY (current_thread_slot_plus_one == 0U) {
390 : 135 : current_thread_slot_plus_one = next_thread_slot.fetch_add(1U, std::memory_order_relaxed) + 1U;
391 : : }
392 : :
393 : 147949 : return current_thread_slot_plus_one - 1U;
394 : : }
395 : :
396 : 147523 : static size_t current_tier_shard(const MemoryTierState& state) noexcept {
397 : 147523 : return current_thread_slot() & (state.shard_count - 1U);
398 : : }
399 : :
400 : 281 : static size_t default_tier_shard_count() noexcept {
401 : 281 : const size_t threads = std::thread::hardware_concurrency();
402 : 281 : size_t count = kMinTierShardCount;
403 : :
404 [ - + - - ]: 281 : while (count < threads && count < kMaxTierShardCount) {
405 : 0 : count *= 2U;
406 : : }
407 : :
408 : 281 : return count;
409 : : }
410 : :
411 : 742875 : static MemoryFreeNode* head_of(const MemoryTierShard& shard) noexcept {
412 : 742875 : return shard.free_list_head.load(std::memory_order_relaxed);
413 : : }
414 : :
415 : 754171 : static void set_head(MemoryTierShard& shard, MemoryFreeNode* head) noexcept {
416 : 754171 : shard.free_list_head.store(head, std::memory_order_relaxed);
417 : 756400 : }
418 : :
419 : 718464 : static void bump_counter(std::atomic<uint64_t>& counter) noexcept {
420 : 1437025 : counter.store(counter.load(std::memory_order_relaxed) + 1U, std::memory_order_relaxed);
421 : 718645 : }
422 : :
423 : 76776 : static MemoryFreeNode* pop_free_node(MemoryTierShard& shard) noexcept {
424 : 76776 : SpinLockGuard lock(shard.mtx);
425 : 77746 : MemoryFreeNode* node = head_of(shard);
426 : :
427 [ + + ]: 77297 : if (node == nullptr) {
428 : 6188 : return nullptr;
429 : : }
430 : :
431 : 71109 : set_head(shard, node->next);
432 : 71656 : bump_counter(shard.hit_count);
433 : :
434 : 71939 : return node;
435 : 78127 : }
436 : :
437 : 4110 : static MemoryFreeNode* steal_free_nodes(MemoryTierState& state, size_t target_index) noexcept {
438 : 4110 : MemoryTierShard& target = state.shards[target_index];
439 : :
440 [ + + ]: 14458 : for (size_t offset = 1U; offset < state.shard_count; ++offset) {
441 : 13786 : MemoryTierShard& source = state.shards[(target_index + offset) & (state.shard_count - 1U)];
442 : 13786 : MemoryFreeNode* first = nullptr;
443 : 13786 : MemoryFreeNode* last = nullptr;
444 : :
445 [ + + ]: 13786 : if (head_of(source) == nullptr) {
446 : 10249 : continue;
447 : : }
448 : :
449 : : {
450 : 3544 : SpinLockGuard source_lock(source.mtx);
451 : 3552 : first = head_of(source);
452 : :
453 [ + + ]: 3549 : if (first == nullptr) {
454 : 99 : continue;
455 : : }
456 : :
457 : 3450 : last = first;
458 : :
459 : 3450 : size_t count = 1U;
460 : :
461 [ + + + + ]: 39341 : while (count < state.batch_size && last->next != nullptr) {
462 : 35891 : last = last->next;
463 : 35891 : ++count;
464 : : }
465 : :
466 : 3450 : set_head(source, last->next);
467 : 3450 : last->next = nullptr;
468 : 3450 : bump_counter(source.hit_count);
469 [ + + ]: 3552 : }
470 : :
471 : 3453 : MemoryFreeNode* cached = first->next;
472 : 3453 : first->next = nullptr;
473 : :
474 [ + + ]: 3453 : if (cached != nullptr) {
475 : 3008 : SpinLockGuard target_lock(target.mtx);
476 : 3008 : last->next = head_of(target);
477 : 3007 : set_head(target, cached);
478 : 3008 : }
479 : :
480 : 3453 : return first;
481 : : }
482 : :
483 : 672 : return nullptr;
484 : : }
485 : :
486 : 76814 : static MemoryFreeNode* try_allocate_from_shards(MemoryTierState& state, size_t shard_index) noexcept {
487 : 76814 : MemoryFreeNode* node = pop_free_node(state.shards[shard_index]);
488 : :
489 [ + + ]: 77574 : if VLIKELY (node != nullptr) {
490 : 71555 : return node;
491 : : }
492 : :
493 [ + + ]: 6019 : if (!state.sharded.load(std::memory_order_relaxed)) {
494 : 2075 : return nullptr;
495 : : }
496 : :
497 : 4112 : return steal_free_nodes(state, shard_index);
498 : : }
499 : :
500 : : // state.grow_mtx must be held. When allocated is non-null, one node is removed from the new chunk.
501 : 1237 : static bool grow_tier_chunk(MemoryTierState& state, size_t shard_index, MemoryFreeNode** allocated) noexcept {
502 : 1237 : size_t blocks = state.next_chunk_blocks;
503 : :
504 [ - + ]: 1237 : if VUNLIKELY (blocks > state.blocks_per_chunk) {
505 : : blocks = state.blocks_per_chunk; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
506 : : }
507 : :
508 [ + + + + ]: 1237 : if (allocated != nullptr && blocks > state.lazy_chunk_blocks) {
509 : 193 : blocks = state.lazy_chunk_blocks;
510 : : }
511 : :
512 : 1237 : const size_t block_size = state.block_size;
513 : 1237 : const size_t chunk_bytes = block_size * blocks;
514 : :
515 [ - + ]: 1237 : if VUNLIKELY (chunk_bytes / block_size != blocks) {
516 : : return false; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
517 : : }
518 : :
519 : 1237 : void* ptr = ::operator new(chunk_bytes, std::align_val_t{MemoryPool::kBlockAlignment}, std::nothrow);
520 : :
521 [ - + ]: 1237 : if VUNLIKELY (ptr == nullptr) {
522 : : return false; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
523 : : }
524 : :
525 : 1237 : auto* base = static_cast<std::byte*>(ptr);
526 : 1237 : auto* local_tail = ::new (base + (blocks - 1U) * block_size) MemoryFreeNode{nullptr};
527 : 1237 : MemoryFreeNode* local_head = local_tail;
528 : :
529 [ + + ]: 773334 : for (size_t i = blocks - 1U; i > 0; --i) {
530 : 772097 : local_head = ::new (base + (i - 1U) * block_size) MemoryFreeNode{local_head};
531 : : }
532 : :
533 : : try {
534 [ + - ]: 1237 : state.chunks.push_back(MemoryChunk{ptr, chunk_bytes});
535 [ - - ]: 0 : } catch (std::exception&) {
536 : : // LCOV_EXCL_START GCOVR_EXCL_START
537 : : ::operator delete(ptr, chunk_bytes, std::align_val_t{MemoryPool::kBlockAlignment});
538 : : return false;
539 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
540 : 0 : }
541 : :
542 : 1237 : state.upstream_alloc_count.fetch_add(1, std::memory_order_relaxed);
543 : 1237 : state.upstream_alloc_bytes.fetch_add(chunk_bytes, std::memory_order_relaxed);
544 : 1237 : state.chunk_count.fetch_add(1, std::memory_order_relaxed);
545 : :
546 : : {
547 : 1237 : MemoryTierShard& shard = state.shards[shard_index];
548 : 1237 : SpinLockGuard lock(shard.mtx);
549 : :
550 : 1237 : local_tail->next = head_of(shard);
551 : :
552 [ + + ]: 1237 : if (allocated != nullptr) {
553 : 1234 : *allocated = local_head;
554 : 1234 : local_head = local_head->next;
555 : 1234 : (*allocated)->next = nullptr;
556 : 1234 : bump_counter(shard.hit_count);
557 : : }
558 : :
559 : 1237 : set_head(shard, local_head);
560 : 1237 : }
561 : :
562 : 1237 : const size_t doubled = blocks * 2U;
563 [ + + ]: 1237 : const size_t target = (doubled < blocks || doubled > state.blocks_per_chunk)
564 [ + - ]: 2474 : ? state.blocks_per_chunk
565 : : : doubled; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
566 : :
567 [ + + ]: 1237 : if (target > state.next_chunk_blocks) {
568 : 809 : state.next_chunk_blocks = target;
569 : : }
570 : :
571 : 1237 : return true;
572 : : }
573 : :
574 : 358565 : static void* tier_allocate(MemoryTierState& state) noexcept {
575 : 358565 : size_t shard_index = 0U;
576 : 358565 : bool sharded = state.sharded.load(std::memory_order_relaxed);
577 : :
578 [ + + ]: 358769 : if (!sharded) {
579 : 284502 : MemoryTierShard& primary = state.shards[0];
580 : :
581 [ + + ]: 284502 : if (primary.mtx.try_lock()) {
582 : 284441 : MemoryFreeNode* node = head_of(primary);
583 : :
584 [ + + ]: 284439 : if VLIKELY (node != nullptr) {
585 : 283400 : set_head(primary, node->next);
586 : 283403 : bump_counter(primary.hit_count);
587 : : }
588 : :
589 : 284444 : primary.mtx.unlock();
590 : :
591 [ + + ]: 284442 : if VLIKELY (node != nullptr) {
592 : 283402 : return node;
593 : : }
594 : : } else {
595 : 61 : const uint32_t contentions = state.contention_count.fetch_add(1U, std::memory_order_relaxed) + 1U;
596 : :
597 [ + + ]: 61 : if (contentions >= kShardingContentionThreshold) {
598 : 6 : state.sharded.store(true, std::memory_order_relaxed);
599 : 6 : sharded = true;
600 : : }
601 : : }
602 : : }
603 : :
604 [ + + ]: 75368 : if (sharded) {
605 : 74188 : shard_index = current_tier_shard(state);
606 : : }
607 : :
608 : 75515 : MemoryFreeNode* node = try_allocate_from_shards(state, shard_index);
609 : :
610 [ + + ]: 76056 : if VLIKELY (node != nullptr) {
611 : 74553 : return node;
612 : : }
613 : :
614 : : {
615 : 1503 : std::lock_guard grow_lock(state.grow_mtx);
616 : :
617 : 1507 : node = try_allocate_from_shards(state, shard_index);
618 : :
619 [ + + ]: 1507 : if VLIKELY (node != nullptr) {
620 : 273 : return node;
621 : : }
622 : :
623 [ + - ]: 1234 : if VLIKELY (grow_tier_chunk(state, shard_index, &node)) {
624 : 1234 : return node;
625 : : }
626 [ - + ]: 1507 : }
627 : :
628 : 0 : std::lock_guard clear_lock(state.clear_mtx);
629 : :
630 : 0 : node = try_allocate_from_shards(state, shard_index);
631 : :
632 [ # # ]: 0 : if (node != nullptr) {
633 : 0 : return node;
634 : : }
635 : :
636 : 0 : std::lock_guard grow_lock(state.grow_mtx);
637 : :
638 [ # # ]: 0 : return grow_tier_chunk(state, shard_index, &node) ? node : nullptr;
639 : 0 : }
640 : :
641 : 358752 : static void tier_deallocate(MemoryTierState& state, void* p) noexcept {
642 [ + + ]: 358752 : if (!state.sharded.load(std::memory_order_relaxed)) {
643 : 282948 : MemoryTierShard& primary = state.shards[0];
644 : :
645 [ + + ]: 282948 : if (primary.mtx.try_lock()) {
646 : 282879 : set_head(primary, ::new (p) MemoryFreeNode{head_of(primary)});
647 : 282881 : bump_counter(primary.deallocate_count);
648 : 282883 : primary.mtx.unlock();
649 : :
650 : 282945 : return;
651 : : }
652 : :
653 : 69 : const uint32_t contentions = state.contention_count.fetch_add(1U, std::memory_order_relaxed) + 1U;
654 : :
655 [ + + ]: 69 : if (contentions < kShardingContentionThreshold) {
656 : 63 : SpinLockGuard lock(primary.mtx);
657 : 63 : set_head(primary, ::new (p) MemoryFreeNode{head_of(primary)});
658 : 63 : bump_counter(primary.deallocate_count);
659 : :
660 : 63 : return;
661 : 63 : }
662 : :
663 : 6 : state.sharded.store(true, std::memory_order_relaxed);
664 : : }
665 : :
666 : 76043 : MemoryTierShard& shard = state.shards[current_tier_shard(state)];
667 : 75991 : SpinLockGuard lock(shard.mtx);
668 : :
669 : 76786 : set_head(shard, ::new (p) MemoryFreeNode{head_of(shard)});
670 : 76813 : bump_counter(shard.deallocate_count);
671 : 77000 : }
672 : :
673 : 3 : static void prealloc_full_quota(MemoryTierState& state) noexcept {
674 : 3 : std::lock_guard grow_lock(state.grow_mtx);
675 : :
676 : 3 : state.next_chunk_blocks = state.blocks_per_chunk;
677 : 3 : const bool ok = grow_tier_chunk(state, 0U, nullptr);
678 : :
679 [ - + ]: 3 : if VUNLIKELY (!ok) {
680 : : state.next_chunk_blocks = state.initial_chunk_blocks; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
681 : : }
682 : :
683 [ - + ]: 3 : if VUNLIKELY (!ok) {
684 : : // LCOV_EXCL_START GCOVR_EXCL_START
685 : : MEMORY_POOL_LOG(
686 : : "MemoryPool: prealloc failed for tier (max_size=%zu, blocks_per_chunk=%zu); "
687 : : "tier reverts to lazy growth.",
688 : : state.max_size, state.blocks_per_chunk);
689 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
690 : : }
691 : 3 : }
692 : :
693 : 275 : static bool validate_tiers_log(const std::vector<MemoryPool::Tier>& tiers) noexcept {
694 : : static constexpr size_t kMaxTierSize = SIZE_MAX - MemoryPool::kBlockAlignment + 1U;
695 : :
696 [ + + ]: 275 : if VUNLIKELY (tiers.size() > kMaxTierCount) {
697 : 1 : MEMORY_POOL_LOG("MemoryPool: tier count %zu exceeds max %zu; falling back to default pyramid.", tiers.size(),
698 : : kMaxTierCount);
699 : :
700 : 1 : return false;
701 : : }
702 : :
703 [ + + ]: 4871 : for (size_t i = 0; i < tiers.size(); ++i) {
704 [ + + ]: 4602 : if VUNLIKELY (tiers[i].max_size == 0) {
705 : 1 : MEMORY_POOL_LOG("MemoryPool: tier %zu has max_size == 0; falling back to default pyramid.", i);
706 : :
707 : 1 : return false;
708 : : }
709 : :
710 [ + + ]: 4601 : if VUNLIKELY (tiers[i].max_size < sizeof(MemoryFreeNode)) {
711 : 1 : MEMORY_POOL_LOG(
712 : : "MemoryPool: tier %zu max_size (%zu) is below the minimum block size %zu; "
713 : : "falling back to default pyramid.",
714 : : i, tiers[i].max_size, sizeof(MemoryFreeNode));
715 : :
716 : 1 : return false;
717 : : }
718 : :
719 [ + + ]: 4600 : if VUNLIKELY (tiers[i].max_size > kMaxTierSize) {
720 : 1 : MEMORY_POOL_LOG("MemoryPool: tier %zu max_size overflows after alignment rounding; falling back.", i);
721 : :
722 : 1 : return false;
723 : : }
724 : :
725 [ + + + + : 4599 : if VUNLIKELY (i > 0 && tiers[i].max_size <= tiers[i - 1].max_size) {
+ + ]
726 : 2 : MEMORY_POOL_LOG("MemoryPool: tier %zu max_size is not strictly increasing; falling back to default pyramid.", i);
727 : :
728 : 2 : return false;
729 : : }
730 : : }
731 : :
732 : 269 : return true;
733 : : }
734 : :
735 : 252 : static MemoryPool::Config create_memory_config(int level, bool prealloc) {
736 [ + - + + : 252 : if VUNLIKELY (level < kMinMemoryLevel || level > kMaxMemoryLevel) {
+ + ]
737 : 1 : MEMORY_POOL_LOG("MemoryPool: level %d out of range [%d, %d], clamped.", level, kMinMemoryLevel, kMaxMemoryLevel);
738 : :
739 [ - + ]: 1 : level = (level < kMinMemoryLevel) ? kMinMemoryLevel : kMaxMemoryLevel;
740 : : }
741 : :
742 : 252 : const auto row_index = static_cast<size_t>(level - kMinMemoryLevel);
743 : 252 : const auto& row = kDefaultTierTable[row_index];
744 : :
745 : 252 : MemoryPool::Config config;
746 : 252 : config.prealloc = prealloc;
747 [ + - ]: 252 : config.tiers.reserve(kMaxTierCount);
748 : :
749 [ + - + + ]: 5040 : for (size_t i = 0; i < kMaxTierCount && row[i].max_size != 0; ++i) {
750 [ + - ]: 4788 : config.tiers.emplace_back(row[i]);
751 : : }
752 : :
753 : 252 : return config;
754 : : } // LCOV_EXCL_LINE GCOVR_EXCL_LINE
755 : :
756 : : struct MemoryPool::Impl final { // NOLINT(clang-analyzer-optin.performance.Padding)
757 : : alignas(64) size_t dispatch_max_sizes[kMaxTierCount]{};
758 : : MemoryTierState* dispatch_states[kMaxTierCount]{};
759 : : size_t dispatch_count{0};
760 : :
761 : : MemoryTierState* tier_states[kMaxTierCount]{};
762 : : size_t tier_count{0};
763 : : std::unique_ptr<MemoryTierShard[]> shards;
764 : : std::vector<std::unique_ptr<MemoryTierState>> owned_states;
765 : :
766 : : std::unique_ptr<MemoryOversizedCounters[]> oversized;
767 : : size_t oversized_count{0};
768 : : };
769 : :
770 [ + - ]: 4 : MemoryPool::MemoryPool() : MemoryPool(Config{}) {}
771 : :
772 [ + - ]: 16 : MemoryPool::MemoryPool(int level, bool prealloc) : MemoryPool(create_memory_config(level, prealloc)) {}
773 : :
774 : 281 : MemoryPool::MemoryPool(const Config& config) : impl_(std::make_unique<Impl>()) {
775 : 281 : const size_t shard_count = default_tier_shard_count();
776 : :
777 [ + - ]: 281 : impl_->oversized = std::make_unique<MemoryOversizedCounters[]>(shard_count);
778 : 281 : impl_->oversized_count = shard_count;
779 : :
780 [ + + ]: 281 : if (config.tiers.empty()) {
781 : 6 : impl_->tier_count = 0;
782 : 6 : return;
783 : : }
784 : :
785 : 275 : std::vector<Tier> fallback;
786 : 275 : const bool use_caller = validate_tiers_log(config.tiers);
787 : :
788 [ + + ]: 275 : if VUNLIKELY (!use_caller) {
789 : 6 : const auto& row = kDefaultTierTable[kDefaultMemoryLevel - kMinMemoryLevel];
790 [ + - ]: 6 : fallback.assign(row, row + kMaxTierCount);
791 : : }
792 : :
793 [ + + ]: 275 : const std::vector<Tier>& source = use_caller ? config.tiers : fallback;
794 [ + + ]: 275 : const size_t batch_size = config.batch_size == 0U ? kDefaultBatchSize : config.batch_size;
795 : :
796 [ + + ]: 275 : if VUNLIKELY (config.batch_size == 0U) {
797 [ + - + - ]: 1 : MEMORY_POOL_LOG("MemoryPool: batch_size is 0; fallback to %zu.", kDefaultBatchSize);
798 : : }
799 : :
800 [ + - ]: 275 : impl_->owned_states.reserve(source.size());
801 : :
802 : 275 : size_t managed = 0;
803 : :
804 [ + + ]: 4990 : for (const auto& cfg : source) {
805 [ + + + + ]: 4715 : if (cfg.max_size != 0U && cfg.blocks_per_chunk != 0U) {
806 : 3944 : ++managed;
807 : : }
808 : : }
809 : :
810 [ + - ]: 275 : impl_->shards = std::make_unique<MemoryTierShard[]>(managed * shard_count);
811 : :
812 : 275 : size_t live = 0;
813 : 275 : size_t dispatch = 0;
814 : :
815 [ + + ]: 4990 : for (const auto& cfg : source) {
816 [ + + ]: 4715 : if VUNLIKELY (cfg.max_size == 0U) {
817 : 771 : continue;
818 : : }
819 : :
820 : 4709 : impl_->dispatch_max_sizes[dispatch] = cfg.max_size;
821 : :
822 [ + + ]: 4709 : if VUNLIKELY (cfg.blocks_per_chunk == 0U) {
823 : 765 : impl_->dispatch_states[dispatch] = nullptr;
824 : 765 : ++dispatch;
825 : 765 : continue;
826 : : }
827 : :
828 [ + - ]: 3944 : auto state = std::make_unique<MemoryTierState>();
829 : 3944 : state->max_size = cfg.max_size;
830 : 3944 : state->blocks_per_chunk = cfg.blocks_per_chunk;
831 : 3944 : state->batch_size = batch_size;
832 : 3944 : state->shards = impl_->shards.get() + live * shard_count;
833 : 3944 : state->shard_count = shard_count;
834 [ + - ]: 3944 : state->chunks.reserve(kInitialChunksReserve);
835 : 3944 : state->block_size = round_up(cfg.max_size, kBlockAlignment);
836 : :
837 [ + - ]: 3944 : size_t initial = (state->block_size > 0U) ? (kInitialChunkBytesTarget / state->block_size) : kInitialBlocksPerChunk;
838 : :
839 [ + + ]: 3944 : if (initial < kInitialBlocksPerChunk) {
840 : 975 : initial = kInitialBlocksPerChunk;
841 : : }
842 : :
843 [ + + ]: 3944 : if (initial > state->blocks_per_chunk) {
844 : 49 : initial = state->blocks_per_chunk;
845 : : }
846 : :
847 : 3944 : state->initial_chunk_blocks = initial;
848 : 3944 : state->next_chunk_blocks = initial;
849 : :
850 [ + + ]: 3963 : const size_t lazy_blocks = config.lazy_scale ? std::max(state->blocks_per_chunk / kLazyChunkQuotaDivisor,
851 : 19 : kMinLazyChunkBytes / state->block_size)
852 : 3925 : : kMaxLazyChunkBytes / state->block_size;
853 : :
854 : 3944 : state->lazy_chunk_blocks = std::clamp(lazy_blocks, size_t{1}, state->blocks_per_chunk);
855 : :
856 : 3944 : impl_->tier_states[live] = state.get();
857 : 3944 : impl_->dispatch_states[dispatch] = state.get();
858 [ + - ]: 3944 : impl_->owned_states.emplace_back(std::move(state));
859 : :
860 : 3944 : ++live;
861 : 3944 : ++dispatch;
862 : 3944 : }
863 : :
864 [ + + ]: 275 : impl_->dispatch_count = (live == 0U) ? 0U : dispatch;
865 : 275 : impl_->tier_count = live;
866 : :
867 [ + + ]: 275 : if (config.prealloc) {
868 [ + + ]: 5 : for (auto& state : impl_->owned_states) {
869 : 3 : prealloc_full_quota(*state);
870 : : }
871 : : }
872 : 275 : }
873 : :
874 : 281 : MemoryPool::~MemoryPool() {
875 : : #ifdef _WIN32
876 : : if (Utils::is_terminating()) {
877 : : (void)impl_.release();
878 : : return;
879 : : }
880 : : #endif
881 : :
882 [ + + ]: 4225 : for (auto& state : impl_->owned_states) {
883 [ + + ]: 4979 : for (const MemoryChunk& chunk : state->chunks) {
884 : 1035 : ::operator delete(chunk.ptr, chunk.bytes, std::align_val_t{kBlockAlignment});
885 : : }
886 : :
887 : 3944 : state->chunks.clear();
888 : :
889 [ + + ]: 35496 : for (size_t index = 0U; index < state->shard_count; ++index) {
890 : 31552 : set_head(state->shards[index], nullptr);
891 : : }
892 : : }
893 : 281 : }
894 : :
895 : 359066 : void* MemoryPool::allocate(size_t bytes, size_t alignment) noexcept {
896 [ + + ]: 359066 : if VUNLIKELY (!is_power_of_two(alignment)) {
897 : 1 : MEMORY_POOL_LOG("MemoryPool::allocate: alignment %zu is not a power of two; returning nullptr.", alignment);
898 : :
899 : 1 : return nullptr;
900 : : }
901 : :
902 : 359260 : const size_t idx = find_tier(bytes);
903 : :
904 [ + # + + : 359028 : if VUNLIKELY (idx == kMaxTierCount || alignment > kBlockAlignment || impl_->dispatch_states[idx] == nullptr) {
+ # + + +
+ ]
905 [ + + ]: 101 : void* p = (alignment > kBlockAlignment) ? ::operator new(bytes, std::align_val_t{alignment}, std::nothrow)
906 : 16 : : ::operator new(bytes, std::nothrow);
907 : :
908 [ - + ]: 101 : if VUNLIKELY (p == nullptr) {
909 : : return nullptr; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
910 : : }
911 : :
912 : 101 : MemoryOversizedCounters& counters = impl_->oversized[current_thread_slot() & (impl_->oversized_count - 1U)];
913 : 101 : counters.alloc_count.fetch_add(1, std::memory_order_relaxed);
914 : 101 : counters.alloc_bytes.fetch_add(bytes, std::memory_order_relaxed);
915 : :
916 : 101 : return p;
917 : : }
918 : :
919 : 358363 : return tier_allocate(*impl_->dispatch_states[idx]);
920 : : }
921 : :
922 : 359204 : void MemoryPool::deallocate(void* p, size_t bytes, size_t alignment) noexcept {
923 [ # + ]: 359204 : if VUNLIKELY (!is_power_of_two(alignment)) {
924 : 0 : MEMORY_POOL_LOG("MemoryPool::deallocate: alignment %zu is not a power of two; leaking %p.", alignment, p);
925 : :
926 : 1 : return;
927 : : }
928 : :
929 [ + + ]: 359463 : if VUNLIKELY (p == nullptr) {
930 : 2 : return;
931 : : }
932 : :
933 : 359461 : const size_t idx = find_tier(bytes);
934 : :
935 [ + # + + : 359286 : if VUNLIKELY (idx == kMaxTierCount || alignment > kBlockAlignment || impl_->dispatch_states[idx] == nullptr) {
+ # + + +
+ ]
936 [ + + ]: 100 : if (alignment > kBlockAlignment) {
937 : 84 : ::operator delete(p, bytes, std::align_val_t{alignment});
938 : : } else {
939 : 16 : ::operator delete(p, bytes);
940 : : }
941 : :
942 : 100 : impl_->oversized[current_thread_slot() & (impl_->oversized_count - 1U)].dealloc_count.fetch_add(
943 : : 1, std::memory_order_relaxed);
944 : :
945 : 100 : return;
946 : : }
947 : :
948 : 358724 : tier_deallocate(*impl_->dispatch_states[idx], p);
949 : : }
950 : :
951 : 17 : size_t MemoryPool::get_tier_count() const noexcept { return impl_->tier_count; }
952 : :
953 : 46 : std::vector<MemoryPool::TierStats> MemoryPool::get_stats() const noexcept {
954 : 46 : const size_t count = impl_->tier_count;
955 : :
956 : 46 : std::vector<TierStats> result;
957 : :
958 : : try {
959 [ + - ]: 46 : result.reserve(count);
960 : : } catch (...) { // LCOV_EXCL_LINE GCOVR_EXCL_LINE
961 : : return {}; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
962 : : } // LCOV_EXCL_LINE GCOVR_EXCL_LINE
963 : :
964 [ + + ]: 348 : for (size_t i = 0; i < count; ++i) {
965 : 302 : const MemoryTierState& state = *impl_->tier_states[i];
966 : 302 : uint64_t hits = 0U;
967 : 302 : uint64_t deallocs = 0U;
968 : :
969 [ + + ]: 2718 : for (size_t index = 0U; index < state.shard_count; ++index) {
970 : 2416 : hits += state.shards[index].hit_count.load(std::memory_order_relaxed);
971 : 4832 : deallocs += state.shards[index].deallocate_count.load(std::memory_order_relaxed);
972 : : }
973 : :
974 : 302 : TierStats item;
975 : 302 : item.max_size = state.max_size;
976 : 302 : item.blocks_per_chunk = state.blocks_per_chunk;
977 : 302 : item.block_size = state.block_size;
978 : 302 : item.hit_count = hits;
979 : 302 : item.deallocate_count = deallocs;
980 [ + - ]: 302 : item.in_use_blocks = (hits >= deallocs) ? (hits - deallocs) : 0U;
981 : 302 : item.upstream_alloc_count = state.upstream_alloc_count.load(std::memory_order_relaxed);
982 : 302 : item.upstream_alloc_bytes = state.upstream_alloc_bytes.load(std::memory_order_relaxed);
983 : 302 : item.chunk_count = state.chunk_count.load(std::memory_order_relaxed);
984 : :
985 : 302 : result.emplace_back(item);
986 : : }
987 : :
988 : 46 : return result;
989 : 46 : }
990 : :
991 : 34 : MemoryPool::OversizedStats MemoryPool::get_oversized_stats() const noexcept {
992 : 34 : OversizedStats result;
993 : :
994 [ + + ]: 306 : for (size_t i = 0; i < impl_->oversized_count; ++i) {
995 : 272 : const MemoryOversizedCounters& counters = impl_->oversized[i];
996 : :
997 : 272 : result.alloc_count += counters.alloc_count.load(std::memory_order_relaxed);
998 : 272 : result.alloc_bytes += counters.alloc_bytes.load(std::memory_order_relaxed);
999 : 544 : result.dealloc_count += counters.dealloc_count.load(std::memory_order_relaxed);
1000 : : }
1001 : :
1002 : 34 : return result;
1003 : : }
1004 : :
1005 : 1 : void MemoryPool::reset_stats() noexcept {
1006 : 1 : const size_t count = impl_->tier_count;
1007 : :
1008 [ + + ]: 2 : for (size_t i = 0; i < count; ++i) {
1009 : 1 : MemoryTierState& state = *impl_->tier_states[i];
1010 : :
1011 [ + + ]: 9 : for (size_t index = 0U; index < state.shard_count; ++index) {
1012 : 8 : MemoryTierShard& shard = state.shards[index];
1013 : 8 : SpinLockGuard lock(shard.mtx);
1014 : :
1015 : 8 : shard.hit_count.store(0, std::memory_order_relaxed);
1016 : 8 : shard.deallocate_count.store(0, std::memory_order_relaxed);
1017 : 8 : }
1018 : : }
1019 : :
1020 [ + + ]: 9 : for (size_t i = 0; i < impl_->oversized_count; ++i) {
1021 : 8 : MemoryOversizedCounters& counters = impl_->oversized[i];
1022 : :
1023 : 8 : counters.alloc_count.store(0, std::memory_order_relaxed);
1024 : 8 : counters.alloc_bytes.store(0, std::memory_order_relaxed);
1025 : 8 : counters.dealloc_count.store(0, std::memory_order_relaxed);
1026 : : }
1027 : 1 : }
1028 : :
1029 : 2688 : static MemoryFreeNode* detach_free_list(MemoryTierShard& shard) noexcept {
1030 : 2688 : SpinLockGuard lock(shard.mtx);
1031 : :
1032 : 2688 : MemoryFreeNode* head = head_of(shard);
1033 : 2688 : set_head(shard, nullptr);
1034 : :
1035 : 5376 : return head;
1036 : 2688 : }
1037 : :
1038 : 2688 : static void attach_free_list(MemoryTierShard& shard, MemoryFreeNode* head, MemoryFreeNode* tail) noexcept {
1039 [ + + ]: 2688 : if (head == nullptr) {
1040 : 2129 : return;
1041 : : }
1042 : :
1043 : 559 : SpinLockGuard lock(shard.mtx);
1044 : :
1045 : 559 : tail->next = head_of(shard);
1046 : 559 : set_head(shard, head);
1047 : 559 : }
1048 : :
1049 : 330 : void MemoryPool::clear() noexcept {
1050 [ + + ]: 692 : for (auto& state : impl_->owned_states) {
1051 : 362 : std::lock_guard clear_lock(state->clear_mtx);
1052 : 362 : std::vector<MemoryChunkTally> tally;
1053 : :
1054 : : try {
1055 [ + - ]: 362 : std::lock_guard grow_lock(state->grow_mtx);
1056 : :
1057 [ + - ]: 362 : std::sort(state->chunks.begin(), state->chunks.end(), [](const MemoryChunk& a, const MemoryChunk& b) noexcept {
1058 : 347 : return reinterpret_cast<std::uintptr_t>(a.ptr) < reinterpret_cast<std::uintptr_t>(b.ptr);
1059 : : });
1060 : :
1061 [ + - ]: 362 : tally.reserve(state->chunks.size());
1062 : :
1063 [ + + ]: 892 : for (const MemoryChunk& chunk : state->chunks) {
1064 [ + - ]: 530 : tally.push_back(MemoryChunkTally{chunk, 0U});
1065 : : }
1066 [ - - ]: 362 : } catch (std::exception&) {
1067 : : continue; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
1068 : 0 : }
1069 : :
1070 [ + + ]: 362 : if (tally.empty()) {
1071 : 26 : continue;
1072 : : }
1073 : :
1074 : 336 : MemoryFreeNode* heads[kMaxTierShardCount] = {};
1075 : :
1076 [ + + ]: 3024 : for (size_t s = 0U; s < state->shard_count; ++s) {
1077 : 2688 : heads[s] = detach_free_list(state->shards[s]);
1078 : : }
1079 : :
1080 : 336 : const size_t block_size = state->block_size;
1081 : :
1082 : 658696 : const auto find_tally = [&tally](const void* p) noexcept -> MemoryChunkTally* {
1083 : 140302 : const auto addr = reinterpret_cast<std::uintptr_t>(p);
1084 : 140302 : size_t lo = 0;
1085 : 140302 : size_t hi = tally.size();
1086 : :
1087 [ + - ]: 189046 : while (lo < hi) {
1088 : 189046 : const size_t mid = lo + (hi - lo) / 2U;
1089 : 189046 : const auto cs = reinterpret_cast<std::uintptr_t>(tally[mid].chunk.ptr);
1090 : 189046 : const auto ce = cs + tally[mid].chunk.bytes;
1091 : :
1092 [ + + ]: 189046 : if (addr < cs) {
1093 : 42676 : hi = mid;
1094 [ + + ]: 146370 : } else if (addr >= ce) {
1095 : 6068 : lo = mid + 1U;
1096 : : } else {
1097 : 140302 : return &tally[mid];
1098 : : }
1099 : : }
1100 : :
1101 : 0 : return nullptr;
1102 : 336 : };
1103 : :
1104 : 142422 : const auto is_free = [block_size](const MemoryChunkTally* t) noexcept {
1105 [ + - + + ]: 71211 : return t != nullptr && t->free_nodes == t->chunk.bytes / block_size;
1106 : 336 : };
1107 : :
1108 [ + + ]: 3024 : for (size_t s = 0U; s < state->shard_count; ++s) {
1109 [ + + ]: 72839 : for (MemoryFreeNode* node = heads[s]; node != nullptr; node = node->next) {
1110 : 70151 : MemoryChunkTally* t = find_tally(node);
1111 : :
1112 [ + - ]: 70151 : if VLIKELY (t != nullptr) {
1113 : 70151 : ++t->free_nodes;
1114 : : }
1115 : : }
1116 : : }
1117 : :
1118 [ + + ]: 3024 : for (size_t s = 0U; s < state->shard_count; ++s) {
1119 : 2688 : MemoryFreeNode* kept_head = nullptr;
1120 : 2688 : MemoryFreeNode* kept_tail = nullptr;
1121 : 2688 : MemoryFreeNode* current = heads[s];
1122 : :
1123 [ + + ]: 72839 : while (current != nullptr) {
1124 : 70151 : MemoryFreeNode* next = current->next;
1125 : :
1126 [ + + ]: 70151 : if (!is_free(find_tally(current))) {
1127 : 44134 : current->next = kept_head;
1128 : 44134 : kept_head = current;
1129 : :
1130 [ + + ]: 44134 : if (kept_tail == nullptr) {
1131 : 559 : kept_tail = current;
1132 : : }
1133 : : }
1134 : :
1135 : 70151 : current = next;
1136 : : }
1137 : :
1138 : 2688 : attach_free_list(state->shards[s], kept_head, kept_tail);
1139 : : }
1140 : :
1141 : 336 : size_t released = 0U;
1142 : :
1143 : : {
1144 : 336 : std::lock_guard grow_lock(state->grow_mtx);
1145 : 336 : std::vector<MemoryChunk>& live = state->chunks;
1146 : 336 : size_t write = 0U;
1147 : :
1148 [ + + ]: 1057 : for (size_t read = 0U; read < live.size(); ++read) {
1149 [ + + + + : 721 : if (read < tally.size() && is_free(&tally[read])) {
+ + ]
1150 : 202 : ++released;
1151 : 202 : continue;
1152 : : }
1153 : :
1154 : 519 : live[write] = live[read];
1155 : 519 : ++write;
1156 : : }
1157 : :
1158 : 336 : live.resize(write);
1159 : 336 : state->chunk_count.fetch_sub(released, std::memory_order_relaxed);
1160 : 336 : }
1161 : :
1162 [ + + ]: 866 : for (const MemoryChunkTally& t : tally) {
1163 [ + + ]: 530 : if (is_free(&t)) {
1164 : 202 : ::operator delete(t.chunk.ptr, t.chunk.bytes, std::align_val_t{kBlockAlignment});
1165 : : }
1166 : : }
1167 [ + + + + ]: 388 : }
1168 : 330 : }
1169 : :
1170 : 2 : void MemoryPool::trim() noexcept { clear(); }
1171 : :
1172 : 236 : MemoryPool::Config MemoryPool::get_default_config() {
1173 : 222 : static int level = []() noexcept {
1174 : 444 : const std::string env_value = Utils::get_env("VLINK_MEMORY_LEVEL", "3");
1175 : :
1176 : 222 : int parsed = kDefaultMemoryLevel;
1177 : :
1178 : 222 : const char* first = env_value.data();
1179 : 222 : const char* last = first + env_value.size();
1180 : :
1181 : 222 : auto [ptr, ec] = std::from_chars(first, last, parsed);
1182 : :
1183 [ + + - + : 222 : if VUNLIKELY (ec != std::errc() || ptr != last) {
+ + ]
1184 : : // LCOV_EXCL_START GCOVR_EXCL_START
1185 : : MEMORY_POOL_LOG("MemoryPool: VLINK_MEMORY_LEVEL=\"%s\" is not a valid integer, fallback to %d.",
1186 : : env_value.c_str(), kDefaultMemoryLevel);
1187 : :
1188 : : return kDefaultMemoryLevel;
1189 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
1190 : : }
1191 : :
1192 [ + - - + : 203 : if VUNLIKELY (parsed < kMinMemoryLevel || parsed > kMaxMemoryLevel) {
- + ]
1193 : : // LCOV_EXCL_START GCOVR_EXCL_START
1194 : : MEMORY_POOL_LOG("MemoryPool: VLINK_MEMORY_LEVEL=%d out of range [%d, %d], clamped.", parsed, kMinMemoryLevel,
1195 : : kMaxMemoryLevel);
1196 : :
1197 : : return parsed < kMinMemoryLevel ? kMinMemoryLevel : kMaxMemoryLevel;
1198 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
1199 : : }
1200 : :
1201 : 203 : return parsed;
1202 [ + + + - ]: 458 : }();
1203 : :
1204 [ + + + - : 236 : static bool prealloc_env = (Utils::get_env("VLINK_MEMORY_PREALLOC") == "1");
+ - + - -
- ]
1205 [ + + + - : 236 : static bool lazy_scale_env = (Utils::get_env("VLINK_MEMORY_LAZY_SCALE") == "1");
+ - + - -
- ]
1206 : :
1207 : 222 : static size_t batch_size = []() noexcept {
1208 : 444 : const std::string env_value = Utils::get_env("VLINK_MEMORY_BATCH_SIZE", "16");
1209 : 222 : size_t parsed = kDefaultBatchSize;
1210 : :
1211 : 222 : const char* first = env_value.data();
1212 : 222 : const char* last = first + env_value.size();
1213 : 222 : auto [ptr, ec] = std::from_chars(first, last, parsed);
1214 : :
1215 [ + + - + : 222 : if VUNLIKELY (ec != std::errc() || ptr != last || parsed == 0U) {
+ + + + +
+ ]
1216 : : // LCOV_EXCL_START GCOVR_EXCL_START
1217 : : MEMORY_POOL_LOG("MemoryPool: VLINK_MEMORY_BATCH_SIZE=\"%s\" is not a positive integer, fallback to %zu.",
1218 : : env_value.c_str(), kDefaultBatchSize);
1219 : :
1220 : : return kDefaultBatchSize;
1221 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
1222 : : }
1223 : :
1224 : 201 : return parsed;
1225 [ + + + - ]: 458 : }();
1226 : :
1227 : 236 : Config config = create_memory_config(level, prealloc_env);
1228 : 236 : config.batch_size = batch_size;
1229 : 236 : config.lazy_scale = lazy_scale_env;
1230 : :
1231 : 236 : return config;
1232 : : }
1233 : :
1234 : 102529 : MemoryPool& MemoryPool::global_instance(bool use_env_level) {
1235 : : #if MEMORY_POOL_NEVER_DELETE
1236 : : alignas(MemoryPool) static char buf[sizeof(MemoryPool)];
1237 : :
1238 : : static auto* instance =
1239 : : new (buf) MemoryPool(use_env_level ? get_default_config() : create_memory_config(kDefaultMemoryLevel, false));
1240 : :
1241 : : return *instance;
1242 : : #else
1243 [ + + + - : 102529 : static MemoryPool instance(use_env_level ? get_default_config() : create_memory_config(kDefaultMemoryLevel, false));
+ - + - -
- + - -
- ]
1244 : :
1245 : 102530 : return instance;
1246 : : #endif
1247 : : }
1248 : :
1249 : 716150 : size_t MemoryPool::find_tier(size_t bytes) const noexcept {
1250 : 716150 : const size_t count = impl_->dispatch_count;
1251 : 716015 : const size_t* const sizes = impl_->dispatch_max_sizes;
1252 : :
1253 [ + + ]: 1594005 : for (size_t i = 0; i < count; ++i) {
1254 [ + + ]: 1593989 : if (bytes <= sizes[i]) {
1255 : 715988 : return i;
1256 : : }
1257 : : }
1258 : :
1259 : 16 : return kMaxTierCount;
1260 : : }
1261 : :
1262 : : } // namespace vlink
|
