[ASan] Enhance libsanitizer support for invalid-pointer-pair.

Following patch adds support of all memory origins in
CheckForInvalidPointerPair function. For small difference of pointers,
it's directly done in shadow memory (the limit was set to 2048B).
Then we search for origin of first pointer and verify that the second
one has the same origin. If so, we verify that it points either to a same
variable (in case of stack memory or a global variable), or to a same
heap segment.

Committing on behanf of marxin and jakubjelinek.

Reviewers: alekseyshl, kcc

Subscribers: llvm-commits

Differential revision: https://reviews.llvm.org/D40600

llvm-svn: 319668

10 files changed, 410 insertions, 7 deletions

diff --git a/compiler-rt/lib/asan/asan_descriptions.cc b/compiler-rt/lib/asan/asan_descriptions.cc
index 0a4fb82fd39..86c6af7d9f7 100644
--- a/compiler-rt/lib/asan/asan_descriptions.cc
+++ b/compiler-rt/lib/asan/asan_descriptions.cc
@@ -336,6 +336,26 @@ void GlobalAddressDescription::Print(const char *bug_type) const {
   }
 }
 
+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];
diff --git a/compiler-rt/lib/asan/asan_descriptions.h b/compiler-rt/lib/asan/asan_descriptions.h
index cd278add832..1a1b01cf20c 100644
--- a/compiler-rt/lib/asan/asan_descriptions.h
+++ b/compiler-rt/lib/asan/asan_descriptions.h
@@ -146,6 +146,10 @@ struct GlobalAddressDescription {
   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,
diff --git a/compiler-rt/lib/asan/asan_report.cc b/compiler-rt/lib/asan/asan_report.cc
index 42fae9c73f0..e3bc02994ef 100644
--- a/compiler-rt/lib/asan/asan_report.cc
+++ b/compiler-rt/lib/asan/asan_report.cc
@@ -298,17 +298,58 @@ static NOINLINE void ReportInvalidPointerPair(uptr pc, uptr bp, uptr sp,
   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
diff --git a/compiler-rt/lib/asan/asan_thread.cc b/compiler-rt/lib/asan/asan_thread.cc
index c41d3ba9450..ad81512dff0 100644
--- a/compiler-rt/lib/asan/asan_thread.cc
+++ b/compiler-rt/lib/asan/asan_thread.cc
@@ -317,7 +317,7 @@ bool AsanThread::GetStackFrameAccessByAddr(uptr addr,
     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);
@@ -346,6 +346,29 @@ bool AsanThread::GetStackFrameAccessByAddr(uptr addr,
   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;
diff --git a/compiler-rt/lib/asan/asan_thread.h b/compiler-rt/lib/asan/asan_thread.h
index 1cd283a59bb..66091921101 100644
--- a/compiler-rt/lib/asan/asan_thread.h
+++ b/compiler-rt/lib/asan/asan_thread.h
@@ -90,6 +90,9 @@ class AsanThread {
   };
   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) {
diff --git a/compiler-rt/test/asan/TestCases/Posix/invalid-pointer-pairs-threads.cc b/compiler-rt/test/asan/TestCases/Posix/invalid-pointer-pairs-threads.cc
new file mode 100644
index 00000000000..db7f2b7fbc1
--- /dev/null
+++ b/compiler-rt/test/asan/TestCases/Posix/invalid-pointer-pairs-threads.cc
@@ -0,0 +1,54 @@
+// 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;
+}
diff --git a/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-compare-errors.cc b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-compare-errors.cc
new file mode 100644
index 00000000000..82f63359ead
--- /dev/null
+++ b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-compare-errors.cc
@@ -0,0 +1,103 @@
+// 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;
+}
diff --git a/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-compare-success.cc b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-compare-success.cc
new file mode 100644
index 00000000000..565d3908834
--- /dev/null
+++ b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-compare-success.cc
@@ -0,0 +1,74 @@
+// 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;
+}
diff --git a/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-subtract-errors.cc b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-subtract-errors.cc
new file mode 100644
index 00000000000..546f61f8184
--- /dev/null
+++ b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-subtract-errors.cc
@@ -0,0 +1,48 @@
+// 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;
+}
diff --git a/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-subtract-success.cc b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-subtract-success.cc
new file mode 100644
index 00000000000..4ce48424899
--- /dev/null
+++ b/compiler-rt/test/asan/TestCases/invalid-pointer-pairs-subtract-success.cc
@@ -0,0 +1,33 @@
+// 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;
+}