diff options
Diffstat (limited to 'Ryujinx.Memory/Range')
| -rw-r--r-- | Ryujinx.Memory/Range/INonOverlappingRange.cs | 16 | ||||
| -rw-r--r-- | Ryujinx.Memory/Range/IRange.cs | 31 | ||||
| -rw-r--r-- | Ryujinx.Memory/Range/NonOverlappingRangeList.cs | 108 | ||||
| -rw-r--r-- | Ryujinx.Memory/Range/RangeList.cs | 342 |
4 files changed, 497 insertions, 0 deletions
diff --git a/Ryujinx.Memory/Range/INonOverlappingRange.cs b/Ryujinx.Memory/Range/INonOverlappingRange.cs new file mode 100644 index 00000000..1886eb1d --- /dev/null +++ b/Ryujinx.Memory/Range/INonOverlappingRange.cs @@ -0,0 +1,16 @@ +namespace Ryujinx.Memory.Range +{ + /// <summary> + /// Range of memory that can be split in two. + /// </summary> + interface INonOverlappingRange : IRange + { + /// <summary> + /// Split this region into two, around the specified address. + /// This region is updated to end at the split address, and a new region is created to represent past that point. + /// </summary> + /// <param name="splitAddress">Address to split the region around</param> + /// <returns>The second part of the split region, with start address at the given split.</returns> + public INonOverlappingRange Split(ulong splitAddress); + } +} diff --git a/Ryujinx.Memory/Range/IRange.cs b/Ryujinx.Memory/Range/IRange.cs new file mode 100644 index 00000000..1685396d --- /dev/null +++ b/Ryujinx.Memory/Range/IRange.cs @@ -0,0 +1,31 @@ +namespace Ryujinx.Memory.Range +{ + /// <summary> + /// Range of memory. + /// </summary> + public interface IRange + { + /// <summary> + /// Base address. + /// </summary> + ulong Address { get; } + + /// <summary> + /// Size of the range. + /// </summary> + ulong Size { get; } + + /// <summary> + /// End address. + /// </summary> + ulong EndAddress { get; } + + /// <summary> + /// Check if this range overlaps with another. + /// </summary> + /// <param name="address">Base address</param> + /// <param name="size">Size of the range</param> + /// <returns>True if overlapping, false otherwise</returns> + bool OverlapsWith(ulong address, ulong size); + } +}
\ No newline at end of file diff --git a/Ryujinx.Memory/Range/NonOverlappingRangeList.cs b/Ryujinx.Memory/Range/NonOverlappingRangeList.cs new file mode 100644 index 00000000..9a8f84dd --- /dev/null +++ b/Ryujinx.Memory/Range/NonOverlappingRangeList.cs @@ -0,0 +1,108 @@ +using System; +using System.Collections.Generic; + +namespace Ryujinx.Memory.Range +{ + /// <summary> + /// A range list that assumes ranges are non-overlapping, with list items that can be split in two to avoid overlaps. + /// </summary> + /// <typeparam name="T">Type of the range.</typeparam> + class NonOverlappingRangeList<T> : RangeList<T> where T : INonOverlappingRange + { + /// <summary> + /// Finds a list of regions that cover the desired (address, size) range. + /// If this range starts or ends in the middle of an existing region, it is split and only the relevant part is added. + /// If there is no matching region, or there is a gap, then new regions are created with the factory. + /// Regions are added to the list in address ascending order. + /// </summary> + /// <param name="list">List to add found regions to</param> + /// <param name="address">Start address of the search region</param> + /// <param name="size">Size of the search region</param> + /// <param name="factory">Factory for creating new ranges</param> + public void GetOrAddRegions(List<T> list, ulong address, ulong size, Func<ulong, ulong, T> factory) + { + // (regarding the specific case this generalized function is used for) + // A new region may be split into multiple parts if multiple virtual regions have mapped to it. + // For instance, while a virtual mapping could cover 0-2 in physical space, the space 0-1 may have already been reserved... + // So we need to return both the split 0-1 and 1-2 ranges. + + var results = new T[1]; + int count = FindOverlapsNonOverlapping(address, size, ref results); + + if (count == 0) + { + // The region is fully unmapped. Create and add it to the range list. + T region = factory(address, size); + list.Add(region); + Add(region); + } + else + { + ulong lastAddress = address; + ulong endAddress = address + size; + + for (int i = 0; i < count; i++) + { + T region = results[i]; + if (count == 1 && region.Address == address && region.Size == size) + { + // Exact match, no splitting required. + list.Add(region); + return; + } + + if (lastAddress < region.Address) + { + // There is a gap between this region and the last. We need to fill it. + T fillRegion = factory(lastAddress, region.Address - lastAddress); + list.Add(fillRegion); + Add(fillRegion); + } + + if (region.Address < address) + { + // Split the region around our base address and take the high half. + + region = Split(region, address); + } + + if (region.EndAddress > address + size) + { + // Split the region around our end address and take the low half. + + Split(region, address + size); + } + + list.Add(region); + lastAddress = region.EndAddress; + } + + if (lastAddress < endAddress) + { + // There is a gap between this region and the end. We need to fill it. + T fillRegion = factory(lastAddress, endAddress - lastAddress); + list.Add(fillRegion); + Add(fillRegion); + } + } + } + + /// <summary> + /// Splits a region around a target point and updates the region list. + /// The original region's size is modified, but its address stays the same. + /// A new region starting from the split address is added to the region list and returned. + /// </summary> + /// <param name="region">The region to split</param> + /// <param name="splitAddress">The address to split with</param> + /// <returns>The new region (high part)</returns> + private T Split(T region, ulong splitAddress) + { + Remove(region); + + T newRegion = (T)region.Split(splitAddress); + Add(region); + Add(newRegion); + return newRegion; + } + } +} diff --git a/Ryujinx.Memory/Range/RangeList.cs b/Ryujinx.Memory/Range/RangeList.cs new file mode 100644 index 00000000..3c8c4c4c --- /dev/null +++ b/Ryujinx.Memory/Range/RangeList.cs @@ -0,0 +1,342 @@ +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 RangeList<T> : IEnumerable<T> where T : IRange + { + private const int ArrayGrowthSize = 32; + + private readonly List<T> _items; + + public int Count => _items.Count; + + /// <summary> + /// Creates a new range list. + /// </summary> + public RangeList() + { + _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.Address); + + 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.Address); + + if (index >= 0) + { + while (index > 0 && _items[index - 1].Address == item.Address) + { + index--; + } + + while (index < _items.Count) + { + if (_items[index].Equals(item)) + { + _items.RemoveAt(index); + + return true; + } + + if (_items[index].Address > item.Address) + { + break; + } + + index++; + } + } + + return false; + } + + /// <summary> + /// Gets the first item on the list overlapping in memory with the specified item. + /// </summary> + /// <remarks> + /// Despite the name, this has no ordering guarantees of the returned item. + /// It only ensures that the item returned overlaps the specified item. + /// </remarks> + /// <param name="item">Item to check for overlaps</param> + /// <returns>The overlapping item, or the default value for the type if none found</returns> + public T FindFirstOverlap(T item) + { + return FindFirstOverlap(item.Address, item.Size); + } + + /// <summary> + /// Gets the first item on the list overlapping the specified memory range. + /// </summary> + /// <remarks> + /// Despite the name, this has no ordering guarantees of the returned item. + /// It only ensures that the item returned overlaps the specified memory range. + /// </remarks> + /// <param name="address">Start address of the range</param> + /// <param name="size">Size in bytes of the range</param> + /// <returns>The overlapping item, or the default value for the type if none found</returns> + public T FindFirstOverlap(ulong address, ulong size) + { + int index = BinarySearch(address, size); + + if (index < 0) + { + return default(T); + } + + return _items[index]; + } + + /// <summary> + /// Gets all items overlapping with the specified item in memory. + /// </summary> + /// <param name="item">Item to check for overlaps</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(T item, ref T[] output) + { + return FindOverlaps(item.Address, item.Size, ref output); + } + + /// <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) + { + int outputIndex = 0; + + ulong endAddress = address + size; + + foreach (T item in _items) + { + if (item.Address >= endAddress) + { + break; + } + + if (item.OverlapsWith(address, size)) + { + if (outputIndex == output.Length) + { + Array.Resize(ref output, outputIndex + ArrayGrowthSize); + } + + output[outputIndex++] = item; + } + } + + return outputIndex; + } + + /// <summary> + /// Gets all items overlapping with the specified item in memory. + /// </summary> + /// <remarks> + /// This method only returns correct results if none of the items on the list overlaps with + /// each other. If that is not the case, this method should not be used. + /// This method is faster than the regular method to find all overlaps. + /// </remarks> + /// <param name="item">Item to check for overlaps</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 FindOverlapsNonOverlapping(T item, ref T[] output) + { + return FindOverlapsNonOverlapping(item.Address, item.Size, ref output); + } + + /// <summary> + /// Gets all items on the list overlapping the specified memory range. + /// </summary> + /// <remarks> + /// This method only returns correct results if none of the items on the list overlaps with + /// each other. If that is not the case, this method should not be used. + /// This method is faster than the regular method to find all overlaps. + /// </remarks> + /// <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 FindOverlapsNonOverlapping(ulong address, ulong size, ref T[] output) + { + // This is a bit faster than FindOverlaps, but only works + // when none of the items on the list overlaps with each other. + int outputIndex = 0; + + int index = BinarySearch(address, size); + + if (index >= 0) + { + while (index > 0 && _items[index - 1].OverlapsWith(address, size)) + { + index--; + } + + do + { + if (outputIndex == output.Length) + { + Array.Resize(ref output, outputIndex + ArrayGrowthSize); + } + + output[outputIndex++] = _items[index++]; + } + while (index < _items.Count && _items[index].OverlapsWith(address, size)); + } + + return outputIndex; + } + + /// <summary> + /// Gets all items on the list with the specified memory address. + /// </summary> + /// <param name="address">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 address, ref T[] output) + { + int index = BinarySearch(address); + + int outputIndex = 0; + + if (index >= 0) + { + while (index > 0 && _items[index - 1].Address == address) + { + index--; + } + + while (index < _items.Count) + { + T overlap = _items[index++]; + + if (overlap.Address != address) + { + 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.Address == address) + { + return middle; + } + + if (address < item.Address) + { + right = middle - 1; + } + else + { + left = middle + 1; + } + } + + return ~left; + } + + /// <summary> + /// Performs binary search for items overlapping a given memory range. + /// </summary> + /// <param name="address">Start address of the range</param> + /// <param name="size">Size in bytes of the range</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, ulong size) + { + 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.OverlapsWith(address, size)) + { + return middle; + } + + if (address < item.Address) + { + 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 |