Fix a bug in IRMemoryMap which generated bogus allocations

[zturner]

Summary

The IRMemoryMap represents a set of disjoint allocations, stored as an interval map. A bug in its allocation algorithm would cause this disjoint property to be violated, resulting in overlapping intervals in the map.

Consider the following scenario:

Allocation 1: 8 bytes, address 8192 is chosen by the allocator
Allocation 2: 524288, address 0 is probed

Without this patch, the IntersectsAllocation() method would behave as follows:

1. lower_bound(0) returns an iterator referring to allocation 1
2. 0 is compared against 8192, and since 0 < 8192, it says there is no intersection.

With the patch, it does proper interval tests.

[zturner]

Closed by commit rL211726 (authored by @zturner).

include/lldb/Expression/IRMemoryMap.h

 //----------------------------------------------------------------------
 /// @class IRMemoryMap IRMemoryMap.h "lldb/Expression/IRMemoryMap.h"
 /// @brief Encapsulates memory that may exist in the process but must
 ///     also be available in the host process.
 ///
 /// 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
 /// exist, allocations still get made-up addresses.  If an inferior appears
 /// at some point, then those addresses need to be re-mapped.
 //----------------------------------------------------------------------
 class IRMemoryMap
 {
private:
     lldb::ProcessWP                             m_process_wp;
     lldb::TargetWP                              m_target_wp;
     typedef std::map<lldb::addr_t, Allocation>  AllocationMap;
     AllocationMap                               m_allocations;
         
     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.
+    bool IntersectsAllocation (lldb::addr_t addr1, size_t size1, lldb::addr_t addr2, size_t size2) const;
 };
     
 }
 
 #endif

source/Expression/IRMemoryMap.cpp

IRMemoryMap::FindAllocation (lldb::addr_t addr, size_t size)
     
     if (iter->first <= addr && iter->first + iter->second.m_size >= addr + size)
         return iter;
     
     return m_allocations.end();
 }
 
 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);
-    
-    if (iter == m_allocations.end() ||
-        iter->first > addr)
-    {
-        if (iter == m_allocations.begin())
-            return false;
-        
-        iter--;
+    AllocationMap::const_iterator iter = m_allocations.lower_bound (addr);
+    // 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::IntersectsAllocation(lldb::addr_t addr1, size_t size1, lldb::addr_t addr2, size_t size2) const {
+  // 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()
 {
     lldb::ProcessSP process_sp = m_process_wp.lock();
     
     if (process_sp)
         return process_sp->GetByteOrder();