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 "memtag.h"
17 #include "options.h"
18 #include "release.h"
19 #include "stats.h"
20 #include "string_utils.h"
21 
22 namespace scudo {
23 
24 // SizeClassAllocator64 is an allocator tuned for 64-bit address space.
25 //
26 // It starts by reserving NumClasses * 2^RegionSizeLog bytes, equally divided in
27 // Regions, specific to each size class. Note that the base of that mapping is
28 // random (based to the platform specific map() capabilities). If
29 // PrimaryEnableRandomOffset is set, each Region actually starts at a random
30 // offset from its base.
31 //
32 // Regions are mapped incrementally on demand to fulfill allocation requests,
33 // those mappings being split into equally sized Blocks based on the size class
34 // they belong to. The Blocks created are shuffled to prevent predictable
35 // address patterns (the predictability increases with the size of the Blocks).
36 //
37 // The 1st Region (for size class 0) holds the TransferBatches. This is a
38 // structure used to transfer arrays of available pointers from the class size
39 // freelist to the thread specific freelist, and back.
40 //
41 // The memory used by this allocator is never unmapped, but can be partially
42 // released if the platform allows for it.
43 
44 template <typename Config> class SizeClassAllocator64 {
45 public:
46   typedef typename Config::PrimaryCompactPtrT CompactPtrT;
47   static const uptr CompactPtrScale = Config::PrimaryCompactPtrScale;
48   typedef typename Config::SizeClassMap SizeClassMap;
49   typedef SizeClassAllocator64<Config> ThisT;
50   typedef SizeClassAllocatorLocalCache<ThisT> CacheT;
51   typedef typename CacheT::TransferBatch TransferBatch;
52 
53   static uptr getSizeByClassId(uptr ClassId) {
54     return (ClassId == SizeClassMap::BatchClassId)
55                ? roundUpTo(sizeof(TransferBatch), 1U << CompactPtrScale)
56                : SizeClassMap::getSizeByClassId(ClassId);
57   }
58 
59   static bool canAllocate(uptr Size) { return Size <= SizeClassMap::MaxSize; }
60 
61   void init(s32 ReleaseToOsInterval) {
62     DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));
63     DCHECK_EQ(PrimaryBase, 0U);
64     // Reserve the space required for the Primary.
65     PrimaryBase = reinterpret_cast<uptr>(
66         map(nullptr, PrimarySize, nullptr, MAP_NOACCESS, &Data));
67 
68     u32 Seed;
69     const u64 Time = getMonotonicTime();
70     if (!getRandom(reinterpret_cast<void *>(&Seed), sizeof(Seed)))
71       Seed = static_cast<u32>(Time ^ (PrimaryBase >> 12));
72     const uptr PageSize = getPageSizeCached();
73     for (uptr I = 0; I < NumClasses; I++) {
74       RegionInfo *Region = getRegionInfo(I);
75       // The actual start of a region is offset by a random number of pages
76       // when PrimaryEnableRandomOffset is set.
77       Region->RegionBeg = getRegionBaseByClassId(I) +
78                           (Config::PrimaryEnableRandomOffset
79                                ? ((getRandomModN(&Seed, 16) + 1) * PageSize)
80                                : 0);
81       Region->RandState = getRandomU32(&Seed);
82       Region->ReleaseInfo.LastReleaseAtNs = Time;
83     }
84     setOption(Option::ReleaseInterval, static_cast<sptr>(ReleaseToOsInterval));
85   }
86 
87   void unmapTestOnly() {
88     for (uptr I = 0; I < NumClasses; I++) {
89       RegionInfo *Region = getRegionInfo(I);
90       *Region = {};
91     }
92     if (PrimaryBase)
93       unmap(reinterpret_cast<void *>(PrimaryBase), PrimarySize, UNMAP_ALL,
94             &Data);
95     PrimaryBase = 0U;
96   }
97 
98   TransferBatch *popBatch(CacheT *C, uptr ClassId) {
99     DCHECK_LT(ClassId, NumClasses);
100     RegionInfo *Region = getRegionInfo(ClassId);
101     ScopedLock L(Region->Mutex);
102     TransferBatch *B = Region->FreeList.front();
103     if (B) {
104       Region->FreeList.pop_front();
105     } else {
106       B = populateFreeList(C, ClassId, Region);
107       if (UNLIKELY(!B))
108         return nullptr;
109     }
110     DCHECK_GT(B->getCount(), 0);
111     Region->Stats.PoppedBlocks += B->getCount();
112     return B;
113   }
114 
115   void pushBatch(uptr ClassId, TransferBatch *B) {
116     DCHECK_GT(B->getCount(), 0);
117     RegionInfo *Region = getRegionInfo(ClassId);
118     ScopedLock L(Region->Mutex);
119     Region->FreeList.push_front(B);
120     Region->Stats.PushedBlocks += B->getCount();
121     if (ClassId != SizeClassMap::BatchClassId)
122       releaseToOSMaybe(Region, ClassId);
123   }
124 
125   void disable() {
126     // The BatchClassId must be locked last since other classes can use it.
127     for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
128       if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
129         continue;
130       getRegionInfo(static_cast<uptr>(I))->Mutex.lock();
131     }
132     getRegionInfo(SizeClassMap::BatchClassId)->Mutex.lock();
133   }
134 
135   void enable() {
136     getRegionInfo(SizeClassMap::BatchClassId)->Mutex.unlock();
137     for (uptr I = 0; I < NumClasses; I++) {
138       if (I == SizeClassMap::BatchClassId)
139         continue;
140       getRegionInfo(I)->Mutex.unlock();
141     }
142   }
143 
144   template <typename F> void iterateOverBlocks(F Callback) {
145     for (uptr I = 0; I < NumClasses; I++) {
146       if (I == SizeClassMap::BatchClassId)
147         continue;
148       const RegionInfo *Region = getRegionInfo(I);
149       const uptr BlockSize = getSizeByClassId(I);
150       const uptr From = Region->RegionBeg;
151       const uptr To = From + Region->AllocatedUser;
152       for (uptr Block = From; Block < To; Block += BlockSize)
153         Callback(Block);
154     }
155   }
156 
157   void getStats(ScopedString *Str) {
158     // TODO(kostyak): get the RSS per region.
159     uptr TotalMapped = 0;
160     uptr PoppedBlocks = 0;
161     uptr PushedBlocks = 0;
162     for (uptr I = 0; I < NumClasses; I++) {
163       RegionInfo *Region = getRegionInfo(I);
164       if (Region->MappedUser)
165         TotalMapped += Region->MappedUser;
166       PoppedBlocks += Region->Stats.PoppedBlocks;
167       PushedBlocks += Region->Stats.PushedBlocks;
168     }
169     Str->append("Stats: SizeClassAllocator64: %zuM mapped (%uM rss) in %zu "
170                 "allocations; remains %zu\n",
171                 TotalMapped >> 20, 0U, PoppedBlocks,
172                 PoppedBlocks - PushedBlocks);
173 
174     for (uptr I = 0; I < NumClasses; I++)
175       getStats(Str, I, 0);
176   }
177 
178   bool setOption(Option O, sptr Value) {
179     if (O == Option::ReleaseInterval) {
180       const s32 Interval = Max(
181           Min(static_cast<s32>(Value), Config::PrimaryMaxReleaseToOsIntervalMs),
182           Config::PrimaryMinReleaseToOsIntervalMs);
183       atomic_store_relaxed(&ReleaseToOsIntervalMs, Interval);
184       return true;
185     }
186     // Not supported by the Primary, but not an error either.
187     return true;
188   }
189 
190   uptr releaseToOS() {
191     uptr TotalReleasedBytes = 0;
192     for (uptr I = 0; I < NumClasses; I++) {
193       if (I == SizeClassMap::BatchClassId)
194         continue;
195       RegionInfo *Region = getRegionInfo(I);
196       ScopedLock L(Region->Mutex);
197       TotalReleasedBytes += releaseToOSMaybe(Region, I, /*Force=*/true);
198     }
199     return TotalReleasedBytes;
200   }
201 
202   const char *getRegionInfoArrayAddress() const {
203     return reinterpret_cast<const char *>(RegionInfoArray);
204   }
205 
206   static uptr getRegionInfoArraySize() { return sizeof(RegionInfoArray); }
207 
208   uptr getCompactPtrBaseByClassId(uptr ClassId) {
209     // If we are not compacting pointers, base everything off of 0.
210     if (sizeof(CompactPtrT) == sizeof(uptr) && CompactPtrScale == 0)
211       return 0;
212     return getRegionInfo(ClassId)->RegionBeg;
213   }
214 
215   CompactPtrT compactPtr(uptr ClassId, uptr Ptr) {
216     DCHECK_LE(ClassId, SizeClassMap::LargestClassId);
217     return compactPtrInternal(getCompactPtrBaseByClassId(ClassId), Ptr);
218   }
219 
220   void *decompactPtr(uptr ClassId, CompactPtrT CompactPtr) {
221     DCHECK_LE(ClassId, SizeClassMap::LargestClassId);
222     return reinterpret_cast<void *>(
223         decompactPtrInternal(getCompactPtrBaseByClassId(ClassId), CompactPtr));
224   }
225 
226   static BlockInfo findNearestBlock(const char *RegionInfoData, uptr Ptr) {
227     const RegionInfo *RegionInfoArray =
228         reinterpret_cast<const RegionInfo *>(RegionInfoData);
229     uptr ClassId;
230     uptr MinDistance = -1UL;
231     for (uptr I = 0; I != NumClasses; ++I) {
232       if (I == SizeClassMap::BatchClassId)
233         continue;
234       uptr Begin = RegionInfoArray[I].RegionBeg;
235       uptr End = Begin + RegionInfoArray[I].AllocatedUser;
236       if (Begin > End || End - Begin < SizeClassMap::getSizeByClassId(I))
237         continue;
238       uptr RegionDistance;
239       if (Begin <= Ptr) {
240         if (Ptr < End)
241           RegionDistance = 0;
242         else
243           RegionDistance = Ptr - End;
244       } else {
245         RegionDistance = Begin - Ptr;
246       }
247 
248       if (RegionDistance < MinDistance) {
249         MinDistance = RegionDistance;
250         ClassId = I;
251       }
252     }
253 
254     BlockInfo B = {};
255     if (MinDistance <= 8192) {
256       B.RegionBegin = RegionInfoArray[ClassId].RegionBeg;
257       B.RegionEnd = B.RegionBegin + RegionInfoArray[ClassId].AllocatedUser;
258       B.BlockSize = SizeClassMap::getSizeByClassId(ClassId);
259       B.BlockBegin =
260           B.RegionBegin + uptr(sptr(Ptr - B.RegionBegin) / sptr(B.BlockSize) *
261                                sptr(B.BlockSize));
262       while (B.BlockBegin < B.RegionBegin)
263         B.BlockBegin += B.BlockSize;
264       while (B.RegionEnd < B.BlockBegin + B.BlockSize)
265         B.BlockBegin -= B.BlockSize;
266     }
267     return B;
268   }
269 
270   AtomicOptions Options;
271 
272 private:
273   static const uptr RegionSize = 1UL << Config::PrimaryRegionSizeLog;
274   static const uptr NumClasses = SizeClassMap::NumClasses;
275   static const uptr PrimarySize = RegionSize * NumClasses;
276 
277   static const uptr MapSizeIncrement = Config::PrimaryMapSizeIncrement;
278   // Fill at most this number of batches from the newly map'd memory.
279   static const u32 MaxNumBatches = SCUDO_ANDROID ? 4U : 8U;
280 
281   struct RegionStats {
282     uptr PoppedBlocks;
283     uptr PushedBlocks;
284   };
285 
286   struct ReleaseToOsInfo {
287     uptr PushedBlocksAtLastRelease;
288     uptr RangesReleased;
289     uptr LastReleasedBytes;
290     u64 LastReleaseAtNs;
291   };
292 
293   struct UnpaddedRegionInfo {
294     HybridMutex Mutex;
295     SinglyLinkedList<TransferBatch> FreeList;
296     uptr RegionBeg = 0;
297     RegionStats Stats = {};
298     u32 RandState = 0;
299     uptr MappedUser = 0;    // Bytes mapped for user memory.
300     uptr AllocatedUser = 0; // Bytes allocated for user memory.
301     MapPlatformData Data = {};
302     ReleaseToOsInfo ReleaseInfo = {};
303     bool Exhausted = false;
304   };
305   struct RegionInfo : UnpaddedRegionInfo {
306     char Padding[SCUDO_CACHE_LINE_SIZE -
307                  (sizeof(UnpaddedRegionInfo) % SCUDO_CACHE_LINE_SIZE)] = {};
308   };
309   static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
310 
311   uptr PrimaryBase = 0;
312   MapPlatformData Data = {};
313   atomic_s32 ReleaseToOsIntervalMs = {};
314   alignas(SCUDO_CACHE_LINE_SIZE) RegionInfo RegionInfoArray[NumClasses];
315 
316   RegionInfo *getRegionInfo(uptr ClassId) {
317     DCHECK_LT(ClassId, NumClasses);
318     return &RegionInfoArray[ClassId];
319   }
320 
321   uptr getRegionBaseByClassId(uptr ClassId) const {
322     return PrimaryBase + (ClassId << Config::PrimaryRegionSizeLog);
323   }
324 
325   static CompactPtrT compactPtrInternal(uptr Base, uptr Ptr) {
326     return static_cast<CompactPtrT>((Ptr - Base) >> CompactPtrScale);
327   }
328 
329   static uptr decompactPtrInternal(uptr Base, CompactPtrT CompactPtr) {
330     return Base + (static_cast<uptr>(CompactPtr) << CompactPtrScale);
331   }
332 
333   NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
334                                            RegionInfo *Region) {
335     const uptr Size = getSizeByClassId(ClassId);
336     const u32 MaxCount = TransferBatch::getMaxCached(Size);
337 
338     const uptr RegionBeg = Region->RegionBeg;
339     const uptr MappedUser = Region->MappedUser;
340     const uptr TotalUserBytes = Region->AllocatedUser + MaxCount * Size;
341     // Map more space for blocks, if necessary.
342     if (TotalUserBytes > MappedUser) {
343       // Do the mmap for the user memory.
344       const uptr MapSize =
345           roundUpTo(TotalUserBytes - MappedUser, MapSizeIncrement);
346       const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId);
347       if (UNLIKELY(RegionBase + MappedUser + MapSize > RegionSize)) {
348         if (!Region->Exhausted) {
349           Region->Exhausted = true;
350           ScopedString Str;
351           getStats(&Str);
352           Str.append(
353               "Scudo OOM: The process has exhausted %zuM for size class %zu.\n",
354               RegionSize >> 20, Size);
355           Str.output();
356         }
357         return nullptr;
358       }
359       if (MappedUser == 0)
360         Region->Data = Data;
361       if (UNLIKELY(!map(
362               reinterpret_cast<void *>(RegionBeg + MappedUser), MapSize,
363               "scudo:primary",
364               MAP_ALLOWNOMEM | MAP_RESIZABLE |
365                   (useMemoryTagging<Config>(Options.load()) ? MAP_MEMTAG : 0),
366               &Region->Data)))
367         return nullptr;
368       Region->MappedUser += MapSize;
369       C->getStats().add(StatMapped, MapSize);
370     }
371 
372     const u32 NumberOfBlocks = Min(
373         MaxNumBatches * MaxCount,
374         static_cast<u32>((Region->MappedUser - Region->AllocatedUser) / Size));
375     DCHECK_GT(NumberOfBlocks, 0);
376 
377     constexpr u32 ShuffleArraySize =
378         MaxNumBatches * TransferBatch::MaxNumCached;
379     CompactPtrT ShuffleArray[ShuffleArraySize];
380     DCHECK_LE(NumberOfBlocks, ShuffleArraySize);
381 
382     const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
383     uptr P = RegionBeg + Region->AllocatedUser;
384     for (u32 I = 0; I < NumberOfBlocks; I++, P += Size)
385       ShuffleArray[I] = compactPtrInternal(CompactPtrBase, P);
386     // No need to shuffle the batches size class.
387     if (ClassId != SizeClassMap::BatchClassId)
388       shuffle(ShuffleArray, NumberOfBlocks, &Region->RandState);
389     for (u32 I = 0; I < NumberOfBlocks;) {
390       TransferBatch *B =
391           C->createBatch(ClassId, reinterpret_cast<void *>(decompactPtrInternal(
392                                       CompactPtrBase, ShuffleArray[I])));
393       if (UNLIKELY(!B))
394         return nullptr;
395       const u32 N = Min(MaxCount, NumberOfBlocks - I);
396       B->setFromArray(&ShuffleArray[I], N);
397       Region->FreeList.push_back(B);
398       I += N;
399     }
400     TransferBatch *B = Region->FreeList.front();
401     Region->FreeList.pop_front();
402     DCHECK(B);
403     DCHECK_GT(B->getCount(), 0);
404 
405     const uptr AllocatedUser = Size * NumberOfBlocks;
406     C->getStats().add(StatFree, AllocatedUser);
407     Region->AllocatedUser += AllocatedUser;
408 
409     return B;
410   }
411 
412   void getStats(ScopedString *Str, uptr ClassId, uptr Rss) {
413     RegionInfo *Region = getRegionInfo(ClassId);
414     if (Region->MappedUser == 0)
415       return;
416     const uptr InUse = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks;
417     const uptr TotalChunks = Region->AllocatedUser / getSizeByClassId(ClassId);
418     Str->append("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
419                 "inuse: %6zu total: %6zu rss: %6zuK releases: %6zu last "
420                 "released: %6zuK region: 0x%zx (0x%zx)\n",
421                 Region->Exhausted ? "F" : " ", ClassId,
422                 getSizeByClassId(ClassId), Region->MappedUser >> 10,
423                 Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks, InUse,
424                 TotalChunks, Rss >> 10, Region->ReleaseInfo.RangesReleased,
425                 Region->ReleaseInfo.LastReleasedBytes >> 10, Region->RegionBeg,
426                 getRegionBaseByClassId(ClassId));
427   }
428 
429   NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
430                                  bool Force = false) {
431     const uptr BlockSize = getSizeByClassId(ClassId);
432     const uptr PageSize = getPageSizeCached();
433 
434     DCHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks);
435     const uptr BytesInFreeList =
436         Region->AllocatedUser -
437         (Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks) * BlockSize;
438     if (BytesInFreeList < PageSize)
439       return 0; // No chance to release anything.
440     const uptr BytesPushed = (Region->Stats.PushedBlocks -
441                               Region->ReleaseInfo.PushedBlocksAtLastRelease) *
442                              BlockSize;
443     if (BytesPushed < PageSize)
444       return 0; // Nothing new to release.
445 
446     // Releasing smaller blocks is expensive, so we want to make sure that a
447     // significant amount of bytes are free, and that there has been a good
448     // amount of batches pushed to the freelist before attempting to release.
449     if (BlockSize < PageSize / 16U) {
450       if (!Force && BytesPushed < Region->AllocatedUser / 16U)
451         return 0;
452       // We want 8x% to 9x% free bytes (the larger the block, the lower the %).
453       if ((BytesInFreeList * 100U) / Region->AllocatedUser <
454           (100U - 1U - BlockSize / 16U))
455         return 0;
456     }
457 
458     if (!Force) {
459       const s32 IntervalMs = atomic_load_relaxed(&ReleaseToOsIntervalMs);
460       if (IntervalMs < 0)
461         return 0;
462       if (Region->ReleaseInfo.LastReleaseAtNs +
463               static_cast<u64>(IntervalMs) * 1000000 >
464           getMonotonicTime()) {
465         return 0; // Memory was returned recently.
466       }
467     }
468 
469     ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
470     const uptr CompactPtrBase = getCompactPtrBaseByClassId(ClassId);
471     auto DecompactPtr = [CompactPtrBase](CompactPtrT CompactPtr) {
472       return decompactPtrInternal(CompactPtrBase, CompactPtr);
473     };
474     auto SkipRegion = [](UNUSED uptr RegionIndex) { return false; };
475     releaseFreeMemoryToOS(Region->FreeList, Region->AllocatedUser, 1U,
476                           BlockSize, &Recorder, DecompactPtr, SkipRegion);
477 
478     if (Recorder.getReleasedRangesCount() > 0) {
479       Region->ReleaseInfo.PushedBlocksAtLastRelease =
480           Region->Stats.PushedBlocks;
481       Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
482       Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
483     }
484     Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
485     return Recorder.getReleasedBytes();
486   }
487 };
488 
489 } // namespace scudo
490 
491 #endif // SCUDO_PRIMARY64_H_
492