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