aboutsummaryrefslogtreecommitdiff
path: root/Ryujinx.HLE/HOS/Kernel/Memory/KPageBitmap.cs
diff options
context:
space:
mode:
authorgdkchan <gab.dark.100@gmail.com>2022-06-22 12:28:14 -0300
committerGitHub <noreply@github.com>2022-06-22 12:28:14 -0300
commitf2a41b7a1cad027cc1f1f8f687cda6ab42030eb9 (patch)
tree0e128bb17fe36bce8f1924a62b9ae516adbfdd30 /Ryujinx.HLE/HOS/Kernel/Memory/KPageBitmap.cs
parentc881cd2d1452dc6ad87a570db76139a0c6105132 (diff)
Rewrite kernel memory allocator (#3316)1.1.152
* Rewrite kernel memory allocator * Remove unused using * Adjust private static field naming * Change UlongBitSize to UInt64BitSize * Fix unused argument, change argument order to be inline with official code and disable random allocation
Diffstat (limited to 'Ryujinx.HLE/HOS/Kernel/Memory/KPageBitmap.cs')
-rw-r--r--Ryujinx.HLE/HOS/Kernel/Memory/KPageBitmap.cs298
1 files changed, 298 insertions, 0 deletions
diff --git a/Ryujinx.HLE/HOS/Kernel/Memory/KPageBitmap.cs b/Ryujinx.HLE/HOS/Kernel/Memory/KPageBitmap.cs
new file mode 100644
index 00000000..0568325a
--- /dev/null
+++ b/Ryujinx.HLE/HOS/Kernel/Memory/KPageBitmap.cs
@@ -0,0 +1,298 @@
+using Ryujinx.Common;
+using System;
+using System.Numerics;
+
+namespace Ryujinx.HLE.HOS.Kernel.Memory
+{
+ class KPageBitmap
+ {
+ private struct RandomNumberGenerator
+ {
+ private uint _entropy;
+ private uint _bitsAvailable;
+
+ private void RefreshEntropy()
+ {
+ _entropy = 0;
+ _bitsAvailable = sizeof(uint) * 8;
+ }
+
+ private bool GenerateRandomBit()
+ {
+ if (_bitsAvailable == 0)
+ {
+ RefreshEntropy();
+ }
+
+ bool bit = (_entropy & 1) != 0;
+
+ _entropy >>= 1;
+ _bitsAvailable--;
+
+ return bit;
+ }
+
+ public int SelectRandomBit(ulong bitmap)
+ {
+ int selected = 0;
+
+ int bitsCount = UInt64BitSize / 2;
+ ulong mask = (1UL << bitsCount) - 1;
+
+ while (bitsCount != 0)
+ {
+ ulong low = bitmap & mask;
+ ulong high = (bitmap >> bitsCount) & mask;
+
+ bool chooseLow;
+
+ if (high == 0)
+ {
+ chooseLow = true;
+ }
+ else if (low == 0)
+ {
+ chooseLow = false;
+ }
+ else
+ {
+ chooseLow = GenerateRandomBit();
+ }
+
+ if (chooseLow)
+ {
+ bitmap = low;
+ }
+ else
+ {
+ bitmap = high;
+ selected += bitsCount;
+ }
+
+ bitsCount /= 2;
+ mask >>= bitsCount;
+ }
+
+ return selected;
+ }
+ }
+
+ private const int UInt64BitSize = sizeof(ulong) * 8;
+ private const int MaxDepth = 4;
+
+ private readonly RandomNumberGenerator _rng;
+ private readonly ArraySegment<ulong>[] _bitStorages;
+ private int _usedDepths;
+
+ public int BitsCount { get; private set; }
+
+ public int HighestDepthIndex => _usedDepths - 1;
+
+ public KPageBitmap()
+ {
+ _rng = new RandomNumberGenerator();
+ _bitStorages = new ArraySegment<ulong>[MaxDepth];
+ }
+
+ public ArraySegment<ulong> Initialize(ArraySegment<ulong> storage, ulong size)
+ {
+ _usedDepths = GetRequiredDepth(size);
+
+ for (int depth = HighestDepthIndex; depth >= 0; depth--)
+ {
+ _bitStorages[depth] = storage;
+ size = BitUtils.DivRoundUp(size, UInt64BitSize);
+ storage = storage.Slice((int)size);
+ }
+
+ return storage;
+ }
+
+ public ulong FindFreeBlock(bool random)
+ {
+ ulong offset = 0;
+ int depth = 0;
+
+ if (random)
+ {
+ do
+ {
+ ulong v = _bitStorages[depth][(int)offset];
+
+ if (v == 0)
+ {
+ return ulong.MaxValue;
+ }
+
+ offset = offset * UInt64BitSize + (ulong)_rng.SelectRandomBit(v);
+ }
+ while (++depth < _usedDepths);
+ }
+ else
+ {
+ do
+ {
+ ulong v = _bitStorages[depth][(int)offset];
+
+ if (v == 0)
+ {
+ return ulong.MaxValue;
+ }
+
+ offset = offset * UInt64BitSize + (ulong)BitOperations.TrailingZeroCount(v);
+ }
+ while (++depth < _usedDepths);
+ }
+
+ return offset;
+ }
+
+ public void SetBit(ulong offset)
+ {
+ SetBit(HighestDepthIndex, offset);
+ BitsCount++;
+ }
+
+ public void ClearBit(ulong offset)
+ {
+ ClearBit(HighestDepthIndex, offset);
+ BitsCount--;
+ }
+
+ public bool ClearRange(ulong offset, int count)
+ {
+ int depth = HighestDepthIndex;
+ var bits = _bitStorages[depth];
+
+ int bitInd = (int)(offset / UInt64BitSize);
+
+ if (count < UInt64BitSize)
+ {
+ int shift = (int)(offset % UInt64BitSize);
+
+ ulong mask = ((1UL << count) - 1) << shift;
+
+ ulong v = bits[bitInd];
+
+ if ((v & mask) != mask)
+ {
+ return false;
+ }
+
+ v &= ~mask;
+ bits[bitInd] = v;
+
+ if (v == 0)
+ {
+ ClearBit(depth - 1, (ulong)bitInd);
+ }
+ }
+ else
+ {
+ int remaining = count;
+ int i = 0;
+
+ do
+ {
+ if (bits[bitInd + i++] != ulong.MaxValue)
+ {
+ return false;
+ }
+
+ remaining -= UInt64BitSize;
+ }
+ while (remaining > 0);
+
+ remaining = count;
+ i = 0;
+
+ do
+ {
+ bits[bitInd + i] = 0;
+ ClearBit(depth - 1, (ulong)(bitInd + i));
+ i++;
+ remaining -= UInt64BitSize;
+ }
+ while (remaining > 0);
+ }
+
+ BitsCount -= count;
+ return true;
+ }
+
+ private void SetBit(int depth, ulong offset)
+ {
+ while (depth >= 0)
+ {
+ int ind = (int)(offset / UInt64BitSize);
+ int which = (int)(offset % UInt64BitSize);
+
+ ulong mask = 1UL << which;
+
+ ulong v = _bitStorages[depth][ind];
+
+ _bitStorages[depth][ind] = v | mask;
+
+ if (v != 0)
+ {
+ break;
+ }
+
+ offset = (ulong)ind;
+ depth--;
+ }
+ }
+
+ private void ClearBit(int depth, ulong offset)
+ {
+ while (depth >= 0)
+ {
+ int ind = (int)(offset / UInt64BitSize);
+ int which = (int)(offset % UInt64BitSize);
+
+ ulong mask = 1UL << which;
+
+ ulong v = _bitStorages[depth][ind];
+
+ v &= ~mask;
+
+ _bitStorages[depth][ind] = v;
+
+ if (v != 0)
+ {
+ break;
+ }
+
+ offset = (ulong)ind;
+ depth--;
+ }
+ }
+
+ private static int GetRequiredDepth(ulong regionSize)
+ {
+ int depth = 0;
+
+ do
+ {
+ regionSize /= UInt64BitSize;
+ depth++;
+ }
+ while (regionSize != 0);
+
+ return depth;
+ }
+
+ public static int CalculateManagementOverheadSize(ulong regionSize)
+ {
+ int overheadBits = 0;
+
+ for (int depth = GetRequiredDepth(regionSize) - 1; depth >= 0; depth--)
+ {
+ regionSize = BitUtils.DivRoundUp(regionSize, UInt64BitSize);
+ overheadBits += (int)regionSize;
+ }
+
+ return overheadBits * sizeof(ulong);
+ }
+ }
+}