Repository Public License
1<!-- ORIX Clean / File: docs/architecture/scanner.md / Author: Simon-Pierre Boucher / Contact: contact@spboucher.ai -->2# Scanner34The scanner turns a directory into a `ScanTree`: one fixed-size record per filesystem object, with sizes5aggregated up to the root. Sources: `FileScanner/DirectoryReader.swift`, `FileScanner/FileScanner.swift`,6`FileScanner/ScanTree.swift`.78## Design decisions910| Decision | Rationale |11|---|---|12| `getattrlistbulk(2)` instead of `readdir` plus `stat`, or `FileManager` enumeration | One system call returns names and all needed attributes for many entries. It is also the only bulk route to the APFS private size, clone id and extended flags |13| Never follow symbolic links | A link is recorded as a link with its own size. Loops cannot occur and nothing outside the root is counted |14| Mount points detected by `fstat` of the opened directory | The directory entry describes the covered folder; the open descriptor describes what is mounted on it |15| Hard links counted once | Totals must match what the volume actually stores |16| Dataless files never read | Reading an evicted iCloud or File Provider item would download it |17| Dedicated threads, default 3 | Enumeration is bound by the filesystem, not by cores (see `docs/development/performance.md`) |18| Arena of 64-byte records | Predictable memory, cache-friendly aggregation, cheap `Sendable` hand-off |1920## Reading one directory2122`DirectoryReader.open` opens with `O_RDONLY | O_DIRECTORY | O_NOFOLLOW | O_CLOEXEC`. If `open` fails with23`ENAMETOOLONG`, the path is walked component by component with `openat` from `/`; only the last component24refuses symlinks, as `open(2)` itself does.2526`DirectoryReader.read` calls `getattrlistbulk` in a loop on a 256 KiB buffer owned by the worker thread.2728### Attributes requested2930| Group | Attributes |31|---|---|32| `commonattr` | `ATTR_CMN_RETURNED_ATTRS`, `ATTR_CMN_ERROR`, `ATTR_CMN_NAME`, `ATTR_CMN_DEVID`, `ATTR_CMN_OBJTYPE`, `ATTR_CMN_MODTIME`, `ATTR_CMN_FLAGS`, `ATTR_CMN_FILEID` |33| `dirattr` | `ATTR_DIR_MOUNTSTATUS` |34| `fileattr` | `ATTR_FILE_LINKCOUNT`, `ATTR_FILE_TOTALSIZE`, `ATTR_FILE_ALLOCSIZE` |35| `forkattr` with `FSOPT_ATTR_CMN_EXTENDED` | `ATTR_CMNEXT_PRIVATESIZE`, `ATTR_CMNEXT_CLONEID`, `ATTR_CMNEXT_EXT_FLAGS` |3637### Order in the returned buffer3839Each entry starts with a `UInt32` length. The parser then reads, in this order, only the attributes present in40the returned set:4142| # | Field | Size in bytes | Stored as |43|---|---|---|---|44| 1 | entry length | 4 | advance cursor |45| 2 | `attribute_set_t` returned attributes | 20 | presence mask |46| 3 | error | 4 | `RawEntry.error` |47| 4 | name reference `attrreference_t` | 8 | offset and length; bytes copied without the trailing NUL |48| 5 | device id | 4 | `device` |49| 6 | object type | 4 | `objType`: 1 regular, 2 directory, 5 symlink |50| 7 | modification time `timespec` | 16 | seconds only |51| 8 | BSD flags | 4 | `SF_DATALESS`, `UF_COMPRESSED` |52| 9 | file id | 8 | inode number |53| 10 | mount status, directories | 4 | `mountStatus` |54| 11 | link count, files | 4 | `linkCount` |55| 12 | total size, files | 8 | `logicalSize` |56| 13 | allocated size, files | 8 | `allocatedSize` |57| 14 | private size | 8 | `privateSize`, -1 when absent |58| 15 | clone id | 8 | `cloneID` |59| 16 | extended flags | 8 | `EF_MAY_SHARE_BLOCKS`, `EF_IS_SPARSE` |6061All loads are unaligned. If the first call fails with `EINVAL` or `ENOTSUP` while extended attributes were62requested, the directory is read again without them; `ScanResult.sharingMeasured` is true only if at least one63regular file reported a private size.6465## Traversal6667```mermaid68flowchart TD69 Start[run: lstat root, probe open] --> Seed[push root on the work stack]70 Seed --> Take[worker takes a directory]71 Take --> Open[open with O_NOFOLLOW]72 Open -->|fails| Fail[record issue, flag unreadable if EACCES or EPERM]73 Open --> Stat[fstat the descriptor]74 Stat -->|other device, not allowed| Boundary[flag boundary, do not read]75 Stat --> Read[getattrlistbulk until empty]76 Read --> Commit[commit under the lock: append nodes and names]77 Commit --> Classify{entry type}78 Classify -->|directory| DirRules[dataless, excluded, foreign device, or queue]79 Classify -->|regular file| FileRules[sizes, flags, hard-link set]80 Classify -->|symlink| Link[flag symlink, own size only]81 Classify -->|other| Special[flag special]82 DirRules --> Take83 Fail --> Take84 Boundary --> Take85 Take -->|stack empty and no worker active| Aggregate[one reverse pass sums directories]86 Aggregate --> Result[ScanResult]87```8889Shared state (work stack, tree, issue list, counters, the two "seen" sets) is guarded by one `NSCondition`.90Workers read directories without the lock and take it only to pop work and to commit a whole batch. The stack91is LIFO, so traversal is depth-first per worker. A worker exits when the stack is empty and no other worker is92active, or on cancellation. Threads use `.userInitiated` quality of service and a 1 MiB stack.9394Rules applied to each entry at commit:9596- **Directory**: flagged `package` when its extension is in `PackageTypes.extensions` (packages are still97 traversed). It is not queued when it is dataless, listed in `excludedPaths` (`skipped`), on a device other98 than the root and not in `allowedDevices` (`boundary`), reported with an error, or already seen. The seen set99 is keyed by device and file id.100- **Regular file**: counted; sizes copied; flags `dataless`, `compressed`, `mayShareBlocks`, `sparse` set from101 the kernel flags. A clone id is stored in `tree.cloneIDs` only when the file may share blocks. With a link102 count above 1 the file is `hardLinked`, and every name after the first seen is also `hardLinkDuplicate`.103- **Symlink**: flagged, its own logical and allocated size kept, never queued.104- **Anything else** (socket, FIFO, device): flagged `special`, size zero.105106`ScanOptions.startupVolume()` is used for `/`: it allows the device of `/System/Volumes/Data` and excludes107`/System/Volumes`, `/Volumes`, `/dev` and `/.vol`, so the firmlinked data is counted once.108109## Data structures110111`ScanNode` is 64 bytes:112113| Field | Type | Bytes | Meaning |114|---|---|---|---|115| `nameOffset` | `UInt32` | 4 | Offset in the shared name buffer |116| `nameLength` | `UInt16` | 2 | UTF-8 length |117| `flags` | `NodeFlags` (`UInt16`) | 2 | 14 flags, see below |118| `parent` | `Int32` | 4 | -1 for the root |119| `childStart` | `Int32` | 4 | Index of the first child |120| `childCount` | `Int32` | 4 | Children are contiguous |121| `fileCount` | `UInt32` | 4 | Regular files below; 1 for a file |122| `logicalSize` | `Int64` | 8 | Content bytes |123| `allocatedSize` | `Int64` | 8 | Bytes allocated on disk |124| `privateSize` | `Int64` | 8 | APFS private size; -1 when not reported |125| `modified` | `Int64` | 8 | Seconds since 1970 |126| `fileID` | `UInt64` | 8 | Inode number |127128`NodeFlags`: `directory`, `symlink`, `package`, `hardLinked`, `hardLinkDuplicate`, `mayShareBlocks`, `sparse`,129`dataless`, `unreadable`, `boundary`, `compressed`, `special`, `removed`, `skipped`.130131`ScanTree` holds `nodes: [ScanNode]`, `names: [UInt8]` (all names back to back, no terminators),132`cloneIDs: [Int32: UInt64]`, `rootPath` and `rootDevice`. Paths are rebuilt on demand by walking parents.133134## Invariants135136- Index 0 is the root. The children of a directory are contiguous and always have a larger index than their137 parent; `aggregate()` relies on this to sum every directory in one reverse pass.138- A `hardLinkDuplicate` node contributes its `fileCount` but no bytes to any total.139- A directory's `privateSize` is the sum of positive private sizes below it, hence a lower bound.140- After `run()` returns, the tree is read-only except for `markRemoved`, which must not run while an analysis141 reads the tree. `markRemoved` flags the subtree and subtracts its totals from every ancestor.142- The running `allocatedBytes` progress counter excludes hard-link duplicates.143144## Failure handling145146| Situation | Result |147|---|---|148| Root missing, not a directory, or unreadable | `ScanError.rootNotFound`, `.rootNotDirectory`, `.rootUnreadable(path, errno)` thrown before any thread starts |149| Directory cannot be opened | `ScanIssue` with kind from errno: `permissionDenied` (`EACCES`, `EPERM`), `vanished` (`ENOENT`, `ENOTDIR`), `pathTooLong`, otherwise `ioError`; node flagged `unreadable` for permission errors; scan continues |150| Read fails part-way | Issue recorded; entries already returned are kept |151| Per-entry error from the kernel | Issue recorded for that entry; a directory with an error is not queued |152| Tree would exceed `Int32` node indexes or `UInt32` name bytes | Issue with `EOVERFLOW` for that directory; its entries are dropped |153| Cancel | Workers stop taking work; aggregation still runs; `ScanResult.cancelled` is true |154| Pause | Workers finish their current directory and wait on the condition |155156The application discards a cancelled result and keeps the previous tree.157158## Not handled159160- Directory hard links and firmlink subtleties beyond the device and file id check.161- Extended attributes and resource forks as separate items; `ATTR_FILE_TOTALSIZE` already includes all forks.162- Sizes of directories themselves (zero on APFS; filesystems that allocate blocks for directories are163 under-counted by that amount).164- Names longer than 65,535 bytes are truncated to that length in the arena.165- No incremental update: a rescan rebuilds the whole tree.166- Filesystems other than APFS were exercised only as far as the fallback path compiles; see the "not measured"167 list in `docs/development/performance.md`.168