Directory Entries

directory와 classic entry 형식

ext4에서 directory는 임의의 byte string, 보통 ASCII filename을 filesystem의 inode number에 연결하는 flat file에 가깝습니다. 같은 inode number를 가리키는 directory entry가 여러 개면 hard link입니다. 다른 filesystem의 file을 hard link할 수 없는 이유도 inode number가 해당 filesystem 안에서만 의미가 있기 때문입니다.

특정 entry를 찾을 때는 directory file에 연결된 data block을 읽습니다. 기본 directory는 entry를 거의 linear array처럼 나열합니다. 다만 entry 하나를 filesystem block 경계에 걸쳐 나누지 않으므로 실제로는 여러 data block 각각에 linear entry array가 있는 구조입니다.

각 block의 array 끝은 block 끝에 도달해 알 수 있습니다. 마지막 entry의 `rec_len`이 block 끝까지 남은 공간을 모두 차지합니다. directory 전체 끝은 file 끝이고, 사용하지 않는 entry는 `inode = 0`으로 표시합니다.

기본 형식은 `struct ext4_dir_entry_2`입니다. `filetype` feature flag가 설정되지 않았을 때만 `struct ext4_dir_entry`를 사용합니다.

원래 형식인 `struct ext4_dir_entry`는 최대 263 bytes지만 실제 on-disk 길이는 `dirent.rec_len`을 봐야 합니다. `rec_len`은 4의 배수여야 합니다.

offset `0x0`의 `__le32 inode`는 entry가 가리키는 inode number, `0x4`의 `__le16 rec_len`은 entry 길이, `0x6`의 `__le16 name_len`은 filename 길이, `0x8`의 `char name[EXT4_NAME_LEN]`은 filename입니다.

filename은 255 bytes를 넘을 수 없으므로 새 형식은 `name_len`을 줄이고 남는 공간에 file type flag를 둡니다. directory traversal 때 모든 inode를 load하지 않고 type을 알기 위한 최적화입니다. 새 `ext4_dir_entry_2`도 최대 263 bytes이며 실제 길이는 `dirent.rec_len`을 사용합니다.

.. SPDX-License-Identifier: GPL-2.0

Directory Entries
-----------------

In an ext4 filesystem, a directory is more or less a flat file that maps
an arbitrary byte string (usually ASCII) to an inode number on the
filesystem. There can be many directory entries across the filesystem
that reference the same inode number--these are known as hard links, and
that is why hard links cannot reference files on other filesystems. As
such, directory entries are found by reading the data block(s)
associated with a directory file for the particular directory entry that
is desired.

Linear (Classic) Directories
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

By default, each directory lists its entries in an “almost-linear”
array. I write “almost” because it's not a linear array in the memory
sense because directory entries are not split across filesystem blocks.
Therefore, it is more accurate to say that a directory is a series of
data blocks and that each block contains a linear array of directory
entries. The end of each per-block array is signified by reaching the
end of the block; the last entry in the block has a record length that
takes it all the way to the end of the block. The end of the entire
directory is of course signified by reaching the end of the file. Unused
directory entries are signified by inode = 0. By default the filesystem
uses ``struct ext4_dir_entry_2`` for directory entries unless the
“filetype” feature flag is not set, in which case it uses
``struct ext4_dir_entry``.

The original directory entry format is ``struct ext4_dir_entry``, which
is at most 263 bytes long, though on disk you'll need to reference
``dirent.rec_len`` to know for sure.

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Size
     - Name
     - Description
   * - 0x0
     - __le32
     - inode
     - Number of the inode that this directory entry points to.
   * - 0x4
     - __le16
     - rec_len
     - Length of this directory entry. Must be a multiple of 4.
   * - 0x6
     - __le16
     - name_len
     - Length of the file name.
   * - 0x8
     - char
     - name[EXT4_NAME_LEN]
     - File name.

Since file names cannot be longer than 255 bytes, the new directory
entry format shortens the name_len field and uses the space for a file
type flag, probably to avoid having to load every inode during directory
tree traversal. This format is ``ext4_dir_entry_2``, which is at most
263 bytes long, though on disk you'll need to reference
``dirent.rec_len`` to know for sure.

file type과 encrypted+casefold extension

`ext4_dir_entry_2`의 field는 offset `0x0` `__le32 inode`, `0x4` `__le16 rec_len`, `0x6` `__u8 name_len`, `0x7` `__u8 file_type`, `0x8` `char name[EXT4_NAME_LEN]`입니다.

directory file type code는 `0x0` unknown, `0x1` regular file, `0x2` directory, `0x3` character device file, `0x4` block device file, `0x5` FIFO, `0x6` socket, `0x7` symbolic link입니다.

