. /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   // 3   //
4   // Distributed under the Boost Software License, Version 1.0. (See accompanying 4   // 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) 5   // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6   // 6   //
7   // Official repository: https://github.com/cppalliance/capy 7   // Official repository: https://github.com/cppalliance/capy
8   // 8   //
9   9  
10   #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP 10   #ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
11   #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP 11   #define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12   12  
13   #include <boost/capy/detail/config.hpp> 13   #include <boost/capy/detail/config.hpp>
14   14  
15   #include <bit> 15   #include <bit>
16   #include <cstddef> 16   #include <cstddef>
17   #include <memory_resource> 17   #include <memory_resource>
18   #include <mutex> 18   #include <mutex>
19   19  
20   namespace boost { 20   namespace boost {
21   namespace capy { 21   namespace capy {
22   22  
23   /** Recycling memory resource with size-class buckets. 23   /** Recycling memory resource with size-class buckets.
24   24  
25   This memory resource recycles memory blocks using power-of-two 25   This memory resource recycles memory blocks using power-of-two
26   size classes for O(1) allocation lookup. It maintains a thread-local 26   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 27   pool for fast lock-free access and a global pool for cross-thread
28   block sharing. 28   block sharing.
29   29  
30   Size classes: 64, 128, 256, 512, 1024, 2048 bytes. 30   Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
31   Allocations larger than 2048 bytes bypass the pools entirely. 31   Allocations larger than 2048 bytes bypass the pools entirely.
32   32  
33   This is the default allocator used by run_async when no allocator 33   This is the default allocator used by run_async when no allocator
34   is specified. 34   is specified.
35   35  
36   @par Thread Safety 36   @par Thread Safety
37   Thread-safe. The thread-local pool requires no synchronization. 37   Thread-safe. The thread-local pool requires no synchronization.
38   The global pool uses a mutex for cross-thread access. 38   The global pool uses a mutex for cross-thread access.
39   39  
40   @par Example 40   @par Example
41   @code 41   @code
42   auto* mr = get_recycling_memory_resource(); 42   auto* mr = get_recycling_memory_resource();
43   run_async(ex, mr)(my_task()); 43   run_async(ex, mr)(my_task());
44   @endcode 44   @endcode
45   45  
46   @see get_recycling_memory_resource 46   @see get_recycling_memory_resource
47   @see run_async 47   @see run_async
48   */ 48   */
49   BOOST_CAPY_MSVC_WARNING_PUSH 49   BOOST_CAPY_MSVC_WARNING_PUSH
50   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class 50   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
51   class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource 51   class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
52   { 52   {
53   static constexpr std::size_t num_classes = 6; 53   static constexpr std::size_t num_classes = 6;
54   static constexpr std::size_t min_class_size = 64; // 2^6 54   static constexpr std::size_t min_class_size = 64; // 2^6
55   static constexpr std::size_t max_class_size = 2048; // 2^11 55   static constexpr std::size_t max_class_size = 2048; // 2^11
56   static constexpr std::size_t bucket_capacity = 16; 56   static constexpr std::size_t bucket_capacity = 16;
57   57  
58   static std::size_t 58   static std::size_t
HITCBC 59   29852 round_up_pow2(std::size_t n) noexcept 59   29902 round_up_pow2(std::size_t n) noexcept
60   { 60   {
HITCBC 61   29852 return n <= min_class_size ? min_class_size : std::bit_ceil(n); 61   29902 return n <= min_class_size ? min_class_size : std::bit_ceil(n);
62   } 62   }
63   63  
64   static std::size_t 64   static std::size_t
HITCBC 65   29852 get_class_index(std::size_t rounded) noexcept 65   29902 get_class_index(std::size_t rounded) noexcept
66   { 66   {
HITCBC 67   29852 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6 67   29902 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
HITCBC 68   29852 return idx < num_classes ? idx : num_classes; 68   29902 return idx < num_classes ? idx : num_classes;
69   } 69   }
70   70  
71   struct bucket 71   struct bucket
72   { 72   {
73   std::size_t count = 0; 73   std::size_t count = 0;
74   void* ptrs[bucket_capacity] = {}; 74   void* ptrs[bucket_capacity] = {};
75   75  
HITCBC 76   19221 void* pop() noexcept 76   19247 void* pop() noexcept
77   { 77   {
HITCBC 78   19221 if(count == 0) 78   19247 if(count == 0)
HITCBC 79   6870 return nullptr; 79   7096 return nullptr;
HITCBC 80   12351 return ptrs[--count]; 80   12151 return ptrs[--count];
81   } 81   }
82   82  
83   // Peter Dimov's idea 83   // Peter Dimov's idea
HITCBC 84   6870 void* pop(bucket& b) noexcept 84   7096 void* pop(bucket& b) noexcept
85   { 85   {
HITCBC 86   6870 if(count == 0) 86   7096 if(count == 0)
HITCBC 87   6273 return nullptr; 87   6255 return nullptr;
HITCBC 88   4887 for(std::size_t i = 0; i < count; ++i) 88   5178 for(std::size_t i = 0; i < count; ++i)
HITCBC 89   4290 b.ptrs[i] = ptrs[i]; 89   4337 b.ptrs[i] = ptrs[i];
HITCBC 90   597 b.count = count - 1; 90   841 b.count = count - 1;
HITCBC 91   597 count = 0; 91   841 count = 0;
HITCBC 92   597 return b.ptrs[b.count]; 92   841 return b.ptrs[b.count];
93   } 93   }
94   94  
HITCBC 95   21235 bool push(void* p) noexcept 95   21288 bool push(void* p) noexcept
96   { 96   {
HITCBC 97   21235 if(count >= bucket_capacity) 97   21288 if(count >= bucket_capacity)
HITCBC 98   8287 return false; 98   8296 return false;
HITCBC 99   12948 ptrs[count++] = p; 99   12992 ptrs[count++] = p;
HITCBC 100   12948 return true; 100   12992 return true;
101   } 101   }
102   }; 102   };
103   103  
104   struct pool 104   struct pool
105   { 105   {
106   bucket buckets[num_classes]; 106   bucket buckets[num_classes];
107   107  
108   // No destructor: a non-trivial dtor forces a guard variable on the 108   // No destructor: a non-trivial dtor forces a guard variable on the
109   // thread_local in local(), checked on every alloc/free. Constant 109   // thread_local in local(), checked on every alloc/free. Constant
110   // initialization plus a trivial dtor makes that access a bare TLS 110   // initialization plus a trivial dtor makes that access a bare TLS
111   // load. Cached blocks are instead reclaimed explicitly: per-thread 111   // load. Cached blocks are instead reclaimed explicitly: per-thread
112   // by arm_thread_cleanup() at thread exit, and the global pool by 112   // by arm_thread_cleanup() at thread exit, and the global pool by
113   // global()'s holder destructor at process exit. 113   // global()'s holder destructor at process exit.
114   }; 114   };
115   115  
HITCBC 116   37019 static pool& local() noexcept 116   37296 static pool& local() noexcept
117   { 117   {
118   static thread_local pool p; 118   static thread_local pool p;
HITCBC 119   37019 return p; 119   37296 return p;
120   } 120   }
121   121  
122   static pool& global() noexcept; 122   static pool& global() noexcept;
123   static std::mutex& global_mutex() noexcept; 123   static std::mutex& global_mutex() noexcept;
124   124  
125   void* allocate_slow(std::size_t rounded, std::size_t idx); 125   void* allocate_slow(std::size_t rounded, std::size_t idx);
126   void deallocate_slow(void* p, std::size_t idx); 126   void deallocate_slow(void* p, std::size_t idx);
127   127  
128   // Register a thread-exit callback that drains this thread's local 128   // Register a thread-exit callback that drains this thread's local
129   // pool back to the OS. Called only off the hot path: unconditionally 129   // pool back to the OS. Called only off the hot path: unconditionally
130   // from the slow paths, and once per thread from deallocate_fast 130   // from the slow paths, and once per thread from deallocate_fast
131   // behind a guard-free flag. 131   // behind a guard-free flag.
132   static void arm_thread_cleanup() noexcept; 132   static void arm_thread_cleanup() noexcept;
133   133  
134   public: 134   public:
135   ~recycling_memory_resource(); 135   ~recycling_memory_resource();
136   136  
137   /** Allocate without virtual dispatch. 137   /** Allocate without virtual dispatch.
138   138  
139   Handles the fast path inline (thread-local bucket pop) 139   Handles the fast path inline (thread-local bucket pop)
140   and falls through to the slow path for global pool or 140   and falls through to the slow path for global pool or
141   heap allocation. 141   heap allocation.
142   */ 142   */
143   void* 143   void*
HITCBC 144   14926 allocate_fast(std::size_t bytes, std::size_t) 144   14951 allocate_fast(std::size_t bytes, std::size_t)
145   { 145   {
HITCBC 146   14926 std::size_t rounded = round_up_pow2(bytes); 146   14951 std::size_t rounded = round_up_pow2(bytes);
HITCBC 147   14926 std::size_t idx = get_class_index(rounded); 147   14951 std::size_t idx = get_class_index(rounded);
HITCBC 148   14926 if(idx >= num_classes) 148   14951 if(idx >= num_classes)
MISUBC 149   ✗ return ::operator new(bytes); 149   ✗ return ::operator new(bytes);
HITCBC 150   14926 auto& lp = local(); 150   14951 auto& lp = local();
HITCBC 151   14926 if(auto* p = lp.buckets[idx].pop()) 151   14951 if(auto* p = lp.buckets[idx].pop())
HITCBC 152   8056 return p; 152   7855 return p;
HITCBC 153   6870 return allocate_slow(rounded, idx); 153   7096 return allocate_slow(rounded, idx);
154   } 154   }
155   155  
156   /** Deallocate without virtual dispatch. 156   /** Deallocate without virtual dispatch.
157   157  
158   Handles the fast path inline (thread-local bucket push) 158   Handles the fast path inline (thread-local bucket push)
159   and falls through to the slow path for global pool or 159   and falls through to the slow path for global pool or
160   heap deallocation. 160   heap deallocation.
161   */ 161   */
162   void 162   void
HITCBC 163   14926 deallocate_fast(void* p, std::size_t bytes, std::size_t) 163   14951 deallocate_fast(void* p, std::size_t bytes, std::size_t)
164   { 164   {
HITCBC 165   14926 std::size_t rounded = round_up_pow2(bytes); 165   14951 std::size_t rounded = round_up_pow2(bytes);
HITCBC 166   14926 std::size_t idx = get_class_index(rounded); 166   14951 std::size_t idx = get_class_index(rounded);
HITCBC 167   14926 if(idx >= num_classes) 167   14951 if(idx >= num_classes)
168   { 168   {
MISUBC 169   ✗ ::operator delete(p); 169   ✗ ::operator delete(p);
MISUBC 170   ✗ return; 170   ✗ return;
171   } 171   }
172   // Guard-free flag (constinit bool, trivial dtor): arms thread-exit 172   // Guard-free flag (constinit bool, trivial dtor): arms thread-exit
173   // cleanup exactly once for any thread that caches via deallocate, 173   // cleanup exactly once for any thread that caches via deallocate,
174   // including consumer threads that never hit a slow path. 174   // including consumer threads that never hit a slow path.
175   static thread_local bool armed = false; 175   static thread_local bool armed = false;
HITCBC 176   14926 if(!armed) 176   14951 if(!armed)
177   { 177   {
HITCBC 178   291 armed = true; 178   293 armed = true;
HITCBC 179   291 arm_thread_cleanup(); 179   293 arm_thread_cleanup();
180   } 180   }
HITCBC 181   14926 auto& lp = local(); 181   14951 auto& lp = local();
HITCBC 182   14926 if(lp.buckets[idx].push(p)) 182   14951 if(lp.buckets[idx].push(p))
HITCBC 183   8617 return; 183   8614 return;
HITCBC 184   6309 deallocate_slow(p, idx); 184   6337 deallocate_slow(p, idx);
185   } 185   }
186   186  
187   protected: 187   protected:
188   void* 188   void*
189   do_allocate(std::size_t bytes, std::size_t) override; 189   do_allocate(std::size_t bytes, std::size_t) override;
190   190  
191   void 191   void
192   do_deallocate(void* p, std::size_t bytes, std::size_t) override; 192   do_deallocate(void* p, std::size_t bytes, std::size_t) override;
193   193  
194   bool 194   bool
HITCBC 195   2 do_is_equal(const memory_resource& other) const noexcept override 195   2 do_is_equal(const memory_resource& other) const noexcept override
196   { 196   {
HITCBC 197   2 return this == &other; 197   2 return this == &other;
198   } 198   }
199   }; 199   };
200   BOOST_CAPY_MSVC_WARNING_POP 200   BOOST_CAPY_MSVC_WARNING_POP
201   201  
202   /** Returns pointer to the default recycling memory resource. 202   /** Returns pointer to the default recycling memory resource.
203   203  
204   The returned pointer is valid for the lifetime of the program. 204   The returned pointer is valid for the lifetime of the program.
205   This is the default allocator used by run_async. 205   This is the default allocator used by run_async.
206   206  
207   @return Pointer to the recycling memory resource. 207   @return Pointer to the recycling memory resource.
208   208  
209   @see recycling_memory_resource 209   @see recycling_memory_resource
210   @see run_async 210   @see run_async
211   */ 211   */
212   BOOST_CAPY_DECL 212   BOOST_CAPY_DECL
213   std::pmr::memory_resource* 213   std::pmr::memory_resource*
214   get_recycling_memory_resource() noexcept; 214   get_recycling_memory_resource() noexcept;
215   215  
216   } // namespace capy 216   } // namespace capy
217   } // namespace boost 217   } // namespace boost
218   218  
219   #endif 219   #endif