2 files changed, 254 insertions, 0 deletions

diff --git a/src/core/hle/kernel/memory/memory_block_manager.cpp b/src/core/hle/kernel/memory/memory_block_manager.cpp
new file mode 100644
index 000000000..da009566f
--- /dev/null
+++ b/src/core/hle/kernel/memory/memory_block_manager.cpp
@@ -0,0 +1,190 @@
+// Copyright 2020 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#include "core/hle/kernel/memory/memory_block_manager.h"
+#include "core/hle/kernel/memory/memory_types.h"
+
+namespace Kernel::Memory {
+
+MemoryBlockManager::MemoryBlockManager(VAddr start_addr, VAddr end_addr)
+    : start_addr{start_addr}, end_addr{end_addr} {
+    const u64 num_pages{(end_addr - start_addr) / PageSize};
+    memory_block_tree.emplace_back(start_addr, num_pages, MemoryState::Free, MemoryPermission::None,
+                                   MemoryAttribute::None);
+}
+
+MemoryBlockManager::iterator MemoryBlockManager::FindIterator(VAddr addr) {
+    iterator node{memory_block_tree.begin()};
+    while (node != end()) {
+        const VAddr end_addr{node->GetNumPages() * PageSize + node->GetAddress()};
+        if (node->GetAddress() <= addr && end_addr - 1 >= addr) {
+            return node;
+        }
+        node = std::next(node);
+    }
+    return end();
+}
+
+VAddr MemoryBlockManager::FindFreeArea(VAddr region_start, std::size_t region_num_pages,
+                                       std::size_t num_pages, std::size_t align, std::size_t offset,
+                                       std::size_t guard_pages) {
+    if (num_pages == 0) {
+        return {};
+    }
+
+    const VAddr region_end{region_start + region_num_pages * PageSize};
+    const VAddr region_last{region_end - 1};
+    for (const_iterator it{FindIterator(region_start)}; it != memory_block_tree.cend(); it++) {
+        const MemoryInfo info{it->GetMemoryInfo()};
+        if (region_last < info.GetAddress()) {
+            break;
+        }
+
+        if (info.state != MemoryState::Free) {
+            continue;
+        }
+
+        VAddr area{(info.GetAddress() <= region_start) ? region_start : info.GetAddress()};
+        area += guard_pages * PageSize;
+
+        const VAddr offset_area{Common::AlignDown(area, align) + offset};
+        area = (area <= offset_area) ? offset_area : offset_area + align;
+
+        const VAddr area_end{area + num_pages * PageSize + guard_pages * PageSize};
+        const VAddr area_last{area_end - 1};
+
+        if (info.GetAddress() <= area && area < area_last && area_last <= region_last &&
+            area_last <= info.GetLastAddress()) {
+            return area;
+        }
+    }
+
+    return {};
+}
+
+void MemoryBlockManager::Update(VAddr addr, std::size_t num_pages, MemoryState prev_state,
+                                MemoryPermission prev_perm, MemoryAttribute prev_attribute,
+                                MemoryState state, MemoryPermission perm,
+                                MemoryAttribute attribute) {
+    const std::size_t prev_count{memory_block_tree.size()};
+    const VAddr end_addr{addr + num_pages * PageSize};
+    iterator node{memory_block_tree.begin()};
+
+    prev_attribute |= MemoryAttribute::IpcAndDeviceMapped;
+
+    while (node != memory_block_tree.end()) {
+        MemoryBlock* block{&(*node)};
+        iterator next_node{std::next(node)};
+        const VAddr cur_addr{block->GetAddress()};
+        const VAddr cur_end_addr{block->GetNumPages() * PageSize + cur_addr};
+
+        if (addr < cur_end_addr && cur_addr < end_addr) {
+            if (!block->HasProperties(prev_state, prev_perm, prev_attribute)) {
+                node = next_node;
+                continue;
+            }
+
+            iterator new_node{node};
+            if (addr > cur_addr) {
+                memory_block_tree.insert(node, block->Split(addr));
+            }
+
+            if (end_addr < cur_end_addr) {
+                new_node = memory_block_tree.insert(node, block->Split(end_addr));
+            }
+
+            new_node->Update(state, perm, attribute);
+
+            MergeAdjacent(new_node, next_node);
+        }
+
+        if (cur_end_addr - 1 >= end_addr - 1) {
+            break;
+        }
+
+        node = next_node;
+    }
+}
+
+void MemoryBlockManager::Update(VAddr addr, std::size_t num_pages, MemoryState state,
+                                MemoryPermission perm, MemoryAttribute attribute) {
+    const std::size_t prev_count{memory_block_tree.size()};
+    const VAddr end_addr{addr + num_pages * PageSize};
+    iterator node{memory_block_tree.begin()};
+
+    while (node != memory_block_tree.end()) {
+        MemoryBlock* block{&(*node)};
+        iterator next_node{std::next(node)};
+        const VAddr cur_addr{block->GetAddress()};
+        const VAddr cur_end_addr{block->GetNumPages() * PageSize + cur_addr};
+
+        if (addr < cur_end_addr && cur_addr < end_addr) {
+            iterator new_node{node};
+
+            if (addr > cur_addr) {
+                memory_block_tree.insert(node, block->Split(addr));
+            }
+
+            if (end_addr < cur_end_addr) {
+                new_node = memory_block_tree.insert(node, block->Split(end_addr));
+            }
+
+            new_node->Update(state, perm, attribute);
+
+            MergeAdjacent(new_node, next_node);
+        }
+
+        if (cur_end_addr - 1 >= end_addr - 1) {
+            break;
+        }
+
+        node = next_node;
+    }
+}
+
+void MemoryBlockManager::IterateForRange(VAddr start, VAddr end, IterateFunc&& func) {
+    const_iterator it{FindIterator(start)};
+    MemoryInfo info{};
+    do {
+        info = it->GetMemoryInfo();
+        func(info);
+        it = std::next(it);
+    } while (info.addr + info.size - 1 < end - 1 && it != cend());
+}
+
+void MemoryBlockManager::MergeAdjacent(iterator it, iterator& next_it) {
+    MemoryBlock* block{&(*it)};
+
+    auto EraseIt = [&](const iterator it_to_erase) {
+        if (next_it == it_to_erase) {
+            next_it = std::next(next_it);
+        }
+        memory_block_tree.erase(it_to_erase);
+    };
+
+    if (it != memory_block_tree.begin()) {
+        MemoryBlock* prev{&(*std::prev(it))};
+
+        if (block->HasSameProperties(*prev)) {
+            const iterator prev_it{std::prev(it)};
+
+            prev->Add(block->GetNumPages());
+            EraseIt(it);
+
+            it = prev_it;
+            block = prev;
+        }
+    }
+
+    if (it != cend()) {
+        const MemoryBlock* const next{&(*std::next(it))};
+
+        if (block->HasSameProperties(*next)) {
+            block->Add(next->GetNumPages());
+            EraseIt(std::next(it));
+        }
+    }
+}
+
+} // namespace Kernel::Memory
diff --git a/src/core/hle/kernel/memory/memory_block_manager.h b/src/core/hle/kernel/memory/memory_block_manager.h
new file mode 100644
index 000000000..0f2270f0f
--- /dev/null
+++ b/src/core/hle/kernel/memory/memory_block_manager.h
@@ -0,0 +1,64 @@
+// Copyright 2020 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <functional>
+#include <list>
+#include <memory>
+
+#include "common/common_types.h"
+#include "core/hle/kernel/memory/memory_block.h"
+
+namespace Kernel::Memory {
+
+class MemoryBlockManager final {
+public:
+    using MemoryBlockTree = std::list<MemoryBlock>;
+    using iterator = MemoryBlockTree::iterator;
+    using const_iterator = MemoryBlockTree::const_iterator;
+
+public:
+    MemoryBlockManager(VAddr start_addr, VAddr end_addr);
+
+    iterator end() {
+        return memory_block_tree.end();
+    }
+    const_iterator end() const {
+        return memory_block_tree.end();
+    }
+    const_iterator cend() const {
+        return memory_block_tree.cend();
+    }
+
+    iterator FindIterator(VAddr addr);
+
+    VAddr FindFreeArea(VAddr region_start, std::size_t region_num_pages, std::size_t num_pages,
+                       std::size_t align, std::size_t offset, std::size_t guard_pages);
+
+    void Update(VAddr addr, std::size_t num_pages, MemoryState prev_state,
+                MemoryPermission prev_perm, MemoryAttribute prev_attribute, MemoryState state,
+                MemoryPermission perm, MemoryAttribute attribute);
+
+    void Update(VAddr addr, std::size_t num_pages, MemoryState state,
+                MemoryPermission perm = MemoryPermission::None,
+                MemoryAttribute attribute = MemoryAttribute::None);
+
+    using IterateFunc = std::function<void(const MemoryInfo&)>;
+    void IterateForRange(VAddr start, VAddr end, IterateFunc&& func);
+
+    MemoryBlock& FindBlock(VAddr addr) {
+        return *FindIterator(addr);
+    }
+
+private:
+    void MergeAdjacent(iterator it, iterator& next_it);
+
+    const VAddr start_addr;
+    const VAddr end_addr;
+
+    MemoryBlockTree memory_block_tree;
+};
+
+} // namespace Kernel::Memory