use core::mem::size_of;
use std::collections::HashMap;
use std::io;
use std::sync::{Arc, Mutex, MutexGuard, OnceLock};
use bstack::{BStackGenOp, BStackRange};
use bytemuck::{Pod, Zeroable};
use crate::BStackRaiiAllocator;
use crate::io_core::dealloc_range;
use crate::primitives::{NonNullOffset, Offset};
use crate::registry::{self, FileId};
use crate::util::bytes::read_u64;
use crate::util::{io_error, io_errorfn};
const WAL_MAGIC: u64 = 0x6273_7461_636b_5741;
const WAL_MIN_CAP: u64 = 8;
const WAL_MAX_CAP: u64 = 1 << 20;
const WAL_STATUS_OFFSET: u64 = 8;
const WAL_COUNT_OFFSET: u64 = 16;
pub const STD_WAL_ANCHOR: NonNullOffset =
unsafe { NonNullOffset::new_unchecked(Offset::from_raw(8)) };
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[repr(u8)]
pub(crate) enum WalStatus {
None = 0,
Pending = 1,
Complete = 2,
Abandon = 3,
}
impl WalStatus {
#[cfg(test)]
pub fn advance(self) -> Self {
match self {
WalStatus::None => WalStatus::Pending,
WalStatus::Pending => WalStatus::Complete,
other => other,
}
}
#[cfg(test)]
pub fn recover(self) -> Self {
match self {
WalStatus::Pending => WalStatus::Abandon,
other => other,
}
}
fn from_u8(v: u8) -> Self {
match v {
0 => WalStatus::None,
1 => WalStatus::Pending,
2 => WalStatus::Complete,
_ => WalStatus::Abandon,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[repr(u8)]
pub(crate) enum WalOp {
Alloc = 0,
Dealloc = 1,
}
impl WalOp {
fn from_u8(v: u8) -> Option<Self> {
match v {
0 => Some(WalOp::Alloc),
1 => Some(WalOp::Dealloc),
_ => None,
}
}
}
#[derive(Clone, Copy, Debug, Pod, Zeroable)]
#[repr(C)]
pub(crate) struct WalEntry {
status: u8,
op: u8,
_pad: [u8; 6],
file_id: FileId,
_obj_id: u32,
word_a: u64,
word_b: u64,
}
impl WalEntry {
pub fn alloc(status: WalStatus, slice: BStackRange) -> Self {
Self::alloc_in(status, FileId::SELF, slice)
}
pub fn alloc_in(status: WalStatus, file: FileId, slice: BStackRange) -> Self {
WalEntry {
status: status as u8,
op: WalOp::Alloc as u8,
_pad: [0; 6],
file_id: file,
_obj_id: 0,
word_a: slice.start(),
word_b: slice.len(),
}
}
#[cfg(test)]
pub fn dealloc(status: WalStatus, slice: BStackRange) -> Self {
Self::dealloc_in(status, FileId::SELF, slice)
}
pub fn dealloc_in(status: WalStatus, file: FileId, slice: BStackRange) -> Self {
WalEntry {
status: status as u8,
op: WalOp::Dealloc as u8,
_pad: [0; 6],
file_id: file,
_obj_id: 0,
word_a: slice.start(),
word_b: slice.len(),
}
}
pub fn status(&self) -> WalStatus {
WalStatus::from_u8(self.status)
}
pub fn op(&self) -> Option<WalOp> {
WalOp::from_u8(self.op)
}
pub fn file_id(&self) -> u64 {
self.file_id.as_u64()
}
pub fn as_alloc(&self) -> Option<BStackRange> {
match self.op() {
Some(WalOp::Alloc) => Some(BStackRange::new(self.word_a, self.word_b)),
_ => None,
}
}
pub fn as_dealloc(&self) -> Option<BStackRange> {
match self.op() {
Some(WalOp::Dealloc) => Some(BStackRange::new(self.word_a, self.word_b)),
_ => None,
}
}
}
pub(crate) struct WalLog {
entries: Vec<WalEntry>,
#[cfg(test)]
next_id: u64,
}
impl WalLog {
pub fn with_capacity(ops: usize) -> Self {
WalLog {
entries: Vec::with_capacity(ops),
#[cfg(test)]
next_id: 0,
}
}
#[cfg(test)]
pub fn fresh_id(&mut self) -> u64 {
let id = self.next_id;
self.next_id = self.next_id.wrapping_add(1);
id
}
pub fn append(&mut self, entry: WalEntry) {
self.entries.push(entry);
}
pub fn entries(&self) -> &[WalEntry] {
&self.entries
}
#[cfg(test)]
pub fn as_bytes(&self) -> &[u8] {
bytemuck::cast_slice(&self.entries)
}
pub fn entries_from_bytes(bytes: &[u8]) -> Vec<WalEntry> {
let sz = size_of::<WalEntry>();
let count = bytes.len() / sz;
let mut out = Vec::with_capacity(count);
for i in 0..count {
out.push(bytemuck::pod_read_unaligned(&bytes[i * sz..(i + 1) * sz]));
}
out
}
}
io_errorfn!(
corrupt_wal_capacity,
InvalidData,
"corrupt persistent WAL block: capacity/count out of range"
);
#[derive(Clone, Copy, Debug, Pod, Zeroable)]
#[repr(C)]
pub(crate) struct WalHeader {
magic: u64,
txn_status: u8,
_pad: [u8; 7],
count: u64,
capacity: u64,
}
impl WalHeader {
fn txn_status(&self) -> WalStatus {
WalStatus::from_u8(self.txn_status)
}
}
impl WalLog {
pub fn block_image(&self, txn_status: WalStatus, capacity: u64) -> Vec<u8> {
let header = WalHeader {
magic: WAL_MAGIC,
txn_status: txn_status as u8,
_pad: [0; 7],
count: self.entries.len() as u64,
capacity,
};
let mut img =
Vec::with_capacity(size_of::<WalHeader>() + self.entries.len() * size_of::<WalEntry>());
img.extend_from_slice(bytemuck::bytes_of(&header));
img.extend_from_slice(bytemuck::cast_slice(&self.entries));
img
}
}
static WAL_LOCKS: OnceLock<Mutex<HashMap<usize, std::sync::Weak<Mutex<()>>>>> = OnceLock::new();
pub(crate) fn wal_lock_for<A: BStackRaiiAllocator>(allocator: &A) -> Arc<Mutex<()>> {
let key = core::ptr::from_ref(allocator.stack()) as usize;
let reg = WAL_LOCKS.get_or_init(|| Mutex::new(HashMap::new()));
let mut map = reg.lock().unwrap_or_else(|e| e.into_inner());
if let Some(live) = map.get(&key).and_then(std::sync::Weak::upgrade) {
return live;
}
map.retain(|_, w| w.strong_count() > 0);
let fresh = Arc::new(Mutex::new(()));
map.insert(key, Arc::downgrade(&fresh));
fresh
}
thread_local! {
static HELD_CLONE_LOCKS: core::cell::RefCell<Vec<usize>> = const { core::cell::RefCell::new(Vec::new()) };
}
pub(crate) struct HeldLock {
guard: Option<MutexGuard<'static, ()>>,
_arc: Arc<Mutex<()>>,
key: usize,
}
impl HeldLock {
pub(crate) fn acquire<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<Self> {
let key = core::ptr::from_ref(allocator.stack()) as usize;
if HELD_CLONE_LOCKS.with(|h| h.borrow().contains(&key)) {
return Err(io_error!(
WouldBlock,
"clone re-entered a file already being cloned on this thread (an owned \
cross-file cycle, or a `Foreign` that resolves to the home file); this \
would deadlock on the per-file WAL lock"
));
}
let arc = wal_lock_for(allocator);
let nested = HELD_CLONE_LOCKS.with(|h| !h.borrow().is_empty());
let guard = if nested {
match arc.try_lock() {
Ok(g) => g,
Err(std::sync::TryLockError::Poisoned(e)) => e.into_inner(),
Err(std::sync::TryLockError::WouldBlock) => {
return Err(io_error!(
WouldBlock,
"clone contends for another file's WAL lock while already holding \
one (a concurrent cross-file clone is acquiring the same files in \
the opposite order); retry the clone"
));
}
}
} else {
arc.lock().unwrap_or_else(|e| e.into_inner())
};
let guard: MutexGuard<'static, ()> = unsafe { core::mem::transmute(guard) };
HELD_CLONE_LOCKS.with(|h| h.borrow_mut().push(key));
Ok(HeldLock {
guard: Some(guard),
_arc: arc,
key,
})
}
}
impl Drop for HeldLock {
fn drop(&mut self) {
self.guard = None;
HELD_CLONE_LOCKS.with(|h| {
let mut v = h.borrow_mut();
if let Some(pos) = v.iter().rposition(|&k| k == self.key) {
v.swap_remove(pos);
}
});
}
}
impl HeldLock {
fn read_anchor<A: BStackRaiiAllocator>(
&self,
allocator: &A,
) -> io::Result<Option<NonNullOffset>> {
let slot = match allocator.wal_anchor() {
Some(s) => s,
None => return Ok(None),
};
let raw = read_u64(allocator.stack(), slot.as_u64())?;
Ok(Offset::from_raw(raw).to_non_null())
}
fn ensure_block<A: BStackRaiiAllocator>(
&self,
allocator: &A,
needed: u64,
) -> io::Result<WalBlock> {
let slot = allocator
.wal_anchor()
.ok_or_else(|| io::Error::other("allocator names no WAL anchor slot"))?;
let stack = allocator.stack();
let hsz = size_of::<WalHeader>() as u64;
let esz = size_of::<WalEntry>() as u64;
let mut old_to_free: Option<BStackRange> = None;
if let Some(off) = self.read_anchor(allocator)? {
let off = off.as_u64();
let mut hbuf = [0u8; size_of::<WalHeader>()];
stack.get_into(off, &mut hbuf)?;
let header: WalHeader = bytemuck::pod_read_unaligned(&hbuf);
if header.magic == WAL_MAGIC {
if header.capacity > WAL_MAX_CAP {
return Err(corrupt_wal_capacity());
}
if header.capacity >= needed {
return Ok(WalBlock {
range: BStackRange::new(off, hsz + header.capacity * esz),
capacity: header.capacity,
});
}
old_to_free = Some(BStackRange::new(off, hsz + header.capacity * esz));
}
}
let capacity = needed.max(WAL_MIN_CAP).next_power_of_two();
let mut slice = allocator.alloc(hsz + capacity * esz)?;
let off = slice.as_range().start();
let header = WalHeader {
magic: WAL_MAGIC,
txn_status: WalStatus::None as u8,
_pad: [0; 7],
count: 0,
capacity,
};
if let Err(e) = slice.write_range(0, bytemuck::bytes_of(&header)) {
let _ = allocator.dealloc(slice);
return Err(e);
}
stack.set(slot.as_u64(), off.to_le_bytes())?;
if let Some(old) = old_to_free {
unsafe { dealloc_range(allocator, old)? };
}
Ok(WalBlock {
range: BStackRange::new(off, hsz + capacity * esz),
capacity,
})
}
pub(crate) fn persist<A: BStackRaiiAllocator>(
&self,
allocator: &A,
log: &WalLog,
status: WalStatus,
) -> io::Result<BStackRange> {
let block = self.ensure_block(allocator, log.entries().len() as u64)?;
let image = log.block_image(status, block.capacity);
allocator.stack().set(block.range.start(), &image)?;
Ok(block.range)
}
fn load<A: BStackRaiiAllocator>(
&self,
allocator: &A,
) -> io::Result<Option<(BStackRange, WalHeader, Vec<WalEntry>)>> {
let stack = allocator.stack();
let wal_off = match self.read_anchor(allocator)? {
Some(off) => off.as_u64(),
None => return Ok(None),
};
let mut hbuf = [0u8; size_of::<WalHeader>()];
stack.get_into(wal_off, &mut hbuf)?;
let header: WalHeader = bytemuck::pod_read_unaligned(&hbuf);
if header.magic != WAL_MAGIC {
return Ok(None);
}
if header.capacity > WAL_MAX_CAP || header.count > header.capacity {
return Err(corrupt_wal_capacity());
}
let ebytes = header.count as usize * size_of::<WalEntry>();
let mut ebuf = vec![0u8; ebytes];
stack.get_into(wal_off + size_of::<WalHeader>() as u64, &mut ebuf)?;
let entries = WalLog::entries_from_bytes(&ebuf);
let block_size =
size_of::<WalHeader>() as u64 + header.capacity * size_of::<WalEntry>() as u64;
Ok(Some((
BStackRange::new(wal_off, block_size),
header,
entries,
)))
}
pub(crate) fn set_idle<A: BStackRaiiAllocator>(
&self,
allocator: &A,
block_off: u64,
) -> io::Result<()> {
allocator
.stack()
.set(block_off + WAL_STATUS_OFFSET, [WalStatus::None as u8])
}
fn mark_complete<A: BStackRaiiAllocator>(
&self,
allocator: &A,
block_off: u64,
) -> io::Result<()> {
let flip = [WalStatus::Complete as u8];
let mut done = false;
allocator.stack().inplace_gen(|_feedback| {
if done {
None
} else {
done = true;
let data: &[u8] = unsafe { core::mem::transmute::<&[u8], _>(&flip[..]) };
Some(BStackGenOp::Write {
offset: block_off + WAL_STATUS_OFFSET,
data,
})
}
})
}
fn append_alloc<A: BStackRaiiAllocator>(
&self,
allocator: &A,
block_off: u64,
index: u64,
slice: BStackRange,
) -> io::Result<()> {
let stack = allocator.stack();
let hsz = size_of::<WalHeader>() as u64;
let esz = size_of::<WalEntry>() as u64;
let entry = WalEntry::alloc(WalStatus::Pending, slice);
stack.set(block_off + hsz + index * esz, bytemuck::bytes_of(&entry))?;
stack.set(block_off + WAL_COUNT_OFFSET, (index + 1).to_le_bytes())?;
Ok(())
}
fn free_recorded<A: BStackRaiiAllocator>(
&self,
allocator: &A,
file_id: u64,
slice: BStackRange,
) -> io::Result<()> {
if file_id == 0 {
return unsafe { dealloc_range(allocator, slice) };
}
let Some(id) = FileId::from_u64(file_id) else {
return Ok(()); };
match registry::with_host(id, |host| unsafe { host.dealloc(slice) }) {
Some(res) => res.map_err(|e| e.source),
None => Ok(()), }
}
pub(crate) fn finish<A: BStackRaiiAllocator>(&self, allocator: &A) -> io::Result<usize> {
let (wal_range, header, entries) = match self.load(allocator)? {
Some(x) => x,
None => return Ok(0),
};
let stack = allocator.stack();
let txn = header.txn_status();
if txn == WalStatus::None {
return Ok(0);
}
let committed = txn == WalStatus::Complete;
let base = wal_range.start() + size_of::<WalHeader>() as u64;
let esz = size_of::<WalEntry>() as u64;
let mut completed = 0usize;
if allocator.atomic_bulk() {
let mut local: Vec<BStackRange> = Vec::new();
let mut foreign: Vec<(u64, BStackRange)> = Vec::new();
for (i, e) in entries.iter().enumerate() {
if e.status() != WalStatus::Pending {
continue;
}
let slice = if committed {
e.as_dealloc()
} else {
e.as_alloc()
};
if let Some(slice) = slice {
stack.set(base + i as u64 * esz, [WalStatus::Complete as u8])?;
if e.file_id() == 0 {
local.push(slice);
} else {
foreign.push((e.file_id(), slice));
}
completed += 1;
}
}
if !local.is_empty() {
unsafe { allocator.free_many(local)? };
}
for (fid, s) in foreign {
self.free_recorded(allocator, fid, s)?;
}
} else {
for (i, e) in entries.iter().enumerate() {
if e.status() != WalStatus::Pending {
continue;
}
let slice = if committed {
e.as_dealloc()
} else {
e.as_alloc()
};
if let Some(slice) = slice {
let entry_off = base + i as u64 * esz;
stack.set(entry_off, [WalStatus::Complete as u8])?;
self.free_recorded(allocator, e.file_id(), slice)?;
completed += 1;
}
}
}
self.set_idle(allocator, wal_range.start())?;
Ok(completed)
}
}
pub(crate) struct WalTxn {
held: HeldLock,
block_off: u64,
capacity: u64,
logged: u64,
}
impl WalTxn {
pub(crate) fn begin<A: BStackRaiiAllocator>(
allocator: &A,
first: BStackRange,
) -> io::Result<Self> {
Self::begin_many(allocator, &[first])
}
pub(crate) fn begin_many<A: BStackRaiiAllocator>(
allocator: &A,
ranges: &[BStackRange],
) -> io::Result<Self> {
let held = HeldLock::acquire(allocator)?;
let mut log = WalLog::with_capacity(ranges.len());
for &r in ranges {
log.append(WalEntry::alloc(WalStatus::Pending, r));
}
let block = held.persist(allocator, &log, WalStatus::Pending)?;
Ok(WalTxn {
held,
block_off: block.start(),
capacity: Self::capacity_of(block),
logged: ranges.len() as u64,
})
}
pub(crate) fn append<A: BStackRaiiAllocator>(
&mut self,
allocator: &A,
logged_so_far: &[BStackRange],
range: BStackRange,
) -> io::Result<()> {
if self.logged < self.capacity {
self.held
.append_alloc(allocator, self.block_off, self.logged, range)?;
self.logged += 1;
} else {
let mut log = WalLog::with_capacity(logged_so_far.len() + 1);
for &r in logged_so_far {
log.append(WalEntry::alloc(WalStatus::Pending, r));
}
log.append(WalEntry::alloc(WalStatus::Pending, range));
let block = self.held.persist(allocator, &log, WalStatus::Pending)?;
self.block_off = block.start();
self.capacity = Self::capacity_of(block);
self.logged = logged_so_far.len() as u64 + 1;
}
Ok(())
}
fn capacity_of(block: BStackRange) -> u64 {
(block.len() - size_of::<WalHeader>() as u64) / size_of::<WalEntry>() as u64
}
pub(crate) fn commit_marker_off(&self) -> u64 {
self.block_off + WAL_STATUS_OFFSET
}
pub(crate) fn set_idle<A: BStackRaiiAllocator>(&self, allocator: &A) -> io::Result<()> {
self.held.set_idle(allocator, self.block_off)
}
pub(crate) fn finish<A: BStackRaiiAllocator>(&self, allocator: &A) -> io::Result<usize> {
self.held.finish(allocator)
}
}
pub(crate) fn alloc_logged<A: BStackRaiiAllocator>(
alloc: &A,
wal: &mut Option<WalTxn>,
allocated: &mut Vec<BStackRange>,
size: u64,
) -> io::Result<BStackRange> {
let slice = alloc.alloc(size)?;
let range = slice.as_range();
if alloc.wal_anchor().is_some()
&& let Err(e) = log_alloc(alloc, wal, allocated, range)
{
let _ = alloc.dealloc(slice);
return Err(e);
}
allocated.push(range);
Ok(range)
}
fn log_alloc<A: BStackRaiiAllocator>(
alloc: &A,
wal: &mut Option<WalTxn>,
allocated: &[BStackRange],
range: BStackRange,
) -> io::Result<()> {
match wal {
None => {
*wal = Some(WalTxn::begin(alloc, range)?);
Ok(())
}
Some(w) => w.append(alloc, allocated, range),
}
}
struct WalBlock {
range: BStackRange,
capacity: u64,
}
pub fn finish<A: BStackRaiiAllocator>(allocator: &A) -> io::Result<usize> {
HeldLock::acquire(allocator)?.finish(allocator)
}
pub(crate) fn commit_frees<A: BStackRaiiAllocator>(
allocator: &A,
slices: Vec<(FileId, BStackRange)>,
) -> io::Result<()> {
if slices.is_empty() {
return Ok(());
}
if allocator.atomic_bulk() && slices.iter().all(|(fid, _)| *fid == FileId::SELF) {
return unsafe { allocator.free_many(slices.into_iter().map(|(_, r)| r)) };
}
let held = HeldLock::acquire(allocator)?;
let mut log = WalLog::with_capacity(slices.len());
for (fid, s) in &slices {
log.append(WalEntry::dealloc_in(WalStatus::Pending, *fid, *s));
}
let wal_range = held.persist(allocator, &log, WalStatus::Pending)?;
held.mark_complete(allocator, wal_range.start())?;
held.finish(allocator)?;
Ok(())
}
pub(crate) unsafe fn commit_home_frees<A: BStackRaiiAllocator>(
allocator: &A,
ranges: Vec<BStackRange>,
) -> io::Result<()> {
commit_frees(
allocator,
ranges.into_iter().map(|r| (FileId::SELF, r)).collect(),
)
}
#[cfg(test)]
pub(crate) fn test_reentrant_acquire_is_rejected<A: BStackRaiiAllocator>(alloc: &A) -> bool {
let _outer = HeldLock::acquire(alloc).expect("first acquire should succeed");
HeldLock::acquire(alloc).is_err()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn wal_status_maps() {
assert_eq!(WalStatus::None.advance(), WalStatus::Pending);
assert_eq!(WalStatus::Pending.advance(), WalStatus::Complete);
assert_eq!(WalStatus::Complete.advance(), WalStatus::Complete);
assert_eq!(WalStatus::Abandon.advance(), WalStatus::Abandon);
assert_eq!(WalStatus::None.recover(), WalStatus::None);
assert_eq!(WalStatus::Pending.recover(), WalStatus::Abandon);
assert_eq!(WalStatus::Complete.recover(), WalStatus::Complete);
}
#[test]
fn wal_entry_roundtrip() {
let a = WalEntry::alloc(WalStatus::Pending, BStackRange::new(0x1000, 256));
assert_eq!(a.op(), Some(WalOp::Alloc));
assert_eq!(a.status(), WalStatus::Pending);
assert_eq!(a.as_alloc(), Some(BStackRange::new(0x1000, 256)));
assert_eq!(a.as_dealloc(), None);
assert_eq!(a.file_id(), 0);
let d = WalEntry::dealloc(WalStatus::Complete, BStackRange::new(0x6CD4, 256));
assert_eq!(d.op(), Some(WalOp::Dealloc));
assert_eq!(d.as_dealloc(), Some(BStackRange::new(0x6CD4, 256)));
assert_eq!(d.as_alloc(), None);
assert_eq!(d.file_id(), 0);
let fa = WalEntry::alloc_in(
WalStatus::Pending,
FileId::from_u64(7).unwrap(),
BStackRange::new(0x20, 48),
);
assert_eq!(fa.file_id(), 7);
assert_eq!(fa.as_alloc(), Some(BStackRange::new(0x20, 48)));
let fd = WalEntry::dealloc_in(
WalStatus::Pending,
FileId::from_u64(3).unwrap(),
BStackRange::new(0x40, 16),
);
assert_eq!(fd.file_id(), 3);
assert_eq!(fd.as_dealloc(), Some(BStackRange::new(0x40, 16)));
}
#[test]
fn wal_entry_is_32_bytes_and_pod_roundtrips() {
assert_eq!(size_of::<WalEntry>(), 32);
let mut log = WalLog::with_capacity(2);
log.append(WalEntry::alloc(
WalStatus::Pending,
BStackRange::new(8192, 64),
));
log.append(WalEntry::dealloc_in(
WalStatus::Pending,
FileId::from_u64(9).unwrap(),
BStackRange::new(4096, 64),
));
let bytes = log.as_bytes().to_vec();
let back = WalLog::entries_from_bytes(&bytes);
assert_eq!(back.len(), 2);
assert_eq!(back[0].as_alloc(), Some(BStackRange::new(8192, 64)));
assert_eq!(back[0].file_id(), 0);
assert_eq!(back[1].as_dealloc(), Some(BStackRange::new(4096, 64)));
assert_eq!(back[1].file_id(), 9); }
#[test]
fn wal_fresh_id_wraps() {
let mut log = WalLog::with_capacity(0);
assert_eq!(log.fresh_id(), 0);
assert_eq!(log.fresh_id(), 1);
log.next_id = u64::MAX;
assert_eq!(log.fresh_id(), u64::MAX);
assert_eq!(log.fresh_id(), 0); }
}