Inside Bitcoin

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