encrypted이면서 casefolded인 directory를 지원하려면 entry에 hash 정보도 넣어야 합니다. dot과 dotdot entry는 기존 형식을 유지하고, 나머지 `ext4_dir_entry_2`의 `name` 바로 뒤에 `ext4_extended_dir_entry_2`를 붙입니다.

extension도 `rec_len`이 나타내는 크기에 포함됩니다. extension을 쓰는 directory entry의 최대 크기는 271 bytes입니다.

`ext4_extended_dir_entry_2`의 offset `0x0` `__le32 hash`는 directory name hash이고, offset `0x4` `__le32 minor_hash`는 directory name의 minor hash입니다.

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Size
     - Name
     - Description
   * - 0x0
     - __le32
     - inode
     - Number of the inode that this directory entry points to.
   * - 0x4
     - __le16
     - rec_len
     - Length of this directory entry.
   * - 0x6
     - __u8
     - name_len
     - Length of the file name.
   * - 0x7
     - __u8
     - file_type
     - File type code, see ftype_ table below.
   * - 0x8
     - char
     - name[EXT4_NAME_LEN]
     - File name.

.. _ftype:

The directory file type is one of the following values:

.. list-table::
   :widths: 16 64
   :header-rows: 1

   * - Value
     - Description
   * - 0x0
     - Unknown.
   * - 0x1
     - Regular file.
   * - 0x2
     - Directory.
   * - 0x3
     - Character device file.
   * - 0x4
     - Block device file.
   * - 0x5
     - FIFO.
   * - 0x6
     - Socket.
   * - 0x7
     - Symbolic link.

To support directories that are both encrypted and casefolded directories, we
must also include hash information in the directory entry. We append
``ext4_extended_dir_entry_2`` to ``ext4_dir_entry_2`` except for the entries
for dot and dotdot, which are kept the same. The structure follows immediately
after ``name`` and is included in the size listed by ``rec_len`` If a directory
entry uses this extension, it may be up to 271 bytes.

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Size
     - Name
     - Description
   * - 0x0
     - __le32
     - hash
     - The hash of the directory name
   * - 0x4
     - __le32
     - minor_hash
     - The minor hash of the directory name

classic leaf block checksum tail

classic directory block에 checksum을 추가할 때 각 leaf block 끝에 가짜 `struct ext4_dir_entry`를 둡니다. 이 12-byte entry가 checksum을 담습니다.

오래된 software가 빈 entry로 보고 무시하도록 inode number와 `name_len`을 0으로 설정합니다. 평소 name이 있는 위치에 checksum을 저장하며 실제 structure 이름은 `struct ext4_dir_entry_tail`입니다.

offset `0x0`의 `__le32 det_reserved_zero1`은 반드시 0인 inode number입니다. `0x4`의 `__le16 det_rec_len`은 반드시 12인 entry 길이입니다.

offset `0x6`의 `__u8 det_reserved_zero2`는 반드시 0인 filename 길이입니다. `0x7`의 `__u8 det_reserved_ft`는 반드시 `0xDE`인 file type입니다. `0x8`의 `__le32 det_checksum`은 directory leaf block checksum입니다.

leaf checksum은 filesystem checksum seed feature가 있으면 checksum seed를, 아니면 FS UUID를 사용합니다. 여기에 directory inode number, inode generation number, fake directory entry 직전까지의 directory entry block 전체를 결합해 계산합니다.

In order to add checksums to these classic directory blocks, a phony
``struct ext4_dir_entry`` is placed at the end of each leaf block to
hold the checksum. The directory entry is 12 bytes long. The inode
number and name_len fields are set to zero to fool old software into
ignoring an apparently empty directory entry, and the checksum is stored
in the place where the name normally goes. The structure is
``struct ext4_dir_entry_tail``:

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Size
     - Name
     - Description
   * - 0x0
     - __le32
     - det_reserved_zero1
     - Inode number, which must be zero.
   * - 0x4
     - __le16
     - det_rec_len
     - Length of this directory entry, which must be 12.
   * - 0x6
     - __u8
     - det_reserved_zero2
     - Length of the file name, which must be zero.
   * - 0x7
     - __u8
     - det_reserved_ft
     - File type, which must be 0xDE.
   * - 0x8
     - __le32
     - det_checksum
     - Directory leaf block checksum.

The leaf directory block checksum is calculated against the FS UUID (or
the checksum seed, if that feature is enabled for the fs), the directory's
inode number, the directory's inode generation number, and the entire
directory entry block up to (but not including) the fake directory entry.

