482 lines · c
1//===-- Implementation header for a block of memory -------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_BLOCK_H10#define LLVM_LIBC_SRC___SUPPORT_BLOCK_H11 12#include "hdr/stdint_proxy.h"13#include "src/__support/CPP/algorithm.h"14#include "src/__support/CPP/cstddef.h"15#include "src/__support/CPP/limits.h"16#include "src/__support/CPP/new.h"17#include "src/__support/CPP/optional.h"18#include "src/__support/CPP/span.h"19#include "src/__support/CPP/type_traits.h"20#include "src/__support/libc_assert.h"21#include "src/__support/macros/config.h"22#include "src/__support/math_extras.h"23 24namespace LIBC_NAMESPACE_DECL {25 26/// Returns the value rounded down to the nearest multiple of alignment.27LIBC_INLINE constexpr size_t align_down(size_t value, size_t alignment) {28 // Note this shouldn't overflow since the result will always be <= value.29 return (value / alignment) * alignment;30}31 32/// Returns the value rounded up to the nearest multiple of alignment. May wrap33/// around.34LIBC_INLINE constexpr size_t align_up(size_t value, size_t alignment) {35 return align_down(value + alignment - 1, alignment);36}37 38using ByteSpan = cpp::span<LIBC_NAMESPACE::cpp::byte>;39using cpp::optional;40 41/// Memory region with links to adjacent blocks.42///43/// The blocks store their offsets to the previous and next blocks. The latter44/// is also the block's size.45///46/// All blocks have their usable space aligned to some multiple of max_align_t.47/// This also implies that block outer sizes are aligned to max_align_t.48///49/// As an example, the diagram below represents two contiguous `Block`s. The50/// indices indicate byte offsets:51///52/// @code{.unparsed}53/// Block 1:54/// +---------------------+--------------+55/// | Header | Usable space |56/// +----------+----------+--------------+57/// | prev | next | |58/// | 0......3 | 4......7 | 8........227 |59/// | 00000000 | 00000230 | <app data> |60/// +----------+----------+--------------+61/// Block 2:62/// +---------------------+--------------+63/// | Header | Usable space |64/// +----------+----------+--------------+65/// | prev | next | |66/// | 0......3 | 4......7 | 8........827 |67/// | 00000230 | 00000830 | f7f7....f7f7 |68/// +----------+----------+--------------+69/// @endcode70///71/// As a space optimization, when a block is allocated, it consumes the prev72/// field of the following block:73///74/// Block 1 (used):75/// +---------------------+--------------+76/// | Header | Usable space |77/// +----------+----------+--------------+78/// | prev | next | |79/// | 0......3 | 4......7 | 8........230 |80/// | 00000000 | 00000230 | <app data> |81/// +----------+----------+--------------+82/// Block 2:83/// +---------------------+--------------+84/// | B1 | Header | Usable space |85/// +----------+----------+--------------+86/// | | next | |87/// | 0......3 | 4......7 | 8........827 |88/// | xxxxxxxx | 00000830 | f7f7....f7f7 |89/// +----------+----------+--------------+90///91/// The next offset of a block matches the previous offset of its next block.92/// The first block in a list is denoted by having a previous offset of `0`.93class Block {94 // Masks for the contents of the next_ field.95 static constexpr size_t PREV_FREE_MASK = 1 << 0;96 static constexpr size_t LAST_MASK = 1 << 1;97 static constexpr size_t SIZE_MASK = ~(PREV_FREE_MASK | LAST_MASK);98 99public:100 // No copy or move.101 Block(const Block &other) = delete;102 Block &operator=(const Block &other) = delete;103 104 /// Initializes a given memory region into a first block and a sentinel last105 /// block. Returns the first block, which has its usable space aligned to106 /// max_align_t.107 static optional<Block *> init(ByteSpan region);108 109 /// @returns A pointer to a `Block`, given a pointer to the start of the110 /// usable space inside the block.111 ///112 /// This is the inverse of `usable_space()`.113 ///114 /// @warning This method does not do any checking; passing a random115 /// pointer will return a non-null pointer.116 LIBC_INLINE static Block *from_usable_space(void *usable_space) {117 auto *bytes = reinterpret_cast<cpp::byte *>(usable_space);118 return reinterpret_cast<Block *>(bytes - sizeof(Block));119 }120 LIBC_INLINE static const Block *from_usable_space(const void *usable_space) {121 const auto *bytes = reinterpret_cast<const cpp::byte *>(usable_space);122 return reinterpret_cast<const Block *>(bytes - sizeof(Block));123 }124 125 /// @returns The total size of the block in bytes, including the header.126 LIBC_INLINE size_t outer_size() const { return next_ & SIZE_MASK; }127 128 LIBC_INLINE static size_t outer_size(size_t inner_size) {129 // The usable region includes the prev_ field of the next block.130 return inner_size - sizeof(prev_) + sizeof(Block);131 }132 133 /// @returns The number of usable bytes inside the block were it to be134 /// allocated.135 LIBC_INLINE size_t inner_size() const {136 if (!next())137 return 0;138 return inner_size(outer_size());139 }140 141 /// @returns The number of usable bytes inside a block with the given outer142 /// size were it to be allocated.143 LIBC_INLINE static size_t inner_size(size_t outer_size) {144 // The usable region includes the prev_ field of the next block.145 return inner_size_free(outer_size) + sizeof(prev_);146 }147 148 /// @returns The number of usable bytes inside the block if it remains free.149 LIBC_INLINE size_t inner_size_free() const {150 if (!next())151 return 0;152 return inner_size_free(outer_size());153 }154 155 /// @returns The number of usable bytes inside a block with the given outer156 /// size if it remains free.157 LIBC_INLINE static size_t inner_size_free(size_t outer_size) {158 return outer_size - sizeof(Block);159 }160 161 /// @returns A pointer to the usable space inside this block.162 ///163 /// Aligned to some multiple of max_align_t.164 LIBC_INLINE cpp::byte *usable_space() {165 auto *s = reinterpret_cast<cpp::byte *>(this) + sizeof(Block);166 LIBC_ASSERT(reinterpret_cast<uintptr_t>(s) % alignof(max_align_t) == 0 &&167 "usable space must be aligned to a multiple of max_align_t");168 return s;169 }170 LIBC_INLINE const cpp::byte *usable_space() const {171 const auto *s = reinterpret_cast<const cpp::byte *>(this) + sizeof(Block);172 LIBC_ASSERT(reinterpret_cast<uintptr_t>(s) % alignof(max_align_t) == 0 &&173 "usable space must be aligned to a multiple of max_align_t");174 return s;175 }176 177 // @returns The region of memory the block manages, including the header.178 LIBC_INLINE ByteSpan region() {179 return {reinterpret_cast<cpp::byte *>(this), outer_size()};180 }181 182 /// Attempts to split this block.183 ///184 /// If successful, the block will have an inner size of at least185 /// `new_inner_size`. The remaining space will be returned as a new block,186 /// with usable space aligned to `usable_space_alignment`. Note that the prev_187 /// field of the next block counts as part of the inner size of the block.188 /// `usable_space_alignment` must be a multiple of max_align_t.189 optional<Block *> split(size_t new_inner_size,190 size_t usable_space_alignment = alignof(max_align_t));191 192 /// Merges this block with the one that comes after it.193 bool merge_next();194 195 /// @returns The block immediately after this one, or a null pointer if this196 /// is the last block.197 LIBC_INLINE Block *next() const {198 if (next_ & LAST_MASK)199 return nullptr;200 return reinterpret_cast<Block *>(reinterpret_cast<uintptr_t>(this) +201 outer_size());202 }203 204 /// @returns The free block immediately before this one, otherwise nullptr.205 LIBC_INLINE Block *prev_free() const {206 if (!(next_ & PREV_FREE_MASK))207 return nullptr;208 return reinterpret_cast<Block *>(reinterpret_cast<uintptr_t>(this) - prev_);209 }210 211 /// @returns Whether the block is unavailable for allocation.212 LIBC_INLINE bool used() const { return !next() || !next()->prev_free(); }213 214 /// Marks this block as in use.215 LIBC_INLINE void mark_used() {216 LIBC_ASSERT(next() && "last block is always considered used");217 next()->next_ &= ~PREV_FREE_MASK;218 }219 220 /// Marks this block as free.221 LIBC_INLINE void mark_free() {222 LIBC_ASSERT(next() && "last block is always considered used");223 next()->next_ |= PREV_FREE_MASK;224 // The next block's prev_ field becomes alive, as it is no longer part of225 // this block's used space.226 *new (&next()->prev_) size_t = outer_size();227 }228 229 LIBC_INLINE Block(size_t outer_size, bool is_last) : next_(outer_size) {230 // Last blocks are not usable, so they need not have sizes aligned to231 // max_align_t. Their lower bits must still be free, so they must be aligned232 // to Block.233 LIBC_ASSERT(234 outer_size % (is_last ? alignof(Block) : alignof(max_align_t)) == 0 &&235 "block sizes must be aligned");236 LIBC_ASSERT(is_usable_space_aligned(alignof(max_align_t)) &&237 "usable space must be aligned to a multiple of max_align_t");238 if (is_last)239 next_ |= LAST_MASK;240 }241 242 LIBC_INLINE bool is_usable_space_aligned(size_t alignment) const {243 return reinterpret_cast<uintptr_t>(usable_space()) % alignment == 0;244 }245 246 // Returns the minimum inner size necessary for a block of that size to247 // always be able to allocate at the given size and alignment.248 //249 // Returns 0 if there is no such size.250 LIBC_INLINE static size_t min_size_for_allocation(size_t alignment,251 size_t size) {252 LIBC_ASSERT(alignment >= alignof(max_align_t) &&253 alignment % alignof(max_align_t) == 0 &&254 "alignment must be multiple of max_align_t");255 256 if (alignment == alignof(max_align_t))257 return size;258 259 // We must create a new block inside this one (splitting). This requires a260 // block header in addition to the requested size.261 if (add_overflow(size, sizeof(Block), size))262 return 0;263 264 // Beyond that, padding space may need to remain in this block to ensure265 // that the usable space of the next block is aligned.266 //267 // Consider a position P of some lesser alignment, L, with maximal distance268 // to the next position of some greater alignment, G, where G is a multiple269 // of L. P must be one L unit past a G-aligned point. If it were one L-unit270 // earlier, its distance would be zero. If it were one L-unit later, its271 // distance would not be maximal. If it were not some integral number of L272 // units away, it would not be L-aligned.273 //274 // So the maximum distance would be G - L. As a special case, if L is 1275 // (unaligned), the max distance is G - 1.276 //277 // This block's usable space is aligned to max_align_t >= Block. With zero278 // padding, the next block's usable space is sizeof(Block) past it, which is279 // a point aligned to Block. Thus the max padding needed is alignment -280 // alignof(Block).281 if (add_overflow(size, alignment - alignof(Block), size))282 return 0;283 return size;284 }285 286 // This is the return type for `allocate` which can split one block into up to287 // three blocks.288 struct BlockInfo {289 // This is the newly aligned block. It will have the alignment requested by290 // a call to `allocate` and at most `size`.291 Block *block;292 293 // If the usable_space in the new block was not aligned according to the294 // `alignment` parameter, we will need to split into this block and the295 // `block` to ensure `block` is properly aligned. In this case, `prev` will296 // be a pointer to this new "padding" block. `prev` will be nullptr if no297 // new block was created or we were able to merge the block before the298 // original block with the "padding" block.299 Block *prev;300 301 // This is the remainder of the next block after splitting the `block`302 // according to `size`. This can happen if there's enough space after the303 // `block`.304 Block *next;305 };306 307 // Divide a block into up to 3 blocks according to `BlockInfo`. Behavior is308 // undefined if allocation is not possible for the given size and alignment.309 static BlockInfo allocate(Block *block, size_t alignment, size_t size);310 311 // These two functions may wrap around.312 LIBC_INLINE static uintptr_t next_possible_block_start(313 uintptr_t ptr, size_t usable_space_alignment = alignof(max_align_t)) {314 return align_up(ptr + sizeof(Block), usable_space_alignment) -315 sizeof(Block);316 }317 LIBC_INLINE static uintptr_t prev_possible_block_start(318 uintptr_t ptr, size_t usable_space_alignment = alignof(max_align_t)) {319 return align_down(ptr, usable_space_alignment) - sizeof(Block);320 }321 322private:323 /// Construct a block to represent a span of bytes. Overwrites only enough324 /// memory for the block header; the rest of the span is left alone.325 LIBC_INLINE static Block *as_block(ByteSpan bytes) {326 LIBC_ASSERT(reinterpret_cast<uintptr_t>(bytes.data()) % alignof(Block) ==327 0 &&328 "block start must be suitably aligned");329 return ::new (bytes.data()) Block(bytes.size(), /*is_last=*/false);330 }331 332 LIBC_INLINE static void make_last_block(cpp::byte *start) {333 LIBC_ASSERT(reinterpret_cast<uintptr_t>(start) % alignof(Block) == 0 &&334 "block start must be suitably aligned");335 ::new (start) Block(sizeof(Block), /*is_last=*/true);336 }337 338 /// Offset from this block to the previous block. 0 if this is the first339 /// block. This field is only alive when the previous block is free;340 /// otherwise, its memory is reused as part of the previous block's usable341 /// space.342 size_t prev_ = 0;343 344 /// Offset from this block to the next block. Valid even if this is the last345 /// block, since it equals the size of the block.346 size_t next_ = 0;347 348 /// Information about the current state of the block is stored in the two low349 /// order bits of the next_ value. These are guaranteed free by a minimum350 /// alignment (and thus, alignment of the size) of 4. The lowest bit is the351 /// `prev_free` flag, and the other bit is the `last` flag.352 ///353 /// * If the `prev_free` flag is set, the block isn't the first and the354 /// previous block is free.355 /// * If the `last` flag is set, the block is the sentinel last block. It is356 /// summarily considered used and has no next block.357 358public:359 /// Only for testing.360 static constexpr size_t PREV_FIELD_SIZE = sizeof(prev_);361};362 363static_assert(alignof(Block) >= 4,364 "at least 2 bits must be available in block sizes for flags");365 366LIBC_INLINE367optional<Block *> Block::init(ByteSpan region) {368 if (!region.data())369 return {};370 371 uintptr_t start = reinterpret_cast<uintptr_t>(region.data());372 uintptr_t end = start + region.size();373 if (end < start)374 return {};375 376 uintptr_t block_start = next_possible_block_start(start);377 if (block_start < start)378 return {};379 380 uintptr_t last_start = prev_possible_block_start(end);381 if (last_start >= end)382 return {};383 384 if (block_start + sizeof(Block) > last_start)385 return {};386 387 auto *last_start_ptr = reinterpret_cast<cpp::byte *>(last_start);388 Block *block =389 as_block({reinterpret_cast<cpp::byte *>(block_start), last_start_ptr});390 make_last_block(last_start_ptr);391 block->mark_free();392 return block;393}394 395LIBC_INLINE396Block::BlockInfo Block::allocate(Block *block, size_t alignment, size_t size) {397 LIBC_ASSERT(alignment % alignof(max_align_t) == 0 &&398 "alignment must be a multiple of max_align_t");399 400 BlockInfo info{block, /*prev=*/nullptr, /*next=*/nullptr};401 402 if (!info.block->is_usable_space_aligned(alignment)) {403 Block *original = info.block;404 // The padding block has no minimum size requirement.405 optional<Block *> maybe_aligned_block = original->split(0, alignment);406 LIBC_ASSERT(maybe_aligned_block.has_value() &&407 "it should always be possible to split for alignment");408 409 if (Block *prev = original->prev_free()) {410 // If there is a free block before this, we can merge the current one with411 // the newly created one.412 prev->merge_next();413 } else {414 info.prev = original;415 }416 417 Block *aligned_block = *maybe_aligned_block;418 LIBC_ASSERT(aligned_block->is_usable_space_aligned(alignment) &&419 "The aligned block isn't aligned somehow.");420 info.block = aligned_block;421 }422 423 // Now get a block for the requested size.424 if (optional<Block *> next = info.block->split(size))425 info.next = *next;426 427 return info;428}429 430LIBC_INLINE431optional<Block *> Block::split(size_t new_inner_size,432 size_t usable_space_alignment) {433 LIBC_ASSERT(usable_space_alignment % alignof(max_align_t) == 0 &&434 "alignment must be a multiple of max_align_t");435 if (used())436 return {};437 438 // Compute the minimum outer size that produces a block of at least439 // `new_inner_size`.440 size_t min_outer_size = outer_size(cpp::max(new_inner_size, sizeof(prev_)));441 442 uintptr_t start = reinterpret_cast<uintptr_t>(this);443 uintptr_t next_block_start =444 next_possible_block_start(start + min_outer_size, usable_space_alignment);445 if (next_block_start < start)446 return {};447 size_t new_outer_size = next_block_start - start;448 LIBC_ASSERT(new_outer_size % alignof(max_align_t) == 0 &&449 "new size must be aligned to max_align_t");450 451 if (outer_size() < new_outer_size ||452 outer_size() - new_outer_size < sizeof(Block))453 return {};454 455 ByteSpan new_region = region().subspan(new_outer_size);456 next_ &= ~SIZE_MASK;457 next_ |= new_outer_size;458 459 Block *new_block = as_block(new_region);460 mark_free(); // Free status for this block is now stored in new_block.461 new_block->next()->prev_ = new_region.size();462 463 LIBC_ASSERT(new_block->is_usable_space_aligned(usable_space_alignment) &&464 "usable space must have requested alignment");465 return new_block;466}467 468LIBC_INLINE469bool Block::merge_next() {470 if (used() || next()->used())471 return false;472 size_t new_size = outer_size() + next()->outer_size();473 next_ &= ~SIZE_MASK;474 next_ |= new_size;475 next()->prev_ = new_size;476 return true;477}478 479} // namespace LIBC_NAMESPACE_DECL480 481#endif // LLVM_LIBC_SRC___SUPPORT_BLOCK_H482