1 // Copyright (c) 2022 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 #ifndef LIMENKA_TEST_UTIL_POOLRESOURCETESTER_H
6 #define LIMENKA_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 PtrAndBytes(const void* p, std::size_t s)
26 : ptr(reinterpret_cast<uintptr_t>(p)), size(s)
27 {
28 }
29 30 /**
31 * defines a sort ordering by the pointer value
32 */
33 friend bool operator<(PtrAndBytes const& a, PtrAndBytes const& b)
34 {
35 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 static void CheckAllDataAccountedFor(const PoolResource<MAX_BLOCK_SIZE_BYTES, ALIGN_BYTES>& resource)
76 {
77 // collect all free blocks by iterating all freelists
78 std::vector<PtrAndBytes> free_blocks;
79 for (std::size_t freelist_idx = 0; freelist_idx < resource.m_free_lists.size(); ++freelist_idx) {
80 std::size_t bytes = freelist_idx * resource.ELEM_ALIGN_BYTES;
81 auto* ptr = resource.m_free_lists[freelist_idx];
82 while (ptr != nullptr) {
83 free_blocks.emplace_back(ptr, bytes);
84 ptr = ptr->m_next;
85 }
86 }
87 // also add whatever has not yet been used for blocks
88 auto num_available_bytes = resource.m_available_memory_end - resource.m_available_memory_it;
89 if (num_available_bytes > 0) {
90 free_blocks.emplace_back(resource.m_available_memory_it, num_available_bytes);
91 }
92 93 // collect all chunks
94 std::vector<PtrAndBytes> chunks;
95 for (const std::byte* ptr : resource.m_allocated_chunks) {
96 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 std::sort(free_blocks.begin(), free_blocks.end());
102 std::sort(chunks.begin(), chunks.end());
103 104 auto chunk_it = chunks.begin();
105 auto chunk_ptr_remaining = chunk_it->ptr;
106 auto chunk_size_remaining = chunk_it->size;
107 for (const auto& free_block : free_blocks) {
108 if (chunk_size_remaining == 0) {
109 assert(chunk_it != chunks.end());
110 ++chunk_it;
111 assert(chunk_it != chunks.end());
112 chunk_ptr_remaining = chunk_it->ptr;
113 chunk_size_remaining = chunk_it->size;
114 }
115 assert(free_block.ptr == chunk_ptr_remaining); // ensure addresses match
116 assert(free_block.size <= chunk_size_remaining); // ensure no overflow
117 assert((free_block.ptr & (resource.ELEM_ALIGN_BYTES - 1)) == 0); // ensure correct alignment
118 chunk_ptr_remaining += free_block.size;
119 chunk_size_remaining -= free_block.size;
120 }
121 // ensure we are at the end of the chunks
122 assert(chunk_ptr_remaining == chunk_it->ptr + chunk_it->size);
123 ++chunk_it;
124 assert(chunk_it == chunks.end());
125 assert(chunk_size_remaining == 0);
126 }
127 };
128 129 #endif // LIMENKA_TEST_UTIL_POOLRESOURCETESTER_H
130