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