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