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