Support for resources on non-contiguous GPU memory regions (#1905)

* Support for resources on non-contiguous GPU memory regions

* Implement MultiRange physical addresses, only used with a single range for now

* Actually use non-contiguous ranges

* GetPhysicalRegions fixes

* Documentation and remove Address property from TextureInfo

* Finish implementing GetWritableRegion

* Fix typo

4 files changed, 579 insertions, 0 deletions

diff --git a/Ryujinx.Memory/Range/IMultiRangeItem.cs b/Ryujinx.Memory/Range/IMultiRangeItem.cs
new file mode 100644
index 00000000..e95a69fc
--- /dev/null
+++ b/Ryujinx.Memory/Range/IMultiRangeItem.cs
@@ -0,0 +1,9 @@
+namespace Ryujinx.Memory.Range
+{
+    public interface IMultiRangeItem
+    {
+        MultiRange Range { get; }
+
+        ulong BaseAddress => Range.GetSubRange(0).Address;
+    }
+}
diff --git a/Ryujinx.Memory/Range/MemoryRange.cs b/Ryujinx.Memory/Range/MemoryRange.cs
new file mode 100644
index 00000000..ba12bae5
--- /dev/null
+++ b/Ryujinx.Memory/Range/MemoryRange.cs
@@ -0,0 +1,71 @@
+using System;
+
+namespace Ryujinx.Memory.Range
+{
+    /// <summary>
+    /// Range of memory composed of an address and size.
+    /// </summary>
+    public struct MemoryRange : IEquatable<MemoryRange>
+    {
+        /// <summary>
+        /// An empty memory range, with a null address and zero size.
+        /// </summary>
+        public static MemoryRange Empty => new MemoryRange(0UL, 0);
+
+        /// <summary>
+        /// Start address of the range.
+        /// </summary>
+        public ulong Address { get; }
+
+        /// <summary>
+        /// Size of the range in bytes.
+        /// </summary>
+        public ulong Size { get; }
+
+        /// <summary>
+        /// Address where the range ends (exclusive).
+        /// </summary>
+        public ulong EndAddress => Address + Size;
+
+        /// <summary>
+        /// Creates a new memory range with the specified address and size.
+        /// </summary>
+        /// <param name="address">Start address</param>
+        /// <param name="size">Size in bytes</param>
+        public MemoryRange(ulong address, ulong size)
+        {
+            Address = address;
+            Size = size;
+        }
+
+        /// <summary>
+        /// Checks if the range overlaps with another.
+        /// </summary>
+        /// <param name="other">The other range to check for overlap</param>
+        /// <returns>True if the ranges overlap, false otherwise</returns>
+        public bool OverlapsWith(MemoryRange other)
+        {
+            ulong thisAddress = Address;
+            ulong thisEndAddress = EndAddress;
+            ulong otherAddress = other.Address;
+            ulong otherEndAddress = other.EndAddress;
+
+            return thisAddress < otherEndAddress && otherAddress < thisEndAddress;
+        }
+
+        public override bool Equals(object obj)
+        {
+            return obj is MemoryRange other && Equals(other);
+        }
+
+        public bool Equals(MemoryRange other)
+        {
+            return Address == other.Address && Size == other.Size;
+        }
+
+        public override int GetHashCode()
+        {
+            return HashCode.Combine(Address, Size);
+        }
+    }
+}
diff --git a/Ryujinx.Memory/Range/MultiRange.cs b/Ryujinx.Memory/Range/MultiRange.cs
new file mode 100644
index 00000000..b40daa8a
--- /dev/null
+++ b/Ryujinx.Memory/Range/MultiRange.cs
@@ -0,0 +1,295 @@
+using System;
+
+namespace Ryujinx.Memory.Range
+{
+    /// <summary>
+    /// Sequence of physical memory regions that a single non-contiguous virtual memory region maps to.
+    /// </summary>
+    public struct MultiRange : IEquatable<MultiRange>
+    {
+        private readonly MemoryRange _singleRange;
+        private readonly MemoryRange[] _ranges;
+
+        private bool HasSingleRange => _ranges == null;
+
+        /// <summary>
+        /// Total of physical sub-ranges on the virtual memory region.
+        /// </summary>
+        public int Count => HasSingleRange ? 1 : _ranges.Length;
+
+        /// <summary>
+        /// Minimum start address of all sub-ranges.
+        /// </summary>
+        public ulong MinAddress { get; }
+
+        /// <summary>
+        /// Maximum end address of all sub-ranges.
+        /// </summary>
+        public ulong MaxAddress { get; }
+
+        /// <summary>
+        /// Creates a new multi-range with a single physical region.
+        /// </summary>
+        /// <param name="address">Start address of the region</param>
+        /// <param name="size">Size of the region in bytes</param>
+        public MultiRange(ulong address, ulong size)
+        {
+            _singleRange = new MemoryRange(address, size);
+            _ranges = null;
+            MinAddress = address;
+            MaxAddress = address + size;
+        }
+
+        /// <summary>
+        /// Creates a new multi-range with multiple physical regions.
+        /// </summary>
+        /// <param name="ranges">Array of physical regions</param>
+        /// <exception cref="ArgumentNullException"><paramref name="ranges"/> is null</exception>
+        public MultiRange(MemoryRange[] ranges)
+        {
+            _singleRange = MemoryRange.Empty;
+            _ranges = ranges ?? throw new ArgumentNullException(nameof(ranges));
+
+            if (ranges.Length != 0)
+            {
+                MinAddress = ulong.MaxValue;
+                MaxAddress = 0UL;
+
+                foreach (MemoryRange range in ranges)
+                {
+                    if (MinAddress > range.Address)
+                    {
+                        MinAddress = range.Address;
+                    }
+
+                    if (MaxAddress < range.EndAddress)
+                    {
+                        MaxAddress = range.EndAddress;
+                    }
+                }
+            }
+            else
+            {
+                MinAddress = 0UL;
+                MaxAddress = 0UL;
+            }
+        }
+
+        /// <summary>
+        /// Gets the physical region at the specified index.
+        /// </summary>
+        /// <param name="index">Index of the physical region</param>
+        /// <returns>Region at the index specified</returns>
+        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is invalid</exception>
+        public MemoryRange GetSubRange(int index)
+        {
+            if (HasSingleRange)
+            {
+                if (index != 0)
+                {
+                    throw new ArgumentOutOfRangeException(nameof(index));
+                }
+
+                return _singleRange;
+            }
+            else
+            {
+                if ((uint)index >= _ranges.Length)
+                {
+                    throw new ArgumentOutOfRangeException(nameof(index));
+                }
+
+                return _ranges[index];
+            }
+        }
+
+        /// <summary>
+        /// Gets the physical region at the specified index, without explicit bounds checking.
+        /// </summary>
+        /// <param name="index">Index of the physical region</param>
+        /// <returns>Region at the index specified</returns>
+        private MemoryRange GetSubRangeUnchecked(int index)
+        {
+            return HasSingleRange ? _singleRange : _ranges[index];
+        }
+
+        /// <summary>
+        /// Check if two multi-ranges overlap with each other.
+        /// </summary>
+        /// <param name="other">Other multi-range to check for overlap</param>
+        /// <returns>True if any sub-range overlaps, false otherwise</returns>
+        public bool OverlapsWith(MultiRange other)
+        {
+            if (HasSingleRange && other.HasSingleRange)
+            {
+                return _singleRange.OverlapsWith(other._singleRange);
+            }
+            else
+            {
+                for (int i = 0; i < Count; i++)
+                {
+                    MemoryRange currentRange = GetSubRangeUnchecked(i);
+
+                    for (int j = 0; j < other.Count; j++)
+                    {
+                        if (currentRange.OverlapsWith(other.GetSubRangeUnchecked(j)))
+                        {
+                            return true;
+                        }
+                    }
+                }
+            }
+
+            return false;
+        }
+
+        /// <summary>
+        /// Checks if a given multi-range is fully contained inside another.
+        /// </summary>
+        /// <param name="other">Multi-range to be checked</param>
+        /// <returns>True if all the sub-ranges on <paramref name="other"/> are contained inside the multi-range, with the same order, false otherwise</returns>
+        public bool Contains(MultiRange other)
+        {
+            return FindOffset(other) >= 0;
+        }
+
+        /// <summary>
+        /// Calculates the offset of a given multi-range inside another, when the multi-range is fully contained
+        /// inside the other multi-range, otherwise returns -1.
+        /// </summary>
+        /// <param name="other">Multi-range that should be fully contained inside this one</param>
+        /// <returns>Offset in bytes if fully contained, otherwise -1</returns>
+        public int FindOffset(MultiRange other)
+        {
+            int thisCount = Count;
+            int otherCount = other.Count;
+
+            if (thisCount == 1 && otherCount == 1)
+            {
+                MemoryRange otherFirstRange = other.GetSubRangeUnchecked(0);
+                MemoryRange currentFirstRange = GetSubRangeUnchecked(0);
+
+                if (otherFirstRange.Address >= currentFirstRange.Address &&
+                    otherFirstRange.EndAddress <= currentFirstRange.EndAddress)
+                {
+                    return (int)(otherFirstRange.Address - currentFirstRange.Address);
+                }
+            }
+            else if (thisCount >= otherCount)
+            {
+                ulong baseOffset = 0;
+
+                MemoryRange otherFirstRange = other.GetSubRangeUnchecked(0);
+                MemoryRange otherLastRange = other.GetSubRangeUnchecked(otherCount - 1);
+
+                for (int i = 0; i < (thisCount - otherCount) + 1; baseOffset += GetSubRangeUnchecked(i).Size, i++)
+                {
+                    MemoryRange currentFirstRange = GetSubRangeUnchecked(i);
+                    MemoryRange currentLastRange = GetSubRangeUnchecked(i + otherCount - 1);
+
+                    if (otherCount > 1)
+                    {
+                        if (otherFirstRange.Address < currentFirstRange.Address ||
+                            otherFirstRange.EndAddress != currentFirstRange.EndAddress)
+                        {
+                            continue;
+                        }
+
+                        if (otherLastRange.Address != currentLastRange.Address ||
+                            otherLastRange.EndAddress > currentLastRange.EndAddress)
+                        {
+                            continue;
+                        }
+
+                        bool fullMatch = true;
+
+                        for (int j = 1; j < otherCount - 1; j++)
+                        {
+                            if (!GetSubRangeUnchecked(i + j).Equals(other.GetSubRangeUnchecked(j)))
+                            {
+                                fullMatch = false;
+                                break;
+                            }
+                        }
+
+                        if (!fullMatch)
+                        {
+                            continue;
+                        }
+                    }
+                    else if (currentFirstRange.Address > otherFirstRange.Address ||
+                             currentFirstRange.EndAddress < otherFirstRange.EndAddress)
+                    {
+                        continue;
+                    }
+
+                    return (int)(baseOffset + (otherFirstRange.Address - currentFirstRange.Address));
+                }
+            }
+
+            return -1;
+        }
+
+        /// <summary>
+        /// Gets the total size of all sub-ranges in bytes.
+        /// </summary>
+        /// <returns>Total size in bytes</returns>
+        public ulong GetSize()
+        {
+            ulong sum = 0;
+
+            foreach (MemoryRange range in _ranges)
+            {
+                sum += range.Size;
+            }
+
+            return sum;
+        }
+
+        public override bool Equals(object obj)
+        {
+            return obj is MultiRange other && Equals(other);
+        }
+
+        public bool Equals(MultiRange other)
+        {
+            if (HasSingleRange && other.HasSingleRange)
+            {
+                return _singleRange.Equals(other._singleRange);
+            }
+
+            int thisCount = Count;
+            if (thisCount != other.Count)
+            {
+                return false;
+            }
+
+            for (int i = 0; i < thisCount; i++)
+            {
+                if (!GetSubRangeUnchecked(i).Equals(other.GetSubRangeUnchecked(i)))
+                {
+                    return false;
+                }
+            }
+
+            return true;
+        }
+
+        public override int GetHashCode()
+        {
+            if (HasSingleRange)
+            {
+                return _singleRange.GetHashCode();
+            }
+
+            HashCode hash = new HashCode();
+
+            foreach (MemoryRange range in _ranges)
+            {
+                hash.Add(range);
+            }
+
+            return hash.ToHashCode();
+        }
+    }
+}
diff --git a/Ryujinx.Memory/Range/MultiRangeList.cs b/Ryujinx.Memory/Range/MultiRangeList.cs
new file mode 100644
index 00000000..1d5439a0
--- /dev/null
+++ b/Ryujinx.Memory/Range/MultiRangeList.cs
@@ -0,0 +1,204 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+
+namespace Ryujinx.Memory.Range
+{
+    /// <summary>
+    /// Sorted list of ranges that supports binary search.
+    /// </summary>
+    /// <typeparam name="T">Type of the range.</typeparam>
+    public class MultiRangeList<T> : IEnumerable<T> where T : IMultiRangeItem
+    {
+        private const int ArrayGrowthSize = 32;
+
+        private readonly List<T> _items;
+
+        public int Count => _items.Count;
+
+        /// <summary>
+        /// Creates a new range list.
+        /// </summary>
+        public MultiRangeList()
+        {
+            _items = new List<T>();
+        }
+
+        /// <summary>
+        /// Adds a new item to the list.
+        /// </summary>
+        /// <param name="item">The item to be added</param>
+        public void Add(T item)
+        {
+            int index = BinarySearch(item.BaseAddress);
+
+            if (index < 0)
+            {
+                index = ~index;
+            }
+
+            _items.Insert(index, item);
+        }
+
+        /// <summary>
+        /// Removes an item from the list.
+        /// </summary>
+        /// <param name="item">The item to be removed</param>
+        /// <returns>True if the item was removed, or false if it was not found</returns>
+        public bool Remove(T item)
+        {
+            int index = BinarySearch(item.BaseAddress);
+
+            if (index >= 0)
+            {
+                while (index > 0 && _items[index - 1].BaseAddress == item.BaseAddress)
+                {
+                    index--;
+                }
+
+                while (index < _items.Count)
+                {
+                    if (_items[index].Equals(item))
+                    {
+                        _items.RemoveAt(index);
+
+                        return true;
+                    }
+
+                    if (_items[index].BaseAddress > item.BaseAddress)
+                    {
+                        break;
+                    }
+
+                    index++;
+                }
+            }
+
+            return false;
+        }
+
+        /// <summary>
+        /// Gets all items on the list overlapping the specified memory range.
+        /// </summary>
+        /// <param name="address">Start address of the range</param>
+        /// <param name="size">Size in bytes of the range</param>
+        /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
+        /// <returns>The number of overlapping items found</returns>
+        public int FindOverlaps(ulong address, ulong size, ref T[] output)
+        {
+            return FindOverlaps(new MultiRange(address, size), ref output);
+        }
+
+        /// <summary>
+        /// Gets all items on the list overlapping the specified memory ranges.
+        /// </summary>
+        /// <param name="range">Ranges of memory being searched</param>
+        /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
+        /// <returns>The number of overlapping items found</returns>
+        public int FindOverlaps(MultiRange range, ref T[] output)
+        {
+            int outputIndex = 0;
+
+            foreach (T item in _items)
+            {
+                if (item.Range.OverlapsWith(range))
+                {
+                    if (outputIndex == output.Length)
+                    {
+                        Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+                    }
+
+                    output[outputIndex++] = item;
+                }
+            }
+
+            return outputIndex;
+        }
+
+        /// <summary>
+        /// Gets all items on the list starting at the specified memory address.
+        /// </summary>
+        /// <param name="baseAddress">Base address to find</param>
+        /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
+        /// <returns>The number of matches found</returns>
+        public int FindOverlaps(ulong baseAddress, ref T[] output)
+        {
+            int index = BinarySearch(baseAddress);
+
+            int outputIndex = 0;
+
+            if (index >= 0)
+            {
+                while (index > 0 && _items[index - 1].BaseAddress == baseAddress)
+                {
+                    index--;
+                }
+
+                while (index < _items.Count)
+                {
+                    T overlap = _items[index++];
+
+                    if (overlap.BaseAddress != baseAddress)
+                    {
+                        break;
+                    }
+
+                    if (outputIndex == output.Length)
+                    {
+                        Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+                    }
+
+                    output[outputIndex++] = overlap;
+                }
+            }
+
+            return outputIndex;
+        }
+
+        /// <summary>
+        /// Performs binary search on the internal list of items.
+        /// </summary>
+        /// <param name="address">Address to find</param>
+        /// <returns>List index of the item, or complement index of nearest item with lower value on the list</returns>
+        private int BinarySearch(ulong address)
+        {
+            int left = 0;
+            int right = _items.Count - 1;
+
+            while (left <= right)
+            {
+                int range = right - left;
+
+                int middle = left + (range >> 1);
+
+                T item = _items[middle];
+
+                if (item.BaseAddress == address)
+                {
+                    return middle;
+                }
+
+                if (address < item.BaseAddress)
+                {
+                    right = middle - 1;
+                }
+                else
+                {
+                    left = middle + 1;
+                }
+            }
+
+            return ~left;
+        }
+
+        public IEnumerator<T> GetEnumerator()
+        {
+            return _items.GetEnumerator();
+        }
+
+        IEnumerator IEnumerable.GetEnumerator()
+        {
+            return _items.GetEnumerator();
+        }
+    }
+}
\ No newline at end of file