Line data    Source code

       1             : // Copyright (c) 2022 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             : #ifndef BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H
       6             : #define BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H
       7             : 
       8             : #include <support/allocators/pool.h>
       9             : 
      10             : #include <algorithm>
      11             : #include <cassert>
      12             : #include <cstddef>
      13             : #include <cstdint>
      14             : #include <vector>
      15             : 
      16             : /**
      17             :  * Helper to get access to private parts of PoolResource. Used in unit tests and in the fuzzer
      18             :  */
      19             : class PoolResourceTester
      20             : {
      21             :     struct PtrAndBytes {
      22             :         uintptr_t ptr;
      23             :         std::size_t size;
      24             : 
      25           0 :         PtrAndBytes(const void* p, std::size_t s)
      26           0 :             : ptr(reinterpret_cast<uintptr_t>(p)), size(s)
      27             :         {
      28           0 :         }
      29             : 
      30             :         /**
      31             :          * defines a sort ordering by the pointer value
      32             :          */
      33           0 :         friend bool operator<(PtrAndBytes const& a, PtrAndBytes const& b)
      34             :         {
      35           0 :             return a.ptr < b.ptr;
      36             :         }
      37             :     };
      38             : 
      39             : public:
      40             :     /**
      41             :      * Extracts the number of elements per freelist
      42             :      */
      43             :     template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
      44             :     static std::vector<std::size_t> FreeListSizes(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource)
      45             :     {
      46             :         auto sizes = std::vector<std::size_t>();
      47             :         for (const auto* ptr : resource.m_free_lists) {
      48             :             size_t size = 0;
      49             :             while (ptr != nullptr) {
      50             :                 ++size;
      51             :                 ptr = ptr->m_next;
      52             :             }
      53             :             sizes.push_back(size);
      54             :         }
      55             :         return sizes;
      56             :     }
      57             : 
      58             :     /**
      59             :      * How many bytes are still available from the last allocated chunk
      60             :      */
      61             :     template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
      62             :     static std::size_t AvailableMemoryFromChunk(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource)
      63             :     {
      64             :         return resource.m_available_memory_end - resource.m_available_memory_it;
      65             :     }
      66             : 
      67             :     /**
      68             :      * Once all blocks are given back to the resource, tests that the freelists are consistent:
      69             :      *
      70             :      * * All data in the freelists must come from the chunks
      71             :      * * Memory doesn't overlap
      72             :      * * Each byte in the chunks can be accounted for in either the freelist or as available bytes.
      73             :      */
      74             :     template <std::size_t MAX_BLOCK_SIZE_BYTES, std::size_t ALIGN_BYTES>
      75           0 :     static void CheckAllDataAccountedFor(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource)
      76             :     {
      77             :         // collect all free blocks by iterating all freelists
      78           0 :         std::vector<PtrAndBytes> free_blocks;
      79           0 :         for (std::size_t freelist_idx = 0; freelist_idx < resource.m_free_lists.size(); ++freelist_idx) {
      80           0 :             std::size_t bytes = freelist_idx * resource.ELEM_ALIGN_BYTES;
      81           0 :             auto* ptr = resource.m_free_lists[freelist_idx];
      82           0 :             while (ptr != nullptr) {
      83           0 :                 free_blocks.emplace_back(ptr, bytes);
      84           0 :                 ptr = ptr->m_next;
      85             :             }
      86           0 :         }
      87             :         // also add whatever has not yet been used for blocks
      88           0 :         auto num_available_bytes = resource.m_available_memory_end - resource.m_available_memory_it;
      89           0 :         if (num_available_bytes > 0) {
      90           0 :             free_blocks.emplace_back(resource.m_available_memory_it, num_available_bytes);
      91           0 :         }
      92             : 
      93             :         // collect all chunks
      94           0 :         std::vector<PtrAndBytes> chunks;
      95           0 :         for (const std::byte* ptr : resource.m_allocated_chunks) {
      96           0 :             chunks.emplace_back(ptr, resource.ChunkSizeBytes());
      97             :         }
      98             : 
      99             :         // now we have all the data from all freelists on the one hand side, and all chunks on the other hand side.
     100             :         // To check if all of them match, sort by address and iterate.
     101           0 :         std::sort(free_blocks.begin(), free_blocks.end());
     102           0 :         std::sort(chunks.begin(), chunks.end());
     103             : 
     104           0 :         auto chunk_it = chunks.begin();
     105           0 :         auto chunk_ptr_remaining = chunk_it->ptr;
     106           0 :         auto chunk_size_remaining = chunk_it->size;
     107           0 :         for (const auto& free_block : free_blocks) {
     108           0 :             if (chunk_size_remaining == 0) {
     109           0 :                 assert(chunk_it != chunks.end());
     110           0 :                 ++chunk_it;
     111           0 :                 assert(chunk_it != chunks.end());
     112           0 :                 chunk_ptr_remaining = chunk_it->ptr;
     113           0 :                 chunk_size_remaining = chunk_it->size;
     114           0 :             }
     115           0 :             assert(free_block.ptr == chunk_ptr_remaining);                   // ensure addresses match
     116           0 :             assert(free_block.size <= chunk_size_remaining);                 // ensure no overflow
     117           0 :             assert((free_block.ptr & (resource.ELEM_ALIGN_BYTES - 1)) == 0); // ensure correct alignment
     118           0 :             chunk_ptr_remaining += free_block.size;
     119           0 :             chunk_size_remaining -= free_block.size;
     120             :         }
     121             :         // ensure we are at the end of the chunks
     122           0 :         assert(chunk_ptr_remaining == chunk_it->ptr + chunk_it->size);
     123           0 :         ++chunk_it;
     124           0 :         assert(chunk_it == chunks.end());
     125           0 :         assert(chunk_size_remaining == 0);
     126           0 :     }
     127             : };
     128             : 
     129             : #endif // BITCOIN_TEST_UTIL_POOLRESOURCETESTER_H