pw_allocator/block.cc

// Copyright 2020 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.

#include "pw_allocator/block.h"

#include <cstring>

#include "pw_assert/check.h"
#include "pw_span/span.h"

namespace pw::allocator {

Status Block::Init(const span<std::byte> region, Block** block) {
  // Ensure the region we're given is aligned and sized accordingly
  if (reinterpret_cast<uintptr_t>(region.data()) % alignof(Block) != 0) {
    return Status::InvalidArgument();
  }

  if (region.size() < sizeof(Block)) {
    return Status::InvalidArgument();
  }

  union {
    Block* block;
    std::byte* bytes;
  } aliased;
  aliased.bytes = region.data();

  // Make "next" point just past the end of this block; forming a linked list
  // with the following storage. Since the space between this block and the
  // next are implicitly part of the raw data, size can be computed by
  // subtracting the pointers.
  aliased.block->next_ =
      reinterpret_cast<Block*>(region.data() + region.size_bytes());
  aliased.block->MarkLast();

  aliased.block->prev_ = nullptr;
  *block = aliased.block;
#if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
  (*block)->PoisonBlock();
#endif  // PW_ALLOCATOR_POISON_ENABLE
  return OkStatus();
}

Status Block::Split(size_t head_block_inner_size, Block** new_block) {
  if (new_block == nullptr) {
    return Status::InvalidArgument();
  }

  // Don't split used blocks.
  // TODO: Relax this restriction? Flag to enable/disable this check?
  if (Used()) {
    return Status::FailedPrecondition();
  }

  // First round the head_block_inner_size up to a alignof(Block) bounary.
  // This ensures that the next block header is aligned accordingly.
  // Alignment must be a power of two, hence align()-1 will return the
  // remainder.
  auto align_bit_mask = alignof(Block) - 1;
  size_t aligned_head_block_inner_size = head_block_inner_size;
  if ((head_block_inner_size & align_bit_mask) != 0) {
    aligned_head_block_inner_size =
        (head_block_inner_size & ~align_bit_mask) + alignof(Block);
  }

  // (1) Are we trying to allocate a head block larger than the current head
  // block? This may happen because of the alignment above.
  if (aligned_head_block_inner_size > InnerSize()) {
    return Status::OutOfRange();
  }

  // (2) Does the resulting block have enough space to store the header?
  // TODO: What to do if the returned section is empty (i.e. remaining
  // size == sizeof(Block))?
  if (InnerSize() - aligned_head_block_inner_size <
      sizeof(Block) + 2 * PW_ALLOCATOR_POISON_OFFSET) {
    return Status::ResourceExhausted();
  }

  // Create the new block inside the current one.
  Block* new_next = reinterpret_cast<Block*>(
      // From the current position...
      reinterpret_cast<intptr_t>(this) +
      // skip past the current header...
      sizeof(*this) +
      // add the poison bytes before usable space ...
      PW_ALLOCATOR_POISON_OFFSET +
      // into the usable bytes by the new inner size...
      aligned_head_block_inner_size +
      // add the poison bytes after the usable space ...
      PW_ALLOCATOR_POISON_OFFSET);

  // If we're inserting in the middle, we need to update the current next
  // block to point to what we're inserting
  if (!Last()) {
    Next()->prev_ = new_next;
  }

  // Copy next verbatim so the next block also gets the "last"-ness
  new_next->next_ = next_;
  new_next->prev_ = this;

  // Update the current block to point to the new head.
  next_ = new_next;

  *new_block = next_;

#if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
  PoisonBlock();
  (*new_block)->PoisonBlock();
#endif  // PW_ALLOCATOR_POISON_ENABLE

  return OkStatus();
}

Status Block::MergeNext() {
  // Anything to merge with?
  if (Last()) {
    return Status::OutOfRange();
  }

  // Is this or the next block in use?
  if (Used() || Next()->Used()) {
    return Status::FailedPrecondition();
  }

  // Simply enough, this block's next pointer becomes the next block's
  // next pointer. We then need to re-wire the "next next" block's prev
  // pointer to point back to us though.
  next_ = Next()->next_;

  // Copying the pointer also copies the "last" status, so this is safe.
  if (!Last()) {
    Next()->prev_ = this;
  }

  return OkStatus();
}

Status Block::MergePrev() {
  // We can't merge if we have no previous. After that though, merging with
  // the previous block is just MergeNext from the previous block.
  if (prev_ == nullptr) {
    return Status::OutOfRange();
  }

  // WARNING: This class instance will still exist, but technically be invalid
  // after this has been invoked. Be careful when doing anything with `this`
  // After doing the below.
  return prev_->MergeNext();
}

// TODO(b/234875269): Add stack tracing to locate which call to the heap
// operation caused the corruption.
// TODO: Add detailed information to log report and leave succinct messages
// in the crash message.
void Block::CrashIfInvalid() {
  switch (CheckStatus()) {
    case VALID:
      break;
    case MISALIGNED:
      PW_DCHECK(false,
                "The block at address %p is not aligned.",
                static_cast<void*>(this));
      break;
    case NEXT_MISMATCHED:
      PW_DCHECK(false,
                "The 'prev' field in the next block (%p) does not match the "
                "address of the current block (%p).",
                static_cast<void*>(Next()->Prev()),
                static_cast<void*>(this));
      break;
    case PREV_MISMATCHED:
      PW_DCHECK(false,
                "The 'next' field in the previous block (%p) does not match "
                "the address of the current block (%p).",
                static_cast<void*>(Prev()->Next()),
                static_cast<void*>(this));
      break;
    case POISON_CORRUPTED:
      PW_DCHECK(false,
                "The poisoned pattern in the block at %p is corrupted.",
                static_cast<void*>(this));
      break;
  }
}

// This function will return a Block::BlockStatus that is either VALID or
// indicates the reason why the Block is invalid. If the Block is invalid at
// multiple points, this function will only return one of the reasons.
Block::BlockStatus Block::CheckStatus() const {
  // Make sure the Block is aligned.
  if (reinterpret_cast<uintptr_t>(this) % alignof(Block) != 0) {
    return BlockStatus::MISALIGNED;
  }

  // Test if the prev/next pointer for this Block matches.
  if (!Last() && (this >= Next() || this != Next()->Prev())) {
    return BlockStatus::NEXT_MISMATCHED;
  }

  if (Prev() && (this <= Prev() || this != Prev()->Next())) {
    return BlockStatus::PREV_MISMATCHED;
  }

#if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
  if (!this->CheckPoisonBytes()) {
    return BlockStatus::POISON_CORRUPTED;
  }
#endif  // PW_ALLOCATOR_POISON_ENABLE
  return BlockStatus::VALID;
}

// Paint sizeof(void*) bytes before and after the usable space in Block as the
// randomized function pattern.
void Block::PoisonBlock() {
#if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
  std::byte* front_region = reinterpret_cast<std::byte*>(this) + sizeof(*this);
  memcpy(front_region, POISON_PATTERN, PW_ALLOCATOR_POISON_OFFSET);

  std::byte* end_region =
      reinterpret_cast<std::byte*>(Next()) - PW_ALLOCATOR_POISON_OFFSET;
  memcpy(end_region, POISON_PATTERN, PW_ALLOCATOR_POISON_OFFSET);
#endif  // PW_ALLOCATOR_POISON_ENABLE
}

bool Block::CheckPoisonBytes() const {
#if defined(PW_ALLOCATOR_POISON_ENABLE) && PW_ALLOCATOR_POISON_ENABLE
  std::byte* front_region = reinterpret_cast<std::byte*>(
      reinterpret_cast<intptr_t>(this) + sizeof(*this));
  if (std::memcmp(front_region, POISON_PATTERN, PW_ALLOCATOR_POISON_OFFSET)) {
    return false;
  }
  std::byte* end_region = reinterpret_cast<std::byte*>(
      reinterpret_cast<intptr_t>(this->Next()) - PW_ALLOCATOR_POISON_OFFSET);
  if (std::memcmp(end_region, POISON_PATTERN, PW_ALLOCATOR_POISON_OFFSET)) {
    return false;
  }
#endif  // PW_ALLOCATOR_POISON_ENABLE
  return true;
}

}  // namespace pw::allocator