NVDRV: Refactor HeapMapper to use RangeSets

1 files changed, 43 insertions, 144 deletions

diff --git a/src/core/hle/service/nvdrv/core/heap_mapper.cpp b/src/core/hle/service/nvdrv/core/heap_mapper.cpp
index 096dc5deb..542125a1c 100644
--- a/src/core/hle/service/nvdrv/core/heap_mapper.cpp
+++ b/src/core/hle/service/nvdrv/core/heap_mapper.cpp
@@ -3,110 +3,21 @@
 
 #include <mutex>
 
-#include <boost/container/small_vector.hpp>
-#define BOOST_NO_MT
-#include <boost/pool/detail/mutex.hpp>
-#undef BOOST_NO_MT
-#include <boost/icl/interval.hpp>
-#include <boost/icl/interval_base_set.hpp>
-#include <boost/icl/interval_set.hpp>
-#include <boost/icl/split_interval_map.hpp>
-#include <boost/pool/pool.hpp>
-#include <boost/pool/pool_alloc.hpp>
-#include <boost/pool/poolfwd.hpp>
-
+#include "common/range_sets.h"
+#include "common/range_sets.inc"
 #include "core/hle/service/nvdrv/core/heap_mapper.h"
 #include "video_core/host1x/host1x.h"
 
