compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h

   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
  16 template<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
  40 struct SizeClassAllocator32FlagMasks {  //  Bit masks.
  41   enum {
  42     kRandomShuffleChunks = 1,
  43     kUseSeparateSizeClassForBatch = 2,
  44   };
  45 };
  46
  47 template <class Params>
  48 class 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 };