1//===-- 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#ifndef SCUDO_LOCAL_CACHE_H_
10#define SCUDO_LOCAL_CACHE_H_
11
12#include "internal_defs.h"
13#include "list.h"
14#include "platform.h"
15#include "report.h"
16#include "stats.h"
17#include "string_utils.h"
18
19namespace scudo {
20
21template <class SizeClassAllocator> struct SizeClassAllocatorLocalCache {
22 typedef typename SizeClassAllocator::SizeClassMap SizeClassMap;
23 typedef typename SizeClassAllocator::CompactPtrT CompactPtrT;
24
25 void init(GlobalStats *S, SizeClassAllocator *A) {
26 DCHECK(isEmpty());
27 Stats.init();
28 if (LIKELY(S))
29 S->link(S: &Stats);
30 Allocator = A;
31 initCache();
32 }
33
34 void destroy(GlobalStats *S) {
35 drain();
36 if (LIKELY(S))
37 S->unlink(S: &Stats);
38 }
39
40 void *allocate(uptr ClassId) {
41 DCHECK_LT(ClassId, NumClasses);
42 PerClass *C = &PerClassArray[ClassId];
43 if (C->Count == 0) {
44 // Refill half of the number of max cached.
45 DCHECK_GT(C->MaxCount / 2, 0U);
46 if (UNLIKELY(!refill(C, ClassId, C->MaxCount / 2)))
47 return nullptr;
48 DCHECK_GT(C->Count, 0);
49 }
50 // We read ClassSize first before accessing Chunks because it's adjacent to
51 // Count, while Chunks might be further off (depending on Count). That keeps
52 // the memory accesses in close quarters.
53 const uptr ClassSize = C->ClassSize;
54 CompactPtrT CompactP = C->Chunks[--C->Count];
55 Stats.add(I: StatAllocated, V: ClassSize);
56 Stats.sub(I: StatFree, V: ClassSize);
57 return Allocator->decompactPtr(ClassId, CompactP);
58 }
59
60 bool deallocate(uptr ClassId, void *P) {
61 CHECK_LT(ClassId, NumClasses);
62 PerClass *C = &PerClassArray[ClassId];
63
64 // If the cache is full, drain half of blocks back to the main allocator.
65 const bool NeedToDrainCache = C->Count == C->MaxCount;
66 if (NeedToDrainCache)
67 drain(C, ClassId);
68 // See comment in allocate() about memory accesses.
69 const uptr ClassSize = C->ClassSize;
70 C->Chunks[C->Count++] =
71 Allocator->compactPtr(ClassId, reinterpret_cast<uptr>(P));
72 Stats.sub(I: StatAllocated, V: ClassSize);
73 Stats.add(I: StatFree, V: ClassSize);
74
75 return NeedToDrainCache;
76 }
77
78 bool isEmpty() const {
79 for (uptr I = 0; I < NumClasses; ++I)
80 if (PerClassArray[I].Count)
81 return false;
82 return true;
83 }
84
85 void drain() {
86 // Drain BatchClassId last as it may be needed while draining normal blocks.
87 for (uptr I = 0; I < NumClasses; ++I) {
88 if (I == BatchClassId)
89 continue;
90 while (PerClassArray[I].Count > 0)
91 drain(&PerClassArray[I], I);
92 }
93 while (PerClassArray[BatchClassId].Count > 0)
94 drain(&PerClassArray[BatchClassId], BatchClassId);
95 DCHECK(isEmpty());
96 }
97
98 void *getBatchClassBlock() {
99 void *B = allocate(ClassId: BatchClassId);
100 if (UNLIKELY(!B))
101 reportOutOfMemory(SizeClassAllocator::getSizeByClassId(BatchClassId));
102 return B;
103 }
104
105 LocalStats &getStats() { return Stats; }
106
107 void getStats(ScopedString *Str) {
108 bool EmptyCache = true;
109 for (uptr I = 0; I < NumClasses; ++I) {
110 if (PerClassArray[I].Count == 0)
111 continue;
112
113 EmptyCache = false;
114 // The size of BatchClass is set to 0 intentionally. See the comment in
115 // initCache() for more details.
116 const uptr ClassSize = I == BatchClassId
117 ? SizeClassAllocator::getSizeByClassId(I)
118 : PerClassArray[I].ClassSize;
119 // Note that the string utils don't support printing u16 thus we cast it
120 // to a common use type uptr.
121 Str->append(Format: " %02zu (%6zu): cached: %4zu max: %4zu\n", I, ClassSize,
122 static_cast<uptr>(PerClassArray[I].Count),
123 static_cast<uptr>(PerClassArray[I].MaxCount));
124 }
125
126 if (EmptyCache)
127 Str->append(Format: " No block is cached.\n");
128 }
129
130 static u16 getMaxCached(uptr Size) {
131 return Min(SizeClassMap::MaxNumCachedHint,
132 SizeClassMap::getMaxCachedHint(Size));
133 }
134
135private:
136 static const uptr NumClasses = SizeClassMap::NumClasses;
137 static const uptr BatchClassId = SizeClassMap::BatchClassId;
138 struct alignas(SCUDO_CACHE_LINE_SIZE) PerClass {
139 u16 Count;
140 u16 MaxCount;
141 // Note: ClassSize is zero for the transfer batch.
142 uptr ClassSize;
143 CompactPtrT Chunks[2 * SizeClassMap::MaxNumCachedHint];
144 };
145 PerClass PerClassArray[NumClasses] = {};
146 LocalStats Stats;
147 SizeClassAllocator *Allocator = nullptr;
148
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 = static_cast<u16>(2 * getMaxCached(Size));
154 if (I != BatchClassId) {
155 P->ClassSize = Size;
156 } else {
157 // ClassSize in this struct is only used for malloc/free stats, which
158 // should only track user allocations, not internal movements.
159 P->ClassSize = 0;
160 }
161 }
162 }
163
164 void destroyBatch(uptr ClassId, void *B) {
165 if (ClassId != BatchClassId)
166 deallocate(ClassId: BatchClassId, P: B);
167 }
168
169 NOINLINE bool refill(PerClass *C, uptr ClassId, u16 MaxRefill) {
170 const u16 NumBlocksRefilled =
171 Allocator->popBlocks(this, ClassId, C->Chunks, MaxRefill);
172 DCHECK_LE(NumBlocksRefilled, MaxRefill);
173 C->Count = static_cast<u16>(C->Count + NumBlocksRefilled);
174 return NumBlocksRefilled != 0;
175 }
176
177 NOINLINE void drain(PerClass *C, uptr ClassId) {
178 const u16 Count = Min(static_cast<u16>(C->MaxCount / 2), C->Count);
179 Allocator->pushBlocks(this, ClassId, &C->Chunks[0], Count);
180 // u16 will be promoted to int by arithmetic type conversion.
181 C->Count = static_cast<u16>(C->Count - Count);
182 for (u16 I = 0; I < C->Count; I++)
183 C->Chunks[I] = C->Chunks[I + Count];
184 }
185};
186
187} // namespace scudo
188
189#endif // SCUDO_LOCAL_CACHE_H_
190

source code of compiler-rt/lib/scudo/standalone/local_cache.h