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;
21 struct TransferBatch {
22 static const u32 MaxNumCached = SizeClassMap::MaxNumCachedHint;
23 void setFromArray(void **Array, u32 N) {
24 DCHECK_LE(N, MaxNumCached);
26 memcpy(Batch, Array, sizeof(void *) * Count);
28 void clear() { Count = 0; }
30 DCHECK_LT(Count, MaxNumCached);
33 void copyToArray(void **Array) const {
34 memcpy(Array, Batch, sizeof(void *) * Count);
36 u32 getCount() const { return Count; }
37 void *get(u32 I) const {
41 static u32 getMaxCached(uptr Size) {
42 return Min(MaxNumCached, SizeClassMap::getMaxCachedHint(Size));
48 void *Batch[MaxNumCached];
51 void initLinkerInitialized(GlobalStats *S, SizeClassAllocator *A) {
52 Stats.initLinkerInitialized();
58 void init(GlobalStats *S, SizeClassAllocator *A) {
59 memset(this, 0, sizeof(*this));
60 initLinkerInitialized(S, A);
63 void destroy(GlobalStats *S) {
69 void *allocate(uptr ClassId) {
70 DCHECK_LT(ClassId, NumClasses);
71 PerClass *C = &PerClassArray[ClassId];
73 if (UNLIKELY(!refill(C, ClassId)))
75 DCHECK_GT(C->Count, 0);
77 // We read ClassSize first before accessing Chunks because it's adjacent to
78 // Count, while Chunks might be further off (depending on Count). That keeps
79 // the memory accesses in close quarters.
80 const uptr ClassSize = C->ClassSize;
81 void *P = C->Chunks[--C->Count];
82 // The jury is still out as to whether any kind of PREFETCH here increases
83 // performance. It definitely decreases performance on Android though.
84 // if (!SCUDO_ANDROID) PREFETCH(P);
85 Stats.add(StatAllocated, ClassSize);
86 Stats.sub(StatFree, ClassSize);
90 void deallocate(uptr ClassId, void *P) {
91 CHECK_LT(ClassId, NumClasses);
92 PerClass *C = &PerClassArray[ClassId];
93 // We still have to initialize the cache in the event that the first heap
94 // operation in a thread is a deallocation.
96 if (C->Count == C->MaxCount)
98 // See comment in allocate() about memory accesses.
99 const uptr ClassSize = C->ClassSize;
100 C->Chunks[C->Count++] = P;
101 Stats.sub(StatAllocated, ClassSize);
102 Stats.add(StatFree, ClassSize);
106 for (uptr I = 0; I < NumClasses; I++) {
107 PerClass *C = &PerClassArray[I];
113 TransferBatch *createBatch(uptr ClassId, void *B) {
114 if (ClassId != SizeClassMap::BatchClassId)
115 B = allocate(SizeClassMap::BatchClassId);
116 return reinterpret_cast<TransferBatch *>(B);
119 LocalStats &getStats() { return Stats; }
122 static const uptr NumClasses = SizeClassMap::NumClasses;
127 void *Chunks[2 * TransferBatch::MaxNumCached];
129 PerClass PerClassArray[NumClasses];
131 SizeClassAllocator *Allocator;
133 ALWAYS_INLINE void initCacheMaybe(PerClass *C) {
134 if (LIKELY(C->MaxCount))
137 DCHECK_NE(C->MaxCount, 0U);
140 NOINLINE void initCache() {
141 for (uptr I = 0; I < NumClasses; I++) {
142 PerClass *P = &PerClassArray[I];
143 const uptr Size = SizeClassAllocator::getSizeByClassId(I);
144 P->MaxCount = 2 * TransferBatch::getMaxCached(Size);
149 void destroyBatch(uptr ClassId, void *B) {
150 if (ClassId != SizeClassMap::BatchClassId)
151 deallocate(SizeClassMap::BatchClassId, B);
154 NOINLINE bool refill(PerClass *C, uptr ClassId) {
156 TransferBatch *B = Allocator->popBatch(this, ClassId);
159 DCHECK_GT(B->getCount(), 0);
160 C->Count = B->getCount();
161 B->copyToArray(C->Chunks);
162 destroyBatch(ClassId, B);
166 NOINLINE void drain(PerClass *C, uptr ClassId) {
167 const u32 Count = Min(C->MaxCount / 2, C->Count);
168 TransferBatch *B = createBatch(ClassId, C->Chunks[0]);
171 SizeClassAllocator::getSizeByClassId(SizeClassMap::BatchClassId));
172 B->setFromArray(&C->Chunks[0], Count);
174 for (uptr I = 0; I < C->Count; I++)
175 C->Chunks[I] = C->Chunks[I + Count];
176 Allocator->pushBatch(ClassId, B);
182 #endif // SCUDO_LOCAL_CACHE_H_