code:
// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <array>
#include <tuple>

#include "common/common_funcs.h"
#include "core/hle/kernel/k_light_lock.h"
#include "core/hle/kernel/k_memory_layout.h"
#include "core/hle/kernel/k_page_heap.h"
#include "core/hle/kernel/k_typed_address.h"
#include "core/hle/result.h"

namespace Core {
class System;
}

namespace Kernel {

class KPageGroup;

class KMemoryManager {
public:
    enum class Pool : u32 {
        Application = 0,
        Applet = 1,
        System = 2,
        SystemNonSecure = 3,

        Count,

        Shift = 4,
        Mask = (0xF << Shift),

        // Aliases.
        Unsafe = Application,
        Secure = System,
    };

    enum class Direction : u32 {
        FromFront = 0,
        FromBack = 1,
        Shift = 0,
        Mask = (0xF << Shift),
    };

    static constexpr size_t MaxManagerCount = 10;

    explicit KMemoryManager(Core::System& system);

    void Initialize(KVirtualAddress management_region, size_t management_region_size);

    Result InitializeOptimizedMemory(u64 process_id, Pool pool);
    void FinalizeOptimizedMemory(u64 process_id, Pool pool);

    KPhysicalAddress AllocateAndOpenContinuous(size_t num_pages, size_t align_pages, u32 option);
    Result AllocateAndOpen(KPageGroup* out, size_t num_pages, u32 option);
    Result AllocateForProcess(KPageGroup* out, size_t num_pages, u32 option, u64 process_id,
                              u8 fill_pattern);

    Pool GetPool(KPhysicalAddress address) const {
        return this->GetManager(address).GetPool();
    }

    void Open(KPhysicalAddress address, size_t num_pages) {
        // Repeatedly open references until we've done so for all pages.
        while (num_pages) {
            auto& manager = this->GetManager(address);
            const size_t cur_pages = std::min(num_pages, manager.GetPageOffsetToEnd(address));

            {
                KScopedLightLock lk(m_pool_locks[static_cast<size_t>(manager.GetPool())]);
                manager.Open(address, cur_pages);
            }

            num_pages -= cur_pages;
            address += cur_pages * PageSize;
        }
    }

    void OpenFirst(KPhysicalAddress address, size_t num_pages) {
        // Repeatedly open references until we've done so for all pages.
        while (num_pages) {
            auto& manager = this->GetManager(address);
            const size_t cur_pages = std::min(num_pages, manager.GetPageOffsetToEnd(address));

            {
                KScopedLightLock lk(m_pool_locks[static_cast<size_t>(manager.GetPool())]);
                manager.OpenFirst(address, cur_pages);
            }

            num_pages -= cur_pages;
            address += cur_pages * PageSize;
        }
    }

    void Close(KPhysicalAddress address, size_t num_pages) {
        // Repeatedly close references until we've done so for all pages.
        while (num_pages) {
            auto& manager = this->GetManager(address);
            const size_t cur_pages = std::min(num_pages, manager.GetPageOffsetToEnd(address));

            {
                KScopedLightLock lk(m_pool_locks[static_cast<size_t>(manager.GetPool())]);
                manager.Close(address, cur_pages);
            }

            num_pages -= cur_pages;
            address += cur_pages * PageSize;
        }
    }

    size_t GetSize() {
        size_t total = 0;
        for (size_t i = 0; i < m_num_managers; i++) {
            total += m_managers[i].GetSize();
        }
        return total;
    }

    size_t GetSize(Pool pool) {
        constexpr Direction GetSizeDirection = Direction::FromFront;
        size_t total = 0;
        for (auto* manager = this->GetFirstManager(pool, GetSizeDirection); manager != nullptr;
             manager = this->GetNextManager(manager, GetSizeDirection)) {
            total += manager->GetSize();
        }
        return total;
    }

    size_t GetFreeSize() {
        size_t total = 0;
        for (size_t i = 0; i < m_num_managers; i++) {
            KScopedLightLock lk(m_pool_locks[static_cast<size_t>(m_managers[i].GetPool())]);
            total += m_managers[i].GetFreeSize();
        }
        return total;
    }

    size_t GetFreeSize(Pool pool) {
        KScopedLightLock lk(m_pool_locks[static_cast<size_t>(pool)]);

        constexpr Direction GetSizeDirection = Direction::FromFront;
        size_t total = 0;
        for (auto* manager = this->GetFirstManager(pool, GetSizeDirection); manager != nullptr;
             manager = this->GetNextManager(manager, GetSizeDirection)) {
            total += manager->GetFreeSize();
        }
        return total;
    }

    void DumpFreeList(Pool pool) {
        KScopedLightLock lk(m_pool_locks[static_cast<size_t>(pool)]);

        constexpr Direction DumpDirection = Direction::FromFront;
        for (auto* manager = this->GetFirstManager(pool, DumpDirection); manager != nullptr;
             manager = this->GetNextManager(manager, DumpDirection)) {
            manager->DumpFreeList();
        }
    }

public:
    static size_t CalculateManagementOverheadSize(size_t region_size) {
        return Impl::CalculateManagementOverheadSize(region_size);
    }

    static constexpr u32 EncodeOption(Pool pool, Direction dir) {
        return (static_cast<u32>(pool) << static_cast<u32>(Pool::Shift)) |
               (static_cast<u32>(dir) << static_cast<u32>(Direction::Shift));
    }

    static constexpr Pool GetPool(u32 option) {
        return static_cast<Pool>((option & static_cast<u32>(Pool::Mask)) >>
                                 static_cast<u32>(Pool::Shift));
    }

    static constexpr Direction GetDirection(u32 option) {
        return static_cast<Direction>((option & static_cast<u32>(Direction::Mask)) >>
                                      static_cast<u32>(Direction::Shift));
    }

    static constexpr std::tuple<Pool, Direction> DecodeOption(u32 option) {
        return std::make_tuple(GetPool(option), GetDirection(option));
    }

private:
    class Impl {
    public:
        static size_t CalculateManagementOverheadSize(size_t region_size);

        static constexpr size_t CalculateOptimizedProcessOverheadSize(size_t region_size) {
            return (Common::AlignUp((region_size / PageSize), Common::BitSize<u64>()) /
                    Common::BitSize<u64>()) *
                   sizeof(u64);
        }

    public:
        Impl() = default;

        size_t Initialize(KPhysicalAddress address, size_t size, KVirtualAddress management,
                          KVirtualAddress management_end, Pool p);

        KPhysicalAddress AllocateBlock(s32 index, bool random) {
            return m_heap.AllocateBlock(index, random);
        }
        KPhysicalAddress AllocateAligned(s32 index, size_t num_pages, size_t align_pages) {
            return m_heap.AllocateAligned(index, num_pages, align_pages);
        }
        void Free(KPhysicalAddress addr, size_t num_pages) {
            m_heap.Free(addr, num_pages);
        }

        void SetInitialUsedHeapSize(size_t reserved_size) {
            m_heap.SetInitialUsedSize(reserved_size);
        }

        void InitializeOptimizedMemory(KernelCore& kernel);

        void TrackUnoptimizedAllocation(KernelCore& kernel, KPhysicalAddress block,
                                        size_t num_pages);
        void TrackOptimizedAllocation(KernelCore& kernel, KPhysicalAddress block, size_t num_pages);

        bool ProcessOptimizedAllocation(KernelCore& kernel, KPhysicalAddress block,
                                        size_t num_pages, u8 fill_pattern);

        constexpr Pool GetPool() const {
            return m_pool;
        }
        constexpr size_t GetSize() const {
            return m_heap.GetSize();
        }
        constexpr KPhysicalAddress GetEndAddress() const {
            return m_heap.GetEndAddress();
        }

        size_t GetFreeSize() const {
            return m_heap.GetFreeSize();
        }

        void DumpFreeList() const {
            UNIMPLEMENTED();
        }

        constexpr size_t GetPageOffset(KPhysicalAddress address) const {
            return m_heap.GetPageOffset(address);
        }
        constexpr size_t GetPageOffsetToEnd(KPhysicalAddress address) const {
            return m_heap.GetPageOffsetToEnd(address);
        }

        constexpr void SetNext(Impl* n) {
            m_next = n;
        }
        constexpr void SetPrev(Impl* n) {
            m_prev = n;
        }
        constexpr Impl* GetNext() const {
            return m_next;
        }
        constexpr Impl* GetPrev() const {
            return m_prev;
        }

        void OpenFirst(KPhysicalAddress address, size_t num_pages) {
            size_t index = this->GetPageOffset(address);
            const size_t end = index + num_pages;
            while (index < end) {
                const RefCount ref_count = (++m_page_reference_counts[index]);
                ASSERT(ref_count == 1);

                index++;
            }
        }

        void Open(KPhysicalAddress address, size_t num_pages) {
            size_t index = this->GetPageOffset(address);
            const size_t end = index + num_pages;
            while (index < end) {
                const RefCount ref_count = (++m_page_reference_counts[index]);
                ASSERT(ref_count > 1);

                index++;
            }
        }

        void Close(KPhysicalAddress address, size_t num_pages) {
            size_t index = this->GetPageOffset(address);
            const size_t end = index + num_pages;

            size_t free_start = 0;
            size_t free_count = 0;
            while (index < end) {
                ASSERT(m_page_reference_counts[index] > 0);
                const RefCount ref_count = (--m_page_reference_counts[index]);

                // Keep track of how many zero refcounts we see in a row, to minimize calls to free.
                if (ref_count == 0) {
                    if (free_count > 0) {
                        free_count++;
                    } else {
                        free_start = index;
                        free_count = 1;
                    }
                } else {
                    if (free_count > 0) {
                        this->Free(m_heap.GetAddress() + free_start * PageSize, free_count);
                        free_count = 0;
                    }
                }

                index++;
            }

            if (free_count > 0) {
                this->Free(m_heap.GetAddress() + free_start * PageSize, free_count);
            }
        }

    private:
        using RefCount = u16;

