Build a Disk Usage Analyzer in Rust Like du and ncdu

A disk is full and you want to know why. du answers, in a way that is accurate and awkward to read, and ncdu answers interactively. Building a small version yourself, rdu, is a good exercise because the problem looks trivial, add up the file sizes, and is not. "Size" has two meanings that differ by 10 percent on a tidy directory and by a factor of ten on a directory full of small files. Hard links make the same bytes appear in two places. A symlink to a parent directory loops forever if followed. Parallel scanning makes the answer depend on thread timing unless you design against it. And a directory you cannot read must not stop the report.

This guide builds rdu step by step, finds a real nondeterminism bug in the first parallel version by running it twelve times, fixes it, checks the result against du, and measures the speed. It was written on Rust 1.99 (edition 2024) with rayon 1.12 and clap 4.6.7, on macOS, so file-system details such as block size and APFS behavior reflect that platform. The output blocks are real.

Two sizes: what you wrote and what you pay for

A file has an apparent size, the number of bytes in its contents, and a disk usage, the number of bytes of storage the file system allocated for it. They differ for three reasons. Storage is allocated in blocks, so a 9-byte file costs a whole block. Sparse files have holes that cost nothing. And compressing file systems store less than the logical size. The standard library exposes both through std::fs::Metadata: len() is apparent size, and on Unix the MetadataExt::blocks() method returns the number of 512-byte units allocated.

fn measure(md: &fs::Metadata, how: Measure) -> u64 {
    match how {
        Measure::Apparent => md.len(),
        Measure::Disk => md.blocks() * 512,
    }
}

du reports disk usage by default and du --apparent-size reports the other. The tool should do the same, and name the choice in a flag. The difference is visible on a small directory built to show it: a 5 MB file, a 3 MB file, an 800 KB file, 200 tiny log files of a few bytes each, a 120 KB source file, plus empty directories.

$ rdu /tmp/du_demo
   9.3 MiB  100.0%  ####################  .
...
206 files, 9.3 MiB

$ rdu --apparent /tmp/du_demo
   8.5 MiB  100.0%  ####################  .
   8.4 MiB   98.6%  ####################  media
   117.3 KiB    1.3%                      src
    8.0 KiB    0.1%                      logs
        64 B    0.0%                      empty
206 files, 8.5 MiB

The logs directory holds 200 files of about eight bytes each, so its apparent size is 8.0 KiB (the files plus the directory entries). Its disk usage is far larger, because 200 files each occupy at least one 4 KiB block: the disk-usage mode reports logs at 1.5 MiB, a hundred and ninety times the apparent size. This is exactly the case where the two measures disagree, and the one that explains most "where did my disk go" puzzles: a directory with a hundred thousand small files is cheap in bytes and expensive in blocks. Always show the disk usage by default and offer the other as a flag.

Two experiments that show why the modes exist

The demo tree hides the two cases where apparent and disk size diverge most. A second tree makes them obvious: a 1 GiB sparse file created with truncate -s 1G (all hole, no data), a 1 MB file of random bytes, and a directory of 1,000 files that each contain a single byte.

$ rdu /tmp/du_sparse -d 1
   4.9 MiB  100.0%  ####################  .
     3.9 MiB   80.3%  ################     many
1002 files, 4.9 MiB

$ rdu --apparent /tmp/du_sparse -d 1
   1.0 GiB  100.0%  ####################  .
    32.3 KiB    0.0%                       many
1002 files, 1.0 GiB

The same directory is 4.9 MiB by one measure and 1.0 GiB by the other. The sparse file contributes a gigabyte of apparent size and nothing at all to disk usage: stat confirms it, reporting 1,073,741,824 bytes and zero blocks. This is why a virtual machine image or a database preallocated with holes looks enormous in ls -l and costs almost nothing on disk, and why copying such a file naively with a tool that does not preserve holes fills the disk. In the other direction, the 1,000 single-byte files total 32.3 KiB of content, but each occupies a full allocation of 8 blocks of 512 bytes, 4,096 bytes, so the directory costs 3.9 MiB, which is 125 times its apparent size. du -sk agreed with the disk-usage figure, reporting 4,980 KiB for the tree. A tool that reports only apparent size would miss the many-small-files case, and one that reports only disk size would miss the sparse file; offer both, default to the one that answers the question "what is using my disk".

