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