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