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

   1 //===-- sanitizer_allocator_secondary.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 // This class can (de)allocate only large chunks of memory using mmap/unmap.
  18 // The main purpose of this allocator is to cover large and rare allocation
  19 // sizes not covered by more efficient allocators (e.g. SizeClassAllocator64).
  20 template <class MapUnmapCallback = NoOpMapUnmapCallback>
  21 class LargeMmapAllocator {
  22  public:
  23   void InitLinkerInitialized(bool may_return_null) {
  24     page_size_ = GetPageSizeCached();
  25     atomic_store(&may_return_null_, may_return_null, memory_order_relaxed);
  26   }
  27
  28   void Init(bool may_return_null) {
  29     internal_memset(this, 0, sizeof(*this));
  30     InitLinkerInitialized(may_return_null);
  31   }
  32
  33   void *Allocate(AllocatorStats *stat, uptr size, uptr alignment) {
  34     CHECK(IsPowerOfTwo(alignment));
  35     uptr map_size = RoundUpMapSize(size);
  36     if (alignment > page_size_)
  37       map_size += alignment;
  38     // Overflow.
  39     if (map_size < size) return ReturnNullOrDieOnBadRequest();
  40     uptr map_beg = reinterpret_cast<uptr>(
  41         MmapOrDie(map_size, "LargeMmapAllocator"));
  42     CHECK(IsAligned(map_beg, page_size_));
  43     MapUnmapCallback().OnMap(map_beg, map_size);
  44     uptr map_end = map_beg + map_size;
  45     uptr res = map_beg + page_size_;
  46     if (res & (alignment - 1))  // Align.
  47       res += alignment - (res & (alignment - 1));
  48     CHECK(IsAligned(res, alignment));
  49     CHECK(IsAligned(res, page_size_));
  50     CHECK_GE(res + size, map_beg);
  51     CHECK_LE(res + size, map_end);
  52     Header *h = GetHeader(res);
  53     h->size = size;
  54     h->map_beg = map_beg;
  55     h->map_size = map_size;
  56     uptr size_log = MostSignificantSetBitIndex(map_size);
  57     CHECK_LT(size_log, ARRAY_SIZE(stats.by_size_log));
  58     {
  59       SpinMutexLock l(&mutex_);
  60       uptr idx = n_chunks_++;
  61       chunks_sorted_ = false;
  62       CHECK_LT(idx, kMaxNumChunks);
  63       h->chunk_idx = idx;
  64       chunks_[idx] = h;
  65       stats.n_allocs++;
  66       stats.currently_allocated += map_size;
  67       stats.max_allocated = Max(stats.max_allocated, stats.currently_allocated);
  68       stats.by_size_log[size_log]++;
  69       stat->Add(AllocatorStatAllocated, map_size);
  70       stat->Add(AllocatorStatMapped, map_size);
  71     }
  72     return reinterpret_cast<void*>(res);
  73   }
  74
  75   bool MayReturnNull() const {
  76     return atomic_load(&may_return_null_, memory_order_acquire);
  77   }
  78
  79   void *ReturnNullOrDieOnBadRequest() {
  80     if (MayReturnNull()) return nullptr;
  81     ReportAllocatorCannotReturnNull(false);
  82   }
  83
  84   void *ReturnNullOrDieOnOOM() {
  85     if (MayReturnNull()) return nullptr;
  86     ReportAllocatorCannotReturnNull(true);
  87   }
  88
  89   void SetMayReturnNull(bool may_return_null) {
  90     atomic_store(&may_return_null_, may_return_null, memory_order_release);
  91   }
  92
  93   void Deallocate(AllocatorStats *stat, void *p) {
  94     Header *h = GetHeader(p);
  95     {
  96       SpinMutexLock l(&mutex_);
  97       uptr idx = h->chunk_idx;
  98       CHECK_EQ(chunks_[idx], h);
  99       CHECK_LT(idx, n_chunks_);
 100       chunks_[idx] = chunks_[n_chunks_ - 1];
 101       chunks_[idx]->chunk_idx = idx;
 102       n_chunks_--;
 103       chunks_sorted_ = false;
 104       stats.n_frees++;
 105       stats.currently_allocated -= h->map_size;
 106       stat->Sub(AllocatorStatAllocated, h->map_size);
 107       stat->Sub(AllocatorStatMapped, h->map_size);
 108     }
 109     MapUnmapCallback().OnUnmap(h->map_beg, h->map_size);
 110     UnmapOrDie(reinterpret_cast<void*>(h->map_beg), h->map_size);
 111   }
 112
 113   uptr TotalMemoryUsed() {
 114     SpinMutexLock l(&mutex_);
 115     uptr res = 0;
 116     for (uptr i = 0; i < n_chunks_; i++) {
 117       Header *h = chunks_[i];
 118       CHECK_EQ(h->chunk_idx, i);
 119       res += RoundUpMapSize(h->size);
 120     }
 121     return res;
 122   }
 123
 124   bool PointerIsMine(const void *p) {
 125     return GetBlockBegin(p) != nullptr;
 126   }
 127
 128   uptr GetActuallyAllocatedSize(void *p) {
 129     return RoundUpTo(GetHeader(p)->size, page_size_);
 130   }
 131
 132   // At least page_size_/2 metadata bytes is available.
 133   void *GetMetaData(const void *p) {
 134     // Too slow: CHECK_EQ(p, GetBlockBegin(p));
 135     if (!IsAligned(reinterpret_cast<uptr>(p), page_size_)) {
 136       Printf("%s: bad pointer %p\n", SanitizerToolName, p);
 137       CHECK(IsAligned(reinterpret_cast<uptr>(p), page_size_));
 138     }
 139     return GetHeader(p) + 1;
 140   }
 141
 142   void *GetBlockBegin(const void *ptr) {
 143     uptr p = reinterpret_cast<uptr>(ptr);
 144     SpinMutexLock l(&mutex_);
 145     uptr nearest_chunk = 0;
 146     // Cache-friendly linear search.
 147     for (uptr i = 0; i < n_chunks_; i++) {
 148       uptr ch = reinterpret_cast<uptr>(chunks_[i]);
 149       if (p < ch) continue;  // p is at left to this chunk, skip it.
 150       if (p - ch < p - nearest_chunk)
 151         nearest_chunk = ch;
 152     }
 153     if (!nearest_chunk)
 154       return nullptr;
 155     Header *h = reinterpret_cast<Header *>(nearest_chunk);
 156     CHECK_GE(nearest_chunk, h->map_beg);
 157     CHECK_LT(nearest_chunk, h->map_beg + h->map_size);
 158     CHECK_LE(nearest_chunk, p);
 159     if (h->map_beg + h->map_size <= p)
 160       return nullptr;
 161     return GetUser(h);
 162   }
 163
 164   void EnsureSortedChunks() {
 165     if (chunks_sorted_) return;
 166     SortArray(reinterpret_cast<uptr*>(chunks_), n_chunks_);
 167     for (uptr i = 0; i < n_chunks_; i++)
 168       chunks_[i]->chunk_idx = i;
 169     chunks_sorted_ = true;
 170   }
 171
 172   // This function does the same as GetBlockBegin, but is much faster.
 173   // Must be called with the allocator locked.
 174   void *GetBlockBeginFastLocked(void *ptr) {
 175     mutex_.CheckLocked();
 176     uptr p = reinterpret_cast<uptr>(ptr);
 177     uptr n = n_chunks_;
 178     if (!n) return nullptr;
 179     EnsureSortedChunks();
 180     auto min_mmap_ = reinterpret_cast<uptr>(chunks_[0]);
 181     auto max_mmap_ =
 182         reinterpret_cast<uptr>(chunks_[n - 1]) + chunks_[n - 1]->map_size;
 183     if (p < min_mmap_ || p >= max_mmap_)
 184       return nullptr;
 185     uptr beg = 0, end = n - 1;
 186     // This loop is a log(n) lower_bound. It does not check for the exact match
 187     // to avoid expensive cache-thrashing loads.
 188     while (end - beg >= 2) {
 189       uptr mid = (beg + end) / 2;  // Invariant: mid >= beg + 1
 190       if (p < reinterpret_cast<uptr>(chunks_[mid]))
 191         end = mid - 1;  // We are not interested in chunks_[mid].
 192       else
 193         beg = mid;  // chunks_[mid] may still be what we want.
 194     }
 195
 196     if (beg < end) {
 197       CHECK_EQ(beg + 1, end);
 198       // There are 2 chunks left, choose one.
 199       if (p >= reinterpret_cast<uptr>(chunks_[end]))
 200         beg = end;
 201     }
 202
 203     Header *h = chunks_[beg];
 204     if (h->map_beg + h->map_size <= p || p < h->map_beg)
 205       return nullptr;
 206     return GetUser(h);
 207   }
 208
 209   void PrintStats() {
 210     Printf("Stats: LargeMmapAllocator: allocated %zd times, "
 211            "remains %zd (%zd K) max %zd M; by size logs: ",
 212            stats.n_allocs, stats.n_allocs - stats.n_frees,
 213            stats.currently_allocated >> 10, stats.max_allocated >> 20);
 214     for (uptr i = 0; i < ARRAY_SIZE(stats.by_size_log); i++) {
 215       uptr c = stats.by_size_log[i];
 216       if (!c) continue;
 217       Printf("%zd:%zd; ", i, c);
 218     }
 219     Printf("\n");
 220   }
 221
 222   // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
 223   // introspection API.
 224   void ForceLock() {
 225     mutex_.Lock();
 226   }
 227
 228   void ForceUnlock() {
 229     mutex_.Unlock();
 230   }
 231
 232   // Iterate over all existing chunks.
 233   // The allocator must be locked when calling this function.
 234   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
 235     EnsureSortedChunks();  // Avoid doing the sort while iterating.
 236     for (uptr i = 0; i < n_chunks_; i++) {
 237       auto t = chunks_[i];
 238       callback(reinterpret_cast<uptr>(GetUser(chunks_[i])), arg);
 239       // Consistency check: verify that the array did not change.
 240       CHECK_EQ(chunks_[i], t);
 241       CHECK_EQ(chunks_[i]->chunk_idx, i);
 242     }
 243   }
 244
 245  private:
 246   static const int kMaxNumChunks = 1 << FIRST_32_SECOND_64(15, 18);
 247   struct Header {
 248     uptr map_beg;
 249     uptr map_size;
 250     uptr size;
 251     uptr chunk_idx;
 252   };
 253
 254   Header *GetHeader(uptr p) {
 255     CHECK(IsAligned(p, page_size_));
 256     return reinterpret_cast<Header*>(p - page_size_);
 257   }
 258   Header *GetHeader(const void *p) {
 259     return GetHeader(reinterpret_cast<uptr>(p));
 260   }
 261
 262   void *GetUser(Header *h) {
 263     CHECK(IsAligned((uptr)h, page_size_));
 264     return reinterpret_cast<void*>(reinterpret_cast<uptr>(h) + page_size_);
 265   }
 266
 267   uptr RoundUpMapSize(uptr size) {
 268     return RoundUpTo(size, page_size_) + page_size_;
 269   }
 270
 271   uptr page_size_;
 272   Header *chunks_[kMaxNumChunks];
 273   uptr n_chunks_;
 274   bool chunks_sorted_;
 275   struct Stats {
 276     uptr n_allocs, n_frees, currently_allocated, max_allocated, by_size_log[64];
 277   } stats;
 278   atomic_uint8_t may_return_null_;
 279   SpinMutex mutex_;
 280 };
 281
 282