[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

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@319668 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 98 insertions, 7 deletions

diff --git a/lib/asan/asan_descriptions.cc b/lib/asan/asan_descriptions.cc
index 0a4fb82fd..86c6af7d9 100644
--- a/lib/asan/asan_descriptions.cc
+++ b/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/lib/asan/asan_descriptions.h b/lib/asan/asan_descriptions.h
index cd278add8..1a1b01cf2 100644
--- a/lib/asan/asan_descriptions.h
+++ b/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/lib/asan/asan_report.cc b/lib/asan/asan_report.cc
index 42fae9c73..e3bc02994 100644
--- a/lib/asan/asan_report.cc
+++ b/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/lib/asan/asan_thread.cc b/lib/asan/asan_thread.cc
index c41d3ba94..ad81512df 100644
--- a/lib/asan/asan_thread.cc
+++ b/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/lib/asan/asan_thread.h b/lib/asan/asan_thread.h
index 1cd283a59..660919211 100644
--- a/lib/asan/asan_thread.h
+++ b/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) {