454 lines · plain
1.. SPDX-License-Identifier: GPL-2.02 3Directory Entries4-----------------5 6In an ext4 filesystem, a directory is more or less a flat file that maps7an arbitrary byte string (usually ASCII) to an inode number on the8filesystem. There can be many directory entries across the filesystem9that reference the same inode number--these are known as hard links, and10that is why hard links cannot reference files on other filesystems. As11such, directory entries are found by reading the data block(s)12associated with a directory file for the particular directory entry that13is desired.14 15Linear (Classic) Directories16~~~~~~~~~~~~~~~~~~~~~~~~~~~~17 18By default, each directory lists its entries in an “almost-linear”19array. I write “almost” because it's not a linear array in the memory20sense because directory entries are not split across filesystem blocks.21Therefore, it is more accurate to say that a directory is a series of22data blocks and that each block contains a linear array of directory23entries. The end of each per-block array is signified by reaching the24end of the block; the last entry in the block has a record length that25takes it all the way to the end of the block. The end of the entire26directory is of course signified by reaching the end of the file. Unused27directory entries are signified by inode = 0. By default the filesystem28uses ``struct ext4_dir_entry_2`` for directory entries unless the29“filetype” feature flag is not set, in which case it uses30``struct ext4_dir_entry``.31 32The original directory entry format is ``struct ext4_dir_entry``, which33is at most 263 bytes long, though on disk you'll need to reference34``dirent.rec_len`` to know for sure.35 36.. list-table::37 :widths: 8 8 24 4038 :header-rows: 139 40 * - Offset41 - Size42 - Name43 - Description44 * - 0x045 - __le3246 - inode47 - Number of the inode that this directory entry points to.48 * - 0x449 - __le1650 - rec_len51 - Length of this directory entry. Must be a multiple of 4.52 * - 0x653 - __le1654 - name_len55 - Length of the file name.56 * - 0x857 - char58 - name[EXT4_NAME_LEN]59 - File name.60 61Since file names cannot be longer than 255 bytes, the new directory62entry format shortens the name_len field and uses the space for a file63type flag, probably to avoid having to load every inode during directory64tree traversal. This format is ``ext4_dir_entry_2``, which is at most65263 bytes long, though on disk you'll need to reference66``dirent.rec_len`` to know for sure.67 68.. list-table::69 :widths: 8 8 24 4070 :header-rows: 171 72 * - Offset73 - Size74 - Name75 - Description76 * - 0x077 - __le3278 - inode79 - Number of the inode that this directory entry points to.80 * - 0x481 - __le1682 - rec_len83 - Length of this directory entry.84 * - 0x685 - __u886 - name_len87 - Length of the file name.88 * - 0x789 - __u890 - file_type91 - File type code, see ftype_ table below.92 * - 0x893 - char94 - name[EXT4_NAME_LEN]95 - File name.96 97.. _ftype:98 99The directory file type is one of the following values:100 101.. list-table::102 :widths: 16 64103 :header-rows: 1104 105 * - Value106 - Description107 * - 0x0108 - Unknown.109 * - 0x1110 - Regular file.111 * - 0x2112 - Directory.113 * - 0x3114 - Character device file.115 * - 0x4116 - Block device file.117 * - 0x5118 - FIFO.119 * - 0x6120 - Socket.121 * - 0x7122 - Symbolic link.123 124To support directories that are both encrypted and casefolded directories, we125must also include hash information in the directory entry. We append126``ext4_extended_dir_entry_2`` to ``ext4_dir_entry_2`` except for the entries127for dot and dotdot, which are kept the same. The structure follows immediately128after ``name`` and is included in the size listed by ``rec_len`` If a directory129entry uses this extension, it may be up to 271 bytes.130 131.. list-table::132 :widths: 8 8 24 40133 :header-rows: 1134 135 * - Offset136 - Size137 - Name138 - Description139 * - 0x0140 - __le32141 - hash142 - The hash of the directory name143 * - 0x4144 - __le32145 - minor_hash146 - The minor hash of the directory name147 148 149In order to add checksums to these classic directory blocks, a phony150``struct ext4_dir_entry`` is placed at the end of each leaf block to151hold the checksum. The directory entry is 12 bytes long. The inode152number and name_len fields are set to zero to fool old software into153ignoring an apparently empty directory entry, and the checksum is stored154in the place where the name normally goes. The structure is155``struct ext4_dir_entry_tail``:156 157.. list-table::158 :widths: 8 8 24 40159 :header-rows: 1160 161 * - Offset162 - Size163 - Name164 - Description165 * - 0x0166 - __le32167 - det_reserved_zero1168 - Inode number, which must be zero.169 * - 0x4170 - __le16171 - det_rec_len172 - Length of this directory entry, which must be 12.173 * - 0x6174 - __u8175 - det_reserved_zero2176 - Length of the file name, which must be zero.177 * - 0x7178 - __u8179 - det_reserved_ft180 - File type, which must be 0xDE.181 * - 0x8182 - __le32183 - det_checksum184 - Directory leaf block checksum.185 186The leaf directory block checksum is calculated against the FS UUID, the187directory's inode number, the directory's inode generation number, and188the entire directory entry block up to (but not including) the fake189directory entry.190 191Hash Tree Directories192~~~~~~~~~~~~~~~~~~~~~193 194A linear array of directory entries isn't great for performance, so a195new feature was added to ext3 to provide a faster (but peculiar)196balanced tree keyed off a hash of the directory entry name. If the197EXT4_INDEX_FL (0x1000) flag is set in the inode, this directory uses a198hashed btree (htree) to organize and find directory entries. For199backwards read-only compatibility with ext2, this tree is actually200hidden inside the directory file, masquerading as “empty” directory data201blocks! It was stated previously that the end of the linear directory202entry table was signified with an entry pointing to inode 0; this is203(ab)used to fool the old linear-scan algorithm into thinking that the204rest of the directory block is empty so that it moves on.205 206The root of the tree always lives in the first data block of the207directory. By ext2 custom, the '.' and '..' entries must appear at the208beginning of this first block, so they are put here as two209``struct ext4_dir_entry_2`` s and not stored in the tree. The rest of210the root node contains metadata about the tree and finally a hash->block211map to find nodes that are lower in the htree. If212``dx_root.info.indirect_levels`` is non-zero then the htree has two213levels; the data block pointed to by the root node's map is an interior214node, which is indexed by a minor hash. Interior nodes in this tree215contains a zeroed out ``struct ext4_dir_entry_2`` followed by a216minor_hash->block map to find leafe nodes. Leaf nodes contain a linear217array of all ``struct ext4_dir_entry_2``; all of these entries218(presumably) hash to the same value. If there is an overflow, the219entries simply overflow into the next leaf node, and the220least-significant bit of the hash (in the interior node map) that gets221us to this next leaf node is set.222 223To traverse the directory as a htree, the code calculates the hash of224the desired file name and uses it to find the corresponding block225number. If the tree is flat, the block is a linear array of directory226entries that can be searched; otherwise, the minor hash of the file name227is computed and used against this second block to find the corresponding228third block number. That third block number will be a linear array of229directory entries.230 231To traverse the directory as a linear array (such as the old code does),232the code simply reads every data block in the directory. The blocks used233for the htree will appear to have no entries (aside from '.' and '..')234and so only the leaf nodes will appear to have any interesting content.235 236The root of the htree is in ``struct dx_root``, which is the full length237of a data block:238 239.. list-table::240 :widths: 8 8 24 40241 :header-rows: 1242 243 * - Offset244 - Type245 - Name246 - Description247 * - 0x0248 - __le32249 - dot.inode250 - inode number of this directory.251 * - 0x4252 - __le16253 - dot.rec_len254 - Length of this record, 12.255 * - 0x6256 - u8257 - dot.name_len258 - Length of the name, 1.259 * - 0x7260 - u8261 - dot.file_type262 - File type of this entry, 0x2 (directory) (if the feature flag is set).263 * - 0x8264 - char265 - dot.name[4]266 - “.\0\0\0”267 * - 0xC268 - __le32269 - dotdot.inode270 - inode number of parent directory.271 * - 0x10272 - __le16273 - dotdot.rec_len274 - block_size - 12. The record length is long enough to cover all htree275 data.276 * - 0x12277 - u8278 - dotdot.name_len279 - Length of the name, 2.280 * - 0x13281 - u8282 - dotdot.file_type283 - File type of this entry, 0x2 (directory) (if the feature flag is set).284 * - 0x14285 - char286 - dotdot_name[4]287 - “..\0\0”288 * - 0x18289 - __le32290 - struct dx_root_info.reserved_zero291 - Zero.292 * - 0x1C293 - u8294 - struct dx_root_info.hash_version295 - Hash type, see dirhash_ table below.296 * - 0x1D297 - u8298 - struct dx_root_info.info_length299 - Length of the tree information, 0x8.300 * - 0x1E301 - u8302 - struct dx_root_info.indirect_levels303 - Depth of the htree. Cannot be larger than 3 if the INCOMPAT_LARGEDIR304 feature is set; cannot be larger than 2 otherwise.305 * - 0x1F306 - u8307 - struct dx_root_info.unused_flags308 -309 * - 0x20310 - __le16311 - limit312 - Maximum number of dx_entries that can follow this header, plus 1 for313 the header itself.314 * - 0x22315 - __le16316 - count317 - Actual number of dx_entries that follow this header, plus 1 for the318 header itself.319 * - 0x24320 - __le32321 - block322 - The block number (within the directory file) that goes with hash=0.323 * - 0x28324 - struct dx_entry325 - entries[0]326 - As many 8-byte ``struct dx_entry`` as fits in the rest of the data block.327 328.. _dirhash:329 330The directory hash is one of the following values:331 332.. list-table::333 :widths: 16 64334 :header-rows: 1335 336 * - Value337 - Description338 * - 0x0339 - Legacy.340 * - 0x1341 - Half MD4.342 * - 0x2343 - Tea.344 * - 0x3345 - Legacy, unsigned.346 * - 0x4347 - Half MD4, unsigned.348 * - 0x5349 - Tea, unsigned.350 * - 0x6351 - Siphash.352 353Interior nodes of an htree are recorded as ``struct dx_node``, which is354also the full length of a data block:355 356.. list-table::357 :widths: 8 8 24 40358 :header-rows: 1359 360 * - Offset361 - Type362 - Name363 - Description364 * - 0x0365 - __le32366 - fake.inode367 - Zero, to make it look like this entry is not in use.368 * - 0x4369 - __le16370 - fake.rec_len371 - The size of the block, in order to hide all of the dx_node data.372 * - 0x6373 - u8374 - name_len375 - Zero. There is no name for this “unused” directory entry.376 * - 0x7377 - u8378 - file_type379 - Zero. There is no file type for this “unused” directory entry.380 * - 0x8381 - __le16382 - limit383 - Maximum number of dx_entries that can follow this header, plus 1 for384 the header itself.385 * - 0xA386 - __le16387 - count388 - Actual number of dx_entries that follow this header, plus 1 for the389 header itself.390 * - 0xE391 - __le32392 - block393 - The block number (within the directory file) that goes with the lowest394 hash value of this block. This value is stored in the parent block.395 * - 0x12396 - struct dx_entry397 - entries[0]398 - As many 8-byte ``struct dx_entry`` as fits in the rest of the data block.399 400The hash maps that exist in both ``struct dx_root`` and401``struct dx_node`` are recorded as ``struct dx_entry``, which is 8 bytes402long:403 404.. list-table::405 :widths: 8 8 24 40406 :header-rows: 1407 408 * - Offset409 - Type410 - Name411 - Description412 * - 0x0413 - __le32414 - hash415 - Hash code.416 * - 0x4417 - __le32418 - block419 - Block number (within the directory file, not filesystem blocks) of the420 next node in the htree.421 422(If you think this is all quite clever and peculiar, so does the423author.)424 425If metadata checksums are enabled, the last 8 bytes of the directory426block (precisely the length of one dx_entry) are used to store a427``struct dx_tail``, which contains the checksum. The ``limit`` and428``count`` entries in the dx_root/dx_node structures are adjusted as429necessary to fit the dx_tail into the block. If there is no space for430the dx_tail, the user is notified to run e2fsck -D to rebuild the431directory index (which will ensure that there's space for the checksum.432The dx_tail structure is 8 bytes long and looks like this:433 434.. list-table::435 :widths: 8 8 24 40436 :header-rows: 1437 438 * - Offset439 - Type440 - Name441 - Description442 * - 0x0443 - u32444 - dt_reserved445 - Zero.446 * - 0x4447 - __le32448 - dt_checksum449 - Checksum of the htree directory block.450 451The checksum is calculated against the FS UUID, the htree index header452(dx_root or dx_node), all of the htree indices (dx_entry) that are in453use, and the tail block (dx_tail).454