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 :
21 : namespace boost {
22 : namespace capy {
23 :
24 : /** Recycles freed blocks through per-thread pools, with a shared pool for cross-thread reuse.
25 :
26 : This memory resource recycles memory blocks using power-of-two
27 : size classes for O(1) allocation lookup. It maintains a thread-local
28 : pool for fast lock-free access and a global pool for cross-thread
29 : block sharing.
30 :
31 : Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
32 : Allocations larger than 2048 bytes bypass the pools entirely.
33 :
34 : This is the default allocator used by run_async when no allocator
35 : is specified.
36 :
37 : @par Thread Safety
38 : Thread-safe. The thread-local pool requires no synchronization.
39 : The global pool uses a mutex for cross-thread access.
40 :
41 : @par Example
42 : @par !example example
43 :
44 :
45 : @see get_recycling_memory_resource
46 : @see run_async
47 : */
48 : BOOST_CAPY_MSVC_WARNING_PUSH
49 : BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
50 : class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
51 : {
52 : static constexpr std::size_t num_classes = 6;
53 : static constexpr std::size_t min_class_size = 64; // 2^6
54 : static constexpr std::size_t max_class_size = 2048; // 2^11
55 : static constexpr std::size_t bucket_capacity = 16;
56 :
57 : static std::size_t
58 HIT 433150 : round_up_pow2(std::size_t n) noexcept
59 : {
60 433150 : return n <= min_class_size ? min_class_size : std::bit_ceil(n);
61 : }
62 :
63 : static std::size_t
64 433150 : get_class_index(std::size_t rounded) noexcept
65 : {
66 433150 : std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
67 433150 : return idx < num_classes ? idx : num_classes;
68 : }
69 :
70 : struct bucket
71 : {
72 : std::size_t count = 0;
73 : void* ptrs[bucket_capacity] = {};
74 :
75 221234 : void* pop() noexcept
76 : {
77 221234 : if(count == 0)
78 210567 : return nullptr;
79 10667 : return ptrs[--count];
80 : }
81 :
82 : // Peter Dimov's idea
83 210566 : void* pop(bucket& b) noexcept
84 : {
85 210566 : if(count == 0)
86 209999 : return nullptr;
87 4678 : for(std::size_t i = 0; i < count; ++i)
88 4111 : b.ptrs[i] = ptrs[i];
89 567 : b.count = count - 1;
90 567 : count = 0;
91 567 : return b.ptrs[b.count];
92 : }
93 :
94 426147 : bool push(void* p) noexcept
95 : {
96 426147 : if(count >= bucket_capacity)
97 414913 : return false;
98 11234 : ptrs[count++] = p;
99 11234 : return true;
100 : }
101 : };
102 :
103 : struct pool
104 : {
105 : bucket buckets[num_classes];
106 :
107 : // No destructor: a non-trivial dtor forces a guard variable on the
108 : // thread_local in local(), checked on every alloc/free. Constant
109 : // initialization plus a trivial dtor makes that access a bare TLS
110 : // load. Cached blocks are instead reclaimed explicitly: per-thread
111 : // by arm_thread_cleanup() at thread exit, and the global pool by
112 : // global()'s holder destructor at process exit.
113 : };
114 :
115 : #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
116 : !defined(BOOST_CAPY_STATIC_LINK)
117 : // A shared build defines this thread's pool, and the flag below, in
118 : // the library: inline, each module would cache in a pool of its own,
119 : // which the library's thread-exit cleanup never drains.
120 : static pool& local() noexcept;
121 : #else
122 : static pool& local() noexcept
123 : {
124 : static thread_local pool p;
125 : return p;
126 : }
127 : #endif
128 :
129 : static pool& global() noexcept;
130 : static std::mutex& global_mutex() noexcept;
131 :
132 : void* allocate_slow(std::size_t rounded, std::size_t idx);
133 : void deallocate_slow(void* p, std::size_t idx);
134 :
135 : // Register a thread-exit callback that drains this thread's local
136 : // pool back to the OS. Called only off the hot path: unconditionally
137 : // from the slow paths, and from deallocate_fast while the flag below
138 : // is clear. Returns false once that callback has run: nothing drains
139 : // the local pool after it, so frees must bypass it.
140 : static bool arm_thread_cleanup() noexcept;
141 :
142 : // Guard-free flag (constinit bool, trivial dtor): set once cleanup is
143 : // armed, and cleared again when the cleanup has run.
144 : #if (defined(BOOST_CAPY_DYN_LINK) || defined(BOOST_ALL_DYN_LINK)) && \
145 : !defined(BOOST_CAPY_STATIC_LINK)
146 : static bool& thread_armed() noexcept;
147 : #else
148 : static bool& thread_armed() noexcept
149 : {
150 : static thread_local bool armed = false;
151 : return armed;
152 : }
153 : #endif
154 :
155 : public:
156 : /** Destroy the resource.
157 :
158 : No cached block is released here. Every pool is static, so an
159 : instance holds no state of its own. The thread-local pool is
160 : drained at thread exit, and the global pool at process exit.
161 : */
162 : ~recycling_memory_resource();
163 :
164 : /** Allocate without virtual dispatch.
165 :
166 : Handles the fast path inline (thread-local bucket pop)
167 : and falls through to the slow path for global pool or
168 : heap allocation.
169 :
170 : A request larger than the largest size class (2048 bytes)
171 : bypasses the pools and goes straight to `::operator new`.
172 :
173 : The second parameter is the requested alignment, and it is ignored.
174 : Every block comes from `::operator new`, so blocks carry the
175 : implementation's default new alignment and no more.
176 :
177 : @param bytes The number of bytes to allocate.
178 :
179 : @return A pointer to a block of at least `bytes` bytes. A pooled
180 : block is rounded up to its size class, so it may be larger than
181 : requested.
182 :
183 : @throws std::bad_alloc If the underlying `::operator new` fails.
184 : */
185 : void*
186 216575 : allocate_fast(std::size_t bytes, std::size_t)
187 : {
188 216575 : std::size_t rounded = round_up_pow2(bytes);
189 216575 : std::size_t idx = get_class_index(rounded);
190 216575 : if(idx >= num_classes)
191 MIS 0 : return ::operator new(bytes);
192 HIT 216575 : auto& lp = local();
193 216575 : if(auto* p = lp.buckets[idx].pop())
194 6008 : return p;
195 210567 : return allocate_slow(rounded, idx);
196 : }
197 :
198 : /** Deallocate without virtual dispatch.
199 :
200 : Handles the fast path inline (thread-local bucket push)
201 : and falls through to the slow path for global pool or
202 : heap deallocation.
203 :
204 : The block is cached in the pool of the thread that frees it, not
205 : the thread that allocated it.
206 :
207 : The third parameter is the alignment the block was allocated with,
208 : and it is ignored, as it is on allocation.
209 :
210 : @param p The block to return. It must have come from
211 : @ref allocate_fast or @ref do_allocate on this resource.
212 :
213 : @param bytes The size the block was allocated with. The size class
214 : is recomputed from it, so passing a different value puts the block
215 : in the wrong bucket.
216 : */
217 : void
218 216575 : deallocate_fast(void* p, std::size_t bytes, std::size_t)
219 : {
220 216575 : std::size_t rounded = round_up_pow2(bytes);
221 216575 : std::size_t idx = get_class_index(rounded);
222 216575 : if(idx >= num_classes)
223 : {
224 MIS 0 : ::operator delete(p);
225 0 : return;
226 : }
227 : // Arms thread-exit cleanup for any thread that caches via
228 : // deallocate, including consumer threads that never hit a slow
229 : // path; after that cleanup, the block bypasses the local pool.
230 HIT 216575 : auto& armed = thread_armed();
231 216575 : if(!armed)
232 : {
233 360 : if(!arm_thread_cleanup())
234 : {
235 4 : deallocate_slow(p, idx);
236 4 : return;
237 : }
238 356 : armed = true;
239 : }
240 216571 : auto& lp = local();
241 216571 : if(lp.buckets[idx].push(p))
242 6999 : return;
243 209572 : deallocate_slow(p, idx);
244 : }
245 :
246 : protected:
247 : /** Allocate through the `std::pmr::memory_resource` interface.
248 :
249 : Forwards to @ref allocate_fast, so it has that function's contract.
250 : Call `allocate_fast` directly to skip the virtual dispatch.
251 :
252 : @param bytes The number of bytes to allocate.
253 :
254 : @param alignment The requested alignment. It is ignored.
255 :
256 : @return A pointer to a block of at least `bytes` bytes.
257 :
258 : @throws std::bad_alloc If the underlying `::operator new` fails.
259 : */
260 : void*
261 : do_allocate(std::size_t bytes, std::size_t alignment) override;
262 :
263 : /** Deallocate through the `std::pmr::memory_resource` interface.
264 :
265 : Forwards to @ref deallocate_fast, so it has that function's
266 : contract.
267 :
268 : @param p The block to return, as obtained from this resource.
269 :
270 : @param bytes The size the block was allocated with.
271 :
272 : @param alignment The alignment the block was allocated with. It is
273 : ignored.
274 : */
275 : void
276 : do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override;
277 :
278 : /** Compare this resource with another for equality.
279 :
280 : Equality is object identity: two distinct
281 : `recycling_memory_resource` objects compare unequal, even though the
282 : pools they draw from are static and therefore shared.
283 :
284 : @param other The resource to compare against.
285 :
286 : @return `true` if `other` is the same object as `*this`; otherwise
287 : `false`.
288 : */
289 : bool
290 2 : do_is_equal(const memory_resource& other) const noexcept override
291 : {
292 2 : return this == &other;
293 : }
294 : };
295 : BOOST_CAPY_MSVC_WARNING_POP
296 :
297 : /** Returns pointer to the default recycling memory resource.
298 :
299 : The returned pointer is valid for the lifetime of the program.
300 : This is the default allocator used by run_async.
301 :
302 : @return Pointer to the recycling memory resource.
303 :
304 : @see recycling_memory_resource
305 : @see run_async
306 : */
307 : BOOST_CAPY_DECL
308 : std::pmr::memory_resource*
309 : get_recycling_memory_resource() noexcept;
310 :
311 : } // namespace capy
312 : } // namespace boost
313 :
314 : #endif
|
