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_TEST_UTIL_POOLRESOURCETESTER_H
6#define BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H
7
8#include <support/allocators/pool.h>
9#include <util/check.h>
10
11#include <algorithm>
12#include <cassert>
13#include <cstddef>
14#include <cstdint>
15#include <vector>
16
17/**
18 * Helper to get access to private parts of PoolResource. Used in unit tests and in the fuzzer
19 */
20class PoolResourceTester
21{
22    struct PtrAndBytes {
23        uintptr_t ptr;
24        std::size_t size;
25
26        PtrAndBytes(const void* p, std::size_t s)
27            : ptr(reinterpret_cast<uintptr_t>(p)), size(s)
28        {
29        }
30
31        /**
32         * defines a sort ordering by the pointer value
33         */
34        friend bool operator<(PtrAndBytes const& a, PtrAndBytes const& b)
35        {
36            return a.ptr < b.ptr;
37        }
38    };
39
40public:
41    /**
42     * Extracts the number of elements per freelist
43     */
44    template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
45    static std::vector<std::size_t> FreeListSizes(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource)
46    {
47        auto sizes = std::vector<std::size_t>();
48        for (const auto* ptr : resource.m_free_lists) {
49            size_t size = 0;
50            while (ptr != nullptr) {
51                ++size;
52                const auto* ptr_ = ptr;
53                ASAN_UNPOISON_MEMORY_REGION(ptr_, sizeof(typename PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>::ListNode));
54                ptr = ptr->m_next;
55                ASAN_POISON_MEMORY_REGION(ptr_, sizeof(typename PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>::ListNode));
56            }
57            sizes.push_back(size);
58        }
59        return sizes;
60    }
61
62    /**
63     * How many bytes are still available from the last allocated chunk
64     */
65    template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
66    static std::size_t AvailableMemoryFromChunk(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource)
67    {
68        return resource.m_available_memory_end - resource.m_available_memory_it;
69    }
70
71    /**
72     * Once all blocks are given back to the resource, tests that the freelists are consistent:
73     *
74     * * All data in the freelists must come from the chunks
75     * * Memory doesn't overlap
76     * * Each byte in the chunks can be accounted for in either the freelist or as available bytes.
77     */
78    template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
79    static void CheckAllDataAccountedFor(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource)
80    {
81        // collect all free blocks by iterating all freelists
82        std::vector<PtrAndBytes> free_blocks;
83        for (std::size_t freelist_idx = 0; freelist_idx < resource.m_free_lists.size(); ++freelist_idx) {
84            std::size_t bytes = freelist_idx * resource.ELEM_ALIGN_BYTES;
85            auto* ptr = resource.m_free_lists[freelist_idx];
86            while (ptr != nullptr) {
87                free_blocks.emplace_back(ptr, bytes);
88                const auto* ptr_ = ptr;
89                ASAN_UNPOISON_MEMORY_REGION(ptr_, sizeof(typename PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>::ListNode));
90                ptr = ptr->m_next;
91                ASAN_POISON_MEMORY_REGION(ptr_, sizeof(typename PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>::ListNode));
92            }
93        }
94        // also add whatever has not yet been used for blocks
95        auto num_available_bytes = resource.m_available_memory_end - resource.m_available_memory_it;
96        if (num_available_bytes > 0) {
97            free_blocks.emplace_back(resource.m_available_memory_it, num_available_bytes);
98        }
99
100        // collect all chunks
101        std::vector<PtrAndBytes> chunks;
102        for (const std::byte* ptr : resource.m_allocated_chunks) {
103            chunks.emplace_back(ptr, resource.ChunkSizeBytes());
104        }
105
106        // now we have all the data from all freelists on the one hand side, and all chunks on the other hand side.
107        // To check if all of them match, sort by address and iterate.
108        std::sort(free_blocks.begin(), free_blocks.end());
109        std::sort(chunks.begin(), chunks.end());
110
111        auto chunk_it = chunks.begin();
112        auto chunk_ptr_remaining = chunk_it->ptr;
113        auto chunk_size_remaining = chunk_it->size;
114        for (const auto& free_block : free_blocks) {
115            if (chunk_size_remaining == 0) {
116                assert(chunk_it != chunks.end());
117                ++chunk_it;
118                assert(chunk_it != chunks.end());
119                chunk_ptr_remaining = chunk_it->ptr;
120                chunk_size_remaining = chunk_it->size;
121            }
122            assert(free_block.ptr == chunk_ptr_remaining);                   // ensure addresses match
123            assert(free_block.size <= chunk_size_remaining);                 // ensure no overflow
124            assert((free_block.ptr & (resource.ELEM_ALIGN_BYTES - 1)) == 0); // ensure correct alignment
125            chunk_ptr_remaining += free_block.size;
126            chunk_size_remaining -= free_block.size;
127        }
128        // ensure we are at the end of the chunks
129        assert(chunk_ptr_remaining == chunk_it->ptr + chunk_it->size);
130        ++chunk_it;
131        assert(chunk_it == chunks.end());
132        assert(chunk_size_remaining == 0);
133    }
134};
135
136#endif // BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H
137