1 // Copyright 2020 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <cstddef> 17 #include <cstdint> 18 #include <limits> 19 #include <new> 20 21 #include "pw_allocator/block/alignable.h" 22 #include "pw_allocator/block/allocatable.h" 23 #include "pw_allocator/block/basic.h" 24 #include "pw_allocator/block/contiguous.h" 25 #include "pw_allocator/block/iterable.h" 26 #include "pw_allocator/block/poisonable.h" 27 #include "pw_allocator/block/result.h" 28 #include "pw_allocator/block/with_layout.h" 29 #include "pw_allocator/layout.h" 30 #include "pw_assert/assert.h" 31 #include "pw_bytes/span.h" 32 #include "pw_preprocessor/compiler.h" 33 #include "pw_result/result.h" 34 #include "pw_status/status.h" 35 36 namespace pw::allocator { 37 38 /// Parameters type that encapsulates the block parameters. 39 /// 40 /// @tparam OffsetType Unsigned integral type used to encode offsets. Larger 41 /// types can address more memory, but consume greater 42 /// overhead. 43 /// @tparam WhenFree Optional intrusive type that uses the block's usable 44 /// space to track the block when free. This will affect 45 /// the minimum alignment, and what portion of the usable 46 /// space is skipped when poisoning. 47 template <typename OffsetType_, typename WhenFree> 48 struct DetailedBlockParameters { 49 using OffsetType = std::make_unsigned_t<OffsetType_>; 50 static constexpr Layout kLayoutWhenFree = Layout::Of<WhenFree>(); 51 }; 52 53 template <typename OffsetType_> 54 struct DetailedBlockParameters<OffsetType_, void> { 55 using OffsetType = std::make_unsigned_t<OffsetType_>; 56 static constexpr Layout kLayoutWhenFree = Layout(0, 1); 57 }; 58 59 /// A block implementation that implements most optional block mix-ins. 60 /// 61 /// This block dervies from various block mix-ins, allowing it to perform 62 /// aligned allocations, iterate over blocks, poison and check free blocks, 63 /// retrieve requested memory layouts, and more. 64 /// 65 /// The amount of memory that can be addressed by a block of this type depends 66 /// on it given `OffsetType`. This type is used to describe the size of both the 67 /// current and previous block, so the maximum addressable range is given by 68 /// `std::numeric_limits<OffsetType> * alignof(OffsetType)`. 69 /// 70 /// An additional 4 bytes are used to store details about an allocation, 71 /// including whether it is in use or free, whether it is poisoned, and what the 72 /// originally requested layout for a block was. 73 /// 74 /// See also the `DetailedBlock` alias which provides the `Parameters` type 75 /// automatically. 76 /// 77 /// @tparam Parameters Block traits, such as `DetailedBlockParameters`, which 78 /// encapsulate a set of template parameters. 79 template <typename Parameters> 80 class DetailedBlockImpl 81 : public BasicBlock<DetailedBlockImpl<Parameters>>, 82 public ForwardIterableBlock<DetailedBlockImpl<Parameters>>, 83 public ReverseIterableBlock<DetailedBlockImpl<Parameters>>, 84 public ContiguousBlock<DetailedBlockImpl<Parameters>>, 85 public AllocatableBlock<DetailedBlockImpl<Parameters>>, 86 public AlignableBlock<DetailedBlockImpl<Parameters>>, 87 public BlockWithLayout<DetailedBlockImpl<Parameters>>, 88 public PoisonableBlock<DetailedBlockImpl<Parameters>> { 89 private: 90 using BlockType = DetailedBlockImpl<Parameters>; 91 using Basic = BasicBlock<BlockType>; 92 93 public: 94 using OffsetType = typename Parameters::OffsetType; 95 96 using Range = typename ForwardIterableBlock<BlockType>::Range; 97 using Iterator = typename ForwardIterableBlock<BlockType>::Iterator; 98 99 using ReverseRange = typename ReverseIterableBlock<BlockType>::ReverseRange; 100 using ReverseIterator = 101 typename ReverseIterableBlock<BlockType>::ReverseIterator; 102 103 private: 104 constexpr explicit DetailedBlockImpl(size_t outer_size) : info_{} { 105 next_ = outer_size / Basic::kAlignment; 106 info_.last = 1; 107 info_.alignment = Basic::kAlignment; 108 } 109 110 // `Basic` required methods. 111 friend Basic; 112 static constexpr size_t DefaultAlignment() { 113 return std::max(alignof(OffsetType), 114 Parameters::kLayoutWhenFree.alignment()); 115 } 116 static constexpr size_t BlockOverhead() { return sizeof(BlockType); } 117 static constexpr size_t MinInnerSize() { return 1; } 118 static constexpr size_t ReservedWhenFree() { 119 return Parameters::kLayoutWhenFree.size(); 120 } 121 size_t OuterSizeUnchecked() const; 122 123 // `Basic` overrides. 124 bool DoCheckInvariants(bool crash_on_failure) const; 125 126 // `Contiguous` required methods. 127 using Contiguous = ContiguousBlock<BlockType>; 128 friend Contiguous; 129 130 static constexpr size_t MaxAddressableSize() { 131 auto kOffsetMax = 132 static_cast<size_t>(std::numeric_limits<OffsetType>::max()); 133 auto kSizeMax = static_cast<size_t>(std::numeric_limits<size_t>::max()); 134 return std::min(kSizeMax / Basic::kAlignment, kOffsetMax) * 135 Basic::kAlignment; 136 } 137 138 constexpr bool IsLastUnchecked() const { return info_.last != 0; } 139 static inline BlockType* AsBlock(ByteSpan bytes); 140 void SetNext(size_t outer_size, BlockType* next); 141 size_t PrevOuterSizeUnchecked() const; 142 143 // `Contiguous` overrides. 144 inline BlockType* DoSplitFirst(size_t new_inner_size); 145 inline BlockType* DoSplitLast(size_t new_inner_size); 146 inline void DoMergeNext(); 147 148 // `Allocatable` required methods. 149 using Allocatable = AllocatableBlock<BlockType>; 150 friend Allocatable; 151 constexpr bool IsFreeUnchecked() const { return info_.used == 0; } 152 void SetFree(bool is_free); 153 154 // `Alignable` overrides. 155 using Alignable = AlignableBlock<BlockType>; 156 friend Alignable; 157 inline StatusWithSize DoCanAlloc(Layout layout) const; 158 static inline BlockResult<BlockType> DoAllocFirst(BlockType*&& block, 159 Layout layout); 160 static inline BlockResult<BlockType> DoAllocLast(BlockType*&& block, 161 Layout layout); 162 inline BlockResult<BlockType> DoResize(size_t new_inner_size, 163 bool shifted = false); 164 static inline BlockResult<BlockType> DoFree(BlockType*&& block); 165 166 // `WithLayout` required methods. 167 using WithLayout = BlockWithLayout<BlockType>; 168 friend WithLayout; 169 constexpr size_t RequestedSize() const { 170 return Basic::InnerSize() - padding_; 171 } 172 constexpr size_t RequestedAlignment() const { return info_.alignment; } 173 void SetRequestedSize(size_t size); 174 void SetRequestedAlignment(size_t alignment); 175 176 // `Poisonable` required methods. 177 using Poisonable = PoisonableBlock<BlockType>; 178 friend Poisonable; 179 constexpr bool IsPoisonedUnchecked() const { return info_.poisoned != 0; } 180 constexpr void SetPoisoned(bool is_poisoned) { info_.poisoned = is_poisoned; } 181 182 /// Offset (in increments of the minimum alignment) from this block to the 183 /// previous block. 0 if this is the first block. 184 OffsetType prev_ = 0; 185 186 /// Offset (in increments of the minimum alignment) from this block to the 187 /// next block. Valid even if this is the last block, since it equals the 188 /// size of the block. 189 OffsetType next_ = 0; 190 191 /// Information about the current state of the block: 192 /// * If the `used` flag is set, the block's usable memory has been allocated 193 /// and is being used. 194 /// * If the `poisoned` flag is set and the `used` flag is clear, the block's 195 /// usable memory contains a poison pattern that will be checked when the 196 /// block is allocated. 197 /// * If the `last` flag is set, the block does not have a next block. 198 /// * If the `used` flag is set, the alignment represents the requested value 199 /// when the memory was allocated, which may be less strict than the actual 200 /// alignment. 201 struct { 202 uint16_t used : 1; 203 uint16_t poisoned : 1; 204 uint16_t last : 1; 205 uint16_t alignment : 13; 206 } info_; 207 208 /// Number of bytes allocated beyond what was requested. This will be at most 209 /// the minimum alignment, i.e. `alignof(OffsetType).` 210 uint16_t padding_ = 0; 211 }; 212 213 // Convenience alias that constructs the block traits automatically. 214 template <typename OffsetType = uintptr_t, typename WhenFree = void> 215 using DetailedBlock = 216 DetailedBlockImpl<DetailedBlockParameters<OffsetType, WhenFree>>; 217 218 // Template method implementations. 219 220 // `Basic` methods. 221 222 template <typename Parameters> 223 size_t DetailedBlockImpl<Parameters>::OuterSizeUnchecked() const { 224 size_t outer_size; 225 PW_ASSERT(!PW_MUL_OVERFLOW(next_, Basic::kAlignment, &outer_size)); 226 return outer_size; 227 } 228 229 template <typename Parameters> 230 bool DetailedBlockImpl<Parameters>::DoCheckInvariants( 231 bool crash_on_failure) const { 232 return Basic::DoCheckInvariants(crash_on_failure) && 233 Contiguous::DoCheckInvariants(crash_on_failure) && 234 Poisonable::DoCheckInvariants(crash_on_failure); 235 } 236 237 // `Contiguous` methods. 238 239 template <typename Parameters> 240 DetailedBlockImpl<Parameters>* DetailedBlockImpl<Parameters>::AsBlock( 241 ByteSpan bytes) { 242 return ::new (bytes.data()) DetailedBlockImpl(bytes.size()); 243 } 244 245 template <typename Parameters> 246 void DetailedBlockImpl<Parameters>::SetNext(size_t outer_size, 247 BlockType* next) { 248 next_ = outer_size / Basic::kAlignment; 249 if (next == nullptr) { 250 info_.last = 1; 251 return; 252 } 253 info_.last = 0; 254 next->prev_ = next_; 255 } 256 257 template <typename Parameters> 258 size_t DetailedBlockImpl<Parameters>::PrevOuterSizeUnchecked() const { 259 size_t outer_size; 260 PW_ASSERT(!PW_MUL_OVERFLOW(prev_, Basic::kAlignment, &outer_size)); 261 return outer_size; 262 } 263 264 template <typename Parameters> 265 DetailedBlockImpl<Parameters>* DetailedBlockImpl<Parameters>::DoSplitFirst( 266 size_t new_inner_size) { 267 return Poisonable::DoSplitFirst(new_inner_size); 268 } 269 270 template <typename Parameters> 271 DetailedBlockImpl<Parameters>* DetailedBlockImpl<Parameters>::DoSplitLast( 272 size_t new_inner_size) { 273 return Poisonable::DoSplitLast(new_inner_size); 274 } 275 276 template <typename Parameters> 277 void DetailedBlockImpl<Parameters>::DoMergeNext() { 278 Poisonable::DoMergeNext(); 279 } 280 281 // `Alignable` methods. 282 283 template <typename Parameters> 284 void DetailedBlockImpl<Parameters>::SetFree(bool is_free) { 285 info_.used = !is_free; 286 Poisonable::SetFree(is_free); 287 } 288 289 // `Alignable` methods. 290 291 template <typename Parameters> 292 StatusWithSize DetailedBlockImpl<Parameters>::DoCanAlloc(Layout layout) const { 293 return Alignable::DoCanAlloc(layout); 294 } 295 296 template <typename Parameters> 297 BlockResult<DetailedBlockImpl<Parameters>> 298 DetailedBlockImpl<Parameters>::DoAllocFirst(DetailedBlockImpl*&& block, 299 Layout layout) { 300 return WithLayout::DoAllocFirst(std::move(block), layout); 301 } 302 303 template <typename Parameters> 304 BlockResult<DetailedBlockImpl<Parameters>> 305 DetailedBlockImpl<Parameters>::DoAllocLast(DetailedBlockImpl*&& block, 306 Layout layout) { 307 return WithLayout::DoAllocLast(std::move(block), layout); 308 } 309 310 template <typename Parameters> 311 BlockResult<DetailedBlockImpl<Parameters>> 312 DetailedBlockImpl<Parameters>::DoResize(size_t new_inner_size, bool shifted) { 313 return WithLayout::DoResize(new_inner_size, shifted); 314 } 315 316 template <typename Parameters> 317 BlockResult<DetailedBlockImpl<Parameters>> 318 DetailedBlockImpl<Parameters>::DoFree(DetailedBlockImpl*&& block) { 319 return WithLayout::DoFree(std::move(block)); 320 } 321 322 // `WithLayout` methods. 323 324 template <typename Parameters> 325 void DetailedBlockImpl<Parameters>::SetRequestedSize(size_t size) { 326 size_t inner_size = Basic::InnerSize(); 327 size_t padding; 328 PW_ASSERT(!PW_SUB_OVERFLOW(inner_size, size, &padding)); 329 PW_ASSERT(padding <= std::numeric_limits<uint16_t>::max()); 330 padding_ = static_cast<uint16_t>(padding); 331 } 332 333 template <typename Parameters> 334 void DetailedBlockImpl<Parameters>::SetRequestedAlignment(size_t alignment) { 335 PW_ASSERT((alignment & (alignment - 1)) == 0); 336 PW_ASSERT(alignment < 0x2000); 337 info_.alignment = alignment; 338 } 339 340 } // namespace pw::allocator 341