use std::collections::BTreeMap;
use std::fs::File;
use std::io::Read;
use std::path::{Component, Path, PathBuf};
use std::sync::Arc;
use anyhow::{bail, Context, Result};
use crate::part::idcol::{get_varint, put_varint};
use crate::readat::Slice;
pub const MAGIC: &[u8; 8] = b"TURNCTNR";
pub const CONTAINER_VERSION: u8 = 1;
pub const SLOT_LEN: u64 = 4096;
pub const REGION_START: u64 = SLOT_LEN * 2;
const SB_LEN: usize = 56;
pub const HOT_SUFFIX: &str = "-hot";
const MAX_DIR_STORED: u32 = 64 << 20;
const MAX_DIR_RAW: u32 = 256 << 20;
const MAX_MEMBERS: u32 = 1_000_000;
const MAX_NAME: u64 = 16 << 10;
type Entry = (u64, u64, u32);
#[derive(Clone, Copy, Debug)]
struct Superblock {
seq: u64,
dir_off: u64,
dir_stored: u32,
dir_raw: u32,
n_entries: u32,
dir_xsum: u32,
tail: u64,
dir_codec: u8,
}
impl Superblock {
fn empty() -> Superblock {
Superblock {
seq: 0,
dir_off: REGION_START,
dir_stored: 0,
dir_raw: 0,
n_entries: 0,
dir_xsum: 0,
tail: REGION_START,
dir_codec: 0,
}
}
fn encode(&self) -> [u8; SLOT_LEN as usize] {
let mut slot = [0u8; SLOT_LEN as usize];
slot[0..8].copy_from_slice(MAGIC);
slot[8..16].copy_from_slice(&self.seq.to_le_bytes());
slot[16..24].copy_from_slice(&self.dir_off.to_le_bytes());
slot[24..28].copy_from_slice(&self.dir_stored.to_le_bytes());
slot[28..32].copy_from_slice(&self.dir_raw.to_le_bytes());
slot[32..36].copy_from_slice(&self.n_entries.to_le_bytes());
slot[36..40].copy_from_slice(&self.dir_xsum.to_le_bytes());
slot[40..48].copy_from_slice(&self.tail.to_le_bytes());
slot[48] = self.dir_codec;
slot[49] = CONTAINER_VERSION;
let digest = blake3::hash(&slot[0..52]);
slot[52..56].copy_from_slice(&digest.as_bytes()[0..4]);
slot
}
fn decode(slot: &[u8]) -> Result<Option<Superblock>> {
if slot.len() < SB_LEN || &slot[0..8] != MAGIC {
return Ok(None);
}
let digest = blake3::hash(&slot[0..52]);
if slot[52..56] != digest.as_bytes()[0..4] {
return Ok(None);
}
if slot[49] != CONTAINER_VERSION {
bail!(
"container superblock declares version {}, and this build reads {CONTAINER_VERSION}",
slot[49]
);
}
if slot[50..52] != [0, 0] {
bail!("container superblock sets reserved bits that must be zero");
}
Ok(Some(Superblock {
seq: u64::from_le_bytes(slot[8..16].try_into()?),
dir_off: u64::from_le_bytes(slot[16..24].try_into()?),
dir_stored: u32::from_le_bytes(slot[24..28].try_into()?),
dir_raw: u32::from_le_bytes(slot[28..32].try_into()?),
n_entries: u32::from_le_bytes(slot[32..36].try_into()?),
dir_xsum: u32::from_le_bytes(slot[36..40].try_into()?),
tail: u64::from_le_bytes(slot[40..48].try_into()?),
dir_codec: slot[48],
}))
}
}
pub struct Container {
f: Arc<File>,
path: PathBuf,
dir: BTreeMap<String, Entry>,
free: Vec<(u64, u64)>,
tail: u64,
seq: u64,
slot: u8,
staged: bool,
}
impl Container {
pub fn create(path: &Path) -> Result<Container> {
let f = crate::vfs::create_new(path)
.with_context(|| format!("create container {}", path.display()))?;
let sb = Superblock::empty();
crate::vfs::write_all_at(&f, path, &sb.encode(), 0)?;
crate::vfs::write_all_at(&f, path, &[0u8; SLOT_LEN as usize], SLOT_LEN)?;
crate::vfs::sync_file(&f, path)?;
if let Some(parent) = path.parent() {
let _ = crate::vfs::sync_dir(parent);
}
Ok(Container {
f: Arc::new(f),
path: path.to_path_buf(),
dir: BTreeMap::new(),
free: Vec::new(),
tail: REGION_START,
seq: 0,
slot: 0,
staged: false,
})
}
pub fn open(path: &Path) -> Result<Container> {
let (f, created) = crate::vfs::open_or_create(path)
.with_context(|| format!("open container {}", path.display()))?;
if created {
let _ = crate::vfs::unlink(path);
bail!("not a container: {} does not exist", path.display());
}
let len = f.metadata()?.len();
if len < REGION_START {
bail!("not a container: {} is shorter than its superblocks", path.display());
}
let mut a = [0u8; SLOT_LEN as usize];
let mut b = [0u8; SLOT_LEN as usize];
crate::sys::read_exact_at(&f, &mut a, 0)?;
crate::sys::read_exact_at(&f, &mut b, SLOT_LEN)?;
let sa = Superblock::decode(&a)
.with_context(|| format!("container {} slot 0", path.display()))?;
let sb = Superblock::decode(&b)
.with_context(|| format!("container {} slot 1", path.display()))?;
if sa.is_none() && sb.is_none() {
bail!("not a container, or both superblocks are unreadable: {}", path.display());
}
let (live, slot) = match (sa, sb) {
(Some(x), Some(y)) if y.seq > x.seq => (y, 1u8),
(Some(x), _) => (x, 0u8),
(None, Some(y)) => (y, 1u8),
(None, None) => unreachable!("checked above"),
};
if live.tail > len {
bail!(
"container {} is truncated: committed tail {} exceeds file length {len}",
path.display(),
live.tail
);
}
let f = Arc::new(f);
let (dir, free) = read_directory(&f, path, &live)?;
Ok(Container {
f,
path: path.to_path_buf(),
dir,
free,
tail: live.tail,
seq: live.seq,
slot,
staged: false,
})
}
pub fn seq(&self) -> u64 {
self.seq
}
pub fn names(&self) -> impl Iterator<Item = &str> {
self.dir.keys().map(|k| k.as_str())
}
pub fn contains(&self, name: &str) -> bool {
self.dir.contains_key(name)
}
pub fn len(&self) -> usize {
self.dir.len()
}
pub fn is_empty(&self) -> bool {
self.dir.is_empty()
}
pub fn free_bytes(&self) -> u64 {
self.free.iter().map(|(_, len)| *len).sum()
}
pub fn member_bytes(&self) -> u64 {
self.dir.values().map(|(_, len, _)| *len).sum()
}
pub fn extent(&self, name: &str) -> Option<Slice<Arc<File>>> {
let &(off, len, _) = self.dir.get(name)?;
Some(Slice::new(self.f.clone(), off, len))
}
pub fn read_file_bounded(&self, name: &str, max_bytes: u64) -> Result<Vec<u8>> {
let &(off, len, _) = self
.dir
.get(name)
.ok_or_else(|| anyhow::anyhow!("container member not found: {name}"))?;
if len > max_bytes {
bail!("container member {name} is {len} bytes, over the {max_bytes} byte ceiling");
}
let mut buf = Vec::new();
buf.try_reserve_exact(len as usize)?;
buf.resize(len as usize, 0);
crate::sys::read_exact_at(&self.f, &mut buf, off)?;
Ok(buf)
}
pub fn put_bytes(&mut self, name: &str, bytes: &[u8]) -> Result<()> {
validate_name(name)?;
let off = self.tail;
crate::vfs::write_all_at(&self.f, &self.path, bytes, off)?;
self.stage_entry(name, off, bytes.len() as u64, crc32fast::hash(bytes));
Ok(())
}
pub fn put_stream(
&mut self,
name: &str,
len: u64,
mut fill: impl FnMut(u64, &mut [u8]) -> std::io::Result<()>,
) -> Result<()> {
validate_name(name)?;
let off = self.tail;
let mut hasher = crc32fast::Hasher::new();
let mut buf = vec![0u8; (1 << 20).min(len.max(1)) as usize];
let mut at = 0u64;
while at < len {
let take = buf.len().min((len - at) as usize);
fill(at, &mut buf[..take])?;
crate::vfs::write_all_at(&self.f, &self.path, &buf[..take], off + at)?;
hasher.update(&buf[..take]);
at += take as u64;
}
self.stage_entry(name, off, len, hasher.finalize());
Ok(())
}
pub fn ingest(&mut self, name: &str, from: &Path) -> Result<u64> {
validate_name(name)?;
let mut src =
File::open(from).with_context(|| format!("ingest source {}", from.display()))?;
let off = self.tail;
let mut hasher = crc32fast::Hasher::new();
let mut buf = vec![0u8; 1 << 20];
let mut written = 0u64;
loop {
let n = src.read(&mut buf)?;
if n == 0 {
break;
}
crate::vfs::write_all_at(&self.f, &self.path, &buf[..n], off + written)?;
hasher.update(&buf[..n]);
written += n as u64;
}
self.stage_entry(name, off, written, hasher.finalize());
Ok(written)
}
pub fn remove(&mut self, name: &str) -> Result<bool> {
match self.dir.remove(name) {
Some((off, len, _)) => {
self.free.push((off, len));
self.staged = true;
Ok(true)
}
None => Ok(false),
}
}
fn stage_entry(&mut self, name: &str, off: u64, len: u64, xsum: u32) {
if let Some((old_off, old_len, _)) = self.dir.insert(name.to_string(), (off, len, xsum)) {
self.free.push((old_off, old_len));
}
self.tail = off + len;
self.staged = true;
}
pub fn commit(&mut self) -> Result<u64> {
if !self.staged {
return Ok(self.seq);
}
let payload = encode_directory(&self.dir, &self.free);
let (dir_codec, stored) = crate::fold::codec::encode(&payload, None, 3)?;
if stored.len() as u64 > u64::from(MAX_DIR_STORED) {
bail!("container directory is {} bytes, over the ceiling", stored.len());
}
let dir_off = self.tail;
crate::vfs::write_all_at(&self.f, &self.path, &stored, dir_off)?;
let tail = dir_off + stored.len() as u64;
crate::vfs::sync_file(&self.f, &self.path)?;
let sb = Superblock {
seq: self.seq + 1,
dir_off,
dir_stored: stored.len() as u32,
dir_raw: payload.len() as u32,
n_entries: self.dir.len() as u32,
dir_xsum: crc32fast::hash(&stored),
tail,
dir_codec,
};
let next_slot = 1 - self.slot;
crate::vfs::write_all_at(
&self.f,
&self.path,
&sb.encode(),
u64::from(next_slot) * SLOT_LEN,
)?;
crate::vfs::sync_file(&self.f, &self.path)?;
self.seq = sb.seq;
self.tail = tail;
self.slot = next_slot;
self.staged = false;
Ok(self.seq)
}
pub fn verify(&self) -> Result<usize> {
let mut buf = vec![0u8; 1 << 20];
for (name, &(off, len, want)) in &self.dir {
let mut hasher = crc32fast::Hasher::new();
let mut at = 0u64;
while at < len {
let take = std::cmp::min(buf.len() as u64, len - at) as usize;
crate::sys::read_exact_at(&self.f, &mut buf[..take], off + at)?;
hasher.update(&buf[..take]);
at += take as u64;
}
let got = hasher.finalize();
if got != want {
bail!("container member {name} fails its checksum: {got:08x} != {want:08x}");
}
}
Ok(self.dir.len())
}
}
#[derive(Clone, Copy, Debug)]
pub struct ReclaimStats {
pub members: usize,
pub bytes_before: u64,
pub bytes_after: u64,
pub reclaimed: u64,
}
pub fn reclaim(path: &Path) -> Result<ReclaimStats> {
let mut hot = path.as_os_str().to_os_string();
hot.push(HOT_SUFFIX);
if Path::new(&hot).exists() {
bail!(
"{} has a writer's working directory beside it; settle or close that writer first",
path.display()
);
}
let source = Container::open(path)?;
let bytes_before = std::fs::metadata(path)?.len();
if source.free_bytes() == 0 {
return Ok(ReclaimStats {
members: source.len(),
bytes_before,
bytes_after: bytes_before,
reclaimed: 0,
});
}
let staging = path.with_extension("reclaiming");
let _ = crate::vfs::unlink(&staging);
let mut fresh = Container::create(&staging)?;
for name in source.names().map(String::from).collect::<Vec<_>>() {
let extent = source
.extent(&name)
.ok_or_else(|| anyhow::anyhow!("container lost member {name} mid-reclaim"))?;
let len = crate::readat::ReadAt::len(&extent)?;
fresh.put_stream(&name, len, |at, into| {
crate::readat::ReadAt::read_exact_at(&extent, into, at)
})?;
}
let members = fresh.len();
fresh.commit()?;
fresh.verify()?;
drop(fresh);
let bytes_after = std::fs::metadata(&staging)?.len();
crate::vfs::rename(&staging, path)?;
if let Some(parent) = path.parent() {
let _ = crate::vfs::sync_dir(parent);
}
Ok(ReclaimStats {
members,
bytes_before,
bytes_after,
reclaimed: bytes_before.saturating_sub(bytes_after),
})
}
fn validate_name(name: &str) -> Result<()> {
if name.is_empty() {
bail!("container member name is empty");
}
if name.len() as u64 > MAX_NAME {
bail!("container member name is {} bytes, over the ceiling", name.len());
}
if name.contains('\\') {
bail!("container member name contains a backslash: {name}");
}
let p = Path::new(name);
if p.components().any(|c| !matches!(c, Component::Normal(_))) {
bail!("container member name is not a relative path of normal components: {name}");
}
Ok(())
}
fn encode_directory(dir: &BTreeMap<String, Entry>, free: &[(u64, u64)]) -> Vec<u8> {
let mut out = Vec::new();
put_varint(&mut out, dir.len() as u64);
for (name, &(off, len, xsum)) in dir {
put_varint(&mut out, name.len() as u64);
out.extend_from_slice(name.as_bytes());
put_varint(&mut out, off);
put_varint(&mut out, len);
out.extend_from_slice(&xsum.to_le_bytes());
}
put_varint(&mut out, free.len() as u64);
for &(off, len) in free {
put_varint(&mut out, off);
put_varint(&mut out, len);
}
out
}
type Directory = (BTreeMap<String, Entry>, Vec<(u64, u64)>);
fn read_directory(f: &Arc<File>, path: &Path, sb: &Superblock) -> Result<Directory> {
let mut dir = BTreeMap::new();
if sb.n_entries == 0 && sb.dir_stored == 0 {
return Ok((dir, Vec::new()));
}
if sb.dir_stored > MAX_DIR_STORED || sb.dir_raw > MAX_DIR_RAW || sb.n_entries > MAX_MEMBERS {
bail!("container {} declares a directory over the admission ceilings", path.display());
}
if sb.dir_off < REGION_START || sb.dir_off + u64::from(sb.dir_stored) > sb.tail {
bail!("container {} directory lies outside its committed region", path.display());
}
let mut stored = Vec::new();
stored.try_reserve_exact(sb.dir_stored as usize)?;
stored.resize(sb.dir_stored as usize, 0);
crate::sys::read_exact_at(f, &mut stored, sb.dir_off)?;
if crc32fast::hash(&stored) != sb.dir_xsum {
bail!("container {} directory fails its checksum", path.display());
}
let payload = crate::fold::codec::decode(sb.dir_codec, &stored, sb.dir_raw, None)?;
let mut at = 0usize;
let n = get_varint(&payload, &mut at)?;
if n != u64::from(sb.n_entries) {
bail!(
"container {} directory holds {n} entries, superblock says {}",
path.display(),
sb.n_entries
);
}
for _ in 0..n {
let name_len = get_varint(&payload, &mut at)? as usize;
let end = at.checked_add(name_len).context("container directory name truncated")?;
let name = std::str::from_utf8(
payload.get(at..end).context("container directory name truncated")?,
)?
.to_string();
at = end;
let off = get_varint(&payload, &mut at)?;
let len = get_varint(&payload, &mut at)?;
let xsum_bytes =
payload.get(at..at + 4).context("container directory checksum truncated")?;
let xsum = u32::from_le_bytes(xsum_bytes.try_into()?);
at += 4;
validate_name(&name)?;
if off < REGION_START || off + len > sb.tail {
bail!("container {} member {name} lies outside its committed region", path.display());
}
if dir.insert(name.clone(), (off, len, xsum)).is_some() {
bail!("container {} names {name} twice", path.display());
}
}
let mut free = Vec::new();
let n_free = get_varint(&payload, &mut at)?;
if n_free > u64::from(MAX_MEMBERS) {
bail!("container {} declares {n_free} free extents, over the ceiling", path.display());
}
for _ in 0..n_free {
let off = get_varint(&payload, &mut at)?;
let len = get_varint(&payload, &mut at)?;
free.push((off, len));
}
Ok((dir, free))
}