//===-- sanitizer_allocator_primary32.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
//
//===----------------------------------------------------------------------===//
//
// Part of the Sanitizer Allocator.
//
//===----------------------------------------------------------------------===//
#ifndef SANITIZER_ALLOCATOR_H
#error This file must be included inside sanitizer_allocator.h
#endif

template<class SizeClassAllocator> struct SizeClassAllocator32LocalCache;

// SizeClassAllocator32 -- allocator for 32-bit address space.
// This allocator can theoretically be used on 64-bit arch, but there it is less
// efficient than SizeClassAllocator64.
//
// [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
// be returned by MmapOrDie().
//
// Region:
//   a result of a single call to MmapAlignedOrDieOnFatalError(kRegionSize,
//                                                             kRegionSize).
// Since the regions are aligned by kRegionSize, there are exactly
// kNumPossibleRegions possible regions in the address space and so we keep
// a ByteMap possible_regions to store the size classes of each Region.
// 0 size class means the region is not used by the allocator.
//
// One Region is used to allocate chunks of a single size class.
// A Region looks like this:
// UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1
//
// In order to avoid false sharing the objects of this class should be
// chache-line aligned.

struct SizeClassAllocator32FlagMasks {  //  Bit masks.
  enum {
    kRandomShuffleChunks = 1,
    kUseSeparateSizeClassForBatch = 2,
  };
};

template <class Params>
class SizeClassAllocator32 {
 private:
  static const u64 kTwoLevelByteMapSize1 =
      (Params::kSpaceSize >> Params::kRegionSizeLog) >> 12;
  static const u64 kMinFirstMapSizeTwoLevelByteMap = 4;

 public:
  using AddressSpaceView = typename Params::AddressSpaceView;
  static const uptr kSpaceBeg = Params::kSpaceBeg;
  static const u64 kSpaceSize = Params::kSpaceSize;
  static const uptr kMetadataSize = Params::kMetadataSize;
  typedef typename Params::SizeClassMap SizeClassMap;
  static const uptr kRegionSizeLog = Params::kRegionSizeLog;
  typedef typename Params::MapUnmapCallback MapUnmapCallback;
  using ByteMap = typename conditional<
      (kTwoLevelByteMapSize1 < kMinFirstMapSizeTwoLevelByteMap),
      FlatByteMap<(Params::kSpaceSize >> Params::kRegionSizeLog),
                  AddressSpaceView>,
      TwoLevelByteMap<kTwoLevelByteMapSize1, 1 << 12, AddressSpaceView>>::type;

  COMPILER_CHECK(!SANITIZER_SIGN_EXTENDED_ADDRESSES ||
                 (kSpaceSize & (kSpaceSize - 1)) == 0);

  static const bool kRandomShuffleChunks = Params::kFlags &
      SizeClassAllocator32FlagMasks::kRandomShuffleChunks;
  static const bool kUseSeparateSizeClassForBatch = Params::kFlags &
      SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch;

  struct TransferBatch {
    static const uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2;
    void SetFromArray(void *batch[], uptr count) {
      DCHECK_LE(count, kMaxNumCached);
      count_ = count;
      for (uptr i = 0; i < count; i++)
        batch_[i] = batch[i];
    }
    uptr Count() const { return count_; }
    void Clear() { count_ = 0; }
    void Add(void *ptr) {
      batch_[count_++] = ptr;
      DCHECK_LE(count_, kMaxNumCached);
    }
    void CopyToArray(void *to_batch[]) const {
      for (uptr i = 0, n = Count(); i < n; i++)
        to_batch[i] = batch_[i];
    }

    // How much memory do we need for a batch containing n elements.
    static uptr AllocationSizeRequiredForNElements(uptr n) {
      return sizeof(uptr) * 2 + sizeof(void *) * n;
    }
    static uptr MaxCached(uptr size) {
      return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(size));
    }

    TransferBatch *next;

