1 //===-- local_cache.h -------------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 #ifndef SCUDO_LOCAL_CACHE_H_
10 #define SCUDO_LOCAL_CACHE_H_
12 #include "internal_defs.h"
18 template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache {
19 typedef typename SizeClassAllocator::SizeClassMap SizeClassMap;
20 typedef typename SizeClassAllocator::CompactPtrT CompactPtrT;
22 struct TransferBatch {
23 static const u32 MaxNumCached = SizeClassMap::MaxNumCachedHint;
24 void setFromArray(CompactPtrT *Array, u32 N) {
25 DCHECK_LE(N, MaxNumCached);
27 memcpy(Batch, Array, sizeof(Batch[0]) * Count);
29 void clear() { Count = 0; }
30 void add(CompactPtrT P) {
31 DCHECK_LT(Count, MaxNumCached);
34 void copyToArray(CompactPtrT *Array) const {
35 memcpy(Array, Batch, sizeof(Batch[0]) * Count);
37 u32 getCount() const { return Count; }
38 CompactPtrT get(u32 I) const {
42 static u32 getMaxCached(uptr Size) {
43 return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size));
49 CompactPtrT Batch[MaxNumCached];
52 void init(GlobalStats *S, SizeClassAllocator *A) {
60 void destroy(GlobalStats *S) {
66 void *allocate(uptr ClassId) {
67 DCHECK_LT(ClassId, NumClasses);
68 PerClass *C = &PerClassArray[ClassId];
70 if (UNLIKELY(!refill(C, ClassId)))
72 DCHECK_GT(C->Count, 0);
74 // We read ClassSize first before accessing Chunks because it's adjacent to
75 // Count, while Chunks might be further off (depending on Count). That keeps
76 // the memory accesses in close quarters.
77 const uptr ClassSize = C->ClassSize;
78 CompactPtrT CompactP = C->Chunks[--C->Count];
79 Stats.add(StatAllocated, ClassSize);
80 Stats.sub(StatFree, ClassSize);
81 return Allocator->decompactPtr(ClassId, CompactP);
84 void deallocate(uptr ClassId, void *P) {
85 CHECK_LT(ClassId, NumClasses);
86 PerClass *C = &PerClassArray[ClassId];
87 // We still have to initialize the cache in the event that the first heap
88 // operation in a thread is a deallocation.
90 if (C->Count == C->MaxCount)
92 // See comment in allocate() about memory accesses.
93 const uptr ClassSize = C->ClassSize;
94 C->Chunks[C->Count++] =
95 Allocator->compactPtr(ClassId, reinterpret_cast<uptr>(P));
96 Stats.sub(StatAllocated, ClassSize);
97 Stats.add(StatFree, ClassSize);
100 bool isEmpty() const {
101 for (uptr I = 0; I < NumClasses; ++I)
102 if (PerClassArray[I].Count)
108 // Drain BatchClassId last as createBatch can refill it.
109 for (uptr I = 0; I < NumClasses; ++I) {
110 if (I == BatchClassId)
112 while (PerClassArray[I].Count > 0)
113 drain(&PerClassArray[I], I);
115 while (PerClassArray[BatchClassId].Count > 0)
116 drain(&PerClassArray[BatchClassId], BatchClassId);
120 TransferBatch *createBatch(uptr ClassId, void *B) {
121 if (ClassId != BatchClassId)
122 B = allocate(BatchClassId);
123 return reinterpret_cast<TransferBatch *>(B);
126 LocalStats &getStats() { return Stats; }
129 static const uptr NumClasses = SizeClassMap::NumClasses;
130 static const uptr BatchClassId = SizeClassMap::BatchClassId;
134 // Note: ClassSize is zero for the transfer batch.
136 CompactPtrT Chunks[2 * TransferBatch::MaxNumCached];
138 PerClass PerClassArray[NumClasses] = {};
140 SizeClassAllocator *Allocator = nullptr;
142 ALWAYS_INLINE void initCacheMaybe(PerClass *C) {
143 if (LIKELY(C->MaxCount))
146 DCHECK_NE(C->MaxCount, 0U);
149 NOINLINE void initCache() {
150 for (uptr I = 0; I < NumClasses; I++) {
151 PerClass *P = &PerClassArray[I];
152 const uptr Size = SizeClassAllocator::getSizeByClassId(I);
153 P->MaxCount = 2 * TransferBatch::getMaxCached(Size);
154 if (I != BatchClassId) {
157 // ClassSize in this struct is only used for malloc/free stats, which
158 // should only track user allocations, not internal movements.
164 void destroyBatch(uptr ClassId, void *B) {
165 if (ClassId != BatchClassId)
166 deallocate(BatchClassId, B);
169 NOINLINE bool refill(PerClass *C, uptr ClassId) {
171 TransferBatch *B = Allocator->popBatch(this, ClassId);
174 DCHECK_GT(B->getCount(), 0);
175 C->Count = B->getCount();
176 B->copyToArray(C->Chunks);
178 destroyBatch(ClassId, B);
182 NOINLINE void drain(PerClass *C, uptr ClassId) {
183 const u32 Count = Min(C->MaxCount / 2, C->Count);
185 createBatch(ClassId, Allocator->decompactPtr(ClassId, C->Chunks[0]));
187 reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId));
188 B->setFromArray(&C->Chunks[0], Count);
190 for (uptr I = 0; I < C->Count; I++)
191 C->Chunks[I] = C->Chunks[I + Count];
192 Allocator->pushBatch(ClassId, B);
198 #endif // SCUDO_LOCAL_CACHE_H_