How tree -s Calculates Directory Sizes in Linux

This article explains how the Linux operating system processes file and directory sizes when using the tree -s command. It covers the underlying Virtual Filesystem (VFS) architecture, the relevant system calls used during directory traversal, why standard directory sizes appear fixed at 4096 bytes, and how recursive accumulation operates under the hood.

The Role of tree -s

The tree command is a recursive directory listing program that produces a depth-indented listing of files. When passed the -s flag, tree prints the size of each file in bytes alongside its name.

To report these sizes, tree does not directly inspect storage blocks on disk. Instead, it interfaces with the Linux Virtual Filesystem (VFS) abstraction layer through standard POSIX system calls.

System Calls and Directory Traversal

When you execute tree -s, the process interacts with the Linux kernel using two primary operations for every node in the filesystem tree:

  1. Reading Directory Entries: The program uses the opendir() and readdir() library functions, which invoke the underlying getdents64 (get directory entries) system call. This reads raw directory entries from the kernel, retrieving file names and their associated inode numbers.
  2. Querying File Metadata: For each entry found, tree calls lstat() or fstatat(). This system call populates a stat buffer containing the inode's metadata without following symbolic links. The size printed by -s corresponds directly to the st_size field returned in this buffer.

Why tree -s Does Not Sum Directory Contents by Default

A common misconception is that running tree -s automatically sums the contents of a directory to display its cumulative size. Under Unix-like operating systems, a directory is simply a special type of file that contains a mapping of filenames to inode numbers.

When tree -s queries a directory using lstat(), the kernel returns the size of that directory file itself—representing the space allocated to hold the list of directory entries. On modern Linux filesystems such as ext4, this value is almost always 4096 bytes (one filesystem block) or a multiple of 4096 if the directory contains thousands of files.

Therefore, standard tree -s output reflects:

Handling Recursive Accumulation with --du

To calculate true recursive directory sizes, tree must be invoked with the --du (disk usage) flag, often combined with -s or -h.

When calculating cumulative sizes recursively, the process follows these steps:

  1. Depth-First Traversal (Post-Order): The tree algorithm descends to the deepest leaf nodes of the directory tree before finalizing the size of parent directories.
  2. Inode Tracking: To prevent inflated calculations caused by hard links, tree maintains a hash table of visited device IDs and inode numbers (st_dev and st_ino). If a hard link points to an already-tallied inode, its size is omitted from subsequent parent totals.
  3. Aggregation: As the traversal unwinds back up the directory tree, the accumulated bytes of all child files and subdirectories are summed into the parent directory's total.

File Size vs. Disk Allocation

When viewing sizes via tree -s, the value represents logical size (st_size), not physical storage consumption. Sparse files, for example, may report large logical sizes via st_size despite consuming very few physical blocks on disk. If accurate disk block consumption is required rather than apparent size, commands relying on st_blocks (such as du) or tree --du reflect the true allocation managed by the filesystem allocator.