Fix incorrect L1 inferior memory cache flushing

[jarin]

Summary

As discussed in https://reviews.llvm.org/D74398, the L1 memory cache flushing is incorrect.

For instance, if the L1 cache contains two chunks (10, 10) and (30, 10) and we call MemoryCache::Flush(25, 10), the current code does not flush anything (because it just tries to flush the previous range (10, 10) and if that is not intersecting, it will bail out).

With this patch, if the previous chunk is not overlapping, we still try the next chunk, and only if that one is not overlapping, we bail out.

This also adds some unit tests for the cache (some of the tests fail with the current code). The unit tests required some changes for testability.

[clayborg]

I am not a pro at the gtest stuff, but this was very hard to follow and figure out what these tests are doing.

lldb/source/Target/Memory.cpp

23–24

Might be cleaner to add getting the cache line size from the MemoryFromInferiorReader as a second virtual function. This would avoid having to add the extra parameter here and to the clear method.

31

remove "cache_line_size" if we add a new virtual function to MemoryFromInferiorReader

37

Change to:

m_L2_cache_line_byte_size = m_reader.GetCacheLineSize();

if we add virtual function to MemoryFromInferiorReader

65–66

This can just be:

BlockMap::iterator previous = pos - 1;

67–68

name "chunk_range" like in the while loop below for consistency?

lldb/source/Target/Process.cpp

488

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

612

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

1456

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

5575

remove GetMemoryCacheLineSize() if we add virtual method to MemoryFromInferiorReader

lldb/unittests/Target/MemoryCacheTest.cpp

32–69

Just inline these to avoid having to have a declaration inside the class and then these functions outside of the class?

34–35

Comment maybe saying something like:

// Fill memory from [0x0 - 0x256) with byte values that match the index. We will use this memory in each test and each test will start with a fresh copy.

75–76

So we are reading 10 bytes, but only verifying the first byte in the 10 bytes we read? Why not verify all of them to be sure it worked with a for loop?

for (int i=0; i<result.size(); ++i) 
  ASSERT_EQ(i+10, result[i]);

or just do manual asserts:

ASSERT_EQ(10, result[0]);
ASSERT_EQ(11, result[1]);
ASSERT_EQ(12, result[2]);
...

81

So with "IncrementAndFlushRange(10, 1);" we are modifying one byte at index 10 by incrementing it right? It isn't clear from the:

ASSERT_EQ(m_memory[10], result[0]);

What we are verifying here. Wouldn't it be simpler to do:

ASSERT_EQ(11, result[0]);

And also verify that all of the other 9 bytes we read were unchanged?

ASSERT_EQ(11, result[1]);
ASSERT_EQ(12, result[2]);
...

92

seems weird to use AddRangeToL1Cache instead of just reading memory from these locations and it makes it less of a real world kind a test if we are mucking with the L1 cache directly. Makes the test a bit harder to follow. Maybe just reading from memory is easier to follow?:

// Read ranges from memory to populate the L1 cache
std::vector<uint8_t> result(10);
for (std::pair<lldb::addr_t, size_t> p : cached)
  ReadByBytes(p.first, p.second);

98–100

I can't tell what these three lines are doing. Very hard to follow

121

Same comment as last test about just reading from memory to populate the cache?

127–129

How do we know this won't try and read any memory? Are we assured that IncrementAndFlushRange won't touch any ranges we are trying to read here?

132–134

What is this checking?

[jarin]

Addressed some of the reviewer comments.

[jarin]

I rewrote parts of the test, hopefully making it a bit clearer. Please let me know if this made it better.

lldb/source/Target/Memory.cpp

23–24

That's what I thought originally, but it does not logically belong there - it does not feel like inferior's memory should control cache line sizes. I also like that the extra parameter makes it clear when we reflect changes in the cache line size setting in the cache itself rather than having to guess when the cache might do a callback. I had trouble understanding that part before.

Also, note that Process::GetMemoryCacheLineSize would have to be some ugly forwarder method because the existing GetMemoryCacheLineSize method is in ProcessProperties.

