================
@@ -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;) {
----------------
felipepiovezan wrote:
Feel free to push back on this, but the way I was expecting this algorithm to
be written was:
1. One insertion of an unaligned chunk
2. A sequence of insertions of aligned chunks
3. One insertion of an unaligned chunk
https://github.com/llvm/llvm-project/pull/222688
_______________________________________________
lldb-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
