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 if 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    // The BatchClassId must be locked last since other classes can use it.
129    for (sptr I = static_cast<sptr>(NumClasses) - 1; I >= 0; I--) {
130      if (static_cast<uptr>(I) == SizeClassMap::BatchClassId)
131        continue;
132      getRegionInfo(static_cast<uptr>(I))->Mutex.lock();
133    }
134    getRegionInfo(SizeClassMap::BatchClassId)->Mutex.lock();
135  }
136
137  void enable() {
138    getRegionInfo(SizeClassMap::BatchClassId)->Mutex.unlock();
139    for (uptr I = 0; I < NumClasses; I++) {
140      if (I == SizeClassMap::BatchClassId)
141        continue;
142      getRegionInfo(I)->Mutex.unlock();
143    }
144  }
145
146  template <typename F> void iterateOverBlocks(F Callback) const {
147    for (uptr I = 0; I < NumClasses; I++) {
148      if (I == SizeClassMap::BatchClassId)
149        continue;
150      const RegionInfo *Region = getRegionInfo(I);
151      const uptr BlockSize = getSizeByClassId(I);
152      const uptr From = Region->RegionBeg;
153      const uptr To = From + Region->AllocatedUser;
154      for (uptr Block = From; Block < To; Block += BlockSize)
155        Callback(Block);
156    }
157  }
158
159  void getStats(ScopedString *Str) const {
160    // TODO(kostyak): get the RSS per region.
161    uptr TotalMapped = 0;
162    uptr PoppedBlocks = 0;
163    uptr PushedBlocks = 0;
164    for (uptr I = 0; I < NumClasses; I++) {
165      RegionInfo *Region = getRegionInfo(I);
166      if (Region->MappedUser)
167        TotalMapped += Region->MappedUser;
168      PoppedBlocks += Region->Stats.PoppedBlocks;
169      PushedBlocks += Region->Stats.PushedBlocks;
170    }
171    Str->append("Stats: SizeClassAllocator64: %zuM mapped (%zuM rss) in %zu "
172                "allocations; remains %zu\n",
173                TotalMapped >> 20, 0, PoppedBlocks,
174                PoppedBlocks - PushedBlocks);
175
176    for (uptr I = 0; I < NumClasses; I++)
177      getStats(Str, I, 0);
178  }
179
180  uptr releaseToOS() {
181    uptr TotalReleasedBytes = 0;
182    for (uptr I = 0; I < NumClasses; I++) {
183      if (I == SizeClassMap::BatchClassId)
184        continue;
185      RegionInfo *Region = getRegionInfo(I);
186      ScopedLock L(Region->Mutex);
187      TotalReleasedBytes += releaseToOSMaybe(Region, I, /*Force=*/true);
188    }
189    return TotalReleasedBytes;
190  }
191
192private:
193  static const uptr RegionSize = 1UL << RegionSizeLog;
194  static const uptr NumClasses = SizeClassMap::NumClasses;
195  static const uptr PrimarySize = RegionSize * NumClasses;
196
197  // Call map for user memory with at least this size.
198  static const uptr MapSizeIncrement = 1UL << 17;
199  // Fill at most this number of batches from the newly map'd memory.
200  static const u32 MaxNumBatches = 8U;
201
202  struct RegionStats {
203    uptr PoppedBlocks;
204    uptr PushedBlocks;
205  };
206
207  struct ReleaseToOsInfo {
208    uptr PushedBlocksAtLastRelease;
209    uptr RangesReleased;
210    uptr LastReleasedBytes;
211    u64 LastReleaseAtNs;
212  };
213
214  struct ALIGNED(SCUDO_CACHE_LINE_SIZE) RegionInfo {
215    HybridMutex Mutex;
216    SinglyLinkedList<TransferBatch> FreeList;
217    RegionStats Stats;
218    bool CanRelease;
219    bool Exhausted;
220    u32 RandState;
221    uptr RegionBeg;
222    uptr MappedUser;    // Bytes mapped for user memory.
223    uptr AllocatedUser; // Bytes allocated for user memory.
224    MapPlatformData Data;
225    ReleaseToOsInfo ReleaseInfo;
226  };
227  static_assert(sizeof(RegionInfo) % SCUDO_CACHE_LINE_SIZE == 0, "");
228
229  uptr PrimaryBase;
230  RegionInfo *RegionInfoArray;
231  MapPlatformData Data;
232  s32 ReleaseToOsIntervalMs;
233
234  RegionInfo *getRegionInfo(uptr ClassId) const {
235    DCHECK_LT(ClassId, NumClasses);
236    return &RegionInfoArray[ClassId];
237  }
238
239  uptr getRegionBaseByClassId(uptr ClassId) const {
240    return PrimaryBase + (ClassId << RegionSizeLog);
241  }
242
243  bool populateBatches(CacheT *C, RegionInfo *Region, uptr ClassId,
244                       TransferBatch **CurrentBatch, u32 MaxCount,
245                       void **PointersArray, u32 Count) {
246    // No need to shuffle the batches size class.
247    if (ClassId != SizeClassMap::BatchClassId)
248      shuffle(PointersArray, Count, &Region->RandState);
249    TransferBatch *B = *CurrentBatch;
250    for (uptr I = 0; I < Count; I++) {
251      if (B && B->getCount() == MaxCount) {
252        Region->FreeList.push_back(B);
253        B = nullptr;
254      }
255      if (!B) {
256        B = C->createBatch(ClassId, PointersArray[I]);
257        if (UNLIKELY(!B))
258          return false;
259        B->clear();
260      }
261      B->add(PointersArray[I]);
262    }
263    *CurrentBatch = B;
264    return true;
265  }
266
267  NOINLINE TransferBatch *populateFreeList(CacheT *C, uptr ClassId,
268                                           RegionInfo *Region) {
269    const uptr Size = getSizeByClassId(ClassId);
270    const u32 MaxCount = TransferBatch::getMaxCached(Size);
271
272    const uptr RegionBeg = Region->RegionBeg;
273    const uptr MappedUser = Region->MappedUser;
274    const uptr TotalUserBytes = Region->AllocatedUser + MaxCount * Size;
275    // Map more space for blocks, if necessary.
276    if (TotalUserBytes > MappedUser) {
277      // Do the mmap for the user memory.
278      const uptr UserMapSize =
279          roundUpTo(TotalUserBytes - MappedUser, MapSizeIncrement);
280      const uptr RegionBase = RegionBeg - getRegionBaseByClassId(ClassId);
281      if (UNLIKELY(RegionBase + MappedUser + UserMapSize > RegionSize)) {
282        if (!Region->Exhausted) {
283          Region->Exhausted = true;
284          ScopedString Str(1024);
285          getStats(&Str);
286          Str.append(
287              "Scudo OOM: The process has Exhausted %zuM for size class %zu.\n",
288              RegionSize >> 20, Size);
289          Str.output();
290        }
291        return nullptr;
292      }
293      if (UNLIKELY(MappedUser == 0))
294        Region->Data = Data;
295      if (UNLIKELY(!map(reinterpret_cast<void *>(RegionBeg + MappedUser),
296                        UserMapSize, "scudo:primary",
297                        MAP_ALLOWNOMEM | MAP_RESIZABLE, &Region->Data)))
298        return nullptr;
299      Region->MappedUser += UserMapSize;
300      C->getStats().add(StatMapped, UserMapSize);
301    }
302
303    const u32 NumberOfBlocks = Min(
304        MaxNumBatches * MaxCount,
305        static_cast<u32>((Region->MappedUser - Region->AllocatedUser) / Size));
306    DCHECK_GT(NumberOfBlocks, 0);
307
308    TransferBatch *B = nullptr;
309    constexpr u32 ShuffleArraySize =
310        MaxNumBatches * TransferBatch::MaxNumCached;
311    void *ShuffleArray[ShuffleArraySize];
312    u32 Count = 0;
313    const uptr P = RegionBeg + Region->AllocatedUser;
314    const uptr AllocatedUser = Size * NumberOfBlocks;
315    for (uptr I = P; I < P + AllocatedUser; I += Size) {
316      ShuffleArray[Count++] = reinterpret_cast<void *>(I);
317      if (Count == ShuffleArraySize) {
318        if (UNLIKELY(!populateBatches(C, Region, ClassId, &B, MaxCount,
319                                      ShuffleArray, Count)))
320          return nullptr;
321        Count = 0;
322      }
323    }
324    if (Count) {
325      if (UNLIKELY(!populateBatches(C, Region, ClassId, &B, MaxCount,
326                                    ShuffleArray, Count)))
327        return nullptr;
328    }
329    DCHECK(B);
330    if (!Region->FreeList.empty()) {
331      Region->FreeList.push_back(B);
332      B = Region->FreeList.front();
333      Region->FreeList.pop_front();
334    }
335    DCHECK_GT(B->getCount(), 0);
336
337    C->getStats().add(StatFree, AllocatedUser);
338    Region->AllocatedUser += AllocatedUser;
339    Region->Exhausted = false;
340    if (Region->CanRelease)
341      Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
342
343    return B;
344  }
345
346  void getStats(ScopedString *Str, uptr ClassId, uptr Rss) const {
347    RegionInfo *Region = getRegionInfo(ClassId);
348    if (Region->MappedUser == 0)
349      return;
350    const uptr InUse = Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks;
351    const uptr TotalChunks = Region->AllocatedUser / getSizeByClassId(ClassId);
352    Str->append("%s %02zu (%6zu): mapped: %6zuK popped: %7zu pushed: %7zu "
353                "inuse: %6zu total: %6zu rss: %6zuK releases: %6zu last "
354                "released: %6zuK region: 0x%zx (0x%zx)\n",
355                Region->Exhausted ? "F" : " ", ClassId,
356                getSizeByClassId(ClassId), Region->MappedUser >> 10,
357                Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks, InUse,
358                TotalChunks, Rss >> 10, Region->ReleaseInfo.RangesReleased,
359                Region->ReleaseInfo.LastReleasedBytes >> 10, Region->RegionBeg,
360                getRegionBaseByClassId(ClassId));
361  }
362
363  NOINLINE uptr releaseToOSMaybe(RegionInfo *Region, uptr ClassId,
364                                 bool Force = false) {
365    const uptr BlockSize = getSizeByClassId(ClassId);
366    const uptr PageSize = getPageSizeCached();
367
368    CHECK_GE(Region->Stats.PoppedBlocks, Region->Stats.PushedBlocks);
369    const uptr BytesInFreeList =
370        Region->AllocatedUser -
371        (Region->Stats.PoppedBlocks - Region->Stats.PushedBlocks) * BlockSize;
372    if (BytesInFreeList < PageSize)
373      return 0; // No chance to release anything.
374    if ((Region->Stats.PushedBlocks -
375         Region->ReleaseInfo.PushedBlocksAtLastRelease) *
376            BlockSize <
377        PageSize) {
378      return 0; // Nothing new to release.
379    }
380
381    if (!Force) {
382      const s32 IntervalMs = ReleaseToOsIntervalMs;
383      if (IntervalMs < 0)
384        return 0;
385      if (Region->ReleaseInfo.LastReleaseAtNs +
386              static_cast<uptr>(IntervalMs) * 1000000ULL >
387          getMonotonicTime()) {
388        return 0; // Memory was returned recently.
389      }
390    }
391
392    ReleaseRecorder Recorder(Region->RegionBeg, &Region->Data);
393    releaseFreeMemoryToOS(Region->FreeList, Region->RegionBeg,
394                          roundUpTo(Region->AllocatedUser, PageSize) / PageSize,
395                          BlockSize, &Recorder);
396
397    if (Recorder.getReleasedRangesCount() > 0) {
398      Region->ReleaseInfo.PushedBlocksAtLastRelease =
399          Region->Stats.PushedBlocks;
400      Region->ReleaseInfo.RangesReleased += Recorder.getReleasedRangesCount();
401      Region->ReleaseInfo.LastReleasedBytes = Recorder.getReleasedBytes();
402    }
403    Region->ReleaseInfo.LastReleaseAtNs = getMonotonicTime();
404    return Recorder.getReleasedBytes();
405  }
406};
407
408} // namespace scudo
409
410#endif // SCUDO_PRIMARY64_H_
411