include/boost/capy/ex/recycling_memory_resource.hpp

94.9% Lines (56 / 59) 100.0% Functions (9 / 9)

[ ] prev/next file n p prev/next uncovered line

recycling_memory_resource.hpp

f(x) Functions (9)

Function Calls Lines Blocks

Line	Hits	Source Code
1		//
2		// Copyright (c) 2025 Vinnie Falco (vinnie.falco@gmail.com)
3		// Copyright (c) 2026 Michael Vandeberg
4		//
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)
7		//
8		// Official repository: https://github.com/cppalliance/capy
9		//
10
11		#ifndef BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
12		#define BOOST_CAPY_RECYCLING_MEMORY_RESOURCE_HPP
13
14		#include <boost/capy/detail/config.hpp>
15
16		#include <bit>
17		#include <cstddef>
18		#include <memory_resource>
19		#include <mutex>
20		#include <new>
21
22		namespace boost {
23		namespace capy {
24
25		/** Recycles freed blocks through per-thread pools, with a shared pool for cross-thread reuse.
26
27		This memory resource recycles memory blocks using power-of-two
28		size classes for O(1) allocation lookup. It maintains a thread-local
29		pool for fast lock-free access and a global pool for cross-thread
30		block sharing.
31
32		Size classes: 64, 128, 256, 512, 1024, 2048 bytes.
33		Allocations larger than 2048 bytes bypass the pools entirely.
34
35		Each pool caches at most 256 KiB of blocks per size class:
36		4096 blocks of the smallest class, 128 of the largest. A freed
37		block that fits in neither the thread's pool nor the global pool
38		goes back to `::operator delete`.
39
40		Blocks a thread caches but stops using drain back to the global
41		pool. The drain runs as the thread goes on freeing blocks or
42		refilling from the global pool. Other threads can then reuse what a
43		burst leaves behind. Blocks the global pool has no room for go back
44		to `::operator delete`.
45
46		This is the default allocator used by run_async when no allocator
47		is specified.
48
49		@par Thread Safety
50		Thread-safe. The thread-local pool requires no synchronization.
51		The global pool uses a mutex for cross-thread access.
52
53		@par Example
54		@par !example example
55
56
57		@see @ref get_recycling_memory_resource
58		@see @ref run_async
59		*/
60		BOOST_CAPY_MSVC_WARNING_PUSH
61		BOOST_CAPY_MSVC_WARNING_DISABLE(4275) // non dll-interface base class
62		class BOOST_CAPY_DECL recycling_memory_resource : public std::pmr::memory_resource
63		{
64		static constexpr std::size_t num_classes = 6;
65		static constexpr std::size_t min_class_size = 64; // 2^6
66		static constexpr std::size_t max_class_size = 2048; // 2^11
67		static constexpr int min_class_shift = std::countr_zero(min_class_size);
68		static constexpr std::size_t max_cached_bytes = 256 * 1024;
69
70		// Frees on one thread, plus blocks it refills from the global pool,
71		// between decay passes. Allocations served from the thread's pool
72		// aren't counted, which keeps the counter off that path.
73		static constexpr std::size_t decay_period = 4096;
74
75		static std::size_t
76	2287936x	round_up_pow2(std::size_t n) noexcept
77		{
78	2287936x	return n <= min_class_size ? min_class_size : std::bit_ceil(n);
79		}
80
81		static std::size_t
82	2287936x	get_class_index(std::size_t rounded) noexcept
83		{
84		auto const idx = static_cast<std::size_t>(
85	2287936x	std::countr_zero(rounded) - min_class_shift);
86	2287936x	return idx < num_classes ? idx : num_classes;
87		}
88
89		static constexpr std::size_t
90	1410470x	bucket_capacity(std::size_t idx) noexcept
91		{
92	1410470x	return max_cached_bytes >> (idx + min_class_shift);
93		}
94
95		// Cached blocks are linked through their own storage, so a bucket
96		// holds any number of them without a side array.
97		struct node
98		{
99		node* next;
100		};
101
102		struct bucket
103		{
104		node* head = nullptr;
105		std::size_t count = 0;
106
107		// Fewest blocks cached since the last decay pass: that many sat
108		// unused through the whole period.
109		std::size_t low = 0;
110
111	1199427x	void* pop() noexcept
112		{
113	1199427x	node* n = head;
114	1199427x	if(n == nullptr)
115	302445x	return nullptr;
116	896982x	head = n->next;
117	896982x	--count;
118	896982x	if(count < low)
119	53349x	low = count;
120	896982x	return n;
121		}
122
123		// Peter Dimov's idea
124		// `b` must be empty: its chain is overwritten.
125	302443x	void* pop(bucket& b) noexcept
126		{
127	302443x	if(head == nullptr)
128	302414x	return nullptr;
129	29x	b.head = head;
130	29x	b.count = count;
131	29x	head = nullptr;
132	29x	count = 0;
133	29x	low = 0;
134	29x	return b.pop();
135		}
136
137	1410348x	bool push(void* p, std::size_t capacity) noexcept
138		{
139	1410348x	if(count >= capacity)
140	473705x	return false;
141	936643x	head = ::new(p) node{head};
142	936643x	++count;
143	936643x	return true;
144		}
145		};
146
147		struct pool
148		{
149		bucket buckets[num_classes];
150		std::size_t arrivals = 0;
151
152		// No destructor: a non-trivial dtor forces a guard variable on the
153		// thread_local in local(), checked on every alloc/free. Constant
154		// initialization plus a trivial dtor makes that access a bare TLS
155		// load. Cached blocks are instead reclaimed explicitly: per-thread
156		// by arm_thread_cleanup() at thread exit, and the global pool by
157		// global()'s holder destructor at process exit.
158		};
159
160		#if (defined(BOOST_CAPY_DYN_LINK) \|\| defined(BOOST_ALL_DYN_LINK)) && \
161		!defined(BOOST_CAPY_STATIC_LINK)
162		// A shared build defines this thread's pool, and the flag below, in
163		// the library: inline, each module would cache in a pool of its own,
164		// which the library's thread-exit cleanup never drains.
165		static pool& local() noexcept;
166		#else
167		static pool& local() noexcept
168		{
169		static thread_local pool p;
170		return p;
171		}
172		#endif
173
174		static pool& global() noexcept;
175		static std::mutex& global_mutex() noexcept;
176
177		void* allocate_slow(std::size_t rounded, std::size_t idx);
178		void deallocate_slow(void* p, std::size_t idx);
179
180		// Move half of each bucket's idle blocks to the global pool, or
181		// release them when it has no room. Halving, rather than emptying,
182		// leaves a burst that skips one period half its blocks.
183		static void decay(pool& lp) noexcept;
184
185		// Register a thread-exit callback that drains this thread's local
186		// pool back to the OS. Called only off the hot path: unconditionally
187		// from the slow paths, and from deallocate_fast while the flag below
188		// is clear. Returns false once that callback has run: nothing drains
189		// the local pool after it, so frees must bypass it.
190		static bool arm_thread_cleanup() noexcept;
191
192		// Guard-free flag (constinit bool, trivial dtor): set once cleanup is
193		// armed, and cleared again when the cleanup has run.
194		#if (defined(BOOST_CAPY_DYN_LINK) \|\| defined(BOOST_ALL_DYN_LINK)) && \
195		!defined(BOOST_CAPY_STATIC_LINK)
196		static bool& thread_armed() noexcept;
197		#else
198		static bool& thread_armed() noexcept
199		{
200		static thread_local bool armed = false;
201		return armed;
202		}
203		#endif
204
205		public:
206		/** Destroy the resource.
207
208		No cached block is released here. Every pool is static, so an
209		instance holds no state of its own. The thread-local pool is
210		drained at thread exit, and the global pool at process exit.
211		*/
212		~recycling_memory_resource();
213
214		/** Allocate without virtual dispatch.
215
216		Handles the fast path inline (thread-local bucket pop)
217		and falls through to the slow path for global pool or
218		heap allocation.
219
220		A request larger than the largest size class (2048 bytes)
221		bypasses the pools and goes straight to `::operator new`.
222
223		The second parameter is the requested alignment, and it is ignored.
224		Every block comes from `::operator new`, so blocks carry the
225		implementation's default new alignment and no more.
226
227		@par Complexity
228		Amortized constant. Now and then a call also hands this thread's
229		idle cached blocks to the global pool, or releases them when it
230		has no room.
231
232		@param bytes The number of bytes to allocate.
233
234		@return A pointer to a block of at least `bytes` bytes. A pooled
235		block is rounded up to its size class, so it may be larger than
236		requested.
237
238		@throws std::bad_alloc If the underlying `::operator new` fails.
239		*/
240		void*
241	1143968x	allocate_fast(std::size_t bytes, std::size_t)
242		{
243	1143968x	std::size_t rounded = round_up_pow2(bytes);
244	1143968x	std::size_t idx = get_class_index(rounded);
245	1143968x	if(idx >= num_classes)
246	✗	return ::operator new(bytes);
247	1143968x	if(auto* p = local().buckets[idx].pop())
248	841524x	return p;
249	302444x	return allocate_slow(rounded, idx);
250		}
251
252		/** Deallocate without virtual dispatch.
253
254		Handles the fast path inline (thread-local bucket push)
255		and falls through to the slow path for global pool or
256		heap deallocation.
257
258		The block is cached in the pool of the thread that frees it, not
259		the thread that allocated it.
260
261		The third parameter is the alignment the block was allocated with,
262		and it is ignored, as it is on allocation.
263
264		@par Complexity
265		Amortized constant. Now and then a call also hands this thread's
266		idle cached blocks to the global pool, or releases them when it
267		has no room.
268
269		@param p The block to return. It must have come from
270		@ref allocate_fast or @ref do_allocate on this resource.
271
272		@param bytes The size the block was allocated with. The size class
273		is recomputed from it, so passing a different value puts the block
274		in the wrong bucket.
275		*/
276		void
277	1143968x	deallocate_fast(void* p, std::size_t bytes, std::size_t)
278		{
279	1143968x	std::size_t rounded = round_up_pow2(bytes);
280	1143968x	std::size_t idx = get_class_index(rounded);
281	1143968x	if(idx >= num_classes)
282		{
283	✗	::operator delete(p);
284	✗	return;
285		}
286		// Arms thread-exit cleanup for any thread that caches via
287		// deallocate, including consumer threads that never hit a slow
288		// path; after that cleanup, the block bypasses the local pool.
289	1143968x	auto& armed = thread_armed();
290	1143968x	if(!armed)
291		{
292	375x	if(!arm_thread_cleanup())
293		{
294	4x	deallocate_slow(p, idx);
295	4x	return;
296		}
297	371x	armed = true;
298		}
299	1143964x	auto& lp = local();
300	1143964x	if(++lp.arrivals == decay_period)
301	272x	decay(lp);
302	1143964x	if(lp.buckets[idx].push(p, bucket_capacity(idx)))
303	877584x	return;
304	266380x	deallocate_slow(p, idx);
305		}
306
307		protected:
308		/** Allocate through the `std::pmr::memory_resource` interface.
309
310		Forwards to @ref allocate_fast, so it has that function's contract.
311		Call `allocate_fast` directly to skip the virtual dispatch.
312
313		@param bytes The number of bytes to allocate.
314
315		@param alignment The requested alignment. It is ignored.
316
317		@return A pointer to a block of at least `bytes` bytes.
318
319		@throws std::bad_alloc If the underlying `::operator new` fails.
320		*/
321		void*
322		do_allocate(std::size_t bytes, std::size_t alignment) override;
323
324		/** Deallocate through the `std::pmr::memory_resource` interface.
325
326		Forwards to @ref deallocate_fast, so it has that function's
327		contract.
328
329		@param p The block to return, as obtained from this resource.
330
331		@param bytes The size the block was allocated with.
332
333		@param alignment The alignment the block was allocated with. It is
334		ignored.
335		*/
336		void
337		do_deallocate(void* p, std::size_t bytes, std::size_t alignment) override;
338
339		/** Compare this resource with another for equality.
340
341		Equality is object identity: two distinct
342		`recycling_memory_resource` objects compare unequal, even though the
343		pools they draw from are static and therefore shared.
344
345		@param other The resource to compare against.
346
347		@return `true` if `other` is the same object as `*this`; otherwise
348		`false`.
349		*/
350		bool
351	2x	do_is_equal(const memory_resource& other) const noexcept override
352		{
353	2x	return this == &other;
354		}
355		};
356		BOOST_CAPY_MSVC_WARNING_POP
357
358		/** Returns pointer to the default recycling memory resource.
359
360		The returned pointer is valid for the lifetime of the program.
361		This is the default allocator used by run_async.
362
363		@return Pointer to the recycling memory resource.
364
365		@see @ref recycling_memory_resource
366		@see @ref run_async
367		*/
368		BOOST_CAPY_DECL
369		std::pmr::memory_resource*
370		get_recycling_memory_resource() noexcept;
371
372		} // namespace capy
373		} // namespace boost
374
375		#endif
376