        KPageHeap m_heap;
        std::vector<RefCount> m_page_reference_counts;
        KVirtualAddress m_management_region{};
        Pool m_pool{};
        Impl* m_next{};
        Impl* m_prev{};
    };

private:
    Impl& GetManager(KPhysicalAddress address) {
        return m_managers[m_memory_layout.GetPhysicalLinearRegion(address).GetAttributes()];
    }

    const Impl& GetManager(KPhysicalAddress address) const {
        return m_managers[m_memory_layout.GetPhysicalLinearRegion(address).GetAttributes()];
    }

    constexpr Impl* GetFirstManager(Pool pool, Direction dir) {
        return dir == Direction::FromBack ? m_pool_managers_tail[static_cast<size_t>(pool)]
                                          : m_pool_managers_head[static_cast<size_t>(pool)];
    }

    constexpr Impl* GetNextManager(Impl* cur, Direction dir) {
        if (dir == Direction::FromBack) {
            return cur->GetPrev();
        } else {
            return cur->GetNext();
        }
    }

    Result AllocatePageGroupImpl(KPageGroup* out, size_t num_pages, Pool pool, Direction dir,
                                 bool unoptimized, bool random);

private:
    template <typename T>
    using PoolArray = std::array<T, static_cast<size_t>(Pool::Count)>;

    Core::System& m_system;
    const KMemoryLayout& m_memory_layout;
    PoolArray<KLightLock> m_pool_locks;
    std::array<Impl*, MaxManagerCount> m_pool_managers_head{};
    std::array<Impl*, MaxManagerCount> m_pool_managers_tail{};
    std::array<Impl, MaxManagerCount> m_managers;
    size_t m_num_managers{};
    PoolArray<u64> m_optimized_process_ids{};
    PoolArray<bool> m_has_optimized_process{};
};

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include "common/assert.h"
#include "common/common_funcs.h"
#include "common/intrusive_red_black_tree.h"
#include "core/hle/kernel/k_memory_region_type.h"
#include "core/hle/kernel/k_typed_address.h"

namespace Kernel {

class KMemoryRegionAllocator;

class KMemoryRegion final : public Common::IntrusiveRedBlackTreeBaseNode<KMemoryRegion> {
    friend class KMemoryRegionTree;

public:
    YUZU_NON_COPYABLE(KMemoryRegion);
    YUZU_NON_MOVEABLE(KMemoryRegion);

    constexpr KMemoryRegion() = default;
    constexpr KMemoryRegion(u64 address, u64 last_address)
        : m_address{address}, m_last_address{last_address} {}
    constexpr KMemoryRegion(u64 address, u64 last_address, u64 pair_address, u32 attributes,
                            u32 type_id)
        : m_address(address), m_last_address(last_address), m_pair_address(pair_address),
          m_attributes(attributes), m_type_id(type_id) {}
    constexpr KMemoryRegion(u64 address, u64 last_address, u32 attributes, u32 type_id)
        : KMemoryRegion(address, last_address, std::numeric_limits<u64>::max(), attributes,
                        type_id) {}

    ~KMemoryRegion() = default;

    static constexpr int Compare(const KMemoryRegion& lhs, const KMemoryRegion& rhs) {
        if (lhs.GetAddress() < rhs.GetAddress()) {
            return -1;
        } else if (lhs.GetAddress() <= rhs.GetLastAddress()) {
            return 0;
        } else {
            return 1;
        }
    }

    constexpr u64 GetAddress() const {
        return m_address;
    }

    constexpr u64 GetPairAddress() const {
        return m_pair_address;
    }

    constexpr u64 GetLastAddress() const {
        return m_last_address;
    }

    constexpr u64 GetEndAddress() const {
        return this->GetLastAddress() + 1;
    }

    constexpr size_t GetSize() const {
        return this->GetEndAddress() - this->GetAddress();
    }

    constexpr u32 GetAttributes() const {
        return m_attributes;
    }

    constexpr u32 GetType() const {
        return m_type_id;
    }

    constexpr void SetType(u32 type) {
        ASSERT(this->CanDerive(type));
        m_type_id = type;
    }

    constexpr bool Contains(u64 addr) const {
        ASSERT(this->GetEndAddress() != 0);
        return this->GetAddress() <= addr && addr <= this->GetLastAddress();
    }

    constexpr bool IsDerivedFrom(u32 type) const {
        return (this->GetType() | type) == this->GetType();
    }

    constexpr bool HasTypeAttribute(u32 attr) const {
        return (this->GetType() | attr) == this->GetType();
    }

    constexpr bool CanDerive(u32 type) const {
        return (this->GetType() | type) == type;
    }

    constexpr void SetPairAddress(u64 a) {
        m_pair_address = a;
    }

    constexpr void SetTypeAttribute(u32 attr) {
        m_type_id |= attr;
    }

private:
    constexpr void Reset(u64 a, u64 la, u64 p, u32 r, u32 t) {
        m_address = a;
        m_pair_address = p;
        m_last_address = la;
        m_attributes = r;
        m_type_id = t;
    }

    u64 m_address{};
    u64 m_last_address{};
    u64 m_pair_address{};
    u32 m_attributes{};
    u32 m_type_id{};
};

class KMemoryRegionTree final {
private:
    using TreeType =
        Common::IntrusiveRedBlackTreeBaseTraits<KMemoryRegion>::TreeType<KMemoryRegion>;

public:
    YUZU_NON_COPYABLE(KMemoryRegionTree);
    YUZU_NON_MOVEABLE(KMemoryRegionTree);

    using value_type = TreeType::value_type;
    using size_type = TreeType::size_type;
    using difference_type = TreeType::difference_type;
    using pointer = TreeType::pointer;
    using const_pointer = TreeType::const_pointer;
    using reference = TreeType::reference;
    using const_reference = TreeType::const_reference;
    using iterator = TreeType::iterator;
    using const_iterator = TreeType::const_iterator;

    struct DerivedRegionExtents {
        const KMemoryRegion* first_region{};
        const KMemoryRegion* last_region{};

        constexpr DerivedRegionExtents() = default;

        constexpr u64 GetAddress() const {
            return this->first_region->GetAddress();
        }

        constexpr u64 GetLastAddress() const {
            return this->last_region->GetLastAddress();
        }

        constexpr u64 GetEndAddress() const {
            return this->GetLastAddress() + 1;
        }

        constexpr size_t GetSize() const {
            return this->GetEndAddress() - this->GetAddress();
        }
    };

    explicit KMemoryRegionTree(KMemoryRegionAllocator& memory_region_allocator_);
    ~KMemoryRegionTree() = default;

    KMemoryRegion* FindModifiable(u64 address) {
        if (auto it = this->find(KMemoryRegion(address, address, 0, 0)); it != this->end()) {
            return std::addressof(*it);
        } else {
            return nullptr;
        }
    }

    const KMemoryRegion* Find(u64 address) const {
        if (auto it = this->find(KMemoryRegion(address, address, 0, 0)); it != this->cend()) {
            return std::addressof(*it);
        } else {
            return nullptr;
        }
    }

    const KMemoryRegion* FindByType(KMemoryRegionType type_id) const {
        for (auto it = this->cbegin(); it != this->cend(); ++it) {
            if (it->GetType() == static_cast<u32>(type_id)) {
                return std::addressof(*it);
            }
        }
        return nullptr;
    }

    const KMemoryRegion* FindByTypeAndAttribute(u32 type_id, u32 attr) const {
        for (auto it = this->cbegin(); it != this->cend(); ++it) {
            if (it->GetType() == type_id && it->GetAttributes() == attr) {
                return std::addressof(*it);
            }
        }
        return nullptr;
    }

    const KMemoryRegion* FindFirstDerived(KMemoryRegionType type_id) const {
        for (auto it = this->cbegin(); it != this->cend(); it++) {
            if (it->IsDerivedFrom(type_id)) {
                return std::addressof(*it);
            }
        }
        return nullptr;
    }

    const KMemoryRegion* FindLastDerived(KMemoryRegionType type_id) const {
        const KMemoryRegion* region = nullptr;
        for (auto it = this->begin(); it != this->end(); it++) {
            if (it->IsDerivedFrom(type_id)) {
                region = std::addressof(*it);
            }
        }
        return region;
    }

    DerivedRegionExtents GetDerivedRegionExtents(KMemoryRegionType type_id) const {
        DerivedRegionExtents extents;

        ASSERT(extents.first_region == nullptr);
        ASSERT(extents.last_region == nullptr);

        for (auto it = this->cbegin(); it != this->cend(); it++) {
            if (it->IsDerivedFrom(type_id)) {
                if (extents.first_region == nullptr) {
                    extents.first_region = std::addressof(*it);
                }
                extents.last_region = std::addressof(*it);
            }
        }

        ASSERT(extents.first_region != nullptr);
        ASSERT(extents.last_region != nullptr);

        return extents;
    }

    DerivedRegionExtents GetDerivedRegionExtents(u32 type_id) const {
        return GetDerivedRegionExtents(static_cast<KMemoryRegionType>(type_id));
    }

    void InsertDirectly(u64 address, u64 last_address, u32 attr = 0, u32 type_id = 0);
    bool Insert(u64 address, size_t size, u32 type_id, u32 new_attr = 0, u32 old_attr = 0);

    KVirtualAddress GetRandomAlignedRegion(size_t size, size_t alignment, u32 type_id);

    KVirtualAddress GetRandomAlignedRegionWithGuard(size_t size, size_t alignment, u32 type_id,
                                                    size_t guard_size) {
        return this->GetRandomAlignedRegion(size + 2 * guard_size, alignment, type_id) + guard_size;
    }

    // Iterator accessors.
    iterator begin() {
        return m_tree.begin();
    }

    const_iterator begin() const {
        return m_tree.begin();
    }

    iterator end() {
        return m_tree.end();
    }

    const_iterator end() const {
        return m_tree.end();
    }

    const_iterator cbegin() const {
        return this->begin();
    }

    const_iterator cend() const {
        return this->end();
    }

    iterator iterator_to(reference ref) {
        return m_tree.iterator_to(ref);
    }

    const_iterator iterator_to(const_reference ref) const {
        return m_tree.iterator_to(ref);
    }

    // Content management.
    bool empty() const {
        return m_tree.empty();
    }

    reference back() {
        return m_tree.back();
    }

