Inside Bitcoin

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 */
72template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
73class 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
178public:
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    /**