allocator-inl.h

Go to the documentation of this file.

#pragma once
 
#include <algorithm>
 
#include "src/allocator.h"
#include "src/globals.h"
#include "src/platform/platform-base.h"
 
namespace broom {
FreeListAllocator::~FreeListAllocator() {
  // Unmap all of our spaces.
  for (const MemorySpace& space : spaces_) {
    platform::UnmapMemorySpace(space);
  }
  for (const MemorySpace& space : large_spaces_) {
    platform::UnmapMemorySpace(space);
  }
}
 
// Creates a new MemorySpace for use in the allocator. This method can be quite
// slow, so calling it should be the last resort in any allocation strategy.
bool FreeListAllocator::Grow(size_t requested_size,
                             MemorySpace** space_to_update) {
  size_t size_to_grow_by;
  // Figure out what space we need to allocate in.
  if (requested_size >= LargeSpaceThreshold()) {
    // If we are allocating in the large space, round up the size to match an
    // expected multiple of the large space size.
    requested_size = RoundUp<kGiantMappingSize>(requested_size);
    size_to_grow_by = std::max(requested_size, large_space_size_);
  } else {
    BASSERT_LT(requested_size, space_size_,
               "requested_size >= space_size: {} >= {}", requested_size,
               space_size_);
    size_to_grow_by = space_size_;
  }
  // Get the new space and ensure its validity.
  MemorySpace space = platform::MapMemorySpace(size_to_grow_by);
  if (!space.IsValid()) BROOM_UNLIKELY return false;
  BASSERT_LE(stats_.total_mapped_bytes,
             std::numeric_limits<decltype(stats_.total_mapped_bytes)>::max() -
                 size_to_grow_by,
             "total_mapped_bytes would overflow: {}",
             stats_.total_mapped_bytes);
  stats_.total_mapped_bytes += size_to_grow_by;
  stats_.free_bytes += size_to_grow_by;
  if (size_to_grow_by > LargeSpaceThreshold()) {
    large_spaces_.emplace_back(space);
    // Update our currently used large space.
    current_large_space_ = &large_spaces_[large_spaces_.size() - 1];
    *space_to_update = current_large_space_;
    return true;
  } else {
    spaces_.emplace_back(space);
    // Update our currently used regular space.
    current_space_ = &spaces_[spaces_.size() - 1];
    *space_to_update = current_space_;
    return true;
  }
  abort();
}
 
#ifdef BROOM_DEBUG_SLOW
void FreeListAllocator::PrintList(std::string prefix,
                                  const FreeList& free_list) const {
  std::println("{}", prefix);
  for (const auto& space : free_list) {
    std::println("  {:#x} .. {:#x}", space.Start(), space.End());
  }
}
 
bool FreeListAllocator::VerifyLists() const {
  absl::btree_set<UintPtr> verifier_front;
  absl::btree_set<UintPtr> verifier_back;
  for (const auto& space : free_list_) {
    if (verifier_front.contains(space.Start()) ||
        verifier_back.contains(space.End())) {
      PrintList("Regular space FreeList:", free_list_);
      PrintList("Large space FreeList", large_free_list_);
      return false;
    }
    verifier_front.insert(space.Start());
    verifier_back.insert(space.End());
  }
 
  for (const auto& space : large_free_list_) {
    if (verifier_front.contains(space.Start()) ||
        verifier_back.contains(space.End())) {
      PrintList("Regular space FreeList:", free_list_);
      PrintList("Large space FreeList", large_free_list_);
      return false;
    }
    verifier_front.insert(space.Start());
    verifier_back.insert(space.End());
  }
  return true;
}
#endif
 
// Splits a B-tree node into two parts:
//  - [start, start + requested_size)
//  - [start + requested_size, end)
// The first split is used to fulfill an allocation request of requested_size
// and returned to the caller, while the second split is re-inserted into the
// B-tree as the remaining free space.
//
// Additionally, the metadata is updated as follows:
//  - metadata @ (start + requested_size) is first zeroed, and then its size is
//    updated to match the new size. The zeroing is a necessary step because we
//    don't know what kind of data was present there before, and we don't want
//    to accidentally have unexpected bits set in our metadata;
//
//  - metadata @ end has its size updated to match the remaining size. No
//  zeroing
//    is needed here because we know that metadata was already in this location,
//    and that it must have been disposed by virtue of it already being in our
//    B-tree.
//
// The real metadata of the first split is not updated as the allocation is not
// yet considered fulfilled. Doing so is not the job of this method.
void* FreeListAllocator::SplitFreeListEntry(FreeList& free_list,
                                            FreeList::iterator& pos,
                                            size_t requested_size) {
  // First split.
  void* allocated_ptr = pos->StartPtr();
  BDEBUG_LOG("ALLOCATOR: {:#x} .. {:#x} -> {:#x} .. {:#x}\n", pos->Start(),
             pos->End(), pos->Start(), pos->Start() + requested_size);
  auto node = free_list.extract(pos);
  node.value().IncrementStart(requested_size);
  // Second split.
  UintPtr new_ptr = node.value().Start();
  size_t new_size = node.value().Size();
  BDEBUG_LOG(" | {:#x} .. {:#x}\n", node.value().Start(), node.value().End());
  free_list.insert(std::move(node));
  BASSERT_SLOW(VerifyLists(), "Failed to verify lists");
  // Update the metadata.
  {
    AllocatorFrontMetadata* metadata =
        UnsafeCast<AllocatorFrontMetadata*>(new_ptr);
    metadata->ZeroBytes();
    metadata->SetSize(new_size);
  }
  {
    AllocatorBackMetadata* metadata = UnsafeCast<AllocatorBackMetadata*>(
        new_ptr + new_size - Allocator::kBackMetadataSize);
    metadata->SetSize(new_size);
  }
  return allocated_ptr;
}
 
// Returns a pointer to the start of a memory region that has enough space to
// hold requested_size bytes or a null pointer. The method will first attempt to
// find an exact match. Failing that, it will return the next best match. It
// also handles empty trees and trees with only one region in them.
void* FreeListAllocator::TryAllocateExactOrFindNext(FreeList& free_list,
                                                    FreeList::iterator& pos,
                                                    size_t requested_size) {
  // Since we are trying to extract a region from the tree, first ensure that
  // the tree is valid.
  BASSERT_SLOW(VerifyLists(), "Failed to verify lists");
  // If there are no entries, simply return a null pointer.
  if (pos == free_list.end()) return nullptr;
  if (pos->Size() == requested_size) {
    // Found an exact match, return that and remove it from our tree.
    void* allocated_ptr = pos->StartPtr();
    BDEBUG_LOG("ALLOCATOR: {:#x} .. {:#x}\n", pos->Start(), pos->End());
    free_list.erase(pos);
    return allocated_ptr;
  }
  // If we don't have an exact match, then this is the exact element we should
  // return, but we need to split it in the free list into the allocated portion
  // and free portion.
  BASSERT_GE(pos->Size(), requested_size, "Expected {} < {}", pos->Size(),
             requested_size);
  return SplitFreeListEntry(free_list, pos, requested_size);
}
 
void* FreeListAllocator::TryAllocateFromFreeListImpl(FreeList& free_list,
                                                     size_t requested_size) {
  // Early exit for no entries.
  if (free_list.size() == 0) return nullptr;
  auto cmp = [](const MemoryRegion& region, size_t requested_size) {
    return region.Size() < requested_size;
  };
  auto it =
      std::lower_bound(free_list.begin(), free_list.end(), requested_size, cmp);
  return TryAllocateExactOrFindNext(free_list, it, requested_size);
}
 
void* FreeListAllocator::TryAllocateFromLargeFreeList(size_t requested_size) {
  return TryAllocateFromFreeListImpl(large_free_list_, requested_size);
}
 
void* FreeListAllocator::TryAllocateFromFreeList(size_t requested_size) {
  return TryAllocateFromFreeListImpl(free_list_, requested_size);
}
 
// Ensures that the current space we're using is filled and that any remaining
// space is added to the corresponding free list.
void FreeListAllocator::FillSpaceAndAddToFreeList(FreeList* list,
                                                  MemorySpace* space) {
  // We need at least enough space to fit one pointer and our metadata. Storing
  // anything smaller than that is pointless.
  size_t remaining_bytes = space->RemainingBytes();
  if (remaining_bytes <= (Allocator::kTotalMetadataSize + kPointerSize)) {
    space->Fill();
    return;
  }
  // We are now sure we can fit this into our free list. Update the metadata in
  // the corresponding locations to maintain consistency and then add it to the
  // correct free list.
  AllocatorFrontMetadata* front_metadata =
      UnsafeCast<AllocatorFrontMetadata*>(space->Top());
  AllocatorBackMetadata* back_metadata = UnsafeCast<AllocatorBackMetadata*>(
      SafeCast<UintPtr>(space->End()) - Allocator::kBackMetadataSize);
  BASSERT(!front_metadata->IsCurrentlyAllocated(),
          "Front metadata should not be currently allocated");
  BASSERT(!back_metadata->IsCurrentlyAllocated(),
          "Back metadata should not be currently allocated");
  front_metadata->SetSize(remaining_bytes);
  back_metadata->SetSize(remaining_bytes);
 
  // Add it to our free list.
  list->emplace(space->Top(), space->End());
  space->Fill();
}
 
// Attempt to allocate a pointer that can fit requested_size bytes. We still
// don't fill in the metadata of the allocation here. The pointer returned is to
// the start of the region, i.e. to the start of the front metadata of the
// allocation.
//
// The strategy is to first try and allocate from our B-trees rather than use up
// new bytes in our latest allocated space or attempt growing the space. Failing
// that, we try to bump the top pointer in our latest memory space. If that also
// fails, we will map a new space all together.
void* FreeListAllocator::AllocateRawPointer(size_t requested_size) {
  MemorySpace** correct_space;
  FreeList* correct_list;
  // Determine which space this allocation belongs to and attempt to allocate
  // from our B-trees.
  if (requested_size >= LargeSpaceThreshold()) {
    void* result = TryAllocateFromLargeFreeList(requested_size);
    if (result != nullptr) return result;
    correct_space = &current_large_space_;
    correct_list = &large_free_list_;
  } else {
    void* result = TryAllocateFromFreeList(requested_size);
    if (result != nullptr) return result;
    correct_space = &current_space_;
    correct_list = &free_list_;
  }
 
  // We couldn't find a suitable region in a B-tree, attempt to bump the pointer
  // in our latest space.
  UintPtr maybe_ptr = *correct_space != nullptr
                          ? (*correct_space)->Allocate(requested_size)
                          : kNullUintPtr;
  if (maybe_ptr != kNullUintPtr) {
    return SafeCast<void*>(maybe_ptr);
  }
  // There wasn't enough room in the current space. Bump the top pointer to the
  // end of the space and add the region to the corresponding B-tree. Then, try
  // to map a new space.
  if (*correct_space != nullptr) {
    FillSpaceAndAddToFreeList(correct_list, *correct_space);
  }
  if (!Grow(requested_size, correct_space)) {
    return nullptr;
  }
  BENSURE_NE(*correct_space, nullptr, "correct_space shouldn't be NULL");
  // This should never fail as we've just finished successfully mapping a space
  // which can fit the amount of bytes requested.
  maybe_ptr = (*correct_space)->Allocate(requested_size);
  BENSURE_NE(maybe_ptr, kNullUintPtr, "Expected a successful allocation");
  BDEBUG_LOG("ALLOCATOR: ALLOCATE {:#x} .. {:#x}\n", maybe_ptr,
             maybe_ptr + requested_size);
  return SafeCast<void*>(maybe_ptr);
}
 
// Returns a pointer that user data will be stored into (right after the front
// metadata). The method will first attempt to allocate a enough space to fit
// all the data we need to store in there and then update the front and back
// metadata with the correct values.
void* FreeListAllocator::Allocate(size_t requested_size) {
  // Guard very large allocation sizes we cannot handle.
  if (requested_size > FreeListAllocator::MaximumAllocationSize())
    return nullptr;
  // Compute the real size.
  size_t real_size = FreeListAllocator::GetRealAllocationSize(requested_size);
  UintPtr definitely_pointer = SafeCast<UintPtr>(AllocateRawPointer(real_size));
  if (definitely_pointer == kNullUintPtr) return nullptr;
  // Update our metadata.
  {
    AllocatorFrontMetadata* metadata =
        UnsafeCast<AllocatorFrontMetadata*>(definitely_pointer);
    metadata->MarkAllocated(real_size);
  }
  {
    AllocatorBackMetadata* metadata = UnsafeCast<AllocatorBackMetadata*>(
        SafeCast<UintPtr>(definitely_pointer) + real_size -
        Allocator::kBackMetadataSize);
    metadata->MarkAllocated(real_size);
  }
  BASSERT(IsAligned<kPointerSize>(definitely_pointer +
                                  Allocator::kFrontMetadataSize),
          "The allocated pointer ({:#x}) must be pointer aligned.",
          definitely_pointer);
  BASSERT_LE(
      stats_.allocated_bytes,
      std::numeric_limits<decltype(stats_.allocated_bytes)>::max() - real_size,
      "allocated_bytes would ovreflow = {}", stats_.allocated_bytes);
  BASSERT_GE(stats_.free_bytes, real_size, "free_bytes would underflow = {}",
             stats_.free_bytes);
  // Update our statistics.
  stats_.allocated_bytes += real_size;
  stats_.free_bytes -= real_size;
  // Return the pointer where the real data will be stored.
  return SafeCast<void*>(definitely_pointer + Allocator::kFrontMetadataSize);
}
 
void FreeListAllocator::AddOrCoalesceLargeFreeList(
    const MemoryRegion current, const MemoryRegion previous,
    const MemoryRegion next, const MemoryRegion coalesced) {
  AddOrCoalesceFreeListImpl(large_free_list_, current, previous, next,
                            coalesced);
}
 
void FreeListAllocator::AddOrCoalesceFreeList(const MemoryRegion current,
                                              const MemoryRegion previous,
                                              const MemoryRegion next,
                                              const MemoryRegion coalesced) {
  AddOrCoalesceFreeListImpl(free_list_, current, previous, next, coalesced);
}
 
// Adds an entry to the correct B-tree or coalesces any entries that can be
// coalesced with the region we are attempting to add into the tree. We don't
// need to check if the regions can be coalesced, as we will have done so during
// pointer disposal by manipulating the corresponding allocator metadata. Here,
// we are simply maintaining the B-tree state. There are four different cases we
// need to handle:
//  - We can't coalesce the newly available free region, in which case we will
//    simply add it into the corresponding B-tree.
//
//  - We are able to coalesce with the region directly following the current
//    region, requiring us to update its start pointer (thereby changing its
//    size) and causing rebalancing in the B-tree.
//
//  - We are able to coalesce with the region directly before the current
//    region, requiring us to update its size, rebalancing the B-tree in the
//    process.
//
//  - We can coalesce with both the region directly before and following the
//    current region. That case is slightly more complicated than the other
//    three. We handle it by growing the region directly before the current
//    region and erasing the node in the B-tree corresponding to the region
//    directly following the current region. This action also causes tree
//    rebalancing.
void FreeListAllocator::AddOrCoalesceFreeListImpl(
    FreeList& free_list, const MemoryRegion current,
    const MemoryRegion previous, const MemoryRegion next,
    const MemoryRegion coalesced) {
  // Helpers.
  UintPtr start_current = current.Start();
  UintPtr end_current = current.End();
  UintPtr start_previous = previous.Start();
  UintPtr end_previous = previous.End();
  UintPtr start_next = next.Start();
  UintPtr end_next = next.End();
  UintPtr start_coalesced = coalesced.Start();
  UintPtr end_coalesced = coalesced.End();
 
  // We should never be called with a current region being null.
  BASSERT_NE(start_current, kNullUintPtr, "start_current is NULL");
  BASSERT_NE(end_current, kNullUintPtr, "end_current is NULL");
  if (start_current == start_coalesced && end_current == end_coalesced) {
    // We didn't coalesce anything, just add the new entry.
    BDEBUG_LOG("ALLOCATOR: FreeList ++ {:#x} .. {:#x}\n", start_current,
               end_current);
    free_list.insert({start_current, end_current});
  } else if (start_current == start_coalesced) {
    // Coalesced the next region. Fetch the next node and update it.
    BASSERT_NE(start_next, kNullUintPtr, "start_next is NULL");
    BASSERT_NE(end_next, kNullUintPtr, "end_next is NULL");
    const MemoryRegion region_to_find = {start_next, end_next};
    FreeList::iterator it = FindExactRegion(free_list, region_to_find);
    // [start_current, end_current) ++ [start_next, end_next)
    //   -> [start_current, end_next)
    BASSERT_NE(it, free_list.end(), "Couldn't find {:#x} .. {:#x}", start_next,
               end_next);
    auto node = free_list.extract(it);
    node.value() = {start_coalesced, end_coalesced};
    BDEBUG_LOG(
        "ALLOCATOR: Coalesce({:#x} .. {:#x}, {:#x} .. {:#x}) -> {:#x} .. "
        "{:#x}\n",
        start_current, end_current, start_next, end_next, node.value().Start(),
        node.value().End());
    free_list.insert(std::move(node));
  } else if (end_current == end_coalesced) {
    // Coalesced with the previous region. Update that node with the correct
    // information.
    BASSERT_NE(start_previous, kNullUintPtr, "start_previous is NULL");
    BASSERT_NE(end_previous, kNullUintPtr, "end_previous is NULL");
    const MemoryRegion region_to_find = {start_previous, end_previous};
    FreeList::iterator it = FindExactRegion(free_list, region_to_find);
    // [start_previous, end_previous) ++ [start_current, end_current)
    //   -> [start_previous, end_current)
    BASSERT_NE(it, free_list.end(), "Couldn't find {:#x} .. {:#x}",
               start_previous, end_previous);
    auto node = free_list.extract(it);
    node.value() = {start_coalesced, end_coalesced};
    BDEBUG_LOG(
        "ALLOCATOR: Coalesce({:#x} .. {:#x},  {:#x} .. {:#x}) -> {:#x} .. "
        "{:#x}\n",
        start_previous, end_previous, start_current, end_current,
        node.value().Start(), node.value().End());
    free_list.insert(std::move(node));
  } else {
    // Coalesced both. Need to squash the two nodes into one.
    BASSERT_NE(start_next, kNullUintPtr, "start_next is NULL");
    BASSERT_NE(end_next, kNullUintPtr, "end_next is NULL");
    BASSERT_NE(start_previous, kNullUintPtr, "start_previous is NULL");
    BASSERT_NE(end_previous, kNullUintPtr, "end_previous is NULL");
    const MemoryRegion previous_region = {start_previous, end_previous};
    FreeList::iterator it_previous =
        FindExactRegion(free_list, previous_region);
    const MemoryRegion next_region = {start_next, end_next};
    if (BROOM_DEBUG_BOOL) {
      BROOM_UNUSED FreeList::iterator it_next =
          FindExactRegion(free_list, next_region);
      BASSERT_NE(it_next, free_list.end(),
                 "Couldn't find next range: {:#x} .. {:#x}", start_next,
                 end_next);
    }
    // [start_previous, end_previous) ++
    // [start_current, end_current) ++
    // [start_next, end_next)
    //   -> [start_previous, end_next)
    BASSERT_NE(it_previous, free_list.end(),
               "Couldn't find previous range: {:#x} .. {:#x}", start_previous,
               end_previous);
    auto node = free_list.extract(it_previous);
    node.value() = {start_coalesced, end_coalesced};
    BDEBUG_LOG(
        "ALLOCATOR: Coalesce({:#x} .. {:#x}, {:#x} .. {:#x},  {:#x} .. {:#x}) "
        "->"
        " {:#x} .. {:#x}, remove: {:#x}, {:#x}\n",
        start_previous, end_previous, start_current, end_current, start_next,
        end_next, node.value().Start(), node.value().End(), start_next,
        end_next);
    free_list.insert(std::move(node));
    // Erase the next region as we have coalesced it into the previous one.
    free_list.erase(FindExactRegion(free_list, next_region));
  }
  BASSERT_SLOW(VerifyLists(), "Failed to verify lists");
}
 
// The main meat of the disposal for FreeListAllocator. The strategy for
// disposal is to first find the space which the pointer belongs to so that we
// have a start and end of the space we can check. We then check for two things:
//  - Can the memory region immediately preceding the region described by the
//    pointer we are currently disposing be coalesced with the current one;
//
//  - Ditto for the region immediately following it.
//
// After we determine that a region can be coalesced, we attempt to update its
// metadata to do so and keep track of the start and end of the coalesced
// region. Once we have checked both the previous and next region and updated
// any metadata that needed updating, we call into a helper method to update our
// B-tree state.
void FreeListAllocator::DisposeRawPointer(void* definitely_pointer) {
  if (definitely_pointer == nullptr) return;
  BASSERT_SLOW(VerifyLists(), "Failed to verify lists");
  UintPtr space_start = kNullUintPtr;
  UintPtr space_end = kNullUintPtr;
  MemoryAddress ptr_addr = SafeCast<MemoryAddress>(definitely_pointer);
  // Look through our large spaces to find the pointer.
  for (const MemorySpace& space : large_spaces_) {
    if (space.Start() <= ptr_addr && ptr_addr < space.End()) {
      space_start = space.Start();
      space_end = space.End();
      break;
    }
  }
  UintPtr to_dispose =
      SafeCast<UintPtr>(definitely_pointer) - Allocator::kFrontMetadataSize;
  if (space_start == kNullUintPtr) {
    // If we haven't found the pointer in one of our large spaces, we know that
    // regular spaces are always sized equally, so we can simply mask the
    // pointer to the start of our space.
    space_start = to_dispose & Allocator::SpaceMask(space_size_);
    space_end = space_start + space_size_;
  }
  BASSERT_NE(space_start, kNullUintPtr, "Expected to find a space");
  // Get our allocator metadata. We need both the top and bottom to attempt to
  // coalesce the free list.
  AllocatorFrontMetadata* metadata =
      UnsafeCast<AllocatorFrontMetadata*>(to_dispose);
  size_t current_size = metadata->Size();
  BASSERT_GE(stats_.allocated_bytes, current_size,
             "allocated_bytes would underflow = {}", stats_.allocated_bytes);
  BASSERT_LE(
      stats_.free_bytes,
      std::numeric_limits<decltype(stats_.free_bytes)>::max() - current_size,
      "free_bytes would overflow = {}", stats_.free_bytes);
  // Update our statistics.
  stats_.allocated_bytes -= current_size;
  stats_.free_bytes += current_size;
  AllocatorBackMetadata* metadata_bottom = UnsafeCast<AllocatorBackMetadata*>(
      to_dispose + current_size - Allocator::kBackMetadataSize);
  BDEBUG_LOG("ALLOCATOR: Dispose {:#x} .. {:#x}\n", to_dispose,
             to_dispose + current_size);
  // Dispose both the top and bottom metadata of the current allocation.
  metadata->MarkDisposed();
  metadata_bottom->MarkDisposed();
  // Helpers.
  UintPtr start_of_current_region = to_dispose;
  UintPtr end_of_current_region =
      SafeCast<UintPtr>(metadata_bottom) + Allocator::kBackMetadataSize;
  UintPtr start_of_previous_region = kNullUintPtr;
  UintPtr end_of_previous_region = kNullUintPtr;
  UintPtr start_of_next_region = kNullUintPtr;
  UintPtr end_of_next_region = kNullUintPtr;
  UintPtr start_of_coalesced_region = start_of_current_region;
  UintPtr end_of_coalesced_region = end_of_current_region;
  if (to_dispose > space_start) {
    // We aren't at the start of the space, therefore there must be a previous
    // region and we can check its metadata.
    AllocatorBackMetadata* previous = UnsafeCast<AllocatorBackMetadata*>(
        to_dispose - Allocator::kBackMetadataSize);
    BASSERT(previous->IsValid(), "Expected {:#x} to be valid",
            SafeCast<UintPtr>(previous));
    AllocatorFrontMetadata* previous_top =
        UnsafeCast<AllocatorFrontMetadata*>(to_dispose - previous->Size());
    // Keep track of the previous region's start and end.
    start_of_previous_region = SafeCast<UintPtr>(previous_top);
    end_of_previous_region =
        SafeCast<UintPtr>(previous) + Allocator::kBackMetadataSize;
    // Attempt to coalesce the current disposed allocation into the previous
    // one.
    if (!previous->IsCurrentlyAllocated()) {
      BDEBUG_LOG("ALLOCATOR: Attempt coalesce with previous: {:#x} .. {:#x}\n",
                 start_of_previous_region, end_of_previous_region);
      // Attempt to grow the allocation that was maybe disposed before our
      // current allocation. If this succeeds, we can proceed to grow the
      // bottom metadata as well.
      if (previous_top->AttemptGrow(current_size)) {
        // We managed to grow the top metadata. Now grow the bottom of the
        // current allocation. This should always succeed.
        BENSURE(metadata_bottom->AttemptGrow(previous->Size()),
                "Failed to grow metadata_bottom");
        // Update the start of our coalesced region.
        start_of_coalesced_region = start_of_previous_region;
        metadata->ZeroBytes();
        metadata = previous_top;
      }
    }
  }
 
  // If our current region doesn't end at the end of the space, we must either
  // have a next region, or zeroes.
  if (to_dispose + current_size < space_end) {
    // Now attempt to coalesce the current allocation with the next allocation.
    AllocatorFrontMetadata* next =
        UnsafeCast<AllocatorFrontMetadata*>(to_dispose + current_size);
    // Effectively checks if the metadata exists, or if we're hitting zeroes.
    if (next->IsValid()) {
      AllocatorBackMetadata* next_bottom = UnsafeCast<AllocatorBackMetadata*>(
          SafeCast<UintPtr>(next) + next->Size() -
          Allocator::kBackMetadataSize);
      // Keep track of the start and end of the next region.
      start_of_next_region = SafeCast<UintPtr>(next);
      end_of_next_region =
          SafeCast<UintPtr>(next_bottom) + Allocator::kBackMetadataSize;
      // We need to check if it's initialised because we might be at the end of
      // our currently allocated area, and we rely on that being zeroed.
      if (!next->IsCurrentlyAllocated()) {
        BDEBUG_LOG("ALLOCATOR: Attempt coalesce with next: {:#x} .. {:#x}\n",
                   start_of_next_region, end_of_next_region);
        BASSERT_LE(
            SafeCast<UintPtr>(next_bottom), space_end,
            "Expected next_bottom to be lesser or equal to the space end: "
            "{:#x} > {:#x}",
            SafeCast<UintPtr>(next_bottom), space_end);
        // Attempt to grow the current allocation.
        if (metadata->AttemptGrow(next->Size())) {
          BENSURE(next_bottom->AttemptGrow(metadata_bottom->Size()),
                  "Failed to grow next_bottom");
          // Update the end of our coalesced region.
          end_of_coalesced_region = end_of_next_region;
          metadata_bottom->ZeroBytes();
          metadata_bottom = next_bottom;
        }
      }
    }
  }
 
  // Finally, coalesce the regions in our B-trees.
  if (current_size >= LargeSpaceThreshold()) {
    AddOrCoalesceLargeFreeList(
        {start_of_current_region, end_of_current_region},
        {start_of_previous_region, end_of_previous_region},
        {start_of_next_region, end_of_next_region},
        {start_of_coalesced_region, end_of_coalesced_region});
  } else {
    AddOrCoalesceFreeList({start_of_current_region, end_of_current_region},
                          {start_of_previous_region, end_of_previous_region},
                          {start_of_next_region, end_of_next_region},
                          {start_of_coalesced_region, end_of_coalesced_region});
  }
}
 
void FreeListAllocator::Dispose(void* definitely_pointer) {
  DisposeRawPointer(definitely_pointer);
}
 
// A helper function to figure out a base pointer (the one returned by our
// allocation method) from a possible inner pointer into an object. The GC needs
// this to operate during scanning. Our strategy here is to simply iterate
// through the spaces in order to determine which space contains our pointer,
// and then loop through the space looking for our pointer. Since our metadata
// is structured in a way where the front metadata holds the exact size of the
// current region, we can simply iterate region by region.
const void* FreeListAllocator::GetBasePointerOfMaybeInnerPointer(
    const void* maybe_inner) const {
  if (maybe_inner == nullptr) return nullptr;
  MemoryAddress ptr_addr = SafeCast<MemoryAddress>(maybe_inner);
  UintPtr space_start = kNullUintPtr;
  UintPtr space_end = kNullUintPtr;
  // Find the space which contains our pointer.
  for (const MemorySpace& space : spaces_) {
    if (space.Start() <= ptr_addr && ptr_addr < space.End()) {
      space_start = space.Start();
      space_end = space.End();
      break;
    }
  }
  if (space_start == kNullUintPtr) {
    for (const MemorySpace& space : large_spaces_) {
      if (space.Start() <= ptr_addr && ptr_addr < space.End()) {
        space_start = space.Start();
        space_end = space.End();
        break;
      }
    }
  }
  // No space, meaning this isn't a pointer allocated by this allocator.
  if (space_start == kNullUintPtr) return nullptr;
  UintPtr base_pointer = kNullUintPtr;
  UintPtr maybe_inner_ptr = SafeCast<UintPtr>(maybe_inner);
  size_t size_to_add = 0;
  // Now iterate through the regions, looking for the region that our pointer is
  // a part of.
  for (UintPtr current = space_start; current < space_end;
       current += size_to_add) {
    AllocatorFrontMetadata* metadata =
        UnsafeCast<AllocatorFrontMetadata*>(current);
    size_t current_chunk_size = metadata->Size();
    // We scanned a value that just happens to pretend to be a pointer into our
    // space, but we've obviously gone past the end of our currently allocated
    // space.
    if (current_chunk_size == 0) {
      return nullptr;
    }
    // This is a pointer somewhere into the metadata, so it shouldn't have been
    // a managed pointer actually used by the application.
    if (maybe_inner_ptr < current + Allocator::kFrontMetadataSize)
      return nullptr;
    if (maybe_inner_ptr >= current + Allocator::kFrontMetadataSize &&
        maybe_inner_ptr <= (current + current_chunk_size)) {
      if (metadata->IsCurrentlyAllocated()) {
        // We've found our pointer.
        base_pointer = current;
        break;
      } else {
        // This pointer has already been free'd, so there's no base pointer for
        // it. Simply return null.
        //
        // This early bailout isn't strictly necessary and is done for
        // performance reasons.
        return nullptr;
      }
    }
    size_to_add = current_chunk_size;
  }
  return SafeCast<const void*>(base_pointer + Allocator::kFrontMetadataSize);
}
}  // namespace broom