aboutsummaryrefslogtreecommitdiff
path: root/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs
diff options
context:
space:
mode:
authorgdk <gab.dark.100@gmail.com>2022-06-23 04:05:56 -0300
committerMary-nyan <thog@protonmail.com>2022-09-10 16:23:49 +0200
commit45e520a27c2deb11d22a38c58962048d303460eb (patch)
tree91976e4ed29f90e5deb74eaa4651b6ec60599cf1 /Ryujinx.Memory/WindowsShared/PlaceholderManager.cs
parent5b5810a46a9c2506af82f03b90174741e06568dd (diff)
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
Diffstat (limited to 'Ryujinx.Memory/WindowsShared/PlaceholderManager.cs')
-rw-r--r--Ryujinx.Memory/WindowsShared/PlaceholderManager.cs105
1 files changed, 57 insertions, 48 deletions
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<ulong, ulong> _mappings;
- private readonly IntervalTree<ulong, MemoryPermission> _protections;
+ private readonly MappingTree<ulong> _mappings;
+ private readonly MappingTree<MemoryPermission> _protections;
private readonly IntPtr _partialUnmapStatePtr;
private readonly Thread _partialUnmapTrimThread;
@@ -25,8 +25,8 @@ namespace Ryujinx.Memory.WindowsShared
/// </summary>
public PlaceholderManager()
{
- _mappings = new IntervalTree<ulong, ulong>();
- _protections = new IntervalTree<ulong, MemoryPermission>();
+ _mappings = new MappingTree<ulong>();
+ _protections = new MappingTree<MemoryPermission>();
_partialUnmapStatePtr = PartialUnmapState.GlobalState;
@@ -67,7 +67,7 @@ namespace Ryujinx.Memory.WindowsShared
{
lock (_mappings)
{
- _mappings.Add(address, address + size, ulong.MaxValue);
+ _mappings.Add(new RangeNode<ulong>(address, address + size, ulong.MaxValue));
}
}
@@ -81,12 +81,12 @@ namespace Ryujinx.Memory.WindowsShared
{
ulong endAddress = address + size;
- var overlaps = Array.Empty<IntervalTreeNode<ulong, ulong>>();
+ var overlaps = new RangeNode<ulong>[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<IntervalTreeNode<ulong, ulong>>();
+ var overlaps = new RangeNode<ulong>[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<ulong>(overlapStart, address, overlapValue));
+ _mappings.Add(new RangeNode<ulong>(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<ulong>(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<ulong>(endAddress, overlapEnd, AddBackingOffset(overlapValue, overlappedSize)));
}
- _mappings.Add(address, endAddress, backingOffset);
+ _mappings.Add(new RangeNode<ulong>(address, endAddress, backingOffset));
}
}
@@ -280,12 +280,12 @@ namespace Ryujinx.Memory.WindowsShared
ulong unmapSize = (ulong)size;
ulong endAddress = startAddress + unmapSize;
- var overlaps = Array.Empty<IntervalTreeNode<ulong, ulong>>();
+ var overlaps = new RangeNode<ulong>[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<ulong>(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<IntervalTreeNode<ulong, ulong>>();
+ var overlaps = new RangeNode<ulong>[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<ulong> predecessor = overlaps[0].Predecessor;
+ RangeNode<ulong> 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<ulong>(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<IntervalTreeNode<ulong, ulong>>();
+ var overlaps = new RangeNode<ulong>[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<IntervalTreeNode<ulong, MemoryPermission>>();
+ var overlaps = new RangeNode<MemoryPermission>[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<MemoryPermission>(protAddress, startAddress, protPermission));
}
if (endAddress < protEndAddress)
{
- _protections.Add(endAddress, protEndAddress, protPermission);
+ _protections.Add(new RangeNode<MemoryPermission>(endAddress, protEndAddress, protPermission));
}
}
}
- _protections.Add(startAddress, endAddress, permission);
+ _protections.Add(new RangeNode<MemoryPermission>(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<IntervalTreeNode<ulong, MemoryPermission>>();
+ var overlaps = new RangeNode<MemoryPermission>[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<MemoryPermission>(protAddress, address, protPermission));
}
if (endAddress < protEndAddress)
{
- _protections.Add(endAddress, protEndAddress, protPermission);
+ _protections.Add(new RangeNode<MemoryPermission>(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<IntervalTreeNode<ulong, MemoryPermission>>();
+ var overlaps = new RangeNode<MemoryPermission>[InitialOverlapsSize];
int count;
lock (_protections)
{
- count = _protections.Get(address, endAddress, ref overlaps);
+ count = _protections.GetNodes(address, endAddress, ref overlaps);
}
ulong startAddress = address;
generated by cgit v1.2.3-70-g09d2 (git 2.49.0) at 2025-03-27 16:52:55 +0000