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 : : #include <memusage.h>
6 : : #include <support/allocators/pool.h>
7 : : #include <test/util/poolresourcetester.h>
8 : : #include <test/util/random.h>
9 : : #include <test/util/setup_common.h>
10 : :
11 : : #include <boost/test/unit_test.hpp>
12 : :
13 : : #include <cstddef>
14 : : #include <cstdint>
15 : : #include <unordered_map>
16 : : #include <vector>
17 : :
18 : : BOOST_FIXTURE_TEST_SUITE(pool_tests, BasicTestingSetup)
19 : :
20 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(basic_allocating)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
21 : : {
22 : 1 : auto resource = PoolResource<8, 8>();
23 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
24 : :
25 : : // first chunk is already allocated
26 [ + - ]: 1 : size_t expected_bytes_available = resource.ChunkSizeBytes();
27 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
28 : :
29 : : // chunk is used, no more allocation
30 [ + - ]: 1 : void* block = resource.Allocate(8, 8);
31 : 1 : expected_bytes_available -= 8;
32 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
33 : :
34 [ + - + - : 2 : BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - ]
35 [ + - ]: 1 : resource.Deallocate(block, 8, 8);
36 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
37 [ + - + - : 2 : BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
38 : :
39 : : // alignment is too small, but the best fitting freelist is used. Nothing is allocated.
40 [ + - ]: 1 : void* b = resource.Allocate(8, 1);
41 [ + - + - : 2 : BOOST_TEST(b == block); // we got the same block of memory as before
+ - + - ]
42 [ + - + - : 2 : BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
43 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
44 : :
45 [ + - ]: 1 : resource.Deallocate(block, 8, 1);
46 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
47 [ + - + - : 2 : BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
48 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
49 : :
50 : : // can't use resource because alignment is too big, allocate system memory
51 [ + - ]: 1 : b = resource.Allocate(8, 16);
52 [ + - + - : 2 : BOOST_TEST(b != block);
+ - + - ]
53 : 1 : block = b;
54 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
55 [ + - + - : 2 : BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
56 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - ]
57 : :
58 : 1 : resource.Deallocate(block, 8, 16);
59 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
60 [ + - + - : 2 : BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
61 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
62 : :
63 : : // can't use chunk because size is too big
64 [ + - ]: 1 : block = resource.Allocate(16, 8);
65 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
66 [ + - + - : 2 : BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
67 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - ]
68 : :
69 : 1 : resource.Deallocate(block, 16, 8);
70 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
71 [ + - + - : 2 : BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
72 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
73 : :
74 : : // it's possible that 0 bytes are allocated, make sure this works. In that case the call is forwarded to operator new
75 : : // 0 bytes takes one entry from the first freelist
76 [ + - ]: 1 : void* p = resource.Allocate(0, 1);
77 [ + - + - : 2 : BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
78 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
79 : :
80 [ + - ]: 1 : resource.Deallocate(p, 0, 1);
81 : : PoolResourceTester::CheckAllDataAccountedFor(resource);
82 [ + - + - : 2 : BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
+ - + - +
- ]
83 [ + - + - : 2 : BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
+ - + - ]
84 : 1 : }
85 : :
86 : : // Allocates from 0 to n bytes were n > the PoolResource's data, and each should work
87 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(allocate_any_byte)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
88 : : {
89 : 1 : auto resource = PoolResource<128, 8>(1024);
90 : :
91 : 1 : uint8_t num_allocs = 200;
92 : :
93 : 1 : auto data = std::vector<Span<uint8_t>>();
94 : :
95 : : // allocate an increasing number of bytes
96 [ + + ]: 201 : for (uint8_t num_bytes = 0; num_bytes < num_allocs; ++num_bytes) {
97 [ + - ]: 200 : uint8_t* bytes = new (resource.Allocate(num_bytes, 1)) uint8_t[num_bytes];
98 [ + - + - : 400 : BOOST_TEST(bytes != nullptr);
+ - + - ]
99 [ + - ]: 200 : data.emplace_back(bytes, num_bytes);
100 : :
101 : : // set each byte to num_bytes
102 : 200 : std::fill(bytes, bytes + num_bytes, num_bytes);
103 : : }
104 : :
105 : : // now that we got all allocated, test if all still have the correct values, and give everything back to the allocator
106 : 1 : uint8_t val = 0;
107 [ + + ]: 201 : for (auto const& span : data) {
108 [ + + ]: 20100 : for (auto x : span) {
109 [ + - + - : 39800 : BOOST_TEST(val == x);
+ - ]
110 : : }
111 : 200 : std::destroy(span.data(), span.data() + span.size());
112 : 200 : resource.Deallocate(span.data(), span.size(), 1);
113 : 200 : ++val;
114 : : }
115 : :
116 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
117 : 1 : }
118 : :
119 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(random_allocations)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
120 : : {
121 : 1 : struct PtrSizeAlignment {
122 : : void* ptr;
123 : : size_t bytes;
124 : : size_t alignment;
125 : : };
126 : :
127 : : // makes a bunch of random allocations and gives all of them back in random order.
128 : 1 : auto resource = PoolResource<128, 8>(65536);
129 : 1 : std::vector<PtrSizeAlignment> ptr_size_alignment{};
130 [ + + ]: 1001 : for (size_t i = 0; i < 1000; ++i) {
131 : : // make it a bit more likely to allocate than deallocate
132 [ + + + + ]: 1000 : if (ptr_size_alignment.empty() || 0 != m_rng.randrange(4)) {
133 : : // allocate a random item
134 : 744 : std::size_t alignment = std::size_t{1} << m_rng.randrange(8); // 1, 2, ..., 128
135 : 744 : std::size_t size = (m_rng.randrange(200) / alignment + 1) * alignment; // multiple of alignment
136 [ + - ]: 744 : void* ptr = resource.Allocate(size, alignment);
137 [ + - + - : 1488 : BOOST_TEST(ptr != nullptr);
+ - + - ]
138 [ + - + - : 1488 : BOOST_TEST((reinterpret_cast<uintptr_t>(ptr) & (alignment - 1)) == 0);
+ - + - ]
139 [ + - ]: 1000 : ptr_size_alignment.push_back({ptr, size, alignment});
140 : : } else {
141 : : // deallocate a random item
142 : 256 : auto& x = ptr_size_alignment[m_rng.randrange(ptr_size_alignment.size())];
143 : 256 : resource.Deallocate(x.ptr, x.bytes, x.alignment);
144 : 256 : x = ptr_size_alignment.back();
145 : 256 : ptr_size_alignment.pop_back();
146 : : }
147 : : }
148 : :
149 : : // deallocate all the rest
150 [ + + ]: 489 : for (auto const& x : ptr_size_alignment) {
151 : 488 : resource.Deallocate(x.ptr, x.bytes, x.alignment);
152 : : }
153 : :
154 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
155 : 1 : }
156 : :
157 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(memusage_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
158 : : {
159 [ + - ]: 1 : auto std_map = std::unordered_map<int64_t, int64_t>{};
160 : :
161 : 1 : using Map = std::unordered_map<int64_t,
162 : : int64_t,
163 : : std::hash<int64_t>,
164 : : std::equal_to<int64_t>,
165 : : PoolAllocator<std::pair<const int64_t, int64_t>,
166 : : sizeof(std::pair<const int64_t, int64_t>) + sizeof(void*) * 4>>;
167 [ + - ]: 1 : auto resource = Map::allocator_type::ResourceType(1024);
168 : :
169 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
170 : :
171 : 1 : {
172 [ + - ]: 1 : auto resource_map = Map{0, std::hash<int64_t>{}, std::equal_to<int64_t>{}, &resource};
173 : :
174 : : // can't have the same resource usage
175 [ + - + - : 3 : BOOST_TEST(memusage::DynamicUsage(std_map) != memusage::DynamicUsage(resource_map));
+ - + - ]
176 : :
177 [ + + ]: 10001 : for (size_t i = 0; i < 10000; ++i) {
178 [ + - ]: 10000 : std_map[i];
179 [ + - ]: 10000 : resource_map[i];
180 : : }
181 : :
182 : : // Eventually the resource_map should have a much lower memory usage because it has less malloc overhead
183 [ + - + - : 3 : BOOST_TEST(memusage::DynamicUsage(resource_map) <= memusage::DynamicUsage(std_map) * 90 / 100);
+ - + - ]
184 : :
185 : : // Make sure the pool is actually used by the nodes
186 [ + - ]: 1 : auto max_nodes_per_chunk = resource.ChunkSizeBytes() / sizeof(Map::value_type);
187 [ + - ]: 1 : auto min_num_allocated_chunks = resource_map.size() / max_nodes_per_chunk + 1;
188 [ + - + - : 2 : BOOST_TEST(resource.NumAllocatedChunks() >= min_num_allocated_chunks);
+ - ]
189 : 0 : }
190 : :
191 [ + - ]: 1 : PoolResourceTester::CheckAllDataAccountedFor(resource);
192 : 1 : }
193 : :
194 : : BOOST_AUTO_TEST_SUITE_END()
|
