Add a thread-local ring buffer of heap allocations

[kcc]

Summary

We need this in order to properly report heap-use-after-free,
since we don't have a quarantine.

This is a first part of the code, more like a proof of concept.
But I'd like to commit at as is and proceed with refactoring,
adding a ThreadRegistry, and extending the functionality.

[eugenis]

Looks good for a start.
A test would be nice.

[kcc]

of course, will add tests when there is more to test

lib/hwasan/hwasan_allocator.h

 // This file is a part of HWAddressSanitizer.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef HWASAN_ALLOCATOR_H
 #define HWASAN_ALLOCATOR_H
 
 #include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_common/sanitizer_ring_buffer.h"
 
 namespace __hwasan {
 
 struct HwasanThreadLocalMallocStorage {
   // Allocator cache contains atomic_uint64_t which must be 8-byte aligned.
   ALIGNED(8) uptr allocator_cache[96 * (512 * 8 + 16)];  // Opaque.
   void CommitBack();
 
public:
   u32 GetFreeStackId() const;
  private:
   uptr block_;
   Metadata *const metadata_;
 };
 
 HwasanChunkView FindHeapChunkByAddress(uptr address);
 
+// Information about one (de)allocation that happened in the past.
+// These are recorded in a thread-local ring buffer.
+struct HeapAllocationRecord {
+  uptr tagged_addr;
+  u32  free_context_id;
+  u32  requested_size;
+};
+
+typedef RingBuffer<HeapAllocationRecord> HeapAllocationsRingBuffer;
+
+
 } // namespace __hwasan
 
 #endif // HWASAN_ALLOCATOR_H

