TLA Line data Source code
1 : //
2 : // Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // Official repository: https://github.com/cppalliance/capy
8 : //
9 :
10 : #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
11 : #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12 :
13 : #include <boost/capy/detail/config.hpp>
14 :
15 : #include <bit>
16 : #include <cstddef>
17 : #include <memory_resource>
18 : #include <mutex>
19 :
20 : namespace boost {
21 : namespace capy {
22 :
23 : /** Recycling memory resource with size-class buckets.
24 :
25 : This memory resource recycles memory blocks using power-of-two
26 : size classes for O(1) allocation lookup. It maintains a thread-local
27 : pool for fast lock-free access and a global pool for cross-thread
28 : block sharing.
29 :
30 : Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
31 : Allocations larger than 2048 bytes bypass the pools entirely.
32 :
33 : This is the default allocator used by run_async when no allocator
34 : is specified.
35 :
36 : @note This resource honors only the default new alignment
37 : (`__STDCPP_DEFAULT_NEW_ALIGNMENT__`, typically
38 : `alignof(std::max_align_t)`). The alignment argument passed to
39 : `do_allocate`/`do_deallocate` (and to `allocate_fast`/`deallocate_fast`)
40 : is ignored; backing storage comes from `::operator new`. Over-aligned
41 : requests are therefore not satisfied. This is sufficient for coroutine
42 : frame allocation but means the resource cannot be used where
43 : over-aligned memory is required.
44 :
45 : @par Thread Safety
46 : Thread-safe. The thread-local pool requires no synchronization.
47 : The global pool uses a mutex for cross-thread access.
48 :
49 : @par Example
50 : @code
51 : auto* mr = get_recycling_memory_resource();
52 : run_async(ex, mr)(my_task());
53 : @endcode
54 :
55 : @see get_recycling_memory_resource
56 : @see run_async
57 : */
58 : BOOST_CAPY_MSVC_WARNING_PUSH
59 : BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
60 : class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
61 : {
62 : static constexpr std::size_t num_classes = 6;
63 : static constexpr std::size_t min_class_size = 64; // 2^6
64 : static constexpr std::size_t max_class_size = 2048; // 2^11
65 : static constexpr std::size_t bucket_capacity = 16;
66 :
67 : static std::size_t
68 HIT 10458 : round_up_pow2(std::size_t n) noexcept
69 : {
70 10458 : return n <= min_class_size ? min_class_size : std::bit_ceil(n);
71 : }
72 :
73 : static std::size_t
74 10458 : get_class_index(std::size_t rounded) noexcept
75 : {
76 10458 : std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
77 10458 : return idx < num_classes ? idx : num_classes;
78 : }
79 :
80 : struct bucket
81 : {
82 : std::size_t count = 0;
83 : void* ptrs[bucket_capacity];
84 :
85 5413 : void* pop() noexcept
86 : {
87 5413 : if(count == 0)
88 221 : return nullptr;
89 5192 : return ptrs[--count];
90 : }
91 :
92 : // Peter Dimov's idea
93 221 : void* pop(bucket& b) noexcept
94 : {
95 221 : if(count == 0)
96 220 : return nullptr;
97 17 : for(std::size_t i = 0; i < count; ++i)
98 16 : b.ptrs[i] = ptrs[i];
99 1 : b.count = count - 1;
100 1 : count = 0;
101 1 : return b.ptrs[b.count];
102 : }
103 :
104 5306 : bool push(void* p) noexcept
105 : {
106 5306 : if(count >= bucket_capacity)
107 113 : return false;
108 5193 : ptrs[count++] = p;
109 5193 : return true;
110 : }
111 : };
112 :
113 : struct pool
114 : {
115 : bucket buckets[num_classes];
116 :
117 82 : ~pool()
118 : {
119 574 : for(auto& b : buckets)
120 676 : while(b.count > 0)
121 184 : ::operator delete(b.pop());
122 82 : }
123 : };
124 :
125 10679 : static pool& local() noexcept
126 : {
127 10679 : static thread_local pool p;
128 10679 : return p;
129 : }
130 :
131 : static pool& global() noexcept;
132 : static std::mutex& global_mutex() noexcept;
133 :
134 : void* allocate_slow(std::size_t rounded, std::size_t idx);
135 : void deallocate_slow(void* p, std::size_t idx);
136 :
137 : public:
138 : /** Destructor.
139 :
140 : Releases any blocks still held in this resource's thread-local
141 : pool for the calling thread. Blocks held in the process-wide
142 : global pool, and in other threads' thread-local pools, are
143 : released when those pools are destroyed.
144 : */
145 : ~recycling_memory_resource();
146 :
147 : /** Allocate without virtual dispatch.
148 :
149 : Handles the fast path inline (thread-local bucket pop)
150 : and falls through to the slow path for global pool or
151 : heap allocation.
152 :
153 : @param bytes The number of bytes to allocate.
154 :
155 : @return A pointer to the allocated storage.
156 :
157 : @note The second (alignment) argument is ignored; only the
158 : default new alignment is honored. See the class-level note.
159 : */
160 : void*
161 5229 : allocate_fast(std::size_t bytes, std::size_t /*alignment*/)
162 : {
163 5229 : std::size_t rounded = round_up_pow2(bytes);
164 5229 : std::size_t idx = get_class_index(rounded);
165 5229 : if(idx >= num_classes)
166 MIS 0 : return ::operator new(bytes);
167 HIT 5229 : auto& lp = local();
168 5229 : if(auto* p = lp.buckets[idx].pop())
169 5008 : return p;
170 221 : return allocate_slow(rounded, idx);
171 : }
172 :
173 : /** Deallocate without virtual dispatch.
174 :
175 : Handles the fast path inline (thread-local bucket push)
176 : and falls through to the slow path for global pool or
177 : heap deallocation.
178 :
179 : @param p Pointer previously returned by `allocate_fast`
180 : (or `do_allocate`) on a resource that compares equal to this one.
181 :
182 : @param bytes The size, in bytes, originally requested for `p`.
183 :
184 : @note The third (alignment) argument is ignored; only the
185 : default new alignment is honored. See the class-level note.
186 : */
187 : void
188 5229 : deallocate_fast(void* p, std::size_t bytes, std::size_t /*alignment*/)
189 : {
190 5229 : std::size_t rounded = round_up_pow2(bytes);
191 5229 : std::size_t idx = get_class_index(rounded);
192 5229 : if(idx >= num_classes)
193 : {
194 MIS 0 : ::operator delete(p);
195 0 : return;
196 : }
197 HIT 5229 : auto& lp = local();
198 5229 : if(lp.buckets[idx].push(p))
199 5152 : return;
200 77 : deallocate_slow(p, idx);
201 : }
202 :
203 : protected:
204 : /** Allocate storage (`std::pmr::memory_resource` interface).
205 :
206 : Forwards to `allocate_fast`. The alignment argument is ignored;
207 : see the class-level note.
208 :
209 : @param bytes The number of bytes to allocate.
210 :
211 : @return A pointer to the allocated storage.
212 : */
213 : void*
214 : do_allocate(std::size_t bytes, std::size_t /*alignment*/) override;
215 :
216 : /** Deallocate storage (`std::pmr::memory_resource` interface).
217 :
218 : Forwards to `deallocate_fast`. The alignment argument is ignored;
219 : see the class-level note.
220 :
221 : @param p Pointer previously returned by `do_allocate`.
222 :
223 : @param bytes The size, in bytes, originally requested for `p`.
224 : */
225 : void
226 : do_deallocate(void* p, std::size_t bytes, std::size_t /*alignment*/) override;
227 :
228 : bool
229 2 : do_is_equal(const memory_resource& other) const noexcept override
230 : {
231 2 : return this == &other;
232 : }
233 : };
234 : BOOST_CAPY_MSVC_WARNING_POP
235 :
236 : /** Returns pointer to the default recycling memory resource.
237 :
238 : The returned pointer is valid for the lifetime of the program.
239 : This is the default allocator used by run_async.
240 :
241 : @return Pointer to the recycling memory resource.
242 :
243 : @see recycling_memory_resource
244 : @see run_async
245 : */
246 : BOOST_CAPY_DECL
247 : std::pmr::memory_resource*
248 : get_recycling_memory_resource() noexcept;
249 :
250 : } // namespace capy
251 : } // namespace boost
252 :
253 : #endif
|
