A treemap for finding and removing what fills your disk, for Omarchy. Rust + GPUI.
Rust
//! What a walk on macOS needs beyond the standard library.
//!
//! `std::fs::read_dir` lists a directory with `readdir`, whose records carry
//! a name and a type, and `DirEntry::metadata` is then an `lstat` of each
//! entry's full path. `getattrlistbulk(2)` returns every entry's size,
//! identity, age and flags for a whole buffer of entries, without the kernel
//! setting up per-file state for each one as a stat must.
#![allow(
unsafe_code,
reason = "getattrlistbulk, which neither std nor rustix wraps; each block \
says why it is sound"
)]
use std::cell::RefCell;
use std::ffi::{OsStr, c_int, c_void};
use std::io;
use std::os::fd::{AsRawFd as _, OwnedFd};
use std::os::unix::ffi::OsStrExt as _;
use std::path::{Path, PathBuf};
use rustix::fs::{AtFlags, FileType, Mode, OFlags};
/// Bytes the kernel fills per call: some hundreds of entries.
const BUFFER_BYTES: usize = 64 * 1024;
// From <sys/attr.h> and <sys/vnode.h>, which the libc crate does not cover.
const ATTR_BIT_MAP_COUNT: u16 = 5;
const ATTR_CMN_NAME: u32 = 0x0000_0001;
const ATTR_CMN_DEVID: u32 = 0x0000_0002;
const ATTR_CMN_OBJTYPE: u32 = 0x0000_0008;
const ATTR_CMN_MODTIME: u32 = 0x0000_0400;
const ATTR_CMN_FLAGS: u32 = 0x0004_0000;
const ATTR_CMN_FILEID: u32 = 0x0200_0000;
const ATTR_CMN_ERROR: u32 = 0x2000_0000;
const ATTR_CMN_RETURNED_ATTRS: u32 = 0x8000_0000;
const ATTR_FILE_LINKCOUNT: u32 = 0x0000_0001;
/// Every fork, which is what `st_blocks` counts: a resource fork is on the
/// disk too.
const ATTR_FILE_ALLOCSIZE: u32 = 0x0000_0004;
/// The data fork alone, which is what `st_size` is.
const ATTR_FILE_DATALENGTH: u32 = 0x0000_0200;
const VREG: u32 = 1;
const VDIR: u32 = 2;
const VLNK: u32 = 5;
/// `SF_DATALESS` from <sys/stat.h>.
const SF_DATALESS: u32 = 0x4000_0000;
const COMMON_ATTRIBUTES: u32 = ATTR_CMN_RETURNED_ATTRS
| ATTR_CMN_NAME
| ATTR_CMN_DEVID
| ATTR_CMN_OBJTYPE
| ATTR_CMN_MODTIME
| ATTR_CMN_FLAGS
| ATTR_CMN_FILEID
| ATTR_CMN_ERROR;
const FILE_ATTRIBUTES: u32 =
ATTR_FILE_LINKCOUNT | ATTR_FILE_ALLOCSIZE | ATTR_FILE_DATALENGTH;
/// What [`Cursor::entry`] reads after the name; a file system may leave
/// any of them out.
const MEASURED: u32 = ATTR_CMN_DEVID
| ATTR_CMN_OBJTYPE
| ATTR_CMN_MODTIME
| ATTR_CMN_FLAGS
| ATTR_CMN_FILEID;
#[repr(C)]
struct AttrList {
bitmapcount: u16,
reserved: u16,
commonattr: u32,
volattr: u32,
dirattr: u32,
fileattr: u32,
forkattr: u32,
}
unsafe extern "C" {
fn getattrlistbulk(
dirfd: c_int,
attr_list: *mut AttrList,
attr_buf: *mut c_void,
attr_buf_size: usize,
options: u64,
) -> c_int;
}
thread_local! {
/// The last finished listing's buffer, for the next one on this thread:
/// a walk lists millions of directories, one at a time per thread.
static SPARE: RefCell<Option<Box<[u64]>>> = const { RefCell::new(None) };
}
/// What an entry is.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Kind {
Directory,
Link,
File,
/// A FIFO, a socket or a device node.
Other,
}
/// One directory entry, with what a measurement needs.
#[derive(Debug)]
pub struct Entry {
name: Box<str>,
/// The name as the file system spells it, only when `name` could not:
/// a name that is not UTF-8 is shown lossy but must still open.
exact: Option<Box<OsStr>>,
kind: Kind,
apparent: u64,
allocated: u64,
modified: i64,
device: u64,
inode: u64,
links: u32,
flags: u32,
}
impl Entry {
/// The entry's path inside `dir`, the directory it was listed from.
pub fn path(&self, dir: &Path) -> PathBuf {
dir.join(self.file_name())
}
pub fn file_name(&self) -> &OsStr {
self.exact
.as_deref()
.unwrap_or_else(|| OsStr::new(&*self.name))
}
/// The name as text; see [`Self::file_name`] for what it may lose.
pub fn name(&self) -> &str {
&self.name
}
/// The name, moved out: the tree keeps it, so nothing copies it. The
/// entry's other accessors keep working; `name`, `file_name` and
/// `path` do not.
pub fn take_name(&mut self) -> Box<str> {
std::mem::take(&mut self.name)
}
pub const fn kind(&self) -> Kind {
self.kind
}
/// `st_size`.
pub const fn apparent(&self) -> u64 {
self.apparent
}
/// `st_blocks * 512`.
pub const fn allocated(&self) -> u64 {
self.allocated
}
/// Last write, in Unix seconds.
pub const fn modified(&self) -> i64 {
self.modified
}
/// `(st_dev, st_ino)`: the same for two names of one file.
pub const fn identity(&self) -> (u64, u64) {
(self.device, self.inode)
}
pub const fn device(&self) -> u64 {
self.device
}
/// Whether the file has more than one name.
pub const fn shared(&self) -> bool {
self.links > 1
}
/// Whether this is a directory iCloud Drive or a File Provider has
/// evicted, which listing would make it fetch.
pub const fn evicted(&self) -> bool {
matches!(self.kind, Kind::Directory) && self.flags & SF_DATALESS != 0
}
fn named(name: &[u8]) -> (Box<str>, Option<Box<OsStr>>) {
match std::str::from_utf8(name) {
Ok(text) => (text.into(), None),
Err(_) => (
String::from_utf8_lossy(name).into(),
Some(OsStr::from_bytes(name).into()),
),
}
}
fn from_stat(name: &[u8], stat: &rustix::fs::Stat) -> Self {
let (name, exact) = Self::named(name);
let kind = match FileType::from_raw_mode(stat.st_mode) {
FileType::Directory => Kind::Directory,
FileType::Symlink => Kind::Link,
FileType::RegularFile => Kind::File,
_ => Kind::Other,
};
Self {
name,
exact,
kind,
apparent: stat.st_size.max(0) as u64,
allocated: (stat.st_blocks.max(0) as u64).saturating_mul(512),
modified: stat.st_mtime,
device: i64::from(stat.st_dev).cast_unsigned(),
inode: stat.st_ino,
links: u32::from(stat.st_nlink),
flags: stat.st_flags,
}
}
}
/// A directory being listed; like `std::fs::ReadDir`, it leaves out `.`
/// and `..`.
#[derive(Debug)]
pub struct ReadDir {
fd: OwnedFd,
/// `u64`s for alignment; the records themselves are 4-byte aligned.
buffer: Option<Box<[u64]>>,
/// Records in the buffer not yet handed out.
remaining: u32,
/// Where the next of them starts.
offset: usize,
done: bool,
}
/// List `dir`, with each entry's size, identity and age. A link at `dir`
/// itself is followed, as `std::fs::read_dir` follows it.
pub fn read_dir(dir: &Path) -> io::Result<ReadDir> {
let fd = rustix::fs::open(
dir,
OFlags::RDONLY | OFlags::DIRECTORY | OFlags::CLOEXEC,
Mode::empty(),
)?;
let buffer = SPARE
.with_borrow_mut(Option::take)
.unwrap_or_else(|| vec![0; BUFFER_BYTES / 8].into_boxed_slice());
Ok(ReadDir {
fd,
buffer: Some(buffer),
remaining: 0,
offset: 0,
done: false,
})
}
impl Drop for ReadDir {
fn drop(&mut self) {
if let Some(buffer) = self.buffer.take() {
SPARE.with_borrow_mut(|spare| *spare = Some(buffer));
}
}
}
impl Iterator for ReadDir {
type Item = io::Result<Entry>;
fn next(&mut self) -> Option<Self::Item> {
if self.remaining == 0 {
if self.done {
return None;
}
match self.fill() {
Ok(0) => {
self.done = true;
return None;
}
Ok(count) => {
self.remaining = count;
self.offset = 0;
}
Err(error) => {
self.done = true;
return Some(Err(error));
}
}
}
self.remaining -= 1;
match self.record() {
Ok((entry, length)) => {
self.offset += length;
Some(entry)
}
Err(error) => {
self.remaining = 0;
self.done = true;
Some(Err(error))
}
}
}
}
impl ReadDir {
/// Ask the kernel for the next buffer of records; how many it wrote.
fn fill(&mut self) -> io::Result<u32> {
let buffer = self.buffer.as_mut().expect("held until drop");
let mut request = AttrList {
bitmapcount: ATTR_BIT_MAP_COUNT,
reserved: 0,
commonattr: COMMON_ATTRIBUTES,
volattr: 0,
dirattr: 0,
fileattr: FILE_ATTRIBUTES,
forkattr: 0,
};
loop {
// SAFETY: the descriptor is an open directory owned by `self`;
// `request` is a valid attrlist for the call's duration; and the
// pointer and length describe `buffer`, which is writable for
// that many bytes and not otherwise borrowed during the call.
let count = unsafe {
getattrlistbulk(
self.fd.as_raw_fd(),
&raw mut request,
buffer.as_mut_ptr().cast(),
BUFFER_BYTES,
0,
)
};
if let Ok(count) = u32::try_from(count) {
return Ok(count);
}
let error = io::Error::last_os_error();
if error.kind() != io::ErrorKind::Interrupted {
return Err(error);
}
}
}
/// The buffer as the bytes the kernel wrote.
fn bytes(&self) -> &[u8] {
let buffer = self.buffer.as_deref().expect("held until drop");
// SAFETY: `[u64]` can be read as `u8`s of eight times its length:
// one allocation, no alignment requirement for `u8`, and every byte
// initialized, since the buffer starts zeroed.
unsafe {
std::slice::from_raw_parts(
buffer.as_ptr().cast::<u8>(),
size_of_val(buffer),
)
}
}
/// The entry at `self.offset` and the record's length. Every length and
/// offset the kernel wrote is checked against the buffer before it is
/// used.
///
/// Layout per getattrlist(2): a `u32` length, the returned
/// `attribute_set_t`, `ATTR_CMN_ERROR` when it is set, then every other
/// attribute in bit order, each packed at 4-byte alignment.
fn record(&self) -> io::Result<(io::Result<Entry>, usize)> {
let bytes = self.bytes();
let length = read_u32(bytes, self.offset)? as usize;
let record = bytes
.get(self.offset..self.offset + length)
.ok_or_else(malformed)?;
let mut cursor = Cursor { record, at: 4 };
let common = cursor.u32()?;
cursor.at += 8;
let file = cursor.u32()?;
cursor.at += 4;
let error = if common & ATTR_CMN_ERROR == 0 {
0
} else {
cursor.u32()?
};
let name = cursor.name()?;
if error != 0 {
let error = io::Error::from_raw_os_error(error.cast_signed());
return Ok((Err(error), length));
}
let entry = if common & MEASURED == MEASURED {
cursor.entry(file, name)?
} else {
None
};
Ok((entry.map_or_else(|| self.stat(name), Ok), length))
}
/// An entry the file system described only in part, read the ordinary
/// way, relative to the directory already open.
fn stat(&self, name: &[u8]) -> io::Result<Entry> {
let stat =
rustix::fs::statat(&self.fd, name, AtFlags::SYMLINK_NOFOLLOW)?;
Ok(Entry::from_stat(name, &stat))
}
}
fn malformed() -> io::Error {
io::Error::other("the kernel returned a malformed record")
}
fn read_u32(bytes: &[u8], at: usize) -> io::Result<u32> {
let field = at
.checked_add(4)
.and_then(|end| bytes.get(at..end))
.ok_or_else(malformed)?;
Ok(u32::from_ne_bytes(
field.try_into().map_err(|_| malformed())?,
))
}
/// Reads a record's attributes in order; reading past its end is a
/// malformed record.
struct Cursor<'a> {
record: &'a [u8],
at: usize,
}
impl<'a> Cursor<'a> {
fn u32(&mut self) -> io::Result<u32> {
let value = read_u32(self.record, self.at)?;
self.at += 4;
Ok(value)
}
fn u64(&mut self) -> io::Result<u64> {
let field = self
.at
.checked_add(8)
.and_then(|end| self.record.get(self.at..end))
.ok_or_else(malformed)?;
self.at += 8;
Ok(u64::from_ne_bytes(
field.try_into().map_err(|_| malformed())?,
))
}
/// An `attrreference_t`: an offset from itself and a length that counts
/// the terminating NUL.
fn name(&mut self) -> io::Result<&'a [u8]> {
let reference = self.at;
let offset = isize::try_from(self.u32()?.cast_signed())
.map_err(|_| malformed())?;
let length = self.u32()? as usize;
reference
.checked_add_signed(offset)
.zip(length.checked_sub(1))
.and_then(|(start, length)| {
self.record.get(start..start.checked_add(length)?)
})
.ok_or_else(malformed)
}
/// The attributes after the name, every one of them asked for; `None`
/// for a file whose sizes the file system left out.
fn entry(&mut self, file: u32, name: &[u8]) -> io::Result<Option<Entry>> {
let device = self.u32()?.cast_signed();
let kind = match self.u32()? {
VDIR => Kind::Directory,
VLNK => Kind::Link,
VREG => Kind::File,
_ => Kind::Other,
};
let modified = self.u64()?.cast_signed();
self.at += 8;
let flags = self.u32()?;
let inode = self.u64()?;
// A directory is stated the ordinary way. A mount point is listed
// with the attributes of the directory it covers, so its DEVID is
// the parent volume's, and the walk would cross into every disk,
// share and system volume mounted below the root. `statat` reads
// the mounted root, as `lstat` did; directories are few beside files.
let (links, allocated, apparent) = if kind == Kind::Directory {
return Ok(None);
} else if file & FILE_ATTRIBUTES == FILE_ATTRIBUTES {
(self.u32()?, self.u64()?, self.u64()?)
} else {
return Ok(None);
};
let (name, exact) = Entry::named(name);
Ok(Some(Entry {
name,
exact,
kind,
apparent,
allocated,
modified,
device: i64::from(device).cast_unsigned(),
inode,
links,
flags,
}))
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::fs;
use std::os::unix::fs::symlink;
use tempfile::TempDir;
fn listed(dir: &Path) -> Vec<Entry> {
let mut entries: Vec<Entry> = read_dir(dir)
.expect("list")
.collect::<io::Result<_>>()
.expect("entries");
entries.sort_by(|left, right| left.name.cmp(&right.name));
entries
}
/// What `lstat` says of each entry, the way the standard listing reads it.
fn stated(dir: &Path) -> Vec<Entry> {
let mut entries: Vec<Entry> = fs::read_dir(dir)
.expect("list")
.map(|entry| {
let entry = entry.expect("entry");
let stat = rustix::fs::lstat(entry.path()).expect("lstat");
Entry::from_stat(entry.file_name().as_bytes(), &stat)
})
.collect();
entries.sort_by(|left, right| left.name.cmp(&right.name));
entries
}
type Fields = (String, Kind, u64, u64, i64, (u64, u64), bool, bool);
/// What the walk reads of a leaf.
fn fields(entry: &Entry) -> Fields {
(
entry.name.to_string(),
entry.kind,
entry.apparent,
entry.allocated,
entry.modified,
entry.identity(),
entry.shared(),
entry.evicted(),
)
}
#[test]
fn a_listing_has_names_kinds_lengths_and_no_dot_entries() {
let temp = TempDir::new().expect("tempdir");
fs::create_dir(temp.path().join("sub")).expect("mkdir");
fs::write(temp.path().join("data.bin"), vec![7_u8; 100_000])
.expect("write");
symlink("data.bin", temp.path().join("link")).expect("symlink");
let entries = listed(temp.path());
let names: Vec<&OsStr> = entries.iter().map(Entry::file_name).collect();
assert_eq!(names, ["data.bin", "link", "sub"]);
assert_eq!(entries[0].kind(), Kind::File);
assert_eq!(entries[0].apparent(), 100_000);
assert_eq!(entries[0].path(temp.path()), temp.path().join("data.bin"));
assert_eq!(entries[1].kind(), Kind::Link);
assert_eq!(entries[2].kind(), Kind::Directory);
assert!(entries[0].modified() > 0, "written just now");
}
#[test]
fn every_leaf_reads_as_lstat_reads_it() {
let temp = TempDir::new().expect("tempdir");
let root = temp.path();
fs::write(root.join("plain"), b"hi").expect("write");
fs::hard_link(root.join("plain"), root.join("hard")).expect("link");
// Ten megabytes long, nothing written: no blocks.
fs::File::create(root.join("sparse"))
.and_then(|file| file.set_len(10 << 20))
.expect("sparse");
symlink("plain", root.join("link")).expect("symlink");
// A resource fork, which `st_blocks` counts and `st_size` does not.
let forked = root.join("forked");
fs::write(&forked, b"data").expect("write");
rustix::fs::setxattr(
&forked,
"com.apple.ResourceFork",
&vec![b'r'; 20_000],
rustix::fs::XattrFlags::empty(),
)
.expect("resource fork");
let listed: Vec<Fields> = listed(root).iter().map(fields).collect();
let stated: Vec<Fields> = stated(root).iter().map(fields).collect();
assert_eq!(listed, stated);
let forked = listed.iter().find(|leaf| leaf.0 == "forked").unwrap();
assert_eq!(forked.2, 4, "the data fork's length");
assert!(forked.3 >= 20_000, "the fork's blocks: {}", forked.3);
let plain = listed.iter().find(|leaf| leaf.0 == "plain").unwrap();
assert!(plain.6, "two names");
}
#[test]
fn a_directory_larger_than_the_buffer_is_listed_whole() {
let temp = TempDir::new().expect("tempdir");
// About a hundred bytes a record: several fills.
let count = 3 * BUFFER_BYTES / 100;
for index in 0..count {
fs::write(temp.path().join(format!("file-{index:05}")), b"")
.expect("write");
}
let entries = listed(temp.path());
assert_eq!(entries.len(), count);
assert_eq!(entries[0].name(), "file-00000");
assert_eq!(entries[count - 1].name(), format!("file-{:05}", count - 1));
}
#[test]
fn names_are_text_and_open() {
let temp = TempDir::new().expect("tempdir");
for name in ["café", "日本語", "with space", "a\nb"] {
fs::write(temp.path().join(name), b"x").expect("write");
}
let entries = listed(temp.path());
assert_eq!(entries.len(), 4);
for entry in entries {
assert!(entry.exact.is_none(), "{}", entry.name());
assert!(fs::metadata(entry.path(temp.path())).is_ok());
}
}
#[test]
fn a_missing_directory_is_an_error() {
let temp = TempDir::new().expect("tempdir");
let error = read_dir(&temp.path().join("gone")).expect_err("missing");
assert_eq!(error.kind(), io::ErrorKind::NotFound);
}
}