I am happy to put the method there if you insist, but I do not think it is a good idea. I would like to hear Pavel's opinion, too.

65–66

It cannot because map::iterator does not have operator-.

lldb/source/Target/Process.cpp

488

Is not calling virtual functions in constructors dangerous? Note that this is going to be called during the construction of process.

lldb/unittests/Target/MemoryCacheTest.cpp

75–76

Ouch, this test does not make sense because we do not put anything into L1. Fixed now.

Changed this to test just one byte.

81

What we really care about is that the value that Read returns is the same as the real one in memory, no? I actually do not really care how the IncrementAndFlushRange method modifies the memory as long as Read returns the correct value.

Nevertheless, I rewrote the code to read just one byte and to assert both the value and the invariant.

92

I am quite confused by this comment. What the test does is precisely what we do in the real world.

As far as I can see, reading from memory does not update L1 cache (only L2). The only way to update L1 is what is done here.

98–100

I agree, this was a mess. Changed to check in a loop.

121

See above.

127–129

Because this test is only called with range that won't flush L1. I merged the test with the test above, hopefully making it clearer.

132–134

This just checks that the read return the real contents of the memory. Changed that to a check in a loop.

[labath]

Thanks for tackling this. I believe this should be split into two patches: an NFC patch which makes it possible to unit test this code, and then a follow-up patch to fix the actual bug. The first patch can include the general testing infrastructure, and a some tests for the functionality which *is* working at the moment.

lldb/source/Target/Memory.cpp

31

I agree with @jarin that cache_line_size looks out of place on the MemoryFromInferiorReader inferface. Maybe this would look better if Clear is renamed to Reset ?

[jarin]

As labath@ suggested, I have teased apart the test and the testability refactoring into a separate patch. The patch lives at https://reviews.llvm.org/D77790, could you please take a look?

[jarin]

Abandoning the patch since we cannot reach agreement on how this should be tested.