What counts as a file

The scanner makes a small number of decisions about file types, and each one should be stated because users hit them. The table lists the cases with the behavior of rdu and the reason.

Real tools expose some of these as options: du -L follows symlinks, -l counts hard links every time they appear, and -x refuses to cross file systems. Which to choose depends on the question. If you are asking "how much would I free by deleting this directory?", hard links to files that live elsewhere do not count, because deleting this name leaves the bytes in place. That is a harder question than it looks: the correct answer for one directory depends on what else links to its files, which a single scan from that directory cannot know. A faithful "what would deleting free" mode scans the whole file system, counts links per inode globally and charges a directory only for inodes whose every link lies inside it.

The scanner

The scan is a recursive function that returns an Entry for each path: its total size, the number of files below it and, for directories, the child entries. It uses symlink_metadata, which does not follow symlinks, because following them would loop on a link that points at its own parent and would double-count anything reachable twice.

use std::collections::HashSet;
use std::fs;
use std::os::unix::fs::MetadataExt;
use std::path::{Path, PathBuf};
use std::sync::Mutex;

use rayon::prelude::*;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Measure {
    /// Bytes of content, what `ls -l` shows.
    Apparent,
    /// Bytes allocated on disk, what `du` shows: whole blocks, so small files cost a block each.
    Disk,
}

#[derive(Debug)]
pub struct Entry {
    pub path: PathBuf,
    pub size: u64,
    pub files: u64,
    pub children: Vec<Entry>,
}

#[derive(Default)]
pub struct Stats {
    pub errors: Mutex<Vec<String>>,
    /// Files with more than one link. They are not charged during the scan, because threads reach
    /// them in a different order each run. `settle` charges each one to its first path, sorted.
    hard_links: Mutex<Vec<(u64, u64, PathBuf, u64)>>,
}

/// Charge every hard-linked file exactly once, to the path that sorts first, so the report does
/// not depend on which thread got there first.
pub fn settle(root: &mut Entry, stats: &Stats) {
    let mut claims = std::mem::take(&mut *stats.hard_links.lock().unwrap());
    claims.sort_by(|a, b| a.2.cmp(&b.2));
    let mut charged = HashSet::new();
    for (dev, ino, path, size) in claims {
        if charged.insert((dev, ino)) {
            add_to_ancestors(root, &path, size);
        }
    }
}

fn add_to_ancestors(entry: &mut Entry, path: &Path, size: u64) {
    if path.starts_with(&entry.path) {
        entry.size += size;
        for child in &mut entry.children {
            add_to_ancestors(child, path, size);
        }
        entry.children.sort_by(|a, b| b.size.cmp(&a.size));
    }
}

fn measure(md: &fs::Metadata, how: Measure) -> u64 {
    match how {
        Measure::Apparent => md.len(),
        Measure::Disk => md.blocks() * 512,
    }
}

