allocator_tests.cpp raw
1 // Copyright (c) 2012-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 <common/system.h>
6 #include <support/lockedpool.h>
7
8 #include <limits>
9 #include <memory>
10 #include <stdexcept>
11 #include <util/byte_units.h>
12 #include <utility>
13 #include <vector>
14
15 #include <boost/test/unit_test.hpp>
16
17 BOOST_AUTO_TEST_SUITE(allocator_tests)
18
19 BOOST_AUTO_TEST_CASE(arena_tests)
20 {
21 // Fake memory base address for testing
22 // without actually using memory.
23 void *synth_base = reinterpret_cast<void*>(0x08000000);
24 const size_t synth_size{1_MiB};
25 Arena b(synth_base, synth_size, 16);
26 void *chunk = b.alloc(1000);
27 #ifdef ARENA_DEBUG
28 b.walk();
29 #endif
30 BOOST_CHECK(chunk != nullptr);
31 BOOST_CHECK(b.stats().used == 1008); // Aligned to 16
32 BOOST_CHECK(b.stats().total == synth_size); // Nothing has disappeared?
33 b.free(chunk);
34 #ifdef ARENA_DEBUG
35 b.walk();
36 #endif
37 BOOST_CHECK(b.stats().used == 0);
38 BOOST_CHECK(b.stats().free == synth_size);
39 try { // Test exception on double-free
40 b.free(chunk);
41 BOOST_CHECK(0);
42 } catch(std::runtime_error &)
43 {
44 }
45
46 void *a0 = b.alloc(128);
47 void *a1 = b.alloc(256);
48 void *a2 = b.alloc(512);
49 BOOST_CHECK(b.stats().used == 896);
50 BOOST_CHECK(b.stats().total == synth_size);
51 #ifdef ARENA_DEBUG
52 b.walk();
53 #endif
54 b.free(a0);
55 #ifdef ARENA_DEBUG
56 b.walk();
57 #endif
58 BOOST_CHECK(b.stats().used == 768);
59 b.free(a1);
60 BOOST_CHECK(b.stats().used == 512);
61 void *a3 = b.alloc(128);
62 #ifdef ARENA_DEBUG
63 b.walk();
64 #endif
65 BOOST_CHECK(b.stats().used == 640);
66 b.free(a2);
67 BOOST_CHECK(b.stats().used == 128);
68 b.free(a3);
69 BOOST_CHECK(b.stats().used == 0);
70 BOOST_CHECK_EQUAL(b.stats().chunks_used, 0U);
71 BOOST_CHECK(b.stats().total == synth_size);
72 BOOST_CHECK(b.stats().free == synth_size);
73 BOOST_CHECK_EQUAL(b.stats().chunks_free, 1U);
74
75 std::vector<void*> addr;
76 BOOST_CHECK(b.alloc(0) == nullptr); // allocating 0 always returns nullptr
77 #ifdef ARENA_DEBUG
78 b.walk();
79 #endif
80 // Sweeping allocate all memory
81 addr.reserve(2048);
82 for (int x=0; x<1024; ++x)
83 addr.push_back(b.alloc(1024));
84 BOOST_CHECK(b.stats().free == 0);
85 BOOST_CHECK(b.alloc(1024) == nullptr); // memory is full, this must return nullptr
86 BOOST_CHECK(b.alloc(0) == nullptr);
87 for (int x=0; x<1024; ++x)
88 b.free(addr[x]);
89 addr.clear();
90 BOOST_CHECK(b.stats().total == synth_size);
91 BOOST_CHECK(b.stats().free == synth_size);
92
93 // Now in the other direction...
94 for (int x=0; x<1024; ++x)
95 addr.push_back(b.alloc(1024));
96 for (int x=0; x<1024; ++x)
97 b.free(addr[1023-x]);
98 addr.clear();
99
100 // Now allocate in smaller unequal chunks, then deallocate haphazardly
101 // Not all the chunks will succeed allocating, but freeing nullptr is
102 // allowed so that is no problem.
103 for (int x=0; x<2048; ++x)
104 addr.push_back(b.alloc(x+1));
105 for (int x=0; x<2048; ++x)
106 b.free(addr[((x*23)%2048)^242]);
107 addr.clear();
108
109 // Go entirely wild: free and alloc interleaved,
110 // generate targets and sizes using pseudo-randomness.
111 for (int x=0; x<2048; ++x)
112 addr.push_back(nullptr);
113 uint32_t s = 0x12345678;
114 for (int x=0; x<5000; ++x) {
115 int idx = s & (addr.size()-1);
116 if (s & 0x80000000) {
117 b.free(addr[idx]);
118 addr[idx] = nullptr;
119 } else if(!addr[idx]) {
120 addr[idx] = b.alloc((s >> 16) & 2047);
121 }
122 bool lsb = s & 1;
123 s >>= 1;
124 if (lsb)
125 s ^= 0xf00f00f0; // LFSR period 0xf7ffffe0
126 }
127 for (void *ptr: addr)
128 b.free(ptr);
129 addr.clear();
130
131 BOOST_CHECK(b.stats().total == synth_size);
132 BOOST_CHECK(b.stats().free == synth_size);
133 }
134
135 /** Mock LockedPageAllocator for testing */
136 class TestLockedPageAllocator: public LockedPageAllocator
137 {
138 public:
139 TestLockedPageAllocator(int count_in, int lockedcount_in): count(count_in), lockedcount(lockedcount_in) {}
140 void* AllocateLocked(size_t len, bool *lockingSuccess) override
141 {
142 *lockingSuccess = false;
143 if (count > 0) {
144 --count;
145
146 if (lockedcount > 0) {
147 --lockedcount;
148 *lockingSuccess = true;
149 }
150
151 return reinterpret_cast<void*>(uint64_t{static_cast<uint64_t>(0x08000000) + (count << 24)}); // Fake address, do not actually use this memory
152 }
153 return nullptr;
154 }
155 void FreeLocked(void* addr, size_t len) override
156 {
157 }
158 size_t GetLimit() override
159 {
160 return std::numeric_limits<size_t>::max();
161 }
162 private:
163 int count;
164 int lockedcount;
165 };
166
167 BOOST_AUTO_TEST_CASE(lockedpool_tests_mock)
168 {
169 // Test over three virtual arenas, of which one will succeed being locked
170 std::unique_ptr<LockedPageAllocator> x = std::make_unique<TestLockedPageAllocator>(3, 1);
171 LockedPool pool(std::move(x));
172 BOOST_CHECK(pool.stats().total == 0);
173 BOOST_CHECK(pool.stats().locked == 0);
174
175 // Ensure unreasonable requests are refused without allocating anything
176 void *invalid_toosmall = pool.alloc(0);
177 BOOST_CHECK(invalid_toosmall == nullptr);
178 BOOST_CHECK(pool.stats().used == 0);
179 BOOST_CHECK(pool.stats().free == 0);
180 void *invalid_toobig = pool.alloc(LockedPool::ARENA_SIZE+1);
181 BOOST_CHECK(invalid_toobig == nullptr);
182 BOOST_CHECK(pool.stats().used == 0);
183 BOOST_CHECK(pool.stats().free == 0);
184
185 void *a0 = pool.alloc(LockedPool::ARENA_SIZE / 2);
186 BOOST_CHECK(a0);
187 BOOST_CHECK(pool.stats().locked == LockedPool::ARENA_SIZE);
188 void *a1 = pool.alloc(LockedPool::ARENA_SIZE / 2);
189 BOOST_CHECK(a1);
190 void *a2 = pool.alloc(LockedPool::ARENA_SIZE / 2);
191 BOOST_CHECK(a2);
192 void *a3 = pool.alloc(LockedPool::ARENA_SIZE / 2);
193 BOOST_CHECK(a3);
194 void *a4 = pool.alloc(LockedPool::ARENA_SIZE / 2);
195 BOOST_CHECK(a4);
196 void *a5 = pool.alloc(LockedPool::ARENA_SIZE / 2);
197 BOOST_CHECK(a5);
198 // We've passed a count of three arenas, so this allocation should fail
199 void *a6 = pool.alloc(16);
200 BOOST_CHECK(!a6);
201
202 pool.free(a0);
203 pool.free(a2);
204 pool.free(a4);
205 pool.free(a1);
206 pool.free(a3);
207 pool.free(a5);
208 BOOST_CHECK(pool.stats().total == 3*LockedPool::ARENA_SIZE);
209 BOOST_CHECK(pool.stats().locked == LockedPool::ARENA_SIZE);
210 BOOST_CHECK(pool.stats().used == 0);
211 }
212
213 // These tests used the live LockedPoolManager object, this is also used
214 // by other tests so the conditions are somewhat less controllable and thus the
215 // tests are somewhat more error-prone.
216 BOOST_AUTO_TEST_CASE(lockedpool_tests_live)
217 {
218 LockedPoolManager &pool = LockedPoolManager::Instance();
219 LockedPool::Stats initial = pool.stats();
220
221 void *a0 = pool.alloc(16);
222 BOOST_CHECK(a0);
223 // Test reading and writing the allocated memory
224 *((uint32_t*)a0) = 0x1234;
225 BOOST_CHECK(*((uint32_t*)a0) == 0x1234);
226
227 pool.free(a0);
228 try { // Test exception on double-free
229 pool.free(a0);
230 BOOST_CHECK(0);
231 } catch(std::runtime_error &)
232 {
233 }
234 // If more than one new arena was allocated for the above tests, something is wrong
235 BOOST_CHECK(pool.stats().total <= (initial.total + LockedPool::ARENA_SIZE));
236 // Usage must be back to where it started
237 BOOST_CHECK(pool.stats().used == initial.used);
238 }
239
240 BOOST_AUTO_TEST_SUITE_END()
241