    const_reference back() const {
        return m_tree.back();
    }

    reference front() {
        return m_tree.front();
    }

    const_reference front() const {
        return m_tree.front();
    }

    iterator insert(reference ref) {
        return m_tree.insert(ref);
    }

    iterator erase(iterator it) {
        return m_tree.erase(it);
    }

    iterator find(const_reference ref) const {
        return m_tree.find(ref);
    }

    iterator nfind(const_reference ref) const {
        return m_tree.nfind(ref);
    }

private:
    TreeType m_tree{};
    KMemoryRegionAllocator& m_memory_region_allocator;
};

class KMemoryRegionAllocator final {
public:
    YUZU_NON_COPYABLE(KMemoryRegionAllocator);
    YUZU_NON_MOVEABLE(KMemoryRegionAllocator);

    static constexpr size_t MaxMemoryRegions = 200;

    constexpr KMemoryRegionAllocator() = default;
    constexpr ~KMemoryRegionAllocator() = default;

    template <typename... Args>
    KMemoryRegion* Allocate(Args&&... args) {
        // Ensure we stay within the bounds of our heap.
        ASSERT(m_num_regions < MaxMemoryRegions);

        // Create the new region.
        KMemoryRegion* region = std::addressof(m_region_heap[m_num_regions++]);
        std::construct_at(region, std::forward<Args>(args)...);

        return region;
    }

private:
    std::array<KMemoryRegion, MaxMemoryRegions> m_region_heap{};
    size_t m_num_regions{};
};

} // namespace Kernel

repo_name: litucks/torzu

license: mit


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include "common/bit_util.h"
#include "common/common_funcs.h"
#include "common/common_types.h"

#define ARCH_ARM64
#define BOARD_NINTENDO_NX

namespace Kernel {

enum KMemoryRegionType : u32 {
    KMemoryRegionAttr_CarveoutProtected = 0x02000000,
    KMemoryRegionAttr_Uncached = 0x04000000,
    KMemoryRegionAttr_DidKernelMap = 0x08000000,
    KMemoryRegionAttr_ShouldKernelMap = 0x10000000,
    KMemoryRegionAttr_UserReadOnly = 0x20000000,
    KMemoryRegionAttr_NoUserMap = 0x40000000,
    KMemoryRegionAttr_LinearMapped = 0x80000000,
};
DECLARE_ENUM_FLAG_OPERATORS(KMemoryRegionType);

namespace impl {

constexpr size_t BitsForDeriveSparse(size_t n) {
    return n + 1;
}

constexpr size_t BitsForDeriveDense(size_t n) {
    size_t low = 0, high = 1;
    for (size_t i = 0; i < n - 1; ++i) {
        if ((++low) == high) {
            ++high;
            low = 0;
        }
    }
    return high + 1;
}

class KMemoryRegionTypeValue {
public:
    using ValueType = std::underlying_type_t<KMemoryRegionType>;

    constexpr KMemoryRegionTypeValue() = default;

    constexpr operator KMemoryRegionType() const {
        return static_cast<KMemoryRegionType>(m_value);
    }

    constexpr ValueType GetValue() const {
        return m_value;
    }

    constexpr const KMemoryRegionTypeValue& Finalize() {
        m_finalized = true;
        return *this;
    }

    constexpr const KMemoryRegionTypeValue& SetSparseOnly() {
        m_sparse_only = true;
        return *this;
    }

    constexpr const KMemoryRegionTypeValue& SetDenseOnly() {
        m_dense_only = true;
        return *this;
    }

    constexpr KMemoryRegionTypeValue& SetAttribute(u32 attr) {
        m_value |= attr;
        return *this;
    }

    constexpr KMemoryRegionTypeValue DeriveInitial(
        size_t i, size_t next = Common::BitSize<ValueType>()) const {
        KMemoryRegionTypeValue new_type = *this;
        new_type.m_value = (ValueType{1} << i);
        new_type.m_next_bit = next;
        return new_type;
    }

    constexpr KMemoryRegionTypeValue DeriveAttribute(u32 attr) const {
        KMemoryRegionTypeValue new_type = *this;
        new_type.m_value |= attr;
        return new_type;
    }

    constexpr KMemoryRegionTypeValue DeriveTransition(size_t ofs = 0, size_t adv = 1) const {
        KMemoryRegionTypeValue new_type = *this;
        new_type.m_value |= (ValueType{1} << (m_next_bit + ofs));
        new_type.m_next_bit += adv;
        return new_type;
    }

    constexpr KMemoryRegionTypeValue DeriveSparse(size_t ofs, size_t n, size_t i) const {
        KMemoryRegionTypeValue new_type = *this;
        new_type.m_value |= (ValueType{1} << (m_next_bit + ofs));
        new_type.m_value |= (ValueType{1} << (m_next_bit + ofs + 1 + i));
        new_type.m_next_bit += ofs + n + 1;
        return new_type;
    }

    constexpr KMemoryRegionTypeValue Derive(size_t n, size_t i) const {
        size_t low = 0, high = 1;
        for (size_t j = 0; j < i; ++j) {
            if ((++low) == high) {
                ++high;
                low = 0;
            }
        }

        KMemoryRegionTypeValue new_type = *this;
        new_type.m_value |= (ValueType{1} << (m_next_bit + low));
        new_type.m_value |= (ValueType{1} << (m_next_bit + high));
        new_type.m_next_bit += BitsForDeriveDense(n);
        return new_type;
    }

    constexpr KMemoryRegionTypeValue Advance(size_t n) const {
        KMemoryRegionTypeValue new_type = *this;
        new_type.m_next_bit += n;
        return new_type;
    }

