From 0cb9bc12fc80769676c48cb3fc173c4f46b7996e Mon Sep 17 00:00:00 2001
From: bunnei <bunneidev@gmail.com>
Date: Sat, 29 Oct 2022 13:55:30 -0700
Subject: core: hle: kernel: k_page_heap: Refresh.

---
 src/core/hle/kernel/k_page_heap.cpp | 86 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 84 insertions(+), 2 deletions(-)

(limited to 'src/core/hle/kernel/k_page_heap.cpp')

diff --git a/src/core/hle/kernel/k_page_heap.cpp b/src/core/hle/kernel/k_page_heap.cpp
index 5ede60168..7b02c7d8b 100644
--- a/src/core/hle/kernel/k_page_heap.cpp
+++ b/src/core/hle/kernel/k_page_heap.cpp
@@ -44,11 +44,11 @@ size_t KPageHeap::GetNumFreePages() const {
     return num_free;
 }
 
-PAddr KPageHeap::AllocateBlock(s32 index, bool random) {
+PAddr KPageHeap::AllocateByLinearSearch(s32 index) {
     const size_t needed_size = m_blocks[index].GetSize();
 
     for (s32 i = index; i < static_cast<s32>(m_num_blocks); i++) {
-        if (const PAddr addr = m_blocks[i].PopBlock(random); addr != 0) {
+        if (const PAddr addr = m_blocks[i].PopBlock(false); addr != 0) {
             if (const size_t allocated_size = m_blocks[i].GetSize(); allocated_size > needed_size) {
                 this->Free(addr + needed_size, (allocated_size - needed_size) / PageSize);
             }
@@ -59,6 +59,88 @@ PAddr KPageHeap::AllocateBlock(s32 index, bool random) {
     return 0;
 }
 
+PAddr KPageHeap::AllocateByRandom(s32 index, size_t num_pages, size_t align_pages) {
+    // Get the size and required alignment.
+    const size_t needed_size = num_pages * PageSize;
+    const size_t align_size = align_pages * PageSize;
+
+    // Determine meta-alignment of our desired alignment size.
+    const size_t align_shift = std::countr_zero(align_size);
+
+    // Decide on a block to allocate from.
+    constexpr size_t MinimumPossibleAlignmentsForRandomAllocation = 4;
+    {
+        // By default, we'll want to look at all blocks larger than our current one.
+        s32 max_blocks = static_cast<s32>(m_num_blocks);
+
+        // Determine the maximum block we should try to allocate from.
+        size_t possible_alignments = 0;
+        for (s32 i = index; i < max_blocks; ++i) {
+            // Add the possible alignments from blocks at the current size.
+            possible_alignments += (1 + ((m_blocks[i].GetSize() - needed_size) >> align_shift)) *
+                                   m_blocks[i].GetNumFreeBlocks();
+
+            // If there are enough possible alignments, we don't need to look at larger blocks.
+            if (possible_alignments >= MinimumPossibleAlignmentsForRandomAllocation) {
+                max_blocks = i + 1;
+                break;
+            }
+        }
+
+        // If we have any possible alignments which require a larger block, we need to pick one.
+        if (possible_alignments > 0 && index + 1 < max_blocks) {
+            // Select a random alignment from the possibilities.
+            const size_t rnd = m_rng.GenerateRandom(possible_alignments);
+
+            // Determine which block corresponds to the random alignment we chose.
+            possible_alignments = 0;
+            for (s32 i = index; i < max_blocks; ++i) {
+                // Add the possible alignments from blocks at the current size.
+                possible_alignments +=
+                    (1 + ((m_blocks[i].GetSize() - needed_size) >> align_shift)) *
+                    m_blocks[i].GetNumFreeBlocks();
+
+                // If the current block gets us to our random choice, use the current block.
+                if (rnd < possible_alignments) {
+                    index = i;
+                    break;
+                }
+            }
+        }
+    }
+
+    // Pop a block from the index we selected.
+    if (PAddr addr = m_blocks[index].PopBlock(true); addr != 0) {
+        // Determine how much size we have left over.
+        if (const size_t leftover_size = m_blocks[index].GetSize() - needed_size;
+            leftover_size > 0) {
+            // Determine how many valid alignments we can have.
+            const size_t possible_alignments = 1 + (leftover_size >> align_shift);
+
+            // Select a random valid alignment.
+            const size_t random_offset = m_rng.GenerateRandom(possible_alignments) << align_shift;
+
+            // Free memory before the random offset.
+            if (random_offset != 0) {
+                this->Free(addr, random_offset / PageSize);
+            }
+
+            // Advance our block by the random offset.
+            addr += random_offset;
+
+            // Free memory after our allocated block.
+            if (random_offset != leftover_size) {
+                this->Free(addr + needed_size, (leftover_size - random_offset) / PageSize);
+            }
+        }
+
+        // Return the block we allocated.
+        return addr;
+    }
+
+    return 0;
+}
+
 void KPageHeap::FreeBlock(PAddr block, s32 index) {
     do {
         block = m_blocks[index++].PushBlock(block);
-- 
cgit v1.2.3