Made IRMemoryMap::FindSpace a little cleverer,

and made attempts to allocate memory in the process
fall back to FindSpace and just allocate memory on
the host (but with real-looking pointers, hence
FindSpace) if the process doesn't allow allocation.
This allows expressions to run on processes that don't
support allocation, like core files.

This introduces an extremely rare potential problem:
If all of the following are true:

- The Process doesn't support allocation;

- the user writes an expression that refers to an
  address that does not yet map to anything, or is
  dynamically generated (e.g., the result of calling
  a function); and

- the randomly-selected address for the static data
  for that specific expression runs into the
  address the user was expecting to work with;

then dereferencing the pointer later results
in the user seeing something unexpected.  This is
unlikely but possible; as a future piece of work,
we should have processes be able to hint to the
expression parser where it can allocate temporary data
of this kind.

llvm-svn: 179827

1 files changed, 82 insertions, 40 deletions

diff --git a/lldb/source/Expression/IRMemoryMap.cpp b/lldb/source/Expression/IRMemoryMap.cpp
index 28a2fc1e0de..9a6f4479a54 100644
--- a/lldb/source/Expression/IRMemoryMap.cpp
+++ b/lldb/source/Expression/IRMemoryMap.cpp
@@ -50,36 +50,52 @@ IRMemoryMap::~IRMemoryMap ()
 lldb::addr_t
 IRMemoryMap::FindSpace (size_t size)
 {
-    // Yup, this is just plain O(n) insertion.  We'll use a range tree if we
-    // start caring.
-    
-    lldb::addr_t remote_address = 0x1000; // skip first page of memory
-    
-    for (AllocationMap::value_type &allocation : m_allocations)
-    {
-        if (remote_address < allocation.second.m_process_start &&
-            remote_address + size <= allocation.second.m_process_start)
-            return remote_address;
+    lldb::TargetSP target_sp = m_target_wp.lock();
+    lldb::ProcessSP process_sp = m_process_wp.lock();
         
-        remote_address = allocation.second.m_process_start + allocation.second.m_size;
-    }
+    lldb::addr_t ret = LLDB_INVALID_ADDRESS;
     
-    if (remote_address + size < remote_address)
-        return LLDB_INVALID_ADDRESS; // massively unlikely
-    
-    return remote_address;
-}
-
-bool
-IRMemoryMap::ContainsHostOnlyAllocations ()
-{
-    for (AllocationMap::value_type &allocation : m_allocations)
+    for (int iterations = 0; iterations < 16; ++iterations)
     {
-        if (allocation.second.m_policy == eAllocationPolicyHostOnly)
-            return true;
+        lldb::addr_t candidate;
+        
+        switch (target_sp->GetArchitecture().GetAddressByteSize())
+        {
+        case 4:
+            {
+                uint32_t random_data = random();
+                candidate = random_data;
+                candidate &= ~0xfffull;
+                break;
+            }
+        case 8:
+            {
+                uint32_t random_low = random();
+                uint32_t random_high = random();
+                candidate = random_high;
+                candidate <<= 32ull;
+                candidate |= random_low;
+                candidate &= ~0xfffull;
+                break;
+            }
+        }
+        
+        if (IntersectsAllocation(candidate, size))
+            continue;
+        
+        char buf[1];
+        
+        Error err;
+        
+        if (process_sp &&
+            (process_sp->ReadMemory(candidate, buf, 1, err) == 1 ||
+             process_sp->ReadMemory(candidate + size, buf, 1, err) == 1))
+            continue;
+        
+        ret = candidate;
     }
     
-    return false;
+    return ret;
 }
 
 IRMemoryMap::AllocationMap::iterator
@@ -104,6 +120,34 @@ IRMemoryMap::FindAllocation (lldb::addr_t addr, size_t size)
     return m_allocations.end();
 }
 
+bool
+IRMemoryMap::IntersectsAllocation (lldb::addr_t addr, size_t size)
+{
+    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--;
+    }
+    
+    while (iter != m_allocations.end() && iter->second.m_process_alloc < addr + size)
+    {
+        if (iter->second.m_process_start + iter->second.m_size > addr)
+            return true;
+        
+        ++iter;
+    }
+    
+    return false;
+}
+
 lldb::ByteOrder
 IRMemoryMap::GetByteOrder()
 {
@@ -179,14 +223,8 @@ IRMemoryMap::Malloc (size_t size, uint8_t alignment, uint32_t permissions, Alloc
         }
         break;
     case eAllocationPolicyMirror:
-        if (ContainsHostOnlyAllocations())
-        {
-            error.SetErrorToGenericError();
-            error.SetErrorString("Couldn't malloc: host-only allocations are polluting the address space");
-            return LLDB_INVALID_ADDRESS;
-        }
         process_sp = m_process_wp.lock();
-        if (process_sp)
+        if (process_sp && process_sp->CanJIT())
         {
             allocation_address = process_sp->AllocateMemory(allocation_size, permissions, error);
             if (!error.Success())
@@ -194,6 +232,7 @@ IRMemoryMap::Malloc (size_t size, uint8_t alignment, uint32_t permissions, Alloc
         }
         else
         {
+            policy = eAllocationPolicyHostOnly;
             allocation_address = FindSpace(allocation_size);
             if (allocation_address == LLDB_INVALID_ADDRESS)
             {
@@ -204,18 +243,21 @@ IRMemoryMap::Malloc (size_t size, uint8_t alignment, uint32_t permissions, Alloc
         }
         break;
     case eAllocationPolicyProcessOnly:
-        if (ContainsHostOnlyAllocations())
-        {
-            error.SetErrorToGenericError();
-            error.SetErrorString("Couldn't malloc: host-only allocations are polluting the address space");
-            return LLDB_INVALID_ADDRESS;
-        }
         process_sp = m_process_wp.lock();
         if (process_sp)
         {
-            allocation_address = process_sp->AllocateMemory(allocation_size, permissions, error);
-            if (!error.Success())
+            if (process_sp->CanJIT())
+            {
+                allocation_address = process_sp->AllocateMemory(allocation_size, permissions, error);
+                if (!error.Success())
+                    return LLDB_INVALID_ADDRESS;
+            }
+            else
+            {
+                error.SetErrorToGenericError();
+                error.SetErrorString("Couldn't malloc: process doesn't support allocating memory");
                 return LLDB_INVALID_ADDRESS;
+            }
         }
         else
         {