    constexpr bool IsAncestorOf(ValueType v) const {
        return (m_value | v) == v;
    }

private:
    constexpr KMemoryRegionTypeValue(ValueType v) : m_value(v) {}

private:
    ValueType m_value{};
    size_t m_next_bit{};
    bool m_finalized{};
    bool m_sparse_only{};
    bool m_dense_only{};
};

} // namespace impl

constexpr inline auto KMemoryRegionType_None = impl::KMemoryRegionTypeValue();

constexpr inline auto KMemoryRegionType_Kernel = KMemoryRegionType_None.DeriveInitial(0, 2);
constexpr inline auto KMemoryRegionType_Dram = KMemoryRegionType_None.DeriveInitial(1, 2);
static_assert(KMemoryRegionType_Kernel.GetValue() == 0x1);
static_assert(KMemoryRegionType_Dram.GetValue() == 0x2);

// constexpr inline auto KMemoryRegionType_CoreLocalRegion =
// KMemoryRegionType_None.DeriveInitial(2).Finalize();
// static_assert(KMemoryRegionType_CoreLocalRegion.GetValue() == 0x4);

constexpr inline auto KMemoryRegionType_DramKernelBase =
    KMemoryRegionType_Dram.DeriveSparse(0, 3, 0)
        .SetAttribute(KMemoryRegionAttr_NoUserMap)
        .SetAttribute(KMemoryRegionAttr_CarveoutProtected);
constexpr inline auto KMemoryRegionType_DramReservedBase =
    KMemoryRegionType_Dram.DeriveSparse(0, 3, 1);
constexpr inline auto KMemoryRegionType_DramHeapBase =
    KMemoryRegionType_Dram.DeriveSparse(0, 3, 2).SetAttribute(KMemoryRegionAttr_LinearMapped);
static_assert(KMemoryRegionType_DramKernelBase.GetValue() ==
              (0xE | KMemoryRegionAttr_CarveoutProtected | KMemoryRegionAttr_NoUserMap));
static_assert(KMemoryRegionType_DramReservedBase.GetValue() == (0x16));
static_assert(KMemoryRegionType_DramHeapBase.GetValue() == (0x26 | KMemoryRegionAttr_LinearMapped));

constexpr inline auto KMemoryRegionType_DramKernelCode =
    KMemoryRegionType_DramKernelBase.DeriveSparse(0, 4, 0);
constexpr inline auto KMemoryRegionType_DramKernelSlab =
    KMemoryRegionType_DramKernelBase.DeriveSparse(0, 4, 1);
constexpr inline auto KMemoryRegionType_DramKernelPtHeap =
    KMemoryRegionType_DramKernelBase.DeriveSparse(0, 4, 2).SetAttribute(
        KMemoryRegionAttr_LinearMapped);
constexpr inline auto KMemoryRegionType_DramKernelInitPt =
    KMemoryRegionType_DramKernelBase.DeriveSparse(0, 4, 3).SetAttribute(
        KMemoryRegionAttr_LinearMapped);
static_assert(KMemoryRegionType_DramKernelCode.GetValue() ==
              (0xCE | KMemoryRegionAttr_CarveoutProtected | KMemoryRegionAttr_NoUserMap));
static_assert(KMemoryRegionType_DramKernelSlab.GetValue() ==
              (0x14E | KMemoryRegionAttr_CarveoutProtected | KMemoryRegionAttr_NoUserMap));
static_assert(KMemoryRegionType_DramKernelPtHeap.GetValue() ==
              (0x24E | KMemoryRegionAttr_CarveoutProtected | KMemoryRegionAttr_NoUserMap |
               KMemoryRegionAttr_LinearMapped));
static_assert(KMemoryRegionType_DramKernelInitPt.GetValue() ==
              (0x44E | KMemoryRegionAttr_CarveoutProtected | KMemoryRegionAttr_NoUserMap |
               KMemoryRegionAttr_LinearMapped));

constexpr inline auto KMemoryRegionType_DramKernelSecureAppletMemory =
    KMemoryRegionType_DramKernelBase.DeriveSparse(1, 3, 0).SetAttribute(
        KMemoryRegionAttr_LinearMapped);
constexpr inline const auto KMemoryRegionType_DramKernelSecureUnknown =
    KMemoryRegionType_DramKernelBase.DeriveSparse(1, 3, 1).SetAttribute(
        KMemoryRegionAttr_LinearMapped);
static_assert(KMemoryRegionType_DramKernelSecureAppletMemory.GetValue() ==
              (0x18E | KMemoryRegionAttr_CarveoutProtected | KMemoryRegionAttr_NoUserMap |
               KMemoryRegionAttr_LinearMapped));
static_assert(KMemoryRegionType_DramKernelSecureUnknown.GetValue() ==
              (0x28E | KMemoryRegionAttr_CarveoutProtected | KMemoryRegionAttr_NoUserMap |
               KMemoryRegionAttr_LinearMapped));

constexpr inline auto KMemoryRegionType_DramReservedEarly =
    KMemoryRegionType_DramReservedBase.DeriveAttribute(KMemoryRegionAttr_NoUserMap);
static_assert(KMemoryRegionType_DramReservedEarly.GetValue() ==
              (0x16 | KMemoryRegionAttr_NoUserMap));

constexpr inline auto KMemoryRegionType_KernelTraceBuffer =
    KMemoryRegionType_DramReservedBase.DeriveSparse(0, 3, 0)
        .SetAttribute(KMemoryRegionAttr_LinearMapped)
        .SetAttribute(KMemoryRegionAttr_UserReadOnly);
constexpr inline auto KMemoryRegionType_OnMemoryBootImage =
    KMemoryRegionType_DramReservedBase.DeriveSparse(0, 3, 1);
constexpr inline auto KMemoryRegionType_DTB =
    KMemoryRegionType_DramReservedBase.DeriveSparse(0, 3, 2);
static_assert(KMemoryRegionType_KernelTraceBuffer.GetValue() ==
              (0xD6 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_UserReadOnly));
static_assert(KMemoryRegionType_OnMemoryBootImage.GetValue() == 0x156);
static_assert(KMemoryRegionType_DTB.GetValue() == 0x256);

constexpr inline auto KMemoryRegionType_DramPoolPartition =
    KMemoryRegionType_DramHeapBase.DeriveAttribute(KMemoryRegionAttr_NoUserMap);
static_assert(KMemoryRegionType_DramPoolPartition.GetValue() ==
              (0x26 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_NoUserMap));

// UNUSED: .Derive(4, 1);
// UNUSED: .Derive(4, 2);
constexpr inline const auto KMemoryRegionType_DramPoolManagement =
    KMemoryRegionType_DramPoolPartition.Derive(4, 0).SetAttribute(
        KMemoryRegionAttr_CarveoutProtected);
constexpr inline const auto KMemoryRegionType_DramUserPool =
    KMemoryRegionType_DramPoolPartition.Derive(4, 3);
static_assert(KMemoryRegionType_DramPoolManagement.GetValue() ==
              (0xE6 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_NoUserMap |
               KMemoryRegionAttr_CarveoutProtected));
static_assert(KMemoryRegionType_DramUserPool.GetValue() ==
              (0x266 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_NoUserMap));

constexpr inline auto KMemoryRegionType_DramApplicationPool =
    KMemoryRegionType_DramUserPool.Derive(4, 0);
constexpr inline auto KMemoryRegionType_DramAppletPool =
    KMemoryRegionType_DramUserPool.Derive(4, 1);
constexpr inline auto KMemoryRegionType_DramSystemNonSecurePool =
    KMemoryRegionType_DramUserPool.Derive(4, 2);
constexpr inline auto KMemoryRegionType_DramSystemPool =
    KMemoryRegionType_DramUserPool.Derive(4, 3).SetAttribute(KMemoryRegionAttr_CarveoutProtected);
static_assert(KMemoryRegionType_DramApplicationPool.GetValue() ==
              (0xE66 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_NoUserMap));
static_assert(KMemoryRegionType_DramAppletPool.GetValue() ==
              (0x1666 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_NoUserMap));
static_assert(KMemoryRegionType_DramSystemNonSecurePool.GetValue() ==
              (0x1A66 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_NoUserMap));
static_assert(KMemoryRegionType_DramSystemPool.GetValue() ==
              (0x2666 | KMemoryRegionAttr_LinearMapped | KMemoryRegionAttr_NoUserMap |
               KMemoryRegionAttr_CarveoutProtected));

constexpr inline auto KMemoryRegionType_VirtualDramHeapBase =
    KMemoryRegionType_Dram.DeriveSparse(1, 4, 0);
constexpr inline auto KMemoryRegionType_VirtualDramKernelPtHeap =
    KMemoryRegionType_Dram.DeriveSparse(1, 4, 1);
constexpr inline auto KMemoryRegionType_VirtualDramKernelTraceBuffer =
    KMemoryRegionType_Dram.DeriveSparse(1, 4, 2);
static_assert(KMemoryRegionType_VirtualDramHeapBase.GetValue() == 0x1A);
static_assert(KMemoryRegionType_VirtualDramKernelPtHeap.GetValue() == 0x2A);
static_assert(KMemoryRegionType_VirtualDramKernelTraceBuffer.GetValue() == 0x4A);

// UNUSED: .Derive(4, 2);
constexpr inline const auto KMemoryRegionType_VirtualDramUnknownDebug =
    KMemoryRegionType_Dram.Advance(2).Derive(4, 0);
constexpr inline const auto KMemoryRegionType_VirtualDramKernelSecureAppletMemory =
    KMemoryRegionType_Dram.Advance(2).Derive(4, 1);
constexpr inline const auto KMemoryRegionType_VirtualDramKernelSecureUnknown =
    KMemoryRegionType_Dram.Advance(2).Derive(4, 3);
static_assert(KMemoryRegionType_VirtualDramUnknownDebug.GetValue() == (0x32));
static_assert(KMemoryRegionType_VirtualDramKernelSecureAppletMemory.GetValue() == (0x52));
static_assert(KMemoryRegionType_VirtualDramKernelSecureUnknown.GetValue() == (0x92));

// UNUSED: .Derive(4, 3);
constexpr inline const auto KMemoryRegionType_VirtualDramKernelInitPt =
    KMemoryRegionType_VirtualDramHeapBase.Derive(4, 0);
constexpr inline const auto KMemoryRegionType_VirtualDramPoolManagement =
    KMemoryRegionType_VirtualDramHeapBase.Derive(4, 1);
constexpr inline const auto KMemoryRegionType_VirtualDramUserPool =
    KMemoryRegionType_VirtualDramHeapBase.Derive(4, 2);
static_assert(KMemoryRegionType_VirtualDramKernelInitPt.GetValue() == 0x31A);
static_assert(KMemoryRegionType_VirtualDramPoolManagement.GetValue() == 0x51A);
static_assert(KMemoryRegionType_VirtualDramUserPool.GetValue() == 0x61A);

// NOTE: For unknown reason, the pools are derived out-of-order here.
// It's worth eventually trying to understand why Nintendo made this choice.
// UNUSED: .Derive(6, 0);
// UNUSED: .Derive(6, 1);
constexpr inline const auto KMemoryRegionType_VirtualDramApplicationPool =
    KMemoryRegionType_VirtualDramUserPool.Derive(4, 0);
constexpr inline const auto KMemoryRegionType_VirtualDramAppletPool =
    KMemoryRegionType_VirtualDramUserPool.Derive(4, 1);
constexpr inline const auto KMemoryRegionType_VirtualDramSystemNonSecurePool =
    KMemoryRegionType_VirtualDramUserPool.Derive(4, 2);
constexpr inline const auto KMemoryRegionType_VirtualDramSystemPool =
    KMemoryRegionType_VirtualDramUserPool.Derive(4, 3);
static_assert(KMemoryRegionType_VirtualDramApplicationPool.GetValue() == 0x361A);
static_assert(KMemoryRegionType_VirtualDramAppletPool.GetValue() == 0x561A);
static_assert(KMemoryRegionType_VirtualDramSystemNonSecurePool.GetValue() == 0x661A);
static_assert(KMemoryRegionType_VirtualDramSystemPool.GetValue() == 0x961A);

constexpr inline auto KMemoryRegionType_ArchDeviceBase =
    KMemoryRegionType_Kernel.DeriveTransition(0, 1).SetSparseOnly();
constexpr inline auto KMemoryRegionType_BoardDeviceBase =
    KMemoryRegionType_Kernel.DeriveTransition(0, 2).SetDenseOnly();
static_assert(KMemoryRegionType_ArchDeviceBase.GetValue() == 0x5);
static_assert(KMemoryRegionType_BoardDeviceBase.GetValue() == 0x5);

#if defined(ARCH_ARM64)
#include "core/hle/kernel/arch/arm64/k_memory_region_device_types.inc"
#elif defined(ARCH_ARM)
#error "Unimplemented"
#else
// Default to no architecture devices.
constexpr inline auto NumArchitectureDeviceRegions = 0;
#endif
static_assert(NumArchitectureDeviceRegions >= 0);

#if defined(BOARD_NINTENDO_NX)
#include "core/hle/kernel/board/nintendo/nx/k_memory_region_device_types.inc"
#else
// Default to no board devices.
constexpr inline auto NumBoardDeviceRegions = 0;
#endif
static_assert(NumBoardDeviceRegions >= 0);

constexpr inline auto KMemoryRegionType_KernelCode = KMemoryRegionType_Kernel.DeriveSparse(1, 4, 0);
constexpr inline auto KMemoryRegionType_KernelStack =
    KMemoryRegionType_Kernel.DeriveSparse(1, 4, 1);
constexpr inline auto KMemoryRegionType_KernelMisc = KMemoryRegionType_Kernel.DeriveSparse(1, 4, 2);
constexpr inline auto KMemoryRegionType_KernelSlab = KMemoryRegionType_Kernel.DeriveSparse(1, 4, 3);
static_assert(KMemoryRegionType_KernelCode.GetValue() == 0x19);
static_assert(KMemoryRegionType_KernelStack.GetValue() == 0x29);
static_assert(KMemoryRegionType_KernelMisc.GetValue() == 0x49);
static_assert(KMemoryRegionType_KernelSlab.GetValue() == 0x89);

constexpr inline auto KMemoryRegionType_KernelMiscDerivedBase =
    KMemoryRegionType_KernelMisc.DeriveTransition();
static_assert(KMemoryRegionType_KernelMiscDerivedBase.GetValue() == 0x149);

// UNUSED: .Derive(7, 0);
constexpr inline auto KMemoryRegionType_KernelMiscMainStack =
    KMemoryRegionType_KernelMiscDerivedBase.Derive(7, 1);
constexpr inline auto KMemoryRegionType_KernelMiscMappedDevice =
    KMemoryRegionType_KernelMiscDerivedBase.Derive(7, 2);
constexpr inline auto KMemoryRegionType_KernelMiscExceptionStack =
    KMemoryRegionType_KernelMiscDerivedBase.Derive(7, 3);
constexpr inline auto KMemoryRegionType_KernelMiscUnknownDebug =
    KMemoryRegionType_KernelMiscDerivedBase.Derive(7, 4);
// UNUSED: .Derive(7, 5);
constexpr inline auto KMemoryRegionType_KernelMiscIdleStack =
    KMemoryRegionType_KernelMiscDerivedBase.Derive(7, 6);
static_assert(KMemoryRegionType_KernelMiscMainStack.GetValue() == 0xB49);
static_assert(KMemoryRegionType_KernelMiscMappedDevice.GetValue() == 0xD49);
static_assert(KMemoryRegionType_KernelMiscExceptionStack.GetValue() == 0x1349);
static_assert(KMemoryRegionType_KernelMiscUnknownDebug.GetValue() == 0x1549);
static_assert(KMemoryRegionType_KernelMiscIdleStack.GetValue() == 0x2349);

constexpr inline auto KMemoryRegionType_KernelTemp =
    KMemoryRegionType_Kernel.Advance(2).Derive(2, 0);
static_assert(KMemoryRegionType_KernelTemp.GetValue() == 0x31);

constexpr KMemoryRegionType GetTypeForVirtualLinearMapping(u32 type_id) {
    if (KMemoryRegionType_DramKernelPtHeap.IsAncestorOf(type_id)) {
        return KMemoryRegionType_VirtualDramKernelPtHeap;
    } else if (KMemoryRegionType_DramKernelSecureAppletMemory.IsAncestorOf(type_id)) {
        return KMemoryRegionType_VirtualDramKernelSecureAppletMemory;
    } else if (KMemoryRegionType_DramKernelSecureUnknown.IsAncestorOf(type_id)) {
        return KMemoryRegionType_VirtualDramKernelSecureUnknown;
    } else if (KMemoryRegionType_KernelTraceBuffer.IsAncestorOf(type_id)) {
        return KMemoryRegionType_VirtualDramKernelTraceBuffer;
    } else if ((type_id | KMemoryRegionAttr_ShouldKernelMap) == type_id) {
        return KMemoryRegionType_VirtualDramUnknownDebug;
    } else {
        return KMemoryRegionType_Dram;
    }
}

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2023 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include "core/hle/kernel/k_object_name.h"

namespace Kernel {

KObjectNameGlobalData::KObjectNameGlobalData(KernelCore& kernel) : m_object_list_lock{kernel} {}
KObjectNameGlobalData::~KObjectNameGlobalData() = default;

void KObjectName::Initialize(KAutoObject* obj, const char* name) {
    // Set member variables.
    m_object = obj;
    std::strncpy(m_name.data(), name, sizeof(m_name) - 1);
    m_name[sizeof(m_name) - 1] = '\x00';

    // Open a reference to the object we hold.
    m_object->Open();
}

bool KObjectName::MatchesName(const char* name) const {
    return std::strncmp(m_name.data(), name, sizeof(m_name)) == 0;
}

Result KObjectName::NewFromName(KernelCore& kernel, KAutoObject* obj, const char* name) {
    // Create a new object name.
    KObjectName* new_name = KObjectName::Allocate(kernel);
    R_UNLESS(new_name != nullptr, ResultOutOfResource);

    // Initialize the new name.
    new_name->Initialize(obj, name);

    // Check if there's an existing name.
    {
        // Get the global data.
        KObjectNameGlobalData& gd{kernel.ObjectNameGlobalData()};

        // Ensure we have exclusive access to the global list.
        KScopedLightLock lk{gd.GetObjectListLock()};

        // If the object doesn't exist, put it into the list.
        KScopedAutoObject existing_object = FindImpl(kernel, name);
        if (existing_object.IsNull()) {
            gd.GetObjectList().push_back(*new_name);
            R_SUCCEED();
        }
    }

    // The object already exists, which is an error condition. Perform cleanup.
    obj->Close();
    KObjectName::Free(kernel, new_name);
    R_THROW(ResultInvalidState);
}

Result KObjectName::Delete(KernelCore& kernel, KAutoObject* obj, const char* compare_name) {
    // Get the global data.
    KObjectNameGlobalData& gd{kernel.ObjectNameGlobalData()};

    // Ensure we have exclusive access to the global list.
    KScopedLightLock lk{gd.GetObjectListLock()};

    // Find a matching entry in the list, and delete it.
    for (auto& name : gd.GetObjectList()) {
        if (name.MatchesName(compare_name) && obj == name.GetObject()) {
            // We found a match, clean up its resources.
            obj->Close();
            gd.GetObjectList().erase(gd.GetObjectList().iterator_to(name));
            KObjectName::Free(kernel, std::addressof(name));
            R_SUCCEED();
        }
    }

    // We didn't find the object in the list.
    R_THROW(ResultNotFound);
}

KScopedAutoObject<KAutoObject> KObjectName::Find(KernelCore& kernel, const char* name) {
    // Get the global data.
    KObjectNameGlobalData& gd{kernel.ObjectNameGlobalData()};

    // Ensure we have exclusive access to the global list.
    KScopedLightLock lk{gd.GetObjectListLock()};

    return FindImpl(kernel, name);
}

KScopedAutoObject<KAutoObject> KObjectName::FindImpl(KernelCore& kernel, const char* compare_name) {
    // Get the global data.
    KObjectNameGlobalData& gd{kernel.ObjectNameGlobalData()};

    // Try to find a matching object in the global list.
    for (const auto& name : gd.GetObjectList()) {
        if (name.MatchesName(compare_name)) {
            return name.GetObject();
        }
    }

    // There's no matching entry in the list.
    return nullptr;
}

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2023 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <array>
#include <memory>

#include "common/intrusive_list.h"

#include "core/hle/kernel/k_light_lock.h"
#include "core/hle/kernel/slab_helpers.h"
#include "core/hle/kernel/svc_results.h"

namespace Kernel {

class KObjectNameGlobalData;

class KObjectName : public KSlabAllocated<KObjectName>,
                    public Common::IntrusiveListBaseNode<KObjectName> {
public:
    explicit KObjectName(KernelCore&) {}
    virtual ~KObjectName() = default;

    static constexpr size_t NameLengthMax = 12;
    using List = Common::IntrusiveListBaseTraits<KObjectName>::ListType;

    static Result NewFromName(KernelCore& kernel, KAutoObject* obj, const char* name);
    static Result Delete(KernelCore& kernel, KAutoObject* obj, const char* name);

    static KScopedAutoObject<KAutoObject> Find(KernelCore& kernel, const char* name);

    template <typename Derived>
    static Result Delete(KernelCore& kernel, const char* name) {
        // Find the object.
        KScopedAutoObject obj = Find(kernel, name);
        R_UNLESS(obj.IsNotNull(), ResultNotFound);

        // Cast the object to the desired type.
        Derived* derived = obj->DynamicCast<Derived*>();
        R_UNLESS(derived != nullptr, ResultNotFound);

        // Check that the object is closed.
        R_UNLESS(derived->IsServerClosed(), ResultInvalidState);

        R_RETURN(Delete(kernel, obj.GetPointerUnsafe(), name));
    }

    template <typename Derived>
        requires(std::derived_from<Derived, KAutoObject>)
    static KScopedAutoObject<Derived> Find(KernelCore& kernel, const char* name) {
        return Find(kernel, name);
    }

private:
    static KScopedAutoObject<KAutoObject> FindImpl(KernelCore& kernel, const char* name);

    void Initialize(KAutoObject* obj, const char* name);

    bool MatchesName(const char* name) const;
    KAutoObject* GetObject() const {
        return m_object;
    }

private:
    std::array<char, NameLengthMax> m_name{};
    KAutoObject* m_object{};
};

class KObjectNameGlobalData {
public:
    explicit KObjectNameGlobalData(KernelCore& kernel);
    ~KObjectNameGlobalData();

