use core::cell::UnsafeCell;
use std::sync::atomic::{AtomicBool, AtomicPtr, AtomicUsize, Ordering};
use std::sync::{Arc, OnceLock};
use crate::sched::io_pool::global_io_pool;
pub trait VerifyHasher: Send + 'static {
fn update(&mut self, chunk: &[u8]);
fn finalize(self: Box<Self>) -> [u8; 32];
}
#[cfg(feature = "verify-chain")]
mod blake3_impl {
use super::VerifyHasher;
pub struct Blake3Hasher(pub blake3::Hasher);
impl Blake3Hasher {
pub fn new() -> Self {
Self(blake3::Hasher::new())
}
}
impl Default for Blake3Hasher {
fn default() -> Self {
Self::new()
}
}
impl VerifyHasher for Blake3Hasher {
fn update(&mut self, chunk: &[u8]) {
self.0.update(chunk);
}
fn finalize(self: Box<Self>) -> [u8; 32] {
*self.0.finalize().as_bytes()
}
}
}
#[cfg(feature = "verify-chain")]
pub use blake3_impl::Blake3Hasher;
pub struct FxFallbackHasher {
state: u64,
}
impl FxFallbackHasher {
pub fn new() -> Self {
Self { state: 0xCBF2_9CE4_8422_2325 }
}
}
impl Default for FxFallbackHasher {
fn default() -> Self {
Self::new()
}
}
impl VerifyHasher for FxFallbackHasher {
fn update(&mut self, chunk: &[u8]) {
const PRIME: u64 = 0x100_0000_01B3;
for &b in chunk {
self.state = self.state.wrapping_mul(PRIME) ^ (b as u64);
}
}
fn finalize(self: Box<Self>) -> [u8; 32] {
let mut out = [0u8; 32];
let mut acc = self.state;
for i in 0..4 {
let mix = acc.wrapping_mul(0xC2B2_AE3D_27D4_EB4F);
out[i * 8..i * 8 + 8].copy_from_slice(&mix.to_le_bytes());
acc = mix.rotate_left(17);
}
out
}
}
#[cfg(feature = "verify-chain")]
pub fn default_hasher() -> Box<dyn VerifyHasher> {
Box::new(Blake3Hasher::new())
}
#[cfg(not(feature = "verify-chain"))]
pub fn default_hasher() -> Box<dyn VerifyHasher> {
Box::new(FxFallbackHasher::new())
}
struct ChainShared {
pending: AtomicUsize,
submitted: AtomicUsize,
waiter: OnceLock<std::thread::Thread>,
arrived: AtomicPtr<Arrival>,
folding: AtomicBool,
fold: UnsafeCell<FoldState>,
}
unsafe impl Sync for ChainShared {}
struct Arrival {
index: usize,
bytes: Vec<u8>,
next: *mut Arrival,
}
#[derive(Default)]
struct FoldState {
hasher: Option<Box<dyn VerifyHasher>>,
waiting: Vec<Option<Vec<u8>>>,
next: usize,
}
fn with_fold<R>(inner: &ChainShared, act: impl FnOnce(&mut FoldState) -> R) -> Option<R> {
if inner
.folding
.compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
.is_err()
{
return None;
}
let state = unsafe { &mut *inner.fold.get() };
let out = act(state);
inner.folding.store(false, Ordering::Release);
Some(out)
}
fn deposit_and_fold(inner: &ChainShared, index: usize, chunk: Vec<u8>) {
let node = Box::into_raw(Box::new(Arrival {
index,
bytes: chunk,
next: core::ptr::null_mut(),
}));
loop {
let head = inner.arrived.load(Ordering::Acquire);
unsafe { (*node).next = head };
if inner
.arrived
.compare_exchange(head, node, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
break;
}
}
fold_ready_prefix(inner);
}
fn fold_ready_prefix(inner: &ChainShared) {
loop {
let folded = with_fold(inner, |state| {
let mut chain = inner.arrived.swap(core::ptr::null_mut(), Ordering::AcqRel);
while !chain.is_null() {
let Arrival { index, bytes, next } = *unsafe { Box::from_raw(chain) };
chain = next;
if state.waiting.len() <= index {
state.waiting.resize_with(index + 1, || None);
}
state.waiting[index] = Some(bytes);
}
if let Some(h) = state.hasher.as_mut() {
let mut next = state.next;
while let Some(slot) = state.waiting.get_mut(next) {
let Some(bytes) = slot.take() else { break };
h.update(&bytes);
next += 1;
}
state.next = next;
}
});
if folded.is_none() {
return;
}
if inner.arrived.load(Ordering::Acquire).is_null() {
return;
}
}
}
#[derive(Clone)]
pub struct VerifyChain {
inner: Arc<ChainShared>,
}
impl VerifyChain {
pub fn new() -> Self {
Self::with_hasher(default_hasher())
}
pub fn with_hasher(hasher: Box<dyn VerifyHasher>) -> Self {
Self {
inner: Arc::new(ChainShared {
pending: AtomicUsize::new(0),
submitted: AtomicUsize::new(0),
waiter: OnceLock::new(),
arrived: AtomicPtr::new(core::ptr::null_mut()),
folding: AtomicBool::new(false),
fold: UnsafeCell::new(FoldState {
hasher: Some(hasher),
waiting: Vec::new(),
next: 0,
}),
}),
}
}
pub fn submit_chunk(&self, chunk: Vec<u8>) {
self.inner.pending.fetch_add(1, Ordering::AcqRel);
let index = self.inner.submitted.fetch_add(1, Ordering::AcqRel);
let inner = Arc::clone(&self.inner);
let task = move || {
deposit_and_fold(&inner, index, chunk);
let prev = inner.pending.fetch_sub(1, Ordering::AcqRel);
if prev == 1
&& let Some(waiter) = inner.waiter.get()
{
waiter.unpark();
}
};
match global_io_pool() {
Some(pool) => pool.submit(task),
None => task(),
}
}
pub fn finalize(self) -> [u8; 32] {
loop {
if self.inner.pending.load(Ordering::Acquire) == 0 {
break;
}
self.inner.waiter.get_or_init(std::thread::current);
if self.inner.pending.load(Ordering::Acquire) == 0 {
break;
}
std::thread::park();
}
fold_ready_prefix(&self.inner);
loop {
if let Some(root) = with_fold(&self.inner, |state| match state.hasher.take() {
Some(hasher) => hasher.finalize(),
None => [0u8; 32],
}) {
return root;
}
std::hint::spin_loop();
}
}
pub fn pending_count(&self) -> usize {
self.inner.pending.load(Ordering::Acquire)
}
}
impl Drop for ChainShared {
fn drop(&mut self) {
let mut chain = *self.arrived.get_mut();
while !chain.is_null() {
let node = *unsafe { Box::from_raw(chain) };
chain = node.next;
}
}
}
impl Default for VerifyChain {
fn default() -> Self {
Self::new()
}
}
impl std::fmt::Debug for VerifyChain {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("VerifyChain")
.field("pending", &self.pending_count())
.finish()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn fx_fallback_finalize_with_no_chunks_returns_seeded_root() {
let h: Box<FxFallbackHasher> = Box::default();
let root = h.finalize();
assert!(root.iter().any(|&b| b != 0), "expected non-zero root for seeded empty input");
}
#[test]
fn chain_inline_single_chunk_produces_stable_root() {
let chain = VerifyChain::new();
chain.submit_chunk(b"hello world".to_vec());
let root1 = chain.finalize();
let chain2 = VerifyChain::new();
chain2.submit_chunk(b"hello world".to_vec());
let root2 = chain2.finalize();
assert_eq!(root1, root2, "same input should produce same root");
}
#[test]
fn chain_inline_different_chunks_produce_different_roots() {
let c1 = VerifyChain::new();
c1.submit_chunk(b"input A".to_vec());
let r1 = c1.finalize();
let c2 = VerifyChain::new();
c2.submit_chunk(b"input B".to_vec());
let r2 = c2.finalize();
assert_ne!(r1, r2, "different inputs should produce different roots");
}
#[test]
fn chain_inline_many_chunks_finalize_blocks_until_done() {
const N: usize = 32;
let chain = VerifyChain::new();
for i in 0..N {
let chunk = format!("stripe-{:08}", i).into_bytes();
chain.submit_chunk(chunk);
}
assert_eq!(chain.pending_count(), 0);
let root = chain.finalize();
assert!(root.iter().any(|&b| b != 0));
}
#[test]
fn the_root_does_not_depend_on_the_order_the_chunks_finish() {
let chunks: Vec<Vec<u8>> = vec![
b"first".to_vec(),
b"second".to_vec(),
b"third".to_vec(),
b"fourth".to_vec(),
];
let in_order = VerifyChain::new();
for c in &chunks {
in_order.submit_chunk(c.clone());
}
let want = in_order.finalize();
for arrival in [[3usize, 1, 0, 2], [3, 2, 1, 0], [1, 3, 2, 0]] {
let chain = VerifyChain::new();
for &i in &arrival {
deposit_and_fold(&chain.inner, i, chunks[i].clone());
}
assert_eq!(
chain.finalize(),
want,
"arrivals {arrival:?} rooted differently from submission order"
);
}
}
#[test]
fn a_chunk_still_outstanding_is_folded_in_by_finalize() {
let chunks: Vec<Vec<u8>> = vec![b"a".to_vec(), b"b".to_vec()];
let in_order = VerifyChain::new();
for c in &chunks {
in_order.submit_chunk(c.clone());
}
let want = in_order.finalize();
let chain = VerifyChain::new();
deposit_and_fold(&chain.inner, 1, chunks[1].clone());
let cursor = with_fold(&chain.inner, |state| state.next)
.expect("no task holds the fold token in this test");
assert_eq!(cursor, 0, "nothing folds while index 0 is missing");
with_fold(&chain.inner, |state| {
if state.waiting.is_empty() {
state.waiting.push(None);
}
state.waiting[0] = Some(chunks[0].clone());
})
.expect("no task holds the fold token in this test");
assert_eq!(chain.finalize(), want, "finalize must sweep what is left");
}
#[test]
fn chain_finalize_after_finalize_returns_zero_root() {
let chain = VerifyChain::new();
chain.submit_chunk(vec![1, 2, 3]);
let first = chain.clone().finalize();
let second = chain.finalize();
assert!(first.iter().any(|&b| b != 0));
assert_eq!(second, [0u8; 32]);
}
}