Directory Entries as a Name-to-Inode Map

Every lookup performed by a program that opens a file by pathname ends in the same operation: a search inside a directory for a record whose name matches the component just parsed. The directory is not a special opaque object with its own namespace machinery. It is a file, stored like any other, whose contents happen to be a sequence of records, and every rule about directory behaviour follows from the shape of those records.

Records, not a text listing

A directory’s data area holds an array of variable-length entries. Each entry carries the inode number of the target, the length of the name, the length of the whole record, and the name bytes themselves. Ext4’s second-generation entry format is representative:

/* Layout of an ext4_dir_entry_2 record; fields are little-endian on disk. */
struct ext4_dir_entry_2 {
    uint32_t inode;      /* inode number, 0 for an unused record */
    uint16_t rec_len;    /* bytes occupied by this record, including padding */
    uint8_t  name_len;   /* significant bytes in name[] */
    uint8_t  file_type;  /* DT_REG, DT_DIR, DT_LNK, ... */
    char     name[];     /* not NUL-terminated; padded to a 4-byte boundary */
};

The record length is separate from the name length because names are padded to a four-byte boundary and the padding belongs to the record. That single decision is what makes deletion cheap. Removing a name does not shift the following records left, which would require rewriting the rest of the block. The entry’s inode number is set to zero and the record stays where it is, or, more commonly, the record is merged into its predecessor by adding its length to the predecessor’s rec_len. Either way, the bytes after the deleted name remain in place, and subsequent lookups skip over the gap by advancing rec_len bytes at a time.

Two properties follow immediately. Directory sizes only grow: the block count of a directory rises as entries are added and does not fall when they are removed, because reclaiming the space would mean compacting records that other processes might be mid-scan through. And a directory’s data area can contain a large fraction of dead space, which is why an ext4 directory that once held a hundred thousand files remains several megabytes in size after all of them are deleted.

The name limit comes from the record format as much as from the interface. name_len is one byte, capping a name at 255 bytes, and POSIX exposes that ceiling as NAME_MAX. The limit is bytes, not characters, so a name of 200 multi-byte characters can exceed it. Separately, PATH_MAX limits a whole pathname string to 4096 bytes on Linux, and that limit applies to the buffer a program passes to open, not to the depth of the tree: a path can be resolved in pieces through openat with directory descriptors even when the concatenated string would exceed the limit.

The two entries every directory contains

A new directory is created with two entries that name inodes already in existence: . points to the directory itself, and .. points to its parent. Both are ordinary entries, indistinguishable in format from any other, and both are skipped by most tools only because the code filters the names.

.. in the root of a filesystem points to the root itself, which terminates an upward walk. That is the mechanism by which path resolution stops: the walk checks for .. and consults the parent link rather than a special case in the resolver. In a mount namespace the resolver applies additional rules at mount points, described in Path Resolution Component by Component, because the parent recorded on disk is not always the directory the resolver arrives from.

The presence of .. in every subdirectory explains a statistic that surprises people reading stat output: a directory with no subdirectories has a link count of two, and each subdirectory raises it by one. The count is not counting hard links in the usual sense. It is counting the entries that name the directory’s inode, and .. in each child is one such entry. Removing a subdirectory decrements the parent’s count, which is why the count can be used to estimate the number of children without reading the directory at all.

Why directories refuse hard links

A directory entry naming an inode is a hard link, and link is permitted to fail on a directory. POSIX allows an implementation to reject the operation, and Linux returns EPERM for any attempt, including by a privileged process. The reason is not that the format cannot express it. It is that the resulting graph would not be a tree.

Two links to one directory from different parents produce a directory with two distinct .. entries pointing at different places, and the on-disk .. can only hold one inode number. Even without a second link, a cycle becomes constructible: link a directory into one of its own descendants and the upward walk from below never terminates. A filesystem that permits cycles must therefore stop relying on .. and instead check every ancestor during each walk, which turns a constant-time operation into one proportional to depth. Refusing the link keeps the structure a tree and keeps the invariants that every tool assumes.

