seminix 0.1.61

#![allow(clippy::ptr_eq)]

use core::ffi::c_void;

use semx_unsafe_list::{UnsafeListHead, UnsafeListNode};

use super::{
    GfpFlags,
    error::{KallocError, Result},
    free_pages,
    global::{GLOBAL_PAGE_ALLOC, GlobalDataInner, free_pages_sub},
    slab::KmemPage,
};
use crate::{
    irq::irqflags::{local_irq_restore, local_irq_save},
    processor::this_processor_id,
    space::{
        addr::{Pfn, Vaddr},
        kalloc::global::{MAX_ORDER, free_pages_add},
    },
};

#[inline(always)]
fn prefetch(page: *const Page) {
    #[cfg(aarch64_seminix)]
    unsafe {
        core::arch::aarch64::_prefetch::<
            { core::arch::aarch64::_PREFETCH_READ },
            { core::arch::aarch64::_PREFETCH_LOCALITY3 },
        >(page.cast::<i8>());
    }
    #[cfg(not(aarch64_seminix))]
    let _ = page;
}

#[inline(always)]
fn prefetchw(page: *const Page) {
    #[cfg(aarch64_seminix)]
    unsafe {
        core::arch::aarch64::_prefetch::<
            { core::arch::aarch64::_PREFETCH_WRITE },
            { core::arch::aarch64::_PREFETCH_LOCALITY3 },
        >(page.cast::<i8>());
    }
    #[cfg(not(aarch64_seminix))]
    let _ = page;
}

#[allow(non_upper_case_globals, non_snake_case)]
mod PageFlags {
    // 页从属模块标记

    // 页属于伙伴系统
    pub(crate) const PageBuddy: u32 = 0b0000000001;
    // 页属于 slab 系统
    pub(crate) const PageSlab: u32 = 0b0000000010;

    // 页额外信息标记, 初始化后不会再被修改

    // 页属于预留页, 不会被使用
    pub(crate) const PageReserved: u32 = 0b0000000100;
    // 页被初始化, 首次对页进行初始化
    pub(crate) const PageInitialized: u32 = 0b0000001000;

    // 页是否分配标记, 以及用于标识当前页分配后的属性

    // 当页是复合页时, 标记页是头部页
    pub(crate) const PageHead: u32 = 0b0000010000;
    // 当页是复合页时, 标记页是尾部页(尾随部分)
    pub(crate) const PageTail: u32 = 0b0000100000;
    // 指示该页是否被分配, 被设置则处于被分配状态
    pub(crate) const PageAlloced: u32 = 0b0001000000;

    // 页在分配和释放时使用的掩码

    // 当一个页释放时检查使用. 页在释放前不应该包含这些 flags. 如果有, 则有问题.
    pub(crate) const CheckAtFree: u32 = PageBuddy | PageSlab | PageReserved | PageAlloced;
    // 当一个页分配时, 不应该包含这些 flags
    pub(crate) const CheckAtAlloc: u32 = CheckAtFree;
    // 当一个页释放回伙伴系统时, 清除这些标志
    pub(crate) const ClearAtFree: u32 = PageHead | PageTail;
}

// 当页是头部页或者单页时用于链表存储
// 如果页在伙伴系统中并且为首页, 则 page.ty 一定为 PageLru
#[derive(Clone, Copy)]
#[repr(C)]
pub(crate) struct PageLru {
    pub(crate) lru: UnsafeListNode<Page>,
    pub(crate) order: usize,
}

// 当页是复合页并且是尾随页时用于记录头部页地址和 order
// 当页处于伙伴系统中时, 不标记自己 page.ty 为 PageComp,
// 只有在分配出去后会记录 page.ty 为 PageComp
#[derive(Clone, Copy)]
pub(crate) struct PageComp {
    comp_head: usize,
    comp_order: usize,
}

