use std::collections::BTreeMap;
use serde::{Deserialize, Serialize};
use crate::error::{MnemoError, Result};
#[derive(Serialize, Deserialize, Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct FreeRun {
pub freed_at: u64,
pub page: u64,
pub count: u64,
}
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct FreeList {
runs: BTreeMap<u64, (u64, u64)>,
}
impl FreeList {
pub fn from_runs(runs: Vec<FreeRun>) -> Result<FreeList> {
let mut fl = FreeList::default();
for r in runs {
fl.free(r.freed_at, r.page, r.count)?;
}
Ok(fl)
}
pub fn to_runs(&self) -> Vec<FreeRun> {
self.runs
.iter()
.map(|(&page, &(count, freed_at))| FreeRun {
freed_at,
page,
count,
})
.collect()
}
pub fn len(&self) -> usize {
self.runs.len()
}
pub fn pages(&self) -> u64 {
self.runs.values().map(|&(c, _)| c).sum()
}
pub fn pinned_pages(&self, min_snapshot_txn: u64) -> u64 {
self.runs
.values()
.filter(|&&(_, f)| f > min_snapshot_txn)
.map(|&(c, _)| c)
.sum()
}
pub fn take_tail(
&mut self,
end: u64,
committed_txn: u64,
min_snapshot_txn: u64,
) -> Option<u64> {
let (&p, &(c, f)) = self.runs.range(..end).next_back()?;
if p + c == end && f <= committed_txn && f <= min_snapshot_txn {
self.runs.remove(&p);
Some(p)
} else {
None
}
}
pub fn free(&mut self, freed_at: u64, page: u64, count: u64) -> Result<()> {
if count == 0 {
return Ok(());
}
if page == 0 {
return Err(MnemoError::Invalid(
"free list: page 0 is the header".into(),
));
}
let end = page
.checked_add(count)
.ok_or_else(|| MnemoError::Invalid("free list: run overflows".into()))?;
let mut start = page;
let mut len = count;
if let Some((&p, &(c, f))) = self.runs.range(..=page).next_back() {
if p + c > page {
return Err(MnemoError::Invalid(format!(
"free list: double free of page {page} (overlaps run {p}+{c})"
)));
}
if p + c == page && f == freed_at {
self.runs.remove(&p);
start = p;
len += c;
}
}
if let Some((&p, &(c, f))) = self.runs.range(page..).next() {
if p < end {
return Err(MnemoError::Invalid(format!(
"free list: double free of page {p} (inside freed run {page}+{count})"
)));
}
if p == end && f == freed_at {
self.runs.remove(&p);
len += c;
}
}
self.runs.insert(start, (len, freed_at));
Ok(())
}
pub fn alloc(&mut self, count: u64, committed_txn: u64, min_snapshot_txn: u64) -> Option<u64> {
if count == 0 {
return None;
}
let eligible = |f: u64| f <= committed_txn && f <= min_snapshot_txn;
let fits = |runs: &BTreeMap<u64, (u64, u64)>| {
runs.iter()
.find(|(_, &(c, f))| c >= count && eligible(f))
.map(|(&p, &(c, f))| (p, c, f))
};
let (page, c, f) = match fits(&self.runs) {
Some(hit) => hit,
None => {
self.merge_eligible(committed_txn, min_snapshot_txn);
fits(&self.runs)?
}
};
self.runs.remove(&page);
if c > count {
self.runs.insert(page + count, (c - count, f));
}
Some(page)
}
pub fn merge_eligible(&mut self, committed_txn: u64, min_snapshot_txn: u64) {
let eligible = |f: u64| f <= committed_txn && f <= min_snapshot_txn;
let runs: Vec<(u64, u64, u64)> = self.runs.iter().map(|(&p, &(c, f))| (p, c, f)).collect();
let mut merged: BTreeMap<u64, (u64, u64)> = BTreeMap::new();
let mut cur: Option<(u64, u64, u64)> = None;
for (p, c, f) in runs {
cur = match cur {
Some((cp, cc, cf)) if cp + cc == p && eligible(cf) && eligible(f) => {
Some((cp, cc + c, cf.max(f)))
}
Some((cp, cc, cf)) => {
merged.insert(cp, (cc, cf));
Some((p, c, f))
}
None => Some((p, c, f)),
};
}
if let Some((cp, cc, cf)) = cur {
merged.insert(cp, (cc, cf));
}
self.runs = merged;
}
pub fn unfree(&mut self, page: u64, count: u64) {
if count == 0 {
return;
}
let end = page.saturating_add(count);
let overlapping: Vec<(u64, u64, u64)> = self
.runs
.range(..end)
.rev()
.take_while(|(&p, &(c, _))| p + c > page || p >= page)
.filter(|(&p, &(c, _))| p + c > page && p < end)
.map(|(&p, &(c, f))| (p, c, f))
.collect();
for (p, c, f) in overlapping {
self.runs.remove(&p);
if p < page {
self.runs.insert(p, (page - p, f));
}
if p + c > end {
self.runs.insert(end, (p + c - end, f));
}
}
}
pub fn overlaps(&self, page: u64, count: u64) -> bool {
let end = page.saturating_add(count);
self.runs
.range(..end)
.next_back()
.is_some_and(|(&p, &(c, _))| p + c > page)
}
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
#[test]
fn coalesces_and_splits() {
let mut fl = FreeList::default();
fl.free(5, 10, 2).unwrap();
fl.free(5, 12, 3).unwrap();
assert_eq!(fl.len(), 1, "same transaction: coalesced");
fl.free(6, 8, 2).unwrap();
assert_eq!(fl.len(), 2, "different transactions stay apart");
assert_eq!(fl.alloc(7, 5, u64::MAX), None, "txn 6 isn't committed");
assert_eq!(fl.alloc(7, 6, u64::MAX), Some(8));
assert_eq!(fl.len(), 0);
fl.free(6, 10, 2).unwrap();
fl.free(6, 12, 2).unwrap();
assert_eq!(fl.alloc(0, 6, u64::MAX), None);
assert_eq!(fl.pages(), 4);
fl.unfree(12, 1);
assert_eq!(fl.pages(), 3);
assert!(!fl.overlaps(12, 1));
assert!(fl.overlaps(11, 1));
assert!(fl.overlaps(13, 2));
}
#[test]
fn quarantine_blocks_uncommitted_and_snapshot_pinned_runs() {
let mut fl = FreeList::default();
fl.free(10, 100, 4).unwrap();
assert_eq!(fl.alloc(1, 9, u64::MAX), None);
assert_eq!(fl.alloc(1, 10, 8), None);
assert_eq!(fl.alloc(1, 10, 10), Some(100));
}
#[test]
fn tail_runs_come_off_only_when_eligible() {
let mut fl = FreeList::default();
fl.free(3, 10, 5).unwrap(); assert_eq!(fl.take_tail(16, 9, u64::MAX), None, "not at the tail");
assert_eq!(fl.take_tail(15, 2, u64::MAX), None, "not committed");
assert_eq!(fl.take_tail(15, 9, 2), None, "pinned by a snapshot");
assert_eq!(fl.pinned_pages(2), 5);
assert_eq!(fl.take_tail(15, 9, 9), Some(10));
assert_eq!(fl.pages(), 0);
}
#[test]
fn double_free_is_an_error() {
let mut fl = FreeList::default();
fl.free(1, 10, 4).unwrap();
assert!(fl.free(2, 12, 1).is_err());
assert!(fl.free(2, 8, 3).is_err());
assert!(fl.free(2, 13, 5).is_err());
assert!(fl.free(2, 0, 1).is_err());
assert!(fl.free(2, 14, 1).is_ok());
assert!(FreeList::from_runs(vec![
FreeRun {
freed_at: 1,
page: 5,
count: 3
},
FreeRun {
freed_at: 1,
page: 6,
count: 1
},
])
.is_err());
}
#[derive(Debug, Clone)]
enum Op {
Alloc(u64),
FreeOne(usize),
Commit,
Snapshot,
DropSnapshot,
}
fn op() -> impl Strategy<Value = Op> {
prop_oneof![
4 => (1u64..4).prop_map(Op::Alloc),
3 => any::<usize>().prop_map(Op::FreeOne),
2 => Just(Op::Commit),
1 => Just(Op::Snapshot),
1 => Just(Op::DropSnapshot),
]
}
proptest! {
#[test]
fn alloc_never_returns_quarantined_or_live_pages(ops in proptest::collection::vec(op(), 1..200)) {
let mut fl = FreeList::default();
let mut next_page = 1u64;
let mut committed = 0u64;
let mut live: Vec<(u64, u64)> = Vec::new();
let mut snaps: Vec<u64> = Vec::new();
let mut freed_at: std::collections::HashMap<u64, u64> = Default::default();
for op in ops {
let txn = committed + 1;
let min_snap = snaps.iter().copied().min().unwrap_or(u64::MAX);
match op {
Op::Alloc(n) => {
let page = match fl.alloc(n, committed, min_snap) {
Some(p) => {
for q in p..p + n {
let f = freed_at.remove(&q).expect("allocated page was on the list");
prop_assert!(f <= committed, "page {q} freed at {f}, committed {committed}");
prop_assert!(f <= min_snap, "page {q} freed at {f}, oldest snapshot {min_snap}");
}
p
}
None => {
let p = next_page;
next_page += n;
p
}
};
for &(lp, lc) in &live {
prop_assert!(page + n <= lp || lp + lc <= page, "overlaps a live run");
}
live.push((page, n));
}
Op::FreeOne(i) => {
if !live.is_empty() {
let (p, c) = live.swap_remove(i % live.len());
fl.free(txn, p, c).unwrap();
for q in p..p + c {
freed_at.insert(q, txn);
}
}
}
Op::Commit => committed = txn,
Op::Snapshot => snaps.push(committed),
Op::DropSnapshot => {
if !snaps.is_empty() {
snaps.remove(0);
}
}
}
prop_assert_eq!(fl.pages(), freed_at.len() as u64);
}
}
}
}