Kernel: Use intrusive RegionTree solution for kernel regions as well

This patch ports MemoryManager to RegionTree as well. The biggest
difference between this and the userspace code is that kernel regions
are owned by extant OwnPtr<Region> objects spread around the kernel,
while userspace regions are owned by the AddressSpace itself.

For kernelspace, there are a couple of situations where we need to make
large VM reservations that never get backed by regular VMObjects
(for example the kernel image reservation, or the big kmalloc range.)
Since we can't make a VM reservation without a Region object anymore,
this patch adds a way to create unbacked Region objects that can be
used for this exact purpose. They have no internal VMObject.)

9 files changed, 65 insertions, 43 deletions

diff --git a/Kernel/Memory/MemoryManager.cpp b/Kernel/Memory/MemoryManager.cpp
index 833ae22812..874bc868a2 100644
--- a/Kernel/Memory/MemoryManager.cpp
+++ b/Kernel/Memory/MemoryManager.cpp
@@ -23,6 +23,7 @@
 #include <Kernel/Memory/SharedInodeVMObject.h>
 #include <Kernel/Multiboot.h>
 #include <Kernel/Panic.h>
+#include <Kernel/Prekernel/Prekernel.h>
 #include <Kernel/Process.h>
 #include <Kernel/Sections.h>
 #include <Kernel/StdLib.h>
@@ -74,7 +75,14 @@ bool MemoryManager::is_initialized()
     return s_the != nullptr;
 }
 
+static UNMAP_AFTER_INIT VirtualRange kernel_virtual_range()
+{
+    auto kernel_range_start = kernel_mapping_base + 2 * MiB; // The first 2 MiB are used for mapping the pre-kernel
+    return VirtualRange { VirtualAddress(kernel_range_start), KERNEL_PD_END - kernel_range_start };
+}
+
 UNMAP_AFTER_INIT MemoryManager::MemoryManager()