/// Total size of `path`, with one `Entry` per directory down to `depth` levels.
pub fn scan(path: &Path, how: Measure, depth: usize, stats: &Stats) -> Entry {
    let md = match fs::symlink_metadata(path) {
        Ok(md) => md,
        Err(e) => {
            stats.errors.lock().unwrap().push(format!("{}: {e}", path.display()));
            return Entry { path: path.into(), size: 0, files: 0, children: vec![] };
        }
    };
    // A symlink is counted as the link itself and never followed, which avoids loops.
    if !md.is_dir() {
        let size = measure(&md, how);
        if md.nlink() > 1 && !md.file_type().is_symlink() {
            stats.hard_links.lock().unwrap().push((md.dev(), md.ino(), path.to_path_buf(), size));
            return Entry { path: path.into(), size: 0, files: 1, children: vec![] };
        }
        return Entry { path: path.into(), size, files: 1, children: vec![] };
    }

    let names: Vec<PathBuf> = match fs::read_dir(path) {
        Ok(rd) => rd.filter_map(|e| e.ok()).map(|e| e.path()).collect(),
        Err(e) => {
            stats.errors.lock().unwrap().push(format!("{}: {e}", path.display()));
            vec![]
        }
    };
    let mut kids: Vec<Entry> = names.par_iter().map(|p| scan(p, how, depth.saturating_sub(1), stats)).collect();
    let size = measure(&md, how) + kids.iter().map(|k| k.size).sum::<u64>();
    let files = kids.iter().map(|k| k.files).sum();
    // Keep only directories as children, and only down to the requested depth.
    kids.retain(|k| !k.children.is_empty() || fs::symlink_metadata(&k.path).is_ok_and(|m| m.is_dir()));
    if depth == 0 {
        kids.clear();
    }
    kids.sort_by(|a, b| b.size.cmp(&a.size));
    Entry { path: path.into(), size, files, children: kids }
}

pub fn human(bytes: u64) -> String {
    const UNITS: [&str; 5] = ["B", "KiB", "MiB", "GiB", "TiB"];
    let mut value = bytes as f64;
    let mut unit = 0;
    while value >= 1024.0 && unit < UNITS.len() - 1 {
        value /= 1024.0;
        unit += 1;
    }
    if unit == 0 { format!("{bytes} B") } else { format!("{value:.1} {}", UNITS[unit]) }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::os::unix::fs::symlink;

    fn tree() -> PathBuf {
        static NEXT: std::sync::atomic::AtomicU32 = std::sync::atomic::AtomicU32::new(0);
        let n = NEXT.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
        let root = std::env::temp_dir().join(format!("rdu-test-{}-{n}", std::process::id()));
        let _ = fs::remove_dir_all(&root);
        fs::create_dir_all(root.join("a")).unwrap();
        fs::create_dir_all(root.join("b")).unwrap();
        root
    }

    fn run(root: &Path, how: Measure) -> Entry {
        let stats = Stats::default();
        let mut e = scan(root, how, 1, &stats);
        settle(&mut e, &stats);
        e
    }

    #[test]
    fn apparent_size_adds_up_file_contents() {
        let root = tree();
        fs::write(root.join("a/one"), vec![0u8; 1000]).unwrap();
        fs::write(root.join("b/two"), vec![0u8; 2500]).unwrap();
        let e = run(&root, Measure::Apparent);
        let dirs = fs::symlink_metadata(&root).unwrap().len() + fs::symlink_metadata(root.join("a")).unwrap().len() + fs::symlink_metadata(root.join("b")).unwrap().len();
        assert_eq!(e.size, 3500 + dirs);
        assert_eq!(e.files, 2);
        fs::remove_dir_all(root).unwrap();
    }

    #[test]
    fn a_hard_link_is_charged_once_and_to_the_first_path() {
        let root = tree();
        fs::write(root.join("b/big"), vec![0u8; 100_000]).unwrap();
        fs::hard_link(root.join("b/big"), root.join("a/alias")).unwrap();
        for _ in 0..20 {
            let e = run(&root, Measure::Apparent);
            let a = e.children.iter().find(|c| c.path.ends_with("a")).unwrap();
            let b = e.children.iter().find(|c| c.path.ends_with("b")).unwrap();
            assert!(a.size >= 100_000, "the first sorted path owns the bytes");
            assert!(b.size < 100_000);
        }
        fs::remove_dir_all(root).unwrap();
    }

    #[test]
    fn a_symlink_loop_terminates_and_is_not_followed() {
        let root = tree();
        symlink(&root, root.join("a/loop")).unwrap();
        let e = run(&root, Measure::Apparent);
        assert_eq!(e.files, 1); // only the link itself
        fs::remove_dir_all(root).unwrap();
    }

    #[test]
    fn an_unreadable_directory_is_reported_not_fatal() {
        use std::os::unix::fs::PermissionsExt;
        let root = tree();
        fs::write(root.join("a/ok"), b"x").unwrap();
        fs::set_permissions(root.join("b"), fs::Permissions::from_mode(0o000)).unwrap();
        let stats = Stats::default();
        let e = scan(&root, Measure::Apparent, 1, &stats);
        assert_eq!(e.files, 1);
        assert_eq!(stats.errors.lock().unwrap().len(), 1);
        fs::set_permissions(root.join("b"), fs::Permissions::from_mode(0o755)).unwrap();
        fs::remove_dir_all(root).unwrap();
    }
}

