Enhance libsanitizer support for invalid-pointer-pair.

[jakubjelinek]

Summary

This was intended to go into D38971, but Phabricator doesn't want to allow me to upload it there because I haven't filed that and Martin is on longer vacation.
I believe I've addressed all review comments from the last review.

[jakubjelinek]

Can you or Konstantin please commit it? I don't have write access to llvm repo.
Thanks.

[alekseyshl]

I'll do it

lib/asan/asan_descriptions.h

struct GlobalAddressDescription {
   // Assume address is close to at most four globals.
   static const int kMaxGlobals = 4;
   __asan_global globals[kMaxGlobals];
   u32 reg_sites[kMaxGlobals];
   uptr access_size;
   u8 size;
 
   void Print(const char *bug_type = "") const;
+
+  // Returns true when this descriptions points inside the same global variable
+  // as other. Descriptions can have different address within the variable
+  bool PointsInsideTheSameVariable(const GlobalAddressDescription &other) const;
 };
 
 bool GetGlobalAddressInformation(uptr addr, uptr access_size,
                                  GlobalAddressDescription *descr);
 bool DescribeAddressIfGlobal(uptr addr, uptr access_size, const char *bug_type);
 
 // General function to describe an address. Will try to describe the address as
 // a shadow, global (variable), stack, or heap address.

lib/asan/asan_descriptions.cc

if (bug_type &&
         0 == internal_strcmp(bug_type, "initialization-order-fiasco") &&
         reg_sites[i]) {
       Printf("  registered at:\n");
       StackDepotGet(reg_sites[i]).Print();
     }
   }
 }
 
