[HWASan] Improve invalid free reports.

[hctim]

Summary

Improve invalid free reports by checking that the pointer is valid on
free. This is relatively cheap for the primary, but is somewhat
expensive for the secondary as it involves locking.

This patch also fixes up some minor grammatical errors in the existing
reports, namely 'of a X-byte region' instead of 'of X-byte region'.

[hctim]

• Fix up weird invalid space character.

[eugenis]

compiler-rt/lib/hwasan/hwasan_allocator.cpp

184

That's O(live allocations).

compiler-rt/lib/hwasan/hwasan_report.cpp

538

just print "??" instead of the memory tag

[hctim]

Offline chat - we're talking about how to identify secondary allocations in a cheaper-than-O(n) way. There's two possibilities, either the secondary maintains a hashset of allocated ptrs (I really don't want to implement this data structure), or we make it stash a cookie that's stored on free(). Probably the latter.

compiler-rt/lib/hwasan/hwasan_allocator.cpp

if (flags()->tag_in_malloc && malloc_bisect(stack, orig_size)) {
       user_ptr = (void *)TagMemoryAligned((uptr)user_ptr, size, 0);
     }
   }
 
   HWASAN_MALLOC_HOOK(user_ptr, size);
   return user_ptr;
 }
 
-static bool PointerAndMemoryTagsMatch(void *tagged_ptr) {
+static bool IsInvalidFree(void *tagged_ptr) {
   CHECK(tagged_ptr);
   uptr tagged_uptr = reinterpret_cast<uptr>(tagged_ptr);
-  tag_t mem_tag = *reinterpret_cast<tag_t *>(
-      MemToShadow(reinterpret_cast<uptr>(UntagPtr(tagged_ptr))));
-  return PossiblyShortTagMatches(mem_tag, tagged_uptr, 1);
+  void *untagged_ptr = UntagPtr(tagged_ptr);
+  uptr untagged_uptr = reinterpret_cast<uptr>(untagged_ptr);
+  // Note: GetBlockBegin is expensive for the secondary, as it requires locking.
+  // Not so bad when we're considering there's an mmap() syscall, but many
+  // threads that are free()-ing secondary allocations at the same time might
+  // get some contention.
+  if (untagged_ptr != allocator.GetBlockBegin(untagged_ptr))
+    return true;
+
+  tag_t mem_tag = *reinterpret_cast<tag_t *>(MemToShadow(untagged_uptr));
+  return !PossiblyShortTagMatches(mem_tag, tagged_uptr, 1);
 }
 
-static void HwasanDeallocate(StackTrace *stack, void *tagged_ptr) {
+static void HwasanDeallocate(StackTrace *stack, void *tagged_ptr,
+                             bool check_if_invalid = true) {
   CHECK(tagged_ptr);
   HWASAN_FREE_HOOK(tagged_ptr);
 
-  if (!PointerAndMemoryTagsMatch(tagged_ptr))
+  void *untagged_ptr = UntagPtr(tagged_ptr);
+  if (check_if_invalid && IsInvalidFree(tagged_ptr))
     ReportInvalidFree(stack, reinterpret_cast<uptr>(tagged_ptr));
 
-  void *untagged_ptr = UntagPtr(tagged_ptr);
   void *aligned_ptr = reinterpret_cast<void *>(
       RoundDownTo(reinterpret_cast<uptr>(untagged_ptr), kShadowAlignment));
   Metadata *meta =
       reinterpret_cast<Metadata *>(allocator.GetMetaData(aligned_ptr));
   uptr orig_size = meta->get_requested_size();
   u32 free_context_id = StackDepotPut(*stack);
   u32 alloc_context_id = meta->alloc_context_id;
 
if (t) {
     SpinMutexLock l(&fallback_mutex);
     AllocatorCache *cache = &fallback_allocator_cache;
     allocator.Deallocate(cache, aligned_ptr);
   }
 }
 
 static void *HwasanReallocate(StackTrace *stack, void *tagged_ptr_old,
                               uptr new_size, uptr alignment) {
-  if (!PointerAndMemoryTagsMatch(tagged_ptr_old))
+  if (IsInvalidFree(tagged_ptr_old))
     ReportInvalidFree(stack, reinterpret_cast<uptr>(tagged_ptr_old));
 
   void *tagged_ptr_new =
       HwasanAllocate(stack, new_size, alignment, false /*zeroise*/);
   if (tagged_ptr_old && tagged_ptr_new) {
     void *untagged_ptr_old =  UntagPtr(tagged_ptr_old);
     Metadata *meta =
         reinterpret_cast<Metadata *>(allocator.GetMetaData(untagged_ptr_old));
     internal_memcpy(
         UntagPtr(tagged_ptr_new), untagged_ptr_old,
         Min(new_size, static_cast<uptr>(meta->get_requested_size())));
-    HwasanDeallocate(stack, tagged_ptr_old);
+    // Invalid checks were conducted above, no need to re-do them.
+    HwasanDeallocate(stack, tagged_ptr_old, /*check_if_invalid*/ false);
   }
   return tagged_ptr_new;
 }
 
 static void *HwasanCalloc(StackTrace *stack, uptr nmemb, uptr size) {
   if (UNLIKELY(CheckForCallocOverflow(size, nmemb))) {
     if (AllocatorMayReturnNull())
       return nullptr;

compiler-rt/lib/hwasan/hwasan_report.cpp

for (int i = 0; i < 1000; i++) {
     ++right;
   }
 
   if (candidate) {
     uptr mem = ShadowToMem(reinterpret_cast<uptr>(candidate));
     HwasanChunkView chunk = FindHeapChunkByAddress(mem);
     if (chunk.IsAllocated()) {
       Printf("%s", d.Location());
-      Printf("%p is located %zd bytes to the %s of %zd-byte region [%p,%p)\n",
-             untagged_addr,
-             candidate == left ? untagged_addr - chunk.End()
-                               : chunk.Beg() - untagged_addr,
-             candidate == left ? "right" : "left", chunk.UsedSize(),
-             chunk.Beg(), chunk.End());
+      uptr offset = chunk.Beg() - untagged_addr;
+      const char *locality = "to the left of";
+      if (candidate == left) {
+        uptr offset_from_start = untagged_addr - chunk.Beg();
+        if (offset_from_start < chunk.UsedSize()) {
+          offset = offset_from_start;
+          locality = "into";
+        } else {
+          offset = untagged_addr - chunk.End();
+          locality = "to the right of";
+        }
+      }
+
+      Printf("%p is located %zd byte%s %s a %zd-byte region [%p,%p)\n",
+             untagged_addr, offset, offset == 1 ? "" : "s", locality,
+             chunk.UsedSize(), chunk.Beg(), chunk.End());
       Printf("%s", d.Allocation());
       Printf("allocated here:\n");
       Printf("%s", d.Default());
       GetStackTraceFromId(chunk.GetAllocStackId()).Print();
       num_descriptions_printed++;
     } else {
       // Check whether the address points into a loaded library. If so, this is
       // most likely a global variable.
       const char *module_name;
       uptr module_address;
       Symbolizer *sym = Symbolizer::GetOrInit();
       if (sym->GetModuleNameAndOffsetForPC(mem, &module_name,
                                            &module_address)) {
         DataInfo info;
         if (sym->SymbolizeData(mem, &info) && info.start) {
           Printf(
-              "%p is located %zd bytes to the %s of %zd-byte global variable "
+              "%p is located %zd bytes to the %s of a %zd-byte global variable "
               "%s [%p,%p) in %s\n",
               untagged_addr,
               candidate == left ? untagged_addr - (info.start + info.size)
                                 : info.start - untagged_addr,
               candidate == left ? "right" : "left", info.size, info.name,
               info.start, info.start + info.size, module_name);
         } else {
           uptr size = GetGlobalSizeFromDescriptor(mem);
void PrintAddressDescription(
   hwasanThreadList().VisitAllLiveThreads([&](Thread *t) {
     // Scan all threads' ring buffers to find if it's a heap-use-after-free.
     HeapAllocationRecord har;
     uptr ring_index, num_matching_addrs, num_matching_addrs_4b;
     if (FindHeapAllocation(t->heap_allocations(), tagged_addr, &har,
                            &ring_index, &num_matching_addrs,
                            &num_matching_addrs_4b)) {
       Printf("%s", d.Location());
-      Printf("%p is located %zd bytes inside of %zd-byte region [%p,%p)\n",
+      Printf("%p is located %zd bytes inside of a %zd-byte region [%p,%p)\n",
              untagged_addr, untagged_addr - UntagAddr(har.tagged_addr),
              har.requested_size, UntagAddr(har.tagged_addr),
              UntagAddr(har.tagged_addr) + har.requested_size);
       Printf("%s", d.Allocation());
       Printf("freed by thread T%zd here:\n", t->unique_id());
       Printf("%s", d.Default());
       GetStackTraceFromId(har.free_context_id).Print();
 

 }
 
 void ReportInvalidFree(StackTrace *stack, uptr tagged_addr) {
   ScopedReport R(flags()->halt_on_error);
 
   uptr untagged_addr = UntagAddr(tagged_addr);
   tag_t ptr_tag = GetTagFromPointer(tagged_addr);
   tag_t *tag_ptr = reinterpret_cast<tag_t*>(MemToShadow(untagged_addr));
-  tag_t mem_tag = *tag_ptr;
+
+  bool shadow_in_range = false;
+  uptr shadow_ptr = reinterpret_cast<uptr>(tag_ptr);
+  if ((shadow_ptr >= kLowShadowStart && shadow_ptr < kLowShadowEnd) ||
+      (shadow_ptr >= kHighShadowStart && shadow_ptr < kHighShadowEnd))
+    shadow_in_range = true;
+
   Decorator d;
   Printf("%s", d.Error());
   uptr pc = stack->size ? stack->trace[0] : 0;
   const char *bug_type = "invalid-free";
   Report("ERROR: %s: %s on address %p at pc %p\n", SanitizerToolName, bug_type,
          untagged_addr, pc);
   Printf("%s", d.Access());
-  Printf("tags: %02x/%02x (ptr/mem)\n", ptr_tag, mem_tag);
+  if (shadow_in_range)
+    Printf("tags: %02x/%02x (ptr/mem)\n", ptr_tag, *tag_ptr);
+  else
+    Printf(
+        "pointer tag: %02x (wild free - pointer is not in any known bounds).\n",
+        ptr_tag);
   Printf("%s", d.Default());
 
   stack->Print();
 
+  if (shadow_in_range) {
     PrintAddressDescription(tagged_addr, 0, nullptr);
-
     PrintTagsAroundAddr(tag_ptr);
+  }
 
   ReportErrorSummary(bug_type, stack);
 }
 
 void ReportTailOverwritten(StackTrace *stack, uptr tagged_addr, uptr orig_size,
                            const u8 *expected) {
   uptr tail_size = kShadowAlignment - (orig_size % kShadowAlignment);
   ScopedReport R(flags()->halt_on_error);

compiler-rt/test/hwasan/TestCases/global.c

 // RUN: %clang_hwasan %s -o %t
 // RUN: %run %t 0
 // RUN: not %run %t 1 2>&1 | FileCheck --check-prefixes=CHECK,RSYM %s
 // RUN: not %env_hwasan_opts=symbolize=0 %run %t 1 2>&1 | FileCheck --check-prefixes=CHECK,RNOSYM %s
 // RUN: not %run %t -1 2>&1 | FileCheck --check-prefixes=CHECK,LSYM %s
 // RUN: not %env_hwasan_opts=symbolize=0 %run %t -1 2>&1 | FileCheck --check-prefixes=CHECK,LNOSYM %s
 
+#include <stdlib.h>
+
 int x = 1;
 
 int main(int argc, char **argv) {
-  // RSYM: is located 0 bytes to the right of 4-byte global variable x {{.*}} in {{.*}}global.c.tmp
+  // RSYM: is located 0 bytes to the right of a 4-byte global variable x {{.*}} in {{.*}}global.c.tmp
   // RNOSYM: is located to the right of a 4-byte global variable in ({{.*}}global.c.tmp+{{.*}})
-  // LSYM: is located 4 bytes to the left of 4-byte global variable x {{.*}} in {{.*}}global.c.tmp
+  // LSYM: is located 4 bytes to the left of a 4-byte global variable x {{.*}} in {{.*}}global.c.tmp
   // LNOSYM: is located to the left of a 4-byte global variable in ({{.*}}global.c.tmp+{{.*}})
   // CHECK-NOT: can not describe
   (&x)[atoi(argv[1])] = 1;
 }

compiler-rt/test/hwasan/TestCases/heap-buffer-overflow.c

int main(int argc, char **argv) {
   __hwasan_enable_allocator_tagging();
   int offset = argc < 2 ? 40 : atoi(argv[1]);
   int size = argc < 3 ? 30 : atoi(argv[2]);
   char * volatile x = (char*)malloc(size);
   untag_fprintf(stderr, "base: %p access: %p\n", x, &x[offset]);
   sink = x[offset];
 
 // CHECK40: allocated heap chunk; size: 32 offset: 8
-// CHECK40: is located 10 bytes to the right of 30-byte region
+// CHECK40: is located 10 bytes to the right of a 30-byte region
 //
 // CHECK80: allocated heap chunk; size: 32 offset: 16
-// CHECK80: is located 50 bytes to the right of 30-byte region
+// CHECK80: is located 50 bytes to the right of a 30-byte region
 //
-// CHECKm30: is located 30 bytes to the left of 30-byte region
+// CHECKm30: is located 30 bytes to the left of a 30-byte region
 //
 // CHECKMm30: is a large allocated heap chunk; size: 1003520 offset: -30
-// CHECKMm30: is located 30 bytes to the left of 1000000-byte region
+// CHECKMm30: is located 30 bytes to the left of a 1000000-byte region
 //
 // CHECKM: is a large allocated heap chunk; size: 1003520 offset: 1000000
-// CHECKM: is located 0 bytes to the right of 1000000-byte region
+// CHECKM: is located 0 bytes to the right of a 1000000-byte region
 //
 // CHECK31: tags: [[TAG:..]]/0e (ptr/mem)
-// CHECK31: is located 1 bytes to the right of 30-byte region
+// CHECK31: is located 1 byte to the right of a 30-byte region
 // CHECK31: Memory tags around the buggy address
 // CHECK31: [0e]
 // CHECK31: Tags for short granules around the buggy address
 // CHECK31: {{\[}}[[TAG]]]
 //
-// CHECK20: is located 10 bytes to the right of 20-byte region [0x{{.*}}0,0x{{.*}}4)
+// CHECK20: is located 10 bytes to the right of a 20-byte region [0x{{.*}}0,0x{{.*}}4)
   free(x);
 }

compiler-rt/test/hwasan/TestCases/invalid-free.c

+#include <stdio.h>
+#include <stdlib.h>
+
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=1 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,1
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=2 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,2
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=3 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,3
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=4 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,4
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=5 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,5
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=6 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,6
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=7 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,7
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=8 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,8
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=9 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,9
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=10 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,10
+// RUN: %clang_hwasan %s -o %t -DTESTCASE=11 && not %run %t 2>&1 | FileCheck %s --check-prefixes=ALL,11
+
+// Note:
+//  Huge OOB -> Outside of the size class.
+//  Large    -> Outside the allocation, inside the size class (or, in the case
+//              of secondary allocations, it's adjacent).
+//  Medium   -> Inside the allocation, but outside of the granule.
+//  Tiny     -> Inside the allocation, inside the granule.
+
+#include <sanitizer/hwasan_interface.h>
+
+// ALL: HWAddressSanitizer: invalid-free
+int main(int argc, char **argv) {
+  __hwasan_enable_allocator_tagging();
+#if TESTCASE == 1
+  // Huge OOB from the primary.
+  char *p = (char *)malloc(128);
+  free(p + 0x10000000000);
+  // 1: wild free - pointer is not in any known bounds
+#elif TESTCASE == 2
+  // Large OOB from the primary.
+  char *p = (char *)malloc(128);
+  free(p + 128);
+  // 2: is located 0 bytes to the right of a 128-byte region
+#elif TESTCASE == 3
+  // Medium OOB from the primary.
+  char *p = (char *)malloc(128);
+  free(p + 64);
+  // 3: is a small allocated heap chunk
+  // 3: is located 64 bytes into a 128-byte region
+#elif TESTCASE == 4
+  // Tiny OOB from the primary.
+  char *p = (char*) malloc(128);
+  free(p + 1);
+  // 4: is a small allocated heap chunk
+  // 4: is located 1 byte into a 128-byte region
+#elif TESTCASE == 5
+  // Huge OOB from the secondary.
+  char *p = (char *)malloc(0x100000000);
+  free(p + 0x400000000);
+  // It's possible for the shadow to be mapped here, so don't check for any
+  // specific address description.
+#elif TESTCASE == 6
+  // Large OOB from the secondary.
+  char *p = (char *)malloc(0x100000000);
+  free(p + 0x100000000);
+  // 6: is located 0 bytes to the right of a 4294967296-byte region
+#elif TESTCASE == 7
+  // Medium OOB from the secondary (specifically page aligned).
+  char *p = (char*) malloc(0x100000000);
+  free(p + 4096);
+  // 7: is a large allocated heap chunk
+  // 7: is located 4096 bytes into a 4294967296-byte region
+#elif TESTCASE == 8
+  // Tiny OOB from the secondary.
+  char *p = (char*) malloc(0x100000000);
+  free(p + 1);
+  // 8: is a large allocated heap chunk
+  // 8: is located 1 byte into a 4294967296-byte region
+#elif TESTCASE == 9
+  // Completely wild free.
+  char* p = NULL;
+  free(p + 0xdeadbeef0000ul);
+  // 9: wild free - pointer is not in any known bounds
+#elif TESTCASE == 10
+  // OOB underflow from the primary.
+  char *p = (char*) malloc(128);
+  free(p - 1);
+  // 10: is located 1 byte to the left of a 128-byte region
+#elif TESTCASE == 11
+  // OOB underflow from the secondary.
+  char *p = (char*) malloc(0x100000000);
+  free(p - 1);
+  // 11: is located 1 byte to the left of a 4294967296-byte region
+#else
+#error Invalid Test ID.
+#endif
+  return 0;
+}

compiler-rt/test/hwasan/TestCases/tag_in_free.c

int main() {
   for (int i = 0; i < 100; ++i) {
     char * volatile p = (char*)malloc(10);
     free(p);
   }
 
   char * volatile p = (char*)malloc(10);
 #ifdef MALLOC
   // MALLOC: READ of size 1 at
-  // MALLOC: is located 6 bytes to the right of 10-byte region
+  // MALLOC: is located 6 bytes to the right of a 10-byte region
   // MALLOC: allocated here:
   char volatile x = p[16];
 #endif
   free(p);
 #ifdef FREE
   // FREE: READ of size 1 at
-  // FREE: is located 0 bytes inside of 10-byte region
+  // FREE: is located 0 bytes inside of a 10-byte region
   // FREE: freed by thread T0 here:
   // FREE: previously allocated here:
   char volatile y = p[0];
 #endif
 
   __hwasan_disable_allocator_tagging();
 
   return 0;
 }

compiler-rt/test/hwasan/TestCases/use-after-free.c

int main() {
   untag_fprintf(stderr, ISREAD ? "Going to do a READ\n" : "Going to do a WRITE\n");
   // CHECK: Going to do a [[TYPE:[A-Z]*]]
   int r = 0;
   if (ISREAD) r = x[5]; else x[5] = 42;  // should be on the same line.
   // CHECK: [[TYPE]] of size 1 at {{.*}} tags: [[PTR_TAG:[0-9a-f][0-9a-f]]]/[[MEM_TAG:[0-9a-f][0-9a-f]]] (ptr/mem)
   // CHECK: #0 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-2]]
   // Offset is 5 or 11 depending on left/right alignment.
   // CHECK: is a small unallocated heap chunk; size: 32 offset: {{5|11}}
-  // CHECK: is located 5 bytes inside of 10-byte region
+  // CHECK: is located 5 bytes inside of a 10-byte region
   //
   // CHECK: freed by thread {{.*}} here:
   // CHECK: #0 {{.*}} in {{.*}}free{{.*}} {{.*}}hwasan_interceptors.cpp
   // CHECK: #1 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-14]]
 
   // CHECK: previously allocated here:
   // CHECK: #0 {{.*}} in {{.*}}malloc{{.*}} {{.*}}hwasan_interceptors.cpp
   // CHECK: #1 {{.*}} in main {{.*}}use-after-free.c:[[@LINE-19]]
   // CHECK: Memory tags around the buggy address (one tag corresponds to 16 bytes):
   // CHECK: =>{{.*}}[[MEM_TAG]]
   // CHECK: SUMMARY: HWAddressSanitizer: tag-mismatch {{.*}} in main
   return r;
 }