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 | |
19 | namespace scudo { |
20 | |
21 | template <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 | |
135 | private: |
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 | |