+bool GlobalAddressDescription::PointsInsideTheSameVariable(
+    const GlobalAddressDescription &other) const {
+  if (size == 0 || other.size == 0) return false;
+
+  for (uptr i = 0; i < size; i++) {
+    const __asan_global &a = globals[i];
+    for (uptr j = 0; j < other.size; j++) {
+      const __asan_global &b = other.globals[j];
+      if (a.beg == b.beg &&
+          a.beg <= addr &&
+          b.beg <= other.addr &&
+          (addr + access_size) < (a.beg + a.size) &&
+          (other.addr + other.access_size) < (b.beg + b.size))
+        return true;
+    }
+  }
+
+  return false;
+}
+
 void StackAddressDescription::Print() const {
   Decorator d;
   char tname[128];
   Printf("%s", d.Location());
   Printf("Address %p is located in stack of thread T%d%s", addr, tid,
          ThreadNameWithParenthesis(tid, tname, sizeof(tname)));
 
   if (!frame_descr) {

lib/asan/asan_report.cc

 // ----------------------- CheckForInvalidPointerPair ----------- {{{1
 static NOINLINE void ReportInvalidPointerPair(uptr pc, uptr bp, uptr sp,
                                               uptr a1, uptr a2) {
   ScopedInErrorReport in_report;
   ErrorInvalidPointerPair error(GetCurrentTidOrInvalid(), pc, bp, sp, a1, a2);
   in_report.ReportError(error);
 }
 
+static bool IsInvalidPointerPair(uptr a1, uptr a2) {
+  if (a1 == a2)
+    return false;
+
+  // 256B in shadow memory can be iterated quite fast
+  static const uptr kMaxOffset = 2048;
+
+  uptr left = a1 < a2 ? a1 : a2;
+  uptr right = a1 < a2 ? a2 : a1;
+  uptr offset = right - left;
+  if (offset <= kMaxOffset)
+    return __asan_region_is_poisoned(left, offset);
+
+  AsanThread *t = GetCurrentThread();
+
+  // check whether left is a stack memory pointer
+  if (uptr shadow_offset1 = t->GetStackVariableShadowStart(left)) {
+    uptr shadow_offset2 = t->GetStackVariableShadowStart(right);
+    return shadow_offset2 == 0 || shadow_offset1 != shadow_offset2;
+  }
+
+  // check whether left is a heap memory address
+  HeapAddressDescription hdesc1, hdesc2;
+  if (GetHeapAddressInformation(left, 0, &hdesc1) &&
+      hdesc1.chunk_access.access_type == kAccessTypeInside)
+    return !GetHeapAddressInformation(right, 0, &hdesc2) ||
+        hdesc2.chunk_access.access_type != kAccessTypeInside ||
+        hdesc1.chunk_access.chunk_begin != hdesc2.chunk_access.chunk_begin;
+
+  // check whether left is an address of a global variable
+  GlobalAddressDescription gdesc1, gdesc2;
+  if (GetGlobalAddressInformation(left, 0, &gdesc1))
+    return !GetGlobalAddressInformation(right - 1, 0, &gdesc2) ||
+        !gdesc1.PointsInsideTheSameVariable(gdesc2);
+
+  if (t->GetStackVariableShadowStart(right) ||
+      GetHeapAddressInformation(right, 0, &hdesc2) ||
+      GetGlobalAddressInformation(right - 1, 0, &gdesc2))
+    return true;
+
+  // At this point we know nothing about both a1 and a2 addresses.
+  return false;
+}
+
 static INLINE void CheckForInvalidPointerPair(void *p1, void *p2) {
   if (!flags()->detect_invalid_pointer_pairs) return;
   uptr a1 = reinterpret_cast<uptr>(p1);
   uptr a2 = reinterpret_cast<uptr>(p2);
-  AsanChunkView chunk1 = FindHeapChunkByAddress(a1);
-  AsanChunkView chunk2 = FindHeapChunkByAddress(a2);
-  bool valid1 = chunk1.IsAllocated();
-  bool valid2 = chunk2.IsAllocated();
-  if (!valid1 || !valid2 || !chunk1.Eq(chunk2)) {
+
+  if (IsInvalidPointerPair(a1, a2)) {
     GET_CALLER_PC_BP_SP;
-    return ReportInvalidPointerPair(pc, bp, sp, a1, a2);
+    ReportInvalidPointerPair(pc, bp, sp, a1, a2);
   }
 }
 // ----------------------- Mac-specific reports ----------------- {{{1
 
 void ReportMacMzReallocUnknown(uptr addr, uptr zone_ptr, const char *zone_name,
                                BufferedStackTrace *stack) {
   ScopedInErrorReport in_report;
   Printf("mz_realloc(%p) -- attempting to realloc unallocated memory.\n"

lib/asan/asan_thread.h

public:
 
   struct StackFrameAccess {
     uptr offset;
     uptr frame_pc;
     const char *frame_descr;
   };
   bool GetStackFrameAccessByAddr(uptr addr, StackFrameAccess *access);
 
+  // Returns a pointer to the start of the stack variable's shadow memory.
+  uptr GetStackVariableShadowStart(uptr addr);
+
   bool AddrIsInStack(uptr addr);
 
   void DeleteFakeStack(int tid) {
     if (!fake_stack_) return;
     FakeStack *t = fake_stack_;
     fake_stack_ = nullptr;
     SetTLSFakeStack(nullptr);
     t->Destroy(tid);

lib/asan/asan_thread.cc

bool AsanThread::GetStackFrameAccessByAddr(uptr addr,
   } else if (has_fake_stack()) {
     bottom = fake_stack()->AddrIsInFakeStack(addr);
     CHECK(bottom);
     access->offset = addr - bottom;
     access->frame_pc = ((uptr*)bottom)[2];
     access->frame_descr = (const char *)((uptr*)bottom)[1];
     return true;
   }
-  uptr aligned_addr = addr & ~(SANITIZER_WORDSIZE/8 - 1);  // align addr.
+  uptr aligned_addr = RoundDownTo(addr, SANITIZER_WORDSIZE / 8);  // align addr.
   uptr mem_ptr = RoundDownTo(aligned_addr, SHADOW_GRANULARITY);
   u8 *shadow_ptr = (u8*)MemToShadow(aligned_addr);
   u8 *shadow_bottom = (u8*)MemToShadow(bottom);
 
   while (shadow_ptr >= shadow_bottom &&
          *shadow_ptr != kAsanStackLeftRedzoneMagic) {
     shadow_ptr--;
     mem_ptr -= SHADOW_GRANULARITY;
bool AsanThread::GetStackFrameAccessByAddr(uptr addr,
   uptr* ptr = (uptr*)(mem_ptr + SHADOW_GRANULARITY);
   CHECK(ptr[0] == kCurrentStackFrameMagic);
   access->offset = addr - (uptr)ptr;
   access->frame_pc = ptr[2];
   access->frame_descr = (const char*)ptr[1];
   return true;
 }
 
+uptr AsanThread::GetStackVariableShadowStart(uptr addr) {
+  uptr bottom = 0;
+  if (AddrIsInStack(addr)) {
+    bottom = stack_bottom();
+  } else if (has_fake_stack()) {
+    bottom = fake_stack()->AddrIsInFakeStack(addr);
+    CHECK(bottom);
+  } else
+    return 0;
+
+  uptr aligned_addr = RoundDownTo(addr, SANITIZER_WORDSIZE / 8);  // align addr.
+  u8 *shadow_ptr = (u8*)MemToShadow(aligned_addr);
+  u8 *shadow_bottom = (u8*)MemToShadow(bottom);
+
+  while (shadow_ptr >= shadow_bottom &&
+         (*shadow_ptr != kAsanStackLeftRedzoneMagic &&
+          *shadow_ptr != kAsanStackMidRedzoneMagic &&
+          *shadow_ptr != kAsanStackRightRedzoneMagic))
+    shadow_ptr--;
+
+  return (uptr)shadow_ptr + 1;
+}
+
 bool AsanThread::AddrIsInStack(uptr addr) {
   const auto bounds = GetStackBounds();
   return addr >= bounds.bottom && addr < bounds.top;
 }
 
 static bool ThreadStackContainsAddress(ThreadContextBase *tctx_base,
                                        void *addr) {
   AsanThreadContext *tctx = static_cast<AsanThreadContext*>(tctx_base);

test/asan/TestCases/Posix/invalid-pointer-pairs-threads.cc

+// RUN: %clangxx_asan -O0 %s -o %t -mllvm -asan-detect-invalid-pointer-pair
+
+// RUN: %env_asan_opts=detect_invalid_pointer_pairs=1 %run %t a 2>&1 | FileCheck %s -check-prefix=OK -allow-empty
+// RUN: %env_asan_opts=detect_invalid_pointer_pairs=1 not %run %t b 2>&1 | FileCheck %s -check-prefix=B
+
+#include <assert.h>
+#include <pthread.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+char *pointers[2];
+pthread_barrier_t bar;
+
+void *thread_main(void *n) {
+  char local;
+
+  unsigned long id = (unsigned long)n;
+  pointers[id] = &local;
+  pthread_barrier_wait(&bar);
+  pthread_barrier_wait(&bar);
+
+  return NULL;
+}
+
+int main(int argc, char **argv) {
+  assert(argc >= 2);
+
+  char t = argv[1][0];
+
+  pthread_t threads[2];
+  pthread_barrier_init(&bar, NULL, 3);
+  pthread_create(&threads[0], 0, thread_main, (void *)0);
+  pthread_create(&threads[1], 0, thread_main, (void *)1);
+  pthread_barrier_wait(&bar);
+
+  if (t == 'a') {
+    // OK-NOT: not handled yet
+    unsigned r = pointers[0] - pointers[1];
+  } else {
+    char local;
+    char *parent_pointer = &local;
+
+    // B: ERROR: AddressSanitizer: invalid-pointer-pair
+    // B: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-threads.cc:[[@LINE+1]]
+    unsigned r = parent_pointer - pointers[0];
+  }
+
+  pthread_barrier_wait(&bar);
+  pthread_join(threads[0], 0);
+  pthread_join(threads[1], 0);
+  pthread_barrier_destroy(&bar);
+
+  return 0;
+}

test/asan/TestCases/invalid-pointer-pairs-compare-errors.cc

+// RUN: %clangxx_asan -O0 %s -o %t -mllvm -asan-detect-invalid-pointer-pair
+
+// RUN: %env_asan_opts=detect_invalid_pointer_pairs=1:halt_on_error=0 %run %t 2>&1 | FileCheck %s
+
+#include <assert.h>
+#include <stdlib.h>
+
+int foo(char *p, char *q) {
+  return p > q;
+}
+
+char global1[100] = {}, global2[100] = {};
+char small_global[7] = {};
+char large_global[5000] = {};
+
+int main() {
+  // Heap allocated memory.
+  char *heap1 = (char *)malloc(42);
+  char *heap2 = (char *)malloc(42);
+
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(heap1, heap2);
+  free(heap1);
+  free(heap2);
+
+  heap1 = (char *)malloc(1024);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(heap1, heap1 + 1025);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(heap1 + 1024, heap1 + 1025);
+  free(heap1);
+
+  heap1 = (char *)malloc(4096);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(heap1, heap1 + 4097);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(heap1, 0);
+
+  // Global variables.
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(&global1[0], &global2[10]);
+
+  char *p = &small_global[0];
+  foo(p, p); // OK
+  foo(p, p + 7); // OK
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p, p + 8);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p - 1, p);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p, p - 1);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p - 1, p + 8);
+
+  p = &large_global[0];
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p - 1, p);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p, p - 1);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p, &global1[0]);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p, &small_global[0]);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(p, 0);
+
+  // Stack variables.
+  char stack1, stack2;
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(&stack1, &stack2);
+
+  // Mixtures.
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(heap1, &stack1);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  foo(heap1, &global1[0]);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  foo(&stack1, &global1[0]);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-compare-errors.cc:[[@LINE+1]]
+  foo(&stack1, 0);
+
+  free(heap1);
+
+  return 0;
+}