lldb/include/lldb/Target/Memory.h

 
 #include "lldb/Utility/RangeMap.h"
 #include "lldb/lldb-private.h"
 #include <map>
 #include <mutex>
 #include <vector>
 
 namespace lldb_private {
+
+// Abstraction of a reader from inferior's memory.
+class MemoryFromInferiorReader {
+public:
+  /// Read of memory from a process.
+  ///
+  /// This function has the same semantics of ReadMemory except that it
+  /// bypasses caching.
+  ///
+  /// \param[in] vm_addr
+  ///     A virtual load address that indicates where to start reading
+  ///     memory from.
+  ///
+  /// \param[out] buf
+  ///     A byte buffer that is at least \a size bytes long that
+  ///     will receive the memory bytes.
+  ///
+  /// \param[in] size
+  ///     The number of bytes to read.
+  ///
+  /// \param[out] error
+  ///     An error that indicates the success or failure of this
+  ///     operation. If error indicates success (error.Success()),
+  ///     then the value returned can be trusted, otherwise zero
+  ///     will be returned.
+  ///
+  /// \return
+  ///     The number of bytes that were actually read into \a buf. If
+  ///     the returned number is greater than zero, yet less than \a
+  ///     size, then this function will get called again with \a
+  ///     vm_addr, \a buf, and \a size updated appropriately. Zero is
+  ///     returned in the case of an error.
+  virtual size_t ReadMemoryFromInferior(lldb::addr_t vm_addr, void *buf,
+                                        size_t size, Status &error) = 0;
+};
+
 // A class to track memory that was read from a live process between
 // runs.
 class MemoryCache {
 public:
   // Constructors and Destructors
-  MemoryCache(Process &process);
+  MemoryCache(MemoryFromInferiorReader &reader, uint64_t cache_line_size);
 
   ~MemoryCache();
 
-  void Clear(bool clear_invalid_ranges = false);
+  void Clear(uint64_t cache_line_size, bool clear_invalid_ranges = false);
 
   void Flush(lldb::addr_t addr, size_t size);
 
   size_t Read(lldb::addr_t addr, void *dst, size_t dst_len, Status &error);
 
   uint32_t GetMemoryCacheLineSize() const { return m_L2_cache_line_byte_size; }
 
   void AddInvalidRange(lldb::addr_t base_addr, lldb::addr_t byte_size);
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
+  BlockMap m_L2_cache; // A memory cache of fixed size chunks
                        // (m_L2_cache_line_byte_size bytes in size each)
   InvalidRanges m_invalid_ranges;
-  Process &m_process;
+  MemoryFromInferiorReader &m_reader;
   uint32_t m_L2_cache_line_byte_size;
 
 private:
   DISALLOW_COPY_AND_ASSIGN(MemoryCache);
 };
 
     
 

lldb/include/lldb/Target/Process.h

 
 /// \class Process Process.h "lldb/Target/Process.h"
 /// A plug-in interface definition class for debugging a process.
 class Process : public std::enable_shared_from_this<Process>,
                 public ProcessProperties,
                 public UserID,
                 public Broadcaster,
                 public ExecutionContextScope,
-                public PluginInterface {
+                public PluginInterface,
+                public MemoryFromInferiorReader {
   friend class FunctionCaller; // For WaitForStateChangeEventsPrivate
   friend class Debugger; // For PopProcessIOHandler and ProcessIOHandlerIsActive
   friend class DynamicLoader; // For LoadOperatingSystemPlugin
   friend class ProcessEventData;
   friend class StopInfo;
   friend class Target;
   friend class ThreadList;
 
public:
   ///
   /// \return
   ///     The number of bytes that were actually read into \a buf. If
   ///     the returned number is greater than zero, yet less than \a
   ///     size, then this function will get called again with \a
   ///     vm_addr, \a buf, and \a size updated appropriately. Zero is
   ///     returned in the case of an error.
   size_t ReadMemoryFromInferior(lldb::addr_t vm_addr, void *buf, size_t size,
-                                Status &error);
+                                Status &error) override;
 
   /// Read a NULL terminated string from memory
   ///
   /// This function will read a cache page at a time until a NULL string
   /// terminator is found. It will stop reading if an aligned sequence of NULL
   /// termination \a type_width bytes is not found before reading \a
   /// cstr_max_len bytes.  The results are always guaranteed to be NULL
   /// terminated, and that no more than (max_bytes - type_width) bytes will be

lldb/source/Target/Memory.cpp

 
 #include <cinttypes>
 #include <memory>
 
 using namespace lldb;
 using namespace lldb_private;
 
 // MemoryCache constructor
-MemoryCache::MemoryCache(Process &process)
+MemoryCache::MemoryCache(MemoryFromInferiorReader &reader,
+                         uint64_t cache_line_size)
     : m_mutex(), m_L1_cache(), m_L2_cache(), m_invalid_ranges(),
-      m_process(process),
-      m_L2_cache_line_byte_size(process.GetMemoryCacheLineSize()) {}
+      m_reader(reader), m_L2_cache_line_byte_size(cache_line_size) {}
 
 // Destructor
 MemoryCache::~MemoryCache() {}
 
-void MemoryCache::Clear(bool clear_invalid_ranges) {
+void MemoryCache::Clear(uint64_t cache_line_size, 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();
+  m_L2_cache_line_byte_size = cache_line_size;
 }
 
 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::Flush(addr_t addr, size_t size) {
 
   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);
     BlockMap::iterator pos = m_L1_cache.upper_bound(addr);
     if (pos != m_L1_cache.begin()) {
-      --pos;
+      // If we are not in the beginning, the previous range might be
+      // intersecting.
+      BlockMap::iterator previous = pos;
+      previous--;
+      AddrRange previous_range(previous->first,
+                               previous->second->GetByteSize());
+      if (previous_range.DoesIntersect(flush_range))
+        m_L1_cache.erase(previous);
     }
     while (pos != m_L1_cache.end()) {
       AddrRange chunk_range(pos->first, pos->second->GetByteSize());
       if (!chunk_range.DoesIntersect(flush_range))
         break;
       pos = m_L1_cache.erase(pos);
     }
   }
size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len,
   // (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);
+        m_reader.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);
     return bytes_read;
   }
 
   if (dst && bytes_left > 0) {
while (bytes_left > 0) {
             // an entire page. If this happens, we must cap off how much data
             // we are able to read...
             if (pos->second->GetByteSize() != cache_line_byte_size)
               return dst_len - bytes_left;
           }
         }
       }
 
