Have MemoryCache cache addresses that were unreadable, so duplicate read attempts can be suppressed

[jasonmolenda]

Summary

This patch is to address an issue hit by one of our heavy SB API scripting developers; they have some code iterating over a large number of objects in SBValue's and one of the elements of the object has a type of void*; the Itanium ABI is trying to sniff the memory there to see if it might have a dynamic type. In this case, the elements often have the value 0, so lldb is trying to read memory at address 0, which fails, and the number of reads is quite large. Each failing memory read takes long enough in a JTAG like environment that this is a big perf issue.

We have a MemoryCache subsystem that saves blocks of inferior memory when we do a read, so repeated reads of the same address, or reads near the address that were cached, are saved at a single point in time. These memory cache buffers are flushed when execution is resumed.

This patch adds a new list of addresses we've tried to read from at this execution stop, which returned an error, and will not try to read from those addresses again. If lldb allocates memory in the inferior, or if we resume execution, this list of addresses is flushed.

I settled on using an llvm::SmallSet container for these addr_t's, but I'd appreciate if people have a different suggestion for the most appropriate container. I expect this list to be relatively small -- it is not common that lldb tries to read from addresses that are unreadable -- and my primary optimization concern is quick lookup because I will consult this list before I read from any address in memory.

When I was outlining my idea for this, Jim pointed out that MemoryCache has a InvalidRanges m_invalid_ranges ivar already, and could I reuse this. This is called by the DynamicLoader to mark a region of memory as never accessible (e.g. the lower 4GB on a 64-bit Darwin process), and is not flushed on execution resume / memory allocation. It is expressed in terms of memory ranges, when I don't know the range of memory that is inaccessible beyond an address. I could assume the range extends to the end of a page boundary, if I knew the page boundary size, but that still doesn't address the fact that m_invalid_ranges is intended to track inaccessible memory that is invariant during the process lifetime.

[DavidSpickett]

Seems like a valid thing to do.

Is it a problem that maybe you read from address N to N+100 and the problem address is actually at N+50, not N? I think you might be handling that already but I didn't read all the logic just your additions. Maybe not an issue because a lot of this is done in pages of memory, unlikely to be a <10 byte gap where something fails (and you can manually flush the cache if that somehow happens).

In this case, the elements often have the value 0, so lldb is trying to read memory at address 0, which fails, and the number of reads is quite large.

In this environment I guess they don't have a dynamic loader to have set the ranges? So in Mac OS userspace, this wouldn't be a problem because the zero page would be marked as always invalid, but they don't have that luxury.

And there's nothing stopping a bare metal program from mapping memory at 0, so one can't just say 0 means invalid 100% of the time.

doesn't address the fact that m_invalid_ranges is intended to track inaccessible memory that is invariant during the process lifetime.

Please add this as a comment, will be good to know if/when there are two lists involved.

lldb/source/Target/Memory.cpp

157

Should this be more specific like "failed because we know this is unreadable" or "has previously failed to read"?

[jingham]

LGTM

I didn't see a more appropriate datatype than SmallSet in the llvm collection.

I wondered about the same thing Dave asked - should the errors mention that this failed because we checked a negative cache - but I think that would be more confusing than helpful to lldb users. If we wanted to track these decisions it would be more appropriate to log them, but I'm not sure even that is necessary.

[DavidSpickett]

If we wanted to track these decisions it would be more appropriate to log them, but I'm not sure even that is necessary.

Yeah this is a better idea, if we do it at all.

Let me rephrase the question. If I had a memory read failing and I suspected that the cache was marking it as unreadable how would I confirm that? If there's a way to do that when it's really needed, then we're good.

Perhaps log only when a new address is added to the unreadable list? Then with the memory log plus the packet log you could figure out the issue, even if you didn't know that the cache had this unreadable address feature before you started investigating.

[jasonmolenda]

Jim & David, thanks so much for the comments. The most important question of correctness that David asks is whether we might try to read 32k from an address and mark that address as inaccessible because a page 24k into the memory read failed (for instance). I tried to be conservative and only mark an address as inaccessible when we were able to read 0 bytes (ReadMemory returns partial reads).

I think adding a little hint in the error message, "(cached)" would make it clearer to an lldb maintainer what happened, and not distract the user with too much.

In D134906#3830290, @DavidSpickett wrote:

If we wanted to track these decisions it would be more appropriate to log them, but I'm not sure even that is necessary.

Yeah this is a better idea, if we do it at all.

Let me rephrase the question. If I had a memory read failing and I suspected that the cache was marking it as unreadable how would I confirm that? If there's a way to do that when it's really needed, then we're good.