test/asan/TestCases/invalid-pointer-pairs-compare-success.cc

+// RUN: %clangxx_asan -O0 %s -o %t -mllvm -asan-detect-invalid-pointer-pair
+
+// RUN: %env_asan_opts=detect_invalid_pointer_pairs=1 %run %t
+
+#include <assert.h>
+#include <stdlib.h>
+
+int foo(char *p) {
+  char *p2 = p + 20;
+  return p > p2;
+}
+
+int bar(char *p, char *q) {
+  return p <= q;
+}
+
+int baz(char *p, char *q) {
+  return p != 0 && p < q;
+}
+
+char global[8192] = {};
+char small_global[7] = {};
+
+int main() {
+  // Heap allocated memory.
+  char *p = (char *)malloc(42);
+  int r = foo(p);
+  free(p);
+
+  p = (char *)malloc(1024);
+  bar(p, p + 1024);
+  bar(p + 1024, p + 1023);
+  bar(p + 1, p + 1023);
+  free(p);
+
+  p = (char *)malloc(4096);
+  bar(p, p + 4096);
+  bar(p + 10, p + 100);
+  bar(p + 1024, p + 4096);
+  bar(p + 4095, p + 4096);
+  bar(p + 4095, p + 4094);
+  bar(p + 100, p + 4096);
+  bar(p + 100, p + 4094);
+  free(p);
+
+  // Global variable.
+  bar(&global[0], &global[1]);
+  bar(&global[1], &global[2]);
+  bar(&global[2], &global[1]);
+  bar(&global[0], &global[100]);
+  bar(&global[1000], &global[7000]);
+  bar(&global[500], &global[10]);
+  p = &global[0];
+  bar(p, p + 8192);
+  p = &global[8000];
+  bar(p, p + 192);
+
+  p = &small_global[0];
+  bar(p, p + 1);
+  bar(p, p + 7);
+  bar(p + 7, p + 1);
+  bar(p + 6, p + 7);
+  bar(p + 7, p + 7);
+
+  // Stack variable.
+  char stack[10000];
+  bar(&stack[0], &stack[100]);
+  bar(&stack[1000], &stack[9000]);
+  bar(&stack[500], &stack[10]);
+
+  baz(0, &stack[10]);
+
+  return 0;
+}

