rustubs/mm/allocator/

buddy.rs

// buddy allocator, mimicing that of the linux kernel.
// very fucking unsafe.
//
//
// TERMINOLOGY: (TODO: move to docs)
//
//                             |       | page size
// +---------------------------+-------+-----------+
// |                           | order | 12 bits   |
// +---------------------------+-------+-----------+
// |<--Physical Block Number-->|       |           |
// |                                   |           |
// |<--Physical Frame Number (PFN)---->|           |
// |                                               |
// |<--Physical Address (PA) --------------------->|
//
// BlockID		:= (PA - ZONE_BASE) << (order + 12)
// BuddyBlockID := BlockID ^ 1
// BuddyPFN     := PFN ^ (1 << order)

use core::{
	fmt,
	ops::Range,
	ptr::{self, null_mut},
};

use crate::defs;
use defs::Mem::*;

#[derive(Copy, Clone)]
struct Node {
	next: *const Node,
	prev: *const Node,
}

type FreeList = Node;

/// return type of the buddy allocation, describes the allocated physical memory
/// frame(s)
/// - `pfn`: physical frame number of the starting address
/// - `order` : number of allocated frames in 2's order
pub struct FrameDesc {
	pfn: u64,     // paddr = pfn << pageshift;
	order: usize, // block_size == page_size << order
}

impl FrameDesc {
	pub fn get_size(&self) -> usize {
		return (PAGE_SIZE << self.order) as usize;
	}
	pub fn get_paddr(&self) -> u64 { return self.pfn << PAGE_SHIFT; }
	pub fn from_paddr(paddr: u64, order: usize) -> FrameDesc {
		return Self { pfn: paddr >> PAGE_SHIFT, order };
	}
}

#[derive(Debug)]
/// A contiguous physical memory range to be managed by a (buddy) allocator.
/// `free_areas` : free-lists for difference sizes (in order of 2).
///
/// IMPORTANT: the Zone, or the global ZONE object is unprotected in any sense.
/// One must synchronize the operations via a sane Allocator object.
pub struct Zone {
	pa_range: Range<u64>,
	free_areas: [FreeArea; PFA_NR_PAGE_ORDER],
}

// the implementations of Zone only provides meta information. Any
// allocation-related method should be implemented in the Allocator
impl Zone {
	pub const fn default() -> Self {
		Self {
			pa_range: Range::<u64> { start: 0, end: 0 },
			free_areas: [FreeArea::default(); PFA_NR_PAGE_ORDER],
		}
	}

	// pfn offset = (pa - base) >> PAGESHIFT
	pub fn get_buddy(&self, frame: &FrameDesc) -> Option<FrameDesc> {
		// we assume that the reference frame is valid wrt. the zone.
		// .. also a few extra steps in calculation to make it more readable.
		let pa: u64 = frame.get_paddr();
		let offset_pfn = (pa - self.pa_range.start) >> PAGE_SHIFT;
		let buddy_pfn = offset_pfn ^ (1 << frame.order);
		let buddy = FrameDesc { pfn: buddy_pfn, order: frame.order };

		// since we don't enforce the memory size to be power of 2, some blocks
		// may not have a buddy. In which case we'll treat its psuedo-buddy as
		// permanently "occupied"
		if !self.contains(&buddy) {
			return None;
		}
		Some(FrameDesc { pfn: buddy_pfn, order: frame.order })
	}

	// similar to get_buddy, but gets buddy pa via ref pa.
	// I don't mind repeat a few lines of code, btw.
	pub fn get_buddy_by_pa(&self, pa: u64, order: usize) -> Option<u64> {
		let offset_pfn = (pa - self.pa_range.start) >> PAGE_SHIFT;
		let buddy_offset_pfn = offset_pfn ^ (1 << order);
		let buddy_offset_pa = buddy_offset_pfn << PAGE_SHIFT;
		let buddy_pa = buddy_offset_pa + self.pa_range.start;
		if !self.pa_range.contains(&buddy_pa) {
			return None;
		}
		return Some(buddy_pa);
	}

	#[inline]
	pub fn contains(&self, frame: &FrameDesc) -> bool {
		let pa: u64 = frame.get_paddr();
		let pa_end = pa + frame.get_size() as u64;
		return self.pa_range.contains(&pa) && self.pa_range.contains(&pa_end);
	}
}

#[derive(Copy, Clone)]
struct FreeArea {
	list_head: FreeList,
	nr_free: usize,
	order: usize,
}

impl fmt::Debug for FreeArea {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
		write!(f, "free: {}", self.nr_free)
	}
}

impl FreeArea {
	pub const fn default() -> FreeArea {
		FreeArea {
			list_head: FreeList {
				next: ptr::null_mut::<Node>(),
				prev: ptr::null_mut::<Node>(),
			},
			nr_free: 0,
			order: 0,
		}
	}

	// this linked list uses the list head as sentinel
	pub fn init_empty(&mut self) {
		self.list_head.next = &self.list_head as *const Node;
		self.list_head.prev = self.list_head.next;
	}

	// don't care about ordering ... (yet)
	// let's push and pop both from the one end.
	// the caller is responsible of making sure n points to valid memory.
	pub unsafe fn push(&mut self, n: *mut Node) {
		(*n).next = self.list_head.next;
		(*n).prev = &(self.list_head);
		self.list_head.next = n;
		(*(self.list_head.next as *mut Node)).prev = n;
		self.nr_free += 1;
	}

