contiguous.h

// Copyright 2024 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.
#pragma once
 
#include "lib/stdcompat/bit.h"
#include "pw_allocator/block/basic.h"
#include "pw_allocator/hardening.h"
#include "pw_bytes/span.h"
 
namespace pw::allocator {
namespace internal {
 
// Trivial base class for trait support.
struct ContiguousBase {};
 
}  // namespace internal
 
template <typename Derived>
class ContiguousBlock : public internal::ContiguousBase {
 protected:
  constexpr explicit ContiguousBlock() {
    // Assert within a function, since `Derived` is not complete when this type
    // is defined.
    static_assert(
        is_block_v<Derived>,
        "Types derived from ContiguousBlock must also derive from BasicBlock");
  }
 
 public:
  constexpr Derived* Prev() const;
 
  constexpr Derived* Next() const;
 
 protected:
  constexpr Derived* DoSplitFirst(size_t new_inner_size);
 
  constexpr Derived* DoSplitLast(size_t new_inner_size);
 
  constexpr void DoMergeNext();
 
  constexpr bool DoCheckInvariants(bool strict) const;
 
 private:
  constexpr Derived* derived() { return static_cast<Derived*>(this); }
  constexpr const Derived* derived() const {
    return static_cast<const Derived*>(this);
  }
 
  constexpr Derived* PrevUnchecked() const;
 
  constexpr Derived* NextUnchecked() const;
 
  static constexpr Derived* Split(Derived*& block, size_t new_inner_size);
 
  static constexpr ByteSpan AsBytes(Derived*&& block);
 
  // PoisonableBlock calls DoSplitFirst, DoSplitLast, and DoMergeNext
  template <typename>
  friend class PoisonableBlock;
};
 
template <typename BlockType>
struct is_contiguous : std::is_base_of<internal::ContiguousBase, BlockType> {};
 
template <typename BlockType>
constexpr bool is_contiguous_v = is_contiguous<BlockType>::value;
 
namespace internal {
 
 
void CheckNextMisaligned(const void* block,
                         const void* next,
                         bool next_is_aligned);
 
void CheckNextPrevMismatched(const void* block,
                             const void* next,
                             const void* next_prev,
                             bool next_prev_matches);
 
void CheckPrevMisaligned(const void* block,
                         const void* prev,
                         bool prev_is_aligned);
 
void CheckPrevNextMismatched(const void* block,
                             const void* prev,
                             const void* prev_next,
                             bool prev_next_matches);
 
}  // namespace internal
 
// Template method implementations.
 
template <typename Derived>
constexpr Derived* ContiguousBlock<Derived>::Prev() const {
  if constexpr (Hardening::kIncludesDebugChecks) {
    derived()->CheckInvariants();
  }
  return PrevUnchecked();
}
 
template <typename Derived>
constexpr Derived* ContiguousBlock<Derived>::PrevUnchecked() const {
  size_t prev_outer_size = derived()->PrevOuterSizeUnchecked();
  if (prev_outer_size == 0) {
    return nullptr;
  }
  auto addr = cpp20::bit_cast<uintptr_t>(this);
  Hardening::Decrement(addr, prev_outer_size);
  return std::launder(reinterpret_cast<Derived*>(addr));
}
 
template <typename Derived>
constexpr Derived* ContiguousBlock<Derived>::Next() const {
  if constexpr (Hardening::kIncludesDebugChecks) {
    derived()->CheckInvariants();
  }
  return NextUnchecked();
}
 
template <typename Derived>
constexpr Derived* ContiguousBlock<Derived>::NextUnchecked() const {
  if (derived()->IsLastUnchecked()) {
    return nullptr;
  }
  size_t outer_size = derived()->OuterSizeUnchecked();
  auto addr = cpp20::bit_cast<uintptr_t>(this);
  Hardening::Increment(addr, outer_size);
  return std::launder(reinterpret_cast<Derived*>(addr));
}
 
template <typename Derived>
constexpr Derived* ContiguousBlock<Derived>::DoSplitFirst(
    size_t new_inner_size) {
  Derived* next = derived()->Next();
  size_t new_outer_size = Derived::kBlockOverhead + new_inner_size;
  ByteSpan bytes(derived()->UsableSpace(), derived()->InnerSize());
  bytes = bytes.subspan(new_inner_size);
  auto* trailing = Derived::AsBlock(bytes);
  derived()->SetNext(new_outer_size, trailing);
  trailing->SetNext(bytes.size(), next);
  return trailing;
}
 
template <typename Derived>
constexpr Derived* ContiguousBlock<Derived>::DoSplitLast(
    size_t new_inner_size) {
  size_t new_outer_size = Derived::kBlockOverhead + new_inner_size;
  return DoSplitFirst(derived()->InnerSize() - new_outer_size);
}
 
template <typename Derived>
constexpr void ContiguousBlock<Derived>::DoMergeNext() {
  Derived* next = derived()->Next();
  if (next != nullptr) {
    size_t outer_size = derived()->OuterSize() + next->OuterSize();
    derived()->SetNext(outer_size, next->Next());
  }
}
 
template <typename Derived>
constexpr bool ContiguousBlock<Derived>::DoCheckInvariants(bool strict) const {
  bool valid = true;
 
  Derived* next = derived()->NextUnchecked();
  if (next != nullptr) {
    valid &= (cpp20::bit_cast<uintptr_t>(next) % Derived::kAlignment) == 0;
    if constexpr (Hardening::kIncludesDebugChecks) {
      internal::CheckNextMisaligned(this, next, valid || !strict);
    }
 
    Derived* next_prev = next->PrevUnchecked();
    valid &= this == next_prev;
    if constexpr (Hardening::kIncludesDebugChecks) {
      internal::CheckNextPrevMismatched(
          this, next, next_prev, valid || !strict);
    }
  }
 
  Derived* prev = derived()->PrevUnchecked();
  if (prev != nullptr) {
    valid &= (cpp20::bit_cast<uintptr_t>(prev) % Derived::kAlignment) == 0;
    if constexpr (Hardening::kIncludesDebugChecks) {
      internal::CheckPrevMisaligned(this, prev, valid || !strict);
    }
 
    Derived* prev_next = prev->NextUnchecked();
    valid &= this == prev_next;
    if constexpr (Hardening::kIncludesDebugChecks) {
      internal::CheckPrevNextMismatched(
          this, prev, prev_next, valid || !strict);
    }
  }
 
  return valid;
}
 
}  // namespace pw::allocator