diff options
Diffstat (limited to 'mm/vma.cc')
| -rw-r--r-- | mm/vma.cc | 640 |
1 files changed, 640 insertions, 0 deletions
diff --git a/mm/vma.cc b/mm/vma.cc new file mode 100644 index 0000000..da89e08 --- /dev/null +++ b/mm/vma.cc @@ -0,0 +1,640 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +/* Copyright (C) 2026 Richard Qin */ + +/* + * vma.cc — Virtual Memory Area management (MI layer) + * + * Manages user address spaces using a red-black tree of VMA regions. + * Implements demand paging: vmm_map_user records intent only; + * physical pages are allocated on page fault via vmm_handle_page_fault. + * + * MI/MD separation: this file NEVER references pmap::PTE_* constants. + * Permission translation is delegated to pmap::vm_perm_to_pte(). + * + * Reference: docs/specs/vmm.md + */ + +#include <lume/vmm.h> +#include <lume/addr.h> +#include <lume/config.h> +#include <lume/errno.h> +#include <lume/pmm.h> +#include <lume/new.h> +#include <lume/klog.h> +#include <arch/pmap.h> +#include <lume/tlb.h> +#include <lume/mm_layout.h> + +/* ------------------------------------------------------------------ */ +/* Rbtree callbacks for VMA interval tree */ +/* ------------------------------------------------------------------ */ + +static bool vma_less(struct rb_node* node, const struct rb_node* parent) { + VmAreaStruct* n = reinterpret_cast<VmAreaStruct*>( + reinterpret_cast<char*>(node) - __builtin_offsetof(VmAreaStruct, rb)); + const VmAreaStruct* p = reinterpret_cast<const VmAreaStruct*>( + reinterpret_cast<const char*>(parent) - __builtin_offsetof(VmAreaStruct, rb)); + return n->start < p->start; +} + +static int vma_cmp(const void* key, const struct rb_node* node) { + uint64 addr = *static_cast<const uint64*>(key); + const VmAreaStruct* n = reinterpret_cast<const VmAreaStruct*>( + reinterpret_cast<const char*>(node) - __builtin_offsetof(VmAreaStruct, rb)); + if (addr < n->start) return -1; + if (addr >= n->end) return 1; + return 0; +} + +static VmAreaStruct* node_to_vma(struct rb_node* node) +{ + return reinterpret_cast<VmAreaStruct*>( + reinterpret_cast<char*>(node) - __builtin_offsetof(VmAreaStruct, rb)); +} + +static uint64 align_up_any(uint64 value, uint64 align) +{ + if (align == 0) { + return value; + } + return ((value + align - 1) / align) * align; +} + +static bool range_overlaps(uint64 a_start, uint64 a_end, + uint64 b_start, uint64 b_end) +{ + return a_start < b_end && b_start < a_end; +} + + + +static bool vma_overlaps_locked(VmSpace* space, uint64 start, uint64 end) +{ + struct rb_node* node = rb_first(&space->vma_tree); + while (node) { + VmAreaStruct* vma = node_to_vma(node); + if (range_overlaps(start, end, vma->start, vma->end)) { + return true; + } + node = rb_next(node); + } + return false; +} + +static bool vma_range_covered_locked(VmSpace* space, uint64 start, uint64 end) +{ + uint64 cursor = start; + struct rb_node* node = rb_first(&space->vma_tree); + while (node && cursor < end) { + VmAreaStruct* vma = node_to_vma(node); + if (vma->end <= cursor) { + node = rb_next(node); + continue; + } + if (vma->start > cursor) { + return false; + } + if (vma->end > cursor) { + cursor = vma->end; + } + node = rb_next(node); + } + return cursor >= end; +} + +static void vma_try_merge_neighbors_locked(VmSpace* space, VmAreaStruct* vma) +{ + struct rb_node* prev_node = rb_prev(&vma->rb); + if (prev_node) { + VmAreaStruct* prev = node_to_vma(prev_node); + if (prev->end == vma->start && prev->perm == vma->perm) { + prev->end = vma->end; + rb_erase(&vma->rb, &space->vma_tree); + delete vma; + vma = prev; + } + } + + struct rb_node* next_node = rb_next(&vma->rb); + if (next_node) { + VmAreaStruct* next = node_to_vma(next_node); + if (vma->end == next->start && vma->perm == next->perm) { + vma->end = next->end; + rb_erase(&next->rb, &space->vma_tree); + delete next; + } + } +} + +static int vma_split_locked(VmSpace* space, VmAreaStruct* vma, uint64 split) +{ + if (split <= vma->start || split >= vma->end) { + return 0; + } + + VmAreaStruct* right = new VmAreaStruct; + if (!right) { + return -ENOMEM; + } + + right->start = split; + right->end = vma->end; + right->perm = vma->perm; + right->mm = space; + + vma->end = split; + rb_add(&right->rb, &space->vma_tree, vma_less); + return 0; +} + +static int vma_split_range_locked(VmSpace* space, uint64 start, uint64 end) +{ + if (end <= start) { + return 0; + } + + struct rb_node* start_node = rb_find(&start, &space->vma_tree, vma_cmp); + if (!start_node) { + return -ENOMEM; + } + VmAreaStruct* start_vma = node_to_vma(start_node); + int ret = vma_split_locked(space, start_vma, start); + if (ret < 0) { + return ret; + } + + uint64 end_key = end - 1; + struct rb_node* end_node = rb_find(&end_key, &space->vma_tree, vma_cmp); + if (!end_node) { + return -ENOMEM; + } + VmAreaStruct* end_vma = node_to_vma(end_node); + return vma_split_locked(space, end_vma, end); +} + +/* ------------------------------------------------------------------ */ +/* VmSpace lifecycle */ +/* ------------------------------------------------------------------ */ + +VmSpace* VmSpace::create() { + VmSpace* space = new VmSpace; + if (!space) return nullptr; + + space->root_pa = pmap::create(); + if (!space->root_pa) { + delete space; + return nullptr; + } + + space->vma_tree = RB_ROOT; + space->lock.init("VmSpace"); + space->refcount.store(1, __ATOMIC_RELAXED); + space->brk_start = 0; + space->brk_end = 0; + return space; +} + +void VmSpace::incref() { + refcount.fetch_add(1, __ATOMIC_RELAXED); +} + +void VmSpace::put() { + if (refcount.fetch_sub(1, __ATOMIC_ACQ_REL) == 1) { + destroy(); + } +} + +void VmSpace::destroy() { + /* Drain VMA tree under lock, then release BEFORE delete this */ + lock.acquire(); + uint64 root = root_pa; + struct rb_node* node = rb_first(&vma_tree); + while (node) { + VmAreaStruct* vma = reinterpret_cast<VmAreaStruct*>( + reinterpret_cast<char*>(node) - __builtin_offsetof(VmAreaStruct, rb)); + + /* Decref and dec mapcount for all mapped physical pages */ + for (uint64 addr = vma->start; addr < vma->end; addr += kPageSize) { + uint64 pa; + if (pmap::lookup(root, addr, &pa)) { + Page* pg = pa_to_page(phys_addr(pa)); + page_dec_mapcount(pg); + page_decref(pg); + } + } + + node = rb_next(node); + rb_erase(&vma->rb, &vma_tree); + delete vma; + } + lock.release(); + + /* Destroy hardware page tables outside the lock */ + pmap::destroy(root); + + /* Finally free VmSpace itself */ + delete this; +} + +/* ------------------------------------------------------------------ */ +/* Public API: VMA manipulation */ +/* ------------------------------------------------------------------ */ + +int vmm_map_user(VmSpace* space, uint64 va, uint64 len, uint64 perm) { + if (!space) return -EINVAL; + + va = page_align_down(va); + len = page_align_up(len); + if (len == 0) return 0; + if (va < kUserVaBase) return -EINVAL; + if (va >= kUserVaLimit) return -EINVAL; + if (va + len < va || va + len > kUserVaLimit) return -EINVAL; + + VmAreaStruct* vma = new VmAreaStruct; + if (!vma) return -ENOMEM; + vma->start = va; + vma->end = va + len; + vma->perm = perm | VM_USER; // Enforce user-mode access (MI flag) + vma->mm = space; + + LockGuard guard(space->lock); + if (vma_overlaps_locked(space, vma->start, vma->end)) { + delete vma; + return -EINVAL; + } + rb_add(&vma->rb, &space->vma_tree, vma_less); + vma_try_merge_neighbors_locked(space, vma); + return 0; +} + +int vmm_unmap_user(VmSpace* space, uint64 va, uint64 len) { + if (!space) return -EINVAL; + va = page_align_down(va); + len = page_align_up(len); + if (len == 0) return 0; + if (va < kUserVaBase) return -EINVAL; + if (va >= kUserVaLimit) return -EINVAL; + if (va + len < va || va + len > kUserVaLimit) return -EINVAL; + uint64 end = va + len; + + LockGuard guard(space->lock); + struct rb_node* node = rb_first(&space->vma_tree); + while (node) { + VmAreaStruct* vma = node_to_vma(node); + struct rb_node* next = rb_next(node); + + if (vma->end <= va) { + node = next; + continue; + } + if (vma->start >= end) { + break; + } + + uint64 unmap_start = (vma->start > va) ? vma->start : va; + uint64 unmap_end = (vma->end < end) ? vma->end : end; + + if (unmap_start < unmap_end) { + for (uint64 addr = unmap_start; addr < unmap_end; addr += kPageSize) { + uint64 pa; + if (pmap::lookup(space->root_pa, addr, &pa)) { + pmap::unmap(space->root_pa, addr); + Page* pg = pa_to_page(phys_addr(pa)); + page_dec_mapcount(pg); + page_decref(pg); + } + } + } + + if (unmap_start == vma->start && unmap_end == vma->end) { + rb_erase(&vma->rb, &space->vma_tree); + delete vma; + } else if (unmap_start == vma->start) { + rb_erase(&vma->rb, &space->vma_tree); + vma->start = unmap_end; + rb_add(&vma->rb, &space->vma_tree, vma_less); + } else if (unmap_end == vma->end) { + vma->end = unmap_start; + } else { + VmAreaStruct* right = new VmAreaStruct; + if (!right) { + return -ENOMEM; + } + right->start = unmap_end; + right->end = vma->end; + right->perm = vma->perm; + right->mm = space; + + vma->end = unmap_start; + rb_add(&right->rb, &space->vma_tree, vma_less); + break; + } + + node = next; + } + return 0; +} + +int vmm_protect_user(VmSpace* space, uint64 va, uint64 len, uint64 perm) +{ + if (!space) return -EINVAL; + va = page_align_down(va); + len = page_align_up(len); + if (len == 0) return -EINVAL; + if (va < kUserVaBase) return -EINVAL; + if (va >= kUserVaLimit) return -EINVAL; + if (va + len < va || va + len > kUserVaLimit) return -EINVAL; + + uint64 end = va + len; + + LockGuard guard(space->lock); + if (!vma_range_covered_locked(space, va, end)) { + return -ENOMEM; + } + int ret = vma_split_range_locked(space, va, end); + if (ret < 0) { + return ret; + } + + bool tlb_flush_needed = false; + struct rb_node* node = rb_find(&va, &space->vma_tree, vma_cmp); + while (node) { + VmAreaStruct* vma = node_to_vma(node); + if (vma->start >= end) { + break; + } + if (vma->end <= va) { + node = rb_next(node); + continue; + } + + vma->perm = (perm | VM_USER); + + for (uint64 addr = vma->start; addr < vma->end; addr += kPageSize) { + uint64 pa; + if (!pmap::lookup(space->root_pa, addr, &pa)) { + continue; + } + + if (perm == 0) { + Page* pg = pa_to_page(phys_addr(pa)); + page_dec_mapcount(pg); + page_decref(pg); + pmap::unmap(space->root_pa, addr); + tlb_flush_needed = true; + continue; + } + + uint64 pte_perm = pmap::vm_perm_to_pte(vma->perm); + if ((vma->perm & VM_WRITE) && pmap::is_cow(space->root_pa, addr)) { + pte_perm &= ~pmap::PTE_W; + pte_perm |= pmap::PTE_COW; + } + + int ret = pmap::protect(space->root_pa, addr, pte_perm); + if (ret < 0) { + return ret; + } + tlb_flush_needed = true; + } + + node = rb_next(node); + } + + if (tlb_flush_needed) { + tlb_shootdown_range(space, va, end); + } + return 0; +} + +uint64 mm_find_free_va(VmSpace* space, uint64 length, uint64 align) +{ + if (!space) return 0; + length = page_align_up(length); + if (length == 0) return 0; + if (align < kPageSize) align = kPageSize; + + LockGuard guard(space->lock); + + /* Linux: arch_get_unmapped_area() starts from mm->mmap_base. + * RISC-V: TASK_UNMAPPED_BASE = PAGE_ALIGN(TASK_SIZE / 3). + * Fall back to kUserVaBase if mmap_base not set (kernel VmSpaces). */ + uint64 base = space->mmap_base ? space->mmap_base : kUserVaBase; + uint64 cursor = align_up_any(base, align); + struct rb_node* node = rb_first(&space->vma_tree); + while (node) { + VmAreaStruct* vma = node_to_vma(node); + if (cursor <= vma->start) { + if (cursor > kUserVaLimit - length) { + return 0; + } + if (cursor + length <= vma->start) { + return cursor; + } + } + if (cursor < vma->end) { + cursor = vma->end; + } + cursor = align_up_any(cursor, align); + node = rb_next(node); + } + + if (cursor > kUserVaLimit - length) { + return 0; + } + return cursor; +} + +bool vma_range_covered(VmSpace* space, uint64 start, uint64 end) +{ + if (!space) return false; + start = page_align_down(start); + end = page_align_up(end); + if (end <= start) return true; + + LockGuard guard(space->lock); + return vma_range_covered_locked(space, start, end); +} + +/* ------------------------------------------------------------------ */ +/* Page fault handler (demand paging) */ +/* ------------------------------------------------------------------ */ + +static bool vma_allows(const VmAreaStruct* vma, VmFaultCause cause) +{ + switch (cause) { + case VmFaultCause::Read: + return (vma->perm & VM_READ) != 0; + case VmFaultCause::Write: + return (vma->perm & VM_WRITE) != 0; + case VmFaultCause::Exec: + return (vma->perm & VM_EXEC) != 0; + default: + return false; + } +} + +int vmm_handle_page_fault(VmSpace* space, uint64 fault_addr, VmFaultCause cause) { + if (!space) return -EINVAL; + + uint64 aligned_addr = page_align_down(fault_addr); + + LockGuard guard(space->lock); + struct rb_node* node = rb_find(&fault_addr, &space->vma_tree, vma_cmp); + if (!node) { + return -EFAULT; // No VMA covers this address → segfault + } + + VmAreaStruct* vma = reinterpret_cast<VmAreaStruct*>( + reinterpret_cast<char*>(node) - __builtin_offsetof(VmAreaStruct, rb)); + + if (!vma_allows(vma, cause)) { + return -EFAULT; + } + + /* Check if page is already mapped */ + uint64 paddr; + if (pmap::lookup(space->root_pa, aligned_addr, &paddr)) { + if (cause == VmFaultCause::Write && pmap::is_cow(space->root_pa, aligned_addr)) { + /* Store Page Fault on a COW page */ + Page* page = pmm_alloc_page(); + if (!page) return -ENOMEM; + uint64 new_pa = page_to_pa(page).raw; + + /* Copy page contents */ + uint8* dst = reinterpret_cast<uint8*>(pa_to_va(phys_addr(new_pa)).raw); + const uint8* src = reinterpret_cast<const uint8*>(pa_to_va(phys_addr(paddr)).raw); + for (uint64 i = 0; i < kPageSize; i++) { + dst[i] = src[i]; + } + + /* Remap with write permission, clearing COW */ + uint64 pte_perm = pmap::vm_perm_to_pte(vma->perm); + if (pmap::map(space->root_pa, aligned_addr, new_pa, pte_perm) != 0) { + pmm_free_page(page); + return -ENOMEM; + } + + /* New page gets mapcount = 1 (we just mapped it) */ + page_inc_mapcount(page); + + /* Decrement mapcount and refcount of old page */ + Page* old_page = pa_to_page(phys_addr(paddr)); + page_dec_mapcount(old_page); + page_decref(old_page); + + /* Flush TLB to remove old read-only cached translation */ + tlb_shootdown_page(space, aligned_addr); + return 0; + } + /* DEBUG: page already mapped but still faulting — dump PTE */ + { + uint64 cur_satp; + asm volatile("csrr %0, satp" : "=r"(cur_satp)); + printk(KERN_ERR "fault: va=%llx pa=%llx cause=%d pte=%llx satp=%llx root=%llx\n", + aligned_addr, paddr, static_cast<int>(cause), + pmap::lookup_pte(space->root_pa, aligned_addr), + cur_satp, space->root_pa); + } + return 0; // Already mapped, maybe read fault on existing page + } + + /* Allocate physical page and zero it. + * Linux: do_anonymous_page() uses alloc_zeroed_user_highpage_movable(). + * Anonymous pages MUST be zeroed — userspace expects MAP_ANONYMOUS + * pages to contain all zeros (POSIX requirement). */ + Page* page = pmm_alloc_page(); + if (!page) return -ENOMEM; + + uint64 pa = page_to_pa(page).raw; + + /* Zero the page before mapping it to userspace */ + /* Zero the page before mapping it to userspace */ + uint8* kva = reinterpret_cast<uint8*>(pa_to_va(PhysAddr{pa}).raw); + for (uint64 i = 0; i < kPageSize; i++) kva[i] = 0; + + /* Translate MI permission flags to hardware PTE bits (MD layer) */ + uint64 pte_perm = pmap::vm_perm_to_pte(vma->perm); + + if (pmap::map(space->root_pa, aligned_addr, pa, pte_perm) != 0) { + pmm_free_page(page); + return -ENOMEM; + } + + /* Initial mapping: refcount is already 1 from pmm_alloc_page. + * Set mapcount = 1 to track this PTE mapping. */ + page_inc_mapcount(page); + + return 0; +} + +/* ------------------------------------------------------------------ */ +/* Fork / Clone (COW infrastructure) */ +/* ------------------------------------------------------------------ */ + +VmSpace* vmm_clone(VmSpace* parent) { + if (!parent) return nullptr; + + VmSpace* child = VmSpace::create(); + if (!child) return nullptr; + + child->brk_start = parent->brk_start; + child->brk_end = parent->brk_end; + + LockGuard parent_guard(parent->lock); + + struct rb_node* node = rb_first(&parent->vma_tree); + while (node) { + VmAreaStruct* parent_vma = reinterpret_cast<VmAreaStruct*>( + reinterpret_cast<char*>(node) - __builtin_offsetof(VmAreaStruct, rb)); + + VmAreaStruct* child_vma = new VmAreaStruct; + if (!child_vma) { + child->destroy(); + return nullptr; + } + child_vma->start = parent_vma->start; + child_vma->end = parent_vma->end; + child_vma->perm = parent_vma->perm; + child_vma->mm = child; + + /* Copy pages and mark COW if writable */ + for (uint64 va = child_vma->start; va < child_vma->end; va += kPageSize) { + uint64 pa; + if (pmap::lookup(parent->root_pa, va, &pa)) { + /* Make parent COW if it was writable */ + if (child_vma->perm & VM_WRITE) { + pmap::make_cow(parent->root_pa, va); + /* Flush TLB for parent since we reduced permissions */ + tlb_shootdown_page(parent, va); + } + + /* Map in child as COW or read-only */ + uint64 pte_perm = pmap::vm_perm_to_pte(child_vma->perm); + if (child_vma->perm & VM_WRITE) { + pte_perm &= ~pmap::PTE_W; + pte_perm |= pmap::PTE_COW; + } + + if (pmap::map(child->root_pa, va, pa, pte_perm) != 0) { + /* If map fails, we leak what we did in this loop for now, + * but child->destroy() will clean it up safely since + * we increment refcounts as we go. */ + delete child_vma; + child->destroy(); + return nullptr; + } + + /* Increment physical page refcount and mapcount */ + Page* shared_page = pa_to_page(phys_addr(pa)); + page_incref(shared_page); + page_inc_mapcount(shared_page); + } + } + + rb_add(&child_vma->rb, &child->vma_tree, vma_less); + node = rb_next(node); + } + + return child; +} |