-      // We need to read from the process
+      // We need to read from the inferior
 
       if (bytes_left > 0) {
         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(
+        size_t inferior_bytes_read = m_reader.ReadMemoryFromInferior(
             curr_addr, data_buffer_heap_up->GetBytes(),
             data_buffer_heap_up->GetByteSize(), error);
-        if (process_bytes_read == 0)
+        if (inferior_bytes_read == 0)
           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;
+        if (inferior_bytes_read != cache_line_byte_size) {
+          if (inferior_bytes_read < data_buffer_heap_up->GetByteSize()) {
+            dst_len -= data_buffer_heap_up->GetByteSize() - inferior_bytes_read;
+            bytes_left = inferior_bytes_read;
           }
-          data_buffer_heap_up->SetByteSize(process_bytes_read);
+          data_buffer_heap_up->SetByteSize(inferior_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...
       }
     }
   }
 

lldb/source/Target/Process.cpp

: ProcessProperties(this), UserID(LLDB_INVALID_PROCESS_ID),
       m_thread_list(this), m_extended_thread_list(this),
       m_extended_thread_stop_id(0), m_queue_list(this), m_queue_list_stop_id(0),
       m_notifications(), m_image_tokens(), m_listener_sp(listener_sp),
       m_breakpoint_site_list(), m_dynamic_checkers_up(),
       m_unix_signals_sp(unix_signals_sp), m_abi_sp(), m_process_input_reader(),
       m_stdio_communication("process.stdio"), m_stdio_communication_mutex(),
       m_stdin_forward(false), m_stdout_data(), m_stderr_data(),
       m_profile_data_comm_mutex(), m_profile_data(), m_iohandler_sync(0),
-      m_memory_cache(*this), m_allocated_memory_cache(*this),
-      m_should_detach(false), m_next_event_action_up(), m_public_run_lock(),
-      m_private_run_lock(), m_finalizing(false), m_finalize_called(false),
+      m_memory_cache(*this, GetMemoryCacheLineSize()),
+      m_allocated_memory_cache(*this), m_should_detach(false),
+      m_next_event_action_up(), m_public_run_lock(), m_private_run_lock(),
+      m_finalizing(false), m_finalize_called(false),
       m_clear_thread_plans_on_stop(false), m_force_next_event_delivery(false),
       m_last_broadcast_state(eStateInvalid), m_destroy_in_process(false),
       m_can_interpret_function_calls(false), m_warnings_issued(),
       m_run_thread_plan_lock(), m_can_jit(eCanJITDontKnow) {
   CheckInWithManager();
 
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_OBJECT));
   LLDB_LOGF(log, "%p Process::Process()", static_cast<void *>(this));
