lib/scudo/standalone/primary32.h - compiler-rt - Git at Google

 //===-- 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
 //
 //===----------------------------------------------------------------------===//

 #ifndef SCUDO_PRIMARY32_H_
 #define SCUDO_PRIMARY32_H_

 #include "bytemap.h"
 #include "common.h"
 #include "list.h"
 #include "local_cache.h"
 #include "release.h"
 #include "report.h"
 #include "stats.h"
 #include "string_utils.h"

 namespace scudo {

 // SizeClassAllocator32 is an allocator for 32 or 64-bit address space.
 //
 // It maps Regions of 2^RegionSizeLog bytes aligned on a 2^RegionSizeLog bytes
 // boundary, and keeps a bytemap of the mappable address space to track the size
 // class they are associated with.
 //
 // Mapped regions are split into equally sized Blocks according to the size
 // class they belong to, and the associated pointers are shuffled to prevent any
 // predictable address pattern (the predictability increases with the block
 // size).
 //
 // Regions for size class 0 are special and used to hold TransferBatches, which
 // allow to transfer arrays of pointers from the global size class freelist to
 // the thread specific freelist for said class, and back.
 //
 // Memory used by this allocator is never unmapped but can be partially
 // reclaimed if the platform allows for it.

 template <class SizeClassMapT, uptr RegionSizeLog> class SizeClassAllocator32 {
 public:
   typedef SizeClassMapT SizeClassMap;
   // Regions should be large enough to hold the largest Block.
   COMPILER_CHECK((1UL << RegionSizeLog) >= SizeClassMap::MaxSize);
   typedef SizeClassAllocator32<SizeClassMapT, RegionSizeLog> ThisT;
   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
   typedef typename CacheT::TransferBatch TransferBatch;

   static uptr getSizeByClassId(uptr ClassId) {
     return (ClassId == SizeClassMap::BatchClassId)
                ? sizeof(TransferBatch)
                : SizeClassMap::getSizeByClassId(ClassId);
   }

   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }

   void initLinkerInitialized(s32 ReleaseToOsInterval) {
     if (SCUDO_FUCHSIA)
       reportError("SizeClassAllocator32 is not supported on Fuchsia");

     PossibleRegions.initLinkerInitialized();
     MinRegionIndex = NumRegions; // MaxRegionIndex is already initialized to 0.

     u32 Seed;
     if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))))
       Seed =
           static_cast<u32>(getMonotonicTime() ^
                            (reinterpret_cast<uptr>(SizeClassInfoArray) >> 6));
     const uptr PageSize = getPageSizeCached();
     for (uptr I = 0; I < NumClasses; I++) {
       SizeClassInfo *Sci = getSizeClassInfo(I);
       Sci->RandState = getRandomU32(&Seed);
       // See comment in the 64-bit primary about releasing smaller size classes.
       Sci->CanRelease = (ReleaseToOsInterval >= 0) &&
                         (I != SizeClassMap::BatchClassId) &&
                         (getSizeByClassId(I) >= (PageSize / 32));
     }
     ReleaseToOsIntervalMs = ReleaseToOsInterval;
   }
   void init(s32 ReleaseToOsInterval) {
     memset(this, 0, sizeof(*this));
     initLinkerInitialized(ReleaseToOsInterval);
   }

   void unmapTestOnly() {
     while (NumberOfStashedRegions > 0)
       unmap(reinterpret_cast<void *>(RegionsStash[--NumberOfStashedRegions]),
             RegionSize);
     // TODO(kostyak): unmap the TransferBatch regions as well.
     for (uptr I = 0; I < NumRegions; I++)
       if (PossibleRegions[I])
         unmap(reinterpret_cast<void *>(I * RegionSize), RegionSize);
     PossibleRegions.unmapTestOnly();
   }

   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
     ScopedLock L(Sci->Mutex);
     TransferBatch *B = Sci->FreeList.front();
     if (B) {
       Sci->FreeList.pop_front();
     } else {
       B = populateFreeList(C, ClassId, Sci);
       if (UNLIKELY(!B))
         return nullptr;
     }
     DCHECK_GT(B->getCount(), 0);
     Sci->Stats.PoppedBlocks += B->getCount();
     return B;
   }

   void pushBatch(uptr ClassId, TransferBatch *B) {
     DCHECK_LT(ClassId, NumClasses);
     DCHECK_GT(B->getCount(), 0);
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
     ScopedLock L(Sci->Mutex);
     Sci->FreeList.push_front(B);
     Sci->Stats.PushedBlocks += B->getCount();
     if (Sci->CanRelease)
       releaseToOSMaybe(Sci, ClassId);
   }

   void disable() {
     for (uptr I = 0; I < NumClasses; I++)
       getSizeClassInfo(I)->Mutex.lock();
   }

   void enable() {
     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--)
       getSizeClassInfo(static_cast<uptr>(I))->Mutex.unlock();
   }

   template <typename F> void iterateOverBlocks(F Callback) {
     for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++)
       if (PossibleRegions[I]) {
         const uptr BlockSize = getSizeByClassId(PossibleRegions[I]);
         const uptr From = I * RegionSize;
         const uptr To = From + (RegionSize / BlockSize) * BlockSize;
         for (uptr Block = From; Block < To; Block += BlockSize)
           Callback(Block);
       }
   }

   void getStats(ScopedString *Str) {
     // TODO(kostyak): get the RSS per region.
     uptr TotalMapped = 0;
     uptr PoppedBlocks = 0;
     uptr PushedBlocks = 0;
     for (uptr I = 0; I < NumClasses; I++) {
       SizeClassInfo *Sci = getSizeClassInfo(I);
       TotalMapped += Sci->AllocatedUser;
       PoppedBlocks += Sci->Stats.PoppedBlocks;
       PushedBlocks += Sci->Stats.PushedBlocks;
     }
     Str->append("Stats: SizeClassAllocator32: %zuM mapped in %zu allocations; "
                 "remains %zu\n",
                 TotalMapped >> 20, PoppedBlocks, PoppedBlocks - PushedBlocks);
     for (uptr I = 0; I < NumClasses; I++)
       getStats(Str, I, 0);
   }

   uptr releaseToOS() {
     uptr TotalReleasedBytes = 0;
     for (uptr I = 0; I < NumClasses; I++) {
       if (I == SizeClassMap::BatchClassId)
         continue;
       SizeClassInfo *Sci = getSizeClassInfo(I);
       ScopedLock L(Sci->Mutex);
       TotalReleasedBytes += releaseToOSMaybe(Sci, I, /*Force=*/true);
     }
     return TotalReleasedBytes;
   }

 private:
   static const uptr NumClasses = SizeClassMap::NumClasses;
   static const uptr RegionSize = 1UL << RegionSizeLog;
   static const uptr NumRegions = SCUDO_MMAP_RANGE_SIZE >> RegionSizeLog;
 #if SCUDO_WORDSIZE == 32U
   typedef FlatByteMap<NumRegions> ByteMap;
 #else
   typedef TwoLevelByteMap<(NumRegions >> 12), 1UL << 12> ByteMap;
 #endif

   struct SizeClassStats {
     uptr PoppedBlocks;
     uptr PushedBlocks;
   };

   struct ReleaseToOsInfo {
     uptr PushedBlocksAtLastRelease;
     uptr RangesReleased;
     uptr LastReleasedBytes;
     u64 LastReleaseAtNs;
   };

   struct ALIGNED(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
     HybridMutex Mutex;
     IntrusiveList<TransferBatch> FreeList;
     SizeClassStats Stats;
     bool CanRelease;
     u32 RandState;
     uptr AllocatedUser;
     ReleaseToOsInfo ReleaseInfo;
   };
   COMPILER_CHECK(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0);

   uptr computeRegionId(uptr Mem) {
     const uptr Id = Mem >> RegionSizeLog;
     CHECK_LT(Id, NumRegions);
     return Id;
   }

   uptr allocateRegionSlow() {
     uptr MapSize = 2 * RegionSize;
     const uptr MapBase = reinterpret_cast<uptr>(
         map(nullptr, MapSize, "scudo:primary", MAP_ALLOWNOMEM));
     if (UNLIKELY(!MapBase))
       return 0;
     const uptr MapEnd = MapBase + MapSize;
     uptr Region = MapBase;
     if (isAligned(Region, RegionSize)) {
       ScopedLock L(RegionsStashMutex);
       if (NumberOfStashedRegions < MaxStashedRegions)
         RegionsStash[NumberOfStashedRegions++] = MapBase + RegionSize;
       else
         MapSize = RegionSize;
     } else {
       Region = roundUpTo(MapBase, RegionSize);
       unmap(reinterpret_cast<void *>(MapBase), Region - MapBase);
       MapSize = RegionSize;
     }
     const uptr End = Region + MapSize;
     if (End != MapEnd)
       unmap(reinterpret_cast<void *>(End), MapEnd - End);
     return Region;
   }

   uptr allocateRegion(uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     uptr Region = 0;
     {
       ScopedLock L(RegionsStashMutex);
       if (NumberOfStashedRegions > 0)
         Region = RegionsStash[--NumberOfStashedRegions];
     }
     if (!Region)
       Region = allocateRegionSlow();
     if (LIKELY(Region)) {
       if (ClassId) {
         const uptr RegionIndex = computeRegionId(Region);
         if (RegionIndex < MinRegionIndex)
           MinRegionIndex = RegionIndex;
         if (RegionIndex > MaxRegionIndex)
           MaxRegionIndex = RegionIndex;
         PossibleRegions.set(RegionIndex, static_cast<u8>(ClassId));
       }
     }
     return Region;
   }

   SizeClassInfo *getSizeClassInfo(uptr ClassId) {
     DCHECK_LT(ClassId, NumClasses);
     return &SizeClassInfoArray[ClassId];
   }

   bool populateBatches(CacheT *C, SizeClassInfo *Sci, uptr ClassId,
                        TransferBatch **CurrentBatch, u32 MaxCount,
                        void **PointersArray, u32 Count) {
     if (ClassId != SizeClassMap::BatchClassId)
       shuffle(PointersArray, Count, &Sci->RandState);
     TransferBatch *B = *CurrentBatch;
     for (uptr I = 0; I < Count; I++) {
       if (B && B->getCount() == MaxCount) {
         Sci->FreeList.push_back(B);
         B = nullptr;
       }
       if (!B) {
         B = C->createBatch(ClassId, PointersArray[I]);
         if (UNLIKELY(!B))
           return false;
         B->clear();
       }
       B->add(PointersArray[I]);
     }
     *CurrentBatch = B;
     return true;
   }

   NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
                                            SizeClassInfo *Sci) {
     const uptr Region = allocateRegion(ClassId);
     if (UNLIKELY(!Region))
       return nullptr;
     C->getStats().add(StatMapped, RegionSize);
     const uptr Size = getSizeByClassId(ClassId);
     const u32 MaxCount = TransferBatch::getMaxCached(Size);
     DCHECK_GT(MaxCount, 0);
     const uptr NumberOfBlocks = RegionSize / Size;
     DCHECK_GT(NumberOfBlocks, 0);
     TransferBatch *B = nullptr;
     constexpr uptr ShuffleArraySize = 48;
     void *ShuffleArray[ShuffleArraySize];
     u32 Count = 0;
     const uptr AllocatedUser = NumberOfBlocks * Size;
     for (uptr I = Region; I < Region + AllocatedUser; I += Size) {
       ShuffleArray[Count++] = reinterpret_cast<void *>(I);
       if (Count == ShuffleArraySize) {
         if (UNLIKELY(!populateBatches(C, Sci, ClassId, &B, MaxCount,
                                       ShuffleArray, Count)))
           return nullptr;
         Count = 0;
       }
     }
     if (Count) {
       if (UNLIKELY(!populateBatches(C, Sci, ClassId, &B, MaxCount, ShuffleArray,
                                     Count)))
         return nullptr;
     }
     DCHECK(B);
     DCHECK_GT(B->getCount(), 0);

     C->getStats().add(StatFree, AllocatedUser);
     Sci->AllocatedUser += AllocatedUser;
     if (Sci->CanRelease)
       Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return B;
   }

   void getStats(ScopedString *Str, uptr ClassId, uptr Rss) {
     SizeClassInfo *Sci = getSizeClassInfo(ClassId);
     if (Sci->AllocatedUser == 0)
       return;
     const uptr InUse = Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks;
     const uptr AvailableChunks = Sci->AllocatedUser / getSizeByClassId(ClassId);
     Str->append("  %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
                 "inuse: %6zu avail: %6zu rss: %6zuK\n",
                 ClassId, getSizeByClassId(ClassId), Sci->AllocatedUser >> 10,
                 Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks, InUse,
                 AvailableChunks, Rss >> 10);
   }

   NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
                                  bool Force = false) {
     const uptr BlockSize = getSizeByClassId(ClassId);
     const uptr PageSize = getPageSizeCached();

     CHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
     const uptr BytesInFreeList =
         Sci->AllocatedUser -
         (Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks) * BlockSize;
     if (BytesInFreeList < PageSize)
       return 0; // No chance to release anything.
     if ((Sci->Stats.PushedBlocks - Sci->ReleaseInfo.PushedBlocksAtLastRelease) *
             BlockSize <
         PageSize) {
       return 0; // Nothing new to release.
     }

     if (!Force) {
       const s32 IntervalMs = ReleaseToOsIntervalMs;
       if (IntervalMs < 0)
         return 0;
       if (Sci->ReleaseInfo.LastReleaseAtNs +
               static_cast<uptr>(IntervalMs) * 1000000ULL >
           getMonotonicTime()) {
         return 0; // Memory was returned recently.
       }
     }

     // TODO(kostyak): currently not ideal as we loop over all regions and
     // iterate multiple times over the same freelist if a ClassId spans multiple
     // regions. But it will have to do for now.
     uptr TotalReleasedBytes = 0;
     for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
       if (PossibleRegions[I] == ClassId) {
         ReleaseRecorder Recorder(I * RegionSize);
         releaseFreeMemoryToOS(&Sci->FreeList, I * RegionSize,
                               RegionSize / PageSize, BlockSize, &Recorder);
         if (Recorder.getReleasedRangesCount() > 0) {
           Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
           Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
           Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
           TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
         }
       }
     }
     Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
     return TotalReleasedBytes;
   }

   SizeClassInfo SizeClassInfoArray[NumClasses];

   ByteMap PossibleRegions;
   // Keep track of the lowest & highest regions allocated to avoid looping
   // through the whole NumRegions.
   uptr MinRegionIndex;
   uptr MaxRegionIndex;
   s32 ReleaseToOsIntervalMs;
   // Unless several threads request regions simultaneously from different size
   // classes, the stash rarely contains more than 1 entry.
   static constexpr uptr MaxStashedRegions = 4;
   HybridMutex RegionsStashMutex;
   uptr NumberOfStashedRegions;
   uptr RegionsStash[MaxStashedRegions];
 };

 } // namespace scudo

 #endif // SCUDO_PRIMARY32_H_
	//===-- 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
	//
	//===----------------------------------------------------------------------===//

	#ifndef SCUDO_PRIMARY32_H_
	#define SCUDO_PRIMARY32_H_

	#include "bytemap.h"
	#include "common.h"
	#include "list.h"
	#include "local_cache.h"
	#include "release.h"
	#include "report.h"
	#include "stats.h"
	#include "string_utils.h"

	namespace scudo {

	// SizeClassAllocator32 is an allocator for 32 or 64-bit address space.
	//
	// It maps Regions of 2^RegionSizeLog bytes aligned on a 2^RegionSizeLog bytes
	// boundary, and keeps a bytemap of the mappable address space to track the size
	// class they are associated with.
	//
	// Mapped regions are split into equally sized Blocks according to the size
	// class they belong to, and the associated pointers are shuffled to prevent any
	// predictable address pattern (the predictability increases with the block
	// size).
	//
	// Regions for size class 0 are special and used to hold TransferBatches, which
	// allow to transfer arrays of pointers from the global size class freelist to
	// the thread specific freelist for said class, and back.
	//
	// Memory used by this allocator is never unmapped but can be partially
	// reclaimed if the platform allows for it.

	template <class SizeClassMapT, uptr RegionSizeLog> class SizeClassAllocator32 {
	public:
	typedef SizeClassMapT SizeClassMap;
	// Regions should be large enough to hold the largest Block.
	COMPILER_CHECK((1UL << RegionSizeLog) >= SizeClassMap::MaxSize);
	typedef SizeClassAllocator32<SizeClassMapT, RegionSizeLog> ThisT;
	typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
	typedef typename CacheT::TransferBatch TransferBatch;

	static uptr getSizeByClassId(uptr ClassId) {
	return (ClassId == SizeClassMap::BatchClassId)
	? sizeof(TransferBatch)
	: SizeClassMap::getSizeByClassId(ClassId);
	}

	static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }

	void initLinkerInitialized(s32 ReleaseToOsInterval) {
	if (SCUDO_FUCHSIA)
	reportError("SizeClassAllocator32 is not supported on Fuchsia");

	PossibleRegions.initLinkerInitialized();
	MinRegionIndex = NumRegions; // MaxRegionIndex is already initialized to 0.

	u32 Seed;
	if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed))))
	Seed =
	static_cast<u32>(getMonotonicTime() ^
	(reinterpret_cast<uptr>(SizeClassInfoArray) >> 6));
	const uptr PageSize = getPageSizeCached();
	for (uptr I = 0; I < NumClasses; I++) {
	SizeClassInfo *Sci = getSizeClassInfo(I);
	Sci->RandState = getRandomU32(&Seed);
	// See comment in the 64-bit primary about releasing smaller size classes.
	Sci->CanRelease = (ReleaseToOsInterval >= 0) &&
	(I != SizeClassMap::BatchClassId) &&
	(getSizeByClassId(I) >= (PageSize / 32));
	}
	ReleaseToOsIntervalMs = ReleaseToOsInterval;
	}
	void init(s32 ReleaseToOsInterval) {
	memset(this, 0, sizeof(*this));
	initLinkerInitialized(ReleaseToOsInterval);
	}

	void unmapTestOnly() {
	while (NumberOfStashedRegions > 0)
	unmap(reinterpret_cast<void *>(RegionsStash[--NumberOfStashedRegions]),
	RegionSize);
	// TODO(kostyak): unmap the TransferBatch regions as well.
	for (uptr I = 0; I < NumRegions; I++)
	if (PossibleRegions[I])
	unmap(reinterpret_cast<void >(I RegionSize), RegionSize);
	PossibleRegions.unmapTestOnly();
	}

	TransferBatch popBatch(CacheT C, uptr ClassId) {
	DCHECK_LT(ClassId, NumClasses);
	SizeClassInfo *Sci = getSizeClassInfo(ClassId);
	ScopedLock L(Sci->Mutex);
	TransferBatch *B = Sci->FreeList.front();
	if (B) {
	Sci->FreeList.pop_front();
	} else {
	B = populateFreeList(C, ClassId, Sci);
	if (UNLIKELY(!B))
	return nullptr;
	}
	DCHECK_GT(B->getCount(), 0);
	Sci->Stats.PoppedBlocks += B->getCount();
	return B;
	}

	void pushBatch(uptr ClassId, TransferBatch *B) {
	DCHECK_LT(ClassId, NumClasses);
	DCHECK_GT(B->getCount(), 0);
	SizeClassInfo *Sci = getSizeClassInfo(ClassId);
	ScopedLock L(Sci->Mutex);
	Sci->FreeList.push_front(B);
	Sci->Stats.PushedBlocks += B->getCount();
	if (Sci->CanRelease)
	releaseToOSMaybe(Sci, ClassId);
	}

	void disable() {
	for (uptr I = 0; I < NumClasses; I++)
	getSizeClassInfo(I)->Mutex.lock();
	}

	void enable() {
	for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--)
	getSizeClassInfo(static_cast<uptr>(I))->Mutex.unlock();
	}

	template <typename F> void iterateOverBlocks(F Callback) {
	for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++)
	if (PossibleRegions[I]) {
	const uptr BlockSize = getSizeByClassId(PossibleRegions[I]);
	const uptr From = I * RegionSize;
	const uptr To = From + (RegionSize / BlockSize) * BlockSize;
	for (uptr Block = From; Block < To; Block += BlockSize)
	Callback(Block);
	}
	}

	void getStats(ScopedString *Str) {
	// TODO(kostyak): get the RSS per region.
	uptr TotalMapped = 0;
	uptr PoppedBlocks = 0;
	uptr PushedBlocks = 0;
	for (uptr I = 0; I < NumClasses; I++) {
	SizeClassInfo *Sci = getSizeClassInfo(I);
	TotalMapped += Sci->AllocatedUser;
	PoppedBlocks += Sci->Stats.PoppedBlocks;
	PushedBlocks += Sci->Stats.PushedBlocks;
	}
	Str->append("Stats: SizeClassAllocator32: %zuM mapped in %zu allocations; "
	"remains %zu\n",
	TotalMapped >> 20, PoppedBlocks, PoppedBlocks - PushedBlocks);
	for (uptr I = 0; I < NumClasses; I++)
	getStats(Str, I, 0);
	}

	uptr releaseToOS() {
	uptr TotalReleasedBytes = 0;
	for (uptr I = 0; I < NumClasses; I++) {
	if (I == SizeClassMap::BatchClassId)
	continue;
	SizeClassInfo *Sci = getSizeClassInfo(I);
	ScopedLock L(Sci->Mutex);
	TotalReleasedBytes += releaseToOSMaybe(Sci, I, /Force=/true);
	}
	return TotalReleasedBytes;
	}

	private:
	static const uptr NumClasses = SizeClassMap::NumClasses;
	static const uptr RegionSize = 1UL << RegionSizeLog;
	static const uptr NumRegions = SCUDO_MMAP_RANGE_SIZE >> RegionSizeLog;
	#if SCUDO_WORDSIZE == 32U
	typedef FlatByteMap<NumRegions> ByteMap;
	#else
	typedef TwoLevelByteMap<(NumRegions >> 12), 1UL << 12> ByteMap;
	#endif

	struct SizeClassStats {
	uptr PoppedBlocks;
	uptr PushedBlocks;
	};

	struct ReleaseToOsInfo {
	uptr PushedBlocksAtLastRelease;
	uptr RangesReleased;
	uptr LastReleasedBytes;
	u64 LastReleaseAtNs;
	};

	struct ALIGNED(SCUDO_CACHE_LINE_SIZE) SizeClassInfo {
	HybridMutex Mutex;
	IntrusiveList<TransferBatch> FreeList;
	SizeClassStats Stats;
	bool CanRelease;
	u32 RandState;
	uptr AllocatedUser;
	ReleaseToOsInfo ReleaseInfo;
	};
	COMPILER_CHECK(sizeof(SizeClassInfo) % SCUDO_CACHE_LINE_SIZE == 0);

	uptr computeRegionId(uptr Mem) {
	const uptr Id = Mem >> RegionSizeLog;
	CHECK_LT(Id, NumRegions);
	return Id;
	}

	uptr allocateRegionSlow() {
	uptr MapSize = 2 * RegionSize;
	const uptr MapBase = reinterpret_cast<uptr>(
	map(nullptr, MapSize, "scudo:primary", MAP_ALLOWNOMEM));
	if (UNLIKELY(!MapBase))
	return 0;
	const uptr MapEnd = MapBase + MapSize;
	uptr Region = MapBase;
	if (isAligned(Region, RegionSize)) {
	ScopedLock L(RegionsStashMutex);
	if (NumberOfStashedRegions < MaxStashedRegions)
	RegionsStash[NumberOfStashedRegions++] = MapBase + RegionSize;
	else
	MapSize = RegionSize;
	} else {
	Region = roundUpTo(MapBase, RegionSize);
	unmap(reinterpret_cast<void *>(MapBase), Region - MapBase);
	MapSize = RegionSize;
	}
	const uptr End = Region + MapSize;
	if (End != MapEnd)
	unmap(reinterpret_cast<void *>(End), MapEnd - End);
	return Region;
	}

	uptr allocateRegion(uptr ClassId) {
	DCHECK_LT(ClassId, NumClasses);
	uptr Region = 0;
	{
	ScopedLock L(RegionsStashMutex);
	if (NumberOfStashedRegions > 0)
	Region = RegionsStash[--NumberOfStashedRegions];
	}
	if (!Region)
	Region = allocateRegionSlow();
	if (LIKELY(Region)) {
	if (ClassId) {
	const uptr RegionIndex = computeRegionId(Region);
	if (RegionIndex < MinRegionIndex)
	MinRegionIndex = RegionIndex;
	if (RegionIndex > MaxRegionIndex)
	MaxRegionIndex = RegionIndex;
	PossibleRegions.set(RegionIndex, static_cast<u8>(ClassId));
	}
	}
	return Region;
	}

	SizeClassInfo *getSizeClassInfo(uptr ClassId) {
	DCHECK_LT(ClassId, NumClasses);
	return &SizeClassInfoArray[ClassId];
	}

	bool populateBatches(CacheT C, SizeClassInfo Sci, uptr ClassId,
	TransferBatch **CurrentBatch, u32 MaxCount,
	void **PointersArray, u32 Count) {
	if (ClassId != SizeClassMap::BatchClassId)
	shuffle(PointersArray, Count, &Sci->RandState);
	TransferBatch B = CurrentBatch;
	for (uptr I = 0; I < Count; I++) {
	if (B && B->getCount() == MaxCount) {
	Sci->FreeList.push_back(B);
	B = nullptr;
	}
	if (!B) {
	B = C->createBatch(ClassId, PointersArray[I]);
	if (UNLIKELY(!B))
	return false;
	B->clear();
	}
	B->add(PointersArray[I]);
	}
	*CurrentBatch = B;
	return true;
	}

	NOINLINE TransferBatch populateFreeList(CacheT C, uptr ClassId,
	SizeClassInfo *Sci) {
	const uptr Region = allocateRegion(ClassId);
	if (UNLIKELY(!Region))
	return nullptr;
	C->getStats().add(StatMapped, RegionSize);
	const uptr Size = getSizeByClassId(ClassId);
	const u32 MaxCount = TransferBatch::getMaxCached(Size);
	DCHECK_GT(MaxCount, 0);
	const uptr NumberOfBlocks = RegionSize / Size;
	DCHECK_GT(NumberOfBlocks, 0);
	TransferBatch *B = nullptr;
	constexpr uptr ShuffleArraySize = 48;
	void *ShuffleArray[ShuffleArraySize];
	u32 Count = 0;
	const uptr AllocatedUser = NumberOfBlocks * Size;
	for (uptr I = Region; I < Region + AllocatedUser; I += Size) {
	ShuffleArray[Count++] = reinterpret_cast<void *>(I);
	if (Count == ShuffleArraySize) {
	if (UNLIKELY(!populateBatches(C, Sci, ClassId, &B, MaxCount,
	ShuffleArray, Count)))
	return nullptr;
	Count = 0;
	}
	}
	if (Count) {
	if (UNLIKELY(!populateBatches(C, Sci, ClassId, &B, MaxCount, ShuffleArray,
	Count)))
	return nullptr;
	}
	DCHECK(B);
	DCHECK_GT(B->getCount(), 0);

	C->getStats().add(StatFree, AllocatedUser);
	Sci->AllocatedUser += AllocatedUser;
	if (Sci->CanRelease)
	Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
	return B;
	}

	void getStats(ScopedString *Str, uptr ClassId, uptr Rss) {
	SizeClassInfo *Sci = getSizeClassInfo(ClassId);
	if (Sci->AllocatedUser == 0)
	return;
	const uptr InUse = Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks;
	const uptr AvailableChunks = Sci->AllocatedUser / getSizeByClassId(ClassId);
	Str->append(" %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
	"inuse: %6zu avail: %6zu rss: %6zuK\n",
	ClassId, getSizeByClassId(ClassId), Sci->AllocatedUser >> 10,
	Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks, InUse,
	AvailableChunks, Rss >> 10);
	}

	NOINLINE uptr releaseToOSMaybe(SizeClassInfo *Sci, uptr ClassId,
	bool Force = false) {
	const uptr BlockSize = getSizeByClassId(ClassId);
	const uptr PageSize = getPageSizeCached();

	CHECK_GE(Sci->Stats.PoppedBlocks, Sci->Stats.PushedBlocks);
	const uptr BytesInFreeList =
	Sci->AllocatedUser -
	(Sci->Stats.PoppedBlocks - Sci->Stats.PushedBlocks) * BlockSize;
	if (BytesInFreeList < PageSize)
	return 0; // No chance to release anything.
	if ((Sci->Stats.PushedBlocks - Sci->ReleaseInfo.PushedBlocksAtLastRelease) *
	BlockSize <
	PageSize) {
	return 0; // Nothing new to release.
	}

	if (!Force) {
	const s32 IntervalMs = ReleaseToOsIntervalMs;
	if (IntervalMs < 0)
	return 0;
	if (Sci->ReleaseInfo.LastReleaseAtNs +
	static_cast<uptr>(IntervalMs) * 1000000ULL >
	getMonotonicTime()) {
	return 0; // Memory was returned recently.
	}
	}

	// TODO(kostyak): currently not ideal as we loop over all regions and
	// iterate multiple times over the same freelist if a ClassId spans multiple
	// regions. But it will have to do for now.
	uptr TotalReleasedBytes = 0;
	for (uptr I = MinRegionIndex; I <= MaxRegionIndex; I++) {
	if (PossibleRegions[I] == ClassId) {
	ReleaseRecorder Recorder(I * RegionSize);
	releaseFreeMemoryToOS(&Sci->FreeList, I * RegionSize,
	RegionSize / PageSize, BlockSize, &Recorder);
	if (Recorder.getReleasedRangesCount() > 0) {
	Sci->ReleaseInfo.PushedBlocksAtLastRelease = Sci->Stats.PushedBlocks;
	Sci->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
	Sci->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
	TotalReleasedBytes += Sci->ReleaseInfo.LastReleasedBytes;
	}
	}
	}
	Sci->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
	return TotalReleasedBytes;
	}

	SizeClassInfo SizeClassInfoArray[NumClasses];

	ByteMap PossibleRegions;
	// Keep track of the lowest & highest regions allocated to avoid looping
	// through the whole NumRegions.
	uptr MinRegionIndex;
	uptr MaxRegionIndex;
	s32 ReleaseToOsIntervalMs;
	// Unless several threads request regions simultaneously from different size
	// classes, the stash rarely contains more than 1 entry.
	static constexpr uptr MaxStashedRegions = 4;
	HybridMutex RegionsStashMutex;
	uptr NumberOfStashedRegions;
	uptr RegionsStash[MaxStashedRegions];
	};

	} // namespace scudo

	#endif // SCUDO_PRIMARY32_H_