   private:
    uptr count_;
    void *batch_[kMaxNumCached];
  };

  static const uptr kBatchSize = sizeof(TransferBatch);
  COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0);
  COMPILER_CHECK(kBatchSize == SizeClassMap::kMaxNumCachedHint * sizeof(uptr));

  static uptr ClassIdToSize(uptr class_id) {
    return (class_id == SizeClassMap::kBatchClassID) ?
        kBatchSize : SizeClassMap::Size(class_id);
  }

  typedef SizeClassAllocator32<Params> ThisT;
  typedef SizeClassAllocator32LocalCache<ThisT> AllocatorCache;

  void Init(s32 release_to_os_interval_ms, uptr heap_start = 0) {
    CHECK(!heap_start);
    possible_regions.Init();
    internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));
  }

  s32 ReleaseToOSIntervalMs() const {
    return kReleaseToOSIntervalNever;
  }

  void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
    // This is empty here. Currently only implemented in 64-bit allocator.
  }

  void ForceReleaseToOS() {
    // Currently implemented in 64-bit allocator only.
  }

  void *MapWithCallback(uptr size) {
    void *res = MmapOrDie(size, PrimaryAllocatorName);
    MapUnmapCallback().OnMap((uptr)res, size);
    return res;
  }

  void UnmapWithCallback(uptr beg, uptr size) {
    MapUnmapCallback().OnUnmap(beg, size);
    UnmapOrDie(reinterpret_cast<void *>(beg), size);
  }

  static bool CanAllocate(uptr size, uptr alignment) {
    return size <= SizeClassMap::kMaxSize &&
      alignment <= SizeClassMap::kMaxSize;
  }

  void *GetMetaData(const void *p) {
    CHECK(kMetadataSize);
    CHECK(PointerIsMine(p));
    uptr mem = reinterpret_cast<uptr>(p);
    uptr beg = ComputeRegionBeg(mem);
    uptr size = ClassIdToSize(GetSizeClass(p));
    u32 offset = mem - beg;
    uptr n = offset / (u32)size;  // 32-bit division
    uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;
    return reinterpret_cast<void*>(meta);
  }

  NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,
                                        uptr class_id) {
    DCHECK_LT(class_id, kNumClasses);
    SizeClassInfo *sci = GetSizeClassInfo(class_id);
    SpinMutexLock l(&sci->mutex);
    if (sci->free_list.empty()) {
      if (UNLIKELY(!PopulateFreeList(stat, c, sci, class_id)))
        return nullptr;
      DCHECK(!sci->free_list.empty());
    }
    TransferBatch *b = sci->free_list.front();
    sci->free_list.pop_front();
    return b;
  }

  NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,
                                TransferBatch *b) {
    DCHECK_LT(class_id, kNumClasses);
    CHECK_GT(b->Count(), 0);
    SizeClassInfo *sci = GetSizeClassInfo(class_id);
    SpinMutexLock l(&sci->mutex);
    sci->free_list.push_front(b);
  }

  bool PointerIsMine(const void *p) {
    uptr mem = reinterpret_cast<uptr>(p);
    if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
      mem &= (kSpaceSize - 1);
    if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)
      return false;
    return GetSizeClass(p) != 0;
  }

  uptr GetSizeClass(const void *p) {
    return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))];
  }

  void *GetBlockBegin(const void *p) {
    CHECK(PointerIsMine(p));
    uptr mem = reinterpret_cast<uptr>(p);
    uptr beg = ComputeRegionBeg(mem);
    uptr size = ClassIdToSize(GetSizeClass(p));
    u32 offset = mem - beg;
    u32 n = offset / (u32)size;  // 32-bit division
    uptr res = beg + (n * (u32)size);
    return reinterpret_cast<void*>(res);
  }

  uptr GetActuallyAllocatedSize(void *p) {
    CHECK(PointerIsMine(p));
    return ClassIdToSize(GetSizeClass(p));
  }

  static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }

  uptr TotalMemoryUsed() {
    // No need to lock here.
    uptr res = 0;
    for (uptr i = 0; i < kNumPossibleRegions; i++)
      if (possible_regions[i])
        res += kRegionSize;
    return res;
  }

  void TestOnlyUnmap() {
    for (uptr i = 0; i < kNumPossibleRegions; i++)
      if (possible_regions[i])
        UnmapWithCallback((i * kRegionSize), kRegionSize);
  }

  // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
  // introspection API.
  void ForceLock() NO_THREAD_SAFETY_ANALYSIS {
    for (uptr i = 0; i < kNumClasses; i++) {
      GetSizeClassInfo(i)->mutex.Lock();
    }
  }

  void ForceUnlock() NO_THREAD_SAFETY_ANALYSIS {
    for (int i = kNumClasses - 1; i >= 0; i--) {
      GetSizeClassInfo(i)->mutex.Unlock();
    }
  }

  // Iterate over all existing chunks.
  // The allocator must be locked when calling this function.
  void ForEachChunk(ForEachChunkCallback callback, void *arg) {
    for (uptr region = 0; region < kNumPossibleRegions; region++)
      if (possible_regions[region]) {
        uptr chunk_size = ClassIdToSize(possible_regions[region]);
        uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);
        uptr region_beg = region * kRegionSize;
        for (uptr chunk = region_beg;
             chunk < region_beg + max_chunks_in_region * chunk_size;
             chunk += chunk_size) {
          // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
          callback(chunk, arg);
        }
      }
  }

  void PrintStats() {}

  static uptr AdditionalSize() { return 0; }

  typedef SizeClassMap SizeClassMapT;
  static const uptr kNumClasses = SizeClassMap::kNumClasses;

 private:
  static const uptr kRegionSize = 1 << kRegionSizeLog;
  static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;

  struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) SizeClassInfo {
    StaticSpinMutex mutex;
    IntrusiveList<TransferBatch> free_list;
    u32 rand_state;
  };
  COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0);

  uptr ComputeRegionId(uptr mem) const {
    if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
      mem &= (kSpaceSize - 1);
    const uptr res = mem >> kRegionSizeLog;
    CHECK_LT(res, kNumPossibleRegions);
    return res;
  }

  uptr ComputeRegionBeg(uptr mem) {
    return mem & ~(kRegionSize - 1);
  }

  uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
    DCHECK_LT(class_id, kNumClasses);
    const uptr res = reinterpret_cast<uptr>(MmapAlignedOrDieOnFatalError(
        kRegionSize, kRegionSize, PrimaryAllocatorName));
    if (UNLIKELY(!res))
      return 0;
    MapUnmapCallback().OnMap(res, kRegionSize);
    stat->Add(AllocatorStatMapped, kRegionSize);
    CHECK(IsAligned(res, kRegionSize));
    possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id));
    return res;
  }

  SizeClassInfo *GetSizeClassInfo(uptr class_id) {
    DCHECK_LT(class_id, kNumClasses);
    return &size_class_info_array[class_id];
  }

  bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id,
                       TransferBatch **current_batch, uptr max_count,
                       uptr *pointers_array, uptr count) {
    // If using a separate class for batches, we do not need to shuffle it.
    if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch ||
        class_id != SizeClassMap::kBatchClassID))
      RandomShuffle(pointers_array, count, &sci->rand_state);
    TransferBatch *b = *current_batch;
    for (uptr i = 0; i < count; i++) {
      if (!b) {
        b = c->CreateBatch(class_id, this, (TransferBatch*)pointers_array[i]);
        if (UNLIKELY(!b))
          return false;
        b->Clear();
      }
      b->Add((void*)pointers_array[i]);
      if (b->Count() == max_count) {
        sci->free_list.push_back(b);
        b = nullptr;
      }
    }
    *current_batch = b;
    return true;
  }

  bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
                        SizeClassInfo *sci, uptr class_id) {
    const uptr region = AllocateRegion(stat, class_id);
    if (UNLIKELY(!region))
      return false;
    if (kRandomShuffleChunks)
      if (UNLIKELY(sci->rand_state == 0))
        // The random state is initialized from ASLR (PIE) and time.
        sci->rand_state = reinterpret_cast<uptr>(sci) ^ NanoTime();
    const uptr size = ClassIdToSize(class_id);
    const uptr n_chunks = kRegionSize / (size + kMetadataSize);
    const uptr max_count = TransferBatch::MaxCached(size);
    DCHECK_GT(max_count, 0);
    TransferBatch *b = nullptr;
    constexpr uptr kShuffleArraySize = 48;
    uptr shuffle_array[kShuffleArraySize];
    uptr count = 0;
    for (uptr i = region; i < region + n_chunks * size; i += size) {
      shuffle_array[count++] = i;
      if (count == kShuffleArraySize) {
        if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
                                      shuffle_array, count)))
          return false;
        count = 0;
      }
    }
    if (count) {
      if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
                                    shuffle_array, count)))
        return false;
    }
    if (b) {
      CHECK_GT(b->Count(), 0);
      sci->free_list.push_back(b);
    }
    return true;
  }

  ByteMap possible_regions;
  SizeClassInfo size_class_info_array[kNumClasses];
};