primary64.h revision 360660
1//===-- primary64.h ---------------------------------------------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#ifndef SCUDO_PRIMARY64_H_ 10#define SCUDO_PRIMARY64_H_ 11 12#include "bytemap.h" 13#include "common.h" 14#include "list.h" 15#include "local_cache.h" 16#include "release.h" 17#include "stats.h" 18#include "string_utils.h" 19 20namespace scudo { 21 22// SizeClassAllocator64 is an allocator tuned for 64-bit address space. 23// 24// It starts by reserving NumClasses * 2^RegionSizeLog bytes, equally divided in 25// Regions, specific to each size class. Note that the base of that mapping is 26// random (based to the platform specific map() capabilities), and that each 27// Region actually starts at a random offset from its base. 28// 29// Regions are mapped incrementally on demand to fulfill allocation requests, 30// those mappings being split into equally sized Blocks based on the size class 31// they belong to. The Blocks created are shuffled to prevent predictable 32// address patterns (the predictability increases with the size of the Blocks). 33// 34// The 1st Region (for size class 0) holds the TransferBatches. This is a 35// structure used to transfer arrays of available pointers from the class size 36// freelist to the thread specific freelist, and back. 37// 38// The memory used by this allocator is never unmapped, but can be partially 39// released it the platform allows for it. 40 41template <class SizeClassMapT, uptr RegionSizeLog> class SizeClassAllocator64 { 42public: 43 typedef SizeClassMapT SizeClassMap; 44 typedef SizeClassAllocator64<SizeClassMap, RegionSizeLog> ThisT; 45 typedef SizeClassAllocatorLocalCache<ThisT> CacheT; 46 typedef typename CacheT::TransferBatch TransferBatch; 47 48 static uptr getSizeByClassId(uptr ClassId) { 49 return (ClassId == SizeClassMap::BatchClassId) 50 ? sizeof(TransferBatch) 51 : SizeClassMap::getSizeByClassId(ClassId); 52 } 53 54 static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; } 55 56 void initLinkerInitialized(s32 ReleaseToOsInterval) { 57 // Reserve the space required for the Primary. 58 PrimaryBase = reinterpret_cast<uptr>( 59 map(nullptr, PrimarySize, "scudo:primary", MAP_NOACCESS, &Data)); 60 61 RegionInfoArray = reinterpret_cast<RegionInfo *>( 62 map(nullptr, sizeof(RegionInfo) * NumClasses, "scudo:regioninfo")); 63 DCHECK_EQ(reinterpret_cast<uptr>(RegionInfoArray) % SCUDO_CACHE_LINE_SIZE, 64 0); 65 66 u32 Seed; 67 if (UNLIKELY(!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed)))) 68 Seed = static_cast<u32>(getMonotonicTime() ^ (PrimaryBase >> 12)); 69 const uptr PageSize = getPageSizeCached(); 70 for (uptr I = 0; I < NumClasses; I++) { 71 RegionInfo *Region = getRegionInfo(I); 72 // The actual start of a region is offseted by a random number of pages. 73 Region->RegionBeg = 74 getRegionBaseByClassId(I) + (getRandomModN(&Seed, 16) + 1) * PageSize; 75 // Releasing smaller size classes doesn't necessarily yield to a 76 // meaningful RSS impact: there are more blocks per page, they are 77 // randomized around, and thus pages are less likely to be entirely empty. 78 // On top of this, attempting to release those require more iterations and 79 // memory accesses which ends up being fairly costly. The current lower 80 // limit is mostly arbitrary and based on empirical observations. 81 // TODO(kostyak): make the lower limit a runtime option 82 Region->CanRelease = (ReleaseToOsInterval > 0) && 83 (I != SizeClassMap::BatchClassId) && 84 (getSizeByClassId(I) >= (PageSize / 32)); 85 Region->RandState = getRandomU32(&Seed); 86 } 87 ReleaseToOsIntervalMs = ReleaseToOsInterval; 88 } 89 void init(s32 ReleaseToOsInterval) { 90 memset(this, 0, sizeof(*this)); 91 initLinkerInitialized(ReleaseToOsInterval); 92 } 93 94 void unmapTestOnly() { 95 unmap(reinterpret_cast<void *>(PrimaryBase), PrimarySize, UNMAP_ALL, &Data); 96 unmap(reinterpret_cast<void *>(RegionInfoArray), 97 sizeof(RegionInfo) * NumClasses); 98 } 99 100 TransferBatch *popBatch(CacheT *C, uptr ClassId) { 101 DCHECK_LT(ClassId, NumClasses); 102 RegionInfo *Region = getRegionInfo(ClassId); 103 ScopedLock L(Region->Mutex); 104 TransferBatch *B = Region->FreeList.front(); 105 if (B) 106 Region->FreeList.pop_front(); 107 else { 108 B = populateFreeList(C, ClassId, Region); 109 if (UNLIKELY(!B)) 110 return nullptr; 111 } 112 DCHECK_GT(B->getCount(), 0); 113 Region->Stats.PoppedBlocks += B->getCount(); 114 return B; 115 } 116 117 void pushBatch(uptr ClassId, TransferBatch *B) { 118 DCHECK_GT(B->getCount(), 0); 119 RegionInfo *Region = getRegionInfo(ClassId); 120 ScopedLock L(Region->Mutex); 121 Region->FreeList.push_front(B); 122 Region->Stats.PushedBlocks += B->getCount(); 123 if (Region->CanRelease) 124 releaseToOSMaybe(Region, ClassId); 125 } 126 127 void disable() { 128 for (uptr I = 0; I < NumClasses; I++) 129 getRegionInfo(I)->Mutex.lock(); 130 } 131 132 void enable() { 133 for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) 134 getRegionInfo(I)->Mutex.unlock(); 135 } 136 137 template <typename F> void iterateOverBlocks(F Callback) const { 138 for (uptr I = 1; I < NumClasses; I++) { 139 const RegionInfo *Region = getRegionInfo(I); 140 const uptr BlockSize = getSizeByClassId(I); 141 const uptr From = Region->RegionBeg; 142 const uptr To = From + Region->AllocatedUser; 143 for (uptr Block = From; Block < To; Block += BlockSize) 144 Callback(Block); 145 } 146 } 147 148 void printStats() const { 149 // TODO(kostyak): get the RSS per region. 150 uptr TotalMapped = 0; 151 uptr PoppedBlocks = 0; 152 uptr PushedBlocks = 0; 153 for (uptr I = 0; I < NumClasses; I++) { 154 RegionInfo *Region = getRegionInfo(I); 155 if (Region->MappedUser) 156 TotalMapped += Region->MappedUser; 157 PoppedBlocks += Region->Stats.PoppedBlocks; 158 PushedBlocks += Region->Stats.PushedBlocks; 159 } 160 Printf("Stats: Primary64: %zuM mapped (%zuM rss) in %zu allocations; " 161 "remains %zu\n", 162 TotalMapped >> 20, 0, PoppedBlocks, PoppedBlocks - PushedBlocks); 163 164 for (uptr I = 0; I < NumClasses; I++) 165 printStats(I, 0); 166 } 167 168 void releaseToOS() { 169 for (uptr I = 0; I < NumClasses; I++) { 170 if (I == SizeClassMap::BatchClassId) 171 continue; 172 RegionInfo *Region = getRegionInfo(I); 173 ScopedLock L(Region->Mutex); 174 releaseToOSMaybe(Region, I, /*Force=*/true); 175 } 176 } 177 178private: 179 static const uptr RegionSize = 1UL << RegionSizeLog; 180 static const uptr NumClasses = SizeClassMap::NumClasses; 181 static const uptr PrimarySize = RegionSize * NumClasses; 182 183 // Call map for user memory with at least this size. 184 static const uptr MapSizeIncrement = 1UL << 16; 185 186 struct RegionStats { 187 uptr PoppedBlocks; 188 uptr PushedBlocks; 189 }; 190 191 struct ReleaseToOsInfo { 192 uptr PushedBlocksAtLastRelease; 193 uptr RangesReleased; 194 uptr LastReleasedBytes; 195 u64 LastReleaseAtNs; 196 }; 197 198 struct ALIGNED(SCUDO_CACHE_LINE_SIZE) RegionInfo { 199 HybridMutex Mutex; 200 IntrusiveList<TransferBatch> FreeList; 201 RegionStats Stats; 202 bool CanRelease; 203 bool Exhausted; 204 u32 RandState; 205 uptr RegionBeg; 206 uptr MappedUser; // Bytes mapped for user memory. 207 uptr AllocatedUser; // Bytes allocated for user memory. 208 MapPlatformData Data; 209 ReleaseToOsInfo ReleaseInfo; 210 }; 211 COMPILER_CHECK(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0); 212 213 uptr PrimaryBase; 214 RegionInfo *RegionInfoArray; 215 MapPlatformData Data; 216 s32 ReleaseToOsIntervalMs; 217 218 RegionInfo *getRegionInfo(uptr ClassId) const { 219 DCHECK_LT(ClassId, NumClasses); 220 return &RegionInfoArray[ClassId]; 221 } 222 223 uptr getRegionBaseByClassId(uptr ClassId) const { 224 return PrimaryBase + (ClassId << RegionSizeLog); 225 } 226 227 bool populateBatches(CacheT *C, RegionInfo *Region, uptr ClassId, 228 TransferBatch **CurrentBatch, u32 MaxCount, 229 void **PointersArray, u32 Count) { 230 // No need to shuffle the batches size class. 231 if (ClassId != SizeClassMap::BatchClassId) 232 shuffle(PointersArray, Count, &Region->RandState); 233 TransferBatch *B = *CurrentBatch; 234 for (uptr I = 0; I < Count; I++) { 235 if (B && B->getCount() == MaxCount) { 236 Region->FreeList.push_back(B); 237 B = nullptr; 238 } 239 if (!B) { 240 B = C->createBatch(ClassId, PointersArray[I]); 241 if (UNLIKELY(!B)) 242 return false; 243 B->clear(); 244 } 245 B->add(PointersArray[I]); 246 } 247 *CurrentBatch = B; 248 return true; 249 } 250 251 NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId, 252 RegionInfo *Region) { 253 const uptr Size = getSizeByClassId(ClassId); 254 const u32 MaxCount = TransferBatch::getMaxCached(Size); 255 256 const uptr RegionBeg = Region->RegionBeg; 257 const uptr MappedUser = Region->MappedUser; 258 const uptr TotalUserBytes = Region->AllocatedUser + MaxCount * Size; 259 // Map more space for blocks, if necessary. 260 if (LIKELY(TotalUserBytes > MappedUser)) { 261 // Do the mmap for the user memory. 262 const uptr UserMapSize = 263 roundUpTo(TotalUserBytes - MappedUser, MapSizeIncrement); 264 const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId); 265 if (UNLIKELY(RegionBase + MappedUser + UserMapSize > RegionSize)) { 266 if (!Region->Exhausted) { 267 Region->Exhausted = true; 268 printStats(); 269 Printf( 270 "Scudo OOM: The process has Exhausted %zuM for size class %zu.\n", 271 RegionSize >> 20, Size); 272 } 273 return nullptr; 274 } 275 if (MappedUser == 0) 276 Region->Data = Data; 277 if (UNLIKELY(!map(reinterpret_cast<void *>(RegionBeg + MappedUser), 278 UserMapSize, "scudo:primary", 279 MAP_ALLOWNOMEM | MAP_RESIZABLE, &Region->Data))) 280 return nullptr; 281 Region->MappedUser += UserMapSize; 282 C->getStats().add(StatMapped, UserMapSize); 283 } 284 285 const uptr NumberOfBlocks = Min( 286 8UL * MaxCount, (Region->MappedUser - Region->AllocatedUser) / Size); 287 DCHECK_GT(NumberOfBlocks, 0); 288 289 TransferBatch *B = nullptr; 290 constexpr uptr ShuffleArraySize = 48; 291 void *ShuffleArray[ShuffleArraySize]; 292 u32 Count = 0; 293 const uptr P = RegionBeg + Region->AllocatedUser; 294 const uptr AllocatedUser = NumberOfBlocks * Size; 295 for (uptr I = P; I < P + AllocatedUser; I += Size) { 296 ShuffleArray[Count++] = reinterpret_cast<void *>(I); 297 if (Count == ShuffleArraySize) { 298 if (UNLIKELY(!populateBatches(C, Region, ClassId, &B, MaxCount, 299 ShuffleArray, Count))) 300 return nullptr; 301 Count = 0; 302 } 303 } 304 if (Count) { 305 if (UNLIKELY(!populateBatches(C, Region, ClassId, &B, MaxCount, 306 ShuffleArray, Count))) 307 return nullptr; 308 } 309 DCHECK(B); 310 CHECK_GT(B->getCount(), 0); 311 312 Region->AllocatedUser += AllocatedUser; 313 Region->Exhausted = false; 314 if (Region->CanRelease) 315 Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime(); 316 317 return B; 318 } 319 320 void printStats(uptr ClassId, uptr Rss) const { 321 RegionInfo *Region = getRegionInfo(ClassId); 322 if (Region->MappedUser == 0) 323 return; 324 const uptr InUse = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks; 325 const uptr AvailableChunks = 326 Region->AllocatedUser / getSizeByClassId(ClassId); 327 Printf("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu inuse: " 328 "%6zu avail: %6zu rss: %6zuK releases: %6zu last released: %6zuK " 329 "region: 0x%zx (0x%zx)\n", 330 Region->Exhausted ? "F" : " ", ClassId, getSizeByClassId(ClassId), 331 Region->MappedUser >> 10, Region->Stats.PoppedBlocks, 332 Region->Stats.PushedBlocks, InUse, AvailableChunks, Rss >> 10, 333 Region->ReleaseInfo.RangesReleased, 334 Region->ReleaseInfo.LastReleasedBytes >> 10, Region->RegionBeg, 335 getRegionBaseByClassId(ClassId)); 336 } 337 338 NOINLINE void releaseToOSMaybe(RegionInfo *Region, uptr ClassId, 339 bool Force = false) { 340 const uptr BlockSize = getSizeByClassId(ClassId); 341 const uptr PageSize = getPageSizeCached(); 342 343 CHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks); 344 const uptr N = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks; 345 if (N * BlockSize < PageSize) 346 return; // No chance to release anything. 347 if ((Region->Stats.PushedBlocks - 348 Region->ReleaseInfo.PushedBlocksAtLastRelease) * 349 BlockSize < 350 PageSize) { 351 return; // Nothing new to release. 352 } 353 354 if (!Force) { 355 const s32 IntervalMs = ReleaseToOsIntervalMs; 356 if (IntervalMs < 0) 357 return; 358 if (Region->ReleaseInfo.LastReleaseAtNs + IntervalMs * 1000000ULL > 359 getMonotonicTime()) { 360 return; // Memory was returned recently. 361 } 362 } 363 364 ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data); 365 releaseFreeMemoryToOS(&Region->FreeList, Region->RegionBeg, 366 roundUpTo(Region->AllocatedUser, PageSize) / PageSize, 367 BlockSize, &Recorder); 368 369 if (Recorder.getReleasedRangesCount() > 0) { 370 Region->ReleaseInfo.PushedBlocksAtLastRelease = 371 Region->Stats.PushedBlocks; 372 Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount(); 373 Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes(); 374 } 375 Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime(); 376 } 377}; 378 379} // namespace scudo 380 381#endif // SCUDO_PRIMARY64_H_ 382