Several choices in that listing are the substance of the tool.

A symlink is counted as the link itself, a few dozen bytes, and never followed. A directory is read with read_dir, and an entry that fails to read is recorded in a shared error list and treated as empty, so one permission problem cannot abort a whole scan. Failure is information to report at the end, not an exception.

The directory's own size is added to the total of its children, which is what du does: a directory is a file with contents of its own. On this APFS volume empty directories have no blocks, so empty reports 0 B in disk mode and 64 B apparent.

Each directory scans its children in parallel with par_iter from rayon, which hands the children to a thread pool sized to the number of cores. Because scan is a pure recursive function that returns values, the parallelism is a one-word change from iter to par_iter. The only shared state is the Stats object, behind a Mutex, and it is touched only on errors and for hard links, both rare.

The bug that only shows on the twelfth run

The first version handled hard links the obvious way. A file can have several names, two directory entries pointing at one inode, and du charges its bytes once. The scanner kept a HashSet of (device, inode) pairs and counted a file only when it was inserted for the first time. That is correct for the total. Run the tool twelve times on the demo tree, in which media/video.bin (800 KB) has a hard link in logs, and look at how the two directories were charged:

  1      7.6 MiB media    1.5 MiB logs
 11      8.4 MiB media    800.0 KiB logs

Eleven runs charged the 800 KB file to media, and one charged it to logs. The totals were always equal, 9.3 MiB, but the per-directory numbers changed from one run to the next. The cause is the thread pool. Both directories are scanned concurrently, and whichever thread reached the shared inode first inserted it and paid. This is a classic parallel-programming trap: nothing is wrong with the locking, and the result is still not a function of the input.

du has no such problem because it walks the tree in order, so the file is charged to whichever path comes first in its traversal. In the sample, that is logs: du reported logs at 1,584 KiB and media at 7,816 KiB, the same split as the corrected tool.

The fix makes the choice explicit. Files with more than one link are not charged during the scan; their claims are recorded in Stats. After the scan, settle sorts the claims by path, keeps the first claim for each inode, and adds the bytes to that path and every ancestor directory's entry:

pub fn settle(root: &mut Entry, stats: &Stats) {
    let mut claims = std::mem::take(&mut *stats.hard_links.lock().unwrap());
    claims.sort_by(|a, b| a.2.cmp(&b.2));
    let mut charged = HashSet::new();
    for (dev, ino, path, size) in claims {
        if charged.insert((dev, ino)) {
            add_to_ancestors(root, &path, size);
        }
    }
}

With that change, thirty consecutive runs produced one result, 7.6 MiB media and 1.5 MiB logs, matching du. The principle is worth stating plainly: when the order of work is not deterministic, make the rule that depends on order explicit and deterministic, here "the path that sorts first". Do not rely on timing being stable.

Reading the output

The report prints each directory with its size, share of the total and a bar scaled to 5 percent per #. Sorting by size puts the answer at the top:

   9.3 MiB  100.0%  ####################  .
     7.6 MiB   82.1%  ################     media
       7.6 MiB   82.1%  ################     media/photos
     1.5 MiB   16.6%  ###                  logs
   120.0 KiB    1.3%                       src
         0 B    0.0%                       empty
206 files, 9.3 MiB

With -d 2, the tool descends two levels and shows that media/photos holds nearly all of media. The human function formats with binary units, KiB, MiB and GiB, because the file system allocates in powers of two and because KB is ambiguous between 1,000 and 1,024 bytes. The final line gives the file count, which for the sample is 206: 200 logs, three media files, the hard link and the source file, with the symlink counted once.

