1 // Copyright (c) 2022-present The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 5 #ifndef BITCOIN_SUPPORT_ALLOCATORS_POOL_H
6 #define BITCOIN_SUPPORT_ALLOCATORS_POOL_H
7 8 #include <array>
9 #include <cassert>
10 #include <cstddef>
11 #include <list>
12 #include <memory>
13 #include <new>
14 #include <type_traits>
15 #include <utility>
16 17 #include <util/check.h>
18 #include <util/overflow.h>
19 20 /**
21 * A memory resource similar to std::pmr::unsynchronized_pool_resource, but
22 * optimized for node-based containers. It has the following properties:
23 *
24 * * Owns the allocated memory and frees it on destruction, even when deallocate
25 * has not been called on the allocated blocks.
26 *
27 * * Consists of a number of pools, each one for a different block size.
28 * Each pool holds blocks of uniform size in a freelist.
29 *
30 * * Exhausting memory in a freelist causes a new allocation of a fixed size chunk.
31 * This chunk is used to carve out blocks.
32 *
33 * * Block sizes or alignments that can not be served by the pools are allocated
34 * and deallocated by operator new().
35 *
36 * PoolResource is not thread-safe. It is intended to be used by PoolAllocator.
37 *
38 * @tparam MAX_BLOCK_SIZE_BYTES Maximum size to allocate with the pool. If larger
39 * sizes are requested, allocation falls back to new().
40 *
41 * @tparam ALIGN_BYTES Required alignment for the allocations.
42 *
43 * An example: If you create a PoolResource<128, 8>(262144) and perform a bunch of
44 * allocations and deallocate 2 blocks with size 8 bytes, and 3 blocks with size 16,
45 * the members will look like this:
46 *
47 * m_free_lists m_allocated_chunks
48 * ┌───┐ ┌───┐ ┌────────────-------──────┐
49 * │ │ blocks │ ├─►│ 262144 B │
50 * │ │ ┌─────┐ ┌─────┐ └─┬─┘ └────────────-------──────┘
51 * │ 1 ├─►│ 8 B ├─►│ 8 B │ │
52 * │ │ └─────┘ └─────┘ :
53 * │ │ │
54 * │ │ ┌─────┐ ┌─────┐ ┌─────┐ ▼
55 * │ 2 ├─►│16 B ├─►│16 B ├─►│16 B │ ┌───┐ ┌─────────────────────────┐
56 * │ │ └─────┘ └─────┘ └─────┘ │ ├─►│ ▲ │ ▲
57 * │ │ └───┘ └──────────┬──────────────┘ │
58 * │ . │ │ m_available_memory_end
59 * │ . │ m_available_memory_it
60 * │ . │
61 * │ │
62 * │ │
63 * │16 │
64 * └───┘
65 *
66 * Here m_free_lists[1] holds the 2 blocks of size 8 bytes, and m_free_lists[2]
67 * holds the 3 blocks of size 16. The blocks came from the data stored in the
68 * m_allocated_chunks list. Each chunk has bytes 262144. The last chunk has still
69 * some memory available for the blocks, and when m_available_memory_it is at the
70 * end, a new chunk will be allocated and added to the list.
71 */
72 template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
73 class PoolResource final
74 {
75 static_assert(ALIGN_BYTES > 0, "ALIGN_BYTES must be nonzero");
76 static_assert((ALIGN_BYTES & (ALIGN_BYTES - 1)) == 0, "ALIGN_BYTES must be a power of two");
77 78 /**
79 * In-place linked list of the allocations, used for the freelist.
80 */
81 struct ListNode {
82 ListNode* m_next;
83 84 explicit ListNode(ListNode* next) : m_next(next) {}
85 };
86 static_assert(std::is_trivially_destructible_v<ListNode>, "Make sure we don't need to manually call a destructor");
87 88 /**
89 * Internal alignment value. The larger of the requested ALIGN_BYTES and alignof(FreeList).
90 */
91 static constexpr std::size_t ELEM_ALIGN_BYTES = std::max(alignof(ListNode), ALIGN_BYTES);
92 static_assert((ELEM_ALIGN_BYTES & (ELEM_ALIGN_BYTES - 1)) == 0, "ELEM_ALIGN_BYTES must be a power of two");
93 static_assert(sizeof(ListNode) <= ELEM_ALIGN_BYTES, "Units of size ELEM_SIZE_ALIGN need to be able to store a ListNode");
94 static_assert((MAX_BLOCK_SIZE_BYTES & (ELEM_ALIGN_BYTES - 1)) == 0, "MAX_BLOCK_SIZE_BYTES needs to be a multiple of the alignment.");
95 96 /**
97 * Size in bytes to allocate per chunk
98 */
99 const size_t m_chunk_size_bytes;
100 101 /**
102 * Contains all allocated pools of memory, used to free the data in the destructor.
103 */
104 std::list<std::byte*> m_allocated_chunks{};
105 106 /**
107 * Single linked lists of all data that came from deallocating.
108 * m_free_lists[n] will serve blocks of size n*ELEM_ALIGN_BYTES.
109 */
110 std::array<ListNode*, MAX_BLOCK_SIZE_BYTES / ELEM_ALIGN_BYTES + 1> m_free_lists{};
111 112 /**
113 * Points to the beginning of available memory for carving out allocations.
114 */
115 std::byte* m_available_memory_it = nullptr;
116 117 /**
118 * Points to the end of available memory for carving out allocations.
119 *
120 * That member variable is redundant, and is always equal to `m_allocated_chunks.back() + m_chunk_size_bytes`
121 * whenever it is accessed, but `m_available_memory_end` caches this for clarity and efficiency.
122 */
123 std::byte* m_available_memory_end = nullptr;
124 125 /**
126 * How many multiple of ELEM_ALIGN_BYTES are necessary to fit bytes. We use that result directly as an index
127 * into m_free_lists. Round up for the special case when bytes==0.
128 */
129 [[nodiscard]] static constexpr std::size_t NumElemAlignBytes(std::size_t bytes)
130 {
131 return CeilDiv(bytes, ELEM_ALIGN_BYTES) + (bytes == 0);
132 }
133 134 /**
135 * True when it is possible to make use of the freelist
136 */
137 [[nodiscard]] static constexpr bool IsFreeListUsable(std::size_t bytes, std::size_t alignment)
138 {
139 return alignment <= ELEM_ALIGN_BYTES && bytes <= MAX_BLOCK_SIZE_BYTES;
140 }
141 142 /**
143 * Replaces node with placement constructed ListNode that points to the previous node
144 */
145 void PlacementAddToList(void* p, ListNode*& node)
146 {
147 node = new (p) ListNode{node};
148 }
149 150 /**
151 * Allocate one full memory chunk which will be used to carve out allocations.
152 * Also puts any leftover bytes into the freelist.
153 *
154 * Precondition: leftover bytes are either 0 or few enough to fit into a place in the freelist
155 */
156 void AllocateChunk()
157 {
158 // if there is still any available memory left, put it into the freelist.
159 size_t remaining_available_bytes = m_available_memory_end - m_available_memory_it;
160 if (0 != remaining_available_bytes) {
161 ASAN_UNPOISON_MEMORY_REGION(m_available_memory_it, sizeof(ListNode));
162 PlacementAddToList(m_available_memory_it, m_free_lists[remaining_available_bytes / ELEM_ALIGN_BYTES]);
163 ASAN_POISON_MEMORY_REGION(m_available_memory_it, sizeof(ListNode));
164 }
165 166 void* storage = ::operator new (m_chunk_size_bytes, std::align_val_t{ELEM_ALIGN_BYTES});
167 m_available_memory_it = new (storage) std::byte[m_chunk_size_bytes];
168 m_available_memory_end = m_available_memory_it + m_chunk_size_bytes;
169 ASAN_POISON_MEMORY_REGION(m_available_memory_it, m_chunk_size_bytes);
170 m_allocated_chunks.emplace_back(m_available_memory_it);
171 }
172 173 /**
174 * Access to internals for testing purpose only
175 */
176 friend class PoolResourceTester;
177 178 public:
179 /**
180 * Construct a new PoolResource object which allocates the first chunk.
181 * chunk_size_bytes will be rounded up to next multiple of ELEM_ALIGN_BYTES.
182 */
183 explicit PoolResource(std::size_t chunk_size_bytes)
184 : m_chunk_size_bytes(NumElemAlignBytes(chunk_size_bytes) * ELEM_ALIGN_BYTES)
185 {
186 assert(m_chunk_size_bytes >= MAX_BLOCK_SIZE_BYTES);
187 AllocateChunk();
188 }
189 190 /**
191 * Construct a new Pool Resource object, defaults to 2^18=262144 chunk size.
192 */
193 PoolResource() : PoolResource(262144) {}
194 195 /**
196 * Disable copy & move semantics, these are not supported for the resource.
197 */
198 PoolResource(const PoolResource&) = delete;
199 PoolResource& operator=(const PoolResource&) = delete;
200 PoolResource(PoolResource&&) = delete;
201 PoolResource& operator=(PoolResource&&) = delete;
202 203 /**
204 * Deallocates all memory allocated associated with the memory resource.
205 */
206 ~PoolResource()
207 {
208 for (std::byte* chunk : m_allocated_chunks) {
209 std::destroy(chunk, chunk + m_chunk_size_bytes);
210 ::operator delete ((void*)chunk, std::align_val_t{ELEM_ALIGN_BYTES});
211 ASAN_UNPOISON_MEMORY_REGION(chunk, m_chunk_size_bytes);
212 }
213 }
214 215 /**
216 * Allocates a block of bytes. If possible the freelist is used, otherwise allocation
217 * is forwarded to ::operator new().
218 */
219 void* Allocate(std::size_t bytes, std::size_t alignment)
220 {
221 if (IsFreeListUsable(bytes, alignment)) {
222 const std::size_t num_alignments = NumElemAlignBytes(bytes);
223 if (nullptr != m_free_lists[num_alignments]) {
224 // we've already got data in the pool's freelist, unlink one element and return the pointer
225 // to the unlinked memory. Since FreeList is trivially destructible we can just treat it as
226 // uninitialized memory.
227 ASAN_UNPOISON_MEMORY_REGION(m_free_lists[num_alignments], sizeof(ListNode));
228 auto* next{m_free_lists[num_alignments]->m_next};
229 ASAN_POISON_MEMORY_REGION(m_free_lists[num_alignments], sizeof(ListNode));
230 ASAN_UNPOISON_MEMORY_REGION(m_free_lists[num_alignments], bytes);
231 return std::exchange(m_free_lists[num_alignments], next);
232 }
233 234 // freelist is empty: get one allocation from allocated chunk memory.
235 const std::ptrdiff_t round_bytes = static_cast<std::ptrdiff_t>(num_alignments * ELEM_ALIGN_BYTES);
236 if (round_bytes > m_available_memory_end - m_available_memory_it) {
237 // slow path, only happens when a new chunk needs to be allocated
238 AllocateChunk();
239 }
240 241 // Make sure we use the right amount of bytes for that freelist (might be rounded up),
242 ASAN_UNPOISON_MEMORY_REGION(m_available_memory_it, round_bytes);
243 return std::exchange(m_available_memory_it, m_available_memory_it + round_bytes);
244 }
245 246 // Can't use the pool => use operator new()
247 return ::operator new (bytes, std::align_val_t{alignment});
248 }
249 250 /**
251 * Returns a block to the freelists, or deletes the block when it did not come from the chunks.
252 */
253 void Deallocate(void* p, std::size_t bytes, std::size_t alignment) noexcept
254 {
255 if (IsFreeListUsable(bytes, alignment)) {
256 const std::size_t num_alignments = NumElemAlignBytes(bytes);
257 // put the memory block into the linked list. We can placement construct the FreeList
258 // into the memory since we can be sure the alignment is correct.
259 ASAN_UNPOISON_MEMORY_REGION(p, sizeof(ListNode));
260 PlacementAddToList(p, m_free_lists[num_alignments]);
261 ASAN_POISON_MEMORY_REGION(p, std::max(bytes, sizeof(ListNode)));
262 } else {
263 // Can't use the pool => forward deallocation to ::operator delete().
264 ::operator delete (p, std::align_val_t{alignment});
265 }
266 }
267 268 /**
269 * Number of allocated chunks
270 */
271 [[nodiscard]] std::size_t NumAllocatedChunks() const
272 {
273 return m_allocated_chunks.size();
274 }
275 276 /**
277 * Size in bytes to allocate per chunk, currently hardcoded to a fixed size.
278 */
279 [[nodiscard]] size_t ChunkSizeBytes() const
280 {
281 return m_chunk_size_bytes;
282 }
283 };
284 285 286 /**
287 * Forwards all allocations/deallocations to the PoolResource.
288 */
289 template <class T, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES = alignof(T)>
290 class PoolAllocator
291 {
292 PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>* m_resource;
293 294 template <typename U, std::size_t M, std::size_t A>
295 friend class PoolAllocator;
296 297 public:
298 using value_type = T;
299 using ResourceType = PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>;
300 301 /**
302 * Not explicit so we can easily construct it with the correct resource
303 */
304 PoolAllocator(ResourceType* resource) noexcept
305 : m_resource(resource)
306 {
307 }
308 309 PoolAllocator(const PoolAllocator& other) noexcept = default;
310 PoolAllocator& operator=(const PoolAllocator& other) noexcept = default;
311 312 template <class U>
313 PoolAllocator(const PoolAllocator<U, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& other) noexcept
314 : m_resource(other.resource())
315 {
316 }
317 318 /**
319 * The rebind struct here is mandatory because we use non type template arguments for
320 * PoolAllocator. See https://en.cppreference.com/w/cpp/named_req/Allocator#cite_note-2
321 */
322 template <typename U>
323 struct rebind {
324 using other = PoolAllocator<U, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>;
325 };
326 327 /**
328 * Forwards each call to the resource.
329 */
330 T* allocate(size_t n)
331 {
332 return static_cast<T*>(m_resource->Allocate(n * sizeof(T), alignof(T)));
333 }
334 335 /**
336 * Forwards each call to the resource.
337 */
338 void deallocate(T* p, size_t n) noexcept
339 {
340 m_resource->Deallocate(p, n * sizeof(T), alignof(T));
341 }
342 343 ResourceType* resource() const noexcept
344 {
345 return m_resource;
346 }
347 };
348 349 template <class T1, class T2, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
350 bool operator==(const PoolAllocator<T1, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& a,
351 const PoolAllocator<T2, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& b) noexcept
352 {
353 return a.resource() == b.resource();
354 }
355 356 #endif // BITCOIN_SUPPORT_ALLOCATORS_POOL_H
357