arenaallocator.cpp (8045B)
1 // This file is part of Blend2D project <https://blend2d.com> 2 // 3 // See blend2d.h or LICENSE.md for license and copyright information 4 // SPDX-License-Identifier: Zlib 5 6 #include "../api-build_p.h" 7 #include "../support/arenaallocator_p.h" 8 #include "../support/intops_p.h" 9 10 namespace bl { 11 12 // bl::ArenaAllocator - API 13 // ======================== 14 15 //! Zero block, used by a default constructed `ArenaAllocator`, which doesn't hold any allocated block. This block 16 //! must be properly aligned so when arena allocator aligns its current pointer to check for aligned allocation it 17 //! would not overflow past the end of the block - which is the same as the beginning of the block as it has no size. 18 struct alignas(64) ArenaAllocatorZeroBlock { 19 uint8_t padding[64 - sizeof(ArenaAllocator::Block)]; 20 ArenaAllocator::Block block; 21 }; 22 23 // Zero size block used by `ArenaAllocator` that doesn't have any memory allocated. 24 // Should be allocated in read-only memory and should never be modified. 25 static const ArenaAllocatorZeroBlock kArenaAllocatorZeroBlock = { { 0 }, { nullptr, nullptr, 0 } }; 26 27 static BL_INLINE void ArenaAllocator_assignZeroBlock(ArenaAllocator* self) noexcept { 28 ArenaAllocator::Block* block = const_cast<ArenaAllocator::Block*>(&kArenaAllocatorZeroBlock.block); 29 self->_ptr = block->data(); 30 self->_end = block->data(); 31 self->_block = block; 32 } 33 34 static BL_INLINE void ArenaAllocator_assignBlock(ArenaAllocator* self, ArenaAllocator::Block* block) noexcept { 35 size_t alignment = self->block_alignment(); 36 self->_ptr = IntOps::align_up(block->data(), alignment); 37 self->_end = block->data() + block->size; 38 self->_block = block; 39 } 40 41 void ArenaAllocator::_init(size_t block_size, size_t block_alignment, void* static_data, size_t static_size) noexcept { 42 BL_ASSERT(block_size >= kMinBlockSize); 43 BL_ASSERT(block_size <= kMaxBlockSize); 44 BL_ASSERT(block_alignment <= 64); 45 46 ArenaAllocator_assignZeroBlock(this); 47 48 size_t block_size_shift = IntOps::bit_size_of<size_t>() - IntOps::clz(block_size); 49 size_t block_alignment_shift = IntOps::bit_size_of<size_t>() - IntOps::clz(block_alignment | (size_t(1) << 3)); 50 51 _block_alignment_shift = uint8_t(block_alignment_shift); 52 _min_block_size_shift = uint8_t(block_size_shift); 53 _max_block_size_shift = uint8_t(25); // (1 << 25) Equals 32 MiB blocks (should be enough for all cases) 54 _has_static_block = uint8_t(static_data != nullptr); 55 _reserved = uint8_t(0u); 56 _block_count = size_t(static_data != nullptr); 57 58 // Setup the first [temporary] block, if necessary. 59 if (static_data) { 60 Block* block = static_cast<Block*>(static_data); 61 block->prev = nullptr; 62 block->next = nullptr; 63 64 BL_ASSERT(static_size >= kBlockSize); 65 block->size = static_size - kBlockSize; 66 67 ArenaAllocator_assignBlock(this, block); 68 _block_count = 1u; 69 } 70 } 71 72 void ArenaAllocator::reset() noexcept { 73 // Can't be altered. 74 Block* cur = _block; 75 if (cur == &kArenaAllocatorZeroBlock.block) 76 return; 77 78 Block* initial = const_cast<ArenaAllocator::Block*>(&kArenaAllocatorZeroBlock.block); 79 _ptr = initial->data(); 80 _end = initial->data(); 81 _block = initial; 82 _block_count = 0u; 83 84 // Since cur can be in the middle of the double-linked list, we have to traverse both directions separately. 85 Block* next = cur->next; 86 do { 87 Block* prev = cur->prev; 88 89 // If this is the first block and this AllocatorTmp is temporary then the first block is statically allocated. 90 // We cannot free it and it makes sense to keep it even when this is hard reset. 91 if (prev == nullptr && _has_static_block) { 92 cur->prev = nullptr; 93 cur->next = nullptr; 94 ArenaAllocator_assignBlock(this, cur); 95 break; 96 } 97 98 ::free(cur); 99 cur = prev; 100 } while (cur); 101 102 cur = next; 103 while (cur) { 104 next = cur->next; 105 ::free(cur); 106 cur = next; 107 } 108 } 109 110 void ArenaAllocator::clear() noexcept { 111 Block* cur = _block; 112 while (cur->prev) { 113 cur = cur->prev; 114 } 115 ArenaAllocator_assignBlock(this, cur); 116 } 117 118 void* ArenaAllocator::_alloc(size_t size, size_t alignment) noexcept { 119 Block* cur_block = _block; 120 Block* next = cur_block->next; 121 122 size_t default_block_alignment = block_alignment(); 123 size_t required_block_alignment = bl_max<size_t>(alignment, default_block_alignment); 124 125 // If the `Arena` has been cleared the current block doesn't have to be the last one. Check if there is a block 126 // that can be used instead of allocating a new one. If there is a `next` block it's completely unused, we don't 127 // have to check for remaining bytes in that case. 128 if (next) { 129 uint8_t* ptr = IntOps::align_up(next->data(), required_block_alignment); 130 uint8_t* end = next->data() + next->size; 131 132 if (size <= (size_t)(end - ptr)) { 133 _block = next; 134 _ptr = ptr + size; 135 _end = end; 136 return static_cast<void*>(ptr); 137 } 138 } 139 140 // Calculates the "default" size of a next block - in most cases this would be enough for the allocation. In 141 // general we want to gradually increase block size when more and more blocks are allocated until the maximum 142 // block size. Since we use shifts (aka log2(size) sizes) we just need block count and minumum/maximum block 143 // size shift to calculate the final size. 144 size_t default_block_size_shift = bl_min<size_t>(_block_count + _min_block_size_shift, _max_block_size_shift); 145 size_t default_block_size = size_t(1) << default_block_size_shift; 146 147 // Allocate a new block. We have to accommodate all possible overheads so after the memory is allocated and then 148 // properly aligned there will be size for the requested memory. In 99.9999% cases this is never a problem, but 149 // we must be sure that even rare border cases would allocate properly. 150 size_t alignment_overhead = required_block_alignment - bl_min<size_t>(required_block_alignment, BL_ALLOC_ALIGNMENT); 151 size_t block_size_overhead = kBlockSize + BL_ALLOC_OVERHEAD + alignment_overhead; 152 153 // If the requested size is larger than a default calculated block size -> increase block size so the allocation 154 // would be enough to fit the requested size. 155 size_t final_block_size = default_block_size; 156 157 if (BL_UNLIKELY(size > default_block_size - block_size_overhead)) { 158 if (BL_UNLIKELY(size > SIZE_MAX - block_size_overhead)) { 159 // This would probably never happen in practice - however, it needs to be done to stop malicious cases like 160 // `alloc(SIZE_MAX)`. 161 return nullptr; 162 } 163 final_block_size = size + alignment_overhead + kBlockSize; 164 } 165 else { 166 final_block_size -= BL_ALLOC_OVERHEAD; 167 } 168 169 // Allocate new block. 170 Block* new_block = static_cast<Block*>(::malloc(final_block_size)); 171 172 if (BL_UNLIKELY(!new_block)) { 173 return nullptr; 174 } 175 176 // final_block_size includes the struct size, which must be avoided when assigning the size to a newly allocated block. 177 size_t real_block_size = final_block_size - kBlockSize; 178 179 // Align the pointer to `minimum_alignment` and adjust the size of this block accordingly. It's the same as using 180 // `minimum_alignment - Support::align_up_diff()`, just written differently. 181 new_block->prev = nullptr; 182 new_block->next = nullptr; 183 new_block->size = real_block_size; 184 185 if (cur_block != &kArenaAllocatorZeroBlock.block) { 186 new_block->prev = cur_block; 187 cur_block->next = new_block; 188 189 // Does only happen if there is a next block, but the requested memory can't fit into it. In this case a new 190 // buffer is allocated and inserted between the current block and the next one. 191 if (next) { 192 new_block->next = next; 193 next->prev = new_block; 194 } 195 } 196 197 uint8_t* ptr = IntOps::align_up(new_block->data(), required_block_alignment); 198 uint8_t* end = new_block->data() + real_block_size; 199 200 _ptr = ptr + size; 201 _end = end; 202 _block = new_block; 203 _block_count++; 204 205 BL_ASSERT(_ptr <= _end); 206 return static_cast<void*>(ptr); 207 } 208 209 void* ArenaAllocator::alloc_zeroed(size_t size, size_t alignment) noexcept { 210 void* p = alloc(size, alignment); 211 if (BL_UNLIKELY(!p)) 212 return p; 213 return memset(p, 0, size); 214 } 215 216 } // {bl}