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