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(&Stats);
30    Allocator = A;
31    initCache();
32  }
33
34  void destroy(GlobalStats *S) {
35    drain();
36    if (LIKELY(S))
37      S->unlink(&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(StatAllocated, ClassSize);
56    Stats.sub(StatFree, 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(StatAllocated, ClassSize);
73    Stats.add(StatFree, 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(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("    %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("    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(BatchClassId, 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