    KLightLock& GetObjectListLock() {
        return m_object_list_lock;
    }

    KObjectName::List& GetObjectList() {
        return m_object_list;
    }

private:
    KLightLock m_object_list_lock;
    KObjectName::List m_object_list;
};

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <array>
#include <bit>

#include "common/alignment.h"
#include "common/assert.h"
#include "common/bit_util.h"
#include "common/common_types.h"
#include "common/tiny_mt.h"
#include "core/hle/kernel/k_system_control.h"

namespace Kernel {

class KPageBitmap {
public:
    class RandomBitGenerator {
    public:
        RandomBitGenerator() {
            m_rng.Initialize(static_cast<u32>(KSystemControl::GenerateRandomU64()));
        }

        u64 SelectRandomBit(u64 bitmap) {
            u64 selected = 0;

            for (size_t cur_num_bits = Common::BitSize<decltype(bitmap)>() / 2; cur_num_bits != 0;
                 cur_num_bits /= 2) {
                const u64 high = (bitmap >> cur_num_bits);
                const u64 low = (bitmap & (~(UINT64_C(0xFFFFFFFFFFFFFFFF) << cur_num_bits)));

                // Choose high if we have high and (don't have low or select high randomly).
                if (high && (low == 0 || this->GenerateRandomBit())) {
                    bitmap = high;
                    selected += cur_num_bits;
                } else {
                    bitmap = low;
                    selected += 0;
                }
            }

            return selected;
        }

        u64 GenerateRandom(u64 max) {
            // Determine the number of bits we need.
            const u64 bits_needed = 1 + (Common::BitSize<decltype(max)>() - std::countl_zero(max));

            // Generate a random value of the desired bitwidth.
            const u64 rnd = this->GenerateRandomBits(static_cast<u32>(bits_needed));

            // Adjust the value to be in range.
            return rnd - ((rnd / max) * max);
        }

    private:
        void RefreshEntropy() {
            m_entropy = m_rng.GenerateRandomU32();
            m_bits_available = static_cast<u32>(Common::BitSize<decltype(m_entropy)>());
        }

