path: root/src/paging.zig

// SPDX-FileCopyrightText: 2024 Himbeer <himbeer@disroot.org>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

// This is an implementation of Sv39 paging, meaning that the virtual addresses
// are 39 bits wide. Sv32 and Sv48 are currently not implemented.

// Defined by linker script.
const heap_start = @extern(*void, .{ .name = "_heap_start" });
const heap_size = @extern(*void, .{ .name = "_heap_size" });

const num_pages = @intFromPtr(heap_size) / page_size;
const alloc_start: *void = @ptrFromInt(heap_start + num_pages * page_size); // Beyond page descriptors

pub const page_size = 0x1000; // 4096 bytes

pub const AllocError = error{
    ZeroSize,
    OutOfMemory,
    OutOfRange,
    DoubleFree,
    AlreadyTaken,
};

pub const TableError = error{
    NotALeaf,
};

// Flags of a page descriptor.
pub const PageFlags = enum(u8) {
    empty = 0,
    active = 1 << 0,
    last = 1 << 1,
};

// A page descriptor for use by the heap allocator.
pub const Page = struct {
    flags: u8,

    pub fn isFree(self: Page) bool {
        return !(self.flags & PageFlags.active);
    }

    // Reports whether this is the last page of a contiguous allocation.
    pub fn isLast(self: Page) bool {
        return self.flags & PageFlags.last;
    }

    // Marks a page as taken, optionally flagging it as the last page of an allocation.
    // Fails if the page is already taken.
    // Returns whether the operation was successful.
    pub fn take(self: *Page, last: bool) !void {
        if (!self.isFree()) return AllocError.AlreadyTaken;

        self.flags |= PageFlags.active;
        if (last) self.flags |= PageFlags.last;
    }

    // Clears all flags to mark a page as free.
    pub fn clear(self: *Page) void {
        self.flags = PageFlags.empty;
    }
};

// Returns the offset from the page base. Works with both physical and virtual addresses.
// Offsets are never translated.
fn offsetOf(addr: usize) usize {
    // Offset is in bottom 12 bits of both physical and virtual addresses.
    return addr & 0xfff;
}

// Returns the virtual page numbers of a virtual address by paging level.
fn virtualPageNumbers(vaddr: usize) [3]usize {
    // Virtual address format:
    //
    // VPN[2] | VPN[1] | VPN[0] | offset
    // 9 bits | 9 bits | 9 bits | 12 bits
    //
    // Virtual page numbers are indexes into the page table of their level,
    // i.e. VPN[2] is an index to the root page table on level 2
    // whereas VPN[1] is an index to the page table on level 1 specified by VPN[2].
    //
    // Offsets are never translated.

    return [3]usize{
        (vaddr >> 12) & 0x1ff,
        (vaddr >> 21) & 0x1ff,
        (vaddr >> 30) & 0x1ff,
    };
}

// Returns the physical page numbers of a physical address by paging level.
fn physicalPageNumbers(paddr: usize) [3]usize {
    // Physical address format:
    //
    // PPN[2]  | PPN[1] | PPN[0] | offset
    // 26 bits | 9 bits | 9 bits | 12 bits
    //
    // PPN[i] is what to map VPN[i] to.
    //
    // Offsets are never translated.

    return [3]usize{
        (paddr >> 12) & 0x1ff,
        (paddr >> 21) & 0x1ff,
        (paddr >> 30) & 0x3ff_ffff,
    };
}

pub const EntryFlags = enum(i64) {
    valid = 1 << 0,
    read = 1 << 1,
    write = 1 << 2,
    exec = 1 << 3,
    user = 1 << 4,
    global = 1 << 5,
    accessed = 1 << 6,
    dirty = 1 << 7,
};

