contrib/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h

   1 //===-- sanitizer_allocator_primary32.h -------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Part of the Sanitizer Allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #ifndef SANITIZER_ALLOCATOR_H
  14 #error This file must be included inside sanitizer_allocator.h
  15 #endif
  16
  17 template<class SizeClassAllocator> struct SizeClassAllocator32LocalCache;
  18
  19 // SizeClassAllocator32 -- allocator for 32-bit address space.
  20 // This allocator can theoretically be used on 64-bit arch, but there it is less
  21 // efficient than SizeClassAllocator64.
  22 //
  23 // [kSpaceBeg, kSpaceBeg + kSpaceSize) is the range of addresses which can
  24 // be returned by MmapOrDie().
  25 //
  26 // Region:
  27 //   a result of a single call to MmapAlignedOrDie(kRegionSize, 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 template <const uptr kSpaceBeg, const u64 kSpaceSize,
  40           const uptr kMetadataSize, class SizeClassMap,
  41           const uptr kRegionSizeLog,
  42           class ByteMap,
  43           class MapUnmapCallback = NoOpMapUnmapCallback>
  44 class SizeClassAllocator32 {
  45  public:
  46   struct TransferBatch {
  47     static const uptr kMaxNumCached = SizeClassMap::kMaxNumCachedHint - 2;
  48     void SetFromArray(uptr region_beg_unused, void *batch[], uptr count) {
  49       count_ = count;
  50       CHECK_LE(count_, kMaxNumCached);
  51       for (uptr i = 0; i < count; i++)
  52         batch_[i] = batch[i];
  53     }
  54     uptr Count() const { return count_; }
  55     void Clear() { count_ = 0; }
  56     void Add(void *ptr) {
  57       batch_[count_++] = ptr;
  58       CHECK_LE(count_, kMaxNumCached);
  59     }
  60     void CopyToArray(void *to_batch[]) {
  61       for (uptr i = 0, n = Count(); i < n; i++)
  62         to_batch[i] = batch_[i];
  63     }
  64
  65     // How much memory do we need for a batch containing n elements.
  66     static uptr AllocationSizeRequiredForNElements(uptr n) {
  67       return sizeof(uptr) * 2 + sizeof(void *) * n;
  68     }
  69     static uptr MaxCached(uptr class_id) {
  70       return Min(kMaxNumCached, SizeClassMap::MaxCachedHint(class_id));
  71     }
  72
  73     TransferBatch *next;
  74
  75    private:
  76     uptr count_;
  77     void *batch_[kMaxNumCached];
  78   };
  79
  80   static const uptr kBatchSize = sizeof(TransferBatch);
  81   COMPILER_CHECK((kBatchSize & (kBatchSize - 1)) == 0);
  82   COMPILER_CHECK(sizeof(TransferBatch) ==
  83                  SizeClassMap::kMaxNumCachedHint * sizeof(uptr));
  84
  85   static uptr ClassIdToSize(uptr class_id) {
  86     return SizeClassMap::Size(class_id);
  87   }
  88
  89   typedef SizeClassAllocator32<kSpaceBeg, kSpaceSize, kMetadataSize,
  90       SizeClassMap, kRegionSizeLog, ByteMap, MapUnmapCallback> ThisT;
  91   typedef SizeClassAllocator32LocalCache<ThisT> AllocatorCache;
  92
  93   void Init(s32 release_to_os_interval_ms) {
  94     possible_regions.TestOnlyInit();
  95     internal_memset(size_class_info_array, 0, sizeof(size_class_info_array));
  96   }
  97
  98   s32 ReleaseToOSIntervalMs() const {
  99     return kReleaseToOSIntervalNever;
 100   }
 101
 102   void SetReleaseToOSIntervalMs(s32 release_to_os_interval_ms) {
 103     // This is empty here. Currently only implemented in 64-bit allocator.
 104   }
 105
 106   void *MapWithCallback(uptr size) {
 107     size = RoundUpTo(size, GetPageSizeCached());
 108     void *res = MmapOrDie(size, "SizeClassAllocator32");
 109     MapUnmapCallback().OnMap((uptr)res, size);
 110     return res;
 111   }
 112
 113   void UnmapWithCallback(uptr beg, uptr size) {
 114     MapUnmapCallback().OnUnmap(beg, size);
 115     UnmapOrDie(reinterpret_cast<void *>(beg), size);
 116   }
 117
 118   static bool CanAllocate(uptr size, uptr alignment) {
 119     return size <= SizeClassMap::kMaxSize &&
 120       alignment <= SizeClassMap::kMaxSize;
 121   }
 122
 123   void *GetMetaData(const void *p) {
 124     CHECK(PointerIsMine(p));
 125     uptr mem = reinterpret_cast<uptr>(p);
 126     uptr beg = ComputeRegionBeg(mem);
 127     uptr size = ClassIdToSize(GetSizeClass(p));
 128     u32 offset = mem - beg;
 129     uptr n = offset / (u32)size;  // 32-bit division
 130     uptr meta = (beg + kRegionSize) - (n + 1) * kMetadataSize;
 131     return reinterpret_cast<void*>(meta);
 132   }
 133
 134   NOINLINE TransferBatch *AllocateBatch(AllocatorStats *stat, AllocatorCache *c,
 135                                         uptr class_id) {
 136     CHECK_LT(class_id, kNumClasses);
 137     SizeClassInfo *sci = GetSizeClassInfo(class_id);
 138     SpinMutexLock l(&sci->mutex);
 139     if (sci->free_list.empty())
 140       PopulateFreeList(stat, c, sci, class_id);
 141     CHECK(!sci->free_list.empty());
 142     TransferBatch *b = sci->free_list.front();
 143     sci->free_list.pop_front();
 144     return b;
 145   }
 146
 147   NOINLINE void DeallocateBatch(AllocatorStats *stat, uptr class_id,
 148                                 TransferBatch *b) {
 149     CHECK_LT(class_id, kNumClasses);
 150     SizeClassInfo *sci = GetSizeClassInfo(class_id);
 151     SpinMutexLock l(&sci->mutex);
 152     CHECK_GT(b->Count(), 0);
 153     sci->free_list.push_front(b);
 154   }
 155
 156   uptr GetRegionBeginBySizeClass(uptr class_id) { return 0; }
 157
 158   bool PointerIsMine(const void *p) {
 159     uptr mem = reinterpret_cast<uptr>(p);
 160     if (mem < kSpaceBeg || mem >= kSpaceBeg + kSpaceSize)
 161       return false;
 162     return GetSizeClass(p) != 0;
 163   }
 164
 165   uptr GetSizeClass(const void *p) {
 166     return possible_regions[ComputeRegionId(reinterpret_cast<uptr>(p))];
 167   }
 168
 169   void *GetBlockBegin(const void *p) {
 170     CHECK(PointerIsMine(p));
 171     uptr mem = reinterpret_cast<uptr>(p);
 172     uptr beg = ComputeRegionBeg(mem);
 173     uptr size = ClassIdToSize(GetSizeClass(p));
 174     u32 offset = mem - beg;
 175     u32 n = offset / (u32)size;  // 32-bit division
 176     uptr res = beg + (n * (u32)size);
 177     return reinterpret_cast<void*>(res);
 178   }
 179
 180   uptr GetActuallyAllocatedSize(void *p) {
 181     CHECK(PointerIsMine(p));
 182     return ClassIdToSize(GetSizeClass(p));
 183   }
 184
 185   uptr ClassID(uptr size) { return SizeClassMap::ClassID(size); }
 186
 187   uptr TotalMemoryUsed() {
 188     // No need to lock here.
 189     uptr res = 0;
 190     for (uptr i = 0; i < kNumPossibleRegions; i++)
 191       if (possible_regions[i])
 192         res += kRegionSize;
 193     return res;
 194   }
 195
 196   void TestOnlyUnmap() {
 197     for (uptr i = 0; i < kNumPossibleRegions; i++)
 198       if (possible_regions[i])
 199         UnmapWithCallback((i * kRegionSize), kRegionSize);
 200   }
 201
 202   // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
 203   // introspection API.
 204   void ForceLock() {
 205     for (uptr i = 0; i < kNumClasses; i++) {
 206       GetSizeClassInfo(i)->mutex.Lock();
 207     }
 208   }
 209
 210   void ForceUnlock() {
 211     for (int i = kNumClasses - 1; i >= 0; i--) {
 212       GetSizeClassInfo(i)->mutex.Unlock();
 213     }
 214   }
 215
 216   // Iterate over all existing chunks.
 217   // The allocator must be locked when calling this function.
 218   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
 219     for (uptr region = 0; region < kNumPossibleRegions; region++)
 220       if (possible_regions[region]) {
 221         uptr chunk_size = ClassIdToSize(possible_regions[region]);
 222         uptr max_chunks_in_region = kRegionSize / (chunk_size + kMetadataSize);
 223         uptr region_beg = region * kRegionSize;
 224         for (uptr chunk = region_beg;
 225              chunk < region_beg + max_chunks_in_region * chunk_size;
 226              chunk += chunk_size) {
 227           // Too slow: CHECK_EQ((void *)chunk, GetBlockBegin((void *)chunk));
 228           callback(chunk, arg);
 229         }
 230       }
 231   }
 232
 233   void PrintStats() {
 234   }
 235
 236   static uptr AdditionalSize() {
 237     return 0;
 238   }
 239
 240   typedef SizeClassMap SizeClassMapT;
 241   static const uptr kNumClasses = SizeClassMap::kNumClasses;
 242
 243  private:
 244   static const uptr kRegionSize = 1 << kRegionSizeLog;
 245   static const uptr kNumPossibleRegions = kSpaceSize / kRegionSize;
 246
 247   struct SizeClassInfo {
 248     SpinMutex mutex;
 249     IntrusiveList<TransferBatch> free_list;
 250     char padding[kCacheLineSize - sizeof(uptr) -
 251                  sizeof(IntrusiveList<TransferBatch>)];
 252   };
 253   COMPILER_CHECK(sizeof(SizeClassInfo) == kCacheLineSize);
 254
 255   uptr ComputeRegionId(uptr mem) {
 256     uptr res = mem >> kRegionSizeLog;
 257     CHECK_LT(res, kNumPossibleRegions);
 258     return res;
 259   }
 260
 261   uptr ComputeRegionBeg(uptr mem) {
 262     return mem & ~(kRegionSize - 1);
 263   }
 264
 265   uptr AllocateRegion(AllocatorStats *stat, uptr class_id) {
 266     CHECK_LT(class_id, kNumClasses);
 267     uptr res = reinterpret_cast<uptr>(MmapAlignedOrDie(kRegionSize, kRegionSize,
 268                                       "SizeClassAllocator32"));
 269     MapUnmapCallback().OnMap(res, kRegionSize);
 270     stat->Add(AllocatorStatMapped, kRegionSize);
 271     CHECK_EQ(0U, (res & (kRegionSize - 1)));
 272     possible_regions.set(ComputeRegionId(res), static_cast<u8>(class_id));
 273     return res;
 274   }
 275
 276   SizeClassInfo *GetSizeClassInfo(uptr class_id) {
 277     CHECK_LT(class_id, kNumClasses);
 278     return &size_class_info_array[class_id];
 279   }
 280
 281   void PopulateFreeList(AllocatorStats *stat, AllocatorCache *c,
 282                         SizeClassInfo *sci, uptr class_id) {
 283     uptr size = ClassIdToSize(class_id);
 284     uptr reg = AllocateRegion(stat, class_id);
 285     uptr n_chunks = kRegionSize / (size + kMetadataSize);
 286     uptr max_count = TransferBatch::MaxCached(class_id);
 287     TransferBatch *b = nullptr;
 288     for (uptr i = reg; i < reg + n_chunks * size; i += size) {
 289       if (!b) {
 290         b = c->CreateBatch(class_id, this, (TransferBatch*)i);
 291         b->Clear();
 292       }
 293       b->Add((void*)i);
 294       if (b->Count() == max_count) {
 295         CHECK_GT(b->Count(), 0);
 296         sci->free_list.push_back(b);
 297         b = nullptr;
 298       }
 299     }
 300     if (b) {
 301       CHECK_GT(b->Count(), 0);
 302       sci->free_list.push_back(b);
 303     }
 304   }
 305
 306   ByteMap possible_regions;
 307   SizeClassInfo size_class_info_array[kNumClasses];
 308 };
 309
 310