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#ifndef __STDC_FORMAT_MACROS
13// Ensure PRId64 macro is available
14#define __STDC_FORMAT_MACROS 1
15#endif
16#include <inttypes.h>
17
18#include "chunk.h"
19#include "common.h"
20#include "list.h"
21#include "mem_map.h"
22#include "memtag.h"
23#include "mutex.h"
24#include "options.h"
25#include "stats.h"
26#include "string_utils.h"
27#include "thread_annotations.h"
28#include "tracing.h"
29#include "vector.h"
30
31namespace scudo {
32
33// This allocator wraps the platform allocation primitives, and as such is on
34// the slower side and should preferably be used for larger sized allocations.
35// Blocks allocated will be preceded and followed by a guard page, and hold
36// their own header that is not checksummed: the guard pages and the Combined
37// header should be enough for our purpose.
38
39namespace LargeBlock {
40
41struct alignas(Max<uptr>(A: archSupportsMemoryTagging()
42 ? archMemoryTagGranuleSize()
43 : 1,
44 B: 1U << SCUDO_MIN_ALIGNMENT_LOG)) Header {
45 LargeBlock::Header *Prev;
46 LargeBlock::Header *Next;
47 uptr CommitBase;
48 uptr CommitSize;
49 MemMapT MemMap;
50};
51
52static_assert(sizeof(Header) % (1U << SCUDO_MIN_ALIGNMENT_LOG) == 0, "");
53static_assert(!archSupportsMemoryTagging() ||
54 sizeof(Header) % archMemoryTagGranuleSize() == 0,
55 "");
56
57constexpr uptr getHeaderSize() { return sizeof(Header); }
58
59template <typename Config> static uptr addHeaderTag(uptr Ptr) {
60 if (allocatorSupportsMemoryTagging<Config>())
61 return addFixedTag(Ptr, Tag: 1);
62 return Ptr;
63}
64
65template <typename Config> static Header *getHeader(uptr Ptr) {
66 return reinterpret_cast<Header *>(addHeaderTag<Config>(Ptr)) - 1;
67}
68
69template <typename Config> static Header *getHeader(const void *Ptr) {
70 return getHeader<Config>(reinterpret_cast<uptr>(Ptr));
71}
72
73} // namespace LargeBlock
74
75static inline void unmap(MemMapT &MemMap) { MemMap.unmap(); }
76
77namespace {
78
79struct CachedBlock {
80 static constexpr u16 CacheIndexMax = UINT16_MAX;
81 static constexpr u16 EndOfListVal = CacheIndexMax;
82
83 // We allow a certain amount of fragmentation and part of the fragmented bytes
84 // will be released by `releaseAndZeroPagesToOS()`. This increases the chance
85 // of cache hit rate and reduces the overhead to the RSS at the same time. See
86 // more details in the `MapAllocatorCache::retrieve()` section.
87 //
88 // We arrived at this default value after noticing that mapping in larger
89 // memory regions performs better than releasing memory and forcing a cache
90 // hit. According to the data, it suggests that beyond 4 pages, the release
91 // execution time is longer than the map execution time. In this way,
92 // the default is dependent on the platform.
93 static constexpr uptr MaxReleasedCachePages = 4U;
94
95 uptr CommitBase = 0;
96 uptr CommitSize = 0;
97 uptr BlockBegin = 0;
98 MemMapT MemMap = {};
99 u64 Time = 0;
100 u16 Next = 0;
101 u16 Prev = 0;
102
103 enum CacheFlags : u16 {
104 None = 0,
105 NoAccess = 0x1,
106 };
107 CacheFlags Flags = CachedBlock::None;
108
109 bool isValid() { return CommitBase != 0; }
110
111 void invalidate() { CommitBase = 0; }
112};
113} // namespace
114
115template <typename Config> class MapAllocatorNoCache {
116public:
117 void init(UNUSED s32 ReleaseToOsInterval) {}
118 CachedBlock retrieve(UNUSED uptr MaxAllowedFragmentedBytes, UNUSED uptr Size,
119 UNUSED uptr Alignment, UNUSED uptr HeadersSize,
120 UNUSED uptr &EntryHeaderPos) {
121 return {};
122 }
123 void store(UNUSED Options Options, UNUSED uptr CommitBase,
124 UNUSED uptr CommitSize, UNUSED uptr BlockBegin,
125 UNUSED MemMapT MemMap) {
126 // This should never be called since canCache always returns false.
127 UNREACHABLE(
128 "It is not valid to call store on MapAllocatorNoCache objects.");
129 }
130
131 bool canCache(UNUSED uptr Size) { return false; }
132 void disable() {}
133 void enable() {}
134 void releaseToOS(ReleaseToOS) {}
135 void disableMemoryTagging() {}
136 void unmapTestOnly() {}
137 bool setOption(Option O, UNUSED sptr Value) {
138 if (O == Option::ReleaseInterval || O == Option::MaxCacheEntriesCount ||
139 O == Option::MaxCacheEntrySize)
140 return false;
141 // Not supported by the Secondary Cache, but not an error either.
142 return true;
143 }
144
145 void getStats(UNUSED ScopedString *Str) {
146 Str->append(Format: "Secondary Cache Disabled\n");
147 }
148};
149
150static const uptr MaxUnreleasedCachePages = 4U;
151
152template <typename Config>
153bool mapSecondary(const Options &Options, uptr CommitBase, uptr CommitSize,
154 uptr AllocPos, uptr Flags, MemMapT &MemMap) {
155 Flags |= MAP_RESIZABLE;
156 Flags |= MAP_ALLOWNOMEM;
157
158 const uptr PageSize = getPageSizeCached();
159 if (SCUDO_TRUSTY) {
160 /*
161 * On Trusty we need AllocPos to be usable for shared memory, which cannot
162 * cross multiple mappings. This means we need to split around AllocPos
163 * and not over it. We can only do this if the address is page-aligned.
164 */
165 const uptr TaggedSize = AllocPos - CommitBase;
166 if (useMemoryTagging<Config>(Options) && isAligned(X: TaggedSize, Alignment: PageSize)) {
167 DCHECK_GT(TaggedSize, 0);
168 return MemMap.remap(Addr: CommitBase, Size: TaggedSize, Name: "scudo:secondary",
169 MAP_MEMTAG | Flags) &&
170 MemMap.remap(Addr: AllocPos, Size: CommitSize - TaggedSize, Name: "scudo:secondary",
171 Flags);
172 } else {
173 const uptr RemapFlags =
174 (useMemoryTagging<Config>(Options) ? MAP_MEMTAG : 0) | Flags;
175 return MemMap.remap(Addr: CommitBase, Size: CommitSize, Name: "scudo:secondary",
176 Flags: RemapFlags);
177 }
178 }
179
180 const uptr MaxMteMappedBytes = 2 * PageSize;
181 if (useMemoryTagging<Config>(Options) && CommitSize > MaxMteMappedBytes) {
182 // If the headers cross page boundary then two pages need to be mapped with
183 // PROT_MTE, otherwise a single page is sufficient. We could do the math and
184 // apply PROT_MTE to only one page (likely enough in most scenarios), but if
185 // the chunk is cached then this might not be true for the new allocation
186 // while reusing the chunk. Hence, PROT_MTE is used on two pages always.
187 const uptr UntaggedPos = Max(A: AllocPos, B: CommitBase + MaxMteMappedBytes);
188 return MemMap.remap(Addr: CommitBase, Size: UntaggedPos - CommitBase, Name: "scudo:secondary",
189 MAP_MEMTAG | Flags) &&
190 MemMap.remap(Addr: UntaggedPos, Size: CommitBase + CommitSize - UntaggedPos,
191 Name: "scudo:secondary", Flags);
192 } else {
193 const uptr RemapFlags =
194 (useMemoryTagging<Config>(Options) ? MAP_MEMTAG : 0) | Flags;
195 return MemMap.remap(Addr: CommitBase, Size: CommitSize, Name: "scudo:secondary", Flags: RemapFlags);
196 }
197}
198
199// Template specialization to avoid producing zero-length array
200template <typename T, size_t Size> class NonZeroLengthArray {
201public:
202 T &operator[](uptr Idx) { return values[Idx]; }
203
204private:
205 T values[Size];
206};
207template <typename T> class NonZeroLengthArray<T, 0> {
208public:
209 T &operator[](uptr UNUSED Idx) { UNREACHABLE("Unsupported!"); }
210};
211
212// The default unmap callback is simply scudo::unmap.
213// In testing, a different unmap callback is used to
214// record information about unmaps in the cache
215template <typename Config, void (*unmapCallBack)(MemMapT &) = unmap>
216class MapAllocatorCache {
217public:
218 void getStats(ScopedString *Str) {
219 ScopedLock L(Mutex);
220 Str->append(Format: "Config Stats Secondary: ");
221 Config::getConfigValues(Str);
222 uptr Integral;
223 uptr Fractional;
224 computePercentage(Numerator: SuccessfulRetrieves, Denominator: CallsToRetrieve, Integral: &Integral,
225 Fractional: &Fractional);
226 const s32 Interval = atomic_load_relaxed(A: &ReleaseToOsIntervalMs);
227 Str->append(Format: "Stats: MapAllocatorCache: EntriesCount: %zu, "
228 "MaxEntriesCount: %u, MaxEntrySize: %zu, ReleaseToOsSkips: "
229 "%zu, ReleaseToOsIntervalMs = %d\n",
230 LRUEntries.size(), atomic_load_relaxed(A: &MaxEntriesCount),
231 atomic_load_relaxed(A: &MaxEntrySize),
232 atomic_load_relaxed(A: &ReleaseToOsSkips),
233 Interval >= 0 ? Interval : -1);
234 Str->append(Format: "Stats: CacheRetrievalStats: SuccessRate: %u/%u "
235 "(%zu.%02zu%%)\n",
236 SuccessfulRetrieves, CallsToRetrieve, Integral, Fractional);
237 Str->append(Format: "Cache Entry Info (Most Recent -> Least Recent):\n");
238
239 for (CachedBlock &Entry : LRUEntries) {
240 Str->append(Format: " StartBlockAddress: 0x%zx, EndBlockAddress: 0x%zx, "
241 "BlockSize: %zu%s, Flags: %s",
242 Entry.CommitBase, Entry.CommitBase + Entry.CommitSize,
243 Entry.CommitSize, Entry.Time == 0 ? " [R]" : "",
244 Entry.Flags & CachedBlock::NoAccess ? "NoAccess" : "None");
245 const s64 ResidentPages =
246 Entry.MemMap.getResidentPages(From: Entry.CommitBase, Size: Entry.CommitSize);
247
248 if (ResidentPages >= 0) {
249 Str->append(Format: ", Resident Pages: %" PRId64 "/%zu", ResidentPages,
250 Entry.CommitSize / getPageSizeCached());
251 }
252 Str->append(Format: "\n");
253 }
254 }
255
256 // Ensure the default maximum specified fits the array.
257 static_assert(Config::getDefaultMaxEntriesCount() <=
258 Config::getEntriesArraySize(),
259 "");
260 // Ensure the cache entry array size fits in the LRU list Next and Prev
261 // index fields
262 static_assert(Config::getEntriesArraySize() <= CachedBlock::CacheIndexMax,
263 "Cache entry array is too large to be indexed.");
264
265 void init(s32 ReleaseToOsInterval) NO_THREAD_SAFETY_ANALYSIS {
266 DCHECK_EQ(LRUEntries.size(), 0U);
267 setOption(O: Option::MaxCacheEntriesCount,
268 Value: static_cast<sptr>(Config::getDefaultMaxEntriesCount()));
269 setOption(O: Option::MaxCacheEntrySize,
270 Value: static_cast<sptr>(Config::getDefaultMaxEntrySize()));
271 // The default value in the cache config has the higher priority.
272 if (Config::getDefaultReleaseToOsIntervalMs() != INT32_MIN)
273 ReleaseToOsInterval = Config::getDefaultReleaseToOsIntervalMs();
274 setOption(O: Option::ReleaseInterval, Value: static_cast<sptr>(ReleaseToOsInterval));
275
276 LRUEntries.clear();
277 LRUEntries.init(Base: Entries, BaseSize: sizeof(Entries));
278 OldestPresentEntry = nullptr;
279
280 AvailEntries.clear();
281 AvailEntries.init(Base: Entries, BaseSize: sizeof(Entries));
282 for (u32 I = 0; I < Config::getEntriesArraySize(); I++)
283 AvailEntries.push_back(X: &Entries[I]);
284 }
285
286 void store(const Options &Options, uptr CommitBase, uptr CommitSize,
287 uptr BlockBegin, MemMapT MemMap) EXCLUDES(Mutex) {
288 DCHECK(canCache(CommitSize));
289
290 const s32 Interval = atomic_load_relaxed(A: &ReleaseToOsIntervalMs);
291 u64 Time;
292 CachedBlock Entry;
293
294 Entry.CommitBase = CommitBase;
295 Entry.CommitSize = CommitSize;
296 Entry.BlockBegin = BlockBegin;
297 Entry.MemMap = MemMap;
298 Entry.Time = UINT64_MAX;
299 Entry.Flags = CachedBlock::None;
300
301 bool MemoryTaggingEnabled = useMemoryTagging<Config>(Options);
302 if (MemoryTaggingEnabled) {
303 if (Interval == 0 && !SCUDO_FUCHSIA) {
304 // Release the memory and make it inaccessible at the same time by
305 // creating a new MAP_NOACCESS mapping on top of the existing mapping.
306 // Fuchsia does not support replacing mappings by creating a new mapping
307 // on top so we just do the two syscalls there.
308 Entry.Time = 0;
309 if (!mapSecondary<Config>(Options, Entry.CommitBase, Entry.CommitSize,
310 Entry.CommitBase, MAP_NOACCESS,
311 Entry.MemMap)) {
312 // A mmap failed, unmap and return.
313 unmapCallBack(Entry.MemMap);
314 return;
315 }
316 } else {
317 Entry.MemMap.setMemoryPermission(Addr: Entry.CommitBase, Size: Entry.CommitSize,
318 MAP_NOACCESS);
319 }
320 Entry.Flags = CachedBlock::NoAccess;
321 }
322
323 // Usually only one entry will be evicted from the cache.
324 // Only in the rare event that the cache shrinks in real-time
325 // due to a decrease in the configurable value MaxEntriesCount
326 // will more than one cache entry be evicted.
327 // The vector is used to save the MemMaps of evicted entries so
328 // that the unmap call can be performed outside the lock
329 Vector<MemMapT, 1U> EvictionMemMaps;
330
331 do {
332 ScopedLock L(Mutex);
333
334 // Time must be computed under the lock to ensure
335 // that the LRU cache remains sorted with respect to
336 // time in a multithreaded environment
337 Time = getMonotonicTimeFast();
338 if (Entry.Time != 0)
339 Entry.Time = Time;
340
341 if (MemoryTaggingEnabled && !useMemoryTagging<Config>(Options)) {
342 // If we get here then memory tagging was disabled in between when we
343 // read Options and when we locked Mutex. We can't insert our entry into
344 // the quarantine or the cache because the permissions would be wrong so
345 // just unmap it.
346 unmapCallBack(Entry.MemMap);
347 break;
348 }
349
350 if (!Config::getQuarantineDisabled() && Config::getQuarantineSize()) {
351 QuarantinePos =
352 (QuarantinePos + 1) % Max(Config::getQuarantineSize(), 1u);
353 if (!Quarantine[QuarantinePos].isValid()) {
354 Quarantine[QuarantinePos] = Entry;
355 return;
356 }
357 CachedBlock PrevEntry = Quarantine[QuarantinePos];
358 Quarantine[QuarantinePos] = Entry;
359 Entry = PrevEntry;
360 }
361
362 // All excess entries are evicted from the cache. Note that when
363 // `MaxEntriesCount` is zero, cache storing shouldn't happen and it's
364 // guarded by the `DCHECK(canCache(CommitSize))` above. As a result, we
365 // won't try to pop `LRUEntries` when it's empty.
366 while (LRUEntries.size() >= atomic_load_relaxed(A: &MaxEntriesCount)) {
367 // Save MemMaps of evicted entries to perform unmap outside of lock
368 CachedBlock *Entry = LRUEntries.back();
369 EvictionMemMaps.push_back(Element: Entry->MemMap);
370 remove(Entry);
371 }
372
373 insert(Entry);
374 } while (0);
375
376 for (MemMapT &EvictMemMap : EvictionMemMaps)
377 unmapCallBack(EvictMemMap);
378
379 if (Interval >= 0) {
380 // It is very likely that multiple threads trying to do a release at the
381 // same time will not actually release any extra elements. Therefore,
382 // let any other thread continue, skipping the release.
383 if (Mutex.tryLock()) {
384 SCUDO_SCOPED_TRACE(
385 GetSecondaryReleaseToOSTraceName(ReleaseToOS::Normal));
386
387 releaseOlderThan(ReleaseTime: Time - static_cast<u64>(Interval) * 1000000);
388 Mutex.unlock();
389 } else
390 atomic_fetch_add(A: &ReleaseToOsSkips, V: 1U, MO: memory_order_relaxed);
391 }
392 }
393
394 CachedBlock retrieve(uptr MaxAllowedFragmentedPages, uptr Size,
395 uptr Alignment, uptr HeadersSize, uptr &EntryHeaderPos)
396 EXCLUDES(Mutex) {
397 const uptr PageSize = getPageSizeCached();
398 // 10% of the requested size proved to be the optimal choice for
399 // retrieving cached blocks after testing several options.
400 constexpr u32 FragmentedBytesDivisor = 10;
401 CachedBlock Entry;
402 EntryHeaderPos = 0;
403 {
404 ScopedLock L(Mutex);
405 CallsToRetrieve++;
406 if (LRUEntries.size() == 0)
407 return {};
408 CachedBlock *RetrievedEntry = nullptr;
409 uptr MinDiff = UINTPTR_MAX;
410
411 // Since allocation sizes don't always match cached memory chunk sizes
412 // we allow some memory to be unused (called fragmented bytes). The
413 // amount of unused bytes is exactly EntryHeaderPos - CommitBase.
414 //
415 // CommitBase CommitBase + CommitSize
416 // V V
417 // +---+------------+-----------------+---+
418 // | | | | |
419 // +---+------------+-----------------+---+
420 // ^ ^ ^
421 // Guard EntryHeaderPos Guard-page-end
422 // page-begin
423 //
424 // [EntryHeaderPos, CommitBase + CommitSize) contains the user data as
425 // well as the header metadata. If EntryHeaderPos - CommitBase exceeds
426 // MaxAllowedFragmentedPages * PageSize, the cached memory chunk is
427 // not considered valid for retrieval.
428 for (CachedBlock &Entry : LRUEntries) {
429 const uptr CommitBase = Entry.CommitBase;
430 const uptr CommitSize = Entry.CommitSize;
431 const uptr AllocPos =
432 roundDown(X: CommitBase + CommitSize - Size, Boundary: Alignment);
433 const uptr HeaderPos = AllocPos - HeadersSize;
434 const uptr MaxAllowedFragmentedBytes =
435 MaxAllowedFragmentedPages * PageSize;
436 if (HeaderPos > CommitBase + CommitSize)
437 continue;
438 // TODO: Remove AllocPos > CommitBase + MaxAllowedFragmentedBytes
439 // and replace with Diff > MaxAllowedFragmentedBytes
440 if (HeaderPos < CommitBase ||
441 AllocPos > CommitBase + MaxAllowedFragmentedBytes) {
442 continue;
443 }
444
445 const uptr Diff = roundDown(X: HeaderPos, Boundary: PageSize) - CommitBase;
446
447 // Keep track of the smallest cached block
448 // that is greater than (AllocSize + HeaderSize)
449 if (Diff >= MinDiff)
450 continue;
451
452 MinDiff = Diff;
453 RetrievedEntry = &Entry;
454 EntryHeaderPos = HeaderPos;
455
456 // Immediately use a cached block if its size is close enough to the
457 // requested size
458 const uptr OptimalFitThesholdBytes =
459 (CommitBase + CommitSize - HeaderPos) / FragmentedBytesDivisor;
460 if (Diff <= OptimalFitThesholdBytes)
461 break;
462 }
463
464 if (RetrievedEntry != nullptr) {
465 Entry = *RetrievedEntry;
466 remove(Entry: RetrievedEntry);
467 SuccessfulRetrieves++;
468 }
469 }
470
471 // The difference between the retrieved memory chunk and the request
472 // size is at most MaxAllowedFragmentedPages
473 //
474 // +- MaxAllowedFragmentedPages * PageSize -+
475 // +--------------------------+-------------+
476 // | | |
477 // +--------------------------+-------------+
478 // \ Bytes to be released / ^
479 // |
480 // (may or may not be committed)
481 //
482 // The maximum number of bytes released to the OS is capped by
483 // MaxReleasedCachePages
484 //
485 // TODO : Consider making MaxReleasedCachePages configurable since
486 // the release to OS API can vary across systems.
487 if (Entry.Time != 0) {
488 const uptr FragmentedBytes =
489 roundDown(X: EntryHeaderPos, Boundary: PageSize) - Entry.CommitBase;
490 const uptr MaxUnreleasedCacheBytes = MaxUnreleasedCachePages * PageSize;
491 if (FragmentedBytes > MaxUnreleasedCacheBytes) {
492 const uptr MaxReleasedCacheBytes =
493 CachedBlock::MaxReleasedCachePages * PageSize;
494 uptr BytesToRelease =
495 roundUp(X: Min<uptr>(A: MaxReleasedCacheBytes,
496 B: FragmentedBytes - MaxUnreleasedCacheBytes),
497 Boundary: PageSize);
498 Entry.MemMap.releaseAndZeroPagesToOS(From: Entry.CommitBase, Size: BytesToRelease);
499 }
500 }
501
502 return Entry;
503 }
504
505 bool canCache(uptr Size) {
506 return atomic_load_relaxed(A: &MaxEntriesCount) != 0U &&
507 Size <= atomic_load_relaxed(A: &MaxEntrySize);
508 }
509
510 bool setOption(Option O, sptr Value) {
511 if (O == Option::ReleaseInterval) {
512 const s32 Interval = Max(
513 Min(static_cast<s32>(Value), Config::getMaxReleaseToOsIntervalMs()),
514 Config::getMinReleaseToOsIntervalMs());
515 atomic_store_relaxed(A: &ReleaseToOsIntervalMs, V: Interval);
516 return true;
517 }
518 if (O == Option::MaxCacheEntriesCount) {
519 if (Value < 0)
520 return false;
521 atomic_store_relaxed(
522 &MaxEntriesCount,
523 Min<u32>(static_cast<u32>(Value), Config::getEntriesArraySize()));
524 return true;
525 }
526 if (O == Option::MaxCacheEntrySize) {
527 atomic_store_relaxed(A: &MaxEntrySize, V: static_cast<uptr>(Value));
528 return true;
529 }
530 // Not supported by the Secondary Cache, but not an error either.
531 return true;
532 }
533
534 void releaseToOS([[maybe_unused]] ReleaseToOS ReleaseType) EXCLUDES(Mutex) {
535 SCUDO_SCOPED_TRACE(GetSecondaryReleaseToOSTraceName(ReleaseType));
536
537 if (ReleaseType == ReleaseToOS::ForceFast) {
538 // Never wait for the lock, always move on if there is already
539 // a release operation in progress.
540 if (Mutex.tryLock()) {
541 releaseOlderThan(UINT64_MAX);
542 Mutex.unlock();
543 }
544 } else {
545 // Since this is a request to release everything, always wait for the
546 // lock so that we guarantee all entries are released after this call.
547 ScopedLock L(Mutex);
548 releaseOlderThan(UINT64_MAX);
549 }
550 }
551
552 void disableMemoryTagging() EXCLUDES(Mutex) {
553 if (Config::getQuarantineDisabled())
554 return;
555
556 ScopedLock L(Mutex);
557 for (u32 I = 0; I != Config::getQuarantineSize(); ++I) {
558 if (Quarantine[I].isValid()) {
559 MemMapT &MemMap = Quarantine[I].MemMap;
560 unmapCallBack(MemMap);
561 Quarantine[I].invalidate();
562 }
563 }
564 QuarantinePos = -1U;
565 }
566
567 void disable() NO_THREAD_SAFETY_ANALYSIS { Mutex.lock(); }
568
569 void enable() NO_THREAD_SAFETY_ANALYSIS { Mutex.unlock(); }
570
571 void unmapTestOnly() { empty(); }
572
573 void releaseOlderThanTestOnly(u64 ReleaseTime) {
574 ScopedLock L(Mutex);
575 releaseOlderThan(ReleaseTime);
576 }
577
578private:
579 void insert(const CachedBlock &Entry) REQUIRES(Mutex) {
580 CachedBlock *AvailEntry = AvailEntries.front();
581 AvailEntries.pop_front();
582
583 *AvailEntry = Entry;
584 LRUEntries.push_front(X: AvailEntry);
585 if (OldestPresentEntry == nullptr && AvailEntry->Time != 0)
586 OldestPresentEntry = AvailEntry;
587 }
588
589 void remove(CachedBlock *Entry) REQUIRES(Mutex) {
590 DCHECK(Entry->isValid());
591 if (OldestPresentEntry == Entry) {
592 OldestPresentEntry = LRUEntries.getPrev(X: Entry);
593 DCHECK(OldestPresentEntry == nullptr || OldestPresentEntry->Time != 0);
594 }
595 LRUEntries.remove(X: Entry);
596 Entry->invalidate();
597 AvailEntries.push_front(X: Entry);
598 }
599
600 void empty() {
601 MemMapT MapInfo[Config::getEntriesArraySize()];
602 uptr N = 0;
603 {
604 ScopedLock L(Mutex);
605
606 for (CachedBlock &Entry : LRUEntries)
607 MapInfo[N++] = Entry.MemMap;
608 LRUEntries.clear();
609 OldestPresentEntry = nullptr;
610 }
611 for (uptr I = 0; I < N; I++) {
612 MemMapT &MemMap = MapInfo[I];
613 unmapCallBack(MemMap);
614 }
615 }
616
617 void releaseOlderThan(u64 ReleaseTime) REQUIRES(Mutex) {
618 SCUDO_SCOPED_TRACE(GetSecondaryReleaseOlderThanTraceName());
619
620 if (!Config::getQuarantineDisabled()) {
621 for (uptr I = 0; I < Config::getQuarantineSize(); I++) {
622 auto &Entry = Quarantine[I];
623 if (!Entry.isValid() || Entry.Time == 0 || Entry.Time > ReleaseTime)
624 continue;
625 Entry.MemMap.releaseAndZeroPagesToOS(Entry.CommitBase,
626 Entry.CommitSize);
627 Entry.Time = 0;
628 }
629 }
630
631 for (CachedBlock *Entry = OldestPresentEntry; Entry != nullptr;
632 Entry = LRUEntries.getPrev(X: Entry)) {
633 DCHECK(Entry->isValid());
634 DCHECK(Entry->Time != 0);
635
636 if (Entry->Time > ReleaseTime) {
637 // All entries are newer than this, so no need to keep scanning.
638 OldestPresentEntry = Entry;
639 return;
640 }
641
642 Entry->MemMap.releaseAndZeroPagesToOS(From: Entry->CommitBase,
643 Size: Entry->CommitSize);
644 Entry->Time = 0;
645 }
646 OldestPresentEntry = nullptr;
647 }
648
649 HybridMutex Mutex;
650 u32 QuarantinePos GUARDED_BY(Mutex) = 0;
651 atomic_u32 MaxEntriesCount = {};
652 atomic_uptr MaxEntrySize = {};
653 atomic_s32 ReleaseToOsIntervalMs = {};
654 u32 CallsToRetrieve GUARDED_BY(Mutex) = 0;
655 u32 SuccessfulRetrieves GUARDED_BY(Mutex) = 0;
656 atomic_uptr ReleaseToOsSkips = {};
657
658 CachedBlock Entries[Config::getEntriesArraySize()] GUARDED_BY(Mutex) = {};
659 NonZeroLengthArray<CachedBlock, Config::getQuarantineSize()>
660 Quarantine GUARDED_BY(Mutex) = {};
661
662 // The oldest entry in the LRUEntries that has Time non-zero.
663 CachedBlock *OldestPresentEntry GUARDED_BY(Mutex) = nullptr;
664 // Cached blocks stored in LRU order
665 DoublyLinkedList<CachedBlock> LRUEntries GUARDED_BY(Mutex);
666 // The unused Entries
667 SinglyLinkedList<CachedBlock> AvailEntries GUARDED_BY(Mutex);
668};
669
670template <typename Config> class MapAllocator {
671public:
672 void init(GlobalStats *S,
673 s32 ReleaseToOsInterval = -1) NO_THREAD_SAFETY_ANALYSIS {
674 DCHECK_EQ(AllocatedBytes, 0U);
675 DCHECK_EQ(FreedBytes, 0U);
676 Cache.init(ReleaseToOsInterval);
677 Stats.init();
678 if (LIKELY(S))
679 S->link(S: &Stats);
680 }
681
682 void *allocate(const Options &Options, uptr Size, uptr AlignmentHint = 0,
683 uptr *BlockEnd = nullptr,
684 FillContentsMode FillContents = NoFill);
685
686 void deallocate(const Options &Options, void *Ptr);
687
688 void *tryAllocateFromCache(const Options &Options, uptr Size, uptr Alignment,
689 uptr *BlockEndPtr, FillContentsMode FillContents);
690
691 static uptr getBlockEnd(void *Ptr) {
692 auto *B = LargeBlock::getHeader<Config>(Ptr);
693 return B->CommitBase + B->CommitSize;
694 }
695
696 static uptr getBlockSize(void *Ptr) {
697 return getBlockEnd(Ptr) - reinterpret_cast<uptr>(Ptr);
698 }
699
700 static uptr getGuardPageSize() {
701 if (Config::getEnableGuardPages())
702 return getPageSizeCached();
703 return 0U;
704 }
705
706 static constexpr uptr getHeadersSize() {
707 return Chunk::getHeaderSize() + LargeBlock::getHeaderSize();
708 }
709
710 void disable() NO_THREAD_SAFETY_ANALYSIS {
711 Mutex.lock();
712 Cache.disable();
713 }
714
715 void enable() NO_THREAD_SAFETY_ANALYSIS {
716 Cache.enable();
717 Mutex.unlock();
718 }
719
720 template <typename F> void iterateOverBlocks(F Callback) const {
721 Mutex.assertHeld();
722
723 for (const auto &H : InUseBlocks) {
724 uptr Ptr = reinterpret_cast<uptr>(&H) + LargeBlock::getHeaderSize();
725 if (allocatorSupportsMemoryTagging<Config>())
726 Ptr = untagPointer(Ptr);
727 Callback(Ptr);
728 }
729 }
730
731 bool canCache(uptr Size) { return Cache.canCache(Size); }
732
733 bool setOption(Option O, sptr Value) { return Cache.setOption(O, Value); }
734
735 void releaseToOS(ReleaseToOS ReleaseType) { Cache.releaseToOS(ReleaseType); }
736
737 void disableMemoryTagging() { Cache.disableMemoryTagging(); }
738
739 void unmapTestOnly() { Cache.unmapTestOnly(); }
740
741 void getStats(ScopedString *Str);
742
743private:
744 typename Config::template CacheT<typename Config::CacheConfig> Cache;
745
746 mutable HybridMutex Mutex;
747 DoublyLinkedList<LargeBlock::Header> InUseBlocks GUARDED_BY(Mutex);
748 uptr AllocatedBytes GUARDED_BY(Mutex) = 0;
749 uptr FreedBytes GUARDED_BY(Mutex) = 0;
750 uptr FragmentedBytes GUARDED_BY(Mutex) = 0;
751 uptr LargestSize GUARDED_BY(Mutex) = 0;
752 u32 NumberOfAllocs GUARDED_BY(Mutex) = 0;
753 u32 NumberOfFrees GUARDED_BY(Mutex) = 0;
754 LocalStats Stats GUARDED_BY(Mutex);
755};
756
757template <typename Config>
758void *
759MapAllocator<Config>::tryAllocateFromCache(const Options &Options, uptr Size,
760 uptr Alignment, uptr *BlockEndPtr,
761 FillContentsMode FillContents) {
762 CachedBlock Entry;
763 uptr EntryHeaderPos;
764 uptr MaxAllowedFragmentedPages = MaxUnreleasedCachePages;
765
766 if (LIKELY(!useMemoryTagging<Config>(Options))) {
767 MaxAllowedFragmentedPages += CachedBlock::MaxReleasedCachePages;
768 } else {
769 // TODO: Enable MaxReleasedCachePages may result in pages for an entry being
770 // partially released and it erases the tag of those pages as well. To
771 // support this feature for MTE, we need to tag those pages again.
772 DCHECK_EQ(MaxAllowedFragmentedPages, MaxUnreleasedCachePages);
773 }
774
775 Entry = Cache.retrieve(MaxAllowedFragmentedPages, Size, Alignment,
776 getHeadersSize(), EntryHeaderPos);
777 if (!Entry.isValid())
778 return nullptr;
779
780 LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(
781 LargeBlock::addHeaderTag<Config>(EntryHeaderPos));
782 bool Zeroed = Entry.Time == 0;
783
784 if (UNLIKELY(Entry.Flags & CachedBlock::NoAccess)) {
785 // NOTE: Flags set to 0 actually restores read-write.
786 Entry.MemMap.setMemoryPermission(Addr: Entry.CommitBase, Size: Entry.CommitSize,
787 /*Flags=*/Flags: 0);
788 }
789
790 if (useMemoryTagging<Config>(Options)) {
791 uptr NewBlockBegin = reinterpret_cast<uptr>(H + 1);
792 if (Zeroed || (Entry.BlockBegin < NewBlockBegin)) {
793 storeTags(Begin: reinterpret_cast<uptr>(H), End: NewBlockBegin);
794 } else {
795 storeTags(Begin: untagPointer(Ptr: NewBlockBegin), End: untagPointer(Ptr: Entry.BlockBegin));
796 storeTags(Begin: reinterpret_cast<uptr>(H), End: NewBlockBegin);
797 }
798 }
799
800 H->CommitBase = Entry.CommitBase;
801 H->CommitSize = Entry.CommitSize;
802 H->MemMap = Entry.MemMap;
803
804 const uptr BlockEnd = H->CommitBase + H->CommitSize;
805 if (BlockEndPtr)
806 *BlockEndPtr = BlockEnd;
807 uptr HInt = reinterpret_cast<uptr>(H);
808 if (allocatorSupportsMemoryTagging<Config>())
809 HInt = untagPointer(Ptr: HInt);
810 const uptr PtrInt = HInt + LargeBlock::getHeaderSize();
811 void *Ptr = reinterpret_cast<void *>(PtrInt);
812 if (FillContents && !Zeroed)
813 memset(s: Ptr, c: FillContents == ZeroFill ? 0 : PatternFillByte,
814 n: BlockEnd - PtrInt);
815 {
816 ScopedLock L(Mutex);
817 InUseBlocks.push_back(X: H);
818 AllocatedBytes += H->CommitSize;
819 FragmentedBytes += H->MemMap.getCapacity() - H->CommitSize;
820 NumberOfAllocs++;
821 Stats.add(I: StatAllocated, V: H->CommitSize);
822 Stats.add(I: StatMapped, V: H->MemMap.getCapacity());
823 }
824 return Ptr;
825}
826// As with the Primary, the size passed to this function includes any desired
827// alignment, so that the frontend can align the user allocation. The hint
828// parameter allows us to unmap spurious memory when dealing with larger
829// (greater than a page) alignments on 32-bit platforms.
830// Due to the sparsity of address space available on those platforms, requesting
831// an allocation from the Secondary with a large alignment would end up wasting
832// VA space (even though we are not committing the whole thing), hence the need
833// to trim off some of the reserved space.
834// For allocations requested with an alignment greater than or equal to a page,
835// the committed memory will amount to something close to Size - AlignmentHint
836// (pending rounding and headers).
837template <typename Config>
838void *MapAllocator<Config>::allocate(const Options &Options, uptr Size,
839 uptr Alignment, uptr *BlockEndPtr,
840 FillContentsMode FillContents) {
841 if (Options.get(Opt: OptionBit::AddLargeAllocationSlack))
842 Size += 1UL << SCUDO_MIN_ALIGNMENT_LOG;
843 Alignment = Max(A: Alignment, B: uptr(1U) << SCUDO_MIN_ALIGNMENT_LOG);
844 const uptr PageSize = getPageSizeCached();
845
846 // Note that cached blocks may have aligned address already. Thus we simply
847 // pass the required size (`Size` + `getHeadersSize()`) to do cache look up.
848 const uptr MinNeededSizeForCache = roundUp(X: Size + getHeadersSize(), Boundary: PageSize);
849
850 if (Alignment < PageSize && Cache.canCache(MinNeededSizeForCache)) {
851 void *Ptr = tryAllocateFromCache(Options, Size, Alignment, BlockEndPtr,
852 FillContents);
853 if (Ptr != nullptr)
854 return Ptr;
855 }
856
857 uptr RoundedSize =
858 roundUp(X: roundUp(X: Size, Boundary: Alignment) + getHeadersSize(), Boundary: PageSize);
859 if (UNLIKELY(Alignment > PageSize))
860 RoundedSize += Alignment - PageSize;
861
862 ReservedMemoryT ReservedMemory;
863 const uptr MapSize = RoundedSize + 2 * getGuardPageSize();
864 if (UNLIKELY(!ReservedMemory.create(/*Addr=*/0U, MapSize, nullptr,
865 MAP_ALLOWNOMEM))) {
866 return nullptr;
867 }
868
869 // Take the entire ownership of reserved region.
870 MemMapT MemMap = ReservedMemory.dispatch(Addr: ReservedMemory.getBase(),
871 Size: ReservedMemory.getCapacity());
872 uptr MapBase = MemMap.getBase();
873 uptr CommitBase = MapBase + getGuardPageSize();
874 uptr MapEnd = MapBase + MapSize;
875
876 // In the unlikely event of alignments larger than a page, adjust the amount
877 // of memory we want to commit, and trim the extra memory.
878 if (UNLIKELY(Alignment >= PageSize)) {
879 // For alignments greater than or equal to a page, the user pointer (eg:
880 // the pointer that is returned by the C or C++ allocation APIs) ends up
881 // on a page boundary , and our headers will live in the preceding page.
882 CommitBase =
883 roundUp(X: MapBase + getGuardPageSize() + 1, Boundary: Alignment) - PageSize;
884 // We only trim the extra memory on 32-bit platforms: 64-bit platforms
885 // are less constrained memory wise, and that saves us two syscalls.
886 if (SCUDO_WORDSIZE == 32U) {
887 const uptr NewMapBase = CommitBase - getGuardPageSize();
888 DCHECK_GE(NewMapBase, MapBase);
889 if (NewMapBase != MapBase) {
890 MemMap.unmap(Addr: MapBase, Size: NewMapBase - MapBase);
891 MapBase = NewMapBase;
892 }
893 // CommitBase is past the first guard page, but this computation needs
894 // to include a page where the header lives.
895 const uptr NewMapEnd =
896 CommitBase + PageSize + roundUp(X: Size, Boundary: PageSize) + getGuardPageSize();
897 DCHECK_LE(NewMapEnd, MapEnd);
898 if (NewMapEnd != MapEnd) {
899 MemMap.unmap(Addr: NewMapEnd, Size: MapEnd - NewMapEnd);
900 MapEnd = NewMapEnd;
901 }
902 }
903 }
904
905 const uptr CommitSize = MapEnd - getGuardPageSize() - CommitBase;
906 const uptr AllocPos = roundDown(X: CommitBase + CommitSize - Size, Boundary: Alignment);
907 if (!mapSecondary<Config>(Options, CommitBase, CommitSize, AllocPos, 0,
908 MemMap)) {
909 MemMap.unmap();
910 return nullptr;
911 }
912 const uptr HeaderPos = AllocPos - getHeadersSize();
913 // Make sure that the header is not in the guard page or before the base.
914 DCHECK_GE(HeaderPos, MapBase + getGuardPageSize());
915 LargeBlock::Header *H = reinterpret_cast<LargeBlock::Header *>(
916 LargeBlock::addHeaderTag<Config>(HeaderPos));
917 if (useMemoryTagging<Config>(Options))
918 storeTags(Begin: reinterpret_cast<uptr>(H), End: reinterpret_cast<uptr>(H + 1));
919 H->CommitBase = CommitBase;
920 H->CommitSize = CommitSize;
921 H->MemMap = MemMap;
922 if (BlockEndPtr)
923 *BlockEndPtr = CommitBase + CommitSize;
924 {
925 ScopedLock L(Mutex);
926 InUseBlocks.push_back(X: H);
927 AllocatedBytes += CommitSize;
928 FragmentedBytes += H->MemMap.getCapacity() - CommitSize;
929 if (LargestSize < CommitSize)
930 LargestSize = CommitSize;
931 NumberOfAllocs++;
932 Stats.add(I: StatAllocated, V: CommitSize);
933 Stats.add(I: StatMapped, V: H->MemMap.getCapacity());
934 }
935 return reinterpret_cast<void *>(HeaderPos + LargeBlock::getHeaderSize());
936}
937
938template <typename Config>
939void MapAllocator<Config>::deallocate(const Options &Options, void *Ptr)
940 EXCLUDES(Mutex) {
941 LargeBlock::Header *H = LargeBlock::getHeader<Config>(Ptr);
942 const uptr CommitSize = H->CommitSize;
943 {
944 ScopedLock L(Mutex);
945 InUseBlocks.remove(X: H);
946 FreedBytes += CommitSize;
947 FragmentedBytes -= H->MemMap.getCapacity() - CommitSize;
948 NumberOfFrees++;
949 Stats.sub(I: StatAllocated, V: CommitSize);
950 Stats.sub(I: StatMapped, V: H->MemMap.getCapacity());
951 }
952
953 if (Cache.canCache(H->CommitSize)) {
954 Cache.store(Options, H->CommitBase, H->CommitSize,
955 reinterpret_cast<uptr>(H + 1), H->MemMap);
956 } else {
957 // Note that the `H->MemMap` is stored on the pages managed by itself. Take
958 // over the ownership before unmap() so that any operation along with
959 // unmap() won't touch inaccessible pages.
960 MemMapT MemMap = H->MemMap;
961 unmap(MemMap);
962 }
963}
964
965template <typename Config>
966void MapAllocator<Config>::getStats(ScopedString *Str) EXCLUDES(Mutex) {
967 ScopedLock L(Mutex);
968 Str->append(Format: "Stats: MapAllocator: allocated %u times (%zuK), freed %u times "
969 "(%zuK), remains %u (%zuK) max %zuM, Fragmented %zuK\n",
970 NumberOfAllocs, AllocatedBytes >> 10, NumberOfFrees,
971 FreedBytes >> 10, NumberOfAllocs - NumberOfFrees,
972 (AllocatedBytes - FreedBytes) >> 10, LargestSize >> 20,
973 FragmentedBytes >> 10);
974 Cache.getStats(Str);
975}
976
977} // namespace scudo
978
979#endif // SCUDO_SECONDARY_H_
980