[Asan] Don't use allocator Metadata

[vitalybuka]

Summary

Previously we used Metadata only with the secondary allocator.

Size goes into 48 bits of ChunkHeader.

Pointer to header goes into new field. This let us with confidence identify
initialized headers. This however increase header to 24 bytes.

Now we can find allocation begin from ChunkHeader without call
to allocator.

Remove now unused ChunkHeader fields.

Depends on D87217.

[vitalybuka]

remove printf

[vitalybuka]

comments

[vitalybuka]

ULL

[vitalybuka]

remove unused fields

[tejohnson]

compiler-rt/lib/asan/asan_allocator.cpp

565

In trying to figure out how to tweak the heap allocator patch, I'm now confused as to why meta[1] was needed in the first place. We've already saved chunk_beg above in alloc_beg[1] in the case where chunk_beg!=alloc_beg. Why can't we use the same method as for the primary allocator in GetAsanChunk, and avoid the need to save this in the metadata?

[vitalybuka]

compiler-rt/lib/asan/asan_allocator.cpp

565

alloc_beg[0], alloc_beg[1] : we save this for both primary/and secondary, but only allocations from primary will use it

secondary uses only meta.
I don't see good reasons for that as secondary allocation always has enough space left of the used_beg.

In either case these pointers should be set later and as atomics, when AsanChunk is initialized. See SetChunkPtr

BTW. I am going to delay this patch until we have stronger reason to increase header to 24 bytes.
Main problem I tried to solve here is in GetAsanChunk where as-is primary allocation for AsanChunk == alloc_begin (no kAllocBegMagic) can return pointer to uninitialized garbage. And don't see how to reasonable solve this without extending Header.

[tejohnson]

compiler-rt/lib/asan/asan_allocator.cpp

565

I don't see good reasons for that as secondary allocation always has enough space left of the used_beg.

Ok thanks for confirming that I'm not completely missing something.

For the heap profiler the possibility of data race that you are trying to solve here is I think less concerning since at the worst the profile is a bit off.

