From 45e520a27c2deb11d22a38c58962048d303460eb Mon Sep 17 00:00:00 2001 From: gdk Date: Thu, 23 Jun 2022 04:05:56 -0300 Subject: Rewrite PlaceholderManager4KB to use intrusive RBTree, and to coalesce free placeholders Also make the other placeholder manager use intrusive RBTree, allows the IntervalTree that was added just for this to be deleted --- Ryujinx.Memory/WindowsShared/PlaceholderManager.cs | 105 +++++++++++---------- 1 file changed, 57 insertions(+), 48 deletions(-) (limited to 'Ryujinx.Memory/WindowsShared/PlaceholderManager.cs') diff --git a/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs b/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs index 0937d462..6db8d7df 100644 --- a/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs +++ b/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs @@ -13,10 +13,10 @@ namespace Ryujinx.Memory.WindowsShared [SupportedOSPlatform("windows")] class PlaceholderManager { - private const ulong MinimumPageSize = 0x1000; + private const int InitialOverlapsSize = 10; - private readonly IntervalTree _mappings; - private readonly IntervalTree _protections; + private readonly MappingTree _mappings; + private readonly MappingTree _protections; private readonly IntPtr _partialUnmapStatePtr; private readonly Thread _partialUnmapTrimThread; @@ -25,8 +25,8 @@ namespace Ryujinx.Memory.WindowsShared /// public PlaceholderManager() { - _mappings = new IntervalTree(); - _protections = new IntervalTree(); + _mappings = new MappingTree(); + _protections = new MappingTree(); _partialUnmapStatePtr = PartialUnmapState.GlobalState; @@ -67,7 +67,7 @@ namespace Ryujinx.Memory.WindowsShared { lock (_mappings) { - _mappings.Add(address, address + size, ulong.MaxValue); + _mappings.Add(new RangeNode(address, address + size, ulong.MaxValue)); } } @@ -81,12 +81,12 @@ namespace Ryujinx.Memory.WindowsShared { ulong endAddress = address + size; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; int count; lock (_mappings) { - count = _mappings.Get(address, endAddress, ref overlaps); + count = _mappings.GetNodes(address, endAddress, ref overlaps); for (int index = 0; index < count; index++) { @@ -178,11 +178,11 @@ namespace Ryujinx.Memory.WindowsShared { ulong endAddress = address + size; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; lock (_mappings) { - int count = _mappings.Get(address, endAddress, ref overlaps); + int count = _mappings.GetNodes(address, endAddress, ref overlaps); Debug.Assert(count == 1); Debug.Assert(!IsMapped(overlaps[0].Value)); @@ -206,8 +206,8 @@ namespace Ryujinx.Memory.WindowsShared (IntPtr)size, AllocationType.Release | AllocationType.PreservePlaceholder)); - _mappings.Add(overlapStart, address, overlapValue); - _mappings.Add(endAddress, overlapEnd, AddBackingOffset(overlapValue, endAddress - overlapStart)); + _mappings.Add(new RangeNode(overlapStart, address, overlapValue)); + _mappings.Add(new RangeNode(endAddress, overlapEnd, AddBackingOffset(overlapValue, endAddress - overlapStart))); } else if (overlapStartsBefore) { @@ -218,7 +218,7 @@ namespace Ryujinx.Memory.WindowsShared (IntPtr)overlappedSize, AllocationType.Release | AllocationType.PreservePlaceholder)); - _mappings.Add(overlapStart, address, overlapValue); + _mappings.Add(new RangeNode(overlapStart, address, overlapValue)); } else if (overlapEndsAfter) { @@ -229,10 +229,10 @@ namespace Ryujinx.Memory.WindowsShared (IntPtr)overlappedSize, AllocationType.Release | AllocationType.PreservePlaceholder)); - _mappings.Add(endAddress, overlapEnd, AddBackingOffset(overlapValue, overlappedSize)); + _mappings.Add(new RangeNode(endAddress, overlapEnd, AddBackingOffset(overlapValue, overlappedSize))); } - _mappings.Add(address, endAddress, backingOffset); + _mappings.Add(new RangeNode(address, endAddress, backingOffset)); } } @@ -280,12 +280,12 @@ namespace Ryujinx.Memory.WindowsShared ulong unmapSize = (ulong)size; ulong endAddress = startAddress + unmapSize; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; int count; lock (_mappings) { - count = _mappings.Get(startAddress, endAddress, ref overlaps); + count = _mappings.GetNodes(startAddress, endAddress, ref overlaps); } for (int index = 0; index < count; index++) @@ -302,7 +302,7 @@ namespace Ryujinx.Memory.WindowsShared lock (_mappings) { _mappings.Remove(overlap); - _mappings.Add(overlapStart, overlapEnd, ulong.MaxValue); + _mappings.Add(new RangeNode(overlapStart, overlapEnd, ulong.MaxValue)); } bool overlapStartsBefore = overlapStart < startAddress; @@ -374,44 +374,53 @@ namespace Ryujinx.Memory.WindowsShared ulong endAddress = address + size; ulong blockAddress = (ulong)owner.Pointer; ulong blockEnd = blockAddress + owner.Size; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; int unmappedCount = 0; lock (_mappings) { - int count = _mappings.Get( - Math.Max(address - MinimumPageSize, blockAddress), - Math.Min(endAddress + MinimumPageSize, blockEnd), ref overlaps); + int count = _mappings.GetNodes(address, endAddress, ref overlaps); - if (count < 2) + if (count == 0) { - // Nothing to coalesce if we only have 1 or no overlaps. + // Nothing to coalesce if we no overlaps. return; } + RangeNode predecessor = overlaps[0].Predecessor; + RangeNode successor = overlaps[count - 1].Successor; + for (int index = 0; index < count; index++) { var overlap = overlaps[index]; if (!IsMapped(overlap.Value)) { - if (address > overlap.Start) - { - address = overlap.Start; - } - - if (endAddress < overlap.End) - { - endAddress = overlap.End; - } + address = Math.Min(address, overlap.Start); + endAddress = Math.Max(endAddress, overlap.End); _mappings.Remove(overlap); - unmappedCount++; } } - _mappings.Add(address, endAddress, ulong.MaxValue); + if (predecessor != null && !IsMapped(predecessor.Value) && predecessor.Start >= blockAddress) + { + address = Math.Min(address, predecessor.Start); + + _mappings.Remove(predecessor); + unmappedCount++; + } + + if (successor != null && !IsMapped(successor.Value) && successor.End <= blockEnd) + { + endAddress = Math.Max(endAddress, successor.End); + + _mappings.Remove(successor); + unmappedCount++; + } + + _mappings.Add(new RangeNode(address, endAddress, ulong.MaxValue)); } if (unmappedCount > 1) @@ -462,12 +471,12 @@ namespace Ryujinx.Memory.WindowsShared ulong reprotectSize = (ulong)size; ulong endAddress = reprotectAddress + reprotectSize; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; int count; lock (_mappings) { - count = _mappings.Get(reprotectAddress, endAddress, ref overlaps); + count = _mappings.GetNodes(reprotectAddress, endAddress, ref overlaps); } bool success = true; @@ -567,12 +576,12 @@ namespace Ryujinx.Memory.WindowsShared private void AddProtection(ulong address, ulong size, MemoryPermission permission) { ulong endAddress = address + size; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; int count; lock (_protections) { - count = _protections.Get(address, endAddress, ref overlaps); + count = _protections.GetNodes(address, endAddress, ref overlaps); if (count == 1 && overlaps[0].Start <= address && @@ -610,17 +619,17 @@ namespace Ryujinx.Memory.WindowsShared { if (startAddress > protAddress) { - _protections.Add(protAddress, startAddress, protPermission); + _protections.Add(new RangeNode(protAddress, startAddress, protPermission)); } if (endAddress < protEndAddress) { - _protections.Add(endAddress, protEndAddress, protPermission); + _protections.Add(new RangeNode(endAddress, protEndAddress, protPermission)); } } } - _protections.Add(startAddress, endAddress, permission); + _protections.Add(new RangeNode(startAddress, endAddress, permission)); } } @@ -632,12 +641,12 @@ namespace Ryujinx.Memory.WindowsShared private void RemoveProtection(ulong address, ulong size) { ulong endAddress = address + size; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; int count; lock (_protections) { - count = _protections.Get(address, endAddress, ref overlaps); + count = _protections.GetNodes(address, endAddress, ref overlaps); for (int index = 0; index < count; index++) { @@ -651,12 +660,12 @@ namespace Ryujinx.Memory.WindowsShared if (address > protAddress) { - _protections.Add(protAddress, address, protPermission); + _protections.Add(new RangeNode(protAddress, address, protPermission)); } if (endAddress < protEndAddress) { - _protections.Add(endAddress, protEndAddress, protPermission); + _protections.Add(new RangeNode(endAddress, protEndAddress, protPermission)); } } } @@ -670,12 +679,12 @@ namespace Ryujinx.Memory.WindowsShared private void RestoreRangeProtection(ulong address, ulong size) { ulong endAddress = address + size; - var overlaps = Array.Empty>(); + var overlaps = new RangeNode[InitialOverlapsSize]; int count; lock (_protections) { - count = _protections.Get(address, endAddress, ref overlaps); + count = _protections.GetNodes(address, endAddress, ref overlaps); } ulong startAddress = address; -- cgit v1.2.3