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