// 标记当前页的状态
//
// 如下:
// 对于预留页是 None
// 如果该页在伙伴系统中并且是单页或者头部页则 ty 为 PageLru
// 如果该页在伙伴系统中并且是尾部页 ty 为 None
// 如果该页不在伙伴系统并且是单页或者头部页则 ty 为 None
// 如果该页不在伙伴系统并且是尾部页 ty 为 PageComp
// 如果该页被Slab系统申请则 ty 为 KmemPage
#[derive(Clone, Copy)]
pub(crate) enum PageType {
    None,
    Lru(PageLru),
    Comp(PageComp),
    Slab(KmemPage),
}

/// 页结构
#[derive(Clone, Copy)]
pub struct Page {
    pub(crate) ty: PageType,
    flags: u32,
}

#[allow(non_snake_case)]
impl Page {
    #[inline(always)]
    pub(crate) fn init_page(&mut self, reserved: bool) {
        self.ty = PageType::None;
        let reserved_flags = if reserved { PageFlags::PageReserved } else { 0 };
        self.flags = PageFlags::PageInitialized | reserved_flags;
    }

    #[inline(always)]
    fn is_PageBuddy(&self) -> bool {
        self.flags & PageFlags::PageBuddy != 0
    }

    #[inline(always)]
    pub(crate) fn is_PageSlab(&self) -> bool {
        self.flags & PageFlags::PageSlab != 0
    }

    #[inline(always)]
    fn is_PageReserved(&self) -> bool {
        self.flags & PageFlags::PageReserved != 0
    }

    #[inline(always)]
    fn is_PageInitialized(&self) -> bool {
        self.flags & PageFlags::PageInitialized != 0
    }

    #[inline(always)]
    fn is_PageHead(&self) -> bool {
        self.flags & PageFlags::PageHead != 0
    }

    #[inline(always)]
    fn is_PageTail(&self) -> bool {
        self.flags & PageFlags::PageTail != 0
    }

    #[inline(always)]
    pub(crate) fn is_PageComp(&self) -> bool {
        self.is_PageHead() || self.is_PageTail()
    }

    #[inline(always)]
    fn is_PageAlloced(&self) -> bool {
        self.flags & PageFlags::PageAlloced != 0
    }

    #[inline(always)]
    pub(crate) fn set_PageSlab(&mut self) {
        self.flags |= PageFlags::PageSlab;
    }

    #[inline(always)]
    pub(crate) fn clear_PageSlab(&mut self) {
        self.flags &= !PageFlags::PageSlab;
    }
}

impl Page {
    #[inline(always)]
    // 设置单页或者头部页的 order, 并且设置 PageBuddy 标记, 表明该页属于伙伴系统
    pub(crate) fn set_page_order(&mut self, order: usize) {
        // 这里不需要调用 init_list_node 来初始化 list, 确保后续会将其添加到 free lists 中
        self.ty = PageType::Lru(PageLru { lru: UnsafeListNode::new(), order });
        self.flags |= PageFlags::PageBuddy;
    }

    // 清除单页或者头部页的 order, 并且清除 PageBuddy 标记
    #[inline(always)]
    pub(crate) fn rmv_page_order(&mut self) {
        self.flags &= !PageFlags::PageBuddy;
        match &mut self.ty {
            PageType::Lru(h) => h.order = 0,
            _ => {
                unreachable!()
            },
        }
    }

    // 获取单页或者头部页的 order
    #[inline(always)]
    fn page_order(&self) -> usize {
        match &self.ty {
            PageType::Lru(h) => h.order,
            _ => {
                unreachable!()
            },
        }
    }

    // 当页是复合页时, 返回该复合页对应的头部页
    #[inline(always)]
    fn page_head(&self) -> &Page {
        assert!(self.is_PageComp());
        assert_ne!(self.is_PageHead(), self.is_PageTail());

        if self.is_PageHead() {
            self
        } else {
            match &self.ty {
                PageType::Comp(c) => unsafe {
                    let head = core::ptr::read_volatile(&raw const c.comp_head);
                    &*(head as *const Page)
                },
                _ => {
                    unreachable!()
                },
            }
        }
    }