        bool GenerateRandomBit() {
            if (m_bits_available == 0) {
                this->RefreshEntropy();
            }

            const bool rnd_bit = (m_entropy & 1) != 0;
            m_entropy >>= 1;
            --m_bits_available;
            return rnd_bit;
        }

        u64 GenerateRandomBits(u32 num_bits) {
            u64 result = 0;

            // Iteratively add random bits to our result.
            while (num_bits > 0) {
                // Ensure we have random bits to take from.
                if (m_bits_available == 0) {
                    this->RefreshEntropy();
                }

                // Determine how many bits to take this round.
                const auto cur_bits = std::min(num_bits, m_bits_available);

                // Generate mask for our current bits.
                const u64 mask = (static_cast<u64>(1) << cur_bits) - 1;

                // Add bits to output from our entropy.
                result <<= cur_bits;
                result |= (m_entropy & mask);

                // Remove bits from our entropy.
                m_entropy >>= cur_bits;
                m_bits_available -= cur_bits;

                // Advance.
                num_bits -= cur_bits;
            }

            return result;
        }

    private:
        Common::TinyMT m_rng;
        u32 m_entropy{};
        u32 m_bits_available{};
    };

public:
    static constexpr size_t MaxDepth = 4;

public:
    KPageBitmap() = default;

    constexpr size_t GetNumBits() const {
        return m_num_bits;
    }
    constexpr s32 GetHighestDepthIndex() const {
        return static_cast<s32>(m_used_depths) - 1;
    }

    u64* Initialize(u64* storage, size_t size) {
        // Initially, everything is un-set.
        m_num_bits = 0;

        // Calculate the needed bitmap depth.
        m_used_depths = static_cast<size_t>(GetRequiredDepth(size));
        ASSERT(m_used_depths <= MaxDepth);

        // Set the bitmap pointers.
        for (s32 depth = this->GetHighestDepthIndex(); depth >= 0; depth--) {
            m_bit_storages[depth] = storage;
            size = Common::AlignUp(size, Common::BitSize<u64>()) / Common::BitSize<u64>();
            storage += size;
            m_end_storages[depth] = storage;
        }

        return storage;
    }

    s64 FindFreeBlock(bool random) {
        uintptr_t offset = 0;
        s32 depth = 0;

        if (random) {
            do {
                const u64 v = m_bit_storages[depth][offset];
                if (v == 0) {
                    // If depth is bigger than zero, then a previous level indicated a block was
                    // free.
                    ASSERT(depth == 0);
                    return -1;
                }
                offset = offset * Common::BitSize<u64>() + m_rng.SelectRandomBit(v);
                ++depth;
            } while (depth < static_cast<s32>(m_used_depths));
        } else {
            do {
                const u64 v = m_bit_storages[depth][offset];
                if (v == 0) {
                    // If depth is bigger than zero, then a previous level indicated a block was
                    // free.
                    ASSERT(depth == 0);
                    return -1;
                }
                offset = offset * Common::BitSize<u64>() + std::countr_zero(v);
                ++depth;
            } while (depth < static_cast<s32>(m_used_depths));
        }

        return static_cast<s64>(offset);
    }

    s64 FindFreeRange(size_t count) {
        // Check that it is possible to find a range.
        const u64* const storage_start = m_bit_storages[m_used_depths - 1];
        const u64* const storage_end = m_end_storages[m_used_depths - 1];

        // If we don't have a storage to iterate (or want more blocks than fit in a single storage),
        // we can't find a free range.
        if (!(storage_start < storage_end && count <= Common::BitSize<u64>())) {
            return -1;
        }

        // Walk the storages to select a random free range.
        const size_t options_per_storage = std::max<size_t>(Common::BitSize<u64>() / count, 1);
        const size_t num_entries = std::max<size_t>(storage_end - storage_start, 1);

        const u64 free_mask = (static_cast<u64>(1) << count) - 1;

        size_t num_valid_options = 0;
        s64 chosen_offset = -1;
        for (size_t storage_index = 0; storage_index < num_entries; ++storage_index) {
            u64 storage = storage_start[storage_index];
            for (size_t option = 0; option < options_per_storage; ++option) {
                if ((storage & free_mask) == free_mask) {
                    // We've found a new valid option.
                    ++num_valid_options;

                    // Select the Kth valid option with probability 1/K. This leads to an overall
                    // uniform distribution.
                    if (num_valid_options == 1 || m_rng.GenerateRandom(num_valid_options) == 0) {
                        // This is our first option, so select it.
                        chosen_offset = storage_index * Common::BitSize<u64>() + option * count;
                    }
                }
                storage >>= count;
            }
        }

        // Return the random offset we chose.*/
        return chosen_offset;
    }

    void SetBit(size_t offset) {
        this->SetBit(this->GetHighestDepthIndex(), offset);
        m_num_bits++;
    }

    void ClearBit(size_t offset) {
        this->ClearBit(this->GetHighestDepthIndex(), offset);
        m_num_bits--;
    }

    bool ClearRange(size_t offset, size_t count) {
        s32 depth = this->GetHighestDepthIndex();
        u64* bits = m_bit_storages[depth];
        size_t bit_ind = offset / Common::BitSize<u64>();
        if (count < Common::BitSize<u64>()) [[likely]] {
            const size_t shift = offset % Common::BitSize<u64>();
            ASSERT(shift + count <= Common::BitSize<u64>());
            // Check that all the bits are set.
            const u64 mask = ((u64(1) << count) - 1) << shift;
            u64 v = bits[bit_ind];
            if ((v & mask) != mask) {
                return false;
            }

            // Clear the bits.
            v &= ~mask;
            bits[bit_ind] = v;
            if (v == 0) {
                this->ClearBit(depth - 1, bit_ind);
            }
        } else {
            ASSERT(offset % Common::BitSize<u64>() == 0);
            ASSERT(count % Common::BitSize<u64>() == 0);
            // Check that all the bits are set.
            size_t remaining = count;
            size_t i = 0;
            do {
                if (bits[bit_ind + i++] != ~u64(0)) {
                    return false;
                }
                remaining -= Common::BitSize<u64>();
            } while (remaining > 0);

            // Clear the bits.
            remaining = count;
            i = 0;
            do {
                bits[bit_ind + i] = 0;
                this->ClearBit(depth - 1, bit_ind + i);
                i++;
                remaining -= Common::BitSize<u64>();
            } while (remaining > 0);
        }

        m_num_bits -= count;
        return true;
    }

private:
    void SetBit(s32 depth, size_t offset) {
        while (depth >= 0) {
            size_t ind = offset / Common::BitSize<u64>();
            size_t which = offset % Common::BitSize<u64>();
            const u64 mask = u64(1) << which;

            u64* bit = std::addressof(m_bit_storages[depth][ind]);
            u64 v = *bit;
            ASSERT((v & mask) == 0);
            *bit = v | mask;
            if (v) {
                break;
            }
            offset = ind;
            depth--;
        }
    }

    void ClearBit(s32 depth, size_t offset) {
        while (depth >= 0) {
            size_t ind = offset / Common::BitSize<u64>();
            size_t which = offset % Common::BitSize<u64>();
            const u64 mask = u64(1) << which;

            u64* bit = std::addressof(m_bit_storages[depth][ind]);
            u64 v = *bit;
            ASSERT((v & mask) != 0);
            v &= ~mask;
            *bit = v;
            if (v) {
                break;
            }
            offset = ind;
            depth--;
        }
    }

private:
    static constexpr s32 GetRequiredDepth(size_t region_size) {
        s32 depth = 0;
        while (true) {
            region_size /= Common::BitSize<u64>();
            depth++;
            if (region_size == 0) {
                return depth;
            }
        }
    }

public:
    static constexpr size_t CalculateManagementOverheadSize(size_t region_size) {
        size_t overhead_bits = 0;
        for (s32 depth = GetRequiredDepth(region_size) - 1; depth >= 0; depth--) {
            region_size =
                Common::AlignUp(region_size, Common::BitSize<u64>()) / Common::BitSize<u64>();
            overhead_bits += region_size;
        }
        return overhead_bits * sizeof(u64);
    }

private:
    std::array<u64*, MaxDepth> m_bit_storages{};
    std::array<u64*, MaxDepth> m_end_storages{};
    RandomBitGenerator m_rng;
    size_t m_num_bits{};
    size_t m_used_depths{};
};

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include "common/alignment.h"
#include "common/assert.h"
#include "core/core.h"
#include "core/device_memory.h"
#include "core/hle/kernel/k_page_buffer.h"
#include "core/hle/kernel/memory_types.h"

namespace Kernel {

KPageBuffer* KPageBuffer::FromPhysicalAddress(Core::System& system, KPhysicalAddress phys_addr) {
    ASSERT(Common::IsAligned(GetInteger(phys_addr), PageSize));
    return system.DeviceMemory().GetPointer<KPageBuffer>(phys_addr);
}

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <array>

#include "common/common_types.h"
#include "core/hle/kernel/memory_types.h"
#include "core/hle/kernel/slab_helpers.h"

namespace Kernel {

class KernelCore;

class KPageBufferSlabHeap : protected impl::KSlabHeapImpl {
public:
    static constexpr size_t BufferSize = PageSize;

public:
    void Initialize(Core::System& system);
};

class KPageBuffer final : public KSlabAllocated<KPageBuffer> {
public:
    explicit KPageBuffer(KernelCore&) {}
    KPageBuffer() = default;

