Branch data     Line data    Source code

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