    #[inline(always)]
    fn compound_order(&self) -> usize {
        assert!(self.is_PageTail());

        match &self.ty {
            PageType::Comp(c) => c.comp_order,
            _ => {
                unreachable!()
            },
        }
    }

    // 确保操作的 page 是一个复合页
    #[inline(always)]
    pub(crate) fn compound_or_head_order(&self) -> usize {
        if self.is_PageHead() {
            let next = unsafe { &*(self as *const Page).add(1) };
            next.compound_order()
        } else {
            self.compound_order()
        }
    }

    // 包含 flags 则有问题
    #[inline(always)]
    fn page_expected_state(&self, flags: u32) -> Result<()> {
        if self.is_PageAlloced() {
            return Err(KallocError::Ealloced);
        }

        if self.flags & flags != 0 {
            return Err(KallocError::Echeck);
        }
        Ok(())
    }

    // 释放页时的检测, 包括 refcount/flags 检查
    #[inline(always)]
    pub(crate) fn free_pages_check(&self) -> Result<()> {
        self.page_expected_state(PageFlags::CheckAtFree)
    }

    // 当页是复合页时, 检查该复合页是否正确
    #[inline(always)]
    fn free_tail_pages_check(&self, page: &Page) -> Result<()> {
        if !page.is_PageTail() {
            return Err(KallocError::Enotail);
        }
        if page.page_head() as *const Page as usize != self as *const Page as usize {
            return Err(KallocError::Enocomp);
        }
        Ok(())
    }

    // 预备释放页, 进行页检查
    #[inline(always)]
    fn free_pages_prepare(&mut self, order: usize) -> Result<()> {
        self.clear_page_alloced();
        if order != 0 {
            let compound = self.is_PageComp();
            let next = unsafe { &*(self as *const Page).add(1) };
            assert!(!compound || next.compound_order() == order);

            for i in 1..(1 << order) {
                let next = unsafe { &mut *(self as *mut Page).add(i) };

                if compound {
                    self.free_tail_pages_check(next)?;
                }
                next.free_pages_check()?;
                next.flags &= !PageFlags::ClearAtFree;
            }
        }
        self.free_pages_check()?;
        self.flags &= !PageFlags::ClearAtFree;
        free_pages_add(1 << order);
        Ok(())
    }

    // 这个函数检查伙伴页是否空闲并且是真的一个伙伴页
    //
    // 我们可以合并一个页面和它的伙伴, 如果:
    // (a) 伙伴不是空洞的(调用前检查!)
    // (b) 伙伴是伙伴系统的
    // (c) page 和伙伴页有相同的 order
    //
    // 为了记录一个 page 是否在伙伴系统中, 我们设置 PageBuddy.
    // 为了记录 order, 使用 page_order.
    #[inline(always)]
    fn page_is_buddy(buddy: &Page, order: usize) -> bool {
        if buddy.is_PageBuddy() && buddy.page_order() == order {
            assert!(!buddy.is_PageAlloced());
            return true;
        }
        false
    }

    // 为配对中的匹配伙伴和它们组成的组合 O(n + 1)页定位结构页
    #[inline(always)]
    fn find_buddy_pfn(page_pfn: Pfn, order: usize) -> Pfn {
        Pfn::from(page_pfn.to_value() ^ (1 << order))
    }

    #[inline(always)]
    fn buddy_page(&self, buddy_pfn: usize, pfn: usize) -> &Page {
        unsafe {
            if buddy_pfn >= pfn {
                &*(self as *const Page).add(buddy_pfn - pfn)
            } else {
                &*(self as *const Page).sub(pfn - buddy_pfn)
            }
        }
    }

