1 files changed, 338 insertions, 0 deletions

diff --git a/src/common/address_space.inc b/src/common/address_space.inc
new file mode 100644
index 000000000..907c55d88
--- /dev/null
+++ b/src/common/address_space.inc
@@ -0,0 +1,338 @@
+// SPDX-License-Identifier: GPLv3 or later
+// Copyright © 2021 Skyline Team and Contributors (https://github.com/skyline-emu/)
+
+#include "common/address_space.h"
+#include "common/assert.h"
+
+#define MAP_MEMBER(returnType)                                                                     \
+    template <typename VaType, VaType UnmappedVa, typename PaType, PaType UnmappedPa,              \
+              bool PaContigSplit, size_t AddressSpaceBits, typename ExtraBlockInfo>                \
+    requires AddressSpaceValid<VaType, AddressSpaceBits> returnType FlatAddressSpaceMap<           \
+        VaType, UnmappedVa, PaType, UnmappedPa, PaContigSplit, AddressSpaceBits, ExtraBlockInfo>
+#define MAP_MEMBER_CONST()                                                                         \
+    template <typename VaType, VaType UnmappedVa, typename PaType, PaType UnmappedPa,              \
+              bool PaContigSplit, size_t AddressSpaceBits, typename ExtraBlockInfo>                \
+    requires AddressSpaceValid<VaType, AddressSpaceBits> FlatAddressSpaceMap<                      \
+        VaType, UnmappedVa, PaType, UnmappedPa, PaContigSplit, AddressSpaceBits, ExtraBlockInfo>
+
+#define MM_MEMBER(returnType)                                                                      \
+    template <typename VaType, VaType UnmappedVa, size_t AddressSpaceBits>                         \
+    requires AddressSpaceValid<VaType, AddressSpaceBits> returnType                                \
+        FlatMemoryManager<VaType, UnmappedVa, AddressSpaceBits>
+
+#define ALLOC_MEMBER(returnType)                                                                   \
+    template <typename VaType, VaType UnmappedVa, size_t AddressSpaceBits>                         \
+    requires AddressSpaceValid<VaType, AddressSpaceBits> returnType                                \
+        FlatAllocator<VaType, UnmappedVa, AddressSpaceBits>
+#define ALLOC_MEMBER_CONST()                                                                       \
+    template <typename VaType, VaType UnmappedVa, size_t AddressSpaceBits>                         \
+    requires AddressSpaceValid<VaType, AddressSpaceBits>                                           \
+        FlatAllocator<VaType, UnmappedVa, AddressSpaceBits>
+
+namespace Common {
+MAP_MEMBER_CONST()::FlatAddressSpaceMap(VaType vaLimit,
+                                        std::function<void(VaType, VaType)> unmapCallback)
+    : unmapCallback(std::move(unmapCallback)), vaLimit(vaLimit) {
+    if (vaLimit > VaMaximum)
+        UNREACHABLE_MSG("Invalid VA limit!");
+}
+
+MAP_MEMBER(void)::MapLocked(VaType virt, PaType phys, VaType size, ExtraBlockInfo extraInfo) {
+    VaType virtEnd{virt + size};
+
+    if (virtEnd > vaLimit)
+        UNREACHABLE_MSG("Trying to map a block past the VA limit: virtEnd: 0x{:X}, vaLimit: 0x{:X}",
+                        virtEnd, vaLimit);
+
+    auto blockEndSuccessor{std::lower_bound(blocks.begin(), blocks.end(), virtEnd)};
+    if (blockEndSuccessor == blocks.begin())
+        UNREACHABLE_MSG("Trying to map a block before the VA start: virtEnd: 0x{:X}", virtEnd);
+
+    auto blockEndPredecessor{std::prev(blockEndSuccessor)};
+
+    if (blockEndSuccessor != blocks.end()) {
+        // We have blocks in front of us, if one is directly in front then we don't have to add a
+        // tail
+        if (blockEndSuccessor->virt != virtEnd) {
+            PaType tailPhys{[&]() -> PaType {
+                if constexpr (!PaContigSplit) {
+                    return blockEndPredecessor
+                        ->phys; // Always propagate unmapped regions rather than calculating offset
+                } else {
+                    if (blockEndPredecessor->Unmapped())
+                        return blockEndPredecessor->phys; // Always propagate unmapped regions
+                                                          // rather than calculating offset
+                    else
+                        return blockEndPredecessor->phys + virtEnd - blockEndPredecessor->virt;
+                }
+            }()};
+
+            if (blockEndPredecessor->virt >= virt) {
+                // If this block's start would be overlapped by the map then reuse it as a tail
+                // block
+                blockEndPredecessor->virt = virtEnd;
+                blockEndPredecessor->phys = tailPhys;
+                blockEndPredecessor->extraInfo = blockEndPredecessor->extraInfo;
+
+                // No longer predecessor anymore
+                blockEndSuccessor = blockEndPredecessor--;
+            } else {
+                // Else insert a new one and we're done
+                blocks.insert(blockEndSuccessor,
+                              {Block(virt, phys, extraInfo),
+                               Block(virtEnd, tailPhys, blockEndPredecessor->extraInfo)});
+                if (unmapCallback)
+                    unmapCallback(virt, size);
+
+                return;
+            }
+        }
+    } else {
+        // blockEndPredecessor will always be unmapped as blocks has to be terminated by an unmapped
+        // chunk
+        if (blockEndPredecessor != blocks.begin() && blockEndPredecessor->virt >= virt) {
+            // Move the unmapped block start backwards
+            blockEndPredecessor->virt = virtEnd;
+
+            // No longer predecessor anymore
+            blockEndSuccessor = blockEndPredecessor--;
+        } else {
+            // Else insert a new one and we're done
+            blocks.insert(blockEndSuccessor,
+                          {Block(virt, phys, extraInfo), Block(virtEnd, UnmappedPa, {})});
+            if (unmapCallback)
+                unmapCallback(virt, size);
+
+            return;
+        }
+    }
+
+    auto blockStartSuccessor{blockEndSuccessor};
+
+    // Walk the block vector to find the start successor as this is more efficient than another
+    // binary search in most scenarios
+    while (std::prev(blockStartSuccessor)->virt >= virt)
+        blockStartSuccessor--;
+
+    // Check that the start successor is either the end block or something in between
+    if (blockStartSuccessor->virt > virtEnd) {
+        UNREACHABLE_MSG("Unsorted block in AS map: virt: 0x{:X}", blockStartSuccessor->virt);
+    } else if (blockStartSuccessor->virt == virtEnd) {
+        // We need to create a new block as there are none spare that we would overwrite
+        blocks.insert(blockStartSuccessor, Block(virt, phys, extraInfo));
+    } else {
+        // Erase overwritten blocks
+        if (auto eraseStart{std::next(blockStartSuccessor)}; eraseStart != blockEndSuccessor)
+            blocks.erase(eraseStart, blockEndSuccessor);
+
+        // Reuse a block that would otherwise be overwritten as a start block
+        blockStartSuccessor->virt = virt;
+        blockStartSuccessor->phys = phys;
+        blockStartSuccessor->extraInfo = extraInfo;
+    }
+
+    if (unmapCallback)
+        unmapCallback(virt, size);
+}
+
+MAP_MEMBER(void)::UnmapLocked(VaType virt, VaType size) {
+    VaType virtEnd{virt + size};
+
+    if (virtEnd > vaLimit)
+        UNREACHABLE_MSG("Trying to map a block past the VA limit: virtEnd: 0x{:X}, vaLimit: 0x{:X}",
+                        virtEnd, vaLimit);
+
+    auto blockEndSuccessor{std::lower_bound(blocks.begin(), blocks.end(), virtEnd)};
+    if (blockEndSuccessor == blocks.begin())
+        UNREACHABLE_MSG("Trying to unmap a block before the VA start: virtEnd: 0x{:X}", virtEnd);
+
+    auto blockEndPredecessor{std::prev(blockEndSuccessor)};
+
+    auto walkBackToPredecessor{[&](auto iter) {
+        while (iter->virt >= virt)
+            iter--;
+
+        return iter;
+    }};
+
+    auto eraseBlocksWithEndUnmapped{[&](auto unmappedEnd) {
+        auto blockStartPredecessor{walkBackToPredecessor(unmappedEnd)};
+        auto blockStartSuccessor{std::next(blockStartPredecessor)};
+
+        auto eraseEnd{[&]() {
+            if (blockStartPredecessor->Unmapped()) {
+                // If the start predecessor is unmapped then we can erase everything in our region
+                // and be done
+                return std::next(unmappedEnd);
+            } else {
+                // Else reuse the end predecessor as the start of our unmapped region then erase all
+                // up to it
+                unmappedEnd->virt = virt;
+                return unmappedEnd;
+            }
+        }()};
+
+        // We can't have two unmapped regions after each other
+        if (eraseEnd != blocks.end() &&
+            (eraseEnd == blockStartSuccessor ||
+             (blockStartPredecessor->Unmapped() && eraseEnd->Unmapped())))
+            UNREACHABLE_MSG("Multiple contiguous unmapped regions are unsupported!");
+
+        blocks.erase(blockStartSuccessor, eraseEnd);
+    }};
+
+    // We can avoid any splitting logic if these are the case
+    if (blockEndPredecessor->Unmapped()) {
+        if (blockEndPredecessor->virt > virt)
+            eraseBlocksWithEndUnmapped(blockEndPredecessor);
+
+        if (unmapCallback)
+            unmapCallback(virt, size);
+
+        return; // The region is unmapped, bail out early
+    } else if (blockEndSuccessor->virt == virtEnd && blockEndSuccessor->Unmapped()) {
+        eraseBlocksWithEndUnmapped(blockEndSuccessor);
+
+        if (unmapCallback)
+            unmapCallback(virt, size);
+
+        return; // The region is unmapped here and doesn't need splitting, bail out early
+    } else if (blockEndSuccessor == blocks.end()) {
+        // This should never happen as the end should always follow an unmapped block
+        UNREACHABLE_MSG("Unexpected Memory Manager state!");
+    } else if (blockEndSuccessor->virt != virtEnd) {
+        // If one block is directly in front then we don't have to add a tail
+
+        // The previous block is mapped so we will need to add a tail with an offset
+        PaType tailPhys{[&]() {
+            if constexpr (PaContigSplit)
+                return blockEndPredecessor->phys + virtEnd - blockEndPredecessor->virt;
+            else
+                return blockEndPredecessor->phys;
+        }()};
+
+        if (blockEndPredecessor->virt >= virt) {
+            // If this block's start would be overlapped by the unmap then reuse it as a tail block
+            blockEndPredecessor->virt = virtEnd;
+            blockEndPredecessor->phys = tailPhys;
+
+            // No longer predecessor anymore
+            blockEndSuccessor = blockEndPredecessor--;
+        } else {
+            blocks.insert(blockEndSuccessor,
+                          {Block(virt, UnmappedPa, {}),
+                           Block(virtEnd, tailPhys, blockEndPredecessor->extraInfo)});
+            if (unmapCallback)
+                unmapCallback(virt, size);
+
+            return; // The previous block is mapped and ends before
+        }
+    }
+
+    // Walk the block vector to find the start predecessor as this is more efficient than another
+    // binary search in most scenarios
+    auto blockStartPredecessor{walkBackToPredecessor(blockEndSuccessor)};
+    auto blockStartSuccessor{std::next(blockStartPredecessor)};
+
+    if (blockStartSuccessor->virt > virtEnd) {
+        UNREACHABLE_MSG("Unsorted block in AS map: virt: 0x{:X}", blockStartSuccessor->virt);
+    } else if (blockStartSuccessor->virt == virtEnd) {
+        // There are no blocks between the start and the end that would let us skip inserting a new
+        // one for head
+
+        // The previous block is may be unmapped, if so we don't need to insert any unmaps after it
+        if (blockStartPredecessor->Mapped())
+            blocks.insert(blockStartSuccessor, Block(virt, UnmappedPa, {}));
+    } else if (blockStartPredecessor->Unmapped()) {
+        // If the previous block is unmapped
+        blocks.erase(blockStartSuccessor, blockEndPredecessor);
+    } else {
+        // Erase overwritten blocks, skipping the first one as we have written the unmapped start
+        // block there
+        if (auto eraseStart{std::next(blockStartSuccessor)}; eraseStart != blockEndSuccessor)
+            blocks.erase(eraseStart, blockEndSuccessor);
+
+        // Add in the unmapped block header
+        blockStartSuccessor->virt = virt;
+        blockStartSuccessor->phys = UnmappedPa;
+    }
+
+    if (unmapCallback)
+        unmapCallback(virt, size);
+}
+
+ALLOC_MEMBER_CONST()::FlatAllocator(VaType vaStart, VaType vaLimit)
+    : Base(vaLimit), currentLinearAllocEnd(vaStart), vaStart(vaStart) {}
+
+ALLOC_MEMBER(VaType)::Allocate(VaType size) {
+    std::scoped_lock lock(this->blockMutex);
+
+    VaType allocStart{UnmappedVa};
+    VaType allocEnd{currentLinearAllocEnd + size};
+
+    // Avoid searching backwards in the address space if possible
+    if (allocEnd >= currentLinearAllocEnd && allocEnd <= this->vaLimit) {
+        auto allocEndSuccessor{
+            std::lower_bound(this->blocks.begin(), this->blocks.end(), allocEnd)};
+        if (allocEndSuccessor == this->blocks.begin())
+            UNREACHABLE_MSG("First block in AS map is invalid!");
+
+        auto allocEndPredecessor{std::prev(allocEndSuccessor)};
+        if (allocEndPredecessor->virt <= currentLinearAllocEnd) {
+            allocStart = currentLinearAllocEnd;
+        } else {
+            // Skip over fixed any mappings in front of us
+            while (allocEndSuccessor != this->blocks.end()) {
+                if (allocEndSuccessor->virt - allocEndPredecessor->virt < size ||
+                    allocEndPredecessor->Mapped()) {
+                    allocStart = allocEndPredecessor->virt;
+                    break;
+                }
+
+                allocEndPredecessor = allocEndSuccessor++;
+
+                // Use the VA limit to calculate if we can fit in the final block since it has no
+                // successor
+                if (allocEndSuccessor == this->blocks.end()) {
+                    allocEnd = allocEndPredecessor->virt + size;
+
+                    if (allocEnd >= allocEndPredecessor->virt && allocEnd <= this->vaLimit)
+                        allocStart = allocEndPredecessor->virt;
+                }
+            }
+        }
+    }
+
+    if (allocStart != UnmappedVa) {
+        currentLinearAllocEnd = allocStart + size;
+    } else { // If linear allocation overflows the AS then find a gap
+        if (this->blocks.size() <= 2)
+            UNREACHABLE_MSG("Unexpected allocator state!");
+
+        auto searchPredecessor{this->blocks.begin()};
+        auto searchSuccessor{std::next(searchPredecessor)};
+
+        while (searchSuccessor != this->blocks.end() &&
+               (searchSuccessor->virt - searchPredecessor->virt < size ||
+                searchPredecessor->Mapped())) {
+            searchPredecessor = searchSuccessor++;
+        }
+
+        if (searchSuccessor != this->blocks.end())
+            allocStart = searchPredecessor->virt;
+        else
+            return {}; // AS is full
+    }
+
+    this->MapLocked(allocStart, true, size, {});
+    return allocStart;
+}
+
+ALLOC_MEMBER(void)::AllocateFixed(VaType virt, VaType size) {
+    this->Map(virt, true, size);
+}
+
+ALLOC_MEMBER(void)::Free(VaType virt, VaType size) {
+    this->Unmap(virt, size);
+}
+} // namespace Common