Revert "[InstCombine] Support gep nuw in icmp folds" (#118698)

[llvm-project.git] / compiler-rt / lib / scudo / standalone / release.h

//===-- release.h -----------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef SCUDO_RELEASE_H_
#define SCUDO_RELEASE_H_

#include "common.h"
#include "list.h"
#include "mem_map.h"
#include "mutex.h"
#include "thread_annotations.h"

namespace scudo {

template <typename MemMapT> class RegionReleaseRecorder {
public:
  RegionReleaseRecorder(MemMapT *RegionMemMap, uptr Base, uptr Offset = 0)
      : RegionMemMap(RegionMemMap), Base(Base), Offset(Offset) {}

  uptr getReleasedRangesCount() const { return ReleasedRangesCount; }

  uptr getReleasedBytes() const { return ReleasedBytes; }

  uptr getBase() const { return Base; }

  // Releases [From, To) range of pages back to OS. Note that `From` and `To`
  // are offseted from `Base` + Offset.
  void releasePageRangeToOS(uptr From, uptr To) {
    const uptr Size = To - From;
    RegionMemMap->releasePagesToOS(getBase() + Offset + From, Size);
    ReleasedRangesCount++;
    ReleasedBytes += Size;
  }

private:
  uptr ReleasedRangesCount = 0;
  uptr ReleasedBytes = 0;
  MemMapT *RegionMemMap = nullptr;
  uptr Base = 0;
  // The release offset from Base. This is used when we know a given range after
  // Base will not be released.
  uptr Offset = 0;
};

class ReleaseRecorder {
public:
  ReleaseRecorder(uptr Base, uptr Offset = 0, MapPlatformData *Data = nullptr)
      : Base(Base), Offset(Offset), Data(Data) {}

  uptr getReleasedRangesCount() const { return ReleasedRangesCount; }

  uptr getReleasedBytes() const { return ReleasedBytes; }

  uptr getBase() const { return Base; }

  // Releases [From, To) range of pages back to OS.
  void releasePageRangeToOS(uptr From, uptr To) {
    const uptr Size = To - From;
    releasePagesToOS(Base, From + Offset, Size, Data);
    ReleasedRangesCount++;
    ReleasedBytes += Size;
  }

private:
  uptr ReleasedRangesCount = 0;
  uptr ReleasedBytes = 0;
  // The starting address to release. Note that we may want to combine (Base +
  // Offset) as a new Base. However, the Base is retrieved from
  // `MapPlatformData` on Fuchsia, which means the offset won't be aware.
  // Therefore, store them separately to make it work on all the platforms.
  uptr Base = 0;
  // The release offset from Base. This is used when we know a given range after
  // Base will not be released.
  uptr Offset = 0;
  MapPlatformData *Data = nullptr;
};

class FragmentationRecorder {
public:
  FragmentationRecorder() = default;

  uptr getReleasedPagesCount() const { return ReleasedPagesCount; }

  void releasePageRangeToOS(uptr From, uptr To) {
    DCHECK_EQ((To - From) % getPageSizeCached(), 0U);
    ReleasedPagesCount += (To - From) >> getPageSizeLogCached();
  }

private:
  uptr ReleasedPagesCount = 0;
};

template <uptr GroupSize, uptr NumGroups>
class MemoryGroupFragmentationRecorder {
public:
  const uptr NumPagesInOneGroup = GroupSize / getPageSizeCached();

  void releasePageRangeToOS(uptr From, uptr To) {
    for (uptr I = From / getPageSizeCached(); I < To / getPageSizeCached(); ++I)
      ++FreePagesCount[I / NumPagesInOneGroup];
  }

  uptr getNumFreePages(uptr GroupId) { return FreePagesCount[GroupId]; }

private:
  uptr FreePagesCount[NumGroups] = {};
};

// A buffer pool which holds a fixed number of static buffers of `uptr` elements
// for fast buffer allocation. If the request size is greater than
// `StaticBufferNumElements` or if all the static buffers are in use, it'll
// delegate the allocation to map().
template <uptr StaticBufferCount, uptr StaticBufferNumElements>
class BufferPool {
public:
  // Preserve 1 bit in the `Mask` so that we don't need to do zero-check while
  // extracting the least significant bit from the `Mask`.
  static_assert(StaticBufferCount < SCUDO_WORDSIZE, "");
  static_assert(isAligned(StaticBufferNumElements * sizeof(uptr),
                          SCUDO_CACHE_LINE_SIZE),
                "");

  struct Buffer {
    // Pointer to the buffer's memory, or nullptr if no buffer was allocated.
    uptr *Data = nullptr;

    // The index of the underlying static buffer, or StaticBufferCount if this
    // buffer was dynamically allocated. This value is initially set to a poison
    // value to aid debugging.
    uptr BufferIndex = ~static_cast<uptr>(0);

    // Only valid if BufferIndex == StaticBufferCount.
    MemMapT MemMap = {};
  };

  // Return a zero-initialized buffer which can contain at least the given
  // number of elements, or nullptr on failure.
  Buffer getBuffer(const uptr NumElements) {
    if (UNLIKELY(NumElements > StaticBufferNumElements))
      return getDynamicBuffer(NumElements);

    uptr index;
    {
      // TODO: In general, we expect this operation should be fast so the
      // waiting thread won't be put into sleep. The HybridMutex does implement
      // the busy-waiting but we may want to review the performance and see if
      // we need an explict spin lock here.
      ScopedLock L(Mutex);
      index = getLeastSignificantSetBitIndex(Mask);
      if (index < StaticBufferCount)
        Mask ^= static_cast<uptr>(1) << index;
    }

    if (index >= StaticBufferCount)
      return getDynamicBuffer(NumElements);

    Buffer Buf;
    Buf.Data = &RawBuffer[index * StaticBufferNumElements];
    Buf.BufferIndex = index;
    memset(Buf.Data, 0, StaticBufferNumElements * sizeof(uptr));
    return Buf;
  }

  void releaseBuffer(Buffer Buf) {
    DCHECK_NE(Buf.Data, nullptr);
    DCHECK_LE(Buf.BufferIndex, StaticBufferCount);
    if (Buf.BufferIndex != StaticBufferCount) {
      ScopedLock L(Mutex);
      DCHECK_EQ((Mask & (static_cast<uptr>(1) << Buf.BufferIndex)), 0U);
      Mask |= static_cast<uptr>(1) << Buf.BufferIndex;
    } else {
      Buf.MemMap.unmap();
    }
  }

  bool isStaticBufferTestOnly(const Buffer &Buf) {
    DCHECK_NE(Buf.Data, nullptr);
    DCHECK_LE(Buf.BufferIndex, StaticBufferCount);
    return Buf.BufferIndex != StaticBufferCount;
  }

private:
  Buffer getDynamicBuffer(const uptr NumElements) {
    // When using a heap-based buffer, precommit the pages backing the
    // Vmar by passing |MAP_PRECOMMIT| flag. This allows an optimization
    // where page fault exceptions are skipped as the allocated memory
    // is accessed. So far, this is only enabled on Fuchsia. It hasn't proven a
    // performance benefit on other platforms.
    const uptr MmapFlags = MAP_ALLOWNOMEM | (SCUDO_FUCHSIA ? MAP_PRECOMMIT : 0);
    const uptr MappedSize =
        roundUp(NumElements * sizeof(uptr), getPageSizeCached());
    Buffer Buf;
    if (Buf.MemMap.map(/*Addr=*/0, MappedSize, "scudo:counters", MmapFlags)) {
      Buf.Data = reinterpret_cast<uptr *>(Buf.MemMap.getBase());
      Buf.BufferIndex = StaticBufferCount;
    }
    return Buf;
  }

  HybridMutex Mutex;
  // '1' means that buffer index is not used. '0' means the buffer is in use.
  uptr Mask GUARDED_BY(Mutex) = ~static_cast<uptr>(0);
  uptr RawBuffer[StaticBufferCount * StaticBufferNumElements] GUARDED_BY(Mutex);
};

// A Region page map is used to record the usage of pages in the regions. It
// implements a packed array of Counters. Each counter occupies 2^N bits, enough
// to store counter's MaxValue. Ctor will try to use a static buffer first, and
// if that fails (the buffer is too small or already locked), will allocate the
// required Buffer via map(). The caller is expected to check whether the
// initialization was successful by checking isAllocated() result. For
// performance sake, none of the accessors check the validity of the arguments,
// It is assumed that Index is always in [0, N) range and the value is not
// incremented past MaxValue.
class RegionPageMap {
public:
  RegionPageMap()
      : Regions(0), NumCounters(0), CounterSizeBitsLog(0), CounterMask(0),
        PackingRatioLog(0), BitOffsetMask(0), SizePerRegion(0),
        BufferNumElements(0) {}
  RegionPageMap(uptr NumberOfRegions, uptr CountersPerRegion, uptr MaxValue) {
    reset(NumberOfRegions, CountersPerRegion, MaxValue);
  }
  ~RegionPageMap() {
    if (!isAllocated())
      return;
    Buffers.releaseBuffer(Buffer);
    Buffer = {};
  }

  // Lock of `StaticBuffer` is acquired conditionally and there's no easy way to
  // specify the thread-safety attribute properly in current code structure.
  // Besides, it's the only place we may want to check thread safety. Therefore,
  // it's fine to bypass the thread-safety analysis now.
  void reset(uptr NumberOfRegion, uptr CountersPerRegion, uptr MaxValue) {
    DCHECK_GT(NumberOfRegion, 0);
    DCHECK_GT(CountersPerRegion, 0);
    DCHECK_GT(MaxValue, 0);

    Regions = NumberOfRegion;
    NumCounters = CountersPerRegion;

    constexpr uptr MaxCounterBits = sizeof(*Buffer.Data) * 8UL;
    // Rounding counter storage size up to the power of two allows for using
    // bit shifts calculating particular counter's Index and offset.
    const uptr CounterSizeBits =
        roundUpPowerOfTwo(getMostSignificantSetBitIndex(MaxValue) + 1);
    DCHECK_LE(CounterSizeBits, MaxCounterBits);
    CounterSizeBitsLog = getLog2(CounterSizeBits);
    CounterMask = ~(static_cast<uptr>(0)) >> (MaxCounterBits - CounterSizeBits);

    const uptr PackingRatio = MaxCounterBits >> CounterSizeBitsLog;
    DCHECK_GT(PackingRatio, 0);
    PackingRatioLog = getLog2(PackingRatio);
    BitOffsetMask = PackingRatio - 1;

    SizePerRegion =
        roundUp(NumCounters, static_cast<uptr>(1U) << PackingRatioLog) >>
        PackingRatioLog;
    BufferNumElements = SizePerRegion * Regions;
    Buffer = Buffers.getBuffer(BufferNumElements);
  }

  bool isAllocated() const { return Buffer.Data != nullptr; }

  uptr getCount() const { return NumCounters; }

  uptr get(uptr Region, uptr I) const {
    DCHECK_LT(Region, Regions);
    DCHECK_LT(I, NumCounters);
    const uptr Index = I >> PackingRatioLog;
    const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
    return (Buffer.Data[Region * SizePerRegion + Index] >> BitOffset) &
           CounterMask;
  }

  void inc(uptr Region, uptr I) const {
    DCHECK_LT(get(Region, I), CounterMask);
    const uptr Index = I >> PackingRatioLog;
    const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
    DCHECK_LT(BitOffset, SCUDO_WORDSIZE);
    DCHECK_EQ(isAllCounted(Region, I), false);
    Buffer.Data[Region * SizePerRegion + Index] += static_cast<uptr>(1U)
                                                   << BitOffset;
  }

  void incN(uptr Region, uptr I, uptr N) const {
    DCHECK_GT(N, 0U);
    DCHECK_LE(N, CounterMask);
    DCHECK_LE(get(Region, I), CounterMask - N);
    const uptr Index = I >> PackingRatioLog;
    const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
    DCHECK_LT(BitOffset, SCUDO_WORDSIZE);
    DCHECK_EQ(isAllCounted(Region, I), false);
    Buffer.Data[Region * SizePerRegion + Index] += N << BitOffset;
  }

  void incRange(uptr Region, uptr From, uptr To) const {
    DCHECK_LE(From, To);
    const uptr Top = Min(To + 1, NumCounters);
    for (uptr I = From; I < Top; I++)
      inc(Region, I);
  }

  // Set the counter to the max value. Note that the max number of blocks in a
  // page may vary. To provide an easier way to tell if all the blocks are
  // counted for different pages, set to the same max value to denote the
  // all-counted status.
  void setAsAllCounted(uptr Region, uptr I) const {
    DCHECK_LE(get(Region, I), CounterMask);
    const uptr Index = I >> PackingRatioLog;
    const uptr BitOffset = (I & BitOffsetMask) << CounterSizeBitsLog;
    DCHECK_LT(BitOffset, SCUDO_WORDSIZE);
    Buffer.Data[Region * SizePerRegion + Index] |= CounterMask << BitOffset;
  }
  void setAsAllCountedRange(uptr Region, uptr From, uptr To) const {
    DCHECK_LE(From, To);
    const uptr Top = Min(To + 1, NumCounters);
    for (uptr I = From; I < Top; I++)
      setAsAllCounted(Region, I);
  }

  bool updateAsAllCountedIf(uptr Region, uptr I, uptr MaxCount) {
    const uptr Count = get(Region, I);
    if (Count == CounterMask)
      return true;
    if (Count == MaxCount) {
      setAsAllCounted(Region, I);
      return true;
    }
    return false;
  }
  bool isAllCounted(uptr Region, uptr I) const {
    return get(Region, I) == CounterMask;
  }

  uptr getBufferNumElements() const { return BufferNumElements; }

private:
  // We may consider making this configurable if there are cases which may
  // benefit from this.
  static const uptr StaticBufferCount = 2U;
  static const uptr StaticBufferNumElements = 512U;
  using BufferPoolT = BufferPool<StaticBufferCount, StaticBufferNumElements>;
  static BufferPoolT Buffers;

  uptr Regions;
  uptr NumCounters;
  uptr CounterSizeBitsLog;
  uptr CounterMask;
  uptr PackingRatioLog;
  uptr BitOffsetMask;

  uptr SizePerRegion;
  uptr BufferNumElements;
  BufferPoolT::Buffer Buffer;
};

template <class ReleaseRecorderT> class FreePagesRangeTracker {
public:
  explicit FreePagesRangeTracker(ReleaseRecorderT &Recorder)
      : Recorder(Recorder) {}

  void processNextPage(bool Released) {
    if (Released) {
      if (!InRange) {
        CurrentRangeStatePage = CurrentPage;
        InRange = true;
      }
    } else {
      closeOpenedRange();
    }
    CurrentPage++;
  }

  void skipPages(uptr N) {
    closeOpenedRange();
    CurrentPage += N;
  }

  void finish() { closeOpenedRange(); }

private:
  void closeOpenedRange() {
    if (InRange) {
      const uptr PageSizeLog = getPageSizeLogCached();
      Recorder.releasePageRangeToOS((CurrentRangeStatePage << PageSizeLog),
                                    (CurrentPage << PageSizeLog));
      InRange = false;
    }
  }

  ReleaseRecorderT &Recorder;
  bool InRange = false;
  uptr CurrentPage = 0;
  uptr CurrentRangeStatePage = 0;
};

struct PageReleaseContext {
  PageReleaseContext(uptr BlockSize, uptr NumberOfRegions, uptr ReleaseSize,
                     uptr ReleaseOffset = 0)
      : BlockSize(BlockSize), NumberOfRegions(NumberOfRegions) {
    const uptr PageSize = getPageSizeCached();
    if (BlockSize <= PageSize) {
      if (PageSize % BlockSize == 0) {
        // Same number of chunks per page, no cross overs.
        FullPagesBlockCountMax = PageSize / BlockSize;
        SameBlockCountPerPage = true;
      } else if (BlockSize % (PageSize % BlockSize) == 0) {
        // Some chunks are crossing page boundaries, which means that the page
        // contains one or two partial chunks, but all pages contain the same
        // number of chunks.
        FullPagesBlockCountMax = PageSize / BlockSize + 1;
        SameBlockCountPerPage = true;
      } else {
        // Some chunks are crossing page boundaries, which means that the page
        // contains one or two partial chunks.
        FullPagesBlockCountMax = PageSize / BlockSize + 2;
        SameBlockCountPerPage = false;
      }
    } else {
      if ((BlockSize & (PageSize - 1)) == 0) {
        // One chunk covers multiple pages, no cross overs.
        FullPagesBlockCountMax = 1;
        SameBlockCountPerPage = true;
      } else {
        // One chunk covers multiple pages, Some chunks are crossing page
        // boundaries. Some pages contain one chunk, some contain two.
        FullPagesBlockCountMax = 2;
        SameBlockCountPerPage = false;
      }
    }

    // TODO: For multiple regions, it's more complicated to support partial
    // region marking (which includes the complexity of how to handle the last
    // block in a region). We may consider this after markFreeBlocks() accepts
    // only free blocks from the same region.
    if (NumberOfRegions != 1)
      DCHECK_EQ(ReleaseOffset, 0U);

    const uptr PageSizeLog = getPageSizeLogCached();
    PagesCount = roundUp(ReleaseSize, PageSize) >> PageSizeLog;
    ReleasePageOffset = ReleaseOffset >> PageSizeLog;
  }

  // PageMap is lazily allocated when markFreeBlocks() is invoked.
  bool hasBlockMarked() const {
    return PageMap.isAllocated();
  }

  bool ensurePageMapAllocated() {
    if (PageMap.isAllocated())
      return true;
    PageMap.reset(NumberOfRegions, PagesCount, FullPagesBlockCountMax);
    // TODO: Log some message when we fail on PageMap allocation.
    return PageMap.isAllocated();
  }

  // Mark all the blocks in the given range [From, to). Instead of visiting all
  // the blocks, we will just mark the page as all counted. Note the `From` and
  // `To` has to be page aligned but with one exception, if `To` is equal to the
  // RegionSize, it's not necessary to be aligned with page size.
  bool markRangeAsAllCounted(uptr From, uptr To, uptr Base,
                             const uptr RegionIndex, const uptr RegionSize) {
    const uptr PageSize = getPageSizeCached();
    DCHECK_LT(From, To);
    DCHECK_LE(To, Base + RegionSize);
    DCHECK_EQ(From % PageSize, 0U);
    DCHECK_LE(To - From, RegionSize);

    if (!ensurePageMapAllocated())
      return false;

    uptr FromInRegion = From - Base;
    uptr ToInRegion = To - Base;
    uptr FirstBlockInRange = roundUpSlow(FromInRegion, BlockSize);

    // The straddling block sits across entire range.
    if (FirstBlockInRange >= ToInRegion)
      return true;

    // First block may not sit at the first pape in the range, move
    // `FromInRegion` to the first block page.
    FromInRegion = roundDown(FirstBlockInRange, PageSize);

    // When The first block is not aligned to the range boundary, which means
    // there is a block sitting acorss `From`, that looks like,
    //
    //   From                                             To
    //     V                                               V
    //     +-----------------------------------------------+
    //  +-----+-----+-----+-----+
    //  |     |     |     |     | ...
    //  +-----+-----+-----+-----+
    //     |-    first page     -||-    second page    -||- ...
    //
    // Therefore, we can't just mark the first page as all counted. Instead, we
    // increment the number of blocks in the first page in the page map and
    // then round up the `From` to the next page.
    if (FirstBlockInRange != FromInRegion) {
      DCHECK_GT(FromInRegion + PageSize, FirstBlockInRange);
      uptr NumBlocksInFirstPage =
          (FromInRegion + PageSize - FirstBlockInRange + BlockSize - 1) /
          BlockSize;
      PageMap.incN(RegionIndex, getPageIndex(FromInRegion),
                   NumBlocksInFirstPage);
      FromInRegion = roundUp(FromInRegion + 1, PageSize);
    }

    uptr LastBlockInRange = roundDownSlow(ToInRegion - 1, BlockSize);

    // Note that LastBlockInRange may be smaller than `FromInRegion` at this
    // point because it may contain only one block in the range.

    // When the last block sits across `To`, we can't just mark the pages
    // occupied by the last block as all counted. Instead, we increment the
    // counters of those pages by 1. The exception is that if it's the last
    // block in the region, it's fine to mark those pages as all counted.
    if (LastBlockInRange + BlockSize != RegionSize) {
      DCHECK_EQ(ToInRegion % PageSize, 0U);
      // The case below is like,
      //
      //   From                                      To
      //     V                                        V
      //     +----------------------------------------+
      //                          +-----+-----+-----+-----+
      //                          |     |     |     |     | ...
      //                          +-----+-----+-----+-----+
      //                    ... -||-    last page    -||-    next page    -|
      //
      // The last block is not aligned to `To`, we need to increment the
      // counter of `next page` by 1.
      if (LastBlockInRange + BlockSize != ToInRegion) {
        PageMap.incRange(RegionIndex, getPageIndex(ToInRegion),
                         getPageIndex(LastBlockInRange + BlockSize - 1));
      }
    } else {
      ToInRegion = RegionSize;
    }

    // After handling the first page and the last block, it's safe to mark any
    // page in between the range [From, To).
    if (FromInRegion < ToInRegion) {
      PageMap.setAsAllCountedRange(RegionIndex, getPageIndex(FromInRegion),
                                   getPageIndex(ToInRegion - 1));
    }

    return true;
  }

  template <class TransferBatchT, typename DecompactPtrT>
  bool markFreeBlocksInRegion(const IntrusiveList<TransferBatchT> &FreeList,
                              DecompactPtrT DecompactPtr, const uptr Base,
                              const uptr RegionIndex, const uptr RegionSize,
                              bool MayContainLastBlockInRegion) {
    if (!ensurePageMapAllocated())
      return false;

    const uptr PageSize = getPageSizeCached();
    if (MayContainLastBlockInRegion) {
      const uptr LastBlockInRegion =
          ((RegionSize / BlockSize) - 1U) * BlockSize;
      // The last block in a region may not use the entire page, we mark the
      // following "pretend" memory block(s) as free in advance.
      //
      //     Region Boundary
      //         v
      //  -----+-----------------------+
      //       |      Last Page        | <- Rounded Region Boundary
      //  -----+-----------------------+
      //   |-----||- trailing blocks  -|
      //      ^
      //   last block
      const uptr RoundedRegionSize = roundUp(RegionSize, PageSize);
      const uptr TrailingBlockBase = LastBlockInRegion + BlockSize;
      // If the difference between `RoundedRegionSize` and
      // `TrailingBlockBase` is larger than a page, that implies the reported
      // `RegionSize` may not be accurate.
      DCHECK_LT(RoundedRegionSize - TrailingBlockBase, PageSize);

      // Only the last page touched by the last block needs to mark the trailing
      // blocks. Note that if the last "pretend" block straddles the boundary,
      // we still have to count it in so that the logic of counting the number
      // of blocks on a page is consistent.
      uptr NumTrailingBlocks =
          (roundUpSlow(RoundedRegionSize - TrailingBlockBase, BlockSize) +
           BlockSize - 1) /
          BlockSize;
      if (NumTrailingBlocks > 0) {
        PageMap.incN(RegionIndex, getPageIndex(TrailingBlockBase),
                     NumTrailingBlocks);
      }
    }

    // Iterate over free chunks and count how many free chunks affect each
    // allocated page.
    if (BlockSize <= PageSize && PageSize % BlockSize == 0) {
      // Each chunk affects one page only.
      for (const auto &It : FreeList) {
        for (u16 I = 0; I < It.getCount(); I++) {
          const uptr PInRegion = DecompactPtr(It.get(I)) - Base;
          DCHECK_LT(PInRegion, RegionSize);
          PageMap.inc(RegionIndex, getPageIndex(PInRegion));
        }
      }
    } else {
      // In all other cases chunks might affect more than one page.
      DCHECK_GE(RegionSize, BlockSize);
      for (const auto &It : FreeList) {
        for (u16 I = 0; I < It.getCount(); I++) {
          const uptr PInRegion = DecompactPtr(It.get(I)) - Base;
          PageMap.incRange(RegionIndex, getPageIndex(PInRegion),
                           getPageIndex(PInRegion + BlockSize - 1));
        }
      }
    }

    return true;
  }

  uptr getPageIndex(uptr P) {
    return (P >> getPageSizeLogCached()) - ReleasePageOffset;
  }
  uptr getReleaseOffset() {
    return ReleasePageOffset << getPageSizeLogCached();
  }

  uptr BlockSize;
  uptr NumberOfRegions;
  // For partial region marking, some pages in front are not needed to be
  // counted.
  uptr ReleasePageOffset;
  uptr PagesCount;
  uptr FullPagesBlockCountMax;
  bool SameBlockCountPerPage;
  RegionPageMap PageMap;
};

// Try to release the page which doesn't have any in-used block, i.e., they are
// all free blocks. The `PageMap` will record the number of free blocks in each
// page.
template <class ReleaseRecorderT, typename SkipRegionT>
NOINLINE void
releaseFreeMemoryToOS(PageReleaseContext &Context,
                      ReleaseRecorderT &Recorder, SkipRegionT SkipRegion) {
  const uptr PageSize = getPageSizeCached();
  const uptr BlockSize = Context.BlockSize;
  const uptr PagesCount = Context.PagesCount;
  const uptr NumberOfRegions = Context.NumberOfRegions;
  const uptr ReleasePageOffset = Context.ReleasePageOffset;
  const uptr FullPagesBlockCountMax = Context.FullPagesBlockCountMax;
  const bool SameBlockCountPerPage = Context.SameBlockCountPerPage;
  RegionPageMap &PageMap = Context.PageMap;

  // Iterate over pages detecting ranges of pages with chunk Counters equal
  // to the expected number of chunks for the particular page.
  FreePagesRangeTracker<ReleaseRecorderT> RangeTracker(Recorder);
  if (SameBlockCountPerPage) {
    // Fast path, every page has the same number of chunks affecting it.
    for (uptr I = 0; I < NumberOfRegions; I++) {
      if (SkipRegion(I)) {
        RangeTracker.skipPages(PagesCount);
        continue;
      }
      for (uptr J = 0; J < PagesCount; J++) {
        const bool CanRelease =
            PageMap.updateAsAllCountedIf(I, J, FullPagesBlockCountMax);
        RangeTracker.processNextPage(CanRelease);
      }
    }
  } else {
    // Slow path, go through the pages keeping count how many chunks affect
    // each page.
    const uptr Pn = BlockSize < PageSize ? PageSize / BlockSize : 1;
    const uptr Pnc = Pn * BlockSize;
    // The idea is to increment the current page pointer by the first chunk
    // size, middle portion size (the portion of the page covered by chunks
    // except the first and the last one) and then the last chunk size, adding
    // up the number of chunks on the current page and checking on every step
    // whether the page boundary was crossed.
    for (uptr I = 0; I < NumberOfRegions; I++) {
      if (SkipRegion(I)) {
        RangeTracker.skipPages(PagesCount);
        continue;
      }
      uptr PrevPageBoundary = 0;
      uptr CurrentBoundary = 0;
      if (ReleasePageOffset > 0) {
        PrevPageBoundary = ReleasePageOffset << getPageSizeLogCached();
        CurrentBoundary = roundUpSlow(PrevPageBoundary, BlockSize);
      }
      for (uptr J = 0; J < PagesCount; J++) {
        const uptr PageBoundary = PrevPageBoundary + PageSize;
        uptr BlocksPerPage = Pn;
        if (CurrentBoundary < PageBoundary) {
          if (CurrentBoundary > PrevPageBoundary)
            BlocksPerPage++;
          CurrentBoundary += Pnc;
          if (CurrentBoundary < PageBoundary) {
            BlocksPerPage++;
            CurrentBoundary += BlockSize;
          }
        }
        PrevPageBoundary = PageBoundary;
        const bool CanRelease =
            PageMap.updateAsAllCountedIf(I, J, BlocksPerPage);
        RangeTracker.processNextPage(CanRelease);
      }
    }
  }
  RangeTracker.finish();
}

} // namespace scudo

#endif // SCUDO_RELEASE_H_