diff options
Diffstat (limited to 'Ryujinx.Memory/Tracking')
| -rw-r--r-- | Ryujinx.Memory/Tracking/AbstractRegion.cs | 63 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/IMultiRegionHandle.cs | 48 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/IRegionHandle.cs | 16 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/IVirtualMemoryManager.cs | 9 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/MemoryTracking.cs | 321 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/MultiRegionHandle.cs | 134 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/PhysicalRegion.cs | 97 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/RegionHandle.cs | 134 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/RegionSignal.cs | 4 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs | 236 | ||||
| -rw-r--r-- | Ryujinx.Memory/Tracking/VirtualRegion.cs | 165 |
11 files changed, 1227 insertions, 0 deletions
diff --git a/Ryujinx.Memory/Tracking/AbstractRegion.cs b/Ryujinx.Memory/Tracking/AbstractRegion.cs new file mode 100644 index 00000000..ffac439f --- /dev/null +++ b/Ryujinx.Memory/Tracking/AbstractRegion.cs @@ -0,0 +1,63 @@ +using Ryujinx.Memory.Range; + +namespace Ryujinx.Memory.Tracking +{ + /// <summary> + /// A region of memory. + /// </summary> + abstract class AbstractRegion : INonOverlappingRange + { + /// <summary> + /// Base address. + /// </summary> + public ulong Address { get; } + + /// <summary> + /// Size of the range in bytes. + /// </summary> + public ulong Size { get; protected set; } + + /// <summary> + /// End address. + /// </summary> + public ulong EndAddress => Address + Size; + + /// <summary> + /// Create a new region. + /// </summary> + /// <param name="address">Base address</param> + /// <param name="size">Size of the range</param> + protected AbstractRegion(ulong address, ulong size) + { + Address = address; + Size = size; + } + + /// <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> + public bool OverlapsWith(ulong address, ulong size) + { + return Address < address + size && address < EndAddress; + } + + /// <summary> + /// Signals to the handles that a memory event has occurred, and unprotects the region. Assumes that the tracking lock has been obtained. + /// </summary> + /// <param name="address">Address accessed</param> + /// <param name="size">Size of the region affected in bytes</param> + /// <param name="write">Whether the region was written to or read</param> + public abstract void Signal(ulong address, ulong size, bool write); + + /// <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 abstract INonOverlappingRange Split(ulong splitAddress); + } +} diff --git a/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs b/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs new file mode 100644 index 00000000..357b8c5c --- /dev/null +++ b/Ryujinx.Memory/Tracking/IMultiRegionHandle.cs @@ -0,0 +1,48 @@ +using System; + +namespace Ryujinx.Memory.Tracking +{ + public interface IMultiRegionHandle : IDisposable + { + /// <summary> + /// True if any write has occurred to the whole region since the last use of QueryModified (with no subregion specified). + /// </summary> + bool Dirty { get; } + + /// <summary> + /// Check if any part of the region has been modified, and perform an action for each. + /// Contiguous modified regions are combined. + /// </summary> + /// <param name="modifiedAction">Action to perform for modified regions</param> + void QueryModified(Action<ulong, ulong> modifiedAction); + + + /// <summary> + /// 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. + /// </summary> + /// <param name="address">Start address of the range</param> + /// <param name="size">Size of the range</param> + /// <param name="modifiedAction">Action to perform for modified regions</param> + void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction); + + /// <summary> + /// 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. + /// </summary> + /// <param name="address">Start address of the range</param> + /// <param name="size">Size of the range</param> + /// <param name="modifiedAction">Action to perform for modified regions</param> + /// <param name="sequenceNumber">Current sequence number</param> + void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction, int sequenceNumber); + + /// <summary> + /// Signal that one of the subregions of this multi-region has been modified. This sets the overall dirty flag. + /// </summary> + void SignalWrite(); + } +} diff --git a/Ryujinx.Memory/Tracking/IRegionHandle.cs b/Ryujinx.Memory/Tracking/IRegionHandle.cs new file mode 100644 index 00000000..33628da6 --- /dev/null +++ b/Ryujinx.Memory/Tracking/IRegionHandle.cs @@ -0,0 +1,16 @@ +using System; + +namespace Ryujinx.Memory.Tracking +{ + public interface IRegionHandle : IDisposable + { + bool Dirty { get; } + + ulong Address { get; } + ulong Size { get; } + ulong EndAddress { get; } + + void Reprotect(); + void RegisterAction(RegionSignal action); + } +} diff --git a/Ryujinx.Memory/Tracking/IVirtualMemoryManager.cs b/Ryujinx.Memory/Tracking/IVirtualMemoryManager.cs new file mode 100644 index 00000000..6b5474e1 --- /dev/null +++ b/Ryujinx.Memory/Tracking/IVirtualMemoryManager.cs @@ -0,0 +1,9 @@ +namespace Ryujinx.Memory.Tracking +{ + public interface IVirtualMemoryManager + { + (ulong address, ulong size)[] GetPhysicalRegions(ulong va, ulong size); + + void TrackingReprotect(ulong va, ulong size, MemoryPermission protection); + } +} diff --git a/Ryujinx.Memory/Tracking/MemoryTracking.cs b/Ryujinx.Memory/Tracking/MemoryTracking.cs new file mode 100644 index 00000000..779166c4 --- /dev/null +++ b/Ryujinx.Memory/Tracking/MemoryTracking.cs @@ -0,0 +1,321 @@ +using Ryujinx.Memory.Range; +using System.Collections.Generic; + +namespace Ryujinx.Memory.Tracking +{ + /// <summary> + /// Manages memory tracking for a given virutal/physical memory block. + /// </summary> + public class MemoryTracking + { + private readonly IVirtualMemoryManager _memoryManager; + private readonly MemoryBlock _block; + + // Only use these from within the lock. + private readonly NonOverlappingRangeList<VirtualRegion> _virtualRegions; + private readonly NonOverlappingRangeList<PhysicalRegion> _physicalRegions; + + // Only use these from within the lock. + private readonly VirtualRegion[] _virtualResults = new VirtualRegion[10]; + private readonly PhysicalRegion[] _physicalResults = new PhysicalRegion[10]; + + private readonly int _pageSize; + + /// <summary> + /// This lock must be obtained when traversing or updating the region-handle hierarchy. + /// It is not required when reading dirty flags. + /// </summary> + internal object TrackingLock = new object(); + + public bool EnablePhysicalProtection { get; set; } + + /// <summary> + /// 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. + /// </summary> + /// <param name="memoryManager">Virtual memory manager</param> + /// <param name="block">Physical memory block</param> + /// <param name="pageSize">Page size of the virtual memory space</param> + public MemoryTracking(IVirtualMemoryManager memoryManager, MemoryBlock block, int pageSize) + { + _memoryManager = memoryManager; + _block = block; + _pageSize = pageSize; + + _virtualRegions = new NonOverlappingRangeList<VirtualRegion>(); + _physicalRegions = new NonOverlappingRangeList<PhysicalRegion>(); + } + + 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); + } + + /// <summary> + /// 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. + /// </summary> + /// <param name="va">Virtual memory address</param> + /// <param name="pa">Physical memory address</param> + /// <param name="size">Size to be mapped</param> + public void Map(ulong va, ulong pa, 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) + { + var results = _virtualResults; + int count = _virtualRegions.FindOverlapsNonOverlapping(va, size, ref results); + + for (int i = 0; i < count; i++) + { + VirtualRegion region = results[i]; + region.RecalculatePhysicalChildren(); + } + } + } + + /// <summary> + /// Indicate that a virtual region has been unmapped. + /// Should be called after the unmapping is complete. + /// </summary> + /// <param name="va">Virtual memory address</param> + /// <param name="size">Size to be unmapped</param> + 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 recalculate their physical regions + + lock (TrackingLock) + { + var results = _virtualResults; + int count = _virtualRegions.FindOverlapsNonOverlapping(va, size, ref results); + + for (int i = 0; i < count; i++) + { + VirtualRegion region = results[i]; + region.RecalculatePhysicalChildren(); + } + } + } + + /// <summary> + /// Get a list of virtual regions that a handle covers. + /// </summary> + /// <param name="va">Starting virtual memory address of the handle</param> + /// <param name="size">Size of the handle's memory region</param> + /// <returns>A list of virtual regions within the given range</returns> + internal List<VirtualRegion> GetVirtualRegionsForHandle(ulong va, ulong size) + { + List<VirtualRegion> result = new List<VirtualRegion>(); + _virtualRegions.GetOrAddRegions(result, va, size, (va, size) => new VirtualRegion(this, va, size)); + + return result; + } + + /// <summary> + /// Get a list of physical regions that a virtual region covers. + /// Note that this becomes outdated if the virtual or physical regions are unmapped or remapped. + /// </summary> + /// <param name="va">Virtual memory address</param> + /// <param name="size">Size of the virtual region</param> + /// <returns>A list of physical regions the virtual region covers</returns> + internal List<PhysicalRegion> GetPhysicalRegionsForVirtual(ulong va, ulong size) + { + List<PhysicalRegion> result = new List<PhysicalRegion>(); + + // Get a list of physical regions for this virtual region, from our injected virtual mapping function. + (ulong Address, ulong Size)[] physicalRegions = _memoryManager.GetPhysicalRegions(va, size); + + if (physicalRegions != null) + { + foreach (var region in physicalRegions) + { + _physicalRegions.GetOrAddRegions(result, region.Address, region.Size, (pa, size) => new PhysicalRegion(this, pa, size)); + } + } + + return result; + } + + /// <summary> + /// Remove a virtual region from the range list. This assumes that the lock has been acquired. + /// </summary> + /// <param name="region">Region to remove</param> + internal void RemoveVirtual(VirtualRegion region) + { + _virtualRegions.Remove(region); + } + + /// <summary> + /// Remove a physical region from the range list. This assumes that the lock has been acquired. + /// </summary> + /// <param name="region">Region to remove</param> + internal void RemovePhysical(PhysicalRegion region) + { + _physicalRegions.Remove(region); + } + + /// <summary> + /// Obtains a memory tracking handle for the given virtual region, with a specified granularity. This should be disposed when finished with. + /// </summary> + /// <param name="address">CPU virtual address of the region</param> + /// <param name="size">Size of the region</param> + /// <param name="granularity">Desired granularity of write tracking</param> + /// <returns>The memory tracking handle</returns> + public MultiRegionHandle BeginGranularTracking(ulong address, ulong size, ulong granularity) + { + (address, size) = PageAlign(address, size); + + return new MultiRegionHandle(this, address, size, granularity); + } + + /// <summary> + /// Obtains a smart memory tracking handle for the given virtual region, with a specified granularity. This should be disposed when finished with. + /// </summary> + /// <param name="address">CPU virtual address of the region</param> + /// <param name="size">Size of the region</param> + /// <param name="granularity">Desired granularity of write tracking</param> + /// <returns>The memory tracking handle</returns> + public SmartMultiRegionHandle BeginSmartGranularTracking(ulong address, ulong size, ulong granularity) + { + (address, size) = PageAlign(address, size); + + return new SmartMultiRegionHandle(this, address, size, granularity); + } + + /// <summary> + /// Obtains a memory tracking handle for the given virtual region. This should be disposed when finished with. + /// </summary> + /// <param name="address">CPU virtual address of the region</param> + /// <param name="size">Size of the region</param> + /// <returns>The memory tracking handle</returns> + public RegionHandle BeginTracking(ulong address, ulong size) + { + (address, size) = PageAlign(address, size); + + lock (TrackingLock) + { + RegionHandle handle = new RegionHandle(this, address, size); + + return handle; + } + } + + /// <summary> + /// Signal that a physical memory event happened at the given location. + /// </summary> + /// <param name="address">Physical address accessed</param> + /// <param name="write">Whether the region was written to or read</param> + /// <returns>True if the event triggered any tracking regions, false otherwise</returns> + public bool PhysicalMemoryEvent(ulong address, bool write) + { + // Look up the physical region using the region list. + // Signal up the chain to relevant handles. + + lock (TrackingLock) + { + var results = _physicalResults; + int count = _physicalRegions.FindOverlapsNonOverlapping(address, 1, ref results); // TODO: get/use the actual access size? + + if (count == 0) + { + _block.Reprotect(address & ~(ulong)(_pageSize - 1), (ulong)_pageSize, MemoryPermission.ReadAndWrite); + return false; // We can't handle this - unprotect and return. + } + + for (int i = 0; i < count; i++) + { + PhysicalRegion region = results[i]; + region.Signal(address, 1, write); + } + } + + return true; + } + + /// <summary> + /// Signal that a virtual memory event happened at the given location (one byte). + /// </summary> + /// <param name="address">Virtual address accessed</param> + /// <param name="write">Whether the address was written to or read</param> + /// <returns>True if the event triggered any tracking regions, false otherwise</returns> + public bool VirtualMemoryEventTracking(ulong address, bool write) + { + return VirtualMemoryEvent(address, 1, write); + } + + /// <summary> + /// Signal that a virtual memory event happened at the given location. + /// </summary> + /// <param name="address">Virtual address accessed</param> + /// <param name="size">Size of the region affected in bytes</param> + /// <param name="write">Whether the region was written to or read</param> + /// <returns>True if the event triggered any tracking regions, false otherwise</returns> + public bool VirtualMemoryEvent(ulong address, ulong size, bool write) + { + // Look up the virtual region using the region list. + // Signal up the chain to relevant handles. + + lock (TrackingLock) + { + var results = _virtualResults; + int count = _virtualRegions.FindOverlapsNonOverlapping(address, size, ref results); + + if (count == 0) + { + _memoryManager.TrackingReprotect(address & ~(ulong)(_pageSize - 1), (ulong)_pageSize, MemoryPermission.ReadAndWrite); + return false; // We can't handle this - it's probably a real invalid access. + } + + for (int i = 0; i < count; i++) + { + VirtualRegion region = results[i]; + region.Signal(address, size, write); + } + } + + return true; + } + + /// <summary> + /// Reprotect a given physical region, if enabled. This is protected on the memory block provided during initialization. + /// </summary> + /// <param name="region">Region to reprotect</param> + /// <param name="permission">Memory permission to protect with</param> + internal void ProtectPhysicalRegion(PhysicalRegion region, MemoryPermission permission) + { + if (EnablePhysicalProtection) + { + _block.Reprotect(region.Address, region.Size, permission); + } + } + + /// <summary> + /// Reprotect a given virtual region. The virtual memory manager will handle this. + /// </summary> + /// <param name="region">Region to reprotect</param> + /// <param name="permission">Memory permission to protect with</param> + internal void ProtectVirtualRegion(VirtualRegion region, MemoryPermission permission) + { + _memoryManager.TrackingReprotect(region.Address, region.Size, permission); + } + + /// <summary> + /// Returns the number of virtual and physical regions currently being tracked. + /// Useful for tests and metrics. + /// </summary> + /// <returns>The number of virtual regions, and the number of physical regions</returns> + public (int VirtualCount, int PhysicalCount) GetRegionCounts() + { + lock (TrackingLock) + { + return (_virtualRegions.Count, _physicalRegions.Count); + } + } + } +} diff --git a/Ryujinx.Memory/Tracking/MultiRegionHandle.cs b/Ryujinx.Memory/Tracking/MultiRegionHandle.cs new file mode 100644 index 00000000..02ae3a8b --- /dev/null +++ b/Ryujinx.Memory/Tracking/MultiRegionHandle.cs @@ -0,0 +1,134 @@ +using System; + +namespace Ryujinx.Memory.Tracking +{ + /// <summary> + /// A region handle that tracks a large region using many smaller handles, to provide + /// granular tracking that can be used to track partial updates. + /// </summary> + public class MultiRegionHandle : IMultiRegionHandle + { + /// <summary> + /// A list of region handles for each granularity sized chunk of the whole region. + /// </summary> + private readonly RegionHandle[] _handles; + private readonly ulong Address; + private readonly ulong Granularity; + private readonly ulong Size; + + public bool Dirty { get; private set; } = true; + + internal MultiRegionHandle(MemoryTracking tracking, ulong address, ulong size, ulong granularity) + { + _handles = new RegionHandle[size / granularity]; + Granularity = granularity; + + for (int i = 0; i < _handles.Length; i++) + { + RegionHandle handle = tracking.BeginTracking(address + (ulong)i * granularity, granularity); + handle.Parent = this; + _handles[i] = handle; + } + + Address = address; + Size = size; + } + + public void SignalWrite() + { + Dirty = true; + } + + public void QueryModified(Action<ulong, ulong> modifiedAction) + { + if (!Dirty) + { + return; + } + + Dirty = false; + + QueryModified(Address, Size, modifiedAction); + } + + public void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction) + { + int startHandle = (int)((address - Address) / Granularity); + int lastHandle = (int)((address + (size - 1) - Address) / Granularity); + + ulong rgStart = _handles[startHandle].Address; + ulong rgSize = 0; + + for (int i = startHandle; i <= lastHandle; i++) + { + RegionHandle 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; + } + } + + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + } + } + + public void QueryModified(ulong address, ulong size, Action<ulong, ulong> modifiedAction, int sequenceNumber) + { + int startHandle = (int)((address - Address) / Granularity); + int lastHandle = (int)((address + (size - 1) - Address) / Granularity); + + ulong rgStart = _handles[startHandle].Address; + ulong rgSize = 0; + + for (int i = startHandle; i <= lastHandle; i++) + { + RegionHandle 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; + } + + if (rgSize != 0) + { + modifiedAction(rgStart, rgSize); + } + } + + public void Dispose() + { + foreach (var handle in _handles) + { + handle.Dispose(); + } + } + } +} diff --git a/Ryujinx.Memory/Tracking/PhysicalRegion.cs b/Ryujinx.Memory/Tracking/PhysicalRegion.cs new file mode 100644 index 00000000..683186b1 --- /dev/null +++ b/Ryujinx.Memory/Tracking/PhysicalRegion.cs @@ -0,0 +1,97 @@ +using Ryujinx.Memory.Range; +using System.Collections.Generic; + +namespace Ryujinx.Memory.Tracking +{ + /// <summary> + /// A region of physical memory. + /// </summary> + class PhysicalRegion : AbstractRegion + { + public List<VirtualRegion> VirtualParents = new List<VirtualRegion>(); + public MemoryPermission Protection { get; private set; } + public MemoryTracking Tracking; + + public PhysicalRegion(MemoryTracking tracking, ulong address, ulong size) : base(address, size) + { + Tracking = tracking; + Protection = MemoryPermission.ReadAndWrite; + } + + public override void Signal(ulong address, ulong size, bool write) + { + Protection = MemoryPermission.ReadAndWrite; + Tracking.ProtectPhysicalRegion(this, MemoryPermission.ReadAndWrite); // Remove our protection immedately. + foreach (var parent in VirtualParents) + { + parent.Signal(address, size, write); + } + } + + /// <summary> + /// Update the protection of this region, based on our parent's requested protection. + /// </summary> + public void UpdateProtection() + { + // Re-evaluate protection, and commit to the block. + + lock (Tracking.TrackingLock) + { + MemoryPermission result = MemoryPermission.ReadAndWrite; + foreach (var parent in VirtualParents) + { + result &= parent.GetRequiredPermission(); + if (result == 0) break; + } + + if (Protection != result) + { + Protection = result; + Tracking.ProtectPhysicalRegion(this, result); + } + } + } + + public override INonOverlappingRange Split(ulong splitAddress) + { + PhysicalRegion newRegion = new PhysicalRegion(Tracking, splitAddress, EndAddress - splitAddress); + Size = splitAddress - Address; + + // The new region inherits all of our parents. + newRegion.VirtualParents = new List<VirtualRegion>(VirtualParents); + foreach (var parent in VirtualParents) + { + parent.AddChild(newRegion); + } + + return newRegion; + } + + /// <summary> + /// Remove a parent virtual region from this physical region. Assumes that the tracking lock has been obtained. + /// </summary> + /// <param name="region">Region to remove</param> + /// <returns>True if there are no more parents and we should be removed, false otherwise.</returns> + public bool RemoveParent(VirtualRegion region) + { + VirtualParents.Remove(region); + UpdateProtection(); + if (VirtualParents.Count == 0) + { + return true; + } + return false; + } + + /// <summary> + /// Deletes this physical region if there are no more virtual parents. + /// </summary> + public void TryDelete() + { + if (VirtualParents.Count == 0) + { + Tracking.RemovePhysical(this); + } + } + } +} diff --git a/Ryujinx.Memory/Tracking/RegionHandle.cs b/Ryujinx.Memory/Tracking/RegionHandle.cs new file mode 100644 index 00000000..c00d039b --- /dev/null +++ b/Ryujinx.Memory/Tracking/RegionHandle.cs @@ -0,0 +1,134 @@ +using Ryujinx.Memory.Range; +using System.Collections.Generic; +using System.Threading; + +namespace Ryujinx.Memory.Tracking +{ + /// <summary> + /// 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. + /// </summary> + public class RegionHandle : IRegionHandle, IRange + { + public bool Dirty { get; private set; } = true; + + public ulong Address { get; } + public ulong Size { get; } + public ulong EndAddress { get; } + + internal IMultiRegionHandle Parent { get; set; } + internal int SequenceNumber { get; set; } + + private RegionSignal _preAction; // Action to perform before a read or write. This will block the memory access. + private readonly List<VirtualRegion> _regions; + private readonly MemoryTracking _tracking; + + internal MemoryPermission RequiredPermission => _preAction != null ? MemoryPermission.None : (Dirty ? MemoryPermission.ReadAndWrite : MemoryPermission.Read); + + /// <summary> + /// 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. + /// </summary> + /// <param name="tracking">Tracking object for the target memory block</param> + /// <param name="address">Virtual address of the region to track</param> + /// <param name="size">Size of the region to track</param> + internal RegionHandle(MemoryTracking tracking, ulong address, ulong size) + { + Address = address; + Size = size; + EndAddress = address + size; + + _tracking = tracking; + _regions = tracking.GetVirtualRegionsForHandle(address, size); + foreach (var region in _regions) + { + region.Handles.Add(this); + } + } + + /// <summary> + /// Signal that a memory action occurred within this handle's virtual regions. + /// </summary> + /// <param name="write">Whether the region was written to or read</param> + internal void Signal(ulong address, ulong size, bool write) + { + RegionSignal action = Interlocked.Exchange(ref _preAction, null); + action?.Invoke(address, size); + + if (write) + { + Dirty = true; + Parent?.SignalWrite(); + } + } + + /// <summary> + /// Consume the dirty flag for this handle, and reprotect so it can be set on the next write. + /// </summary> + public void Reprotect() + { + Dirty = false; + lock (_tracking.TrackingLock) + { + foreach (VirtualRegion region in _regions) + { + region.UpdateProtection(); + } + } + } + + /// <summary> + /// Register an action to perform when the tracked region is read or written. + /// The action is automatically removed after it runs. + /// </summary> + /// <param name="action">Action to call on read or write</param> + public void RegisterAction(RegionSignal action) + { + RegionSignal lastAction = Interlocked.Exchange(ref _preAction, action); + if (lastAction == null && action != lastAction) + { + lock (_tracking.TrackingLock) + { + foreach (VirtualRegion region in _regions) + { + region.UpdateProtection(); + } + } + } + } + + /// <summary> + /// Add a child virtual region to this handle. + /// </summary> + /// <param name="region">Virtual region to add as a child</param> + internal void AddChild(VirtualRegion region) + { + _regions.Add(region); + } + + /// <summary> + /// Check if this region overlaps with another. + /// </summary> + /// <param name="address">Base address</param> + /// <param name="size">Size of the region</param> + /// <returns>True if overlapping, false otherwise</returns> + public bool OverlapsWith(ulong address, ulong size) + { + return Address < address + size && address < EndAddress; + } + + /// <summary> + /// Dispose the handle. Within the tracking lock, this removes references from virtual and physical regions. + /// </summary> + public void Dispose() + { + lock (_tracking.TrackingLock) + { + foreach (VirtualRegion region in _regions) + { + region.RemoveHandle(this); + } + } + } + } +} diff --git a/Ryujinx.Memory/Tracking/RegionSignal.cs b/Ryujinx.Memory/Tracking/RegionSignal.cs new file mode 100644 index 00000000..c8a28d7d --- /dev/null +++ b/Ryujinx.Memory/Tracking/RegionSignal.cs @@ -0,0 +1,4 @@ +namespace Ryujinx.Memory.Tracking +{ + public delegate void RegionSignal(ulong address, ulong size); +} diff --git a/Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs b/Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs new file mode 100644 index 00000000..60188400 --- /dev/null +++ b/Ryujinx.Memory/Tracking/SmartMultiRegionHandle.cs @@ -0,0 +1,236 @@ +using System; +using System.Runtime.CompilerServices; + +namespace Ryujinx.Memory.Tracking +{ + /// <summary> + /// 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. + /// </summary> + public class SmartMultiRegionHandle : IMultiRegionHandle + { + /// <summary> + /// A list of region handles starting at each granularity size increment. + /// </summary> + private readonly RegionHandle[] _handles; + private readonly ulong _address; + private readonly ulong _granularity; + private readonly ulong _size; + private MemoryTracking _tracking; + + public bool Dirty { get; private set; } = true; + + internal SmartMultiRegionHandle(MemoryTracking tracking, ulong address, ulong size, ulong granularity) + { + // 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; + } + + public void SignalWrite() + { + Dirty = true; + } + + public void QueryModified(Action<ulong, ulong> 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. + handle.Dispose(); + + RegionHandle splitLow = _tracking.BeginTracking(address, size); + splitLow.Parent = this; + _handles[handleIndex] = splitLow; + + RegionHandle splitHigh = _tracking.BeginTracking(address + size, handle.Size - size); + splitHigh.Parent = this; + _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)); + handle.Parent = this; + _handles[startHandle] = handle; + return; + } + } + + // Can fill the whole range. + _handles[startHandle] = _tracking.BeginTracking(startAddress, HandlesToBytes(1 + lastHandle - startHandle)); + _handles[startHandle].Parent = this; + } + + public void QueryModified(ulong address, ulong size, Action<ulong, ulong> 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<ulong, ulong> 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/Ryujinx.Memory/Tracking/VirtualRegion.cs b/Ryujinx.Memory/Tracking/VirtualRegion.cs new file mode 100644 index 00000000..90fb55d6 --- /dev/null +++ b/Ryujinx.Memory/Tracking/VirtualRegion.cs @@ -0,0 +1,165 @@ +using Ryujinx.Memory.Range; +using System.Collections.Generic; + +namespace Ryujinx.Memory.Tracking +{ + /// <summary> + /// A region of virtual memory. + /// </summary> + class VirtualRegion : AbstractRegion + { + public List<RegionHandle> Handles = new List<RegionHandle>(); + private List<PhysicalRegion> _physicalChildren; + + private readonly MemoryTracking _tracking; + + public VirtualRegion(MemoryTracking tracking, ulong address, ulong size) : base(address, size) + { + _tracking = tracking; + + UpdatePhysicalChildren(); + } + + public override void Signal(ulong address, ulong size, bool write) + { + _tracking.ProtectVirtualRegion(this, MemoryPermission.ReadAndWrite); // Remove our protection immedately. + + foreach (var handle in Handles) + { + handle.Signal(address, size, write); + } + } + + /// <summary> + /// Clears all physical children of this region. Assumes that the tracking lock has been obtained. + /// </summary> + private void ClearPhysicalChildren() + { + if (_physicalChildren != null) + { + foreach (PhysicalRegion child in _physicalChildren) + { + child.RemoveParent(this); + } + } + } + + /// <summary> + /// Updates the physical children of this region, assuming that they are clear and that the tracking lock has been obtained. + /// </summary> + private void UpdatePhysicalChildren() + { + _physicalChildren = _tracking.GetPhysicalRegionsForVirtual(Address, Size); + + foreach (PhysicalRegion child in _physicalChildren) + { + child.VirtualParents.Add(this); + } + } + + /// <summary> + /// Recalculates the physical children for this virtual region. Assumes that the tracking lock has been obtained. + /// </summary> + public void RecalculatePhysicalChildren() + { + ClearPhysicalChildren(); + UpdatePhysicalChildren(); + } + + /// <summary> + /// Gets the strictest permission that the child handles demand. Assumes that the tracking lock has been obtained. + /// </summary> + /// <returns>Protection level that this region demands</returns> + 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; + } + + /// <summary> + /// Updates the protection for this virtual region, and all child physical regions. + /// </summary> + public void UpdateProtection() + { + // Re-evaluate protection for all physical children. + + _tracking.ProtectVirtualRegion(this, GetRequiredPermission()); + lock (_tracking.TrackingLock) + { + foreach (var child in _physicalChildren) + { + child.UpdateProtection(); + } + } + } + + /// <summary> + /// Removes a handle from this virtual region. If there are no handles left, this virtual region is removed. + /// </summary> + /// <param name="handle">Handle to remove</param> + public void RemoveHandle(RegionHandle handle) + { + bool removedRegions = false; + lock (_tracking.TrackingLock) + { + Handles.Remove(handle); + UpdateProtection(); + if (Handles.Count == 0) + { + _tracking.RemoveVirtual(this); + foreach (var child in _physicalChildren) + { + removedRegions |= child.RemoveParent(this); + } + } + } + + if (removedRegions) + { + // The first lock will unprotect any regions that have been removed. This second lock will remove them. + lock (_tracking.TrackingLock) + { + foreach (var child in _physicalChildren) + { + child.TryDelete(); + } + } + } + } + + /// <summary> + /// Add a child physical region to this virtual region. Assumes that the tracking lock has been obtained. + /// </summary> + /// <param name="region">Physical region to add as a child</param> + public void AddChild(PhysicalRegion region) + { + _physicalChildren.Add(region); + } + + public override INonOverlappingRange Split(ulong splitAddress) + { + ClearPhysicalChildren(); + VirtualRegion newRegion = new VirtualRegion(_tracking, splitAddress, EndAddress - splitAddress); + Size = splitAddress - Address; + UpdatePhysicalChildren(); + + // The new region inherits all of our parents. + newRegion.Handles = new List<RegionHandle>(Handles); + foreach (var parent in Handles) + { + parent.AddChild(newRegion); + } + + return newRegion; + } + } +} |