poolresourcetester.h raw
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 */
20 class 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
40 public:
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