The program exits with status 1 if any entry could not be read, and prints the first failure to standard error. A scan of a directory with a locked subdirectory reports the readable part and then complains:

   4.0 KiB  100.0%  ####################  .
     4.0 KiB  100.0%  ####################  open
         0 B    0.0%                       locked
1 files, 4.0 KiB
rdu: 1 entries could not be read, for example /tmp/du_perm/locked: Permission denied (os error 13)

A report that silently omits what it could not read is worse than none, because the totals look authoritative. The error line and the exit status make the gap visible to a script.

Checking it against du

A tool like this is only trustworthy once it agrees with the established one on real data. The test tree was a Cargo target directory of 25,350 files. du -sk reported 10,959,208 KiB, which is 10.45 GiB; rdu reported 10.5 GiB (it rounds to one decimal place), and the file count of 25,350 matched find -type f | wc -l. Speed, measured with time:

• rdu with the thread pool: 0.10 to 0.11 s (one 0.17 s run while the cache warmed).
• rdu with iter in place of par_iter: 0.20 s.
• du -sk: 0.09 to 0.10 s.

The parallel scan is twice as fast as the sequential one on this machine, and equal to du within noise. The directory metadata was in the operating system's cache, so these are warm-cache numbers; on a cold disk or a network file system, where each stat waits, parallelism helps more, because threads overlap the waiting. The lesson matches the one in building a fast file finder: walking a tree is dominated by system calls, and the cheap win is overlapping them.

Tests that guard the sharp edges

The four unit tests build a real directory tree under the system temp directory and assert the properties that went wrong or could go wrong:

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

One checks that apparent sizes add up, including the directories' own sizes. One creates a hard link and runs the scan twenty times, asserting each time that the directory sorting first owns the bytes: the regression test for the nondeterminism. One creates a symlink that points at its own parent and asserts the scan terminates and counts only the link. One removes all permissions from a subdirectory and asserts that the scan finishes, reports one error, and counts the readable part. Each fixture cleans up after itself, uses the process id in its name so parallel test runs do not collide, and restores permissions before deleting.

Where to take it

The natural next steps each teach something. A -x flag that stays on one file system compares dev from MetadataExt with the root's and skips directories on other devices, so a scan of / does not wander into network mounts. An --exclude pattern filters paths with the globset crate before descending. A --json output serializes the Entry tree with serde for other tools. An interactive browser built with ratatui (a terminal UI guide covers the loop) lets you move into a directory, sort differently and press a key to delete. And on Linux, reading getdents directly with the rustix crate avoids allocating a path for every entry and makes the scan notably faster on huge trees.

When to use the real tools

For a one-off, du -sh * | sort -h is faster to type than any program, and ncdu has a polished interface and years of edge-case fixes. Write your own when you need the numbers inside another tool, as a library function in a deployment script or a service that watches a cache directory, or when you need a policy du lacks: charging by owner, grouping by extension, ignoring a build directory. The structure here, a pure recursive function with a small shared error log, a deterministic rule for the shared inode, and a test for each sharp edge, is the one to copy.

Making the scanner reusable

As written, rdu is one binary with the scanner in a module. The first request after it works is "can I call this from another program", and the structure to adopt before that arrives is a library crate with a thin binary: move scan.rs into src/lib.rs, keep the command line in src/main.rs, and let the binary depend on the library like any other crate. The tests move with the scanner, and a second consumer, such as a monitoring service that alerts when a cache directory passes a size, gets scan, settle and Measure without the argument parser.

Two API choices pay off then. Return the error list as part of the result instead of collecting it in a shared Stats that callers must create; a function that returns (Entry, Vec<String>) is harder to misuse than one that needs a mutable accumulator and a separate call to settle. And hide the two-step scan then settle behind one function, scan_tree, so no caller can forget the second step and get the racy answer the first version produced. A bug you fixed once should be impossible to reintroduce by calling the API wrongly, which is a design rule worth applying to every library in this series, and the one that makes the earlier regression test, twenty runs asserting one answer, a safety net and not the only defense.