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