libasan/asan_allocator.cc

   1 //===-- asan_allocator.cc -------------------------------------------------===//
   2 //
   3 // This file is distributed under the University of Illinois Open Source
   4 // License. See LICENSE.TXT for details.
   5 //
   6 //===----------------------------------------------------------------------===//
   7 //
   8 // This file is a part of AddressSanitizer, an address sanity checker.
   9 //
  10 // Implementation of ASan's memory allocator.
  11 // Evey piece of memory (AsanChunk) allocated by the allocator
  12 // has a left redzone of REDZONE bytes and
  13 // a right redzone such that the end of the chunk is aligned by REDZONE
  14 // (i.e. the right redzone is between 0 and REDZONE-1).
  15 // The left redzone is always poisoned.
  16 // The right redzone is poisoned on malloc, the body is poisoned on free.
  17 // Once freed, a chunk is moved to a quarantine (fifo list).
  18 // After quarantine, a chunk is returned to freelists.
  19 //
  20 // The left redzone contains ASan's internal data and the stack trace of
  21 // the malloc call.
  22 // Once freed, the body of the chunk contains the stack trace of the free call.
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #include "asan_allocator.h"
  27 #include "asan_interceptors.h"
  28 #include "asan_internal.h"
  29 #include "asan_lock.h"
  30 #include "asan_mapping.h"
  31 #include "asan_stats.h"
  32 #include "asan_report.h"
  33 #include "asan_thread.h"
  34 #include "asan_thread_registry.h"
  35 #include "sanitizer/asan_interface.h"
  36 #include "sanitizer_common/sanitizer_atomic.h"
  37
  38 #if defined(_WIN32) && !defined(__clang__)
  39 #include <intrin.h>
  40 #endif
  41
  42 namespace __asan {
  43
  44 #define REDZONE ((uptr)(flags()->redzone))
  45 static const uptr kMinAllocSize = REDZONE * 2;
  46 static const u64 kMaxAvailableRam = 128ULL << 30;  // 128G
  47 static const uptr kMaxThreadLocalQuarantine = 1 << 20;  // 1M
  48
  49 static const uptr kMinMmapSize = (ASAN_LOW_MEMORY) ? 4UL << 17 : 4UL << 20;
  50 static const uptr kMaxSizeForThreadLocalFreeList =
  51     (ASAN_LOW_MEMORY) ? 1 << 15 : 1 << 17;
  52
  53 // Size classes less than kMallocSizeClassStep are powers of two.
  54 // All other size classes are multiples of kMallocSizeClassStep.
  55 static const uptr kMallocSizeClassStepLog = 26;
  56 static const uptr kMallocSizeClassStep = 1UL << kMallocSizeClassStepLog;
  57
  58 static const uptr kMaxAllowedMallocSize =
  59     (__WORDSIZE == 32) ? 3UL << 30 : 8UL << 30;
  60
  61 static inline bool IsAligned(uptr a, uptr alignment) {
  62   return (a & (alignment - 1)) == 0;
  63 }
  64
  65 static inline uptr Log2(uptr x) {
  66   CHECK(IsPowerOfTwo(x));
  67 #if !defined(_WIN32) || defined(__clang__)
  68   return __builtin_ctzl(x);
  69 #elif defined(_WIN64)
  70   unsigned long ret;  // NOLINT
  71   _BitScanForward64(&ret, x);
  72   return ret;
  73 #else
  74   unsigned long ret;  // NOLINT
  75   _BitScanForward(&ret, x);
  76   return ret;
  77 #endif
  78 }
  79
  80 static inline uptr RoundUpToPowerOfTwo(uptr size) {
  81   CHECK(size);
  82   if (IsPowerOfTwo(size)) return size;
  83
  84   unsigned long up;  // NOLINT
  85 #if !defined(_WIN32) || defined(__clang__)
  86   up = __WORDSIZE - 1 - __builtin_clzl(size);
  87 #elif defined(_WIN64)
  88   _BitScanReverse64(&up, size);
  89 #else
  90   _BitScanReverse(&up, size);
  91 #endif
  92   CHECK(size < (1ULL << (up + 1)));
  93   CHECK(size > (1ULL << up));
  94   return 1UL << (up + 1);
  95 }
  96
  97 static inline uptr SizeClassToSize(u8 size_class) {
  98   CHECK(size_class < kNumberOfSizeClasses);
  99   if (size_class <= kMallocSizeClassStepLog) {
 100     return 1UL << size_class;
 101   } else {
 102     return (size_class - kMallocSizeClassStepLog) * kMallocSizeClassStep;
 103   }
 104 }
 105
 106 static inline u8 SizeToSizeClass(uptr size) {
 107   u8 res = 0;
 108   if (size <= kMallocSizeClassStep) {
 109     uptr rounded = RoundUpToPowerOfTwo(size);
 110     res = Log2(rounded);
 111   } else {
 112     res = ((size + kMallocSizeClassStep - 1) / kMallocSizeClassStep)
 113         + kMallocSizeClassStepLog;
 114   }
 115   CHECK(res < kNumberOfSizeClasses);
 116   CHECK(size <= SizeClassToSize(res));
 117   return res;
 118 }
 119
 120 // Given REDZONE bytes, we need to mark first size bytes
 121 // as addressable and the rest REDZONE-size bytes as unaddressable.
 122 static void PoisonHeapPartialRightRedzone(uptr mem, uptr size) {
 123   CHECK(size <= REDZONE);
 124   CHECK(IsAligned(mem, REDZONE));
 125   CHECK(IsPowerOfTwo(SHADOW_GRANULARITY));
 126   CHECK(IsPowerOfTwo(REDZONE));
 127   CHECK(REDZONE >= SHADOW_GRANULARITY);
 128   PoisonShadowPartialRightRedzone(mem, size, REDZONE,
 129                                   kAsanHeapRightRedzoneMagic);
 130 }
 131
 132 static u8 *MmapNewPagesAndPoisonShadow(uptr size) {
 133   CHECK(IsAligned(size, kPageSize));
 134   u8 *res = (u8*)MmapOrDie(size, __FUNCTION__);
 135   PoisonShadow((uptr)res, size, kAsanHeapLeftRedzoneMagic);
 136   if (flags()->debug) {
 137     Printf("ASAN_MMAP: [%p, %p)\n", res, res + size);
 138   }
 139   return res;
 140 }
 141
 142 // Every chunk of memory allocated by this allocator can be in one of 3 states:
 143 // CHUNK_AVAILABLE: the chunk is in the free list and ready to be allocated.
 144 // CHUNK_ALLOCATED: the chunk is allocated and not yet freed.
 145 // CHUNK_QUARANTINE: the chunk was freed and put into quarantine zone.
 146 //
 147 // The pseudo state CHUNK_MEMALIGN is used to mark that the address is not
 148 // the beginning of a AsanChunk (in which the actual chunk resides at
 149 // this - this->used_size).
 150 //
 151 // The magic numbers for the enum values are taken randomly.
 152 enum {
 153   CHUNK_AVAILABLE  = 0x57,
 154   CHUNK_ALLOCATED  = 0x32,
 155   CHUNK_QUARANTINE = 0x19,
 156   CHUNK_MEMALIGN   = 0xDC
 157 };
 158
 159 struct ChunkBase {
 160   // First 8 bytes.
 161   uptr  chunk_state : 8;
 162   uptr  alloc_tid   : 24;
 163   uptr  size_class  : 8;
 164   uptr  free_tid    : 24;
 165
 166   // Second 8 bytes.
 167   uptr alignment_log : 8;
 168   uptr used_size : FIRST_32_SECOND_64(32, 56);  // Size requested by the user.
 169
 170   // This field may overlap with the user area and thus should not
 171   // be used while the chunk is in CHUNK_ALLOCATED state.
 172   AsanChunk *next;
 173
 174   // Typically the beginning of the user-accessible memory is 'this'+REDZONE
 175   // and is also aligned by REDZONE. However, if the memory is allocated
 176   // by memalign, the alignment might be higher and the user-accessible memory
 177   // starts at the first properly aligned address after 'this'.
 178   uptr Beg() { return RoundUpTo((uptr)this + 1, 1 << alignment_log); }
 179   uptr Size() { return SizeClassToSize(size_class); }
 180   u8 SizeClass() { return size_class; }
 181 };
 182
 183 struct AsanChunk: public ChunkBase {
 184   u32 *compressed_alloc_stack() {
 185     return (u32*)((uptr)this + sizeof(ChunkBase));
 186   }
 187   u32 *compressed_free_stack() {
 188     return (u32*)((uptr)this + Max((uptr)REDZONE, (uptr)sizeof(ChunkBase)));
 189   }
 190
 191   // The left redzone after the ChunkBase is given to the alloc stack trace.
 192   uptr compressed_alloc_stack_size() {
 193     if (REDZONE < sizeof(ChunkBase)) return 0;
 194     return (REDZONE - sizeof(ChunkBase)) / sizeof(u32);
 195   }
 196   uptr compressed_free_stack_size() {
 197     if (REDZONE < sizeof(ChunkBase)) return 0;
 198     return (REDZONE) / sizeof(u32);
 199   }
 200 };
 201
 202 uptr AsanChunkView::Beg() { return chunk_->Beg(); }
 203 uptr AsanChunkView::End() { return Beg() + UsedSize(); }
 204 uptr AsanChunkView::UsedSize() { return chunk_->used_size; }
 205 uptr AsanChunkView::AllocTid() { return chunk_->alloc_tid; }
 206 uptr AsanChunkView::FreeTid() { return chunk_->free_tid; }
 207
 208 void AsanChunkView::GetAllocStack(StackTrace *stack) {
 209   StackTrace::UncompressStack(stack, chunk_->compressed_alloc_stack(),
 210                               chunk_->compressed_alloc_stack_size());
 211 }
 212
 213 void AsanChunkView::GetFreeStack(StackTrace *stack) {
 214   StackTrace::UncompressStack(stack, chunk_->compressed_free_stack(),
 215                               chunk_->compressed_free_stack_size());
 216 }
 217
 218 bool AsanChunkView::AddrIsInside(uptr addr, uptr access_size, uptr *offset) {
 219   if (addr >= Beg() && (addr + access_size) <= End()) {
 220     *offset = addr - Beg();
 221     return true;
 222   }
 223   return false;
 224 }
 225
 226 bool AsanChunkView::AddrIsAtLeft(uptr addr, uptr access_size, uptr *offset) {
 227   if (addr < Beg()) {
 228     *offset = Beg() - addr;
 229     return true;
 230   }
 231   return false;
 232 }
 233
 234 bool AsanChunkView::AddrIsAtRight(uptr addr, uptr access_size, uptr *offset) {
 235   if (addr + access_size >= End()) {
 236     if (addr <= End())
 237       *offset = 0;
 238     else
 239       *offset = addr - End();
 240     return true;
 241   }
 242   return false;
 243 }
 244
 245 static AsanChunk *PtrToChunk(uptr ptr) {
 246   AsanChunk *m = (AsanChunk*)(ptr - REDZONE);
 247   if (m->chunk_state == CHUNK_MEMALIGN) {
 248     m = (AsanChunk*)((uptr)m - m->used_size);
 249   }
 250   return m;
 251 }
 252
 253 void AsanChunkFifoList::PushList(AsanChunkFifoList *q) {
 254   CHECK(q->size() > 0);
 255   if (last_) {
 256     CHECK(first_);
 257     CHECK(!last_->next);
 258     last_->next = q->first_;
 259     last_ = q->last_;
 260   } else {
 261     CHECK(!first_);
 262     last_ = q->last_;
 263     first_ = q->first_;
 264     CHECK(first_);
 265   }
 266   CHECK(last_);
 267   CHECK(!last_->next);
 268   size_ += q->size();
 269   q->clear();
 270 }
 271
 272 void AsanChunkFifoList::Push(AsanChunk *n) {
 273   CHECK(n->next == 0);
 274   if (last_) {
 275     CHECK(first_);
 276     CHECK(!last_->next);
 277     last_->next = n;
 278     last_ = n;
 279   } else {
 280     CHECK(!first_);
 281     last_ = first_ = n;
 282   }
 283   size_ += n->Size();
 284 }
 285
 286 // Interesting performance observation: this function takes up to 15% of overal
 287 // allocator time. That's because *first_ has been evicted from cache long time
 288 // ago. Not sure if we can or want to do anything with this.
 289 AsanChunk *AsanChunkFifoList::Pop() {
 290   CHECK(first_);
 291   AsanChunk *res = first_;
 292   first_ = first_->next;
 293   if (first_ == 0)
 294     last_ = 0;
 295   CHECK(size_ >= res->Size());
 296   size_ -= res->Size();
 297   if (last_) {
 298     CHECK(!last_->next);
 299   }
 300   return res;
 301 }
 302
 303 // All pages we ever allocated.
 304 struct PageGroup {
 305   uptr beg;
 306   uptr end;
 307   uptr size_of_chunk;
 308   uptr last_chunk;
 309   bool InRange(uptr addr) {
 310     return addr >= beg && addr < end;
 311   }
 312 };
 313
 314 class MallocInfo {
 315  public:
 316   explicit MallocInfo(LinkerInitialized x) : mu_(x) { }
 317
 318   AsanChunk *AllocateChunks(u8 size_class, uptr n_chunks) {
 319     AsanChunk *m = 0;
 320     AsanChunk **fl = &free_lists_[size_class];
 321     {
 322       ScopedLock lock(&mu_);
 323       for (uptr i = 0; i < n_chunks; i++) {
 324         if (!(*fl)) {
 325           *fl = GetNewChunks(size_class);
 326         }
 327         AsanChunk *t = *fl;
 328         *fl = t->next;
 329         t->next = m;
 330         CHECK(t->chunk_state == CHUNK_AVAILABLE);
 331         m = t;
 332       }
 333     }
 334     return m;
 335   }
 336
 337   void SwallowThreadLocalMallocStorage(AsanThreadLocalMallocStorage *x,
 338                                        bool eat_free_lists) {
 339     CHECK(flags()->quarantine_size > 0);
 340     ScopedLock lock(&mu_);
 341     AsanChunkFifoList *q = &x->quarantine_;
 342     if (q->size() > 0) {
 343       quarantine_.PushList(q);
 344       while (quarantine_.size() > (uptr)flags()->quarantine_size) {
 345         QuarantinePop();
 346       }
 347     }
 348     if (eat_free_lists) {
 349       for (uptr size_class = 0; size_class < kNumberOfSizeClasses;
 350            size_class++) {
 351         AsanChunk *m = x->free_lists_[size_class];
 352         while (m) {
 353           AsanChunk *t = m->next;
 354           m->next = free_lists_[size_class];
 355           free_lists_[size_class] = m;
 356           m = t;
 357         }
 358         x->free_lists_[size_class] = 0;
 359       }
 360     }
 361   }
 362
 363   void BypassThreadLocalQuarantine(AsanChunk *chunk) {
 364     ScopedLock lock(&mu_);
 365     quarantine_.Push(chunk);
 366   }
 367
 368   AsanChunk *FindChunkByAddr(uptr addr) {
 369     ScopedLock lock(&mu_);
 370     return FindChunkByAddrUnlocked(addr);
 371   }
 372
 373   uptr AllocationSize(uptr ptr) {
 374     if (!ptr) return 0;
 375     ScopedLock lock(&mu_);
 376
 377     // Make sure this is our chunk and |ptr| actually points to the beginning
 378     // of the allocated memory.
 379     AsanChunk *m = FindChunkByAddrUnlocked(ptr);
 380     if (!m || m->Beg() != ptr) return 0;
 381
 382     if (m->chunk_state == CHUNK_ALLOCATED) {
 383       return m->used_size;
 384     } else {
 385       return 0;
 386     }
 387   }
 388
 389   void ForceLock() {
 390     mu_.Lock();
 391   }
 392
 393   void ForceUnlock() {
 394     mu_.Unlock();
 395   }
 396
 397   void PrintStatus() {
 398     ScopedLock lock(&mu_);
 399     uptr malloced = 0;
 400
 401     Printf(" MallocInfo: in quarantine: %zu malloced: %zu; ",
 402            quarantine_.size() >> 20, malloced >> 20);
 403     for (uptr j = 1; j < kNumberOfSizeClasses; j++) {
 404       AsanChunk *i = free_lists_[j];
 405       if (!i) continue;
 406       uptr t = 0;
 407       for (; i; i = i->next) {
 408         t += i->Size();
 409       }
 410       Printf("%zu:%zu ", j, t >> 20);
 411     }
 412     Printf("\n");
 413   }
 414
 415   PageGroup *FindPageGroup(uptr addr) {
 416     ScopedLock lock(&mu_);
 417     return FindPageGroupUnlocked(addr);
 418   }
 419
 420  private:
 421   PageGroup *FindPageGroupUnlocked(uptr addr) {
 422     int n = atomic_load(&n_page_groups_, memory_order_relaxed);
 423     // If the page groups are not sorted yet, sort them.
 424     if (n_sorted_page_groups_ < n) {
 425       SortArray((uptr*)page_groups_, n);
 426       n_sorted_page_groups_ = n;
 427     }
 428     // Binary search over the page groups.
 429     int beg = 0, end = n;
 430     while (beg < end) {
 431       int med = (beg + end) / 2;
 432       uptr g = (uptr)page_groups_[med];
 433       if (addr > g) {
 434         // 'g' points to the end of the group, so 'addr'
 435         // may not belong to page_groups_[med] or any previous group.
 436         beg = med + 1;
 437       } else {
 438         // 'addr' may belong to page_groups_[med] or a previous group.
 439         end = med;
 440       }
 441     }
 442     if (beg >= n)
 443       return 0;
 444     PageGroup *g = page_groups_[beg];
 445     CHECK(g);
 446     if (g->InRange(addr))
 447       return g;
 448     return 0;
 449   }
 450
 451   // We have an address between two chunks, and we want to report just one.
 452   AsanChunk *ChooseChunk(uptr addr,
 453                          AsanChunk *left_chunk, AsanChunk *right_chunk) {
 454     // Prefer an allocated chunk or a chunk from quarantine.
 455     if (left_chunk->chunk_state == CHUNK_AVAILABLE &&
 456         right_chunk->chunk_state != CHUNK_AVAILABLE)
 457       return right_chunk;
 458     if (right_chunk->chunk_state == CHUNK_AVAILABLE &&
 459         left_chunk->chunk_state != CHUNK_AVAILABLE)
 460       return left_chunk;
 461     // Choose based on offset.
 462     uptr l_offset = 0, r_offset = 0;
 463     CHECK(AsanChunkView(left_chunk).AddrIsAtRight(addr, 1, &l_offset));
 464     CHECK(AsanChunkView(right_chunk).AddrIsAtLeft(addr, 1, &r_offset));
 465     if (l_offset < r_offset)
 466       return left_chunk;
 467     return right_chunk;
 468   }
 469
 470   AsanChunk *FindChunkByAddrUnlocked(uptr addr) {
 471     PageGroup *g = FindPageGroupUnlocked(addr);
 472     if (!g) return 0;
 473     CHECK(g->size_of_chunk);
 474     uptr offset_from_beg = addr - g->beg;
 475     uptr this_chunk_addr = g->beg +
 476         (offset_from_beg / g->size_of_chunk) * g->size_of_chunk;
 477     CHECK(g->InRange(this_chunk_addr));
 478     AsanChunk *m = (AsanChunk*)this_chunk_addr;
 479     CHECK(m->chunk_state == CHUNK_ALLOCATED ||
 480           m->chunk_state == CHUNK_AVAILABLE ||
 481           m->chunk_state == CHUNK_QUARANTINE);
 482     uptr offset = 0;
 483     AsanChunkView m_view(m);
 484     if (m_view.AddrIsInside(addr, 1, &offset))
 485       return m;
 486
 487     if (m_view.AddrIsAtRight(addr, 1, &offset)) {
 488       if (this_chunk_addr == g->last_chunk)  // rightmost chunk
 489         return m;
 490       uptr right_chunk_addr = this_chunk_addr + g->size_of_chunk;
 491       CHECK(g->InRange(right_chunk_addr));
 492       return ChooseChunk(addr, m, (AsanChunk*)right_chunk_addr);
 493     } else {
 494       CHECK(m_view.AddrIsAtLeft(addr, 1, &offset));
 495       if (this_chunk_addr == g->beg)  // leftmost chunk
 496         return m;
 497       uptr left_chunk_addr = this_chunk_addr - g->size_of_chunk;
 498       CHECK(g->InRange(left_chunk_addr));
 499       return ChooseChunk(addr, (AsanChunk*)left_chunk_addr, m);
 500     }
 501   }
 502
 503   void QuarantinePop() {
 504     CHECK(quarantine_.size() > 0);
 505     AsanChunk *m = quarantine_.Pop();
 506     CHECK(m);
 507     // if (F_v >= 2) Printf("MallocInfo::pop %p\n", m);
 508
 509     CHECK(m->chunk_state == CHUNK_QUARANTINE);
 510     m->chunk_state = CHUNK_AVAILABLE;
 511     PoisonShadow((uptr)m, m->Size(), kAsanHeapLeftRedzoneMagic);
 512     CHECK(m->alloc_tid >= 0);
 513     CHECK(m->free_tid >= 0);
 514
 515     uptr size_class = m->SizeClass();
 516     m->next = free_lists_[size_class];
 517     free_lists_[size_class] = m;
 518
 519     // Statistics.
 520     AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
 521     thread_stats.real_frees++;
 522     thread_stats.really_freed += m->used_size;
 523     thread_stats.really_freed_redzones += m->Size() - m->used_size;
 524     thread_stats.really_freed_by_size[m->SizeClass()]++;
 525   }
 526
 527   // Get a list of newly allocated chunks.
 528   AsanChunk *GetNewChunks(u8 size_class) {
 529     uptr size = SizeClassToSize(size_class);
 530     CHECK(IsPowerOfTwo(kMinMmapSize));
 531     CHECK(size < kMinMmapSize || (size % kMinMmapSize) == 0);
 532     uptr mmap_size = Max(size, kMinMmapSize);
 533     uptr n_chunks = mmap_size / size;
 534     CHECK(n_chunks * size == mmap_size);
 535     if (size < kPageSize) {
 536       // Size is small, just poison the last chunk.
 537       n_chunks--;
 538     } else {
 539       // Size is large, allocate an extra page at right and poison it.
 540       mmap_size += kPageSize;
 541     }
 542     CHECK(n_chunks > 0);
 543     u8 *mem = MmapNewPagesAndPoisonShadow(mmap_size);
 544
 545     // Statistics.
 546     AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
 547     thread_stats.mmaps++;
 548     thread_stats.mmaped += mmap_size;
 549     thread_stats.mmaped_by_size[size_class] += n_chunks;
 550
 551     AsanChunk *res = 0;
 552     for (uptr i = 0; i < n_chunks; i++) {
 553       AsanChunk *m = (AsanChunk*)(mem + i * size);
 554       m->chunk_state = CHUNK_AVAILABLE;
 555       m->size_class = size_class;
 556       m->next = res;
 557       res = m;
 558     }
 559     PageGroup *pg = (PageGroup*)(mem + n_chunks * size);
 560     // This memory is already poisoned, no need to poison it again.
 561     pg->beg = (uptr)mem;
 562     pg->end = pg->beg + mmap_size;
 563     pg->size_of_chunk = size;
 564     pg->last_chunk = (uptr)(mem + size * (n_chunks - 1));
 565     int idx = atomic_fetch_add(&n_page_groups_, 1, memory_order_relaxed);
 566     CHECK(idx < (int)ARRAY_SIZE(page_groups_));
 567     page_groups_[idx] = pg;
 568     return res;
 569   }
 570
 571   AsanChunk *free_lists_[kNumberOfSizeClasses];
 572   AsanChunkFifoList quarantine_;
 573   AsanLock mu_;
 574
 575   PageGroup *page_groups_[kMaxAvailableRam / kMinMmapSize];
 576   atomic_uint32_t n_page_groups_;
 577   int n_sorted_page_groups_;
 578 };
 579
 580 static MallocInfo malloc_info(LINKER_INITIALIZED);
 581
 582 void AsanThreadLocalMallocStorage::CommitBack() {
 583   malloc_info.SwallowThreadLocalMallocStorage(this, true);
 584 }
 585
 586 AsanChunkView FindHeapChunkByAddress(uptr address) {
 587   return AsanChunkView(malloc_info.FindChunkByAddr(address));
 588 }
 589
 590 static u8 *Allocate(uptr alignment, uptr size, StackTrace *stack) {
 591   __asan_init();
 592   CHECK(stack);
 593   if (size == 0) {
 594     size = 1;  // TODO(kcc): do something smarter
 595   }
 596   CHECK(IsPowerOfTwo(alignment));
 597   uptr rounded_size = RoundUpTo(size, REDZONE);
 598   uptr needed_size = rounded_size + REDZONE;
 599   if (alignment > REDZONE) {
 600     needed_size += alignment;
 601   }
 602   CHECK(IsAligned(needed_size, REDZONE));
 603   if (size > kMaxAllowedMallocSize || needed_size > kMaxAllowedMallocSize) {
 604     Report("WARNING: AddressSanitizer failed to allocate %p bytes\n",
 605            (void*)size);
 606     return 0;
 607   }
 608
 609   u8 size_class = SizeToSizeClass(needed_size);
 610   uptr size_to_allocate = SizeClassToSize(size_class);
 611   CHECK(size_to_allocate >= kMinAllocSize);
 612   CHECK(size_to_allocate >= needed_size);
 613   CHECK(IsAligned(size_to_allocate, REDZONE));
 614
 615   if (flags()->verbosity >= 3) {
 616     Printf("Allocate align: %zu size: %zu class: %u real: %zu\n",
 617          alignment, size, size_class, size_to_allocate);
 618   }
 619
 620   AsanThread *t = asanThreadRegistry().GetCurrent();
 621   AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
 622   // Statistics
 623   thread_stats.mallocs++;
 624   thread_stats.malloced += size;
 625   thread_stats.malloced_redzones += size_to_allocate - size;
 626   thread_stats.malloced_by_size[size_class]++;
 627
 628   AsanChunk *m = 0;
 629   if (!t || size_to_allocate >= kMaxSizeForThreadLocalFreeList) {
 630     // get directly from global storage.
 631     m = malloc_info.AllocateChunks(size_class, 1);
 632     thread_stats.malloc_large++;
 633   } else {
 634     // get from the thread-local storage.
 635     AsanChunk **fl = &t->malloc_storage().free_lists_[size_class];
 636     if (!*fl) {
 637       uptr n_new_chunks = kMaxSizeForThreadLocalFreeList / size_to_allocate;
 638       *fl = malloc_info.AllocateChunks(size_class, n_new_chunks);
 639       thread_stats.malloc_small_slow++;
 640     }
 641     m = *fl;
 642     *fl = (*fl)->next;
 643   }
 644   CHECK(m);
 645   CHECK(m->chunk_state == CHUNK_AVAILABLE);
 646   m->chunk_state = CHUNK_ALLOCATED;
 647   m->next = 0;
 648   CHECK(m->Size() == size_to_allocate);
 649   uptr addr = (uptr)m + REDZONE;
 650   CHECK(addr <= (uptr)m->compressed_free_stack());
 651
 652   if (alignment > REDZONE && (addr & (alignment - 1))) {
 653     addr = RoundUpTo(addr, alignment);
 654     CHECK((addr & (alignment - 1)) == 0);
 655     AsanChunk *p = (AsanChunk*)(addr - REDZONE);
 656     p->chunk_state = CHUNK_MEMALIGN;
 657     p->used_size = (uptr)p - (uptr)m;
 658     m->alignment_log = Log2(alignment);
 659     CHECK(m->Beg() == addr);
 660   } else {
 661     m->alignment_log = Log2(REDZONE);
 662   }
 663   CHECK(m == PtrToChunk(addr));
 664   m->used_size = size;
 665   CHECK(m->Beg() == addr);
 666   m->alloc_tid = t ? t->tid() : 0;
 667   m->free_tid   = kInvalidTid;
 668   StackTrace::CompressStack(stack, m->compressed_alloc_stack(),
 669                                 m->compressed_alloc_stack_size());
 670   PoisonShadow(addr, rounded_size, 0);
 671   if (size < rounded_size) {
 672     PoisonHeapPartialRightRedzone(addr + rounded_size - REDZONE,
 673                                   size & (REDZONE - 1));
 674   }
 675   if (size <= (uptr)(flags()->max_malloc_fill_size)) {
 676     REAL(memset)((void*)addr, 0, rounded_size);
 677   }
 678   return (u8*)addr;
 679 }
 680
 681 static void Deallocate(u8 *ptr, StackTrace *stack) {
 682   if (!ptr) return;
 683   CHECK(stack);
 684
 685   if (flags()->debug) {
 686     CHECK(malloc_info.FindPageGroup((uptr)ptr));
 687   }
 688
 689   // Printf("Deallocate %p\n", ptr);
 690   AsanChunk *m = PtrToChunk((uptr)ptr);
 691
 692   // Flip the chunk_state atomically to avoid race on double-free.
 693   u8 old_chunk_state = atomic_exchange((atomic_uint8_t*)m, CHUNK_QUARANTINE,
 694                                        memory_order_acq_rel);
 695
 696   if (old_chunk_state == CHUNK_QUARANTINE) {
 697     ReportDoubleFree((uptr)ptr, stack);
 698   } else if (old_chunk_state != CHUNK_ALLOCATED) {
 699     ReportFreeNotMalloced((uptr)ptr, stack);
 700   }
 701   CHECK(old_chunk_state == CHUNK_ALLOCATED);
 702   // With REDZONE==16 m->next is in the user area, otherwise it should be 0.
 703   CHECK(REDZONE <= 16 || !m->next);
 704   CHECK(m->free_tid == kInvalidTid);
 705   CHECK(m->alloc_tid >= 0);
 706   AsanThread *t = asanThreadRegistry().GetCurrent();
 707   m->free_tid = t ? t->tid() : 0;
 708   StackTrace::CompressStack(stack, m->compressed_free_stack(),
 709                                 m->compressed_free_stack_size());
 710   uptr rounded_size = RoundUpTo(m->used_size, REDZONE);
 711   PoisonShadow((uptr)ptr, rounded_size, kAsanHeapFreeMagic);
 712
 713   // Statistics.
 714   AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
 715   thread_stats.frees++;
 716   thread_stats.freed += m->used_size;
 717   thread_stats.freed_by_size[m->SizeClass()]++;
 718
 719   CHECK(m->chunk_state == CHUNK_QUARANTINE);
 720
 721   if (t) {
 722     AsanThreadLocalMallocStorage *ms = &t->malloc_storage();
 723     ms->quarantine_.Push(m);
 724
 725     if (ms->quarantine_.size() > kMaxThreadLocalQuarantine) {
 726       malloc_info.SwallowThreadLocalMallocStorage(ms, false);
 727     }
 728   } else {
 729     malloc_info.BypassThreadLocalQuarantine(m);
 730   }
 731 }
 732
 733 static u8 *Reallocate(u8 *old_ptr, uptr new_size,
 734                            StackTrace *stack) {
 735   CHECK(old_ptr && new_size);
 736
 737   // Statistics.
 738   AsanStats &thread_stats = asanThreadRegistry().GetCurrentThreadStats();
 739   thread_stats.reallocs++;
 740   thread_stats.realloced += new_size;
 741
 742   AsanChunk *m = PtrToChunk((uptr)old_ptr);
 743   CHECK(m->chunk_state == CHUNK_ALLOCATED);
 744   uptr old_size = m->used_size;
 745   uptr memcpy_size = Min(new_size, old_size);
 746   u8 *new_ptr = Allocate(0, new_size, stack);
 747   if (new_ptr) {
 748     CHECK(REAL(memcpy) != 0);
 749     REAL(memcpy)(new_ptr, old_ptr, memcpy_size);
 750     Deallocate(old_ptr, stack);
 751   }
 752   return new_ptr;
 753 }
 754
 755 }  // namespace __asan
 756
 757 // Default (no-op) implementation of malloc hooks.
 758 extern "C" {
 759 SANITIZER_WEAK_ATTRIBUTE SANITIZER_INTERFACE_ATTRIBUTE
 760 void __asan_malloc_hook(void *ptr, uptr size) {
 761   (void)ptr;
 762   (void)size;
 763 }
 764 SANITIZER_WEAK_ATTRIBUTE SANITIZER_INTERFACE_ATTRIBUTE
 765 void __asan_free_hook(void *ptr) {
 766   (void)ptr;
 767 }
 768 }  // extern "C"
 769
 770 namespace __asan {
 771
 772 SANITIZER_INTERFACE_ATTRIBUTE
 773 void *asan_memalign(uptr alignment, uptr size, StackTrace *stack) {
 774   void *ptr = (void*)Allocate(alignment, size, stack);
 775   __asan_malloc_hook(ptr, size);
 776   return ptr;
 777 }
 778
 779 SANITIZER_INTERFACE_ATTRIBUTE
 780 void asan_free(void *ptr, StackTrace *stack) {
 781   __asan_free_hook(ptr);
 782   Deallocate((u8*)ptr, stack);
 783 }
 784
 785 SANITIZER_INTERFACE_ATTRIBUTE
 786 void *asan_malloc(uptr size, StackTrace *stack) {
 787   void *ptr = (void*)Allocate(0, size, stack);
 788   __asan_malloc_hook(ptr, size);
 789   return ptr;
 790 }
 791
 792 void *asan_calloc(uptr nmemb, uptr size, StackTrace *stack) {
 793   void *ptr = (void*)Allocate(0, nmemb * size, stack);
 794   if (ptr)
 795     REAL(memset)(ptr, 0, nmemb * size);
 796   __asan_malloc_hook(ptr, nmemb * size);
 797   return ptr;
 798 }
 799
 800 void *asan_realloc(void *p, uptr size, StackTrace *stack) {
 801   if (p == 0) {
 802     void *ptr = (void*)Allocate(0, size, stack);
 803     __asan_malloc_hook(ptr, size);
 804     return ptr;
 805   } else if (size == 0) {
 806     __asan_free_hook(p);
 807     Deallocate((u8*)p, stack);
 808     return 0;
 809   }
 810   return Reallocate((u8*)p, size, stack);
 811 }
 812
 813 void *asan_valloc(uptr size, StackTrace *stack) {
 814   void *ptr = (void*)Allocate(kPageSize, size, stack);
 815   __asan_malloc_hook(ptr, size);
 816   return ptr;
 817 }
 818
 819 void *asan_pvalloc(uptr size, StackTrace *stack) {
 820   size = RoundUpTo(size, kPageSize);
 821   if (size == 0) {
 822     // pvalloc(0) should allocate one page.
 823     size = kPageSize;
 824   }
 825   void *ptr = (void*)Allocate(kPageSize, size, stack);
 826   __asan_malloc_hook(ptr, size);
 827   return ptr;
 828 }
 829
 830 int asan_posix_memalign(void **memptr, uptr alignment, uptr size,
 831                           StackTrace *stack) {
 832   void *ptr = Allocate(alignment, size, stack);
 833   CHECK(IsAligned((uptr)ptr, alignment));
 834   __asan_malloc_hook(ptr, size);
 835   *memptr = ptr;
 836   return 0;
 837 }
 838
 839 uptr asan_malloc_usable_size(void *ptr, StackTrace *stack) {
 840   CHECK(stack);
 841   if (ptr == 0) return 0;
 842   uptr usable_size = malloc_info.AllocationSize((uptr)ptr);
 843   if (flags()->check_malloc_usable_size && (usable_size == 0)) {
 844     ReportMallocUsableSizeNotOwned((uptr)ptr, stack);
 845   }
 846   return usable_size;
 847 }
 848
 849 uptr asan_mz_size(const void *ptr) {
 850   return malloc_info.AllocationSize((uptr)ptr);
 851 }
 852
 853 void asan_mz_force_lock() {
 854   malloc_info.ForceLock();
 855 }
 856
 857 void asan_mz_force_unlock() {
 858   malloc_info.ForceUnlock();
 859 }
 860
 861 // ---------------------- Fake stack-------------------- {{{1
 862 FakeStack::FakeStack() {
 863   CHECK(REAL(memset) != 0);
 864   REAL(memset)(this, 0, sizeof(*this));
 865 }
 866
 867 bool FakeStack::AddrIsInSizeClass(uptr addr, uptr size_class) {
 868   uptr mem = allocated_size_classes_[size_class];
 869   uptr size = ClassMmapSize(size_class);
 870   bool res = mem && addr >= mem && addr < mem + size;
 871   return res;
 872 }
 873
 874 uptr FakeStack::AddrIsInFakeStack(uptr addr) {
 875   for (uptr i = 0; i < kNumberOfSizeClasses; i++) {
 876     if (AddrIsInSizeClass(addr, i)) return allocated_size_classes_[i];
 877   }
 878   return 0;
 879 }
 880
 881 // We may want to compute this during compilation.
 882 inline uptr FakeStack::ComputeSizeClass(uptr alloc_size) {
 883   uptr rounded_size = RoundUpToPowerOfTwo(alloc_size);
 884   uptr log = Log2(rounded_size);
 885   CHECK(alloc_size <= (1UL << log));
 886   if (!(alloc_size > (1UL << (log-1)))) {
 887     Printf("alloc_size %zu log %zu\n", alloc_size, log);
 888   }
 889   CHECK(alloc_size > (1UL << (log-1)));
 890   uptr res = log < kMinStackFrameSizeLog ? 0 : log - kMinStackFrameSizeLog;
 891   CHECK(res < kNumberOfSizeClasses);
 892   CHECK(ClassSize(res) >= rounded_size);
 893   return res;
 894 }
 895
 896 void FakeFrameFifo::FifoPush(FakeFrame *node) {
 897   CHECK(node);
 898   node->next = 0;
 899   if (first_ == 0 && last_ == 0) {
 900     first_ = last_ = node;
 901   } else {
 902     CHECK(first_);
 903     CHECK(last_);
 904     last_->next = node;
 905     last_ = node;
 906   }
 907 }
 908
 909 FakeFrame *FakeFrameFifo::FifoPop() {
 910   CHECK(first_ && last_ && "Exhausted fake stack");
 911   FakeFrame *res = 0;
 912   if (first_ == last_) {
 913     res = first_;
 914     first_ = last_ = 0;
 915   } else {
 916     res = first_;
 917     first_ = first_->next;
 918   }
 919   return res;
 920 }
 921
 922 void FakeStack::Init(uptr stack_size) {
 923   stack_size_ = stack_size;
 924   alive_ = true;
 925 }
 926
 927 void FakeStack::Cleanup() {
 928   alive_ = false;
 929   for (uptr i = 0; i < kNumberOfSizeClasses; i++) {
 930     uptr mem = allocated_size_classes_[i];
 931     if (mem) {
 932       PoisonShadow(mem, ClassMmapSize(i), 0);
 933       allocated_size_classes_[i] = 0;
 934       UnmapOrDie((void*)mem, ClassMmapSize(i));
 935     }
 936   }
 937 }
 938
 939 uptr FakeStack::ClassMmapSize(uptr size_class) {
 940   return RoundUpToPowerOfTwo(stack_size_);
 941 }
 942
 943 void FakeStack::AllocateOneSizeClass(uptr size_class) {
 944   CHECK(ClassMmapSize(size_class) >= kPageSize);
 945   uptr new_mem = (uptr)MmapOrDie(
 946       ClassMmapSize(size_class), __FUNCTION__);
 947   // Printf("T%d new_mem[%zu]: %p-%p mmap %zu\n",
 948   //       asanThreadRegistry().GetCurrent()->tid(),
 949   //       size_class, new_mem, new_mem + ClassMmapSize(size_class),
 950   //       ClassMmapSize(size_class));
 951   uptr i;
 952   for (i = 0; i < ClassMmapSize(size_class);
 953        i += ClassSize(size_class)) {
 954     size_classes_[size_class].FifoPush((FakeFrame*)(new_mem + i));
 955   }
 956   CHECK(i == ClassMmapSize(size_class));
 957   allocated_size_classes_[size_class] = new_mem;
 958 }
 959
 960 uptr FakeStack::AllocateStack(uptr size, uptr real_stack) {
 961   if (!alive_) return real_stack;
 962   CHECK(size <= kMaxStackMallocSize && size > 1);
 963   uptr size_class = ComputeSizeClass(size);
 964   if (!allocated_size_classes_[size_class]) {
 965     AllocateOneSizeClass(size_class);
 966   }
 967   FakeFrame *fake_frame = size_classes_[size_class].FifoPop();
 968   CHECK(fake_frame);
 969   fake_frame->size_minus_one = size - 1;
 970   fake_frame->real_stack = real_stack;
 971   while (FakeFrame *top = call_stack_.top()) {
 972     if (top->real_stack > real_stack) break;
 973     call_stack_.LifoPop();
 974     DeallocateFrame(top);
 975   }
 976   call_stack_.LifoPush(fake_frame);
 977   uptr ptr = (uptr)fake_frame;
 978   PoisonShadow(ptr, size, 0);
 979   return ptr;
 980 }
 981
 982 void FakeStack::DeallocateFrame(FakeFrame *fake_frame) {
 983   CHECK(alive_);
 984   uptr size = fake_frame->size_minus_one + 1;
 985   uptr size_class = ComputeSizeClass(size);
 986   CHECK(allocated_size_classes_[size_class]);
 987   uptr ptr = (uptr)fake_frame;
 988   CHECK(AddrIsInSizeClass(ptr, size_class));
 989   CHECK(AddrIsInSizeClass(ptr + size - 1, size_class));
 990   size_classes_[size_class].FifoPush(fake_frame);
 991 }
 992
 993 void FakeStack::OnFree(uptr ptr, uptr size, uptr real_stack) {
 994   FakeFrame *fake_frame = (FakeFrame*)ptr;
 995   CHECK(fake_frame->magic = kRetiredStackFrameMagic);
 996   CHECK(fake_frame->descr != 0);
 997   CHECK(fake_frame->size_minus_one == size - 1);
 998   PoisonShadow(ptr, size, kAsanStackAfterReturnMagic);
 999 }
1000
1001 }  // namespace __asan
1002
1003 // ---------------------- Interface ---------------- {{{1
1004 using namespace __asan;  // NOLINT
1005
1006 uptr __asan_stack_malloc(uptr size, uptr real_stack) {
1007   if (!flags()->use_fake_stack) return real_stack;
1008   AsanThread *t = asanThreadRegistry().GetCurrent();
1009   if (!t) {
1010     // TSD is gone, use the real stack.
1011     return real_stack;
1012   }
1013   uptr ptr = t->fake_stack().AllocateStack(size, real_stack);
1014   // Printf("__asan_stack_malloc %p %zu %p\n", ptr, size, real_stack);
1015   return ptr;
1016 }
1017
1018 void __asan_stack_free(uptr ptr, uptr size, uptr real_stack) {
1019   if (!flags()->use_fake_stack) return;
1020   if (ptr != real_stack) {
1021     FakeStack::OnFree(ptr, size, real_stack);
1022   }
1023 }
1024
1025 // ASan allocator doesn't reserve extra bytes, so normally we would
1026 // just return "size".
1027 uptr __asan_get_estimated_allocated_size(uptr size) {
1028   if (size == 0) return 1;
1029   return Min(size, kMaxAllowedMallocSize);
1030 }
1031
1032 bool __asan_get_ownership(const void *p) {
1033   return malloc_info.AllocationSize((uptr)p) > 0;
1034 }
1035
1036 uptr __asan_get_allocated_size(const void *p) {
1037   if (p == 0) return 0;
1038   uptr allocated_size = malloc_info.AllocationSize((uptr)p);
1039   // Die if p is not malloced or if it is already freed.
1040   if (allocated_size == 0) {
1041     GET_STACK_TRACE_HERE(kStackTraceMax);
1042     ReportAsanGetAllocatedSizeNotOwned((uptr)p, &stack);
1043   }
1044   return allocated_size;
1045 }