VLink  2.3.0
A high-performance communication middleware
memory_pool.h
Go to the documentation of this file.
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 /**
25  * @file memory_pool.h
26  * @brief Size-class tiered memory pool with per-tier free lists and runtime statistics.
27  *
28  * @details
29  * @c MemoryPool dispatches each allocation request to one of a fixed pyramid of size classes.
30  * Every tier owns a set of singly-linked free-list shards (a power of two sized from the hardware
31  * concurrency, between 8 and 64) plus one shared vector of upstream chunks. A tier starts on its
32  * primary shard and enables sharded dispatch only after repeated real lock contention is
33  * observed. Empty local shards steal at most
34  * @c Config::batch_size nodes at a time. Lazy growth installs chunks of at most 64 KiB (or one
35  * block when a single block is larger), so an allocating thread never pays more than a bounded
36  * first-touch burst; with @c Config::lazy_scale the cap becomes one sixteenth of the tier quota
37  * (never below 32 KiB), trading a larger first touch for fewer upstream calls at higher levels.
38  * The configured @c blocks_per_chunk still bounds every install, and preallocation fills the
39  * whole quota as one chunk. Lazy tiers therefore accumulate more, smaller chunks than a
40  * preallocated tier holding the same bytes. Sharding does not multiply chunk quotas.
41  * Requests larger than the biggest tier (or with an alignment stricter than
42  * @c alignof(std::max_align_t)) bypass the pool and route directly to @c ::operator @c new /
43  * @c ::operator @c delete.
44  *
45  * @par Tier / bucket source
46  *
47  * | Source | When used |
48  * | ------------------------------------- | ------------------------------------------------------ |
49  * | Caller-supplied @c Config | @c MemoryPool(const @c Config&) with non-empty tiers |
50  * | @c get_default_config() (level 0..9) | @c global_instance(true) |
51  * | Built-in level-3 balanced pyramid | Malformed input fallback or @c global_instance(false) |
52  * | Built-in level @c N row | @c MemoryPool(int @c level, @c bool @c prealloc) ctor |
53  *
54  * @par Allocation flow
55  *
56  * @verbatim
57  * allocate(bytes, align)
58  * |
59  * v
60  * +-----------------+ align > kBlockAlignment? +---------------------+
61  * | guard | ----------------------------------> | oversized bypass |
62  * +-----------------+ | ::operator new |
63  * | no +---------------------+
64  * v
65  * +-----------------+ no fit ----> oversized bypass
66  * | find_tier(bs) |
67  * +--------+--------+
68  * | tier hit
69  * v
70  * +-----------------+ free list non-empty -> pop block
71  * | per-tier shard |
72  * +--------+--------+
73  * | free list empty
74  * v
75  * +-----------------+ ::operator new for next chunk
76  * | upstream alloc | carve into N blocks of tier size
77  * +-----------------+
78  * @endverbatim
79  *
80  * @par Cleanup primitives
81  *
82  * | Method | What it releases | Concurrent traffic? |
83  * | ------------------ | --------------------------------------------- | ------------------- |
84  * | @c clear / @c trim | Only fully-free chunks; live blocks preserved | Safe |
85  * | @c ~MemoryPool | Every chunk unconditionally | Caller must quiesce |
86  *
87  * @par Example
88  * @code
89  * auto& pool = vlink::MemoryPool::global_instance();
90  * void* p = pool.allocate(512);
91  * pool.deallocate(p, 512); // sizes MUST match
92  *
93  * pool.trim(); // periodic memory reclaim
94  * @endcode
95  *
96  * @note Public methods are @c noexcept and safe for concurrent use. Different size classes do
97  * not contend, while same-tier traffic is distributed after repeated contention is observed.
98  * @c deallocate requires the same @p bytes value passed to @c allocate. @c allocate
99  * returns @c nullptr on upstream OOM and never throws.
100  */
101 
102 #pragma once
103 
104 #include <cstddef>
105 #include <cstdint>
106 #include <memory>
107 #include <vector>
108 
109 #include "./macros.h"
110 
111 namespace vlink {
112 
113 /**
114  * @class MemoryPool
115  * @brief Per-tier free-list pool with runtime statistics and oversized passthrough.
116  *
117  * @details
118  * Thread-safe. Each tier owns a fixed set of short-held free-list spin locks and a blocking
119  * growth lock. The primary free list preserves the single-thread fast path; same-tier traffic
120  * switches to sharded dispatch after repeated contention. Bypass mode -- selected by an empty
121  * tier list -- routes every request through the global allocator without any pooling.
122  */
124  public:
125  /**
126  * @brief Default block alignment for every pooled allocation.
127  *
128  * @details
129  * Equal to @c alignof(std::max_align_t). Stricter alignments bypass the pool and request
130  * memory directly through @c ::operator @c new with @c std::align_val_t.
131  */
132  static constexpr size_t kBlockAlignment = alignof(std::max_align_t);
133 
134  /**
135  * @brief Descriptor for one size class.
136  */
137  struct Tier final {
138  size_t max_size{0}; ///< Inclusive upper bound of the tier in bytes.
139  size_t blocks_per_chunk{0}; ///< Maximum blocks carved from a single upstream chunk.
140  };
141 
142  /**
143  * @brief Constructor configuration for tiers, preallocation, cross-shard batch size and lazy scaling.
144  *
145  * @details
146  * @c prealloc controls whether the constructor immediately fills every tier to its full
147  * @c blocks_per_chunk quota. Default @c false keeps the lazy growth path. Preallocation is
148  * best effort; any tier whose @c ::operator @c new fails stays in lazy state and the
149  * constructor continues. @c batch_size limits how many nodes an empty shard transfers
150  * from another shard while holding its short free-list lock; @c 0 falls back to the default 16.
151  * @c lazy_scale switches the lazy install cap from 64 KiB (or one larger block) to one sixteenth
152  * of the tier quota (never below 32 KiB or one block), so higher quotas need fewer upstream calls.
153  */
154  struct Config final {
155  std::vector<Tier> tiers; ///< Tier descriptors; empty or all-sentinel selects bypass mode.
156  bool prealloc{false}; ///< When @c true, eagerly fill every managed tier to its quota.
157  size_t batch_size{16U}; ///< Maximum nodes transferred per cross-shard steal; @c 0 uses 16.
158  bool lazy_scale{false}; ///< When @c true, scale lazy chunk installs with the tier quota.
159  };
160 
161  /**
162  * @brief Per-tier runtime statistics snapshot.
163  *
164  * @details
165  * Counters use relaxed atomics; @c in_use_blocks and the lifetime upstream fields are best
166  * effort under concurrent traffic, not globally atomic.
167  */
168  struct TierStats final {
169  size_t max_size{0}; ///< Configured @c max_size for this tier.
170  size_t blocks_per_chunk{0}; ///< Configured @c blocks_per_chunk for this tier.
171  size_t block_size{0}; ///< Effective block size after alignment rounding.
172  uint64_t hit_count{0}; ///< Allocations dispatched to this tier (resettable).
173  uint64_t deallocate_count{0}; ///< Deallocations dispatched to this tier (resettable).
174  uint64_t in_use_blocks{0}; ///< Best-effort @c hit_count @c - @c deallocate_count.
175  uint64_t chunk_count{0}; ///< Currently owned chunks; @c clear decrements by released count.
176  uint64_t upstream_alloc_count{0}; ///< Lifetime number of chunks fully installed in this tier.
177  uint64_t upstream_alloc_bytes{0}; ///< Lifetime bytes of those installed chunks.
178  };
179 
180  /**
181  * @brief Statistics for allocations that bypass the tier free lists.
182  *
183  * @details
184  * Captures requests whose size exceeds the largest tier or whose alignment exceeds
185  * @c kBlockAlignment.
186  */
187  struct OversizedStats final {
188  uint64_t alloc_count{0}; ///< Oversized allocations forwarded to the system allocator.
189  uint64_t alloc_bytes{0}; ///< Total bytes of oversized allocations.
190  uint64_t dealloc_count{0}; ///< Oversized deallocations observed.
191  };
192 
193  /**
194  * @brief Constructs an empty pool in bypass mode.
195  *
196  * @details
197  * Equivalent to @c MemoryPool(Config{}): every request hits @c ::operator @c new / @c delete.
198  */
200 
201  /**
202  * @brief Constructs a tiered pool using the built-in pyramid for @p level.
203  *
204  * @details
205  * Out-of-range values are clamped to @c [0, @c 9] and a warning is logged. Level @c 0 yields
206  * bypass mode; the @p prealloc flag is ignored in that case. Level @c 9 fully saturates to
207  * roughly 656 MiB of resident memory.
208  *
209  * @param level Built-in level in @c [0, @c 9].
210  * @param prealloc When @c true, fills every tier to its quota on construction (best effort).
211  * Default: @c false.
212  */
213  explicit MemoryPool(int level, bool prealloc = false);
214 
215  /**
216  * @brief Constructs a tiered pool with an explicit configuration.
217  *
218  * @details
219  * Empty @c config.tiers selects bypass mode. Sentinel entries with @c blocks_per_chunk
220  * @c == @c 0 declare a size ceiling but are stripped at construction; an all-sentinel list is
221  * therefore equivalent to bypass mode. Malformed input (non-monotonic ordering, duplicate
222  * @c max_size, zero @c max_size or @c max_size below the minimum block size) logs an error
223  * and silently falls back to the level-3 default pyramid. @c std::bad_alloc may propagate
224  * from internal vector growth.
225  *
226  * @param config Tier descriptors, preallocation flag and cross-shard steal batch size.
227  */
228  explicit MemoryPool(const Config& config);
229 
230  /**
231  * @brief Releases every owned chunk unconditionally.
232  *
233  * @warning The caller must guarantee no outstanding pooled block is in use and no other
234  * thread is calling @c allocate, @c deallocate, @c clear or @c trim on this instance.
235  * Use @c clear for a non-destructive trim.
236  */
238 
239  /**
240  * @brief Allocates @p bytes of memory from the appropriate tier.
241  *
242  * @details
243  * Routes to the first tier whose @c max_size is @c >= @p bytes. Requests larger than the
244  * biggest tier or with @p alignment @c > @c kBlockAlignment bypass the pool. @p bytes @c ==
245  * @c 0 routes to the smallest tier and still returns a unique non-null pointer that must be
246  * passed back to @c deallocate with the same @c 0 size. Never throws.
247  *
248  * @param bytes Requested size.
249  * @param alignment Required alignment (power of two). Default: @c kBlockAlignment.
250  * @return Pointer to allocated memory, or @c nullptr on upstream OOM.
251  */
252  [[nodiscard]] void* allocate(size_t bytes, size_t alignment = kBlockAlignment) noexcept;
253 
254  /**
255  * @brief Returns a block previously allocated through @c allocate to the pool.
256  *
257  * @param p Pointer returned by @c allocate. @c nullptr is a no-op.
258  * @param bytes Original size passed to @c allocate; MUST match.
259  * @param alignment Original alignment passed to @c allocate.
260  */
261  void deallocate(void* p, size_t bytes, size_t alignment = kBlockAlignment) noexcept;
262 
263  /**
264  * @brief Returns the number of live managed tiers.
265  *
266  * @details
267  * @c 0 indicates bypass mode. Sentinel entries are stripped at construction so the count
268  * reflects only tiers backed by a live free list.
269  *
270  * @return Tier count after sentinel stripping.
271  */
272  [[nodiscard]] size_t get_tier_count() const noexcept;
273 
274  /**
275  * @brief Returns a snapshot of per-tier statistics.
276  *
277  * @return Vector with one entry per live tier.
278  */
279  [[nodiscard]] std::vector<TierStats> get_stats() const noexcept;
280 
281  /**
282  * @brief Returns a snapshot of the oversized-passthrough statistics.
283  *
284  * @details
285  * Counters are loaded with relaxed ordering and are not a globally atomic snapshot.
286  *
287  * @return Aggregated counters for the oversized path.
288  */
289  [[nodiscard]] OversizedStats get_oversized_stats() const noexcept;
290 
291  /**
292  * @brief Resets per-call statistics counters to zero.
293  *
294  * @details
295  * Clears @c hit_count and @c deallocate_count on every tier and the @c oversized_* counters.
296  * Physical / lifetime state (@c chunk_count, @c upstream_alloc_count, @c upstream_alloc_bytes)
297  * is preserved.
298  */
299  void reset_stats() noexcept;
300 
301  /**
302  * @brief Releases only fully-free chunks; preserves chunks still backing live allocations.
303  *
304  * @details
305  * For each tier the free lists are detached under their shard locks, grouped by owning chunk
306  * without holding any lock, and re-attached; chunks whose free-node count equals their block
307  * capacity are released, others stay intact. @c chunk_count is decremented by the number of
308  * released chunks. Safe to call concurrently with @c allocate and @c deallocate: locks are
309  * held only while the chunk list is snapshotted and sorted, the lists are detached and
310  * re-attached, and the chunk list is compacted, so allocations that arrive while the
311  * @c O(F @c log @c C) grouping runs may install new chunks instead of waiting.
312  */
313  void clear() noexcept;
314 
315  /**
316  * @brief Alias of @c clear with a name suited to periodic-trim phrasing.
317  *
318  * @details
319  * Behaviour, complexity and thread-safety are identical to @c clear.
320  */
321  void trim() noexcept;
322 
323  /**
324  * @brief Returns the default configuration using the @c VLINK_MEMORY_* environment variables.
325  *
326  * @details
327  * Each level @c 0..9 maps to a hand-coded row of @c {max_size, @c blocks_per_chunk} pairs.
328  * Level @c 0 is bypass mode. Levels @c 1..9 return 19 entries covering 32 B to 16 MiB; the
329  * 1 MiB / 4 MiB / 8 MiB / 16 MiB ceilings activate at level @c 2 / @c 4 / @c 5 / @c 6 and are
330  * sentinels below those thresholds. Within each level the 32 B head tier carries twice the
331  * @c blocks_per_chunk of the 64 B tier to absorb high-density tiny allocations.
332  *
333  * @c VLINK_MEMORY_PREALLOC controls the @c prealloc flag; only the literal value @c "1"
334  * enables preallocation. @c VLINK_MEMORY_BATCH_SIZE overrides @c batch_size;
335  * it must be a positive integer and defaults to @c 16. @c VLINK_MEMORY_LAZY_SCALE sets
336  * @c lazy_scale; only the literal value @c "1" enables it. Environment values are captured on
337  * the first call to @c get_default_config().
338  *
339  * @return @c Config ready to pass to the constructor.
340  */
341  [[nodiscard]] static Config get_default_config();
342 
343  /**
344  * @brief Returns the process-wide shared @c MemoryPool instance.
345  *
346  * @details
347  * Lazy Meyers singleton. Only the first call decides the configuration; subsequent calls
348  * return the same instance and ignore the argument.
349  *
350  * @warning Whichever value @p use_env_level takes on the first call is baked in for the
351  * rest of the program's lifetime.
352  *
353  * @param use_env_level @c true (default): use @c get_default_config and honour the
354  * environment. @c false: use the built-in level-3 pyramid.
355  * @return Reference to the global pool.
356  */
357  static MemoryPool& global_instance(bool use_env_level = true);
358 
359  private:
360  size_t find_tier(size_t bytes) const noexcept;
361 
362  struct Impl;
363  std::unique_ptr<Impl> impl_;
364 
366 };
367 
368 } // namespace vlink
Cross-platform macros for visibility, branch hints, copy prevention, singletons and string helpers.
#define VLINK_EXPORT
Definition: macros.h:81
#define VLINK_DISALLOW_COPY_AND_ASSIGN(classname)
Deletes the copy constructor and copy-assignment operator of classname.
Definition: macros.h:174