From 15362445948550136a7e6a62e334ef943e832ce9 Mon Sep 17 00:00:00 2001
From: Zachary Turner <zturner@google.com>
Date: Wed, 25 Jun 2014 18:37:19 +0000
Subject: [PATCH] Fix a bug in the IRMemoryMap which generated bogus
 allocations.

Previously, only the starting locations of the candidate interval
and the existing interval were compared.  To correctly detect
range intersections, it is necessary to compare the entire range
of both intervals against each other.

Reviewed by: scallanan

Differential Revision: http://reviews.llvm.org/D4286

llvm-svn: 211726
---
 lldb/include/lldb/Expression/IRMemoryMap.h | 10 +++++--
 lldb/source/Expression/IRMemoryMap.cpp     | 47 ++++++++++++++++++++----------
 2 files changed, 39 insertions(+), 18 deletions(-)

diff --git a/lldb/include/lldb/Expression/IRMemoryMap.h b/lldb/include/lldb/Expression/IRMemoryMap.h
index 750ff68..4faa522 100644
--- a/lldb/include/lldb/Expression/IRMemoryMap.h
+++ b/lldb/include/lldb/Expression/IRMemoryMap.h
@@ -27,7 +27,8 @@ namespace lldb_private
 /// This class encapsulates a group of memory objects that must be readable
 /// or writable from the host process regardless of whether the process
 /// exists.  This allows the IR interpreter as well as JITted code to access
-/// the same memory.
+/// the same memory.  All allocations made by this class are represented as
+/// disjoint intervals.
 ///
 /// Point queries against this group of memory objects can be made by the
 /// address in the tar at which they reside.  If the inferior does not
@@ -118,7 +119,12 @@ private:
     lldb::addr_t FindSpace (size_t size);
     bool ContainsHostOnlyAllocations ();
     AllocationMap::iterator FindAllocation (lldb::addr_t addr, size_t size);
-    bool IntersectsAllocation (lldb::addr_t addr, size_t size);
+
+    // Returns true if the given allocation intersects any allocation in the memory map.
+    bool IntersectsAllocation (lldb::addr_t addr, size_t size) const;
+
+    // Returns true if the two given allocations intersect each other.
+    static bool AllocationsIntersect (lldb::addr_t addr1, size_t size1, lldb::addr_t addr2, size_t size2);
 };
     
 }
diff --git a/lldb/source/Expression/IRMemoryMap.cpp b/lldb/source/Expression/IRMemoryMap.cpp
index 7bc2ed0..d4f7b70 100644
--- a/lldb/source/Expression/IRMemoryMap.cpp
+++ b/lldb/source/Expression/IRMemoryMap.cpp
@@ -125,33 +125,48 @@ IRMemoryMap::FindAllocation (lldb::addr_t addr, size_t size)
 }
 
 bool
-IRMemoryMap::IntersectsAllocation (lldb::addr_t addr, size_t size)
+IRMemoryMap::IntersectsAllocation (lldb::addr_t addr, size_t size) const
 {
     if (addr == LLDB_INVALID_ADDRESS)
         return false;
     
-    AllocationMap::iterator iter = m_allocations.lower_bound (addr);
+    AllocationMap::const_iterator iter = m_allocations.lower_bound (addr);
     
-    if (iter == m_allocations.end() ||
-        iter->first > addr)
-    {
-        if (iter == m_allocations.begin())
-            return false;
-        
-        iter--;
+    // Since we only know that the returned interval begins at a location greater than or
+    // equal to where the given interval begins, it's possible that the given interval
+    // intersects either the returned interval or the previous interval.  Thus, we need to
+    // check both. Note that we only need to check these two intervals.  Since all intervals
+    // are disjoint it is not possible that an adjacent interval does not intersect, but a
+    // non-adjacent interval does intersect.
+    if (iter != m_allocations.end()) {
+        if (IntersectsAllocation(addr, size, iter->second.m_process_start, iter->second.m_size))
+            return true;
     }
-    
-    while (iter != m_allocations.end() && iter->second.m_process_alloc < addr + size)
-    {
-        if (iter->second.m_process_start + iter->second.m_size > addr)
+
+    if (iter != m_allocations.begin()) {
+        --iter;
+        if (IntersectsAllocation(addr, size, iter->second.m_process_start, iter->second.m_size))
             return true;
-        
-        ++iter;
     }
-    
+
     return false;
 }
 
+bool
+IRMemoryMap::AllocationsIntersect(lldb::addr_t addr1, size_t size1, lldb::addr_t addr2, size_t size2) {
+  // Given two half open intervals [A, B) and [X, Y), the only 6 permutations that satisfy
+  // A<B and X<Y are the following:
+  // A B X Y
+  // A X B Y  (intersects)
+  // A X Y B  (intersects)
+  // X A B Y  (intersects)
+  // X A Y B  (intersects)
+  // X Y A B
+  // The first is B <= X, and the last is Y <= A.
+  // So the condition is !(B <= X || Y <= A)), or (X < B && A < Y)
+  return (addr2 < (addr1 + size1)) && (addr1 < (addr2 + size2));
+}
+
 lldb::ByteOrder
 IRMemoryMap::GetByteOrder()
 {
-- 
2.7.4