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
author: gdkchan <gab.dark.100@gmail.com> 2022-06-22 12:28:14 -0300
committer: GitHub <noreply@github.com> 2022-06-22 12:28:14 -0300
commit: f2a41b7a1cad027cc1f1f8f687cda6ab42030eb9 (patch)
tree: 0e128bb17fe36bce8f1924a62b9ae516adbfdd30
parent: c881cd2d1452dc6ad87a570db76139a0c6105132 (diff)
7 files changed, 671 insertions, 475 deletions
diff --git a/Ryujinx.Common/Utilities/BitUtils.cs b/Ryujinx.Common/Utilities/BitUtils.cs
index b231886f..5c68dc9e 100644
--- a/Ryujinx.Common/Utilities/BitUtils.cs
+++ b/Ryujinx.Common/Utilities/BitUtils.cs
@@ -22,7 +22,17 @@ namespace Ryujinx.Common
 
         public static long AlignUp(long value, int size)
         {
-            return (value + (size - 1)) & -(long)size;
+            return AlignUp(value, (long)size);
+        }
+
+        public static ulong AlignUp(ulong value, ulong size)
+        {
+            return (ulong)AlignUp((long)value, (long)size);
+        }
+
+        public static long AlignUp(long value, long size)
+        {
+            return (value + (size - 1)) & -size;
         }
 
         public static uint AlignDown(uint value, int size)
@@ -42,7 +52,17 @@ namespace Ryujinx.Common
 
         public static long AlignDown(long value, int size)
         {
-            return value & -(long)size;
+            return AlignDown(value, (long)size);
+        }
+
+        public static ulong AlignDown(ulong value, ulong size)
+        {
+            return (ulong)AlignDown((long)value, (long)size);
+        }
+
+        public static long AlignDown(long value, long size)
+        {
+            return value & -size;
         }
 
         public static int DivRoundUp(int value, int dividend)
diff --git a/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryRegionBlock.cs b/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryRegionBlock.cs
deleted file mode 100644
index 9a773495..00000000
--- a/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryRegionBlock.cs
+++ /dev/null
@@ -1,87 +0,0 @@
-namespace Ryujinx.HLE.HOS.Kernel.Memory
-{
-    class KMemoryRegionBlock
-    {
-        public long[][] Masks;
-
-        public ulong FreeCount;
-        public int   MaxLevel;
-        public ulong StartAligned;
-        public ulong SizeInBlocksTruncated;
-        public ulong SizeInBlocksRounded;
-        public int   Order;
-        public int   NextOrder;
-
-        public bool TryCoalesce(int index, int count)
-        {
-            long mask = ((1L << count) - 1) << (index & 63);
-
-            index /= 64;
-
-            if (count >= 64)
-            {
-                int remaining = count;
-                int tempIdx = index;
-
-                do
-                {
-                    if (Masks[MaxLevel - 1][tempIdx++] != -1L)
-                    {
-                        return false;
-                    }
-
-                    remaining -= 64;
-                }
-                while (remaining != 0);
-
-                remaining = count;
-                tempIdx = index;
-
-                do
-                {
-                    Masks[MaxLevel - 1][tempIdx] = 0;
-
-                    ClearMaskBit(MaxLevel - 2, tempIdx++);
-
-                    remaining -= 64;
-                }
-                while (remaining != 0);
-            }
-            else
-            {
-                long value = Masks[MaxLevel - 1][index];
-
-                if ((mask & ~value) != 0)
-                {
-                    return false;
-                }
-
-                value &= ~mask;
-
-                Masks[MaxLevel - 1][index] = value;
-
-                if (value == 0)
-                {
-                    ClearMaskBit(MaxLevel - 2, index);
-                }
-            }
-
-            FreeCount -= (ulong)count;
-
-            return true;
-        }
-
-        public void ClearMaskBit(int startLevel, int index)
-        {
-            for (int level = startLevel; level >= 0; level--, index /= 64)
-            {
-                Masks[level][index / 64] &= ~(1L << (index & 63));
-
-                if (Masks[level][index / 64] != 0)
-                {
-                    break;
-                }
-            }
-        }
-    }
-}
-\ No newline at end of file
diff --git a/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryRegionManager.cs b/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryRegionManager.cs
index 43e3e820..43d48946 100644
--- a/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryRegionManager.cs
+++ b/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryRegionManager.cs
@@ -1,102 +1,42 @@
-using Ryujinx.Common;
 using Ryujinx.HLE.HOS.Kernel.Common;
 using System.Diagnostics;