    #[inline(always)]
    fn buddy_page_mut(page: *mut Page, buddy_pfn: usize, pfn: usize) -> &'static mut Page {
        unsafe {
            if buddy_pfn >= pfn {
                &mut *(page).add(buddy_pfn - pfn)
            } else {
                &mut *(page).sub(pfn - buddy_pfn)
            }
        }
    }

    #[inline(always)]
    pub(crate) fn prefetch_buddy(&self) {
        let pfn = self.to_pfn();
        let buddy_pfn = Page::find_buddy_pfn(pfn, 0);
        let buddy = self.buddy_page(buddy_pfn.to_value(), pfn.to_value());
        prefetch(buddy as *const Page);
    }

    #[inline(always)]
    pub(crate) fn buddy_list_del(&mut self) {
        unsafe {
            match &mut self.ty {
                PageType::Lru(h) => h.lru.list_del(),
                _ => {
                    unreachable!()
                },
            }
        }
    }

    #[inline(always)]
    pub(crate) fn buddy_list_add(&mut self, head: &mut UnsafeListHead<Page>) {
        match &mut self.ty {
            PageType::Lru(h) => unsafe { head.list_add(&mut h.lru) },
            _ => {
                unreachable!()
            },
        }
    }

    pub(crate) fn buddy_list_add_tail(&mut self, head: &mut UnsafeListHead<Page>) {
        match &mut self.ty {
            PageType::Lru(h) => unsafe { head.list_add_tail(&mut h.lru) },
            _ => {
                unreachable!()
            },
        }
    }

    #[inline(always)]
    pub(crate) fn check_new_page(&self) -> Result<()> {
        self.page_expected_state(PageFlags::CheckAtAlloc)
    }

    #[inline(always)]
    pub(crate) fn check_new_pages(&self, order: usize) -> Result<()> {
        for i in 0..1 << order {
            let p = unsafe { &*(self as *const Page).add(i) };
            p.check_new_page()?;
        }
        Ok(())
    }

    #[inline(always)]
    fn set_page_alloced(&mut self) {
        assert!(!self.is_PageTail());
        assert!(!self.is_PageAlloced());
        self.flags |= PageFlags::PageAlloced;
    }

    #[inline(always)]
    fn clear_page_alloced(&mut self) {
        assert!(!self.is_PageTail());
        assert!(self.is_PageAlloced());
        self.flags &= !PageFlags::PageAlloced;
    }

    #[inline(always)]
    fn set_compund_page(&self, comp: &mut Page, order: usize) {
        comp.ty =
            PageType::Comp(PageComp { comp_head: self as *const Page as usize, comp_order: order });
        comp.flags |= PageFlags::PageTail;
    }

    #[inline(always)]
    pub(crate) fn prep_compound_page(&mut self, order: usize) {
        let nr_pages = 1 << order;

        self.flags |= PageFlags::PageHead;
        for i in 1..nr_pages {
            let p = unsafe { &mut *(self as *mut Page).add(i) };
            p.flags &= !PageFlags::PageAlloced;
            self.set_compund_page(p, order);
        }
    }

    // 对申请的页进行预备处理
    #[inline(always)]
    pub(crate) fn prep_new_page(&mut self, order: usize, gfp_mask: GfpFlags) {
        unsafe extern "C" {
            fn clear_page(to: *mut c_void);
        }

        self.ty = PageType::None;
        self.set_page_alloced();

        if gfp_mask.clear() {
            for i in 0..1 << order {
                unsafe {
                    let page = &*(self as *const Page).add(i);
                    let v = page.to_virt().unwrap().to_value();
                    clear_page(v as *mut c_void);
                }
            }
        }

        if order != 0 {
            self.prep_compound_page(order);
        }
        free_pages_sub(1 << order);
    }

    #[inline]
    pub(crate) fn __free_one_page(
        &mut self,
        global_inner: &mut GlobalDataInner,
        mut pfn: Pfn,
        mut order: usize,
    ) {
        debug_assert!(self.flags & PageFlags::PageInitialized != 0);
        assert!(self.flags & PageFlags::ClearAtFree == 0);
        assert!(pfn.to_value() & ((1 << order) - 1) == 0);

        let mut page = self;
        let mut buddy_pfn = Pfn::from_error();
        while order < MAX_ORDER - 1 {
            buddy_pfn = Page::find_buddy_pfn(pfn, order);
            let buddy = Page::buddy_page_mut(page, buddy_pfn.to_value(), pfn.to_value());
            if !buddy_pfn.pfn_valid() {
                break;
            }
            if !Page::page_is_buddy(buddy, order) {
                break;
            }
            buddy.buddy_list_del();
            global_inner.free_area[order].nr_free -= 1;
            buddy.rmv_page_order();
            let combined_pfn = buddy_pfn & pfn;
            page = Page::buddy_page_mut(page as *mut Page, combined_pfn.to_value(), pfn.to_value());
            pfn = combined_pfn;
            order += 1;
        }

        page.set_page_order(order);

        if (order < MAX_ORDER - 2) && buddy_pfn.pfn_valid() {
            let combined_pfn = buddy_pfn & pfn;
            let higher_page =
                Page::buddy_page_mut(page as *mut Page, buddy_pfn.to_value(), pfn.to_value());

            buddy_pfn = Page::find_buddy_pfn(combined_pfn, order + 1);
            let higher_buddy = Page::buddy_page_mut(
                higher_page as *mut Page,
                buddy_pfn.to_value(),
                combined_pfn.to_value(),
            );

            if buddy_pfn.pfn_valid() && Page::page_is_buddy(higher_buddy, order + 1) {
                page.buddy_list_add(&mut global_inner.free_area[order].free_list);
                global_inner.free_area[order].nr_free += 1;
                return;
            }
        }
        page.buddy_list_add(&mut global_inner.free_area[order].free_list);
        global_inner.free_area[order].nr_free += 1;
    }

    fn __free_page_to_pcp(&mut self) {
        let raw_pcp;
        let pcp;
        unsafe {
            raw_pcp = core::ptr::addr_of_mut!(
                GLOBAL_PAGE_ALLOC.inner.lock_irq_save().pcp[this_processor_id()]
            );
            pcp = &mut *raw_pcp;
        }

        // 不要使用 self.set_page_order(0),  因为会赋值 PageBuddy, 导致 free_pcppages_bulk 失败.
        self.ty = PageType::Lru(PageLru { lru: UnsafeListNode::new(), order: 0 });
        self.buddy_list_add(&mut pcp.lists);
        pcp.count += 1;
        if pcp.count >= pcp.high {
            let batch;
            unsafe {
                batch = core::ptr::read_volatile(&raw const pcp.batch);
            }
            GLOBAL_PAGE_ALLOC.free_pcppages_bulk(batch as usize, pcp);
        }
    }

    pub(crate) fn free_page_to_pcp(&mut self) {
        self.free_pages_prepare(0).unwrap();
        let flags = local_irq_save();
        self.__free_page_to_pcp();
        local_irq_restore(flags);
    }

    pub(crate) fn free_pages_to_area(&mut self, order: usize) {
        self.free_pages_prepare(order).unwrap();
        let flags = local_irq_save();
        GLOBAL_PAGE_ALLOC.free_one_page(self, self.to_pfn(), order);
        local_irq_restore(flags);
    }
}

pub(crate) fn __free_pages_memory(page: *mut Page, vaddr: Vaddr, order: usize) {
    assert_eq!(unsafe { (*page).to_virt().unwrap().to_value() }, vaddr.to_value());

    prefetchw(page);
    let nr_pages = 1 << order;
    for i in 0..(nr_pages - 1) {
        unsafe {
            let next = page.add(i + 1);
            prefetchw(next);
            debug_assert!(!(*next).is_PageReserved());
            debug_assert!((*next).is_PageInitialized());
        }
    }
    let p = unsafe { &mut *page };
    p.set_page_alloced();
    free_pages(vaddr, order);
}