272 lines · c
1//===-- sanitizer_allocator_local_cache.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// Part of the Sanitizer Allocator.10//11//===----------------------------------------------------------------------===//12#ifndef SANITIZER_ALLOCATOR_H13#error This file must be included inside sanitizer_allocator.h14#endif15 16// Cache used by SizeClassAllocator64.17template <class SizeClassAllocator>18struct SizeClassAllocator64LocalCache {19 typedef SizeClassAllocator Allocator;20 typedef MemoryMapper<Allocator> MemoryMapperT;21 22 void Init(AllocatorGlobalStats *s) {23 stats_.Init();24 if (s)25 s->Register(&stats_);26 }27 28 void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) {29 Drain(allocator);30 if (s)31 s->Unregister(&stats_);32 }33 34 void *Allocate(SizeClassAllocator *allocator, uptr class_id) {35 CHECK_NE(class_id, 0UL);36 CHECK_LT(class_id, kNumClasses);37 PerClass *c = &per_class_[class_id];38 if (UNLIKELY(c->count == 0)) {39 if (UNLIKELY(!Refill(c, allocator, class_id)))40 return nullptr;41 DCHECK_GT(c->count, 0);42 }43 CompactPtrT chunk = c->chunks[--c->count];44 stats_.Add(AllocatorStatAllocated, c->class_size);45 return reinterpret_cast<void *>(allocator->CompactPtrToPointer(46 allocator->GetRegionBeginBySizeClass(class_id), chunk));47 }48 49 void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) {50 CHECK_NE(class_id, 0UL);51 CHECK_LT(class_id, kNumClasses);52 // If the first allocator call on a new thread is a deallocation, then53 // max_count will be zero, leading to check failure.54 PerClass *c = &per_class_[class_id];55 InitCache(c);56 if (UNLIKELY(c->count == c->max_count))57 DrainHalfMax(c, allocator, class_id);58 CompactPtrT chunk = allocator->PointerToCompactPtr(59 allocator->GetRegionBeginBySizeClass(class_id),60 reinterpret_cast<uptr>(p));61 c->chunks[c->count++] = chunk;62 stats_.Sub(AllocatorStatAllocated, c->class_size);63 }64 65 void Drain(SizeClassAllocator *allocator) {66 MemoryMapperT memory_mapper(*allocator);67 for (uptr i = 1; i < kNumClasses; i++) {68 PerClass *c = &per_class_[i];69 while (c->count > 0) Drain(&memory_mapper, c, allocator, i, c->count);70 }71 }72 73 private:74 typedef typename Allocator::SizeClassMapT SizeClassMap;75 static const uptr kNumClasses = SizeClassMap::kNumClasses;76 typedef typename Allocator::CompactPtrT CompactPtrT;77 78 struct PerClass {79 u32 count;80 u32 max_count;81 uptr class_size;82 CompactPtrT chunks[2 * SizeClassMap::kMaxNumCachedHint];83 };84 PerClass per_class_[kNumClasses];85 AllocatorStats stats_;86 87 void InitCache(PerClass *c) {88 if (LIKELY(c->max_count))89 return;90 for (uptr i = 1; i < kNumClasses; i++) {91 PerClass *c = &per_class_[i];92 const uptr size = Allocator::ClassIdToSize(i);93 c->max_count = 2 * SizeClassMap::MaxCachedHint(size);94 c->class_size = size;95 }96 DCHECK_NE(c->max_count, 0UL);97 }98 99 NOINLINE bool Refill(PerClass *c, SizeClassAllocator *allocator,100 uptr class_id) {101 InitCache(c);102 const uptr num_requested_chunks = c->max_count / 2;103 if (UNLIKELY(!allocator->GetFromAllocator(&stats_, class_id, c->chunks,104 num_requested_chunks)))105 return false;106 c->count = num_requested_chunks;107 return true;108 }109 110 NOINLINE void DrainHalfMax(PerClass *c, SizeClassAllocator *allocator,111 uptr class_id) {112 MemoryMapperT memory_mapper(*allocator);113 Drain(&memory_mapper, c, allocator, class_id, c->max_count / 2);114 }115 116 void Drain(MemoryMapperT *memory_mapper, PerClass *c,117 SizeClassAllocator *allocator, uptr class_id, uptr count) {118 CHECK_GE(c->count, count);119 const uptr first_idx_to_drain = c->count - count;120 c->count -= count;121 allocator->ReturnToAllocator(memory_mapper, &stats_, class_id,122 &c->chunks[first_idx_to_drain], count);123 }124};125 126// Cache used by SizeClassAllocator32.127template <class SizeClassAllocator>128struct SizeClassAllocator32LocalCache {129 typedef SizeClassAllocator Allocator;130 typedef typename Allocator::TransferBatch TransferBatch;131 132 void Init(AllocatorGlobalStats *s) {133 stats_.Init();134 if (s)135 s->Register(&stats_);136 }137 138 // Returns a TransferBatch suitable for class_id.139 TransferBatch *CreateBatch(uptr class_id, SizeClassAllocator *allocator,140 TransferBatch *b) {141 if (uptr batch_class_id = per_class_[class_id].batch_class_id)142 return (TransferBatch*)Allocate(allocator, batch_class_id);143 return b;144 }145 146 // Destroys TransferBatch b.147 void DestroyBatch(uptr class_id, SizeClassAllocator *allocator,148 TransferBatch *b) {149 if (uptr batch_class_id = per_class_[class_id].batch_class_id)150 Deallocate(allocator, batch_class_id, b);151 }152 153 void Destroy(SizeClassAllocator *allocator, AllocatorGlobalStats *s) {154 Drain(allocator);155 if (s)156 s->Unregister(&stats_);157 }158 159 void *Allocate(SizeClassAllocator *allocator, uptr class_id) {160 CHECK_NE(class_id, 0UL);161 CHECK_LT(class_id, kNumClasses);162 PerClass *c = &per_class_[class_id];163 if (UNLIKELY(c->count == 0)) {164 if (UNLIKELY(!Refill(c, allocator, class_id)))165 return nullptr;166 DCHECK_GT(c->count, 0);167 }168 void *res = c->batch[--c->count];169 PREFETCH(c->batch[c->count > 0 ? c->count - 1 : 0]);170 stats_.Add(AllocatorStatAllocated, c->class_size);171 return res;172 }173 174 void Deallocate(SizeClassAllocator *allocator, uptr class_id, void *p) {175 CHECK_NE(class_id, 0UL);176 CHECK_LT(class_id, kNumClasses);177 // If the first allocator call on a new thread is a deallocation, then178 // max_count will be zero, leading to check failure.179 PerClass *c = &per_class_[class_id];180 InitCache(c);181 if (UNLIKELY(c->count == c->max_count))182 Drain(c, allocator, class_id);183 c->batch[c->count++] = p;184 stats_.Sub(AllocatorStatAllocated, c->class_size);185 }186 187 void Drain(SizeClassAllocator *allocator) {188 for (uptr i = 1; i < kNumClasses; i++) {189 PerClass *c = &per_class_[i];190 while (c->count > 0)191 Drain(c, allocator, i);192 }193 }194 195 private:196 typedef typename Allocator::SizeClassMapT SizeClassMap;197 static const uptr kBatchClassID = SizeClassMap::kBatchClassID;198 static const uptr kNumClasses = SizeClassMap::kNumClasses;199 // If kUseSeparateSizeClassForBatch is true, all TransferBatch objects are200 // allocated from kBatchClassID size class (except for those that are needed201 // for kBatchClassID itself). The goal is to have TransferBatches in a totally202 // different region of RAM to improve security.203 static const bool kUseSeparateSizeClassForBatch =204 Allocator::kUseSeparateSizeClassForBatch;205 206 struct PerClass {207 uptr count;208 uptr max_count;209 uptr class_size;210 uptr batch_class_id;211 void *batch[2 * TransferBatch::kMaxNumCached];212 };213 PerClass per_class_[kNumClasses];214 AllocatorStats stats_;215 216 void InitCache(PerClass *c) {217 if (LIKELY(c->max_count))218 return;219 const uptr batch_class_id = SizeClassMap::ClassID(sizeof(TransferBatch));220 for (uptr i = 1; i < kNumClasses; i++) {221 PerClass *c = &per_class_[i];222 const uptr size = Allocator::ClassIdToSize(i);223 const uptr max_cached = TransferBatch::MaxCached(size);224 c->max_count = 2 * max_cached;225 c->class_size = size;226 // Precompute the class id to use to store batches for the current class227 // id. 0 means the class size is large enough to store a batch within one228 // of the chunks. If using a separate size class, it will always be229 // kBatchClassID, except for kBatchClassID itself.230 if (kUseSeparateSizeClassForBatch) {231 c->batch_class_id = (i == kBatchClassID) ? 0 : kBatchClassID;232 } else {233 c->batch_class_id = (size <234 TransferBatch::AllocationSizeRequiredForNElements(max_cached)) ?235 batch_class_id : 0;236 }237 }238 DCHECK_NE(c->max_count, 0UL);239 }240 241 NOINLINE bool Refill(PerClass *c, SizeClassAllocator *allocator,242 uptr class_id) {243 InitCache(c);244 TransferBatch *b = allocator->AllocateBatch(&stats_, this, class_id);245 if (UNLIKELY(!b))246 return false;247 CHECK_GT(b->Count(), 0);248 b->CopyToArray(c->batch);249 c->count = b->Count();250 DestroyBatch(class_id, allocator, b);251 return true;252 }253 254 NOINLINE void Drain(PerClass *c, SizeClassAllocator *allocator,255 uptr class_id) {256 const uptr count = Min(c->max_count / 2, c->count);257 const uptr first_idx_to_drain = c->count - count;258 TransferBatch *b = CreateBatch(259 class_id, allocator, (TransferBatch *)c->batch[first_idx_to_drain]);260 // Failure to allocate a batch while releasing memory is non recoverable.261 // TODO(alekseys): Figure out how to do it without allocating a new batch.262 if (UNLIKELY(!b)) {263 Report("FATAL: Internal error: %s's allocator failed to allocate a "264 "transfer batch.\n", SanitizerToolName);265 Die();266 }267 b->SetFromArray(&c->batch[first_idx_to_drain], count);268 c->count -= count;269 allocator->DeallocateBatch(&stats_, class_id, b);270 }271};272