================
@@ -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>>;
----------------
qiyao wrote:
These two caches are used differently, so they have different data structure.
`LineCache` is keyed by line index, so every lookup is an exact `find` and
every entry is exactly one line long. A per-entry length would be redundant,
so `unique_ptr<uint8_t[]>` is enough and it saves `vector`'s size and capacity
fields. Nothing in L2 needs ordering, which is why the iterator doc says the
order is unspecified: with `DenseMap` that is compiler-enforced rather than a
property of the call sites.
`ChunkCache` is keyed by an arbitrary start address and its entries vary in
length, so a length has to be stored somewhere and `vector` already carries
one. Its lookup is "which chunk contains this address", which no exact `find`
can answer. `FindChunkContaining` needs `upper_bound`, the gap
walk in `InsertMissing` needs `lower_bound`, and `EraseRange` needs
`lower_bound` plus ordered erase. `DenseMap` has none of those.
The container follows from the queries, and the value type follows from the
key type.
https://github.com/llvm/llvm-project/pull/222688
_______________________________________________
lldb-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