lib/hwasan/hwasan_allocator.cc

 enum {
   CHUNK_INVALID = 0,
   CHUNK_FREE = 1,
   CHUNK_ALLOCATED = 2
 };
 
 struct Metadata {
   u64 state : 2;
-  u64 requested_size : 62;
+  u32 requested_size;  // Current use cases of hwasan do not expect sizes > 4G.
   u32 alloc_context_id;
   u32 free_context_id;
 };
 
 bool HwasanChunkView::IsValid() const {
   return metadata_ && metadata_->state != CHUNK_INVALID;
 }
 bool HwasanChunkView::IsAllocated() const {
if (UNLIKELY(!allocated)) {
     SetAllocatorOutOfMemory();
     if (AllocatorMayReturnNull())
       return nullptr;
     ReportOutOfMemory(size, stack);
   }
   Metadata *meta =
       reinterpret_cast<Metadata *>(allocator.GetMetaData(allocated));
   meta->state = CHUNK_ALLOCATED;
-  meta->requested_size = size;
+  meta->requested_size = static_cast<u32>(size);
   meta->alloc_context_id = StackDepotPut(*stack);
   if (zeroise) {
     internal_memset(allocated, 0, size);
   } else if (flags()->max_malloc_fill_size > 0) {
     uptr fill_size = Min(size, (uptr)flags()->max_malloc_fill_size);
     internal_memset(allocated, flags()->malloc_fill_byte, fill_size);
   }
 
void HwasanDeallocate(StackTrace *stack, void *user_ptr) {
   if (!PointerAndMemoryTagsMatch(user_ptr))
     ReportInvalidFree(stack, reinterpret_cast<uptr>(user_ptr));
 
   void *p = GetAddressFromPointer(user_ptr);
   Metadata *meta = reinterpret_cast<Metadata *>(allocator.GetMetaData(p));
   uptr size = meta->requested_size;
   meta->state = CHUNK_FREE;
   meta->requested_size = 0;
-  meta->free_context_id = StackDepotPut(*stack);
+  u32 free_context_id = StackDepotPut(*stack);
+  meta->free_context_id = free_context_id;
   // This memory will not be reused by anyone else, so we are free to keep it
   // poisoned.
   HwasanThread *t = GetCurrentThread();
   if (flags()->max_free_fill_size > 0) {
     uptr fill_size = Min(size, (uptr)flags()->max_free_fill_size);
     internal_memset(p, flags()->free_fill_byte, fill_size);
   }
   if (flags()->tag_in_free &&
       atomic_load_relaxed(&hwasan_allocator_tagging_enabled))
     TagMemoryAligned((uptr)p, size,
                      t ? t->GenerateRandomTag() : kFallbackFreeTag);
   if (t) {
     AllocatorCache *cache = GetAllocatorCache(&t->malloc_storage());
     allocator.Deallocate(cache, p);
+    if (auto *ha = t->heap_allocations())
+      ha->push({reinterpret_cast<uptr>(user_ptr), free_context_id,
+                static_cast<u32>(size)});
   } else {
     SpinMutexLock l(&fallback_mutex);
     AllocatorCache *cache = &fallback_allocator_cache;
     allocator.Deallocate(cache, p);
   }
 }
 
 void *HwasanReallocate(StackTrace *stack, void *user_old_p, uptr new_size,
if (new_size <= actually_allocated_size) {
     return user_old_p;
   }
   uptr memcpy_size = Min(new_size, old_size);
   void *new_p = HwasanAllocate(stack, new_size, alignment, false /*zeroise*/);
   if (new_p) {
     internal_memcpy(new_p, old_p, memcpy_size);
     HwasanDeallocate(stack, old_p);
   }
+  // FIXME: update t->heap_allocations or simplify HwasanReallocate.
   return new_p;
 }
 
 void *HwasanCalloc(StackTrace *stack, uptr nmemb, uptr size) {
   if (UNLIKELY(CheckForCallocOverflow(size, nmemb))) {
     if (AllocatorMayReturnNull())
       return nullptr;
     ReportCallocOverflow(nmemb, size, stack);

lib/hwasan/hwasan_flags.inc

 HWASAN_FLAG(
     int, max_free_fill_size, 0,
     "HWASan allocator flag. max_free_fill_size is the maximal amount of "
     "bytes that will be filled with free_fill_byte during free.")
 HWASAN_FLAG(int, malloc_fill_byte, 0xbe,
           "Value used to fill the newly allocated memory.")
 HWASAN_FLAG(int, free_fill_byte, 0x55,
           "Value used to fill deallocated memory.")
+HWASAN_FLAG(int, heap_history_size, 1023,
+          "The number of heap (de)allocations remembered per thread. "
+          "Affects the quality of heap-related reports, but not the ability "
+          "to find bugs.")

lib/hwasan/hwasan_report.cc

 // This file is a part of HWAddressSanitizer.
 //
 // Error reporting.
 //===----------------------------------------------------------------------===//
 
 #include "hwasan.h"
 #include "hwasan_allocator.h"
 #include "hwasan_mapping.h"
+#include "hwasan_thread.h"
 #include "sanitizer_common/sanitizer_allocator_internal.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_mutex.h"
 #include "sanitizer_common/sanitizer_report_decorator.h"
 #include "sanitizer_common/sanitizer_stackdepot.h"
 #include "sanitizer_common/sanitizer_symbolizer.h"
 
if (free_stack_id) {
       Printf("%spreviously allocated here:%s\n", d.Allocation(), d.Default());
     } else {
       Printf("%sallocated here:%s\n", d.Allocation(), d.Default());
     }
     GetStackTraceFromId(alloc_stack_id).Print();
   }
 };
 
+bool FindHeapAllocation(HeapAllocationsRingBuffer *rb,
+                        uptr tagged_addr,
+                        HeapAllocationRecord *har) {
+  if (!rb) return false;
+  for (uptr i = 0, size = rb->size(); i < size; i++) {
+    auto h = (*rb)[i];
+    if (h.tagged_addr <= tagged_addr &&
+        h.tagged_addr + h.requested_size > tagged_addr) {
+      *har = h;
+      return true;
+    }
+  }
+  return false;
+}
+
 bool GetHeapAddressInformation(uptr addr, uptr access_size,
                                HeapAddressDescription *description) {
   HwasanChunkView chunk = FindHeapChunkByAddress(addr);
   if (!chunk.IsValid())
     return false;
   description->addr = addr;
   description->alloc_stack_id = chunk.GetAllocStackId();
   description->free_stack_id = chunk.GetFreeStackId();
void ReportTagMismatch(StackTrace *stack, uptr addr, uptr access_size,
   Printf("%s of size %zu at %p tags: %02x/%02x (ptr/mem)\n",
          is_store ? "WRITE" : "READ", access_size, address, ptr_tag, mem_tag);
   Printf("%s", d.Default());
 
   stack->Print();
 
   PrintAddressDescription(address, access_size);
 
+  // Temporary functionality; to be folded into PrintAddressDescription.
+  // TODOs:
+  // * implement ThreadRegistry
+  // * check all threads, not just the current one.
+  // * remove reduntant fields from the allocator metadata
+  // * use the allocations found in the ring buffer for the main report.
+  HeapAllocationRecord har;
+  HwasanThread *t = GetCurrentThread();
+  if (t && FindHeapAllocation(t->heap_allocations(), addr, &har))
+    Printf("Address found in the ring buffer: %p %u %u\n", har.tagged_addr,
+           har.free_context_id, har.requested_size);
+
   PrintTagsAroundAddr(tag_ptr);
 
   ReportErrorSummary(bug_type, stack);
 }
 
 }  // namespace __hwasan

lib/hwasan/hwasan_thread.h

public:
   void EnterSymbolizer() { in_symbolizer_++; }
   void LeaveSymbolizer() { in_symbolizer_--; }
 
   bool InInterceptorScope() { return in_interceptor_scope_; }
   void EnterInterceptorScope() { in_interceptor_scope_++; }
   void LeaveInterceptorScope() { in_interceptor_scope_--; }
 
   HwasanThreadLocalMallocStorage &malloc_storage() { return malloc_storage_; }
+  HeapAllocationsRingBuffer *heap_allocations() {
+    return heap_allocations_;
+  }
 
   tag_t GenerateRandomTag();
 
   int destructor_iterations_;
 
  private:
   // NOTE: There is no HwasanThread constructor. It is allocated
   // via mmap() and *must* be valid in zero-initialized state.
private:
   unsigned in_signal_handler_;
   unsigned in_symbolizer_;
   unsigned in_interceptor_scope_;
 
   u32 random_state_;
   u32 random_buffer_;
 
   HwasanThreadLocalMallocStorage malloc_storage_;
+  HeapAllocationsRingBuffer *heap_allocations_;
 };
 
 HwasanThread *GetCurrentThread();
 void SetCurrentThread(HwasanThread *t);
 
 } // namespace __hwasan
 
 #endif // HWASAN_THREAD_H

