310 lines · c
1//===-- quarantine.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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef SCUDO_QUARANTINE_H_10#define SCUDO_QUARANTINE_H_11 12#include "list.h"13#include "mutex.h"14#include "string_utils.h"15#include "thread_annotations.h"16 17namespace scudo {18 19struct QuarantineBatch {20 // With the following count, a batch (and the header that protects it) occupy21 // 4096 bytes on 32-bit platforms, and 8192 bytes on 64-bit.22 static const u32 MaxCount = 1019;23 QuarantineBatch *Next;24 uptr Size;25 u32 Count;26 void *Batch[MaxCount];27 28 void init(void *Ptr, uptr Size) {29 Count = 1;30 Batch[0] = Ptr;31 this->Size = Size + sizeof(QuarantineBatch); // Account for the Batch Size.32 }33 34 // The total size of quarantined nodes recorded in this batch.35 uptr getQuarantinedSize() const { return Size - sizeof(QuarantineBatch); }36 37 void push_back(void *Ptr, uptr Size) {38 DCHECK_LT(Count, MaxCount);39 Batch[Count++] = Ptr;40 this->Size += Size;41 }42 43 bool canMerge(const QuarantineBatch *const From) const {44 return Count + From->Count <= MaxCount;45 }46 47 void merge(QuarantineBatch *const From) {48 DCHECK_LE(Count + From->Count, MaxCount);49 DCHECK_GE(Size, sizeof(QuarantineBatch));50 51 for (uptr I = 0; I < From->Count; ++I)52 Batch[Count + I] = From->Batch[I];53 Count += From->Count;54 Size += From->getQuarantinedSize();55 56 From->Count = 0;57 From->Size = sizeof(QuarantineBatch);58 }59 60 void shuffle(u32 State) { ::scudo::shuffle(Batch, Count, &State); }61};62 63static_assert(sizeof(QuarantineBatch) <= (1U << 13), ""); // 8Kb.64 65// Per-thread cache of memory blocks.66template <typename Callback> class QuarantineCache {67public:68 void init() { DCHECK_EQ(atomic_load_relaxed(&Size), 0U); }69 70 // Total memory used, including internal accounting.71 uptr getSize() const { return atomic_load_relaxed(&Size); }72 // Memory used for internal accounting.73 uptr getOverheadSize() const { return List.size() * sizeof(QuarantineBatch); }74 75 void enqueue(Callback Cb, void *Ptr, uptr Size) {76 if (List.empty() || List.back()->Count == QuarantineBatch::MaxCount) {77 QuarantineBatch *B =78 reinterpret_cast<QuarantineBatch *>(Cb.allocate(sizeof(*B)));79 DCHECK(B);80 B->init(Ptr, Size);81 enqueueBatch(B);82 } else {83 List.back()->push_back(Ptr, Size);84 addToSize(Size);85 }86 }87 88 void transfer(QuarantineCache *From) {89 List.append_back(&From->List);90 addToSize(From->getSize());91 atomic_store_relaxed(&From->Size, 0);92 }93 94 void enqueueBatch(QuarantineBatch *B) {95 List.push_back(B);96 addToSize(B->Size);97 }98 99 QuarantineBatch *dequeueBatch() {100 if (List.empty())101 return nullptr;102 QuarantineBatch *B = List.front();103 List.pop_front();104 subFromSize(B->Size);105 return B;106 }107 108 void mergeBatches(QuarantineCache *ToDeallocate) {109 uptr ExtractedSize = 0;110 QuarantineBatch *Current = List.front();111 while (Current && Current->Next) {112 if (Current->canMerge(Current->Next)) {113 QuarantineBatch *Extracted = Current->Next;114 // Move all the chunks into the current batch.115 Current->merge(Extracted);116 DCHECK_EQ(Extracted->Count, 0);117 DCHECK_EQ(Extracted->Size, sizeof(QuarantineBatch));118 // Remove the next batch From the list and account for its Size.119 List.extract(Current, Extracted);120 ExtractedSize += Extracted->Size;121 // Add it to deallocation list.122 ToDeallocate->enqueueBatch(Extracted);123 } else {124 Current = Current->Next;125 }126 }127 subFromSize(ExtractedSize);128 }129 130 void getStats(ScopedString *Str) const {131 uptr BatchCount = 0;132 uptr TotalOverheadBytes = 0;133 uptr TotalBytes = 0;134 uptr TotalQuarantineChunks = 0;135 for (const QuarantineBatch &Batch : List) {136 BatchCount++;137 TotalBytes += Batch.Size;138 TotalOverheadBytes += Batch.Size - Batch.getQuarantinedSize();139 TotalQuarantineChunks += Batch.Count;140 }141 const uptr QuarantineChunksCapacity =142 BatchCount * QuarantineBatch::MaxCount;143 const uptr ChunksUsagePercent =144 (QuarantineChunksCapacity == 0)145 ? 0146 : TotalQuarantineChunks * 100 / QuarantineChunksCapacity;147 const uptr TotalQuarantinedBytes = TotalBytes - TotalOverheadBytes;148 const uptr MemoryOverheadPercent =149 (TotalQuarantinedBytes == 0)150 ? 0151 : TotalOverheadBytes * 100 / TotalQuarantinedBytes;152 Str->append(153 "Stats: Quarantine: batches: %zu; bytes: %zu (user: %zu); chunks: %zu "154 "(capacity: %zu); %zu%% chunks used; %zu%% memory overhead\n",155 BatchCount, TotalBytes, TotalQuarantinedBytes, TotalQuarantineChunks,156 QuarantineChunksCapacity, ChunksUsagePercent, MemoryOverheadPercent);157 }158 159private:160 SinglyLinkedList<QuarantineBatch> List;161 atomic_uptr Size = {};162 163 void addToSize(uptr add) { atomic_store_relaxed(&Size, getSize() + add); }164 void subFromSize(uptr sub) { atomic_store_relaxed(&Size, getSize() - sub); }165};166 167// The callback interface is:168// void Callback::recycle(Node *Ptr);169// void *Callback::allocate(uptr Size);170// void Callback::deallocate(void *Ptr);171template <typename Callback, typename Node> class GlobalQuarantine {172public:173 typedef QuarantineCache<Callback> CacheT;174 using ThisT = GlobalQuarantine<Callback, Node>;175 176 void init(uptr Size, uptr CacheSize) NO_THREAD_SAFETY_ANALYSIS {177 DCHECK(isAligned(reinterpret_cast<uptr>(this), alignof(ThisT)));178 DCHECK_EQ(atomic_load_relaxed(&MaxSize), 0U);179 DCHECK_EQ(atomic_load_relaxed(&MinSize), 0U);180 DCHECK_EQ(atomic_load_relaxed(&MaxCacheSize), 0U);181 // Thread local quarantine size can be zero only when global quarantine size182 // is zero (it allows us to perform just one atomic read per put() call).183 CHECK((Size == 0 && CacheSize == 0) || CacheSize != 0);184 185 atomic_store_relaxed(&MaxSize, Size);186 atomic_store_relaxed(&MinSize, Size / 10 * 9); // 90% of max size.187 atomic_store_relaxed(&MaxCacheSize, CacheSize);188 189 Cache.init();190 }191 192 uptr getMaxSize() const { return atomic_load_relaxed(&MaxSize); }193 uptr getCacheSize() const { return atomic_load_relaxed(&MaxCacheSize); }194 195 // This is supposed to be used in test only.196 bool isEmpty() {197 ScopedLock L(CacheMutex);198 return Cache.getSize() == 0U;199 }200 201 void put(CacheT *C, Callback Cb, Node *Ptr, uptr Size) {202 C->enqueue(Cb, Ptr, Size);203 if (C->getSize() > getCacheSize())204 drain(C, Cb);205 }206 207 void NOINLINE drain(CacheT *C, Callback Cb) EXCLUDES(CacheMutex) {208 bool needRecycle = false;209 {210 ScopedLock L(CacheMutex);211 Cache.transfer(C);212 needRecycle = Cache.getSize() > getMaxSize();213 }214 215 if (needRecycle && RecycleMutex.tryLock())216 recycle(atomic_load_relaxed(&MinSize), Cb);217 }218 219 void NOINLINE drainAndRecycle(CacheT *C, Callback Cb) EXCLUDES(CacheMutex) {220 {221 ScopedLock L(CacheMutex);222 Cache.transfer(C);223 }224 RecycleMutex.lock();225 recycle(0, Cb);226 }227 228 void getStats(ScopedString *Str) EXCLUDES(CacheMutex) {229 ScopedLock L(CacheMutex);230 // It assumes that the world is stopped, just as the allocator's printStats.231 Cache.getStats(Str);232 Str->append("Quarantine limits: global: %zuK; thread local: %zuK\n",233 getMaxSize() >> 10, getCacheSize() >> 10);234 }235 236 void disable() NO_THREAD_SAFETY_ANALYSIS {237 // RecycleMutex must be locked 1st since we grab CacheMutex within recycle.238 RecycleMutex.lock();239 CacheMutex.lock();240 }241 242 void enable() NO_THREAD_SAFETY_ANALYSIS {243 CacheMutex.unlock();244 RecycleMutex.unlock();245 }246 247private:248 // Read-only data.249 alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex CacheMutex;250 CacheT Cache GUARDED_BY(CacheMutex);251 alignas(SCUDO_CACHE_LINE_SIZE) HybridMutex RecycleMutex;252 atomic_uptr MinSize = {};253 atomic_uptr MaxSize = {};254 alignas(SCUDO_CACHE_LINE_SIZE) atomic_uptr MaxCacheSize = {};255 256 void NOINLINE recycle(uptr MinSize, Callback Cb) RELEASE(RecycleMutex)257 EXCLUDES(CacheMutex) {258 CacheT Tmp;259 Tmp.init();260 {261 ScopedLock L(CacheMutex);262 // Go over the batches and merge partially filled ones to263 // save some memory, otherwise batches themselves (since the memory used264 // by them is counted against quarantine limit) can overcome the actual265 // user's quarantined chunks, which diminishes the purpose of the266 // quarantine.267 const uptr CacheSize = Cache.getSize();268 const uptr OverheadSize = Cache.getOverheadSize();269 DCHECK_GE(CacheSize, OverheadSize);270 // Do the merge only when overhead exceeds this predefined limit (might271 // require some tuning). It saves us merge attempt when the batch list272 // quarantine is unlikely to contain batches suitable for merge.273 constexpr uptr OverheadThresholdPercents = 100;274 if (CacheSize > OverheadSize &&275 OverheadSize * (100 + OverheadThresholdPercents) >276 CacheSize * OverheadThresholdPercents) {277 Cache.mergeBatches(&Tmp);278 }279 // Extract enough chunks from the quarantine to get below the max280 // quarantine size and leave some leeway for the newly quarantined chunks.281 while (Cache.getSize() > MinSize)282 Tmp.enqueueBatch(Cache.dequeueBatch());283 }284 RecycleMutex.unlock();285 doRecycle(&Tmp, Cb);286 }287 288 void NOINLINE doRecycle(CacheT *C, Callback Cb) {289 while (QuarantineBatch *B = C->dequeueBatch()) {290 const u32 Seed = static_cast<u32>(291 (reinterpret_cast<uptr>(B) ^ reinterpret_cast<uptr>(C)) >> 4);292 B->shuffle(Seed);293 constexpr uptr NumberOfPrefetch = 8UL;294 CHECK(NumberOfPrefetch <= ARRAY_SIZE(B->Batch));295 for (uptr I = 0; I < NumberOfPrefetch; I++)296 PREFETCH(B->Batch[I]);297 for (uptr I = 0, Count = B->Count; I < Count; I++) {298 if (I + NumberOfPrefetch < Count)299 PREFETCH(B->Batch[I + NumberOfPrefetch]);300 Cb.recycle(reinterpret_cast<Node *>(B->Batch[I]));301 }302 Cb.deallocate(B);303 }304 }305};306 307} // namespace scudo308 309#endif // SCUDO_QUARANTINE_H_310