compiler-rt/lib/asan/asan_allocator.h

 namespace __asan {
 
 enum AllocType {
   FROM_MALLOC = 1,  // Memory block came from malloc, calloc, realloc, etc.
   FROM_NEW = 2,     // Memory block came from operator new.
   FROM_NEW_BR = 3   // Memory block came from operator new [ ]
 };
 
-struct AsanChunk;
+class AsanChunk;
 
 struct AllocatorOptions {
   u32 quarantine_size_mb;
   u32 thread_local_quarantine_size_kb;
   u16 min_redzone;
   u16 max_redzone;
   u8 may_return_null;
   u8 alloc_dealloc_mismatch;

compiler-rt/lib/asan/asan_allocator.cpp

static void AtomicContextLoad(const volatile atomic_uint64_t *atomic_context,
                               u32 &tid, u32 &stack) {
   u64 context = atomic_load(atomic_context, memory_order_relaxed);
   stack = context;
   context >>= 32;
   tid = context;
 }
 
 // The memory chunk allocated from the underlying allocator looks like this:
-// L L L L L L H H U U U U U U R R
+// M L L L L L H H U U U U U U R R
+//   M -- Magic ChunkHeader which points to real one.
 //   L -- left redzone words (0 or more bytes)
-//   H -- ChunkHeader (16 bytes), which is also a part of the left redzone.
+//   H -- ChunkHeader, which is also a part of the left redzone.
 //   U -- user memory.
 //   R -- right redzone (0 or more bytes)
 // ChunkBase consists of ChunkHeader and other bytes that overlap with user
 // memory.
 
-// If the left redzone is greater than the ChunkHeader size we store a magic
-// value in the first uptr word of the memory block and store the address of
-// ChunkBase in the next uptr.
-// M B L L L L L L L L L  H H U U U U U U
-//   |                    ^
-//   ---------------------|
-//   M -- magic value kAllocBegMagic
-//   B -- address of ChunkHeader pointing to the first 'H'
-static const uptr kAllocBegMagic = 0xCC6E96B9;
+static const u64 kAllocBegMagic = 0xCC6E96B9CC6E96B9ULL;
 
-struct ChunkHeader {
+class ChunkHeader {
+ private:
+  // This is xor-ed pointer to itself or another header.
+  // Magic ChunkHeader points to real one, realone points to the Magic one.
+  // Pointer is xor-ed to avoid random unrelated garbage interpreded as the
+  // header. We use this value to let lsan to identify fully initialized
+  // headers.
+  atomic_uint64_t magic_ptr;
+
+ public:
   atomic_uint8_t chunk_state;
-  u8 from_memalign : 1;
   u8 alloc_type : 2;
   u8 rz_log : 3;
   u8 lsan_tag : 2;
 
-  // This field is used for small sizes. For large sizes it is equal to
-  // SizeClassMap::kMaxSize and the actual size is stored in the
-  // SecondaryAllocator's metadata.
-  u32 user_requested_size : 29;
   // align < 8 -> 0
   // else      -> log2(min(align, 512)) - 2
-  u32 user_requested_alignment_log : 3;
+  u16 user_requested_alignment_log : 3;
 
  private:
+  // Should be enough according kMaxAllowedMallocSize.
+  u16 user_requested_size_hi : 13;
+  u32 user_requested_size_lo;
   atomic_uint64_t alloc_context_id;
 
  public:
+  uptr UsedSize() const {
+    uptr R = user_requested_size_lo;
+    if (sizeof(uptr) > sizeof(user_requested_size_lo))
+      R += (uptr)user_requested_size_hi << (8 * sizeof(user_requested_size_lo));
+    return R;
+  }
+
+  void SetUsedSize(uptr size) {
+    user_requested_size_lo = size;
+    if (sizeof(uptr) > sizeof(user_requested_size_lo)) {
+      size >>= (8 * sizeof(user_requested_size_lo));
+      user_requested_size_hi = size;
+      CHECK_EQ(user_requested_size_hi, size);
+    }
+  }
+
   void SetAllocContext(u32 tid, u32 stack) {
     AtomicContextStore(&alloc_context_id, tid, stack);
   }
 
   void GetAllocContext(u32 &tid, u32 &stack) const {
     AtomicContextLoad(&alloc_context_id, tid, stack);
   }
+
+  uptr Beg() { return reinterpret_cast<uptr>(this) + sizeof(ChunkHeader); }
+
+  void *AllocBeg() { return GetChunkPtr(); }
+
+  bool AddrIsInside(uptr addr) {
+    return (addr >= Beg()) && (addr < Beg() + UsedSize());
+  }
+
+  void SetChunkPtr(AsanChunk *p) {
+    atomic_store(&magic_ptr, kAllocBegMagic ^ reinterpret_cast<u64>(p),
+                 memory_order_release);
+  }
+
+  AsanChunk *GetChunkPtr() const {
+    return reinterpret_cast<AsanChunk *>(
+        kAllocBegMagic ^ atomic_load(&magic_ptr, memory_order_acquire));
+  }
 };
 
-class ChunkBase : public ChunkHeader {
+class AsanChunk : public ChunkHeader {
   atomic_uint64_t free_context_id;
 
  public:
   void SetFreeContext(u32 tid, u32 stack) {
     AtomicContextStore(&free_context_id, tid, stack);
   }
 
   void GetFreeContext(u32 &tid, u32 &stack) const {
     AtomicContextLoad(&free_context_id, tid, stack);
   }
 };
 
 static const uptr kChunkHeaderSize = sizeof(ChunkHeader);
-static const uptr kChunkHeader2Size = sizeof(ChunkBase) - kChunkHeaderSize;
-COMPILER_CHECK(kChunkHeaderSize == 16);
+static const uptr kChunkHeader2Size = sizeof(AsanChunk) - kChunkHeaderSize;
+COMPILER_CHECK(kChunkHeaderSize == 24);
 COMPILER_CHECK(kChunkHeader2Size <= 16);
 
 enum {
   // Either just allocated by underlying allocator, but AsanChunk is not yet
   // ready, or almost returned to undelying allocator and AsanChunk is already
   // meaningless.
   CHUNK_INVALID = 0,
   // The chunk is allocated and not yet freed.
   CHUNK_ALLOCATED = 2,
   // The chunk was freed and put into quarantine zone.
   CHUNK_QUARANTINE = 3,
 };
 
-struct AsanChunk: ChunkBase {
-  uptr Beg() { return reinterpret_cast<uptr>(this) + kChunkHeaderSize; }
-  uptr UsedSize(bool locked_version = false) {
-    if (user_requested_size != SizeClassMap::kMaxSize)
-      return user_requested_size;
-    return *reinterpret_cast<uptr *>(
-        get_allocator().GetMetaData(AllocBeg(locked_version)));
-  }
-  void *AllocBeg(bool locked_version = false) {
-    if (from_memalign) {
-      if (locked_version)
-        return get_allocator().GetBlockBeginFastLocked(
-            reinterpret_cast<void *>(this));
-      return get_allocator().GetBlockBegin(reinterpret_cast<void *>(this));
-    }
-    return reinterpret_cast<void*>(Beg() - RZLog2Size(rz_log));
-  }
-  bool AddrIsInside(uptr addr, bool locked_version = false) {
-    return (addr >= Beg()) && (addr < Beg() + UsedSize(locked_version));
-  }
-};
-
 struct QuarantineCallback {
   QuarantineCallback(AllocatorCache *cache, BufferedStackTrace *stack)
       : cache_(cache),
         stack_(stack) {
   }
 
   void Recycle(AsanChunk *m) {
+    AsanChunk *p = reinterpret_cast<AsanChunk *>(m->AllocBeg());
+    p->SetChunkPtr(nullptr);
+    if (p != m)
+      m->SetChunkPtr(nullptr);
     u8 old_chunk_state = CHUNK_QUARANTINE;
     if (!atomic_compare_exchange_strong(&m->chunk_state, &old_chunk_state,
                                         CHUNK_INVALID, memory_order_acquire)) {
       CHECK_EQ(old_chunk_state, CHUNK_QUARANTINE);
     }
 
     PoisonShadow(m->Beg(),
                  RoundUpTo(m->UsedSize(), SHADOW_GRANULARITY),
                  kAsanHeapLeftRedzoneMagic);
-    void *p = reinterpret_cast<void *>(m->AllocBeg());
-    if (p != m) {
-      uptr *alloc_magic = reinterpret_cast<uptr *>(p);
-      CHECK_EQ(alloc_magic[0], kAllocBegMagic);
-      // Clear the magic value, as allocator internals may overwrite the
-      // contents of deallocated chunk, confusing GetAsanChunk lookup.
-      alloc_magic[0] = 0;
-      CHECK_EQ(alloc_magic[1], reinterpret_cast<uptr>(m));
-    }
-
     // Statistics.
     AsanStats &thread_stats = GetCurrentThreadStats();
     thread_stats.real_frees++;
     thread_stats.really_freed += m->UsedSize();
 
     get_allocator().Deallocate(cache_, p);
   }
 
struct Allocator {
   void RePoisonChunk(uptr chunk) {
     // This could be a user-facing chunk (with redzones), or some internal
     // housekeeping chunk, like TransferBatch. Start by assuming the former.
     AsanChunk *ac = GetAsanChunk((void *)chunk);
     uptr allocated_size = allocator.GetActuallyAllocatedSize((void *)chunk);
     if (ac && atomic_load(&ac->chunk_state, memory_order_acquire) ==
                   CHUNK_ALLOCATED) {
       uptr beg = ac->Beg();
-      uptr end = ac->Beg() + ac->UsedSize(true);
+      uptr end = ac->Beg() + ac->UsedSize();
       uptr chunk_end = chunk + allocated_size;
       if (chunk < beg && beg < end && end <= chunk_end) {
         // Looks like a valid AsanChunk in use, poison redzones only.
         PoisonShadow(chunk, beg - chunk, kAsanHeapLeftRedzoneMagic);
         uptr end_aligned_down = RoundDownTo(end, SHADOW_GRANULARITY);
         FastPoisonShadowPartialRightRedzone(
             end_aligned_down, end - end_aligned_down,
             chunk_end - end_aligned_down, kAsanHeapLeftRedzoneMagic);
void *Allocate(uptr size, uptr alignment, BufferedStackTrace *stack,
     }
     CHECK(IsPowerOfTwo(alignment));
     uptr rz_log = ComputeRZLog(size);
     uptr rz_size = RZLog2Size(rz_log);
     uptr rounded_size = RoundUpTo(Max(size, kChunkHeader2Size), alignment);
     uptr needed_size = rounded_size + rz_size;
     if (alignment > min_alignment)
       needed_size += alignment;
-    bool using_primary_allocator = true;
     // If we are allocating from the secondary allocator, there will be no
     // automatic right redzone, so add the right redzone manually.
-    if (!PrimaryAllocator::CanAllocate(needed_size, alignment)) {
+    if (!PrimaryAllocator::CanAllocate(needed_size, alignment))
       needed_size += rz_size;
-      using_primary_allocator = false;
-    }
     CHECK(IsAligned(needed_size, min_alignment));
     if (size > kMaxAllowedMallocSize || needed_size > kMaxAllowedMallocSize ||
         size > max_user_defined_malloc_size) {
       if (AllocatorMayReturnNull()) {
         Report("WARNING: AddressSanitizer failed to allocate 0x%zx bytes\n",
                (void*)size);
         return nullptr;
       }
void *Allocate(uptr size, uptr alignment, BufferedStackTrace *stack,
     if (!IsAligned(user_beg, alignment))
       user_beg = RoundUpTo(user_beg, alignment);
     uptr user_end = user_beg + size;
     CHECK_LE(user_end, alloc_end);
     uptr chunk_beg = user_beg - kChunkHeaderSize;
     AsanChunk *m = reinterpret_cast<AsanChunk *>(chunk_beg);
     m->alloc_type = alloc_type;
     m->rz_log = rz_log;
-    m->from_memalign = user_beg != beg_plus_redzone;
-    if (alloc_beg != chunk_beg) {
-      CHECK_LE(alloc_beg + 2 * sizeof(uptr), chunk_beg);
-      reinterpret_cast<uptr *>(alloc_beg)[0] = kAllocBegMagic;
-      reinterpret_cast<uptr *>(alloc_beg)[1] = chunk_beg;
-    }
-    if (using_primary_allocator) {
-      CHECK(size);
-      m->user_requested_size = size;
-      CHECK(allocator.FromPrimary(allocated));
-    } else {
-      CHECK(!allocator.FromPrimary(allocated));
-      m->user_requested_size = SizeClassMap::kMaxSize;
-      uptr *meta = reinterpret_cast<uptr *>(allocator.GetMetaData(allocated));
-      meta[0] = size;
-      meta[1] = chunk_beg;
-    }
+    m->SetUsedSize(size);
     m->user_requested_alignment_log = user_requested_alignment_log;
 
     m->SetAllocContext(t ? t->tid() : 0, StackDepotPut(*stack));
 
     uptr size_rounded_down_to_granularity =
         RoundDownTo(size, SHADOW_GRANULARITY);
     // Unpoison the bulk of the memory region.
     if (size_rounded_down_to_granularity)
void *Allocate(uptr size, uptr alignment, BufferedStackTrace *stack,
     if (can_fill && fl.max_malloc_fill_size) {
       uptr fill_size = Min(size, (uptr)fl.max_malloc_fill_size);
       REAL(memset)(res, fl.malloc_fill_byte, fill_size);
     }
 #if CAN_SANITIZE_LEAKS
     m->lsan_tag = __lsan::DisabledInThisThread() ? __lsan::kIgnored
                                                  : __lsan::kDirectlyLeaked;
 #endif
-    // Must be the last mutation of metadata in this function.
     atomic_store(&m->chunk_state, CHUNK_ALLOCATED, memory_order_release);
+    // Must be the last mutation of metadata in this function.
+    AsanChunk *magic = reinterpret_cast<AsanChunk *>(alloc_beg);
+    m->SetChunkPtr(magic);
+    if (m != magic) {
+      // Magic header stores only u64. min_alignment guarantees that it's true.
+      CHECK_GE(chunk_beg - alloc_beg, 8);
+      magic->SetChunkPtr(m);
+    }
+
     ASAN_MALLOC_HOOK(res, size);
     return res;
   }
 
   // Set quarantine flag if chunk is allocated, issue ASan error report on
   // available and quarantined chunks. Return true on success, false otherwise.
   bool AtomicallySetQuarantineFlagIfAllocated(AsanChunk *m, void *ptr,
                                               BufferedStackTrace *stack) {
#endif
 
   // Assumes alloc_beg == allocator.GetBlockBegin(alloc_beg).
   // Returns nullptr if AsanChunk is not yet initialized just after
   // get_allocator().Allocate(), or is being destroyed just before
   // get_allocator().Deallocate().
   AsanChunk *GetAsanChunk(void *alloc_beg) {
     if (!alloc_beg)
       return nullptr;
-    AsanChunk *p = nullptr;
-    if (!allocator.FromPrimary(alloc_beg)) {
-      uptr *meta = reinterpret_cast<uptr *>(allocator.GetMetaData(alloc_beg));
-      p = reinterpret_cast<AsanChunk *>(meta[1]);
-    } else {
-      uptr *alloc_magic = reinterpret_cast<uptr *>(alloc_beg);
-      if (alloc_magic[0] == kAllocBegMagic)
-        p = reinterpret_cast<AsanChunk *>(alloc_magic[1]);
-      else
-        p = reinterpret_cast<AsanChunk *>(alloc_beg);
-    }
-    if (!p)
+    AsanChunk *m = reinterpret_cast<AsanChunk *>(alloc_beg);
+    AsanChunk *m2 = m->GetChunkPtr();
+    if (m != m2) {
+      // Check that Magic header points into allocated block.
+      if (m2 < m ||
+          (reinterpret_cast<uptr>(m2) - reinterpret_cast<uptr>(m) +
+           sizeof(AsanChunk)) >= allocator.GetActuallyAllocatedSize(alloc_beg))
         return nullptr;
-    u8 state = atomic_load(&p->chunk_state, memory_order_relaxed);
-    // It does not guaranty that Chunk is initialized, but it's
-    // definitely not for any other value.
-    if (state == CHUNK_ALLOCATED || state == CHUNK_QUARANTINE)
-      return p;
+      // Check that read header points back Magic header.
+      if (m != m2->GetChunkPtr())
         return nullptr;
+      // Now we sure that this is the real one.
+      m = m2;
+    }
+    u8 state = atomic_load(&m->chunk_state, memory_order_relaxed);
+    CHECK(state == CHUNK_ALLOCATED || state == CHUNK_QUARANTINE);
+    return m;
   }
 
   AsanChunk *GetAsanChunkByAddr(uptr p) {
     void *alloc_beg = allocator.GetBlockBegin(reinterpret_cast<void *>(p));
     return GetAsanChunk(alloc_beg);
   }
 
   // Allocator must be locked when this function is called.

 
 uptr PointsIntoChunk(void* p) {
   uptr addr = reinterpret_cast<uptr>(p);
   __asan::AsanChunk *m = __asan::instance.GetAsanChunkByAddrFastLocked(addr);
   if (!m || atomic_load(&m->chunk_state, memory_order_acquire) !=
                 __asan::CHUNK_ALLOCATED)
     return 0;
   uptr chunk = m->Beg();
-  if (m->AddrIsInside(addr, /*locked_version=*/true))
+  if (m->AddrIsInside(addr))
     return chunk;
-  if (IsSpecialCaseOfOperatorNew0(chunk, m->UsedSize(/*locked_version*/ true),
-                                  addr))
+  if (IsSpecialCaseOfOperatorNew0(chunk, m->UsedSize(), addr))
     return chunk;
   return 0;
 }
 
 uptr GetUserBegin(uptr chunk) {
   __asan::AsanChunk *m = __asan::instance.GetAsanChunkByAddrFastLocked(chunk);
   return m ? m->Beg() : 0;
 }

 
 void LsanMetadata::set_tag(ChunkTag value) {
   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
   m->lsan_tag = value;
 }
 
 uptr LsanMetadata::requested_size() const {
   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
-  return m->UsedSize(/*locked_version=*/true);
+  return m->UsedSize();
 }
 
 u32 LsanMetadata::stack_trace_id() const {
   __asan::AsanChunk *m = reinterpret_cast<__asan::AsanChunk *>(metadata_);
   u32 tid = 0;
   u32 stack = 0;
   m->GetAllocContext(tid, stack);
   return stack;