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, uptr heap_start = 0) {
123    CHECK(!heap_start);
124    possible_regions.Init();
125    internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));
126  }
127
128  s32 ReleaseToOSIntervalMs() const {
129    return kReleaseToOSIntervalNever;
130  }
131
132  void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
133    // This is empty here. Currently only implemented in 64-bit allocator.
134  }
135
136  void ForceReleaseToOS() {
137    // Currently implemented in 64-bit allocator only.
138  }
139
140  void *MapWithCallback(uptr size) {
141    void *res = MmapOrDie(size, PrimaryAllocatorName);
142    MapUnmapCallback().OnMap((uptr)res, size);
143    return res;
144  }
145
146  void UnmapWithCallback(uptr beg, uptr size) {
147    MapUnmapCallback().OnUnmap(beg, size);
148    UnmapOrDie(reinterpret_cast<void *>(beg), size);
149  }
150
151  static bool CanAllocate(uptr size, uptr alignment) {
152    return size <= SizeClassMap::kMaxSize &&
153      alignment <= SizeClassMap::kMaxSize;
154  }
155
156  void *GetMetaData(const void *p) {
157    CHECK(kMetadataSize);
158    CHECK(PointerIsMine(p));
159    uptr mem = reinterpret_cast<uptr>(p);
160    uptr beg = ComputeRegionBeg(mem);
161    uptr size = ClassIdToSize(GetSizeClass(p));
162    u32 offset = mem - beg;
163    uptr n = offset / (u32)size;  // 32-bit division
164    uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;
165    return reinterpret_cast<void*>(meta);
166  }
167
168  NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,
169                                        uptr class_id) {
170    DCHECK_LT(class_id, kNumClasses);
171    SizeClassInfo *sci = GetSizeClassInfo(class_id);
172    SpinMutexLock l(&sci->mutex);
173    if (sci->free_list.empty()) {
174      if (UNLIKELY(!PopulateFreeList(stat, c, sci, class_id)))
175        return nullptr;
176      DCHECK(!sci->free_list.empty());
177    }
178    TransferBatch *b = sci->free_list.front();
179    sci->free_list.pop_front();
180    return b;
181  }
182
183  NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,
184                                TransferBatch *b) {
185    DCHECK_LT(class_id, kNumClasses);
186    CHECK_GT(b->Count(), 0);
187    SizeClassInfo *sci = GetSizeClassInfo(class_id);
188    SpinMutexLock l(&sci->mutex);
189    sci->free_list.push_front(b);
190  }
191
192  bool PointerIsMine(const void *p) const {
193    uptr mem = reinterpret_cast<uptr>(p);
194    if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
195      mem &= (kSpaceSize - 1);
196    if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)
197      return false;
198    return GetSizeClass(p) != 0;
199  }
200
201  uptr GetSizeClass(const void *p) const {
202    uptr id = ComputeRegionId(reinterpret_cast<uptr>(p));
203    return possible_regions.contains(id) ? possible_regions[id] : 0;
204  }
205
206  void *GetBlockBegin(const void *p) {
207    CHECK(PointerIsMine(p));
208    uptr mem = reinterpret_cast<uptr>(p);
209    uptr beg = ComputeRegionBeg(mem);
210    uptr size = ClassIdToSize(GetSizeClass(p));
211    u32 offset = mem - beg;
212    u32 n = offset / (u32)size;  // 32-bit division
213    uptr res = beg + (n * (u32)size);
214    return reinterpret_cast<void*>(res);
215  }
216
217  uptr GetActuallyAllocatedSize(void *p) {
218    CHECK(PointerIsMine(p));
219    return ClassIdToSize(GetSizeClass(p));
220  }
221
222  static uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
223
224  uptr TotalMemoryUsed() {
225    // No need to lock here.
226    uptr res = 0;
227    for (uptr i = 0; i < kNumPossibleRegions; i++)
228      if (possible_regions[i])
229        res += kRegionSize;
230    return res;
231  }
232
233  void TestOnlyUnmap() {
234    for (uptr i = 0; i < kNumPossibleRegions; i++)
235      if (possible_regions[i])
236        UnmapWithCallback((i * kRegionSize), kRegionSize);
237  }
238
239  // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
240  // introspection API.
241  void ForceLock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
242    for (uptr i = 0; i < kNumClasses; i++) {
243      GetSizeClassInfo(i)->mutex.Lock();
244    }
245  }
246
247  void ForceUnlock() SANITIZER_NO_THREAD_SAFETY_ANALYSIS {
248    for (int i = kNumClasses - 1; i >= 0; i--) {
249      GetSizeClassInfo(i)->mutex.Unlock();
250    }
251  }
252
253  // Iterate over all existing chunks.
254  // The allocator must be locked when calling this function.
255  void ForEachChunk(ForEachChunkCallback callback, void *arg) const {
256    for (uptr region = 0; region < kNumPossibleRegions; region++)
257      if (possible_regions.contains(region) && possible_regions[region]) {
258        uptr chunk_size = ClassIdToSize(possible_regions[region]);
259        uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);
260        uptr region_beg = region * kRegionSize;
261        for (uptr chunk = region_beg;
262             chunk < region_beg + max_chunks_in_region * chunk_size;
263             chunk += chunk_size) {
264          // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
265          callback(chunk, arg);
266        }
267      }
268  }
269
270  void PrintStats() {}
271
272  static uptr AdditionalSize() { return 0; }
273
274  typedef SizeClassMap SizeClassMapT;
275  static const uptr kNumClasses = SizeClassMap::kNumClasses;
276
277 private:
278  static const uptr kRegionSize = 1 << kRegionSizeLog;
279  static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;
280
281  struct ALIGNED(SANITIZER_CACHE_LINE_SIZE) SizeClassInfo {
282    StaticSpinMutex mutex;
283    IntrusiveList<TransferBatch> free_list;
284    u32 rand_state;
285  };
286  COMPILER_CHECK(sizeof(SizeClassInfo) % kCacheLineSize == 0);
287
288  uptr ComputeRegionId(uptr mem) const {
289    if (SANITIZER_SIGN_EXTENDED_ADDRESSES)
290      mem &= (kSpaceSize - 1);
291    const uptr res = mem >> kRegionSizeLog;
292    CHECK_LT(res, kNumPossibleRegions);
293    return res;
294  }
295
296  uptr ComputeRegionBeg(uptr mem) const { return mem & ~(kRegionSize - 1); }
297
298  uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
299    DCHECK_LT(class_id, kNumClasses);
300    const uptr res = reinterpret_cast<uptr>(MmapAlignedOrDieOnFatalError(
301        kRegionSize, kRegionSize, PrimaryAllocatorName));
302    if (UNLIKELY(!res))
303      return 0;
304    MapUnmapCallback().OnMap(res, kRegionSize);
305    stat->Add(AllocatorStatMapped, kRegionSize);
306    CHECK(IsAligned(res, kRegionSize));
307    possible_regions[ComputeRegionId(res)] = class_id;
308    return res;
309  }
310
311  SizeClassInfo *GetSizeClassInfo(uptr class_id) {
312    DCHECK_LT(class_id, kNumClasses);
313    return &size_class_info_array[class_id];
314  }
315
316  bool PopulateBatches(AllocatorCache *c, SizeClassInfo *sci, uptr class_id,
317                       TransferBatch **current_batch, uptr max_count,
318                       uptr *pointers_array, uptr count) {
319    // If using a separate class for batches, we do not need to shuffle it.
320    if (kRandomShuffleChunks && (!kUseSeparateSizeClassForBatch ||
321        class_id != SizeClassMap::kBatchClassID))
322      RandomShuffle(pointers_array, count, &sci->rand_state);
323    TransferBatch *b = *current_batch;
324    for (uptr i = 0; i < count; i++) {
325      if (!b) {
326        b = c->CreateBatch(class_id, this, (TransferBatch*)pointers_array[i]);
327        if (UNLIKELY(!b))
328          return false;
329        b->Clear();
330      }
331      b->Add((void*)pointers_array[i]);
332      if (b->Count() == max_count) {
333        sci->free_list.push_back(b);
334        b = nullptr;
335      }
336    }
337    *current_batch = b;
338    return true;
339  }
340
341  bool PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
342                        SizeClassInfo *sci, uptr class_id) {
343    const uptr region = AllocateRegion(stat, class_id);
344    if (UNLIKELY(!region))
345      return false;
346    if (kRandomShuffleChunks)
347      if (UNLIKELY(sci->rand_state == 0))
348        // The random state is initialized from ASLR (PIE) and time.
349        sci->rand_state = reinterpret_cast<uptr>(sci) ^ NanoTime();
350    const uptr size = ClassIdToSize(class_id);
351    const uptr n_chunks = kRegionSize / (size + kMetadataSize);
352    const uptr max_count = TransferBatch::MaxCached(size);
353    DCHECK_GT(max_count, 0);
354    TransferBatch *b = nullptr;
355    constexpr uptr kShuffleArraySize = 48;
356    UNINITIALIZED uptr shuffle_array[kShuffleArraySize];
357    uptr count = 0;
358    for (uptr i = region; i < region + n_chunks * size; i += size) {
359      shuffle_array[count++] = i;
360      if (count == kShuffleArraySize) {
361        if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
362                                      shuffle_array, count)))
363          return false;
364        count = 0;
365      }
366    }
367    if (count) {
368      if (UNLIKELY(!PopulateBatches(c, sci, class_id, &b, max_count,
369                                    shuffle_array, count)))
370        return false;
371    }
372    if (b) {
373      CHECK_GT(b->Count(), 0);
374      sci->free_list.push_back(b);
375    }
376    return true;
377  }
378
379  ByteMap possible_regions;
380  SizeClassInfo size_class_info_array[kNumClasses];
381};
382