-namespace boost {
-template <typename T>
-class fast_pool_allocator<T, default_user_allocator_new_delete, details::pool::null_mutex, 4096, 0>;
-}
-
 namespace Service::Nvidia::NvCore {
 
-using IntervalCompare = std::less<DAddr>;
-using IntervalInstance = boost::icl::interval_type_default<DAddr, std::less>;
-using IntervalAllocator = boost::fast_pool_allocator<DAddr>;
-using IntervalSet = boost::icl::interval_set<DAddr>;
-using IntervalType = typename IntervalSet::interval_type;
-
-template <typename Type>
-struct counter_add_functor : public boost::icl::identity_based_inplace_combine<Type> {
-    // types
-    typedef counter_add_functor<Type> type;
-    typedef boost::icl::identity_based_inplace_combine<Type> base_type;
-
-    // public member functions
-    void operator()(Type& current, const Type& added) const {
-        current += added;
-        if (current < base_type::identity_element()) {
-            current = base_type::identity_element();
-        }
-    }
-
-    // public static functions
-    static void version(Type&){};
-};
-
-using OverlapCombine = counter_add_functor<int>;
-using OverlapSection = boost::icl::inter_section<int>;
-using OverlapCounter = boost::icl::split_interval_map<DAddr, int>;
-
 struct HeapMapper::HeapMapperInternal {
-    HeapMapperInternal(Tegra::Host1x::Host1x& host1x) : device_memory{host1x.MemoryManager()} {}
+    HeapMapperInternal(Tegra::Host1x::Host1x& host1x) : m_device_memory{host1x.MemoryManager()} {}
     ~HeapMapperInternal() = default;
 
-    template <typename Func>
-    void ForEachInOverlapCounter(OverlapCounter& current_range, VAddr cpu_addr, u64 size,
-                                 Func&& func) {
-        const DAddr start_address = cpu_addr;
-        const DAddr end_address = start_address + size;
-        const IntervalType search_interval{start_address, end_address};
-        auto it = current_range.lower_bound(search_interval);
-        if (it == current_range.end()) {
-            return;
-        }
-        auto end_it = current_range.upper_bound(search_interval);
-        for (; it != end_it; it++) {
-            auto& inter = it->first;
-            DAddr inter_addr_end = inter.upper();
-            DAddr inter_addr = inter.lower();
-            if (inter_addr_end > end_address) {
-                inter_addr_end = end_address;
-            }
-            if (inter_addr < start_address) {
-                inter_addr = start_address;
-            }
-            func(inter_addr, inter_addr_end, it->second);
-        }
-    }
-
-    void RemoveEachInOverlapCounter(OverlapCounter& current_range,
-                                    const IntervalType search_interval, int subtract_value) {
-        bool any_removals = false;
-        current_range.add(std::make_pair(search_interval, subtract_value));
-        do {
-            any_removals = false;
-            auto it = current_range.lower_bound(search_interval);
-            if (it == current_range.end()) {
-                return;
-            }
-            auto end_it = current_range.upper_bound(search_interval);
-            for (; it != end_it; it++) {
-                if (it->second <= 0) {
-                    any_removals = true;
-                    current_range.erase(it);
-                    break;
-                }
-            }
-        } while (any_removals);
-    }
-
-    IntervalSet base_set;
-    OverlapCounter mapping_overlaps;
-    Tegra::MaxwellDeviceMemoryManager& device_memory;
-    std::mutex guard;
+    Common::RangeSet<VAddr> m_temporary_set;
+    Common::SplitRangeSet<VAddr> m_mapped_ranges;
+    Tegra::MaxwellDeviceMemoryManager& m_device_memory;
+    std::mutex m_guard;
 };
 
 HeapMapper::HeapMapper(VAddr start_vaddress, DAddr start_daddress, size_t size, Core::Asid asid,
@@ -116,60 +27,48 @@ HeapMapper::HeapMapper(VAddr start_vaddress, DAddr start_daddress, size_t size,
 }
 
 HeapMapper::~HeapMapper() {
-    m_internal->device_memory.Unmap(m_daddress, m_size);
+    // Unmap whatever has been mapped.
+    m_internal->m_mapped_ranges.ForEach([this](VAddr start_addr, VAddr end_addr, s32 count) {
+        const size_t sub_size = end_addr - start_addr;
+        const size_t offset = start_addr - m_vaddress;
+        m_internal->m_device_memory.Unmap(m_daddress + offset, sub_size);
+    });
 }
 
 DAddr HeapMapper::Map(VAddr start, size_t size) {
-    std::scoped_lock lk(m_internal->guard);
-    m_internal->base_set.clear();
-    const IntervalType interval{start, start + size};
-    m_internal->base_set.insert(interval);
-    m_internal->ForEachInOverlapCounter(m_internal->mapping_overlaps, start, size,
-                                        [this](VAddr start_addr, VAddr end_addr, int) {
-                                            const IntervalType other{start_addr, end_addr};
-                                            m_internal->base_set.subtract(other);
-                                        });
-    if (!m_internal->base_set.empty()) {
-        auto it = m_internal->base_set.begin();
-        auto end_it = m_internal->base_set.end();
-        for (; it != end_it; it++) {
-            const VAddr inter_addr_end = it->upper();
-            const VAddr inter_addr = it->lower();
-            const size_t offset = inter_addr - m_vaddress;
-            const size_t sub_size = inter_addr_end - inter_addr;
-            m_internal->device_memory.Map(m_daddress + offset, m_vaddress + offset, sub_size,
-                                          m_asid);
-        }
-    }
-    m_internal->mapping_overlaps += std::make_pair(interval, 1);
-    m_internal->base_set.clear();
-    return m_daddress + (start - m_vaddress);
+    std::scoped_lock lk(m_internal->m_guard);
+    // Add the mapping range to a temporary range set.
+    m_internal->m_temporary_set.Clear();
+    m_internal->m_temporary_set.Add(start, size);
+
+    // Remove anything that's already mapped from the temporary range set.
+    m_internal->m_mapped_ranges.ForEachInRange(
+        start, size, [this](VAddr start_addr, VAddr end_addr, s32) {
+            m_internal->m_temporary_set.Subtract(start_addr, end_addr - start_addr);
+        });
+
+    // Map anything that has not been mapped yet.
+    m_internal->m_temporary_set.ForEach([this](VAddr start_addr, VAddr end_addr) {
+        const size_t sub_size = end_addr - start_addr;
+        const size_t offset = start_addr - m_vaddress;
+        m_internal->m_device_memory.Map(m_daddress + offset, m_vaddress + offset, sub_size, m_asid);
+    });
+
+    // Add the mapping range to the split map, to register the map and overlaps.
+    m_internal->m_mapped_ranges.Add(start, size);
+    m_internal->m_temporary_set.Clear();
+    return m_daddress + static_cast<DAddr>(start - m_vaddress);
 }
 
 void HeapMapper::Unmap(VAddr start, size_t size) {
-    std::scoped_lock lk(m_internal->guard);
-    m_internal->base_set.clear();
-    m_internal->ForEachInOverlapCounter(m_internal->mapping_overlaps, start, size,
-                                        [this](VAddr start_addr, VAddr end_addr, int value) {
-                                            if (value <= 1) {
-                                                const IntervalType other{start_addr, end_addr};
-                                                m_internal->base_set.insert(other);
-                                            }
-                                        });
-    if (!m_internal->base_set.empty()) {
-        auto it = m_internal->base_set.begin();
-        auto end_it = m_internal->base_set.end();
-        for (; it != end_it; it++) {
-            const VAddr inter_addr_end = it->upper();
-            const VAddr inter_addr = it->lower();
-            const size_t offset = inter_addr - m_vaddress;
-            const size_t sub_size = inter_addr_end - inter_addr;
-            m_internal->device_memory.Unmap(m_daddress + offset, sub_size);
-        }
-    }
-    const IntervalType to_remove{start, start + size};
-    m_internal->RemoveEachInOverlapCounter(m_internal->mapping_overlaps, to_remove, -1);
-    m_internal->base_set.clear();
+    std::scoped_lock lk(m_internal->m_guard);
+
+    // Just subtract the range and whatever is deleted, unmap it.
+    m_internal->m_mapped_ranges.Subtract(start, size, [this](VAddr start_addr, VAddr end_addr) {
+        const size_t sub_size = end_addr - start_addr;
+        const size_t offset = start_addr - m_vaddress;
+        m_internal->m_device_memory.Unmap(m_daddress + offset, sub_size);
+    });
 }
 
 } // namespace Service::Nvidia::NvCore