TLA Line data Source code
1 : //
2 : // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3 : // Copyright (c) 2026 Michael Vandeberg
4 : //
5 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
6 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 : //
8 : // Official repository: https://github.com/cppalliance/capy
9 : //
10 :
11 : #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12 : #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
13 :
14 : #include <boost/capy/detail/config.hpp>
15 :
16 : #include <bit>
17 : #include <cstddef>
18 : #include <memory_resource>
19 : #include <mutex>
20 : #include <new>
21 :
22 : namespace boost {
23 : namespace capy {
24 :
25 : /** Recycles freed blocks through per-thread pools, with a shared pool for cross-thread reuse.
26 :
27 : This memory resource recycles memory blocks using power-of-two
28 : size classes for O(1) allocation lookup. It maintains a thread-local
29 : pool for fast lock-free access and a global pool for cross-thread
30 : block sharing.
31 :
32 : Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
33 : Allocations larger than 2048 bytes bypass the pools entirely.
34 :
35 : Each pool caches at most 256 KiB of blocks per size class:
36 : 4096 blocks of the smallest class, 128 of the largest. A freed
37 : block that fits in neither the thread's pool nor the global pool
38 : goes back to `::operator delete`.
39 :
40 : Blocks a thread caches but stops using drain back to the global
41 : pool. The drain runs as the thread goes on freeing blocks or
42 : refilling from the global pool. Other threads can then reuse what a
43 : burst leaves behind. Blocks the global pool has no room for go back
44 : to `::operator delete`.
45 :
46 : This is the default allocator used by run_async when no allocator
47 : is specified.
48 :
49 : @par Thread Safety
50 : Thread-safe. The thread-local pool requires no synchronization.
51 : The global pool uses a mutex for cross-thread access.
52 :
53 : @par Example
54 : @par !example example
55 :
56 :
57 : @see @ref get_recycling_memory_resource
58 : @see @ref run_async
59 : */
60 : BOOST_CAPY_MSVC_WARNING_PUSH
61 : BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
62 : class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
63 : {
64 : static constexpr std::size_t num_classes = 6;
65 : static constexpr std::size_t min_class_size = 64; // 2^6
66 : static constexpr std::size_t max_class_size = 2048; // 2^11
67 : static constexpr int min_class_shift = std::countr_zero(min_class_size);
68 : static constexpr std::size_t max_cached_bytes = 256 * 1024;
69 :
70 : // Frees on one thread, plus blocks it refills from the global pool,
71 : // between decay passes. Allocations served from the thread's pool
72 : // aren't counted, which keeps the counter off that path.
73 : static constexpr std::size_t decay_period = 4096;
74 :
75 : static std::size_t
76 HIT 2287936 : round_up_pow2(std::size_t n) noexcept
77 : {
78 2287936 : return n <= min_class_size ? min_class_size : std::bit_ceil(n);
79 : }
80 :
81 : static std::size_t
82 2287936 : get_class_index(std::size_t rounded) noexcept
83 : {
84 : auto const idx = static_cast<std::size_t>(
85 2287936 : std::countr_zero(rounded) - min_class_shift);
86 2287936 : return idx < num_classes ? idx : num_classes;
87 : }
88 :
89 : static constexpr std::size_t
90 1410470 : bucket_capacity(std::size_t idx) noexcept
91 : {
92 1410470 : return max_cached_bytes >> (idx + min_class_shift);
93 : }
94 :
95 : // Cached blocks are linked through their own storage, so a bucket
96 : // holds any number of them without a side array.
97 : struct node
98 : {
99 : node* next;
100 : };
101 :
102 : struct bucket
103 : {
104 : node* head = nullptr;
105 : std::size_t count = 0;
106 :
107 : // Fewest blocks cached since the last decay pass: that many sat
108 : // unused through the whole period.
109 : std::size_t low = 0;
110 :
111 1199427 : void* pop() noexcept
112 : {
113 1199427 : node* n = head;
114 1199427 : if(n == nullptr)
115 302445 : return nullptr;
116 896982 : head = n->next;
117 896982 : --count;
118 896982 : if(count < low)
119 53349 : low = count;
120 896982 : return n;
121 : }
122 :
123 : // Peter Dimov's idea
124 : // `b` must be empty: its chain is overwritten.
125 302443 : void* pop(bucket& b) noexcept
126 : {
127 302443 : if(head == nullptr)
128 302414 : return nullptr;
129 29 : b.head = head;
130 29 : b.count = count;
131 29 : head = nullptr;
132 29 : count = 0;
133 29 : low = 0;
134 29 : return b.pop();
135 : }
136 :
137 1410348 : bool push(void* p, std::size_t capacity) noexcept
138 : {
139 1410348 : if(count >= capacity)
140 473705 : return false;
141 936643 : head = ::new(p) node{head};
142 936643 : ++count;
143 936643 : return true;
144 : }
145 : };
146 :
147 : struct pool
148 : {
149 : bucket buckets[num_classes];
150 : std::size_t arrivals = 0;
151 :
152 : // No destructor: a non-trivial dtor forces a guard variable on the
153 : // thread_local in local(), checked on every alloc/free. Constant
154 : // initialization plus a trivial dtor makes that access a bare TLS
155 : // load. Cached blocks are instead reclaimed explicitly: per-thread
156 : // by arm_thread_cleanup() at thread exit, and the global pool by
157 : // global()'s holder destructor at process exit.
158 : };
159 :
160 : #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
161 : !defined(BOOST_CAPY_STATIC_LINK)
162 : // A shared build defines this thread's pool, and the flag below, in
163 : // the library: inline, each module would cache in a pool of its own,
164 : // which the library's thread-exit cleanup never drains.
165 : static pool& local() noexcept;
166 : #else
167 : static pool& local() noexcept
168 : {
169 : static thread_local pool p;
170 : return p;
171 : }
172 : #endif
173 :
174 : static pool& global() noexcept;
175 : static std::mutex& global_mutex() noexcept;
176 :
177 : void* allocate_slow(std::size_t rounded, std::size_t idx);
178 : void deallocate_slow(void* p, std::size_t idx);
179 :
180 : // Move half of each bucket's idle blocks to the global pool, or
181 : // release them when it has no room. Halving, rather than emptying,
182 : // leaves a burst that skips one period half its blocks.
183 : static void decay(pool& lp) noexcept;
184 :
185 : // Register a thread-exit callback that drains this thread's local
186 : // pool back to the OS. Called only off the hot path: unconditionally
187 : // from the slow paths, and from deallocate_fast while the flag below
188 : // is clear. Returns false once that callback has run: nothing drains
189 : // the local pool after it, so frees must bypass it.
190 : static bool arm_thread_cleanup() noexcept;
191 :
192 : // Guard-free flag (constinit bool, trivial dtor): set once cleanup is
193 : // armed, and cleared again when the cleanup has run.
194 : #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
195 : !defined(BOOST_CAPY_STATIC_LINK)
196 : static bool& thread_armed() noexcept;
197 : #else
198 : static bool& thread_armed() noexcept
199 : {
200 : static thread_local bool armed = false;
201 : return armed;
202 : }
203 : #endif
204 :
205 : public:
206 : /** Destroy the resource.
207 :
208 : No cached block is released here. Every pool is static, so an
209 : instance holds no state of its own. The thread-local pool is
210 : drained at thread exit, and the global pool at process exit.
211 : */
212 : ~recycling_memory_resource();
213 :
214 : /** Allocate without virtual dispatch.
215 :
216 : Handles the fast path inline (thread-local bucket pop)
217 : and falls through to the slow path for global pool or
218 : heap allocation.
219 :
220 : A request larger than the largest size class (2048 bytes)
221 : bypasses the pools and goes straight to `::operator new`.
222 :
223 : The second parameter is the requested alignment, and it is ignored.
224 : Every block comes from `::operator new`, so blocks carry the
225 : implementation's default new alignment and no more.
226 :
227 : @par Complexity
228 : Amortized constant. Now and then a call also hands this thread's
229 : idle cached blocks to the global pool, or releases them when it
230 : has no room.
231 :
232 : @param bytes The number of bytes to allocate.
233 :
234 : @return A pointer to a block of at least `bytes` bytes. A pooled
235 : block is rounded up to its size class, so it may be larger than
236 : requested.
237 :
238 : @throws std::bad_alloc If the underlying `::operator new` fails.
239 : */
240 : void*
241 1143968 : allocate_fast(std::size_t bytes, std::size_t)
242 : {
243 1143968 : std::size_t rounded = round_up_pow2(bytes);
244 1143968 : std::size_t idx = get_class_index(rounded);
245 1143968 : if(idx >= num_classes)
246 MIS 0 : return ::operator new(bytes);
247 HIT 1143968 : if(auto* p = local().buckets[idx].pop())
248 841524 : return p;
249 302444 : return allocate_slow(rounded, idx);
250 : }
251 :
252 : /** Deallocate without virtual dispatch.
253 :
254 : Handles the fast path inline (thread-local bucket push)
255 : and falls through to the slow path for global pool or
256 : heap deallocation.
257 :
258 : The block is cached in the pool of the thread that frees it, not
259 : the thread that allocated it.
260 :
261 : The third parameter is the alignment the block was allocated with,
262 : and it is ignored, as it is on allocation.
263 :
264 : @par Complexity
265 : Amortized constant. Now and then a call also hands this thread's
266 : idle cached blocks to the global pool, or releases them when it
267 : has no room.
268 :
269 : @param p The block to return. It must have come from
270 : @ref allocate_fast or @ref do_allocate on this resource.
271 :
272 : @param bytes The size the block was allocated with. The size class
273 : is recomputed from it, so passing a different value puts the block
274 : in the wrong bucket.
275 : */
276 : void
277 1143968 : deallocate_fast(void* p, std::size_t bytes, std::size_t)
278 : {
279 1143968 : std::size_t rounded = round_up_pow2(bytes);
280 1143968 : std::size_t idx = get_class_index(rounded);
281 1143968 : if(idx >= num_classes)
282 : {
283 MIS 0 : ::operator delete(p);
284 0 : return;
285 : }
286 : // Arms thread-exit cleanup for any thread that caches via
287 : // deallocate, including consumer threads that never hit a slow
288 : // path; after that cleanup, the block bypasses the local pool.
289 HIT 1143968 : auto& armed = thread_armed();
290 1143968 : if(!armed)
291 : {
292 375 : if(!arm_thread_cleanup())
293 : {
294 4 : deallocate_slow(p, idx);
295 4 : return;
296 : }
297 371 : armed = true;
298 : }
299 1143964 : auto& lp = local();
300 1143964 : if(++lp.arrivals == decay_period)
301 272 : decay(lp);
302 1143964 : if(lp.buckets[idx].push(p, bucket_capacity(idx)))
303 877584 : return;
304 266380 : deallocate_slow(p, idx);
305 : }
306 :
307 : protected:
308 : /** Allocate through the `std::pmr::memory_resource` interface.
309 :
310 : Forwards to @ref allocate_fast, so it has that function's contract.
311 : Call `allocate_fast` directly to skip the virtual dispatch.
312 :
313 : @param bytes The number of bytes to allocate.
314 :
315 : @param alignment The requested alignment. It is ignored.
316 :
317 : @return A pointer to a block of at least `bytes` bytes.
318 :
319 : @throws std::bad_alloc If the underlying `::operator new` fails.
320 : */
321 : void*
322 : do_allocate(std::size_t bytes, std::size_t alignment) override;
323 :
324 : /** Deallocate through the `std::pmr::memory_resource` interface.
325 :
326 : Forwards to @ref deallocate_fast, so it has that function's
327 : contract.
328 :
329 : @param p The block to return, as obtained from this resource.
330 :
331 : @param bytes The size the block was allocated with.
332 :
333 : @param alignment The alignment the block was allocated with. It is
334 : ignored.
335 : */
336 : void
337 : do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override;
338 :
339 : /** Compare this resource with another for equality.
340 :
341 : Equality is object identity: two distinct
342 : `recycling_memory_resource` objects compare unequal, even though the
343 : pools they draw from are static and therefore shared.
344 :
345 : @param other The resource to compare against.
346 :
347 : @return `true` if `other` is the same object as `*this`; otherwise
348 : `false`.
349 : */
350 : bool
351 2 : do_is_equal(const memory_resource& other) const noexcept override
352 : {
353 2 : return this == &other;
354 : }
355 : };
356 : BOOST_CAPY_MSVC_WARNING_POP
357 :
358 : /** Returns pointer to the default recycling memory resource.
359 :
360 : The returned pointer is valid for the lifetime of the program.
361 : This is the default allocator used by run_async.
362 :
363 : @return Pointer to the recycling memory resource.
364 :
365 : @see @ref recycling_memory_resource
366 : @see @ref run_async
367 : */
368 : BOOST_CAPY_DECL
369 : std::pmr::memory_resource*
370 : get_recycling_memory_resource() noexcept;
371 :
372 : } // namespace capy
373 : } // namespace boost
374 :
375 : #endif
|