hash tree directory 구성과 탐색

linear directory array의 성능 한계를 줄이기 위해 ext3부터 directory name hash를 key로 쓰는 빠른 balanced tree가 추가됐습니다. inode에 `EXT4_INDEX_FL (0x1000)`이 설정되면 해당 directory는 hashed btree인 htree로 entry를 조직하고 찾습니다.

ext2와의 read-only 호환성을 위해 interior tree node는 directory file 안에서 block 전체를 차지하는 빈 directory entry처럼 숨습니다. `inode = 0`인 entry를 unused로 건너뛰는 오래된 linear scan 동작을 이용해 interior node data를 감춥니다.

tree root는 항상 directory 첫 data block에 있습니다. ext2 관례에 따라 `.`과 `..` entry는 첫 block 시작에 `struct ext4_dir_entry_2` 두 개로 저장하고 tree에는 넣지 않습니다.

root의 나머지는 tree metadata와 lower htree node를 찾는 hash-to-block map입니다. `dx_root.info.indirect_levels`가 0이 아니면 그 수만큼 level이 있고 root map이 interior node를 가리킵니다.

interior node는 0으로 채운 `struct ext4_dir_entry_2` 뒤에 다음 level을 찾는 hash-to-block map을 둡니다. leaf node는 classic linear directory block처럼 보이지만 모든 entry hash가 parent node에 표시된 hash 이상입니다.

entry name의 실제 hash는 31 bit이고 least-significant bit는 0입니다. 같은 hash의 entry들이 leaf 하나에 들어가지 않아 여러 node로 갈라질 때 interior node의 least-significant bit를 1로 설정할 수 있습니다.

lookup은 filename hash를 계산해 해당 hash range를 담당하는 leaf node를 찾습니다. B-Tree hash lookup과 비슷하며 collision이 있으면 tree 순서상 뒤따르는 leaf도 scan할 수 있습니다.

오래된 code처럼 directory를 linear traversal할 때는 모든 data block을 읽습니다. htree block은 `.`과 `..` 외에는 entry가 없는 것처럼 보여 leaf node만 실제 content를 가진 것으로 나타납니다.

Hash Tree Directories
~~~~~~~~~~~~~~~~~~~~~

A linear array of directory entries isn't great for performance, so a
new feature was added to ext3 to provide a faster (but peculiar)
balanced tree keyed off a hash of the directory entry name. If the
EXT4_INDEX_FL (0x1000) flag is set in the inode, this directory uses a
hashed btree (htree) to organize and find directory entries. For
backwards read-only compatibility with ext2, interior tree nodes are actually
hidden inside the directory file, masquerading as “empty” directory entries
spanning the whole block. It was stated previously that directory entries
with the inode set to 0 are treated as unused entries; this is (ab)used to
fool the old linear-scan algorithm into skipping over those blocks containing
the interior tree node data.

The root of the tree always lives in the first data block of the
directory. By ext2 custom, the '.' and '..' entries must appear at the
beginning of this first block, so they are put here as two
``struct ext4_dir_entry_2`` s and not stored in the tree. The rest of
the root node contains metadata about the tree and finally a hash->block
map to find nodes that are lower in the htree. If
``dx_root.info.indirect_levels`` is non-zero then the htree has that many
levels and the blocks pointed to by the root node's map are interior nodes.
These interior nodes have a zeroed out ``struct ext4_dir_entry_2`` followed by
a hash->block map to find nodes of the next level. Leaf nodes look like
classic linear directory blocks, but all of its entries have a hash value
equal or greater than the indicated hash of the parent node.

The actual hash value for an entry name is only 31 bits, the least-significant
bit is set to 0. However, if there is a hash collision between directory
entries, the least-significant bit may get set to 1 on interior nodes in the
case where these two (or more) hash-colliding entries do not fit into one leaf
node and must be split across multiple nodes.

To look up a name in such a htree, the code calculates the hash of the desired
file name and uses it to find the leaf node with the range of hash values the
calculated hash falls into (in other words, a lookup works basically the same
as it would in a B-Tree keyed by the hash value), and possibly also scanning
the leaf nodes that follow (in tree order) in case of hash collisions.

To traverse the directory as a linear array (such as the old code does),
the code simply reads every data block in the directory. The blocks used
for the htree will appear to have no entries (aside from '.' and '..')
and so only the leaf nodes will appear to have any interesting content.

`struct dx_root` field

htree root는 data block 전체 길이의 `struct dx_root`입니다. 앞부분에는 `.`과 `..` entry가 있고 뒤에 `dx_root_info`, entry count header, left-most leaf와 추가 `dx_entry` 배열이 이어집니다.

