16a5c9aabSmrg //===-- sanitizer_allocator_primary64.h -------------------------*- C++ -*-===// 26a5c9aabSmrg // 3*490215a3Smrg // This file is distributed under the University of Illinois Open Source 4*490215a3Smrg // License. See LICENSE.TXT for details. 56a5c9aabSmrg // 66a5c9aabSmrg //===----------------------------------------------------------------------===// 76a5c9aabSmrg // 86a5c9aabSmrg // Part of the Sanitizer Allocator. 96a5c9aabSmrg // 106a5c9aabSmrg //===----------------------------------------------------------------------===// 116a5c9aabSmrg #ifndef SANITIZER_ALLOCATOR_H 126a5c9aabSmrg #error This file must be included inside sanitizer_allocator.h 136a5c9aabSmrg #endif 146a5c9aabSmrg 156a5c9aabSmrg template<class SizeClassAllocator> struct SizeClassAllocator64LocalCache; 166a5c9aabSmrg 176a5c9aabSmrg // SizeClassAllocator64 -- allocator for 64-bit address space. 186a5c9aabSmrg // The template parameter Params is a class containing the actual parameters. 196a5c9aabSmrg // 206a5c9aabSmrg // Space: a portion of address space of kSpaceSize bytes starting at SpaceBeg. 216a5c9aabSmrg // If kSpaceBeg is ~0 then SpaceBeg is chosen dynamically my mmap. 226a5c9aabSmrg // Otherwise SpaceBeg=kSpaceBeg (fixed address). 236a5c9aabSmrg // kSpaceSize is a power of two. 246a5c9aabSmrg // At the beginning the entire space is mprotect-ed, then small parts of it 256a5c9aabSmrg // are mapped on demand. 266a5c9aabSmrg // 276a5c9aabSmrg // Region: a part of Space dedicated to a single size class. 286a5c9aabSmrg // There are kNumClasses Regions of equal size. 296a5c9aabSmrg // 306a5c9aabSmrg // UserChunk: a piece of memory returned to user. 316a5c9aabSmrg // MetaChunk: kMetadataSize bytes of metadata associated with a UserChunk. 326a5c9aabSmrg 336a5c9aabSmrg // FreeArray is an array free-d chunks (stored as 4-byte offsets) 346a5c9aabSmrg // 356a5c9aabSmrg // A Region looks like this: 366a5c9aabSmrg // UserChunk1 ... UserChunkN <gap> MetaChunkN ... MetaChunk1 FreeArray 376a5c9aabSmrg 386a5c9aabSmrg struct SizeClassAllocator64FlagMasks { // Bit masks. 396a5c9aabSmrg enum { 406a5c9aabSmrg kRandomShuffleChunks = 1, 416a5c9aabSmrg }; 426a5c9aabSmrg }; 436a5c9aabSmrg 446a5c9aabSmrg template <class Params> 456a5c9aabSmrg class SizeClassAllocator64 { 466a5c9aabSmrg public: 476a5c9aabSmrg static const uptr kSpaceBeg = Params::kSpaceBeg; 486a5c9aabSmrg static const uptr kSpaceSize = Params::kSpaceSize; 496a5c9aabSmrg static const uptr kMetadataSize = Params::kMetadataSize; 506a5c9aabSmrg typedef typename Params::SizeClassMap SizeClassMap; 516a5c9aabSmrg typedef typename Params::MapUnmapCallback MapUnmapCallback; 526a5c9aabSmrg 536a5c9aabSmrg static const bool kRandomShuffleChunks = 546a5c9aabSmrg Params::kFlags & SizeClassAllocator64FlagMasks::kRandomShuffleChunks; 556a5c9aabSmrg 566a5c9aabSmrg typedef SizeClassAllocator64<Params> ThisT; 576a5c9aabSmrg typedef SizeClassAllocator64LocalCache<ThisT> AllocatorCache; 586a5c9aabSmrg 596a5c9aabSmrg // When we know the size class (the region base) we can represent a pointer 606a5c9aabSmrg // as a 4-byte integer (offset from the region start shifted right by 4). 616a5c9aabSmrg typedef u32 CompactPtrT; 626a5c9aabSmrg static const uptr kCompactPtrScale = 4; PointerToCompactPtr(uptr base,uptr ptr)63e56e5d0aSmrg CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) const { 646a5c9aabSmrg return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale); 656a5c9aabSmrg } CompactPtrToPointer(uptr base,CompactPtrT ptr32)66e56e5d0aSmrg uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) const { 676a5c9aabSmrg return base + (static_cast<uptr>(ptr32) << kCompactPtrScale); 686a5c9aabSmrg } 696a5c9aabSmrg Init(s32 release_to_os_interval_ms)70e56e5d0aSmrg void Init(s32 release_to_os_interval_ms) { 716a5c9aabSmrg uptr TotalSpaceSize = kSpaceSize + AdditionalSize(); 726a5c9aabSmrg if (kUsingConstantSpaceBeg) { 73ff135a7aSmrg CHECK_EQ(kSpaceBeg, address_range.Init(TotalSpaceSize, 74ff135a7aSmrg PrimaryAllocatorName, kSpaceBeg)); 756a5c9aabSmrg } else { 76ff135a7aSmrg NonConstSpaceBeg = address_range.Init(TotalSpaceSize, 77ff135a7aSmrg PrimaryAllocatorName); 786a5c9aabSmrg CHECK_NE(NonConstSpaceBeg, ~(uptr)0); 796a5c9aabSmrg } 80e56e5d0aSmrg SetReleaseToOSIntervalMs(release_to_os_interval_ms); 81*490215a3Smrg MapWithCallbackOrDie(SpaceEnd(), AdditionalSize()); 82ff135a7aSmrg // Check that the RegionInfo array is aligned on the CacheLine size. 83ff135a7aSmrg DCHECK_EQ(SpaceEnd() % kCacheLineSize, 0); 846a5c9aabSmrg } 856a5c9aabSmrg ReleaseToOSIntervalMs()86e56e5d0aSmrg s32 ReleaseToOSIntervalMs() const { 87e56e5d0aSmrg return atomic_load(&release_to_os_interval_ms_, memory_order_relaxed); 886a5c9aabSmrg } 896a5c9aabSmrg SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms)90e56e5d0aSmrg void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) { 91e56e5d0aSmrg atomic_store(&release_to_os_interval_ms_, release_to_os_interval_ms, 92e56e5d0aSmrg memory_order_relaxed); 936a5c9aabSmrg } 946a5c9aabSmrg ForceReleaseToOS()95ff135a7aSmrg void ForceReleaseToOS() { 96ff135a7aSmrg for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 97ff135a7aSmrg BlockingMutexLock l(&GetRegionInfo(class_id)->mutex); 98ff135a7aSmrg MaybeReleaseToOS(class_id, true /*force*/); 99ff135a7aSmrg } 100ff135a7aSmrg } 101ff135a7aSmrg CanAllocate(uptr size,uptr alignment)1026a5c9aabSmrg static bool CanAllocate(uptr size, uptr alignment) { 1036a5c9aabSmrg return size <= SizeClassMap::kMaxSize && 1046a5c9aabSmrg alignment <= SizeClassMap::kMaxSize; 1056a5c9aabSmrg } 1066a5c9aabSmrg ReturnToAllocator(AllocatorStats * stat,uptr class_id,const CompactPtrT * chunks,uptr n_chunks)1076a5c9aabSmrg NOINLINE void ReturnToAllocator(AllocatorStats *stat, uptr class_id, 1086a5c9aabSmrg const CompactPtrT *chunks, uptr n_chunks) { 1096a5c9aabSmrg RegionInfo *region = GetRegionInfo(class_id); 1106a5c9aabSmrg uptr region_beg = GetRegionBeginBySizeClass(class_id); 1116a5c9aabSmrg CompactPtrT *free_array = GetFreeArray(region_beg); 1126a5c9aabSmrg 1136a5c9aabSmrg BlockingMutexLock l(®ion->mutex); 1146a5c9aabSmrg uptr old_num_chunks = region->num_freed_chunks; 1156a5c9aabSmrg uptr new_num_freed_chunks = old_num_chunks + n_chunks; 116e56e5d0aSmrg // Failure to allocate free array space while releasing memory is non 117e56e5d0aSmrg // recoverable. 118e56e5d0aSmrg if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, 119ff135a7aSmrg new_num_freed_chunks))) { 120ff135a7aSmrg Report("FATAL: Internal error: %s's allocator exhausted the free list " 121ff135a7aSmrg "space for size class %zd (%zd bytes).\n", SanitizerToolName, 122ff135a7aSmrg class_id, ClassIdToSize(class_id)); 123ff135a7aSmrg Die(); 124ff135a7aSmrg } 1256a5c9aabSmrg for (uptr i = 0; i < n_chunks; i++) 1266a5c9aabSmrg free_array[old_num_chunks + i] = chunks[i]; 1276a5c9aabSmrg region->num_freed_chunks = new_num_freed_chunks; 128e56e5d0aSmrg region->stats.n_freed += n_chunks; 129e56e5d0aSmrg 130ff135a7aSmrg MaybeReleaseToOS(class_id, false /*force*/); 1316a5c9aabSmrg } 1326a5c9aabSmrg GetFromAllocator(AllocatorStats * stat,uptr class_id,CompactPtrT * chunks,uptr n_chunks)133e56e5d0aSmrg NOINLINE bool GetFromAllocator(AllocatorStats *stat, uptr class_id, 1346a5c9aabSmrg CompactPtrT *chunks, uptr n_chunks) { 1356a5c9aabSmrg RegionInfo *region = GetRegionInfo(class_id); 1366a5c9aabSmrg uptr region_beg = GetRegionBeginBySizeClass(class_id); 1376a5c9aabSmrg CompactPtrT *free_array = GetFreeArray(region_beg); 1386a5c9aabSmrg 1396a5c9aabSmrg BlockingMutexLock l(®ion->mutex); 1406a5c9aabSmrg if (UNLIKELY(region->num_freed_chunks < n_chunks)) { 141e56e5d0aSmrg if (UNLIKELY(!PopulateFreeArray(stat, class_id, region, 142e56e5d0aSmrg n_chunks - region->num_freed_chunks))) 143e56e5d0aSmrg return false; 1446a5c9aabSmrg CHECK_GE(region->num_freed_chunks, n_chunks); 1456a5c9aabSmrg } 1466a5c9aabSmrg region->num_freed_chunks -= n_chunks; 1476a5c9aabSmrg uptr base_idx = region->num_freed_chunks; 1486a5c9aabSmrg for (uptr i = 0; i < n_chunks; i++) 1496a5c9aabSmrg chunks[i] = free_array[base_idx + i]; 150e56e5d0aSmrg region->stats.n_allocated += n_chunks; 151e56e5d0aSmrg return true; 1526a5c9aabSmrg } 1536a5c9aabSmrg PointerIsMine(const void * p)154*490215a3Smrg bool PointerIsMine(const void *p) { 1556a5c9aabSmrg uptr P = reinterpret_cast<uptr>(p); 1566a5c9aabSmrg if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) 1576a5c9aabSmrg return P / kSpaceSize == kSpaceBeg / kSpaceSize; 1586a5c9aabSmrg return P >= SpaceBeg() && P < SpaceEnd(); 1596a5c9aabSmrg } 1606a5c9aabSmrg GetRegionBegin(const void * p)1616a5c9aabSmrg uptr GetRegionBegin(const void *p) { 1626a5c9aabSmrg if (kUsingConstantSpaceBeg) 1636a5c9aabSmrg return reinterpret_cast<uptr>(p) & ~(kRegionSize - 1); 1646a5c9aabSmrg uptr space_beg = SpaceBeg(); 1656a5c9aabSmrg return ((reinterpret_cast<uptr>(p) - space_beg) & ~(kRegionSize - 1)) + 1666a5c9aabSmrg space_beg; 1676a5c9aabSmrg } 1686a5c9aabSmrg GetRegionBeginBySizeClass(uptr class_id)169e56e5d0aSmrg uptr GetRegionBeginBySizeClass(uptr class_id) const { 1706a5c9aabSmrg return SpaceBeg() + kRegionSize * class_id; 1716a5c9aabSmrg } 1726a5c9aabSmrg GetSizeClass(const void * p)1736a5c9aabSmrg uptr GetSizeClass(const void *p) { 1746a5c9aabSmrg if (kUsingConstantSpaceBeg && (kSpaceBeg % kSpaceSize) == 0) 1756a5c9aabSmrg return ((reinterpret_cast<uptr>(p)) / kRegionSize) % kNumClassesRounded; 1766a5c9aabSmrg return ((reinterpret_cast<uptr>(p) - SpaceBeg()) / kRegionSize) % 1776a5c9aabSmrg kNumClassesRounded; 1786a5c9aabSmrg } 1796a5c9aabSmrg GetBlockBegin(const void * p)1806a5c9aabSmrg void *GetBlockBegin(const void *p) { 1816a5c9aabSmrg uptr class_id = GetSizeClass(p); 1826a5c9aabSmrg uptr size = ClassIdToSize(class_id); 1836a5c9aabSmrg if (!size) return nullptr; 1846a5c9aabSmrg uptr chunk_idx = GetChunkIdx((uptr)p, size); 1856a5c9aabSmrg uptr reg_beg = GetRegionBegin(p); 1866a5c9aabSmrg uptr beg = chunk_idx * size; 1876a5c9aabSmrg uptr next_beg = beg + size; 1886a5c9aabSmrg if (class_id >= kNumClasses) return nullptr; 189*490215a3Smrg RegionInfo *region = GetRegionInfo(class_id); 1906a5c9aabSmrg if (region->mapped_user >= next_beg) 1916a5c9aabSmrg return reinterpret_cast<void*>(reg_beg + beg); 1926a5c9aabSmrg return nullptr; 1936a5c9aabSmrg } 1946a5c9aabSmrg GetActuallyAllocatedSize(void * p)1956a5c9aabSmrg uptr GetActuallyAllocatedSize(void *p) { 1966a5c9aabSmrg CHECK(PointerIsMine(p)); 1976a5c9aabSmrg return ClassIdToSize(GetSizeClass(p)); 1986a5c9aabSmrg } 1996a5c9aabSmrg ClassID(uptr size)200*490215a3Smrg uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); } 2016a5c9aabSmrg GetMetaData(const void * p)2026a5c9aabSmrg void *GetMetaData(const void *p) { 2036a5c9aabSmrg uptr class_id = GetSizeClass(p); 2046a5c9aabSmrg uptr size = ClassIdToSize(class_id); 2056a5c9aabSmrg uptr chunk_idx = GetChunkIdx(reinterpret_cast<uptr>(p), size); 2066a5c9aabSmrg uptr region_beg = GetRegionBeginBySizeClass(class_id); 2076a5c9aabSmrg return reinterpret_cast<void *>(GetMetadataEnd(region_beg) - 2086a5c9aabSmrg (1 + chunk_idx) * kMetadataSize); 2096a5c9aabSmrg } 2106a5c9aabSmrg TotalMemoryUsed()2116a5c9aabSmrg uptr TotalMemoryUsed() { 2126a5c9aabSmrg uptr res = 0; 2136a5c9aabSmrg for (uptr i = 0; i < kNumClasses; i++) 2146a5c9aabSmrg res += GetRegionInfo(i)->allocated_user; 2156a5c9aabSmrg return res; 2166a5c9aabSmrg } 2176a5c9aabSmrg 2186a5c9aabSmrg // Test-only. TestOnlyUnmap()2196a5c9aabSmrg void TestOnlyUnmap() { 220e56e5d0aSmrg UnmapWithCallbackOrDie(SpaceBeg(), kSpaceSize + AdditionalSize()); 2216a5c9aabSmrg } 2226a5c9aabSmrg FillMemoryProfile(uptr start,uptr rss,bool file,uptr * stats,uptr stats_size)2236a5c9aabSmrg static void FillMemoryProfile(uptr start, uptr rss, bool file, uptr *stats, 2246a5c9aabSmrg uptr stats_size) { 2256a5c9aabSmrg for (uptr class_id = 0; class_id < stats_size; class_id++) 2266a5c9aabSmrg if (stats[class_id] == start) 2276a5c9aabSmrg stats[class_id] = rss; 2286a5c9aabSmrg } 2296a5c9aabSmrg PrintStats(uptr class_id,uptr rss)2306a5c9aabSmrg void PrintStats(uptr class_id, uptr rss) { 2316a5c9aabSmrg RegionInfo *region = GetRegionInfo(class_id); 2326a5c9aabSmrg if (region->mapped_user == 0) return; 233e56e5d0aSmrg uptr in_use = region->stats.n_allocated - region->stats.n_freed; 2346a5c9aabSmrg uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id); 2356a5c9aabSmrg Printf( 236e56e5d0aSmrg "%s %02zd (%6zd): mapped: %6zdK allocs: %7zd frees: %7zd inuse: %6zd " 237e56e5d0aSmrg "num_freed_chunks %7zd avail: %6zd rss: %6zdK releases: %6zd " 238e56e5d0aSmrg "last released: %6zdK region: 0x%zx\n", 239e56e5d0aSmrg region->exhausted ? "F" : " ", class_id, ClassIdToSize(class_id), 240e56e5d0aSmrg region->mapped_user >> 10, region->stats.n_allocated, 241e56e5d0aSmrg region->stats.n_freed, in_use, region->num_freed_chunks, avail_chunks, 242e56e5d0aSmrg rss >> 10, region->rtoi.num_releases, 243e56e5d0aSmrg region->rtoi.last_released_bytes >> 10, 244e56e5d0aSmrg SpaceBeg() + kRegionSize * class_id); 2456a5c9aabSmrg } 2466a5c9aabSmrg PrintStats()2476a5c9aabSmrg void PrintStats() { 2486a5c9aabSmrg uptr rss_stats[kNumClasses]; 2496a5c9aabSmrg for (uptr class_id = 0; class_id < kNumClasses; class_id++) 2506a5c9aabSmrg rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id; 2516a5c9aabSmrg GetMemoryProfile(FillMemoryProfile, rss_stats, kNumClasses); 252ff135a7aSmrg 253ff135a7aSmrg uptr total_mapped = 0; 254ff135a7aSmrg uptr total_rss = 0; 255ff135a7aSmrg uptr n_allocated = 0; 256ff135a7aSmrg uptr n_freed = 0; 257ff135a7aSmrg for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 258ff135a7aSmrg RegionInfo *region = GetRegionInfo(class_id); 259ff135a7aSmrg if (region->mapped_user != 0) { 260ff135a7aSmrg total_mapped += region->mapped_user; 261ff135a7aSmrg total_rss += rss_stats[class_id]; 262ff135a7aSmrg } 263ff135a7aSmrg n_allocated += region->stats.n_allocated; 264ff135a7aSmrg n_freed += region->stats.n_freed; 265ff135a7aSmrg } 266ff135a7aSmrg 267ff135a7aSmrg Printf("Stats: SizeClassAllocator64: %zdM mapped (%zdM rss) in " 268ff135a7aSmrg "%zd allocations; remains %zd\n", total_mapped >> 20, 269ff135a7aSmrg total_rss >> 20, n_allocated, n_allocated - n_freed); 2706a5c9aabSmrg for (uptr class_id = 1; class_id < kNumClasses; class_id++) 2716a5c9aabSmrg PrintStats(class_id, rss_stats[class_id]); 2726a5c9aabSmrg } 2736a5c9aabSmrg 2746a5c9aabSmrg // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone 2756a5c9aabSmrg // introspection API. ForceLock()2766a5c9aabSmrg void ForceLock() { 2776a5c9aabSmrg for (uptr i = 0; i < kNumClasses; i++) { 2786a5c9aabSmrg GetRegionInfo(i)->mutex.Lock(); 2796a5c9aabSmrg } 2806a5c9aabSmrg } 2816a5c9aabSmrg ForceUnlock()2826a5c9aabSmrg void ForceUnlock() { 2836a5c9aabSmrg for (int i = (int)kNumClasses - 1; i >= 0; i--) { 2846a5c9aabSmrg GetRegionInfo(i)->mutex.Unlock(); 2856a5c9aabSmrg } 2866a5c9aabSmrg } 2876a5c9aabSmrg 2886a5c9aabSmrg // Iterate over all existing chunks. 2896a5c9aabSmrg // The allocator must be locked when calling this function. ForEachChunk(ForEachChunkCallback callback,void * arg)2906a5c9aabSmrg void ForEachChunk(ForEachChunkCallback callback, void *arg) { 2916a5c9aabSmrg for (uptr class_id = 1; class_id < kNumClasses; class_id++) { 2926a5c9aabSmrg RegionInfo *region = GetRegionInfo(class_id); 2936a5c9aabSmrg uptr chunk_size = ClassIdToSize(class_id); 2946a5c9aabSmrg uptr region_beg = SpaceBeg() + class_id * kRegionSize; 2956a5c9aabSmrg for (uptr chunk = region_beg; 296*490215a3Smrg chunk < region_beg + region->allocated_user; 2976a5c9aabSmrg chunk += chunk_size) { 2986a5c9aabSmrg // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk)); 2996a5c9aabSmrg callback(chunk, arg); 3006a5c9aabSmrg } 3016a5c9aabSmrg } 3026a5c9aabSmrg } 3036a5c9aabSmrg ClassIdToSize(uptr class_id)3046a5c9aabSmrg static uptr ClassIdToSize(uptr class_id) { 3056a5c9aabSmrg return SizeClassMap::Size(class_id); 3066a5c9aabSmrg } 3076a5c9aabSmrg AdditionalSize()3086a5c9aabSmrg static uptr AdditionalSize() { 3096a5c9aabSmrg return RoundUpTo(sizeof(RegionInfo) * kNumClassesRounded, 3106a5c9aabSmrg GetPageSizeCached()); 3116a5c9aabSmrg } 3126a5c9aabSmrg 3136a5c9aabSmrg typedef SizeClassMap SizeClassMapT; 3146a5c9aabSmrg static const uptr kNumClasses = SizeClassMap::kNumClasses; 3156a5c9aabSmrg static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded; 3166a5c9aabSmrg 317e56e5d0aSmrg // A packed array of counters. Each counter occupies 2^n bits, enough to store 318e56e5d0aSmrg // counter's max_value. Ctor will try to allocate the required buffer via 319e56e5d0aSmrg // mapper->MapPackedCounterArrayBuffer and the caller is expected to check 320e56e5d0aSmrg // whether the initialization was successful by checking IsAllocated() result. 321e56e5d0aSmrg // For the performance sake, none of the accessors check the validity of the 322e56e5d0aSmrg // arguments, it is assumed that index is always in [0, n) range and the value 323e56e5d0aSmrg // is not incremented past max_value. 324e56e5d0aSmrg template<class MemoryMapperT> 325e56e5d0aSmrg class PackedCounterArray { 326e56e5d0aSmrg public: PackedCounterArray(u64 num_counters,u64 max_value,MemoryMapperT * mapper)327e56e5d0aSmrg PackedCounterArray(u64 num_counters, u64 max_value, MemoryMapperT *mapper) 328e56e5d0aSmrg : n(num_counters), memory_mapper(mapper) { 329e56e5d0aSmrg CHECK_GT(num_counters, 0); 330e56e5d0aSmrg CHECK_GT(max_value, 0); 331e56e5d0aSmrg constexpr u64 kMaxCounterBits = sizeof(*buffer) * 8ULL; 332e56e5d0aSmrg // Rounding counter storage size up to the power of two allows for using 333e56e5d0aSmrg // bit shifts calculating particular counter's index and offset. 334e56e5d0aSmrg uptr counter_size_bits = 335e56e5d0aSmrg RoundUpToPowerOfTwo(MostSignificantSetBitIndex(max_value) + 1); 336e56e5d0aSmrg CHECK_LE(counter_size_bits, kMaxCounterBits); 337e56e5d0aSmrg counter_size_bits_log = Log2(counter_size_bits); 338e56e5d0aSmrg counter_mask = ~0ULL >> (kMaxCounterBits - counter_size_bits); 339e56e5d0aSmrg 340e56e5d0aSmrg uptr packing_ratio = kMaxCounterBits >> counter_size_bits_log; 341e56e5d0aSmrg CHECK_GT(packing_ratio, 0); 342e56e5d0aSmrg packing_ratio_log = Log2(packing_ratio); 343e56e5d0aSmrg bit_offset_mask = packing_ratio - 1; 344e56e5d0aSmrg 345e56e5d0aSmrg buffer_size = 346e56e5d0aSmrg (RoundUpTo(n, 1ULL << packing_ratio_log) >> packing_ratio_log) * 347e56e5d0aSmrg sizeof(*buffer); 348e56e5d0aSmrg buffer = reinterpret_cast<u64*>( 349e56e5d0aSmrg memory_mapper->MapPackedCounterArrayBuffer(buffer_size)); 350e56e5d0aSmrg } ~PackedCounterArray()351e56e5d0aSmrg ~PackedCounterArray() { 352e56e5d0aSmrg if (buffer) { 353e56e5d0aSmrg memory_mapper->UnmapPackedCounterArrayBuffer( 354e56e5d0aSmrg reinterpret_cast<uptr>(buffer), buffer_size); 355e56e5d0aSmrg } 356e56e5d0aSmrg } 357e56e5d0aSmrg IsAllocated()358e56e5d0aSmrg bool IsAllocated() const { 359e56e5d0aSmrg return !!buffer; 360e56e5d0aSmrg } 361e56e5d0aSmrg GetCount()362e56e5d0aSmrg u64 GetCount() const { 363e56e5d0aSmrg return n; 364e56e5d0aSmrg } 365e56e5d0aSmrg Get(uptr i)366e56e5d0aSmrg uptr Get(uptr i) const { 367e56e5d0aSmrg DCHECK_LT(i, n); 368e56e5d0aSmrg uptr index = i >> packing_ratio_log; 369e56e5d0aSmrg uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log; 370e56e5d0aSmrg return (buffer[index] >> bit_offset) & counter_mask; 371e56e5d0aSmrg } 372e56e5d0aSmrg Inc(uptr i)373e56e5d0aSmrg void Inc(uptr i) const { 374e56e5d0aSmrg DCHECK_LT(Get(i), counter_mask); 375e56e5d0aSmrg uptr index = i >> packing_ratio_log; 376e56e5d0aSmrg uptr bit_offset = (i & bit_offset_mask) << counter_size_bits_log; 377e56e5d0aSmrg buffer[index] += 1ULL << bit_offset; 378e56e5d0aSmrg } 379e56e5d0aSmrg IncRange(uptr from,uptr to)380e56e5d0aSmrg void IncRange(uptr from, uptr to) const { 381e56e5d0aSmrg DCHECK_LE(from, to); 382e56e5d0aSmrg for (uptr i = from; i <= to; i++) 383e56e5d0aSmrg Inc(i); 384e56e5d0aSmrg } 385e56e5d0aSmrg 3866a5c9aabSmrg private: 387e56e5d0aSmrg const u64 n; 388e56e5d0aSmrg u64 counter_size_bits_log; 389e56e5d0aSmrg u64 counter_mask; 390e56e5d0aSmrg u64 packing_ratio_log; 391e56e5d0aSmrg u64 bit_offset_mask; 392e56e5d0aSmrg 393e56e5d0aSmrg MemoryMapperT* const memory_mapper; 394e56e5d0aSmrg u64 buffer_size; 395e56e5d0aSmrg u64* buffer; 396e56e5d0aSmrg }; 397e56e5d0aSmrg 398e56e5d0aSmrg template<class MemoryMapperT> 399e56e5d0aSmrg class FreePagesRangeTracker { 400e56e5d0aSmrg public: FreePagesRangeTracker(MemoryMapperT * mapper)401e56e5d0aSmrg explicit FreePagesRangeTracker(MemoryMapperT* mapper) 402e56e5d0aSmrg : memory_mapper(mapper), 403e56e5d0aSmrg page_size_scaled_log(Log2(GetPageSizeCached() >> kCompactPtrScale)), 404e56e5d0aSmrg in_the_range(false), current_page(0), current_range_start_page(0) {} 405e56e5d0aSmrg NextPage(bool freed)406e56e5d0aSmrg void NextPage(bool freed) { 407e56e5d0aSmrg if (freed) { 408e56e5d0aSmrg if (!in_the_range) { 409e56e5d0aSmrg current_range_start_page = current_page; 410e56e5d0aSmrg in_the_range = true; 411e56e5d0aSmrg } 412e56e5d0aSmrg } else { 413e56e5d0aSmrg CloseOpenedRange(); 414e56e5d0aSmrg } 415e56e5d0aSmrg current_page++; 416e56e5d0aSmrg } 417e56e5d0aSmrg Done()418e56e5d0aSmrg void Done() { 419e56e5d0aSmrg CloseOpenedRange(); 420e56e5d0aSmrg } 421e56e5d0aSmrg 422e56e5d0aSmrg private: CloseOpenedRange()423e56e5d0aSmrg void CloseOpenedRange() { 424e56e5d0aSmrg if (in_the_range) { 425e56e5d0aSmrg memory_mapper->ReleasePageRangeToOS( 426e56e5d0aSmrg current_range_start_page << page_size_scaled_log, 427e56e5d0aSmrg current_page << page_size_scaled_log); 428e56e5d0aSmrg in_the_range = false; 429e56e5d0aSmrg } 430e56e5d0aSmrg } 431e56e5d0aSmrg 432e56e5d0aSmrg MemoryMapperT* const memory_mapper; 433e56e5d0aSmrg const uptr page_size_scaled_log; 434e56e5d0aSmrg bool in_the_range; 435e56e5d0aSmrg uptr current_page; 436e56e5d0aSmrg uptr current_range_start_page; 437e56e5d0aSmrg }; 438e56e5d0aSmrg 439e56e5d0aSmrg // Iterates over the free_array to identify memory pages containing freed 440e56e5d0aSmrg // chunks only and returns these pages back to OS. 441e56e5d0aSmrg // allocated_pages_count is the total number of pages allocated for the 442e56e5d0aSmrg // current bucket. 443e56e5d0aSmrg template<class MemoryMapperT> ReleaseFreeMemoryToOS(CompactPtrT * free_array,uptr free_array_count,uptr chunk_size,uptr allocated_pages_count,MemoryMapperT * memory_mapper)444e56e5d0aSmrg static void ReleaseFreeMemoryToOS(CompactPtrT *free_array, 445e56e5d0aSmrg uptr free_array_count, uptr chunk_size, 446e56e5d0aSmrg uptr allocated_pages_count, 447e56e5d0aSmrg MemoryMapperT *memory_mapper) { 448e56e5d0aSmrg const uptr page_size = GetPageSizeCached(); 449e56e5d0aSmrg 450e56e5d0aSmrg // Figure out the number of chunks per page and whether we can take a fast 451e56e5d0aSmrg // path (the number of chunks per page is the same for all pages). 452e56e5d0aSmrg uptr full_pages_chunk_count_max; 453e56e5d0aSmrg bool same_chunk_count_per_page; 454e56e5d0aSmrg if (chunk_size <= page_size && page_size % chunk_size == 0) { 455e56e5d0aSmrg // Same number of chunks per page, no cross overs. 456e56e5d0aSmrg full_pages_chunk_count_max = page_size / chunk_size; 457e56e5d0aSmrg same_chunk_count_per_page = true; 458e56e5d0aSmrg } else if (chunk_size <= page_size && page_size % chunk_size != 0 && 459e56e5d0aSmrg chunk_size % (page_size % chunk_size) == 0) { 460e56e5d0aSmrg // Some chunks are crossing page boundaries, which means that the page 461e56e5d0aSmrg // contains one or two partial chunks, but all pages contain the same 462e56e5d0aSmrg // number of chunks. 463e56e5d0aSmrg full_pages_chunk_count_max = page_size / chunk_size + 1; 464e56e5d0aSmrg same_chunk_count_per_page = true; 465e56e5d0aSmrg } else if (chunk_size <= page_size) { 466e56e5d0aSmrg // Some chunks are crossing page boundaries, which means that the page 467e56e5d0aSmrg // contains one or two partial chunks. 468e56e5d0aSmrg full_pages_chunk_count_max = page_size / chunk_size + 2; 469e56e5d0aSmrg same_chunk_count_per_page = false; 470e56e5d0aSmrg } else if (chunk_size > page_size && chunk_size % page_size == 0) { 471e56e5d0aSmrg // One chunk covers multiple pages, no cross overs. 472e56e5d0aSmrg full_pages_chunk_count_max = 1; 473e56e5d0aSmrg same_chunk_count_per_page = true; 474e56e5d0aSmrg } else if (chunk_size > page_size) { 475e56e5d0aSmrg // One chunk covers multiple pages, Some chunks are crossing page 476e56e5d0aSmrg // boundaries. Some pages contain one chunk, some contain two. 477e56e5d0aSmrg full_pages_chunk_count_max = 2; 478e56e5d0aSmrg same_chunk_count_per_page = false; 479e56e5d0aSmrg } else { 480e56e5d0aSmrg UNREACHABLE("All chunk_size/page_size ratios must be handled."); 481e56e5d0aSmrg } 482e56e5d0aSmrg 483e56e5d0aSmrg PackedCounterArray<MemoryMapperT> counters(allocated_pages_count, 484e56e5d0aSmrg full_pages_chunk_count_max, 485e56e5d0aSmrg memory_mapper); 486e56e5d0aSmrg if (!counters.IsAllocated()) 487e56e5d0aSmrg return; 488e56e5d0aSmrg 489e56e5d0aSmrg const uptr chunk_size_scaled = chunk_size >> kCompactPtrScale; 490e56e5d0aSmrg const uptr page_size_scaled = page_size >> kCompactPtrScale; 491e56e5d0aSmrg const uptr page_size_scaled_log = Log2(page_size_scaled); 492e56e5d0aSmrg 493e56e5d0aSmrg // Iterate over free chunks and count how many free chunks affect each 494e56e5d0aSmrg // allocated page. 495e56e5d0aSmrg if (chunk_size <= page_size && page_size % chunk_size == 0) { 496e56e5d0aSmrg // Each chunk affects one page only. 497e56e5d0aSmrg for (uptr i = 0; i < free_array_count; i++) 498e56e5d0aSmrg counters.Inc(free_array[i] >> page_size_scaled_log); 499e56e5d0aSmrg } else { 500e56e5d0aSmrg // In all other cases chunks might affect more than one page. 501e56e5d0aSmrg for (uptr i = 0; i < free_array_count; i++) { 502e56e5d0aSmrg counters.IncRange( 503e56e5d0aSmrg free_array[i] >> page_size_scaled_log, 504e56e5d0aSmrg (free_array[i] + chunk_size_scaled - 1) >> page_size_scaled_log); 505e56e5d0aSmrg } 506e56e5d0aSmrg } 507e56e5d0aSmrg 508e56e5d0aSmrg // Iterate over pages detecting ranges of pages with chunk counters equal 509e56e5d0aSmrg // to the expected number of chunks for the particular page. 510e56e5d0aSmrg FreePagesRangeTracker<MemoryMapperT> range_tracker(memory_mapper); 511e56e5d0aSmrg if (same_chunk_count_per_page) { 512e56e5d0aSmrg // Fast path, every page has the same number of chunks affecting it. 513e56e5d0aSmrg for (uptr i = 0; i < counters.GetCount(); i++) 514e56e5d0aSmrg range_tracker.NextPage(counters.Get(i) == full_pages_chunk_count_max); 515e56e5d0aSmrg } else { 516e56e5d0aSmrg // Show path, go through the pages keeping count how many chunks affect 517e56e5d0aSmrg // each page. 518e56e5d0aSmrg const uptr pn = 519e56e5d0aSmrg chunk_size < page_size ? page_size_scaled / chunk_size_scaled : 1; 520e56e5d0aSmrg const uptr pnc = pn * chunk_size_scaled; 521e56e5d0aSmrg // The idea is to increment the current page pointer by the first chunk 522e56e5d0aSmrg // size, middle portion size (the portion of the page covered by chunks 523e56e5d0aSmrg // except the first and the last one) and then the last chunk size, adding 524e56e5d0aSmrg // up the number of chunks on the current page and checking on every step 525e56e5d0aSmrg // whether the page boundary was crossed. 526e56e5d0aSmrg uptr prev_page_boundary = 0; 527e56e5d0aSmrg uptr current_boundary = 0; 528e56e5d0aSmrg for (uptr i = 0; i < counters.GetCount(); i++) { 529e56e5d0aSmrg uptr page_boundary = prev_page_boundary + page_size_scaled; 530e56e5d0aSmrg uptr chunks_per_page = pn; 531e56e5d0aSmrg if (current_boundary < page_boundary) { 532e56e5d0aSmrg if (current_boundary > prev_page_boundary) 533e56e5d0aSmrg chunks_per_page++; 534e56e5d0aSmrg current_boundary += pnc; 535e56e5d0aSmrg if (current_boundary < page_boundary) { 536e56e5d0aSmrg chunks_per_page++; 537e56e5d0aSmrg current_boundary += chunk_size_scaled; 538e56e5d0aSmrg } 539e56e5d0aSmrg } 540e56e5d0aSmrg prev_page_boundary = page_boundary; 541e56e5d0aSmrg 542e56e5d0aSmrg range_tracker.NextPage(counters.Get(i) == chunks_per_page); 543e56e5d0aSmrg } 544e56e5d0aSmrg } 545e56e5d0aSmrg range_tracker.Done(); 546e56e5d0aSmrg } 547e56e5d0aSmrg 548e56e5d0aSmrg private: 549e56e5d0aSmrg friend class MemoryMapper; 550e56e5d0aSmrg 551ff135a7aSmrg ReservedAddressRange address_range; 552ff135a7aSmrg 5536a5c9aabSmrg static const uptr kRegionSize = kSpaceSize / kNumClassesRounded; 5546a5c9aabSmrg // FreeArray is the array of free-d chunks (stored as 4-byte offsets). 5556a5c9aabSmrg // In the worst case it may reguire kRegionSize/SizeClassMap::kMinSize 5566a5c9aabSmrg // elements, but in reality this will not happen. For simplicity we 5576a5c9aabSmrg // dedicate 1/8 of the region's virtual space to FreeArray. 5586a5c9aabSmrg static const uptr kFreeArraySize = kRegionSize / 8; 5596a5c9aabSmrg 5606a5c9aabSmrg static const bool kUsingConstantSpaceBeg = kSpaceBeg != ~(uptr)0; 5616a5c9aabSmrg uptr NonConstSpaceBeg; SpaceBeg()5626a5c9aabSmrg uptr SpaceBeg() const { 5636a5c9aabSmrg return kUsingConstantSpaceBeg ? kSpaceBeg : NonConstSpaceBeg; 5646a5c9aabSmrg } SpaceEnd()5656a5c9aabSmrg uptr SpaceEnd() const { return SpaceBeg() + kSpaceSize; } 5666a5c9aabSmrg // kRegionSize must be >= 2^32. 5673bf62c3fSmrg #if _LP64 5686a5c9aabSmrg COMPILER_CHECK((kRegionSize) >= (1ULL << (SANITIZER_WORDSIZE / 2))); 5696a5c9aabSmrg // kRegionSize must be <= 2^36, see CompactPtrT. 5706a5c9aabSmrg COMPILER_CHECK((kRegionSize) <= (1ULL << (SANITIZER_WORDSIZE / 2 + 4))); 5713bf62c3fSmrg #endif 5726a5c9aabSmrg // Call mmap for user memory with at least this size. 5736a5c9aabSmrg static const uptr kUserMapSize = 1 << 16; 5746a5c9aabSmrg // Call mmap for metadata memory with at least this size. 5756a5c9aabSmrg static const uptr kMetaMapSize = 1 << 16; 5766a5c9aabSmrg // Call mmap for free array memory with at least this size. 5776a5c9aabSmrg static const uptr kFreeArrayMapSize = 1 << 16; 578e56e5d0aSmrg 579e56e5d0aSmrg atomic_sint32_t release_to_os_interval_ms_; 580e56e5d0aSmrg 581e56e5d0aSmrg struct Stats { 582e56e5d0aSmrg uptr n_allocated; 583e56e5d0aSmrg uptr n_freed; 584e56e5d0aSmrg }; 5856a5c9aabSmrg 5866a5c9aabSmrg struct ReleaseToOsInfo { 5876a5c9aabSmrg uptr n_freed_at_last_release; 5886a5c9aabSmrg uptr num_releases; 589e56e5d0aSmrg u64 last_release_at_ns; 590e56e5d0aSmrg u64 last_released_bytes; 5916a5c9aabSmrg }; 5926a5c9aabSmrg ALIGNED(SANITIZER_CACHE_LINE_SIZE)593ff135a7aSmrg struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) RegionInfo { 5946a5c9aabSmrg BlockingMutex mutex; 5956a5c9aabSmrg uptr num_freed_chunks; // Number of elements in the freearray. 5966a5c9aabSmrg uptr mapped_free_array; // Bytes mapped for freearray. 5976a5c9aabSmrg uptr allocated_user; // Bytes allocated for user memory. 5986a5c9aabSmrg uptr allocated_meta; // Bytes allocated for metadata. 5996a5c9aabSmrg uptr mapped_user; // Bytes mapped for user memory. 6006a5c9aabSmrg uptr mapped_meta; // Bytes mapped for metadata. 6016a5c9aabSmrg u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks. 602e56e5d0aSmrg bool exhausted; // Whether region is out of space for new chunks. 603e56e5d0aSmrg Stats stats; 6046a5c9aabSmrg ReleaseToOsInfo rtoi; 6056a5c9aabSmrg }; 606ff135a7aSmrg COMPILER_CHECK(sizeof(RegionInfo) % kCacheLineSize == 0); 6076a5c9aabSmrg GetRegionInfo(uptr class_id)608e56e5d0aSmrg RegionInfo *GetRegionInfo(uptr class_id) const { 609ff135a7aSmrg DCHECK_LT(class_id, kNumClasses); 610ff135a7aSmrg RegionInfo *regions = reinterpret_cast<RegionInfo *>(SpaceEnd()); 6116a5c9aabSmrg return ®ions[class_id]; 6126a5c9aabSmrg } 6136a5c9aabSmrg GetMetadataEnd(uptr region_beg)614e56e5d0aSmrg uptr GetMetadataEnd(uptr region_beg) const { 6156a5c9aabSmrg return region_beg + kRegionSize - kFreeArraySize; 6166a5c9aabSmrg } 6176a5c9aabSmrg GetChunkIdx(uptr chunk,uptr size)618e56e5d0aSmrg uptr GetChunkIdx(uptr chunk, uptr size) const { 6196a5c9aabSmrg if (!kUsingConstantSpaceBeg) 6206a5c9aabSmrg chunk -= SpaceBeg(); 6216a5c9aabSmrg 6226a5c9aabSmrg uptr offset = chunk % kRegionSize; 6236a5c9aabSmrg // Here we divide by a non-constant. This is costly. 6246a5c9aabSmrg // size always fits into 32-bits. If the offset fits too, use 32-bit div. 6256a5c9aabSmrg if (offset >> (SANITIZER_WORDSIZE / 2)) 6266a5c9aabSmrg return offset / size; 6276a5c9aabSmrg return (u32)offset / (u32)size; 6286a5c9aabSmrg } 6296a5c9aabSmrg GetFreeArray(uptr region_beg)630e56e5d0aSmrg CompactPtrT *GetFreeArray(uptr region_beg) const { 631e56e5d0aSmrg return reinterpret_cast<CompactPtrT *>(GetMetadataEnd(region_beg)); 6326a5c9aabSmrg } 6336a5c9aabSmrg MapWithCallback(uptr beg,uptr size)634*490215a3Smrg bool MapWithCallback(uptr beg, uptr size) { 635*490215a3Smrg uptr mapped = address_range.Map(beg, size); 636e56e5d0aSmrg if (UNLIKELY(!mapped)) 637e56e5d0aSmrg return false; 638e56e5d0aSmrg CHECK_EQ(beg, mapped); 639e56e5d0aSmrg MapUnmapCallback().OnMap(beg, size); 640e56e5d0aSmrg return true; 641e56e5d0aSmrg } 642e56e5d0aSmrg MapWithCallbackOrDie(uptr beg,uptr size)643*490215a3Smrg void MapWithCallbackOrDie(uptr beg, uptr size) { 644*490215a3Smrg CHECK_EQ(beg, address_range.MapOrDie(beg, size)); 645e56e5d0aSmrg MapUnmapCallback().OnMap(beg, size); 646e56e5d0aSmrg } 647e56e5d0aSmrg UnmapWithCallbackOrDie(uptr beg,uptr size)648e56e5d0aSmrg void UnmapWithCallbackOrDie(uptr beg, uptr size) { 649e56e5d0aSmrg MapUnmapCallback().OnUnmap(beg, size); 650ff135a7aSmrg address_range.Unmap(beg, size); 651e56e5d0aSmrg } 652e56e5d0aSmrg EnsureFreeArraySpace(RegionInfo * region,uptr region_beg,uptr num_freed_chunks)653e56e5d0aSmrg bool EnsureFreeArraySpace(RegionInfo *region, uptr region_beg, 6546a5c9aabSmrg uptr num_freed_chunks) { 6556a5c9aabSmrg uptr needed_space = num_freed_chunks * sizeof(CompactPtrT); 6566a5c9aabSmrg if (region->mapped_free_array < needed_space) { 6576a5c9aabSmrg uptr new_mapped_free_array = RoundUpTo(needed_space, kFreeArrayMapSize); 658e56e5d0aSmrg CHECK_LE(new_mapped_free_array, kFreeArraySize); 6596a5c9aabSmrg uptr current_map_end = reinterpret_cast<uptr>(GetFreeArray(region_beg)) + 6606a5c9aabSmrg region->mapped_free_array; 6616a5c9aabSmrg uptr new_map_size = new_mapped_free_array - region->mapped_free_array; 662*490215a3Smrg if (UNLIKELY(!MapWithCallback(current_map_end, new_map_size))) 663e56e5d0aSmrg return false; 6646a5c9aabSmrg region->mapped_free_array = new_mapped_free_array; 6656a5c9aabSmrg } 666e56e5d0aSmrg return true; 6676a5c9aabSmrg } 6686a5c9aabSmrg 669e56e5d0aSmrg // Check whether this size class is exhausted. IsRegionExhausted(RegionInfo * region,uptr class_id,uptr additional_map_size)670ff135a7aSmrg bool IsRegionExhausted(RegionInfo *region, uptr class_id, 671ff135a7aSmrg uptr additional_map_size) { 672ff135a7aSmrg if (LIKELY(region->mapped_user + region->mapped_meta + 673ff135a7aSmrg additional_map_size <= kRegionSize - kFreeArraySize)) 674ff135a7aSmrg return false; 675e56e5d0aSmrg if (!region->exhausted) { 676e56e5d0aSmrg region->exhausted = true; 677e56e5d0aSmrg Printf("%s: Out of memory. ", SanitizerToolName); 6786a5c9aabSmrg Printf("The process has exhausted %zuMB for size class %zu.\n", 679ff135a7aSmrg kRegionSize >> 20, ClassIdToSize(class_id)); 6806a5c9aabSmrg } 681ff135a7aSmrg return true; 682ff135a7aSmrg } 683ff135a7aSmrg PopulateFreeArray(AllocatorStats * stat,uptr class_id,RegionInfo * region,uptr requested_count)684ff135a7aSmrg NOINLINE bool PopulateFreeArray(AllocatorStats *stat, uptr class_id, 685ff135a7aSmrg RegionInfo *region, uptr requested_count) { 686ff135a7aSmrg // region->mutex is held. 687ff135a7aSmrg const uptr region_beg = GetRegionBeginBySizeClass(class_id); 688ff135a7aSmrg const uptr size = ClassIdToSize(class_id); 689ff135a7aSmrg 690ff135a7aSmrg const uptr total_user_bytes = 691ff135a7aSmrg region->allocated_user + requested_count * size; 692ff135a7aSmrg // Map more space for chunks, if necessary. 693ff135a7aSmrg if (LIKELY(total_user_bytes > region->mapped_user)) { 694ff135a7aSmrg if (UNLIKELY(region->mapped_user == 0)) { 695ff135a7aSmrg if (!kUsingConstantSpaceBeg && kRandomShuffleChunks) 696ff135a7aSmrg // The random state is initialized from ASLR. 697ff135a7aSmrg region->rand_state = static_cast<u32>(region_beg >> 12); 698ff135a7aSmrg // Postpone the first release to OS attempt for ReleaseToOSIntervalMs, 699ff135a7aSmrg // preventing just allocated memory from being released sooner than 700ff135a7aSmrg // necessary and also preventing extraneous ReleaseMemoryPagesToOS calls 701ff135a7aSmrg // for short lived processes. 702ff135a7aSmrg // Do it only when the feature is turned on, to avoid a potentially 703ff135a7aSmrg // extraneous syscall. 704ff135a7aSmrg if (ReleaseToOSIntervalMs() >= 0) 705ff135a7aSmrg region->rtoi.last_release_at_ns = MonotonicNanoTime(); 706ff135a7aSmrg } 707ff135a7aSmrg // Do the mmap for the user memory. 708ff135a7aSmrg const uptr user_map_size = 709ff135a7aSmrg RoundUpTo(total_user_bytes - region->mapped_user, kUserMapSize); 710ff135a7aSmrg if (UNLIKELY(IsRegionExhausted(region, class_id, user_map_size))) 711e56e5d0aSmrg return false; 712ff135a7aSmrg if (UNLIKELY(!MapWithCallback(region_beg + region->mapped_user, 713*490215a3Smrg user_map_size))) 714ff135a7aSmrg return false; 715ff135a7aSmrg stat->Add(AllocatorStatMapped, user_map_size); 716ff135a7aSmrg region->mapped_user += user_map_size; 717e56e5d0aSmrg } 718ff135a7aSmrg const uptr new_chunks_count = 719ff135a7aSmrg (region->mapped_user - region->allocated_user) / size; 720ff135a7aSmrg 721ff135a7aSmrg if (kMetadataSize) { 722ff135a7aSmrg // Calculate the required space for metadata. 723ff135a7aSmrg const uptr total_meta_bytes = 724ff135a7aSmrg region->allocated_meta + new_chunks_count * kMetadataSize; 725ff135a7aSmrg const uptr meta_map_size = (total_meta_bytes > region->mapped_meta) ? 726ff135a7aSmrg RoundUpTo(total_meta_bytes - region->mapped_meta, kMetaMapSize) : 0; 727e56e5d0aSmrg // Map more space for metadata, if necessary. 728ff135a7aSmrg if (meta_map_size) { 729ff135a7aSmrg if (UNLIKELY(IsRegionExhausted(region, class_id, meta_map_size))) 730e56e5d0aSmrg return false; 731ff135a7aSmrg if (UNLIKELY(!MapWithCallback( 732ff135a7aSmrg GetMetadataEnd(region_beg) - region->mapped_meta - meta_map_size, 733*490215a3Smrg meta_map_size))) 734ff135a7aSmrg return false; 735ff135a7aSmrg region->mapped_meta += meta_map_size; 736ff135a7aSmrg } 7376a5c9aabSmrg } 7386a5c9aabSmrg 739e56e5d0aSmrg // If necessary, allocate more space for the free array and populate it with 740e56e5d0aSmrg // newly allocated chunks. 741e56e5d0aSmrg const uptr total_freed_chunks = region->num_freed_chunks + new_chunks_count; 742e56e5d0aSmrg if (UNLIKELY(!EnsureFreeArraySpace(region, region_beg, total_freed_chunks))) 743e56e5d0aSmrg return false; 744e56e5d0aSmrg CompactPtrT *free_array = GetFreeArray(region_beg); 745ff135a7aSmrg for (uptr i = 0, chunk = region->allocated_user; i < new_chunks_count; 746e56e5d0aSmrg i++, chunk += size) 747e56e5d0aSmrg free_array[total_freed_chunks - 1 - i] = PointerToCompactPtr(0, chunk); 748e56e5d0aSmrg if (kRandomShuffleChunks) 749e56e5d0aSmrg RandomShuffle(&free_array[region->num_freed_chunks], new_chunks_count, 750e56e5d0aSmrg ®ion->rand_state); 751e56e5d0aSmrg 752e56e5d0aSmrg // All necessary memory is mapped and now it is safe to advance all 753e56e5d0aSmrg // 'allocated_*' counters. 754e56e5d0aSmrg region->num_freed_chunks += new_chunks_count; 755e56e5d0aSmrg region->allocated_user += new_chunks_count * size; 756e56e5d0aSmrg CHECK_LE(region->allocated_user, region->mapped_user); 757ff135a7aSmrg region->allocated_meta += new_chunks_count * kMetadataSize; 758e56e5d0aSmrg CHECK_LE(region->allocated_meta, region->mapped_meta); 759e56e5d0aSmrg region->exhausted = false; 760e56e5d0aSmrg 761e56e5d0aSmrg // TODO(alekseyshl): Consider bumping last_release_at_ns here to prevent 762e56e5d0aSmrg // MaybeReleaseToOS from releasing just allocated pages or protect these 763e56e5d0aSmrg // not yet used chunks some other way. 764e56e5d0aSmrg 7656a5c9aabSmrg return true; 7666a5c9aabSmrg } 7676a5c9aabSmrg 768e56e5d0aSmrg class MemoryMapper { 769e56e5d0aSmrg public: MemoryMapper(const ThisT & base_allocator,uptr class_id)770e56e5d0aSmrg MemoryMapper(const ThisT& base_allocator, uptr class_id) 771e56e5d0aSmrg : allocator(base_allocator), 772e56e5d0aSmrg region_base(base_allocator.GetRegionBeginBySizeClass(class_id)), 773e56e5d0aSmrg released_ranges_count(0), 774e56e5d0aSmrg released_bytes(0) { 775e56e5d0aSmrg } 776e56e5d0aSmrg GetReleasedRangesCount()777e56e5d0aSmrg uptr GetReleasedRangesCount() const { 778e56e5d0aSmrg return released_ranges_count; 779e56e5d0aSmrg } 780e56e5d0aSmrg GetReleasedBytes()781e56e5d0aSmrg uptr GetReleasedBytes() const { 782e56e5d0aSmrg return released_bytes; 783e56e5d0aSmrg } 784e56e5d0aSmrg MapPackedCounterArrayBuffer(uptr buffer_size)785e56e5d0aSmrg uptr MapPackedCounterArrayBuffer(uptr buffer_size) { 786e56e5d0aSmrg // TODO(alekseyshl): The idea to explore is to check if we have enough 787e56e5d0aSmrg // space between num_freed_chunks*sizeof(CompactPtrT) and 788e56e5d0aSmrg // mapped_free_array to fit buffer_size bytes and use that space instead 789e56e5d0aSmrg // of mapping a temporary one. 790e56e5d0aSmrg return reinterpret_cast<uptr>( 791e56e5d0aSmrg MmapOrDieOnFatalError(buffer_size, "ReleaseToOSPageCounters")); 792e56e5d0aSmrg } 793e56e5d0aSmrg UnmapPackedCounterArrayBuffer(uptr buffer,uptr buffer_size)794e56e5d0aSmrg void UnmapPackedCounterArrayBuffer(uptr buffer, uptr buffer_size) { 795e56e5d0aSmrg UnmapOrDie(reinterpret_cast<void *>(buffer), buffer_size); 796e56e5d0aSmrg } 797e56e5d0aSmrg 798e56e5d0aSmrg // Releases [from, to) range of pages back to OS. ReleasePageRangeToOS(CompactPtrT from,CompactPtrT to)799e56e5d0aSmrg void ReleasePageRangeToOS(CompactPtrT from, CompactPtrT to) { 800e56e5d0aSmrg const uptr from_page = allocator.CompactPtrToPointer(region_base, from); 801e56e5d0aSmrg const uptr to_page = allocator.CompactPtrToPointer(region_base, to); 802e56e5d0aSmrg ReleaseMemoryPagesToOS(from_page, to_page); 803e56e5d0aSmrg released_ranges_count++; 804e56e5d0aSmrg released_bytes += to_page - from_page; 805e56e5d0aSmrg } 806e56e5d0aSmrg 807e56e5d0aSmrg private: 808e56e5d0aSmrg const ThisT& allocator; 809e56e5d0aSmrg const uptr region_base; 810e56e5d0aSmrg uptr released_ranges_count; 811e56e5d0aSmrg uptr released_bytes; 812e56e5d0aSmrg }; 813e56e5d0aSmrg 814e56e5d0aSmrg // Attempts to release RAM occupied by freed chunks back to OS. The region is 815e56e5d0aSmrg // expected to be locked. MaybeReleaseToOS(uptr class_id,bool force)816ff135a7aSmrg void MaybeReleaseToOS(uptr class_id, bool force) { 8176a5c9aabSmrg RegionInfo *region = GetRegionInfo(class_id); 818e56e5d0aSmrg const uptr chunk_size = ClassIdToSize(class_id); 819e56e5d0aSmrg const uptr page_size = GetPageSizeCached(); 820e56e5d0aSmrg 8216a5c9aabSmrg uptr n = region->num_freed_chunks; 822e56e5d0aSmrg if (n * chunk_size < page_size) 8236a5c9aabSmrg return; // No chance to release anything. 824e56e5d0aSmrg if ((region->stats.n_freed - 825e56e5d0aSmrg region->rtoi.n_freed_at_last_release) * chunk_size < page_size) { 8266a5c9aabSmrg return; // Nothing new to release. 8276a5c9aabSmrg } 828e56e5d0aSmrg 829ff135a7aSmrg if (!force) { 830e56e5d0aSmrg s32 interval_ms = ReleaseToOSIntervalMs(); 831e56e5d0aSmrg if (interval_ms < 0) 832e56e5d0aSmrg return; 833e56e5d0aSmrg 834ff135a7aSmrg if (region->rtoi.last_release_at_ns + interval_ms * 1000000ULL > 835ff135a7aSmrg MonotonicNanoTime()) { 836e56e5d0aSmrg return; // Memory was returned recently. 837ff135a7aSmrg } 838ff135a7aSmrg } 839e56e5d0aSmrg 840e56e5d0aSmrg MemoryMapper memory_mapper(*this, class_id); 841e56e5d0aSmrg 842e56e5d0aSmrg ReleaseFreeMemoryToOS<MemoryMapper>( 843e56e5d0aSmrg GetFreeArray(GetRegionBeginBySizeClass(class_id)), n, chunk_size, 844e56e5d0aSmrg RoundUpTo(region->allocated_user, page_size) / page_size, 845e56e5d0aSmrg &memory_mapper); 846e56e5d0aSmrg 847e56e5d0aSmrg if (memory_mapper.GetReleasedRangesCount() > 0) { 848e56e5d0aSmrg region->rtoi.n_freed_at_last_release = region->stats.n_freed; 849e56e5d0aSmrg region->rtoi.num_releases += memory_mapper.GetReleasedRangesCount(); 850e56e5d0aSmrg region->rtoi.last_released_bytes = memory_mapper.GetReleasedBytes(); 8516a5c9aabSmrg } 852ff135a7aSmrg region->rtoi.last_release_at_ns = MonotonicNanoTime(); 8536a5c9aabSmrg } 8546a5c9aabSmrg }; 855