When I was testing/debugging this, I did it by turning the packet log on :)

Perhaps log only when a new address is added to the unreadable list? Then with the memory log plus the packet log you could figure out the issue, even if you didn't know that the cache had this unreadable address feature before you started investigating.

Yes, I can add a log message to Process when I add an address, good idea.

Let me go through the patch again carefully to make sure I'm correctly handling partially-successful reads (not putting anything in the inaccessible memory cache) and tweak that error message a tad & add a bit of logging.

[labath]

I don't know about debugserver, but both lldb-server and gdbserver currently return an error when the memory is partially accessible, even though the protocol explicitly allows the possibility of truncated reads. It is somewhat hard to reproduce, because the caching mechanism in lldb aligns memory reads, and the cache "line" size is usually smaller than the page size -- which is probably why this behavior hasn't bothered anyone so far. Nonetheless, I would say that this behavior (not returning partial contents) is a (QoI) bug, but the fact that two stubs have it makes me wonder how many other stubs do the same as well..

[jasonmolenda]

In D134906#3832642, @labath wrote:

I don't know about debugserver, but both lldb-server and gdbserver currently return an error when the memory is partially accessible, even though the protocol explicitly allows the possibility of truncated reads. It is somewhat hard to reproduce, because the caching mechanism in lldb aligns memory reads, and the cache "line" size is usually smaller than the page size -- which is probably why this behavior hasn't bothered anyone so far. Nonetheless, I would say that this behavior (not returning partial contents) is a (QoI) bug, but the fact that two stubs have it makes me wonder how many other stubs do the same as well..

Hi Pavel, thanks for pointing this out. I did a quick check with debugserver on darwin, using memory region to find the end of an accessible region in memory, and starting a read request a little earlier, in readable memory:

(lldb) sett set target.process.disable-memory-cache true

(lldb) mem region 0x0000000101800000
 <  31> send packet: $qMemoryRegionInfo:101800000#ce
 <  34> read packet: $start:101800000;size:6a600000;#00
[0x0000000101800000-0x000000016be00000) ---

(lldb) mem region 0x0000000101800000-4
 <  31> send packet: $qMemoryRegionInfo:1017ffffc#d8
 < 122> read packet: $start:101000000;size:800000;permissions:rw;dirty-pages:101000000,101008000,10100c000,1017fc000;type:heap,malloc-small;#00
[0x0000000101000000-0x0000000101800000) rw-

(lldb) x/8wx 0x0000000101800000-4

 <  17> send packet: $x1017ffffc,20#ca
 <   8> read packet: $00000000#00

 <  17> send packet: $x101800000,1c#f2
 <   7> read packet: $E80#00

0x1017ffffc: 0x00000000 0x00000000 0x00000000 0x00000000
0x10180000c: 0x00000000 0x00000000 0x00000000 0x00000000
warning: Not all bytes (4/32) were able to be read from 0x1017ffffc.
(lldb)

We ask for 32 bytes starting at 0x1017ffffc, get back 4 bytes. Then we try to read the remaining 28 bytes starting at 0x101800000, and get an error. So this is different behavior from other stubs where you might simply get an error for the request to read more bytes than are readable. This does complicate the approach I'm doing -- because I'll never know which address was inaccessible beyond "something within this address range". I don't think I can do anything here if that's the case.

[jasonmolenda]

In D134906#3835260, @jasonmolenda wrote:

We ask for 32 bytes starting at 0x1017ffffc, get back 4 bytes. Then we try to read the remaining 28 bytes starting at 0x101800000, and get an error. So this is different behavior from other stubs where you might simply get an error for the request to read more bytes than are readable. This does complicate the approach I'm doing -- because I'll never know which address was inaccessible beyond "something within this address range". I don't think I can do anything here if that's the case.

to be clear, I think I'll need to abandon this.

[labath]

In D134906#3835260, @jasonmolenda wrote:

In D134906#3832642, @labath wrote:

I don't know about debugserver, but both lldb-server and gdbserver currently return an error when the memory is partially accessible, even though the protocol explicitly allows the possibility of truncated reads. It is somewhat hard to reproduce, because the caching mechanism in lldb aligns memory reads, and the cache "line" size is usually smaller than the page size -- which is probably why this behavior hasn't bothered anyone so far. Nonetheless, I would say that this behavior (not returning partial contents) is a (QoI) bug, but the fact that two stubs have it makes me wonder how many other stubs do the same as well..

Hi Pavel, thanks for pointing this out. I did a quick check with debugserver on darwin, using memory region to find the end of an accessible region in memory, and starting a read request a little earlier, in readable memory:

(lldb) sett set target.process.disable-memory-cache true

(lldb) mem region 0x0000000101800000
 <  31> send packet: $qMemoryRegionInfo:101800000#ce
 <  34> read packet: $start:101800000;size:6a600000;#00
[0x0000000101800000-0x000000016be00000) ---

(lldb) mem region 0x0000000101800000-4
 <  31> send packet: $qMemoryRegionInfo:1017ffffc#d8
 < 122> read packet: $start:101000000;size:800000;permissions:rw;dirty-pages:101000000,101008000,10100c000,1017fc000;type:heap,malloc-small;#00
[0x0000000101000000-0x0000000101800000) rw-

(lldb) x/8wx 0x0000000101800000-4

 <  17> send packet: $x1017ffffc,20#ca
 <   8> read packet: $00000000#00

 <  17> send packet: $x101800000,1c#f2
 <   7> read packet: $E80#00

0x1017ffffc: 0x00000000 0x00000000 0x00000000 0x00000000
0x10180000c: 0x00000000 0x00000000 0x00000000 0x00000000
warning: Not all bytes (4/32) were able to be read from 0x1017ffffc.
(lldb)

We ask for 32 bytes starting at 0x1017ffffc, get back 4 bytes. Then we try to read the remaining 28 bytes starting at 0x101800000, and get an error. So this is different behavior from other stubs where you might simply get an error for the request to read more bytes than are readable.

Yes, that's pretty much what I did, except that I was not able to read any data with the caching turned off.

In D134906#3835291, @jasonmolenda wrote:

to be clear, I think I'll need to abandon this.

I don't think this is necessarily a lost cause. I mean, the debugserver behavior (truncated reads) is definitely better here, and the caching of negative acesses makes sense. And, as the example above shows, the current behavior with the non-truncating stubs is already kind of broken, because you cannot read the areas near the end of mapped space without doing some kind of a bisection on the size of the read (we could implement the bisection in lldb, but... ewww).

The safest way to pursue this would be to have the stub indicate (maybe via qSupported) its intention to return truncated reads, and then key the behavior off of that. However, if that's not possible (it seems you have some hardware stub here), I could imagine just enabling this behavior by default. We can definitely change the lldb-server behavior, and for the rest, we can tell them to fix their stubs.

That is, if they even notice this. The memory read alignment hides this problem fairly well. To demonstrate this, we've had to turn the caching off -- but that would also turn off the negative cache, and avoid this problem. So, if someone can't fix their stub, we can always tell them to turn the cache off as a workaround.

lldb/include/lldb/Target/Memory.h

 #define LLDB_TARGET_MEMORY_H
 
 #include "lldb/Utility/RangeMap.h"
 #include "lldb/lldb-private.h"
 #include <map>
 #include <mutex>
 #include <vector>
 