`.` entry는 offset `0x0` `dot.inode`, `0x4` 길이 12인 `dot.rec_len`, `0x6` 길이 1인 `dot.name_len`, `0x7` directory code `0x2`인 `dot.file_type`, `0x8`의 `dot.name[4]` 값 `".\0\0\0"`입니다.

`..` entry는 `0xC` `dotdot.inode`, `0x10` `dotdot.rec_len = block_size - 12`, `0x12` name length 2, `0x13` directory code `0x2`, `0x14` `dotdot_name[4] = "..\0\0"`입니다. 긴 `dotdot.rec_len`이 나머지 htree data를 모두 덮습니다.

`dx_root_info`는 `0x18`의 0인 `reserved_zero`, `0x1C`의 `hash_version`, `0x1D`의 `info_length = 0x8`, `0x1E`의 `indirect_levels`, `0x1F`의 `unused_flags`로 구성됩니다.

htree depth인 `indirect_levels`는 `INCOMPAT_LARGEDIR` feature가 있으면 최대 3, 없으면 최대 2입니다.

offset `0x20`의 `__le16 limit`은 header 자신을 위한 1을 포함한 최대 `dx_entry` 수이고 `0x22`의 `__le16 count`는 header 1을 포함한 실제 entry 수입니다.

offset `0x24`의 `__le32 block`은 가장 낮은 hash entry를 담는 left-most leaf로 이어지는 directory file 내부 block number입니다. `0x28`부터 남은 data block에 들어갈 만큼 8-byte `struct dx_entry entries[0]`가 이어집니다.

The root of the htree is in ``struct dx_root``, which is the full length
of a data block:

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - __le32
     - dot.inode
     - inode number of this directory.
   * - 0x4
     - __le16
     - dot.rec_len
     - Length of this record, 12.
   * - 0x6
     - u8
     - dot.name_len
     - Length of the name, 1.
   * - 0x7
     - u8
     - dot.file_type
     - File type of this entry, 0x2 (directory) (if the feature flag is set).
   * - 0x8
     - char
     - dot.name[4]
     - “.\0\0\0”
   * - 0xC
     - __le32
     - dotdot.inode
     - inode number of parent directory.
   * - 0x10
     - __le16
     - dotdot.rec_len
     - block_size - 12. The record length is long enough to cover all htree
       data.
   * - 0x12
     - u8
     - dotdot.name_len
     - Length of the name, 2.
   * - 0x13
     - u8
     - dotdot.file_type
     - File type of this entry, 0x2 (directory) (if the feature flag is set).
   * - 0x14
     - char
     - dotdot_name[4]
     - “..\0\0”
   * - 0x18
     - __le32
     - struct dx_root_info.reserved_zero
     - Zero.
   * - 0x1C
     - u8
     - struct dx_root_info.hash_version
     - Hash type, see dirhash_ table below.
   * - 0x1D
     - u8
     - struct dx_root_info.info_length
     - Length of the tree information, 0x8.
   * - 0x1E
     - u8
     - struct dx_root_info.indirect_levels
     - Depth of the htree. Cannot be larger than 3 if the INCOMPAT_LARGEDIR
       feature is set; cannot be larger than 2 otherwise.
   * - 0x1F
     - u8
     - struct dx_root_info.unused_flags
     -
   * - 0x20
     - __le16
     - limit
     - Maximum number of dx_entries that can follow this header, plus 1 for
       the header itself.
   * - 0x22
     - __le16
     - count
     - Actual number of dx_entries that follow this header, plus 1 for the
       header itself.
   * - 0x24
     - __le32
     - block
     - The block number (within the directory file) that lead to the left-most
       leaf node, i.e. the leaf containing entries with the lowest hash values.
   * - 0x28
     - struct dx_entry
     - entries[0]
     - As many 8-byte ``struct dx_entry`` as fits in the rest of the data block.

hash version과 `struct dx_node`

directory hash version은 `0x0` Legacy, `0x1` Half MD4, `0x2` Tea, `0x3` Legacy unsigned, `0x4` Half MD4 unsigned, `0x5` Tea unsigned, `0x6` Siphash입니다.

htree interior node는 data block 전체 길이의 `struct dx_node`입니다. 시작 부분을 사용하지 않는 directory entry처럼 만들어 old linear scanner가 block 전체를 건너뛰게 합니다.

offset `0x0`의 `__le32 fake.inode`는 0입니다. `0x4`의 `__le16 fake.rec_len`은 모든 dx_node data를 숨기도록 block size 전체입니다. `0x6` `name_len`과 `0x7` `file_type`도 0입니다.

