directory.rst 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453
  1. .. SPDX-License-Identifier: GPL-2.0
  2. Directory Entries
  3. -----------------
  4. In an ext4 filesystem, a directory is more or less a flat file that maps
  5. an arbitrary byte string (usually ASCII) to an inode number on the
  6. filesystem. There can be many directory entries across the filesystem
  7. that reference the same inode number--these are known as hard links, and
  8. that is why hard links cannot reference files on other filesystems. As
  9. such, directory entries are found by reading the data block(s)
  10. associated with a directory file for the particular directory entry that
  11. is desired.
  12. Linear (Classic) Directories
  13. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  14. By default, each directory lists its entries in an “almost-linear”
  15. array. I write “almost” because it's not a linear array in the memory
  16. sense because directory entries are not split across filesystem blocks.
  17. Therefore, it is more accurate to say that a directory is a series of
  18. data blocks and that each block contains a linear array of directory
  19. entries. The end of each per-block array is signified by reaching the
  20. end of the block; the last entry in the block has a record length that
  21. takes it all the way to the end of the block. The end of the entire
  22. directory is of course signified by reaching the end of the file. Unused
  23. directory entries are signified by inode = 0. By default the filesystem
  24. uses ``struct ext4_dir_entry_2`` for directory entries unless the
  25. “filetype” feature flag is not set, in which case it uses
  26. ``struct ext4_dir_entry``.
  27. The original directory entry format is ``struct ext4_dir_entry``, which
  28. is at most 263 bytes long, though on disk you'll need to reference
  29. ``dirent.rec_len`` to know for sure.
  30. .. list-table::
  31. :widths: 8 8 24 40
  32. :header-rows: 1
  33. * - Offset
  34. - Size
  35. - Name
  36. - Description
  37. * - 0x0
  38. - \_\_le32
  39. - inode
  40. - Number of the inode that this directory entry points to.
  41. * - 0x4
  42. - \_\_le16
  43. - rec\_len
  44. - Length of this directory entry. Must be a multiple of 4.
  45. * - 0x6
  46. - \_\_le16
  47. - name\_len
  48. - Length of the file name.
  49. * - 0x8
  50. - char
  51. - name[EXT4\_NAME\_LEN]
  52. - File name.
  53. Since file names cannot be longer than 255 bytes, the new directory
  54. entry format shortens the name\_len field and uses the space for a file
  55. type flag, probably to avoid having to load every inode during directory
  56. tree traversal. This format is ``ext4_dir_entry_2``, which is at most
  57. 263 bytes long, though on disk you'll need to reference
  58. ``dirent.rec_len`` to know for sure.
  59. .. list-table::
  60. :widths: 8 8 24 40
  61. :header-rows: 1
  62. * - Offset
  63. - Size
  64. - Name
  65. - Description
  66. * - 0x0
  67. - \_\_le32
  68. - inode
  69. - Number of the inode that this directory entry points to.
  70. * - 0x4
  71. - \_\_le16
  72. - rec\_len
  73. - Length of this directory entry.
  74. * - 0x6
  75. - \_\_u8
  76. - name\_len
  77. - Length of the file name.
  78. * - 0x7
  79. - \_\_u8
  80. - file\_type
  81. - File type code, see ftype_ table below.
  82. * - 0x8
  83. - char
  84. - name[EXT4\_NAME\_LEN]
  85. - File name.
  86. .. _ftype:
  87. The directory file type is one of the following values:
  88. .. list-table::
  89. :widths: 16 64
  90. :header-rows: 1
  91. * - Value
  92. - Description
  93. * - 0x0
  94. - Unknown.
  95. * - 0x1
  96. - Regular file.
  97. * - 0x2
  98. - Directory.
  99. * - 0x3
  100. - Character device file.
  101. * - 0x4
  102. - Block device file.
  103. * - 0x5
  104. - FIFO.
  105. * - 0x6
  106. - Socket.
  107. * - 0x7
  108. - Symbolic link.
  109. To support directories that are both encrypted and casefolded directories, we
  110. must also include hash information in the directory entry. We append
  111. ``ext4_extended_dir_entry_2`` to ``ext4_dir_entry_2`` except for the entries
  112. for dot and dotdot, which are kept the same. The structure follows immediately
  113. after ``name`` and is included in the size listed by ``rec_len`` If a directory
  114. entry uses this extension, it may be up to 271 bytes.
  115. .. list-table::
  116. :widths: 8 8 24 40
  117. :header-rows: 1
  118. * - Offset
  119. - Size
  120. - Name
  121. - Description
  122. * - 0x0
  123. - \_\_le32
  124. - hash
  125. - The hash of the directory name
  126. * - 0x4
  127. - \_\_le32
  128. - minor\_hash
  129. - The minor hash of the directory name
  130. In order to add checksums to these classic directory blocks, a phony
  131. ``struct ext4_dir_entry`` is placed at the end of each leaf block to
  132. hold the checksum. The directory entry is 12 bytes long. The inode
  133. number and name\_len fields are set to zero to fool old software into
  134. ignoring an apparently empty directory entry, and the checksum is stored
  135. in the place where the name normally goes. The structure is
  136. ``struct ext4_dir_entry_tail``:
  137. .. list-table::
  138. :widths: 8 8 24 40
  139. :header-rows: 1
  140. * - Offset
  141. - Size
  142. - Name
  143. - Description
  144. * - 0x0
  145. - \_\_le32
  146. - det\_reserved\_zero1
  147. - Inode number, which must be zero.
  148. * - 0x4
  149. - \_\_le16
  150. - det\_rec\_len
  151. - Length of this directory entry, which must be 12.
  152. * - 0x6
  153. - \_\_u8
  154. - det\_reserved\_zero2
  155. - Length of the file name, which must be zero.
  156. * - 0x7
  157. - \_\_u8
  158. - det\_reserved\_ft
  159. - File type, which must be 0xDE.
  160. * - 0x8
  161. - \_\_le32
  162. - det\_checksum
  163. - Directory leaf block checksum.
  164. The leaf directory block checksum is calculated against the FS UUID, the
  165. directory's inode number, the directory's inode generation number, and
  166. the entire directory entry block up to (but not including) the fake
  167. directory entry.
  168. Hash Tree Directories
  169. ~~~~~~~~~~~~~~~~~~~~~
  170. A linear array of directory entries isn't great for performance, so a
  171. new feature was added to ext3 to provide a faster (but peculiar)
  172. balanced tree keyed off a hash of the directory entry name. If the
  173. EXT4\_INDEX\_FL (0x1000) flag is set in the inode, this directory uses a
  174. hashed btree (htree) to organize and find directory entries. For
  175. backwards read-only compatibility with ext2, this tree is actually
  176. hidden inside the directory file, masquerading as “empty” directory data
  177. blocks! It was stated previously that the end of the linear directory
  178. entry table was signified with an entry pointing to inode 0; this is
  179. (ab)used to fool the old linear-scan algorithm into thinking that the
  180. rest of the directory block is empty so that it moves on.
  181. The root of the tree always lives in the first data block of the
  182. directory. By ext2 custom, the '.' and '..' entries must appear at the
  183. beginning of this first block, so they are put here as two
  184. ``struct ext4_dir_entry_2``\ s and not stored in the tree. The rest of
  185. the root node contains metadata about the tree and finally a hash->block
  186. map to find nodes that are lower in the htree. If
  187. ``dx_root.info.indirect_levels`` is non-zero then the htree has two
  188. levels; the data block pointed to by the root node's map is an interior
  189. node, which is indexed by a minor hash. Interior nodes in this tree
  190. contains a zeroed out ``struct ext4_dir_entry_2`` followed by a
  191. minor\_hash->block map to find leafe nodes. Leaf nodes contain a linear
  192. array of all ``struct ext4_dir_entry_2``; all of these entries
  193. (presumably) hash to the same value. If there is an overflow, the
  194. entries simply overflow into the next leaf node, and the
  195. least-significant bit of the hash (in the interior node map) that gets
  196. us to this next leaf node is set.
  197. To traverse the directory as a htree, the code calculates the hash of
  198. the desired file name and uses it to find the corresponding block
  199. number. If the tree is flat, the block is a linear array of directory
  200. entries that can be searched; otherwise, the minor hash of the file name
  201. is computed and used against this second block to find the corresponding
  202. third block number. That third block number will be a linear array of
  203. directory entries.
  204. To traverse the directory as a linear array (such as the old code does),
  205. the code simply reads every data block in the directory. The blocks used
  206. for the htree will appear to have no entries (aside from '.' and '..')
  207. and so only the leaf nodes will appear to have any interesting content.
  208. The root of the htree is in ``struct dx_root``, which is the full length
  209. of a data block:
  210. .. list-table::
  211. :widths: 8 8 24 40
  212. :header-rows: 1
  213. * - Offset
  214. - Type
  215. - Name
  216. - Description
  217. * - 0x0
  218. - \_\_le32
  219. - dot.inode
  220. - inode number of this directory.
  221. * - 0x4
  222. - \_\_le16
  223. - dot.rec\_len
  224. - Length of this record, 12.
  225. * - 0x6
  226. - u8
  227. - dot.name\_len
  228. - Length of the name, 1.
  229. * - 0x7
  230. - u8
  231. - dot.file\_type
  232. - File type of this entry, 0x2 (directory) (if the feature flag is set).
  233. * - 0x8
  234. - char
  235. - dot.name[4]
  236. - “.\\0\\0\\0”
  237. * - 0xC
  238. - \_\_le32
  239. - dotdot.inode
  240. - inode number of parent directory.
  241. * - 0x10
  242. - \_\_le16
  243. - dotdot.rec\_len
  244. - block\_size - 12. The record length is long enough to cover all htree
  245. data.
  246. * - 0x12
  247. - u8
  248. - dotdot.name\_len
  249. - Length of the name, 2.
  250. * - 0x13
  251. - u8
  252. - dotdot.file\_type
  253. - File type of this entry, 0x2 (directory) (if the feature flag is set).
  254. * - 0x14
  255. - char
  256. - dotdot\_name[4]
  257. - “..\\0\\0”
  258. * - 0x18
  259. - \_\_le32
  260. - struct dx\_root\_info.reserved\_zero
  261. - Zero.
  262. * - 0x1C
  263. - u8
  264. - struct dx\_root\_info.hash\_version
  265. - Hash type, see dirhash_ table below.
  266. * - 0x1D
  267. - u8
  268. - struct dx\_root\_info.info\_length
  269. - Length of the tree information, 0x8.
  270. * - 0x1E
  271. - u8
  272. - struct dx\_root\_info.indirect\_levels
  273. - Depth of the htree. Cannot be larger than 3 if the INCOMPAT\_LARGEDIR
  274. feature is set; cannot be larger than 2 otherwise.
  275. * - 0x1F
  276. - u8
  277. - struct dx\_root\_info.unused\_flags
  278. -
  279. * - 0x20
  280. - \_\_le16
  281. - limit
  282. - Maximum number of dx\_entries that can follow this header, plus 1 for
  283. the header itself.
  284. * - 0x22
  285. - \_\_le16
  286. - count
  287. - Actual number of dx\_entries that follow this header, plus 1 for the
  288. header itself.
  289. * - 0x24
  290. - \_\_le32
  291. - block
  292. - The block number (within the directory file) that goes with hash=0.
  293. * - 0x28
  294. - struct dx\_entry
  295. - entries[0]
  296. - As many 8-byte ``struct dx_entry`` as fits in the rest of the data block.
  297. .. _dirhash:
  298. The directory hash is one of the following values:
  299. .. list-table::
  300. :widths: 16 64
  301. :header-rows: 1
  302. * - Value
  303. - Description
  304. * - 0x0
  305. - Legacy.
  306. * - 0x1
  307. - Half MD4.
  308. * - 0x2
  309. - Tea.
  310. * - 0x3
  311. - Legacy, unsigned.
  312. * - 0x4
  313. - Half MD4, unsigned.
  314. * - 0x5
  315. - Tea, unsigned.
  316. * - 0x6
  317. - Siphash.
  318. Interior nodes of an htree are recorded as ``struct dx_node``, which is
  319. also the full length of a data block:
  320. .. list-table::
  321. :widths: 8 8 24 40
  322. :header-rows: 1
  323. * - Offset
  324. - Type
  325. - Name
  326. - Description
  327. * - 0x0
  328. - \_\_le32
  329. - fake.inode
  330. - Zero, to make it look like this entry is not in use.
  331. * - 0x4
  332. - \_\_le16
  333. - fake.rec\_len
  334. - The size of the block, in order to hide all of the dx\_node data.
  335. * - 0x6
  336. - u8
  337. - name\_len
  338. - Zero. There is no name for this “unused” directory entry.
  339. * - 0x7
  340. - u8
  341. - file\_type
  342. - Zero. There is no file type for this “unused” directory entry.
  343. * - 0x8
  344. - \_\_le16
  345. - limit
  346. - Maximum number of dx\_entries that can follow this header, plus 1 for
  347. the header itself.
  348. * - 0xA
  349. - \_\_le16
  350. - count
  351. - Actual number of dx\_entries that follow this header, plus 1 for the
  352. header itself.
  353. * - 0xE
  354. - \_\_le32
  355. - block
  356. - The block number (within the directory file) that goes with the lowest
  357. hash value of this block. This value is stored in the parent block.
  358. * - 0x12
  359. - struct dx\_entry
  360. - entries[0]
  361. - As many 8-byte ``struct dx_entry`` as fits in the rest of the data block.
  362. The hash maps that exist in both ``struct dx_root`` and
  363. ``struct dx_node`` are recorded as ``struct dx_entry``, which is 8 bytes
  364. long:
  365. .. list-table::
  366. :widths: 8 8 24 40
  367. :header-rows: 1
  368. * - Offset
  369. - Type
  370. - Name
  371. - Description
  372. * - 0x0
  373. - \_\_le32
  374. - hash
  375. - Hash code.
  376. * - 0x4
  377. - \_\_le32
  378. - block
  379. - Block number (within the directory file, not filesystem blocks) of the
  380. next node in the htree.
  381. (If you think this is all quite clever and peculiar, so does the
  382. author.)
  383. If metadata checksums are enabled, the last 8 bytes of the directory
  384. block (precisely the length of one dx\_entry) are used to store a
  385. ``struct dx_tail``, which contains the checksum. The ``limit`` and
  386. ``count`` entries in the dx\_root/dx\_node structures are adjusted as
  387. necessary to fit the dx\_tail into the block. If there is no space for
  388. the dx\_tail, the user is notified to run e2fsck -D to rebuild the
  389. directory index (which will ensure that there's space for the checksum.
  390. The dx\_tail structure is 8 bytes long and looks like this:
  391. .. list-table::
  392. :widths: 8 8 24 40
  393. :header-rows: 1
  394. * - Offset
  395. - Type
  396. - Name
  397. - Description
  398. * - 0x0
  399. - u32
  400. - dt\_reserved
  401. - Zero.
  402. * - 0x4
  403. - \_\_le32
  404. - dt\_checksum
  405. - Checksum of the htree directory block.
  406. The checksum is calculated against the FS UUID, the htree index header
  407. (dx\_root or dx\_node), all of the htree indices (dx\_entry) that are in
  408. use, and the tail block (dx\_tail).