1351282Sdim//===-- quarantine.h --------------------------------------------*- C++ -*-===// 2351282Sdim// 3351282Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4351282Sdim// See https://llvm.org/LICENSE.txt for license information. 5351282Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6351282Sdim// 7351282Sdim//===----------------------------------------------------------------------===// 8351282Sdim 9351282Sdim#ifndef SCUDO_QUARANTINE_H_ 10351282Sdim#define SCUDO_QUARANTINE_H_ 11351282Sdim 12351282Sdim#include "list.h" 13351282Sdim#include "mutex.h" 14351282Sdim#include "string_utils.h" 15351282Sdim 16351282Sdimnamespace scudo { 17351282Sdim 18351282Sdimstruct QuarantineBatch { 19351282Sdim // With the following count, a batch (and the header that protects it) occupy 20351282Sdim // 4096 bytes on 32-bit platforms, and 8192 bytes on 64-bit. 21351282Sdim static const u32 MaxCount = 1019; 22351282Sdim QuarantineBatch *Next; 23351282Sdim uptr Size; 24351282Sdim u32 Count; 25351282Sdim void *Batch[MaxCount]; 26351282Sdim 27351282Sdim void init(void *Ptr, uptr Size) { 28351282Sdim Count = 1; 29351282Sdim Batch[0] = Ptr; 30351282Sdim this->Size = Size + sizeof(QuarantineBatch); // Account for the Batch Size. 31351282Sdim } 32351282Sdim 33351282Sdim // The total size of quarantined nodes recorded in this batch. 34351282Sdim uptr getQuarantinedSize() const { return Size - sizeof(QuarantineBatch); } 35351282Sdim 36351282Sdim void push_back(void *Ptr, uptr Size) { 37351282Sdim DCHECK_LT(Count, MaxCount); 38351282Sdim Batch[Count++] = Ptr; 39351282Sdim this->Size += Size; 40351282Sdim } 41351282Sdim 42351282Sdim bool canMerge(const QuarantineBatch *const From) const { 43351282Sdim return Count + From->Count <= MaxCount; 44351282Sdim } 45351282Sdim 46351282Sdim void merge(QuarantineBatch *const From) { 47351282Sdim DCHECK_LE(Count + From->Count, MaxCount); 48351282Sdim DCHECK_GE(Size, sizeof(QuarantineBatch)); 49351282Sdim 50351282Sdim for (uptr I = 0; I < From->Count; ++I) 51351282Sdim Batch[Count + I] = From->Batch[I]; 52351282Sdim Count += From->Count; 53351282Sdim Size += From->getQuarantinedSize(); 54351282Sdim 55351282Sdim From->Count = 0; 56351282Sdim From->Size = sizeof(QuarantineBatch); 57351282Sdim } 58351282Sdim 59351282Sdim void shuffle(u32 State) { ::scudo::shuffle(Batch, Count, &State); } 60351282Sdim}; 61351282Sdim 62360784Sdimstatic_assert(sizeof(QuarantineBatch) <= (1U << 13), ""); // 8Kb. 63351282Sdim 64351282Sdim// Per-thread cache of memory blocks. 65351282Sdimtemplate <typename Callback> class QuarantineCache { 66351282Sdimpublic: 67351282Sdim void initLinkerInitialized() {} 68351282Sdim void init() { 69351282Sdim memset(this, 0, sizeof(*this)); 70351282Sdim initLinkerInitialized(); 71351282Sdim } 72351282Sdim 73351282Sdim // Total memory used, including internal accounting. 74351282Sdim uptr getSize() const { return atomic_load_relaxed(&Size); } 75351282Sdim // Memory used for internal accounting. 76351282Sdim uptr getOverheadSize() const { return List.size() * sizeof(QuarantineBatch); } 77351282Sdim 78351282Sdim void enqueue(Callback Cb, void *Ptr, uptr Size) { 79351282Sdim if (List.empty() || List.back()->Count == QuarantineBatch::MaxCount) { 80351282Sdim QuarantineBatch *B = 81351282Sdim reinterpret_cast<QuarantineBatch *>(Cb.allocate(sizeof(*B))); 82351282Sdim DCHECK(B); 83351282Sdim B->init(Ptr, Size); 84351282Sdim enqueueBatch(B); 85351282Sdim } else { 86351282Sdim List.back()->push_back(Ptr, Size); 87351282Sdim addToSize(Size); 88351282Sdim } 89351282Sdim } 90351282Sdim 91351282Sdim void transfer(QuarantineCache *From) { 92351282Sdim List.append_back(&From->List); 93351282Sdim addToSize(From->getSize()); 94351282Sdim atomic_store_relaxed(&From->Size, 0); 95351282Sdim } 96351282Sdim 97351282Sdim void enqueueBatch(QuarantineBatch *B) { 98351282Sdim List.push_back(B); 99351282Sdim addToSize(B->Size); 100351282Sdim } 101351282Sdim 102351282Sdim QuarantineBatch *dequeueBatch() { 103351282Sdim if (List.empty()) 104351282Sdim return nullptr; 105351282Sdim QuarantineBatch *B = List.front(); 106351282Sdim List.pop_front(); 107351282Sdim subFromSize(B->Size); 108351282Sdim return B; 109351282Sdim } 110351282Sdim 111351282Sdim void mergeBatches(QuarantineCache *ToDeallocate) { 112351282Sdim uptr ExtractedSize = 0; 113351282Sdim QuarantineBatch *Current = List.front(); 114351282Sdim while (Current && Current->Next) { 115351282Sdim if (Current->canMerge(Current->Next)) { 116351282Sdim QuarantineBatch *Extracted = Current->Next; 117351282Sdim // Move all the chunks into the current batch. 118351282Sdim Current->merge(Extracted); 119351282Sdim DCHECK_EQ(Extracted->Count, 0); 120351282Sdim DCHECK_EQ(Extracted->Size, sizeof(QuarantineBatch)); 121351282Sdim // Remove the next batch From the list and account for its Size. 122351282Sdim List.extract(Current, Extracted); 123351282Sdim ExtractedSize += Extracted->Size; 124351282Sdim // Add it to deallocation list. 125351282Sdim ToDeallocate->enqueueBatch(Extracted); 126351282Sdim } else { 127351282Sdim Current = Current->Next; 128351282Sdim } 129351282Sdim } 130351282Sdim subFromSize(ExtractedSize); 131351282Sdim } 132351282Sdim 133360784Sdim void getStats(ScopedString *Str) const { 134351282Sdim uptr BatchCount = 0; 135351282Sdim uptr TotalOverheadBytes = 0; 136351282Sdim uptr TotalBytes = 0; 137351282Sdim uptr TotalQuarantineChunks = 0; 138351282Sdim for (const QuarantineBatch &Batch : List) { 139351282Sdim BatchCount++; 140351282Sdim TotalBytes += Batch.Size; 141351282Sdim TotalOverheadBytes += Batch.Size - Batch.getQuarantinedSize(); 142351282Sdim TotalQuarantineChunks += Batch.Count; 143351282Sdim } 144351282Sdim const uptr QuarantineChunksCapacity = 145351282Sdim BatchCount * QuarantineBatch::MaxCount; 146351282Sdim const uptr ChunksUsagePercent = 147351282Sdim (QuarantineChunksCapacity == 0) 148351282Sdim ? 0 149351282Sdim : TotalQuarantineChunks * 100 / QuarantineChunksCapacity; 150351282Sdim const uptr TotalQuarantinedBytes = TotalBytes - TotalOverheadBytes; 151351282Sdim const uptr MemoryOverheadPercent = 152351282Sdim (TotalQuarantinedBytes == 0) 153351282Sdim ? 0 154351282Sdim : TotalOverheadBytes * 100 / TotalQuarantinedBytes; 155360784Sdim Str->append( 156360784Sdim "Stats: Quarantine: batches: %zu; bytes: %zu (user: %zu); chunks: %zu " 157360784Sdim "(capacity: %zu); %zu%% chunks used; %zu%% memory overhead\n", 158360784Sdim BatchCount, TotalBytes, TotalQuarantinedBytes, TotalQuarantineChunks, 159360784Sdim QuarantineChunksCapacity, ChunksUsagePercent, MemoryOverheadPercent); 160351282Sdim } 161351282Sdim 162351282Sdimprivate: 163360784Sdim SinglyLinkedList<QuarantineBatch> List; 164351282Sdim atomic_uptr Size; 165351282Sdim 166351282Sdim void addToSize(uptr add) { atomic_store_relaxed(&Size, getSize() + add); } 167351282Sdim void subFromSize(uptr sub) { atomic_store_relaxed(&Size, getSize() - sub); } 168351282Sdim}; 169351282Sdim 170351282Sdim// The callback interface is: 171351282Sdim// void Callback::recycle(Node *Ptr); 172351282Sdim// void *Callback::allocate(uptr Size); 173351282Sdim// void Callback::deallocate(void *Ptr); 174351282Sdimtemplate <typename Callback, typename Node> class GlobalQuarantine { 175351282Sdimpublic: 176351282Sdim typedef QuarantineCache<Callback> CacheT; 177351282Sdim 178351282Sdim void initLinkerInitialized(uptr Size, uptr CacheSize) { 179351282Sdim // Thread local quarantine size can be zero only when global quarantine size 180351282Sdim // is zero (it allows us to perform just one atomic read per put() call). 181351282Sdim CHECK((Size == 0 && CacheSize == 0) || CacheSize != 0); 182351282Sdim 183351282Sdim atomic_store_relaxed(&MaxSize, Size); 184351282Sdim atomic_store_relaxed(&MinSize, Size / 10 * 9); // 90% of max size. 185351282Sdim atomic_store_relaxed(&MaxCacheSize, CacheSize); 186351282Sdim 187351282Sdim Cache.initLinkerInitialized(); 188351282Sdim } 189351282Sdim void init(uptr Size, uptr CacheSize) { 190351282Sdim memset(this, 0, sizeof(*this)); 191351282Sdim initLinkerInitialized(Size, CacheSize); 192351282Sdim } 193351282Sdim 194351282Sdim uptr getMaxSize() const { return atomic_load_relaxed(&MaxSize); } 195351282Sdim uptr getCacheSize() const { return atomic_load_relaxed(&MaxCacheSize); } 196351282Sdim 197351282Sdim void put(CacheT *C, Callback Cb, Node *Ptr, uptr Size) { 198351282Sdim C->enqueue(Cb, Ptr, Size); 199351282Sdim if (C->getSize() > getCacheSize()) 200351282Sdim drain(C, Cb); 201351282Sdim } 202351282Sdim 203351282Sdim void NOINLINE drain(CacheT *C, Callback Cb) { 204351282Sdim { 205351282Sdim ScopedLock L(CacheMutex); 206351282Sdim Cache.transfer(C); 207351282Sdim } 208360784Sdim if (Cache.getSize() > getMaxSize() && RecycleMutex.tryLock()) 209351282Sdim recycle(atomic_load_relaxed(&MinSize), Cb); 210351282Sdim } 211351282Sdim 212351282Sdim void NOINLINE drainAndRecycle(CacheT *C, Callback Cb) { 213351282Sdim { 214351282Sdim ScopedLock L(CacheMutex); 215351282Sdim Cache.transfer(C); 216351282Sdim } 217360784Sdim RecycleMutex.lock(); 218351282Sdim recycle(0, Cb); 219351282Sdim } 220351282Sdim 221360784Sdim void getStats(ScopedString *Str) const { 222351282Sdim // It assumes that the world is stopped, just as the allocator's printStats. 223360784Sdim Cache.getStats(Str); 224360784Sdim Str->append("Quarantine limits: global: %zuK; thread local: %zuK\n", 225360784Sdim getMaxSize() >> 10, getCacheSize() >> 10); 226351282Sdim } 227351282Sdim 228360784Sdim void disable() { 229360784Sdim // RecycleMutex must be locked 1st since we grab CacheMutex within recycle. 230360784Sdim RecycleMutex.lock(); 231360784Sdim CacheMutex.lock(); 232360784Sdim } 233360784Sdim 234360784Sdim void enable() { 235360784Sdim CacheMutex.unlock(); 236360784Sdim RecycleMutex.unlock(); 237360784Sdim } 238360784Sdim 239351282Sdimprivate: 240351282Sdim // Read-only data. 241351282Sdim alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex CacheMutex; 242351282Sdim CacheT Cache; 243360784Sdim alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex RecycleMutex; 244351282Sdim atomic_uptr MinSize; 245351282Sdim atomic_uptr MaxSize; 246351282Sdim alignas(SCUDO_CACHE_LINE_SIZE) atomic_uptr MaxCacheSize; 247351282Sdim 248351282Sdim void NOINLINE recycle(uptr MinSize, Callback Cb) { 249351282Sdim CacheT Tmp; 250351282Sdim Tmp.init(); 251351282Sdim { 252351282Sdim ScopedLock L(CacheMutex); 253351282Sdim // Go over the batches and merge partially filled ones to 254351282Sdim // save some memory, otherwise batches themselves (since the memory used 255351282Sdim // by them is counted against quarantine limit) can overcome the actual 256351282Sdim // user's quarantined chunks, which diminishes the purpose of the 257351282Sdim // quarantine. 258351282Sdim const uptr CacheSize = Cache.getSize(); 259351282Sdim const uptr OverheadSize = Cache.getOverheadSize(); 260351282Sdim DCHECK_GE(CacheSize, OverheadSize); 261351282Sdim // Do the merge only when overhead exceeds this predefined limit (might 262351282Sdim // require some tuning). It saves us merge attempt when the batch list 263351282Sdim // quarantine is unlikely to contain batches suitable for merge. 264351282Sdim constexpr uptr OverheadThresholdPercents = 100; 265351282Sdim if (CacheSize > OverheadSize && 266351282Sdim OverheadSize * (100 + OverheadThresholdPercents) > 267351282Sdim CacheSize * OverheadThresholdPercents) { 268351282Sdim Cache.mergeBatches(&Tmp); 269351282Sdim } 270351282Sdim // Extract enough chunks from the quarantine to get below the max 271351282Sdim // quarantine size and leave some leeway for the newly quarantined chunks. 272351282Sdim while (Cache.getSize() > MinSize) 273351282Sdim Tmp.enqueueBatch(Cache.dequeueBatch()); 274351282Sdim } 275360784Sdim RecycleMutex.unlock(); 276351282Sdim doRecycle(&Tmp, Cb); 277351282Sdim } 278351282Sdim 279351282Sdim void NOINLINE doRecycle(CacheT *C, Callback Cb) { 280351282Sdim while (QuarantineBatch *B = C->dequeueBatch()) { 281351282Sdim const u32 Seed = static_cast<u32>( 282351282Sdim (reinterpret_cast<uptr>(B) ^ reinterpret_cast<uptr>(C)) >> 4); 283351282Sdim B->shuffle(Seed); 284351282Sdim constexpr uptr NumberOfPrefetch = 8UL; 285351282Sdim CHECK(NumberOfPrefetch <= ARRAY_SIZE(B->Batch)); 286351282Sdim for (uptr I = 0; I < NumberOfPrefetch; I++) 287351282Sdim PREFETCH(B->Batch[I]); 288351282Sdim for (uptr I = 0, Count = B->Count; I < Count; I++) { 289351282Sdim if (I + NumberOfPrefetch < Count) 290351282Sdim PREFETCH(B->Batch[I + NumberOfPrefetch]); 291351282Sdim Cb.recycle(reinterpret_cast<Node *>(B->Batch[I])); 292351282Sdim } 293351282Sdim Cb.deallocate(B); 294351282Sdim } 295351282Sdim } 296351282Sdim}; 297351282Sdim 298351282Sdim} // namespace scudo 299351282Sdim 300351282Sdim#endif // SCUDO_QUARANTINE_H_ 301