offset `0x8`의 `__le16 limit`은 header 1을 포함한 최대 `dx_entry` 수이고 `0xA`의 `__le16 count`는 header 1을 포함한 실제 수입니다.

offset `0xE`의 `__le32 block`은 이 node의 가장 낮은 hash 값과 연결되는 directory file 내부 block number이며 parent block에 저장되는 값입니다. `0x12`부터 8-byte `struct dx_entry entries[0]`가 block 나머지를 채웁니다.

.. _dirhash:

The directory hash is one of the following values:

.. list-table::
   :widths: 16 64
   :header-rows: 1

   * - Value
     - Description
   * - 0x0
     - Legacy.
   * - 0x1
     - Half MD4.
   * - 0x2
     - Tea.
   * - 0x3
     - Legacy, unsigned.
   * - 0x4
     - Half MD4, unsigned.
   * - 0x5
     - Tea, unsigned.
   * - 0x6
     - Siphash.

Interior nodes of an htree are recorded as ``struct dx_node``, which is
also the full length of a data block:

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - __le32
     - fake.inode
     - Zero, to make it look like this entry is not in use.
   * - 0x4
     - __le16
     - fake.rec_len
     - The size of the block, in order to hide all of the dx_node data.
   * - 0x6
     - u8
     - name_len
     - Zero. There is no name for this “unused” directory entry.
   * - 0x7
     - u8
     - file_type
     - Zero. There is no file type for this “unused” directory entry.
   * - 0x8
     - __le16
     - limit
     - Maximum number of dx_entries that can follow this header, plus 1 for
       the header itself.
   * - 0xA
     - __le16
     - count
     - Actual number of dx_entries that follow this header, plus 1 for the
       header itself.
   * - 0xE
     - __le32
     - block
     - The block number (within the directory file) that goes with the lowest
       hash value of this block. This value is stored in the parent block.
   * - 0x12
     - struct dx_entry
     - entries[0]
     - As many 8-byte ``struct dx_entry`` as fits in the rest of the data block.

`dx_entry` map과 htree checksum tail

`struct dx_root`와 `struct dx_node`의 hash map entry는 8-byte `struct dx_entry`입니다. offset `0x0`의 `__le32 hash`는 hash code이고 `0x4`의 `__le32 block`은 htree의 다음 node가 있는 directory file 내부 block number입니다. filesystem 전체 block number가 아닙니다.

metadata checksum이 활성화되면 directory block 마지막 8 bytes, 즉 `dx_entry` 하나의 길이를 `struct dx_tail`에 사용합니다. `dx_root`와 `dx_node`의 `limit` 및 `count`를 tail이 들어가도록 조정합니다.

`dx_tail` 공간이 없으면 user에게 `e2fsck -D`로 directory index를 다시 만들어 checksum 공간을 확보하라고 알립니다.

8-byte `struct dx_tail`의 offset `0x0` `u32 dt_reserved`는 사용하지 않지만 checksum 계산에는 포함합니다. offset `0x4` `__le32 dt_checksum`은 htree directory block checksum입니다.

checksum 입력은 FS UUID, htree index header인 `dx_root` 또는 `dx_node`, 사용 중인 모든 htree index `dx_entry`, 그리고 `dt_checksum`을 처음에 0으로 둔 `dx_tail`입니다.

The hash maps that exist in both ``struct dx_root`` and
``struct dx_node`` are recorded as ``struct dx_entry``, which is 8 bytes
long:

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - __le32
     - hash
     - Hash code.
   * - 0x4
     - __le32
     - block
     - Block number (within the directory file, not filesystem blocks) of the
       next node in the htree.

(If you think this is all quite clever and peculiar, so does the
author.)

If metadata checksums are enabled, the last 8 bytes of the directory
block (precisely the length of one dx_entry) are used to store a
``struct dx_tail``, which contains the checksum. The ``limit`` and
``count`` entries in the dx_root/dx_node structures are adjusted as
necessary to fit the dx_tail into the block. If there is no space for
the dx_tail, the user is notified to run e2fsck -D to rebuild the
directory index (which will ensure that there's space for the checksum.
The dx_tail structure is 8 bytes long and looks like this:

.. list-table::
   :widths: 8 8 24 40
   :header-rows: 1

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - u32
     - dt_reserved
     - Unused (but still part of the checksum curiously).
   * - 0x4
     - __le32
     - dt_checksum
     - Checksum of the htree directory block.

The checksum is calculated against the FS UUID, the htree index header
(dx_root or dx_node), all of the htree indices (dx_entry) that are in
use, and the tail block (dx_tail) with the dt_checksum initially set to 0.