| 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-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// Part of the Sanitizer Allocator. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
#ifndef SANITIZER_ALLOCATOR_H |
| 13 |
#error This file must be included inside sanitizer_allocator.h |
| 14 |
#endif |
| 15 |
|
| 16 |
// Cache used by SizeClassAllocator64. |
| 17 |
template <class SizeClassAllocator> |
| 18 |
struct 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, then |
| 53 |
// 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. |
| 127 |
template <class SizeClassAllocator> |
| 128 |
struct 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 - 1]); |
| 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, then |
| 178 |
// 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 are |
| 200 |
// allocated from kBatchClassID size class (except for those that are needed |
| 201 |
// for kBatchClassID itself). The goal is to have TransferBatches in a totally |
| 202 |
// 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 class |
| 227 |
// id. 0 means the class size is large enough to store a batch within one |
| 228 |
// of the chunks. If using a separate size class, it will always be |
| 229 |
// 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 |
}; |