+#include "llvm/ADT/SmallSet.h"
+
 namespace lldb_private {
 // A class to track memory that was read from a live process between
 // runs.
 class MemoryCache {
 public:
   // Constructors and Destructors
   MemoryCache(Process &process);
 
public:
   bool RemoveInvalidRange(lldb::addr_t base_addr, lldb::addr_t byte_size);
 
   // Allow external sources to populate data into the L1 memory cache
   void AddL1CacheData(lldb::addr_t addr, const void *src, size_t src_len);
 
   void AddL1CacheData(lldb::addr_t addr,
                       const lldb::DataBufferSP &data_buffer_sp);
 
+  /// Remember that a memory address cannot be read from.
+  void AddUnreadableAddress(lldb::addr_t address);
+
+  /// Test if a memory address was already recorded as unreadable.
+  bool IsAddressUnreadable(lldb::addr_t address);
+
+  /// Clear unreadable address cache.
+  void FlushUnreadableAddresses();
+
 protected:
   typedef std::map<lldb::addr_t, lldb::DataBufferSP> BlockMap;
   typedef RangeVector<lldb::addr_t, lldb::addr_t, 4> InvalidRanges;
   typedef Range<lldb::addr_t, lldb::addr_t> AddrRange;
   // Classes that inherit from MemoryCache can see and modify these
   std::recursive_mutex m_mutex;
   BlockMap m_L1_cache; // A first level memory cache whose chunk sizes vary that
                        // will be used only if the memory read fits entirely in
                        // a chunk
   BlockMap m_L2_cache; // A memory cache of fixed size chinks
                        // (m_L2_cache_line_byte_size bytes in size each)
   InvalidRanges m_invalid_ranges;
   Process &m_process;
   uint32_t m_L2_cache_line_byte_size;
+  llvm::SmallSet<lldb::addr_t, 8> m_unreadable_addresses;
 
 private:
   MemoryCache(const MemoryCache &) = delete;
   const MemoryCache &operator=(const MemoryCache &) = delete;
 };
 
     
 

lldb/source/Target/Memory.cpp

 
 using namespace lldb;
 using namespace lldb_private;
 
 // MemoryCache constructor
 MemoryCache::MemoryCache(Process &process)
     : m_mutex(), m_L1_cache(), m_L2_cache(), m_invalid_ranges(),
       m_process(process),
-      m_L2_cache_line_byte_size(process.GetMemoryCacheLineSize()) {}
+      m_L2_cache_line_byte_size(process.GetMemoryCacheLineSize()),
+      m_unreadable_addresses() {}
 
 // Destructor
 MemoryCache::~MemoryCache() = default;
 
 void MemoryCache::Clear(bool clear_invalid_ranges) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   m_L1_cache.clear();
   m_L2_cache.clear();
   if (clear_invalid_ranges)
     m_invalid_ranges.Clear();
   m_L2_cache_line_byte_size = m_process.GetMemoryCacheLineSize();
+  FlushUnreadableAddresses();
 }
 
 void MemoryCache::AddL1CacheData(lldb::addr_t addr, const void *src,
                                  size_t src_len) {
   AddL1CacheData(
       addr, DataBufferSP(new DataBufferHeap(DataBufferHeap(src, src_len))));
 }
 
 void MemoryCache::AddL1CacheData(lldb::addr_t addr,
                                  const DataBufferSP &data_buffer_sp) {
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
   m_L1_cache[addr] = data_buffer_sp;
 }
 
 void MemoryCache::Flush(addr_t addr, size_t size) {
+  FlushUnreadableAddresses();
+
   if (size == 0)
     return;
 
   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 
   // Erase any blocks from the L1 cache that intersect with the flush range
   if (!m_L1_cache.empty()) {
     AddrRange flush_range(addr, size);
if (!m_L1_cache.empty()) {
     AddrRange chunk_range(pos->first, pos->second->GetByteSize());
     if (chunk_range.Contains(read_range)) {
       memcpy(dst, pos->second->GetBytes() + (addr - chunk_range.GetRangeBase()),
              dst_len);
       return dst_len;
     }
   }
 
+  if (IsAddressUnreadable(addr)) {
+    error.SetErrorStringWithFormat("memory read failed for 0x%" PRIx64, addr);
+    return 0;
+  }
+
   // If this memory read request is larger than the cache line size, then we
   // (1) try to read as much of it at once as possible, and (2) don't add the
   // data to the memory cache.  We don't want to split a big read up into more
   // separate reads than necessary, and with a large memory read request, it is
   // unlikely that the caller function will ask for the next
   // 4 bytes after the large memory read - so there's little benefit to saving
   // it in the cache.
   if (dst && dst_len > m_L2_cache_line_byte_size) {
     size_t bytes_read =
         m_process.ReadMemoryFromInferior(addr, dst, dst_len, error);
     // Add this non block sized range to the L1 cache if we actually read
     // anything
     if (bytes_read > 0)
       AddL1CacheData(addr, dst, bytes_read);
+    else
+      AddUnreadableAddress(addr);
     return bytes_read;
   }
 
   if (dst && bytes_left > 0) {
     const uint32_t cache_line_byte_size = m_L2_cache_line_byte_size;
     uint8_t *dst_buf = (uint8_t *)dst;
     addr_t curr_addr = addr - (addr % cache_line_byte_size);
     addr_t cache_offset = addr - curr_addr;
while (bytes_left > 0) {
               return dst_len - bytes_left;
           }
         }
       }
 
       // We need to read from the process
 
       if (bytes_left > 0) {
+        if (IsAddressUnreadable(curr_addr)) {
+          error.SetErrorStringWithFormat("memory read failed for 0x%" PRIx64,
+                                         addr);
+          return dst_len - bytes_left;
+        }
         assert((curr_addr % cache_line_byte_size) == 0);
         std::unique_ptr<DataBufferHeap> data_buffer_heap_up(
             new DataBufferHeap(cache_line_byte_size, 0));
         size_t process_bytes_read = m_process.ReadMemoryFromInferior(
             curr_addr, data_buffer_heap_up->GetBytes(),
             data_buffer_heap_up->GetByteSize(), error);
-        if (process_bytes_read == 0)
+        if (process_bytes_read == 0) {
+          AddUnreadableAddress(curr_addr);
           return dst_len - bytes_left;
+        }
 
         if (process_bytes_read != cache_line_byte_size) {
           if (process_bytes_read < data_buffer_heap_up->GetByteSize()) {
             dst_len -= data_buffer_heap_up->GetByteSize() - process_bytes_read;
             bytes_left = process_bytes_read;
           }
           data_buffer_heap_up->SetByteSize(process_bytes_read);
         }
         m_L2_cache[curr_addr] = DataBufferSP(data_buffer_heap_up.release());
         // We have read data and put it into the cache, continue through the
         // loop again to get the data out of the cache...
       }
     }
   }
 
   return dst_len - bytes_left;
 }
 
