. /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   25488 round_up_pow2(std::size_t n) noexcept 58   433208 round_up_pow2(std::size_t n) noexcept
59   { 59   {
HITCBC 60   25488 return n <= min_class_size ? min_class_size : std::bit_ceil(n); 60   433208 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   25488 get_class_index(std::size_t rounded) noexcept 64   433208 get_class_index(std::size_t rounded) noexcept
65   { 65   {
HITCBC 66   25488 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6 66   433208 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
HITCBC 67   25488 return idx < num_classes ? idx : num_classes; 67   433208 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   17037 void* pop() noexcept 75   221263 void* pop() noexcept
76   { 76   {
HITCBC 77   17037 if(count == 0) 77   221263 if(count == 0)
HITCBC 78   6921 return nullptr; 78   210221 return nullptr;
HITCBC 79   10116 return ptrs[--count]; 79   11042 return ptrs[--count];
80   } 80   }
81   81  
82   // Peter Dimov's idea 82   // Peter Dimov's idea
HITCBC 83   6921 void* pop(bucket& b) noexcept 83   210220 void* pop(bucket& b) noexcept
84   { 84   {
HITCBC 85   6921 if(count == 0) 85   210220 if(count == 0)
HITCBC 86   6398 return nullptr; 86   209831 return nullptr;
HITCBC 87   4705 for(std::size_t i = 0; i < count; ++i) 87   4622 for(std::size_t i = 0; i < count; ++i)
HITCBC 88   4182 b.ptrs[i] = ptrs[i]; 88   4233 b.ptrs[i] = ptrs[i];
HITCBC 89   523 b.count = count - 1; 89   389 b.count = count - 1;
HITCBC 90   523 count = 0; 90   389 count = 0;
HITCBC 91   523 return b.ptrs[b.count]; 91   389 return b.ptrs[b.count];
92   } 92   }
93   93  
HITCBC 94   19072 bool push(void* p) noexcept 94   426130 bool push(void* p) noexcept
95   { 95   {
HITCBC 96   19072 if(count >= bucket_capacity) 96   426130 if(count >= bucket_capacity)
HITCBC 97   8433 return false; 97   414699 return false;
HITCBC 98   10639 ptrs[count++] = p; 98   11431 ptrs[count++] = p;
HITCBC 99   10639 return true; 99   11431 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)) && \
  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
ECB 115   32698 static pool& local() noexcept 122   static pool& local() noexcept
116   { 123   {
117   static thread_local pool p; 124   static thread_local pool p;
ECB 118   32698 return p; 125   return p;
119   } 126   }
  127 + #endif
120   128  
121   static pool& global() noexcept; 129   static pool& global() noexcept;
122   static std::mutex& global_mutex() noexcept; 130   static std::mutex& global_mutex() noexcept;
123   131  
124   void* allocate_slow(std::size_t rounded, std::size_t idx); 132   void* allocate_slow(std::size_t rounded, std::size_t idx);
125   void deallocate_slow(void* p, std::size_t idx); 133   void deallocate_slow(void* p, std::size_t idx);
126   134  
127   // Register a thread-exit callback that drains this thread's local 135   // Register a thread-exit callback that drains this thread's local
128   // 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
129 - // from the slow paths, and once per thread from deallocate_fast 137 + // from the slow paths, and from deallocate_fast while the flag below
130 - // behind a guard-free flag. 138 + // is clear. Returns false once that callback has run: nothing drains
131 - static void arm_thread_cleanup() noexcept; 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
132   154  
133   public: 155   public:
134   /** Destroy the resource. 156   /** Destroy the resource.
135   157  
136   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
137   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
138   drained at thread exit, and the global pool at process exit. 160   drained at thread exit, and the global pool at process exit.
139   */ 161   */
140   ~recycling_memory_resource(); 162   ~recycling_memory_resource();
141   163  
142   /** Allocate without virtual dispatch. 164   /** Allocate without virtual dispatch.
143   165  
144   Handles the fast path inline (thread-local bucket pop) 166   Handles the fast path inline (thread-local bucket pop)
145   and falls through to the slow path for global pool or 167   and falls through to the slow path for global pool or
146   heap allocation. 168   heap allocation.
147   169  
148   A request larger than the largest size class (2048 bytes) 170   A request larger than the largest size class (2048 bytes)
149   bypasses the pools and goes straight to `::operator new`. 171   bypasses the pools and goes straight to `::operator new`.
150   172  
151   The second parameter is the requested alignment, and it is ignored. 173   The second parameter is the requested alignment, and it is ignored.
152   Every block comes from `::operator new`, so blocks carry the 174   Every block comes from `::operator new`, so blocks carry the
153   implementation's default new alignment and no more. 175   implementation's default new alignment and no more.
154   176  
155   @param bytes The number of bytes to allocate. 177   @param bytes The number of bytes to allocate.
156   178  
157   @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
158   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
159   requested. 181   requested.
160   182  
161   @throws std::bad_alloc If the underlying `::operator new` fails. 183   @throws std::bad_alloc If the underlying `::operator new` fails.
162   */ 184   */
163   void* 185   void*
HITCBC 164   12744 allocate_fast(std::size_t bytes, std::size_t) 186   216604 allocate_fast(std::size_t bytes, std::size_t)
165   { 187   {
HITCBC 166   12744 std::size_t rounded = round_up_pow2(bytes); 188   216604 std::size_t rounded = round_up_pow2(bytes);
HITCBC 167   12744 std::size_t idx = get_class_index(rounded); 189   216604 std::size_t idx = get_class_index(rounded);
HITCBC 168   12744 if(idx >= num_classes) 190   216604 if(idx >= num_classes)
MISUBC 169   ✗ return ::operator new(bytes); 191   ✗ return ::operator new(bytes);
HITCBC 170   12744 auto& lp = local(); 192   216604 auto& lp = local();
HITCBC 171   12744 if(auto* p = lp.buckets[idx].pop()) 193   216604 if(auto* p = lp.buckets[idx].pop())
HITCBC 172   5823 return p; 194   6383 return p;
HITCBC 173   6921 return allocate_slow(rounded, idx); 195   210221 return allocate_slow(rounded, idx);
174   } 196   }
175   197  
176   /** Deallocate without virtual dispatch. 198   /** Deallocate without virtual dispatch.
177   199  
178   Handles the fast path inline (thread-local bucket push) 200   Handles the fast path inline (thread-local bucket push)
179   and falls through to the slow path for global pool or 201   and falls through to the slow path for global pool or
180   heap deallocation. 202   heap deallocation.
181   203  
182   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
183   the thread that allocated it. 205   the thread that allocated it.
184   206  
185   The third parameter is the alignment the block was allocated with, 207   The third parameter is the alignment the block was allocated with,
186   and it is ignored, as it is on allocation. 208   and it is ignored, as it is on allocation.
187   209  
188   @param p The block to return. It must have come from 210   @param p The block to return. It must have come from
189   @ref allocate_fast or @ref do_allocate on this resource. 211   @ref allocate_fast or @ref do_allocate on this resource.
190   212  
191   @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
192   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
193   in the wrong bucket. 215   in the wrong bucket.
194   */ 216   */
195   void 217   void
HITCBC 196   12744 deallocate_fast(void* p, std::size_t bytes, std::size_t) 218   216604 deallocate_fast(void* p, std::size_t bytes, std::size_t)
197   { 219   {
HITCBC 198   12744 std::size_t rounded = round_up_pow2(bytes); 220   216604 std::size_t rounded = round_up_pow2(bytes);
HITCBC 199   12744 std::size_t idx = get_class_index(rounded); 221   216604 std::size_t idx = get_class_index(rounded);
HITCBC 200   12744 if(idx >= num_classes) 222   216604 if(idx >= num_classes)
201   { 223   {
MISUBC 202   ✗ ::operator delete(p); 224   ✗ ::operator delete(p);
MISUBC 203   ✗ return; 225   ✗ return;
204   } 226   }
205 - // Guard-free flag (constinit bool, trivial dtor): arms thread-exit 227 + // Arms thread-exit cleanup for any thread that caches via
206 - // cleanup exactly once for any thread that caches via deallocate, 228 + // deallocate, including consumer threads that never hit a slow
207 - // including consumer threads that never hit a slow path. 229 + // path; after that cleanup, the block bypasses the local pool.
HITGIC 208 - static thread_local bool armed = false; 230 + 216604 auto& armed = thread_armed();
HITCBC 209   12744 if(!armed) 231   216604 if(!armed)
210   { 232   {
HITGNC   233 + 360 if(!arm_thread_cleanup())
  234 + {
HITGNC   235 + 4 deallocate_slow(p, idx);
HITGNC   236 + 4 return;
  237 + }
DCB 211 - 283 arm_thread_cleanup();  
HITCBC 212   283 armed = true; 238   356 armed = true;
213   } 239   }
HITCBC 214   12744 auto& lp = local(); 240   216600 auto& lp = local();
HITCBC 215   12744 if(lp.buckets[idx].push(p)) 241   216600 if(lp.buckets[idx].push(p))
HITCBC 216   6416 return; 242   7074 return;
HITCBC 217   6328 deallocate_slow(p, idx); 243   209526 deallocate_slow(p, idx);
218   } 244   }
219   245  
220   protected: 246   protected:
221   /** Allocate through the `std::pmr::memory_resource` interface. 247   /** Allocate through the `std::pmr::memory_resource` interface.
222   248  
223   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.
224   Call `allocate_fast` directly to skip the virtual dispatch. 250   Call `allocate_fast` directly to skip the virtual dispatch.
225   251  
226   @param bytes The number of bytes to allocate. 252   @param bytes The number of bytes to allocate.
227   253  
228   @param alignment The requested alignment. It is ignored. 254   @param alignment The requested alignment. It is ignored.
229   255  
230   @return A pointer to a block of at least `bytes` bytes. 256   @return A pointer to a block of at least `bytes` bytes.
231   257  
232   @throws std::bad_alloc If the underlying `::operator new` fails. 258   @throws std::bad_alloc If the underlying `::operator new` fails.
233   */ 259   */
234   void* 260   void*
235   do_allocate(std::size_t bytes, std::size_t alignment) override; 261   do_allocate(std::size_t bytes, std::size_t alignment) override;
236   262  
237   /** Deallocate through the `std::pmr::memory_resource` interface. 263   /** Deallocate through the `std::pmr::memory_resource` interface.
238   264  
239   Forwards to @ref deallocate_fast, so it has that function's 265   Forwards to @ref deallocate_fast, so it has that function's
240   contract. 266   contract.
241   267  
242   @param p The block to return, as obtained from this resource. 268   @param p The block to return, as obtained from this resource.
243   269  
244   @param bytes The size the block was allocated with. 270   @param bytes The size the block was allocated with.
245   271  
246   @param alignment The alignment the block was allocated with. It is 272   @param alignment The alignment the block was allocated with. It is
247   ignored. 273   ignored.
248   */ 274   */
249   void 275   void
250   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;
251   277  
252   /** Compare this resource with another for equality. 278   /** Compare this resource with another for equality.
253   279  
254   Equality is object identity: two distinct 280   Equality is object identity: two distinct
255   `recycling_memory_resource` objects compare unequal, even though the 281   `recycling_memory_resource` objects compare unequal, even though the
256   pools they draw from are static and therefore shared. 282   pools they draw from are static and therefore shared.
257   283  
258   @param other The resource to compare against. 284   @param other The resource to compare against.
259   285  
260   @return `true` if `other` is the same object as `*this`; otherwise 286   @return `true` if `other` is the same object as `*this`; otherwise
261   `false`. 287   `false`.
262   */ 288   */
263   bool 289   bool
HITCBC 264   2 do_is_equal(const memory_resource& other) const noexcept override 290   2 do_is_equal(const memory_resource& other) const noexcept override
265   { 291   {
HITCBC 266   2 return this == &other; 292   2 return this == &other;
267   } 293   }
268   }; 294   };
269   BOOST_CAPY_MSVC_WARNING_POP 295   BOOST_CAPY_MSVC_WARNING_POP
270   296  
271   /** Returns pointer to the default recycling memory resource. 297   /** Returns pointer to the default recycling memory resource.
272   298  
273   The returned pointer is valid for the lifetime of the program. 299   The returned pointer is valid for the lifetime of the program.
274   This is the default allocator used by run_async. 300   This is the default allocator used by run_async.
275   301  
276   @return Pointer to the recycling memory resource. 302   @return Pointer to the recycling memory resource.
277   303  
278   @see recycling_memory_resource 304   @see recycling_memory_resource
279   @see run_async 305   @see run_async
280   */ 306   */
281   BOOST_CAPY_DECL 307   BOOST_CAPY_DECL
282   std::pmr::memory_resource* 308   std::pmr::memory_resource*
283   get_recycling_memory_resource() noexcept; 309   get_recycling_memory_resource() noexcept;
284   310  
285   } // namespace capy 311   } // namespace capy
286   } // namespace boost 312   } // namespace boost
287   313  
288   #endif 314   #endif