From cee712105850ac3385cd0091a923438167433f9f Mon Sep 17 00:00:00 2001 From: TSR Berry <20988865+TSRBerry@users.noreply.github.com> Date: Sat, 8 Apr 2023 01:22:00 +0200 Subject: Move solution and projects to src --- src/Ryujinx.Memory/Tracking/AbstractRegion.cs | 73 ++++ src/Ryujinx.Memory/Tracking/BitMap.cs | 199 +++++++++ src/Ryujinx.Memory/Tracking/ConcurrentBitmap.cs | 152 +++++++ src/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs | 55 +++ src/Ryujinx.Memory/Tracking/IRegionHandle.cs | 18 + src/Ryujinx.Memory/Tracking/MemoryTracking.cs | 306 ++++++++++++++ src/Ryujinx.Memory/Tracking/MultiRegionHandle.cs | 415 ++++++++++++++++++ src/Ryujinx.Memory/Tracking/PreciseRegionSignal.cs | 4 + src/Ryujinx.Memory/Tracking/RegionHandle.cs | 464 +++++++++++++++++++++ src/Ryujinx.Memory/Tracking/RegionSignal.cs | 4 + .../Tracking/SmartMultiRegionHandle.cs | 280 +++++++++++++ src/Ryujinx.Memory/Tracking/VirtualRegion.cs | 144 +++++++ 12 files changed, 2114 insertions(+) create mode 100644 src/Ryujinx.Memory/Tracking/AbstractRegion.cs create mode 100644 src/Ryujinx.Memory/Tracking/BitMap.cs create mode 100644 src/Ryujinx.Memory/Tracking/ConcurrentBitmap.cs create mode 100644 src/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs create mode 100644 src/Ryujinx.Memory/Tracking/IRegionHandle.cs create mode 100644 src/Ryujinx.Memory/Tracking/MemoryTracking.cs create mode 100644 src/Ryujinx.Memory/Tracking/MultiRegionHandle.cs create mode 100644 src/Ryujinx.Memory/Tracking/PreciseRegionSignal.cs create mode 100644 src/Ryujinx.Memory/Tracking/RegionHandle.cs create mode 100644 src/Ryujinx.Memory/Tracking/RegionSignal.cs create mode 100644 src/Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs create mode 100644 src/Ryujinx.Memory/Tracking/VirtualRegion.cs (limited to 'src/Ryujinx.Memory/Tracking') diff --git a/src/Ryujinx.Memory/Tracking/AbstractRegion.cs b/src/Ryujinx.Memory/Tracking/AbstractRegion.cs new file mode 100644 index 00000000..bd4c8ab5 --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/AbstractRegion.cs @@ -0,0 +1,73 @@ +using Ryujinx.Memory.Range; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// A region of memory. + /// + abstract class AbstractRegion : INonOverlappingRange + { + /// + /// Base address. + /// + public ulong Address { get; } + + /// + /// Size of the range in bytes. + /// + public ulong Size { get; protected set; } + + /// + /// End address. + /// + public ulong EndAddress => Address + Size; + + /// + /// Create a new region. + /// + /// Base address + /// Size of the range + protected AbstractRegion(ulong address, ulong size) + { + Address = address; + Size = size; + } + + /// + /// Check if this range overlaps with another. + /// + /// Base address + /// Size of the range + /// True if overlapping, false otherwise + public bool OverlapsWith(ulong address, ulong size) + { + return Address < address + size && address < EndAddress; + } + + /// + /// Signals to the handles that a memory event has occurred, and unprotects the region. Assumes that the tracking lock has been obtained. + /// + /// Address accessed + /// Size of the region affected in bytes + /// Whether the region was written to or read + /// Optional ID of the handles that should not be signalled + public abstract void Signal(ulong address, ulong size, bool write, int? exemptId); + + /// + /// Signals to the handles that a precise memory event has occurred. Assumes that the tracking lock has been obtained. + /// + /// Address accessed + /// Size of the region affected in bytes + /// Whether the region was written to or read + /// Optional ID of the handles that should not be signalled + public abstract void SignalPrecise(ulong address, ulong size, bool write, int? exemptId); + + /// + /// 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. + /// + /// Address to split the region around + /// The second part of the split region, with start address at the given split. + public abstract INonOverlappingRange Split(ulong splitAddress); + } +} diff --git a/src/Ryujinx.Memory/Tracking/BitMap.cs b/src/Ryujinx.Memory/Tracking/BitMap.cs new file mode 100644 index 00000000..173952f3 --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/BitMap.cs @@ -0,0 +1,199 @@ +using System.Runtime.CompilerServices; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// A bitmap that can check or set large ranges of true/false values at once. + /// + readonly struct BitMap + { + public const int IntSize = 64; + + private const int IntShift = 6; + private const int IntMask = IntSize - 1; + + /// + /// Masks representing the bitmap. Least significant bit first, 64-bits per mask. + /// + public readonly long[] Masks; + + /// + /// Create a new bitmap. + /// + /// The number of bits to reserve + public BitMap(int count) + { + Masks = new long[(count + IntMask) / IntSize]; + } + + /// + /// Check if any bit in the bitmap is set. + /// + /// True if any bits are set, false otherwise + public bool AnySet() + { + for (int i = 0; i < Masks.Length; i++) + { + if (Masks[i] != 0) + { + return true; + } + } + + return false; + } + + /// + /// Check if a bit in the bitmap is set. + /// + /// The bit index to check + /// True if the bit is set, false otherwise + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public bool IsSet(int bit) + { + int wordIndex = bit >> IntShift; + int wordBit = bit & IntMask; + + long wordMask = 1L << wordBit; + + return (Masks[wordIndex] & wordMask) != 0; + } + + /// + /// Check if any bit in a range of bits in the bitmap are set. (inclusive) + /// + /// The first bit index to check + /// The last bit index to check + /// True if a bit is set, false otherwise + public bool IsSet(int start, int end) + { + if (start == end) + { + return IsSet(start); + } + + int startIndex = start >> IntShift; + int startBit = start & IntMask; + long startMask = -1L << startBit; + + int endIndex = end >> IntShift; + int endBit = end & IntMask; + long endMask = (long)(ulong.MaxValue >> (IntMask - endBit)); + + if (startIndex == endIndex) + { + return (Masks[startIndex] & startMask & endMask) != 0; + } + + if ((Masks[startIndex] & startMask) != 0) + { + return true; + } + + for (int i = startIndex + 1; i < endIndex; i++) + { + if (Masks[i] != 0) + { + return true; + } + } + + if ((Masks[endIndex] & endMask) != 0) + { + return true; + } + + return false; + } + + /// + /// Set a bit at a specific index to 1. + /// + /// The bit index to set + /// True if the bit is set, false if it was already set + public bool Set(int bit) + { + int wordIndex = bit >> IntShift; + int wordBit = bit & IntMask; + + long wordMask = 1L << wordBit; + + if ((Masks[wordIndex] & wordMask) != 0) + { + return false; + } + + Masks[wordIndex] |= wordMask; + + return true; + } + + /// + /// Set a range of bits in the bitmap to 1. + /// + /// The first bit index to set + /// The last bit index to set + public void SetRange(int start, int end) + { + if (start == end) + { + Set(start); + return; + } + + int startIndex = start >> IntShift; + int startBit = start & IntMask; + long startMask = -1L << startBit; + + int endIndex = end >> IntShift; + int endBit = end & IntMask; + long endMask = (long)(ulong.MaxValue >> (IntMask - endBit)); + + if (startIndex == endIndex) + { + Masks[startIndex] |= startMask & endMask; + } + else + { + Masks[startIndex] |= startMask; + + for (int i = startIndex + 1; i < endIndex; i++) + { + Masks[i] |= -1; + } + + Masks[endIndex] |= endMask; + } + } + + /// + /// Clear a bit at a specific index to 0. + /// + /// The bit index to clear + /// True if the bit was set, false if it was not + public bool Clear(int bit) + { + int wordIndex = bit >> IntShift; + int wordBit = bit & IntMask; + + long wordMask = 1L << wordBit; + + bool wasSet = (Masks[wordIndex] & wordMask) != 0; + + Masks[wordIndex] &= ~wordMask; + + return wasSet; + } + + /// + /// Clear the bitmap entirely, setting all bits to 0. + /// + public void Clear() + { + for (int i = 0; i < Masks.Length; i++) + { + Masks[i] = 0; + } + } + } +} diff --git a/src/Ryujinx.Memory/Tracking/ConcurrentBitmap.cs b/src/Ryujinx.Memory/Tracking/ConcurrentBitmap.cs new file mode 100644 index 00000000..994fda92 --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/ConcurrentBitmap.cs @@ -0,0 +1,152 @@ +using System; +using System.Threading; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// A bitmap that can be safely modified from multiple threads. + /// + internal class ConcurrentBitmap + { + public const int IntSize = 64; + + public const int IntShift = 6; + public const int IntMask = IntSize - 1; + + /// + /// Masks representing the bitmap. Least significant bit first, 64-bits per mask. + /// + public readonly long[] Masks; + + /// + /// Create a new multithreaded bitmap. + /// + /// The number of bits to reserve + /// Whether the bits should be initially set or not + public ConcurrentBitmap(int count, bool set) + { + Masks = new long[(count + IntMask) / IntSize]; + + if (set) + { + Array.Fill(Masks, -1L); + } + } + + /// + /// Check if any bit in the bitmap is set. + /// + /// True if any bits are set, false otherwise + public bool AnySet() + { + for (int i = 0; i < Masks.Length; i++) + { + if (Interlocked.Read(ref Masks[i]) != 0) + { + return true; + } + } + + return false; + } + + /// + /// Check if a bit in the bitmap is set. + /// + /// The bit index to check + /// True if the bit is set, false otherwise + public bool IsSet(int bit) + { + int wordIndex = bit >> IntShift; + int wordBit = bit & IntMask; + + long wordMask = 1L << wordBit; + + return (Interlocked.Read(ref Masks[wordIndex]) & wordMask) != 0; + } + + /// + /// Check if any bit in a range of bits in the bitmap are set. (inclusive) + /// + /// The first bit index to check + /// The last bit index to check + /// True if a bit is set, false otherwise + public bool IsSet(int start, int end) + { + if (start == end) + { + return IsSet(start); + } + + int startIndex = start >> IntShift; + int startBit = start & IntMask; + long startMask = -1L << startBit; + + int endIndex = end >> IntShift; + int endBit = end & IntMask; + long endMask = (long)(ulong.MaxValue >> (IntMask - endBit)); + + long startValue = Interlocked.Read(ref Masks[startIndex]); + + if (startIndex == endIndex) + { + return (startValue & startMask & endMask) != 0; + } + + if ((startValue & startMask) != 0) + { + return true; + } + + for (int i = startIndex + 1; i < endIndex; i++) + { + if (Interlocked.Read(ref Masks[i]) != 0) + { + return true; + } + } + + long endValue = Interlocked.Read(ref Masks[endIndex]); + + if ((endValue & endMask) != 0) + { + return true; + } + + return false; + } + + /// + /// Set a bit at a specific index to either true or false. + /// + /// The bit index to set + /// Whether the bit should be set or not + public void Set(int bit, bool value) + { + int wordIndex = bit >> IntShift; + int wordBit = bit & IntMask; + + long wordMask = 1L << wordBit; + + if (value) + { + Interlocked.Or(ref Masks[wordIndex], wordMask); + } + else + { + Interlocked.And(ref Masks[wordIndex], ~wordMask); + } + } + + /// + /// Clear the bitmap entirely, setting all bits to 0. + /// + public void Clear() + { + for (int i = 0; i < Masks.Length; i++) + { + Interlocked.Exchange(ref Masks[i], 0); + } + } + } +} diff --git a/src/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs b/src/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs new file mode 100644 index 00000000..71bd602f --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs @@ -0,0 +1,55 @@ +using System; + +namespace Ryujinx.Memory.Tracking +{ + public interface IMultiRegionHandle : IDisposable + { + /// + /// True if any write has occurred to the whole region since the last use of QueryModified (with no subregion specified). + /// + bool Dirty { get; } + + /// + /// Force the range of handles to be dirty, without reprotecting. + /// + /// Start address of the range + /// Size of the range + public void ForceDirty(ulong address, ulong size); + + /// + /// Check if any part of the region has been modified, and perform an action for each. + /// Contiguous modified regions are combined. + /// + /// Action to perform for modified regions + void QueryModified(Action modifiedAction); + + + /// + /// Check if part of the region has been modified within a given range, and perform an action for each. + /// The range is aligned to the level of granularity of the contained handles. + /// Contiguous modified regions are combined. + /// + /// Start address of the range + /// Size of the range + /// Action to perform for modified regions + void QueryModified(ulong address, ulong size, Action modifiedAction); + + /// + /// Check if part of the region has been modified within a given range, and perform an action for each. + /// The sequence number provided is compared with each handle's saved sequence number. + /// If it is equal, then the handle's dirty flag is ignored. Otherwise, the sequence number is saved. + /// The range is aligned to the level of granularity of the contained handles. + /// Contiguous modified regions are combined. + /// + /// Start address of the range + /// Size of the range + /// Action to perform for modified regions + /// Current sequence number + void QueryModified(ulong address, ulong size, Action modifiedAction, int sequenceNumber); + + /// + /// Signal that one of the subregions of this multi-region has been modified. This sets the overall dirty flag. + /// + void SignalWrite(); + } +} diff --git a/src/Ryujinx.Memory/Tracking/IRegionHandle.cs b/src/Ryujinx.Memory/Tracking/IRegionHandle.cs new file mode 100644 index 00000000..9d99d90e --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/IRegionHandle.cs @@ -0,0 +1,18 @@ +using System; + +namespace Ryujinx.Memory.Tracking +{ + public interface IRegionHandle : IDisposable + { + bool Dirty { get; } + + ulong Address { get; } + ulong Size { get; } + ulong EndAddress { get; } + + void ForceDirty(); + void Reprotect(bool asDirty = false); + void RegisterAction(RegionSignal action); + void RegisterPreciseAction(PreciseRegionSignal action); + } +} diff --git a/src/Ryujinx.Memory/Tracking/MemoryTracking.cs b/src/Ryujinx.Memory/Tracking/MemoryTracking.cs new file mode 100644 index 00000000..bf1e0ad3 --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/MemoryTracking.cs @@ -0,0 +1,306 @@ +using Ryujinx.Common.Pools; +using Ryujinx.Memory.Range; +using System.Collections.Generic; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// Manages memory tracking for a given virutal/physical memory block. + /// + public class MemoryTracking + { + private readonly IVirtualMemoryManager _memoryManager; + private readonly InvalidAccessHandler _invalidAccessHandler; + + // Only use these from within the lock. + private readonly NonOverlappingRangeList _virtualRegions; + + private readonly int _pageSize; + + /// + /// This lock must be obtained when traversing or updating the region-handle hierarchy. + /// It is not required when reading dirty flags. + /// + internal object TrackingLock = new object(); + + /// + /// Create a new tracking structure for the given "physical" memory block, + /// with a given "virtual" memory manager that will provide mappings and virtual memory protection. + /// + /// Virtual memory manager + /// Physical memory block + /// Page size of the virtual memory space + public MemoryTracking(IVirtualMemoryManager memoryManager, int pageSize, InvalidAccessHandler invalidAccessHandler = null) + { + _memoryManager = memoryManager; + _pageSize = pageSize; + _invalidAccessHandler = invalidAccessHandler; + + _virtualRegions = new NonOverlappingRangeList(); + } + + private (ulong address, ulong size) PageAlign(ulong address, ulong size) + { + ulong pageMask = (ulong)_pageSize - 1; + ulong rA = address & ~pageMask; + ulong rS = ((address + size + pageMask) & ~pageMask) - rA; + return (rA, rS); + } + + /// + /// Indicate that a virtual region has been mapped, and which physical region it has been mapped to. + /// Should be called after the mapping is complete. + /// + /// Virtual memory address + /// Size to be mapped + public void Map(ulong va, ulong size) + { + // A mapping may mean we need to re-evaluate each VirtualRegion's affected area. + // Find all handles that overlap with the range, we need to recalculate their physical regions + + lock (TrackingLock) + { + ref var overlaps = ref ThreadStaticArray.Get(); + + int count = _virtualRegions.FindOverlapsNonOverlapping(va, size, ref overlaps); + + for (int i = 0; i < count; i++) + { + VirtualRegion region = overlaps[i]; + + // If the region has been fully remapped, signal that it has been mapped again. + bool remapped = _memoryManager.IsRangeMapped(region.Address, region.Size); + if (remapped) + { + region.SignalMappingChanged(true); + } + + region.UpdateProtection(); + } + } + } + + /// + /// Indicate that a virtual region has been unmapped. + /// Should be called before the unmapping is complete. + /// + /// Virtual memory address + /// Size to be unmapped + public void Unmap(ulong va, ulong size) + { + // An unmapping may mean we need to re-evaluate each VirtualRegion's affected area. + // Find all handles that overlap with the range, we need to notify them that the region was unmapped. + + lock (TrackingLock) + { + ref var overlaps = ref ThreadStaticArray.Get(); + + int count = _virtualRegions.FindOverlapsNonOverlapping(va, size, ref overlaps); + + for (int i = 0; i < count; i++) + { + VirtualRegion region = overlaps[i]; + + region.SignalMappingChanged(false); + } + } + } + + /// + /// Get a list of virtual regions that a handle covers. + /// + /// Starting virtual memory address of the handle + /// Size of the handle's memory region + /// A list of virtual regions within the given range + internal List GetVirtualRegionsForHandle(ulong va, ulong size) + { + List result = new List(); + _virtualRegions.GetOrAddRegions(result, va, size, (va, size) => new VirtualRegion(this, va, size)); + + return result; + } + + /// + /// Remove a virtual region from the range list. This assumes that the lock has been acquired. + /// + /// Region to remove + internal void RemoveVirtual(VirtualRegion region) + { + _virtualRegions.Remove(region); + } + + /// + /// Obtains a memory tracking handle for the given virtual region, with a specified granularity. This should be disposed when finished with. + /// + /// CPU virtual address of the region + /// Size of the region + /// Handles to inherit state from or reuse. When none are present, provide null + /// Desired granularity of write tracking + /// Handle ID + /// The memory tracking handle + public MultiRegionHandle BeginGranularTracking(ulong address, ulong size, IEnumerable handles, ulong granularity, int id) + { + return new MultiRegionHandle(this, address, size, handles, granularity, id); + } + + /// + /// Obtains a smart memory tracking handle for the given virtual region, with a specified granularity. This should be disposed when finished with. + /// + /// CPU virtual address of the region + /// Size of the region + /// Desired granularity of write tracking + /// Handle ID + /// The memory tracking handle + public SmartMultiRegionHandle BeginSmartGranularTracking(ulong address, ulong size, ulong granularity, int id) + { + (address, size) = PageAlign(address, size); + + return new SmartMultiRegionHandle(this, address, size, granularity, id); + } + + /// + /// Obtains a memory tracking handle for the given virtual region. This should be disposed when finished with. + /// + /// CPU virtual address of the region + /// Size of the region + /// Handle ID + /// The memory tracking handle + public RegionHandle BeginTracking(ulong address, ulong size, int id) + { + var (paAddress, paSize) = PageAlign(address, size); + + lock (TrackingLock) + { + bool mapped = _memoryManager.IsRangeMapped(address, size); + RegionHandle handle = new RegionHandle(this, paAddress, paSize, address, size, id, mapped); + + return handle; + } + } + + /// + /// Obtains a memory tracking handle for the given virtual region. This should be disposed when finished with. + /// + /// CPU virtual address of the region + /// Size of the region + /// The bitmap owning the dirty flag for this handle + /// The bit of this handle within the dirty flag + /// Handle ID + /// The memory tracking handle + internal RegionHandle BeginTrackingBitmap(ulong address, ulong size, ConcurrentBitmap bitmap, int bit, int id) + { + var (paAddress, paSize) = PageAlign(address, size); + + lock (TrackingLock) + { + bool mapped = _memoryManager.IsRangeMapped(address, size); + RegionHandle handle = new RegionHandle(this, paAddress, paSize, address, size, bitmap, bit, id, mapped); + + return handle; + } + } + + /// + /// Signal that a virtual memory event happened at the given location. + /// + /// Virtual address accessed + /// Size of the region affected in bytes + /// Whether the region was written to or read + /// True if the event triggered any tracking regions, false otherwise + public bool VirtualMemoryEvent(ulong address, ulong size, bool write) + { + return VirtualMemoryEvent(address, size, write, precise: false, null); + } + + /// + /// Signal that a virtual memory event happened at the given location. + /// This can be flagged as a precise event, which will avoid reprotection and call special handlers if possible. + /// A precise event has an exact address and size, rather than triggering on page granularity. + /// + /// Virtual address accessed + /// Size of the region affected in bytes + /// Whether the region was written to or read + /// True if the access is precise, false otherwise + /// Optional ID that of the handles that should not be signalled + /// True if the event triggered any tracking regions, false otherwise + public bool VirtualMemoryEvent(ulong address, ulong size, bool write, bool precise, int? exemptId = null) + { + // Look up the virtual region using the region list. + // Signal up the chain to relevant handles. + + bool shouldThrow = false; + + lock (TrackingLock) + { + ref var overlaps = ref ThreadStaticArray.Get(); + + int count = _virtualRegions.FindOverlapsNonOverlapping(address, size, ref overlaps); + + if (count == 0 && !precise) + { + if (_memoryManager.IsRangeMapped(address, size)) + { + // TODO: There is currently the possibility that a page can be protected after its virtual region is removed. + // This code handles that case when it happens, but it would be better to find out how this happens. + _memoryManager.TrackingReprotect(address & ~(ulong)(_pageSize - 1), (ulong)_pageSize, MemoryPermission.ReadAndWrite); + return true; // This memory _should_ be mapped, so we need to try again. + } + else + { + shouldThrow = true; + } + } + else + { + for (int i = 0; i < count; i++) + { + VirtualRegion region = overlaps[i]; + + if (precise) + { + region.SignalPrecise(address, size, write, exemptId); + } + else + { + region.Signal(address, size, write, exemptId); + } + } + } + } + + if (shouldThrow) + { + _invalidAccessHandler?.Invoke(address); + + // We can't continue - it's impossible to remove protection from the page. + // Even if the access handler wants us to continue, we wouldn't be able to. + throw new InvalidMemoryRegionException(); + } + + return true; + } + + /// + /// Reprotect a given virtual region. The virtual memory manager will handle this. + /// + /// Region to reprotect + /// Memory permission to protect with + internal void ProtectVirtualRegion(VirtualRegion region, MemoryPermission permission) + { + _memoryManager.TrackingReprotect(region.Address, region.Size, permission); + } + + /// + /// Returns the number of virtual regions currently being tracked. + /// Useful for tests and metrics. + /// + /// The number of virtual regions + public int GetRegionCount() + { + lock (TrackingLock) + { + return _virtualRegions.Count; + } + } + } +} diff --git a/src/Ryujinx.Memory/Tracking/MultiRegionHandle.cs b/src/Ryujinx.Memory/Tracking/MultiRegionHandle.cs new file mode 100644 index 00000000..68fc5e75 --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/MultiRegionHandle.cs @@ -0,0 +1,415 @@ +using System; +using System.Collections.Generic; +using System.Numerics; +using System.Runtime.CompilerServices; +using System.Threading; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// A region handle that tracks a large region using many smaller handles, to provide + /// granular tracking that can be used to track partial updates. Backed by a bitmap + /// to improve performance when scanning large regions. + /// + public class MultiRegionHandle : IMultiRegionHandle + { + /// + /// A list of region handles for each granularity sized chunk of the whole region. + /// + private readonly RegionHandle[] _handles; + private readonly ulong Address; + private readonly ulong Granularity; + private readonly ulong Size; + + private ConcurrentBitmap _dirtyBitmap; + + private int _sequenceNumber; + private BitMap _sequenceNumberBitmap; + private BitMap _dirtyCheckedBitmap; + private int _uncheckedHandles; + + public bool Dirty { get; private set; } = true; + + internal MultiRegionHandle( + MemoryTracking tracking, + ulong address, + ulong size, + IEnumerable handles, + ulong granularity, + int id) + { + _handles = new RegionHandle[(size + granularity - 1) / granularity]; + Granularity = granularity; + + _dirtyBitmap = new ConcurrentBitmap(_handles.Length, true); + _sequenceNumberBitmap = new BitMap(_handles.Length); + _dirtyCheckedBitmap = new BitMap(_handles.Length); + + int i = 0; + + if (handles != null) + { + // Inherit from the handles we were given. Any gaps must be filled with new handles, + // and old handles larger than our granularity must copy their state onto new granular handles and dispose. + // It is assumed that the provided handles do not overlap, in order, are on page boundaries, + // and don't extend past the requested range. + + foreach (RegionHandle handle in handles) + { + int startIndex = (int)((handle.RealAddress - address) / granularity); + + // Fill any gap left before this handle. + while (i < startIndex) + { + RegionHandle fillHandle = tracking.BeginTrackingBitmap(address + (ulong)i * granularity, granularity, _dirtyBitmap, i, id); + fillHandle.Parent = this; + _handles[i++] = fillHandle; + } + + lock (tracking.TrackingLock) + { + if (handle is RegionHandle bitHandle && handle.Size == granularity) + { + handle.Parent = this; + + bitHandle.ReplaceBitmap(_dirtyBitmap, i); + + _handles[i++] = bitHandle; + } + else + { + int endIndex = (int)((handle.RealEndAddress - address) / granularity); + + while (i < endIndex) + { + RegionHandle splitHandle = tracking.BeginTrackingBitmap(address + (ulong)i * granularity, granularity, _dirtyBitmap, i, id); + splitHandle.Parent = this; + + splitHandle.Reprotect(handle.Dirty); + + RegionSignal signal = handle.PreAction; + if (signal != null) + { + splitHandle.RegisterAction(signal); + } + + _handles[i++] = splitHandle; + } + + handle.Dispose(); + } + } + } + } + + // Fill any remaining space with new handles. + while (i < _handles.Length) + { + RegionHandle handle = tracking.BeginTrackingBitmap(address + (ulong)i * granularity, granularity, _dirtyBitmap, i, id); + handle.Parent = this; + _handles[i++] = handle; + } + + _uncheckedHandles = _handles.Length; + + Address = address; + Size = size; + } + + public void SignalWrite() + { + Dirty = true; + } + + public IEnumerable GetHandles() + { + return _handles; + } + + public void ForceDirty(ulong address, ulong size) + { + Dirty = true; + + int startHandle = (int)((address - Address) / Granularity); + int lastHandle = (int)((address + (size - 1) - Address) / Granularity); + + for (int i = startHandle; i <= lastHandle; i++) + { + if (_sequenceNumberBitmap.Clear(i)) + { + _uncheckedHandles++; + } + + _handles[i].ForceDirty(); + } + } + + public void QueryModified(Action modifiedAction) + { + if (!Dirty) + { + return; + } + + Dirty = false; + + QueryModified(Address, Size, modifiedAction); + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private void ParseDirtyBits(long dirtyBits, ref int baseBit, ref int prevHandle, ref ulong rgStart, ref ulong rgSize, Action modifiedAction) + { + while (dirtyBits != 0) + { + int bit = BitOperations.TrailingZeroCount(dirtyBits); + + dirtyBits &= ~(1L << bit); + + int handleIndex = baseBit + bit; + + RegionHandle handle = _handles[handleIndex]; + + if (handleIndex != prevHandle + 1) + { + // Submit handles scanned until the gap as dirty + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + rgSize = 0; + } + + rgStart = handle.RealAddress; + } + + if (handle.Dirty) + { + rgSize += handle.RealSize; + handle.Reprotect(); + } + + prevHandle = handleIndex; + } + + baseBit += ConcurrentBitmap.IntSize; + } + + public void QueryModified(ulong address, ulong size, Action modifiedAction) + { + int startHandle = (int)((address - Address) / Granularity); + int lastHandle = (int)((address + (size - 1) - Address) / Granularity); + + ulong rgStart = Address + (ulong)startHandle * Granularity; + + if (startHandle == lastHandle) + { + RegionHandle handle = _handles[startHandle]; + + if (handle.Dirty) + { + handle.Reprotect(); + modifiedAction(rgStart, handle.RealSize); + } + + return; + } + + ulong rgSize = 0; + + long[] masks = _dirtyBitmap.Masks; + + int startIndex = startHandle >> ConcurrentBitmap.IntShift; + int startBit = startHandle & ConcurrentBitmap.IntMask; + long startMask = -1L << startBit; + + int endIndex = lastHandle >> ConcurrentBitmap.IntShift; + int endBit = lastHandle & ConcurrentBitmap.IntMask; + long endMask = (long)(ulong.MaxValue >> (ConcurrentBitmap.IntMask - endBit)); + + long startValue = Volatile.Read(ref masks[startIndex]); + + int baseBit = startIndex << ConcurrentBitmap.IntShift; + int prevHandle = startHandle - 1; + + if (startIndex == endIndex) + { + ParseDirtyBits(startValue & startMask & endMask, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + } + else + { + ParseDirtyBits(startValue & startMask, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + + for (int i = startIndex + 1; i < endIndex; i++) + { + ParseDirtyBits(Volatile.Read(ref masks[i]), ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + } + + long endValue = Volatile.Read(ref masks[endIndex]); + + ParseDirtyBits(endValue & endMask, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + } + + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + } + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private void ParseDirtyBits(long dirtyBits, long mask, int index, long[] seqMasks, long[] checkMasks, ref int baseBit, ref int prevHandle, ref ulong rgStart, ref ulong rgSize, Action modifiedAction) + { + long seqMask = mask & ~seqMasks[index]; + long checkMask = (~dirtyBits) & seqMask; + dirtyBits &= seqMask; + + while (dirtyBits != 0) + { + int bit = BitOperations.TrailingZeroCount(dirtyBits); + long bitValue = 1L << bit; + + dirtyBits &= ~bitValue; + + int handleIndex = baseBit + bit; + + RegionHandle handle = _handles[handleIndex]; + + if (handleIndex != prevHandle + 1) + { + // Submit handles scanned until the gap as dirty + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + rgSize = 0; + } + rgStart = handle.RealAddress; + } + + rgSize += handle.RealSize; + handle.Reprotect(false, (checkMasks[index] & bitValue) == 0); + + checkMasks[index] &= ~bitValue; + + prevHandle = handleIndex; + } + + checkMasks[index] |= checkMask; + seqMasks[index] |= mask; + _uncheckedHandles -= BitOperations.PopCount((ulong)seqMask); + + baseBit += ConcurrentBitmap.IntSize; + } + + public void QueryModified(ulong address, ulong size, Action modifiedAction, int sequenceNumber) + { + int startHandle = (int)((address - Address) / Granularity); + int lastHandle = (int)((address + (size - 1) - Address) / Granularity); + + ulong rgStart = Address + (ulong)startHandle * Granularity; + + if (sequenceNumber != _sequenceNumber) + { + if (_uncheckedHandles != _handles.Length) + { + _sequenceNumberBitmap.Clear(); + _uncheckedHandles = _handles.Length; + } + + _sequenceNumber = sequenceNumber; + } + + if (startHandle == lastHandle) + { + var handle = _handles[startHandle]; + if (_sequenceNumberBitmap.Set(startHandle)) + { + _uncheckedHandles--; + + if (handle.DirtyOrVolatile()) + { + handle.Reprotect(); + + modifiedAction(rgStart, handle.RealSize); + } + } + + return; + } + + if (_uncheckedHandles == 0) + { + return; + } + + ulong rgSize = 0; + + long[] seqMasks = _sequenceNumberBitmap.Masks; + long[] checkedMasks = _dirtyCheckedBitmap.Masks; + long[] masks = _dirtyBitmap.Masks; + + int startIndex = startHandle >> ConcurrentBitmap.IntShift; + int startBit = startHandle & ConcurrentBitmap.IntMask; + long startMask = -1L << startBit; + + int endIndex = lastHandle >> ConcurrentBitmap.IntShift; + int endBit = lastHandle & ConcurrentBitmap.IntMask; + long endMask = (long)(ulong.MaxValue >> (ConcurrentBitmap.IntMask - endBit)); + + long startValue = Volatile.Read(ref masks[startIndex]); + + int baseBit = startIndex << ConcurrentBitmap.IntShift; + int prevHandle = startHandle - 1; + + if (startIndex == endIndex) + { + ParseDirtyBits(startValue, startMask & endMask, startIndex, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + } + else + { + ParseDirtyBits(startValue, startMask, startIndex, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + + for (int i = startIndex + 1; i < endIndex; i++) + { + ParseDirtyBits(Volatile.Read(ref masks[i]), -1L, i, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + } + + long endValue = Volatile.Read(ref masks[endIndex]); + + ParseDirtyBits(endValue, endMask, endIndex, seqMasks, checkedMasks, ref baseBit, ref prevHandle, ref rgStart, ref rgSize, modifiedAction); + } + + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + } + } + + public void RegisterAction(ulong address, ulong size, RegionSignal action) + { + int startHandle = (int)((address - Address) / Granularity); + int lastHandle = (int)((address + (size - 1) - Address) / Granularity); + + for (int i = startHandle; i <= lastHandle; i++) + { + _handles[i].RegisterAction(action); + } + } + + public void RegisterPreciseAction(ulong address, ulong size, PreciseRegionSignal action) + { + int startHandle = (int)((address - Address) / Granularity); + int lastHandle = (int)((address + (size - 1) - Address) / Granularity); + + for (int i = startHandle; i <= lastHandle; i++) + { + _handles[i].RegisterPreciseAction(action); + } + } + + public void Dispose() + { + foreach (var handle in _handles) + { + handle.Dispose(); + } + } + } +} diff --git a/src/Ryujinx.Memory/Tracking/PreciseRegionSignal.cs b/src/Ryujinx.Memory/Tracking/PreciseRegionSignal.cs new file mode 100644 index 00000000..038f9595 --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/PreciseRegionSignal.cs @@ -0,0 +1,4 @@ +namespace Ryujinx.Memory.Tracking +{ + public delegate bool PreciseRegionSignal(ulong address, ulong size, bool write); +} diff --git a/src/Ryujinx.Memory/Tracking/RegionHandle.cs b/src/Ryujinx.Memory/Tracking/RegionHandle.cs new file mode 100644 index 00000000..7a59f9f2 --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/RegionHandle.cs @@ -0,0 +1,464 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Threading; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// A tracking handle for a given region of virtual memory. The Dirty flag is updated whenever any changes are made, + /// and an action can be performed when the region is read to or written from. + /// + public class RegionHandle : IRegionHandle + { + /// + /// If more than this number of checks have been performed on a dirty flag since its last reprotect, + /// then it is dirtied infrequently. + /// + private const int CheckCountForInfrequent = 3; + + /// + /// Number of frequent dirty/consume in a row to make this handle volatile. + /// + private const int VolatileThreshold = 5; + + public bool Dirty + { + get + { + return Bitmap.IsSet(DirtyBit); + } + protected set + { + Bitmap.Set(DirtyBit, value); + } + } + + internal int SequenceNumber { get; set; } + internal int Id { get; } + + public bool Unmapped { get; private set; } + + public ulong Address { get; } + public ulong Size { get; } + public ulong EndAddress { get; } + + public ulong RealAddress { get; } + public ulong RealSize { get; } + public ulong RealEndAddress { get; } + + internal IMultiRegionHandle Parent { get; set; } + + private event Action _onDirty; + + private object _preActionLock = new object(); + private RegionSignal _preAction; // Action to perform before a read or write. This will block the memory access. + private PreciseRegionSignal _preciseAction; // Action to perform on a precise read or write. + private readonly List _regions; + private readonly MemoryTracking _tracking; + private bool _disposed; + + private int _checkCount = 0; + private int _volatileCount = 0; + private bool _volatile; + + internal MemoryPermission RequiredPermission + { + get + { + // If this is unmapped, allow reprotecting as RW as it can't be dirtied. + // This is required for the partial unmap cases where part of the data are still being accessed. + if (Unmapped) + { + return MemoryPermission.ReadAndWrite; + } + + if (_preAction != null) + { + return MemoryPermission.None; + } + + return Dirty ? MemoryPermission.ReadAndWrite : MemoryPermission.Read; + } + } + + internal RegionSignal PreAction => _preAction; + + internal ConcurrentBitmap Bitmap; + internal int DirtyBit; + + /// + /// Create a new bitmap backed region handle. The handle is registered with the given tracking object, + /// and will be notified of any changes to the specified region. + /// + /// Tracking object for the target memory block + /// Virtual address of the region to track + /// Size of the region to track + /// The real, unaligned address of the handle + /// The real, unaligned size of the handle + /// The bitmap the dirty flag for this handle is stored in + /// The bit index representing the dirty flag for this handle + /// Handle ID + /// True if the region handle starts mapped + internal RegionHandle( + MemoryTracking tracking, + ulong address, + ulong size, + ulong realAddress, + ulong realSize, + ConcurrentBitmap bitmap, + int bit, + int id, + bool mapped = true) + { + Bitmap = bitmap; + DirtyBit = bit; + + Dirty = mapped; + + Id = id; + + Unmapped = !mapped; + Address = address; + Size = size; + EndAddress = address + size; + + RealAddress = realAddress; + RealSize = realSize; + RealEndAddress = realAddress + realSize; + + _tracking = tracking; + _regions = tracking.GetVirtualRegionsForHandle(address, size); + foreach (var region in _regions) + { + region.Handles.Add(this); + } + } + + /// + /// Create a new region handle. The handle is registered with the given tracking object, + /// and will be notified of any changes to the specified region. + /// + /// Tracking object for the target memory block + /// Virtual address of the region to track + /// Size of the region to track + /// The real, unaligned address of the handle + /// The real, unaligned size of the handle + /// Handle ID + /// True if the region handle starts mapped + internal RegionHandle(MemoryTracking tracking, ulong address, ulong size, ulong realAddress, ulong realSize, int id, bool mapped = true) + { + Bitmap = new ConcurrentBitmap(1, mapped); + + Id = id; + + Unmapped = !mapped; + + Address = address; + Size = size; + EndAddress = address + size; + + RealAddress = realAddress; + RealSize = realSize; + RealEndAddress = realAddress + realSize; + + _tracking = tracking; + _regions = tracking.GetVirtualRegionsForHandle(address, size); + foreach (var region in _regions) + { + region.Handles.Add(this); + } + } + + /// + /// Replace the bitmap and bit index used to track dirty state. + /// + /// + /// The tracking lock should be held when this is called, to ensure neither bitmap is modified. + /// + /// The bitmap the dirty flag for this handle is stored in + /// The bit index representing the dirty flag for this handle + internal void ReplaceBitmap(ConcurrentBitmap bitmap, int bit) + { + // Assumes the tracking lock is held, so nothing else can signal right now. + + var oldBitmap = Bitmap; + var oldBit = DirtyBit; + + bitmap.Set(bit, Dirty); + + Bitmap = bitmap; + DirtyBit = bit; + + Dirty |= oldBitmap.IsSet(oldBit); + } + + /// + /// Clear the volatile state of this handle. + /// + private void ClearVolatile() + { + _volatileCount = 0; + _volatile = false; + } + + /// + /// Check if this handle is dirty, or if it is volatile. (changes very often) + /// + /// True if the handle is dirty or volatile, false otherwise + public bool DirtyOrVolatile() + { + _checkCount++; + return _volatile || Dirty; + } + + /// + /// Signal that a memory action occurred within this handle's virtual regions. + /// + /// Address accessed + /// Size of the region affected in bytes + /// Whether the region was written to or read + /// Reference to the handles being iterated, in case the list needs to be copied + internal void Signal(ulong address, ulong size, bool write, ref IList handleIterable) + { + // If this handle was already unmapped (even if just partially), + // then we have nothing to do until it is mapped again. + // The pre-action should be still consumed to avoid flushing on remap. + if (Unmapped) + { + Interlocked.Exchange(ref _preAction, null); + return; + } + + if (_preAction != null) + { + // Limit the range to within this handle. + ulong maxAddress = Math.Max(address, RealAddress); + ulong minEndAddress = Math.Min(address + size, RealAddress + RealSize); + + // Copy the handles list in case it changes when we're out of the lock. + if (handleIterable is List) + { + handleIterable = handleIterable.ToArray(); + } + + // Temporarily release the tracking lock while we're running the action. + Monitor.Exit(_tracking.TrackingLock); + + try + { + lock (_preActionLock) + { + _preAction?.Invoke(maxAddress, minEndAddress - maxAddress); + + // The action is removed after it returns, to ensure that the null check above succeeds when + // it's still in progress rather than continuing and possibly missing a required data flush. + Interlocked.Exchange(ref _preAction, null); + } + } + finally + { + Monitor.Enter(_tracking.TrackingLock); + } + } + + if (write) + { + bool oldDirty = Dirty; + Dirty = true; + if (!oldDirty) + { + _onDirty?.Invoke(); + } + Parent?.SignalWrite(); + } + } + + /// + /// Signal that a precise memory action occurred within this handle's virtual regions. + /// If there is no precise action, or the action returns false, the normal signal handler will be called. + /// + /// Address accessed + /// Size of the region affected in bytes + /// Whether the region was written to or read + /// Reference to the handles being iterated, in case the list needs to be copied + /// True if a precise action was performed and returned true, false otherwise + internal bool SignalPrecise(ulong address, ulong size, bool write, ref IList handleIterable) + { + if (!Unmapped && _preciseAction != null && _preciseAction(address, size, write)) + { + return true; + } + + Signal(address, size, write, ref handleIterable); + + return false; + } + + /// + /// Force this handle to be dirty, without reprotecting. + /// + public void ForceDirty() + { + Dirty = true; + } + + /// + /// Consume the dirty flag for this handle, and reprotect so it can be set on the next write. + /// + /// True if the handle should be reprotected as dirty, rather than have it cleared + /// True if this reprotect is the result of consecutive dirty checks + public void Reprotect(bool asDirty, bool consecutiveCheck = false) + { + if (_volatile) return; + + Dirty = asDirty; + + bool protectionChanged = false; + + lock (_tracking.TrackingLock) + { + foreach (VirtualRegion region in _regions) + { + protectionChanged |= region.UpdateProtection(); + } + } + + if (!protectionChanged) + { + // Counteract the check count being incremented when this handle was forced dirty. + // It doesn't count for protected write tracking. + + _checkCount--; + } + else if (!asDirty) + { + if (consecutiveCheck || (_checkCount > 0 && _checkCount < CheckCountForInfrequent)) + { + if (++_volatileCount >= VolatileThreshold && _preAction == null) + { + _volatile = true; + return; + } + } + else + { + _volatileCount = 0; + } + + _checkCount = 0; + } + } + + /// + /// Consume the dirty flag for this handle, and reprotect so it can be set on the next write. + /// + /// True if the handle should be reprotected as dirty, rather than have it cleared + public void Reprotect(bool asDirty = false) + { + Reprotect(asDirty, false); + } + + /// + /// Register an action to perform when the tracked region is read or written. + /// The action is automatically removed after it runs. + /// + /// Action to call on read or write + public void RegisterAction(RegionSignal action) + { + ClearVolatile(); + + lock (_preActionLock) + { + RegionSignal lastAction = Interlocked.Exchange(ref _preAction, action); + + if (lastAction == null && action != lastAction) + { + lock (_tracking.TrackingLock) + { + foreach (VirtualRegion region in _regions) + { + region.UpdateProtection(); + } + } + } + } + } + + /// + /// Register an action to perform when a precise access occurs (one with exact address and size). + /// If the action returns true, read/write tracking are skipped. + /// + /// Action to call on read or write + public void RegisterPreciseAction(PreciseRegionSignal action) + { + _preciseAction = action; + } + + /// + /// Register an action to perform when the region is written to. + /// This action will not be removed when it is called - it is called each time the dirty flag is set. + /// + /// Action to call on dirty + public void RegisterDirtyEvent(Action action) + { + _onDirty += action; + } + + /// + /// Add a child virtual region to this handle. + /// + /// Virtual region to add as a child + internal void AddChild(VirtualRegion region) + { + _regions.Add(region); + } + + /// + /// Signal that this handle has been mapped or unmapped. + /// + /// True if the handle has been mapped, false if unmapped + internal void SignalMappingChanged(bool mapped) + { + if (Unmapped == mapped) + { + Unmapped = !mapped; + + if (Unmapped) + { + ClearVolatile(); + Dirty = false; + } + } + } + + /// + /// Check if this region overlaps with another. + /// + /// Base address + /// Size of the region + /// True if overlapping, false otherwise + public bool OverlapsWith(ulong address, ulong size) + { + return Address < address + size && address < EndAddress; + } + + /// + /// Dispose the handle. Within the tracking lock, this removes references from virtual regions. + /// + public void Dispose() + { + ObjectDisposedException.ThrowIf(_disposed, this); + + _disposed = true; + + lock (_tracking.TrackingLock) + { + foreach (VirtualRegion region in _regions) + { + region.RemoveHandle(this); + } + } + } + } +} diff --git a/src/Ryujinx.Memory/Tracking/RegionSignal.cs b/src/Ryujinx.Memory/Tracking/RegionSignal.cs new file mode 100644 index 00000000..c8a28d7d --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/RegionSignal.cs @@ -0,0 +1,4 @@ +namespace Ryujinx.Memory.Tracking +{ + public delegate void RegionSignal(ulong address, ulong size); +} diff --git a/src/Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs b/src/Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs new file mode 100644 index 00000000..4acddefa --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs @@ -0,0 +1,280 @@ +using System; +using System.Runtime.CompilerServices; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// A MultiRegionHandle that attempts to segment a region's handles into the regions requested + /// to avoid iterating over granular chunks for canonically large regions. + /// If minimum granularity is to be expected, use MultiRegionHandle. + /// + public class SmartMultiRegionHandle : IMultiRegionHandle + { + /// + /// A list of region handles starting at each granularity size increment. + /// + private readonly RegionHandle[] _handles; + private readonly ulong _address; + private readonly ulong _granularity; + private readonly ulong _size; + private MemoryTracking _tracking; + private readonly int _id; + + public bool Dirty { get; private set; } = true; + + internal SmartMultiRegionHandle(MemoryTracking tracking, ulong address, ulong size, ulong granularity, int id) + { + // For this multi-region handle, the handle list starts empty. + // As regions are queried, they are added to the _handles array at their start index. + // When a region being added overlaps another, the existing region is split. + // A query can therefore scan multiple regions, though with no overlaps they can cover a large area. + + _tracking = tracking; + _handles = new RegionHandle[size / granularity]; + _granularity = granularity; + + _address = address; + _size = size; + _id = id; + } + + public void SignalWrite() + { + Dirty = true; + } + + public void ForceDirty(ulong address, ulong size) + { + foreach (var handle in _handles) + { + if (handle != null && handle.OverlapsWith(address, size)) + { + handle.ForceDirty(); + } + } + } + + public void RegisterAction(RegionSignal action) + { + foreach (var handle in _handles) + { + if (handle != null) + { + handle?.RegisterAction((address, size) => action(handle.Address, handle.Size)); + } + } + } + + public void RegisterPreciseAction(PreciseRegionSignal action) + { + foreach (var handle in _handles) + { + if (handle != null) + { + handle?.RegisterPreciseAction((address, size, write) => action(handle.Address, handle.Size, write)); + } + } + } + + public void QueryModified(Action modifiedAction) + { + if (!Dirty) + { + return; + } + + Dirty = false; + + QueryModified(_address, _size, modifiedAction); + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private ulong HandlesToBytes(int handles) + { + return (ulong)handles * _granularity; + } + + private void SplitHandle(int handleIndex, int splitIndex) + { + RegionHandle handle = _handles[handleIndex]; + ulong address = _address + HandlesToBytes(handleIndex); + ulong size = HandlesToBytes(splitIndex - handleIndex); + + // First, the target handle must be removed. Its data can still be used to determine the new handles. + RegionSignal signal = handle.PreAction; + handle.Dispose(); + + RegionHandle splitLow = _tracking.BeginTracking(address, size, _id); + splitLow.Parent = this; + if (signal != null) + { + splitLow.RegisterAction(signal); + } + _handles[handleIndex] = splitLow; + + RegionHandle splitHigh = _tracking.BeginTracking(address + size, handle.Size - size, _id); + splitHigh.Parent = this; + if (signal != null) + { + splitHigh.RegisterAction(signal); + } + _handles[splitIndex] = splitHigh; + } + + private void CreateHandle(int startHandle, int lastHandle) + { + ulong startAddress = _address + HandlesToBytes(startHandle); + + // Scan for the first handle before us. If it's overlapping us, it must be split. + for (int i = startHandle - 1; i >= 0; i--) + { + RegionHandle handle = _handles[i]; + if (handle != null) + { + if (handle.EndAddress > startAddress) + { + SplitHandle(i, startHandle); + return; // The remainer of this handle should be filled in later on. + } + break; + } + } + + // Scan for handles after us. We should create a handle that goes up to this handle's start point, if present. + for (int i = startHandle + 1; i <= lastHandle; i++) + { + RegionHandle handle = _handles[i]; + if (handle != null) + { + // Fill up to the found handle. + handle = _tracking.BeginTracking(startAddress, HandlesToBytes(i - startHandle), _id); + handle.Parent = this; + _handles[startHandle] = handle; + return; + } + } + + // Can fill the whole range. + _handles[startHandle] = _tracking.BeginTracking(startAddress, HandlesToBytes(1 + lastHandle - startHandle), _id); + _handles[startHandle].Parent = this; + } + + public void QueryModified(ulong address, ulong size, Action modifiedAction) + { + int startHandle = (int)((address - _address) / _granularity); + int lastHandle = (int)((address + (size - 1) - _address) / _granularity); + + ulong rgStart = _address + (ulong)startHandle * _granularity; + ulong rgSize = 0; + + ulong endAddress = _address + ((ulong)lastHandle + 1) * _granularity; + + int i = startHandle; + + while (i <= lastHandle) + { + RegionHandle handle = _handles[i]; + if (handle == null) + { + // Missing handle. A new handle must be created. + CreateHandle(i, lastHandle); + handle = _handles[i]; + } + + if (handle.EndAddress > endAddress) + { + // End address of handle is beyond the end of the search. Force a split. + SplitHandle(i, lastHandle + 1); + handle = _handles[i]; + } + + if (handle.Dirty) + { + rgSize += handle.Size; + handle.Reprotect(); + } + else + { + // Submit the region scanned so far as dirty + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + rgSize = 0; + } + rgStart = handle.EndAddress; + } + + i += (int)(handle.Size / _granularity); + } + + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + } + } + + public void QueryModified(ulong address, ulong size, Action modifiedAction, int sequenceNumber) + { + int startHandle = (int)((address - _address) / _granularity); + int lastHandle = (int)((address + (size - 1) - _address) / _granularity); + + ulong rgStart = _address + (ulong)startHandle * _granularity; + ulong rgSize = 0; + + ulong endAddress = _address + ((ulong)lastHandle + 1) * _granularity; + + int i = startHandle; + + while (i <= lastHandle) + { + RegionHandle handle = _handles[i]; + if (handle == null) + { + // Missing handle. A new handle must be created. + CreateHandle(i, lastHandle); + handle = _handles[i]; + } + + if (handle.EndAddress > endAddress) + { + // End address of handle is beyond the end of the search. Force a split. + SplitHandle(i, lastHandle + 1); + handle = _handles[i]; + } + + if (handle.Dirty && sequenceNumber != handle.SequenceNumber) + { + rgSize += handle.Size; + handle.Reprotect(); + } + else + { + // Submit the region scanned so far as dirty + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + rgSize = 0; + } + rgStart = handle.EndAddress; + } + + handle.SequenceNumber = sequenceNumber; + + i += (int)(handle.Size / _granularity); + } + + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + } + } + + public void Dispose() + { + foreach (var handle in _handles) + { + handle?.Dispose(); + } + } + } +} diff --git a/src/Ryujinx.Memory/Tracking/VirtualRegion.cs b/src/Ryujinx.Memory/Tracking/VirtualRegion.cs new file mode 100644 index 00000000..9651426b --- /dev/null +++ b/src/Ryujinx.Memory/Tracking/VirtualRegion.cs @@ -0,0 +1,144 @@ +using Ryujinx.Memory.Range; +using System.Collections.Generic; + +namespace Ryujinx.Memory.Tracking +{ + /// + /// A region of virtual memory. + /// + class VirtualRegion : AbstractRegion + { + public List Handles = new List(); + + private readonly MemoryTracking _tracking; + private MemoryPermission _lastPermission; + + public VirtualRegion(MemoryTracking tracking, ulong address, ulong size, MemoryPermission lastPermission = MemoryPermission.Invalid) : base(address, size) + { + _lastPermission = lastPermission; + _tracking = tracking; + } + + /// + public override void Signal(ulong address, ulong size, bool write, int? exemptId) + { + IList handles = Handles; + + for (int i = 0; i < handles.Count; i++) + { + if (exemptId == null || handles[i].Id != exemptId.Value) + { + handles[i].Signal(address, size, write, ref handles); + } + } + + UpdateProtection(); + } + + /// + public override void SignalPrecise(ulong address, ulong size, bool write, int? exemptId) + { + IList handles = Handles; + + bool allPrecise = true; + + for (int i = 0; i < handles.Count; i++) + { + if (exemptId == null || handles[i].Id != exemptId.Value) + { + allPrecise &= handles[i].SignalPrecise(address, size, write, ref handles); + } + } + + // Only update protection if a regular signal handler was called. + // This allows precise actions to skip reprotection costs if they want (they can still do it manually). + if (!allPrecise) + { + UpdateProtection(); + } + } + + /// + /// Signal that this region has been mapped or unmapped. + /// + /// True if the region has been mapped, false if unmapped + public void SignalMappingChanged(bool mapped) + { + _lastPermission = MemoryPermission.Invalid; + + foreach (RegionHandle handle in Handles) + { + handle.SignalMappingChanged(mapped); + } + } + + /// + /// Gets the strictest permission that the child handles demand. Assumes that the tracking lock has been obtained. + /// + /// Protection level that this region demands + public MemoryPermission GetRequiredPermission() + { + // Start with Read/Write, each handle can strip off permissions as necessary. + // Assumes the tracking lock has already been obtained. + + MemoryPermission result = MemoryPermission.ReadAndWrite; + + foreach (var handle in Handles) + { + result &= handle.RequiredPermission; + if (result == 0) return result; + } + return result; + } + + /// + /// Updates the protection for this virtual region. + /// + public bool UpdateProtection() + { + MemoryPermission permission = GetRequiredPermission(); + + if (_lastPermission != permission) + { + _tracking.ProtectVirtualRegion(this, permission); + _lastPermission = permission; + + return true; + } + + return false; + } + + /// + /// Removes a handle from this virtual region. If there are no handles left, this virtual region is removed. + /// + /// Handle to remove + public void RemoveHandle(RegionHandle handle) + { + lock (_tracking.TrackingLock) + { + Handles.Remove(handle); + UpdateProtection(); + if (Handles.Count == 0) + { + _tracking.RemoveVirtual(this); + } + } + } + + public override INonOverlappingRange Split(ulong splitAddress) + { + VirtualRegion newRegion = new VirtualRegion(_tracking, splitAddress, EndAddress - splitAddress, _lastPermission); + Size = splitAddress - Address; + + // The new region inherits all of our parents. + newRegion.Handles = new List(Handles); + foreach (var parent in Handles) + { + parent.AddChild(newRegion); + } + + return newRegion; + } + } +} -- cgit v1.2.3