. /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   // 4   //
4   // Distributed under the Boost Software License, Version 1.0. (See accompanying 5   // Distributed under the Boost Software License, Version 1.0. (See accompanying
5   // 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)
6   // 7   //
7   // Official repository: https://github.com/cppalliance/capy 8   // Official repository: https://github.com/cppalliance/capy
8   // 9   //
9   10  
10   #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP 11   #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
11   #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP 12   #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12   13  
13   #include <boost/capy/detail/config.hpp> 14   #include <boost/capy/detail/config.hpp>
14   15  
15   #include <bit> 16   #include <bit>
16   #include <cstddef> 17   #include <cstddef>
17   #include <memory_resource> 18   #include <memory_resource>
18   #include <mutex> 19   #include <mutex>
19   20  
20   namespace boost { 21   namespace boost {
21   namespace capy { 22   namespace capy {
22   23  
23 - /** Recycling memory resource with size-class buckets. 24 + /** Recycles freed blocks through per-thread pools, with a shared pool for cross-thread reuse.
24   25  
25   This memory resource recycles memory blocks using power-of-two 26   This memory resource recycles memory blocks using power-of-two
26   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
27   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
28   block sharing. 29   block sharing.
29   30  
30   Size classes: 64, 128, 256, 512, 1024, 2048 bytes. 31   Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
31   Allocations larger than 2048 bytes bypass the pools entirely. 32   Allocations larger than 2048 bytes bypass the pools entirely.
32   33  
33   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
34   is specified. 35   is specified.
35   36  
36   @par Thread Safety 37   @par Thread Safety
37   Thread-safe. The thread-local pool requires no synchronization. 38   Thread-safe. The thread-local pool requires no synchronization.
38   The global pool uses a mutex for cross-thread access. 39   The global pool uses a mutex for cross-thread access.
39   40  
40   @par Example 41   @par Example
41   @code 42   @code
42   auto* mr = get_recycling_memory_resource(); 43   auto* mr = get_recycling_memory_resource();
43   run_async(ex, mr)(my_task()); 44   run_async(ex, mr)(my_task());
44   @endcode 45   @endcode
45   46  
46   @see get_recycling_memory_resource 47   @see get_recycling_memory_resource
47   @see run_async 48   @see run_async
48   */ 49   */
49   BOOST_CAPY_MSVC_WARNING_PUSH 50   BOOST_CAPY_MSVC_WARNING_PUSH
50   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class 51   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
51   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
52   { 53   {
53   static constexpr std::size_t num_classes = 6; 54   static constexpr std::size_t num_classes = 6;
54   static constexpr std::size_t min_class_size = 64; // 2^6 55   static constexpr std::size_t min_class_size = 64; // 2^6
55   static constexpr std::size_t max_class_size = 2048; // 2^11 56   static constexpr std::size_t max_class_size = 2048; // 2^11
56   static constexpr std::size_t bucket_capacity = 16; 57   static constexpr std::size_t bucket_capacity = 16;
57   58  
58   static std::size_t 59   static std::size_t
HITCBC 59   25532 round_up_pow2(std::size_t n) noexcept 60   25532 round_up_pow2(std::size_t n) noexcept
60   { 61   {
HITCBC 61   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);
62   } 63   }
63   64  
64   static std::size_t 65   static std::size_t
HITCBC 65   25532 get_class_index(std::size_t rounded) noexcept 66   25532 get_class_index(std::size_t rounded) noexcept
66   { 67   {
HITCBC 67   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 68   25532 return idx < num_classes ? idx : num_classes; 69   25532 return idx < num_classes ? idx : num_classes;
69   } 70   }
70   71  
71   struct bucket 72   struct bucket
72   { 73   {
73   std::size_t count = 0; 74   std::size_t count = 0;
74   void* ptrs[bucket_capacity] = {}; 75   void* ptrs[bucket_capacity] = {};
75   76  
HITCBC 76   17059 void* pop() noexcept 77   17059 void* pop() noexcept
77   { 78   {
HITCBC 78   17059 if(count == 0) 79   17059 if(count == 0)
HITCBC 79   7064 return nullptr; 80   7172 return nullptr;
HITCBC 80   9995 return ptrs[--count]; 81   9887 return ptrs[--count];
81   } 82   }
82   83  
83   // Peter Dimov's idea 84   // Peter Dimov's idea
HITCBC 84   7064 void* pop(bucket& b) noexcept 85   7172 void* pop(bucket& b) noexcept
85   { 86   {
HITCBC 86   7064 if(count == 0) 87   7172 if(count == 0)
HITCBC 87   6382 return nullptr; 88   6500 return nullptr;
HITCBC 88   4869 for(std::size_t i = 0; i < count; ++i) 89   4826 for(std::size_t i = 0; i < count; ++i)
HITCBC 89   4187 b.ptrs[i] = ptrs[i]; 90   4154 b.ptrs[i] = ptrs[i];
HITCBC 90   682 b.count = count - 1; 91   672 b.count = count - 1;
HITCBC 91   682 count = 0; 92   672 count = 0;
HITCBC 92   682 return b.ptrs[b.count]; 93   672 return b.ptrs[b.count];
93   } 94   }
94   95  
HITCBC 95   19083 bool push(void* p) noexcept 96   19168 bool push(void* p) noexcept
96   { 97   {
HITCBC 97   19083 if(count >= bucket_capacity) 98   19168 if(count >= bucket_capacity)
HITCBC 98   8406 return false; 99   8609 return false;
HITCBC 99   10677 ptrs[count++] = p; 100   10559 ptrs[count++] = p;
HITCBC 100   10677 return true; 101   10559 return true;
101   } 102   }
102   }; 103   };
103   104  
104   struct pool 105   struct pool
105   { 106   {
106   bucket buckets[num_classes]; 107   bucket buckets[num_classes];
107   108  
108   // 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
109   // thread_local in local(), checked on every alloc/free. Constant 110   // thread_local in local(), checked on every alloc/free. Constant
110   // initialization plus a trivial dtor makes that access a bare TLS 111   // initialization plus a trivial dtor makes that access a bare TLS
111   // load. Cached blocks are instead reclaimed explicitly: per-thread 112   // load. Cached blocks are instead reclaimed explicitly: per-thread
112   // 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
113   // global()'s holder destructor at process exit. 114   // global()'s holder destructor at process exit.
114   }; 115   };
115   116  
HITCBC 116   32885 static pool& local() noexcept 117   32993 static pool& local() noexcept
117   { 118   {
118   static thread_local pool p; 119   static thread_local pool p;
HITCBC 119   32885 return p; 120   32993 return p;
120   } 121   }
121   122  
122   static pool& global() noexcept; 123   static pool& global() noexcept;
123   static std::mutex& global_mutex() noexcept; 124   static std::mutex& global_mutex() noexcept;
124   125  
125   void* allocate_slow(std::size_t rounded, std::size_t idx); 126   void* allocate_slow(std::size_t rounded, std::size_t idx);
126   void deallocate_slow(void* p, std::size_t idx); 127   void deallocate_slow(void* p, std::size_t idx);
127   128  
128   // Register a thread-exit callback that drains this thread's local 129   // Register a thread-exit callback that drains this thread's local
129   // 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
130   // from the slow paths, and once per thread from deallocate_fast 131   // from the slow paths, and once per thread from deallocate_fast
131   // behind a guard-free flag. 132   // behind a guard-free flag.
132   static void arm_thread_cleanup() noexcept; 133   static void arm_thread_cleanup() noexcept;
133   134  
134   public: 135   public:
  136 + /** Destroy the resource.
  137 +
  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
  140 + drained at thread exit, and the global pool at process exit.
  141 + */
135   ~recycling_memory_resource(); 142   ~recycling_memory_resource();
136   143  
137   /** Allocate without virtual dispatch. 144   /** Allocate without virtual dispatch.
138   145  
139   Handles the fast path inline (thread-local bucket pop) 146   Handles the fast path inline (thread-local bucket pop)
140   and falls through to the slow path for global pool or 147   and falls through to the slow path for global pool or
141   heap allocation. 148   heap allocation.
  149 +
  150 + A request larger than the largest size class (2048 bytes)
  151 + bypasses the pools and goes straight to `::operator new`.
  152 +
  153 + The second parameter is the requested alignment, and it is ignored.
  154 + Every block comes from `::operator new`, so blocks carry the
  155 + implementation's default new alignment and no more.
  156 +
  157 + @param bytes The number of bytes to allocate.
  158 +
  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
  161 + requested.
  162 +
  163 + @throws std::bad_alloc If the underlying `::operator new` fails.
142   */ 164   */
143   void* 165   void*
HITCBC 144   12766 allocate_fast(std::size_t bytes, std::size_t) 166   12766 allocate_fast(std::size_t bytes, std::size_t)
145   { 167   {
HITCBC 146   12766 std::size_t rounded = round_up_pow2(bytes); 168   12766 std::size_t rounded = round_up_pow2(bytes);
HITCBC 147   12766 std::size_t idx = get_class_index(rounded); 169   12766 std::size_t idx = get_class_index(rounded);
HITCBC 148   12766 if(idx >= num_classes) 170   12766 if(idx >= num_classes)
MISUBC 149   ✗ return ::operator new(bytes); 171   ✗ return ::operator new(bytes);
HITCBC 150   12766 auto& lp = local(); 172   12766 auto& lp = local();
HITCBC 151   12766 if(auto* p = lp.buckets[idx].pop()) 173   12766 if(auto* p = lp.buckets[idx].pop())
HITCBC 152   5702 return p; 174   5594 return p;
HITCBC 153   7064 return allocate_slow(rounded, idx); 175   7172 return allocate_slow(rounded, idx);
154   } 176   }
155   177  
156   /** Deallocate without virtual dispatch. 178   /** Deallocate without virtual dispatch.
157   179  
158   Handles the fast path inline (thread-local bucket push) 180   Handles the fast path inline (thread-local bucket push)
159   and falls through to the slow path for global pool or 181   and falls through to the slow path for global pool or
160   heap deallocation. 182   heap deallocation.
  183 +
  184 + The block is cached in the pool of the thread that frees it, not
  185 + the thread that allocated it.
  186 +
  187 + The third parameter is the alignment the block was allocated with,
  188 + and it is ignored, as it is on allocation.
  189 +
  190 + @param p The block to return. It must have come from
  191 + @ref allocate_fast or @ref do_allocate on this resource.
  192 +
  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
  195 + in the wrong bucket.
161   */ 196   */
162   void 197   void
HITCBC 163   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)
164   { 199   {
HITCBC 165   12766 std::size_t rounded = round_up_pow2(bytes); 200   12766 std::size_t rounded = round_up_pow2(bytes);
HITCBC 166   12766 std::size_t idx = get_class_index(rounded); 201   12766 std::size_t idx = get_class_index(rounded);
HITCBC 167   12766 if(idx >= num_classes) 202   12766 if(idx >= num_classes)
168   { 203   {
MISUBC 169   ✗ ::operator delete(p); 204   ✗ ::operator delete(p);
MISUBC 170   ✗ return; 205   ✗ return;
171   } 206   }
172   // Guard-free flag (constinit bool, trivial dtor): arms thread-exit 207   // Guard-free flag (constinit bool, trivial dtor): arms thread-exit
173   // cleanup exactly once for any thread that caches via deallocate, 208   // cleanup exactly once for any thread that caches via deallocate,
174   // including consumer threads that never hit a slow path. 209   // including consumer threads that never hit a slow path.
175   static thread_local bool armed = false; 210   static thread_local bool armed = false;
HITCBC 176   12766 if(!armed) 211   12766 if(!armed)
177   { 212   {
HITCBC 178   283 armed = true; 213   283 armed = true;
HITCBC 179   283 arm_thread_cleanup(); 214   283 arm_thread_cleanup();
180   } 215   }
HITCBC 181   12766 auto& lp = local(); 216   12766 auto& lp = local();
HITCBC 182   12766 if(lp.buckets[idx].push(p)) 217   12766 if(lp.buckets[idx].push(p))
HITCBC 183   6449 return; 218   6364 return;
HITCBC 184   6317 deallocate_slow(p, idx); 219   6402 deallocate_slow(p, idx);
185   } 220   }
186   221  
187   protected: 222   protected:
  223 + /** Allocate through the `std::pmr::memory_resource` interface.
  224 +
  225 + Forwards to @ref allocate_fast, so it has that function's contract.
  226 + Call `allocate_fast` directly to skip the virtual dispatch.
  227 +
  228 + @param bytes The number of bytes to allocate.
  229 +
  230 + @param alignment The requested alignment. It is ignored.
  231 +
  232 + @return A pointer to a block of at least `bytes` bytes.
  233 +
  234 + @throws std::bad_alloc If the underlying `::operator new` fails.
  235 + */
188   void* 236   void*
189 - do_allocate(std::size_t bytes, std::size_t) override; 237 + do_allocate(std::size_t bytes, std::size_t alignment) override;
  238 +
  239 + /** Deallocate through the `std::pmr::memory_resource` interface.
  240 +
  241 + Forwards to @ref deallocate_fast, so it has that function's
  242 + contract.
  243 +
  244 + @param p The block to return, as obtained from this resource.
  245 +
  246 + @param bytes The size the block was allocated with.
190   247  
  248 + @param alignment The alignment the block was allocated with. It is
  249 + ignored.
  250 + */
191   void 251   void
192 - do_deallocate(void* p, std::size_t bytes, std::size_t) override; 252 + do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override;
  253 +
  254 + /** Compare this resource with another for equality.
193   255  
  256 + Equality is object identity: two distinct
  257 + `recycling_memory_resource` objects compare unequal, even though the
  258 + pools they draw from are static and therefore shared.
  259 +
  260 + @param other The resource to compare against.
  261 +
  262 + @return `true` if `other` is the same object as `*this`; otherwise
  263 + `false`.
  264 + */
194   bool 265   bool
HITCBC 195   2 do_is_equal(const memory_resource& other) const noexcept override 266   2 do_is_equal(const memory_resource& other) const noexcept override
196   { 267   {
HITCBC 197   2 return this == &other; 268   2 return this == &other;
198   } 269   }
199   }; 270   };
200   BOOST_CAPY_MSVC_WARNING_POP 271   BOOST_CAPY_MSVC_WARNING_POP
201   272  
202   /** Returns pointer to the default recycling memory resource. 273   /** Returns pointer to the default recycling memory resource.
203   274  
204   The returned pointer is valid for the lifetime of the program. 275   The returned pointer is valid for the lifetime of the program.
205   This is the default allocator used by run_async. 276   This is the default allocator used by run_async.
206   277  
207   @return Pointer to the recycling memory resource. 278   @return Pointer to the recycling memory resource.
208   279  
209   @see recycling_memory_resource 280   @see recycling_memory_resource
210   @see run_async 281   @see run_async
211   */ 282   */
212   BOOST_CAPY_DECL 283   BOOST_CAPY_DECL
213   std::pmr::memory_resource* 284   std::pmr::memory_resource*
214   get_recycling_memory_resource() noexcept; 285   get_recycling_memory_resource() noexcept;
215   286  
216   } // namespace capy 287   } // namespace capy
217   } // namespace boost 288   } // namespace boost
218   289  
219   #endif 290   #endif