	pub fn pop(&mut self) -> Option<*const Node> {
		if self.nr_free == 0 {
			return None;
		}

		let n = self.list_head.next;
		unsafe {
			self.list_head.next = (*n).next;
			(*((*n).next as *mut Node)).prev = &self.list_head;
		}
		self.nr_free -= 1;
		return Some(n);
	}
}

// unlocked buddy allocator. Should use with sync wrapper.
#[derive(Debug)]
pub struct BuddyAllocator {
	zone: Zone,
}

// very fucking bogus pointer ops which completely lose the point of using rust.
// But hey, rust doesn't like intrusive linked list anyways..
impl BuddyAllocator {
	pub const fn default() -> Self { BuddyAllocator { zone: Zone::default() } }

	// TODO: deal with ill-formed frame object (though unlikely...)
	// TODO: move this to FreeArea::push
	// merging is TODO
	// since we don't require the zone size to be 2's power, a calculated
	// buddy block (in the top order) could be out of range. However we
	// won't merge blocks above this order either. So no checking is
	// necessary here. Here is for sanitychecks whether the to-be-freed
	// block is ill-formed
	pub unsafe fn free_frame_by_pa(&mut self, paddr: u64, order: usize) {
		if let Some(va) = defs::P2V(paddr) {
			let n = va as *mut Node;
			self.zone.free_areas[order].push(n);
		} else {
			return;
		}
	}

	pub unsafe fn free_frame_by_desc(&mut self, frame: &FrameDesc) {
		self.free_frame_by_pa(frame.get_paddr(), frame.order);
	}

	pub fn print_debug_info(&self) {
		for i in &self.zone.free_areas {
			print!("{}:{}  ;", i.order, i.nr_free);
		}
		print!("\n");
	}

	pub fn alloc_frame(&mut self, order: usize) -> Option<FrameDesc> {
		let n = self.recursive_split_down(order);
		n.map(|n| FrameDesc {
			pfn: defs::V2P(n as u64).unwrap() >> PAGE_SHIFT,
			order,
		})
	}

	// split an order N block in two order N - 1 blk. No return.
	fn split_buddy_block(&mut self, n: *mut Node, order: usize) {
		let pa = defs::V2P(n as u64).unwrap();
		let buddy_pa = self.zone.get_buddy_by_pa(pa, order - 1);

		if buddy_pa.is_none() {
			return;
		}

		let buddy_pa = buddy_pa.unwrap();
		let buddy_node = defs::P2V(buddy_pa).unwrap() as *mut Node;

		let fa_down = &mut self.zone.free_areas[order - 1];
		unsafe {
			fa_down.push(buddy_node);
		}
	}

	// do_split: whether split the block on the non-recuseive (i.e. first)  match
	fn recursive_split_down(&mut self, order: usize) -> Option<*const Node> {
		if order > PFA_MAX_PAGE_ORDER {
			return None;
		}
		let n = self.zone.free_areas[order].pop();

		if let Some(n) = n {
			Some(n)
		} else {
			let n_higher = self.recursive_split_down(order + 1)?;
			self.split_buddy_block(n_higher as *mut Node, order + 1);
			return Some(n_higher);
		}
	}

	// initialize one single zone for PFA
	/// [start: end) the physical address range to initialize the PFA.
	/// unsafe because it assumes no data race. This could only work safely during
	/// system initialization.
	pub unsafe fn init(&mut self, start: u64, end: u64) {
		let start = defs::roundup_4k(start);
		let end = defs::rounddown_4k(end);
		let len = end - start;
		// sanity checks
		assert!(
			len >= MIN_PHY_MEM,
			"TO LITTLE RAM ...{:X}-{:X} = {}",
			start,
			end,
			end - start
		);

		// decompose the whole physical range into max order chunks
		// For simplicity, the tail <= max size (order 10 == 4MB) will not be used.
		const MAX_ORDER_BLKSIZE: u64 = PAGE_SIZE << PFA_MAX_PAGE_ORDER;
		const {
			assert!(MAX_ORDER_BLKSIZE == 4 * M, "sancheck failed");
		}

		self.zone.pa_range = start..end;

		// initialize all free areas and list heads.
		for i in PFA_ORDER_RANGE {
			let fa = &mut self.zone.free_areas[i];
			fa.order = i;
			fa.init_empty();
		}

		// populate the highest order free areas
		let list_head = &(self.zone.free_areas[PFA_MAX_PAGE_ORDER].list_head)
			as *const Node;

		let mut prev_node_ptr = list_head;
		let mut curr = start; // the starting address (aligned)
		let mut n: *mut Node = null_mut::<Node>();
		let mut free_blocks: usize = 0;

		while curr + MAX_ORDER_BLKSIZE <= end {
			n = defs::P2V(curr).unwrap() as *mut Node;

			unsafe {
				(*n).prev = prev_node_ptr;
				(*(prev_node_ptr as *mut Node)).next = n as *const Node;
			}

			prev_node_ptr = n;
			free_blocks += 1;
			curr += MAX_ORDER_BLKSIZE;
		}

		// n points to the last free node
		if !n.is_null() {
			unsafe {
				(*n).next = list_head;
				(*(list_head as *mut Node)).prev = n;
			}
		}

		self.zone.free_areas[PFA_MAX_PAGE_ORDER].nr_free = free_blocks;
	}
}