1//===-- sanitizer_allocator_primary32.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// Part of the Sanitizer Allocator.
10//
11//===----------------------------------------------------------------------===//
12#ifndef SANITIZER_ALLOCATOR_H
13#error This file must be included inside sanitizer_allocator.h
14#endif
15
16template<class SizeClassAllocator> struct SizeClassAllocator32LocalCache;
17
18// SizeClassAllocator32 -- allocator for 32-bit address space.
19// This allocator can theoretically be used on 64-bit arch, but there it is less
20// efficient than SizeClassAllocator64.
21//
22// [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
23// be returned by MmapOrDie().
24//
25// Region:
26//   a result of a single call to MmapAlignedOrDieOnFatalError(kRegionSize,
27//                                                             kRegionSize).
28// Since the regions are aligned by kRegionSize, there are exactly
29// kNumPossibleRegions possible regions in the address space and so we keep
30// a ByteMap possible_regions to store the size classes of each Region.
31// 0 size class means the region is not used by the allocator.
32//
33// One Region is used to allocate chunks of a single size class.
34// A Region looks like this:
35// UserChunk1 .. UserChunkN <gap> MetaChunkN .. MetaChunk1
36//
37// In order to avoid false sharing the objects of this class should be
38// chache-line aligned.
39
40struct SizeClassAllocator32FlagMasks {  //  Bit masks.
41  enum {
42    kRandomShuffleChunks = 1,
43    kUseSeparateSizeClassForBatch = 2,
44  };
45};
46
47template <class Params>
48class SizeClassAllocator32 {
49 private:
50  static const u64 kTwoLevelByteMapSize1 =
51      (Params::kSpaceSize >> Params::kRegionSizeLog) >> 12;
52  static const u64 kMinFirstMapSizeTwoLevelByteMap = 4;
53
54 public:
55  using AddressSpaceView = typename Params::AddressSpaceView;
56  static const uptr kSpaceBeg = Params::kSpaceBeg;
57  static const u64 kSpaceSize = Params::kSpaceSize;
58  static const uptr kMetadataSize = Params::kMetadataSize;
59  typedef typename Params::SizeClassMap SizeClassMap;
60  static const uptr kRegionSizeLog = Params::kRegionSizeLog;
61  typedef typename Params::MapUnmapCallback MapUnmapCallback;
62  using ByteMap = typename conditional<
63      (kTwoLevelByteMapSize1 < kMinFirstMapSizeTwoLevelByteMap),
64      FlatByteMap<(Params::kSpaceSize >> Params::kRegionSizeLog),
65                  AddressSpaceView>,
66      TwoLevelByteMap<kTwoLevelByteMapSize1, 1 << 12, AddressSpaceView>>::type;
67
68  COMPILER_CHECK(!SANITIZER_SIGN_EXTENDED_ADDRESSES ||
69                 (kSpaceSize & (kSpaceSize - 1)) == 0);
70
71  static const bool kRandomShuffleChunks = Params::kFlags &
72      SizeClassAllocator32FlagMasks::kRandomShuffleChunks;
73  static const bool kUseSeparateSizeClassForBatch = Params::kFlags &
74      SizeClassAllocator32FlagMasks::kUseSeparateSizeClassForBatch;
75
76  struct TransferBatch {
77    static const uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2;
78    void SetFromArray(void *batch[], uptr count) {
79      DCHECK_LE(count, kMaxNumCached);
80      count_ = count;
81      for (uptr i = 0; i < count; i++)
82        batch_[i] = batch[i];
83    }
84    uptr Count() const { return count_; }
85    void Clear() { count_ = 0; }
86    void Add(void *ptr) {
87      batch_[count_++] = ptr;
88      DCHECK_LE(count_, kMaxNumCached);
89    }
90    void CopyToArray(void *to_batch[]) const {
91      for (uptr i = 0, n = Count(); i < n; i++)
92        to_batch[i] = batch_[i];
93    }
94
95    // How much memory do we need for a batch containing n elements.
96    static uptr AllocationSizeRequiredForNElements(uptr n) {
97      return sizeof(uptr) * 2 + sizeof(void *) * n;
98    }
99    static uptr MaxCached(uptr size) {
100      return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(size));
101    }
102
103    TransferBatch *next;
104
105   private:
106    uptr count_;
107    void *batch_[kMaxNumCached];
108  };
109
110  static const uptr kBatchSize = sizeof(TransferBatch);
111  COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0);
112  COMPILER_CHECK(kBatchSize == SizeClassMap::kMaxNumCachedHint * sizeof(uptr));
113
114  static uptr ClassIdToSize(uptr class_id) {
115    return (class_id == SizeClassMap::kBatchClassID) ?
116        kBatchSize : SizeClassMap::Size(class_id);
117  }
118
119  typedef SizeClassAllocator32<Params> ThisT;
120  typedef SizeClassAllocator32LocalCache<ThisT> AllocatorCache;
121
122  void Init(s32 release_to_os_interval_ms) {
123    possible_regions.Init();
124    internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));
125  }
126
127  s32 ReleaseToOSIntervalMs() const {
128    return kReleaseToOSIntervalNever;
129  }
130
131  void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
132    // This is empty here. Currently only implemented in 64-bit allocator.
133  }
134
135  void ForceReleaseToOS() {
136    // Currently implemented in 64-bit allocator only.
137  }
138
139  void *MapWithCallback(uptr size) {
140    void *res = MmapOrDie(size, PrimaryAllocatorName);
141    MapUnmapCallback().OnMap((uptr)res, size);
142    return res;
143  }
144
145  void UnmapWithCallback(uptr beg, uptr size) {
146    MapUnmapCallback().OnUnmap(beg, size);
147    UnmapOrDie(reinterpret_cast<void *>(beg), size);
148  }
149
150  static bool CanAllocate(uptr size, uptr alignment) {
151    return size <= SizeClassMap::kMaxSize &&
152      alignment <= SizeClassMap::kMaxSize;
153  }
154
155  void *GetMetaData(const void *p) {
156    CHECK(PointerIsMine(p));
157    uptr mem = reinterpret_cast<uptr>(p);
158    uptr beg = ComputeRegionBeg(mem);
159    uptr size = ClassIdToSize(GetSizeClass(p));
160    u32 offset = mem - beg;
161    uptr n = offset / (u32)size;  // 32-bit division
162    uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;
163    return reinterpret_cast<void*>(meta);
164  }
165
166  NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,
167                                        uptr class_id) {
168    DCHECK_LT(class_id, kNumClasses);
169    SizeClassInfo *sci = GetSizeClassInfo(class_id);
170    SpinMutexLock l(&sci->mutex);
171    if (sci->free_list.empty()) {
172      if (UNLIKELY(!PopulateFreeList(stat, c, sci, class_id)))
173        return nullptr;
174      DCHECK(!sci->free_list.empty());
175    }
176    TransferBatch *b = sci->free_list.front();
177    sci->free_list.pop_front();
178    return b;
179  }
180
181  NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,
182                                TransferBatch *b) {
183    DCHECK_LT(class_id, kNumClasses);
184    CHECK_GT(b->Count(), 0);
185    SizeClassInfo *sci = GetSizeClassInfo(class_id);
186    SpinMutexLock l(&sci->mutex);
187    sci->free_list.push_front(b);
188  }
189
190  bool PointerIsMine(const void *p) {
191    uptr mem = reinterpret_cast<uptr>(p);
192    if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
193      mem &= (kSpaceSize - 1);
194    if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)
195      return false;
196    return GetSizeClass(p) != 0;
197  }
198
199  uptr GetSizeClass(const void *p) {
200    return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))];
201  }
202
203  void *GetBlockBegin(const void *p) {
204    CHECK(PointerIsMine(p));
205    uptr mem = reinterpret_cast<uptr>(p);
206    uptr beg = ComputeRegionBeg(mem);
207    uptr size = ClassIdToSize(GetSizeClass(p));
208    u32 offset = mem - beg;
209    u32 n = offset / (u32)size;  // 32-bit division
210    uptr res = beg + (n * (u32)size);
211    return reinterpret_cast<void*>(res);
212  }
213
214  uptr GetActuallyAllocatedSize(void *p) {
215    CHECK(PointerIsMine(p));
216    return ClassIdToSize(GetSizeClass(p));
217  }
218
219  static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
220
221  uptr TotalMemoryUsed() {
222    // No need to lock here.
223    uptr res = 0;
224    for (uptr i = 0; i < kNumPossibleRegions; i++)
225      if (possible_regions[i])
226        res += kRegionSize;
227    return res;
228  }
229
230  void TestOnlyUnmap() {
231    for (uptr i = 0; i < kNumPossibleRegions; i++)
232      if (possible_regions[i])
233        UnmapWithCallback((i * kRegionSize), kRegionSize);
234  }
235
236  // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
237  // introspection API.
238  void ForceLock() {
239    for (uptr i = 0; i < kNumClasses; i++) {
240      GetSizeClassInfo(i)->mutex.Lock();
241    }
242  }
243
244  void ForceUnlock() {
245    for (int i = kNumClasses - 1; i >= 0; i--) {
246      GetSizeClassInfo(i)->mutex.Unlock();
247    }
248  }
249
250  // Iterate over all existing chunks.
251  // The allocator must be locked when calling this function.
252  void ForEachChunk(ForEachChunkCallback callback, void *arg) {
253    for (uptr region = 0; region < kNumPossibleRegions; region++)
254      if (possible_regions[region]) {
255        uptr chunk_size = ClassIdToSize(possible_regions[region]);
256        uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);
257        uptr region_beg = region * kRegionSize;
258        for (uptr chunk = region_beg;
259             chunk < region_beg + max_chunks_in_region * chunk_size;
260             chunk += chunk_size) {
261          // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
262          callback(chunk, arg);
263        }
264      }
265  }
266
267  void PrintStats() {}
268
269  static uptr AdditionalSize() { return 0; }
270
271  typedef SizeClassMap SizeClassMapT;
272  static const uptr kNumClasses = SizeClassMap::kNumClasses;
273
274 private:
275  static const uptr kRegionSize = 1 << kRegionSizeLog;
276  static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;
277
278  struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) SizeClassInfo {
279    StaticSpinMutex mutex;
280    IntrusiveList<TransferBatch> free_list;
281    u32 rand_state;
282  };
283  COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0);
284
285  uptr ComputeRegionId(uptr mem) const {
286    if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
287      mem &= (kSpaceSize - 1);
288    const uptr res = mem >> kRegionSizeLog;
289    CHECK_LT(res, kNumPossibleRegions);
290    return res;
291  }
292
293  uptr ComputeRegionBeg(uptr mem) {
294    return mem & ~(kRegionSize - 1);
295  }
296
297  uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
298    DCHECK_LT(class_id, kNumClasses);
299    const uptr res = reinterpret_cast<uptr>(MmapAlignedOrDieOnFatalError(
300        kRegionSize, kRegionSize, PrimaryAllocatorName));
301    if (UNLIKELY(!res))
302      return 0;
303    MapUnmapCallback().OnMap(res, kRegionSize);
304    stat->Add(AllocatorStatMapped, kRegionSize);
305    CHECK(IsAligned(res, kRegionSize));
306    possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id));
307    return res;
308  }
309
310  SizeClassInfo *GetSizeClassInfo(uptr class_id) {
311    DCHECK_LT(class_id, kNumClasses);
312    return &size_class_info_array[class_id];
313  }
314
315  bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id,
316                       TransferBatch **current_batch, uptr max_count,
317                       uptr *pointers_array, uptr count) {
318    // If using a separate class for batches, we do not need to shuffle it.
319    if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch ||
320        class_id != SizeClassMap::kBatchClassID))
321      RandomShuffle(pointers_array, count, &sci->rand_state);
322    TransferBatch *b = *current_batch;
323    for (uptr i = 0; i < count; i++) {
324      if (!b) {
325        b = c->CreateBatch(class_id, this, (TransferBatch*)pointers_array[i]);
326        if (UNLIKELY(!b))
327          return false;
328        b->Clear();
329      }
330      b->Add((void*)pointers_array[i]);
331      if (b->Count() == max_count) {
332        sci->free_list.push_back(b);
333        b = nullptr;
334      }
335    }
336    *current_batch = b;
337    return true;
338  }
339
340  bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
341                        SizeClassInfo *sci, uptr class_id) {
342    const uptr region = AllocateRegion(stat, class_id);
343    if (UNLIKELY(!region))
344      return false;
345    if (kRandomShuffleChunks)
346      if (UNLIKELY(sci->rand_state == 0))
347        // The random state is initialized from ASLR (PIE) and time.
348        sci->rand_state = reinterpret_cast<uptr>(sci) ^ NanoTime();
349    const uptr size = ClassIdToSize(class_id);
350    const uptr n_chunks = kRegionSize / (size + kMetadataSize);
351    const uptr max_count = TransferBatch::MaxCached(size);
352    DCHECK_GT(max_count, 0);
353    TransferBatch *b = nullptr;
354    constexpr uptr kShuffleArraySize = 48;
355    uptr shuffle_array[kShuffleArraySize];
356    uptr count = 0;
357    for (uptr i = region; i < region + n_chunks * size; i += size) {
358      shuffle_array[count++] = i;
359      if (count == kShuffleArraySize) {
360        if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
361                                      shuffle_array, count)))
362          return false;
363        count = 0;
364      }
365    }
366    if (count) {
367      if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
368                                    shuffle_array, count)))
369        return false;
370    }
371    if (b) {
372      CHECK_GT(b->Count(), 0);
373      sci->free_list.push_back(b);
374    }
375    return true;
376  }
377
378  ByteMap possible_regions;
379  SizeClassInfo size_class_info_array[kNumClasses];
380};
381