    static KPageBuffer* FromPhysicalAddress(Core::System& system, KPhysicalAddress phys_addr);

private:
    alignas(PageSize) std::array<u8, PageSize> m_buffer{};
};
static_assert(sizeof(KPageBuffer) == KPageBufferSlabHeap::BufferSize);

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include "core/hle/kernel/k_dynamic_resource_manager.h"
#include "core/hle/kernel/k_memory_manager.h"
#include "core/hle/kernel/k_page_group.h"
#include "core/hle/kernel/kernel.h"
#include "core/hle/kernel/svc_results.h"

namespace Kernel {

void KPageGroup::Finalize() {
    KBlockInfo* cur = m_first_block;
    while (cur != nullptr) {
        KBlockInfo* next = cur->GetNext();
        m_manager->Free(cur);
        cur = next;
    }

    m_first_block = nullptr;
    m_last_block = nullptr;
}

void KPageGroup::CloseAndReset() {
    auto& mm = m_kernel.MemoryManager();

    KBlockInfo* cur = m_first_block;
    while (cur != nullptr) {
        KBlockInfo* next = cur->GetNext();
        mm.Close(cur->GetAddress(), cur->GetNumPages());
        m_manager->Free(cur);
        cur = next;
    }

    m_first_block = nullptr;
    m_last_block = nullptr;
}

size_t KPageGroup::GetNumPages() const {
    size_t num_pages = 0;

    for (const auto& it : *this) {
        num_pages += it.GetNumPages();
    }

    return num_pages;
}

Result KPageGroup::AddBlock(KPhysicalAddress addr, size_t num_pages) {
    // Succeed immediately if we're adding no pages.
    R_SUCCEED_IF(num_pages == 0);

    // Check for overflow.
    ASSERT(addr < addr + num_pages * PageSize);

    // Try to just append to the last block.
    if (m_last_block != nullptr) {
        R_SUCCEED_IF(m_last_block->TryConcatenate(addr, num_pages));
    }

    // Allocate a new block.
    KBlockInfo* new_block = m_manager->Allocate();
    R_UNLESS(new_block != nullptr, ResultOutOfResource);

    // Initialize the block.
    new_block->Initialize(addr, num_pages);

    // Add the block to our list.
    if (m_last_block != nullptr) {
        m_last_block->SetNext(new_block);
    } else {
        m_first_block = new_block;
    }
    m_last_block = new_block;

    R_SUCCEED();
}

void KPageGroup::Open() const {
    auto& mm = m_kernel.MemoryManager();

    for (const auto& it : *this) {
        mm.Open(it.GetAddress(), it.GetNumPages());
    }
}

void KPageGroup::OpenFirst() const {
    auto& mm = m_kernel.MemoryManager();

    for (const auto& it : *this) {
        mm.OpenFirst(it.GetAddress(), it.GetNumPages());
    }
}

void KPageGroup::Close() const {
    auto& mm = m_kernel.MemoryManager();

    for (const auto& it : *this) {
        mm.Close(it.GetAddress(), it.GetNumPages());
    }
}

bool KPageGroup::IsEquivalentTo(const KPageGroup& rhs) const {
    auto lit = this->begin();
    auto rit = rhs.begin();
    auto lend = this->end();
    auto rend = rhs.end();

    while (lit != lend && rit != rend) {
        if (*lit != *rit) {
            return false;
        }

        ++lit;
        ++rit;
    }

    return lit == lend && rit == rend;
}

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <list>

#include "common/alignment.h"
#include "common/assert.h"
#include "common/common_types.h"
#include "core/hle/kernel/memory_types.h"
#include "core/hle/result.h"

namespace Kernel {

class KBlockInfoManager;
class KernelCore;
class KPageGroup;

class KBlockInfo {
public:
    constexpr explicit KBlockInfo() : m_next(nullptr) {}

    constexpr void Initialize(KPhysicalAddress addr, size_t np) {
        ASSERT(Common::IsAligned(GetInteger(addr), PageSize));
        ASSERT(static_cast<u32>(np) == np);

        m_page_index = static_cast<u32>(addr / PageSize);
        m_num_pages = static_cast<u32>(np);
    }

    constexpr KPhysicalAddress GetAddress() const {
        return m_page_index * PageSize;
    }
    constexpr size_t GetNumPages() const {
        return m_num_pages;
    }
    constexpr size_t GetSize() const {
        return this->GetNumPages() * PageSize;
    }
    constexpr KPhysicalAddress GetEndAddress() const {
        return (m_page_index + m_num_pages) * PageSize;
    }
    constexpr KPhysicalAddress GetLastAddress() const {
        return this->GetEndAddress() - 1;
    }

    constexpr KBlockInfo* GetNext() const {
        return m_next;
    }

    constexpr bool IsEquivalentTo(const KBlockInfo& rhs) const {
        return m_page_index == rhs.m_page_index && m_num_pages == rhs.m_num_pages;
    }

    constexpr bool operator==(const KBlockInfo& rhs) const {
        return this->IsEquivalentTo(rhs);
    }

    constexpr bool operator!=(const KBlockInfo& rhs) const {
        return !(*this == rhs);
    }

    constexpr bool IsStrictlyBefore(KPhysicalAddress addr) const {
        const KPhysicalAddress end = this->GetEndAddress();

        if (m_page_index != 0 && end == 0) {
            return false;
        }

        return end < addr;
    }

    constexpr bool operator<(KPhysicalAddress addr) const {
        return this->IsStrictlyBefore(addr);
    }

    constexpr bool TryConcatenate(KPhysicalAddress addr, size_t np) {
        if (addr != 0 && addr == this->GetEndAddress()) {
            m_num_pages += static_cast<u32>(np);
            return true;
        }
        return false;
    }

private:
    constexpr void SetNext(KBlockInfo* next) {
        m_next = next;
    }

private:
    friend class KPageGroup;

    KBlockInfo* m_next{};
    u32 m_page_index{};
    u32 m_num_pages{};
};
static_assert(sizeof(KBlockInfo) <= 0x10);

class KPageGroup {
public:
    class Iterator {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = const KBlockInfo;
        using difference_type = std::ptrdiff_t;
        using pointer = value_type*;
        using reference = value_type&;

        constexpr explicit Iterator(pointer n) : m_node(n) {}

        constexpr bool operator==(const Iterator& rhs) const {
            return m_node == rhs.m_node;
        }
        constexpr bool operator!=(const Iterator& rhs) const {
            return !(*this == rhs);
        }

        constexpr pointer operator->() const {
            return m_node;
        }
        constexpr reference operator*() const {
            return *m_node;
        }

        constexpr Iterator& operator++() {
            m_node = m_node->GetNext();
            return *this;
        }

        constexpr Iterator operator++(int) {
            const Iterator it{*this};
            ++(*this);
            return it;
        }

    private:
        pointer m_node{};
    };

    explicit KPageGroup(KernelCore& kernel, KBlockInfoManager* m)
        : m_kernel{kernel}, m_manager{m} {}
    ~KPageGroup() {
        this->Finalize();
    }

    void CloseAndReset();
    void Finalize();

    Iterator begin() const {
        return Iterator{m_first_block};
    }
    Iterator end() const {
        return Iterator{nullptr};
    }
    bool empty() const {
        return m_first_block == nullptr;
    }

    Result AddBlock(KPhysicalAddress addr, size_t num_pages);
    void Open() const;
    void OpenFirst() const;
    void Close() const;

    size_t GetNumPages() const;

    bool IsEquivalentTo(const KPageGroup& rhs) const;

    bool operator==(const KPageGroup& rhs) const {
        return this->IsEquivalentTo(rhs);
    }

    bool operator!=(const KPageGroup& rhs) const {
        return !(*this == rhs);
    }

private:
    KernelCore& m_kernel;
    KBlockInfo* m_first_block{};
    KBlockInfo* m_last_block{};
    KBlockInfoManager* m_manager{};
};

class KScopedPageGroup {
public:
    explicit KScopedPageGroup(const KPageGroup* gp, bool not_first = true) : m_pg(gp) {
        if (m_pg) {
            if (not_first) {
                m_pg->Open();
            } else {
                m_pg->OpenFirst();
            }
        }
    }
    explicit KScopedPageGroup(const KPageGroup& gp, bool not_first = true)
        : KScopedPageGroup(std::addressof(gp), not_first) {}
    ~KScopedPageGroup() {
        if (m_pg) {
            m_pg->Close();
        }
    }

    void CancelClose() {
        m_pg = nullptr;
    }

private:
    const KPageGroup* m_pg{};
};

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#include "core/core.h"
#include "core/hle/kernel/k_page_heap.h"

namespace Kernel {

void KPageHeap::Initialize(KPhysicalAddress address, size_t size,
                           KVirtualAddress management_address, size_t management_size,
                           const size_t* block_shifts, size_t num_block_shifts) {
    // Check our assumptions.
    ASSERT(Common::IsAligned(GetInteger(address), PageSize));
    ASSERT(Common::IsAligned(size, PageSize));
    ASSERT(0 < num_block_shifts && num_block_shifts <= NumMemoryBlockPageShifts);
    const KVirtualAddress management_end = management_address + management_size;

    // Set our members.
    m_heap_address = address;
    m_heap_size = size;
    m_num_blocks = num_block_shifts;

    // Setup bitmaps.
    m_management_data.resize(management_size / sizeof(u64));
    u64* cur_bitmap_storage{m_management_data.data()};
    for (size_t i = 0; i < num_block_shifts; i++) {
        const size_t cur_block_shift = block_shifts[i];
        const size_t next_block_shift = (i != num_block_shifts - 1) ? block_shifts[i + 1] : 0;
        cur_bitmap_storage = m_blocks[i].Initialize(m_heap_address, m_heap_size, cur_block_shift,
                                                    next_block_shift, cur_bitmap_storage);
    }

    // Ensure we didn't overextend our bounds.
    ASSERT(KVirtualAddress(cur_bitmap_storage) <= management_end);
}

size_t KPageHeap::GetNumFreePages() const {
    size_t num_free = 0;

    for (size_t i = 0; i < m_num_blocks; i++) {
        num_free += m_blocks[i].GetNumFreePages();
    }

    return num_free;
}

KPhysicalAddress 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 KPhysicalAddress 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);
            }
            return addr;
        }
    }

