use crate::{
allocator::{
Allocator, Counter, RootPageHolder, UpdateList, ALLOCATOR_ROOT_PAGE_VERSION_V0, ALLOCATOR_ROOT_PAGE_VERSION_V1,
},
device::{Device, FreePage, ReadPage},
error::PERes,
io::{read_u64, write_u64, InfallibleReadFormat},
};
pub(crate) const SKIPPED_EXP: usize = 5;
pub(crate) const LISTS_COUNT: usize = 32 - SKIPPED_EXP;
const BUFFER_SIZE: usize = 8 * LISTS_COUNT * 2 + 3;
#[derive(Default)]
pub struct FreeList {
pub(crate) tails: [u64; LISTS_COUNT],
pub(crate) heads: [u64; LISTS_COUNT],
to_flush: bool,
}
fn list_pos(exp: u8) -> usize {
exp as usize - SKIPPED_EXP
}
impl FreeList {
pub fn new(heads: [u64; LISTS_COUNT], tails: [u64; LISTS_COUNT]) -> Self {
FreeList {
tails: heads,
heads: tails,
to_flush: false,
}
}
pub fn check_and_clean(&mut self, device: &dyn Device) -> PERes<()> {
for pos in 0..self.heads.len() {
let page = self.heads[pos];
if page != 0 {
let mut lp = device.load_free_page(page)?;
if lp.is_free_list_head() {
lp.remove_free_list_head_flag();
device.flush_free_page(&lp)?;
}
if lp.is_free()? {
while lp.get_prev_free() != 0 {
lp = device.load_free_page(lp.get_prev_free())?;
assert!(lp.is_free()?);
}
self.heads[pos] = lp.get_index();
} else {
self.heads[pos] = 0;
}
}
}
for pos in 0..self.tails.len() {
let page = self.tails[pos];
let recompute = if page != 0 {
if let Ok(lp) = device.load_free_page(page) {
if lp.is_free().unwrap() {
lp.get_next_free() != 0
} else {
true
}
} else {
true
}
} else {
false
};
if recompute && self.heads[pos] != 0 {
let mut lp = device.load_free_page(self.heads[pos])?;
assert!(lp.is_free()?);
while lp.get_next_free() != 0 {
lp = device.load_free_page(lp.get_next_free())?;
assert!(lp.is_free()?);
}
self.tails[pos] = lp.get_index();
}
}
Ok(())
}
pub fn recover_free(&mut self, page: FreePage) -> PERes<()> {
if self.heads[list_pos(page.get_size_exp())] == 0 {
self.heads[list_pos(page.get_size_exp())] = page.get_index();
}
Ok(())
}
pub fn read(page: &mut ReadPage, holder: &mut RootPageHolder, counter: &mut Counter) -> PERes<FreeList> {
match page.read_u8() {
ALLOCATOR_ROOT_PAGE_VERSION_V0 => Self::read_v0(page, holder, counter),
ALLOCATOR_ROOT_PAGE_VERSION_V1 => Self::read_v1(page, holder, counter),
_ => panic!("unsupported format"),
}
}
fn read_v0(page: &mut ReadPage, holder: &mut RootPageHolder, counter: &mut Counter) -> PERes<FreeList> {
let buffer = Allocator::read_root_page_int(page, 259, holder, counter);
let mut read = [0; 32];
for (index, page) in &mut read.iter_mut().enumerate() {
let pos = 8 * index;
(*page) = read_u64(&buffer[pos..(pos + 8)]);
}
let mut heads = [0; LISTS_COUNT];
let mut tails = [0; LISTS_COUNT];
for pos in 0..heads.len() {
heads[pos] = read[pos + SKIPPED_EXP];
tails[pos] = read[pos + SKIPPED_EXP];
}
Ok(FreeList::new(heads, tails))
}
fn read_v1(page: &mut ReadPage, holder: &mut RootPageHolder, counter: &mut Counter) -> PERes<FreeList> {
let buffer = Allocator::read_root_page_int(page, BUFFER_SIZE, holder, counter);
let (heads, tails) = Self::read_free_list(&buffer);
Ok(FreeList::new(heads, tails))
}
pub fn read_free_list(buffer: &[u8]) -> ([u64; LISTS_COUNT], [u64; LISTS_COUNT]) {
let mut heads = [0; LISTS_COUNT];
for (index, page) in &mut heads.iter_mut().enumerate() {
let pos = 8 * index;
(*page) = read_u64(&buffer[pos..(pos + 8)]);
}
let offset = 8 * LISTS_COUNT;
let mut tails = [0; LISTS_COUNT];
for (index, page) in &mut tails.iter_mut().enumerate() {
let pos = offset + 8 * index;
(*page) = read_u64(&buffer[pos..(pos + 8)]);
}
(heads, tails)
}
pub fn write_free_list(heads: &[u64; LISTS_COUNT], tails: &[u64; LISTS_COUNT]) -> [u8; BUFFER_SIZE] {
let mut buffer = [0; BUFFER_SIZE];
for (index, page) in heads.iter().enumerate() {
let pos = index * 8;
write_u64(&mut buffer[pos..(pos + 8)], *page);
}
let offset = 8 * LISTS_COUNT;
for (index, page) in tails.iter().enumerate() {
let pos = offset + index * 8;
write_u64(&mut buffer[pos..(pos + 8)], *page);
}
buffer
}
pub fn write_list(&mut self) -> [u8; BUFFER_SIZE] {
Self::write_free_list(&self.tails, &self.heads)
}
pub fn set_free(&mut self, exp: u8, new_page: u64) -> u64 {
let pos = list_pos(exp);
let old = self.heads[pos];
self.heads[pos] = new_page;
self.to_flush = true;
if self.tails[pos] == 0 {
self.tails[pos] = new_page;
}
old
}
pub fn set_next_available(&mut self, exp: u8, new_page: u64) -> u64 {
let pos = list_pos(exp);
let old = self.tails[pos];
self.tails[pos] = new_page;
if self.heads[pos] == old {
assert!(new_page == 0);
self.heads[pos] = 0;
}
self.to_flush = true;
old
}
pub fn replace_last_free(&mut self, exp: u8, new_page: u64) -> u64 {
let pos = list_pos(exp);
let old = self.heads[pos];
self.heads[pos] = new_page;
self.to_flush = true;
old
}
pub fn get_next_available(&self, exp: u8) -> u64 {
self.tails[list_pos(exp)]
}
pub fn is_changed(&self) -> bool {
self.to_flush
}
pub fn reset_changed_flag(&mut self) {
self.to_flush = false;
}
}
impl UpdateList for FreeList {
fn update(&mut self, size: u8, page: u64) -> PERes<u64> {
let old = self.set_free(size, page);
debug_assert!(old != page || old == 0, "freeing: {} already free: {} ", page, old);
Ok(old)
}
fn remove(&mut self, size: u8, _page: u64, next: u64, _check: bool) -> PERes<()> {
let _old = self.replace_last_free(size, next);
Ok(())
}
fn remove_last(&mut self, size: u8, _page: u64, next: u64, _check: bool) -> PERes<()> {
let _old = self.set_next_available(size, next);
Ok(())
}
}