void Process::Finalize() {
   m_thread_list_real.Destroy();
   m_thread_list.Destroy();
   m_extended_thread_list.Destroy();
   m_queue_list.Clear();
   m_queue_list_stop_id = 0;
   std::vector<Notifications> empty_notifications;
   m_notifications.swap(empty_notifications);
   m_image_tokens.clear();
-  m_memory_cache.Clear();
+  m_memory_cache.Clear(GetMemoryCacheLineSize());
   m_allocated_memory_cache.Clear();
   {
     std::lock_guard<std::recursive_mutex> guard(m_language_runtimes_mutex);
     m_language_runtimes.clear();
   }
   m_instrumentation_runtimes.clear();
   m_next_event_action_up.reset();
   // Clear the last natural stop ID since it has a strong reference to this
if (StateIsStoppedState(new_state, false)) {
       // The process plugin is responsible for managing the actual behavior of
       // the threads and should have stopped any threads that are going to stop
       // before we get here.
       m_thread_list.DidStop();
 
       m_mod_id.BumpStopID();
       if (!m_mod_id.IsLastResumeForUserExpression())
         m_mod_id.SetStopEventForLastNaturalStopID(event_sp);
-      m_memory_cache.Clear();
+      m_memory_cache.Clear(GetMemoryCacheLineSize());
       LLDB_LOGF(log, "Process::SetPrivateState (%s) stop_id = %u",
                 StateAsCString(new_state), m_mod_id.GetStopID());
     }
 
     // Use our target to get a shared pointer to ourselves...
     if (m_finalize_called && !PrivateStateThreadIsValid())
       BroadcastEvent(event_sp);
     else
void Process::DidExec() {
   m_image_tokens.clear();
   m_allocated_memory_cache.Clear();
   {
     std::lock_guard<std::recursive_mutex> guard(m_language_runtimes_mutex);
     m_language_runtimes.clear();
   }
   m_instrumentation_runtimes.clear();
   m_thread_list.DiscardThreadPlans();
-  m_memory_cache.Clear(true);
+  m_memory_cache.Clear(GetMemoryCacheLineSize(), true);
   DoDidExec();
   CompleteAttach();
   // Flush the process (threads and all stack frames) after running
   // CompleteAttach() in case the dynamic loader loaded things in new
   // locations.
   Flush();
 
   // After we figure out what was loaded/unloaded in CompleteAttach, we need to

lldb/unittests/Target/CMakeLists.txt

 add_lldb_unittest(TargetTests
   ABITest.cpp
   ExecutionContextTest.cpp
+  MemoryCacheTest.cpp
   MemoryRegionInfoTest.cpp
   ModuleCacheTest.cpp
   PathMappingListTest.cpp
   StackFrameRecognizerTest.cpp
 
   LINK_LIBS
       lldbCore
       lldbHost

lldb/unittests/Target/MemoryCacheTest.cpp

+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include "lldb/Target/Memory.h"
+#include "lldb/Utility/Status.h"
+
+using namespace lldb_private;
+using namespace lldb;
+
+namespace {
+
+class MemoryCacheTest : public MemoryFromInferiorReader, public testing::Test {
+  static const size_t k_memory_size = 256;
+  static const uint64_t k_cache_line_size = 16;
+
+  size_t ReadMemoryFromInferior(lldb::addr_t vm_addr, void *buf, size_t size,
+                                Status &error) override;
+
+public:
+  MemoryCacheTest();
+
+  void AddRangeToL1Cache(lldb::addr_t addr, size_t len);
+  void IncrementAndFlushRange(lldb::addr_t addr, size_t len);
+  std::vector<uint8_t> ReadByBytes(lldb::addr_t addr, size_t len);
+
+protected:
+  MemoryCache m_cache;
+  std::vector<uint8_t> m_memory;
+  size_t m_inferior_read_count;
+};
+
+MemoryCacheTest::MemoryCacheTest()
+    : m_cache(*this, k_cache_line_size), m_inferior_read_count(0) {
+  for (size_t i = 0; i < k_memory_size; i++)
+    m_memory.push_back(static_cast<uint8_t>(i));
+}
+
+void MemoryCacheTest::AddRangeToL1Cache(lldb::addr_t addr, size_t len) {
+  m_cache.AddL1CacheData(addr, m_memory.data() + addr, len);
+}
+
+size_t MemoryCacheTest::ReadMemoryFromInferior(lldb::addr_t vm_addr, void *buf,
+                                               size_t size, Status &error) {
+  m_inferior_read_count++;
+
+  if (vm_addr >= m_memory.size())
+    return 0;
+
+  size = std::min(size, m_memory.size() - vm_addr);
+  memcpy(buf, m_memory.data() + vm_addr, size);
+  return size;
+}
+
+void MemoryCacheTest::IncrementAndFlushRange(lldb::addr_t addr, size_t len) {
+  for (size_t i = 0; i < len; i++)
+    m_memory[addr + i]++;
+  m_cache.Flush(addr, len);
+}
+
+std::vector<uint8_t> MemoryCacheTest::ReadByBytes(lldb::addr_t addr,
+                                                  size_t len) {
+  std::vector<uint8_t> result(len, 0);
+  for (size_t i = 0; i < len; i++) {
+    Status error;
+    m_cache.Read(addr + i, &(result[i]), 1, error);
+    EXPECT_TRUE(error.Success());
+  }
+  return result;
+}
+
+TEST_F(MemoryCacheTest, L1FlushSimple) {
+  Status error;
+  std::vector<uint8_t> result(10);
+
+  m_cache.Read(10, result.data(), result.size(), error);
+  ASSERT_EQ(10, result[0]);
+
+  IncrementAndFlushRange(10, 1);
+
+  m_cache.Read(10, result.data(), result.size(), error);
+  ASSERT_EQ(m_memory[10], result[0]);
+}
+
+class MemoryCacheOverlapTest
+    : public MemoryCacheTest,
+      public testing::WithParamInterface<std::pair<lldb::addr_t, size_t>> {};
+
+TEST_P(MemoryCacheOverlapTest, L1FlushFromTwoWithOverlap) {
+  // Add two ranges to the cache.
+  std::vector<std::pair<lldb::addr_t, size_t>> cached = {{10, 10}, {30, 10}};
+  for (std::pair<lldb::addr_t, size_t> p : cached)
+    AddRangeToL1Cache(p.first, p.second);
+
+  // Flush the range given by the parameter.
+  IncrementAndFlushRange(GetParam().first, GetParam().second);
+
+  // Check the memory.
+  size_t check_size = 50;
+  std::vector<uint8_t> result = ReadByBytes(0, check_size);
+  EXPECT_THAT(result, ::testing::ElementsAreArray(m_memory.data(), check_size));
+}
+
+INSTANTIATE_TEST_CASE_P(
+    AllMemoryCacheOverlapTest, MemoryCacheOverlapTest,
+    ::testing::Values(
+        std::make_pair(5, 6), std::make_pair(5, 10), std::make_pair(5, 20),
+        std::make_pair(5, 30), std::make_pair(5, 40), std::make_pair(10, 1),
+        std::make_pair(10, 21), std::make_pair(19, 1), std::make_pair(19, 11),
+        std::make_pair(19, 12), std::make_pair(20, 11), std::make_pair(20, 25),
+        std::make_pair(29, 2), std::make_pair(29, 12), std::make_pair(30, 1),
+        std::make_pair(39, 1), std::make_pair(39, 5)));
+
+class MemoryCacheNoOverlapTest
+    : public MemoryCacheTest,
+      public testing::WithParamInterface<std::pair<lldb::addr_t, size_t>> {};
+
+TEST_P(MemoryCacheNoOverlapTest, L1FlushFromTwoWithoutOverlap) {
+  // Add two ranges to the cache.
+  std::vector<std::pair<lldb::addr_t, size_t>> cached = {{10, 10}, {30, 10}};
+  for (std::pair<lldb::addr_t, size_t> p : cached)
+    AddRangeToL1Cache(p.first, p.second);
+
+  // Flush the range given by the parameter.
+  IncrementAndFlushRange(GetParam().first, GetParam().second);
+
+  // Check that we can read from the cache without going to the inferior.
+  for (std::pair<lldb::addr_t, size_t> p : cached)
+    ReadByBytes(p.first, p.second);
+  EXPECT_EQ(0u, m_inferior_read_count);
+
+  // Check the memory.
+  size_t check_size = 50;
+  std::vector<uint8_t> result = ReadByBytes(0, check_size);
+  EXPECT_THAT(result, ::testing::ElementsAreArray(m_memory.data(), check_size));
+}
+
+INSTANTIATE_TEST_CASE_P(
+    AllMemoryCacheNoOverlapTest, MemoryCacheNoOverlapTest,
+    ::testing::Values(std::make_pair(5, 1), std::make_pair(5, 5),
+                      std::make_pair(9, 1), std::make_pair(20, 1),
+                      std::make_pair(20, 10), std::make_pair(29, 1),
+                      std::make_pair(40, 1), std::make_pair(40, 10)));
+
+} // namespace