-using System.Numerics;
 
 namespace Ryujinx.HLE.HOS.Kernel.Memory
 {
     class KMemoryRegionManager
     {
-        private static readonly int[] BlockOrders = new int[] { 12, 16, 21, 22, 25, 29, 30 };
+        private readonly KPageHeap _pageHeap;
 
-        public ulong Address { get; private set; }
-        public ulong EndAddr { get; private set; }
-        public ulong Size    { get; private set; }
-
-        private int _blockOrdersCount;
-
-        private readonly KMemoryRegionBlock[] _blocks;
+        public ulong Address { get; }
+        public ulong Size { get; }
+        public ulong EndAddr => Address + Size;
 
         private readonly ushort[] _pageReferenceCounts;
 
         public KMemoryRegionManager(ulong address, ulong size, ulong endAddr)
         {
-            _blocks = new KMemoryRegionBlock[BlockOrders.Length];
-
             Address = address;
-            Size    = size;
-            EndAddr = endAddr;
-
-            _blockOrdersCount = BlockOrders.Length;
-
-            for (int blockIndex = 0; blockIndex < _blockOrdersCount; blockIndex++)
-            {
-                _blocks[blockIndex] = new KMemoryRegionBlock();
-
-                _blocks[blockIndex].Order = BlockOrders[blockIndex];
-
-                int nextOrder = blockIndex == _blockOrdersCount - 1 ? 0 : BlockOrders[blockIndex + 1];
-
-                _blocks[blockIndex].NextOrder = nextOrder;
-
-                int currBlockSize = 1 << BlockOrders[blockIndex];
-                int nextBlockSize = currBlockSize;
-
-                if (nextOrder != 0)
-                {
-                    nextBlockSize = 1 << nextOrder;
-                }
-
-                ulong startAligned   = BitUtils.AlignDown(address, nextBlockSize);
-                ulong endAddrAligned = BitUtils.AlignDown(endAddr, currBlockSize);
-
-                ulong sizeInBlocksTruncated = (endAddrAligned - startAligned) >> BlockOrders[blockIndex];
-
-                ulong endAddrRounded = BitUtils.AlignUp(address + size, nextBlockSize);
-
-                ulong sizeInBlocksRounded = (endAddrRounded - startAligned) >> BlockOrders[blockIndex];
-
-                _blocks[blockIndex].StartAligned          = startAligned;
-                _blocks[blockIndex].SizeInBlocksTruncated = sizeInBlocksTruncated;
-                _blocks[blockIndex].SizeInBlocksRounded   = sizeInBlocksRounded;
-
-                ulong currSizeInBlocks = sizeInBlocksRounded;
-
-                int maxLevel = 0;
-
-                do
-                {
-                    maxLevel++;
-                }
-                while ((currSizeInBlocks /= 64) != 0);
-
-                _blocks[blockIndex].MaxLevel = maxLevel;
-
-                _blocks[blockIndex].Masks = new long[maxLevel][];
-
-                currSizeInBlocks = sizeInBlocksRounded;
-
-                for (int level = maxLevel - 1; level >= 0; level--)
-                {
-                    currSizeInBlocks = (currSizeInBlocks + 63) / 64;
-
-                    _blocks[blockIndex].Masks[level] = new long[currSizeInBlocks];
-                }
-            }
+            Size = size;
 
             _pageReferenceCounts = new ushort[size / KPageTableBase.PageSize];
 
-            if (size != 0)
-            {
-                FreePages(address, size / KPageTableBase.PageSize);
-            }
+            _pageHeap = new KPageHeap(address, size);
+            _pageHeap.Free(address, size / KPageTableBase.PageSize);
+            _pageHeap.UpdateUsedSize();
         }
 
-        public KernelResult AllocatePages(ulong pagesCount, bool backwards, out KPageList pageList)
+        public KernelResult AllocatePages(out KPageList pageList, ulong pagesCount)
         {
-            lock (_blocks)
+            if (pagesCount == 0)
+            {
+                pageList = new KPageList();
+
+                return KernelResult.Success;
+            }
+
+            lock (_pageHeap)
             {
-                KernelResult result = AllocatePagesImpl(pagesCount, backwards, out pageList);
+                KernelResult result = AllocatePagesImpl(out pageList, pagesCount, false);
 
                 if (result == KernelResult.Success)
                 {
@@ -112,9 +52,14 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
 
         public ulong AllocatePagesContiguous(KernelContext context, ulong pagesCount, bool backwards)
         {
-            lock (_blocks)
+            if (pagesCount == 0)
+            {
+                return 0;
+            }
+
+            lock (_pageHeap)
             {
-                ulong address = AllocatePagesContiguousImpl(pagesCount, backwards);
+                ulong address = AllocatePagesContiguousImpl(pagesCount, 1, backwards);
 
                 if (address != 0)
                 {
@@ -126,371 +71,108 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
             }
         }
 
-        private KernelResult AllocatePagesImpl(ulong pagesCount, bool backwards, out KPageList pageList)
+        private KernelResult AllocatePagesImpl(out KPageList pageList, ulong pagesCount, bool random)
         {
             pageList = new KPageList();
 
-            if (_blockOrdersCount > 0)
-            {
-                if (GetFreePagesImpl() < pagesCount)
-                {
-                    return KernelResult.OutOfMemory;
-                }
-            }
-            else if (pagesCount != 0)
+            int heapIndex = KPageHeap.GetBlockIndex(pagesCount);
+
+            if (heapIndex < 0)
             {
                 return KernelResult.OutOfMemory;
             }
 
-            for (int blockIndex = _blockOrdersCount - 1; blockIndex >= 0; blockIndex--)
+            for (int index = heapIndex; index >= 0; index--)
             {
-                KMemoryRegionBlock block = _blocks[blockIndex];
-
-                ulong bestFitBlockSize = 1UL << block.Order;
-
-                ulong blockPagesCount = bestFitBlockSize / KPageTableBase.PageSize;
+                ulong pagesPerAlloc = KPageHeap.GetBlockPagesCount(index);
 
-                // Check if this is the best fit for this page size.
-                // If so, try allocating as much requested pages as possible.
-                while (blockPagesCount <= pagesCount)
+                while (pagesCount >= pagesPerAlloc)
                 {
-                    ulong address = AllocatePagesForOrder(blockIndex, backwards, bestFitBlockSize);
+                    ulong allocatedBlock = _pageHeap.AllocateBlock(index, random);
 
-                    // The address being zero means that no free space was found on that order,
-                    // just give up and try with the next one.
-                    if (address == 0)
+                    if (allocatedBlock == 0)
                     {
                         break;
                     }
 
-                    // Add new allocated page(s) to the pages list.
-                    // If an error occurs, then free all allocated pages and fail.
-                    KernelResult result = pageList.AddRange(address, blockPagesCount);
+                    KernelResult result = pageList.AddRange(allocatedBlock, pagesPerAlloc);
 
                     if (result != KernelResult.Success)
                     {
-                        FreePages(address, blockPagesCount);
-
-                        foreach (KPageNode pageNode in pageList)
-                        {
-                            FreePages(pageNode.Address, pageNode.PagesCount);
-                        }
+                        FreePages(pageList);
+                        _pageHeap.Free(allocatedBlock, pagesPerAlloc);
 
                         return result;
                     }
 
-                    pagesCount -= blockPagesCount;
+                    pagesCount -= pagesPerAlloc;
                 }
             }
 
-            // Success case, all requested pages were allocated successfully.
-            if (pagesCount == 0)
+            if (pagesCount != 0)
             {
-                return KernelResult.Success;
-            }
+                FreePages(pageList);
 
-            // Error case, free allocated pages and return out of memory.
-            foreach (KPageNode pageNode in pageList)
-            {
-                FreePages(pageNode.Address, pageNode.PagesCount);
+                return KernelResult.OutOfMemory;
             }
 
-            pageList = null;
-
-            return KernelResult.OutOfMemory;
+            return KernelResult.Success;
         }
 
-        private ulong AllocatePagesContiguousImpl(ulong pagesCount, bool backwards)
+        private ulong AllocatePagesContiguousImpl(ulong pagesCount, ulong alignPages, bool random)
         {
-            if (pagesCount == 0 || _blocks.Length < 1)
-            {
-                return 0;
-            }
+            int heapIndex = KPageHeap.GetAlignedBlockIndex(pagesCount, alignPages);
 
-            int blockIndex = 0;
+            ulong allocatedBlock = _pageHeap.AllocateBlock(heapIndex, random);
 
-            while ((1UL << _blocks[blockIndex].Order) / KPageTableBase.PageSize < pagesCount)
+            if (allocatedBlock == 0)
             {
-                if (++blockIndex >= _blocks.Length)
-                {
-                    return 0;
-                }
+                return 0;
             }
 
-            ulong tightestFitBlockSize = 1UL << _blocks[blockIndex].Order;
-
-            ulong address = AllocatePagesForOrder(blockIndex, backwards, tightestFitBlockSize);
-
-            ulong requiredSize = pagesCount * KPageTableBase.PageSize;
+            ulong allocatedPages = KPageHeap.GetBlockPagesCount(heapIndex);
 
-            if (address != 0 && tightestFitBlockSize > requiredSize)
+            if (allocatedPages > pagesCount)
             {
-                FreePages(address + requiredSize, (tightestFitBlockSize - requiredSize) / KPageTableBase.PageSize);
+                _pageHeap.Free(allocatedBlock + pagesCount * KPageTableBase.PageSize, allocatedPages - pagesCount);
             }
 
-            return address;
+            return allocatedBlock;
         }
 
-        private ulong AllocatePagesForOrder(int blockIndex, bool backwards, ulong bestFitBlockSize)
+        public void FreePage(ulong address)
         {
-            ulong address = 0;
-
-            KMemoryRegionBlock block = null;
-
-            for (int currBlockIndex = blockIndex;
-                     currBlockIndex < _blockOrdersCount && address == 0;
-                     currBlockIndex++)
+            lock (_pageHeap)
             {
-                block = _blocks[currBlockIndex];
-
-                int index = 0;
-
-                bool zeroMask = false;
-
-                for (int level = 0; level < block.MaxLevel; level++)
-                {
-                    long mask = block.Masks[level][index];
-
-                    if (mask == 0)
-                    {
-                        zeroMask = true;
-
-                        break;
-                    }
-
-                    if (backwards)
-                    {
-                        index = (index * 64 + 63) - BitOperations.LeadingZeroCount((ulong)mask);
-                    }
-                    else
-                    {
-                        index = index * 64 + BitOperations.LeadingZeroCount((ulong)BitUtils.ReverseBits64(mask));
-                    }
-                }
-
-                if (block.SizeInBlocksTruncated <= (ulong)index || zeroMask)
-                {
-                    continue;
-                }
-
-                block.FreeCount--;
-
-                int tempIdx = index;
-
-                for (int level = block.MaxLevel - 1; level >= 0; level--, tempIdx /= 64)
-                {
-                    block.Masks[level][tempIdx / 64] &= ~(1L << (tempIdx & 63));
-
-                    if (block.Masks[level][tempIdx / 64] != 0)
-                    {
-                        break;
-                    }
-                }
-
-                address = block.StartAligned + ((ulong)index << block.Order);
+                _pageHeap.Free(address, 1);
             }
-
-            for (int currBlockIndex = blockIndex;
-                     currBlockIndex < _blockOrdersCount && address == 0;
-                     currBlockIndex++)
-            {
-                block = _blocks[currBlockIndex];
-
-                int index = 0;
-
-                bool zeroMask = false;
-
-                for (int level = 0; level < block.MaxLevel; level++)
-                {
-                    long mask = block.Masks[level][index];
-
-                    if (mask == 0)
-                    {
-                        zeroMask = true;
-
-                        break;
-                    }
-
-                    if (backwards)
-                    {
-                        index = index * 64 + BitOperations.LeadingZeroCount((ulong)BitUtils.ReverseBits64(mask));
-                    }
-                    else
-                    {
-                        index = (index * 64 + 63) - BitOperations.LeadingZeroCount((ulong)mask);
-                    }
-                }
-
-                if (block.SizeInBlocksTruncated <= (ulong)index || zeroMask)
-                {
-                    continue;
-                }
-
-                block.FreeCount--;
-
-                int tempIdx = index;
-
-                for (int level = block.MaxLevel - 1; level >= 0; level--, tempIdx /= 64)
-                {
-                    block.Masks[level][tempIdx / 64] &= ~(1L << (tempIdx & 63));
-
-                    if (block.Masks[level][tempIdx / 64] != 0)
-                    {
-                        break;
-                    }
-                }
-
-                address = block.StartAligned + ((ulong)index << block.Order);
-            }
-
-            if (address != 0)
-            {
-                // If we are using a larger order than best fit, then we should
-                // split it into smaller blocks.
-                ulong firstFreeBlockSize = 1UL << block.Order;
-
-                if (firstFreeBlockSize > bestFitBlockSize)
-                {
-                    FreePages(address + bestFitBlockSize, (firstFreeBlockSize - bestFitBlockSize) / KPageTableBase.PageSize);
-                }
-            }
-
-            return address;
         }
 
-        private void FreePages(ulong address, ulong pagesCount)
+        public void FreePages(KPageList pageList)
         {
-            lock (_blocks)
+            lock (_pageHeap)
             {
-                ulong endAddr = address + pagesCount * KPageTableBase.PageSize;
-
-                int blockIndex = _blockOrdersCount - 1;
-
-                ulong addressRounded   = 0;
-                ulong endAddrTruncated = 0;
-
-                for (; blockIndex >= 0; blockIndex--)
-                {
-                    KMemoryRegionBlock allocInfo = _blocks[blockIndex];
-
-                    int blockSize = 1 << allocInfo.Order;
-
-                    addressRounded   = BitUtils.AlignUp  (address, blockSize);
-                    endAddrTruncated = BitUtils.AlignDown(endAddr, blockSize);
-
-                    if (addressRounded < endAddrTruncated)
-                    {
-                        break;
-                    }
-                }
-
-                void FreeRegion(ulong currAddress)
-                {
-                    for (int currBlockIndex = blockIndex;
-                            currBlockIndex < _blockOrdersCount && currAddress != 0;
-                            currBlockIndex++)
-                    {
-                        KMemoryRegionBlock block = _blocks[currBlockIndex];
-
-                        block.FreeCount++;
-
-                        ulong freedBlocks = (currAddress - block.StartAligned) >> block.Order;
-
-                        int index = (int)freedBlocks;
-
-                        for (int level = block.MaxLevel - 1; level >= 0; level--, index /= 64)
-                        {
-                            long mask = block.Masks[level][index / 64];
-
-                            block.Masks[level][index / 64] = mask | (1L << (index & 63));
-
-                            if (mask != 0)
-                            {
-                                break;
-                            }
-                        }
-
-                        int blockSizeDelta = 1 << (block.NextOrder - block.Order);
-
-                        int freedBlocksTruncated = BitUtils.AlignDown((int)freedBlocks, blockSizeDelta);
-
-                        if (!block.TryCoalesce(freedBlocksTruncated, blockSizeDelta))
-                        {
-                            break;
-                        }
-
-                        currAddress = block.StartAligned + ((ulong)freedBlocksTruncated << block.Order);
-                    }
-                }
-
-                // Free inside aligned region.
-                ulong baseAddress = addressRounded;
-
-                while (baseAddress < endAddrTruncated)
+                foreach (KPageNode pageNode in pageList)
                 {
-                    ulong blockSize = 1UL << _blocks[blockIndex].Order;
-
-                    FreeRegion(baseAddress);
-
-                    baseAddress += blockSize;
-                }
-
-                int nextBlockIndex = blockIndex - 1;
-
-                // Free region between Address and aligned region start.
-                baseAddress = addressRounded;
-
-                for (blockIndex = nextBlockIndex; blockIndex >= 0; blockIndex--)
-                {
-                    ulong blockSize = 1UL << _blocks[blockIndex].Order;
-
-                    while (baseAddress - blockSize >= address)
-                    {
-                        baseAddress -= blockSize;
-
-                        FreeRegion(baseAddress);
-                    }
-                }
-
-                // Free region between aligned region end and End Address.
-                baseAddress = endAddrTruncated;
-
-                for (blockIndex = nextBlockIndex; blockIndex >= 0; blockIndex--)
-                {
-                    ulong blockSize = 1UL << _blocks[blockIndex].Order;
-
-                    while (baseAddress + blockSize <= endAddr)
-                    {
-                        FreeRegion(baseAddress);
-
-                        baseAddress += blockSize;
-                    }
+                    _pageHeap.Free(pageNode.Address, pageNode.PagesCount);
                 }
             }
         }
 
-        public ulong GetFreePages()
+        public void FreePages(ulong address, ulong pagesCount)
         {
-            lock (_blocks)
+            lock (_pageHeap)
             {
-                return GetFreePagesImpl();
+                _pageHeap.Free(address, pagesCount);
             }
         }
 
-        private ulong GetFreePagesImpl()
+        public ulong GetFreePages()
         {
-            ulong availablePages = 0;
-
-            for (int blockIndex = 0; blockIndex < _blockOrdersCount; blockIndex++)
+            lock (_pageHeap)
             {
-                KMemoryRegionBlock block = _blocks[blockIndex];
-
-                ulong blockPagesCount = (1UL << block.Order) / KPageTableBase.PageSize;
-
-                availablePages += blockPagesCount * block.FreeCount;
+                return _pageHeap.GetFreePagesCount();
             }
-
-            return availablePages;
         }
 
         public void IncrementPagesReferenceCount(ulong address, ulong pagesCount)
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);
+        }
+    }
+}
diff --git a/Ryujinx.HLE/HOS/Kernel/Memory/KPageHeap.cs b/Ryujinx.HLE/HOS/Kernel/Memory/KPageHeap.cs
new file mode 100644
index 00000000..39ecfdea
--- /dev/null
+++ b/Ryujinx.HLE/HOS/Kernel/Memory/KPageHeap.cs
@@ -0,0 +1,283 @@
+using Ryujinx.Common;
+using System;
+
+namespace Ryujinx.HLE.HOS.Kernel.Memory
+{
+    class KPageHeap
+    {
+        private class Block
+        {
+            private KPageBitmap _bitmap = new KPageBitmap();
+            private ulong _heapAddress;
+            private ulong _endOffset;
+
+            public int Shift { get; private set; }
+            public int NextShift { get; private set; }
+            public ulong Size => 1UL << Shift;
+            public int PagesCount => (int)(Size / KPageTableBase.PageSize);
+            public int FreeBlocksCount => _bitmap.BitsCount;
+            public int FreePagesCount => FreeBlocksCount * PagesCount;
+
+            public ArraySegment<ulong> Initialize(ulong address, ulong size, int blockShift, int nextBlockShift, ArraySegment<ulong> bitStorage)
+            {
+                Shift = blockShift;
+                NextShift = nextBlockShift;
+
+                ulong endAddress = address + size;
+
+                ulong align = nextBlockShift != 0
+                    ? 1UL << nextBlockShift
+                    : 1UL << blockShift;
+
+                address    = BitUtils.AlignDown(address,    align);
+                endAddress = BitUtils.AlignUp  (endAddress, align);
+
+                _heapAddress = address;
+                _endOffset = (endAddress - address) / (1UL << blockShift);
+
+                return _bitmap.Initialize(bitStorage, _endOffset);
+            }
+
+            public ulong PushBlock(ulong address)
+            {
+                ulong offset = (address - _heapAddress) >> Shift;
+
+                _bitmap.SetBit(offset);
+
+                if (NextShift != 0)
+                {
+                    int diff = 1 << (NextShift - Shift);
+
+                    offset = BitUtils.AlignDown(offset, diff);
+
+                    if (_bitmap.ClearRange(offset, diff))
+                    {
+                        return _heapAddress + (offset << Shift);
+                    }
+                }
+
+                return 0;
+            }
+
+            public ulong PopBlock(bool random)
+            {
+                long sOffset = (long)_bitmap.FindFreeBlock(random);
+
+                if (sOffset < 0L)
+                {
+                    return 0;
+                }
+
+                ulong offset = (ulong)sOffset;
+
+                _bitmap.ClearBit(offset);
+
+                return _heapAddress + (offset << Shift);
+            }
+
+            public static int CalculateManagementOverheadSize(ulong regionSize, int currBlockShift, int nextBlockShift)
+            {
+                ulong currBlockSize = 1UL << currBlockShift;
+                ulong nextBlockSize = 1UL << nextBlockShift;
+                ulong align = nextBlockShift != 0 ? nextBlockSize : currBlockSize;
+                return KPageBitmap.CalculateManagementOverheadSize((align * 2 + BitUtils.AlignUp(regionSize, align)) / currBlockSize);
+            }
+        }
+
+        private static readonly int[] _memoryBlockPageShifts = new int[] { 12, 16, 21, 22, 25, 29, 30 };
+
+        private readonly ulong _heapAddress;
+        private readonly ulong _heapSize;
+        private ulong _usedSize;
+        private readonly int _blocksCount;
+        private readonly Block[] _blocks;
+
+        public KPageHeap(ulong address, ulong size) : this(address, size, _memoryBlockPageShifts)
+        {
+        }
+
+        public KPageHeap(ulong address, ulong size, int[] blockShifts)
+        {
+            _heapAddress = address;
+            _heapSize = size;
+            _blocksCount = blockShifts.Length;
+            _blocks = new Block[_memoryBlockPageShifts.Length];
+
+            var currBitmapStorage = new ArraySegment<ulong>(new ulong[CalculateManagementOverheadSize(size, blockShifts)]);
+
+            for (int i = 0; i < blockShifts.Length; i++)
+            {
+                int currBlockShift = blockShifts[i];
+                int nextBlockShift = i != blockShifts.Length - 1 ? blockShifts[i + 1] : 0;
+
+                _blocks[i] = new Block();
+
+                currBitmapStorage = _blocks[i].Initialize(address, size, currBlockShift, nextBlockShift, currBitmapStorage);
+            }
+        }
+
+        public void UpdateUsedSize()
+        {
+            _usedSize = _heapSize - (GetFreePagesCount() * KPageTableBase.PageSize);
+        }
+
+        public ulong GetFreePagesCount()
+        {
+            ulong freeCount = 0;
+
+            for (int i = 0; i < _blocksCount; i++)
+            {
+                freeCount += (ulong)_blocks[i].FreePagesCount;
+            }
+
+            return freeCount;
+        }
+
+        public ulong AllocateBlock(int index, bool random)
+        {
+            ulong neededSize = _blocks[index].Size;
+
+            for (int i = index; i < _blocksCount; i++)
+            {
+                ulong address = _blocks[i].PopBlock(random);
+
+                if (address != 0)
+                {
+                    ulong allocatedSize = _blocks[i].Size;
+
+                    if (allocatedSize > neededSize)
+                    {
+                        Free(address + neededSize, (allocatedSize - neededSize) / KPageTableBase.PageSize);
+                    }
+
+                    return address;
+                }
+            }
+
+            return 0;
+        }
+
+        private void FreeBlock(ulong block, int index)
+        {
+            do
+            {
+                block = _blocks[index++].PushBlock(block);
+            }
+            while (block != 0);
+        }
+
+        public void Free(ulong address, ulong pagesCount)
+        {
+            if (pagesCount == 0)
+            {
+                return;
+            }
+
+            int bigIndex = _blocksCount - 1;
+
+            ulong start       = address;
+            ulong end         = address + pagesCount * KPageTableBase.PageSize;
+            ulong beforeStart = start;
+            ulong beforeEnd   = start;
+            ulong afterStart  = end;
+            ulong afterEnd    = end;
+
+            while (bigIndex >= 0)
+            {
+                ulong blockSize = _blocks[bigIndex].Size;
+
+                ulong bigStart = BitUtils.AlignUp  (start, blockSize);
+                ulong bigEnd   = BitUtils.AlignDown(end,   blockSize);
+
+                if (bigStart < bigEnd)
+                {
+                    for (ulong block = bigStart; block < bigEnd; block += blockSize)
+                    {
+                        FreeBlock(block, bigIndex);
+                    }
+
+                    beforeEnd  = bigStart;
+                    afterStart = bigEnd;
+
+                    break;
+                }
+
+                bigIndex--;
+            }
+
+            for (int i = bigIndex - 1; i >= 0; i--)
+            {
+                ulong blockSize = _blocks[i].Size;
+
+                while (beforeStart + blockSize <= beforeEnd)
+                {
+                    beforeEnd -= blockSize;
+                    FreeBlock(beforeEnd, i);
+                }
+            }
+
+            for (int i = bigIndex - 1; i >= 0; i--)
+            {
+                ulong blockSize = _blocks[i].Size;
+
+                while (afterStart + blockSize <= afterEnd)
+                {
+                    FreeBlock(afterStart, i);
+                    afterStart += blockSize;
+                }
+            }
+        }
+
+        public static int GetAlignedBlockIndex(ulong pagesCount, ulong alignPages)
+        {
+            ulong targetPages = Math.Max(pagesCount, alignPages);
+
+            for (int i = 0; i < _memoryBlockPageShifts.Length; i++)
+            {
+                if (targetPages <= GetBlockPagesCount(i))
+                {
+                    return i;
+                }
+            }
+
+            return -1;
+        }
+
+        public static int GetBlockIndex(ulong pagesCount)
+        {
+            for (int i = _memoryBlockPageShifts.Length - 1; i >= 0; i--)
+            {
+                if (pagesCount >= GetBlockPagesCount(i))
+                {
+                    return i;
+                }
+            }
+
+            return -1;
+        }
+
+        public static ulong GetBlockSize(int index)
+        {
+            return 1UL << _memoryBlockPageShifts[index];
+        }
+
+        public static ulong GetBlockPagesCount(int index)
+        {
+            return GetBlockSize(index) / KPageTableBase.PageSize;
+        }
+
+        private static int CalculateManagementOverheadSize(ulong regionSize, int[] blockShifts)
+        {
+            int overheadSize = 0;
+
+            for (int i = 0; i < blockShifts.Length; i++)
+            {
+                int currBlockShift = blockShifts[i];
+                int nextBlockShift = i != blockShifts.Length - 1 ? blockShifts[i + 1] : 0;
+                overheadSize += Block.CalculateManagementOverheadSize(regionSize, currBlockShift, nextBlockShift);
+            }
+
+            return BitUtils.AlignUp(overheadSize, KPageTableBase.PageSize);
+        }
+    }
+}
diff --git a/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs b/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs
index 94e8fb6a..ab43b477 100644
--- a/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs
+++ b/Ryujinx.HLE/HOS/Kernel/Memory/KPageTableBase.cs
@@ -555,7 +555,7 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
         {
             KMemoryRegionManager region = GetMemoryRegionManager();
 
-            KernelResult result = region.AllocatePages(pagesCount, _aslrDisabled, out KPageList pageList);
+            KernelResult result = region.AllocatePages(out KPageList pageList, pagesCount);
 
             if (result != KernelResult.Success)
             {
@@ -712,7 +712,7 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
 
                     KMemoryRegionManager region = GetMemoryRegionManager();
 
-                    KernelResult result = region.AllocatePages(pagesCount, _aslrDisabled, out KPageList pageList);
+                    KernelResult result = region.AllocatePages(out KPageList pageList, pagesCount);
 
                     using var _ = new OnScopeExit(() => pageList.DecrementPagesReferenceCount(Context.MemoryManager));
 
@@ -1276,7 +1276,7 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
 
                 KMemoryRegionManager region = GetMemoryRegionManager();
 
-                KernelResult result = region.AllocatePages(remainingPages, _aslrDisabled, out KPageList pageList);
+                KernelResult result = region.AllocatePages(out KPageList pageList, remainingPages);
 
                 using var _ = new OnScopeExit(() => pageList.DecrementPagesReferenceCount(Context.MemoryManager));
 
diff --git a/Ryujinx.HLE/HOS/ProgramLoader.cs b/Ryujinx.HLE/HOS/ProgramLoader.cs
index 6b9b6820..66fa20fa 100644
--- a/Ryujinx.HLE/HOS/ProgramLoader.cs
+++ b/Ryujinx.HLE/HOS/ProgramLoader.cs
@@ -90,7 +90,7 @@ namespace Ryujinx.HLE.HOS
 
             KMemoryRegionManager region = context.MemoryManager.MemoryRegions[(int)memoryRegion];
 
-            KernelResult result = region.AllocatePages((ulong)codePagesCount, false, out KPageList pageList);
+            KernelResult result = region.AllocatePages(out KPageList pageList, (ulong)codePagesCount);
 
             if (result != KernelResult.Success)
             {
author	gdkchan <gab.dark.100@gmail.com>	2022-06-22 12:28:14 -0300
committer	GitHub <noreply@github.com>	2022-06-22 12:28:14 -0300
commit	f2a41b7a1cad027cc1f1f8f687cda6ab42030eb9 (patch)
tree	0e128bb17fe36bce8f1924a62b9ae516adbfdd30
parent	c881cd2d1452dc6ad87a570db76139a0c6105132 (diff)