pub const Entry = packed struct(i64) {
    reserved: u10,
    mapping: u44,
    rsw: u2, // Reserved for supervisor use. Currently unused.
    flags: u8,

    // Returns the physical page numbers to map to by paging level.
    pub fn physicalPageNumbers(self: Entry) [3]usize {
        // Mapping format:
        //
        // PPN[2]  | PPN[1] | PPN[0]
        // 26 bits | 9 bits | 9 bits
        //
        // PPN[i] is what to map VPN[i] to.

        return [3]usize{
            self.mapping & 0x1ff,
            (self.mapping >> 9) & 0x1ff,
            (self.mapping >> 18) & 0x3ff_ffff,
        };
    }

    pub fn mappingAddr(self: Entry) usize {
        // Apply an offset of zero since entries always point to an aligned page
        // and this function should return a usable memory address.
        // Callers can change the offset if needed.
        return self.mapping << 12;
    }

    pub fn isValid(self: Entry) bool {
        return self.flags & EntryFlags.valid;
    }

    // Returns whether the entry is a mapping (true) or another page table (false).
    pub fn isLeaf(self: Entry) bool {
        return self.flags & (EntryFlags.read | EntryFlags.write | EntryFlags.exec);
    }
};

pub const Table = struct {
    // Do not add any fields. The unmap function relies on mappings pointing to page tables,
    // casting them to this data structure. This cast becomes invalid if additional fields
    // are added, especially if they preceed the entries field.

    entries: [512]Entry,

    // Create a mapping of a certain virtual page address to a physical page address,
    // discarding offsets. The mapping is written to the specified level,
    // creating page tables as needed.
    //
    // The mapping must be a leaf, meaning that passing flags
    // that indicate no access permissions at all will return an error.
    //
    // This function internally uses zeroedAlloc to allocate memory for the required page tables,
    // but assumes that the physical address to map to has already been allocated by the caller.
    pub fn map(root: *Table, vaddr: usize, paddr: usize, flags: i64, level: usize) !void {
        if (!.{ .flags = flags }.isLeaf()) return TableError.NotALeaf;

        const vpn = virtualPageNumbers(vaddr);

        // Grab the entry in the root (level 2) page table.
        var v = &root.entries[vpn[2]];

        // Walk the page table levels from high to low under the assumption that root is valid.
        for (level..2) |iInv| {
            const i = 1 - iInv;

            // If this entry doesn't point to a lower-level page table or memory page yet,
            // allocate one.
            if (!v.isValid()) {
                const page = zeroedAlloc(1);
                v.* = .{
                    .reserved = 0,
                    .mapping = page >> 12, // Remove the offset, a mapping is just the PPN.
                    .rsw = 0,
                    .flags = EntryFlags.valid, // No permissions, this is a branch to another table.
                };
            }

            // Get the entries of the existing or newly created page table.
            // This cast is safe because the only field of a Table is its entries.
            const table: *Table = @ptrFromInt(v.mappingAddr());
            // Grab the entry of the table by indexing it according to the corresponding VPN.
            v = &table[vpn[i]];
        }

        // Write the actual mapping to the correct table on the requested level.
        v.* = .{
            .reserved = 0,
            .mapping = paddr >> 12, // Remove the offset, a mapping is just the PPN.
            .rsw = 0,
            .flags = flags,
        };
    }

    // Deallocate child page tables recursively. The provided table itself is not affected,
    // allowing partial unmapping of multi-level tables.
    //
    // This function does not deallocate memory pages mapped by the provided table
    // or any of its (recursive) children.
    pub fn unmap(table: *Table) void {
        for (table.entries) |entry| {
            if (entry.isValid() and !entry.isLeaf()) {
                // This cast is safe because the only field of a Table is its entries.
                const lowerLevelTable: *Table = @ptrFromInt(entry.mappingAddr());
                lowerLevelTable.unmap();
                entry.flags &= ~EntryFlags.valid;
                free(lowerLevelTable);
            }
        }
    }

    // Returns the physical address to a virtual address using the provided level 2 page table.
    // This can be used to access virtual addresses whose page table isn't active
    // in the MMU / SATP CSR (Control and Status Register), making it possible
    // to access the memory space of a user mode process (from its perspective)
    // from supervisor mode cleanly.
    //
    // The absence of a return value is equivalent to a page fault.
    pub fn translate(root: *const Table, vaddr: usize) ?usize {
        const vpn = virtualPageNumbers(vaddr);

        // Grab the entry in the root (level 2) page table.
        var v = &root.entries[vpn[2]];

        // Walk the page table levels from high to low.
        for (0..3) |iInv| {
            const i = 2 - iInv;

            if (!v.isValid()) {
                break;
            } else if (v.isLeaf()) {
                // Mapping found.

                // Create a mask starting directly below / after PN[i].
                // Since all levels can have leaves i is not guaranteed to be zero.
                const offsetMask = (1 << (12 + 9 * i)) - 1;
                const offset = vaddr & offsetMask;
                const ppnJoined = v.mappingAddr() & ~offsetMask;

                return ppnJoined | offset;
            }

            // Get the entries of the page table of the current level.
            const entry: *[512]Entry = @ptrFromInt(v.mappingAddr());
            // Grab the entry of the table by indexing it according to the corresponding VPN.
            v = &entry[vpn[i - 1]];
        }

        return null;
    }
};