+    : m_region_tree(kernel_virtual_range())
 {
     s_the = this;
 
@@ -439,13 +447,20 @@ UNMAP_AFTER_INIT void MemoryManager::initialize_physical_pages()
     // Create the bare page directory. This is not a fully constructed page directory and merely contains the allocators!
     m_kernel_page_directory = PageDirectory::must_create_kernel_page_directory();
 
+    {
+        // Carve out the whole page directory covering the kernel image to make MemoryManager::initialize_physical_pages() happy
+        FlatPtr start_of_range = ((FlatPtr)start_of_kernel_image & ~(FlatPtr)0x1fffff);
+        FlatPtr end_of_range = ((FlatPtr)end_of_kernel_image & ~(FlatPtr)0x1fffff) + 0x200000;
+        auto reserved_range = MUST(m_region_tree.try_allocate_specific(VirtualAddress(start_of_range), end_of_range - start_of_range));
+        (void)MUST(Region::create_unbacked(reserved_range)).leak_ptr();
+    }
+
     // Allocate a virtual address range for our array
-    auto range_or_error = m_kernel_page_directory->range_allocator().try_allocate_anywhere(physical_page_array_pages * PAGE_SIZE);
-    if (range_or_error.is_error()) {
-        dmesgln("MM: Could not allocate {} bytes to map physical page array!", physical_page_array_pages * PAGE_SIZE);
-        VERIFY_NOT_REACHED();
+    auto range = MUST(m_region_tree.try_allocate_anywhere(physical_page_array_pages * PAGE_SIZE));
+
+    {
+        (void)MUST(Region::create_unbacked(range)).leak_ptr();
     }
-    auto range = range_or_error.release_value();
 
     // Now that we have our special m_physical_pages_region region with enough pages to hold the entire array
     // try to map the entire region into kernel space so we always have it
@@ -651,7 +666,7 @@ Region* MemoryManager::kernel_region_from_vaddr(VirtualAddress vaddr)
         return nullptr;
 
     SpinlockLocker lock(s_mm_lock);
-    auto* region = MM.m_kernel_regions.find_largest_not_above(vaddr.get());
+    auto* region = MM.m_region_tree.regions().find_largest_not_above(vaddr.get());
     if (!region || !region->contains(vaddr))
         return nullptr;
     return region;
@@ -757,7 +772,7 @@ ErrorOr<NonnullOwnPtr<Region>> MemoryManager::allocate_contiguous_kernel_region(
     VERIFY(!(size % PAGE_SIZE));
     SpinlockLocker lock(kernel_page_directory().get_lock());
     auto vmobject = TRY(AnonymousVMObject::try_create_physically_contiguous_with_size(size));
-    auto range = TRY(kernel_page_directory().range_allocator().try_allocate_anywhere(size));
+    auto range = TRY(m_region_tree.try_allocate_anywhere(size));
     return allocate_kernel_region_with_vmobject(range, move(vmobject), name, access, cacheable);
 }
 
@@ -796,7 +811,7 @@ ErrorOr<NonnullOwnPtr<Region>> MemoryManager::allocate_kernel_region(size_t size
     VERIFY(!(size % PAGE_SIZE));
     auto vmobject = TRY(AnonymousVMObject::try_create_with_size(size, strategy));
     SpinlockLocker lock(kernel_page_directory().get_lock());
-    auto range = TRY(kernel_page_directory().range_allocator().try_allocate_anywhere(size));
+    auto range = TRY(m_region_tree.try_allocate_anywhere(size));
     return allocate_kernel_region_with_vmobject(range, move(vmobject), name, access, cacheable);
 }
 
@@ -805,7 +820,7 @@ ErrorOr<NonnullOwnPtr<Region>> MemoryManager::allocate_kernel_region(PhysicalAdd
     VERIFY(!(size % PAGE_SIZE));
     auto vmobject = TRY(AnonymousVMObject::try_create_for_physical_range(paddr, size));
     SpinlockLocker lock(kernel_page_directory().get_lock());
-    auto range = TRY(kernel_page_directory().range_allocator().try_allocate_anywhere(size));
+    auto range = TRY(m_region_tree.try_allocate_anywhere(size));
     return allocate_kernel_region_with_vmobject(range, move(vmobject), name, access, cacheable);
 }
 
@@ -823,7 +838,7 @@ ErrorOr<NonnullOwnPtr<Region>> MemoryManager::allocate_kernel_region_with_vmobje
 {
     VERIFY(!(size % PAGE_SIZE));
     SpinlockLocker lock(kernel_page_directory().get_lock());
-    auto range = TRY(kernel_page_directory().range_allocator().try_allocate_anywhere(size));
+    auto range = TRY(m_region_tree.try_allocate_anywhere(size));
     return allocate_kernel_region_with_vmobject(range, vmobject, name, access, cacheable);
 }
 
@@ -1146,14 +1161,14 @@ void MemoryManager::register_kernel_region(Region& region)
 {
     VERIFY(region.is_kernel());
     SpinlockLocker lock(s_mm_lock);
-    m_kernel_regions.insert(region.vaddr().get(), region);
+    m_region_tree.regions().insert(region.vaddr().get(), region);
 }
 
 void MemoryManager::unregister_kernel_region(Region& region)
 {
     VERIFY(region.is_kernel());
     SpinlockLocker lock(s_mm_lock);
-    m_kernel_regions.remove(region.vaddr().get());
+    m_region_tree.regions().remove(region.vaddr().get());
 }
 
 void MemoryManager::dump_kernel_regions()
@@ -1167,7 +1182,7 @@ void MemoryManager::dump_kernel_regions()
     dbgln("BEGIN{}         END{}        SIZE{}       ACCESS NAME",
         addr_padding, addr_padding, addr_padding);
     SpinlockLocker lock(s_mm_lock);
-    for (auto const& region : m_kernel_regions) {
+    for (auto const& region : m_region_tree.regions()) {
         dbgln("{:p} -- {:p} {:p} {:c}{:c}{:c}{:c}{:c}{:c} {}",
             region.vaddr().get(),
             region.vaddr().offset(region.size() - 1).get(),
diff --git a/Kernel/Memory/MemoryManager.h b/Kernel/Memory/MemoryManager.h
index 73a230d40b..cac1fdce23 100644
--- a/Kernel/Memory/MemoryManager.h
+++ b/Kernel/Memory/MemoryManager.h
@@ -18,6 +18,7 @@
 #include <Kernel/Memory/PhysicalPage.h>
 #include <Kernel/Memory/PhysicalRegion.h>
 #include <Kernel/Memory/Region.h>
+#include <Kernel/Memory/RegionTree.h>
 #include <Kernel/Memory/VMObject.h>
 
 namespace Kernel {
@@ -245,6 +246,8 @@ public:
 
     IterationDecision for_each_physical_memory_range(Function<IterationDecision(PhysicalMemoryRange const&)>);
 
+    auto& region_tree() { return m_region_tree; }
+
 private:
     MemoryManager();
     ~MemoryManager();
@@ -297,7 +300,7 @@ private:
     PhysicalPageEntry* m_physical_page_entries { nullptr };
     size_t m_physical_page_entries_count { 0 };
 
-    IntrusiveRedBlackTree<&Region::m_tree_node> m_kernel_regions;
+    RegionTree m_region_tree;
 
     Vector<UsedMemoryRange> m_used_memory_ranges;
     Vector<PhysicalMemoryRange> m_physical_memory_ranges;
diff --git a/Kernel/Memory/PageDirectory.cpp b/Kernel/Memory/PageDirectory.cpp
index a1056074aa..5ce21fd65f 100644
--- a/Kernel/Memory/PageDirectory.cpp
+++ b/Kernel/Memory/PageDirectory.cpp
@@ -22,16 +22,7 @@ namespace Kernel::Memory {
 
 UNMAP_AFTER_INIT NonnullRefPtr<PageDirectory> PageDirectory::must_create_kernel_page_directory()
 {
-    auto directory = adopt_ref_if_nonnull(new (nothrow) PageDirectory).release_nonnull();
-
-    auto kernel_range_start = kernel_mapping_base + 2 * MiB; // The first 2 MiB are used for mapping the pre-kernel
-    MUST(directory->m_range_allocator.initialize_with_range(VirtualAddress(kernel_range_start), KERNEL_PD_END - kernel_range_start));
-    // Carve out the whole page directory covering the kernel image to make MemoryManager::initialize_physical_pages() happy
-    FlatPtr start_of_range = ((FlatPtr)start_of_kernel_image & ~(FlatPtr)0x1fffff);
-    FlatPtr end_of_range = ((FlatPtr)end_of_kernel_image & ~(FlatPtr)0x1fffff) + 0x200000;
-    MUST(directory->m_range_allocator.try_allocate_specific(VirtualAddress(start_of_range), end_of_range - start_of_range));
-
-    return directory;
+    return adopt_ref_if_nonnull(new (nothrow) PageDirectory).release_nonnull();
 }
 
 ErrorOr<NonnullRefPtr<PageDirectory>> PageDirectory::try_create_for_userspace()
diff --git a/Kernel/Memory/PageDirectory.h b/Kernel/Memory/PageDirectory.h
index 5bad876153..2e09106e0b 100644
--- a/Kernel/Memory/PageDirectory.h
+++ b/Kernel/Memory/PageDirectory.h
@@ -13,7 +13,6 @@
 #include <AK/RefPtr.h>
 #include <Kernel/Forward.h>
 #include <Kernel/Memory/PhysicalPage.h>
-#include <Kernel/Memory/VirtualRangeAllocator.h>
 
 namespace Kernel::Memory {
 
@@ -47,9 +46,6 @@ public:
 #endif
     }
 
-    VirtualRangeAllocator& range_allocator() { return m_range_allocator; }
-    VirtualRangeAllocator const& range_allocator() const { return m_range_allocator; }
-
     AddressSpace* address_space() { return m_space; }
     AddressSpace const* address_space() const { return m_space; }
 
@@ -66,7 +62,6 @@ private:
     static void deregister_page_directory(PageDirectory* directory);
 
     AddressSpace* m_space { nullptr };
-    VirtualRangeAllocator m_range_allocator;
 #if ARCH(X86_64)
     RefPtr<PhysicalPage> m_pml4t;
 #endif
diff --git a/Kernel/Memory/Region.cpp b/Kernel/Memory/Region.cpp
index 962e8087e0..69d48bbea1 100644
--- a/Kernel/Memory/Region.cpp
+++ b/Kernel/Memory/Region.cpp
@@ -22,6 +22,13 @@
 
 namespace Kernel::Memory {
 
+Region::Region(VirtualRange const& range)
+    : m_range(range)
+{
+    if (is_kernel())
+        MM.register_kernel_region(*this);
+}
+
 Region::Region(VirtualRange const& range, NonnullRefPtr<VMObject> vmobject, size_t offset_in_vmobject, OwnPtr<KString> name, Region::Access access, Cacheable cacheable, bool shared)
     : m_range(range)
     , m_offset_in_vmobject(offset_in_vmobject)
@@ -56,10 +63,7 @@ Region::~Region()
     if (m_page_directory) {
         SpinlockLocker pd_locker(m_page_directory->get_lock());
         if (!is_readable() && !is_writable() && !is_executable()) {
-            // If the region is "PROT_NONE", we didn't map it in the first place,
-            // so all we need to do here is deallocate the VM.
-            if (is_kernel())
-                m_page_directory->range_allocator().deallocate(range());
+            // If the region is "PROT_NONE", we didn't map it in the first place.
         } else {
             SpinlockLocker mm_locker(s_mm_lock);
             unmap_with_locks_held(ShouldDeallocateVirtualRange::Yes, ShouldFlushTLB::Yes, pd_locker, mm_locker);
@@ -68,6 +72,11 @@ Region::~Region()
     }
 }
 
+ErrorOr<NonnullOwnPtr<Region>> Region::create_unbacked(VirtualRange const& range)
+{
+    return adopt_nonnull_own_or_enomem(new (nothrow) Region(range));
+}
+
 ErrorOr<NonnullOwnPtr<Region>> Region::try_clone()
 {
     VERIFY(Process::has_current());
@@ -84,7 +93,7 @@ ErrorOr<NonnullOwnPtr<Region>> Region::try_clone()
             region_name = TRY(m_name->try_clone());
 
         auto region = TRY(Region::try_create_user_accessible(
-            m_range, m_vmobject, m_offset_in_vmobject, move(region_name), access(), m_cacheable ? Cacheable::Yes : Cacheable::No, m_shared));
+            m_range, vmobject(), m_offset_in_vmobject, move(region_name), access(), m_cacheable ? Cacheable::Yes : Cacheable::No, m_shared));
         region->set_mmap(m_mmap);
         region->set_shared(m_shared);
         region->set_syscall_region(is_syscall_region());
@@ -259,7 +268,7 @@ void Region::unmap(ShouldDeallocateVirtualRange should_deallocate_range, ShouldF
     unmap_with_locks_held(should_deallocate_range, should_flush_tlb, pd_locker, mm_locker);
 }
 
-void Region::unmap_with_locks_held(ShouldDeallocateVirtualRange deallocate_range, ShouldFlushTLB should_flush_tlb, SpinlockLocker<RecursiveSpinlock>&, SpinlockLocker<RecursiveSpinlock>&)
+void Region::unmap_with_locks_held(ShouldDeallocateVirtualRange, ShouldFlushTLB should_flush_tlb, SpinlockLocker<RecursiveSpinlock>&, SpinlockLocker<RecursiveSpinlock>&)
 {
     if (!m_page_directory)
         return;
@@ -270,10 +279,6 @@ void Region::unmap_with_locks_held(ShouldDeallocateVirtualRange deallocate_range
     }
     if (should_flush_tlb == ShouldFlushTLB::Yes)
         MemoryManager::flush_tlb(m_page_directory, vaddr(), page_count());
-    if (deallocate_range == ShouldDeallocateVirtualRange::Yes) {
-        if (is_kernel())
-            m_page_directory->range_allocator().deallocate(range());
-    }
     m_page_directory = nullptr;
 }
 
diff --git a/Kernel/Memory/Region.h b/Kernel/Memory/Region.h
index 9b07a53c72..bc73075c85 100644
--- a/Kernel/Memory/Region.h
+++ b/Kernel/Memory/Region.h
@@ -14,7 +14,7 @@
 #include <Kernel/Forward.h>
 #include <Kernel/KString.h>
 #include <Kernel/Memory/PageFaultResponse.h>
-#include <Kernel/Memory/VirtualRangeAllocator.h>
+#include <Kernel/Memory/VirtualRange.h>
 #include <Kernel/Sections.h>
 #include <Kernel/UnixTypes.h>
 
@@ -56,6 +56,7 @@ public:
 
     static ErrorOr<NonnullOwnPtr<Region>> try_create_user_accessible(VirtualRange const&, NonnullRefPtr<VMObject>, size_t offset_in_vmobject, OwnPtr<KString> name, Region::Access access, Cacheable, bool shared);
     static ErrorOr<NonnullOwnPtr<Region>> try_create_kernel_only(VirtualRange const&, NonnullRefPtr<VMObject>, size_t offset_in_vmobject, OwnPtr<KString> name, Region::Access access, Cacheable = Cacheable::Yes);
+    static ErrorOr<NonnullOwnPtr<Region>> create_unbacked(VirtualRange const&);
 
     ~Region();
 
@@ -198,6 +199,7 @@ public:
     void set_syscall_region(bool b) { m_syscall_region = b; }
 
 private:
+    explicit Region(VirtualRange const&);
     Region(VirtualRange const&, NonnullRefPtr<VMObject>, size_t offset_in_vmobject, OwnPtr<KString>, Region::Access access, Cacheable, bool shared);
 
     [[nodiscard]] bool remap_vmobject_page(size_t page_index, bool with_flush = true);
@@ -220,7 +222,7 @@ private:
     RefPtr<PageDirectory> m_page_directory;
     VirtualRange m_range;
     size_t m_offset_in_vmobject { 0 };
-    NonnullRefPtr<VMObject> m_vmobject;
+    RefPtr<VMObject> m_vmobject;
     OwnPtr<KString> m_name;
     u8 m_access { Region::None };
     bool m_shared : 1 { false };
diff --git a/Kernel/Memory/RegionTree.cpp b/Kernel/Memory/RegionTree.cpp
index b2cb2ce708..67d3ef1580 100644
--- a/Kernel/Memory/RegionTree.cpp
+++ b/Kernel/Memory/RegionTree.cpp
@@ -140,4 +140,12 @@ ErrorOr<VirtualRange> RegionTree::try_allocate_randomized(size_t size, size_t al
 
     return try_allocate_anywhere(size, alignment);
 }
+
+ErrorOr<NonnullOwnPtr<Region>> RegionTree::allocate_unbacked_anywhere(size_t size, size_t alignment)
+{
+    SpinlockLocker locker(m_lock);
+    auto range = TRY(try_allocate_anywhere(size, alignment));
+    return Region::create_unbacked(range);
+}
+
 }
diff --git a/Kernel/Memory/RegionTree.h b/Kernel/Memory/RegionTree.h
index 386ba475b1..9a00db9f43 100644
--- a/Kernel/Memory/RegionTree.h
+++ b/Kernel/Memory/RegionTree.h
@@ -8,6 +8,7 @@
 
 #include <AK/Error.h>
 #include <AK/IntrusiveRedBlackTree.h>
+#include <Kernel/Locking/Spinlock.h>
 #include <Kernel/Memory/Region.h>
 #include <Kernel/Memory/VirtualRange.h>
 #include <Kernel/VirtualAddress.h>
@@ -31,6 +32,8 @@ public:
 
     VirtualRange total_range() const { return m_total_range; }
 
+    ErrorOr<NonnullOwnPtr<Region>> allocate_unbacked_anywhere(size_t size, size_t alignment = PAGE_SIZE);
+
     ErrorOr<VirtualRange> try_allocate_anywhere(size_t size, size_t alignment = PAGE_SIZE);
     ErrorOr<VirtualRange> try_allocate_specific(VirtualAddress base, size_t size);
     ErrorOr<VirtualRange> try_allocate_randomized(size_t size, size_t alignment = PAGE_SIZE);
@@ -38,6 +41,8 @@ public:
     void delete_all_regions_assuming_they_are_unmapped();
 
 private:
+    Spinlock m_lock;
+
     IntrusiveRedBlackTree<&Region::m_tree_node> m_regions;
     VirtualRange const m_total_range;
 };
diff --git a/Kernel/Memory/VirtualRange.h b/Kernel/Memory/VirtualRange.h
index 3d69fa6b2b..071f78bb37 100644
--- a/Kernel/Memory/VirtualRange.h
+++ b/Kernel/Memory/VirtualRange.h
@@ -13,8 +13,6 @@
 namespace Kernel::Memory {
 
 class VirtualRange {
-    friend class VirtualRangeAllocator;
-
 public:
     VirtualRange() = delete;
     VirtualRange(VirtualAddress base, size_t size)