Bitcoin ABC 0.26.3
P2P Digital Currency
Loading...
Searching...
No Matches
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
69template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
71 static_assert(ALIGN_BYTES > 0, "ALIGN_BYTES must be nonzero");
72 static_assert((ALIGN_BYTES & (ALIGN_BYTES - 1)) == 0,
73 "ALIGN_BYTES must be a power of two");
74
78 struct ListNode {
80
81 explicit ListNode(ListNode *next) : m_next(next) {}
82 };
83 static_assert(std::is_trivially_destructible_v<ListNode>,
84 "Make sure we don't need to manually call a destructor");
85
90 static constexpr std::size_t ELEM_ALIGN_BYTES =
91 std::max(alignof(ListNode), ALIGN_BYTES);
92 static_assert((ELEM_ALIGN_BYTES & (ELEM_ALIGN_BYTES - 1)) == 0,
93 "ELEM_ALIGN_BYTES must be a power of two");
94 static_assert(
95 sizeof(ListNode) <= ELEM_ALIGN_BYTES,
96 "Units of size ELEM_SIZE_ALIGN need to be able to store a ListNode");
97 static_assert(
99 "MAX_BLOCK_SIZE_BYTES needs to be a multiple of the alignment.");
100
104 const size_t m_chunk_size_bytes;
105
110 std::list<std::byte *> m_allocated_chunks{};
111
116 std::array<ListNode *, MAX_BLOCK_SIZE_BYTES / ELEM_ALIGN_BYTES + 1>
118
122 std::byte *m_available_memory_it = nullptr;
123
132 std::byte *m_available_memory_end = nullptr;
133
139 [[nodiscard]] static constexpr std::size_t
140 NumElemAlignBytes(std::size_t bytes) {
141 return (bytes + ELEM_ALIGN_BYTES - 1) / ELEM_ALIGN_BYTES + (bytes == 0);
142 }
143
147 [[nodiscard]] static constexpr bool
148 IsFreeListUsable(std::size_t bytes, std::size_t alignment) {
149 return alignment <= ELEM_ALIGN_BYTES && bytes <= MAX_BLOCK_SIZE_BYTES;
150 }
151
157 node = new (p) ListNode{node};
158 }
159
168 // if there is still any available memory left, put it into the
169 // freelist.
172 if (0 != remaining_available_bytes) {
176 }
177
179 std::align_val_t{ELEM_ALIGN_BYTES});
183 }
184
188 friend class PoolResourceTester;
189
190public:
201
206
210 PoolResource(const PoolResource &) = delete;
214
219 for (std::byte *chunk : m_allocated_chunks) {
220 std::destroy(chunk, chunk + m_chunk_size_bytes);
221 ::operator delete ((void *)chunk,
222 std::align_val_t{ELEM_ALIGN_BYTES});
223 }
224 }
225
230 void *Allocate(std::size_t bytes, std::size_t alignment) {
231 if (IsFreeListUsable(bytes, alignment)) {
232 const std::size_t num_alignments = NumElemAlignBytes(bytes);
233 if (nullptr != m_free_lists[num_alignments]) {
234 // we've already got data in the pool's freelist, unlink one
235 // element and return the pointer to the unlinked memory. Since
236 // FreeList is trivially destructible we can just treat it as
237 // uninitialized memory.
238 return std::exchange(m_free_lists[num_alignments],
240 }
241
242 // freelist is empty: get one allocation from allocated chunk
243 // memory.
244 const std::ptrdiff_t round_bytes =
245 static_cast<std::ptrdiff_t>(num_alignments * ELEM_ALIGN_BYTES);
247 // slow path, only happens when a new chunk needs to be
248 // allocated
250 }
251
252 // Make sure we use the right amount of bytes for that freelist
253 // (might be rounded up),
254 return std::exchange(m_available_memory_it,
256 }
257
258 // Can't use the pool => use operator new()
259 return ::operator new (bytes, std::align_val_t{alignment});
260 }
261
266 void Deallocate(void *p, std::size_t bytes,
267 std::size_t alignment) noexcept {
268 if (IsFreeListUsable(bytes, alignment)) {
269 const std::size_t num_alignments = NumElemAlignBytes(bytes);
270 // put the memory block into the linked list. We can placement
271 // construct the FreeList into the memory since we can be sure the
272 // alignment is correct.
274 } else {
275 // Can't use the pool => forward deallocation to ::operator
276 // delete().
277 ::operator delete (p, std::align_val_t{alignment});
278 }
279 }
280
284 [[nodiscard]] std::size_t NumAllocatedChunks() const {
285 return m_allocated_chunks.size();
286 }
287
291 [[nodiscard]] size_t ChunkSizeBytes() const { return m_chunk_size_bytes; }
292};
293
297template <class T, std::size_t MAX_BLOCK_SIZE_BYTES,
298 std::size_t ALIGN_BYTES = alignof(T)>
301
302 template <typename U, std::size_t M, std::size_t A>
303 friend class PoolAllocator;
304
305public:
306 using value_type = T;
308
312 PoolAllocator(ResourceType *resource) noexcept : m_resource(resource) {}
313
314 PoolAllocator(const PoolAllocator &other) noexcept = default;
315 PoolAllocator &operator=(const PoolAllocator &other) noexcept = default;
316
317 template <class U>
319 &other) noexcept
320 : m_resource(other.resource()) {}
321
327 template <typename U> struct rebind {
329 };
330
334 T *allocate(size_t n) {
335 return static_cast<T *>(
336 m_resource->Allocate(n * sizeof(T), alignof(T)));
337 }
338
342 void deallocate(T *p, size_t n) noexcept {
343 m_resource->Deallocate(p, n * sizeof(T), alignof(T));
344 }
345
346 ResourceType *resource() const noexcept { return m_resource; }
347};
348
349template <class T1, class T2, std::size_t MAX_BLOCK_SIZE_BYTES,
350 std::size_t ALIGN_BYTES>
354 return a.resource() == b.resource();
355}
356
357template <class T1, class T2, std::size_t MAX_BLOCK_SIZE_BYTES,
358 std::size_t ALIGN_BYTES>
364
365#endif // BITCOIN_SUPPORT_ALLOCATORS_POOL_H
Forwards all allocations/deallocations to the PoolResource.
Definition pool.h:299
PoolResource< MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > * m_resource
Definition pool.h:300
ResourceType * resource() const noexcept
Definition pool.h:346
PoolAllocator & operator=(const PoolAllocator &other) noexcept=default
friend class PoolAllocator
Definition pool.h:303
void deallocate(T *p, size_t n) noexcept
Forwards each call to the resource.
Definition pool.h:342
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:312
T * allocate(size_t n)
Forwards each call to the resource.
Definition pool.h:334
PoolAllocator(const PoolAllocator< U, MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES > &other) noexcept
Definition pool.h:318
A memory resource similar to std::pmr::unsynchronized_pool_resource, but optimized for node-based con...
Definition pool.h:70
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:117
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:156
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:140
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:291
std::byte * m_available_memory_it
Points to the beginning of available memory for carving out allocations.
Definition pool.h:122
PoolResource & operator=(PoolResource &&)=delete
std::size_t NumAllocatedChunks() const
Number of allocated chunks.
Definition pool.h:284
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:148
friend class PoolResourceTester
Access to internals for testing purpose only.
Definition pool.h:188
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:266
std::byte * m_available_memory_end
Points to the end of available memory for carving out allocations.
Definition pool.h:132
PoolResource(std::size_t chunk_size_bytes)
Construct a new PoolResource object which allocates the first chunk.
Definition pool.h:195
~PoolResource()
Deallocates all memory allocated associated with the memory resource.
Definition pool.h:218
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:104
PoolResource()
Construct a new Pool Resource object, defaults to 2^18=262144 chunk size.
Definition pool.h:205
PoolResource(PoolResource &&)=delete
void * Allocate(std::size_t bytes, std::size_t alignment)
Allocates a block of bytes.
Definition pool.h:230
std::list< std::byte * > m_allocated_chunks
Contains all allocated pools of memory, used to free the data in the destructor.
Definition pool.h:110
void AllocateChunk()
Allocate one full memory chunk which will be used to carve out allocations.
Definition pool.h:167
Definition init.h:28
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:359
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:351
T GetRand(T nMax=std::numeric_limits< T >::max()) noexcept
Generate a uniform random integer of type T in the range [0..nMax) nMax defaults to std::numeric_limi...
Definition random.h:85
The rebind struct here is mandatory because we use non type template arguments for PoolAllocator.
Definition pool.h:327
In-place linked list of the allocations, used for the freelist.
Definition pool.h:78
ListNode * m_next
Definition pool.h:79
ListNode(ListNode *next)
Definition pool.h:81
assert(!tx.IsCoinBase())