https://github.com/qiyao updated https://github.com/llvm/llvm-project/pull/222688
>From 6aba49fb9b2840d0fd73e07b543f93cd15bf473c Mon Sep 17 00:00:00 2001 From: Yao Qi <[email protected]> Date: Wed, 2 Sep 2026 14:16:30 +0100 Subject: [PATCH 1/5] [lldb] [NFC] Rename MemoryCache::AddL1CacheData to AddCacheData The next commit partitions the two caches, and this function stops being the way into L1: it splits what it is given at cache line boundaries, so whole lines land in L2 and only the shorter pieces in L1. Rename it first, so that commit carries the behaviour change alone. Until then the name is wider than the function, which still writes to L1 and nothing else. --- lldb/include/lldb/Target/Memory.h | 12 ++++++------ .../Process/gdb-remote/ProcessGDBRemote.cpp | 5 ++--- lldb/source/Target/Memory.cpp | 14 +++++++------- lldb/unittests/Target/MemoryTest.cpp | 8 ++++---- 4 files changed, 19 insertions(+), 20 deletions(-) diff --git a/lldb/include/lldb/Target/Memory.h b/lldb/include/lldb/Target/Memory.h index ad902ea584449..7cf7fa76b9954 100644 --- a/lldb/include/lldb/Target/Memory.h +++ b/lldb/include/lldb/Target/Memory.h @@ -46,16 +46,16 @@ class MemoryCache { 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); + /// Allow external sources to populate data into the memory cache. + void AddCacheData(lldb::addr_t addr, const void *src, size_t src_len); - void AddL1CacheData(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src) { + void AddCacheData(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src) { if (!src.empty()) - AddL1CacheData(addr, src.data(), src.size()); + AddCacheData(addr, src.data(), src.size()); } - void AddL1CacheData(lldb::addr_t addr, - const lldb::DataBufferSP &data_buffer_sp); + void AddCacheData(lldb::addr_t addr, + const lldb::DataBufferSP &data_buffer_sp); protected: typedef std::map<lldb::addr_t, lldb::DataBufferSP> BlockMap; diff --git a/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp b/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp index 9d2ba4ac6b474..4e5a5efcbca72 100644 --- a/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp +++ b/lldb/source/Plugins/Process/gdb-remote/ProcessGDBRemote.cpp @@ -2366,8 +2366,7 @@ ProcessGDBRemote::SetThreadStopInfo(StructuredData::Dictionary *thread_dict) { const size_t bytes_copied = bytes.GetHexBytes(data_buffer_sp->GetData(), 0); if (bytes_copied == byte_size) - m_memory_cache.AddL1CacheData(mem_cache_addr, - data_buffer_sp); + m_memory_cache.AddCacheData(mem_cache_addr, data_buffer_sp); } } } @@ -2557,7 +2556,7 @@ StateType ProcessGDBRemote::SetThreadStopInfo(StringExtractor &stop_packet) { const size_t bytes_copied = bytes.GetHexBytes(data_buffer_sp->GetData(), 0); if (bytes_copied == byte_size) - m_memory_cache.AddL1CacheData(mem_cache_addr, data_buffer_sp); + m_memory_cache.AddCacheData(mem_cache_addr, data_buffer_sp); } } } else if (key.compare("watch") == 0 || key.compare("rwatch") == 0 || diff --git a/lldb/source/Target/Memory.cpp b/lldb/source/Target/Memory.cpp index 5782be0d92f85..ce1776d25ebb0 100644 --- a/lldb/source/Target/Memory.cpp +++ b/lldb/source/Target/Memory.cpp @@ -40,13 +40,13 @@ void MemoryCache::Clear(bool clear_invalid_ranges) { m_L2_cache_line_byte_size = m_process.GetMemoryCacheLineSize(); } -void MemoryCache::AddL1CacheData(lldb::addr_t addr, const void *src, - size_t src_len) { - AddL1CacheData(addr, std::make_shared<DataBufferHeap>(src, src_len)); +void MemoryCache::AddCacheData(lldb::addr_t addr, const void *src, + size_t src_len) { + AddCacheData(addr, std::make_shared<DataBufferHeap>(src, src_len)); } -void MemoryCache::AddL1CacheData(lldb::addr_t addr, - const DataBufferSP &data_buffer_sp) { +void MemoryCache::AddCacheData(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; } @@ -221,7 +221,7 @@ size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len, size_t bytes_read = m_process.ReadMemoryFromInferior(addr, dst, dst_len, error); if (bytes_read > 0) - AddL1CacheData(addr, dst, bytes_read); + AddCacheData(addr, dst, bytes_read); return bytes_read; } @@ -343,7 +343,7 @@ MemoryCache::ReadRanges(llvm::ArrayRef<Range<lldb::addr_t, size_t>> ranges, auto fetched_buffers = llvm::ArrayRef(fetched_buffers_vec); for (auto [missed_range, fetched] : llvm::zip(missed_ranges, fetched_buffers)) - AddL1CacheData(missed_range.GetRangeBase(), fetched); + AddCacheData(missed_range.GetRangeBase(), fetched); // Use the just-fetched memory to fill in the gaps left by the cache. for (auto &result : results) diff --git a/lldb/unittests/Target/MemoryTest.cpp b/lldb/unittests/Target/MemoryTest.cpp index 7891be4698c6c..803a70c677b51 100644 --- a/lldb/unittests/Target/MemoryTest.cpp +++ b/lldb/unittests/Target/MemoryTest.cpp @@ -194,7 +194,7 @@ class CacheTestProcess { void AddCacheChunk(TestMemoryCache &cache, lldb::addr_t addr, size_t size, uint8_t fill) { - cache.AddL1CacheData(addr, std::make_shared<DataBufferHeap>(size, fill)); + cache.AddCacheData(addr, std::make_shared<DataBufferHeap>(size, fill)); } bool AllBytesAre(llvm::ArrayRef<uint8_t> bytes, uint8_t fill) { @@ -666,7 +666,7 @@ TEST_F(MemoryTest, TestCacheCopiesRawBytes) { Status error; TestMemoryCache cache(*process); std::vector<uint8_t> raw(16, 0xAA); - cache.AddL1CacheData(0x5000, raw.data(), raw.size()); + cache.AddCacheData(0x5000, raw.data(), raw.size()); ASSERT_EQ(cache.GetL1Cache().count(0x5000), 1u); EXPECT_NE(cache.GetL1Cache().at(0x5000)->GetBytes(), raw.data()); @@ -1039,7 +1039,7 @@ TEST_F(MemoryDeathTest, TestReadRangesWithShortBufferAndCacheHit) { DummyProcess *process = static_cast<DummyProcess *>(process_sp.get()); TestMemoryCache cache(*process); - cache.AddL1CacheData(0x1000, std::make_shared<DataBufferHeap>(16, 0xAA)); + cache.AddCacheData(0x1000, std::make_shared<DataBufferHeap>(16, 0xAA)); ASSERT_EQ(cache.GetL1Cache().count(0x1000), 1u); llvm::SmallVector<uint8_t, 0> short_buffer(8, 0); @@ -1183,7 +1183,7 @@ TEST_F(MemoryDeathTest, TestVerifyMemoryReads) { // DummyReaderProcess returns the low byte of each address, so a run of // zeroes cannot be what it would read. process_sp->GetMemoryCache().Clear(); - process_sp->GetMemoryCache().AddL1CacheData( + process_sp->GetMemoryCache().AddCacheData( 0x2000, std::make_shared<DataBufferHeap>(16, 0)); std::vector<uint8_t> bad(16, 0); ASSERT_DEATH( >From f5c8c466ae0b5dd13fd2ad02f6db4c85b13d4242 Mon Sep 17 00:00:00 2001 From: Yao Qi <[email protected]> Date: Wed, 2 Sep 2026 14:16:40 +0100 Subject: [PATCH 2/5] [lldb] Memory cache: no overlap and read across cache entries The memory cache keeps two collections of cached bytes, L1 and L2, which are named confusingly. L2 holds cache lines at aligned addresses, but each line size is less than or equal to the fixed line size. L1 holds pieces from arbitrary addresses with arbitrary lengths. This caused two problems: 1. a lookup had to find every byte it wanted inside a *single* entry. A range that spanned two adjacent entries missed even when the two collections together already held every byte of it. The lookup rejected such a read rather than take part of it from each entry. 2. the pieces could also overlap each other, which made the lookup incomplete as well as ambiguous. It examined only the piece starting at or below the address, so a short piece hid a longer one that covered the whole read, and the read missed with the bytes resident. This commit fixes these problems by introducing these properties to the cache: - At most one collection holds any given address. - The line collection holds only whole, aligned lines (`LineCache`). - The piece collection holds only fragments smaller than a line, and they never overlap each other (`ChunkCache`). - A read takes what it needs from consecutive entries in turn until a miss. - `AddCacheData` splits incoming bytes at line boundaries and drops bytes already held, so callers no longer pick the cache tier. Disjoint entries make the cache simple to reason about: - A read no longer depends on which copy of an address is found first, because there is only one. - Probing one candidate is now complete, since entries cannot overlap, the entry starting at or below an address is the only one that can hold it. No byte is stored twice. - Invalidating an address touches one entry, with no second copy elsewhere to find and drop. - Caller of cache needs no knowledge of cache internals. Scanning an Objective-C class table reads each method name through a 256-byte window. Because names are packed end to end, windows start at arbitrary offsets and most of them span two adjacent lines. Under the old lookup, such a window missed even when both lines were resident, because neither line held all 256 bytes alone. It now hits, sending 7 fewer batched read packets during the scan. `Flush` now drops cached entries in the range instead of walking it. It eliminates the overflow and bounds runtime to cache size rather than range size. `GrowReadRange` isolates the read-ahead policy from `Read`. It grows a fetch to whole cache lines where safe and clips the read at invalid ranges. --- lldb/include/lldb/Target/Memory.h | 143 +++++-- lldb/source/Target/Memory.cpp | 422 +++++++++++--------- lldb/unittests/Target/MemoryTest.cpp | 556 +++++++++++++++++++++++---- 3 files changed, 828 insertions(+), 293 deletions(-) diff --git a/lldb/include/lldb/Target/Memory.h b/lldb/include/lldb/Target/Memory.h index 7cf7fa76b9954..fbc5fe93a99de 100644 --- a/lldb/include/lldb/Target/Memory.h +++ b/lldb/include/lldb/Target/Memory.h @@ -12,12 +12,97 @@ #include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include <map> +#include <memory> #include <mutex> #include <vector> namespace lldb_private { + +/// A set of whole, aligned cache lines, keyed by line index. A key names a +/// whole line, so no entry can be partial or unaligned and no length is +/// stored per entry. +class LineCache { + using Collection = llvm::DenseMap<uint64_t, std::unique_ptr<uint8_t[]>>; + +public: + explicit LineCache(uint32_t line_byte_size) + : m_line_byte_size(line_byte_size) {} + + uint32_t GetLineByteSize() const { return m_line_byte_size; } + + /// The cached bytes from \a addr to the end of the line holding it, empty if + /// that line is not resident. + llvm::ArrayRef<uint8_t> Lookup(lldb::addr_t addr) const; + + bool Holds(lldb::addr_t addr) const { + return m_lines.contains(IndexOf(addr)); + } + + /// Add one whole line. \a addr must be line aligned and \a src must hold a + /// whole line. + void Insert(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src); + + /// Drop every line that intersects [addr, addr+size). + void EraseRange(lldb::addr_t addr, lldb::addr_t size); + + void Clear(uint32_t new_line_byte_size) { + m_lines.clear(); + m_line_byte_size = new_line_byte_size; + } + + size_t GetSize() const { return m_lines.size(); } + + /// Iteration yields a line index and its bytes, in unspecified order. + using const_iterator = Collection::const_iterator; + const_iterator begin() const { return m_lines.begin(); } + const_iterator end() const { return m_lines.end(); } + +private: + uint64_t IndexOf(lldb::addr_t addr) const { return addr / m_line_byte_size; } + + Collection m_lines; + uint32_t m_line_byte_size; +}; + +/// A set of non-overlapping byte ranges at arbitrary addresses. Lengths vary, +/// so every chunk carries its own. +class ChunkCache { + using Collection = std::map<lldb::addr_t, std::vector<uint8_t>>; + +public: + /// The cached bytes from \a addr to the end of the chunk holding it, empty + /// if no chunk holds it. + llvm::ArrayRef<uint8_t> Lookup(lldb::addr_t addr) const; + + bool Holds(lldb::addr_t addr) const { return !Lookup(addr).empty(); } + + /// Add the bytes of [addr, addr+src.size()) that no chunk holds yet. Bytes + /// already held are kept: which read produced a byte does not matter. + void InsertMissing(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src); + + /// Drop every chunk that intersects [addr, addr+size). + void EraseRange(lldb::addr_t addr, lldb::addr_t size); + + void Clear() { m_chunks.clear(); } + + size_t GetSize() const { return m_chunks.size(); } + + /// Iteration yields a chunk's start address and its bytes, in address order. + using const_iterator = Collection::const_iterator; + const_iterator begin() const { return m_chunks.begin(); } + const_iterator end() const { return m_chunks.end(); } + +private: + /// The chunk holding \a addr, or end(). Chunks never overlap, so only the + /// one starting at or below \a addr can hold it. + Collection::const_iterator FindChunkContaining(lldb::addr_t addr) const; + + Collection m_chunks; +}; + // A class to track memory that was read from a live process between // runs. class MemoryCache { @@ -33,14 +118,15 @@ class MemoryCache { size_t Read(lldb::addr_t addr, void *dst, size_t dst_len, Status &error); - /// Reads multiple memory ranges, serving cache hits from L1 and L2 and - /// batching all misses through Process::DoReadMemoryRanges. The semantics of - /// the return value match Process::ReadMemoryRanges. + /// Reads memory ranges, serving hits from the cache and batching misses + /// through Process::DoReadMemoryRanges. Matches Process::ReadMemoryRanges. llvm::SmallVector<llvm::MutableArrayRef<uint8_t>> ReadRanges(llvm::ArrayRef<Range<lldb::addr_t, size_t>> ranges, llvm::MutableArrayRef<uint8_t> buffer); - uint32_t GetMemoryCacheLineSize() const { return m_L2_cache_line_byte_size; } + uint32_t GetMemoryCacheLineSize() const { + return m_L2_cache.GetLineByteSize(); + } void AddInvalidRange(lldb::addr_t base_addr, lldb::addr_t byte_size); @@ -58,41 +144,44 @@ class MemoryCache { const lldb::DataBufferSP &data_buffer_sp); 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) + // L1 and L2 partition the cache. An address is held by at most one. L2 + // holds whole, aligned lines; L1 holds smaller, non-overlapping pieces. + ChunkCache m_L1_cache; // Chunks smaller than a cache line. + LineCache m_L2_cache; // Whole cache lines. InvalidRanges m_invalid_ranges; Process &m_process; - uint32_t m_L2_cache_line_byte_size; private: MemoryCache(const MemoryCache &) = delete; const MemoryCache &operator=(const MemoryCache &) = delete; - lldb::DataBufferSP GetL2CacheLine(lldb::addr_t addr, Status &error); - - // If the entire range [addr, addr+len) is covered by a single L1 entry, - // returns a pointer into that entry's data at the correct offset. Returns - // nullptr on a miss. Caller must hold m_mutex. - const uint8_t *FindL1CacheEntry(lldb::addr_t addr, size_t len) const; - - // If the entire range [addr, addr+len) is covered by a single cache line - // that is already in L2, returns a pointer into that line's data at the - // correct offset. Never reads from the inferior. Returns nullptr on a miss. - // Caller must hold m_mutex. - const uint8_t *FindL2CacheEntry(lldb::addr_t addr, size_t len) const; - - // Looks the range [addr, addr+len) up in L1 and then L2, returning a pointer - // into the data of whichever entry covers it. Returns nullptr on a miss. + // Add a whole cache line to L2 and drop the L1 entries it supersedes. // Caller must hold m_mutex. - const uint8_t *FindCacheEntry(lldb::addr_t addr, size_t len) const; + void InsertWholeLine(lldb::addr_t line_base_addr, + llvm::ArrayRef<uint8_t> src); + + // Add the bytes of [addr, addr+src.size()) that no entry holds yet to L1. + // The range must lie within one cache line. Caller must hold m_mutex. + void InsertPartialLine(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src); + + // Split [addr, addr+src.size()) at cache line boundaries: whole lines to L2, + // shorter pieces to L1. Takes m_mutex. + void InsertData(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src); + + // Copy the cached bytes of [addr, addr+len), stopping at the first miss, + // and return the count. Never reads from the inferior; caller holds m_mutex. + size_t ReadFromCaches(lldb::addr_t addr, void *dst, size_t len) const; + + // The range to fetch for a read that ends at caller_end and whose first + // bytes_filled bytes the caches supplied, so read_addr is the first byte + // none of them holds. Grown to whole cache lines where that costs nothing, + // and clipped at an invalid range. Caller must hold m_mutex. + AddrRange GrowReadRange(lldb::addr_t read_addr, lldb::addr_t caller_end, + size_t bytes_filled) const; }; diff --git a/lldb/source/Target/Memory.cpp b/lldb/source/Target/Memory.cpp index ce1776d25ebb0..45362c0cdee50 100644 --- a/lldb/source/Target/Memory.cpp +++ b/lldb/source/Target/Memory.cpp @@ -8,47 +8,183 @@ #include "lldb/Target/Memory.h" #include "lldb/Target/Process.h" -#include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/LLDBLog.h" #include "lldb/Utility/Log.h" #include "lldb/Utility/RangeMap.h" #include "lldb/Utility/State.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Support/MathExtras.h" +#include <algorithm> #include <cinttypes> #include <memory> +#include <utility> using namespace lldb; using namespace lldb_private; +llvm::ArrayRef<uint8_t> LineCache::Lookup(addr_t addr) const { + const auto pos = m_lines.find(IndexOf(addr)); + if (pos == m_lines.end()) + return {}; + const addr_t line_offset = addr % m_line_byte_size; + return llvm::ArrayRef(pos->second.get(), m_line_byte_size) + .drop_front(line_offset); +} + +void LineCache::Insert(addr_t addr, llvm::ArrayRef<uint8_t> src) { + assert((addr % m_line_byte_size) == 0 && + "whole line inserted at an unaligned address!"); + assert(src.size() == m_line_byte_size && + "whole line inserted with a partial buffer!"); + auto line = std::make_unique<uint8_t[]>(m_line_byte_size); + std::copy(src.begin(), src.end(), line.get()); + m_lines[IndexOf(addr)] = std::move(line); +} + +void LineCache::EraseRange(addr_t addr, addr_t size) { + if (size == 0) + return; + // Clamp a range running past the end of the address space to it. + const addr_t end_addr = llvm::SaturatingAdd(addr, size - 1); + const uint64_t first_idx = IndexOf(addr); + const uint64_t last_idx = IndexOf(end_addr); + m_lines.remove_if([first_idx, last_idx](const auto &entry) { + return entry.getFirst() >= first_idx && entry.getFirst() <= last_idx; + }); +} + +ChunkCache::Collection::const_iterator +ChunkCache::FindChunkContaining(addr_t addr) const { + if (m_chunks.empty()) + return m_chunks.end(); + Collection::const_iterator pos = m_chunks.upper_bound(addr); + if (pos == m_chunks.begin()) + return m_chunks.end(); + --pos; + // Sum pos->first + size wraps at the top of the address space. + return addr - pos->first < pos->second.size() ? pos : m_chunks.end(); +} + +llvm::ArrayRef<uint8_t> ChunkCache::Lookup(addr_t addr) const { + const Collection::const_iterator pos = FindChunkContaining(addr); + if (pos == m_chunks.end()) + return {}; + return llvm::ArrayRef(pos->second).drop_front(addr - pos->first); +} + +void ChunkCache::InsertMissing(addr_t addr, llvm::ArrayRef<uint8_t> src) { + if (src.empty()) + return; + // The last addressable byte of the range, clamped if it runs past the end of + // the address space. + const addr_t last_addr = llvm::SaturatingAdd<addr_t>(addr, src.size() - 1); + const uint64_t len = last_addr - addr + 1; + + for (uint64_t offset = 0; offset < len;) { + const addr_t curr_addr = addr + offset; + if (const llvm::ArrayRef<uint8_t> held = Lookup(curr_addr); !held.empty()) { + offset += std::min<uint64_t>(held.size(), len - offset); + continue; + } + // Nothing holds curr_addr, so the gap runs to the next chunk or to the end. + const Collection::const_iterator next = m_chunks.lower_bound(curr_addr); + const uint64_t gap_len = + next == m_chunks.end() + ? len - offset + : std::min<uint64_t>(next->first - curr_addr, len - offset); + const llvm::ArrayRef<uint8_t> gap_bytes = src.slice(offset, gap_len); + m_chunks[curr_addr].assign(gap_bytes.begin(), gap_bytes.end()); + offset += gap_len; + } +} + +void ChunkCache::EraseRange(addr_t addr, addr_t size) { + if (size == 0) + return; + // Clamp a range running past the end of the address space to it. + const addr_t end_addr = llvm::SaturatingAdd(addr, size - 1); + + Collection::iterator pos = m_chunks.lower_bound(addr); + // A chunk starting below addr can still reach into the range. + if (pos != m_chunks.begin()) { + const Collection::iterator prev = std::prev(pos); + if (addr - prev->first < prev->second.size()) + m_chunks.erase(prev); + } + while (pos != m_chunks.end() && pos->first <= end_addr) + pos = m_chunks.erase(pos); +} + // 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_mutex(), m_L1_cache(), m_L2_cache(process.GetMemoryCacheLineSize()), + m_invalid_ranges(), m_process(process) {} // 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(); + m_L1_cache.Clear(); + m_L2_cache.Clear(m_process.GetMemoryCacheLineSize()); if (clear_invalid_ranges) m_invalid_ranges.Clear(); - m_L2_cache_line_byte_size = m_process.GetMemoryCacheLineSize(); } void MemoryCache::AddCacheData(lldb::addr_t addr, const void *src, size_t src_len) { - AddCacheData(addr, std::make_shared<DataBufferHeap>(src, src_len)); + InsertData(addr, {static_cast<const uint8_t *>(src), src_len}); +} + +void MemoryCache::InsertWholeLine(addr_t line_base_addr, + llvm::ArrayRef<uint8_t> src) { + m_L2_cache.Insert(line_base_addr, src); + // The new line holds every byte the L1 entries inside it held. + m_L1_cache.EraseRange(line_base_addr, src.size()); +} + +void MemoryCache::InsertPartialLine(addr_t addr, llvm::ArrayRef<uint8_t> src) { + const uint32_t line_size = m_L2_cache.GetLineByteSize(); + assert(src.size() <= line_size && + addr / line_size == (addr + src.size() - 1) / line_size && + "a partial-line insert must not cross a cache line boundary"); + // L2 holds only whole lines, so a range inside a resident line is held + // already. + if (m_L2_cache.Holds(addr)) + return; + m_L1_cache.InsertMissing(addr, src); +} + +void MemoryCache::InsertData(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src) { + if (src.empty()) + return; + + std::lock_guard<std::recursive_mutex> guard(m_mutex); + // The last addressable byte of the range, clamped if it runs past the end of + // the address space, so no offset added to addr can wrap to 0. + const addr_t last_addr = llvm::SaturatingAdd<addr_t>(addr, src.size() - 1); + const uint64_t len = last_addr - addr + 1; + const uint32_t line_size = m_L2_cache.GetLineByteSize(); + + for (uint64_t offset = 0; offset < len;) { + const addr_t curr_addr = addr + offset; + const uint64_t line_offset = curr_addr % line_size; + const uint64_t piece_len = + std::min<uint64_t>(line_size - line_offset, len - offset); + const llvm::ArrayRef<uint8_t> piece_bytes = src.slice(offset, piece_len); + if (line_offset == 0 && piece_len == line_size) + InsertWholeLine(curr_addr, piece_bytes); + else + InsertPartialLine(curr_addr, piece_bytes); + offset += piece_len; + } } void MemoryCache::AddCacheData(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; + InsertData(addr, {data_buffer_sp->GetBytes(), data_buffer_sp->GetByteSize()}); } void MemoryCache::Flush(addr_t addr, size_t size) { @@ -57,46 +193,8 @@ void MemoryCache::Flush(addr_t addr, size_t size) { std::lock_guard<std::recursive_mutex> guard(m_mutex); - // L1 chunks can overlap, and a chunk starting below addr can still reach - // into the flushed range, so scan the whole L1 cache and erase every chunk - // that intersects it. - if (!m_L1_cache.empty()) { - AddrRange flush_range(addr, size); - BlockMap::iterator pos = m_L1_cache.begin(); - while (pos != m_L1_cache.end()) { - AddrRange chunk_range(pos->first, pos->second->GetByteSize()); - if (chunk_range.DoesIntersect(flush_range)) - pos = m_L1_cache.erase(pos); - else - ++pos; - } - } - - if (!m_L2_cache.empty()) { - const uint32_t cache_line_byte_size = m_L2_cache_line_byte_size; - const addr_t end_addr = (addr + size - 1); - const addr_t first_cache_line_addr = addr - (addr % cache_line_byte_size); - const addr_t last_cache_line_addr = - end_addr - (end_addr % cache_line_byte_size); - // Watch for overflow where size will cause us to go off the end of the - // 64 bit address space - uint32_t num_cache_lines; - if (last_cache_line_addr >= first_cache_line_addr) - num_cache_lines = ((last_cache_line_addr - first_cache_line_addr) / - cache_line_byte_size) + - 1; - else - num_cache_lines = - (UINT64_MAX - first_cache_line_addr + 1) / cache_line_byte_size; - - uint32_t cache_idx = 0; - for (addr_t curr_addr = first_cache_line_addr; cache_idx < num_cache_lines; - curr_addr += cache_line_byte_size, ++cache_idx) { - BlockMap::iterator pos = m_L2_cache.find(curr_addr); - if (pos != m_L2_cache.end()) - m_L2_cache.erase(pos); - } - } + m_L1_cache.EraseRange(addr, size); + m_L2_cache.EraseRange(addr, size); } void MemoryCache::AddInvalidRange(lldb::addr_t base_addr, @@ -124,67 +222,69 @@ bool MemoryCache::RemoveInvalidRange(lldb::addr_t base_addr, return false; } -const uint8_t *MemoryCache::FindL1CacheEntry(lldb::addr_t addr, - size_t len) const { - if (m_L1_cache.empty()) - return nullptr; - AddrRange read_range(addr, len); - BlockMap::const_iterator pos = m_L1_cache.upper_bound(addr); - if (pos != m_L1_cache.begin()) - --pos; - AddrRange chunk_range(pos->first, pos->second->GetByteSize()); - if (!chunk_range.Contains(read_range)) - return nullptr; - return pos->second->GetBytes() + (addr - chunk_range.GetRangeBase()); -} +size_t MemoryCache::ReadFromCaches(lldb::addr_t addr, void *dst, + size_t len) const { + size_t bytes_filled = 0; + // Bytes from addr to the last addressable byte. The walk must not pass + // it, or curr_addr wraps to 0. + const uint64_t space_to_top = UINT64_MAX - addr; + while (bytes_filled < len) { + if (bytes_filled > space_to_top) + break; + const addr_t curr_addr = addr + bytes_filled; -const uint8_t *MemoryCache::FindL2CacheEntry(lldb::addr_t addr, - size_t len) const { - if (m_L2_cache.empty()) - return nullptr; - const lldb::addr_t line_offset = addr % m_L2_cache_line_byte_size; - BlockMap::const_iterator pos = m_L2_cache.find(addr - line_offset); - if (pos == m_L2_cache.end()) - return nullptr; - if (line_offset + len > pos->second->GetByteSize()) - return nullptr; - return pos->second->GetBytes() + line_offset; -} + // At most one of the caches can hold curr_addr. + llvm::ArrayRef<uint8_t> cached = m_L2_cache.Lookup(curr_addr); + if (cached.empty()) + cached = m_L1_cache.Lookup(curr_addr); + if (cached.empty()) + break; -const uint8_t *MemoryCache::FindCacheEntry(lldb::addr_t addr, - size_t len) const { - const uint8_t *cached = FindL1CacheEntry(addr, len); - if (!cached) - cached = FindL2CacheEntry(addr, len); - return cached; + const size_t to_copy = std::min(cached.size(), len - bytes_filled); + memcpy(static_cast<uint8_t *>(dst) + bytes_filled, cached.data(), to_copy); + bytes_filled += to_copy; + } + return bytes_filled; } -lldb::DataBufferSP MemoryCache::GetL2CacheLine(lldb::addr_t line_base_addr, - Status &error) { - // This function assumes that the address given is aligned correctly. - assert((line_base_addr % m_L2_cache_line_byte_size) == 0); - - std::lock_guard<std::recursive_mutex> guard(m_mutex); - auto pos = m_L2_cache.find(line_base_addr); - if (pos != m_L2_cache.end()) - return pos->second; - - auto data_buffer_heap_sp = - std::make_shared<DataBufferHeap>(m_L2_cache_line_byte_size, 0); - size_t process_bytes_read = m_process.ReadMemoryFromInferior( - line_base_addr, data_buffer_heap_sp->GetBytes(), - data_buffer_heap_sp->GetByteSize(), error); - - // If we failed a read, not much we can do. - if (process_bytes_read == 0) - return lldb::DataBufferSP(); - - // If we didn't get a complete read, we can still cache what we did get. - if (process_bytes_read < m_L2_cache_line_byte_size) - data_buffer_heap_sp->SetByteSize(process_bytes_read); - - m_L2_cache[line_base_addr] = data_buffer_heap_sp; - return data_buffer_heap_sp; +MemoryCache::AddrRange MemoryCache::GrowReadRange(addr_t read_addr, + addr_t caller_end, + size_t bytes_filled) const { + const uint64_t line_size = m_L2_cache.GetLineByteSize(); + const addr_t line_base_addr = llvm::alignDown(read_addr, line_size); + // Caps read-ahead at this many whole cache lines. + static constexpr uint32_t kMaxCacheLinesPerRead = 2; + const uint64_t grow_span = kMaxCacheLinesPerRead * line_size; + + // A request already past the cap spans a line, and one whose growth would + // wrap cannot be grown, so both are asked for as they stand. + if (line_base_addr > UINT64_MAX - grow_span || + caller_end > line_base_addr + grow_span) + return AddrRange(read_addr, caller_end - read_addr); + + // Grow down to the line base so the fetch lands in L2 as a whole line rather + // than an unaligned L1 fragment. + if (!m_invalid_ranges.FindEntryThatIntersects( + InvalidRanges::Entry(line_base_addr, read_addr - line_base_addr)) && + (caller_end <= line_base_addr + line_size || bytes_filled == 0)) + read_addr = line_base_addr; + + // Read up to the last line the request touches, skipping that line when L2 + // holds it. + addr_t last_line_addr = llvm::alignDown(caller_end - 1, line_size); + if (last_line_addr > line_base_addr && m_L2_cache.Holds(last_line_addr)) + last_line_addr -= line_size; + const addr_t grow_target = last_line_addr + line_size; + + // Growth stops at the first invalid range among the bytes it adds. + addr_t read_end = grow_target; + if (grow_target > caller_end) { + if (const InvalidRanges::Entry *invalid = + m_invalid_ranges.FindEntryThatIntersects( + InvalidRanges::Entry(caller_end, grow_target - caller_end))) + read_end = invalid->GetRangeBase(); + } + return AddrRange(read_addr, read_end - read_addr); } size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len, @@ -193,11 +293,11 @@ size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len, return 0; std::lock_guard<std::recursive_mutex> guard(m_mutex); - + addr_t invalid_addr = LLDB_INVALID_ADDRESS; if (const InvalidRanges::Entry *invalid = m_invalid_ranges.FindEntryThatIntersects( InvalidRanges::Entry(addr, dst_len))) { - const addr_t invalid_addr = invalid->GetRangeBase(); + invalid_addr = invalid->GetRangeBase(); error = Status::FromErrorStringWithFormat( "memory read failed for 0x%" PRIx64, invalid_addr); if (invalid_addr <= addr) @@ -205,91 +305,33 @@ size_t MemoryCache::Read(addr_t addr, void *dst, size_t dst_len, dst_len = invalid_addr - addr; } - // Check the L1 cache for a range that contains the entire memory read. - // L1 cache contains chunks of memory that are not required to be the size of - // an L2 cache line. We avoid trying to do partial reads from the L1 cache to - // simplify the implementation. - if (const uint8_t *l1_data = FindL1CacheEntry(addr, dst_len)) { - memcpy(dst, l1_data, dst_len); + size_t bytes_from_cache = ReadFromCaches(addr, dst, dst_len); + if (bytes_from_cache == dst_len) return dst_len; - } - // If the size of the read is greater than the size of an L2 cache line, we'll - // just read from the inferior. If that read is successful, we'll cache what - // we read in the L1 cache for future use. - if (dst_len > m_L2_cache_line_byte_size) { - size_t bytes_read = - m_process.ReadMemoryFromInferior(addr, dst, dst_len, error); - if (bytes_read > 0) - AddCacheData(addr, dst, bytes_read); - return bytes_read; + addr_t read_addr = addr + bytes_from_cache; + addr_t read_end = addr + dst_len; + // A request hits the invalid range above, don't grow. + if (invalid_addr == LLDB_INVALID_ADDRESS) { + const AddrRange grown = + GrowReadRange(read_addr, read_end, bytes_from_cache); + read_addr = grown.GetRangeBase(); + read_end = grown.GetRangeEnd(); } - // If the size of the read fits inside one L2 cache line, we'll try reading - // from the L2 cache. Note that if the range of memory we're reading sits - // between two contiguous cache lines, we'll touch two cache lines instead of - // just one. - - // We're going to have all of our loads and reads be cache line aligned. - addr_t cache_line_offset = addr % m_L2_cache_line_byte_size; - addr_t cache_line_base_addr = addr - cache_line_offset; - DataBufferSP first_cache_line = GetL2CacheLine(cache_line_base_addr, error); - // If we get nothing, then the read to the inferior likely failed. Nothing to - // do here. - if (!first_cache_line) - return 0; + std::vector<uint8_t> read_buf(read_end - read_addr); + const size_t bytes_from_inferior = m_process.ReadMemoryFromInferior( + read_addr, read_buf.data(), read_buf.size(), error); + if (bytes_from_inferior == 0) + return bytes_from_cache; - // If the cache line was not filled out completely and the offset is greater - // than what we have available, we can't do anything further here. - if (cache_line_offset >= first_cache_line->GetByteSize()) - return 0; - - uint8_t *dst_buf = (uint8_t *)dst; - size_t bytes_left = dst_len; - size_t read_size = first_cache_line->GetByteSize() - cache_line_offset; - if (read_size > bytes_left) - read_size = bytes_left; - - memcpy(dst_buf + dst_len - bytes_left, - first_cache_line->GetBytes() + cache_line_offset, read_size); - bytes_left -= read_size; - - // If the cache line was not filled out completely and we still have data to - // read, we can't do anything further. - if (first_cache_line->GetByteSize() < m_L2_cache_line_byte_size && - bytes_left > 0) - return dst_len - bytes_left; - - // We'll hit this scenario if our read straddles two cache lines. - if (bytes_left > 0) { - cache_line_base_addr += m_L2_cache_line_byte_size; - - // FIXME: Until we are able to more thoroughly check for invalid ranges, we - // will have to check the second line to see if it is in an invalid range as - // well. See the check near the beginning of the function for more details. - if (m_invalid_ranges.FindEntryThatContains(cache_line_base_addr)) { - error = Status::FromErrorStringWithFormat( - "memory read failed for 0x%" PRIx64, cache_line_base_addr); - return dst_len - bytes_left; - } - - DataBufferSP second_cache_line = - GetL2CacheLine(cache_line_base_addr, error); - if (!second_cache_line) - return dst_len - bytes_left; - - read_size = bytes_left; - if (read_size > second_cache_line->GetByteSize()) - read_size = second_cache_line->GetByteSize(); - - memcpy(dst_buf + dst_len - bytes_left, second_cache_line->GetBytes(), - read_size); - bytes_left -= read_size; - - return dst_len - bytes_left; - } + AddCacheData(read_addr, read_buf.data(), bytes_from_inferior); - return dst_len; + // The grown or clipped fetch may not align with what the caller asked for, + // so pull back only the portion contiguous with what dst already holds. + uint8_t *dst_tail = static_cast<uint8_t *>(dst) + bytes_from_cache; + return bytes_from_cache + ReadFromCaches(addr + bytes_from_cache, dst_tail, + dst_len - bytes_from_cache); } llvm::SmallVector<llvm::MutableArrayRef<uint8_t>> @@ -322,11 +364,9 @@ MemoryCache::ReadRanges(llvm::ArrayRef<Range<lldb::addr_t, size_t>> ranges, continue; } - const uint8_t *cached = FindCacheEntry(addr, len); - if (cached) { + if (ReadFromCaches(addr, buffer.data(), len) == len) { results.push_back(buffer.take_front(len)); buffer = buffer.drop_front(len); - memcpy(results.back().data(), cached, len); continue; } diff --git a/lldb/unittests/Target/MemoryTest.cpp b/lldb/unittests/Target/MemoryTest.cpp index 803a70c677b51..bf73d0724d3cf 100644 --- a/lldb/unittests/Target/MemoryTest.cpp +++ b/lldb/unittests/Target/MemoryTest.cpp @@ -131,15 +131,37 @@ class DummyProcess : public Process { void SetFiller(int filler) { m_filler = filler; } }; -// A MemoryCache subclass that exposes the otherwise-protected L1 cache so a -// test can assert on the exact set of chunks it holds. +// A MemoryCache subclass that exposes the otherwise-protected caches so a +// test can assert on the exact set of entries they hold. class TestMemoryCache : public MemoryCache { public: using MemoryCache::MemoryCache; - const BlockMap &GetL1Cache() const { return m_L1_cache; } - const BlockMap &GetL2Cache() const { return m_L2_cache; } + const ChunkCache &GetL1Cache() const { return m_L1_cache; } + const LineCache &GetL2Cache() const { return m_L2_cache; } }; + +using CacheEntries = + std::vector<std::pair<lldb::addr_t, llvm::ArrayRef<uint8_t>>>; + +// The chunks of \a cache, which iterates in address order already. +CacheEntries Snapshot(const ChunkCache &cache) { + CacheEntries entries; + for (const auto &[addr, chunk] : cache) + entries.emplace_back(addr, llvm::ArrayRef(chunk)); + return entries; +} + +// The lines of \a cache in address order, which its iteration does not give. +CacheEntries Snapshot(const LineCache &cache) { + const uint32_t line_size = cache.GetLineByteSize(); + CacheEntries entries; + for (const auto &[line_idx, line] : cache) + entries.emplace_back(line_idx * line_size, + llvm::ArrayRef(line.get(), line_size)); + llvm::sort(entries, llvm::less_first()); + return entries; +} } // namespace TargetSP CreateTarget(DebuggerSP &debugger_sp, ArchSpec &arch) { @@ -296,12 +318,10 @@ TEST_F(MemoryTest, TesetMemoryCacheRead) { bytes_read = mem_cache.Read(0x4001, data_sp->GetBytes(), data_sp->GetByteSize(), error); ASSERT_TRUE(bytes_read == l2_cache_size); - // One aligned line fetch per line touched. - ASSERT_EQ(process->m_reads.size(), 2u); + // One request, both lines whole. + ASSERT_EQ(process->m_reads.size(), 1u); EXPECT_EQ(process->m_reads[0].first, 0x4000u); - EXPECT_EQ(process->m_reads[0].second, l2_cache_size); - EXPECT_EQ(process->m_reads[1].first, 0x4000u + l2_cache_size); - EXPECT_EQ(process->m_reads[1].second, l2_cache_size); + EXPECT_EQ(process->m_reads[0].second, 2 * l2_cache_size); // What happens when we try to straddle 2 cache lines where the first one is // only partially filled? @@ -312,11 +332,14 @@ TEST_F(MemoryTest, TesetMemoryCacheRead) { data_sp->GetByteSize(), error); ASSERT_TRUE(bytes_read == l2_cache_size - 6); // Ignoring the first 5 bytes, // missing the last byte + ASSERT_TRUE(error.Success()); + // The request is grown to both lines it touches and starts at the line base, + // so it spends part of the mock's byte budget below the read. ASSERT_EQ(process->m_reads.size(), 2u); EXPECT_EQ(process->m_reads[0].first, 0x5000u); - EXPECT_EQ(process->m_reads[0].second, l2_cache_size); + EXPECT_EQ(process->m_reads[0].second, 2 * l2_cache_size); EXPECT_EQ(process->m_reads[1].first, 0x5000u + l2_cache_size - 1); - EXPECT_EQ(process->m_reads[1].second, 1u); + EXPECT_EQ(process->m_reads[1].second, l2_cache_size + 1); // What happens if we add an invalid range and try to do a read larger than // a cache line? @@ -363,69 +386,75 @@ TEST_F(MemoryTest, TesetMemoryCacheRead) { EXPECT_EQ(process->m_reads[0].second, l2_cache_size); } -TEST_F(MemoryTest, TestL1Cache) { +TEST_F(MemoryTest, TestCachePartition) { CacheTestProcess proc; ASSERT_TRUE(proc.GetProcess()); DummyProcess *process = proc.GetProcess(); TestMemoryCache mem_cache(*process); + const lldb::addr_t line = process->GetMemoryCacheLineSize(); + ASSERT_EQ(line, 512u); auto add = [&](lldb::addr_t addr, size_t size, uint8_t fill) { AddCacheChunk(mem_cache, addr, size, fill); }; - // Asserts the L1 cache holds exactly `expected` chunks, matched by start - // address, byte size, and a single repeated fill byte, in address order. + // Asserts a snapshot holds exactly `expected` entries, in address order. struct Chunk { lldb::addr_t addr; size_t size; uint8_t fill; }; - auto expect_l1 = [&](std::vector<Chunk> expected) { - const auto &l1 = mem_cache.GetL1Cache(); - ASSERT_EQ(l1.size(), expected.size()); + auto expect = [](const CacheEntries &entries, std::vector<Chunk> expected) { + ASSERT_EQ(entries.size(), expected.size()); size_t i = 0; - for (const auto &[addr, data_sp] : l1) { + for (const auto &[addr, bytes] : entries) { const Chunk &c = expected[i++]; EXPECT_EQ(addr, c.addr); - ASSERT_EQ(data_sp->GetByteSize(), c.size); - const uint8_t *bytes = data_sp->GetBytes(); + ASSERT_EQ(bytes.size(), c.size); for (size_t j = 0; j < c.size; ++j) EXPECT_EQ(bytes[j], c.fill) << "chunk 0x" << std::hex << addr << " byte " << std::dec << j; } }; + auto expect_l1 = [&](std::vector<Chunk> expected) { + expect(Snapshot(mem_cache.GetL1Cache()), expected); + }; + auto expect_l2 = [&](std::vector<Chunk> expected) { + expect(Snapshot(mem_cache.GetL2Cache()), expected); + }; - // Partial overlap: the new chunk overhangs the existing one on the right. + // Partial overlap: only the part not already held is added on the right. mem_cache.Clear(); add(0x1000, 0x100, 0xAA); add(0x1080, 0x100, 0xBB); - expect_l1({{0x1000, 0x100, 0xAA}, {0x1080, 0x100, 0xBB}}); + expect_l1({{0x1000, 0x100, 0xAA}, {0x1100, 0x80, 0xBB}}); + expect_l2({}); - // Partial overlap: the new chunk overhangs the existing one on the left. + // Partial overlap: the new chunk is added on the left. mem_cache.Clear(); add(0x2080, 0x100, 0xAA); add(0x2000, 0x100, 0xBB); - expect_l1({{0x2000, 0x100, 0xBB}, {0x2080, 0x100, 0xAA}}); + expect_l1({{0x2000, 0x80, 0xBB}, {0x2080, 0x100, 0xAA}}); - // New chunk fully contains an existing one: both are kept. + // New chunk fully contains an existing one: added around it. mem_cache.Clear(); add(0x3040, 0x40, 0xAA); add(0x3000, 0x100, 0xBB); - expect_l1({{0x3000, 0x100, 0xBB}, {0x3040, 0x40, 0xAA}}); + expect_l1({{0x3000, 0x40, 0xBB}, {0x3040, 0x40, 0xAA}, {0x3080, 0x80, 0xBB}}); - // New chunk is fully contained by an existing one: both are kept. + // New chunk is fully contained by an existing one: adds nothing. mem_cache.Clear(); - add(0x4000, 0x200, 0xAA); + add(0x4000, 0x100, 0xAA); add(0x4080, 0x80, 0xBB); - expect_l1({{0x4000, 0x200, 0xAA}, {0x4080, 0x80, 0xBB}}); + expect_l1({{0x4000, 0x100, 0xAA}}); - // New chunk partially overlaps two existing chunks; all three are kept. + // New chunk partially overlaps two existing chunks; fills only the whole + // between them. mem_cache.Clear(); add(0x5000, 0x80, 0xAA); add(0x5100, 0x80, 0xCC); add(0x5040, 0x100, 0xBB); - expect_l1( - {{0x5000, 0x80, 0xAA}, {0x5040, 0x100, 0xBB}, {0x5100, 0x80, 0xCC}}); + expect_l1({{0x5000, 0x80, 0xAA}, {0x5080, 0x80, 0xBB}, {0x5100, 0x80, 0xCC}}); // Disjoint chunks stay separate. mem_cache.Clear(); @@ -439,24 +468,79 @@ TEST_F(MemoryTest, TestL1Cache) { add(0x7080, 0x80, 0xBB); expect_l1({{0x7000, 0x80, 0xAA}, {0x7080, 0x80, 0xBB}}); - // Flush must erase every chunk intersecting the flush range, including a - // chunk that starts below the flushed address. Here 0x8140 lies only in the - // lower-starting, longer chunk; it must be dropped while the chunk that does - // not intersect survives untouched. + // Flush must erase an entry starting below the flushed address, and keep one + // in the same line that it does not intersect. mem_cache.Clear(); - add(0x8000, 0x180, 0xAA); - add(0x8080, 0x40, 0xBB); + add(0x8100, 0x80, 0xAA); + add(0x8000, 0x40, 0xBB); mem_cache.Flush(0x8140, 0x4); - expect_l1({{0x8080, 0x40, 0xBB}}); + expect_l1({{0x8000, 0x40, 0xBB}}); // A flush intersecting several partially overlapping chunks drops all of // them, while a chunk it does not intersect is left in place. mem_cache.Clear(); add(0x9000, 0x80, 0xAA); - add(0x9040, 0x100, 0xBB); + add(0x9080, 0x40, 0xBB); add(0x9100, 0x80, 0xCC); - mem_cache.Flush(0x9060, 0x1); + mem_cache.Flush(0x9020, 0x80); expect_l1({{0x9100, 0x80, 0xCC}}); + expect_l2({}); + + // Flush reaches a line and leaves the remainders on either side of it alone. + mem_cache.Clear(); + add(0xB000 + line - 10, 10 + line + 10, 0xAA); + expect_l2({{0xB000 + line, line, 0xAA}}); + mem_cache.Flush(0xB000 + line + 4, 0x4); + expect_l1({{0xB000 + line - 10, 10, 0xAA}, {0xB000 + 2 * line, 10, 0xAA}}); + expect_l2({}); + + // A whole line at an aligned address belongs to L2, not L1. + mem_cache.Clear(); + add(0x9000, line, 0xAA); + expect_l1({}); + expect_l2({{0x9000, line, 0xAA}}); + + // A partial range at an aligned address stays in L1. + mem_cache.Clear(); + add(0xA000, 0x40, 0xAA); + expect_l1({{0xA000, 0x40, 0xAA}}); + expect_l2({}); + + // An unaligned range longer than a line splits into one whole line plus a + // remainder on each side. + mem_cache.Clear(); + add(0xB000 + line - 10, 10 + line + 10, 0xAA); + expect_l1({{0xB000 + line - 10, 10, 0xAA}, {0xB000 + 2 * line, 10, 0xAA}}); + expect_l2({{0xB000 + line, line, 0xAA}}); + + // A range crossing a line boundary but covering no whole line splits in two. + mem_cache.Clear(); + add(0xC000 + line - 12, 20, 0xAA); + expect_l1({{0xC000 + line - 12, 12, 0xAA}, {0xC000 + line, 8, 0xAA}}); + expect_l2({}); + + // A range already held by a line in L2 is dropped. + mem_cache.Clear(); + add(0xD000, line, 0xAA); + add(0xD000 + 8, 16, 0xBB); + expect_l1({}); + expect_l2({{0xD000, line, 0xAA}}); + + // A flush whose first line is absent from L2 still erases the later lines it + // covers, because the range start is a lower bound and not a lookup. + mem_cache.Clear(); + add(0xF000 + line, line, 0xAA); + add(0xF000 + 2 * line, line, 0xBB); + expect_l2({{0xF000 + line, line, 0xAA}, {0xF000 + 2 * line, line, 0xBB}}); + mem_cache.Flush(0xF000, 2 * line); + expect_l2({{0xF000 + 2 * line, line, 0xBB}}); + + // A whole line evicts an entry it only partly covers. + mem_cache.Clear(); + add(0xE000 + line - 8, 16, 0xAA); + add(0xE000 + line, line, 0xBB); + expect_l1({{0xE000 + line - 8, 8, 0xAA}}); + expect_l2({{0xE000 + line, line, 0xBB}}); } TEST_F(MemoryTest, TestReadStopsAtAnInvalidRange) { @@ -464,7 +548,6 @@ TEST_F(MemoryTest, TestReadStopsAtAnInvalidRange) { ASSERT_TRUE(proc.GetProcess()); DummyProcess *process = proc.GetProcess(); MemoryCache &cache = process->GetMemoryCache(); - const lldb::addr_t line = process->GetMemoryCacheLineSize(); const lldb::addr_t base = 0xE000; cache.AddInvalidRange(base + 16, 16); @@ -480,11 +563,11 @@ TEST_F(MemoryTest, TestReadStopsAtAnInvalidRange) { EXPECT_TRUE(error.Fail()); EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).take_front(16), 0xBB)); - // The whole aligned line is still fetched, crossing the invalid range, even - // though only the 16 bytes below it may be served. + // The request stops where the invalid range starts, so the unreadable bytes + // are never asked for. ASSERT_EQ(process->m_reads.size(), 1u); EXPECT_EQ(process->m_reads[0].first, base); - EXPECT_EQ(process->m_reads[0].second, line); + EXPECT_EQ(process->m_reads[0].second, 16u); // A read starting inside the range has nothing to serve. Status inside_error; @@ -502,8 +585,22 @@ TEST_F(MemoryTest, TestReadRangesFromCaches) { DummyProcess *process = proc.GetProcess(); const uint64_t line_size = proc.GetLineSize(); + { // ReadRanges serves a range one entry covers. + const lldb::addr_t base = 0x6000 + line_size - 10; + process->GetMemoryCache().AddCacheData( + base, std::make_shared<DataBufferHeap>(10 + line_size, 0xAA)); + process->SetMaxReadSize(0); + llvm::SmallVector<uint8_t, 0> buffer(20, 0); + llvm::SmallVector<Range<addr_t, size_t>> ranges = {{base, 20}}; + llvm::SmallVector<llvm::MutableArrayRef<uint8_t>> results = + process->ReadMemoryRanges(ranges, buffer); + ASSERT_EQ(results.size(), 1u); + ASSERT_EQ(results[0].size(), 20u); + EXPECT_TRUE(AllBytesAre(results[0], 0xAA)); + } + { // An entry serves a range only if it covers it all. A short fetch is all - // the caller sees and all L1 keeps of the range it was for. + // the caller sees, and adds to L1 only the bytes no entry holds. TestMemoryCache cache(*process); AddCacheChunk(cache, 0xB000, 40, 0xAA); AddCacheChunk(cache, 0xC000, 8, 0xCC); @@ -527,17 +624,17 @@ TEST_F(MemoryTest, TestReadRangesFromCaches) { EXPECT_EQ(process->m_reads[1].first, 0xB000u + 20u); EXPECT_EQ(process->m_reads[1].second, 64u - 20u); - ASSERT_EQ(cache.GetL1Cache().size(), 2u); - EXPECT_EQ(cache.GetL1Cache().count(0xB000), 1u); - EXPECT_EQ(cache.GetL1Cache().count(0xC000), 1u); - - auto l1cache_line = cache.GetL1Cache().at(0xB000); - // was 40 bytes of 0xAA - EXPECT_EQ(l1cache_line->GetByteSize(), 20u); - EXPECT_TRUE(AllBytesAre(l1cache_line->GetData(), 0xBB)); - l1cache_line = cache.GetL1Cache().at(0xC000); - EXPECT_EQ(l1cache_line->GetByteSize(), 8u); - EXPECT_TRUE(AllBytesAre(l1cache_line->GetData(), 0xCC)); + ASSERT_EQ(cache.GetL1Cache().GetSize(), 2u); + const auto l1_chunks = Snapshot(cache.GetL1Cache()); + ASSERT_EQ(l1_chunks.size(), 2u); + EXPECT_EQ(l1_chunks[0].first, 0xB000u); + EXPECT_EQ(l1_chunks[1].first, 0xC000u); + + // The fetch's 20 bytes are all held already, so the chunk is unchanged. + EXPECT_EQ(l1_chunks[0].second.size(), 40u); + EXPECT_TRUE(AllBytesAre(l1_chunks[0].second, 0xAA)); + EXPECT_EQ(l1_chunks[1].second.size(), 8u); + EXPECT_TRUE(AllBytesAre(l1_chunks[1].second, 0xCC)); } { // A range ReadRanges fetched is cached, so asking for it again serves it @@ -598,12 +695,36 @@ TEST_F(MemoryTest, TestReadRequestShape) { DummyProcess *process = proc.GetProcess(); const uint64_t line_size = proc.GetLineSize(); - { // A read longer than a line that L1 cannot serve whole goes to the inferior - // as one request for the whole range. + { // The request starts at the cache entry, but longer than the cache entry. + TestMemoryCache cache(*process); + Status error; + const lldb::addr_t base = 0x14000; + + // v base v base + line + // cache:|AAAAAAAAAAAAAAAA| + // process:|BBBBBBBBBBBBBBBB|BBBBBBBBBBBBBBB| + // buf :|AAAAAAAAAAAAAAAA|BBB| + // ^ base + line + 88 + AddCacheChunk(cache, base, 256, 0xAA); + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xBB); + process->m_reads.clear(); + std::vector<uint8_t> buf(line_size + 88, 0); + EXPECT_EQ(cache.Read(base, buf.data(), buf.size(), error), buf.size()); + EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).take_front(256), 0xAA)); + EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).drop_front(256), 0xBB)); + // One request, from the first missing byte to the second line's end. + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, base + 256); + EXPECT_EQ(process->m_reads[0].second, 2 * line_size - 256); + } + + { // A read longer than a line that cache cannot serve, read the rest from the + // inferior. // v base v base + line_size // cache: |AAAAAAAAAAAAAA|AA| // process:|BBBBBBBBBBBBBB|BBBBBBBBBBBB|BBBBBBBBBBBB| - // buf: |BBBBBBBBBBBBBB|BBBBBBBBBBBB|BBBBBBBBBBBB| + // buf: |AAAAAAAAAAAAAA|AABBBBBBBBBB|BBBBBBBBBBBB| TestMemoryCache cache(*process); Status error; const lldb::addr_t base = 0x15000; @@ -614,11 +735,14 @@ TEST_F(MemoryTest, TestReadRequestShape) { process->m_reads.clear(); std::vector<uint8_t> buf(3 * line_size, 0); ASSERT_EQ(cache.Read(base, buf.data(), buf.size(), error), buf.size()); - EXPECT_TRUE(AllBytesAre(buf, 0xBB)); - // One request, for exactly what the caller asked. + EXPECT_TRUE( + AllBytesAre(llvm::ArrayRef(buf).take_front(line_size + 8), 0xAA)); + EXPECT_TRUE( + AllBytesAre(llvm::ArrayRef(buf).drop_front(line_size + 8), 0xBB)); + // One request, starting past the cached prefix and covering only the rest. ASSERT_EQ(process->m_reads.size(), 1u); - EXPECT_EQ(process->m_reads[0].first, base); - EXPECT_EQ(process->m_reads[0].second, buf.size()); + EXPECT_EQ(process->m_reads[0].first, base + line_size + 8); + EXPECT_EQ(process->m_reads[0].second, 2 * line_size - 8); // Cached where it was read from, so the same read now sends nothing and // returns the same bytes. @@ -630,32 +754,313 @@ TEST_F(MemoryTest, TestReadRequestShape) { EXPECT_EQ(again, buf); EXPECT_TRUE(process->m_reads.empty()); } + + { // Data split across L1 and L2 stitches back together. The counting + // pattern catches an offset error a uniform fill would hide. + TestMemoryCache cache(*process); + Status error; + const lldb::addr_t base = 0x11000 + line_size - 7; + const size_t size = 7 + 2 * line_size + 5; + auto byte_at = [](size_t i) { return static_cast<uint8_t>(i * 7 + 1); }; + auto pattern = std::make_shared<DataBufferHeap>(size, 0); + for (size_t i = 0; i < size; ++i) + pattern->GetBytes()[i] = byte_at(i); + cache.AddCacheData(base, pattern); + + // One remainder on each side and two whole lines between them. + ASSERT_EQ(cache.GetL1Cache().GetSize(), 2u); + ASSERT_EQ(cache.GetL2Cache().GetSize(), 2u); + + process->SetMaxReadSize(0); + std::vector<uint8_t> buf(size, 0); + ASSERT_EQ(cache.Read(base, buf.data(), buf.size(), error), size); + for (size_t i = 0; i < size; ++i) + ASSERT_EQ(buf[i], byte_at(i)) << "byte " << i; + + // A read starting inside an entry, which a read at its base cannot check. + auto expect_at = [&](size_t offset, size_t len, const char *what) { + SCOPED_TRACE(what); + std::vector<uint8_t> got(len, 0); + ASSERT_EQ(cache.Read(base + offset, got.data(), got.size(), error), len); + for (size_t i = 0; i < len; ++i) + ASSERT_EQ(got[i], byte_at(offset + i)) << "byte " << i; + }; + + expect_at(3, 4, "inside the leading L1 remainder"); + expect_at(7 + 9, 8, "inside the first whole line"); + expect_at(7 - 2, 8, "across the remainder into the line"); + } + + { // A short read must not hide cached bytes that start where it stopped. The + // count is taken from the caches, not from what the inferior returned. + // v base v base+300 + // cache: |CC| + // buf:|AAAAAAAAAAACC| + // ^ base+310 + TestMemoryCache cache(*process); + Status error; + const lldb::addr_t base = 0x18000; + + AddCacheChunk(cache, base + 300, 10, 0xCC); + process->SetMaxReadSize(300); + process->SetFiller(0xAA); + std::vector<uint8_t> buf(600, 0); + EXPECT_EQ(cache.Read(base, buf.data(), buf.size(), error), 310u); + EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).take_front(300), 0xAA)); + EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).slice(300, 10), 0xCC)); + } + + { // A read at an expedited chunk must not reach the inferior once a larger + // read already covers it. + // v fp-line v fp v fp+line + // cache: |AAAA| + // buf: |BBBBBBBBB| + TestMemoryCache cache(*process); + Status error; + const lldb::addr_t fp = 0xF000 + line_size; + cache.AddCacheData(fp, std::make_shared<DataBufferHeap>(16, 0xAA)); + + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xBB); + std::vector<uint8_t> big(2 * line_size, 0); + ASSERT_EQ(cache.Read(fp - line_size, big.data(), big.size(), error), + big.size()); + + process->SetMaxReadSize(0); + process->m_reads.clear(); + std::vector<uint8_t> out(32, 0); + EXPECT_EQ(cache.Read(fp, out.data(), out.size(), error), out.size()); + EXPECT_TRUE(AllBytesAre(out, 0xBB)); + EXPECT_TRUE(process->m_reads.empty()); + } +} + +// A read straddling two lines fetches whole lines, so both land in L2 and +// a later read of either hits. +TEST_F(MemoryTest, TestReadStraddlingTwoLines) { + CacheTestProcess proc; + ASSERT_TRUE(proc.GetProcess()); + DummyProcess *process = proc.GetProcess(); + const uint64_t line_size = proc.GetLineSize(); + const lldb::addr_t first = 0x20000; + const lldb::addr_t second = first + line_size; + + { // Neither line cached: both are fetched whole, in one request. + TestMemoryCache cache(*process); + Status error; + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + + std::vector<uint8_t> buf(16, 0); + EXPECT_EQ(cache.Read(second - 8, buf.data(), buf.size(), error), + buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, first); + EXPECT_EQ(process->m_reads[0].second, 2 * line_size); + EXPECT_TRUE(cache.GetL2Cache().Holds(first)); + EXPECT_TRUE(cache.GetL2Cache().Holds(second)); + + process->m_reads.clear(); + std::vector<uint8_t> again(8, 0); + EXPECT_EQ(cache.Read(first, again.data(), again.size(), error), + again.size()); + EXPECT_TRUE(process->m_reads.empty()); + } + + { // The second line is already in L2, only the first is missing, so only + // that one is fetched and the second is not sent again. + TestMemoryCache cache(*process); + Status error; + std::vector<uint8_t> whole(line_size, 0xBB); + cache.AddCacheData(second, whole.data(), whole.size()); + ASSERT_TRUE(cache.GetL2Cache().Holds(second)); + + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + std::vector<uint8_t> buf(16, 0); + EXPECT_EQ(cache.Read(second - 8, buf.data(), buf.size(), error), + buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, first); + EXPECT_EQ(process->m_reads[0].second, line_size); + // The tail of the request came out of the line that was already there. + EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).take_front(8), 0xAA)); + EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).drop_front(8), 0xBB)); + } + + { // A short second line does not count as present: skipping it would leave a + // hole, so both lines are fetched. + TestMemoryCache cache(*process); + Status error; + std::vector<uint8_t> partial(line_size / 2, 0xBB); + cache.AddCacheData(second, partial.data(), partial.size()); + + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + std::vector<uint8_t> buf(16, 0); + EXPECT_EQ(cache.Read(second - 8, buf.data(), buf.size(), error), + buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].second, 2 * line_size); + EXPECT_EQ(cache.GetL2Cache().GetSize(), 2u); + EXPECT_EQ(cache.GetL1Cache().GetSize(), 0u); + } + + { // A request longer than a line still grows when it fits in the two lines it + // touches. + TestMemoryCache cache(*process); + Status error; + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + + std::vector<uint8_t> buf(line_size + 4, 0); + EXPECT_EQ(cache.Read(first, buf.data(), buf.size(), error), buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, first); + EXPECT_EQ(process->m_reads[0].second, 2 * line_size); + EXPECT_TRUE(cache.GetL2Cache().Holds(first)); + EXPECT_TRUE(cache.GetL2Cache().Holds(second)); + + process->m_reads.clear(); + std::vector<uint8_t> again(8, 0); + EXPECT_EQ( + cache.Read(second + line_size - 8, again.data(), again.size(), error), + again.size()); + EXPECT_TRUE(process->m_reads.empty()); + } + + { // A request reaching a third line is read as asked. + // v first v first+line v fist+2*line + // cache:| | | + // buf: | | | + // ^ first+8 ^first+8+2*line + TestMemoryCache cache(*process); + Status error; + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + + std::vector<uint8_t> buf(2 * line_size, 0); + EXPECT_EQ(cache.Read(first + 8, buf.data(), buf.size(), error), buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, first + 8); + EXPECT_EQ(process->m_reads[0].second, 2 * line_size); + } + + { + TestMemoryCache cache(*process); + Status error; + std::vector<uint8_t> held(8, 0xCC); + cache.AddCacheData(first, held.data(), held.size()); + + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + std::vector<uint8_t> buf(line_size + 4, 0); + EXPECT_EQ(cache.Read(first, buf.data(), buf.size(), error), buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + // A prefix served from the caches stops the straddle arm growing down. + EXPECT_EQ(process->m_reads[0].first, first + 8); + EXPECT_TRUE(AllBytesAre(llvm::ArrayRef(buf).take_front(8), 0xCC)); + } +} + +TEST_F(MemoryTest, TestReadGrowthAgainstInvalidRanges) { + CacheTestProcess proc; + ASSERT_TRUE(proc.GetProcess()); + DummyProcess *process = proc.GetProcess(); + const uint64_t line_size = proc.GetLineSize(); + const lldb::addr_t first = 0x30000; + const lldb::addr_t second = first + line_size; + + { // An invalid range below the read, ending inside the line. + TestMemoryCache cache(*process); + Status error; + cache.AddInvalidRange(first, 0x100); + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + + std::vector<uint8_t> buf(16, 0); + EXPECT_EQ(cache.Read(first + 0x180, buf.data(), buf.size(), error), + buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, first + 0x180); + EXPECT_EQ(process->m_reads[0].second, line_size - 0x180); + } + + { // An invalid range in the bytes growth adds above, inside the same line. + TestMemoryCache cache(*process); + Status error; + cache.AddInvalidRange(first + 0x180, 0x80); + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + + std::vector<uint8_t> buf(16, 0); + EXPECT_EQ(cache.Read(first + 0x100, buf.data(), buf.size(), error), + buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, first); + EXPECT_EQ(process->m_reads[0].second, 0x180u); + } + + { // An invalid range in the second line, which growth would add: the request + // stops below it. + TestMemoryCache cache(*process); + Status error; + cache.AddInvalidRange(second + 0x100, 0x80); + process->SetMaxReadSize(4 * line_size); + process->SetFiller(0xAA); + process->m_reads.clear(); + + std::vector<uint8_t> buf(16, 0); + EXPECT_EQ(cache.Read(second - 8, buf.data(), buf.size(), error), + buf.size()); + ASSERT_EQ(process->m_reads.size(), 1u); + EXPECT_EQ(process->m_reads[0].first, first); + EXPECT_EQ(process->m_reads[0].second, line_size + 0x100); + } } // A flushed range whose end wraps past UINT64_MAX must stop at the top line. -// FIXME: a range whose end wraps past UINT64_MAX leaves the wrapped lines -// cached. TEST_F(MemoryTest, TestFlushAtTheTopOfTheAddressSpace) { CacheTestProcess proc; ASSERT_TRUE(proc.GetProcess()); DummyProcess *process = proc.GetProcess(); const uint64_t line_size = proc.GetLineSize(); const lldb::addr_t top_line = UINT64_MAX - line_size + 1; + const lldb::addr_t line_below_top = top_line - line_size; - // Only L2 is walked line by line, so seed it by reading. The line at 0 is - // the one a wrap would reach first. TestMemoryCache cache(*process); Status error; process->SetMaxReadSize(4 * line_size); - std::vector<uint8_t> buf(8, 0); + std::vector<uint8_t> buf(line_size, 0); cache.Read(top_line, buf.data(), buf.size(), error); cache.Read(0, buf.data(), buf.size(), error); - ASSERT_EQ(cache.GetL2Cache().size(), 2u); + ASSERT_EQ(cache.GetL2Cache().GetSize(), 2u); + ASSERT_TRUE(cache.GetL2Cache().Holds(top_line)); // This range ends past UINT64_MAX. cache.Flush(UINT64_MAX - 8, 100); - EXPECT_EQ(cache.GetL2Cache().count(top_line), 0u); - EXPECT_EQ(cache.GetL2Cache().count(0), 1u); + EXPECT_FALSE(cache.GetL2Cache().Holds(top_line)); + EXPECT_TRUE(cache.GetL2Cache().Holds(0)); + + { // A one-byte flush of the last byte covers only the topmost line, so it + // must not reach the line below it. + TestMemoryCache cache(*process); + cache.AddCacheData(line_below_top, buf.data(), buf.size()); + cache.AddCacheData(top_line, buf.data(), buf.size()); + ASSERT_EQ(cache.GetL2Cache().GetSize(), 2u); + + cache.Flush(UINT64_MAX, 1); + EXPECT_FALSE(cache.GetL2Cache().Holds(top_line)); + EXPECT_TRUE(cache.GetL2Cache().Holds(line_below_top)); + } } // The cache copies raw bytes, which have no buffer behind them to retain. @@ -667,8 +1072,8 @@ TEST_F(MemoryTest, TestCacheCopiesRawBytes) { TestMemoryCache cache(*process); std::vector<uint8_t> raw(16, 0xAA); cache.AddCacheData(0x5000, raw.data(), raw.size()); - ASSERT_EQ(cache.GetL1Cache().count(0x5000), 1u); - EXPECT_NE(cache.GetL1Cache().at(0x5000)->GetBytes(), raw.data()); + ASSERT_TRUE(cache.GetL1Cache().Holds(0x5000)); + EXPECT_NE(cache.GetL1Cache().Lookup(0x5000).data(), raw.data()); // Editing the caller's bytes must not change what the cache returns, and the // inferior supplies nothing, so every byte read came from the cache. @@ -676,6 +1081,7 @@ TEST_F(MemoryTest, TestCacheCopiesRawBytes) { process->SetMaxReadSize(0); std::vector<uint8_t> out(16, 0); EXPECT_EQ(cache.Read(0x5000, out.data(), out.size(), error), out.size()); + ASSERT_TRUE(process->m_reads.empty()); EXPECT_TRUE(AllBytesAre(out, 0xAA)); } @@ -1040,7 +1446,7 @@ TEST_F(MemoryDeathTest, TestReadRangesWithShortBufferAndCacheHit) { DummyProcess *process = static_cast<DummyProcess *>(process_sp.get()); TestMemoryCache cache(*process); cache.AddCacheData(0x1000, std::make_shared<DataBufferHeap>(16, 0xAA)); - ASSERT_EQ(cache.GetL1Cache().count(0x1000), 1u); + ASSERT_TRUE(cache.GetL1Cache().Holds(0x1000)); llvm::SmallVector<uint8_t, 0> short_buffer(8, 0); llvm::SmallVector<Range<addr_t, size_t>> ranges = {{0x1000, 16}}; >From 0696296cf5fc32165edb1bc3aa3b2334cbc6b0d0 Mon Sep 17 00:00:00 2001 From: Yao Qi <[email protected]> Date: Fri, 11 Sep 2026 21:52:32 +0100 Subject: [PATCH 3/5] Fixup --- lldb/include/lldb/Target/Memory.h | 17 ++++++++--------- lldb/source/Target/Memory.cpp | 19 ++++++------------- 2 files changed, 14 insertions(+), 22 deletions(-) diff --git a/lldb/include/lldb/Target/Memory.h b/lldb/include/lldb/Target/Memory.h index fbc5fe93a99de..c874a8456b200 100644 --- a/lldb/include/lldb/Target/Memory.h +++ b/lldb/include/lldb/Target/Memory.h @@ -21,10 +21,10 @@ namespace lldb_private { -/// A set of whole, aligned cache lines, keyed by line index. A key names a -/// whole line, so no entry can be partial or unaligned and no length is -/// stored per entry. +/// A set of cache entries, all of which are aligned and have the same size. +/// Entries cannot be partially filled. class LineCache { + /// Keyed by line index, so a key names a whole line. using Collection = llvm::DenseMap<uint64_t, std::unique_ptr<uint8_t[]>>; public: @@ -119,7 +119,7 @@ class MemoryCache { size_t Read(lldb::addr_t addr, void *dst, size_t dst_len, Status &error); /// Reads memory ranges, serving hits from the cache and batching misses - /// through Process::DoReadMemoryRanges. Matches Process::ReadMemoryRanges. + /// through Process::DoReadMemoryRanges. Matches Process::ReadMemoryRanges. llvm::SmallVector<llvm::MutableArrayRef<uint8_t>> ReadRanges(llvm::ArrayRef<Range<lldb::addr_t, size_t>> ranges, llvm::MutableArrayRef<uint8_t> buffer); @@ -148,7 +148,7 @@ class MemoryCache { typedef Range<lldb::addr_t, lldb::addr_t> AddrRange; // Classes that inherit from MemoryCache can see and modify these std::recursive_mutex m_mutex; - // L1 and L2 partition the cache. An address is held by at most one. L2 + // L1 and L2 partition the cache. An address is held by at most one. L2 // holds whole, aligned lines; L1 holds smaller, non-overlapping pieces. ChunkCache m_L1_cache; // Chunks smaller than a cache line. LineCache m_L2_cache; // Whole cache lines. @@ -176,10 +176,9 @@ class MemoryCache { // and return the count. Never reads from the inferior; caller holds m_mutex. size_t ReadFromCaches(lldb::addr_t addr, void *dst, size_t len) const; - // The range to fetch for a read that ends at caller_end and whose first - // bytes_filled bytes the caches supplied, so read_addr is the first byte - // none of them holds. Grown to whole cache lines where that costs nothing, - // and clipped at an invalid range. Caller must hold m_mutex. + // Returns the range to fetch from the inferior for a read of + // [read_addr, caller_end), where the caches already supplied bytes_filled + // bytes immediately below read_addr. Caller must hold m_mutex. AddrRange GrowReadRange(lldb::addr_t read_addr, lldb::addr_t caller_end, size_t bytes_filled) const; }; diff --git a/lldb/source/Target/Memory.cpp b/lldb/source/Target/Memory.cpp index 45362c0cdee50..0efb7bbed102f 100644 --- a/lldb/source/Target/Memory.cpp +++ b/lldb/source/Target/Memory.cpp @@ -46,7 +46,6 @@ void LineCache::Insert(addr_t addr, llvm::ArrayRef<uint8_t> src) { void LineCache::EraseRange(addr_t addr, addr_t size) { if (size == 0) return; - // Clamp a range running past the end of the address space to it. const addr_t end_addr = llvm::SaturatingAdd(addr, size - 1); const uint64_t first_idx = IndexOf(addr); const uint64_t last_idx = IndexOf(end_addr); @@ -57,18 +56,17 @@ void LineCache::EraseRange(addr_t addr, addr_t size) { ChunkCache::Collection::const_iterator ChunkCache::FindChunkContaining(addr_t addr) const { - if (m_chunks.empty()) - return m_chunks.end(); - Collection::const_iterator pos = m_chunks.upper_bound(addr); + auto pos = m_chunks.upper_bound(addr); if (pos == m_chunks.begin()) return m_chunks.end(); --pos; - // Sum pos->first + size wraps at the top of the address space. + // pos->first + size would overflow for a chunk at the top of the address + // space, do subtraction instead. return addr - pos->first < pos->second.size() ? pos : m_chunks.end(); } llvm::ArrayRef<uint8_t> ChunkCache::Lookup(addr_t addr) const { - const Collection::const_iterator pos = FindChunkContaining(addr); + auto pos = FindChunkContaining(addr); if (pos == m_chunks.end()) return {}; return llvm::ArrayRef(pos->second).drop_front(addr - pos->first); @@ -77,8 +75,6 @@ llvm::ArrayRef<uint8_t> ChunkCache::Lookup(addr_t addr) const { void ChunkCache::InsertMissing(addr_t addr, llvm::ArrayRef<uint8_t> src) { if (src.empty()) return; - // The last addressable byte of the range, clamped if it runs past the end of - // the address space. const addr_t last_addr = llvm::SaturatingAdd<addr_t>(addr, src.size() - 1); const uint64_t len = last_addr - addr + 1; @@ -89,7 +85,7 @@ void ChunkCache::InsertMissing(addr_t addr, llvm::ArrayRef<uint8_t> src) { continue; } // Nothing holds curr_addr, so the gap runs to the next chunk or to the end. - const Collection::const_iterator next = m_chunks.lower_bound(curr_addr); + auto next = m_chunks.lower_bound(curr_addr); const uint64_t gap_len = next == m_chunks.end() ? len - offset @@ -103,7 +99,6 @@ void ChunkCache::InsertMissing(addr_t addr, llvm::ArrayRef<uint8_t> src) { void ChunkCache::EraseRange(addr_t addr, addr_t size) { if (size == 0) return; - // Clamp a range running past the end of the address space to it. const addr_t end_addr = llvm::SaturatingAdd(addr, size - 1); Collection::iterator pos = m_chunks.lower_bound(addr); @@ -157,13 +152,11 @@ void MemoryCache::InsertPartialLine(addr_t addr, llvm::ArrayRef<uint8_t> src) { m_L1_cache.InsertMissing(addr, src); } -void MemoryCache::InsertData(lldb::addr_t addr, llvm::ArrayRef<uint8_t> src) { +void MemoryCache::InsertData(addr_t addr, llvm::ArrayRef<uint8_t> src) { if (src.empty()) return; std::lock_guard<std::recursive_mutex> guard(m_mutex); - // The last addressable byte of the range, clamped if it runs past the end of - // the address space, so no offset added to addr can wrap to 0. const addr_t last_addr = llvm::SaturatingAdd<addr_t>(addr, src.size() - 1); const uint64_t len = last_addr - addr + 1; const uint32_t line_size = m_L2_cache.GetLineByteSize(); >From b5058e8dae6d25140a0c4e1d9fab521d9761fed7 Mon Sep 17 00:00:00 2001 From: Yao Qi <[email protected]> Date: Fri, 11 Sep 2026 21:59:55 +0100 Subject: [PATCH 4/5] Fixup --- lldb/source/Target/Memory.cpp | 31 +++++++++++++++++++------------ 1 file changed, 19 insertions(+), 12 deletions(-) diff --git a/lldb/source/Target/Memory.cpp b/lldb/source/Target/Memory.cpp index 0efb7bbed102f..e48f29d9099c1 100644 --- a/lldb/source/Target/Memory.cpp +++ b/lldb/source/Target/Memory.cpp @@ -158,21 +158,28 @@ void MemoryCache::InsertData(addr_t addr, llvm::ArrayRef<uint8_t> src) { std::lock_guard<std::recursive_mutex> guard(m_mutex); const addr_t last_addr = llvm::SaturatingAdd<addr_t>(addr, src.size() - 1); - const uint64_t len = last_addr - addr + 1; + src = src.take_front(last_addr - addr + 1); const uint32_t line_size = m_L2_cache.GetLineByteSize(); - for (uint64_t offset = 0; offset < len;) { - const addr_t curr_addr = addr + offset; - const uint64_t line_offset = curr_addr % line_size; - const uint64_t piece_len = - std::min<uint64_t>(line_size - line_offset, len - offset); - const llvm::ArrayRef<uint8_t> piece_bytes = src.slice(offset, piece_len); - if (line_offset == 0 && piece_len == line_size) - InsertWholeLine(curr_addr, piece_bytes); - else - InsertPartialLine(curr_addr, piece_bytes); - offset += piece_len; + // A leading piece, up to the first line boundary. + if (const uint64_t line_offset = addr % line_size) { + const uint64_t head_len = + std::min<uint64_t>(line_size - line_offset, src.size()); + InsertPartialLine(addr, src.take_front(head_len)); + addr += head_len; + src = src.drop_front(head_len); } + + // Whole, aligned lines. + while (src.size() >= line_size) { + InsertWholeLine(addr, src.take_front(line_size)); + addr += line_size; + src = src.drop_front(line_size); + } + + // A trailing piece, shorter than a line. + if (!src.empty()) + InsertPartialLine(addr, src); } void MemoryCache::AddCacheData(lldb::addr_t addr, >From af85fad2183d03244df890a90df9fefb4d7d9fa2 Mon Sep 17 00:00:00 2001 From: Yao Qi <[email protected]> Date: Mon, 14 Sep 2026 09:43:35 +0100 Subject: [PATCH 5/5] Fixup: use auto in ChunkCache::EraseRange --- lldb/source/Target/Memory.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/lldb/source/Target/Memory.cpp b/lldb/source/Target/Memory.cpp index e48f29d9099c1..c7f58c8e52bb4 100644 --- a/lldb/source/Target/Memory.cpp +++ b/lldb/source/Target/Memory.cpp @@ -101,10 +101,10 @@ void ChunkCache::EraseRange(addr_t addr, addr_t size) { return; const addr_t end_addr = llvm::SaturatingAdd(addr, size - 1); - Collection::iterator pos = m_chunks.lower_bound(addr); + auto pos = m_chunks.lower_bound(addr); // A chunk starting below addr can still reach into the range. if (pos != m_chunks.begin()) { - const Collection::iterator prev = std::prev(pos); + auto prev = std::prev(pos); if (addr - prev->first < prev->second.size()) m_chunks.erase(prev); } _______________________________________________ lldb-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