+void MemoryCache::AddUnreadableAddress(addr_t address) {
+  m_unreadable_addresses.insert(address);
+}
+
+bool MemoryCache::IsAddressUnreadable(addr_t address) {
+  return m_unreadable_addresses.count(address) > 0;
+}
+
+void MemoryCache::FlushUnreadableAddresses() { m_unreadable_addresses.clear(); }
+
 AllocatedBlock::AllocatedBlock(lldb::addr_t addr, uint32_t byte_size,
                                uint32_t permissions, uint32_t chunk_size)
     : m_range(addr, byte_size), m_permissions(permissions),
       m_chunk_size(chunk_size)
 {
   // The entire address range is free to start with.
   m_free_blocks.Append(m_range);
   assert(byte_size > chunk_size);

lldb/source/Target/Process.cpp

 
 #define USE_ALLOCATE_MEMORY_CACHE 1
 addr_t Process::AllocateMemory(size_t size, uint32_t permissions,
                                Status &error) {
   if (GetPrivateState() != eStateStopped) {
     error.SetErrorToGenericError();
     return LLDB_INVALID_ADDRESS;
   }
+  if (!GetDisableMemoryCache()) {
+    // Flush unreadable addresses list; allocating a
+    // block of memory will change what addresse can be accessed.
+    m_memory_cache.FlushUnreadableAddresses();
+  }
 
 #if defined(USE_ALLOCATE_MEMORY_CACHE)
   return m_allocated_memory_cache.AllocateMemory(size, permissions, error);
 #else
   addr_t allocated_addr = DoAllocateMemory(size, permissions, error);
   Log *log = GetLog(LLDBLog::Process);
   LLDB_LOGF(log,
             "Process::AllocateMemory(size=%" PRIu64

lldb/test/API/functionalities/gdb_remote_client/TestMemoryReadFailCache.py

+import lldb
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test.decorators import *
+from lldbsuite.test.gdbclientutils import *
+from lldbsuite.test.lldbgdbclient import GDBRemoteTestBase
+
+
+class TestMemoryReadFailCache(GDBRemoteTestBase):
+
+    @skipIfXmlSupportMissing
+    def test(self):
+        class MyResponder(MockGDBServerResponder):
+            first_read = True
+
+            def qHostInfo (self):
+                return "cputype:16777228;cpusubtype:2;addressing_bits:47;ostype:macosx;vendor:apple;os_version:12.6.0;endian:little;ptrsize:8;"
+
+            def readMemory(self, addr, length):
+                if self.first_read:
+                  self.first_read = False
+                  return "E05"
+                return "AA" * length
+
+        self.server.responder = MyResponder()
+        target = self.dbg.CreateTarget('')
+        if self.TraceOn():
+          self.runCmd("log enable gdb-remote packets")
+          self.addTearDownHook(
+                lambda: self.runCmd("log disable gdb-remote packets"))
+        process = self.connect(target)
+
+        err = lldb.SBError()
+        uint = process.ReadUnsignedFromMemory(0x1000, 4, err)
+        self.assertTrue (err.Fail(), 
+              "lldb should fail to read memory at 0x100 the first time, "
+              "after checking with stub")
+
+        # Now the remote stub will return a non-zero number if 
+        # we ask again, unlike a real stub.
+        # Confirm that reading from that address still fails - 
+        # that we cached the unreadable address
+        uint = process.ReadUnsignedFromMemory(0x1000, 4, err)
+        self.assertTrue (err.Fail(), 
+              "lldb should fail to read memory at 0x100 the second time, "
+              "because we did not read from the remote stub.")
+
+        # Allocate memory in the inferior, which will flush
+        # the unreadable address cache.
+        process.AllocateMemory(0x100, 3, err)
+
+        uint = process.ReadUnsignedFromMemory(0x1000, 4, err)
+        self.assertTrue (err.Success(), 
+              "lldb should succeed to read memory at 0x100 the third time, "
+              "because we flushed the failed address cache, and the stub is "
+              "now providing data there.")