    return 0;
}

KPhysicalAddress 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 (KPhysicalAddress 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(KPhysicalAddress block, s32 index) {
    do {
        block = m_blocks[index++].PushBlock(block);
    } while (block != 0);
}

void KPageHeap::Free(KPhysicalAddress addr, size_t num_pages) {
    // Freeing no pages is a no-op.
    if (num_pages == 0) {
        return;
    }

    // Find the largest block size that we can free, and free as many as possible.
    s32 big_index = static_cast<s32>(m_num_blocks) - 1;
    const KPhysicalAddress start = addr;
    const KPhysicalAddress end = addr + num_pages * PageSize;
    KPhysicalAddress before_start = start;
    KPhysicalAddress before_end = start;
    KPhysicalAddress after_start = end;
    KPhysicalAddress after_end = end;
    while (big_index >= 0) {
        const size_t block_size = m_blocks[big_index].GetSize();
        const KPhysicalAddress big_start = Common::AlignUp(GetInteger(start), block_size);
        const KPhysicalAddress big_end = Common::AlignDown(GetInteger(end), block_size);
        if (big_start < big_end) {
            // Free as many big blocks as we can.
            for (auto block = big_start; block < big_end; block += block_size) {
                this->FreeBlock(block, big_index);
            }
            before_end = big_start;
            after_start = big_end;
            break;
        }
        big_index--;
    }
    ASSERT(big_index >= 0);

    // Free space before the big blocks.
    for (s32 i = big_index - 1; i >= 0; i--) {
        const size_t block_size = m_blocks[i].GetSize();
        while (before_start + block_size <= before_end) {
            before_end -= block_size;
            this->FreeBlock(before_end, i);
        }
    }

    // Free space after the big blocks.
    for (s32 i = big_index - 1; i >= 0; i--) {
        const size_t block_size = m_blocks[i].GetSize();
        while (after_start + block_size <= after_end) {
            this->FreeBlock(after_start, i);
            after_start += block_size;
        }
    }
}

size_t KPageHeap::CalculateManagementOverheadSize(size_t region_size, const size_t* block_shifts,
                                                  size_t num_block_shifts) {
    size_t overhead_size = 0;
    for (size_t i = 0; i < num_block_shifts; i++) {
        const size_t cur_block_shift = block_shifts[i];
        const size_t next_block_shift = (i != num_block_shifts - 1) ? block_shifts[i + 1] : 0;
        overhead_size += KPageHeap::Block::CalculateManagementOverheadSize(
            region_size, cur_block_shift, next_block_shift);
    }
    return Common::AlignUp(overhead_size, PageSize);
}

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include <array>
#include <vector>

#include "common/alignment.h"
#include "common/common_funcs.h"
#include "core/hle/kernel/k_page_bitmap.h"
#include "core/hle/kernel/k_typed_address.h"
#include "core/hle/kernel/memory_types.h"

namespace Kernel {

class KPageHeap {
public:
    KPageHeap() = default;

    constexpr KPhysicalAddress GetAddress() const {
        return m_heap_address;
    }
    constexpr size_t GetSize() const {
        return m_heap_size;
    }
    constexpr KPhysicalAddress GetEndAddress() const {
        return this->GetAddress() + this->GetSize();
    }
    constexpr size_t GetPageOffset(KPhysicalAddress block) const {
        return (block - this->GetAddress()) / PageSize;
    }
    constexpr size_t GetPageOffsetToEnd(KPhysicalAddress block) const {
        return (this->GetEndAddress() - block) / PageSize;
    }

    void Initialize(KPhysicalAddress heap_address, size_t heap_size,
                    KVirtualAddress management_address, size_t management_size) {
        return this->Initialize(heap_address, heap_size, management_address, management_size,
                                MemoryBlockPageShifts.data(), NumMemoryBlockPageShifts);
    }

    size_t GetFreeSize() const {
        return this->GetNumFreePages() * PageSize;
    }

    void SetInitialUsedSize(size_t reserved_size) {
        // Check that the reserved size is valid.
        const size_t free_size = this->GetNumFreePages() * PageSize;
        ASSERT(m_heap_size >= free_size + reserved_size);

        // Set the initial used size.
        m_initial_used_size = m_heap_size - free_size - reserved_size;
    }

    KPhysicalAddress AllocateBlock(s32 index, bool random) {
        if (random) {
            const size_t block_pages = m_blocks[index].GetNumPages();
            return this->AllocateByRandom(index, block_pages, block_pages);
        } else {
            return this->AllocateByLinearSearch(index);
        }
    }

    KPhysicalAddress AllocateAligned(s32 index, size_t num_pages, size_t align_pages) {
        // TODO: linear search support?
        return this->AllocateByRandom(index, num_pages, align_pages);
    }

    void Free(KPhysicalAddress addr, size_t num_pages);

    static size_t CalculateManagementOverheadSize(size_t region_size) {
        return CalculateManagementOverheadSize(region_size, MemoryBlockPageShifts.data(),
                                               NumMemoryBlockPageShifts);
    }

    static constexpr s32 GetAlignedBlockIndex(size_t num_pages, size_t align_pages) {
        const size_t target_pages = std::max(num_pages, align_pages);
        for (size_t i = 0; i < NumMemoryBlockPageShifts; i++) {
            if (target_pages <= (static_cast<size_t>(1) << MemoryBlockPageShifts[i]) / PageSize) {
                return static_cast<s32>(i);
            }
        }
        return -1;
    }

    static constexpr s32 GetBlockIndex(size_t num_pages) {
        for (s32 i = static_cast<s32>(NumMemoryBlockPageShifts) - 1; i >= 0; i--) {
            if (num_pages >= (static_cast<size_t>(1) << MemoryBlockPageShifts[i]) / PageSize) {
                return i;
            }
        }
        return -1;
    }

    static constexpr size_t GetBlockSize(size_t index) {
        return static_cast<size_t>(1) << MemoryBlockPageShifts[index];
    }

    static constexpr size_t GetBlockNumPages(size_t index) {
        return GetBlockSize(index) / PageSize;
    }

private:
    class Block {
    public:
        Block() = default;

        constexpr size_t GetShift() const {
            return m_block_shift;
        }
        constexpr size_t GetNextShift() const {
            return m_next_block_shift;
        }
        constexpr size_t GetSize() const {
            return u64(1) << this->GetShift();
        }
        constexpr size_t GetNumPages() const {
            return this->GetSize() / PageSize;
        }
        constexpr size_t GetNumFreeBlocks() const {
            return m_bitmap.GetNumBits();
        }
        constexpr size_t GetNumFreePages() const {
            return this->GetNumFreeBlocks() * this->GetNumPages();
        }

        u64* Initialize(KPhysicalAddress addr, size_t size, size_t bs, size_t nbs,
                        u64* bit_storage) {
            // Set shifts.
            m_block_shift = bs;
            m_next_block_shift = nbs;

            // Align up the address.
            KPhysicalAddress end = addr + size;
            const size_t align = (m_next_block_shift != 0) ? (u64(1) << m_next_block_shift)
                                                           : (u64(1) << m_block_shift);
            addr = Common::AlignDown(GetInteger(addr), align);
            end = Common::AlignUp(GetInteger(end), align);

            m_heap_address = addr;
            m_end_offset = (end - addr) / (u64(1) << m_block_shift);
            return m_bitmap.Initialize(bit_storage, m_end_offset);
        }

        KPhysicalAddress PushBlock(KPhysicalAddress address) {
            // Set the bit for the free block.
            size_t offset = (address - m_heap_address) >> this->GetShift();
            m_bitmap.SetBit(offset);

            // If we have a next shift, try to clear the blocks below this one and return the new
            // address.
            if (this->GetNextShift()) {
                const size_t diff = u64(1) << (this->GetNextShift() - this->GetShift());
                offset = Common::AlignDown(offset, diff);
                if (m_bitmap.ClearRange(offset, diff)) {
                    return m_heap_address + (offset << this->GetShift());
                }
            }

            // We couldn't coalesce, or we're already as big as possible.
            return {};
        }

        KPhysicalAddress PopBlock(bool random) {
            // Find a free block.
            s64 soffset = m_bitmap.FindFreeBlock(random);
            if (soffset < 0) {
                return {};
            }
            const size_t offset = static_cast<size_t>(soffset);

            // Update our tracking and return it.
            m_bitmap.ClearBit(offset);
            return m_heap_address + (offset << this->GetShift());
        }

    public:
        static constexpr size_t CalculateManagementOverheadSize(size_t region_size,
                                                                size_t cur_block_shift,
                                                                size_t next_block_shift) {
            const size_t cur_block_size = (u64(1) << cur_block_shift);
            const size_t next_block_size = (u64(1) << next_block_shift);
            const size_t align = (next_block_shift != 0) ? next_block_size : cur_block_size;
            return KPageBitmap::CalculateManagementOverheadSize(
                (align * 2 + Common::AlignUp(region_size, align)) / cur_block_size);
        }

    private:
        KPageBitmap m_bitmap;
        KPhysicalAddress m_heap_address{};
        uintptr_t m_end_offset{};
        size_t m_block_shift{};
        size_t m_next_block_shift{};
    };

private:
    void Initialize(KPhysicalAddress heap_address, size_t heap_size,
                    KVirtualAddress management_address, size_t management_size,
                    const size_t* block_shifts, size_t num_block_shifts);
    size_t GetNumFreePages() const;

    void FreeBlock(KPhysicalAddress block, s32 index);

    static constexpr size_t NumMemoryBlockPageShifts{7};
    static constexpr std::array<size_t, NumMemoryBlockPageShifts> MemoryBlockPageShifts{
        0xC, 0x10, 0x15, 0x16, 0x19, 0x1D, 0x1E,
    };

private:
    KPhysicalAddress AllocateByLinearSearch(s32 index);
    KPhysicalAddress AllocateByRandom(s32 index, size_t num_pages, size_t align_pages);

    static size_t CalculateManagementOverheadSize(size_t region_size, const size_t* block_shifts,
                                                  size_t num_block_shifts);

private:
    KPhysicalAddress m_heap_address{};
    size_t m_heap_size{};
    size_t m_initial_used_size{};
    size_t m_num_blocks{};
    std::array<Block, NumMemoryBlockPageShifts> m_blocks;
    KPageBitmap::RandomBitGenerator m_rng;
    std::vector<u64> m_management_data;
};

} // namespace Kernel


code:
// SPDX-FileCopyrightText: Copyright 2020 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include "core/hle/kernel/k_page_table_base.h"

namespace Kernel {

class KPageTable final : public KPageTableBase {
public:
    explicit KPageTable(KernelCore& kernel) : KPageTableBase(kernel) {}
    ~KPageTable() = default;
};

} // namespace Kernel