Don't use a random probe / allocation scheme in the IRMemoryMap

[zturner]

Summary

The current strategy for host allocation is to choose a random address and attempt to allocate there, eventually failing if the allocation cannot be satisfied.

The C standard only guarantees that RAND_MAX >= 32767, so for platforms where this is true allocations will fail with very high probability. On such platforms, you can reproduce this trivially by running lldb, typing "expr (3)" and then hitting enter you see a failure. Failures generally happen with a frequency of about 1 failure every 5 evaluations.

I cannot come up with a good reason that the allocations need to look like "real" pointers, so this patch changes the allocation scheme to simply jump straight to the end and grab a free chunk of memory.

[tfiala]

Looking at this now.

[tfiala]

Added a couple questions. Going to try the patch as is in a moment here.

source/Expression/IRMemoryMap.cpp

76

This now shadows the size argument to the function. Maybe rename it to something like allocation_size.

I think you also want to check if size (the argument to the function) + ret would bust the address space (i.e. validate that the requested size can really fit within the address space if it comes where the method suggests).

Are we guaranteed that these allocations are contiguous? If they're not contiguous, and if we do not have enough space at the end of the allocations, then that opens up a reason to look for holes earlier in the address space.

[zturner]

source/Expression/IRMemoryMap.cpp

76

They should be contiguous. After all, this is an interval map where each item in the tree can be reduced to the pair (start, size), and by extension represents the interval [start, start+size). So by simply pulling the last entry off the map and rounding up to the required alignment, it should be guaranteed that the entry returns is at the next possible location that a value can be allocated at with the given alignment requirement.

[tfiala]

Does anything ever get removed from it? If so, you've got holes.

[zturner]

Yes, but I believe that the scope of this memory map is the execution of a single expression. So unless a single expression tries to allocate more than the entire address space across some number of allocations, it will always be fine.

[tfiala]

I don't see any new test failures with this. The (lldb) expr command seems to be working fine in a remote inferior process.

The only change I'd like to see if the renaming the shadowed variable to a different name.

I have an open question on the lifetime of an IRMemoryMap and whether we care about holes that develop, and whether we want new allocations to always come at the end of the range if this persists. However, if it is relatively short lived, this probably isn't a big deal.

[zturner]

Bump for the new week. Hopefully can get some traction this week.

[zturner]

Closed by commit rL212630 (authored by @zturner).

source/Expression/IRMemoryMap.cpp

 
 lldb::addr_t
 IRMemoryMap::FindSpace (size_t size)
 {
     lldb::TargetSP target_sp = m_target_wp.lock();
     lldb::ProcessSP process_sp = m_process_wp.lock();
         
     lldb::addr_t ret = LLDB_INVALID_ADDRESS;
+    if (size == 0)
+      return ret;
     
     if (process_sp && process_sp->CanJIT() && process_sp->IsAlive())
     {
         Error alloc_error;
         
         ret = process_sp->AllocateMemory(size, lldb::ePermissionsReadable | lldb::ePermissionsWritable, alloc_error);
         
         if (!alloc_error.Success())
             return LLDB_INVALID_ADDRESS;
         else
             return ret;
     }
     
-    for (int iterations = 0; iterations < 16; ++iterations)
-    {
-        lldb::addr_t candidate = LLDB_INVALID_ADDRESS;
-        
-        switch (target_sp->GetArchitecture().GetAddressByteSize())
-        {
-        case 4:
-            {
-                uint32_t random_data = rand();
-                candidate = random_data;
-                candidate &= ~0xfffull;
-                break;
-            }
-        case 8:
-            {
-                uint32_t random_low = rand();
-                uint32_t random_high = rand();
-                candidate = random_high;
-                candidate <<= 32ull;
-                candidate |= random_low;
-                candidate &= ~0xfffull;
-                break;
-            }
-        }
-        
-        if (IntersectsAllocation(candidate, size))
-            continue;
-                
-        ret = candidate;
-            
-        return ret;
+    // Don't allocate from the zero page.
+    ret = 0x1000;
+    if (!m_allocations.empty()) {
+      auto back = m_allocations.rbegin();
+      lldb::addr_t addr = back->first;
+      size_t size = back->second.m_size;
+      ret = llvm::RoundUpToAlignment(addr+size, 4096);
     }
     
     return ret;
 }
 
 IRMemoryMap::AllocationMap::iterator
 IRMemoryMap::FindAllocation (lldb::addr_t addr, size_t size)
 {