diff options
47 files changed, 2491 insertions, 1846 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt index aeaf8e81f..f77575a00 100644 --- a/src/common/CMakeLists.txt +++ b/src/common/CMakeLists.txt @@ -98,7 +98,6 @@ add_library(common STATIC algorithm.h alignment.h assert.h - atomic_ops.cpp atomic_ops.h detached_tasks.cpp detached_tasks.h @@ -166,8 +165,6 @@ add_library(common STATIC threadsafe_queue.h time_zone.cpp time_zone.h - timer.cpp - timer.h tree.h uint128.cpp uint128.h diff --git a/src/common/alignment.h b/src/common/alignment.h index 5040043de..fb81f10d8 100644 --- a/src/common/alignment.h +++ b/src/common/alignment.h @@ -9,50 +9,45 @@ namespace Common { template <typename T> -[[nodiscard]] constexpr T AlignUp(T value, std::size_t size) { - static_assert(std::is_unsigned_v<T>, "T must be an unsigned value."); +requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignUp(T value, size_t size) { auto mod{static_cast<T>(value % size)}; value -= mod; return static_cast<T>(mod == T{0} ? value : value + size); } template <typename T> -[[nodiscard]] constexpr T AlignDown(T value, std::size_t size) { - static_assert(std::is_unsigned_v<T>, "T must be an unsigned value."); - return static_cast<T>(value - value % size); +requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignUpLog2(T value, size_t align_log2) { + return static_cast<T>((value + ((1ULL << align_log2) - 1)) >> align_log2 << align_log2); } template <typename T> -[[nodiscard]] constexpr T AlignBits(T value, std::size_t align) { - static_assert(std::is_unsigned_v<T>, "T must be an unsigned value."); - return static_cast<T>((value + ((1ULL << align) - 1)) >> align << align); +requires std::is_unsigned_v<T>[[nodiscard]] constexpr T AlignDown(T value, size_t size) { + return static_cast<T>(value - value % size); } template <typename T> -[[nodiscard]] constexpr bool Is4KBAligned(T value) { - static_assert(std::is_unsigned_v<T>, "T must be an unsigned value."); +requires std::is_unsigned_v<T>[[nodiscard]] constexpr bool Is4KBAligned(T value) { return (value & 0xFFF) == 0; } template <typename T> -[[nodiscard]] constexpr bool IsWordAligned(T value) { - static_assert(std::is_unsigned_v<T>, "T must be an unsigned value."); +requires std::is_unsigned_v<T>[[nodiscard]] constexpr bool IsWordAligned(T value) { return (value & 0b11) == 0; } template <typename T> -[[nodiscard]] constexpr bool IsAligned(T value, std::size_t alignment) { - using U = typename std::make_unsigned<T>::type; +requires std::is_integral_v<T>[[nodiscard]] constexpr bool IsAligned(T value, size_t alignment) { + using U = typename std::make_unsigned_t<T>; const U mask = static_cast<U>(alignment - 1); return (value & mask) == 0; } -template <typename T, std::size_t Align = 16> +template <typename T, size_t Align = 16> class AlignmentAllocator { public: using value_type = T; - using size_type = std::size_t; - using difference_type = std::ptrdiff_t; + using size_type = size_t; + using difference_type = ptrdiff_t; using propagate_on_container_copy_assignment = std::true_type; using propagate_on_container_move_assignment = std::true_type; diff --git a/src/common/atomic_ops.cpp b/src/common/atomic_ops.cpp deleted file mode 100644 index 1612d0e67..000000000 --- a/src/common/atomic_ops.cpp +++ /dev/null @@ -1,75 +0,0 @@ -// Copyright 2020 yuzu Emulator Project -// Licensed under GPLv2 or any later version -// Refer to the license.txt file included. - -#include <cstring> - -#include "common/atomic_ops.h" - -#if _MSC_VER -#include <intrin.h> -#endif - -namespace Common { - -#if _MSC_VER - -bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) { - const u8 result = - _InterlockedCompareExchange8(reinterpret_cast<volatile char*>(pointer), value, expected); - return result == expected; -} - -bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) { - const u16 result = - _InterlockedCompareExchange16(reinterpret_cast<volatile short*>(pointer), value, expected); - return result == expected; -} - -bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) { - const u32 result = - _InterlockedCompareExchange(reinterpret_cast<volatile long*>(pointer), value, expected); - return result == expected; -} - -bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) { - const u64 result = _InterlockedCompareExchange64(reinterpret_cast<volatile __int64*>(pointer), - value, expected); - return result == expected; -} - -bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) { - return _InterlockedCompareExchange128(reinterpret_cast<volatile __int64*>(pointer), value[1], - value[0], - reinterpret_cast<__int64*>(expected.data())) != 0; -} - -#else - -bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) { - return __sync_bool_compare_and_swap(pointer, expected, value); -} - -bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) { - return __sync_bool_compare_and_swap(pointer, expected, value); -} - -bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) { - return __sync_bool_compare_and_swap(pointer, expected, value); -} - -bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) { - return __sync_bool_compare_and_swap(pointer, expected, value); -} - -bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) { - unsigned __int128 value_a; - unsigned __int128 expected_a; - std::memcpy(&value_a, value.data(), sizeof(u128)); - std::memcpy(&expected_a, expected.data(), sizeof(u128)); - return __sync_bool_compare_and_swap((unsigned __int128*)pointer, expected_a, value_a); -} - -#endif - -} // namespace Common diff --git a/src/common/atomic_ops.h b/src/common/atomic_ops.h index b46888589..2b1f515e8 100644 --- a/src/common/atomic_ops.h +++ b/src/common/atomic_ops.h @@ -4,14 +4,75 @@ #pragma once +#include <cstring> +#include <memory> + #include "common/common_types.h" +#if _MSC_VER +#include <intrin.h> +#endif + namespace Common { -[[nodiscard]] bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected); -[[nodiscard]] bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected); -[[nodiscard]] bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected); -[[nodiscard]] bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected); -[[nodiscard]] bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected); +#if _MSC_VER + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) { + const u8 result = + _InterlockedCompareExchange8(reinterpret_cast<volatile char*>(pointer), value, expected); + return result == expected; +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) { + const u16 result = + _InterlockedCompareExchange16(reinterpret_cast<volatile short*>(pointer), value, expected); + return result == expected; +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) { + const u32 result = + _InterlockedCompareExchange(reinterpret_cast<volatile long*>(pointer), value, expected); + return result == expected; +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) { + const u64 result = _InterlockedCompareExchange64(reinterpret_cast<volatile __int64*>(pointer), + value, expected); + return result == expected; +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) { + return _InterlockedCompareExchange128(reinterpret_cast<volatile __int64*>(pointer), value[1], + value[0], + reinterpret_cast<__int64*>(expected.data())) != 0; +} + +#else + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u8* pointer, u8 value, u8 expected) { + return __sync_bool_compare_and_swap(pointer, expected, value); +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u16* pointer, u16 value, u16 expected) { + return __sync_bool_compare_and_swap(pointer, expected, value); +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u32* pointer, u32 value, u32 expected) { + return __sync_bool_compare_and_swap(pointer, expected, value); +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u64 value, u64 expected) { + return __sync_bool_compare_and_swap(pointer, expected, value); +} + +[[nodiscard]] inline bool AtomicCompareAndSwap(volatile u64* pointer, u128 value, u128 expected) { + unsigned __int128 value_a; + unsigned __int128 expected_a; + std::memcpy(&value_a, value.data(), sizeof(u128)); + std::memcpy(&expected_a, expected.data(), sizeof(u128)); + return __sync_bool_compare_and_swap((unsigned __int128*)pointer, expected_a, value_a); +} + +#endif } // namespace Common diff --git a/src/common/bit_util.h b/src/common/bit_util.h index 29f59a9a3..685e7fc9b 100644 --- a/src/common/bit_util.h +++ b/src/common/bit_util.h @@ -22,82 +22,6 @@ template <typename T> } #ifdef _MSC_VER -[[nodiscard]] inline u32 CountLeadingZeroes32(u32 value) { - unsigned long leading_zero = 0; - - if (_BitScanReverse(&leading_zero, value) != 0) { - return 31 - leading_zero; - } - - return 32; -} - -[[nodiscard]] inline u32 CountLeadingZeroes64(u64 value) { - unsigned long leading_zero = 0; - - if (_BitScanReverse64(&leading_zero, value) != 0) { - return 63 - leading_zero; - } - - return 64; -} -#else -[[nodiscard]] inline u32 CountLeadingZeroes32(u32 value) { - if (value == 0) { - return 32; - } - - return static_cast<u32>(__builtin_clz(value)); -} - -[[nodiscard]] inline u32 CountLeadingZeroes64(u64 value) { - if (value == 0) { - return 64; - } - - return static_cast<u32>(__builtin_clzll(value)); -} -#endif - -#ifdef _MSC_VER -[[nodiscard]] inline u32 CountTrailingZeroes32(u32 value) { - unsigned long trailing_zero = 0; - - if (_BitScanForward(&trailing_zero, value) != 0) { - return trailing_zero; - } - - return 32; -} - -[[nodiscard]] inline u32 CountTrailingZeroes64(u64 value) { - unsigned long trailing_zero = 0; - - if (_BitScanForward64(&trailing_zero, value) != 0) { - return trailing_zero; - } - - return 64; -} -#else -[[nodiscard]] inline u32 CountTrailingZeroes32(u32 value) { - if (value == 0) { - return 32; - } - - return static_cast<u32>(__builtin_ctz(value)); -} - -[[nodiscard]] inline u32 CountTrailingZeroes64(u64 value) { - if (value == 0) { - return 64; - } - - return static_cast<u32>(__builtin_ctzll(value)); -} -#endif - -#ifdef _MSC_VER [[nodiscard]] inline u32 MostSignificantBit32(const u32 value) { unsigned long result; diff --git a/src/common/intrusive_red_black_tree.h b/src/common/intrusive_red_black_tree.h index fb55de94e..c0bbcd457 100644 --- a/src/common/intrusive_red_black_tree.h +++ b/src/common/intrusive_red_black_tree.h @@ -16,17 +16,30 @@ class IntrusiveRedBlackTreeImpl; } struct IntrusiveRedBlackTreeNode { +public: + using EntryType = RBEntry<IntrusiveRedBlackTreeNode>; + + constexpr IntrusiveRedBlackTreeNode() = default; + + void SetEntry(const EntryType& new_entry) { + entry = new_entry; + } + + [[nodiscard]] EntryType& GetEntry() { + return entry; + } + + [[nodiscard]] const EntryType& GetEntry() const { + return entry; + } private: - RB_ENTRY(IntrusiveRedBlackTreeNode) entry{}; + EntryType entry{}; friend class impl::IntrusiveRedBlackTreeImpl; template <class, class, class> friend class IntrusiveRedBlackTree; - -public: - constexpr IntrusiveRedBlackTreeNode() = default; }; template <class T, class Traits, class Comparator> @@ -35,17 +48,12 @@ class IntrusiveRedBlackTree; namespace impl { class IntrusiveRedBlackTreeImpl { - private: template <class, class, class> friend class ::Common::IntrusiveRedBlackTree; -private: - RB_HEAD(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode); - using RootType = IntrusiveRedBlackTreeRoot; - -private: - IntrusiveRedBlackTreeRoot root; + using RootType = RBHead<IntrusiveRedBlackTreeNode>; + RootType root; public: template <bool Const> @@ -121,57 +129,45 @@ public: } }; -protected: - // Generate static implementations for non-comparison operations for IntrusiveRedBlackTreeRoot. - RB_GENERATE_WITHOUT_COMPARE_STATIC(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode, entry); - private: // Define accessors using RB_* functions. - constexpr void InitializeImpl() { - RB_INIT(&this->root); - } - bool EmptyImpl() const { - return RB_EMPTY(&this->root); + return root.IsEmpty(); } IntrusiveRedBlackTreeNode* GetMinImpl() const { - return RB_MIN(IntrusiveRedBlackTreeRoot, - const_cast<IntrusiveRedBlackTreeRoot*>(&this->root)); + return RB_MIN(const_cast<RootType*>(&root)); } IntrusiveRedBlackTreeNode* GetMaxImpl() const { - return RB_MAX(IntrusiveRedBlackTreeRoot, - const_cast<IntrusiveRedBlackTreeRoot*>(&this->root)); + return RB_MAX(const_cast<RootType*>(&root)); } IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) { - return RB_REMOVE(IntrusiveRedBlackTreeRoot, &this->root, node); + return RB_REMOVE(&root, node); } public: static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) { - return RB_NEXT(IntrusiveRedBlackTreeRoot, nullptr, node); + return RB_NEXT(node); } static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) { - return RB_PREV(IntrusiveRedBlackTreeRoot, nullptr, node); + return RB_PREV(node); } - static IntrusiveRedBlackTreeNode const* GetNext(const IntrusiveRedBlackTreeNode* node) { + static const IntrusiveRedBlackTreeNode* GetNext(const IntrusiveRedBlackTreeNode* node) { return static_cast<const IntrusiveRedBlackTreeNode*>( GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node))); } - static IntrusiveRedBlackTreeNode const* GetPrev(const IntrusiveRedBlackTreeNode* node) { + static const IntrusiveRedBlackTreeNode* GetPrev(const IntrusiveRedBlackTreeNode* node) { return static_cast<const IntrusiveRedBlackTreeNode*>( GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node))); } public: - constexpr IntrusiveRedBlackTreeImpl() : root() { - this->InitializeImpl(); - } + constexpr IntrusiveRedBlackTreeImpl() {} // Iterator accessors. iterator begin() { @@ -269,8 +265,6 @@ private: ImplType impl{}; public: - struct IntrusiveRedBlackTreeRootWithCompare : ImplType::IntrusiveRedBlackTreeRoot {}; - template <bool Const> class Iterator; @@ -363,11 +357,6 @@ public: }; private: - // Generate static implementations for comparison operations for IntrusiveRedBlackTreeRoot. - RB_GENERATE_WITH_COMPARE_STATIC(IntrusiveRedBlackTreeRootWithCompare, IntrusiveRedBlackTreeNode, - entry, CompareImpl, LightCompareImpl); - -private: static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs, const IntrusiveRedBlackTreeNode* rhs) { return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs)); @@ -379,41 +368,27 @@ private: // Define accessors using RB_* functions. IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) { - return RB_INSERT(IntrusiveRedBlackTreeRootWithCompare, - static_cast<IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root), - node); + return RB_INSERT(&impl.root, node, CompareImpl); } IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const { - return RB_FIND( - IntrusiveRedBlackTreeRootWithCompare, - const_cast<IntrusiveRedBlackTreeRootWithCompare*>( - static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)), - const_cast<IntrusiveRedBlackTreeNode*>(node)); + return RB_FIND(const_cast<ImplType::RootType*>(&impl.root), + const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl); } IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const { - return RB_NFIND( - IntrusiveRedBlackTreeRootWithCompare, - const_cast<IntrusiveRedBlackTreeRootWithCompare*>( - static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)), - const_cast<IntrusiveRedBlackTreeNode*>(node)); + return RB_NFIND(const_cast<ImplType::RootType*>(&impl.root), + const_cast<IntrusiveRedBlackTreeNode*>(node), CompareImpl); } IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const { - return RB_FIND_LIGHT( - IntrusiveRedBlackTreeRootWithCompare, - const_cast<IntrusiveRedBlackTreeRootWithCompare*>( - static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)), - static_cast<const void*>(lelm)); + return RB_FIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root), + static_cast<const void*>(lelm), LightCompareImpl); } IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const { - return RB_NFIND_LIGHT( - IntrusiveRedBlackTreeRootWithCompare, - const_cast<IntrusiveRedBlackTreeRootWithCompare*>( - static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)), - static_cast<const void*>(lelm)); + return RB_NFIND_LIGHT(const_cast<ImplType::RootType*>(&impl.root), + static_cast<const void*>(lelm), LightCompareImpl); } public: diff --git a/src/common/timer.cpp b/src/common/timer.cpp deleted file mode 100644 index d17dc2a50..000000000 --- a/src/common/timer.cpp +++ /dev/null @@ -1,159 +0,0 @@ -// Copyright 2013 Dolphin Emulator Project / 2014 Citra Emulator Project -// Licensed under GPLv2 or any later version -// Refer to the license.txt file included. - -#include <ctime> -#include <fmt/format.h> -#include "common/common_types.h" -#include "common/string_util.h" -#include "common/timer.h" - -namespace Common { - -std::chrono::milliseconds Timer::GetTimeMs() { - return std::chrono::duration_cast<std::chrono::milliseconds>( - std::chrono::system_clock::now().time_since_epoch()); -} - -// -------------------------------------------- -// Initiate, Start, Stop, and Update the time -// -------------------------------------------- - -// Set initial values for the class -Timer::Timer() : m_LastTime(0), m_StartTime(0), m_Running(false) { - Update(); -} - -// Write the starting time -void Timer::Start() { - m_StartTime = GetTimeMs(); - m_Running = true; -} - -// Stop the timer -void Timer::Stop() { - // Write the final time - m_LastTime = GetTimeMs(); - m_Running = false; -} - -// Update the last time variable -void Timer::Update() { - m_LastTime = GetTimeMs(); - // TODO(ector) - QPF -} - -// ------------------------------------- -// Get time difference and elapsed time -// ------------------------------------- - -// Get the number of milliseconds since the last Update() -std::chrono::milliseconds Timer::GetTimeDifference() { - return GetTimeMs() - m_LastTime; -} - -// Add the time difference since the last Update() to the starting time. -// This is used to compensate for a paused game. -void Timer::AddTimeDifference() { - m_StartTime += GetTimeDifference(); -} - -// Get the time elapsed since the Start() -std::chrono::milliseconds Timer::GetTimeElapsed() { - // If we have not started yet, return 1 (because then I don't - // have to change the FPS calculation in CoreRerecording.cpp . - if (m_StartTime.count() == 0) - return std::chrono::milliseconds(1); - - // Return the final timer time if the timer is stopped - if (!m_Running) - return (m_LastTime - m_StartTime); - - return (GetTimeMs() - m_StartTime); -} - -// Get the formatted time elapsed since the Start() -std::string Timer::GetTimeElapsedFormatted() const { - // If we have not started yet, return zero - if (m_StartTime.count() == 0) - return "00:00:00:000"; - - // The number of milliseconds since the start. - // Use a different value if the timer is stopped. - std::chrono::milliseconds Milliseconds; - if (m_Running) - Milliseconds = GetTimeMs() - m_StartTime; - else - Milliseconds = m_LastTime - m_StartTime; - // Seconds - std::chrono::seconds Seconds = std::chrono::duration_cast<std::chrono::seconds>(Milliseconds); - // Minutes - std::chrono::minutes Minutes = std::chrono::duration_cast<std::chrono::minutes>(Milliseconds); - // Hours - std::chrono::hours Hours = std::chrono::duration_cast<std::chrono::hours>(Milliseconds); - - std::string TmpStr = fmt::format("{:02}:{:02}:{:02}:{:03}", Hours.count(), Minutes.count() % 60, - Seconds.count() % 60, Milliseconds.count() % 1000); - return TmpStr; -} - -// Get the number of seconds since January 1 1970 -std::chrono::seconds Timer::GetTimeSinceJan1970() { - return std::chrono::duration_cast<std::chrono::seconds>(GetTimeMs()); -} - -std::chrono::seconds Timer::GetLocalTimeSinceJan1970() { - time_t sysTime, tzDiff, tzDST; - struct tm* gmTime; - - time(&sysTime); - - // Account for DST where needed - gmTime = localtime(&sysTime); - if (gmTime->tm_isdst == 1) - tzDST = 3600; - else - tzDST = 0; - - // Lazy way to get local time in sec - gmTime = gmtime(&sysTime); - tzDiff = sysTime - mktime(gmTime); - - return std::chrono::seconds(sysTime + tzDiff + tzDST); -} - -// Return the current time formatted as Minutes:Seconds:Milliseconds -// in the form 00:00:000. -std::string Timer::GetTimeFormatted() { - time_t sysTime; - struct tm* gmTime; - char tmp[13]; - - time(&sysTime); - gmTime = localtime(&sysTime); - - strftime(tmp, 6, "%M:%S", gmTime); - - u64 milliseconds = static_cast<u64>(GetTimeMs().count()) % 1000; - return fmt::format("{}:{:03}", tmp, milliseconds); -} - -// Returns a timestamp with decimals for precise time comparisons -// ---------------- -double Timer::GetDoubleTime() { - // Get continuous timestamp - auto tmp_seconds = static_cast<u64>(GetTimeSinceJan1970().count()); - const auto ms = static_cast<double>(static_cast<u64>(GetTimeMs().count()) % 1000); - - // Remove a few years. We only really want enough seconds to make - // sure that we are detecting actual actions, perhaps 60 seconds is - // enough really, but I leave a year of seconds anyway, in case the - // user's clock is incorrect or something like that. - tmp_seconds = tmp_seconds - (38 * 365 * 24 * 60 * 60); - - // Make a smaller integer that fits in the double - const auto seconds = static_cast<u32>(tmp_seconds); - return seconds + ms; -} - -} // Namespace Common diff --git a/src/common/timer.h b/src/common/timer.h deleted file mode 100644 index 8894a143d..000000000 --- a/src/common/timer.h +++ /dev/null @@ -1,41 +0,0 @@ -// Copyright 2013 Dolphin Emulator Project / 2014 Citra Emulator Project -// Licensed under GPLv2 or any later version -// Refer to the license.txt file included. - -#pragma once - -#include <chrono> -#include <string> -#include "common/common_types.h" - -namespace Common { -class Timer { -public: - Timer(); - - void Start(); - void Stop(); - void Update(); - - // The time difference is always returned in milliseconds, regardless of alternative internal - // representation - [[nodiscard]] std::chrono::milliseconds GetTimeDifference(); - void AddTimeDifference(); - - [[nodiscard]] static std::chrono::seconds GetTimeSinceJan1970(); - [[nodiscard]] static std::chrono::seconds GetLocalTimeSinceJan1970(); - [[nodiscard]] static double GetDoubleTime(); - - [[nodiscard]] static std::string GetTimeFormatted(); - [[nodiscard]] std::string GetTimeElapsedFormatted() const; - [[nodiscard]] std::chrono::milliseconds GetTimeElapsed(); - - [[nodiscard]] static std::chrono::milliseconds GetTimeMs(); - -private: - std::chrono::milliseconds m_LastTime; - std::chrono::milliseconds m_StartTime; - bool m_Running; -}; - -} // Namespace Common diff --git a/src/common/tree.h b/src/common/tree.h index a6b636646..3da49e422 100644 --- a/src/common/tree.h +++ b/src/common/tree.h @@ -27,33 +27,10 @@ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#ifndef _SYS_TREE_H_ -#define _SYS_TREE_H_ - -/* FreeBSD <sys/cdefs.h> has a lot of defines we don't really want. */ -/* tree.h only actually uses __inline and __unused, so we'll just define those. */ - -/* #include <sys/cdefs.h> */ - -#ifndef __inline -#define __inline inline -#endif +#pragma once /* - * This file defines data structures for different types of trees: - * splay trees and red-black trees. - * - * A splay tree is a self-organizing data structure. Every operation - * on the tree causes a splay to happen. The splay moves the requested - * node to the root of the tree and partly rebalances it. - * - * This has the benefit that request locality causes faster lookups as - * the requested nodes move to the top of the tree. On the other hand, - * every lookup causes memory writes. - * - * The Balance Theorem bounds the total access time for m operations - * and n inserts on an initially empty tree as O((m + n)lg n). The - * amortized cost for a sequence of m accesses to a splay tree is O(lg n); + * This file defines data structures for red-black trees. * * A red-black tree is a binary search tree with the node color as an * extra attribute. It fulfills a set of conditions: @@ -66,757 +43,632 @@ * The maximum height of a red-black tree is 2lg (n+1). */ -#define SPLAY_HEAD(name, type) \ - struct name { \ - struct type* sph_root; /* root of the tree */ \ - } - -#define SPLAY_INITIALIZER(root) \ - { NULL } - -#define SPLAY_INIT(root) \ - do { \ - (root)->sph_root = NULL; \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_ENTRY(type) \ - struct { \ - struct type* spe_left; /* left element */ \ - struct type* spe_right; /* right element */ \ - } - -#define SPLAY_LEFT(elm, field) (elm)->field.spe_left -#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right -#define SPLAY_ROOT(head) (head)->sph_root -#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) - -/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ -#define SPLAY_ROTATE_RIGHT(head, tmp, field) \ - do { \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_ROTATE_LEFT(head, tmp, field) \ - do { \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - (head)->sph_root = tmp; \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_LINKLEFT(head, tmp, field) \ - do { \ - SPLAY_LEFT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_LINKRIGHT(head, tmp, field) \ - do { \ - SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ - tmp = (head)->sph_root; \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ - } while (/*CONSTCOND*/ 0) - -#define SPLAY_ASSEMBLE(head, node, left, right, field) \ - do { \ - SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ - SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ - } while (/*CONSTCOND*/ 0) - -/* Generates prototypes and inline functions */ - -#define SPLAY_PROTOTYPE(name, type, field, cmp) \ - void name##_SPLAY(struct name*, struct type*); \ - void name##_SPLAY_MINMAX(struct name*, int); \ - struct type* name##_SPLAY_INSERT(struct name*, struct type*); \ - struct type* name##_SPLAY_REMOVE(struct name*, struct type*); \ - \ - /* Finds the node with the same key as elm */ \ - static __inline struct type* name##_SPLAY_FIND(struct name* head, struct type* elm) { \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) \ - return (head->sph_root); \ - return (NULL); \ - } \ - \ - static __inline struct type* name##_SPLAY_NEXT(struct name* head, struct type* elm) { \ - name##_SPLAY(head, elm); \ - if (SPLAY_RIGHT(elm, field) != NULL) { \ - elm = SPLAY_RIGHT(elm, field); \ - while (SPLAY_LEFT(elm, field) != NULL) { \ - elm = SPLAY_LEFT(elm, field); \ - } \ - } else \ - elm = NULL; \ - return (elm); \ - } \ - \ - static __inline struct type* name##_SPLAY_MIN_MAX(struct name* head, int val) { \ - name##_SPLAY_MINMAX(head, val); \ - return (SPLAY_ROOT(head)); \ - } - -/* Main splay operation. - * Moves node close to the key of elm to top - */ -#define SPLAY_GENERATE(name, type, field, cmp) \ - struct type* name##_SPLAY_INSERT(struct name* head, struct type* elm) { \ - if (SPLAY_EMPTY(head)) { \ - SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ - } else { \ - int __comp; \ - name##_SPLAY(head, elm); \ - __comp = (cmp)(elm, (head)->sph_root); \ - if (__comp < 0) { \ - SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ - SPLAY_RIGHT(elm, field) = (head)->sph_root; \ - SPLAY_LEFT((head)->sph_root, field) = NULL; \ - } else if (__comp > 0) { \ - SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ - SPLAY_LEFT(elm, field) = (head)->sph_root; \ - SPLAY_RIGHT((head)->sph_root, field) = NULL; \ - } else \ - return ((head)->sph_root); \ - } \ - (head)->sph_root = (elm); \ - return (NULL); \ - } \ - \ - struct type* name##_SPLAY_REMOVE(struct name* head, struct type* elm) { \ - struct type* __tmp; \ - if (SPLAY_EMPTY(head)) \ - return (NULL); \ - name##_SPLAY(head, elm); \ - if ((cmp)(elm, (head)->sph_root) == 0) { \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ - (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ - } else { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ - name##_SPLAY(head, elm); \ - SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ - } \ - return (elm); \ - } \ - return (NULL); \ - } \ - \ - void name##_SPLAY(struct name* head, struct type* elm) { \ - struct type __node, *__left, *__right, *__tmp; \ - int __comp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ - __left = __right = &__node; \ - \ - while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if ((cmp)(elm, __tmp) > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } \ - \ - /* Splay with either the minimum or the maximum element \ - * Used to find minimum or maximum element in tree. \ - */ \ - void name##_SPLAY_MINMAX(struct name* head, int __comp) { \ - struct type __node, *__left, *__right, *__tmp; \ - \ - SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ - __left = __right = &__node; \ - \ - while (1) { \ - if (__comp < 0) { \ - __tmp = SPLAY_LEFT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp < 0) { \ - SPLAY_ROTATE_RIGHT(head, __tmp, field); \ - if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKLEFT(head, __right, field); \ - } else if (__comp > 0) { \ - __tmp = SPLAY_RIGHT((head)->sph_root, field); \ - if (__tmp == NULL) \ - break; \ - if (__comp > 0) { \ - SPLAY_ROTATE_LEFT(head, __tmp, field); \ - if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ - break; \ - } \ - SPLAY_LINKRIGHT(head, __left, field); \ - } \ - } \ - SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ - } - -#define SPLAY_NEGINF -1 -#define SPLAY_INF 1 - -#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) -#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) -#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) -#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) -#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) -#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) - -#define SPLAY_FOREACH(x, name, head) \ - for ((x) = SPLAY_MIN(name, head); (x) != NULL; (x) = SPLAY_NEXT(name, head, x)) - -/* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ - struct name { \ - struct type* rbh_root; /* root of the tree */ \ - } - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) \ - do { \ - (root)->rbh_root = NULL; \ - } while (/*CONSTCOND*/ 0) - -#define RB_BLACK 0 -#define RB_RED 1 -#define RB_ENTRY(type) \ - struct { \ - struct type* rbe_left; /* left element */ \ - struct type* rbe_right; /* right element */ \ - struct type* rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ - } - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET(elm, parent, field) \ - do { \ - RB_PARENT(elm, field) = parent; \ - RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ - } while (/*CONSTCOND*/ 0) - -#define RB_SET_BLACKRED(black, red, field) \ - do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ - } while (/*CONSTCOND*/ 0) - -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) \ - do { \ - } while (0) -#endif - -#define RB_ROTATE_LEFT(head, elm, tmp, field) \ - do { \ - (tmp) = RB_RIGHT(elm, field); \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ - RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_LEFT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ - } while (/*CONSTCOND*/ 0) - -#define RB_ROTATE_RIGHT(head, elm, tmp, field) \ - do { \ - (tmp) = RB_LEFT(elm, field); \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ - RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ - } while (/*CONSTCOND*/ 0) - -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) RB_PROTOTYPE_INTERNAL(name, type, field, cmp, ) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ - RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ - RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ - RB_PROTOTYPE_INSERT(name, type, attr); \ - RB_PROTOTYPE_REMOVE(name, type, attr); \ - RB_PROTOTYPE_FIND(name, type, attr); \ - RB_PROTOTYPE_NFIND(name, type, attr); \ - RB_PROTOTYPE_FIND_LIGHT(name, type, attr); \ - RB_PROTOTYPE_NFIND_LIGHT(name, type, attr); \ - RB_PROTOTYPE_NEXT(name, type, attr); \ - RB_PROTOTYPE_PREV(name, type, attr); \ - RB_PROTOTYPE_MINMAX(name, type, attr); -#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr void name##_RB_INSERT_COLOR(struct name*, struct type*) -#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ - attr void name##_RB_REMOVE_COLOR(struct name*, struct type*, struct type*) -#define RB_PROTOTYPE_REMOVE(name, type, attr) \ - attr struct type* name##_RB_REMOVE(struct name*, struct type*) -#define RB_PROTOTYPE_INSERT(name, type, attr) \ - attr struct type* name##_RB_INSERT(struct name*, struct type*) -#define RB_PROTOTYPE_FIND(name, type, attr) \ - attr struct type* name##_RB_FIND(struct name*, struct type*) -#define RB_PROTOTYPE_NFIND(name, type, attr) \ - attr struct type* name##_RB_NFIND(struct name*, struct type*) -#define RB_PROTOTYPE_FIND_LIGHT(name, type, attr) \ - attr struct type* name##_RB_FIND_LIGHT(struct name*, const void*) -#define RB_PROTOTYPE_NFIND_LIGHT(name, type, attr) \ - attr struct type* name##_RB_NFIND_LIGHT(struct name*, const void*) -#define RB_PROTOTYPE_NEXT(name, type, attr) attr struct type* name##_RB_NEXT(struct type*) -#define RB_PROTOTYPE_PREV(name, type, attr) attr struct type* name##_RB_PREV(struct type*) -#define RB_PROTOTYPE_MINMAX(name, type, attr) attr struct type* name##_RB_MINMAX(struct name*, int) - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE_WITHOUT_COMPARE(name, type, field) \ - RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, ) -#define RB_GENERATE_WITHOUT_COMPARE_STATIC(name, type, field) \ - RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, static) -#define RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ - RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ - RB_GENERATE_REMOVE(name, type, field, attr) \ - RB_GENERATE_NEXT(name, type, field, attr) \ - RB_GENERATE_PREV(name, type, field, attr) \ - RB_GENERATE_MINMAX(name, type, field, attr) - -#define RB_GENERATE_WITH_COMPARE(name, type, field, cmp, lcmp) \ - RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, ) -#define RB_GENERATE_WITH_COMPARE_STATIC(name, type, field, cmp, lcmp) \ - RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, static) -#define RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, lcmp, attr) \ - RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ - RB_GENERATE_INSERT(name, type, field, cmp, attr) \ - RB_GENERATE_FIND(name, type, field, cmp, attr) \ - RB_GENERATE_NFIND(name, type, field, cmp, attr) \ - RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ - RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) - -#define RB_GENERATE_ALL(name, type, field, cmp) RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, ) -#define RB_GENERATE_ALL_STATIC(name, type, field, cmp) \ - RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, static) -#define RB_GENERATE_ALL_INTERNAL(name, type, field, cmp, attr) \ - RB_GENERATE_WITHOUT_COMPARE_INTERNAL(name, type, field, attr) \ - RB_GENERATE_WITH_COMPARE_INTERNAL(name, type, field, cmp, attr) - -#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ - attr void name##_RB_INSERT_COLOR(struct name* head, struct type* elm) { \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RB_PARENT(elm, field)) != NULL && RB_COLOR(parent, field) == RB_RED) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field); \ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field); \ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field); \ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RB_COLOR(head->rbh_root, field) = RB_BLACK; \ - } - -#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ - attr void name##_RB_REMOVE_COLOR(struct name* head, struct type* parent, struct type* elm) { \ - struct type* tmp; \ - while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && elm != RB_ROOT(head)) { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field); \ - tmp = RB_RIGHT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ - struct type* oleft; \ - if ((oleft = RB_LEFT(tmp, field)) != NULL) \ - RB_COLOR(oleft, field) = RB_BLACK; \ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field); \ - tmp = RB_RIGHT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_RIGHT(tmp, field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ - RB_ROTATE_LEFT(head, parent, tmp, field); \ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - tmp = RB_LEFT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ - struct type* oright; \ - if ((oright = RB_RIGHT(tmp, field)) != NULL) \ - RB_COLOR(oright, field) = RB_BLACK; \ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field); \ - tmp = RB_LEFT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_LEFT(tmp, field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ - RB_ROTATE_RIGHT(head, parent, tmp, field); \ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RB_COLOR(elm, field) = RB_BLACK; \ - } - -#define RB_GENERATE_REMOVE(name, type, field, attr) \ - attr struct type* name##_RB_REMOVE(struct name* head, struct type* elm) { \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ - struct type* left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field)) != NULL) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old) \ - RB_LEFT(RB_PARENT(old, field), field) = elm; \ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm; \ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field)) != NULL); \ - } \ - goto color; \ - } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - color: \ - if (color == RB_BLACK) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - return (old); \ - } - -#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ - /* Inserts a node into the RB tree */ \ - attr struct type* name##_RB_INSERT(struct name* head, struct type* elm) { \ - struct type* tmp; \ - struct type* parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - return (NULL); \ - } - -#define RB_GENERATE_FIND(name, type, field, cmp, attr) \ - /* Finds the node with the same key as elm */ \ - attr struct type* name##_RB_FIND(struct name* head, struct type* elm) { \ - struct type* tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ - } - -#define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ - /* Finds the first node greater than or equal to the search key */ \ - attr struct type* name##_RB_NFIND(struct name* head, struct type* elm) { \ - struct type* tmp = RB_ROOT(head); \ - struct type* res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ - } - -#define RB_GENERATE_FIND_LIGHT(name, type, field, lcmp, attr) \ - /* Finds the node with the same key as elm */ \ - attr struct type* name##_RB_FIND_LIGHT(struct name* head, const void* lelm) { \ - struct type* tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = lcmp(lelm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ - } - -#define RB_GENERATE_NFIND_LIGHT(name, type, field, lcmp, attr) \ - /* Finds the first node greater than or equal to the search key */ \ - attr struct type* name##_RB_NFIND_LIGHT(struct name* head, const void* lelm) { \ - struct type* tmp = RB_ROOT(head); \ - struct type* res = NULL; \ - int comp; \ - while (tmp) { \ - comp = lcmp(lelm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ - } - -#define RB_GENERATE_NEXT(name, type, field, attr) \ - /* ARGSUSED */ \ - attr struct type* name##_RB_NEXT(struct type* elm) { \ - if (RB_RIGHT(elm, field)) { \ - elm = RB_RIGHT(elm, field); \ - while (RB_LEFT(elm, field)) \ - elm = RB_LEFT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ - } - -#define RB_GENERATE_PREV(name, type, field, attr) \ - /* ARGSUSED */ \ - attr struct type* name##_RB_PREV(struct type* elm) { \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ - } - -#define RB_GENERATE_MINMAX(name, type, field, attr) \ - attr struct type* name##_RB_MINMAX(struct name* head, int val) { \ - struct type* tmp = RB_ROOT(head); \ - struct type* parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RB_LEFT(tmp, field); \ - else \ - tmp = RB_RIGHT(tmp, field); \ - } \ - return (parent); \ - } - -#define RB_NEGINF -1 -#define RB_INF 1 - -#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) -#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) -#define RB_FIND(name, x, y) name##_RB_FIND(x, y) -#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_FIND_LIGHT(name, x, y) name##_RB_FIND_LIGHT(x, y) -#define RB_NFIND_LIGHT(name, x, y) name##_RB_NFIND_LIGHT(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(y) -#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) -#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); (x) != NULL; (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_FROM(x, name, y) \ - for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); (x) = (y)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); (x) != NULL; (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_FROM(x, name, y) \ - for ((x) = (y); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); (x) = (y)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ - (x) = (y)) - -#endif /* _SYS_TREE_H_ */ +namespace Common { +template <typename T> +class RBHead { +public: + [[nodiscard]] T* Root() { + return rbh_root; + } + + [[nodiscard]] const T* Root() const { + return rbh_root; + } + + void SetRoot(T* root) { + rbh_root = root; + } + + [[nodiscard]] bool IsEmpty() const { + return Root() == nullptr; + } + +private: + T* rbh_root = nullptr; +}; + +enum class EntryColor { + Black, + Red, +}; + +template <typename T> +class RBEntry { +public: + [[nodiscard]] T* Left() { + return rbe_left; + } + + [[nodiscard]] const T* Left() const { + return rbe_left; + } + + void SetLeft(T* left) { + rbe_left = left; + } + + [[nodiscard]] T* Right() { + return rbe_right; + } + + [[nodiscard]] const T* Right() const { + return rbe_right; + } + + void SetRight(T* right) { + rbe_right = right; + } + + [[nodiscard]] T* Parent() { + return rbe_parent; + } + + [[nodiscard]] const T* Parent() const { + return rbe_parent; + } + + void SetParent(T* parent) { + rbe_parent = parent; + } + + [[nodiscard]] bool IsBlack() const { + return rbe_color == EntryColor::Black; + } + + [[nodiscard]] bool IsRed() const { + return rbe_color == EntryColor::Red; + } + + [[nodiscard]] EntryColor Color() const { + return rbe_color; + } + + void SetColor(EntryColor color) { + rbe_color = color; + } + +private: + T* rbe_left = nullptr; + T* rbe_right = nullptr; + T* rbe_parent = nullptr; + EntryColor rbe_color{}; +}; + +template <typename Node> +[[nodiscard]] RBEntry<Node>& RB_ENTRY(Node* node) { + return node->GetEntry(); +} + +template <typename Node> +[[nodiscard]] const RBEntry<Node>& RB_ENTRY(const Node* node) { + return node->GetEntry(); +} + +template <typename Node> +[[nodiscard]] Node* RB_PARENT(Node* node) { + return RB_ENTRY(node).Parent(); +} + +template <typename Node> +[[nodiscard]] const Node* RB_PARENT(const Node* node) { + return RB_ENTRY(node).Parent(); +} + +template <typename Node> +void RB_SET_PARENT(Node* node, Node* parent) { + return RB_ENTRY(node).SetParent(parent); +} + +template <typename Node> +[[nodiscard]] Node* RB_LEFT(Node* node) { + return RB_ENTRY(node).Left(); +} + +template <typename Node> +[[nodiscard]] const Node* RB_LEFT(const Node* node) { + return RB_ENTRY(node).Left(); +} + +template <typename Node> +void RB_SET_LEFT(Node* node, Node* left) { + return RB_ENTRY(node).SetLeft(left); +} + +template <typename Node> +[[nodiscard]] Node* RB_RIGHT(Node* node) { + return RB_ENTRY(node).Right(); +} + +template <typename Node> +[[nodiscard]] const Node* RB_RIGHT(const Node* node) { + return RB_ENTRY(node).Right(); +} + +template <typename Node> +void RB_SET_RIGHT(Node* node, Node* right) { + return RB_ENTRY(node).SetRight(right); +} + +template <typename Node> +[[nodiscard]] bool RB_IS_BLACK(const Node* node) { + return RB_ENTRY(node).IsBlack(); +} + +template <typename Node> +[[nodiscard]] bool RB_IS_RED(const Node* node) { + return RB_ENTRY(node).IsRed(); +} + +template <typename Node> +[[nodiscard]] EntryColor RB_COLOR(const Node* node) { + return RB_ENTRY(node).Color(); +} + +template <typename Node> +void RB_SET_COLOR(Node* node, EntryColor color) { + return RB_ENTRY(node).SetColor(color); +} + +template <typename Node> +void RB_SET(Node* node, Node* parent) { + auto& entry = RB_ENTRY(node); + entry.SetParent(parent); + entry.SetLeft(nullptr); + entry.SetRight(nullptr); + entry.SetColor(EntryColor::Red); +} + +template <typename Node> +void RB_SET_BLACKRED(Node* black, Node* red) { + RB_SET_COLOR(black, EntryColor::Black); + RB_SET_COLOR(red, EntryColor::Red); +} + +template <typename Node> +void RB_ROTATE_LEFT(RBHead<Node>* head, Node* elm, Node*& tmp) { + tmp = RB_RIGHT(elm); + RB_SET_RIGHT(elm, RB_LEFT(tmp)); + if (RB_RIGHT(elm) != nullptr) { + RB_SET_PARENT(RB_LEFT(tmp), elm); + } + + RB_SET_PARENT(tmp, RB_PARENT(elm)); + if (RB_PARENT(tmp) != nullptr) { + if (elm == RB_LEFT(RB_PARENT(elm))) { + RB_SET_LEFT(RB_PARENT(elm), tmp); + } else { + RB_SET_RIGHT(RB_PARENT(elm), tmp); + } + } else { + head->SetRoot(tmp); + } + + RB_SET_LEFT(tmp, elm); + RB_SET_PARENT(elm, tmp); +} + +template <typename Node> +void RB_ROTATE_RIGHT(RBHead<Node>* head, Node* elm, Node*& tmp) { + tmp = RB_LEFT(elm); + RB_SET_LEFT(elm, RB_RIGHT(tmp)); + if (RB_LEFT(elm) != nullptr) { + RB_SET_PARENT(RB_RIGHT(tmp), elm); + } + + RB_SET_PARENT(tmp, RB_PARENT(elm)); + if (RB_PARENT(tmp) != nullptr) { + if (elm == RB_LEFT(RB_PARENT(elm))) { + RB_SET_LEFT(RB_PARENT(elm), tmp); + } else { + RB_SET_RIGHT(RB_PARENT(elm), tmp); + } + } else { + head->SetRoot(tmp); + } + + RB_SET_RIGHT(tmp, elm); + RB_SET_PARENT(elm, tmp); +} + +template <typename Node> +void RB_INSERT_COLOR(RBHead<Node>* head, Node* elm) { + Node* parent = nullptr; + Node* tmp = nullptr; + + while ((parent = RB_PARENT(elm)) != nullptr && RB_IS_RED(parent)) { + Node* gparent = RB_PARENT(parent); + if (parent == RB_LEFT(gparent)) { + tmp = RB_RIGHT(gparent); + if (tmp && RB_IS_RED(tmp)) { + RB_SET_COLOR(tmp, EntryColor::Black); + RB_SET_BLACKRED(parent, gparent); + elm = gparent; + continue; + } + + if (RB_RIGHT(parent) == elm) { + RB_ROTATE_LEFT(head, parent, tmp); + tmp = parent; + parent = elm; + elm = tmp; + } + + RB_SET_BLACKRED(parent, gparent); + RB_ROTATE_RIGHT(head, gparent, tmp); + } else { + tmp = RB_LEFT(gparent); + if (tmp && RB_IS_RED(tmp)) { + RB_SET_COLOR(tmp, EntryColor::Black); + RB_SET_BLACKRED(parent, gparent); + elm = gparent; + continue; + } + + if (RB_LEFT(parent) == elm) { + RB_ROTATE_RIGHT(head, parent, tmp); + tmp = parent; + parent = elm; + elm = tmp; + } + + RB_SET_BLACKRED(parent, gparent); + RB_ROTATE_LEFT(head, gparent, tmp); + } + } + + RB_SET_COLOR(head->Root(), EntryColor::Black); +} + +template <typename Node> +void RB_REMOVE_COLOR(RBHead<Node>* head, Node* parent, Node* elm) { + Node* tmp; + while ((elm == nullptr || RB_IS_BLACK(elm)) && elm != head->Root()) { + if (RB_LEFT(parent) == elm) { + tmp = RB_RIGHT(parent); + if (RB_IS_RED(tmp)) { + RB_SET_BLACKRED(tmp, parent); + RB_ROTATE_LEFT(head, parent, tmp); + tmp = RB_RIGHT(parent); + } + + if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && + (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { + RB_SET_COLOR(tmp, EntryColor::Red); + elm = parent; + parent = RB_PARENT(elm); + } else { + if (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp))) { + Node* oleft; + if ((oleft = RB_LEFT(tmp)) != nullptr) { + RB_SET_COLOR(oleft, EntryColor::Black); + } + + RB_SET_COLOR(tmp, EntryColor::Red); + RB_ROTATE_RIGHT(head, tmp, oleft); + tmp = RB_RIGHT(parent); + } + + RB_SET_COLOR(tmp, RB_COLOR(parent)); + RB_SET_COLOR(parent, EntryColor::Black); + if (RB_RIGHT(tmp)) { + RB_SET_COLOR(RB_RIGHT(tmp), EntryColor::Black); + } + + RB_ROTATE_LEFT(head, parent, tmp); + elm = head->Root(); + break; + } + } else { + tmp = RB_LEFT(parent); + if (RB_IS_RED(tmp)) { + RB_SET_BLACKRED(tmp, parent); + RB_ROTATE_RIGHT(head, parent, tmp); + tmp = RB_LEFT(parent); + } + + if ((RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) && + (RB_RIGHT(tmp) == nullptr || RB_IS_BLACK(RB_RIGHT(tmp)))) { + RB_SET_COLOR(tmp, EntryColor::Red); + elm = parent; + parent = RB_PARENT(elm); + } else { + if (RB_LEFT(tmp) == nullptr || RB_IS_BLACK(RB_LEFT(tmp))) { + Node* oright; + if ((oright = RB_RIGHT(tmp)) != nullptr) { + RB_SET_COLOR(oright, EntryColor::Black); + } + + RB_SET_COLOR(tmp, EntryColor::Red); + RB_ROTATE_LEFT(head, tmp, oright); + tmp = RB_LEFT(parent); + } + + RB_SET_COLOR(tmp, RB_COLOR(parent)); + RB_SET_COLOR(parent, EntryColor::Black); + + if (RB_LEFT(tmp)) { + RB_SET_COLOR(RB_LEFT(tmp), EntryColor::Black); + } + + RB_ROTATE_RIGHT(head, parent, tmp); + elm = head->Root(); + break; + } + } + } + + if (elm) { + RB_SET_COLOR(elm, EntryColor::Black); + } +} + +template <typename Node> +Node* RB_REMOVE(RBHead<Node>* head, Node* elm) { + Node* child = nullptr; + Node* parent = nullptr; + Node* old = elm; + EntryColor color{}; + + const auto finalize = [&] { + if (color == EntryColor::Black) { + RB_REMOVE_COLOR(head, parent, child); + } + + return old; + }; + + if (RB_LEFT(elm) == nullptr) { + child = RB_RIGHT(elm); + } else if (RB_RIGHT(elm) == nullptr) { + child = RB_LEFT(elm); + } else { + Node* left; + elm = RB_RIGHT(elm); + while ((left = RB_LEFT(elm)) != nullptr) { + elm = left; + } + + child = RB_RIGHT(elm); + parent = RB_PARENT(elm); + color = RB_COLOR(elm); + + if (child) { + RB_SET_PARENT(child, parent); + } + if (parent) { + if (RB_LEFT(parent) == elm) { + RB_SET_LEFT(parent, child); + } else { + RB_SET_RIGHT(parent, child); + } + } else { + head->SetRoot(child); + } + + if (RB_PARENT(elm) == old) { + parent = elm; + } + + elm->SetEntry(old->GetEntry()); + + if (RB_PARENT(old)) { + if (RB_LEFT(RB_PARENT(old)) == old) { + RB_SET_LEFT(RB_PARENT(old), elm); + } else { + RB_SET_RIGHT(RB_PARENT(old), elm); + } + } else { + head->SetRoot(elm); + } + RB_SET_PARENT(RB_LEFT(old), elm); + if (RB_RIGHT(old)) { + RB_SET_PARENT(RB_RIGHT(old), elm); + } + if (parent) { + left = parent; + } + + return finalize(); + } + + parent = RB_PARENT(elm); + color = RB_COLOR(elm); + + if (child) { + RB_SET_PARENT(child, parent); + } + if (parent) { + if (RB_LEFT(parent) == elm) { + RB_SET_LEFT(parent, child); + } else { + RB_SET_RIGHT(parent, child); + } + } else { + head->SetRoot(child); + } + + return finalize(); +} + +// Inserts a node into the RB tree +template <typename Node, typename CompareFunction> +Node* RB_INSERT(RBHead<Node>* head, Node* elm, CompareFunction cmp) { + Node* parent = nullptr; + Node* tmp = head->Root(); + int comp = 0; + + while (tmp) { + parent = tmp; + comp = cmp(elm, parent); + if (comp < 0) { + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + RB_SET(elm, parent); + + if (parent != nullptr) { + if (comp < 0) { + RB_SET_LEFT(parent, elm); + } else { + RB_SET_RIGHT(parent, elm); + } + } else { + head->SetRoot(elm); + } + + RB_INSERT_COLOR(head, elm); + return nullptr; +} + +// Finds the node with the same key as elm +template <typename Node, typename CompareFunction> +Node* RB_FIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) { + Node* tmp = head->Root(); + + while (tmp) { + const int comp = cmp(elm, tmp); + if (comp < 0) { + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return nullptr; +} + +// Finds the first node greater than or equal to the search key +template <typename Node, typename CompareFunction> +Node* RB_NFIND(RBHead<Node>* head, Node* elm, CompareFunction cmp) { + Node* tmp = head->Root(); + Node* res = nullptr; + + while (tmp) { + const int comp = cmp(elm, tmp); + if (comp < 0) { + res = tmp; + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return res; +} + +// Finds the node with the same key as lelm +template <typename Node, typename CompareFunction> +Node* RB_FIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) { + Node* tmp = head->Root(); + + while (tmp) { + const int comp = lcmp(lelm, tmp); + if (comp < 0) { + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return nullptr; +} + +// Finds the first node greater than or equal to the search key +template <typename Node, typename CompareFunction> +Node* RB_NFIND_LIGHT(RBHead<Node>* head, const void* lelm, CompareFunction lcmp) { + Node* tmp = head->Root(); + Node* res = nullptr; + + while (tmp) { + const int comp = lcmp(lelm, tmp); + if (comp < 0) { + res = tmp; + tmp = RB_LEFT(tmp); + } else if (comp > 0) { + tmp = RB_RIGHT(tmp); + } else { + return tmp; + } + } + + return res; +} + +template <typename Node> +Node* RB_NEXT(Node* elm) { + if (RB_RIGHT(elm)) { + elm = RB_RIGHT(elm); + while (RB_LEFT(elm)) { + elm = RB_LEFT(elm); + } + } else { + if (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } else { + while (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } + elm = RB_PARENT(elm); + } + } + return elm; +} + +template <typename Node> +Node* RB_PREV(Node* elm) { + if (RB_LEFT(elm)) { + elm = RB_LEFT(elm); + while (RB_RIGHT(elm)) { + elm = RB_RIGHT(elm); + } + } else { + if (RB_PARENT(elm) && (elm == RB_RIGHT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } else { + while (RB_PARENT(elm) && (elm == RB_LEFT(RB_PARENT(elm)))) { + elm = RB_PARENT(elm); + } + elm = RB_PARENT(elm); + } + } + return elm; +} + +template <typename Node> +Node* RB_MINMAX(RBHead<Node>* head, bool is_min) { + Node* tmp = head->Root(); + Node* parent = nullptr; + + while (tmp) { + parent = tmp; + if (is_min) { + tmp = RB_LEFT(tmp); + } else { + tmp = RB_RIGHT(tmp); + } + } + + return parent; +} + +template <typename Node> +Node* RB_MIN(RBHead<Node>* head) { + return RB_MINMAX(head, true); +} + +template <typename Node> +Node* RB_MAX(RBHead<Node>* head) { + return RB_MINMAX(head, false); +} +} // namespace Common diff --git a/src/common/x64/native_clock.cpp b/src/common/x64/native_clock.cpp index eb8a7782f..a65f6b832 100644 --- a/src/common/x64/native_clock.cpp +++ b/src/common/x64/native_clock.cpp @@ -2,19 +2,74 @@ // Licensed under GPLv2 or any later version // Refer to the license.txt file included. +#include <array> #include <chrono> +#include <limits> #include <mutex> #include <thread> #ifdef _MSC_VER #include <intrin.h> + +#pragma intrinsic(__umulh) +#pragma intrinsic(_udiv128) #else #include <x86intrin.h> #endif +#include "common/atomic_ops.h" #include "common/uint128.h" #include "common/x64/native_clock.h" +namespace { + +[[nodiscard]] u64 GetFixedPoint64Factor(u64 numerator, u64 divisor) { +#ifdef __SIZEOF_INT128__ + const auto base = static_cast<unsigned __int128>(numerator) << 64ULL; + return static_cast<u64>(base / divisor); +#elif defined(_M_X64) || defined(_M_ARM64) + std::array<u64, 2> r = {0, numerator}; + u64 remainder; +#if _MSC_VER < 1923 + return udiv128(r[1], r[0], divisor, &remainder); +#else + return _udiv128(r[1], r[0], divisor, &remainder); +#endif +#else + // This one is bit more inaccurate. + return MultiplyAndDivide64(std::numeric_limits<u64>::max(), numerator, divisor); +#endif +} + +[[nodiscard]] u64 MultiplyHigh(u64 a, u64 b) { +#ifdef __SIZEOF_INT128__ + return (static_cast<unsigned __int128>(a) * static_cast<unsigned __int128>(b)) >> 64; +#elif defined(_M_X64) || defined(_M_ARM64) + return __umulh(a, b); // MSVC +#else + // Generic fallback + const u64 a_lo = u32(a); + const u64 a_hi = a >> 32; + const u64 b_lo = u32(b); + const u64 b_hi = b >> 32; + + const u64 a_x_b_hi = a_hi * b_hi; + const u64 a_x_b_mid = a_hi * b_lo; + const u64 b_x_a_mid = b_hi * a_lo; + const u64 a_x_b_lo = a_lo * b_lo; + + const u64 carry_bit = (static_cast<u64>(static_cast<u32>(a_x_b_mid)) + + static_cast<u64>(static_cast<u32>(b_x_a_mid)) + (a_x_b_lo >> 32)) >> + 32; + + const u64 multhi = a_x_b_hi + (a_x_b_mid >> 32) + (b_x_a_mid >> 32) + carry_bit; + + return multhi; +#endif +} + +} // namespace + namespace Common { u64 EstimateRDTSCFrequency() { @@ -48,54 +103,71 @@ NativeClock::NativeClock(u64 emulated_cpu_frequency_, u64 emulated_clock_frequen : WallClock(emulated_cpu_frequency_, emulated_clock_frequency_, true), rtsc_frequency{ rtsc_frequency_} { _mm_mfence(); - last_measure = __rdtsc(); - accumulated_ticks = 0U; + time_point.inner.last_measure = __rdtsc(); + time_point.inner.accumulated_ticks = 0U; + ns_rtsc_factor = GetFixedPoint64Factor(1000000000, rtsc_frequency); + us_rtsc_factor = GetFixedPoint64Factor(1000000, rtsc_frequency); + ms_rtsc_factor = GetFixedPoint64Factor(1000, rtsc_frequency); + clock_rtsc_factor = GetFixedPoint64Factor(emulated_clock_frequency, rtsc_frequency); + cpu_rtsc_factor = GetFixedPoint64Factor(emulated_cpu_frequency, rtsc_frequency); } u64 NativeClock::GetRTSC() { - std::scoped_lock scope{rtsc_serialize}; - _mm_mfence(); - const u64 current_measure = __rdtsc(); - u64 diff = current_measure - last_measure; - diff = diff & ~static_cast<u64>(static_cast<s64>(diff) >> 63); // max(diff, 0) - if (current_measure > last_measure) { - last_measure = current_measure; - } - accumulated_ticks += diff; + TimePoint new_time_point{}; + TimePoint current_time_point{}; + do { + current_time_point.pack = time_point.pack; + _mm_mfence(); + const u64 current_measure = __rdtsc(); + u64 diff = current_measure - current_time_point.inner.last_measure; + diff = diff & ~static_cast<u64>(static_cast<s64>(diff) >> 63); // max(diff, 0) + new_time_point.inner.last_measure = current_measure > current_time_point.inner.last_measure + ? current_measure + : current_time_point.inner.last_measure; + new_time_point.inner.accumulated_ticks = current_time_point.inner.accumulated_ticks + diff; + } while (!Common::AtomicCompareAndSwap(time_point.pack.data(), new_time_point.pack, + current_time_point.pack)); /// The clock cannot be more precise than the guest timer, remove the lower bits - return accumulated_ticks & inaccuracy_mask; + return new_time_point.inner.accumulated_ticks & inaccuracy_mask; } void NativeClock::Pause(bool is_paused) { if (!is_paused) { - _mm_mfence(); - last_measure = __rdtsc(); + TimePoint current_time_point{}; + TimePoint new_time_point{}; + do { + current_time_point.pack = time_point.pack; + new_time_point.pack = current_time_point.pack; + _mm_mfence(); + new_time_point.inner.last_measure = __rdtsc(); + } while (!Common::AtomicCompareAndSwap(time_point.pack.data(), new_time_point.pack, + current_time_point.pack)); } } std::chrono::nanoseconds NativeClock::GetTimeNS() { const u64 rtsc_value = GetRTSC(); - return std::chrono::nanoseconds{MultiplyAndDivide64(rtsc_value, 1000000000, rtsc_frequency)}; + return std::chrono::nanoseconds{MultiplyHigh(rtsc_value, ns_rtsc_factor)}; } std::chrono::microseconds NativeClock::GetTimeUS() { const u64 rtsc_value = GetRTSC(); - return std::chrono::microseconds{MultiplyAndDivide64(rtsc_value, 1000000, rtsc_frequency)}; + return std::chrono::microseconds{MultiplyHigh(rtsc_value, us_rtsc_factor)}; } std::chrono::milliseconds NativeClock::GetTimeMS() { const u64 rtsc_value = GetRTSC(); - return std::chrono::milliseconds{MultiplyAndDivide64(rtsc_value, 1000, rtsc_frequency)}; + return std::chrono::milliseconds{MultiplyHigh(rtsc_value, ms_rtsc_factor)}; } u64 NativeClock::GetClockCycles() { const u64 rtsc_value = GetRTSC(); - return MultiplyAndDivide64(rtsc_value, emulated_clock_frequency, rtsc_frequency); + return MultiplyHigh(rtsc_value, clock_rtsc_factor); } u64 NativeClock::GetCPUCycles() { const u64 rtsc_value = GetRTSC(); - return MultiplyAndDivide64(rtsc_value, emulated_cpu_frequency, rtsc_frequency); + return MultiplyHigh(rtsc_value, cpu_rtsc_factor); } } // namespace X64 diff --git a/src/common/x64/native_clock.h b/src/common/x64/native_clock.h index 6d1e32ac8..7cbd400d2 100644 --- a/src/common/x64/native_clock.h +++ b/src/common/x64/native_clock.h @@ -6,7 +6,6 @@ #include <optional> -#include "common/spin_lock.h" #include "common/wall_clock.h" namespace Common { @@ -32,14 +31,28 @@ public: private: u64 GetRTSC(); + union alignas(16) TimePoint { + TimePoint() : pack{} {} + u128 pack{}; + struct Inner { + u64 last_measure{}; + u64 accumulated_ticks{}; + } inner; + }; + /// value used to reduce the native clocks accuracy as some apss rely on /// undefined behavior where the level of accuracy in the clock shouldn't /// be higher. static constexpr u64 inaccuracy_mask = ~(UINT64_C(0x400) - 1); - SpinLock rtsc_serialize{}; - u64 last_measure{}; - u64 accumulated_ticks{}; + TimePoint time_point; + // factors + u64 clock_rtsc_factor{}; + u64 cpu_rtsc_factor{}; + u64 ns_rtsc_factor{}; + u64 us_rtsc_factor{}; + u64 ms_rtsc_factor{}; + u64 rtsc_frequency; }; } // namespace X64 diff --git a/src/core/frontend/input_interpreter.cpp b/src/core/frontend/input_interpreter.cpp index 66ae506cd..ec5fe660e 100644 --- a/src/core/frontend/input_interpreter.cpp +++ b/src/core/frontend/input_interpreter.cpp @@ -25,6 +25,10 @@ void InputInterpreter::PollInput() { button_states[current_index] = button_state; } +bool InputInterpreter::IsButtonPressed(HIDButton button) const { + return (button_states[current_index] & (1U << static_cast<u8>(button))) != 0; +} + bool InputInterpreter::IsButtonPressedOnce(HIDButton button) const { const bool current_press = (button_states[current_index] & (1U << static_cast<u8>(button))) != 0; diff --git a/src/core/frontend/input_interpreter.h b/src/core/frontend/input_interpreter.h index fea9aebe6..73fc47ffb 100644 --- a/src/core/frontend/input_interpreter.h +++ b/src/core/frontend/input_interpreter.h @@ -67,6 +67,27 @@ public: void PollInput(); /** + * Checks whether the button is pressed. + * + * @param button The button to check. + * + * @returns True when the button is pressed. + */ + [[nodiscard]] bool IsButtonPressed(HIDButton button) const; + + /** + * Checks whether any of the buttons in the parameter list is pressed. + * + * @tparam HIDButton The buttons to check. + * + * @returns True when at least one of the buttons is pressed. + */ + template <HIDButton... T> + [[nodiscard]] bool IsAnyButtonPressed() { + return (IsButtonPressed(T) || ...); + } + + /** * The specified button is considered to be pressed once * if it is currently pressed and not pressed previously. * @@ -79,12 +100,12 @@ public: /** * Checks whether any of the buttons in the parameter list is pressed once. * - * @tparam HIDButton The buttons to check. + * @tparam T The buttons to check. * * @returns True when at least one of the buttons is pressed once. */ template <HIDButton... T> - [[nodiscard]] bool IsAnyButtonPressedOnce() { + [[nodiscard]] bool IsAnyButtonPressedOnce() const { return (IsButtonPressedOnce(T) || ...); } @@ -100,12 +121,12 @@ public: /** * Checks whether any of the buttons in the parameter list is held down. * - * @tparam HIDButton The buttons to check. + * @tparam T The buttons to check. * * @returns True when at least one of the buttons is held down. */ template <HIDButton... T> - [[nodiscard]] bool IsAnyButtonHeld() { + [[nodiscard]] bool IsAnyButtonHeld() const { return (IsButtonHeld(T) || ...); } diff --git a/src/core/hle/kernel/k_priority_queue.h b/src/core/hle/kernel/k_priority_queue.h index 99fb8fe93..0dc929040 100644 --- a/src/core/hle/kernel/k_priority_queue.h +++ b/src/core/hle/kernel/k_priority_queue.h @@ -8,11 +8,11 @@ #pragma once #include <array> +#include <bit> #include <concepts> #include "common/assert.h" #include "common/bit_set.h" -#include "common/bit_util.h" #include "common/common_types.h" #include "common/concepts.h" @@ -268,7 +268,7 @@ private: } constexpr s32 GetNextCore(u64& affinity) { - const s32 core = Common::CountTrailingZeroes64(affinity); + const s32 core = std::countr_zero(affinity); ClearAffinityBit(affinity, core); return core; } diff --git a/src/core/hle/kernel/k_scheduler.cpp b/src/core/hle/kernel/k_scheduler.cpp index 42f0ea483..12b5619fb 100644 --- a/src/core/hle/kernel/k_scheduler.cpp +++ b/src/core/hle/kernel/k_scheduler.cpp @@ -5,6 +5,8 @@ // This file references various implementation details from Atmosphere, an open-source firmware for // the Nintendo Switch. Copyright 2018-2020 Atmosphere-NX. +#include <bit> + #include "common/assert.h" #include "common/bit_util.h" #include "common/fiber.h" @@ -31,12 +33,12 @@ static void IncrementScheduledCount(Kernel::Thread* thread) { void KScheduler::RescheduleCores(KernelCore& kernel, u64 cores_pending_reschedule, Core::EmuThreadHandle global_thread) { - u32 current_core = global_thread.host_handle; + const u32 current_core = global_thread.host_handle; bool must_context_switch = global_thread.guest_handle != InvalidHandle && (current_core < Core::Hardware::NUM_CPU_CORES); while (cores_pending_reschedule != 0) { - u32 core = Common::CountTrailingZeroes64(cores_pending_reschedule); + const auto core = static_cast<u32>(std::countr_zero(cores_pending_reschedule)); ASSERT(core < Core::Hardware::NUM_CPU_CORES); if (!must_context_switch || core != current_core) { auto& phys_core = kernel.PhysicalCore(core); @@ -109,7 +111,7 @@ u64 KScheduler::UpdateHighestPriorityThreadsImpl(KernelCore& kernel) { // Idle cores are bad. We're going to try to migrate threads to each idle core in turn. while (idle_cores != 0) { - u32 core_id = Common::CountTrailingZeroes64(idle_cores); + const auto core_id = static_cast<u32>(std::countr_zero(idle_cores)); if (Thread* suggested = priority_queue.GetSuggestedFront(core_id); suggested != nullptr) { s32 migration_candidates[Core::Hardware::NUM_CPU_CORES]; size_t num_candidates = 0; diff --git a/src/core/hle/kernel/memory/page_heap.h b/src/core/hle/kernel/memory/page_heap.h index 22b0de860..131093284 100644 --- a/src/core/hle/kernel/memory/page_heap.h +++ b/src/core/hle/kernel/memory/page_heap.h @@ -8,11 +8,11 @@ #pragma once #include <array> +#include <bit> #include <vector> #include "common/alignment.h" #include "common/assert.h" -#include "common/bit_util.h" #include "common/common_funcs.h" #include "common/common_types.h" #include "core/hle/kernel/memory/memory_types.h" @@ -105,7 +105,7 @@ private: ASSERT(depth == 0); return -1; } - offset = offset * 64 + Common::CountTrailingZeroes64(v); + offset = offset * 64 + static_cast<u32>(std::countr_zero(v)); ++depth; } while (depth < static_cast<s32>(used_depths)); diff --git a/src/core/hle/kernel/process_capability.cpp b/src/core/hle/kernel/process_capability.cpp index 0f128c586..0566311b6 100644 --- a/src/core/hle/kernel/process_capability.cpp +++ b/src/core/hle/kernel/process_capability.cpp @@ -2,6 +2,8 @@ // Licensed under GPLv2 or any later version // Refer to the license.txt file included. +#include <bit> + #include "common/bit_util.h" #include "common/logging/log.h" #include "core/hle/kernel/errors.h" @@ -60,7 +62,7 @@ constexpr CapabilityType GetCapabilityType(u32 value) { u32 GetFlagBitOffset(CapabilityType type) { const auto value = static_cast<u32>(type); - return static_cast<u32>(Common::BitSize<u32>() - Common::CountLeadingZeroes32(value)); + return static_cast<u32>(Common::BitSize<u32>() - static_cast<u32>(std::countl_zero(value))); } } // Anonymous namespace diff --git a/src/tests/CMakeLists.txt b/src/tests/CMakeLists.txt index 8a606b448..6a5c18945 100644 --- a/src/tests/CMakeLists.txt +++ b/src/tests/CMakeLists.txt @@ -1,11 +1,11 @@ add_executable(tests common/bit_field.cpp - common/bit_utils.cpp common/fibers.cpp common/param_package.cpp common/ring_buffer.cpp core/core_timing.cpp tests.cpp + video_core/buffer_base.cpp ) create_target_directory_groups(tests) diff --git a/src/tests/common/bit_utils.cpp b/src/tests/common/bit_utils.cpp deleted file mode 100644 index 479b5995a..000000000 --- a/src/tests/common/bit_utils.cpp +++ /dev/null @@ -1,23 +0,0 @@ -// Copyright 2017 Citra Emulator Project -// Licensed under GPLv2 or any later version -// Refer to the license.txt file included. - -#include <catch2/catch.hpp> -#include <math.h> -#include "common/bit_util.h" - -namespace Common { - -TEST_CASE("BitUtils::CountTrailingZeroes", "[common]") { - REQUIRE(Common::CountTrailingZeroes32(0) == 32); - REQUIRE(Common::CountTrailingZeroes64(0) == 64); - REQUIRE(Common::CountTrailingZeroes32(9) == 0); - REQUIRE(Common::CountTrailingZeroes32(8) == 3); - REQUIRE(Common::CountTrailingZeroes32(0x801000) == 12); - REQUIRE(Common::CountTrailingZeroes64(9) == 0); - REQUIRE(Common::CountTrailingZeroes64(8) == 3); - REQUIRE(Common::CountTrailingZeroes64(0x801000) == 12); - REQUIRE(Common::CountTrailingZeroes64(0x801000000000UL) == 36); -} - -} // namespace Common diff --git a/src/tests/video_core/buffer_base.cpp b/src/tests/video_core/buffer_base.cpp new file mode 100644 index 000000000..651633e9e --- /dev/null +++ b/src/tests/video_core/buffer_base.cpp @@ -0,0 +1,473 @@ +// Copyright 2020 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. + +#include <stdexcept> +#include <unordered_map> + +#include <catch2/catch.hpp> + +#include "common/alignment.h" +#include "common/common_types.h" +#include "video_core/buffer_cache/buffer_base.h" + +namespace { +using VideoCommon::BufferBase; +using Range = std::pair<u64, u64>; + +constexpr u64 PAGE = 4096; +constexpr u64 WORD = 4096 * 64; + +constexpr VAddr c = 0x1328914000; + +class RasterizerInterface { +public: + void UpdatePagesCachedCount(VAddr addr, u64 size, int delta) { + const u64 page_start{addr >> Core::Memory::PAGE_BITS}; + const u64 page_end{(addr + size + Core::Memory::PAGE_SIZE - 1) >> Core::Memory::PAGE_BITS}; + for (u64 page = page_start; page < page_end; ++page) { + int& value = page_table[page]; + value += delta; + if (value < 0) { + throw std::logic_error{"negative page"}; + } + if (value == 0) { + page_table.erase(page); + } + } + } + + [[nodiscard]] int Count(VAddr addr) const noexcept { + const auto it = page_table.find(addr >> Core::Memory::PAGE_BITS); + return it == page_table.end() ? 0 : it->second; + } + + [[nodiscard]] unsigned Count() const noexcept { + unsigned count = 0; + for (const auto [index, value] : page_table) { + count += value; + } + return count; + } + +private: + std::unordered_map<u64, int> page_table; +}; +} // Anonymous namespace + +TEST_CASE("BufferBase: Small buffer", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD); + REQUIRE(rasterizer.Count() == 0); + buffer.UnmarkRegionAsCpuModified(c, WORD); + REQUIRE(rasterizer.Count() == WORD / PAGE); + REQUIRE(buffer.ModifiedCpuRegion(c, WORD) == Range{0, 0}); + + buffer.MarkRegionAsCpuModified(c + PAGE, 1); + REQUIRE(buffer.ModifiedCpuRegion(c, WORD) == Range{PAGE * 1, PAGE * 2}); +} + +TEST_CASE("BufferBase: Large buffer", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 32); + buffer.UnmarkRegionAsCpuModified(c, WORD * 32); + buffer.MarkRegionAsCpuModified(c + 4096, WORD * 4); + REQUIRE(buffer.ModifiedCpuRegion(c, WORD + PAGE * 2) == Range{PAGE, WORD + PAGE * 2}); + REQUIRE(buffer.ModifiedCpuRegion(c + PAGE * 2, PAGE * 6) == Range{PAGE * 2, PAGE * 8}); + REQUIRE(buffer.ModifiedCpuRegion(c, WORD * 32) == Range{PAGE, WORD * 4 + PAGE}); + REQUIRE(buffer.ModifiedCpuRegion(c + WORD * 4, PAGE) == Range{WORD * 4, WORD * 4 + PAGE}); + REQUIRE(buffer.ModifiedCpuRegion(c + WORD * 3 + PAGE * 63, PAGE) == + Range{WORD * 3 + PAGE * 63, WORD * 4}); + + buffer.MarkRegionAsCpuModified(c + WORD * 5 + PAGE * 6, PAGE); + buffer.MarkRegionAsCpuModified(c + WORD * 5 + PAGE * 8, PAGE); + REQUIRE(buffer.ModifiedCpuRegion(c + WORD * 5, WORD) == + Range{WORD * 5 + PAGE * 6, WORD * 5 + PAGE * 9}); + + buffer.UnmarkRegionAsCpuModified(c + WORD * 5 + PAGE * 8, PAGE); + REQUIRE(buffer.ModifiedCpuRegion(c + WORD * 5, WORD) == + Range{WORD * 5 + PAGE * 6, WORD * 5 + PAGE * 7}); + + buffer.MarkRegionAsCpuModified(c + PAGE, WORD * 31 + PAGE * 63); + REQUIRE(buffer.ModifiedCpuRegion(c, WORD * 32) == Range{PAGE, WORD * 32}); + + buffer.UnmarkRegionAsCpuModified(c + PAGE * 4, PAGE); + buffer.UnmarkRegionAsCpuModified(c + PAGE * 6, PAGE); + + buffer.UnmarkRegionAsCpuModified(c, WORD * 32); + REQUIRE(buffer.ModifiedCpuRegion(c, WORD * 32) == Range{0, 0}); +} + +TEST_CASE("BufferBase: Rasterizer counting", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, PAGE * 2); + REQUIRE(rasterizer.Count() == 0); + buffer.UnmarkRegionAsCpuModified(c, PAGE); + REQUIRE(rasterizer.Count() == 1); + buffer.MarkRegionAsCpuModified(c, PAGE * 2); + REQUIRE(rasterizer.Count() == 0); + buffer.UnmarkRegionAsCpuModified(c, PAGE); + buffer.UnmarkRegionAsCpuModified(c + PAGE, PAGE); + REQUIRE(rasterizer.Count() == 2); + buffer.MarkRegionAsCpuModified(c, PAGE * 2); + REQUIRE(rasterizer.Count() == 0); +} + +TEST_CASE("BufferBase: Basic range", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD); + buffer.UnmarkRegionAsCpuModified(c, WORD); + buffer.MarkRegionAsCpuModified(c, PAGE); + int num = 0; + buffer.ForEachUploadRange(c, WORD, [&](u64 offset, u64 size) { + REQUIRE(offset == 0U); + REQUIRE(size == PAGE); + ++num; + }); + REQUIRE(num == 1U); +} + +TEST_CASE("BufferBase: Border upload", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 2); + buffer.UnmarkRegionAsCpuModified(c, WORD * 2); + buffer.MarkRegionAsCpuModified(c + WORD - PAGE, PAGE * 2); + buffer.ForEachUploadRange(c, WORD * 2, [](u64 offset, u64 size) { + REQUIRE(offset == WORD - PAGE); + REQUIRE(size == PAGE * 2); + }); +} + +TEST_CASE("BufferBase: Border upload range", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 2); + buffer.UnmarkRegionAsCpuModified(c, WORD * 2); + buffer.MarkRegionAsCpuModified(c + WORD - PAGE, PAGE * 2); + buffer.ForEachUploadRange(c + WORD - PAGE, PAGE * 2, [](u64 offset, u64 size) { + REQUIRE(offset == WORD - PAGE); + REQUIRE(size == PAGE * 2); + }); + buffer.MarkRegionAsCpuModified(c + WORD - PAGE, PAGE * 2); + buffer.ForEachUploadRange(c + WORD - PAGE, PAGE, [](u64 offset, u64 size) { + REQUIRE(offset == WORD - PAGE); + REQUIRE(size == PAGE); + }); + buffer.ForEachUploadRange(c + WORD, PAGE, [](u64 offset, u64 size) { + REQUIRE(offset == WORD); + REQUIRE(size == PAGE); + }); +} + +TEST_CASE("BufferBase: Border upload partial range", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 2); + buffer.UnmarkRegionAsCpuModified(c, WORD * 2); + buffer.MarkRegionAsCpuModified(c + WORD - PAGE, PAGE * 2); + buffer.ForEachUploadRange(c + WORD - 1, 2, [](u64 offset, u64 size) { + REQUIRE(offset == WORD - PAGE); + REQUIRE(size == PAGE * 2); + }); + buffer.MarkRegionAsCpuModified(c + WORD - PAGE, PAGE * 2); + buffer.ForEachUploadRange(c + WORD - 1, 1, [](u64 offset, u64 size) { + REQUIRE(offset == WORD - PAGE); + REQUIRE(size == PAGE); + }); + buffer.ForEachUploadRange(c + WORD + 50, 1, [](u64 offset, u64 size) { + REQUIRE(offset == WORD); + REQUIRE(size == PAGE); + }); +} + +TEST_CASE("BufferBase: Partial word uploads", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, 0x9d000); + int num = 0; + buffer.ForEachUploadRange(c, WORD, [&](u64 offset, u64 size) { + REQUIRE(offset == 0U); + REQUIRE(size == WORD); + ++num; + }); + REQUIRE(num == 1); + buffer.ForEachUploadRange(c + WORD, WORD, [&](u64 offset, u64 size) { + REQUIRE(offset == WORD); + REQUIRE(size == WORD); + ++num; + }); + REQUIRE(num == 2); + buffer.ForEachUploadRange(c + 0x79000, 0x24000, [&](u64 offset, u64 size) { + REQUIRE(offset == WORD * 2); + REQUIRE(size == PAGE * 0x1d); + ++num; + }); + REQUIRE(num == 3); +} + +TEST_CASE("BufferBase: Partial page upload", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD); + buffer.UnmarkRegionAsCpuModified(c, WORD); + int num = 0; + buffer.MarkRegionAsCpuModified(c + PAGE * 2, PAGE); + buffer.MarkRegionAsCpuModified(c + PAGE * 9, PAGE); + buffer.ForEachUploadRange(c, PAGE * 3, [&](u64 offset, u64 size) { + REQUIRE(offset == PAGE * 2); + REQUIRE(size == PAGE); + ++num; + }); + REQUIRE(num == 1); + buffer.ForEachUploadRange(c + PAGE * 7, PAGE * 3, [&](u64 offset, u64 size) { + REQUIRE(offset == PAGE * 9); + REQUIRE(size == PAGE); + ++num; + }); + REQUIRE(num == 2); +} + +TEST_CASE("BufferBase: Partial page upload with multiple words on the right") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 8); + buffer.UnmarkRegionAsCpuModified(c, WORD * 8); + buffer.MarkRegionAsCpuModified(c + PAGE * 13, WORD * 7); + int num = 0; + buffer.ForEachUploadRange(c + PAGE * 10, WORD * 7, [&](u64 offset, u64 size) { + REQUIRE(offset == PAGE * 13); + REQUIRE(size == WORD * 7 - PAGE * 3); + ++num; + }); + REQUIRE(num == 1); + buffer.ForEachUploadRange(c + PAGE, WORD * 8, [&](u64 offset, u64 size) { + REQUIRE(offset == WORD * 7 + PAGE * 10); + REQUIRE(size == PAGE * 3); + ++num; + }); + REQUIRE(num == 2); +} + +TEST_CASE("BufferBase: Partial page upload with multiple words on the left", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 8); + buffer.UnmarkRegionAsCpuModified(c, WORD * 8); + buffer.MarkRegionAsCpuModified(c + PAGE * 13, WORD * 7); + int num = 0; + buffer.ForEachUploadRange(c + PAGE * 16, WORD * 7, [&](u64 offset, u64 size) { + REQUIRE(offset == PAGE * 16); + REQUIRE(size == WORD * 7 - PAGE * 3); + ++num; + }); + REQUIRE(num == 1); + buffer.ForEachUploadRange(c + PAGE, WORD, [&](u64 offset, u64 size) { + REQUIRE(offset == PAGE * 13); + REQUIRE(size == PAGE * 3); + ++num; + }); + REQUIRE(num == 2); +} + +TEST_CASE("BufferBase: Partial page upload with multiple words in the middle", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 8); + buffer.UnmarkRegionAsCpuModified(c, WORD * 8); + buffer.MarkRegionAsCpuModified(c + PAGE * 13, PAGE * 140); + int num = 0; + buffer.ForEachUploadRange(c + PAGE * 16, WORD, [&](u64 offset, u64 size) { + REQUIRE(offset == PAGE * 16); + REQUIRE(size == WORD); + ++num; + }); + REQUIRE(num == 1); + buffer.ForEachUploadRange(c, WORD, [&](u64 offset, u64 size) { + REQUIRE(offset == PAGE * 13); + REQUIRE(size == PAGE * 3); + ++num; + }); + REQUIRE(num == 2); + buffer.ForEachUploadRange(c, WORD * 8, [&](u64 offset, u64 size) { + REQUIRE(offset == WORD + PAGE * 16); + REQUIRE(size == PAGE * 73); + ++num; + }); + REQUIRE(num == 3); +} + +TEST_CASE("BufferBase: Empty right bits", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 2048); + buffer.UnmarkRegionAsCpuModified(c, WORD * 2048); + buffer.MarkRegionAsCpuModified(c + WORD - PAGE, PAGE * 2); + buffer.ForEachUploadRange(c, WORD * 2048, [](u64 offset, u64 size) { + REQUIRE(offset == WORD - PAGE); + REQUIRE(size == PAGE * 2); + }); +} + +TEST_CASE("BufferBase: Out of bound ranges 1", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD); + buffer.UnmarkRegionAsCpuModified(c, WORD); + buffer.MarkRegionAsCpuModified(c, PAGE); + int num = 0; + buffer.ForEachUploadRange(c - WORD, WORD, [&](u64 offset, u64 size) { ++num; }); + buffer.ForEachUploadRange(c + WORD, WORD, [&](u64 offset, u64 size) { ++num; }); + buffer.ForEachUploadRange(c - PAGE, PAGE, [&](u64 offset, u64 size) { ++num; }); + REQUIRE(num == 0); + buffer.ForEachUploadRange(c - PAGE, PAGE * 2, [&](u64 offset, u64 size) { ++num; }); + REQUIRE(num == 1); + buffer.MarkRegionAsCpuModified(c, WORD); + REQUIRE(rasterizer.Count() == 0); +} + +TEST_CASE("BufferBase: Out of bound ranges 2", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, 0x22000); + REQUIRE_NOTHROW(buffer.UnmarkRegionAsCpuModified(c + 0x22000, PAGE)); + REQUIRE_NOTHROW(buffer.UnmarkRegionAsCpuModified(c + 0x28000, PAGE)); + REQUIRE(rasterizer.Count() == 0); + REQUIRE_NOTHROW(buffer.UnmarkRegionAsCpuModified(c + 0x21100, PAGE - 0x100)); + REQUIRE(rasterizer.Count() == 1); + REQUIRE_NOTHROW(buffer.UnmarkRegionAsCpuModified(c - 0x1000, PAGE * 2)); + buffer.UnmarkRegionAsCpuModified(c - 0x3000, PAGE * 2); + buffer.UnmarkRegionAsCpuModified(c - 0x2000, PAGE * 2); + REQUIRE(rasterizer.Count() == 2); +} + +TEST_CASE("BufferBase: Out of bound ranges 3", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, 0x310720); + buffer.UnmarkRegionAsCpuModified(c, 0x310720); + REQUIRE(rasterizer.Count(c) == 1); + REQUIRE(rasterizer.Count(c + PAGE) == 1); + REQUIRE(rasterizer.Count(c + WORD) == 1); + REQUIRE(rasterizer.Count(c + WORD + PAGE) == 1); +} + +TEST_CASE("BufferBase: Sparse regions 1", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD); + buffer.UnmarkRegionAsCpuModified(c, WORD); + buffer.MarkRegionAsCpuModified(c + PAGE * 1, PAGE); + buffer.MarkRegionAsCpuModified(c + PAGE * 3, PAGE * 4); + buffer.ForEachUploadRange(c, WORD, [i = 0](u64 offset, u64 size) mutable { + static constexpr std::array<u64, 2> offsets{PAGE, PAGE * 3}; + static constexpr std::array<u64, 2> sizes{PAGE, PAGE * 4}; + REQUIRE(offset == offsets.at(i)); + REQUIRE(size == sizes.at(i)); + ++i; + }); +} + +TEST_CASE("BufferBase: Sparse regions 2", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, 0x22000); + buffer.UnmarkRegionAsCpuModified(c, 0x22000); + REQUIRE(rasterizer.Count() == 0x22); + buffer.MarkRegionAsCpuModified(c + PAGE * 0x1B, PAGE); + buffer.MarkRegionAsCpuModified(c + PAGE * 0x21, PAGE); + buffer.ForEachUploadRange(c, WORD, [i = 0](u64 offset, u64 size) mutable { + static constexpr std::array<u64, 2> offsets{PAGE * 0x1B, PAGE * 0x21}; + static constexpr std::array<u64, 2> sizes{PAGE, PAGE}; + REQUIRE(offset == offsets.at(i)); + REQUIRE(size == sizes.at(i)); + ++i; + }); +} + +TEST_CASE("BufferBase: Single page modified range", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, PAGE); + REQUIRE(buffer.IsRegionCpuModified(c, PAGE)); + buffer.UnmarkRegionAsCpuModified(c, PAGE); + REQUIRE(!buffer.IsRegionCpuModified(c, PAGE)); +} + +TEST_CASE("BufferBase: Two page modified range", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, PAGE * 2); + REQUIRE(buffer.IsRegionCpuModified(c, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c, PAGE * 2)); + buffer.UnmarkRegionAsCpuModified(c, PAGE); + REQUIRE(!buffer.IsRegionCpuModified(c, PAGE)); +} + +TEST_CASE("BufferBase: Multi word modified ranges", "[video_core]") { + for (int offset = 0; offset < 4; ++offset) { + const VAddr address = c + WORD * offset; + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, address, WORD * 4); + REQUIRE(buffer.IsRegionCpuModified(address, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(address + PAGE * 48, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(address + PAGE * 56, PAGE)); + + buffer.UnmarkRegionAsCpuModified(address + PAGE * 32, PAGE); + REQUIRE(buffer.IsRegionCpuModified(address + PAGE, WORD)); + REQUIRE(buffer.IsRegionCpuModified(address + PAGE * 31, PAGE)); + REQUIRE(!buffer.IsRegionCpuModified(address + PAGE * 32, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(address + PAGE * 33, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(address + PAGE * 31, PAGE * 2)); + REQUIRE(buffer.IsRegionCpuModified(address + PAGE * 32, PAGE * 2)); + + buffer.UnmarkRegionAsCpuModified(address + PAGE * 33, PAGE); + REQUIRE(!buffer.IsRegionCpuModified(address + PAGE * 32, PAGE * 2)); + } +} + +TEST_CASE("BufferBase: Single page in large buffer", "[video_core]") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 16); + buffer.UnmarkRegionAsCpuModified(c, WORD * 16); + REQUIRE(!buffer.IsRegionCpuModified(c, WORD * 16)); + + buffer.MarkRegionAsCpuModified(c + WORD * 12 + PAGE * 8, PAGE); + REQUIRE(buffer.IsRegionCpuModified(c, WORD * 16)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 10, WORD * 2)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 11, WORD * 2)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 12, WORD * 2)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 12 + PAGE * 4, PAGE * 8)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 12 + PAGE * 6, PAGE * 8)); + REQUIRE(!buffer.IsRegionCpuModified(c + WORD * 12 + PAGE * 6, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 12 + PAGE * 7, PAGE * 2)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 12 + PAGE * 8, PAGE * 2)); +} + +TEST_CASE("BufferBase: Out of bounds region query") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 16); + REQUIRE(!buffer.IsRegionCpuModified(c - PAGE, PAGE)); + REQUIRE(!buffer.IsRegionCpuModified(c - PAGE * 2, PAGE)); + REQUIRE(!buffer.IsRegionCpuModified(c + WORD * 16, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + WORD * 16 - PAGE, WORD * 64)); + REQUIRE(!buffer.IsRegionCpuModified(c + WORD * 16, WORD * 64)); +} + +TEST_CASE("BufferBase: Wrap word regions") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD * 2); + buffer.UnmarkRegionAsCpuModified(c, WORD * 2); + buffer.MarkRegionAsCpuModified(c + PAGE * 63, PAGE * 2); + REQUIRE(buffer.IsRegionCpuModified(c, WORD * 2)); + REQUIRE(!buffer.IsRegionCpuModified(c + PAGE * 62, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 63, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 64, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 63, PAGE * 2)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 63, PAGE * 8)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 60, PAGE * 8)); + + REQUIRE(!buffer.IsRegionCpuModified(c + PAGE * 127, WORD * 16)); + buffer.MarkRegionAsCpuModified(c + PAGE * 127, PAGE); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 127, WORD * 16)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 127, PAGE)); + REQUIRE(!buffer.IsRegionCpuModified(c + PAGE * 126, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE * 126, PAGE * 2)); + REQUIRE(!buffer.IsRegionCpuModified(c + PAGE * 128, WORD * 16)); +} + +TEST_CASE("BufferBase: Unaligned page region query") { + RasterizerInterface rasterizer; + BufferBase buffer(rasterizer, c, WORD); + buffer.UnmarkRegionAsCpuModified(c, WORD); + buffer.MarkRegionAsCpuModified(c + 4000, 1000); + REQUIRE(buffer.IsRegionCpuModified(c, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + PAGE, PAGE)); + REQUIRE(buffer.IsRegionCpuModified(c + 4000, 1000)); + REQUIRE(buffer.IsRegionCpuModified(c + 4000, 1)); +} diff --git a/src/video_core/CMakeLists.txt b/src/video_core/CMakeLists.txt index 25a4b1c5b..e01ea55ab 100644 --- a/src/video_core/CMakeLists.txt +++ b/src/video_core/CMakeLists.txt @@ -1,6 +1,7 @@ add_subdirectory(host_shaders) add_library(video_core STATIC + buffer_cache/buffer_base.h buffer_cache/buffer_block.h buffer_cache/buffer_cache.h buffer_cache/map_interval.cpp @@ -135,8 +136,6 @@ add_library(video_core STATIC renderer_vulkan/vk_graphics_pipeline.h renderer_vulkan/vk_master_semaphore.cpp renderer_vulkan/vk_master_semaphore.h - renderer_vulkan/vk_memory_manager.cpp - renderer_vulkan/vk_memory_manager.h renderer_vulkan/vk_pipeline_cache.cpp renderer_vulkan/vk_pipeline_cache.h renderer_vulkan/vk_query_cache.cpp @@ -259,6 +258,8 @@ add_library(video_core STATIC vulkan_common/vulkan_instance.h vulkan_common/vulkan_library.cpp vulkan_common/vulkan_library.h + vulkan_common/vulkan_memory_allocator.cpp + vulkan_common/vulkan_memory_allocator.h vulkan_common/vulkan_surface.cpp vulkan_common/vulkan_surface.h vulkan_common/vulkan_wrapper.cpp diff --git a/src/video_core/buffer_cache/buffer_base.h b/src/video_core/buffer_cache/buffer_base.h new file mode 100644 index 000000000..ee8602ce9 --- /dev/null +++ b/src/video_core/buffer_cache/buffer_base.h @@ -0,0 +1,495 @@ +// Copyright 2020 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. + +#pragma once + +#include <algorithm> +#include <bit> +#include <limits> +#include <utility> + +#include "common/alignment.h" +#include "common/common_funcs.h" +#include "common/common_types.h" +#include "common/div_ceil.h" +#include "core/memory.h" + +namespace VideoCommon { + +enum class BufferFlagBits { + Picked = 1 << 0, +}; +DECLARE_ENUM_FLAG_OPERATORS(BufferFlagBits) + +/// Tag for creating null buffers with no storage or size +struct NullBufferParams {}; + +/** + * Range tracking buffer container. + * + * It keeps track of the modified CPU and GPU ranges on a CPU page granularity, notifying the given + * rasterizer about state changes in the tracking behavior of the buffer. + * + * The buffer size and address is forcefully aligned to CPU page boundaries. + */ +template <class RasterizerInterface> +class BufferBase { + static constexpr u64 PAGES_PER_WORD = 64; + static constexpr u64 BYTES_PER_PAGE = Core::Memory::PAGE_SIZE; + static constexpr u64 BYTES_PER_WORD = PAGES_PER_WORD * BYTES_PER_PAGE; + + /// Vector tracking modified pages tightly packed with small vector optimization + union WrittenWords { + /// Returns the pointer to the words state + [[nodiscard]] const u64* Pointer(bool is_short) const noexcept { + return is_short ? &stack : heap; + } + + /// Returns the pointer to the words state + [[nodiscard]] u64* Pointer(bool is_short) noexcept { + return is_short ? &stack : heap; + } + + u64 stack = 0; ///< Small buffers storage + u64* heap; ///< Not-small buffers pointer to the storage + }; + + struct GpuCpuWords { + explicit GpuCpuWords() = default; + explicit GpuCpuWords(u64 size_bytes_) : size_bytes{size_bytes_} { + if (IsShort()) { + cpu.stack = ~u64{0}; + gpu.stack = 0; + } else { + // Share allocation between CPU and GPU pages and set their default values + const size_t num_words = NumWords(); + u64* const alloc = new u64[num_words * 2]; + cpu.heap = alloc; + gpu.heap = alloc + num_words; + std::fill_n(cpu.heap, num_words, ~u64{0}); + std::fill_n(gpu.heap, num_words, 0); + } + // Clean up tailing bits + const u64 last_local_page = + Common::DivCeil(size_bytes % BYTES_PER_WORD, BYTES_PER_PAGE); + const u64 shift = (PAGES_PER_WORD - last_local_page) % PAGES_PER_WORD; + u64& last_word = cpu.Pointer(IsShort())[NumWords() - 1]; + last_word = (last_word << shift) >> shift; + } + + ~GpuCpuWords() { + Release(); + } + + GpuCpuWords& operator=(GpuCpuWords&& rhs) noexcept { + Release(); + size_bytes = rhs.size_bytes; + cpu = rhs.cpu; + gpu = rhs.gpu; + rhs.cpu.heap = nullptr; + return *this; + } + + GpuCpuWords(GpuCpuWords&& rhs) noexcept + : size_bytes{rhs.size_bytes}, cpu{rhs.cpu}, gpu{rhs.gpu} { + rhs.cpu.heap = nullptr; + } + + GpuCpuWords& operator=(const GpuCpuWords&) = delete; + GpuCpuWords(const GpuCpuWords&) = delete; + + /// Returns true when the buffer fits in the small vector optimization + [[nodiscard]] bool IsShort() const noexcept { + return size_bytes <= BYTES_PER_WORD; + } + + /// Returns the number of words of the buffer + [[nodiscard]] size_t NumWords() const noexcept { + return Common::DivCeil(size_bytes, BYTES_PER_WORD); + } + + /// Release buffer resources + void Release() { + if (!IsShort()) { + // CPU written words is the base for the heap allocation + delete[] cpu.heap; + } + } + + u64 size_bytes = 0; + WrittenWords cpu; + WrittenWords gpu; + }; + +public: + explicit BufferBase(RasterizerInterface& rasterizer_, VAddr cpu_addr_, u64 size_bytes) + : rasterizer{&rasterizer_}, cpu_addr{Common::AlignDown(cpu_addr_, BYTES_PER_PAGE)}, + words(Common::AlignUp(size_bytes + (cpu_addr_ - cpu_addr), BYTES_PER_PAGE)) {} + + explicit BufferBase(NullBufferParams) {} + + BufferBase& operator=(const BufferBase&) = delete; + BufferBase(const BufferBase&) = delete; + + /// Returns the inclusive CPU modified range in a begin end pair + [[nodiscard]] std::pair<u64, u64> ModifiedCpuRegion(VAddr query_cpu_addr, + u64 query_size) const noexcept { + const u64 offset = query_cpu_addr - cpu_addr; + return ModifiedRegion<false>(offset, query_size); + } + + /// Returns the inclusive GPU modified range in a begin end pair + [[nodiscard]] std::pair<u64, u64> ModifiedGpuRegion(VAddr query_cpu_addr, + u64 query_size) const noexcept { + const u64 offset = query_cpu_addr - cpu_addr; + return ModifiedRegion<true>(offset, query_size); + } + + /// Returns true if a region has been modified from the CPU + [[nodiscard]] bool IsRegionCpuModified(VAddr query_cpu_addr, u64 query_size) const noexcept { + const u64 offset = query_cpu_addr - cpu_addr; + return IsRegionModified<false>(offset, query_size); + } + + /// Returns true if a region has been modified from the GPU + [[nodiscard]] bool IsRegionGpuModified(VAddr query_cpu_addr, u64 query_size) const noexcept { + const u64 offset = query_cpu_addr - cpu_addr; + return IsRegionModified<true>(offset, query_size); + } + + /// Mark region as CPU modified, notifying the rasterizer about this change + void MarkRegionAsCpuModified(VAddr dirty_cpu_addr, u64 size) { + ChangeRegionState<true, true>(words.cpu, dirty_cpu_addr, size); + } + + /// Unmark region as CPU modified, notifying the rasterizer about this change + void UnmarkRegionAsCpuModified(VAddr dirty_cpu_addr, u64 size) { + ChangeRegionState<false, true>(words.cpu, dirty_cpu_addr, size); + } + + /// Mark region as modified from the host GPU + void MarkRegionAsGpuModified(VAddr dirty_cpu_addr, u64 size) noexcept { + ChangeRegionState<true, false>(words.gpu, dirty_cpu_addr, size); + } + + /// Unmark region as modified from the host GPU + void UnmarkRegionAsGpuModified(VAddr dirty_cpu_addr, u64 size) noexcept { + ChangeRegionState<false, false>(words.gpu, dirty_cpu_addr, size); + } + + /// Call 'func' for each CPU modified range and unmark those pages as CPU modified + template <typename Func> + void ForEachUploadRange(VAddr query_cpu_range, u64 size, Func&& func) { + ForEachModifiedRange<false, true>(query_cpu_range, size, func); + } + + /// Call 'func' for each GPU modified range and unmark those pages as GPU modified + template <typename Func> + void ForEachDownloadRange(VAddr query_cpu_range, u64 size, Func&& func) { + ForEachModifiedRange<true, false>(query_cpu_range, size, func); + } + + /// Call 'func' for each GPU modified range and unmark those pages as GPU modified + template <typename Func> + void ForEachDownloadRange(Func&& func) { + ForEachModifiedRange<true, false>(cpu_addr, SizeBytes(), func); + } + + /// Mark buffer as picked + void Pick() noexcept { + flags |= BufferFlagBits::Picked; + } + + /// Unmark buffer as picked + void Unpick() noexcept { + flags &= ~BufferFlagBits::Picked; + } + + /// Returns true when vaddr -> vaddr+size is fully contained in the buffer + [[nodiscard]] bool IsInBounds(VAddr addr, u64 size) const noexcept { + return addr >= cpu_addr && addr + size <= cpu_addr + SizeBytes(); + } + + /// Returns true if the buffer has been marked as picked + [[nodiscard]] bool IsPicked() const noexcept { + return True(flags & BufferFlagBits::Picked); + } + + /// Returns the base CPU address of the buffer + [[nodiscard]] VAddr CpuAddr() const noexcept { + return cpu_addr; + } + + /// Returns the offset relative to the given CPU address + /// @pre IsInBounds returns true + [[nodiscard]] u32 Offset(VAddr other_cpu_addr) const noexcept { + return static_cast<u32>(other_cpu_addr - cpu_addr); + } + + /// Returns the size in bytes of the buffer + [[nodiscard]] u64 SizeBytes() const noexcept { + return words.size_bytes; + } + +private: + /** + * Change the state of a range of pages + * + * @param written_words Pages to be marked or unmarked as modified + * @param dirty_addr Base address to mark or unmark as modified + * @param size Size in bytes to mark or unmark as modified + * + * @tparam enable True when the bits will be set to one, false for zero + * @tparam notify_rasterizer True when the rasterizer has to be notified about the changes + */ + template <bool enable, bool notify_rasterizer> + void ChangeRegionState(WrittenWords& written_words, u64 dirty_addr, + s64 size) noexcept(!notify_rasterizer) { + const s64 difference = dirty_addr - cpu_addr; + const u64 offset = std::max<s64>(difference, 0); + size += std::min<s64>(difference, 0); + if (offset >= SizeBytes() || size < 0) { + return; + } + u64* const state_words = written_words.Pointer(IsShort()); + const u64 offset_end = std::min(offset + size, SizeBytes()); + const u64 begin_page_index = offset / BYTES_PER_PAGE; + const u64 begin_word_index = begin_page_index / PAGES_PER_WORD; + const u64 end_page_index = Common::DivCeil(offset_end, BYTES_PER_PAGE); + const u64 end_word_index = Common::DivCeil(end_page_index, PAGES_PER_WORD); + u64 page_index = begin_page_index % PAGES_PER_WORD; + u64 word_index = begin_word_index; + while (word_index < end_word_index) { + const u64 next_word_first_page = (word_index + 1) * PAGES_PER_WORD; + const u64 left_offset = + std::min(next_word_first_page - end_page_index, PAGES_PER_WORD) % PAGES_PER_WORD; + const u64 right_offset = page_index; + u64 bits = ~u64{0}; + bits = (bits >> right_offset) << right_offset; + bits = (bits << left_offset) >> left_offset; + if constexpr (notify_rasterizer) { + NotifyRasterizer<!enable>(word_index, state_words[word_index], bits); + } + if constexpr (enable) { + state_words[word_index] |= bits; + } else { + state_words[word_index] &= ~bits; + } + page_index = 0; + ++word_index; + } + } + + /** + * Notify rasterizer about changes in the CPU tracking state of a word in the buffer + * + * @param word_index Index to the word to notify to the rasterizer + * @param current_bits Current state of the word + * @param new_bits New state of the word + * + * @tparam add_to_rasterizer True when the rasterizer should start tracking the new pages + */ + template <bool add_to_rasterizer> + void NotifyRasterizer(u64 word_index, u64 current_bits, u64 new_bits) { + u64 changed_bits = (add_to_rasterizer ? current_bits : ~current_bits) & new_bits; + VAddr addr = cpu_addr + word_index * BYTES_PER_WORD; + while (changed_bits != 0) { + const int empty_bits = std::countr_zero(changed_bits); + addr += empty_bits * BYTES_PER_PAGE; + changed_bits >>= empty_bits; + + const u32 continuous_bits = std::countr_one(changed_bits); + const u64 size = continuous_bits * BYTES_PER_PAGE; + const VAddr begin_addr = addr; + addr += size; + changed_bits = continuous_bits < PAGES_PER_WORD ? (changed_bits >> continuous_bits) : 0; + rasterizer->UpdatePagesCachedCount(begin_addr, size, add_to_rasterizer ? 1 : -1); + } + } + + /** + * Loop over each page in the given range, turn off those bits and notify the rasterizer if + * needed. Call the given function on each turned off range. + * + * @param query_cpu_range Base CPU address to loop over + * @param size Size in bytes of the CPU range to loop over + * @param func Function to call for each turned off region + * + * @tparam gpu True for host GPU pages, false for CPU pages + * @tparam notify_rasterizer True when the rasterizer should be notified about state changes + */ + template <bool gpu, bool notify_rasterizer, typename Func> + void ForEachModifiedRange(VAddr query_cpu_range, s64 size, Func&& func) { + const s64 difference = query_cpu_range - cpu_addr; + const u64 query_begin = std::max<s64>(difference, 0); + size += std::min<s64>(difference, 0); + if (query_begin >= SizeBytes() || size < 0) { + return; + } + const u64* const cpu_words = words.cpu.Pointer(IsShort()); + const u64 query_end = query_begin + std::min(static_cast<u64>(size), SizeBytes()); + u64* const state_words = (gpu ? words.gpu : words.cpu).Pointer(IsShort()); + u64* const words_begin = state_words + query_begin / BYTES_PER_WORD; + u64* const words_end = state_words + Common::DivCeil(query_end, BYTES_PER_WORD); + + const auto modified = [](u64 word) { return word != 0; }; + const auto first_modified_word = std::find_if(words_begin, words_end, modified); + if (first_modified_word == words_end) { + // Exit early when the buffer is not modified + return; + } + const auto last_modified_word = std::find_if_not(first_modified_word, words_end, modified); + + const u64 word_index_begin = std::distance(state_words, first_modified_word); + const u64 word_index_end = std::distance(state_words, last_modified_word); + + const unsigned local_page_begin = std::countr_zero(*first_modified_word); + const unsigned local_page_end = PAGES_PER_WORD - std::countl_zero(last_modified_word[-1]); + const u64 word_page_begin = word_index_begin * PAGES_PER_WORD; + const u64 word_page_end = (word_index_end - 1) * PAGES_PER_WORD; + const u64 query_page_begin = query_begin / BYTES_PER_PAGE; + const u64 query_page_end = Common::DivCeil(query_end, BYTES_PER_PAGE); + const u64 page_index_begin = std::max(word_page_begin + local_page_begin, query_page_begin); + const u64 page_index_end = std::min(word_page_end + local_page_end, query_page_end); + const u64 first_word_page_begin = page_index_begin % PAGES_PER_WORD; + const u64 last_word_page_end = (page_index_end - 1) % PAGES_PER_WORD + 1; + + u64 page_begin = first_word_page_begin; + u64 current_base = 0; + u64 current_size = 0; + bool on_going = false; + for (u64 word_index = word_index_begin; word_index < word_index_end; ++word_index) { + const bool is_last_word = word_index + 1 == word_index_end; + const u64 page_end = is_last_word ? last_word_page_end : PAGES_PER_WORD; + const u64 right_offset = page_begin; + const u64 left_offset = PAGES_PER_WORD - page_end; + u64 bits = ~u64{0}; + bits = (bits >> right_offset) << right_offset; + bits = (bits << left_offset) >> left_offset; + + const u64 current_word = state_words[word_index] & bits; + state_words[word_index] &= ~bits; + + // Exclude CPU modified pages when visiting GPU pages + const u64 word = current_word & ~(gpu ? cpu_words[word_index] : 0); + if constexpr (notify_rasterizer) { + NotifyRasterizer<true>(word_index, word, ~u64{0}); + } + u64 page = page_begin; + page_begin = 0; + + while (page < page_end) { + const int empty_bits = std::countr_zero(word >> page); + if (on_going && empty_bits != 0) { + InvokeModifiedRange(func, current_size, current_base); + current_size = 0; + on_going = false; + } + page += empty_bits; + + const int continuous_bits = std::countr_one(word >> page); + if (!on_going && continuous_bits != 0) { + current_base = word_index * PAGES_PER_WORD + page; + on_going = true; + } + current_size += continuous_bits; + page += continuous_bits; + } + } + if (on_going && current_size > 0) { + InvokeModifiedRange(func, current_size, current_base); + } + } + + template <typename Func> + void InvokeModifiedRange(Func&& func, u64 current_size, u64 current_base) { + const u64 current_size_bytes = current_size * BYTES_PER_PAGE; + const u64 offset_begin = current_base * BYTES_PER_PAGE; + const u64 offset_end = std::min(offset_begin + current_size_bytes, SizeBytes()); + func(offset_begin, offset_end - offset_begin); + } + + /** + * Returns true when a region has been modified + * + * @param offset Offset in bytes from the start of the buffer + * @param size Size in bytes of the region to query for modifications + */ + template <bool gpu> + [[nodiscard]] bool IsRegionModified(u64 offset, u64 size) const noexcept { + const u64* const cpu_words = words.cpu.Pointer(IsShort()); + const u64* const state_words = (gpu ? words.gpu : words.cpu).Pointer(IsShort()); + const u64 num_query_words = size / BYTES_PER_WORD + 1; + const u64 word_begin = offset / BYTES_PER_WORD; + const u64 word_end = std::min(word_begin + num_query_words, NumWords()); + const u64 page_limit = Common::DivCeil(offset + size, BYTES_PER_PAGE); + u64 page_index = (offset / BYTES_PER_PAGE) % PAGES_PER_WORD; + for (u64 word_index = word_begin; word_index < word_end; ++word_index, page_index = 0) { + const u64 word = state_words[word_index] & ~(gpu ? cpu_words[word_index] : 0); + if (word == 0) { + continue; + } + const u64 page_end = std::min((word_index + 1) * PAGES_PER_WORD, page_limit); + const u64 local_page_end = page_end % PAGES_PER_WORD; + const u64 page_end_shift = (PAGES_PER_WORD - local_page_end) % PAGES_PER_WORD; + if (((word >> page_index) << page_index) << page_end_shift != 0) { + return true; + } + } + return false; + } + + /** + * Returns a begin end pair with the inclusive modified region + * + * @param offset Offset in bytes from the start of the buffer + * @param size Size in bytes of the region to query for modifications + * + * @tparam gpu True to query GPU modified pages, false for CPU pages + */ + template <bool gpu> + [[nodiscard]] std::pair<u64, u64> ModifiedRegion(u64 offset, u64 size) const noexcept { + const u64* const cpu_words = words.cpu.Pointer(IsShort()); + const u64* const state_words = (gpu ? words.gpu : words.cpu).Pointer(IsShort()); + const u64 num_query_words = size / BYTES_PER_WORD + 1; + const u64 word_begin = offset / BYTES_PER_WORD; + const u64 word_end = std::min(word_begin + num_query_words, NumWords()); + const u64 page_base = offset / BYTES_PER_PAGE; + const u64 page_limit = Common::DivCeil(offset + size, BYTES_PER_PAGE); + u64 begin = std::numeric_limits<u64>::max(); + u64 end = 0; + for (u64 word_index = word_begin; word_index < word_end; ++word_index) { + const u64 word = state_words[word_index] & ~(gpu ? cpu_words[word_index] : 0); + if (word == 0) { + continue; + } + const u64 local_page_begin = std::countr_zero(word); + const u64 local_page_end = PAGES_PER_WORD - std::countl_zero(word); + const u64 page_index = word_index * PAGES_PER_WORD; + const u64 page_begin = std::max(page_index + local_page_begin, page_base); + const u64 page_end = std::min(page_index + local_page_end, page_limit); + begin = std::min(begin, page_begin); + end = std::max(end, page_end); + } + static constexpr std::pair<u64, u64> EMPTY{0, 0}; + return begin < end ? std::make_pair(begin * BYTES_PER_PAGE, end * BYTES_PER_PAGE) : EMPTY; + } + + /// Returns the number of words of the buffer + [[nodiscard]] size_t NumWords() const noexcept { + return words.NumWords(); + } + + /// Returns true when the buffer fits in the small vector optimization + [[nodiscard]] bool IsShort() const noexcept { + return words.IsShort(); + } + + RasterizerInterface* rasterizer = nullptr; + VAddr cpu_addr = 0; + GpuCpuWords words; + BufferFlagBits flags{}; +}; + +} // namespace VideoCommon diff --git a/src/video_core/cdma_pusher.cpp b/src/video_core/cdma_pusher.cpp index 94679d5d1..33b3c060b 100644 --- a/src/video_core/cdma_pusher.cpp +++ b/src/video_core/cdma_pusher.cpp @@ -18,10 +18,10 @@ // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. // +#include <bit> #include "command_classes/host1x.h" #include "command_classes/nvdec.h" #include "command_classes/vic.h" -#include "common/bit_util.h" #include "video_core/cdma_pusher.h" #include "video_core/command_classes/nvdec_common.h" #include "video_core/engines/maxwell_3d.h" @@ -56,7 +56,7 @@ void CDmaPusher::Step() { for (const u32 value : values) { if (mask != 0) { - const u32 lbs = Common::CountTrailingZeroes32(mask); + const auto lbs = static_cast<u32>(std::countr_zero(mask)); mask &= ~(1U << lbs); ExecuteCommand(static_cast<u32>(offset + lbs), value); continue; diff --git a/src/video_core/cdma_pusher.h b/src/video_core/cdma_pusher.h index 8ca70b6dd..e5f212c1a 100644 --- a/src/video_core/cdma_pusher.h +++ b/src/video_core/cdma_pusher.h @@ -126,7 +126,7 @@ private: s32 count{}; s32 offset{}; - s32 mask{}; + u32 mask{}; bool incrementing{}; // Queue of command lists to be processed diff --git a/src/video_core/command_classes/codecs/h264.cpp b/src/video_core/command_classes/codecs/h264.cpp index 65bbeac78..fea6aed98 100644 --- a/src/video_core/command_classes/codecs/h264.cpp +++ b/src/video_core/command_classes/codecs/h264.cpp @@ -19,7 +19,7 @@ // #include <array> -#include "common/bit_util.h" +#include <bit> #include "video_core/command_classes/codecs/h264.h" #include "video_core/gpu.h" #include "video_core/memory_manager.h" @@ -266,7 +266,7 @@ void H264BitWriter::WriteExpGolombCodedInt(s32 value) { } void H264BitWriter::WriteExpGolombCodedUInt(u32 value) { - const s32 size = 32 - Common::CountLeadingZeroes32(static_cast<s32>(value + 1)); + const s32 size = 32 - std::countl_zero(value + 1); WriteBits(1, size); value -= (1U << (size - 1)) - 1; diff --git a/src/video_core/renderer_vulkan/renderer_vulkan.cpp b/src/video_core/renderer_vulkan/renderer_vulkan.cpp index d7437e185..61796e33a 100644 --- a/src/video_core/renderer_vulkan/renderer_vulkan.cpp +++ b/src/video_core/renderer_vulkan/renderer_vulkan.cpp @@ -23,7 +23,6 @@ #include "video_core/renderer_vulkan/renderer_vulkan.h" #include "video_core/renderer_vulkan/vk_blit_screen.h" #include "video_core/renderer_vulkan/vk_master_semaphore.h" -#include "video_core/renderer_vulkan/vk_memory_manager.h" #include "video_core/renderer_vulkan/vk_rasterizer.h" #include "video_core/renderer_vulkan/vk_scheduler.h" #include "video_core/renderer_vulkan/vk_state_tracker.h" @@ -32,6 +31,7 @@ #include "video_core/vulkan_common/vulkan_device.h" #include "video_core/vulkan_common/vulkan_instance.h" #include "video_core/vulkan_common/vulkan_library.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_surface.h" #include "video_core/vulkan_common/vulkan_wrapper.h" @@ -137,7 +137,7 @@ bool RendererVulkan::Init() try { InitializeDevice(); Report(); - memory_manager = std::make_unique<VKMemoryManager>(*device); + memory_allocator = std::make_unique<MemoryAllocator>(*device); state_tracker = std::make_unique<StateTracker>(gpu); @@ -149,11 +149,11 @@ bool RendererVulkan::Init() try { rasterizer = std::make_unique<RasterizerVulkan>(render_window, gpu, gpu.MemoryManager(), cpu_memory, screen_info, *device, - *memory_manager, *state_tracker, *scheduler); + *memory_allocator, *state_tracker, *scheduler); blit_screen = std::make_unique<VKBlitScreen>(cpu_memory, render_window, *rasterizer, *device, - *memory_manager, *swapchain, *scheduler, screen_info); + *memory_allocator, *swapchain, *scheduler, screen_info); return true; } catch (const vk::Exception& exception) { @@ -172,7 +172,7 @@ void RendererVulkan::ShutDown() { blit_screen.reset(); scheduler.reset(); swapchain.reset(); - memory_manager.reset(); + memory_allocator.reset(); device.reset(); } diff --git a/src/video_core/renderer_vulkan/renderer_vulkan.h b/src/video_core/renderer_vulkan/renderer_vulkan.h index 5575ffc54..daf55b9b4 100644 --- a/src/video_core/renderer_vulkan/renderer_vulkan.h +++ b/src/video_core/renderer_vulkan/renderer_vulkan.h @@ -29,8 +29,8 @@ namespace Vulkan { class Device; class StateTracker; +class MemoryAllocator; class VKBlitScreen; -class VKMemoryManager; class VKSwapchain; class VKScheduler; @@ -75,7 +75,7 @@ private: vk::DebugUtilsMessenger debug_callback; std::unique_ptr<Device> device; - std::unique_ptr<VKMemoryManager> memory_manager; + std::unique_ptr<MemoryAllocator> memory_allocator; std::unique_ptr<StateTracker> state_tracker; std::unique_ptr<VKScheduler> scheduler; std::unique_ptr<VKSwapchain> swapchain; diff --git a/src/video_core/renderer_vulkan/vk_blit_screen.cpp b/src/video_core/renderer_vulkan/vk_blit_screen.cpp index 5e184eb42..3e3b895e0 100644 --- a/src/video_core/renderer_vulkan/vk_blit_screen.cpp +++ b/src/video_core/renderer_vulkan/vk_blit_screen.cpp @@ -22,13 +22,13 @@ #include "video_core/renderer_vulkan/renderer_vulkan.h" #include "video_core/renderer_vulkan/vk_blit_screen.h" #include "video_core/renderer_vulkan/vk_master_semaphore.h" -#include "video_core/renderer_vulkan/vk_memory_manager.h" #include "video_core/renderer_vulkan/vk_scheduler.h" #include "video_core/renderer_vulkan/vk_shader_util.h" #include "video_core/renderer_vulkan/vk_swapchain.h" #include "video_core/surface.h" #include "video_core/textures/decoders.h" #include "video_core/vulkan_common/vulkan_device.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Vulkan { @@ -115,10 +115,10 @@ struct VKBlitScreen::BufferData { VKBlitScreen::VKBlitScreen(Core::Memory::Memory& cpu_memory_, Core::Frontend::EmuWindow& render_window_, VideoCore::RasterizerInterface& rasterizer_, const Device& device_, - VKMemoryManager& memory_manager_, VKSwapchain& swapchain_, + MemoryAllocator& memory_allocator_, VKSwapchain& swapchain_, VKScheduler& scheduler_, const VKScreenInfo& screen_info_) : cpu_memory{cpu_memory_}, render_window{render_window_}, rasterizer{rasterizer_}, - device{device_}, memory_manager{memory_manager_}, swapchain{swapchain_}, + device{device_}, memory_allocator{memory_allocator_}, swapchain{swapchain_}, scheduler{scheduler_}, image_count{swapchain.GetImageCount()}, screen_info{screen_info_} { resource_ticks.resize(image_count); @@ -150,8 +150,8 @@ VkSemaphore VKBlitScreen::Draw(const Tegra::FramebufferConfig& framebuffer, bool SetUniformData(data, framebuffer); SetVertexData(data, framebuffer); - auto map = buffer_commit->Map(); - std::memcpy(map.Address(), &data, sizeof(data)); + const std::span<u8> map = buffer_commit.Map(); + std::memcpy(map.data(), &data, sizeof(data)); if (!use_accelerated) { const u64 image_offset = GetRawImageOffset(framebuffer, image_index); @@ -165,8 +165,8 @@ VkSemaphore VKBlitScreen::Draw(const Tegra::FramebufferConfig& framebuffer, bool constexpr u32 block_height_log2 = 4; const u32 bytes_per_pixel = GetBytesPerPixel(framebuffer); Tegra::Texture::UnswizzleTexture( - std::span(map.Address() + image_offset, size_bytes), std::span(host_ptr, size_bytes), - bytes_per_pixel, framebuffer.width, framebuffer.height, 1, block_height_log2, 0); + map.subspan(image_offset, size_bytes), std::span(host_ptr, size_bytes), bytes_per_pixel, + framebuffer.width, framebuffer.height, 1, block_height_log2, 0); const VkBufferImageCopy copy{ .bufferOffset = image_offset, @@ -224,8 +224,6 @@ VkSemaphore VKBlitScreen::Draw(const Tegra::FramebufferConfig& framebuffer, bool VK_PIPELINE_STAGE_FRAGMENT_SHADER_BIT, 0, write_barrier); }); } - map.Release(); - scheduler.Record([renderpass = *renderpass, framebuffer = *framebuffers[image_index], descriptor_set = descriptor_sets[image_index], buffer = *buffer, size = swapchain.GetSize(), pipeline = *pipeline, @@ -642,7 +640,7 @@ void VKBlitScreen::ReleaseRawImages() { raw_images.clear(); raw_buffer_commits.clear(); buffer.reset(); - buffer_commit.reset(); + buffer_commit = MemoryCommit{}; } void VKBlitScreen::CreateStagingBuffer(const Tegra::FramebufferConfig& framebuffer) { @@ -659,7 +657,7 @@ void VKBlitScreen::CreateStagingBuffer(const Tegra::FramebufferConfig& framebuff }; buffer = device.GetLogical().CreateBuffer(ci); - buffer_commit = memory_manager.Commit(buffer, true); + buffer_commit = memory_allocator.Commit(buffer, MemoryUsage::Upload); } void VKBlitScreen::CreateRawImages(const Tegra::FramebufferConfig& framebuffer) { @@ -690,7 +688,7 @@ void VKBlitScreen::CreateRawImages(const Tegra::FramebufferConfig& framebuffer) .pQueueFamilyIndices = nullptr, .initialLayout = VK_IMAGE_LAYOUT_UNDEFINED, }); - raw_buffer_commits[i] = memory_manager.Commit(raw_images[i], false); + raw_buffer_commits[i] = memory_allocator.Commit(raw_images[i], MemoryUsage::DeviceLocal); raw_image_views[i] = device.GetLogical().CreateImageView(VkImageViewCreateInfo{ .sType = VK_STRUCTURE_TYPE_IMAGE_VIEW_CREATE_INFO, .pNext = nullptr, diff --git a/src/video_core/renderer_vulkan/vk_blit_screen.h b/src/video_core/renderer_vulkan/vk_blit_screen.h index 69ed61770..b52576957 100644 --- a/src/video_core/renderer_vulkan/vk_blit_screen.h +++ b/src/video_core/renderer_vulkan/vk_blit_screen.h @@ -6,7 +6,7 @@ #include <memory> -#include "video_core/renderer_vulkan/vk_memory_manager.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Core { @@ -43,7 +43,7 @@ public: explicit VKBlitScreen(Core::Memory::Memory& cpu_memory, Core::Frontend::EmuWindow& render_window, VideoCore::RasterizerInterface& rasterizer, const Device& device, - VKMemoryManager& memory_manager, VKSwapchain& swapchain, + MemoryAllocator& memory_allocator, VKSwapchain& swapchain, VKScheduler& scheduler, const VKScreenInfo& screen_info); ~VKBlitScreen(); @@ -86,7 +86,7 @@ private: Core::Frontend::EmuWindow& render_window; VideoCore::RasterizerInterface& rasterizer; const Device& device; - VKMemoryManager& memory_manager; + MemoryAllocator& memory_allocator; VKSwapchain& swapchain; VKScheduler& scheduler; const std::size_t image_count; @@ -104,14 +104,14 @@ private: vk::Sampler sampler; vk::Buffer buffer; - VKMemoryCommit buffer_commit; + MemoryCommit buffer_commit; std::vector<u64> resource_ticks; std::vector<vk::Semaphore> semaphores; std::vector<vk::Image> raw_images; std::vector<vk::ImageView> raw_image_views; - std::vector<VKMemoryCommit> raw_buffer_commits; + std::vector<MemoryCommit> raw_buffer_commits; u32 raw_width = 0; u32 raw_height = 0; }; diff --git a/src/video_core/renderer_vulkan/vk_buffer_cache.cpp b/src/video_core/renderer_vulkan/vk_buffer_cache.cpp index 58c710344..d8ad40a0f 100644 --- a/src/video_core/renderer_vulkan/vk_buffer_cache.cpp +++ b/src/video_core/renderer_vulkan/vk_buffer_cache.cpp @@ -36,11 +36,11 @@ constexpr VkAccessFlags TRANSFORM_FEEDBACK_WRITE_ACCESS = } // Anonymous namespace -Buffer::Buffer(const Device& device_, VKMemoryManager& memory_manager, VKScheduler& scheduler_, - VKStagingBufferPool& staging_pool_, VAddr cpu_addr_, std::size_t size_) +Buffer::Buffer(const Device& device_, MemoryAllocator& memory_allocator, VKScheduler& scheduler_, + StagingBufferPool& staging_pool_, VAddr cpu_addr_, std::size_t size_) : BufferBlock{cpu_addr_, size_}, device{device_}, scheduler{scheduler_}, staging_pool{ staging_pool_} { - const VkBufferCreateInfo ci{ + buffer = device.GetLogical().CreateBuffer(VkBufferCreateInfo{ .sType = VK_STRUCTURE_TYPE_BUFFER_CREATE_INFO, .pNext = nullptr, .flags = 0, @@ -49,22 +49,20 @@ Buffer::Buffer(const Device& device_, VKMemoryManager& memory_manager, VKSchedul .sharingMode = VK_SHARING_MODE_EXCLUSIVE, .queueFamilyIndexCount = 0, .pQueueFamilyIndices = nullptr, - }; - - buffer.handle = device.GetLogical().CreateBuffer(ci); - buffer.commit = memory_manager.Commit(buffer.handle, false); + }); + commit = memory_allocator.Commit(buffer, MemoryUsage::DeviceLocal); } Buffer::~Buffer() = default; void Buffer::Upload(std::size_t offset, std::size_t data_size, const u8* data) { - const auto& staging = staging_pool.GetUnusedBuffer(data_size, true); - std::memcpy(staging.commit->Map(data_size), data, data_size); + const auto& staging = staging_pool.Request(data_size, MemoryUsage::Upload); + std::memcpy(staging.mapped_span.data(), data, data_size); scheduler.RequestOutsideRenderPassOperationContext(); const VkBuffer handle = Handle(); - scheduler.Record([staging = *staging.handle, handle, offset, data_size, + scheduler.Record([staging = staging.buffer, handle, offset, data_size, &device = device](vk::CommandBuffer cmdbuf) { const VkBufferMemoryBarrier read_barrier{ .sType = VK_STRUCTURE_TYPE_BUFFER_MEMORY_BARRIER, @@ -100,12 +98,12 @@ void Buffer::Upload(std::size_t offset, std::size_t data_size, const u8* data) { } void Buffer::Download(std::size_t offset, std::size_t data_size, u8* data) { - const auto& staging = staging_pool.GetUnusedBuffer(data_size, true); + auto staging = staging_pool.Request(data_size, MemoryUsage::Download); scheduler.RequestOutsideRenderPassOperationContext(); const VkBuffer handle = Handle(); scheduler.Record( - [staging = *staging.handle, handle, offset, data_size](vk::CommandBuffer cmdbuf) { + [staging = staging.buffer, handle, offset, data_size](vk::CommandBuffer cmdbuf) { const VkBufferMemoryBarrier barrier{ .sType = VK_STRUCTURE_TYPE_BUFFER_MEMORY_BARRIER, .pNext = nullptr, @@ -126,7 +124,7 @@ void Buffer::Download(std::size_t offset, std::size_t data_size, u8* data) { }); scheduler.Finish(); - std::memcpy(data, staging.commit->Map(data_size), data_size); + std::memcpy(data, staging.mapped_span.data(), data_size); } void Buffer::CopyFrom(const Buffer& src, std::size_t src_offset, std::size_t dst_offset, @@ -164,29 +162,29 @@ void Buffer::CopyFrom(const Buffer& src, std::size_t src_offset, std::size_t dst VKBufferCache::VKBufferCache(VideoCore::RasterizerInterface& rasterizer_, Tegra::MemoryManager& gpu_memory_, Core::Memory::Memory& cpu_memory_, - const Device& device_, VKMemoryManager& memory_manager_, + const Device& device_, MemoryAllocator& memory_allocator_, VKScheduler& scheduler_, VKStreamBuffer& stream_buffer_, - VKStagingBufferPool& staging_pool_) + StagingBufferPool& staging_pool_) : VideoCommon::BufferCache<Buffer, VkBuffer, VKStreamBuffer>{rasterizer_, gpu_memory_, cpu_memory_, stream_buffer_}, - device{device_}, memory_manager{memory_manager_}, scheduler{scheduler_}, staging_pool{ - staging_pool_} {} + device{device_}, memory_allocator{memory_allocator_}, scheduler{scheduler_}, + staging_pool{staging_pool_} {} VKBufferCache::~VKBufferCache() = default; std::shared_ptr<Buffer> VKBufferCache::CreateBlock(VAddr cpu_addr, std::size_t size) { - return std::make_shared<Buffer>(device, memory_manager, scheduler, staging_pool, cpu_addr, + return std::make_shared<Buffer>(device, memory_allocator, scheduler, staging_pool, cpu_addr, size); } VKBufferCache::BufferInfo VKBufferCache::GetEmptyBuffer(std::size_t size) { size = std::max(size, std::size_t(4)); - const auto& empty = staging_pool.GetUnusedBuffer(size, false); + const auto& empty = staging_pool.Request(size, MemoryUsage::DeviceLocal); scheduler.RequestOutsideRenderPassOperationContext(); - scheduler.Record([size, buffer = *empty.handle](vk::CommandBuffer cmdbuf) { + scheduler.Record([size, buffer = empty.buffer](vk::CommandBuffer cmdbuf) { cmdbuf.FillBuffer(buffer, 0, size, 0); }); - return {*empty.handle, 0, 0}; + return {empty.buffer, 0, 0}; } } // namespace Vulkan diff --git a/src/video_core/renderer_vulkan/vk_buffer_cache.h b/src/video_core/renderer_vulkan/vk_buffer_cache.h index 1c39aed34..41d577510 100644 --- a/src/video_core/renderer_vulkan/vk_buffer_cache.h +++ b/src/video_core/renderer_vulkan/vk_buffer_cache.h @@ -8,21 +8,20 @@ #include "common/common_types.h" #include "video_core/buffer_cache/buffer_cache.h" -#include "video_core/renderer_vulkan/vk_memory_manager.h" #include "video_core/renderer_vulkan/vk_staging_buffer_pool.h" #include "video_core/renderer_vulkan/vk_stream_buffer.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Vulkan { class Device; -class VKMemoryManager; class VKScheduler; class Buffer final : public VideoCommon::BufferBlock { public: - explicit Buffer(const Device& device, VKMemoryManager& memory_manager, VKScheduler& scheduler, - VKStagingBufferPool& staging_pool, VAddr cpu_addr_, std::size_t size_); + explicit Buffer(const Device& device, MemoryAllocator& memory_allocator, VKScheduler& scheduler, + StagingBufferPool& staging_pool, VAddr cpu_addr_, std::size_t size_); ~Buffer(); void Upload(std::size_t offset, std::size_t data_size, const u8* data); @@ -33,7 +32,7 @@ public: std::size_t copy_size); VkBuffer Handle() const { - return *buffer.handle; + return *buffer; } u64 Address() const { @@ -43,18 +42,19 @@ public: private: const Device& device; VKScheduler& scheduler; - VKStagingBufferPool& staging_pool; + StagingBufferPool& staging_pool; - VKBuffer buffer; + vk::Buffer buffer; + MemoryCommit commit; }; class VKBufferCache final : public VideoCommon::BufferCache<Buffer, VkBuffer, VKStreamBuffer> { public: explicit VKBufferCache(VideoCore::RasterizerInterface& rasterizer, Tegra::MemoryManager& gpu_memory, Core::Memory::Memory& cpu_memory, - const Device& device, VKMemoryManager& memory_manager, + const Device& device, MemoryAllocator& memory_allocator, VKScheduler& scheduler, VKStreamBuffer& stream_buffer, - VKStagingBufferPool& staging_pool); + StagingBufferPool& staging_pool); ~VKBufferCache(); BufferInfo GetEmptyBuffer(std::size_t size) override; @@ -64,9 +64,9 @@ protected: private: const Device& device; - VKMemoryManager& memory_manager; + MemoryAllocator& memory_allocator; VKScheduler& scheduler; - VKStagingBufferPool& staging_pool; + StagingBufferPool& staging_pool; }; } // namespace Vulkan diff --git a/src/video_core/renderer_vulkan/vk_compute_pass.cpp b/src/video_core/renderer_vulkan/vk_compute_pass.cpp index 02a6d54b7..5eb6a54be 100644 --- a/src/video_core/renderer_vulkan/vk_compute_pass.cpp +++ b/src/video_core/renderer_vulkan/vk_compute_pass.cpp @@ -164,7 +164,7 @@ VkDescriptorSet VKComputePass::CommitDescriptorSet( QuadArrayPass::QuadArrayPass(const Device& device_, VKScheduler& scheduler_, VKDescriptorPool& descriptor_pool_, - VKStagingBufferPool& staging_buffer_pool_, + StagingBufferPool& staging_buffer_pool_, VKUpdateDescriptorQueue& update_descriptor_queue_) : VKComputePass(device_, descriptor_pool_, BuildQuadArrayPassDescriptorSetLayoutBinding(), BuildQuadArrayPassDescriptorUpdateTemplateEntry(), @@ -177,18 +177,18 @@ QuadArrayPass::~QuadArrayPass() = default; std::pair<VkBuffer, VkDeviceSize> QuadArrayPass::Assemble(u32 num_vertices, u32 first) { const u32 num_triangle_vertices = (num_vertices / 4) * 6; const std::size_t staging_size = num_triangle_vertices * sizeof(u32); - auto& buffer = staging_buffer_pool.GetUnusedBuffer(staging_size, false); + const auto staging_ref = staging_buffer_pool.Request(staging_size, MemoryUsage::DeviceLocal); update_descriptor_queue.Acquire(); - update_descriptor_queue.AddBuffer(*buffer.handle, 0, staging_size); + update_descriptor_queue.AddBuffer(staging_ref.buffer, 0, staging_size); const VkDescriptorSet set = CommitDescriptorSet(update_descriptor_queue); scheduler.RequestOutsideRenderPassOperationContext(); ASSERT(num_vertices % 4 == 0); const u32 num_quads = num_vertices / 4; - scheduler.Record([layout = *layout, pipeline = *pipeline, buffer = *buffer.handle, num_quads, - first, set](vk::CommandBuffer cmdbuf) { + scheduler.Record([layout = *layout, pipeline = *pipeline, buffer = staging_ref.buffer, + num_quads, first, set](vk::CommandBuffer cmdbuf) { constexpr u32 dispatch_size = 1024; cmdbuf.BindPipeline(VK_PIPELINE_BIND_POINT_COMPUTE, pipeline); cmdbuf.BindDescriptorSets(VK_PIPELINE_BIND_POINT_COMPUTE, layout, 0, set, {}); @@ -208,11 +208,11 @@ std::pair<VkBuffer, VkDeviceSize> QuadArrayPass::Assemble(u32 num_vertices, u32 cmdbuf.PipelineBarrier(VK_PIPELINE_STAGE_COMPUTE_SHADER_BIT, VK_PIPELINE_STAGE_VERTEX_INPUT_BIT, 0, {}, {barrier}, {}); }); - return {*buffer.handle, 0}; + return {staging_ref.buffer, 0}; } Uint8Pass::Uint8Pass(const Device& device, VKScheduler& scheduler_, - VKDescriptorPool& descriptor_pool, VKStagingBufferPool& staging_buffer_pool_, + VKDescriptorPool& descriptor_pool, StagingBufferPool& staging_buffer_pool_, VKUpdateDescriptorQueue& update_descriptor_queue_) : VKComputePass(device, descriptor_pool, BuildInputOutputDescriptorSetBindings(), BuildInputOutputDescriptorUpdateTemplate(), {}, VULKAN_UINT8_COMP_SPV), @@ -224,15 +224,15 @@ Uint8Pass::~Uint8Pass() = default; std::pair<VkBuffer, u64> Uint8Pass::Assemble(u32 num_vertices, VkBuffer src_buffer, u64 src_offset) { const u32 staging_size = static_cast<u32>(num_vertices * sizeof(u16)); - auto& buffer = staging_buffer_pool.GetUnusedBuffer(staging_size, false); + const auto staging_ref = staging_buffer_pool.Request(staging_size, MemoryUsage::DeviceLocal); update_descriptor_queue.Acquire(); update_descriptor_queue.AddBuffer(src_buffer, src_offset, num_vertices); - update_descriptor_queue.AddBuffer(*buffer.handle, 0, staging_size); + update_descriptor_queue.AddBuffer(staging_ref.buffer, 0, staging_size); const VkDescriptorSet set = CommitDescriptorSet(update_descriptor_queue); scheduler.RequestOutsideRenderPassOperationContext(); - scheduler.Record([layout = *layout, pipeline = *pipeline, buffer = *buffer.handle, set, + scheduler.Record([layout = *layout, pipeline = *pipeline, buffer = staging_ref.buffer, set, num_vertices](vk::CommandBuffer cmdbuf) { constexpr u32 dispatch_size = 1024; cmdbuf.BindPipeline(VK_PIPELINE_BIND_POINT_COMPUTE, pipeline); @@ -252,12 +252,12 @@ std::pair<VkBuffer, u64> Uint8Pass::Assemble(u32 num_vertices, VkBuffer src_buff cmdbuf.PipelineBarrier(VK_PIPELINE_STAGE_COMPUTE_SHADER_BIT, VK_PIPELINE_STAGE_VERTEX_INPUT_BIT, 0, {}, barrier, {}); }); - return {*buffer.handle, 0}; + return {staging_ref.buffer, 0}; } QuadIndexedPass::QuadIndexedPass(const Device& device_, VKScheduler& scheduler_, VKDescriptorPool& descriptor_pool_, - VKStagingBufferPool& staging_buffer_pool_, + StagingBufferPool& staging_buffer_pool_, VKUpdateDescriptorQueue& update_descriptor_queue_) : VKComputePass(device_, descriptor_pool_, BuildInputOutputDescriptorSetBindings(), BuildInputOutputDescriptorUpdateTemplate(), @@ -286,15 +286,15 @@ std::pair<VkBuffer, u64> QuadIndexedPass::Assemble( const u32 num_tri_vertices = (num_vertices / 4) * 6; const std::size_t staging_size = num_tri_vertices * sizeof(u32); - auto& buffer = staging_buffer_pool.GetUnusedBuffer(staging_size, false); + const auto staging_ref = staging_buffer_pool.Request(staging_size, MemoryUsage::DeviceLocal); update_descriptor_queue.Acquire(); update_descriptor_queue.AddBuffer(src_buffer, src_offset, input_size); - update_descriptor_queue.AddBuffer(*buffer.handle, 0, staging_size); + update_descriptor_queue.AddBuffer(staging_ref.buffer, 0, staging_size); const VkDescriptorSet set = CommitDescriptorSet(update_descriptor_queue); scheduler.RequestOutsideRenderPassOperationContext(); - scheduler.Record([layout = *layout, pipeline = *pipeline, buffer = *buffer.handle, set, + scheduler.Record([layout = *layout, pipeline = *pipeline, buffer = staging_ref.buffer, set, num_tri_vertices, base_vertex, index_shift](vk::CommandBuffer cmdbuf) { static constexpr u32 dispatch_size = 1024; const std::array push_constants = {base_vertex, index_shift}; @@ -317,7 +317,7 @@ std::pair<VkBuffer, u64> QuadIndexedPass::Assemble( cmdbuf.PipelineBarrier(VK_PIPELINE_STAGE_COMPUTE_SHADER_BIT, VK_PIPELINE_STAGE_VERTEX_INPUT_BIT, 0, {}, barrier, {}); }); - return {*buffer.handle, 0}; + return {staging_ref.buffer, 0}; } } // namespace Vulkan diff --git a/src/video_core/renderer_vulkan/vk_compute_pass.h b/src/video_core/renderer_vulkan/vk_compute_pass.h index 7ddb09afb..f5c6f5f17 100644 --- a/src/video_core/renderer_vulkan/vk_compute_pass.h +++ b/src/video_core/renderer_vulkan/vk_compute_pass.h @@ -16,8 +16,8 @@ namespace Vulkan { class Device; +class StagingBufferPool; class VKScheduler; -class VKStagingBufferPool; class VKUpdateDescriptorQueue; class VKComputePass { @@ -45,7 +45,7 @@ class QuadArrayPass final : public VKComputePass { public: explicit QuadArrayPass(const Device& device_, VKScheduler& scheduler_, VKDescriptorPool& descriptor_pool_, - VKStagingBufferPool& staging_buffer_pool_, + StagingBufferPool& staging_buffer_pool_, VKUpdateDescriptorQueue& update_descriptor_queue_); ~QuadArrayPass(); @@ -53,15 +53,14 @@ public: private: VKScheduler& scheduler; - VKStagingBufferPool& staging_buffer_pool; + StagingBufferPool& staging_buffer_pool; VKUpdateDescriptorQueue& update_descriptor_queue; }; class Uint8Pass final : public VKComputePass { public: explicit Uint8Pass(const Device& device_, VKScheduler& scheduler_, - VKDescriptorPool& descriptor_pool_, - VKStagingBufferPool& staging_buffer_pool_, + VKDescriptorPool& descriptor_pool_, StagingBufferPool& staging_buffer_pool_, VKUpdateDescriptorQueue& update_descriptor_queue_); ~Uint8Pass(); @@ -69,7 +68,7 @@ public: private: VKScheduler& scheduler; - VKStagingBufferPool& staging_buffer_pool; + StagingBufferPool& staging_buffer_pool; VKUpdateDescriptorQueue& update_descriptor_queue; }; @@ -77,7 +76,7 @@ class QuadIndexedPass final : public VKComputePass { public: explicit QuadIndexedPass(const Device& device_, VKScheduler& scheduler_, VKDescriptorPool& descriptor_pool_, - VKStagingBufferPool& staging_buffer_pool_, + StagingBufferPool& staging_buffer_pool_, VKUpdateDescriptorQueue& update_descriptor_queue_); ~QuadIndexedPass(); @@ -87,7 +86,7 @@ public: private: VKScheduler& scheduler; - VKStagingBufferPool& staging_buffer_pool; + StagingBufferPool& staging_buffer_pool; VKUpdateDescriptorQueue& update_descriptor_queue; }; diff --git a/src/video_core/renderer_vulkan/vk_memory_manager.cpp b/src/video_core/renderer_vulkan/vk_memory_manager.cpp deleted file mode 100644 index a6abd0eee..000000000 --- a/src/video_core/renderer_vulkan/vk_memory_manager.cpp +++ /dev/null @@ -1,230 +0,0 @@ -// Copyright 2018 yuzu Emulator Project -// Licensed under GPLv2 or any later version -// Refer to the license.txt file included. - -#include <algorithm> -#include <optional> -#include <tuple> -#include <vector> - -#include "common/alignment.h" -#include "common/assert.h" -#include "common/common_types.h" -#include "common/logging/log.h" -#include "video_core/renderer_vulkan/vk_memory_manager.h" -#include "video_core/vulkan_common/vulkan_device.h" -#include "video_core/vulkan_common/vulkan_wrapper.h" - -namespace Vulkan { - -namespace { - -u64 GetAllocationChunkSize(u64 required_size) { - static constexpr u64 sizes[] = {16ULL << 20, 32ULL << 20, 64ULL << 20, 128ULL << 20}; - auto it = std::lower_bound(std::begin(sizes), std::end(sizes), required_size); - return it != std::end(sizes) ? *it : Common::AlignUp(required_size, 256ULL << 20); -} - -} // Anonymous namespace - -class VKMemoryAllocation final { -public: - explicit VKMemoryAllocation(const Device& device_, vk::DeviceMemory memory_, - VkMemoryPropertyFlags properties_, u64 allocation_size_, u32 type_) - : device{device_}, memory{std::move(memory_)}, properties{properties_}, - allocation_size{allocation_size_}, shifted_type{ShiftType(type_)} {} - - VKMemoryCommit Commit(VkDeviceSize commit_size, VkDeviceSize alignment) { - auto found = TryFindFreeSection(free_iterator, allocation_size, - static_cast<u64>(commit_size), static_cast<u64>(alignment)); - if (!found) { - found = TryFindFreeSection(0, free_iterator, static_cast<u64>(commit_size), - static_cast<u64>(alignment)); - if (!found) { - // Signal out of memory, it'll try to do more allocations. - return nullptr; - } - } - auto commit = std::make_unique<VKMemoryCommitImpl>(device, this, memory, *found, - *found + commit_size); - commits.push_back(commit.get()); - - // Last commit's address is highly probable to be free. - free_iterator = *found + commit_size; - - return commit; - } - - void Free(const VKMemoryCommitImpl* commit) { - ASSERT(commit); - - const auto it = std::find(std::begin(commits), std::end(commits), commit); - if (it == commits.end()) { - UNREACHABLE_MSG("Freeing unallocated commit!"); - return; - } - commits.erase(it); - } - - /// Returns whether this allocation is compatible with the arguments. - bool IsCompatible(VkMemoryPropertyFlags wanted_properties, u32 type_mask) const { - return (wanted_properties & properties) && (type_mask & shifted_type) != 0; - } - -private: - static constexpr u32 ShiftType(u32 type) { - return 1U << type; - } - - /// A memory allocator, it may return a free region between "start" and "end" with the solicited - /// requirements. - std::optional<u64> TryFindFreeSection(u64 start, u64 end, u64 size, u64 alignment) const { - u64 iterator = Common::AlignUp(start, alignment); - while (iterator + size <= end) { - const u64 try_left = iterator; - const u64 try_right = try_left + size; - - bool overlap = false; - for (const auto& commit : commits) { - const auto [commit_left, commit_right] = commit->interval; - if (try_left < commit_right && commit_left < try_right) { - // There's an overlap, continue the search where the overlapping commit ends. - iterator = Common::AlignUp(commit_right, alignment); - overlap = true; - break; - } - } - if (!overlap) { - // A free address has been found. - return try_left; - } - } - - // No free regions where found, return an empty optional. - return std::nullopt; - } - - const Device& device; ///< Vulkan device. - const vk::DeviceMemory memory; ///< Vulkan memory allocation handler. - const VkMemoryPropertyFlags properties; ///< Vulkan properties. - const u64 allocation_size; ///< Size of this allocation. - const u32 shifted_type; ///< Stored Vulkan type of this allocation, shifted. - - /// Hints where the next free region is likely going to be. - u64 free_iterator{}; - - /// Stores all commits done from this allocation. - std::vector<const VKMemoryCommitImpl*> commits; -}; - -VKMemoryManager::VKMemoryManager(const Device& device_) - : device{device_}, properties{device_.GetPhysical().GetMemoryProperties()} {} - -VKMemoryManager::~VKMemoryManager() = default; - -VKMemoryCommit VKMemoryManager::Commit(const VkMemoryRequirements& requirements, - bool host_visible) { - const u64 chunk_size = GetAllocationChunkSize(requirements.size); - - // When a host visible commit is asked, search for host visible and coherent, otherwise search - // for a fast device local type. - const VkMemoryPropertyFlags wanted_properties = - host_visible ? VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT | VK_MEMORY_PROPERTY_HOST_COHERENT_BIT - : VK_MEMORY_PROPERTY_DEVICE_LOCAL_BIT; - - if (auto commit = TryAllocCommit(requirements, wanted_properties)) { - return commit; - } - - // Commit has failed, allocate more memory. - if (!AllocMemory(wanted_properties, requirements.memoryTypeBits, chunk_size)) { - // TODO(Rodrigo): Handle these situations in some way like flushing to guest memory. - // Allocation has failed, panic. - UNREACHABLE_MSG("Ran out of VRAM!"); - return {}; - } - - // Commit again, this time it won't fail since there's a fresh allocation above. If it does, - // there's a bug. - auto commit = TryAllocCommit(requirements, wanted_properties); - ASSERT(commit); - return commit; -} - -VKMemoryCommit VKMemoryManager::Commit(const vk::Buffer& buffer, bool host_visible) { - auto commit = Commit(device.GetLogical().GetBufferMemoryRequirements(*buffer), host_visible); - buffer.BindMemory(commit->GetMemory(), commit->GetOffset()); - return commit; -} - -VKMemoryCommit VKMemoryManager::Commit(const vk::Image& image, bool host_visible) { - auto commit = Commit(device.GetLogical().GetImageMemoryRequirements(*image), host_visible); - image.BindMemory(commit->GetMemory(), commit->GetOffset()); - return commit; -} - -bool VKMemoryManager::AllocMemory(VkMemoryPropertyFlags wanted_properties, u32 type_mask, - u64 size) { - const u32 type = [&] { - for (u32 type_index = 0; type_index < properties.memoryTypeCount; ++type_index) { - const auto flags = properties.memoryTypes[type_index].propertyFlags; - if ((type_mask & (1U << type_index)) && (flags & wanted_properties)) { - // The type matches in type and in the wanted properties. - return type_index; - } - } - UNREACHABLE_MSG("Couldn't find a compatible memory type!"); - return 0U; - }(); - - // Try to allocate found type. - vk::DeviceMemory memory = device.GetLogical().TryAllocateMemory({ - .sType = VK_STRUCTURE_TYPE_MEMORY_ALLOCATE_INFO, - .pNext = nullptr, - .allocationSize = size, - .memoryTypeIndex = type, - }); - if (!memory) { - LOG_CRITICAL(Render_Vulkan, "Device allocation failed!"); - return false; - } - - allocations.push_back(std::make_unique<VKMemoryAllocation>(device, std::move(memory), - wanted_properties, size, type)); - return true; -} - -VKMemoryCommit VKMemoryManager::TryAllocCommit(const VkMemoryRequirements& requirements, - VkMemoryPropertyFlags wanted_properties) { - for (auto& allocation : allocations) { - if (!allocation->IsCompatible(wanted_properties, requirements.memoryTypeBits)) { - continue; - } - if (auto commit = allocation->Commit(requirements.size, requirements.alignment)) { - return commit; - } - } - return {}; -} - -VKMemoryCommitImpl::VKMemoryCommitImpl(const Device& device_, VKMemoryAllocation* allocation_, - const vk::DeviceMemory& memory_, u64 begin_, u64 end_) - : device{device_}, memory{memory_}, interval{begin_, end_}, allocation{allocation_} {} - -VKMemoryCommitImpl::~VKMemoryCommitImpl() { - allocation->Free(this); -} - -MemoryMap VKMemoryCommitImpl::Map(u64 size, u64 offset_) const { - return MemoryMap(this, std::span<u8>(memory.Map(interval.first + offset_, size), size)); -} - -void VKMemoryCommitImpl::Unmap() const { - memory.Unmap(); -} - -MemoryMap VKMemoryCommitImpl::Map() const { - return Map(interval.second - interval.first); -} - -} // namespace Vulkan diff --git a/src/video_core/renderer_vulkan/vk_memory_manager.h b/src/video_core/renderer_vulkan/vk_memory_manager.h deleted file mode 100644 index 2452bca4e..000000000 --- a/src/video_core/renderer_vulkan/vk_memory_manager.h +++ /dev/null @@ -1,132 +0,0 @@ -// Copyright 2019 yuzu Emulator Project -// Licensed under GPLv2 or any later version -// Refer to the license.txt file included. - -#pragma once - -#include <memory> -#include <span> -#include <utility> -#include <vector> -#include "common/common_types.h" -#include "video_core/vulkan_common/vulkan_wrapper.h" - -namespace Vulkan { - -class Device; -class MemoryMap; -class VKMemoryAllocation; -class VKMemoryCommitImpl; - -using VKMemoryCommit = std::unique_ptr<VKMemoryCommitImpl>; - -class VKMemoryManager final { -public: - explicit VKMemoryManager(const Device& device_); - VKMemoryManager(const VKMemoryManager&) = delete; - ~VKMemoryManager(); - - /** - * Commits a memory with the specified requeriments. - * @param requirements Requirements returned from a Vulkan call. - * @param host_visible Signals the allocator that it *must* use host visible and coherent - * memory. When passing false, it will try to allocate device local memory. - * @returns A memory commit. - */ - VKMemoryCommit Commit(const VkMemoryRequirements& requirements, bool host_visible); - - /// Commits memory required by the buffer and binds it. - VKMemoryCommit Commit(const vk::Buffer& buffer, bool host_visible); - - /// Commits memory required by the image and binds it. - VKMemoryCommit Commit(const vk::Image& image, bool host_visible); - -private: - /// Allocates a chunk of memory. - bool AllocMemory(VkMemoryPropertyFlags wanted_properties, u32 type_mask, u64 size); - - /// Tries to allocate a memory commit. - VKMemoryCommit TryAllocCommit(const VkMemoryRequirements& requirements, - VkMemoryPropertyFlags wanted_properties); - - const Device& device; ///< Device handler. - const VkPhysicalDeviceMemoryProperties properties; ///< Physical device properties. - std::vector<std::unique_ptr<VKMemoryAllocation>> allocations; ///< Current allocations. -}; - -class VKMemoryCommitImpl final { - friend VKMemoryAllocation; - friend MemoryMap; - -public: - explicit VKMemoryCommitImpl(const Device& device_, VKMemoryAllocation* allocation_, - const vk::DeviceMemory& memory_, u64 begin_, u64 end_); - ~VKMemoryCommitImpl(); - - /// Maps a memory region and returns a pointer to it. - /// It's illegal to have more than one memory map at the same time. - MemoryMap Map(u64 size, u64 offset = 0) const; - - /// Maps the whole commit and returns a pointer to it. - /// It's illegal to have more than one memory map at the same time. - MemoryMap Map() const; - - /// Returns the Vulkan memory handler. - VkDeviceMemory GetMemory() const { - return *memory; - } - - /// Returns the start position of the commit relative to the allocation. - VkDeviceSize GetOffset() const { - return static_cast<VkDeviceSize>(interval.first); - } - -private: - /// Unmaps memory. - void Unmap() const; - - const Device& device; ///< Vulkan device. - const vk::DeviceMemory& memory; ///< Vulkan device memory handler. - std::pair<u64, u64> interval{}; ///< Interval where the commit exists. - VKMemoryAllocation* allocation{}; ///< Pointer to the large memory allocation. -}; - -/// Holds ownership of a memory map. -class MemoryMap final { -public: - explicit MemoryMap(const VKMemoryCommitImpl* commit_, std::span<u8> span_) - : commit{commit_}, span{span_} {} - - ~MemoryMap() { - if (commit) { - commit->Unmap(); - } - } - - /// Prematurely releases the memory map. - void Release() { - commit->Unmap(); - commit = nullptr; - } - - /// Returns a span to the memory map. - [[nodiscard]] std::span<u8> Span() const noexcept { - return span; - } - - /// Returns the address of the memory map. - [[nodiscard]] u8* Address() const noexcept { - return span.data(); - } - - /// Returns the address of the memory map; - [[nodiscard]] operator u8*() const noexcept { - return span.data(); - } - -private: - const VKMemoryCommitImpl* commit{}; ///< Mapped memory commit. - std::span<u8> span; ///< Address to the mapped memory. -}; - -} // namespace Vulkan diff --git a/src/video_core/renderer_vulkan/vk_rasterizer.cpp b/src/video_core/renderer_vulkan/vk_rasterizer.cpp index ce3db49bd..f0a111829 100644 --- a/src/video_core/renderer_vulkan/vk_rasterizer.cpp +++ b/src/video_core/renderer_vulkan/vk_rasterizer.cpp @@ -409,24 +409,24 @@ void RasterizerVulkan::DrawParameters::Draw(vk::CommandBuffer cmdbuf) const { RasterizerVulkan::RasterizerVulkan(Core::Frontend::EmuWindow& emu_window_, Tegra::GPU& gpu_, Tegra::MemoryManager& gpu_memory_, Core::Memory::Memory& cpu_memory_, VKScreenInfo& screen_info_, - const Device& device_, VKMemoryManager& memory_manager_, + const Device& device_, MemoryAllocator& memory_allocator_, StateTracker& state_tracker_, VKScheduler& scheduler_) : RasterizerAccelerated{cpu_memory_}, gpu{gpu_}, gpu_memory{gpu_memory_}, maxwell3d{gpu.Maxwell3D()}, kepler_compute{gpu.KeplerCompute()}, - screen_info{screen_info_}, device{device_}, memory_manager{memory_manager_}, + screen_info{screen_info_}, device{device_}, memory_allocator{memory_allocator_}, state_tracker{state_tracker_}, scheduler{scheduler_}, stream_buffer(device, scheduler), - staging_pool(device, memory_manager, scheduler), descriptor_pool(device, scheduler), + staging_pool(device, memory_allocator, scheduler), descriptor_pool(device, scheduler), update_descriptor_queue(device, scheduler), blit_image(device, scheduler, state_tracker, descriptor_pool), quad_array_pass(device, scheduler, descriptor_pool, staging_pool, update_descriptor_queue), quad_indexed_pass(device, scheduler, descriptor_pool, staging_pool, update_descriptor_queue), uint8_pass(device, scheduler, descriptor_pool, staging_pool, update_descriptor_queue), - texture_cache_runtime{device, scheduler, memory_manager, staging_pool, blit_image}, + texture_cache_runtime{device, scheduler, memory_allocator, staging_pool, blit_image}, texture_cache(texture_cache_runtime, *this, maxwell3d, kepler_compute, gpu_memory), pipeline_cache(*this, gpu, maxwell3d, kepler_compute, gpu_memory, device, scheduler, descriptor_pool, update_descriptor_queue), - buffer_cache(*this, gpu_memory, cpu_memory_, device, memory_manager, scheduler, stream_buffer, - staging_pool), + buffer_cache(*this, gpu_memory, cpu_memory_, device, memory_allocator, scheduler, + stream_buffer, staging_pool), query_cache{*this, maxwell3d, gpu_memory, device, scheduler}, fence_manager(*this, gpu, gpu_memory, texture_cache, buffer_cache, query_cache, scheduler), wfi_event(device.GetLogical().CreateEvent()), async_shaders(emu_window_) { @@ -1445,7 +1445,7 @@ VkBuffer RasterizerVulkan::DefaultBuffer() { .queueFamilyIndexCount = 0, .pQueueFamilyIndices = nullptr, }); - default_buffer_commit = memory_manager.Commit(default_buffer, false); + default_buffer_commit = memory_allocator.Commit(default_buffer, MemoryUsage::DeviceLocal); scheduler.RequestOutsideRenderPassOperationContext(); scheduler.Record([buffer = *default_buffer](vk::CommandBuffer cmdbuf) { diff --git a/src/video_core/renderer_vulkan/vk_rasterizer.h b/src/video_core/renderer_vulkan/vk_rasterizer.h index 4695718e9..8e261b9bd 100644 --- a/src/video_core/renderer_vulkan/vk_rasterizer.h +++ b/src/video_core/renderer_vulkan/vk_rasterizer.h @@ -21,7 +21,6 @@ #include "video_core/renderer_vulkan/vk_compute_pass.h" #include "video_core/renderer_vulkan/vk_descriptor_pool.h" #include "video_core/renderer_vulkan/vk_fence_manager.h" -#include "video_core/renderer_vulkan/vk_memory_manager.h" #include "video_core/renderer_vulkan/vk_pipeline_cache.h" #include "video_core/renderer_vulkan/vk_query_cache.h" #include "video_core/renderer_vulkan/vk_scheduler.h" @@ -30,6 +29,7 @@ #include "video_core/renderer_vulkan/vk_texture_cache.h" #include "video_core/renderer_vulkan/vk_update_descriptor.h" #include "video_core/shader/async_shaders.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Core { @@ -56,7 +56,7 @@ public: explicit RasterizerVulkan(Core::Frontend::EmuWindow& emu_window_, Tegra::GPU& gpu_, Tegra::MemoryManager& gpu_memory_, Core::Memory::Memory& cpu_memory_, VKScreenInfo& screen_info_, const Device& device_, - VKMemoryManager& memory_manager_, StateTracker& state_tracker_, + MemoryAllocator& memory_allocator_, StateTracker& state_tracker_, VKScheduler& scheduler_); ~RasterizerVulkan() override; @@ -213,12 +213,12 @@ private: VKScreenInfo& screen_info; const Device& device; - VKMemoryManager& memory_manager; + MemoryAllocator& memory_allocator; StateTracker& state_tracker; VKScheduler& scheduler; VKStreamBuffer stream_buffer; - VKStagingBufferPool staging_pool; + StagingBufferPool staging_pool; VKDescriptorPool descriptor_pool; VKUpdateDescriptorQueue update_descriptor_queue; BlitImageHelper blit_image; @@ -234,7 +234,7 @@ private: VKFenceManager fence_manager; vk::Buffer default_buffer; - VKMemoryCommit default_buffer_commit; + MemoryCommit default_buffer_commit; vk::Event wfi_event; VideoCommon::Shader::AsyncShaders async_shaders; diff --git a/src/video_core/renderer_vulkan/vk_staging_buffer_pool.cpp b/src/video_core/renderer_vulkan/vk_staging_buffer_pool.cpp index 1e0b8b922..97fd41cc1 100644 --- a/src/video_core/renderer_vulkan/vk_staging_buffer_pool.cpp +++ b/src/video_core/renderer_vulkan/vk_staging_buffer_pool.cpp @@ -3,10 +3,12 @@ // Refer to the license.txt file included. #include <algorithm> -#include <unordered_map> #include <utility> #include <vector> +#include <fmt/format.h> + +#include "common/assert.h" #include "common/bit_util.h" #include "common/common_types.h" #include "video_core/renderer_vulkan/vk_scheduler.h" @@ -16,45 +18,51 @@ namespace Vulkan { -VKStagingBufferPool::StagingBuffer::StagingBuffer(std::unique_ptr<VKBuffer> buffer_) - : buffer{std::move(buffer_)} {} - -VKStagingBufferPool::VKStagingBufferPool(const Device& device_, VKMemoryManager& memory_manager_, - VKScheduler& scheduler_) - : device{device_}, memory_manager{memory_manager_}, scheduler{scheduler_} {} +StagingBufferPool::StagingBufferPool(const Device& device_, MemoryAllocator& memory_allocator_, + VKScheduler& scheduler_) + : device{device_}, memory_allocator{memory_allocator_}, scheduler{scheduler_} {} -VKStagingBufferPool::~VKStagingBufferPool() = default; +StagingBufferPool::~StagingBufferPool() = default; -VKBuffer& VKStagingBufferPool::GetUnusedBuffer(std::size_t size, bool host_visible) { - if (const auto buffer = TryGetReservedBuffer(size, host_visible)) { - return *buffer; +StagingBufferRef StagingBufferPool::Request(size_t size, MemoryUsage usage) { + if (const std::optional<StagingBufferRef> ref = TryGetReservedBuffer(size, usage)) { + return *ref; } - return CreateStagingBuffer(size, host_visible); + return CreateStagingBuffer(size, usage); } -void VKStagingBufferPool::TickFrame() { - current_delete_level = (current_delete_level + 1) % NumLevels; +void StagingBufferPool::TickFrame() { + current_delete_level = (current_delete_level + 1) % NUM_LEVELS; - ReleaseCache(true); - ReleaseCache(false); + ReleaseCache(MemoryUsage::DeviceLocal); + ReleaseCache(MemoryUsage::Upload); + ReleaseCache(MemoryUsage::Download); } -VKBuffer* VKStagingBufferPool::TryGetReservedBuffer(std::size_t size, bool host_visible) { - for (StagingBuffer& entry : GetCache(host_visible)[Common::Log2Ceil64(size)].entries) { - if (!scheduler.IsFree(entry.tick)) { - continue; +std::optional<StagingBufferRef> StagingBufferPool::TryGetReservedBuffer(size_t size, + MemoryUsage usage) { + StagingBuffers& cache_level = GetCache(usage)[Common::Log2Ceil64(size)]; + + const auto is_free = [this](const StagingBuffer& entry) { + return scheduler.IsFree(entry.tick); + }; + auto& entries = cache_level.entries; + const auto hint_it = entries.begin() + cache_level.iterate_index; + auto it = std::find_if(entries.begin() + cache_level.iterate_index, entries.end(), is_free); + if (it == entries.end()) { + it = std::find_if(entries.begin(), hint_it, is_free); + if (it == hint_it) { + return std::nullopt; } - entry.tick = scheduler.CurrentTick(); - return &*entry.buffer; } - return nullptr; + cache_level.iterate_index = std::distance(entries.begin(), it) + 1; + it->tick = scheduler.CurrentTick(); + return it->Ref(); } -VKBuffer& VKStagingBufferPool::CreateStagingBuffer(std::size_t size, bool host_visible) { +StagingBufferRef StagingBufferPool::CreateStagingBuffer(size_t size, MemoryUsage usage) { const u32 log2 = Common::Log2Ceil64(size); - - auto buffer = std::make_unique<VKBuffer>(); - buffer->handle = device.GetLogical().CreateBuffer({ + vk::Buffer buffer = device.GetLogical().CreateBuffer({ .sType = VK_STRUCTURE_TYPE_BUFFER_CREATE_INFO, .pNext = nullptr, .flags = 0, @@ -66,49 +74,63 @@ VKBuffer& VKStagingBufferPool::CreateStagingBuffer(std::size_t size, bool host_v .queueFamilyIndexCount = 0, .pQueueFamilyIndices = nullptr, }); - buffer->commit = memory_manager.Commit(buffer->handle, host_visible); - - std::vector<StagingBuffer>& entries = GetCache(host_visible)[log2].entries; - StagingBuffer& entry = entries.emplace_back(std::move(buffer)); - entry.tick = scheduler.CurrentTick(); - return *entry.buffer; -} - -VKStagingBufferPool::StagingBuffersCache& VKStagingBufferPool::GetCache(bool host_visible) { - return host_visible ? host_staging_buffers : device_staging_buffers; + if (device.HasDebuggingToolAttached()) { + ++buffer_index; + buffer.SetObjectNameEXT(fmt::format("Staging Buffer {}", buffer_index).c_str()); + } + MemoryCommit commit = memory_allocator.Commit(buffer, usage); + const std::span<u8> mapped_span = IsHostVisible(usage) ? commit.Map() : std::span<u8>{}; + + StagingBuffer& entry = GetCache(usage)[log2].entries.emplace_back(StagingBuffer{ + .buffer = std::move(buffer), + .commit = std::move(commit), + .mapped_span = mapped_span, + .tick = scheduler.CurrentTick(), + }); + return entry.Ref(); } -void VKStagingBufferPool::ReleaseCache(bool host_visible) { - auto& cache = GetCache(host_visible); - const u64 size = ReleaseLevel(cache, current_delete_level); - if (size == 0) { - return; +StagingBufferPool::StagingBuffersCache& StagingBufferPool::GetCache(MemoryUsage usage) { + switch (usage) { + case MemoryUsage::DeviceLocal: + return device_local_cache; + case MemoryUsage::Upload: + return upload_cache; + case MemoryUsage::Download: + return download_cache; + default: + UNREACHABLE_MSG("Invalid memory usage={}", usage); + return upload_cache; } } -u64 VKStagingBufferPool::ReleaseLevel(StagingBuffersCache& cache, std::size_t log2) { - static constexpr std::size_t deletions_per_tick = 16; +void StagingBufferPool::ReleaseCache(MemoryUsage usage) { + ReleaseLevel(GetCache(usage), current_delete_level); +} +void StagingBufferPool::ReleaseLevel(StagingBuffersCache& cache, size_t log2) { + constexpr size_t deletions_per_tick = 16; auto& staging = cache[log2]; auto& entries = staging.entries; - const std::size_t old_size = entries.size(); + const size_t old_size = entries.size(); const auto is_deleteable = [this](const StagingBuffer& entry) { return scheduler.IsFree(entry.tick); }; - const std::size_t begin_offset = staging.delete_index; - const std::size_t end_offset = std::min(begin_offset + deletions_per_tick, old_size); - const auto begin = std::begin(entries) + begin_offset; - const auto end = std::begin(entries) + end_offset; + const size_t begin_offset = staging.delete_index; + const size_t end_offset = std::min(begin_offset + deletions_per_tick, old_size); + const auto begin = entries.begin() + begin_offset; + const auto end = entries.begin() + end_offset; entries.erase(std::remove_if(begin, end, is_deleteable), end); - const std::size_t new_size = entries.size(); + const size_t new_size = entries.size(); staging.delete_index += deletions_per_tick; if (staging.delete_index >= new_size) { staging.delete_index = 0; } - - return (1ULL << log2) * (old_size - new_size); + if (staging.iterate_index > new_size) { + staging.iterate_index = 0; + } } } // namespace Vulkan diff --git a/src/video_core/renderer_vulkan/vk_staging_buffer_pool.h b/src/video_core/renderer_vulkan/vk_staging_buffer_pool.h index 90dadcbbe..d42918a47 100644 --- a/src/video_core/renderer_vulkan/vk_staging_buffer_pool.h +++ b/src/video_core/renderer_vulkan/vk_staging_buffer_pool.h @@ -9,7 +9,7 @@ #include "common/common_types.h" -#include "video_core/renderer_vulkan/vk_memory_manager.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Vulkan { @@ -17,55 +17,65 @@ namespace Vulkan { class Device; class VKScheduler; -struct VKBuffer final { - vk::Buffer handle; - VKMemoryCommit commit; +struct StagingBufferRef { + VkBuffer buffer; + std::span<u8> mapped_span; }; -class VKStagingBufferPool final { +class StagingBufferPool { public: - explicit VKStagingBufferPool(const Device& device, VKMemoryManager& memory_manager, - VKScheduler& scheduler); - ~VKStagingBufferPool(); + explicit StagingBufferPool(const Device& device, MemoryAllocator& memory_allocator, + VKScheduler& scheduler); + ~StagingBufferPool(); - VKBuffer& GetUnusedBuffer(std::size_t size, bool host_visible); + StagingBufferRef Request(size_t size, MemoryUsage usage); void TickFrame(); private: - struct StagingBuffer final { - explicit StagingBuffer(std::unique_ptr<VKBuffer> buffer); - - std::unique_ptr<VKBuffer> buffer; + struct StagingBuffer { + vk::Buffer buffer; + MemoryCommit commit; + std::span<u8> mapped_span; u64 tick = 0; + + StagingBufferRef Ref() const noexcept { + return { + .buffer = *buffer, + .mapped_span = mapped_span, + }; + } }; - struct StagingBuffers final { + struct StagingBuffers { std::vector<StagingBuffer> entries; - std::size_t delete_index = 0; + size_t delete_index = 0; + size_t iterate_index = 0; }; - static constexpr std::size_t NumLevels = sizeof(std::size_t) * CHAR_BIT; - using StagingBuffersCache = std::array<StagingBuffers, NumLevels>; + static constexpr size_t NUM_LEVELS = sizeof(size_t) * CHAR_BIT; + using StagingBuffersCache = std::array<StagingBuffers, NUM_LEVELS>; - VKBuffer* TryGetReservedBuffer(std::size_t size, bool host_visible); + std::optional<StagingBufferRef> TryGetReservedBuffer(size_t size, MemoryUsage usage); - VKBuffer& CreateStagingBuffer(std::size_t size, bool host_visible); + StagingBufferRef CreateStagingBuffer(size_t size, MemoryUsage usage); - StagingBuffersCache& GetCache(bool host_visible); + StagingBuffersCache& GetCache(MemoryUsage usage); - void ReleaseCache(bool host_visible); + void ReleaseCache(MemoryUsage usage); - u64 ReleaseLevel(StagingBuffersCache& cache, std::size_t log2); + void ReleaseLevel(StagingBuffersCache& cache, size_t log2); const Device& device; - VKMemoryManager& memory_manager; + MemoryAllocator& memory_allocator; VKScheduler& scheduler; - StagingBuffersCache host_staging_buffers; - StagingBuffersCache device_staging_buffers; + StagingBuffersCache device_local_cache; + StagingBuffersCache upload_cache; + StagingBuffersCache download_cache; - std::size_t current_delete_level = 0; + size_t current_delete_level = 0; + u64 buffer_index = 0; }; } // namespace Vulkan diff --git a/src/video_core/renderer_vulkan/vk_texture_cache.cpp b/src/video_core/renderer_vulkan/vk_texture_cache.cpp index bd11de012..ab14922d7 100644 --- a/src/video_core/renderer_vulkan/vk_texture_cache.cpp +++ b/src/video_core/renderer_vulkan/vk_texture_cache.cpp @@ -10,12 +10,12 @@ #include "video_core/engines/fermi_2d.h" #include "video_core/renderer_vulkan/blit_image.h" #include "video_core/renderer_vulkan/maxwell_to_vk.h" -#include "video_core/renderer_vulkan/vk_memory_manager.h" #include "video_core/renderer_vulkan/vk_rasterizer.h" #include "video_core/renderer_vulkan/vk_scheduler.h" #include "video_core/renderer_vulkan/vk_staging_buffer_pool.h" #include "video_core/renderer_vulkan/vk_texture_cache.h" #include "video_core/vulkan_common/vulkan_device.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Vulkan { @@ -554,10 +554,18 @@ void TextureCacheRuntime::Finish() { } ImageBufferMap TextureCacheRuntime::MapUploadBuffer(size_t size) { - const auto& buffer = staging_buffer_pool.GetUnusedBuffer(size, true); - return ImageBufferMap{ - .handle = *buffer.handle, - .map = buffer.commit->Map(size), + const auto staging_ref = staging_buffer_pool.Request(size, MemoryUsage::Upload); + return { + .handle = staging_ref.buffer, + .span = staging_ref.mapped_span, + }; +} + +ImageBufferMap TextureCacheRuntime::MapDownloadBuffer(size_t size) { + const auto staging_ref = staging_buffer_pool.Request(size, MemoryUsage::Download); + return { + .handle = staging_ref.buffer, + .span = staging_ref.mapped_span, }; } @@ -788,9 +796,9 @@ Image::Image(TextureCacheRuntime& runtime, const ImageInfo& info_, GPUVAddr gpu_ image(MakeImage(runtime.device, info)), buffer(MakeBuffer(runtime.device, info)), aspect_mask(ImageAspectMask(info.format)) { if (image) { - commit = runtime.memory_manager.Commit(image, false); + commit = runtime.memory_allocator.Commit(image, MemoryUsage::DeviceLocal); } else { - commit = runtime.memory_manager.Commit(buffer, false); + commit = runtime.memory_allocator.Commit(buffer, MemoryUsage::DeviceLocal); } if (IsPixelFormatASTC(info.format) && !runtime.device.IsOptimalAstcSupported()) { flags |= VideoCommon::ImageFlagBits::Converted; diff --git a/src/video_core/renderer_vulkan/vk_texture_cache.h b/src/video_core/renderer_vulkan/vk_texture_cache.h index 92a7aad8b..a55d405d1 100644 --- a/src/video_core/renderer_vulkan/vk_texture_cache.h +++ b/src/video_core/renderer_vulkan/vk_texture_cache.h @@ -7,8 +7,8 @@ #include <compare> #include <span> -#include "video_core/renderer_vulkan/vk_memory_manager.h" #include "video_core/texture_cache/texture_cache.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Vulkan { @@ -19,14 +19,13 @@ using VideoCommon::Offset2D; using VideoCommon::RenderTargets; using VideoCore::Surface::PixelFormat; -class VKScheduler; -class VKStagingBufferPool; - class BlitImageHelper; class Device; class Image; class ImageView; class Framebuffer; +class StagingBufferPool; +class VKScheduler; struct RenderPassKey { constexpr auto operator<=>(const RenderPassKey&) const noexcept = default; @@ -60,18 +59,18 @@ struct ImageBufferMap { } [[nodiscard]] std::span<u8> Span() const noexcept { - return map.Span(); + return span; } VkBuffer handle; - MemoryMap map; + std::span<u8> span; }; struct TextureCacheRuntime { const Device& device; VKScheduler& scheduler; - VKMemoryManager& memory_manager; - VKStagingBufferPool& staging_buffer_pool; + MemoryAllocator& memory_allocator; + StagingBufferPool& staging_buffer_pool; BlitImageHelper& blit_image_helper; std::unordered_map<RenderPassKey, vk::RenderPass> renderpass_cache; @@ -79,10 +78,7 @@ struct TextureCacheRuntime { [[nodiscard]] ImageBufferMap MapUploadBuffer(size_t size); - [[nodiscard]] ImageBufferMap MapDownloadBuffer(size_t size) { - // TODO: Have a special function for this - return MapUploadBuffer(size); - } + [[nodiscard]] ImageBufferMap MapDownloadBuffer(size_t size); void BlitImage(Framebuffer* dst_framebuffer, ImageView& dst, ImageView& src, const std::array<Offset2D, 2>& dst_region, @@ -141,7 +137,7 @@ private: VKScheduler* scheduler; vk::Image image; vk::Buffer buffer; - VKMemoryCommit commit; + MemoryCommit commit; VkImageAspectFlags aspect_mask = 0; bool initialized = false; }; diff --git a/src/video_core/texture_cache/accelerated_swizzle.cpp b/src/video_core/texture_cache/accelerated_swizzle.cpp index a4fc1184b..15585caeb 100644 --- a/src/video_core/texture_cache/accelerated_swizzle.cpp +++ b/src/video_core/texture_cache/accelerated_swizzle.cpp @@ -27,7 +27,7 @@ BlockLinearSwizzle2DParams MakeBlockLinearSwizzle2DParams(const SwizzleParameter const Extent3D num_tiles = swizzle.num_tiles; const u32 bytes_per_block = BytesPerBlock(info.format); const u32 stride_alignment = CalculateLevelStrideAlignment(info, swizzle.level); - const u32 stride = Common::AlignBits(num_tiles.width, stride_alignment) * bytes_per_block; + const u32 stride = Common::AlignUpLog2(num_tiles.width, stride_alignment) * bytes_per_block; const u32 gobs_in_x = Common::DivCeilLog2(stride, GOB_SIZE_X_SHIFT); return BlockLinearSwizzle2DParams{ .origin{0, 0, 0}, @@ -47,7 +47,7 @@ BlockLinearSwizzle3DParams MakeBlockLinearSwizzle3DParams(const SwizzleParameter const Extent3D num_tiles = swizzle.num_tiles; const u32 bytes_per_block = BytesPerBlock(info.format); const u32 stride_alignment = CalculateLevelStrideAlignment(info, swizzle.level); - const u32 stride = Common::AlignBits(num_tiles.width, stride_alignment) * bytes_per_block; + const u32 stride = Common::AlignUpLog2(num_tiles.width, stride_alignment) * bytes_per_block; const u32 gobs_in_x = (stride + GOB_SIZE_X - 1) >> GOB_SIZE_X_SHIFT; const u32 block_size = gobs_in_x << (GOB_SIZE_SHIFT + block.height + block.depth); diff --git a/src/video_core/texture_cache/util.cpp b/src/video_core/texture_cache/util.cpp index 279932778..ce8fcfe0a 100644 --- a/src/video_core/texture_cache/util.cpp +++ b/src/video_core/texture_cache/util.cpp @@ -279,7 +279,7 @@ template <u32 GOB_EXTENT> const bool is_small = IsSmallerThanGobSize(blocks, gob, info.block.depth); const u32 alignment = is_small ? 0 : info.tile_width_spacing; return Extent2D{ - .width = Common::AlignBits(gobs.width, alignment), + .width = Common::AlignUpLog2(gobs.width, alignment), .height = gobs.height, }; } @@ -352,7 +352,7 @@ template <u32 GOB_EXTENT> // https://github.com/Ryujinx/Ryujinx/blob/1c9aba6de1520aea5480c032e0ff5664ac1bb36f/Ryujinx.Graphics.Texture/SizeCalculator.cs#L134 if (tile_width_spacing > 0) { const u32 alignment_log2 = GOB_SIZE_SHIFT + tile_width_spacing + block.height + block.depth; - return Common::AlignBits(size_bytes, alignment_log2); + return Common::AlignUpLog2(size_bytes, alignment_log2); } const u32 aligned_height = Common::AlignUp(size.height, tile_size_y); while (block.height != 0 && aligned_height <= (1U << (block.height - 1)) * GOB_SIZE_Y) { @@ -528,9 +528,9 @@ template <u32 GOB_EXTENT> const u32 alignment = StrideAlignment(num_tiles, info.block, bpp_log2, info.tile_width_spacing); const Extent3D mip_block = AdjustMipBlockSize(num_tiles, info.block, 0); return Extent3D{ - .width = Common::AlignBits(num_tiles.width, alignment), - .height = Common::AlignBits(num_tiles.height, GOB_SIZE_Y_SHIFT + mip_block.height), - .depth = Common::AlignBits(num_tiles.depth, GOB_SIZE_Z_SHIFT + mip_block.depth), + .width = Common::AlignUpLog2(num_tiles.width, alignment), + .height = Common::AlignUpLog2(num_tiles.height, GOB_SIZE_Y_SHIFT + mip_block.height), + .depth = Common::AlignUpLog2(num_tiles.depth, GOB_SIZE_Z_SHIFT + mip_block.depth), }; } diff --git a/src/video_core/textures/decoders.cpp b/src/video_core/textures/decoders.cpp index 9f5181318..62685a183 100644 --- a/src/video_core/textures/decoders.cpp +++ b/src/video_core/textures/decoders.cpp @@ -49,7 +49,7 @@ void Swizzle(std::span<u8> output, std::span<const u8> input, u32 bytes_per_pixe // We can configure here a custom pitch // As it's not exposed 'width * bpp' will be the expected pitch. const u32 pitch = width * bytes_per_pixel; - const u32 stride = Common::AlignBits(width, stride_alignment) * bytes_per_pixel; + const u32 stride = Common::AlignUpLog2(width, stride_alignment) * bytes_per_pixel; const u32 gobs_in_x = Common::DivCeilLog2(stride, GOB_SIZE_X_SHIFT); const u32 block_size = gobs_in_x << (GOB_SIZE_SHIFT + block_height + block_depth); @@ -217,9 +217,9 @@ void SwizzleKepler(const u32 width, const u32 height, const u32 dst_x, const u32 std::size_t CalculateSize(bool tiled, u32 bytes_per_pixel, u32 width, u32 height, u32 depth, u32 block_height, u32 block_depth) { if (tiled) { - const u32 aligned_width = Common::AlignBits(width * bytes_per_pixel, GOB_SIZE_X_SHIFT); - const u32 aligned_height = Common::AlignBits(height, GOB_SIZE_Y_SHIFT + block_height); - const u32 aligned_depth = Common::AlignBits(depth, GOB_SIZE_Z_SHIFT + block_depth); + const u32 aligned_width = Common::AlignUpLog2(width * bytes_per_pixel, GOB_SIZE_X_SHIFT); + const u32 aligned_height = Common::AlignUpLog2(height, GOB_SIZE_Y_SHIFT + block_height); + const u32 aligned_depth = Common::AlignUpLog2(depth, GOB_SIZE_Z_SHIFT + block_depth); return aligned_width * aligned_height * aligned_depth; } else { return width * height * depth * bytes_per_pixel; diff --git a/src/video_core/vulkan_common/vulkan_debug_callback.h b/src/video_core/vulkan_common/vulkan_debug_callback.h index 2efcd244c..b0519f132 100644 --- a/src/video_core/vulkan_common/vulkan_debug_callback.h +++ b/src/video_core/vulkan_common/vulkan_debug_callback.h @@ -2,6 +2,8 @@ // Licensed under GPLv2 or any later version // Refer to the license.txt file included. +#pragma once + #include "video_core/vulkan_common/vulkan_wrapper.h" namespace Vulkan { diff --git a/src/video_core/vulkan_common/vulkan_memory_allocator.cpp b/src/video_core/vulkan_common/vulkan_memory_allocator.cpp new file mode 100644 index 000000000..d6eb3af31 --- /dev/null +++ b/src/video_core/vulkan_common/vulkan_memory_allocator.cpp @@ -0,0 +1,268 @@ +// Copyright 2018 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. + +#include <algorithm> +#include <bit> +#include <optional> +#include <vector> + +#include "common/alignment.h" +#include "common/assert.h" +#include "common/common_types.h" +#include "common/logging/log.h" +#include "video_core/vulkan_common/vulkan_device.h" +#include "video_core/vulkan_common/vulkan_memory_allocator.h" +#include "video_core/vulkan_common/vulkan_wrapper.h" + +namespace Vulkan { +namespace { +struct Range { + u64 begin; + u64 end; + + [[nodiscard]] bool Contains(u64 iterator, u64 size) const noexcept { + return iterator < end && begin < iterator + size; + } +}; + +[[nodiscard]] u64 AllocationChunkSize(u64 required_size) { + static constexpr std::array sizes{ + 0x1000ULL << 10, 0x1400ULL << 10, 0x1800ULL << 10, 0x1c00ULL << 10, 0x2000ULL << 10, + 0x3200ULL << 10, 0x4000ULL << 10, 0x6000ULL << 10, 0x8000ULL << 10, 0xA000ULL << 10, + 0x10000ULL << 10, 0x18000ULL << 10, 0x20000ULL << 10, + }; + static_assert(std::is_sorted(sizes.begin(), sizes.end())); + + const auto it = std::ranges::lower_bound(sizes, required_size); + return it != sizes.end() ? *it : Common::AlignUp(required_size, 4ULL << 20); +} + +[[nodiscard]] VkMemoryPropertyFlags MemoryUsagePropertyFlags(MemoryUsage usage) { + switch (usage) { + case MemoryUsage::DeviceLocal: + return VK_MEMORY_PROPERTY_DEVICE_LOCAL_BIT; + case MemoryUsage::Upload: + return VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT | VK_MEMORY_PROPERTY_HOST_COHERENT_BIT; + case MemoryUsage::Download: + return VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT | VK_MEMORY_PROPERTY_HOST_COHERENT_BIT | + VK_MEMORY_PROPERTY_HOST_CACHED_BIT; + } + UNREACHABLE_MSG("Invalid memory usage={}", usage); + return VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT | VK_MEMORY_PROPERTY_HOST_COHERENT_BIT; +} +} // Anonymous namespace + +class MemoryAllocation { +public: + explicit MemoryAllocation(const Device& device_, vk::DeviceMemory memory_, + VkMemoryPropertyFlags properties, u64 allocation_size_, u32 type) + : device{device_}, memory{std::move(memory_)}, allocation_size{allocation_size_}, + property_flags{properties}, shifted_memory_type{1U << type} {} + + [[nodiscard]] std::optional<MemoryCommit> Commit(VkDeviceSize size, VkDeviceSize alignment) { + const std::optional<u64> alloc = FindFreeRegion(size, alignment); + if (!alloc) { + // Signal out of memory, it'll try to do more allocations. + return std::nullopt; + } + const Range range{ + .begin = *alloc, + .end = *alloc + size, + }; + commits.insert(std::ranges::upper_bound(commits, *alloc, {}, &Range::begin), range); + return std::make_optional<MemoryCommit>(this, *memory, *alloc, *alloc + size); + } + + void Free(u64 begin) { + const auto it = std::ranges::find(commits, begin, &Range::begin); + ASSERT_MSG(it != commits.end(), "Invalid commit"); + commits.erase(it); + } + + [[nodiscard]] std::span<u8> Map() { + if (memory_mapped_span.empty()) { + u8* const raw_pointer = memory.Map(0, allocation_size); + memory_mapped_span = std::span<u8>(raw_pointer, allocation_size); + } + return memory_mapped_span; + } + + /// Returns whether this allocation is compatible with the arguments. + [[nodiscard]] bool IsCompatible(VkMemoryPropertyFlags flags, u32 type_mask) const { + return (flags & property_flags) && (type_mask & shifted_memory_type) != 0; + } + +private: + [[nodiscard]] static constexpr u32 ShiftType(u32 type) { + return 1U << type; + } + + [[nodiscard]] std::optional<u64> FindFreeRegion(u64 size, u64 alignment) noexcept { + ASSERT(std::has_single_bit(alignment)); + const u64 alignment_log2 = std::countr_zero(alignment); + std::optional<u64> candidate; + u64 iterator = 0; + auto commit = commits.begin(); + while (iterator + size <= allocation_size) { + candidate = candidate.value_or(iterator); + if (commit == commits.end()) { + break; + } + if (commit->Contains(*candidate, size)) { + candidate = std::nullopt; + } + iterator = Common::AlignUpLog2(commit->end, alignment_log2); + ++commit; + } + return candidate; + } + + const Device& device; ///< Vulkan device. + const vk::DeviceMemory memory; ///< Vulkan memory allocation handler. + const u64 allocation_size; ///< Size of this allocation. + const VkMemoryPropertyFlags property_flags; ///< Vulkan memory property flags. + const u32 shifted_memory_type; ///< Shifted Vulkan memory type. + std::vector<Range> commits; ///< All commit ranges done from this allocation. + std::span<u8> memory_mapped_span; ///< Memory mapped span. Empty if not queried before. +}; + +MemoryCommit::MemoryCommit(MemoryAllocation* allocation_, VkDeviceMemory memory_, u64 begin_, + u64 end_) noexcept + : allocation{allocation_}, memory{memory_}, begin{begin_}, end{end_} {} + +MemoryCommit::~MemoryCommit() { + Release(); +} + +MemoryCommit& MemoryCommit::operator=(MemoryCommit&& rhs) noexcept { + Release(); + allocation = std::exchange(rhs.allocation, nullptr); + memory = rhs.memory; + begin = rhs.begin; + end = rhs.end; + span = std::exchange(rhs.span, std::span<u8>{}); + return *this; +} + +MemoryCommit::MemoryCommit(MemoryCommit&& rhs) noexcept + : allocation{std::exchange(rhs.allocation, nullptr)}, memory{rhs.memory}, begin{rhs.begin}, + end{rhs.end}, span{std::exchange(rhs.span, std::span<u8>{})} {} + +std::span<u8> MemoryCommit::Map() { + if (span.empty()) { + span = allocation->Map().subspan(begin, end - begin); + } + return span; +} + +void MemoryCommit::Release() { + if (allocation) { + allocation->Free(begin); + } +} + +MemoryAllocator::MemoryAllocator(const Device& device_) + : device{device_}, properties{device_.GetPhysical().GetMemoryProperties()} {} + +MemoryAllocator::~MemoryAllocator() = default; + +MemoryCommit MemoryAllocator::Commit(const VkMemoryRequirements& requirements, MemoryUsage usage) { + // Find the fastest memory flags we can afford with the current requirements + const VkMemoryPropertyFlags flags = MemoryPropertyFlags(requirements.memoryTypeBits, usage); + if (std::optional<MemoryCommit> commit = TryCommit(requirements, flags)) { + return std::move(*commit); + } + // Commit has failed, allocate more memory. + // TODO(Rodrigo): Handle out of memory situations in some way like flushing to guest memory. + AllocMemory(flags, requirements.memoryTypeBits, AllocationChunkSize(requirements.size)); + + // Commit again, this time it won't fail since there's a fresh allocation above. + // If it does, there's a bug. + return TryCommit(requirements, flags).value(); +} + +MemoryCommit MemoryAllocator::Commit(const vk::Buffer& buffer, MemoryUsage usage) { + auto commit = Commit(device.GetLogical().GetBufferMemoryRequirements(*buffer), usage); + buffer.BindMemory(commit.Memory(), commit.Offset()); + return commit; +} + +MemoryCommit MemoryAllocator::Commit(const vk::Image& image, MemoryUsage usage) { + auto commit = Commit(device.GetLogical().GetImageMemoryRequirements(*image), usage); + image.BindMemory(commit.Memory(), commit.Offset()); + return commit; +} + +void MemoryAllocator::AllocMemory(VkMemoryPropertyFlags flags, u32 type_mask, u64 size) { + const u32 type = FindType(flags, type_mask).value(); + vk::DeviceMemory memory = device.GetLogical().AllocateMemory({ + .sType = VK_STRUCTURE_TYPE_MEMORY_ALLOCATE_INFO, + .pNext = nullptr, + .allocationSize = size, + .memoryTypeIndex = type, + }); + allocations.push_back( + std::make_unique<MemoryAllocation>(device, std::move(memory), flags, size, type)); +} + +std::optional<MemoryCommit> MemoryAllocator::TryCommit(const VkMemoryRequirements& requirements, + VkMemoryPropertyFlags flags) { + for (auto& allocation : allocations) { + if (!allocation->IsCompatible(flags, requirements.memoryTypeBits)) { + continue; + } + if (auto commit = allocation->Commit(requirements.size, requirements.alignment)) { + return commit; + } + } + return std::nullopt; +} + +VkMemoryPropertyFlags MemoryAllocator::MemoryPropertyFlags(u32 type_mask, MemoryUsage usage) const { + return MemoryPropertyFlags(type_mask, MemoryUsagePropertyFlags(usage)); +} + +VkMemoryPropertyFlags MemoryAllocator::MemoryPropertyFlags(u32 type_mask, + VkMemoryPropertyFlags flags) const { + if (FindType(flags, type_mask)) { + // Found a memory type with those requirements + return flags; + } + if (flags & VK_MEMORY_PROPERTY_HOST_CACHED_BIT) { + // Remove host cached bit in case it's not supported + return MemoryPropertyFlags(type_mask, flags & ~VK_MEMORY_PROPERTY_HOST_CACHED_BIT); + } + if (flags & VK_MEMORY_PROPERTY_DEVICE_LOCAL_BIT) { + // Remove device local, if it's not supported by the requested resource + return MemoryPropertyFlags(type_mask, flags & ~VK_MEMORY_PROPERTY_DEVICE_LOCAL_BIT); + } + UNREACHABLE_MSG("No compatible memory types found"); + return 0; +} + +std::optional<u32> MemoryAllocator::FindType(VkMemoryPropertyFlags flags, u32 type_mask) const { + for (u32 type_index = 0; type_index < properties.memoryTypeCount; ++type_index) { + const VkMemoryPropertyFlags type_flags = properties.memoryTypes[type_index].propertyFlags; + if ((type_mask & (1U << type_index)) && (type_flags & flags)) { + // The type matches in type and in the wanted properties. + return type_index; + } + } + // Failed to find index + return std::nullopt; +} + +bool IsHostVisible(MemoryUsage usage) noexcept { + switch (usage) { + case MemoryUsage::DeviceLocal: + return false; + case MemoryUsage::Upload: + case MemoryUsage::Download: + return true; + } + UNREACHABLE_MSG("Invalid memory usage={}", usage); + return false; +} + +} // namespace Vulkan diff --git a/src/video_core/vulkan_common/vulkan_memory_allocator.h b/src/video_core/vulkan_common/vulkan_memory_allocator.h new file mode 100644 index 000000000..9e6cfabf9 --- /dev/null +++ b/src/video_core/vulkan_common/vulkan_memory_allocator.h @@ -0,0 +1,117 @@ +// Copyright 2019 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. + +#pragma once + +#include <memory> +#include <span> +#include <utility> +#include <vector> +#include "common/common_types.h" +#include "video_core/vulkan_common/vulkan_wrapper.h" + +namespace Vulkan { + +class Device; +class MemoryMap; +class MemoryAllocation; + +/// Hints and requirements for the backing memory type of a commit +enum class MemoryUsage { + DeviceLocal, ///< Hints device local usages, fastest memory type to read and write from the GPU + Upload, ///< Requires a host visible memory type optimized for CPU to GPU uploads + Download, ///< Requires a host visible memory type optimized for GPU to CPU readbacks +}; + +/// Ownership handle of a memory commitment. +/// Points to a subregion of a memory allocation. +class MemoryCommit { +public: + explicit MemoryCommit() noexcept = default; + explicit MemoryCommit(MemoryAllocation* allocation_, VkDeviceMemory memory_, u64 begin_, + u64 end_) noexcept; + ~MemoryCommit(); + + MemoryCommit& operator=(MemoryCommit&&) noexcept; + MemoryCommit(MemoryCommit&&) noexcept; + + MemoryCommit& operator=(const MemoryCommit&) = delete; + MemoryCommit(const MemoryCommit&) = delete; + + /// Returns a host visible memory map. + /// It will map the backing allocation if it hasn't been mapped before. + std::span<u8> Map(); + + /// Returns the Vulkan memory handler. + VkDeviceMemory Memory() const { + return memory; + } + + /// Returns the start position of the commit relative to the allocation. + VkDeviceSize Offset() const { + return static_cast<VkDeviceSize>(begin); + } + +private: + void Release(); + + MemoryAllocation* allocation{}; ///< Pointer to the large memory allocation. + VkDeviceMemory memory{}; ///< Vulkan device memory handler. + u64 begin{}; ///< Beginning offset in bytes to where the commit exists. + u64 end{}; ///< Offset in bytes where the commit ends. + std::span<u8> span; ///< Host visible memory span. Empty if not queried before. +}; + +/// Memory allocator container. +/// Allocates and releases memory allocations on demand. +class MemoryAllocator { +public: + explicit MemoryAllocator(const Device& device_); + ~MemoryAllocator(); + + MemoryAllocator& operator=(const MemoryAllocator&) = delete; + MemoryAllocator(const MemoryAllocator&) = delete; + + /** + * Commits a memory with the specified requirements. + * + * @param requirements Requirements returned from a Vulkan call. + * @param usage Indicates how the memory will be used. + * + * @returns A memory commit. + */ + MemoryCommit Commit(const VkMemoryRequirements& requirements, MemoryUsage usage); + + /// Commits memory required by the buffer and binds it. + MemoryCommit Commit(const vk::Buffer& buffer, MemoryUsage usage); + + /// Commits memory required by the image and binds it. + MemoryCommit Commit(const vk::Image& image, MemoryUsage usage); + +private: + /// Allocates a chunk of memory. + void AllocMemory(VkMemoryPropertyFlags flags, u32 type_mask, u64 size); + + /// Tries to allocate a memory commit. + std::optional<MemoryCommit> TryCommit(const VkMemoryRequirements& requirements, + VkMemoryPropertyFlags flags); + + /// Returns the fastest compatible memory property flags from a wanted usage. + VkMemoryPropertyFlags MemoryPropertyFlags(u32 type_mask, MemoryUsage usage) const; + + /// Returns the fastest compatible memory property flags from the wanted flags. + VkMemoryPropertyFlags MemoryPropertyFlags(u32 type_mask, VkMemoryPropertyFlags flags) const; + + /// Returns index to the fastest memory type compatible with the passed requirements. + std::optional<u32> FindType(VkMemoryPropertyFlags flags, u32 type_mask) const; + + const Device& device; ///< Device handle. + const VkPhysicalDeviceMemoryProperties properties; ///< Physical device properties. + std::vector<std::unique_ptr<MemoryAllocation>> allocations; ///< Current allocations. +}; + +/// Returns true when a memory usage is guaranteed to be host visible. +bool IsHostVisible(MemoryUsage usage) noexcept; + +} // namespace Vulkan |