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