From 6922862db8677fb8067a3e35d2433b1f12f8329c Mon Sep 17 00:00:00 2001
From: gdkchan <gab.dark.100@gmail.com>
Date: Fri, 26 Aug 2022 15:21:48 -0300
Subject: Optimize kernel memory block lookup and consolidate RBTree
implementations (#3410)
* Implement intrusive red-black tree, use it for HLE kernel block manager
* Implement TreeDictionary using IntrusiveRedBlackTree
* Implement IntervalTree using IntrusiveRedBlackTree
* Implement IntervalTree (on Ryujinx.Memory) using IntrusiveRedBlackTree
* Make PredecessorOf and SuccessorOf internal, expose Predecessor and Successor properties on the node itself
* Allocation free tree node lookup
---
Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs | 24 ++++++++++++------------
1 file changed, 12 insertions(+), 12 deletions(-)
(limited to 'Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs')
diff --git a/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs b/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs
index ab43b477..857be7a6 100644
--- a/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs
+++ b/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs
@@ -2447,9 +2447,9 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
{
ulong endAddr = address + size;
- LinkedListNode<KMemoryBlock> node = _blockManager.FindBlockNode(address);
+ KMemoryBlock currBlock = _blockManager.FindBlock(address);
- KMemoryInfo info = node.Value.GetInfo();
+ KMemoryInfo info = currBlock.GetInfo();
MemoryState firstState = info.State;
KMemoryPermission firstPermission = info.Permission;
@@ -2457,7 +2457,7 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
do
{
- info = node.Value.GetInfo();
+ info = currBlock.GetInfo();
// Check if the block state matches what we expect.
if (firstState != info.State ||
@@ -2474,7 +2474,7 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
return false;
}
}
- while (info.Address + info.Size - 1 < endAddr - 1 && (node = node.Next) != null);
+ while (info.Address + info.Size - 1 < endAddr - 1 && (currBlock = currBlock.Successor) != null);
outState = firstState;
outPermission = firstPermission;
@@ -2509,17 +2509,17 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
private IEnumerable<KMemoryInfo> IterateOverRange(ulong start, ulong end)
{
- LinkedListNode<KMemoryBlock> node = _blockManager.FindBlockNode(start);
+ KMemoryBlock currBlock = _blockManager.FindBlock(start);
KMemoryInfo info;
do
{
- info = node.Value.GetInfo();
+ info = currBlock.GetInfo();
yield return info;
}
- while (info.Address + info.Size - 1 < end - 1 && (node = node.Next) != null);
+ while (info.Address + info.Size - 1 < end - 1 && (currBlock = currBlock.Successor) != null);
}
private ulong AllocateVa(ulong regionStart, ulong regionPagesCount, ulong neededPagesCount, int alignment)
@@ -2605,9 +2605,9 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
ulong regionEndAddr = regionStart + regionPagesCount * PageSize;
- LinkedListNode<KMemoryBlock> node = _blockManager.FindBlockNode(regionStart);
+ KMemoryBlock currBlock = _blockManager.FindBlock(regionStart);
- KMemoryInfo info = node.Value.GetInfo();
+ KMemoryInfo info = currBlock.GetInfo();
while (regionEndAddr >= info.Address)
{
@@ -2636,14 +2636,14 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
}
}
- node = node.Next;
+ currBlock = currBlock.Successor;
- if (node == null)
+ if (currBlock == null)
{
break;
}
- info = node.Value.GetInfo();
+ info = currBlock.GetInfo();
}
return 0;
--
cgit v1.2.3-70-g09d2