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 : @code
43 : auto* mr = get_recycling_memory_resource();
44 : run_async(ex, mr)(my_task());
45 : @endcode
46 :
47 : @see get_recycling_memory_resource
48 : @see run_async
49 : */
50 : BOOST_CAPY_MSVC_WARNING_PUSH
51 : BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
52 : class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
53 : {
54 : static constexpr std::size_t num_classes = 6;
55 : static constexpr std::size_t min_class_size = 64; // 2^6
56 : static constexpr std::size_t max_class_size = 2048; // 2^11
57 : static constexpr std::size_t bucket_capacity = 16;
58 :
59 : static std::size_t
60 HIT 25532 : round_up_pow2(std::size_t n) noexcept
61 : {
62 25532 : return n <= min_class_size ? min_class_size : std::bit_ceil(n);
63 : }
64 :
65 : static std::size_t
66 25532 : get_class_index(std::size_t rounded) noexcept
67 : {
68 25532 : std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
69 25532 : return idx < num_classes ? idx : num_classes;
70 : }
71 :
72 : struct bucket
73 : {
74 : std::size_t count = 0;
75 : void* ptrs[bucket_capacity] = {};
76 :
77 17059 : void* pop() noexcept
78 : {
79 17059 : if(count == 0)
80 7172 : return nullptr;
81 9887 : return ptrs[--count];
82 : }
83 :
84 : // Peter Dimov's idea
85 7172 : void* pop(bucket& b) noexcept
86 : {
87 7172 : if(count == 0)
88 6500 : return nullptr;
89 4826 : for(std::size_t i = 0; i < count; ++i)
90 4154 : b.ptrs[i] = ptrs[i];
91 672 : b.count = count - 1;
92 672 : count = 0;
93 672 : return b.ptrs[b.count];
94 : }
95 :
96 19168 : bool push(void* p) noexcept
97 : {
98 19168 : if(count >= bucket_capacity)
99 8609 : return false;
100 10559 : ptrs[count++] = p;
101 10559 : return true;
102 : }
103 : };
104 :
105 : struct pool
106 : {
107 : bucket buckets[num_classes];
108 :
109 : // No destructor: a non-trivial dtor forces a guard variable on the
110 : // thread_local in local(), checked on every alloc/free. Constant
111 : // initialization plus a trivial dtor makes that access a bare TLS
112 : // load. Cached blocks are instead reclaimed explicitly: per-thread
113 : // by arm_thread_cleanup() at thread exit, and the global pool by
114 : // global()'s holder destructor at process exit.
115 : };
116 :
117 32993 : static pool& local() noexcept
118 : {
119 : static thread_local pool p;
120 32993 : return p;
121 : }
122 :
123 : static pool& global() noexcept;
124 : static std::mutex& global_mutex() noexcept;
125 :
126 : void* allocate_slow(std::size_t rounded, std::size_t idx);
127 : void deallocate_slow(void* p, std::size_t idx);
128 :
129 : // Register a thread-exit callback that drains this thread's local
130 : // pool back to the OS. Called only off the hot path: unconditionally
131 : // from the slow paths, and once per thread from deallocate_fast
132 : // behind a guard-free flag.
133 : static void arm_thread_cleanup() noexcept;
134 :
135 : public:
136 : /** Destroy the resource.
137 :
138 : No cached block is released here. Every pool is static, so an
139 : instance holds no state of its own. The thread-local pool is
140 : drained at thread exit, and the global pool at process exit.
141 : */
142 : ~recycling_memory_resource();
143 :
144 : /** Allocate without virtual dispatch.
145 :
146 : Handles the fast path inline (thread-local bucket pop)
147 : and falls through to the slow path for global pool or
148 : heap allocation.
149 :
150 : A request larger than the largest size class (2048 bytes)
151 : bypasses the pools and goes straight to `::operator new`.
152 :
153 : The second parameter is the requested alignment, and it is ignored.
154 : Every block comes from `::operator new`, so blocks carry the
155 : implementation's default new alignment and no more.
156 :
157 : @param bytes The number of bytes to allocate.
158 :
159 : @return A pointer to a block of at least `bytes` bytes. A pooled
160 : block is rounded up to its size class, so it may be larger than
161 : requested.
162 :
163 : @throws std::bad_alloc If the underlying `::operator new` fails.
164 : */
165 : void*
166 12766 : allocate_fast(std::size_t bytes, std::size_t)
167 : {
168 12766 : std::size_t rounded = round_up_pow2(bytes);
169 12766 : std::size_t idx = get_class_index(rounded);
170 12766 : if(idx >= num_classes)
171 MIS 0 : return ::operator new(bytes);
172 HIT 12766 : auto& lp = local();
173 12766 : if(auto* p = lp.buckets[idx].pop())
174 5594 : return p;
175 7172 : return allocate_slow(rounded, idx);
176 : }
177 :
178 : /** Deallocate without virtual dispatch.
179 :
180 : Handles the fast path inline (thread-local bucket push)
181 : and falls through to the slow path for global pool or
182 : heap deallocation.
183 :
184 : The block is cached in the pool of the thread that frees it, not
185 : the thread that allocated it.
186 :
187 : The third parameter is the alignment the block was allocated with,
188 : and it is ignored, as it is on allocation.
189 :
190 : @param p The block to return. It must have come from
191 : @ref allocate_fast or @ref do_allocate on this resource.
192 :
193 : @param bytes The size the block was allocated with. The size class
194 : is recomputed from it, so passing a different value puts the block
195 : in the wrong bucket.
196 : */
197 : void
198 12766 : deallocate_fast(void* p, std::size_t bytes, std::size_t)
199 : {
200 12766 : std::size_t rounded = round_up_pow2(bytes);
201 12766 : std::size_t idx = get_class_index(rounded);
202 12766 : if(idx >= num_classes)
203 : {
204 MIS 0 : ::operator delete(p);
205 0 : return;
206 : }
207 : // Guard-free flag (constinit bool, trivial dtor): arms thread-exit
208 : // cleanup exactly once for any thread that caches via deallocate,
209 : // including consumer threads that never hit a slow path.
210 : static thread_local bool armed = false;
211 HIT 12766 : if(!armed)
212 : {
213 283 : armed = true;
214 283 : arm_thread_cleanup();
215 : }
216 12766 : auto& lp = local();
217 12766 : if(lp.buckets[idx].push(p))
218 6364 : return;
219 6402 : deallocate_slow(p, idx);
220 : }
221 :
222 : protected:
223 : /** Allocate through the `std::pmr::memory_resource` interface.
224 :
225 : Forwards to @ref allocate_fast, so it has that function's contract.
226 : Call `allocate_fast` directly to skip the virtual dispatch.
227 :
228 : @param bytes The number of bytes to allocate.
229 :
230 : @param alignment The requested alignment. It is ignored.
231 :
232 : @return A pointer to a block of at least `bytes` bytes.
233 :
234 : @throws std::bad_alloc If the underlying `::operator new` fails.
235 : */
236 : void*
237 : do_allocate(std::size_t bytes, std::size_t alignment) override;
238 :
239 : /** Deallocate through the `std::pmr::memory_resource` interface.
240 :
241 : Forwards to @ref deallocate_fast, so it has that function's
242 : contract.
243 :
244 : @param p The block to return, as obtained from this resource.
245 :
246 : @param bytes The size the block was allocated with.
247 :
248 : @param alignment The alignment the block was allocated with. It is
249 : ignored.
250 : */
251 : void
252 : do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override;
253 :
254 : /** Compare this resource with another for equality.
255 :
256 : Equality is object identity: two distinct
257 : `recycling_memory_resource` objects compare unequal, even though the
258 : pools they draw from are static and therefore shared.
259 :
260 : @param other The resource to compare against.
261 :
262 : @return `true` if `other` is the same object as `*this`; otherwise
263 : `false`.
264 : */
265 : bool
266 2 : do_is_equal(const memory_resource& other) const noexcept override
267 : {
268 2 : return this == &other;
269 : }
270 : };
271 : BOOST_CAPY_MSVC_WARNING_POP
272 :
273 : /** Returns pointer to the default recycling memory resource.
274 :
275 : The returned pointer is valid for the lifetime of the program.
276 : This is the default allocator used by run_async.
277 :
278 : @return Pointer to the recycling memory resource.
279 :
280 : @see recycling_memory_resource
281 : @see run_async
282 : */
283 : BOOST_CAPY_DECL
284 : std::pmr::memory_resource*
285 : get_recycling_memory_resource() noexcept;
286 :
287 : } // namespace capy
288 : } // namespace boost
289 :
290 : #endif
|
