Bitcoin Core 29.99.0
P2P Digital Currency
pool.h
Go to the documentation of this file.
1// Copyright (c) 2022 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
71template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
72class PoolResource final
73{
74 static_assert(ALIGN_BYTES > 0, "ALIGN_BYTES must be nonzero");
75 static_assert((ALIGN_BYTES & (ALIGN_BYTES - 1)) == 0, "ALIGN_BYTES must be a power of two");
76
80 struct ListNode {
82
83 explicit ListNode(ListNode* next) : m_next(next) {}
84 };
85 static_assert(std::is_trivially_destructible_v<ListNode>, "Make sure we don't need to manually call a destructor");
86
90 static constexpr std::size_t ELEM_ALIGN_BYTES = std::max(alignof(ListNode), ALIGN_BYTES);
91 static_assert((ELEM_ALIGN_BYTES & (ELEM_ALIGN_BYTES - 1)) == 0, "ELEM_ALIGN_BYTES must be a power of two");
92 static_assert(sizeof(ListNode) <= ELEM_ALIGN_BYTES, "Units of size ELEM_SIZE_ALIGN need to be able to store a ListNode");
93 static_assert((MAX_BLOCK_SIZE_BYTES & (ELEM_ALIGN_BYTES - 1)) == 0, "MAX_BLOCK_SIZE_BYTES needs to be a multiple of the alignment.");
94
98 const size_t m_chunk_size_bytes;
99
103 std::list<std::byte*> m_allocated_chunks{};
104
109 std::array<ListNode*, MAX_BLOCK_SIZE_BYTES / ELEM_ALIGN_BYTES + 1> m_free_lists{};
110
114 std::byte* m_available_memory_it = nullptr;
115
122 std::byte* m_available_memory_end = nullptr;
123
128 [[nodiscard]] static constexpr std::size_t NumElemAlignBytes(std::size_t bytes)
129 {
130 return (bytes + ELEM_ALIGN_BYTES - 1) / ELEM_ALIGN_BYTES + (bytes == 0);
131 }
132
136 [[nodiscard]] static constexpr bool IsFreeListUsable(std::size_t bytes, std::size_t alignment)
137 {
138 return alignment <= ELEM_ALIGN_BYTES && bytes <= MAX_BLOCK_SIZE_BYTES;
139 }
140
145 {
146 node = new (p) ListNode{node};
147 }
148
156 {
157 // if there is still any available memory left, put it into the freelist.
158 size_t remaining_available_bytes = std::distance(m_available_memory_it, m_available_memory_end);
159 if (0 != remaining_available_bytes) {
163 }
164
165 void* storage = ::operator new (m_chunk_size_bytes, std::align_val_t{ELEM_ALIGN_BYTES});
166 m_available_memory_it = new (storage) std::byte[m_chunk_size_bytes];
170 }
171
175 friend class PoolResourceTester;
176
177public:
182 explicit PoolResource(std::size_t chunk_size_bytes)
184 {
185 assert(m_chunk_size_bytes >= MAX_BLOCK_SIZE_BYTES);
187 }
188
193
197 PoolResource(const PoolResource&) = delete;
201
206 {
207 for (std::byte* chunk : m_allocated_chunks) {
208 std::destroy(chunk, chunk + m_chunk_size_bytes);
209 ::operator delete ((void*)chunk, std::align_val_t{ELEM_ALIGN_BYTES});
211 }
212 }
213
218 void* Allocate(std::size_t bytes, std::size_t alignment)
219 {
220 if (IsFreeListUsable(bytes, alignment)) {
221 const std::size_t num_alignments = NumElemAlignBytes(bytes);
222 if (nullptr != m_free_lists[num_alignments]) {
223 // we've already got data in the pool's freelist, unlink one element and return the pointer
224 // to the unlinked memory. Since FreeList is trivially destructible we can just treat it as
225 // uninitialized memory.
226 ASAN_UNPOISON_MEMORY_REGION(m_free_lists[num_alignments], sizeof(ListNode));
227 auto* next{m_free_lists[num_alignments]->m_next};
228 ASAN_POISON_MEMORY_REGION(m_free_lists[num_alignments], sizeof(ListNode));
229 ASAN_UNPOISON_MEMORY_REGION(m_free_lists[num_alignments], bytes);
230 return std::exchange(m_free_lists[num_alignments], next);
231 }
232
233 // freelist is empty: get one allocation from allocated chunk memory.
234 const std::ptrdiff_t round_bytes = static_cast<std::ptrdiff_t>(num_alignments * ELEM_ALIGN_BYTES);
235 if (round_bytes > m_available_memory_end - m_available_memory_it) {
236 // slow path, only happens when a new chunk needs to be allocated
238 }
239
240 // Make sure we use the right amount of bytes for that freelist (might be rounded up),
242 return std::exchange(m_available_memory_it, m_available_memory_it + round_bytes);
243 }
244
245 // Can't use the pool => use operator new()
246 return ::operator new (bytes, std::align_val_t{alignment});
247 }
248
252 void Deallocate(void* p, std::size_t bytes, std::size_t alignment) noexcept
253 {
254 if (IsFreeListUsable(bytes, alignment)) {
255 const std::size_t num_alignments = NumElemAlignBytes(bytes);
256 // put the memory block into the linked list. We can placement construct the FreeList
257 // into the memory since we can be sure the alignment is correct.
259 PlacementAddToList(p, m_free_lists[num_alignments]);
260 ASAN_POISON_MEMORY_REGION(p, std::max(bytes, sizeof(ListNode)));
261 } else {
262 // Can't use the pool => forward deallocation to ::operator delete().
263 ::operator delete (p, std::align_val_t{alignment});
264 }
265 }
266
270 [[nodiscard]] std::size_t NumAllocatedChunks() const
271 {
272 return m_allocated_chunks.size();
273 }
274
278 [[nodiscard]] size_t ChunkSizeBytes() const
279 {
280 return m_chunk_size_bytes;
281 }
282};
283
284
288template <class T, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES = alignof(T)>
290{
292
293 template <typename U, std::size_t M, std::size_t A>
294 friend class PoolAllocator;
295
296public:
297 using value_type = T;
299
305 {
306 }
307
308 PoolAllocator(const PoolAllocator& other) noexcept = default;
309 PoolAllocator& operator=(const PoolAllocator& other) noexcept = default;
310
311 template <class U>
313 : m_resource(other.resource())
314 {
315 }
316
321 template <typename U>
322 struct rebind {
324 };
325
329 T* allocate(size_t n)
330 {
331 return static_cast<T*>(m_resource->Allocate(n * sizeof(T), alignof(T)));
332 }
333
337 void deallocate(T* p, size_t n) noexcept
338 {
339 m_resource->Deallocate(p, n * sizeof(T), alignof(T));
340 }
341
342 ResourceType* resource() const noexcept
343 {
344 return m_resource;
345 }
346};
347
348template <class T1, class T2, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
351{
352 return a.resource() == b.resource();
353}
354
355template <class T1, class T2, std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
358{
359 return !(a == b);
360}
361
362#endif // BITCOIN_SUPPORT_ALLOCATORS_POOL_H
#define ASAN_POISON_MEMORY_REGION(addr, size)
Definition: check.h:136
#define ASAN_UNPOISON_MEMORY_REGION(addr, size)
Definition: check.h:137
Forwards all allocations/deallocations to the PoolResource.
Definition: pool.h:290
PoolResource< MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > * m_resource
Definition: pool.h:291
ResourceType * resource() const noexcept
Definition: pool.h:342
T value_type
Definition: pool.h:297
PoolAllocator & operator=(const PoolAllocator &other) noexcept=default
void deallocate(T *p, size_t n) noexcept
Forwards each call to the resource.
Definition: pool.h:337
PoolAllocator(const PoolAllocator &other) noexcept=default
PoolAllocator(ResourceType *resource) noexcept
Not explicit so we can easily construct it with the correct resource.
Definition: pool.h:303
T * allocate(size_t n)
Forwards each call to the resource.
Definition: pool.h:329
PoolAllocator(const PoolAllocator< U, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > &other) noexcept
Definition: pool.h:312
A memory resource similar to std::pmr::unsynchronized_pool_resource, but optimized for node-based con...
Definition: pool.h:73
PoolResource & operator=(const PoolResource &)=delete
void PlacementAddToList(void *p, ListNode *&node)
Replaces node with placement constructed ListNode that points to the previous node.
Definition: pool.h:144
static constexpr std::size_t NumElemAlignBytes(std::size_t bytes)
How many multiple of ELEM_ALIGN_BYTES are necessary to fit bytes.
Definition: pool.h:128
PoolResource(const PoolResource &)=delete
Disable copy & move semantics, these are not supported for the resource.
size_t ChunkSizeBytes() const
Size in bytes to allocate per chunk, currently hardcoded to a fixed size.
Definition: pool.h:278
std::array< ListNode *, MAX_BLOCK_SIZE_BYTES/ELEM_ALIGN_BYTES+1 > m_free_lists
Single linked lists of all data that came from deallocating.
Definition: pool.h:109
std::byte * m_available_memory_it
Points to the beginning of available memory for carving out allocations.
Definition: pool.h:114
PoolResource & operator=(PoolResource &&)=delete
std::size_t NumAllocatedChunks() const
Number of allocated chunks.
Definition: pool.h:270
static constexpr bool IsFreeListUsable(std::size_t bytes, std::size_t alignment)
True when it is possible to make use of the freelist.
Definition: pool.h:136
void Deallocate(void *p, std::size_t bytes, std::size_t alignment) noexcept
Returns a block to the freelists, or deletes the block when it did not come from the chunks.
Definition: pool.h:252
std::byte * m_available_memory_end
Points to the end of available memory for carving out allocations.
Definition: pool.h:122
PoolResource(std::size_t chunk_size_bytes)
Construct a new PoolResource object which allocates the first chunk.
Definition: pool.h:182
~PoolResource()
Deallocates all memory allocated associated with the memory resource.
Definition: pool.h:205
static constexpr std::size_t ELEM_ALIGN_BYTES
Internal alignment value.
Definition: pool.h:90
const size_t m_chunk_size_bytes
Size in bytes to allocate per chunk.
Definition: pool.h:98
std::list< std::byte * > m_allocated_chunks
Contains all allocated pools of memory, used to free the data in the destructor.
Definition: pool.h:103
PoolResource()
Construct a new Pool Resource object, defaults to 2^18=262144 chunk size.
Definition: pool.h:192
PoolResource(PoolResource &&)=delete
void * Allocate(std::size_t bytes, std::size_t alignment)
Allocates a block of bytes.
Definition: pool.h:218
void AllocateChunk()
Allocate one full memory chunk which will be used to carve out allocations.
Definition: pool.h:155
Helper to get access to private parts of PoolResource.
Definition: messages.h:20
bool operator!=(const PoolAllocator< T1, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > &a, const PoolAllocator< T2, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > &b) noexcept
Definition: pool.h:356
bool operator==(const PoolAllocator< T1, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > &a, const PoolAllocator< T2, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > &b) noexcept
Definition: pool.h:349
The rebind struct here is mandatory because we use non type template arguments for PoolAllocator.
Definition: pool.h:322
In-place linked list of the allocations, used for the freelist.
Definition: pool.h:80
ListNode * m_next
Definition: pool.h:81
ListNode(ListNode *next)
Definition: pool.h:83
assert(!tx.IsCoinBase())