test/asan/TestCases/invalid-pointer-pairs-subtract-errors.cc

+// RUN: %clangxx_asan -O0 %s -o %t -mllvm -asan-detect-invalid-pointer-pair
+
+// RUN: %env_asan_opts=detect_invalid_pointer_pairs=1:halt_on_error=0 %run %t 2>&1 | FileCheck %s
+
+#include <assert.h>
+#include <stdlib.h>
+
+int foo(char *p, char *q) {
+  return p - q;
+}
+
+char global1[100] = {}, global2[100] = {};
+
+int main() {
+  // Heap allocated memory.
+  char *heap1 = (char *)malloc(42);
+  char *heap2 = (char *)malloc(42);
+
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-subtract-errors.cc:[[@LINE+1]]
+  foo(heap1, heap2);
+
+  // Global variables.
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-subtract-errors.cc:[[@LINE+1]]
+  foo(&global1[0], &global2[10]);
+
+  // Stack variables.
+  char stack1, stack2;
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-subtract-errors.cc:[[@LINE+1]]
+  foo(&stack1, &stack2);
+
+  // Mixtures.
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-subtract-errors.cc:[[@LINE+1]]
+  foo(heap1, &stack1);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-subtract-errors.cc:[[@LINE+1]]
+  foo(heap1, &global1[0]);
+  // CHECK: ERROR: AddressSanitizer: invalid-pointer-pair
+  // CHECK: #{{[0-9]+ .*}} in main {{.*}}invalid-pointer-pairs-subtract-errors.cc:[[@LINE+1]]
+  foo(&stack1, &global1[0]);
+
+  free(heap1);
+  free(heap2);
+  return 0;
+}

test/asan/TestCases/invalid-pointer-pairs-subtract-success.cc

+// RUN: %clangxx_asan -O0 %s -o %t -mllvm -asan-detect-invalid-pointer-pair
+
+// RUN: %env_asan_opts=detect_invalid_pointer_pairs=1 %run %t
+
+#include <assert.h>
+#include <stdlib.h>
+
+int bar(char *p, char *q) {
+  return p <= q;
+}
+
+char global[10000] = {};
+
+int main() {
+  // Heap allocated memory.
+  char *p = (char *)malloc(42);
+  int r = bar(p, p + 20);
+  free(p);
+
+  // Global variable.
+  bar(&global[0], &global[100]);
+  bar(&global[1000], &global[9000]);
+  bar(&global[500], &global[10]);
+  bar(&global[0], &global[10000]);
+
+  // Stack variable.
+  char stack[10000];
+  bar(&stack[0], &stack[100]);
+  bar(&stack[1000], &stack[9000]);
+  bar(&stack[500], &stack[10]);
+
+  return 0;
+}