llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-lldb Author: Felipe de Azevedo Piovezan (felipepiovezan) <details> <summary>Changes</summary> The RangeVector abstraction is slow w.r.t. amount of sorting it requires, and it is particularly bad when sorting a MemoryRegionInfo, as this object is expensive to move. All of this is aggravated in sanitizer bots, where a handful of tests started timing out as a result of the MemoryRegionInfoCache. This commit fixes the situation by simplifying the code: just use a std::map. Based on current usage, behaviour should be identical to before. In particular, neither case addresses cases like this: 1. Insert range [100, 200] 2. Insert range [150, 160] 3. Query address 170. In both cases we fail to find a cached range and proceed to query the inferior again. Which is not incorrect, jut doesn't maximize the cache usage. A proper fix is to use an interval tree, with the assumption that if overlapping ranges are inserted, they have the same memory region info contents and we can just join the intervals. --- Full diff: https://github.com/llvm/llvm-project/pull/206986.diff 2 Files Affected: - (modified) lldb/include/lldb/Target/MemoryRegionInfoCache.h (+3-6) - (modified) lldb/source/Target/MemoryRegionInfoCache.cpp (+9-14) ``````````diff diff --git a/lldb/include/lldb/Target/MemoryRegionInfoCache.h b/lldb/include/lldb/Target/MemoryRegionInfoCache.h index 538d01f5fb81f..5117f1f598e55 100644 --- a/lldb/include/lldb/Target/MemoryRegionInfoCache.h +++ b/lldb/include/lldb/Target/MemoryRegionInfoCache.h @@ -10,15 +10,15 @@ #define LLDB_TARGET_MEMORYREGIONINFOCACHE_H #include "lldb/Target/MemoryRegionInfo.h" -#include "lldb/Utility/RangeMap.h" +#include <map> #include <mutex> #include <optional> namespace lldb_private { class MemoryRegionInfoCache { public: - MemoryRegionInfoCache() : m_region_infos(), m_is_sorted(true), m_mutex() {} + MemoryRegionInfoCache() = default; /// Remove all cached entries. Should be called whenever /// Process resumes execution of the inferior. @@ -34,10 +34,7 @@ class MemoryRegionInfoCache { size_t GetSize(); private: - typedef RangeDataVector<lldb::addr_t, size_t, lldb_private::MemoryRegionInfo> - InfoMap; - InfoMap m_region_infos; - bool m_is_sorted; + std::map<lldb::addr_t, MemoryRegionInfo> m_region_infos; std::mutex m_mutex; }; } // namespace lldb_private diff --git a/lldb/source/Target/MemoryRegionInfoCache.cpp b/lldb/source/Target/MemoryRegionInfoCache.cpp index 4adaf20227910..47694b3ad58fc 100644 --- a/lldb/source/Target/MemoryRegionInfoCache.cpp +++ b/lldb/source/Target/MemoryRegionInfoCache.cpp @@ -14,33 +14,28 @@ using namespace lldb_private; void MemoryRegionInfoCache::Clear() { std::lock_guard<std::mutex> guard(m_mutex); - m_region_infos.Clear(); - m_is_sorted = true; + m_region_infos.clear(); } size_t MemoryRegionInfoCache::GetSize() { std::lock_guard<std::mutex> guard(m_mutex); - return m_region_infos.GetSize(); + return m_region_infos.size(); } std::optional<MemoryRegionInfo> MemoryRegionInfoCache::GetMemoryRegion(addr_t load_addr) { std::lock_guard<std::mutex> guard(m_mutex); - if (!m_is_sorted) { - m_region_infos.Sort(); - m_is_sorted = true; - } - uint32_t index = m_region_infos.FindEntryIndexThatContains(load_addr); - if (index != UINT32_MAX) - return m_region_infos.GetEntryAtIndex(index)->data; + auto it = m_region_infos.upper_bound(load_addr); + if (it == m_region_infos.begin()) + return std::nullopt; + --it; + if (load_addr < it->second.GetRange().GetRangeEnd()) + return it->second; return std::nullopt; } void MemoryRegionInfoCache::AddRegion(const MemoryRegionInfo &ri) { std::lock_guard<std::mutex> guard(m_mutex); - InfoMap::Entry new_entry(ri.GetRange().GetRangeBase(), - ri.GetRange().GetByteSize(), ri); - m_region_infos.Append(new_entry); - m_is_sorted = false; + m_region_infos.insert_or_assign(ri.GetRange().GetRangeBase(), ri); } `````````` </details> https://github.com/llvm/llvm-project/pull/206986 _______________________________________________ lldb-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
