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 <exception>
32 : : #include <new>
33 : : #include <string>
34 : : #include <system_error>
35 : : #include <thread>
36 : : #include <utility>
37 : : #include <vector>
38 : :
39 : : #include "./base/logger.h"
40 : : #include "./base/spin_lock.h"
41 : : #include "./base/utils.h"
42 : :
43 : : #define MEMORY_POOL_NERVER_DELETE 0
44 : :
45 : : namespace vlink {
46 : :
47 : : static constexpr int kMinMemoryLevel = 0;
48 : : static constexpr int kMaxMemoryLevel = 9;
49 : : static constexpr int kDefaultMemoryLevel = 3;
50 : : static constexpr size_t kMaxTierCount = 20U;
51 : : static constexpr size_t kMaxLevelCount = 10U;
52 : : static constexpr size_t kInitialBlocksPerChunk = 1U;
53 : : static constexpr size_t kInitialChunksReserve = 16U;
54 : : static constexpr size_t kInitialChunkBytesTarget = 64U * 1024U;
55 : :
56 : : // clang-format off
57 : : static constexpr MemoryPool::Tier kDefaultTierTable[kMaxLevelCount][kMaxTierCount] = {
58 : : // L0 ~ 0 MiB. (bypass; all entries are sentinels)
59 : : {
60 : : {32U, 0U},
61 : : {64U, 0U},
62 : : {128U, 0U},
63 : : {256U, 0U},
64 : : {512U, 0U},
65 : : {1U * 1024U, 0U},
66 : : {2U * 1024U, 0U},
67 : : {4U * 1024U, 0U},
68 : : {8U * 1024U, 0U},
69 : : {16U * 1024U, 0U},
70 : : {32U * 1024U, 0U},
71 : : {64U * 1024U, 0U},
72 : : {128U * 1024U, 0U},
73 : : {256U * 1024U, 0U},
74 : : {512U * 1024U, 0U},
75 : : {1U * 1024U * 1024U, 0U},
76 : : {4U * 1024U * 1024U, 0U},
77 : : {8U * 1024U * 1024U, 0U},
78 : : {16U * 1024U * 1024U, 0U},
79 : : },
80 : : // L1 ~ 4 MiB.
81 : : {
82 : : {32U, 8U * 1024U},
83 : : {64U, 4U * 1024U},
84 : : {128U, 2U * 1024U},
85 : : {256U, 1U * 1024U},
86 : : {512U, 512U},
87 : : {1U * 1024U, 256U},
88 : : {2U * 1024U, 128U},
89 : : {4U * 1024U, 64U},
90 : : {8U * 1024U, 32U},
91 : : {16U * 1024U, 16U},
92 : : {32U * 1024U, 8U},
93 : : {64U * 1024U, 4U},
94 : : {128U * 1024U, 2U},
95 : : {256U * 1024U, 1U},
96 : : {512U * 1024U, 1U},
97 : : {1U * 1024U * 1024U, 0U},
98 : : {4U * 1024U * 1024U, 0U},
99 : : {8U * 1024U * 1024U, 0U},
100 : : {16U * 1024U * 1024U, 0U},
101 : : },
102 : : // L2 ~ 8.5 MiB.
103 : : {
104 : : {32U, 16U * 1024U},
105 : : {64U, 8U * 1024U},
106 : : {128U, 4U * 1024U},
107 : : {256U, 2U * 1024U},
108 : : {512U, 1U * 1024U},
109 : : {1U * 1024U, 512U},
110 : : {2U * 1024U, 256U},
111 : : {4U * 1024U, 128U},
112 : : {8U * 1024U, 64U},
113 : : {16U * 1024U, 32U},
114 : : {32U * 1024U, 16U},
115 : : {64U * 1024U, 8U},
116 : : {128U * 1024U, 4U},
117 : : {256U * 1024U, 2U},
118 : : {512U * 1024U, 1U},
119 : : {1U * 1024U * 1024U, 1U},
120 : : {4U * 1024U * 1024U, 0U},
121 : : {8U * 1024U * 1024U, 0U},
122 : : {16U * 1024U * 1024U, 0U},
123 : : },
124 : : // L3 ~ 16 MiB. (Default)
125 : : {
126 : : {32U, 32U * 1024U},
127 : : {64U, 16U * 1024U},
128 : : {128U, 8U * 1024U},
129 : : {256U, 4U * 1024U},
130 : : {512U, 2U * 1024U},
131 : : {1U * 1024U, 1U * 1024U},
132 : : {2U * 1024U, 512U},
133 : : {4U * 1024U, 256U},
134 : : {8U * 1024U, 128U},
135 : : {16U * 1024U, 64U},
136 : : {32U * 1024U, 32U},
137 : : {64U * 1024U, 16U},
138 : : {128U * 1024U, 8U},
139 : : {256U * 1024U, 4U},
140 : : {512U * 1024U, 2U},
141 : : {1U * 1024U * 1024U, 1U},
142 : : {4U * 1024U * 1024U, 0U},
143 : : {8U * 1024U * 1024U, 0U},
144 : : {16U * 1024U * 1024U, 0U},
145 : : },
146 : : // L4 ~ 42 MiB.
147 : : {
148 : : {32U, 64U * 1024U},
149 : : {64U, 32U * 1024U},
150 : : {128U, 16U * 1024U},
151 : : {256U, 8U * 1024U},
152 : : {512U, 4U * 1024U},
153 : : {1U * 1024U, 2U * 1024U},
154 : : {2U * 1024U, 1U * 1024U},
155 : : {4U * 1024U, 512U},
156 : : {8U * 1024U, 256U},
157 : : {16U * 1024U, 128U},
158 : : {32U * 1024U, 64U},
159 : : {64U * 1024U, 32U},
160 : : {128U * 1024U, 16U},
161 : : {256U * 1024U, 8U},
162 : : {512U * 1024U, 4U},
163 : : {1U * 1024U * 1024U, 4U},
164 : : {4U * 1024U * 1024U, 2U},
165 : : {8U * 1024U * 1024U, 0U},
166 : : {16U * 1024U * 1024U, 0U},
167 : : },
168 : : // L5 ~ 92 MiB.
169 : : {
170 : : {32U, 128U * 1024U},
171 : : {64U, 64U * 1024U},
172 : : {128U, 32U * 1024U},
173 : : {256U, 16U * 1024U},
174 : : {512U, 8U * 1024U},
175 : : {1U * 1024U, 4U * 1024U},
176 : : {2U * 1024U, 2U * 1024U},
177 : : {4U * 1024U, 1U * 1024U},
178 : : {8U * 1024U, 512U},
179 : : {16U * 1024U, 256U},
180 : : {32U * 1024U, 128U},
181 : : {64U * 1024U, 64U},
182 : : {128U * 1024U, 32U},
183 : : {256U * 1024U, 16U},
184 : : {512U * 1024U, 8U},
185 : : {1U * 1024U * 1024U, 8U},
186 : : {4U * 1024U * 1024U, 4U},
187 : : {8U * 1024U * 1024U, 1U},
188 : : {16U * 1024U * 1024U, 0U},
189 : : },
190 : : // L6 ~ 200 MiB.
191 : : {
192 : : {32U, 256U * 1024U},
193 : : {64U, 128U * 1024U},
194 : : {128U, 64U * 1024U},
195 : : {256U, 32U * 1024U},
196 : : {512U, 16U * 1024U},
197 : : {1U * 1024U, 8U * 1024U},
198 : : {2U * 1024U, 4U * 1024U},
199 : : {4U * 1024U, 2U * 1024U},
200 : : {8U * 1024U, 1U * 1024U},
201 : : {16U * 1024U, 512U},
202 : : {32U * 1024U, 256U},
203 : : {64U * 1024U, 128U},
204 : : {128U * 1024U, 64U},
205 : : {256U * 1024U, 32U},
206 : : {512U * 1024U, 16U},
207 : : {1U * 1024U * 1024U, 16U},
208 : : {4U * 1024U * 1024U, 8U},
209 : : {8U * 1024U * 1024U, 2U},
210 : : {16U * 1024U * 1024U, 1U},
211 : : },
212 : : // L7 ~ 264 MiB.
213 : : {
214 : : {32U, 256U * 1024U},
215 : : {64U, 128U * 1024U},
216 : : {128U, 64U * 1024U},
217 : : {256U, 32U * 1024U},
218 : : {512U, 16U * 1024U},
219 : : {1U * 1024U, 8U * 1024U},
220 : : {2U * 1024U, 4U * 1024U},
221 : : {4U * 1024U, 2U * 1024U},
222 : : {8U * 1024U, 1U * 1024U},
223 : : {16U * 1024U, 512U},
224 : : {32U * 1024U, 256U},
225 : : {64U * 1024U, 128U},
226 : : {128U * 1024U, 64U},
227 : : {256U * 1024U, 32U},
228 : : {512U * 1024U, 16U},
229 : : {1U * 1024U * 1024U, 16U},
230 : : {4U * 1024U * 1024U, 16U},
231 : : {8U * 1024U * 1024U, 4U},
232 : : {16U * 1024U * 1024U, 2U},
233 : : },
234 : : // L8 ~ 528 MiB.
235 : : {
236 : : {32U, 512U * 1024U},
237 : : {64U, 256U * 1024U},
238 : : {128U, 128U * 1024U},
239 : : {256U, 64U * 1024U},
240 : : {512U, 32U * 1024U},
241 : : {1U * 1024U, 16U * 1024U},
242 : : {2U * 1024U, 8U * 1024U},
243 : : {4U * 1024U, 4U * 1024U},
244 : : {8U * 1024U, 2U * 1024U},
245 : : {16U * 1024U, 1U * 1024U},
246 : : {32U * 1024U, 512U},
247 : : {64U * 1024U, 256U},
248 : : {128U * 1024U, 128U},
249 : : {256U * 1024U, 64U},
250 : : {512U * 1024U, 32U},
251 : : {1U * 1024U * 1024U, 32U},
252 : : {4U * 1024U * 1024U, 32U},
253 : : {8U * 1024U * 1024U, 8U},
254 : : {16U * 1024U * 1024U, 4U},
255 : : },
256 : : // L9 ~ 656 MiB.
257 : : {
258 : : {32U, 512U * 1024U},
259 : : {64U, 256U * 1024U},
260 : : {128U, 128U * 1024U},
261 : : {256U, 64U * 1024U},
262 : : {512U, 32U * 1024U},
263 : : {1U * 1024U, 16U * 1024U},
264 : : {2U * 1024U, 8U * 1024U},
265 : : {4U * 1024U, 4U * 1024U},
266 : : {8U * 1024U, 2U * 1024U},
267 : : {16U * 1024U, 1U * 1024U},
268 : : {32U * 1024U, 512U},
269 : : {64U * 1024U, 256U},
270 : : {128U * 1024U, 128U},
271 : : {256U * 1024U, 64U},
272 : : {512U * 1024U, 32U},
273 : : {1U * 1024U * 1024U, 32U},
274 : : {4U * 1024U * 1024U, 32U},
275 : : {8U * 1024U * 1024U, 16U},
276 : : {16U * 1024U * 1024U, 8U},
277 : : }
278 : : };
279 : : // clang-format on
280 : :
281 : : struct MemoryFreeNode final {
282 : : MemoryFreeNode* next{nullptr};
283 : : };
284 : :
285 : : struct MemoryChunk final {
286 : : void* ptr{nullptr};
287 : : size_t bytes{0};
288 : : };
289 : :
290 : : // NOLINTNEXTLINE(clang-analyzer-optin.performance.Padding)
291 : : struct alignas(64) MemoryTierState final {
292 : : size_t max_size{0};
293 : : size_t block_size{0};
294 : : size_t blocks_per_chunk{0};
295 : : size_t next_chunk_blocks{0};
296 : : size_t initial_chunk_blocks{0};
297 : :
298 : : MemoryFreeNode* free_list_head{nullptr};
299 : : std::vector<MemoryChunk> chunks;
300 : :
301 : : alignas(64) std::atomic<bool> growing{false};
302 : : alignas(64) SpinLock mtx;
303 : : alignas(64) std::atomic<uint64_t> hit_count{0};
304 : : alignas(64) std::atomic<uint64_t> deallocate_count{0};
305 : :
306 : : alignas(64) std::atomic<uint64_t> chunk_count{0};
307 : : alignas(64) std::atomic<uint64_t> upstream_alloc_count{0};
308 : : std::atomic<uint64_t> upstream_alloc_bytes{0};
309 : : };
310 : :
311 : : struct alignas(64) MemoryAllocCounters final {
312 : : std::atomic<uint64_t> count{0};
313 : : std::atomic<uint64_t> bytes{0};
314 : : };
315 : :
316 [ + # + # ]: 60264 : static constexpr bool is_power_of_two(size_t x) noexcept { return x != 0 && ((x & (x - 1U)) == 0U); }
317 : :
318 : 3280 : static constexpr size_t round_up(size_t value, size_t alignment) noexcept {
319 : 3280 : return (value + alignment - 1U) & ~(alignment - 1U);
320 : : }
321 : :
322 : : static constexpr bool default_tier_table_well_formed() noexcept {
323 : : // NOLINTNEXTLINE(modernize-loop-convert)
324 : : for (size_t level = 0; level < kMaxLevelCount; ++level) {
325 : : size_t prev_max_size = 0U;
326 : :
327 : : for (size_t t = 0; t < kMaxTierCount; ++t) {
328 : : const size_t max_size = kDefaultTierTable[level][t].max_size;
329 : :
330 : : if (max_size == 0U) {
331 : : break;
332 : : }
333 : :
334 : : if (max_size < sizeof(MemoryFreeNode)) {
335 : : return false;
336 : : }
337 : :
338 : : if (t > 0U && max_size <= prev_max_size) {
339 : : return false;
340 : : }
341 : :
342 : : prev_max_size = max_size;
343 : : }
344 : : }
345 : :
346 : : return true;
347 : : }
348 : :
349 : : static_assert(default_tier_table_well_formed(),
350 : : "MemoryPool: kDefaultTierTable contains a malformed row "
351 : : "(undersized tier or non-monotonic max_size)");
352 : :
353 : 425 : static bool grow_tier_chunk(MemoryTierState& state) noexcept {
354 : 425 : size_t blocks = state.next_chunk_blocks;
355 : :
356 [ - + ]: 425 : if VUNLIKELY (blocks > state.blocks_per_chunk) {
357 : : blocks = state.blocks_per_chunk; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
358 : : }
359 : :
360 : 425 : const size_t block_size = state.block_size;
361 : 425 : const size_t chunk_bytes = block_size * blocks;
362 : :
363 [ - + ]: 425 : if VUNLIKELY (chunk_bytes / block_size != blocks) {
364 : : return false; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
365 : : }
366 : :
367 : 425 : state.mtx.unlock();
368 : :
369 : 425 : void* ptr = ::operator new(chunk_bytes, std::align_val_t{MemoryPool::kBlockAlignment}, std::nothrow);
370 : :
371 [ - + ]: 425 : if VUNLIKELY (ptr == nullptr) {
372 : : state.mtx.lock(); // LCOV_EXCL_LINE GCOVR_EXCL_LINE
373 : : return false; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
374 : : }
375 : :
376 : 425 : auto* base = static_cast<std::byte*>(ptr);
377 : 425 : auto* local_tail = ::new (base + (blocks - 1U) * block_size) MemoryFreeNode{nullptr};
378 : 425 : MemoryFreeNode* local_head = local_tail;
379 : :
380 [ + + ]: 249248 : for (size_t i = blocks - 1U; i > 0; --i) {
381 : 248825 : local_head = ::new (base + (i - 1U) * block_size) MemoryFreeNode{local_head};
382 : : }
383 : :
384 : 423 : state.mtx.lock();
385 : :
386 : : try {
387 [ + - ]: 425 : state.chunks.push_back(MemoryChunk{ptr, chunk_bytes});
388 [ - - ]: 0 : } catch (std::exception&) {
389 : : // LCOV_EXCL_START GCOVR_EXCL_START
390 : : state.mtx.unlock();
391 : : ::operator delete(ptr, chunk_bytes, std::align_val_t{MemoryPool::kBlockAlignment});
392 : : state.mtx.lock();
393 : :
394 : : return false;
395 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
396 : 0 : }
397 : :
398 : 425 : state.upstream_alloc_count.fetch_add(1, std::memory_order_relaxed);
399 : 425 : state.upstream_alloc_bytes.fetch_add(chunk_bytes, std::memory_order_relaxed);
400 : 425 : state.chunk_count.fetch_add(1, std::memory_order_relaxed);
401 : :
402 : 425 : local_tail->next = state.free_list_head;
403 : 425 : state.free_list_head = local_head;
404 : :
405 : 425 : const size_t doubled = blocks * 2U;
406 [ + + ]: 425 : const size_t target = (doubled < blocks || doubled > state.blocks_per_chunk)
407 [ + - ]: 850 : ? state.blocks_per_chunk
408 : : : doubled; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
409 : :
410 [ + + ]: 425 : if (target > state.next_chunk_blocks) {
411 : 378 : state.next_chunk_blocks = target;
412 : : }
413 : :
414 : 425 : return true;
415 : : }
416 : :
417 : 30317 : static void* tier_allocate(MemoryTierState& state) noexcept {
418 : : for (;;) {
419 : : {
420 : 30317 : uint16_t grow_spins = 0;
421 : :
422 [ + + ]: 32849 : while (state.growing.load(std::memory_order_acquire)) {
423 [ + + ]: 2520 : if (grow_spins < 128) {
424 : 2375 : Utils::yield_cpu();
425 : 2387 : ++grow_spins;
426 : : } else {
427 : 145 : std::this_thread::yield();
428 : : }
429 : : }
430 : : }
431 : :
432 : 30460 : state.mtx.lock();
433 : :
434 [ + + ]: 31177 : if VLIKELY (state.free_list_head != nullptr) {
435 : 30606 : MemoryFreeNode* node = state.free_list_head;
436 : 30606 : state.free_list_head = node->next;
437 : 30606 : state.mtx.unlock();
438 : :
439 : 30762 : return node;
440 : : }
441 : :
442 [ - + ]: 571 : if (state.growing.load(std::memory_order_relaxed)) {
443 : 0 : state.mtx.unlock();
444 : 5 : continue;
445 : : }
446 : :
447 : 422 : state.growing.store(true, std::memory_order_release);
448 : 422 : const bool ok = grow_tier_chunk(state);
449 : 422 : state.growing.store(false, std::memory_order_release);
450 : :
451 [ - + ]: 422 : if VUNLIKELY (!ok) {
452 : : // LCOV_EXCL_START GCOVR_EXCL_START
453 : : if (state.free_list_head != nullptr) {
454 : : MemoryFreeNode* node = state.free_list_head;
455 : : state.free_list_head = node->next;
456 : : state.mtx.unlock();
457 : :
458 : : return node;
459 : : }
460 : :
461 : : state.mtx.unlock();
462 : : return nullptr;
463 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
464 : : }
465 : :
466 : 422 : MemoryFreeNode* node = state.free_list_head;
467 : 422 : state.free_list_head = node->next;
468 : 422 : state.mtx.unlock();
469 : :
470 : 422 : return node;
471 : 5 : }
472 : : }
473 : :
474 : 30284 : static void tier_deallocate(MemoryTierState& state, void* p) noexcept {
475 : 30284 : SpinLockGuard lock(state.mtx);
476 : :
477 : 31133 : auto* node = ::new (p) MemoryFreeNode{state.free_list_head};
478 : :
479 : 31149 : state.free_list_head = node;
480 : 31149 : }
481 : :
482 : 3 : static void prealloc_full_quota(MemoryTierState& state) noexcept {
483 : 3 : state.mtx.lock();
484 : :
485 : 3 : state.growing.store(true, std::memory_order_release);
486 : 3 : state.next_chunk_blocks = state.blocks_per_chunk;
487 : 3 : const bool ok = grow_tier_chunk(state);
488 : :
489 [ - + ]: 3 : if VUNLIKELY (!ok) {
490 : : state.next_chunk_blocks = state.initial_chunk_blocks; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
491 : : }
492 : :
493 : 3 : state.growing.store(false, std::memory_order_release);
494 : :
495 : 3 : state.mtx.unlock();
496 : :
497 [ - + ]: 3 : if VUNLIKELY (!ok) {
498 : 0 : CLOG_W("MemoryPool: prealloc failed for tier (max_size=%zu, blocks_per_chunk=%zu); tier reverts to lazy growth.",
499 : : state.max_size, state.blocks_per_chunk);
500 : : }
501 : 3 : }
502 : :
503 : 228 : static bool validate_tiers_log(const std::vector<MemoryPool::Tier>& tiers) noexcept {
504 : : static constexpr size_t kMaxTierSize = SIZE_MAX - MemoryPool::kBlockAlignment + 1U;
505 : :
506 [ + + ]: 228 : if VUNLIKELY (tiers.size() > kMaxTierCount) {
507 : 2 : CLOG_E("MemoryPool: tier count %zu exceeds max %zu; falling back to default pyramid.", tiers.size(), kMaxTierCount);
508 : 1 : return false;
509 : : }
510 : :
511 [ + + ]: 4037 : for (size_t i = 0; i < tiers.size(); ++i) {
512 [ + + ]: 3815 : if VUNLIKELY (tiers[i].max_size == 0) {
513 : 2 : CLOG_E("MemoryPool: tier %zu has max_size == 0; falling back to default pyramid.", i);
514 : 5 : return false;
515 : : }
516 : :
517 [ + + ]: 3814 : if VUNLIKELY (tiers[i].max_size < sizeof(MemoryFreeNode)) {
518 : 2 : CLOG_E(
519 : : "MemoryPool: tier %zu max_size (%zu) is below the minimum block size %zu; "
520 : : "falling back to default pyramid.",
521 : : i, tiers[i].max_size, sizeof(MemoryFreeNode));
522 : 1 : return false;
523 : : }
524 : :
525 [ + + ]: 3813 : if VUNLIKELY (tiers[i].max_size > kMaxTierSize) {
526 : 2 : CLOG_E("MemoryPool: tier %zu max_size overflows after alignment rounding; falling back.", i);
527 : 1 : return false;
528 : : }
529 : :
530 [ + + + + : 3812 : if VUNLIKELY (i > 0 && tiers[i].max_size <= tiers[i - 1].max_size) {
+ + ]
531 : 4 : CLOG_E("MemoryPool: tier %zu max_size is not strictly increasing; falling back to default pyramid.", i);
532 : 2 : return false;
533 : : }
534 : : }
535 : :
536 : 222 : return true;
537 : : }
538 : :
539 : 199 : static MemoryPool::Config create_memory_config(int level, bool prealloc) {
540 [ + - + + : 199 : if VUNLIKELY (level < kMinMemoryLevel || level > kMaxMemoryLevel) {
+ + ]
541 [ + - + - ]: 2 : CLOG_W("MemoryPool: level %d out of range [%d, %d], clamped.", level, kMinMemoryLevel, kMaxMemoryLevel);
542 [ - + ]: 1 : level = (level < kMinMemoryLevel) ? kMinMemoryLevel : kMaxMemoryLevel;
543 : : }
544 : :
545 : 199 : const auto row_index = static_cast<size_t>(level - kMinMemoryLevel);
546 : 199 : const auto& row = kDefaultTierTable[row_index];
547 : :
548 : 199 : MemoryPool::Config config;
549 : 199 : config.prealloc = prealloc;
550 [ + - ]: 199 : config.tiers.reserve(kMaxTierCount);
551 : :
552 [ + - + + ]: 3980 : for (size_t i = 0; i < kMaxTierCount && row[i].max_size != 0; ++i) {
553 [ + - ]: 3781 : config.tiers.emplace_back(row[i]);
554 : : }
555 : :
556 : 199 : return config;
557 : : } // LCOV_EXCL_LINE GCOVR_EXCL_LINE
558 : :
559 : : struct MemoryPool::Impl final { // NOLINT(clang-analyzer-optin.performance.Padding)
560 : : alignas(64) size_t dispatch_max_sizes[kMaxTierCount]{};
561 : : MemoryTierState* dispatch_states[kMaxTierCount]{};
562 : : size_t dispatch_count{0};
563 : :
564 : : alignas(64) size_t tier_max_sizes[kMaxTierCount]{};
565 : :
566 : : MemoryTierState* tier_states[kMaxTierCount]{};
567 : : size_t tier_count{0};
568 : : std::vector<std::unique_ptr<MemoryTierState>> owned_states;
569 : : MemoryAllocCounters oversized_alloc;
570 : :
571 : : alignas(64) std::atomic<uint64_t> oversized_dealloc_count{0};
572 : : };
573 : :
574 [ + - ]: 4 : MemoryPool::MemoryPool() : MemoryPool(Config{}) {}
575 : :
576 [ + - ]: 16 : MemoryPool::MemoryPool(int level, bool prealloc) : MemoryPool(create_memory_config(level, prealloc)) {}
577 : :
578 : 234 : MemoryPool::MemoryPool(const Config& config) : impl_(std::make_unique<Impl>()) {
579 [ + + ]: 234 : if (config.tiers.empty()) {
580 : 6 : impl_->tier_count = 0;
581 : 6 : return;
582 : : }
583 : :
584 : 228 : std::vector<Tier> fallback;
585 : 228 : const bool use_caller = validate_tiers_log(config.tiers);
586 : :
587 [ + + ]: 228 : if VUNLIKELY (!use_caller) {
588 : 6 : const auto& row = kDefaultTierTable[kDefaultMemoryLevel - kMinMemoryLevel];
589 [ + - ]: 6 : fallback.assign(row, row + kMaxTierCount);
590 : : }
591 : :
592 [ + + ]: 228 : const std::vector<Tier>& source = use_caller ? config.tiers : fallback;
593 : :
594 [ + - ]: 228 : impl_->owned_states.reserve(source.size());
595 : :
596 : 228 : size_t live = 0;
597 : 228 : size_t dispatch = 0;
598 : :
599 [ + + ]: 4156 : for (const auto& cfg : source) {
600 [ + + ]: 3928 : if VUNLIKELY (cfg.max_size == 0U) {
601 : 648 : continue;
602 : : }
603 : :
604 : 3922 : impl_->dispatch_max_sizes[dispatch] = cfg.max_size;
605 : :
606 [ + + ]: 3922 : if VUNLIKELY (cfg.blocks_per_chunk == 0U) {
607 : 642 : impl_->dispatch_states[dispatch] = nullptr;
608 : 642 : ++dispatch;
609 : 642 : continue;
610 : : }
611 : :
612 [ + - ]: 3280 : auto state = std::make_unique<MemoryTierState>();
613 : 3280 : state->max_size = cfg.max_size;
614 : 3280 : state->blocks_per_chunk = cfg.blocks_per_chunk;
615 [ + - ]: 3280 : state->chunks.reserve(kInitialChunksReserve);
616 : 3280 : state->block_size = round_up(cfg.max_size, kBlockAlignment);
617 : :
618 [ + - ]: 3280 : size_t initial = (state->block_size > 0U) ? (kInitialChunkBytesTarget / state->block_size) : kInitialBlocksPerChunk;
619 : :
620 [ + + ]: 3280 : if (initial < kInitialBlocksPerChunk) {
621 : 811 : initial = kInitialBlocksPerChunk;
622 : : }
623 : :
624 [ + + ]: 3280 : if (initial > state->blocks_per_chunk) {
625 : 45 : initial = state->blocks_per_chunk;
626 : : }
627 : :
628 : 3280 : state->initial_chunk_blocks = initial;
629 : 3280 : state->next_chunk_blocks = initial;
630 : :
631 : 3280 : impl_->tier_max_sizes[live] = cfg.max_size;
632 : 3280 : impl_->tier_states[live] = state.get();
633 : 3280 : impl_->dispatch_states[dispatch] = state.get();
634 [ + - ]: 3280 : impl_->owned_states.emplace_back(std::move(state));
635 : :
636 : 3280 : ++live;
637 : 3280 : ++dispatch;
638 : 3280 : }
639 : :
640 : 228 : impl_->dispatch_count = dispatch;
641 : 228 : impl_->tier_count = live;
642 : :
643 [ + + ]: 228 : if (config.prealloc) {
644 [ + + ]: 5 : for (auto& state : impl_->owned_states) {
645 : 3 : prealloc_full_quota(*state);
646 : : }
647 : : }
648 : 228 : }
649 : :
650 : 234 : MemoryPool::~MemoryPool() {
651 [ + + ]: 3514 : for (auto& state : impl_->owned_states) {
652 : : // SpinLockGuard lock(state->mtx);
653 : :
654 [ + + ]: 3695 : for (const MemoryChunk& chunk : state->chunks) {
655 : 415 : ::operator delete(chunk.ptr, chunk.bytes, std::align_val_t{kBlockAlignment});
656 : : }
657 : :
658 : 3280 : state->chunks.clear();
659 : 3280 : state->free_list_head = nullptr;
660 : : }
661 : 234 : }
662 : :
663 : 30456 : void* MemoryPool::allocate(size_t bytes, size_t alignment) noexcept {
664 [ + + ]: 30456 : if VUNLIKELY (!is_power_of_two(alignment)) {
665 : 2 : CLOG_E("MemoryPool::allocate: alignment %zu is not a power of two; returning nullptr.", alignment);
666 : 1 : return nullptr;
667 : : }
668 : :
669 : 30424 : const size_t idx = find_tier(bytes);
670 : :
671 [ + # + + : 30618 : if VUNLIKELY (idx == kMaxTierCount || alignment > kBlockAlignment || impl_->dispatch_states[idx] == nullptr) {
+ + # + +
+ ]
672 : 115 : void* p = ::operator new(bytes, std::align_val_t{alignment}, std::nothrow);
673 : :
674 [ - + ]: 115 : if VUNLIKELY (p == nullptr) {
675 : : return nullptr; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
676 : : }
677 : :
678 : 115 : impl_->oversized_alloc.count.fetch_add(1, std::memory_order_relaxed);
679 : 115 : impl_->oversized_alloc.bytes.fetch_add(bytes, std::memory_order_relaxed);
680 : :
681 : 115 : return p;
682 : : }
683 : :
684 : 30470 : MemoryTierState& state = *impl_->dispatch_states[idx];
685 : 30360 : void* block = tier_allocate(state);
686 : :
687 [ - + ]: 30987 : if VUNLIKELY (block == nullptr) {
688 : : return nullptr; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
689 : : }
690 : :
691 : 30987 : state.hit_count.fetch_add(1, std::memory_order_relaxed);
692 : :
693 : 30987 : return block;
694 : : }
695 : :
696 : 30479 : void MemoryPool::deallocate(void* p, size_t bytes, size_t alignment) noexcept {
697 [ # + ]: 30479 : if VUNLIKELY (!is_power_of_two(alignment)) {
698 : 0 : CLOG_E("MemoryPool::deallocate: alignment %zu is not a power of two; leaking %p.", alignment, p);
699 : 1 : return;
700 : : }
701 : :
702 [ + + ]: 30409 : if VUNLIKELY (p == nullptr) {
703 : 2 : return;
704 : : }
705 : :
706 : 30407 : const size_t idx = find_tier(bytes);
707 : :
708 [ + # + + : 30553 : if VUNLIKELY (idx == kMaxTierCount || alignment > kBlockAlignment || impl_->dispatch_states[idx] == nullptr) {
+ + # + +
+ ]
709 : 114 : ::operator delete(p, bytes, std::align_val_t{alignment});
710 : 114 : impl_->oversized_dealloc_count.fetch_add(1, std::memory_order_relaxed);
711 : :
712 : 114 : return;
713 : : }
714 : :
715 : 30343 : MemoryTierState& state = *impl_->dispatch_states[idx];
716 : 30288 : tier_deallocate(state, p);
717 : 30970 : state.deallocate_count.fetch_add(1, std::memory_order_relaxed);
718 : : }
719 : :
720 : 17 : size_t MemoryPool::get_tier_count() const noexcept { return impl_->tier_count; }
721 : :
722 : 39 : std::vector<MemoryPool::TierStats> MemoryPool::get_stats() const noexcept {
723 : 39 : const size_t count = impl_->tier_count;
724 : :
725 : 39 : std::vector<TierStats> result;
726 : :
727 : : try {
728 [ + - ]: 39 : result.reserve(count);
729 : : } catch (...) { // LCOV_EXCL_LINE GCOVR_EXCL_LINE
730 : : return {}; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
731 : : } // LCOV_EXCL_LINE GCOVR_EXCL_LINE
732 : :
733 [ + + ]: 334 : for (size_t i = 0; i < count; ++i) {
734 : 295 : const MemoryTierState& state = *impl_->tier_states[i];
735 : 295 : const uint64_t hits = state.hit_count.load(std::memory_order_relaxed);
736 : 295 : const uint64_t deallocs = state.deallocate_count.load(std::memory_order_relaxed);
737 : :
738 : 295 : TierStats item;
739 : 295 : item.max_size = state.max_size;
740 : 295 : item.blocks_per_chunk = state.blocks_per_chunk;
741 : 295 : item.block_size = state.block_size;
742 : 295 : item.hit_count = hits;
743 : 295 : item.deallocate_count = deallocs;
744 [ + - ]: 295 : item.in_use_blocks = (hits >= deallocs) ? (hits - deallocs) : 0U;
745 : 295 : item.upstream_alloc_count = state.upstream_alloc_count.load(std::memory_order_relaxed);
746 : 295 : item.upstream_alloc_bytes = state.upstream_alloc_bytes.load(std::memory_order_relaxed);
747 : 295 : item.chunk_count = state.chunk_count.load(std::memory_order_relaxed);
748 : :
749 : 295 : result.emplace_back(item);
750 : : }
751 : :
752 : 39 : return result;
753 : 39 : }
754 : :
755 : 34 : MemoryPool::OversizedStats MemoryPool::get_oversized_stats() const noexcept {
756 : 34 : OversizedStats result;
757 : :
758 : 34 : result.alloc_count = impl_->oversized_alloc.count.load(std::memory_order_relaxed);
759 : 34 : result.alloc_bytes = impl_->oversized_alloc.bytes.load(std::memory_order_relaxed);
760 : 34 : result.dealloc_count = impl_->oversized_dealloc_count.load(std::memory_order_relaxed);
761 : :
762 : 34 : return result;
763 : : }
764 : :
765 : 1 : void MemoryPool::reset_stats() noexcept {
766 : 1 : const size_t count = impl_->tier_count;
767 : :
768 [ + + ]: 2 : for (size_t i = 0; i < count; ++i) {
769 : 1 : MemoryTierState& state = *impl_->tier_states[i];
770 : 1 : state.hit_count.store(0, std::memory_order_relaxed);
771 : 1 : state.deallocate_count.store(0, std::memory_order_relaxed);
772 : : }
773 : :
774 : 1 : impl_->oversized_alloc.count.store(0, std::memory_order_relaxed);
775 : 1 : impl_->oversized_alloc.bytes.store(0, std::memory_order_relaxed);
776 : 1 : impl_->oversized_dealloc_count.store(0, std::memory_order_relaxed);
777 : 1 : }
778 : :
779 : 8 : void MemoryPool::clear() noexcept {
780 : 8 : constexpr size_t kStackSlots = 64U;
781 : :
782 [ + + ]: 48 : for (auto& state : impl_->owned_states) {
783 : 40 : size_t stack_free_counts[kStackSlots] = {};
784 : 40 : MemoryChunk stack_to_delete[kStackSlots];
785 : :
786 : 40 : std::vector<size_t> heap_free_counts;
787 : 40 : std::vector<MemoryChunk> heap_to_delete;
788 : :
789 : 40 : const size_t chunks_hint = state->chunk_count.load(std::memory_order_relaxed);
790 : :
791 [ - + ]: 40 : if VUNLIKELY (chunks_hint > kStackSlots) {
792 : : try {
793 : : // LCOV_EXCL_START GCOVR_EXCL_START
794 : : heap_free_counts.reserve(chunks_hint);
795 : : heap_to_delete.reserve(chunks_hint);
796 : : } catch (std::exception&) {
797 : : }
798 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
799 : : }
800 : :
801 : 40 : MemoryChunk* to_delete = nullptr;
802 : 40 : size_t to_delete_count = 0U;
803 : :
804 : : {
805 : 40 : SpinLockGuard lock(state->mtx);
806 : :
807 : 40 : const size_t chunk_count = state->chunks.size();
808 : :
809 [ + + ]: 40 : if VUNLIKELY (chunk_count == 0U) {
810 : 30 : continue;
811 : : }
812 : :
813 : 10 : size_t* free_counts = stack_free_counts;
814 : :
815 : 10 : const bool spill_to_heap = (chunk_count > kStackSlots);
816 : :
817 [ - + ]: 10 : if VUNLIKELY (spill_to_heap) {
818 : : try {
819 : : // LCOV_EXCL_START GCOVR_EXCL_START
820 : : heap_free_counts.assign(chunk_count, 0U);
821 : : } catch (std::exception&) {
822 : : continue;
823 : : }
824 : :
825 : : free_counts = heap_free_counts.data();
826 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
827 : : }
828 : :
829 : 10 : const size_t block_size = state->block_size;
830 : :
831 : 10 : std::sort(state->chunks.begin(), state->chunks.end(), [](const MemoryChunk& a, const MemoryChunk& b) noexcept {
832 : 3 : return reinterpret_cast<std::uintptr_t>(a.ptr) < reinterpret_cast<std::uintptr_t>(b.ptr);
833 : : });
834 : :
835 : 12238 : const auto find_chunk_idx = [&chunk_count, &state](std::uintptr_t addr) noexcept -> size_t {
836 : 4070 : size_t lo = 0;
837 : 4070 : size_t hi = chunk_count;
838 : :
839 [ + - ]: 4084 : while (lo < hi) {
840 : 4084 : const size_t mid = lo + (hi - lo) / 2U;
841 : 4084 : const auto cs = reinterpret_cast<std::uintptr_t>(state->chunks[mid].ptr);
842 : 4084 : const auto ce = cs + state->chunks[mid].bytes;
843 : :
844 [ + + ]: 4084 : if (addr < cs) {
845 : 14 : hi = mid;
846 [ - + ]: 4070 : } else if (addr >= ce) {
847 : : lo = mid + 1U; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
848 : : } else {
849 : 4070 : return mid;
850 : : }
851 : : }
852 : :
853 : : return SIZE_MAX; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
854 : 10 : };
855 : :
856 [ + + ]: 2045 : for (MemoryFreeNode* node = state->free_list_head; node != nullptr; node = node->next) {
857 : 2035 : const size_t idx = find_chunk_idx(reinterpret_cast<std::uintptr_t>(node));
858 : :
859 [ + - ]: 2035 : if VLIKELY (idx != SIZE_MAX) {
860 : 2035 : ++free_counts[idx];
861 : : }
862 : : }
863 : :
864 : 10 : MemoryFreeNode* new_head = nullptr;
865 : 10 : MemoryFreeNode* current = state->free_list_head;
866 : :
867 [ + + ]: 2045 : while (current != nullptr) {
868 : 2035 : MemoryFreeNode* next = current->next;
869 : 2035 : const size_t idx = find_chunk_idx(reinterpret_cast<std::uintptr_t>(current));
870 : :
871 : 2035 : bool keep = false;
872 : :
873 [ + - ]: 2035 : if VLIKELY (idx != SIZE_MAX) {
874 : 2035 : const size_t total_blocks = state->chunks[idx].bytes / block_size;
875 : 2035 : keep = (free_counts[idx] != total_blocks);
876 : : }
877 : :
878 [ + + ]: 2035 : if (keep) {
879 : 34 : current->next = new_head;
880 : 34 : new_head = current;
881 : : }
882 : :
883 : 2035 : current = next;
884 : : }
885 : :
886 : 10 : state->free_list_head = new_head;
887 : :
888 : 10 : size_t released = 0U;
889 : 10 : size_t write = 0U;
890 : :
891 [ + + ]: 22 : for (size_t read = 0U; read < chunk_count; ++read) {
892 : 12 : const size_t total_blocks = state->chunks[read].bytes / block_size;
893 : :
894 [ + + ]: 12 : if (free_counts[read] == total_blocks) {
895 [ + - ]: 10 : if VLIKELY (!spill_to_heap) {
896 : 10 : stack_to_delete[released] = state->chunks[read];
897 : : } else {
898 : : try {
899 : : // LCOV_EXCL_START GCOVR_EXCL_START
900 : : heap_to_delete.push_back(state->chunks[read]);
901 : : } catch (std::exception&) {
902 : : ::operator delete(state->chunks[read].ptr, state->chunks[read].bytes, std::align_val_t{kBlockAlignment});
903 : : }
904 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
905 : : }
906 : :
907 : 10 : ++released;
908 : : } else {
909 [ - + ]: 2 : if (read != write) {
910 : : state->chunks[write] = state->chunks[read]; // LCOV_EXCL_LINE GCOVR_EXCL_LINE
911 : : }
912 : :
913 : 2 : ++write;
914 : : }
915 : : }
916 : :
917 [ + + ]: 10 : if VLIKELY (released > 0U) {
918 : 9 : state->chunks.resize(write);
919 : 9 : state->chunk_count.fetch_sub(released, std::memory_order_relaxed);
920 : : }
921 : :
922 [ + - ]: 10 : if VLIKELY (!spill_to_heap) {
923 : 10 : to_delete = stack_to_delete;
924 : 10 : to_delete_count = released;
925 : : } else {
926 : : to_delete = heap_to_delete.data(); // LCOV_EXCL_LINE GCOVR_EXCL_LINE
927 : : to_delete_count = heap_to_delete.size(); // LCOV_EXCL_LINE GCOVR_EXCL_LINE
928 : : }
929 [ + + ]: 40 : }
930 : :
931 [ + + ]: 20 : for (size_t i = 0; i < to_delete_count; ++i) {
932 : 10 : ::operator delete(to_delete[i].ptr, to_delete[i].bytes, std::align_val_t{kBlockAlignment});
933 : : }
934 [ + + + + ]: 70 : }
935 : 8 : }
936 : :
937 : 2 : void MemoryPool::trim() noexcept { clear(); }
938 : :
939 : 183 : MemoryPool::Config MemoryPool::get_default_config() {
940 : 181 : static int level = []() noexcept {
941 : 362 : const std::string env_value = Utils::get_env("VLINK_MEMORY_LEVEL", "3");
942 : :
943 : 181 : int parsed = kDefaultMemoryLevel;
944 : :
945 : 181 : const char* first = env_value.data();
946 : 181 : const char* last = first + env_value.size();
947 : :
948 : 181 : auto [ptr, ec] = std::from_chars(first, last, parsed);
949 : :
950 [ + - - + : 181 : if VUNLIKELY (ec != std::errc() || ptr != last) {
- + ]
951 : : // LCOV_EXCL_START GCOVR_EXCL_START
952 : : CLOG_W("MemoryPool: VLINK_MEMORY_LEVEL=\"%s\" is not a valid integer, fallback to %d.", env_value.c_str(),
953 : : kDefaultMemoryLevel);
954 : :
955 : : return kDefaultMemoryLevel;
956 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
957 : : }
958 : :
959 [ + - - + : 181 : if VUNLIKELY (parsed < kMinMemoryLevel || parsed > kMaxMemoryLevel) {
- + ]
960 : : // LCOV_EXCL_START GCOVR_EXCL_START
961 : : CLOG_W("MemoryPool: VLINK_MEMORY_LEVEL=%d out of range [%d, %d], clamped.", parsed, kMinMemoryLevel,
962 : : kMaxMemoryLevel);
963 : :
964 : : return parsed < kMinMemoryLevel ? kMinMemoryLevel : kMaxMemoryLevel;
965 : : // LCOV_EXCL_STOP GCOVR_EXCL_STOP
966 : : }
967 : :
968 : 181 : return parsed;
969 [ + + + - ]: 364 : }();
970 : :
971 [ + + + - : 183 : static bool prealloc_env = (Utils::get_env("VLINK_MEMORY_PREALLOC") == "1");
+ - + - -
- ]
972 : :
973 : 183 : Config config = create_memory_config(level, prealloc_env);
974 : :
975 : 183 : return config;
976 : : }
977 : :
978 : 10183 : MemoryPool& MemoryPool::global_instance(bool use_env_level) {
979 : : #if MEMORY_POOL_NERVER_DELETE
980 : : alignas(MemoryPool) static char buf[sizeof(MemoryPool)];
981 : :
982 : : static auto* instance =
983 : : new (buf) MemoryPool(use_env_level ? get_default_config() : create_memory_config(kDefaultMemoryLevel, false));
984 : :
985 : : return *instance;
986 : : #else
987 [ + + + - : 10183 : static MemoryPool instance(use_env_level ? get_default_config() : create_memory_config(kDefaultMemoryLevel, false));
+ - + - -
- + - -
- ]
988 : :
989 : 10183 : return instance;
990 : : #endif
991 : : }
992 : :
993 : 60236 : size_t MemoryPool::find_tier(size_t bytes) const noexcept {
994 : 60236 : const size_t count = impl_->dispatch_count;
995 : 59639 : const size_t* const sizes = impl_->dispatch_max_sizes;
996 : :
997 [ + + ]: 292343 : for (size_t i = 0; i < count; ++i) {
998 [ + + ]: 292329 : if (bytes <= sizes[i]) {
999 : 60446 : return i;
1000 : : }
1001 : : }
1002 : :
1003 : 14 : return kMaxTierCount;
1004 : : }
1005 : :
1006 : : } // namespace vlink
|