Symbolic links to directories are unrestricted, because a symbolic link is a distinct object whose target is resolved afresh on each traversal, and the resolver can bound the number of links it follows. The bound is the mechanism that makes cycles safe; it is described in the same resolution article.

Lookup cost and the indexed directory

Scanning a linear directory costs one record comparison per entry, so a lookup in a directory of ten thousand names reads on the order of ten thousand records. That is acceptable for small directories and unacceptable for the directories that hold a mail spool or a build cache.

Ext4 addresses this with a hash tree stored inside the directory’s own data blocks. The first block becomes a two-level index: the root of the index holds a hash of the name being looked up, and the index directs the search to a single leaf block whose records are scanned linearly. Lookup becomes a bounded hash probe plus a short scan, at the cost of extra complexity on every insertion that must split a leaf and grow the tree.

The index exists only if the filesystem was created with the feature and the directory is large enough to need it. A directory created on such a filesystem starts linear and is converted when it grows past a block or two. The conversion is invisible through the interface; the observable difference is the time a failed lookup takes, since a miss in a linear directory reads every record and a miss in an indexed one reads a few blocks.

Indexing changes lookup, not iteration. A reader that walks the whole directory still receives records in whatever order they occupy in the leaf blocks, and the interface for reading them has its own consistency rules, covered in Reading a Directory as a Stream: readdir and Its Weak Guarantees.

Case-insensitive lookup is a separate feature layered on the same structure. Ext4 can store a casefolded name alongside the original and hash the folded form, so that a lookup for a differently-cased name finds the entry. The entry still stores the name as created, and two names that fold to the same value are treated as the same name, which means the filesystem must reject a create whose folded form already exists. That is a compatibility decision, not a lookup optimisation: a program that assumes case sensitivity will find that two distinct filenames collide.

Names that are not names

Three strings are handled before any record is consulted. A component of exactly . refers to the directory itself and consumes no lookup. A component of exactly .. refers to the parent. An empty component, produced by a doubled slash or a trailing slash, is skipped in the middle of a path. The trailing slash is not skipped but changes the requirement: a path ending in a slash must resolve to a directory, and open of such a path with O_RDONLY on a regular file fails, reporting ENOTDIR on Linux.

Nothing else is special. A name containing a newline, a space, or a leading dash is an ordinary sequence of bytes, which is why tools that print filenames must be careful about their output and why shell globbing needs its own rules for names beginning with a dash. The only bytes a name cannot contain are the slash and the NUL. The first is the component separator, so a pathname cannot express a name containing one; the second terminates the C string the interface passes in, so a name is truncated at the first NUL and the rest of the buffer is never examined. Both limits come from the representation of the path, not from the directory format, which would happily store either byte.

Because the separator is a single reserved byte, a name can be any other byte sequence, and there is no encoding requirement. Two names that differ only in Unicode normalisation form are distinct entries, and a program that creates café from one source and looks it up from another may fail to find it. Filesystems that store a normalised form exist precisely because the interface cannot express equivalence; the ordinary case is byte comparison.

Where the directory stops and the inode begins

The entry carries the file type as a hint, and Linux uses it to avoid a disk read during readdir, but the authoritative type is in the inode’s mode word. An entry whose file_type disagrees with the inode is a corrupted directory, and filesystem checkers repair it from the inode side.

Deletion of a file touches two objects in sequence: the directory entry, which is removed or merged, and the inode, whose link count is decremented. If the count reaches zero the inode is freed, and if a process still holds the file open the data survives until the last descriptor closes. The ordering of those two steps, and what happens when they are interrupted, is what makes a directory update a crash-safety problem rather than a local edit, and it is the reason rename has its own atomicity guarantee. Both are covered in Rename Atomicity and the Replacement of a Directory Entry and Unlink While Open and the Life of an Orphaned Inode.

A directory entry also does not record the size, owner, or timestamps of its target. All of that requires reading the inode, which is a second metadata access and often a second disk read. The cost of ls -l over a large directory is therefore not the cost of reading the directory but the cost of reading one inode per entry. Sorting the list by inode number before fetching each one is an effective mitigation, because entries created together have adjacent inode numbers, and reading them in that order turns scattered metadata reads into a mostly sequential scan.