1 //===-- secondary.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_SECONDARY_H_
10 #define SCUDO_SECONDARY_H_
11
12 #include "common.h"
13 #include "list.h"
14 #include "mutex.h"
15 #include "stats.h"
16 #include "string_utils.h"
17
18 namespace scudo {
19
20 // This allocator wraps the platform allocation primitives, and as such is on
21 // the slower side and should preferably be used for larger sized allocations.
22 // Blocks allocated will be preceded and followed by a guard page, and hold
23 // their own header that is not checksummed: the guard pages and the Combined
24 // header should be enough for our purpose.
25
26 namespace LargeBlock {
27
28 struct Header {
29 LargeBlock::Header *Prev;
30 LargeBlock::Header *Next;
31 uptr BlockEnd;
32 uptr MapBase;
33 uptr MapSize;
34 MapPlatformData Data;
35 };
36
getHeaderSize()37 constexpr uptr getHeaderSize() {
38 return roundUpTo(sizeof(Header), 1U << SCUDO_MIN_ALIGNMENT_LOG);
39 }
40
getHeader(uptr Ptr)41 static Header *getHeader(uptr Ptr) {
42 return reinterpret_cast<Header *>(Ptr - getHeaderSize());
43 }
44
getHeader(const void * Ptr)45 static Header *getHeader(const void *Ptr) {
46 return getHeader(reinterpret_cast<uptr>(Ptr));
47 }
48
49 } // namespace LargeBlock
50
51 class MapAllocatorNoCache {
52 public:
initLinkerInitialized(UNUSED s32 ReleaseToOsInterval)53 void initLinkerInitialized(UNUSED s32 ReleaseToOsInterval) {}
init(UNUSED s32 ReleaseToOsInterval)54 void init(UNUSED s32 ReleaseToOsInterval) {}
retrieve(UNUSED uptr Size,UNUSED LargeBlock::Header ** H)55 bool retrieve(UNUSED uptr Size, UNUSED LargeBlock::Header **H) {
56 return false;
57 }
store(UNUSED LargeBlock::Header * H)58 bool store(UNUSED LargeBlock::Header *H) { return false; }
canCache(UNUSED uptr Size)59 static bool canCache(UNUSED uptr Size) { return false; }
disable()60 void disable() {}
enable()61 void enable() {}
releaseToOS()62 void releaseToOS() {}
setReleaseToOsIntervalMs(UNUSED s32 Interval)63 void setReleaseToOsIntervalMs(UNUSED s32 Interval) {}
64 };
65
66 template <uptr MaxEntriesCount = 32U, uptr MaxEntrySize = 1UL << 19,
67 s32 MinReleaseToOsIntervalMs = INT32_MIN,
68 s32 MaxReleaseToOsIntervalMs = INT32_MAX>
69 class MapAllocatorCache {
70 public:
71 // Fuchsia doesn't allow releasing Secondary blocks yet. Note that 0 length
72 // arrays are an extension for some compilers.
73 // FIXME(kostyak): support (partially) the cache on Fuchsia.
74 static_assert(!SCUDO_FUCHSIA || MaxEntriesCount == 0U, "");
75
initLinkerInitialized(s32 ReleaseToOsInterval)76 void initLinkerInitialized(s32 ReleaseToOsInterval) {
77 setReleaseToOsIntervalMs(ReleaseToOsInterval);
78 }
init(s32 ReleaseToOsInterval)79 void init(s32 ReleaseToOsInterval) {
80 memset(this, 0, sizeof(*this));
81 initLinkerInitialized(ReleaseToOsInterval);
82 }
83
store(LargeBlock::Header * H)84 bool store(LargeBlock::Header *H) {
85 bool EntryCached = false;
86 bool EmptyCache = false;
87 const u64 Time = getMonotonicTime();
88 {
89 ScopedLock L(Mutex);
90 if (EntriesCount == MaxEntriesCount) {
91 if (IsFullEvents++ == 4U)
92 EmptyCache = true;
93 } else {
94 for (uptr I = 0; I < MaxEntriesCount; I++) {
95 if (Entries[I].Block)
96 continue;
97 if (I != 0)
98 Entries[I] = Entries[0];
99 Entries[0].Block = reinterpret_cast<uptr>(H);
100 Entries[0].BlockEnd = H->BlockEnd;
101 Entries[0].MapBase = H->MapBase;
102 Entries[0].MapSize = H->MapSize;
103 Entries[0].Data = H->Data;
104 Entries[0].Time = Time;
105 EntriesCount++;
106 EntryCached = true;
107 break;
108 }
109 }
110 }
111 s32 Interval;
112 if (EmptyCache)
113 empty();
114 else if ((Interval = getReleaseToOsIntervalMs()) >= 0)
115 releaseOlderThan(Time - static_cast<u64>(Interval) * 1000000);
116 return EntryCached;
117 }
118
retrieve(uptr Size,LargeBlock::Header ** H)119 bool retrieve(uptr Size, LargeBlock::Header **H) {
120 const uptr PageSize = getPageSizeCached();
121 ScopedLock L(Mutex);
122 if (EntriesCount == 0)
123 return false;
124 for (uptr I = 0; I < MaxEntriesCount; I++) {
125 if (!Entries[I].Block)
126 continue;
127 const uptr BlockSize = Entries[I].BlockEnd - Entries[I].Block;
128 if (Size > BlockSize)
129 continue;
130 if (Size < BlockSize - PageSize * 4U)
131 continue;
132 *H = reinterpret_cast<LargeBlock::Header *>(Entries[I].Block);
133 Entries[I].Block = 0;
134 (*H)->BlockEnd = Entries[I].BlockEnd;
135 (*H)->MapBase = Entries[I].MapBase;
136 (*H)->MapSize = Entries[I].MapSize;
137 (*H)->Data = Entries[I].Data;
138 EntriesCount--;
139 return true;
140 }
141 return false;
142 }
143
canCache(uptr Size)144 static bool canCache(uptr Size) {
145 return MaxEntriesCount != 0U && Size <= MaxEntrySize;
146 }
147
setReleaseToOsIntervalMs(s32 Interval)148 void setReleaseToOsIntervalMs(s32 Interval) {
149 if (Interval >= MaxReleaseToOsIntervalMs) {
150 Interval = MaxReleaseToOsIntervalMs;
151 } else if (Interval <= MinReleaseToOsIntervalMs) {
152 Interval = MinReleaseToOsIntervalMs;
153 }
154 atomic_store(&ReleaseToOsIntervalMs, Interval, memory_order_relaxed);
155 }
156
releaseToOS()157 void releaseToOS() { releaseOlderThan(UINT64_MAX); }
158
disable()159 void disable() { Mutex.lock(); }
160
enable()161 void enable() { Mutex.unlock(); }
162
163 private:
empty()164 void empty() {
165 struct {
166 void *MapBase;
167 uptr MapSize;
168 MapPlatformData Data;
169 } MapInfo[MaxEntriesCount];
170 uptr N = 0;
171 {
172 ScopedLock L(Mutex);
173 for (uptr I = 0; I < MaxEntriesCount; I++) {
174 if (!Entries[I].Block)
175 continue;
176 MapInfo[N].MapBase = reinterpret_cast<void *>(Entries[I].MapBase);
177 MapInfo[N].MapSize = Entries[I].MapSize;
178 MapInfo[N].Data = Entries[I].Data;
179 Entries[I].Block = 0;
180 N++;
181 }
182 EntriesCount = 0;
183 IsFullEvents = 0;
184 }
185 for (uptr I = 0; I < N; I++)
186 unmap(MapInfo[I].MapBase, MapInfo[I].MapSize, UNMAP_ALL,
187 &MapInfo[I].Data);
188 }
189
releaseOlderThan(u64 Time)190 void releaseOlderThan(u64 Time) {
191 ScopedLock L(Mutex);
192 if (!EntriesCount)
193 return;
194 for (uptr I = 0; I < MaxEntriesCount; I++) {
195 if (!Entries[I].Block || !Entries[I].Time || Entries[I].Time > Time)
196 continue;
197 releasePagesToOS(Entries[I].Block, 0,
198 Entries[I].BlockEnd - Entries[I].Block,
199 &Entries[I].Data);
200 Entries[I].Time = 0;
201 }
202 }
203
getReleaseToOsIntervalMs()204 s32 getReleaseToOsIntervalMs() {
205 return atomic_load(&ReleaseToOsIntervalMs, memory_order_relaxed);
206 }
207
208 struct CachedBlock {
209 uptr Block;
210 uptr BlockEnd;
211 uptr MapBase;
212 uptr MapSize;
213 MapPlatformData Data;
214 u64 Time;
215 };
216
217 HybridMutex Mutex;
218 CachedBlock Entries[MaxEntriesCount];
219 u32 EntriesCount;
220 uptr LargestSize;
221 u32 IsFullEvents;
222 atomic_s32 ReleaseToOsIntervalMs;
223 };
224
225 template <class CacheT> class MapAllocator {
226 public:
227 void initLinkerInitialized(GlobalStats *S, s32 ReleaseToOsInterval = -1) {
228 Cache.initLinkerInitialized(ReleaseToOsInterval);
229 Stats.initLinkerInitialized();
230 if (LIKELY(S))
231 S->link(&Stats);
232 }
233 void init(GlobalStats *S, s32 ReleaseToOsInterval = -1) {
234 memset(this, 0, sizeof(*this));
235 initLinkerInitialized(S, ReleaseToOsInterval);
236 }
237
238 void *allocate(uptr Size, uptr AlignmentHint = 0, uptr *BlockEnd = nullptr,
239 FillContentsMode FillContents = NoFill);
240
241 void deallocate(void *Ptr);
242
getBlockEnd(void * Ptr)243 static uptr getBlockEnd(void *Ptr) {
244 return LargeBlock::getHeader(Ptr)->BlockEnd;
245 }
246
getBlockSize(void * Ptr)247 static uptr getBlockSize(void *Ptr) {
248 return getBlockEnd(Ptr) - reinterpret_cast<uptr>(Ptr);
249 }
250
251 void getStats(ScopedString *Str) const;
252
disable()253 void disable() {
254 Mutex.lock();
255 Cache.disable();
256 }
257
enable()258 void enable() {
259 Cache.enable();
260 Mutex.unlock();
261 }
262
iterateOverBlocks(F Callback)263 template <typename F> void iterateOverBlocks(F Callback) const {
264 for (const auto &H : InUseBlocks)
265 Callback(reinterpret_cast<uptr>(&H) + LargeBlock::getHeaderSize());
266 }
267
canCache(uptr Size)268 static uptr canCache(uptr Size) { return CacheT::canCache(Size); }
269
setReleaseToOsIntervalMs(s32 Interval)270 void setReleaseToOsIntervalMs(s32 Interval) {
271 Cache.setReleaseToOsIntervalMs(Interval);
272 }
273
releaseToOS()274 void releaseToOS() { Cache.releaseToOS(); }
275
276 private:
277 CacheT Cache;
278
279 HybridMutex Mutex;
280 DoublyLinkedList<LargeBlock::Header> InUseBlocks;
281 uptr AllocatedBytes;
282 uptr FreedBytes;
283 uptr LargestSize;
284 u32 NumberOfAllocs;
285 u32 NumberOfFrees;
286 LocalStats Stats;
287 };
288
289 // As with the Primary, the size passed to this function includes any desired
290 // alignment, so that the frontend can align the user allocation. The hint
291 // parameter allows us to unmap spurious memory when dealing with larger
292 // (greater than a page) alignments on 32-bit platforms.
293 // Due to the sparsity of address space available on those platforms, requesting
294 // an allocation from the Secondary with a large alignment would end up wasting
295 // VA space (even though we are not committing the whole thing), hence the need
296 // to trim off some of the reserved space.
297 // For allocations requested with an alignment greater than or equal to a page,
298 // the committed memory will amount to something close to Size - AlignmentHint
299 // (pending rounding and headers).
300 template <class CacheT>
allocate(uptr Size,uptr AlignmentHint,uptr * BlockEnd,FillContentsMode FillContents)301 void *MapAllocator<CacheT>::allocate(uptr Size, uptr AlignmentHint,
302 uptr *BlockEnd,
303 FillContentsMode FillContents) {
304 DCHECK_GE(Size, AlignmentHint);
305 const uptr PageSize = getPageSizeCached();
306 const uptr RoundedSize =
307 roundUpTo(Size + LargeBlock::getHeaderSize(), PageSize);
308
309 if (AlignmentHint < PageSize && CacheT::canCache(RoundedSize)) {
310 LargeBlock::Header *H;
311 if (Cache.retrieve(RoundedSize, &H)) {
312 if (BlockEnd)
313 *BlockEnd = H->BlockEnd;
314 void *Ptr = reinterpret_cast<void *>(reinterpret_cast<uptr>(H) +
315 LargeBlock::getHeaderSize());
316 if (FillContents)
317 memset(Ptr, FillContents == ZeroFill ? 0 : PatternFillByte,
318 H->BlockEnd - reinterpret_cast<uptr>(Ptr));
319 const uptr BlockSize = H->BlockEnd - reinterpret_cast<uptr>(H);
320 {
321 ScopedLock L(Mutex);
322 InUseBlocks.push_back(H);
323 AllocatedBytes += BlockSize;
324 NumberOfAllocs++;
325 Stats.add(StatAllocated, BlockSize);
326 Stats.add(StatMapped, H->MapSize);
327 }
328 return Ptr;
329 }
330 }
331
332 MapPlatformData Data = {};
333 const uptr MapSize = RoundedSize + 2 * PageSize;
334 uptr MapBase =
335 reinterpret_cast<uptr>(map(nullptr, MapSize, "scudo:secondary",
336 MAP_NOACCESS | MAP_ALLOWNOMEM, &Data));
337 if (UNLIKELY(!MapBase))
338 return nullptr;
339 uptr CommitBase = MapBase + PageSize;
340 uptr MapEnd = MapBase + MapSize;
341
342 // In the unlikely event of alignments larger than a page, adjust the amount
343 // of memory we want to commit, and trim the extra memory.
344 if (UNLIKELY(AlignmentHint >= PageSize)) {
345 // For alignments greater than or equal to a page, the user pointer (eg: the
346 // pointer that is returned by the C or C++ allocation APIs) ends up on a
347 // page boundary , and our headers will live in the preceding page.
348 CommitBase = roundUpTo(MapBase + PageSize + 1, AlignmentHint) - PageSize;
349 const uptr NewMapBase = CommitBase - PageSize;
350 DCHECK_GE(NewMapBase, MapBase);
351 // We only trim the extra memory on 32-bit platforms: 64-bit platforms
352 // are less constrained memory wise, and that saves us two syscalls.
353 if (SCUDO_WORDSIZE == 32U && NewMapBase != MapBase) {
354 unmap(reinterpret_cast<void *>(MapBase), NewMapBase - MapBase, 0, &Data);
355 MapBase = NewMapBase;
356 }
357 const uptr NewMapEnd = CommitBase + PageSize +
358 roundUpTo((Size - AlignmentHint), PageSize) +
359 PageSize;
360 DCHECK_LE(NewMapEnd, MapEnd);
361 if (SCUDO_WORDSIZE == 32U && NewMapEnd != MapEnd) {
362 unmap(reinterpret_cast<void *>(NewMapEnd), MapEnd - NewMapEnd, 0, &Data);
363 MapEnd = NewMapEnd;
364 }
365 }
366
367 const uptr CommitSize = MapEnd - PageSize - CommitBase;
368 const uptr Ptr =
369 reinterpret_cast<uptr>(map(reinterpret_cast<void *>(CommitBase),
370 CommitSize, "scudo:secondary", 0, &Data));
371 LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(Ptr);
372 H->MapBase = MapBase;
373 H->MapSize = MapEnd - MapBase;
374 H->BlockEnd = CommitBase + CommitSize;
375 H->Data = Data;
376 if (BlockEnd)
377 *BlockEnd = CommitBase + CommitSize;
378 {
379 ScopedLock L(Mutex);
380 InUseBlocks.push_back(H);
381 AllocatedBytes += CommitSize;
382 if (LargestSize < CommitSize)
383 LargestSize = CommitSize;
384 NumberOfAllocs++;
385 Stats.add(StatAllocated, CommitSize);
386 Stats.add(StatMapped, H->MapSize);
387 }
388 return reinterpret_cast<void *>(Ptr + LargeBlock::getHeaderSize());
389 }
390
deallocate(void * Ptr)391 template <class CacheT> void MapAllocator<CacheT>::deallocate(void *Ptr) {
392 LargeBlock::Header *H = LargeBlock::getHeader(Ptr);
393 const uptr Block = reinterpret_cast<uptr>(H);
394 const uptr CommitSize = H->BlockEnd - Block;
395 {
396 ScopedLock L(Mutex);
397 InUseBlocks.remove(H);
398 FreedBytes += CommitSize;
399 NumberOfFrees++;
400 Stats.sub(StatAllocated, CommitSize);
401 Stats.sub(StatMapped, H->MapSize);
402 }
403 if (CacheT::canCache(CommitSize) && Cache.store(H))
404 return;
405 void *Addr = reinterpret_cast<void *>(H->MapBase);
406 const uptr Size = H->MapSize;
407 MapPlatformData Data = H->Data;
408 unmap(Addr, Size, UNMAP_ALL, &Data);
409 }
410
411 template <class CacheT>
getStats(ScopedString * Str)412 void MapAllocator<CacheT>::getStats(ScopedString *Str) const {
413 Str->append(
414 "Stats: MapAllocator: allocated %zu times (%zuK), freed %zu times "
415 "(%zuK), remains %zu (%zuK) max %zuM\n",
416 NumberOfAllocs, AllocatedBytes >> 10, NumberOfFrees, FreedBytes >> 10,
417 NumberOfAllocs - NumberOfFrees, (AllocatedBytes - FreedBytes) >> 10,
418 LargestSize >> 20);
419 }
420
421 } // namespace scudo
422
423 #endif // SCUDO_SECONDARY_H_
424