pool_tests.cpp 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 #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 BOOST_AUTO_TEST_CASE(basic_allocating)
21 {
22 auto resource = PoolResource<8, 8>();
23 PoolResourceTester::CheckAllDataAccountedFor(resource);
24
25 // first chunk is already allocated
26 size_t expected_bytes_available = resource.ChunkSizeBytes();
27 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
28
29 // chunk is used, no more allocation
30 void* block = resource.Allocate(8, 8);
31 expected_bytes_available -= 8;
32 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
33
34 BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]);
35 resource.Deallocate(block, 8, 8);
36 PoolResourceTester::CheckAllDataAccountedFor(resource);
37 BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
38
39 // alignment is too small, but the best fitting freelist is used. Nothing is allocated.
40 void* b = resource.Allocate(8, 1);
41 BOOST_TEST(b == block); // we got the same block of memory as before
42 BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]);
43 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
44
45 resource.Deallocate(block, 8, 1);
46 PoolResourceTester::CheckAllDataAccountedFor(resource);
47 BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
48 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
49
50 // can't use resource because alignment is too big, allocate system memory
51 b = resource.Allocate(8, 16);
52 BOOST_TEST(b != block);
53 block = b;
54 PoolResourceTester::CheckAllDataAccountedFor(resource);
55 BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
56 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
57
58 resource.Deallocate(block, 8, 16);
59 PoolResourceTester::CheckAllDataAccountedFor(resource);
60 BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
61 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
62
63 // can't use chunk because size is too big
64 block = resource.Allocate(16, 8);
65 PoolResourceTester::CheckAllDataAccountedFor(resource);
66 BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
67 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
68
69 resource.Deallocate(block, 16, 8);
70 PoolResourceTester::CheckAllDataAccountedFor(resource);
71 BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
72 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 void* p = resource.Allocate(0, 1);
77 BOOST_TEST(0 == PoolResourceTester::FreeListSizes(resource)[1]);
78 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
79
80 resource.Deallocate(p, 0, 1);
81 PoolResourceTester::CheckAllDataAccountedFor(resource);
82 BOOST_TEST(1 == PoolResourceTester::FreeListSizes(resource)[1]);
83 BOOST_TEST(expected_bytes_available == PoolResourceTester::AvailableMemoryFromChunk(resource));
84 }
85
86 // Allocates from 0 to n bytes were n > the PoolResource's data, and each should work
87 BOOST_AUTO_TEST_CASE(allocate_any_byte)
88 {
89 auto resource = PoolResource<128, 8>(1024);
90
91 uint8_t num_allocs = 200;
92
93 auto data = std::vector<std::span<uint8_t>>();
94
95 // allocate an increasing number of bytes
96 for (uint8_t num_bytes = 0; num_bytes < num_allocs; ++num_bytes) {
97 uint8_t* bytes = new (resource.Allocate(num_bytes, 1)) uint8_t[num_bytes];
98 BOOST_TEST(bytes != nullptr);
99 data.emplace_back(bytes, num_bytes);
100
101 // set each byte to num_bytes
102 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 uint8_t val = 0;
107 for (auto const& span : data) {
108 for (auto x : span) {
109 BOOST_TEST(val == x);
110 }
111 std::destroy(span.data(), span.data() + span.size());
112 resource.Deallocate(span.data(), span.size(), 1);
113 ++val;
114 }
115
116 PoolResourceTester::CheckAllDataAccountedFor(resource);
117 }
118
119 BOOST_AUTO_TEST_CASE(random_allocations)
120 {
121 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 auto resource = PoolResource<128, 8>(65536);
129 std::vector<PtrSizeAlignment> ptr_size_alignment{};
130 for (size_t i = 0; i < 1000; ++i) {
131 // make it a bit more likely to allocate than deallocate
132 if (ptr_size_alignment.empty() || 0 != m_rng.randrange(4)) {
133 // allocate a random item
134 std::size_t alignment = std::size_t{1} << m_rng.randrange(8); // 1, 2, ..., 128
135 std::size_t size = (m_rng.randrange(200) / alignment + 1) * alignment; // multiple of alignment
136 void* ptr = resource.Allocate(size, alignment);
137 BOOST_TEST(ptr != nullptr);
138 BOOST_TEST((reinterpret_cast<uintptr_t>(ptr) & (alignment - 1)) == 0);
139 ptr_size_alignment.push_back({ptr, size, alignment});
140 } else {
141 // deallocate a random item
142 auto& x = ptr_size_alignment[m_rng.randrange(ptr_size_alignment.size())];
143 resource.Deallocate(x.ptr, x.bytes, x.alignment);
144 x = ptr_size_alignment.back();
145 ptr_size_alignment.pop_back();
146 }
147 }
148
149 // deallocate all the rest
150 for (auto const& x : ptr_size_alignment) {
151 resource.Deallocate(x.ptr, x.bytes, x.alignment);
152 }
153
154 PoolResourceTester::CheckAllDataAccountedFor(resource);
155 }
156
157 BOOST_AUTO_TEST_CASE(memusage_test)
158 {
159 auto std_map = std::unordered_map<int64_t, int64_t>{};
160
161 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 auto resource = Map::allocator_type::ResourceType(1024);
168
169 PoolResourceTester::CheckAllDataAccountedFor(resource);
170
171 {
172 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 BOOST_TEST(memusage::DynamicUsage(std_map) != memusage::DynamicUsage(resource_map));
176
177 for (size_t i = 0; i < 10000; ++i) {
178 std_map[i];
179 resource_map[i];
180 }
181
182 // Eventually the resource_map should have a much lower memory usage because it has less malloc overhead
183 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 auto max_nodes_per_chunk = resource.ChunkSizeBytes() / sizeof(Map::value_type);
187 auto min_num_allocated_chunks = resource_map.size() / max_nodes_per_chunk + 1;
188 BOOST_TEST(resource.NumAllocatedChunks() >= min_num_allocated_chunks);
189 }
190
191 PoolResourceTester::CheckAllDataAccountedFor(resource);
192 }
193
194 BOOST_AUTO_TEST_SUITE_END()
195