// Allocate memory pages. Passing n <= 0 results in an error.
pub fn alloc(n: usize) !*void {
    if (n <= 0) return AllocError.ZeroSize;

    const pages: *[num_pages]Page = @ptrCast(heap_start);

    // Iterate over potential starting points.
    // The subtraction of n prevents unnecessary iterations for starting points
    // that don't leave enough space for the whole allocation.
    for (0..num_pages - n) |i| {
        if (pages[i].isFree()) {
            // Free starting page found.

            var insufficient = false;

            // Check if there is enough contiguous free space for the whole allocation.
            // If not, move on to the next potential starting point.
            for (i..n + i) |j| {
                if (!pages[j].isFree()) {
                    insufficient = true;
                    break;
                }
            }

            if (!insufficient) {
                // Mark all allocated pages as taken.
                for (i..n + i - 1) |j| {
                    pages[j].take(false);
                }
                pages[n + i - 1].take(true);

                // Construct a pointer to the first page using its descriptor number.
                return alloc_start + i * page_size;
            }
        }
    }

    return AllocError.OutOfMemory;
}

// Free (contiguous) memory page(s). Provides limited protection against double-frees.
pub fn free(ptr: *void) !void {
    // Restore the address to the page descriptor flags from the address of its contents
    // by restoring the descriptor number and indexing the descriptor table
    // at the start of the heap using it.
    const addr = @intFromPtr(heap_start) + (ptr - alloc_start) / page_size;

    // Ensure basic address sanity.
    // Does not check descriptor table bounds.
    if (addr < @intFromPtr(heap_start) or addr >= @intFromPtr(heap_start) + @intFromPtr(heap_size)) return AllocError.OutOfRange;

    const page: [*]Page = @ptrCast(addr);

    // Mark all but the last page as free.
    // A double-free check is performed on the last page before it is freed.
    while (!page.isFree() and !page.isLast()) {
        page.clear();
        page += 1;
    }

    // Free page encountered, but it isn't marked as the last. Potential double-free.
    if (!page.isLast()) return AllocError.DoubleFree;

    // Mark the last page as free.
    page.clear();
}

// Allocate memory pages and overwrite their contents with zeroes for added security.
// Passing n <= 0 results in an error.
pub fn zeroedAlloc(n: usize) !*void {
    const ret = try alloc(n);

    // Write zeroes in batches of 64-bit to reduce the amount of store instructions.
    // The remainder / remaining bytes don't need to be accounted for
    // because page_size (4096) is divisible by 8.

    const size = (n * page_size) / 8;
    const ptr: *volatile [size]u64 = @ptrCast(ret);

    for (0..size) |i| {
        ptr[i] = 0;
    }

    return ret;
}