use std::collections::BTreeMap;
use std::fs::{File, OpenOptions};
use std::io::{Read, Seek, SeekFrom, Write};
use std::path::{Path, PathBuf};
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex};
#[cfg(unix)]
use std::os::unix::fs::MetadataExt;
use crate::error::{Error, Neo4jStoreError, Result};
const DIRECTORY: &str = ".littlegraph-transactions";
const MAGIC: &[u8; 8] = b"LGSPILL1";
const ENTRY_MAGIC: &[u8; 4] = b"LGSE";
const HEADER_LEN: usize = 29;
static NEXT_ID: AtomicU64 = AtomicU64::new(1);
pub(super) trait SpillValue: Clone {
fn encoded_len(&self) -> usize;
fn encode(&self) -> Vec<u8>;
fn decode(bytes: Vec<u8>) -> Result<Self>;
}
impl<const N: usize> SpillValue for [u8; N] {
fn encoded_len(&self) -> usize {
N
}
fn encode(&self) -> Vec<u8> {
self.to_vec()
}
fn decode(bytes: Vec<u8>) -> Result<Self> {
bytes.try_into().map_err(|bytes: Vec<u8>| {
Error::Validation(format!(
"workspace spill record has {} bytes, expected {N}",
bytes.len()
))
})
}
}
impl SpillValue for Vec<u8> {
fn encoded_len(&self) -> usize {
self.len()
}
fn encode(&self) -> Vec<u8> {
self.clone()
}
fn decode(bytes: Vec<u8>) -> Result<Self> {
Ok(bytes)
}
}
#[derive(Debug)]
struct SpillFileInner {
path: PathBuf,
file: Mutex<File>,
max_bytes: Option<u64>,
}
impl Drop for SpillFileInner {
fn drop(&mut self) {
if let Ok(file) = self.file.get_mut() {
if path_matches_open_file(file, &self.path).unwrap_or(false) {
let _ = std::fs::remove_file(&self.path);
}
}
}
}
#[derive(Clone, Debug)]
pub(super) struct SpillFile(Arc<SpillFileInner>);
impl SpillFile {
pub(super) fn create(
database: &Path,
max_bytes: Option<u64>,
transaction_id: Option<u64>,
) -> Result<Self> {
if max_bytes.is_some_and(|limit| limit < MAGIC.len() as u64) {
return Err(resource_limit());
}
let directory = database.join(DIRECTORY);
std::fs::create_dir_all(&directory).map_err(|source| Neo4jStoreError::Write {
path: directory.clone(),
source,
})?;
for _ in 0..64 {
let id = transaction_id.unwrap_or_else(|| NEXT_ID.fetch_add(1, Ordering::Relaxed));
let path = directory.join(format!("workspace-{}-{id}.spill", std::process::id()));
match OpenOptions::new()
.read(true)
.write(true)
.create_new(true)
.open(&path)
{
Ok(mut file) => {
file.write_all(MAGIC)
.and_then(|()| file.sync_data())
.map_err(|source| Neo4jStoreError::Write {
path: path.clone(),
source,
})?;
return Ok(Self(Arc::new(SpillFileInner {
path,
file: Mutex::new(file),
max_bytes,
})));
}
Err(error) if error.kind() == std::io::ErrorKind::AlreadyExists => {}
Err(source) => return Err(Neo4jStoreError::Write { path, source }.into()),
}
}
Err(Error::Validation(
"could not allocate workspace spill file".to_owned(),
))
}
fn append(&self, kind: u8, key: u64, payload: &[u8]) -> Result<Location> {
let mut file = self
.0
.file
.lock()
.map_err(|_| Error::Validation("workspace spill lock poisoned".to_owned()))?;
let offset = file
.seek(SeekFrom::End(0))
.map_err(|source| Neo4jStoreError::Write {
path: self.0.path.clone(),
source,
})?;
let len = u64::try_from(payload.len()).map_err(|_| resource_limit())?;
let end = offset
.checked_add(HEADER_LEN as u64)
.and_then(|n| n.checked_add(len))
.ok_or_else(resource_limit)?;
if self.0.max_bytes.is_some_and(|limit| end > limit) {
return Err(resource_limit());
}
let checksum = checksum(kind, key, payload);
file.write_all(ENTRY_MAGIC)
.and_then(|()| file.write_all(&[kind]))
.and_then(|()| file.write_all(&key.to_le_bytes()))
.and_then(|()| file.write_all(&len.to_le_bytes()))
.and_then(|()| file.write_all(&checksum.to_le_bytes()))
.and_then(|()| file.write_all(payload))
.map_err(|source| Neo4jStoreError::Write {
path: self.0.path.clone(),
source,
})?;
Ok(Location { offset, len })
}
fn read(&self, kind: u8, key: u64, location: Location) -> Result<Vec<u8>> {
let mut file = self
.0
.file
.lock()
.map_err(|_| Error::Validation("workspace spill lock poisoned".to_owned()))?;
file.seek(SeekFrom::Start(location.offset))
.map_err(|source| Neo4jStoreError::Read {
path: self.0.path.clone(),
source,
})?;
let mut header = [0; HEADER_LEN];
file.read_exact(&mut header)
.map_err(|source| Neo4jStoreError::Read {
path: self.0.path.clone(),
source,
})?;
let stored_key = u64::from_le_bytes(header[5..13].try_into().unwrap());
let len = u64::from_le_bytes(header[13..21].try_into().unwrap());
let expected = u64::from_le_bytes(header[21..29].try_into().unwrap());
if &header[..4] != ENTRY_MAGIC
|| header[4] != kind
|| stored_key != key
|| len != location.len
{
return Err(Error::Validation(
"invalid workspace spill entry".to_owned(),
));
}
let mut payload = vec![0; usize::try_from(len).map_err(|_| resource_limit())?];
file.read_exact(&mut payload)
.map_err(|source| Neo4jStoreError::Read {
path: self.0.path.clone(),
source,
})?;
if checksum(kind, key, &payload) != expected {
return Err(Error::Validation(
"workspace spill checksum mismatch".to_owned(),
));
}
Ok(payload)
}
}
#[derive(Clone, Copy, Debug)]
struct Location {
offset: u64,
len: u64,
}
#[derive(Clone, Debug)]
pub(super) struct SpillMap<V> {
kind: u8,
file: Option<SpillFile>,
hot: BTreeMap<u64, V>,
cold: BTreeMap<u64, Location>,
}
impl<V: SpillValue> SpillMap<V> {
pub(super) fn new(kind: u8, file: Option<SpillFile>) -> Self {
Self {
kind,
file,
hot: BTreeMap::new(),
cold: BTreeMap::new(),
}
}
pub(super) fn insert(&mut self, key: u64, value: V) {
self.cold.remove(&key);
self.hot.insert(key, value);
}
pub(super) fn extend(&mut self, values: impl IntoIterator<Item = (u64, V)>) {
for (key, value) in values {
self.insert(key, value);
}
}
pub(super) fn get(&self, key: &u64) -> Result<Option<V>> {
if let Some(value) = self.hot.get(key) {
return Ok(Some(value.clone()));
}
self.cold
.get(key)
.copied()
.map(|location| self.read_value(*key, location))
.transpose()
}
pub(super) fn get_mut(&mut self, key: &u64) -> Result<Option<&mut V>> {
if !self.hot.contains_key(key) {
if let Some(location) = self.cold.remove(key) {
let value = self.read_value(*key, location)?;
self.hot.insert(*key, value);
}
}
Ok(self.hot.get_mut(key))
}
pub(super) fn is_empty(&self) -> bool {
self.hot.is_empty() && self.cold.is_empty()
}
pub(super) fn len(&self) -> usize {
self.hot.len() + self.cold.len()
}
pub(super) fn keys(&self) -> impl Iterator<Item = u64> + '_ {
self.hot.keys().chain(self.cold.keys()).copied()
}
pub(super) fn hot_bytes(&self) -> Result<usize> {
self.hot.values().try_fold(0usize, |n, v| {
n.checked_add(v.encoded_len()).ok_or_else(resource_limit)
})
}
pub(super) fn total_bytes(&self) -> Result<usize> {
self.cold.values().try_fold(self.hot_bytes()?, |n, v| {
n.checked_add(usize::try_from(v.len).map_err(|_| resource_limit())?)
.ok_or_else(resource_limit)
})
}
pub(super) fn spill(&mut self) -> Result<()> {
let Some(file) = self.file.clone() else {
return Ok(());
};
let mut pending = std::mem::take(&mut self.hot).into_iter();
while let Some((key, value)) = pending.next() {
match file.append(self.kind, key, &value.encode()) {
Ok(location) => {
self.cold.insert(key, location);
}
Err(error) => {
self.hot.insert(key, value);
self.hot.extend(pending);
return Err(error);
}
}
}
Ok(())
}
#[cfg(test)]
pub(super) fn try_for_each(&self, mut visitor: impl FnMut(u64, V) -> Result<()>) -> Result<()> {
let mut hot = self.hot.iter().peekable();
let mut cold = self.cold.iter().peekable();
loop {
let hot_key = hot.peek().map(|(key, _)| **key);
let cold_key = cold.peek().map(|(key, _)| **key);
match (hot_key, cold_key) {
(Some(hot_key), Some(cold_key)) if hot_key <= cold_key => {
let (&key, value) = hot.next().unwrap();
visitor(key, value.clone())?;
if hot_key == cold_key {
cold.next();
}
}
(Some(_), Some(_)) | (None, Some(_)) => {
let (&key, &location) = cold.next().unwrap();
visitor(key, self.read_value(key, location)?)?;
}
(Some(_), None) => {
let (&key, value) = hot.next().unwrap();
visitor(key, value.clone())?;
}
(None, None) => return Ok(()),
}
}
}
pub(super) fn drain_try_for_each(
&mut self,
mut visitor: impl FnMut(u64, V) -> Result<()>,
) -> Result<()> {
let mut hot = std::mem::take(&mut self.hot).into_iter().peekable();
let mut cold = std::mem::take(&mut self.cold).into_iter().peekable();
loop {
let hot_key = hot.peek().map(|(key, _)| *key);
let cold_key = cold.peek().map(|(key, _)| *key);
match (hot_key, cold_key) {
(Some(hot_key), Some(cold_key)) if hot_key <= cold_key => {
let (key, value) = hot.next().unwrap();
visitor(key, value)?;
if hot_key == cold_key {
cold.next();
}
}
(Some(_), Some(_)) | (None, Some(_)) => {
let (key, location) = cold.next().unwrap();
visitor(key, self.read_value(key, location)?)?;
}
(Some(_), None) => {
let (key, value) = hot.next().unwrap();
visitor(key, value)?;
}
(None, None) => return Ok(()),
}
}
}
fn read_value(&self, key: u64, location: Location) -> Result<V> {
let file = self
.file
.as_ref()
.ok_or_else(|| Error::Validation("workspace spill missing backing file".to_owned()))?;
V::decode(file.read(self.kind, key, location)?)
}
}
pub(super) fn cleanup_stale(database: &Path) -> Result<()> {
let directory = database.join(DIRECTORY);
let entries = match std::fs::read_dir(&directory) {
Ok(entries) => entries,
Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(()),
Err(source) => {
return Err(Neo4jStoreError::Read {
path: directory,
source,
}
.into())
}
};
for entry in entries {
let entry = entry.map_err(|source| Neo4jStoreError::Read {
path: directory.clone(),
source,
})?;
let name = entry.file_name();
let name = name.to_string_lossy();
if !entry
.file_type()
.map_err(|source| Neo4jStoreError::Read {
path: entry.path(),
source,
})?
.is_file()
|| !is_spill_name(&name)
{
continue;
}
let path = entry.path();
let mut file = File::open(&path).map_err(|source| Neo4jStoreError::Read {
path: path.clone(),
source,
})?;
let mut magic = [0; 8];
if file.read_exact(&mut magic).is_ok()
&& &magic == MAGIC
&& path_matches_open_file(&file, &path).map_err(|source| Neo4jStoreError::Read {
path: path.clone(),
source,
})?
{
std::fs::remove_file(&path)
.map_err(|source| Neo4jStoreError::Write { path, source })?;
}
}
Ok(())
}
fn resource_limit() -> Error {
Error::Transaction(crate::TransactionErrorKind::ResourceLimit)
}
#[cfg(unix)]
fn path_matches_open_file(file: &File, path: &Path) -> std::io::Result<bool> {
let opened = file.metadata()?;
let current = std::fs::symlink_metadata(path)?;
Ok(opened.is_file()
&& current.file_type().is_file()
&& opened.dev() == current.dev()
&& opened.ino() == current.ino())
}
#[cfg(not(unix))]
fn path_matches_open_file(file: &File, path: &Path) -> std::io::Result<bool> {
Ok(file.metadata()?.is_file() && std::fs::symlink_metadata(path)?.file_type().is_file())
}
fn is_spill_name(name: &str) -> bool {
let Some(ids) = name
.strip_prefix("workspace-")
.and_then(|name| name.strip_suffix(".spill"))
else {
return false;
};
let Some((process_id, transaction_id)) = ids.split_once('-') else {
return false;
};
!process_id.is_empty()
&& !transaction_id.is_empty()
&& !transaction_id.contains('-')
&& process_id.parse::<u32>().is_ok()
&& transaction_id.parse::<u64>().is_ok()
}
fn checksum(kind: u8, key: u64, payload: &[u8]) -> u64 {
let mut hash = 0xcbf29ce484222325;
for byte in std::iter::once(&kind)
.chain(key.to_le_bytes().iter())
.chain(payload)
{
hash ^= u64::from(*byte);
hash = hash.wrapping_mul(0x100000001b3);
}
hash
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn spill_map_reads_checked_entries_and_removes_its_file() {
let database = tempfile::tempdir().unwrap();
let file = SpillFile::create(database.path(), Some(1024), Some(42)).unwrap();
let path = file.0.path.clone();
let mut map = SpillMap::new(7, Some(file));
map.insert(2, vec![2, 3]);
map.insert(1, vec![1]);
map.spill().unwrap();
assert_eq!(map.get(&1).unwrap(), Some(vec![1]));
let mut entries = Vec::new();
map.try_for_each(|key, value| {
entries.push((key, value));
Ok(())
})
.unwrap();
assert_eq!(entries, vec![(1, vec![1]), (2, vec![2, 3])]);
let mut drained = Vec::new();
map.drain_try_for_each(|key, value| {
drained.push((key, value));
Ok(())
})
.unwrap();
assert_eq!(drained, entries);
assert!(map.is_empty());
drop(map);
assert!(!path.exists());
}
#[test]
fn stale_cleanup_only_removes_regular_spill_files_with_valid_headers() {
let database = tempfile::tempdir().unwrap();
let directory = database.path().join(DIRECTORY);
std::fs::create_dir(&directory).unwrap();
let valid = directory.join("workspace-1-1.spill");
let foreign = directory.join("workspace-1-2.spill");
let malformed = directory.join("workspace-not-an-id.spill");
std::fs::write(&valid, MAGIC).unwrap();
std::fs::write(&foreign, b"not-a-littlegraph-spill").unwrap();
std::fs::write(&malformed, MAGIC).unwrap();
cleanup_stale(database.path()).unwrap();
assert!(!valid.exists());
assert!(foreign.exists());
assert!(malformed.exists());
}
#[test]
fn spill_checksum_rejects_corruption() {
let database = tempfile::tempdir().unwrap();
let file = SpillFile::create(database.path(), Some(1024), Some(43)).unwrap();
let path = file.0.path.clone();
let mut map = SpillMap::new(1, Some(file));
map.insert(7, vec![1, 2, 3]);
map.spill().unwrap();
let mut corrupt = OpenOptions::new().write(true).open(path).unwrap();
corrupt
.seek(SeekFrom::Start((MAGIC.len() + HEADER_LEN) as u64))
.unwrap();
corrupt.write_all(&[9]).unwrap();
assert!(matches!(map.get(&7), Err(Error::Validation(message))
if message.contains("checksum")));
}
#[test]
fn spill_limit_failure_preserves_unwritten_hot_entries() {
let directory = tempfile::tempdir().unwrap();
let spill = SpillFile::create(directory.path(), Some(41), Some(1)).unwrap();
let mut map = SpillMap::new(1, Some(spill));
map.insert(1, [1_u8; 4]);
map.insert(2, [2_u8; 4]);
assert!(matches!(
map.spill(),
Err(Error::Transaction(
crate::TransactionErrorKind::ResourceLimit
))
));
assert_eq!(map.hot_bytes().unwrap(), 4);
assert_eq!(map.total_bytes().unwrap(), 8);
assert_eq!(map.get(&1).unwrap(), Some([1; 4]));
assert_eq!(map.get(&2).unwrap(), Some([2; 4]));
let mut entries = Vec::new();
map.try_for_each(|key, value| {
entries.push((key, value));
Ok(())
})
.unwrap();
assert_eq!(entries, [(1, [1; 4]), (2, [2; 4])]);
}
#[test]
fn spill_limit_smaller_than_header_fails_without_creating_artifacts() {
let database = tempfile::tempdir().unwrap();
assert!(matches!(
SpillFile::create(database.path(), Some(7), Some(1)),
Err(Error::Transaction(
crate::TransactionErrorKind::ResourceLimit
))
));
assert!(!database.path().join(DIRECTORY).exists());
}
#[cfg(unix)]
#[test]
fn dropping_a_spill_does_not_remove_a_replacement_path() {
let database = tempfile::tempdir().unwrap();
let file = SpillFile::create(database.path(), Some(1024), Some(44)).unwrap();
let path = file.0.path.clone();
std::fs::remove_file(&path).unwrap();
std::fs::write(&path, b"replacement").unwrap();
drop(file);
assert_eq!(std::fs::read(&path).unwrap(), b"replacement");
}
}