File system watching

Deep dive

How it works

In: change hints (a path, maybe a kind) from the OS, or none · Out: an exact list of Created, Modified and Deleted paths · State: snapshot path → (length, mtime), plus pending hints with last-seen times and an overflow flag · Cost: O(hinted subtrees) per batch; O(files) after an overflow

1. Subscribe to the OS first, then take the initial snapshot: changes during the scan arrive as hints (Apple's guide requires this order; inotify(7) gives the same advice for new subdirectories).
2. Put every hint in a bounded map path → last-seen time; a repeat hint only refreshes the time.
3. If the bound is hit, or the OS reports loss, set overflow: IN_Q_OVERFLOW (inotify), FAN_Q_OVERFLOW (fanotify), MustScanSubDirs/KernelDropped/UserDropped (FSEvents), ERROR_NOTIFY_ENUM_DIR or a zero-byte result (ReadDirectoryChangesW).
4. A path with no new hint for the debounce window is ready.
5. For a ready path: old = snapshot entries under it, new = a fresh walk (file, directory or nothing); diff; replace the old entries.
6. On overflow: walk the root, diff against the whole snapshot, clear pending hints.
7. Emit the changes. A rename is Deleted + Created (inotify offers a cookie-paired IN_MOVED_FROM/IN_MOVED_TO, but the manual calls matching them inherently racy).
8. Optionally run step 6 on a timer anyway (Syncthing does hourly).

Native sources: inotify (one watch per directory), fanotify (marks on a whole mount or filesystem), FSEvents (events name a directory to rescan; ids persist across reboots), kqueue EVFILT_VNODE (takes an open file descriptor per object), ReadDirectoryChangesW (bWatchSubtree for recursion).

Code

Portable recovery core, std only; the native subscription feeds Hints::push. Compiled and run on this Mac.

use std::collections::BTreeMap;
use std::path::{Path, PathBuf};
use std::time::{Duration, Instant, UNIX_EPOCH};
use std::{fs, io};

type Snap = BTreeMap<PathBuf, (u64, u128)>; // path -> (len, mtime ns)

#[derive(Debug, PartialEq)]
enum Change { Created(PathBuf), Modified(PathBuf), Deleted(PathBuf) }

/// The truth: walk the tree (a file path gives a one-entry snapshot, a missing path an empty one).
fn scan(p: &Path, out: &mut Snap) -> io::Result<()> {
    let Ok(m) = fs::symlink_metadata(p) else { return Ok(()) }; // vanished while scanning
    if m.is_dir() {
        for e in fs::read_dir(p)? { scan(&e?.path(), out)?; }
    } else {
        let t = m.modified()?.duration_since(UNIX_EPOCH).unwrap().as_nanos();
        out.insert(p.to_path_buf(), (m.len(), t));
    }
    Ok(())
}

fn diff(old: &Snap, new: &Snap) -> Vec<Change> {
    let mut v = Vec::new();
    for (p, st) in new {
        match old.get(p) {
            None => v.push(Change::Created(p.clone())),
            Some(o) if o != st => v.push(Change::Modified(p.clone())),
            _ => {}
        }
    }
    v.extend(old.keys().filter(|p| !new.contains_key(*p)).map(|p| Change::Deleted(p.clone())));
    v
}

/// Debounce + bounded queue: hints are only "look here"; a burst on one path is one entry.
struct Hints { pending: BTreeMap<PathBuf, Instant>, cap: usize, overflow: bool }

impl Hints {
    fn push(&mut self, p: PathBuf, now: Instant) {
        if self.pending.len() >= self.cap && !self.pending.contains_key(&p) {
            self.overflow = true; // an event was lost: hints can no longer be trusted
        } else {
            self.pending.insert(p, now); // repeat hint: just refresh its timestamp
        }
    }
    fn quiet(&mut self, now: Instant, wait: Duration) -> Vec<PathBuf> {
        let ready: Vec<_> = self.pending.iter()
            .filter(|(_, t)| now.duration_since(**t) >= wait).map(|(p, _)| p.clone()).collect();
        for p in &ready { self.pending.remove(p); }
        ready
    }
}

struct Watcher { root: PathBuf, snap: Snap, hints: Hints }

impl Watcher {
    fn new(root: &Path, cap: usize) -> io::Result<Self> {
        // Real use: subscribe to the OS FIRST, then take this first scan.
        let mut snap = Snap::new();
        scan(root, &mut snap)?;
        Ok(Watcher { root: root.into(), snap, hints: Hints { pending: BTreeMap::new(), cap, overflow: false } })
    }
    fn poll(&mut self, now: Instant, wait: Duration) -> io::Result<Vec<Change>> {
        let mut changes = Vec::new();
        if self.hints.overflow {                       // lost events: rescan everything
            self.hints.overflow = false;
            self.hints.pending.clear();
            let mut new = Snap::new();
            scan(&self.root, &mut new)?;
            changes = diff(&self.snap, &new);
            self.snap = new;
            return Ok(changes);
        }
        for p in self.hints.quiet(now, wait) {         // else rescan only the hinted subtrees
            let old: Snap = self.snap.range(p.clone()..).take_while(|(k, _)| k.starts_with(&p))
                .map(|(k, v)| (k.clone(), *v)).collect();
            let mut new = Snap::new();
            scan(&p, &mut new)?;
            changes.extend(diff(&old, &new));
            for k in old.keys() { self.snap.remove(k); }
            self.snap.extend(new);
        }
        Ok(changes)
    }
}

fn main() -> io::Result<()> {
    let root = std::env::args().nth(1).map(PathBuf::from).expect("dir");
    let _ = fs::remove_dir_all(&root);
    fs::create_dir_all(root.join("sub"))?;
    for f in ["a", "keep", "sub/b"] { fs::write(root.join(f), "x")?; }
    let mut w = Watcher::new(&root, 4)?;
    let (t0, wait) = (Instant::now(), Duration::from_millis(50));

    fs::write(root.join("c"), "new")?;                        // create
    fs::write(root.join("a"), "longer content")?;             // modify
    fs::remove_file(root.join("sub/b"))?;                     // delete
    for _ in 0..100 { w.hints.push(root.join("a"), t0); }     // burst of 100 hints on one path
    w.hints.push(root.join("c"), t0);
    w.hints.push(root.join("sub/b"), t0);
    assert!(w.poll(t0, wait)?.is_empty());                    // still inside the debounce window
    let mut got = w.poll(t0 + wait, wait)?;
    got.sort_by_key(|c| format!("{c:?}"));
    assert_eq!(got, vec![Change::Created(root.join("c")), Change::Deleted(root.join("sub/b")),
                         Change::Modified(root.join("a"))]);

    fs::rename(root.join("keep"), root.join("moved"))?;       // no hint for it at all
    for i in 0..10 { w.hints.push(root.join(format!("noise{i}")), t0); } // queue (cap 4) overflows
    assert!(w.hints.overflow);
    let got = w.poll(t0, wait)?; // rename = Deleted(keep) + Created(moved), found by the full rescan
    assert_eq!(got, vec![Change::Created(root.join("moved")), Change::Deleted(root.join("keep"))]);
    println!("ok");
    Ok(())
}

Complexity and constants

• Per hint: O(log pending). Per ready path: a walk of that subtree plus a prefix range in the snapshot. Overflow: O(files in tree) lstat calls.
• Snapshot memory: one path string plus 24 bytes of payload per file here (a PathBuf is heap-allocated; sharing path prefixes would shrink it).
• Measured on this Mac (Apple M4 Pro), release build, 10,000 one-byte files in 100 directories, just created (warm cache): walk 31.7-33.3 ms over 3 runs; diffing two equal 10,000-entry snapshots about 22 ms, mostly PathBuf comparisons.
• Limits: /proc/sys/fs/inotify/max_user_watches, max_queued_events, max_user_instances (inotify(7)).

Efficiency

• Cost: one hint costs a map insert; one rescan costs one lstat per file in the subtree. On this Mac (Apple M4 Pro) the measured warm walk of 32 ms for 10,000 files works out to about 3.2 µs per file. Bound: syscall rate for rescans, kernel memory for watches.
• Levers:
  • rescan only the hinted subtree — cost follows the change, not the tree (the code above) — hints carry a directory path (inotify, FSEvents)
  • debounce window — one rescan per burst (Syncthing waits 10 s, deleted files 1 min) — bulk writes, builds, checkouts
  • persisted cursor (FSEvents sinceWhen event id; watchman since clock) — no full scan after a restart (Apple guide, watchman docs) — daemons that restart
  • ignored paths for generated trees (chokidar ignored/depth) — fewer watches and hints — dependency and build directories
  • raise queue and watch limits — fewer overflow rescans (inotify(7)) — large trees
• Naive → standard → state of the art:
  • poll the full tree every interval · O(files) per interval; about 32 ms per 10,000 files here
  • native events + debounce + rescan of hinted directories, full rescan on overflow · O(changes) normally
  • the same plus a persisted event id or clock, plus a rare scheduled scan · O(changes) across restarts too

Implementation notes

• Use lstat, not stat: a change to a symlink target raises no event for the link (Apple guide).
• Watch the parent directory, not the file: an editor's write-temp-then-rename replaces the inode and a file-level watch goes stale (atomic replacement). chokidar's atomic option merges an unlink + add within 100 ms into one change.
• Subdirectory created or moved in: scan it right after adding its watch; files may already exist (inotify(7)).
• Dispatch: put the inotify descriptor in a poll loop (epoll); read in large batches.
• Compare (length, mtime) only when a miss is tolerable; add inode, ctime or a content hash when it is not.

Pitfalls

• Scanning before subscribing loses changes made in between.
• An event queue that grows without bound under a bulk write; bound it and recover by rescan instead.
• Trusting a path in an old event: inotify(7) warns the name may be deleted or renamed by the time it is read; directory renames invalidate cached watch-to-path maps.
• Network file systems: inotify "does not catch remote events"; /proc, /sys are unmonitorable; writes through mmap are not reported (all inotify(7)).
• inotify ENOSPC means the watch limit is hit, not that the disk is full.
• A same-size rewrite inside the timestamp granularity looks unchanged to a (length, mtime) snapshot.
• Self-triggered events: inotify cannot tell your own writes from others'.

Variants and alternatives

In production

Syncthing: watcher plus hourly full scan by default. Watchman: a shared daemon that clients subscribe to with a settle period. Language servers: the LSP client does the watching and sends workspace/didChangeWatchedFiles; the spec discourages servers watching themselves. Fluent Bit's tail input relies on inotify and records inode and offset per file. Antivirus and hierarchical storage use fanotify. Dev servers use chokidar.

Implementations

Sources

• inotify(7), fanotify(7), Linux man-pages.
• kqueue(2), FreeBSD manual.
• Apple, File System Events Programming Guide, "Using the File System Events API". guide
• Microsoft, ReadDirectoryChangesW.
• Syncthing docs, Syncing (watcher, full scans, delays).
• Watchman subscribe (settle period, since).
• Language Server Protocol 3.17, workspace/didChangeWatchedFiles.
• Fluent Bit, Tail input.