mod sys;
use std::ffi::{CStr, CString};
use std::os::fd::{AsRawFd, OwnedFd, RawFd};
use std::path::Path;
use std::sync::Mutex;
use std::sync::atomic::{AtomicU64, Ordering};
use std::time::Duration;
use rayon::prelude::*;
use crate::size::{Links, Measured};
use sys::Kind;
#[cfg(target_vendor = "apple")]
use sys::USER_IMMUTABLE;
const FANOUT_DEPTH: u32 = 10;
const DIRECTORY_BITS: u32 = 0o700;
const UNLINK_BATCH: usize = 64;
const PARALLEL_FILES: usize = 256;
const RESWEEP_BACKOFF: [Duration; 3] = [
Duration::from_millis(10),
Duration::from_millis(50),
Duration::from_millis(250),
];
const EXHAUSTED_BACKOFF: [Duration; 4] = [
Duration::from_millis(1),
Duration::from_millis(5),
Duration::from_millis(25),
Duration::from_millis(100),
];
fn open(parent: RawFd, name: &CStr) -> std::io::Result<OwnedFd> {
let mut waits = EXHAUSTED_BACKOFF.iter();
loop {
match sys::open_dir_at(parent, name) {
Err(error) if matches!(error.raw_os_error(), Some(libc::EMFILE | libc::ENFILE)) => {
let Some(wait) = waits.next() else { return Err(error) };
std::thread::sleep(*wait);
}
result => return result,
}
}
}
pub(crate) fn measure_below(path: &Path) -> Measured {
let Ok(fd) = sys::open_dir(path) else {
return Measured {
bytes: 0,
unreadable: 1,
};
};
let Ok(own) = sys::stat_fd(fd.as_raw_fd()) else {
return Measured {
bytes: 0,
unreadable: 1,
};
};
measure_open(&fd, own.dev, FANOUT_DEPTH, &Links::default())
}
fn tally(fd: &OwnedFd, dev: u64, seen: &Links) -> (Measured, Vec<CString>) {
let Ok(listing) = sys::list(fd) else {
return (
Measured {
bytes: 0,
unreadable: 1,
},
Vec::new(),
);
};
let mut total = Measured {
bytes: 0,
unreadable: listing.unreadable,
};
let mut subdirectories = Vec::new();
for entry in listing.entries {
if !seen.counted_inode(entry.dev, entry.ino, entry.nlink) {
total.bytes += entry.bytes;
}
if entry.kind == Kind::Dir && !entry.mount_point && entry.dev == dev {
subdirectories.push(entry.name);
}
}
(total, subdirectories)
}
fn measure_open(fd: &OwnedFd, dev: u64, fanout: u32, seen: &Links) -> Measured {
let (total, subdirectories) = tally(fd, dev, seen);
if fanout == 0 {
return total + measure_serially(fd, subdirectories, dev, seen);
}
total
+ subdirectories
.par_iter()
.map(|name| match open(fd.as_raw_fd(), name) {
Ok(child) => measure_open(&child, dev, fanout - 1, seen),
Err(error) if error.kind() == std::io::ErrorKind::NotFound => Measured::default(),
Err(_) => Measured {
bytes: 0,
unreadable: 1,
},
})
.reduce(Measured::default, |left, right| left + right)
}
fn measure_serially(fd: &OwnedFd, names: Vec<CString>, dev: u64, seen: &Links) -> Measured {
let mut total = Measured::default();
let mut stack: Vec<(OwnedFd, Vec<CString>)> = Vec::new();
let mut first = names;
loop {
let (parent, next) = if let Some((dir, pending)) = stack.last_mut() {
let Some(next) = pending.pop() else {
stack.pop();
continue;
};
(dir.as_raw_fd(), next)
} else {
let Some(next) = first.pop() else { return total };
(fd.as_raw_fd(), next)
};
match open(parent, &next) {
Ok(child) => {
let (measured, subdirectories) = tally(&child, dev, seen);
total += measured;
stack.push((child, subdirectories));
}
Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
Err(_) => total.unreadable += 1,
}
}
}
#[derive(Debug, Default)]
pub(crate) struct Removed {
pub(crate) freed: u64,
pub(crate) error: Option<std::io::Error>,
}
pub(crate) fn remove_dir(path: &Path, repair: bool) -> Removed {
let (Some(parent), Some(name)) = (path.parent(), path.file_name()) else {
return Removed {
freed: 0,
error: Some(std::io::Error::from(std::io::ErrorKind::InvalidInput)),
};
};
let result = (|| {
use std::os::unix::ffi::OsStrExt;
let parent = sys::open_dir(parent)?;
let name = CString::new(name.as_bytes())?;
let own = sys::stat_at(parent.as_raw_fd(), &name)?;
if own.kind != Kind::Dir {
return Err(std::io::Error::from(std::io::ErrorKind::NotADirectory));
}
let remover = Remover {
repair,
dev: own.dev,
seen: Links::default(),
freed: AtomicU64::new(0),
error: Mutex::new(None),
};
let root = Sub {
name,
bytes: own.bytes,
flags: own.flags,
};
remover.remove(parent.as_raw_fd(), root, false, FANOUT_DEPTH);
Ok(remover.finish())
})();
result.unwrap_or_else(|error| Removed {
freed: 0,
error: Some(error),
})
}
#[derive(Debug)]
struct Sub {
name: CString,
bytes: u64,
flags: u32,
}
struct Frame {
fd: OwnedFd,
sub: Sub,
pending: Vec<Sub>,
blocked: bool,
}
struct Remover {
repair: bool,
dev: u64,
seen: Links,
freed: AtomicU64,
error: Mutex<Option<std::io::Error>>,
}
fn denied(error: &std::io::Error) -> bool {
matches!(error.raw_os_error(), Some(libc::EACCES | libc::EPERM))
}
impl Remover {
fn finish(self) -> Removed {
Removed {
freed: self.freed.into_inner(),
error: self
.error
.into_inner()
.unwrap_or_else(std::sync::PoisonError::into_inner),
}
}
fn fail(&self, error: std::io::Error) {
if let Ok(mut slot) = self.error.lock()
&& slot.is_none()
{
*slot = Some(error);
}
}
fn counted(&self, dev: u64, ino: u64, nlink: u64, bytes: u64) -> u64 {
if self.seen.counted_inode(dev, ino, nlink) {
0
} else {
bytes
}
}
fn add_freed(&self, bytes: u64) {
if bytes > 0 {
self.freed.fetch_add(bytes, Ordering::Relaxed);
crate::delete::note_freed(bytes);
}
}
fn repair_dir(fd: RawFd) {
if let Ok(own) = sys::stat_fd(fd) {
sys::add_mode_fd(fd, own.mode, DIRECTORY_BITS);
sys::clear_immutable_fd(fd, own.flags);
}
}
fn remove(&self, parent: RawFd, sub: Sub, parent_repairable: bool, fanout: u32) {
let mut prefix: Vec<Frame> = Vec::new();
let mut next = Some(sub);
while let Some(sub) = next.take() {
let current_parent = prefix.last().map_or(parent, |frame| frame.fd.as_raw_fd());
let Some(mut frame) = self.open_and_empty(current_parent, sub) else {
break;
};
if fanout > 0 && frame.pending.len() == 1 {
next = frame.pending.pop();
prefix.push(frame);
continue;
}
self.remove_branch(current_parent, frame, !prefix.is_empty() || parent_repairable, fanout);
break;
}
while let Some(Frame { fd, sub, blocked, .. }) = prefix.pop() {
drop(fd);
let current_parent = prefix.last().map_or(parent, |frame| frame.fd.as_raw_fd());
self.remove_empty(current_parent, &sub, !prefix.is_empty() || parent_repairable, blocked);
}
}
fn remove_branch(&self, parent: RawFd, frame: Frame, parent_repairable: bool, fanout: u32) {
let Frame {
fd,
sub,
pending,
blocked,
} = frame;
if fanout == 0 {
self.remove_serially(&fd, pending);
} else {
pending
.into_par_iter()
.for_each(|child| self.remove(fd.as_raw_fd(), child, true, fanout - 1));
}
drop(fd);
self.remove_empty(parent, &sub, parent_repairable, blocked);
}
fn remove_serially(&self, fd: &OwnedFd, subdirectories: Vec<Sub>) {
let mut first = subdirectories;
let mut stack: Vec<Frame> = Vec::new();
loop {
let next = match stack.last_mut() {
Some(frame) => frame.pending.pop().map(|next| (frame.fd.as_raw_fd(), next)),
None => match first.pop() {
Some(next) => Some((fd.as_raw_fd(), next)),
None => return,
},
};
if let Some((parent, sub)) = next {
if let Some(frame) = self.open_and_empty(parent, sub) {
stack.push(frame);
}
continue;
}
let Some(Frame {
fd: done, sub, blocked, ..
}) = stack.pop()
else {
return;
};
drop(done);
let parent = stack.last().map_or(fd.as_raw_fd(), |frame| frame.fd.as_raw_fd());
self.remove_empty(parent, &sub, true, blocked);
}
}
fn open_and_empty(&self, parent: RawFd, sub: Sub) -> Option<Frame> {
let fd = match open(parent, &sub.name) {
Ok(fd) => fd,
Err(error) if error.kind() == std::io::ErrorKind::NotFound => return None,
Err(error) if self.repair && denied(&error) => {
if let Ok(own) = sys::stat_at(parent, &sub.name)
&& own.kind == Kind::Dir
{
sys::add_mode_at(parent, &sub.name, own.mode, DIRECTORY_BITS);
}
match open(parent, &sub.name) {
Ok(fd) => fd,
Err(error) => {
self.fail(error);
return None;
}
}
}
Err(error) => {
self.fail(error);
return None;
}
};
let listing = match sys::list(&fd) {
Ok(listing) => listing,
Err(error) => {
self.fail(error);
return None;
}
};
if listing.unreadable > 0 {
self.fail(std::io::Error::other(format!(
"{} entries could not be read",
listing.unreadable
)));
}
let mut pending = Vec::new();
let mut files = Vec::new();
let mut blocked = false;
for entry in listing.entries {
if entry.kind == Kind::Dir {
if entry.mount_point || entry.dev != self.dev {
self.fail(std::io::Error::other(format!(
"{} is a mount point; voom does not remove across filesystems",
entry.name.to_string_lossy()
)));
blocked = true;
continue;
}
pending.push(Sub {
name: entry.name,
bytes: entry.bytes,
flags: entry.flags,
});
continue;
}
files.push(entry);
}
self.unlink_files(&fd, &files);
Some(Frame {
fd,
sub,
pending,
blocked,
})
}
fn unlink_files(&self, fd: &OwnedFd, files: &[sys::Entry]) {
let unlink_batch = |batch: &[sys::Entry]| {
let mut repaired = false;
let mut freed = 0;
for entry in batch {
match self.unlink(fd, entry, &mut repaired) {
Ok(()) => freed += self.counted(entry.dev, entry.ino, entry.nlink, entry.bytes),
Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
Err(error) => self.fail(error),
}
}
self.add_freed(freed);
};
if cfg!(target_vendor = "apple") && files.len() < PARALLEL_FILES {
unlink_batch(files);
} else {
files.par_chunks(UNLINK_BATCH).for_each(unlink_batch);
}
}
fn unlink(&self, dir: &OwnedFd, entry: &sys::Entry, repaired: &mut bool) -> std::io::Result<()> {
let error = match sys::unlink_at(dir.as_raw_fd(), &entry.name, false) {
Err(error) if self.repair && denied(&error) => error,
result => return result,
};
if !*repaired {
*repaired = true;
Self::repair_dir(dir.as_raw_fd());
match sys::unlink_at(dir.as_raw_fd(), &entry.name, false) {
Err(error) if denied(&error) => {}
result => return result,
}
}
#[cfg(target_vendor = "apple")]
if entry.flags & USER_IMMUTABLE != 0 && entry.nlink <= 1 {
sys::clear_immutable_at(dir.as_raw_fd(), &entry.name, entry.flags);
return sys::unlink_at(dir.as_raw_fd(), &entry.name, false);
}
Err(error)
}
fn remove_empty(&self, parent: RawFd, sub: &Sub, parent_repairable: bool, mut blocked: bool) {
let mut result = self.unlink_empty(parent, sub, parent_repairable);
for wait in RESWEEP_BACKOFF {
if blocked || !matches!(&result, Err(error) if error.kind() == std::io::ErrorKind::DirectoryNotEmpty) {
break;
}
std::thread::sleep(wait);
let again = Sub {
name: sub.name.clone(),
bytes: sub.bytes,
flags: sub.flags,
};
if let Some(Frame {
fd,
pending,
blocked: still,
..
}) = self.open_and_empty(parent, again)
{
blocked = still;
self.remove_serially(&fd, pending);
}
result = self.unlink_empty(parent, sub, parent_repairable);
}
match result {
Ok(()) => self.add_freed(sub.bytes),
Err(error) if error.kind() == std::io::ErrorKind::NotFound => {}
Err(error) => self.fail(error),
}
}
fn unlink_empty(&self, parent: RawFd, sub: &Sub, parent_repairable: bool) -> std::io::Result<()> {
match sys::unlink_at(parent, &sub.name, true) {
Err(error) if self.repair && denied(&error) => {
#[cfg(target_vendor = "apple")]
if sub.flags & USER_IMMUTABLE != 0
&& let Ok(fd) = open(parent, &sub.name)
{
sys::clear_immutable_fd(fd.as_raw_fd(), sub.flags);
}
if parent_repairable {
Self::repair_dir(parent);
}
sys::unlink_at(parent, &sub.name, true)
}
result => result,
}
}
}
#[cfg(test)]
mod traversal_tests;
#[cfg(test)]
mod tests {
use std::os::unix::fs::PermissionsExt;
use super::*;
use crate::testing::tree;
fn std_measure(path: &Path) -> u64 {
use std::os::unix::fs::MetadataExt;
let mut total = 0;
let mut seen = std::collections::HashSet::new();
let mut stack = vec![path.to_path_buf()];
while let Some(dir) = stack.pop() {
for entry in std::fs::read_dir(&dir).unwrap().flatten() {
let metadata = entry.metadata().unwrap();
if metadata.nlink() > 1 && !metadata.is_dir() && !seen.insert(metadata.ino()) {
continue;
}
total += metadata.blocks() * 512;
if metadata.is_dir() {
stack.push(entry.path());
}
}
}
total
}
fn deep(root: &Path, levels: usize) {
let mut path = root.to_path_buf();
for _ in 0..levels {
path.push("d");
}
std::fs::create_dir_all(&path).unwrap();
std::fs::write(path.join("leaf"), vec![1u8; 9000]).unwrap();
}
#[test]
fn should_measure_exactly_what_a_std_walk_measures() {
let root = tree(&["a/b/c.txt", "a/d.txt", "e/f/g/h.txt", "i.txt"]);
std::fs::write(root.path().join("a/big.bin"), vec![3u8; 1_000_000]).unwrap();
std::fs::hard_link(root.path().join("a/big.bin"), root.path().join("e/again.bin")).unwrap();
std::os::unix::fs::symlink(root.path().join("a"), root.path().join("e/link")).unwrap();
deep(root.path(), 40);
let measured = measure_below(root.path());
assert_eq!(measured.bytes, std_measure(root.path()));
assert_eq!(measured.unreadable, 0);
}
#[test]
fn should_count_a_directory_it_cannot_open_as_unreadable() {
let root = tree(&["locked/inside.txt", "open.txt"]);
let locked = root.path().join("locked");
std::fs::set_permissions(&locked, std::fs::Permissions::from_mode(0o000)).unwrap();
let measured = measure_below(root.path());
std::fs::set_permissions(&locked, std::fs::Permissions::from_mode(0o755)).unwrap();
assert_eq!(measured.unreadable, 1);
}
#[test]
fn should_remove_a_tree_and_count_what_it_freed() {
let root = tree(&["artifact/a/b/c.txt", "artifact/d.txt", "keep.txt"]);
let artifact = root.path().join("artifact");
std::fs::write(artifact.join("a/big.bin"), vec![3u8; 500_000]).unwrap();
deep(&artifact, 30);
let expected = std_measure(&artifact) + {
use std::os::unix::fs::MetadataExt;
std::fs::symlink_metadata(&artifact).unwrap().blocks() * 512
};
let removed = remove_dir(&artifact, false);
assert!(removed.error.is_none(), "{:?}", removed.error);
assert!(!artifact.exists());
assert!(root.path().join("keep.txt").exists());
assert_eq!(removed.freed, expected);
}
#[test]
fn should_remove_flat_batches_and_count_hard_links_once() {
let root = tree(&["artifact/", "source/precious"]);
let artifact = root.path().join("artifact");
for index in 0..(UNLINK_BATCH * 8) {
std::fs::write(artifact.join(index.to_string()), [3u8; 4096]).unwrap();
}
std::fs::hard_link(artifact.join("0"), artifact.join("again")).unwrap();
std::os::unix::fs::symlink(root.path().join("source"), artifact.join("link")).unwrap();
let expected = crate::size::measure(&artifact);
let removed = remove_dir(&artifact, false);
assert!(removed.error.is_none(), "flat removal failed: {:?}", removed.error);
assert_eq!(removed.freed, expected, "batches must count a hard-linked inode once");
assert!(!artifact.exists(), "all flat batches must be removed");
assert!(root.path().join("source/precious").exists(), "symlink target survives");
}
#[test]
fn should_remove_deeper_than_the_fanout_bound() {
let root = tree(&["keep.txt"]);
let artifact = root.path().join("artifact");
deep(&artifact, 300);
let removed = remove_dir(&artifact, false);
assert!(removed.error.is_none(), "{:?}", removed.error);
assert!(!artifact.exists());
}
#[test]
fn should_unlink_a_symlink_and_leave_its_target() {
let root = tree(&["target/precious.txt", "artifact/x.txt"]);
std::os::unix::fs::symlink(root.path().join("target"), root.path().join("artifact/link")).unwrap();
let removed = remove_dir(&root.path().join("artifact"), false);
assert!(removed.error.is_none(), "{:?}", removed.error);
assert!(root.path().join("target/precious.txt").exists());
}
#[test]
fn should_leave_a_read_only_directory_without_repair_and_take_everything_else() {
let root = tree(&["artifact/held/file.txt", "artifact/free/file.txt"]);
let held = root.path().join("artifact/held");
std::fs::set_permissions(&held, std::fs::Permissions::from_mode(0o555)).unwrap();
let removed = remove_dir(&root.path().join("artifact"), false);
let survived = held.join("file.txt").exists();
std::fs::set_permissions(&held, std::fs::Permissions::from_mode(0o755)).unwrap();
assert!(removed.error.is_some());
assert!(survived);
assert!(!root.path().join("artifact/free").exists());
}
#[test]
fn should_repair_a_read_only_directory_when_asked() {
let root = tree(&["artifact/held/deeper/file.txt", "artifact/locked/file.txt"]);
let artifact = root.path().join("artifact");
std::fs::set_permissions(artifact.join("held/deeper"), std::fs::Permissions::from_mode(0o555)).unwrap();
std::fs::set_permissions(artifact.join("held"), std::fs::Permissions::from_mode(0o555)).unwrap();
std::fs::set_permissions(artifact.join("locked"), std::fs::Permissions::from_mode(0o000)).unwrap();
let removed = remove_dir(&artifact, true);
assert!(removed.error.is_none(), "{:?}", removed.error);
assert!(!artifact.exists());
}
#[test]
fn should_never_repair_the_artifacts_parent() {
let root = tree(&["parent/artifact/file.txt"]);
let parent = root.path().join("parent");
std::fs::set_permissions(&parent, std::fs::Permissions::from_mode(0o555)).unwrap();
let removed = remove_dir(&parent.join("artifact"), true);
let mode = std::fs::metadata(&parent).unwrap().permissions().mode();
std::fs::set_permissions(&parent, std::fs::Permissions::from_mode(0o755)).unwrap();
assert!(removed.error.is_some());
assert_eq!(mode & 0o777, 0o555);
}
#[test]
fn should_refuse_a_path_that_is_not_a_directory() {
let root = tree(&["file.txt"]);
let removed = remove_dir(&root.path().join("file.txt"), false);
assert!(removed.error.is_some());
assert!(root.path().join("file.txt").exists());
}
#[test]
fn should_take_files_written_into_a_directory_while_it_is_being_removed() {
let root = tree(&["keep.txt"]);
let artifact = root.path().join("artifact");
for index in 0..40 {
std::fs::create_dir_all(artifact.join(format!("d{index}"))).unwrap();
std::fs::write(artifact.join(format!("d{index}/f")), b"x").unwrap();
}
let writer_dir = artifact.clone();
let writer = std::thread::spawn(move || {
for round in 0..300 {
let _ = std::fs::write(writer_dir.join(format!("d{}/late{round}", round % 40)), b"late");
std::thread::sleep(Duration::from_micros(300));
}
});
let removed = remove_dir(&artifact, false);
writer.join().unwrap();
assert!(removed.error.is_none(), "{:?}", removed.error);
assert!(!artifact.exists(), "nothing the writer added survived");
}
}