lib/hwasan/hwasan_thread.cc

HwasanThread *HwasanThread::Create(thread_callback_t start_routine,
                                void *arg) {
   uptr PageSize = GetPageSizeCached();
   uptr size = RoundUpTo(sizeof(HwasanThread), PageSize);
   HwasanThread *thread = (HwasanThread*)MmapOrDie(size, __func__);
   thread->start_routine_ = start_routine;
   thread->arg_ = arg;
   thread->destructor_iterations_ = GetPthreadDestructorIterations();
   thread->random_state_ = flags()->random_tags ? RandomSeed() : 0;
-
+  if (auto sz = flags()->heap_history_size)
+    thread->heap_allocations_ = RingBuffer<HeapAllocationRecord>::New(sz);
   return thread;
 }
 
 void HwasanThread::SetThreadStackAndTls() {
   // If this process is "init" (pid 1), /proc may not be mounted yet.
   if (IsMainThread() && !FileExists("/proc/self/maps")) {
     stack_top_ = stack_bottom_ = 0;
     tls_begin_ = tls_end_ = 0;
void HwasanThread::ClearShadowForThreadStackAndTLS() {
   if (tls_begin_ != tls_end_)
     TagMemory(tls_begin_, tls_end_ - tls_begin_, 0);
 }
 
 void HwasanThread::Destroy() {
   malloc_storage().CommitBack();
   ClearShadowForThreadStackAndTLS();
   uptr size = RoundUpTo(sizeof(HwasanThread), GetPageSizeCached());
+  if (heap_allocations_)
+    heap_allocations_->Delete();
   UnmapOrDie(this, size);
   DTLS_Destroy();
 }
 
 thread_return_t HwasanThread::ThreadStart() {
   return start_routine_(arg_);
 }