libsanitizer/sanitizer_common/sanitizer_allocator_primary32.h

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