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