. /include/boost/capy /ex /recycling_memory_resource.hpp
94.12% Lines (48/51) 100.00% Functions (10/10)
[ ] 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 + @note This resource honors only the default new alignment
  37 + (`__STDCPP_DEFAULT_NEW_ALIGNMENT__`, typically
  38 + `alignof(std::max_align_t)`). The alignment argument passed to
  39 + `do_allocate`/`do_deallocate` (and to `allocate_fast`/`deallocate_fast`)
  40 + is ignored; backing storage comes from `::operator new`. Over-aligned
  41 + requests are therefore not satisfied. This is sufficient for coroutine
  42 + frame allocation but means the resource cannot be used where
  43 + over-aligned memory is required.
  44 +
36   @par Thread Safety 45   @par Thread Safety
37   Thread-safe. The thread-local pool requires no synchronization. 46   Thread-safe. The thread-local pool requires no synchronization.
38   The global pool uses a mutex for cross-thread access. 47   The global pool uses a mutex for cross-thread access.
39   48  
40   @par Example 49   @par Example
41   @code 50   @code
42   auto* mr = get_recycling_memory_resource(); 51   auto* mr = get_recycling_memory_resource();
43   run_async(ex, mr)(my_task()); 52   run_async(ex, mr)(my_task());
44   @endcode 53   @endcode
45   54  
46   @see get_recycling_memory_resource 55   @see get_recycling_memory_resource
47   @see run_async 56   @see run_async
48   */ 57   */
49   BOOST_CAPY_MSVC_WARNING_PUSH 58   BOOST_CAPY_MSVC_WARNING_PUSH
50   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class 59   BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
51   class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource 60   class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
52   { 61   {
53   static constexpr std::size_t num_classes = 6; 62   static constexpr std::size_t num_classes = 6;
54   static constexpr std::size_t min_class_size = 64; // 2^6 63   static constexpr std::size_t min_class_size = 64; // 2^6
55   static constexpr std::size_t max_class_size = 2048; // 2^11 64   static constexpr std::size_t max_class_size = 2048; // 2^11
56   static constexpr std::size_t bucket_capacity = 16; 65   static constexpr std::size_t bucket_capacity = 16;
57   66  
58   static std::size_t 67   static std::size_t
HITCBC 59   10520 round_up_pow2(std::size_t n) noexcept 68   10458 round_up_pow2(std::size_t n) noexcept
60   { 69   {
HITCBC 61   10520 return n <= min_class_size ? min_class_size : std::bit_ceil(n); 70   10458 return n <= min_class_size ? min_class_size : std::bit_ceil(n);
62   } 71   }
63   72  
64   static std::size_t 73   static std::size_t
HITCBC 65   10520 get_class_index(std::size_t rounded) noexcept 74   10458 get_class_index(std::size_t rounded) noexcept
66   { 75   {
HITCBC 67   10520 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6 76   10458 std::size_t idx = std::countr_zero(rounded) - 6; // 64 = 2^6
HITCBC 68   10520 return idx < num_classes ? idx : num_classes; 77   10458 return idx < num_classes ? idx : num_classes;
69   } 78   }
70   79  
71   struct bucket 80   struct bucket
72   { 81   {
73   std::size_t count = 0; 82   std::size_t count = 0;
74   void* ptrs[bucket_capacity]; 83   void* ptrs[bucket_capacity];
75   84  
HITCBC 76   5445 void* pop() noexcept 85   5413 void* pop() noexcept
77   { 86   {
HITCBC 78   5445 if(count == 0) 87   5413 if(count == 0)
HITCBC 79   222 return nullptr; 88   221 return nullptr;
HITCBC 80   5223 return ptrs[--count]; 89   5192 return ptrs[--count];
81   } 90   }
82   91  
83   // Peter Dimov's idea 92   // Peter Dimov's idea
HITCBC 84   222 void* pop(bucket& b) noexcept 93   221 void* pop(bucket& b) noexcept
85   { 94   {
HITCBC 86   222 if(count == 0) 95   221 if(count == 0)
HITCBC 87   221 return nullptr; 96   220 return nullptr;
HITCBC 88   17 for(std::size_t i = 0; i < count; ++i) 97   17 for(std::size_t i = 0; i < count; ++i)
HITCBC 89   16 b.ptrs[i] = ptrs[i]; 98   16 b.ptrs[i] = ptrs[i];
HITCBC 90   1 b.count = count - 1; 99   1 b.count = count - 1;
HITCBC 91   1 count = 0; 100   1 count = 0;
HITCBC 92   1 return b.ptrs[b.count]; 101   1 return b.ptrs[b.count];
93   } 102   }
94   103  
HITCBC 95   5337 bool push(void* p) noexcept 104   5306 bool push(void* p) noexcept
96   { 105   {
HITCBC 97   5337 if(count >= bucket_capacity) 106   5306 if(count >= bucket_capacity)
HITCBC 98   113 return false; 107   113 return false;
HITCBC 99   5224 ptrs[count++] = p; 108   5193 ptrs[count++] = p;
HITCBC 100   5224 return true; 109   5193 return true;
101   } 110   }
102   }; 111   };
103   112  
104   struct pool 113   struct pool
105   { 114   {
106   bucket buckets[num_classes]; 115   bucket buckets[num_classes];
107   116  
HITCBC 108   82 ~pool() 117   82 ~pool()
109   { 118   {
HITCBC 110   574 for(auto& b : buckets) 119   574 for(auto& b : buckets)
HITCBC 111   677 while(b.count > 0) 120   676 while(b.count > 0)
HITCBC 112   185 ::operator delete(b.pop()); 121   184 ::operator delete(b.pop());
HITCBC 113   82 } 122   82 }
114   }; 123   };
115   124  
HITCBC 116   10742 static pool& local() noexcept 125   10679 static pool& local() noexcept
117   { 126   {
HITCBC 118   10742 static thread_local pool p; 127   10679 static thread_local pool p;
HITCBC 119   10742 return p; 128   10679 return p;
120   } 129   }
121   130  
122   static pool& global() noexcept; 131   static pool& global() noexcept;
123   static std::mutex& global_mutex() noexcept; 132   static std::mutex& global_mutex() noexcept;
124   133  
125   void* allocate_slow(std::size_t rounded, std::size_t idx); 134   void* allocate_slow(std::size_t rounded, std::size_t idx);
126   void deallocate_slow(void* p, std::size_t idx); 135   void deallocate_slow(void* p, std::size_t idx);
127   136  
128   public: 137   public:
  138 + /** Destructor.
  139 +
  140 + Releases any blocks still held in this resource's thread-local
  141 + pool for the calling thread. Blocks held in the process-wide
  142 + global pool, and in other threads' thread-local pools, are
  143 + released when those pools are destroyed.
  144 + */
129   ~recycling_memory_resource(); 145   ~recycling_memory_resource();
130   146  
131   /** Allocate without virtual dispatch. 147   /** Allocate without virtual dispatch.
132   148  
133   Handles the fast path inline (thread-local bucket pop) 149   Handles the fast path inline (thread-local bucket pop)
134   and falls through to the slow path for global pool or 150   and falls through to the slow path for global pool or
135   heap allocation. 151   heap allocation.
  152 +
  153 + @param bytes The number of bytes to allocate.
  154 +
  155 + @return A pointer to the allocated storage.
  156 +
  157 + @note The second (alignment) argument is ignored; only the
  158 + default new alignment is honored. See the class-level note.
136   */ 159   */
137   void* 160   void*
HITCBC 138 - 5260 allocate_fast(std::size_t bytes, std::size_t) 161 + 5229 allocate_fast(std::size_t bytes, std::size_t /*alignment*/)
139   { 162   {
HITCBC 140   5260 std::size_t rounded = round_up_pow2(bytes); 163   5229 std::size_t rounded = round_up_pow2(bytes);
HITCBC 141   5260 std::size_t idx = get_class_index(rounded); 164   5229 std::size_t idx = get_class_index(rounded);
HITCBC 142   5260 if(idx >= num_classes) 165   5229 if(idx >= num_classes)
MISUBC 143   ✗ return ::operator new(bytes); 166   ✗ return ::operator new(bytes);
HITCBC 144   5260 auto& lp = local(); 167   5229 auto& lp = local();
HITCBC 145   5260 if(auto* p = lp.buckets[idx].pop()) 168   5229 if(auto* p = lp.buckets[idx].pop())
HITCBC 146   5038 return p; 169   5008 return p;
HITCBC 147   222 return allocate_slow(rounded, idx); 170   221 return allocate_slow(rounded, idx);
148   } 171   }
149   172  
150   /** Deallocate without virtual dispatch. 173   /** Deallocate without virtual dispatch.
151   174  
152   Handles the fast path inline (thread-local bucket push) 175   Handles the fast path inline (thread-local bucket push)
153   and falls through to the slow path for global pool or 176   and falls through to the slow path for global pool or
154   heap deallocation. 177   heap deallocation.
  178 +
  179 + @param p Pointer previously returned by `allocate_fast`
  180 + (or `do_allocate`) on a resource that compares equal to this one.
  181 +
  182 + @param bytes The size, in bytes, originally requested for `p`.
  183 +
  184 + @note The third (alignment) argument is ignored; only the
  185 + default new alignment is honored. See the class-level note.
155   */ 186   */
156   void 187   void
HITCBC 157 - 5260 deallocate_fast(void* p, std::size_t bytes, std::size_t) 188 + 5229 deallocate_fast(void* p, std::size_t bytes, std::size_t /*alignment*/)
158   { 189   {
HITCBC 159   5260 std::size_t rounded = round_up_pow2(bytes); 190   5229 std::size_t rounded = round_up_pow2(bytes);
HITCBC 160   5260 std::size_t idx = get_class_index(rounded); 191   5229 std::size_t idx = get_class_index(rounded);
HITCBC 161   5260 if(idx >= num_classes) 192   5229 if(idx >= num_classes)
162   { 193   {
MISUBC 163   ✗ ::operator delete(p); 194   ✗ ::operator delete(p);
MISUBC 164   ✗ return; 195   ✗ return;
165   } 196   }
HITCBC 166   5260 auto& lp = local(); 197   5229 auto& lp = local();
HITCBC 167   5260 if(lp.buckets[idx].push(p)) 198   5229 if(lp.buckets[idx].push(p))
HITCBC 168   5183 return; 199   5152 return;
HITCBC 169   77 deallocate_slow(p, idx); 200   77 deallocate_slow(p, idx);
170   } 201   }
171   202  
172   protected: 203   protected:
  204 + /** Allocate storage (`std::pmr::memory_resource` interface).
  205 +
  206 + Forwards to `allocate_fast`. The alignment argument is ignored;
  207 + see the class-level note.
  208 +
  209 + @param bytes The number of bytes to allocate.
  210 +
  211 + @return A pointer to the allocated storage.
  212 + */
173   void* 213   void*
174 - do_allocate(std::size_t bytes, std::size_t) override; 214 + do_allocate(std::size_t bytes, std::size_t /*alignment*/) override;
  215 +
  216 + /** Deallocate storage (`std::pmr::memory_resource` interface).
  217 +
  218 + Forwards to `deallocate_fast`. The alignment argument is ignored;
  219 + see the class-level note.
  220 +
  221 + @param p Pointer previously returned by `do_allocate`.
175   222  
  223 + @param bytes The size, in bytes, originally requested for `p`.
  224 + */
176   void 225   void
177 - do_deallocate(void* p, std::size_t bytes, std::size_t) override; 226 + do_deallocate(void* p, std::size_t bytes, std::size_t /*alignment*/) override;
178   227  
179   bool 228   bool
HITCBC 180   2 do_is_equal(const memory_resource& other) const noexcept override 229   2 do_is_equal(const memory_resource& other) const noexcept override
181   { 230   {
HITCBC 182   2 return this == &other; 231   2 return this == &other;
183   } 232   }
184   }; 233   };
185   BOOST_CAPY_MSVC_WARNING_POP 234   BOOST_CAPY_MSVC_WARNING_POP
186   235  
187   /** Returns pointer to the default recycling memory resource. 236   /** Returns pointer to the default recycling memory resource.
188   237  
189   The returned pointer is valid for the lifetime of the program. 238   The returned pointer is valid for the lifetime of the program.
190   This is the default allocator used by run_async. 239   This is the default allocator used by run_async.
191   240  
192   @return Pointer to the recycling memory resource. 241   @return Pointer to the recycling memory resource.
193   242  
194   @see recycling_memory_resource 243   @see recycling_memory_resource
195   @see run_async 244   @see run_async
196   */ 245   */
197   BOOST_CAPY_DECL 246   BOOST_CAPY_DECL
198   std::pmr::memory_resource* 247   std::pmr::memory_resource*
199   get_recycling_memory_resource() noexcept; 248   get_recycling_memory_resource() noexcept;
200   249  
201   } // namespace capy 250   } // namespace capy
202   } // namespace boost 251   } // namespace boost
203   252  
204   #endif 253   #endif