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