libsanitizer/asan/asan_allocator2.cc

   1 //===-- asan_allocator2.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, 2-nd version.
  11 // This variant uses the allocator from sanitizer_common, i.e. the one shared
  12 // with ThreadSanitizer and MemorySanitizer.
  13 //
  14 //===----------------------------------------------------------------------===//
  15 #include "asan_allocator.h"
  16
  17 #include "asan_mapping.h"
  18 #include "asan_poisoning.h"
  19 #include "asan_report.h"
  20 #include "asan_stack.h"
  21 #include "asan_thread.h"
  22 #include "sanitizer_common/sanitizer_flags.h"
  23 #include "sanitizer_common/sanitizer_internal_defs.h"
  24 #include "sanitizer_common/sanitizer_list.h"
  25 #include "sanitizer_common/sanitizer_stackdepot.h"
  26 #include "sanitizer_common/sanitizer_quarantine.h"
  27 #include "lsan/lsan_common.h"
  28
  29 namespace __asan {
  30
  31 void AsanMapUnmapCallback::OnMap(uptr p, uptr size) const {
  32   PoisonShadow(p, size, kAsanHeapLeftRedzoneMagic);
  33   // Statistics.
  34   AsanStats &thread_stats = GetCurrentThreadStats();
  35   thread_stats.mmaps++;
  36   thread_stats.mmaped += size;
  37 }
  38 void AsanMapUnmapCallback::OnUnmap(uptr p, uptr size) const {
  39   PoisonShadow(p, size, 0);
  40   // We are about to unmap a chunk of user memory.
  41   // Mark the corresponding shadow memory as not needed.
  42   FlushUnneededASanShadowMemory(p, size);
  43   // Statistics.
  44   AsanStats &thread_stats = GetCurrentThreadStats();
  45   thread_stats.munmaps++;
  46   thread_stats.munmaped += size;
  47 }
  48
  49 // We can not use THREADLOCAL because it is not supported on some of the
  50 // platforms we care about (OSX 10.6, Android).
  51 // static THREADLOCAL AllocatorCache cache;
  52 AllocatorCache *GetAllocatorCache(AsanThreadLocalMallocStorage *ms) {
  53   CHECK(ms);
  54   return &ms->allocator2_cache;
  55 }
  56
  57 static Allocator allocator;
  58
  59 static const uptr kMaxAllowedMallocSize =
  60   FIRST_32_SECOND_64(3UL << 30, 64UL << 30);
  61
  62 static const uptr kMaxThreadLocalQuarantine =
  63   FIRST_32_SECOND_64(1 << 18, 1 << 20);
  64
  65 // Every chunk of memory allocated by this allocator can be in one of 3 states:
  66 // CHUNK_AVAILABLE: the chunk is in the free list and ready to be allocated.
  67 // CHUNK_ALLOCATED: the chunk is allocated and not yet freed.
  68 // CHUNK_QUARANTINE: the chunk was freed and put into quarantine zone.
  69 enum {
  70   CHUNK_AVAILABLE  = 0,  // 0 is the default value even if we didn't set it.
  71   CHUNK_ALLOCATED  = 2,
  72   CHUNK_QUARANTINE = 3
  73 };
  74
  75 // Valid redzone sizes are 16, 32, 64, ... 2048, so we encode them in 3 bits.
  76 // We use adaptive redzones: for larger allocation larger redzones are used.
  77 static u32 RZLog2Size(u32 rz_log) {
  78   CHECK_LT(rz_log, 8);
  79   return 16 << rz_log;
  80 }
  81
  82 static u32 RZSize2Log(u32 rz_size) {
  83   CHECK_GE(rz_size, 16);
  84   CHECK_LE(rz_size, 2048);
  85   CHECK(IsPowerOfTwo(rz_size));
  86   u32 res = Log2(rz_size) - 4;
  87   CHECK_EQ(rz_size, RZLog2Size(res));
  88   return res;
  89 }
  90
  91 static uptr ComputeRZLog(uptr user_requested_size) {
  92   u32 rz_log =
  93     user_requested_size <= 64        - 16   ? 0 :
  94     user_requested_size <= 128       - 32   ? 1 :
  95     user_requested_size <= 512       - 64   ? 2 :
  96     user_requested_size <= 4096      - 128  ? 3 :
  97     user_requested_size <= (1 << 14) - 256  ? 4 :
  98     user_requested_size <= (1 << 15) - 512  ? 5 :
  99     user_requested_size <= (1 << 16) - 1024 ? 6 : 7;
 100   return Min(Max(rz_log, RZSize2Log(flags()->redzone)),
 101              RZSize2Log(flags()->max_redzone));
 102 }
 103
 104 // The memory chunk allocated from the underlying allocator looks like this:
 105 // L L L L L L H H U U U U U U R R
 106 //   L -- left redzone words (0 or more bytes)
 107 //   H -- ChunkHeader (16 bytes), which is also a part of the left redzone.
 108 //   U -- user memory.
 109 //   R -- right redzone (0 or more bytes)
 110 // ChunkBase consists of ChunkHeader and other bytes that overlap with user
 111 // memory.
 112
 113 // If the left redzone is greater than the ChunkHeader size we store a magic
 114 // value in the first uptr word of the memory block and store the address of
 115 // ChunkBase in the next uptr.
 116 // M B L L L L L L L L L  H H U U U U U U
 117 //   |                    ^
 118 //   ---------------------|
 119 //   M -- magic value kAllocBegMagic
 120 //   B -- address of ChunkHeader pointing to the first 'H'
 121 static const uptr kAllocBegMagic = 0xCC6E96B9;
 122
 123 struct ChunkHeader {
 124   // 1-st 8 bytes.
 125   u32 chunk_state       : 8;  // Must be first.
 126   u32 alloc_tid         : 24;
 127
 128   u32 free_tid          : 24;
 129   u32 from_memalign     : 1;
 130   u32 alloc_type        : 2;
 131   u32 rz_log            : 3;
 132   u32 lsan_tag          : 2;
 133   // 2-nd 8 bytes
 134   // This field is used for small sizes. For large sizes it is equal to
 135   // SizeClassMap::kMaxSize and the actual size is stored in the
 136   // SecondaryAllocator's metadata.
 137   u32 user_requested_size;
 138   u32 alloc_context_id;
 139 };
 140
 141 struct ChunkBase : ChunkHeader {
 142   // Header2, intersects with user memory.
 143   u32 free_context_id;
 144 };
 145
 146 static const uptr kChunkHeaderSize = sizeof(ChunkHeader);
 147 static const uptr kChunkHeader2Size = sizeof(ChunkBase) - kChunkHeaderSize;
 148 COMPILER_CHECK(kChunkHeaderSize == 16);
 149 COMPILER_CHECK(kChunkHeader2Size <= 16);
 150
 151 struct AsanChunk: ChunkBase {
 152   uptr Beg() { return reinterpret_cast<uptr>(this) + kChunkHeaderSize; }
 153   uptr UsedSize(bool locked_version = false) {
 154     if (user_requested_size != SizeClassMap::kMaxSize)
 155       return user_requested_size;
 156     return *reinterpret_cast<uptr *>(
 157                 allocator.GetMetaData(AllocBeg(locked_version)));
 158   }
 159   void *AllocBeg(bool locked_version = false) {
 160     if (from_memalign) {
 161       if (locked_version)
 162         return allocator.GetBlockBeginFastLocked(
 163             reinterpret_cast<void *>(this));
 164       return allocator.GetBlockBegin(reinterpret_cast<void *>(this));
 165     }
 166     return reinterpret_cast<void*>(Beg() - RZLog2Size(rz_log));
 167   }
 168   // If we don't use stack depot, we store the alloc/free stack traces
 169   // in the chunk itself.
 170   u32 *AllocStackBeg() {
 171     return (u32*)(Beg() - RZLog2Size(rz_log));
 172   }
 173   uptr AllocStackSize() {
 174     CHECK_LE(RZLog2Size(rz_log), kChunkHeaderSize);
 175     return (RZLog2Size(rz_log) - kChunkHeaderSize) / sizeof(u32);
 176   }
 177   u32 *FreeStackBeg() {
 178     return (u32*)(Beg() + kChunkHeader2Size);
 179   }
 180   uptr FreeStackSize() {
 181     if (user_requested_size < kChunkHeader2Size) return 0;
 182     uptr available = RoundUpTo(user_requested_size, SHADOW_GRANULARITY);
 183     return (available - kChunkHeader2Size) / sizeof(u32);
 184   }
 185   bool AddrIsInside(uptr addr, bool locked_version = false) {
 186     return (addr >= Beg()) && (addr < Beg() + UsedSize(locked_version));
 187   }
 188 };
 189
 190 bool AsanChunkView::IsValid() {
 191   return chunk_ != 0 && chunk_->chunk_state != CHUNK_AVAILABLE;
 192 }
 193 uptr AsanChunkView::Beg() { return chunk_->Beg(); }
 194 uptr AsanChunkView::End() { return Beg() + UsedSize(); }
 195 uptr AsanChunkView::UsedSize() { return chunk_->UsedSize(); }
 196 uptr AsanChunkView::AllocTid() { return chunk_->alloc_tid; }
 197 uptr AsanChunkView::FreeTid() { return chunk_->free_tid; }
 198
 199 static void GetStackTraceFromId(u32 id, StackTrace *stack) {
 200   CHECK(id);
 201   uptr size = 0;
 202   const uptr *trace = StackDepotGet(id, &size);
 203   CHECK(trace);
 204   stack->CopyFrom(trace, size);
 205 }
 206
 207 void AsanChunkView::GetAllocStack(StackTrace *stack) {
 208   GetStackTraceFromId(chunk_->alloc_context_id, stack);
 209 }
 210
 211 void AsanChunkView::GetFreeStack(StackTrace *stack) {
 212   GetStackTraceFromId(chunk_->free_context_id, stack);
 213 }
 214
 215 struct QuarantineCallback;
 216 typedef Quarantine<QuarantineCallback, AsanChunk> AsanQuarantine;
 217 typedef AsanQuarantine::Cache QuarantineCache;
 218 static AsanQuarantine quarantine(LINKER_INITIALIZED);
 219 static QuarantineCache fallback_quarantine_cache(LINKER_INITIALIZED);
 220 static AllocatorCache fallback_allocator_cache;
 221 static SpinMutex fallback_mutex;
 222
 223 QuarantineCache *GetQuarantineCache(AsanThreadLocalMallocStorage *ms) {
 224   CHECK(ms);
 225   CHECK_LE(sizeof(QuarantineCache), sizeof(ms->quarantine_cache));
 226   return reinterpret_cast<QuarantineCache *>(ms->quarantine_cache);
 227 }
 228
 229 struct QuarantineCallback {
 230   explicit QuarantineCallback(AllocatorCache *cache)
 231       : cache_(cache) {
 232   }
 233
 234   void Recycle(AsanChunk *m) {
 235     CHECK_EQ(m->chunk_state, CHUNK_QUARANTINE);
 236     atomic_store((atomic_uint8_t*)m, CHUNK_AVAILABLE, memory_order_relaxed);
 237     CHECK_NE(m->alloc_tid, kInvalidTid);
 238     CHECK_NE(m->free_tid, kInvalidTid);
 239     PoisonShadow(m->Beg(),
 240                  RoundUpTo(m->UsedSize(), SHADOW_GRANULARITY),
 241                  kAsanHeapLeftRedzoneMagic);
 242     void *p = reinterpret_cast<void *>(m->AllocBeg());
 243     if (p != m) {
 244       uptr *alloc_magic = reinterpret_cast<uptr *>(p);
 245       CHECK_EQ(alloc_magic[0], kAllocBegMagic);
 246       // Clear the magic value, as allocator internals may overwrite the
 247       // contents of deallocated chunk, confusing GetAsanChunk lookup.
 248       alloc_magic[0] = 0;
 249       CHECK_EQ(alloc_magic[1], reinterpret_cast<uptr>(m));
 250     }
 251
 252     // Statistics.
 253     AsanStats &thread_stats = GetCurrentThreadStats();
 254     thread_stats.real_frees++;
 255     thread_stats.really_freed += m->UsedSize();
 256
 257     allocator.Deallocate(cache_, p);
 258   }
 259
 260   void *Allocate(uptr size) {
 261     return allocator.Allocate(cache_, size, 1, false);
 262   }
 263
 264   void Deallocate(void *p) {
 265     allocator.Deallocate(cache_, p);
 266   }
 267
 268   AllocatorCache *cache_;
 269 };
 270
 271 void InitializeAllocator() {
 272   allocator.Init();
 273   quarantine.Init((uptr)flags()->quarantine_size, kMaxThreadLocalQuarantine);
 274 }
 275
 276 void ReInitializeAllocator() {
 277   quarantine.Init((uptr)flags()->quarantine_size, kMaxThreadLocalQuarantine);
 278 }
 279
 280 static void *Allocate(uptr size, uptr alignment, StackTrace *stack,
 281                       AllocType alloc_type, bool can_fill) {
 282   if (UNLIKELY(!asan_inited))
 283     AsanInitFromRtl();
 284   Flags &fl = *flags();
 285   CHECK(stack);
 286   const uptr min_alignment = SHADOW_GRANULARITY;
 287   if (alignment < min_alignment)
 288     alignment = min_alignment;
 289   if (size == 0) {
 290     // We'd be happy to avoid allocating memory for zero-size requests, but
 291     // some programs/tests depend on this behavior and assume that malloc would
 292     // not return NULL even for zero-size allocations. Moreover, it looks like
 293     // operator new should never return NULL, and results of consecutive "new"
 294     // calls must be different even if the allocated size is zero.
 295     size = 1;
 296   }
 297   CHECK(IsPowerOfTwo(alignment));
 298   uptr rz_log = ComputeRZLog(size);
 299   uptr rz_size = RZLog2Size(rz_log);
 300   uptr rounded_size = RoundUpTo(Max(size, kChunkHeader2Size), alignment);
 301   uptr needed_size = rounded_size + rz_size;
 302   if (alignment > min_alignment)
 303     needed_size += alignment;
 304   bool using_primary_allocator = true;
 305   // If we are allocating from the secondary allocator, there will be no
 306   // automatic right redzone, so add the right redzone manually.
 307   if (!PrimaryAllocator::CanAllocate(needed_size, alignment)) {
 308     needed_size += rz_size;
 309     using_primary_allocator = false;
 310   }
 311   CHECK(IsAligned(needed_size, min_alignment));
 312   if (size > kMaxAllowedMallocSize || needed_size > kMaxAllowedMallocSize) {
 313     Report("WARNING: AddressSanitizer failed to allocate %p bytes\n",
 314            (void*)size);
 315     return AllocatorReturnNull();
 316   }
 317
 318   AsanThread *t = GetCurrentThread();
 319   void *allocated;
 320   if (t) {
 321     AllocatorCache *cache = GetAllocatorCache(&t->malloc_storage());
 322     allocated = allocator.Allocate(cache, needed_size, 8, false);
 323   } else {
 324     SpinMutexLock l(&fallback_mutex);
 325     AllocatorCache *cache = &fallback_allocator_cache;
 326     allocated = allocator.Allocate(cache, needed_size, 8, false);
 327   }
 328
 329   if (*(u8 *)MEM_TO_SHADOW((uptr)allocated) == 0 && flags()->poison_heap) {
 330     // Heap poisoning is enabled, but the allocator provides an unpoisoned
 331     // chunk. This is possible if flags()->poison_heap was disabled for some
 332     // time, for example, due to flags()->start_disabled.
 333     // Anyway, poison the block before using it for anything else.
 334     uptr allocated_size = allocator.GetActuallyAllocatedSize(allocated);
 335     PoisonShadow((uptr)allocated, allocated_size, kAsanHeapLeftRedzoneMagic);
 336   }
 337
 338   uptr alloc_beg = reinterpret_cast<uptr>(allocated);
 339   uptr alloc_end = alloc_beg + needed_size;
 340   uptr beg_plus_redzone = alloc_beg + rz_size;
 341   uptr user_beg = beg_plus_redzone;
 342   if (!IsAligned(user_beg, alignment))
 343     user_beg = RoundUpTo(user_beg, alignment);
 344   uptr user_end = user_beg + size;
 345   CHECK_LE(user_end, alloc_end);
 346   uptr chunk_beg = user_beg - kChunkHeaderSize;
 347   AsanChunk *m = reinterpret_cast<AsanChunk *>(chunk_beg);
 348   m->alloc_type = alloc_type;
 349   m->rz_log = rz_log;
 350   u32 alloc_tid = t ? t->tid() : 0;
 351   m->alloc_tid = alloc_tid;
 352   CHECK_EQ(alloc_tid, m->alloc_tid);  // Does alloc_tid fit into the bitfield?
 353   m->free_tid = kInvalidTid;
 354   m->from_memalign = user_beg != beg_plus_redzone;
 355   if (alloc_beg != chunk_beg) {
 356     CHECK_LE(alloc_beg+ 2 * sizeof(uptr), chunk_beg);
 357     reinterpret_cast<uptr *>(alloc_beg)[0] = kAllocBegMagic;
 358     reinterpret_cast<uptr *>(alloc_beg)[1] = chunk_beg;
 359   }
 360   if (using_primary_allocator) {
 361     CHECK(size);
 362     m->user_requested_size = size;
 363     CHECK(allocator.FromPrimary(allocated));
 364   } else {
 365     CHECK(!allocator.FromPrimary(allocated));
 366     m->user_requested_size = SizeClassMap::kMaxSize;
 367     uptr *meta = reinterpret_cast<uptr *>(allocator.GetMetaData(allocated));
 368     meta[0] = size;
 369     meta[1] = chunk_beg;
 370   }
 371
 372   m->alloc_context_id = StackDepotPut(stack->trace, stack->size);
 373
 374   uptr size_rounded_down_to_granularity = RoundDownTo(size, SHADOW_GRANULARITY);
 375   // Unpoison the bulk of the memory region.
 376   if (size_rounded_down_to_granularity)
 377     PoisonShadow(user_beg, size_rounded_down_to_granularity, 0);
 378   // Deal with the end of the region if size is not aligned to granularity.
 379   if (size != size_rounded_down_to_granularity && fl.poison_heap) {
 380     u8 *shadow = (u8*)MemToShadow(user_beg + size_rounded_down_to_granularity);
 381     *shadow = fl.poison_partial ? (size & (SHADOW_GRANULARITY - 1)) : 0;
 382   }
 383
 384   AsanStats &thread_stats = GetCurrentThreadStats();
 385   thread_stats.mallocs++;
 386   thread_stats.malloced += size;
 387   thread_stats.malloced_redzones += needed_size - size;
 388   uptr class_id = Min(kNumberOfSizeClasses, SizeClassMap::ClassID(needed_size));
 389   thread_stats.malloced_by_size[class_id]++;
 390   if (needed_size > SizeClassMap::kMaxSize)
 391     thread_stats.malloc_large++;
 392
 393   void *res = reinterpret_cast<void *>(user_beg);
 394   if (can_fill && fl.max_malloc_fill_size) {
 395     uptr fill_size = Min(size, (uptr)fl.max_malloc_fill_size);
 396     REAL(memset)(res, fl.malloc_fill_byte, fill_size);
 397   }
 398 #if CAN_SANITIZE_LEAKS
 399   m->lsan_tag = __lsan::DisabledInThisThread() ? __lsan::kIgnored
 400                                                : __lsan::kDirectlyLeaked;
 401 #endif
 402   // Must be the last mutation of metadata in this function.
 403   atomic_store((atomic_uint8_t *)m, CHUNK_ALLOCATED, memory_order_release);
 404   ASAN_MALLOC_HOOK(res, size);
 405   return res;
 406 }
 407
 408 static void ReportInvalidFree(void *ptr, u8 chunk_state, StackTrace *stack) {
 409   if (chunk_state == CHUNK_QUARANTINE)
 410     ReportDoubleFree((uptr)ptr, stack);
 411   else
 412     ReportFreeNotMalloced((uptr)ptr, stack);
 413 }
 414
 415 static void AtomicallySetQuarantineFlag(AsanChunk *m,
 416                                         void *ptr, StackTrace *stack) {
 417   u8 old_chunk_state = CHUNK_ALLOCATED;
 418   // Flip the chunk_state atomically to avoid race on double-free.
 419   if (!atomic_compare_exchange_strong((atomic_uint8_t*)m, &old_chunk_state,
 420                                       CHUNK_QUARANTINE, memory_order_acquire))
 421     ReportInvalidFree(ptr, old_chunk_state, stack);
 422   CHECK_EQ(CHUNK_ALLOCATED, old_chunk_state);
 423 }
 424
 425 // Expects the chunk to already be marked as quarantined by using
 426 // AtomicallySetQuarantineFlag.
 427 static void QuarantineChunk(AsanChunk *m, void *ptr,
 428                             StackTrace *stack, AllocType alloc_type) {
 429   CHECK_EQ(m->chunk_state, CHUNK_QUARANTINE);
 430
 431   if (m->alloc_type != alloc_type && flags()->alloc_dealloc_mismatch)
 432     ReportAllocTypeMismatch((uptr)ptr, stack,
 433                             (AllocType)m->alloc_type, (AllocType)alloc_type);
 434
 435   CHECK_GE(m->alloc_tid, 0);
 436   if (SANITIZER_WORDSIZE == 64)  // On 32-bits this resides in user area.
 437     CHECK_EQ(m->free_tid, kInvalidTid);
 438   AsanThread *t = GetCurrentThread();
 439   m->free_tid = t ? t->tid() : 0;
 440   m->free_context_id = StackDepotPut(stack->trace, stack->size);
 441   // Poison the region.
 442   PoisonShadow(m->Beg(),
 443                RoundUpTo(m->UsedSize(), SHADOW_GRANULARITY),
 444                kAsanHeapFreeMagic);
 445
 446   AsanStats &thread_stats = GetCurrentThreadStats();
 447   thread_stats.frees++;
 448   thread_stats.freed += m->UsedSize();
 449
 450   // Push into quarantine.
 451   if (t) {
 452     AsanThreadLocalMallocStorage *ms = &t->malloc_storage();
 453     AllocatorCache *ac = GetAllocatorCache(ms);
 454     quarantine.Put(GetQuarantineCache(ms), QuarantineCallback(ac),
 455                    m, m->UsedSize());
 456   } else {
 457     SpinMutexLock l(&fallback_mutex);
 458     AllocatorCache *ac = &fallback_allocator_cache;
 459     quarantine.Put(&fallback_quarantine_cache, QuarantineCallback(ac),
 460                    m, m->UsedSize());
 461   }
 462 }
 463
 464 static void Deallocate(void *ptr, StackTrace *stack, AllocType alloc_type) {
 465   uptr p = reinterpret_cast<uptr>(ptr);
 466   if (p == 0) return;
 467
 468   uptr chunk_beg = p - kChunkHeaderSize;
 469   AsanChunk *m = reinterpret_cast<AsanChunk *>(chunk_beg);
 470   ASAN_FREE_HOOK(ptr);
 471   // Must mark the chunk as quarantined before any changes to its metadata.
 472   AtomicallySetQuarantineFlag(m, ptr, stack);
 473   QuarantineChunk(m, ptr, stack, alloc_type);
 474 }
 475
 476 static void *Reallocate(void *old_ptr, uptr new_size, StackTrace *stack) {
 477   CHECK(old_ptr && new_size);
 478   uptr p = reinterpret_cast<uptr>(old_ptr);
 479   uptr chunk_beg = p - kChunkHeaderSize;
 480   AsanChunk *m = reinterpret_cast<AsanChunk *>(chunk_beg);
 481
 482   AsanStats &thread_stats = GetCurrentThreadStats();
 483   thread_stats.reallocs++;
 484   thread_stats.realloced += new_size;
 485
 486   void *new_ptr = Allocate(new_size, 8, stack, FROM_MALLOC, true);
 487   if (new_ptr) {
 488     u8 chunk_state = m->chunk_state;
 489     if (chunk_state != CHUNK_ALLOCATED)
 490       ReportInvalidFree(old_ptr, chunk_state, stack);
 491     CHECK_NE(REAL(memcpy), (void*)0);
 492     uptr memcpy_size = Min(new_size, m->UsedSize());
 493     // If realloc() races with free(), we may start copying freed memory.
 494     // However, we will report racy double-free later anyway.
 495     REAL(memcpy)(new_ptr, old_ptr, memcpy_size);
 496     Deallocate(old_ptr, stack, FROM_MALLOC);
 497   }
 498   return new_ptr;
 499 }
 500
 501 // Assumes alloc_beg == allocator.GetBlockBegin(alloc_beg).
 502 static AsanChunk *GetAsanChunk(void *alloc_beg) {
 503   if (!alloc_beg) return 0;
 504   if (!allocator.FromPrimary(alloc_beg)) {
 505     uptr *meta = reinterpret_cast<uptr *>(allocator.GetMetaData(alloc_beg));
 506     AsanChunk *m = reinterpret_cast<AsanChunk *>(meta[1]);
 507     return m;
 508   }
 509   uptr *alloc_magic = reinterpret_cast<uptr *>(alloc_beg);
 510   if (alloc_magic[0] == kAllocBegMagic)
 511     return reinterpret_cast<AsanChunk *>(alloc_magic[1]);
 512   return reinterpret_cast<AsanChunk *>(alloc_beg);
 513 }
 514
 515 static AsanChunk *GetAsanChunkByAddr(uptr p) {
 516   void *alloc_beg = allocator.GetBlockBegin(reinterpret_cast<void *>(p));
 517   return GetAsanChunk(alloc_beg);
 518 }
 519
 520 // Allocator must be locked when this function is called.
 521 static AsanChunk *GetAsanChunkByAddrFastLocked(uptr p) {
 522   void *alloc_beg =
 523       allocator.GetBlockBeginFastLocked(reinterpret_cast<void *>(p));
 524   return GetAsanChunk(alloc_beg);
 525 }
 526
 527 static uptr AllocationSize(uptr p) {
 528   AsanChunk *m = GetAsanChunkByAddr(p);
 529   if (!m) return 0;
 530   if (m->chunk_state != CHUNK_ALLOCATED) return 0;
 531   if (m->Beg() != p) return 0;
 532   return m->UsedSize();
 533 }
 534
 535 // We have an address between two chunks, and we want to report just one.
 536 AsanChunk *ChooseChunk(uptr addr,
 537                        AsanChunk *left_chunk, AsanChunk *right_chunk) {
 538   // Prefer an allocated chunk over freed chunk and freed chunk
 539   // over available chunk.
 540   if (left_chunk->chunk_state != right_chunk->chunk_state) {
 541     if (left_chunk->chunk_state == CHUNK_ALLOCATED)
 542       return left_chunk;
 543     if (right_chunk->chunk_state == CHUNK_ALLOCATED)
 544       return right_chunk;
 545     if (left_chunk->chunk_state == CHUNK_QUARANTINE)
 546       return left_chunk;
 547     if (right_chunk->chunk_state == CHUNK_QUARANTINE)
 548       return right_chunk;
 549   }
 550   // Same chunk_state: choose based on offset.
 551   sptr l_offset = 0, r_offset = 0;
 552   CHECK(AsanChunkView(left_chunk).AddrIsAtRight(addr, 1, &l_offset));
 553   CHECK(AsanChunkView(right_chunk).AddrIsAtLeft(addr, 1, &r_offset));
 554   if (l_offset < r_offset)
 555     return left_chunk;
 556   return right_chunk;
 557 }
 558
 559 AsanChunkView FindHeapChunkByAddress(uptr addr) {
 560   AsanChunk *m1 = GetAsanChunkByAddr(addr);
 561   if (!m1) return AsanChunkView(m1);
 562   sptr offset = 0;
 563   if (AsanChunkView(m1).AddrIsAtLeft(addr, 1, &offset)) {
 564     // The address is in the chunk's left redzone, so maybe it is actually
 565     // a right buffer overflow from the other chunk to the left.
 566     // Search a bit to the left to see if there is another chunk.
 567     AsanChunk *m2 = 0;
 568     for (uptr l = 1; l < GetPageSizeCached(); l++) {
 569       m2 = GetAsanChunkByAddr(addr - l);
 570       if (m2 == m1) continue;  // Still the same chunk.
 571       break;
 572     }
 573     if (m2 && AsanChunkView(m2).AddrIsAtRight(addr, 1, &offset))
 574       m1 = ChooseChunk(addr, m2, m1);
 575   }
 576   return AsanChunkView(m1);
 577 }
 578
 579 void AsanThreadLocalMallocStorage::CommitBack() {
 580   AllocatorCache *ac = GetAllocatorCache(this);
 581   quarantine.Drain(GetQuarantineCache(this), QuarantineCallback(ac));
 582   allocator.SwallowCache(GetAllocatorCache(this));
 583 }
 584
 585 void PrintInternalAllocatorStats() {
 586   allocator.PrintStats();
 587 }
 588
 589 void *asan_memalign(uptr alignment, uptr size, StackTrace *stack,
 590                     AllocType alloc_type) {
 591   return Allocate(size, alignment, stack, alloc_type, true);
 592 }
 593
 594 void asan_free(void *ptr, StackTrace *stack, AllocType alloc_type) {
 595   Deallocate(ptr, stack, alloc_type);
 596 }
 597
 598 void *asan_malloc(uptr size, StackTrace *stack) {
 599   return Allocate(size, 8, stack, FROM_MALLOC, true);
 600 }
 601
 602 void *asan_calloc(uptr nmemb, uptr size, StackTrace *stack) {
 603   if (CallocShouldReturnNullDueToOverflow(size, nmemb))
 604     return AllocatorReturnNull();
 605   void *ptr = Allocate(nmemb * size, 8, stack, FROM_MALLOC, false);
 606   // If the memory comes from the secondary allocator no need to clear it
 607   // as it comes directly from mmap.
 608   if (ptr && allocator.FromPrimary(ptr))
 609     REAL(memset)(ptr, 0, nmemb * size);
 610   return ptr;
 611 }
 612
 613 void *asan_realloc(void *p, uptr size, StackTrace *stack) {
 614   if (p == 0)
 615     return Allocate(size, 8, stack, FROM_MALLOC, true);
 616   if (size == 0) {
 617     Deallocate(p, stack, FROM_MALLOC);
 618     return 0;
 619   }
 620   return Reallocate(p, size, stack);
 621 }
 622
 623 void *asan_valloc(uptr size, StackTrace *stack) {
 624   return Allocate(size, GetPageSizeCached(), stack, FROM_MALLOC, true);
 625 }
 626
 627 void *asan_pvalloc(uptr size, StackTrace *stack) {
 628   uptr PageSize = GetPageSizeCached();
 629   size = RoundUpTo(size, PageSize);
 630   if (size == 0) {
 631     // pvalloc(0) should allocate one page.
 632     size = PageSize;
 633   }
 634   return Allocate(size, PageSize, stack, FROM_MALLOC, true);
 635 }
 636
 637 int asan_posix_memalign(void **memptr, uptr alignment, uptr size,
 638                         StackTrace *stack) {
 639   void *ptr = Allocate(size, alignment, stack, FROM_MALLOC, true);
 640   CHECK(IsAligned((uptr)ptr, alignment));
 641   *memptr = ptr;
 642   return 0;
 643 }
 644
 645 uptr asan_malloc_usable_size(void *ptr, uptr pc, uptr bp) {
 646   if (ptr == 0) return 0;
 647   uptr usable_size = AllocationSize(reinterpret_cast<uptr>(ptr));
 648   if (flags()->check_malloc_usable_size && (usable_size == 0)) {
 649     GET_STACK_TRACE_FATAL(pc, bp);
 650     ReportMallocUsableSizeNotOwned((uptr)ptr, &stack);
 651   }
 652   return usable_size;
 653 }
 654
 655 uptr asan_mz_size(const void *ptr) {
 656   return AllocationSize(reinterpret_cast<uptr>(ptr));
 657 }
 658
 659 void asan_mz_force_lock() {
 660   allocator.ForceLock();
 661   fallback_mutex.Lock();
 662 }
 663
 664 void asan_mz_force_unlock() {
 665   fallback_mutex.Unlock();
 666   allocator.ForceUnlock();
 667 }
 668
 669 }  // namespace __asan
 670
 671 // --- Implementation of LSan-specific functions --- {{{1
 672 namespace __lsan {
 673 void LockAllocator() {
 674   __asan::allocator.ForceLock();
 675 }
 676
 677 void UnlockAllocator() {
 678   __asan::allocator.ForceUnlock();
 679 }
 680
 681 void GetAllocatorGlobalRange(uptr *begin, uptr *end) {
 682   *begin = (uptr)&__asan::allocator;
 683   *end = *begin + sizeof(__asan::allocator);
 684 }
 685
 686 uptr PointsIntoChunk(void* p) {
 687   uptr addr = reinterpret_cast<uptr>(p);
 688   __asan::AsanChunk *m = __asan::GetAsanChunkByAddrFastLocked(addr);
 689   if (!m) return 0;
 690   uptr chunk = m->Beg();
 691   if (m->chunk_state != __asan::CHUNK_ALLOCATED)
 692     return 0;
 693   if (m->AddrIsInside(addr, /*locked_version=*/true))
 694     return chunk;
 695   if (IsSpecialCaseOfOperatorNew0(chunk, m->UsedSize(/*locked_version*/ true),
 696                                   addr))
 697     return chunk;
 698   return 0;
 699 }
 700
 701 uptr GetUserBegin(uptr chunk) {
 702   __asan::AsanChunk *m =
 703       __asan::GetAsanChunkByAddrFastLocked(chunk);
 704   CHECK(m);
 705   return m->Beg();
 706 }
 707
 708 LsanMetadata::LsanMetadata(uptr chunk) {
 709   metadata_ = reinterpret_cast<void *>(chunk - __asan::kChunkHeaderSize);
 710 }
 711
 712 bool LsanMetadata::allocated() const {
 713   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 714   return m->chunk_state == __asan::CHUNK_ALLOCATED;
 715 }
 716
 717 ChunkTag LsanMetadata::tag() const {
 718   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 719   return static_cast<ChunkTag>(m->lsan_tag);
 720 }
 721
 722 void LsanMetadata::set_tag(ChunkTag value) {
 723   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 724   m->lsan_tag = value;
 725 }
 726
 727 uptr LsanMetadata::requested_size() const {
 728   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 729   return m->UsedSize(/*locked_version=*/true);
 730 }
 731
 732 u32 LsanMetadata::stack_trace_id() const {
 733   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
 734   return m->alloc_context_id;
 735 }
 736
 737 void ForEachChunk(ForEachChunkCallback callback, void *arg) {
 738   __asan::allocator.ForEachChunk(callback, arg);
 739 }
 740
 741 IgnoreObjectResult IgnoreObjectLocked(const void *p) {
 742   uptr addr = reinterpret_cast<uptr>(p);
 743   __asan::AsanChunk *m = __asan::GetAsanChunkByAddr(addr);
 744   if (!m) return kIgnoreObjectInvalid;
 745   if ((m->chunk_state == __asan::CHUNK_ALLOCATED) && m->AddrIsInside(addr)) {
 746     if (m->lsan_tag == kIgnored)
 747       return kIgnoreObjectAlreadyIgnored;
 748     m->lsan_tag = __lsan::kIgnored;
 749     return kIgnoreObjectSuccess;
 750   } else {
 751     return kIgnoreObjectInvalid;
 752   }
 753 }
 754 }  // namespace __lsan
 755
 756 // ---------------------- Interface ---------------- {{{1
 757 using namespace __asan;  // NOLINT
 758
 759 // ASan allocator doesn't reserve extra bytes, so normally we would
 760 // just return "size". We don't want to expose our redzone sizes, etc here.
 761 uptr __asan_get_estimated_allocated_size(uptr size) {
 762   return size;
 763 }
 764
 765 int __asan_get_ownership(const void *p) {
 766   uptr ptr = reinterpret_cast<uptr>(p);
 767   return (AllocationSize(ptr) > 0);
 768 }
 769
 770 uptr __asan_get_allocated_size(const void *p) {
 771   if (p == 0) return 0;
 772   uptr ptr = reinterpret_cast<uptr>(p);
 773   uptr allocated_size = AllocationSize(ptr);
 774   // Die if p is not malloced or if it is already freed.
 775   if (allocated_size == 0) {
 776     GET_STACK_TRACE_FATAL_HERE;
 777     ReportAsanGetAllocatedSizeNotOwned(ptr, &stack);
 778   }
 779   return allocated_size;
 780 }
 781
 782 #if !SANITIZER_SUPPORTS_WEAK_HOOKS
 783 // Provide default (no-op) implementation of malloc hooks.
 784 extern "C" {
 785 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE
 786 void __asan_malloc_hook(void *ptr, uptr size) {
 787   (void)ptr;
 788   (void)size;
 789 }
 790 SANITIZER_INTERFACE_ATTRIBUTE SANITIZER_WEAK_ATTRIBUTE
 791 void __asan_free_hook(void *ptr) {
 792   (void)ptr;
 793 }
 794 }  // extern "C"
 795 #endif