<!DOCTYPE html>
<html lang="en" data-content_root="../../">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<title>4.3. Directory Entries — The Linux Kernel documentation</title>
<link rel="stylesheet" type="text/css" href="../../_static/pygments.css?v=fa44fd50" />
<link rel="stylesheet" type="text/css" href="../../_static/alabaster.css?v=3918102e" />
<script src="../../_static/documentation_options.js?v=5929fcd5"></script>
<script src="../../_static/doctools.js?v=9bcbadda"></script>
<script src="../../_static/sphinx_highlight.js?v=dc90522c"></script>
<link rel="index" title="Index" href="../../genindex.html" />
<link rel="search" title="Search" href="../../search.html" />
<link rel="next" title="4.4. Extended Attributes" href="attributes.html" />
<link rel="prev" title="4.2. The Contents of inode.i_block" href="ifork.html" />
<link rel="stylesheet" href="../../_static/custom.css" type="text/css" />
</head><body>
<div class="document">
<div class="sphinxsidebar" role="navigation" aria-label="Main">
<div class="sphinxsidebarwrapper">
<p class="logo"><a href="../../index.html">
<img class="logo" src="../../_static/logo.svg" alt="Logo of The Linux Kernel"/>
</a></p>
<h1 class="logo"><a href="../../index.html">The Linux Kernel</a></h1>
<p class="blurb">6.18.50</p>
<search id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../../search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</search>
<script>document.getElementById('searchbox').style.display = "block"</script>
<p>
<h3 class="kernel-toc-contents">Contents</h3>
<input type="checkbox" class="kernel-toc-toggle" id = "kernel-toc-toggle" checked>
<label class="kernel-toc-title" for="kernel-toc-toggle"></label>
<div class="kerneltoc" id="kerneltoc">
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../process/development-process.html">Development process</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../process/submitting-patches.html">Submitting patches</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../process/code-of-conduct.html">Code of conduct</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../maintainer/index.html">Maintainer handbook</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../process/index.html">All development-process docs</a></li>
</ul>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../../core-api/index.html">Core API</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../driver-api/index.html">Driver APIs</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../../subsystem-apis.html">Subsystems</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="../../subsystem-apis.html#core-subsystems">Core subsystems</a></li>
<li class="toctree-l2"><a class="reference internal" href="../../subsystem-apis.html#human-interfaces">Human interfaces</a></li>
<li class="toctree-l2"><a class="reference internal" href="../../subsystem-apis.html#networking-interfaces">Networking interfaces</a></li>
<li class="toctree-l2 current"><a class="reference internal" href="../../subsystem-apis.html#storage-interfaces">Storage interfaces</a><ul class="current">
<li class="toctree-l3 current"><a class="reference internal" href="../index.html">Filesystems in the Linux kernel</a></li>
<li class="toctree-l3"><a class="reference internal" href="../../block/index.html">Block</a></li>
<li class="toctree-l3"><a class="reference internal" href="../../cdrom/index.html">CD-ROM</a></li>
<li class="toctree-l3"><a class="reference internal" href="../../scsi/index.html">SCSI Subsystem</a></li>
<li class="toctree-l3"><a class="reference internal" href="../../target/index.html">TCM Virtual Device</a></li>
<li class="toctree-l3"><a class="reference internal" href="../../nvme/index.html">NVMe Subsystem</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="../../subsystem-apis.html#other-subsystems">Other subsystems</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../../locking/index.html">Locking</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../process/license-rules.html">Licensing rules</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../doc-guide/index.html">Writing documentation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../dev-tools/index.html">Development tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../dev-tools/testing-overview.html">Testing guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../kernel-hacking/index.html">Hacking guide</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../trace/index.html">Tracing</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../fault-injection/index.html">Fault injection</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../livepatch/index.html">Livepatching</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../rust/index.html">Rust</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../admin-guide/index.html">Administration</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../kbuild/index.html">Build system</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../admin-guide/reporting-issues.html">Reporting issues</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../tools/index.html">Userspace tools</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../userspace-api/index.html">Userspace API</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../firmware-guide/index.html">Firmware</a></li>
<li class="toctree-l1"><a class="reference internal" href="../../devicetree/index.html">Firmware and Devicetree</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../arch/index.html">CPU architectures</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../staging/index.html">Unsorted documentation</a></li>
</ul>
<ul>
<li class="toctree-l1"><a class="reference internal" href="../../translations/index.html">Translations</a></li>
</ul>
</div>
<script type="text/javascript"> <!--
var sbar = document.getElementsByClassName("sphinxsidebar")[0];
let currents = document.getElementsByClassName("current")
if (currents.length) {
sbar.scrollTop = currents[currents.length - 1].offsetTop;
}
--> </script>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../../_sources/filesystems/ext4/directory.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
</div>
</div>
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="directory-entries">
<h1><span class="section-number">4.3. </span>Directory Entries<a class="headerlink" href="#directory-entries" title="Link to this heading">¶</a></h1>
<p>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.</p>
<section id="linear-classic-directories">
<h2><span class="section-number">4.3.1. </span>Linear (Classic) Directories<a class="headerlink" href="#linear-classic-directories" title="Link to this heading">¶</a></h2>
<p>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 <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ext4_dir_entry_2</span></code> for directory entries unless the
“filetype” feature flag is not set, in which case it uses
<code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ext4_dir_entry</span></code>.</p>
<p>The original directory entry format is <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ext4_dir_entry</span></code>, which
is at most 263 bytes long, though on disk you’ll need to reference
<code class="docutils literal notranslate"><span class="pre">dirent.rec_len</span></code> to know for sure.</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Size</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>__le32</p></td>
<td><p>inode</p></td>
<td><p>Number of the inode that this directory entry points to.</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le16</p></td>
<td><p>rec_len</p></td>
<td><p>Length of this directory entry. Must be a multiple of 4.</p></td>
</tr>
<tr class="row-even"><td><p>0x6</p></td>
<td><p>__le16</p></td>
<td><p>name_len</p></td>
<td><p>Length of the file name.</p></td>
</tr>
<tr class="row-odd"><td><p>0x8</p></td>
<td><p>char</p></td>
<td><p>name[EXT4_NAME_LEN]</p></td>
<td><p>File name.</p></td>
</tr>
</tbody>
</table>
<p>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 <code class="docutils literal notranslate"><span class="pre">ext4_dir_entry_2</span></code>, which is at most
263 bytes long, though on disk you’ll need to reference
<code class="docutils literal notranslate"><span class="pre">dirent.rec_len</span></code> to know for sure.</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Size</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>__le32</p></td>
<td><p>inode</p></td>
<td><p>Number of the inode that this directory entry points to.</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le16</p></td>
<td><p>rec_len</p></td>
<td><p>Length of this directory entry.</p></td>
</tr>
<tr class="row-even"><td><p>0x6</p></td>
<td><p>__u8</p></td>
<td><p>name_len</p></td>
<td><p>Length of the file name.</p></td>
</tr>
<tr class="row-odd"><td><p>0x7</p></td>
<td><p>__u8</p></td>
<td><p>file_type</p></td>
<td><p>File type code, see <a class="reference internal" href="#ftype">ftype</a> table below.</p></td>
</tr>
<tr class="row-even"><td><p>0x8</p></td>
<td><p>char</p></td>
<td><p>name[EXT4_NAME_LEN]</p></td>
<td><p>File name.</p></td>
</tr>
</tbody>
</table>
<p id="ftype">The directory file type is one of the following values:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 20.0%" />
<col style="width: 80.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Value</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>Unknown.</p></td>
</tr>
<tr class="row-odd"><td><p>0x1</p></td>
<td><p>Regular file.</p></td>
</tr>
<tr class="row-even"><td><p>0x2</p></td>
<td><p>Directory.</p></td>
</tr>
<tr class="row-odd"><td><p>0x3</p></td>
<td><p>Character device file.</p></td>
</tr>
<tr class="row-even"><td><p>0x4</p></td>
<td><p>Block device file.</p></td>
</tr>
<tr class="row-odd"><td><p>0x5</p></td>
<td><p>FIFO.</p></td>
</tr>
<tr class="row-even"><td><p>0x6</p></td>
<td><p>Socket.</p></td>
</tr>
<tr class="row-odd"><td><p>0x7</p></td>
<td><p>Symbolic link.</p></td>
</tr>
</tbody>
</table>
<p>To support directories that are both encrypted and casefolded directories, we
must also include hash information in the directory entry. We append
<code class="docutils literal notranslate"><span class="pre">ext4_extended_dir_entry_2</span></code> to <code class="docutils literal notranslate"><span class="pre">ext4_dir_entry_2</span></code> except for the entries
for dot and dotdot, which are kept the same. The structure follows immediately
after <code class="docutils literal notranslate"><span class="pre">name</span></code> and is included in the size listed by <code class="docutils literal notranslate"><span class="pre">rec_len</span></code> If a directory
entry uses this extension, it may be up to 271 bytes.</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Size</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>__le32</p></td>
<td><p>hash</p></td>
<td><p>The hash of the directory name</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le32</p></td>
<td><p>minor_hash</p></td>
<td><p>The minor hash of the directory name</p></td>
</tr>
</tbody>
</table>
<p>In order to add checksums to these classic directory blocks, a phony
<code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ext4_dir_entry</span></code> 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
<code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ext4_dir_entry_tail</span></code>:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Size</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>__le32</p></td>
<td><p>det_reserved_zero1</p></td>
<td><p>Inode number, which must be zero.</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le16</p></td>
<td><p>det_rec_len</p></td>
<td><p>Length of this directory entry, which must be 12.</p></td>
</tr>
<tr class="row-even"><td><p>0x6</p></td>
<td><p>__u8</p></td>
<td><p>det_reserved_zero2</p></td>
<td><p>Length of the file name, which must be zero.</p></td>
</tr>
<tr class="row-odd"><td><p>0x7</p></td>
<td><p>__u8</p></td>
<td><p>det_reserved_ft</p></td>
<td><p>File type, which must be 0xDE.</p></td>
</tr>
<tr class="row-even"><td><p>0x8</p></td>
<td><p>__le32</p></td>
<td><p>det_checksum</p></td>
<td><p>Directory leaf block checksum.</p></td>
</tr>
</tbody>
</table>
<p>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.</p>
</section>
<section id="hash-tree-directories">
<h2><span class="section-number">4.3.2. </span>Hash Tree Directories<a class="headerlink" href="#hash-tree-directories" title="Link to this heading">¶</a></h2>
<p>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.</p>
<p>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
<code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ext4_dir_entry_2</span></code> 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
<code class="docutils literal notranslate"><span class="pre">dx_root.info.indirect_levels</span></code> 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 <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">ext4_dir_entry_2</span></code> 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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>The root of the htree is in <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_root</span></code>, which is the full length
of a data block:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Type</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>__le32</p></td>
<td><p>dot.inode</p></td>
<td><p>inode number of this directory.</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le16</p></td>
<td><p>dot.rec_len</p></td>
<td><p>Length of this record, 12.</p></td>
</tr>
<tr class="row-even"><td><p>0x6</p></td>
<td><p>u8</p></td>
<td><p>dot.name_len</p></td>
<td><p>Length of the name, 1.</p></td>
</tr>
<tr class="row-odd"><td><p>0x7</p></td>
<td><p>u8</p></td>
<td><p>dot.file_type</p></td>
<td><p>File type of this entry, 0x2 (directory) (if the feature flag is set).</p></td>
</tr>
<tr class="row-even"><td><p>0x8</p></td>
<td><p>char</p></td>
<td><p>dot.name[4]</p></td>
<td><p>“.000”</p></td>
</tr>
<tr class="row-odd"><td><p>0xC</p></td>
<td><p>__le32</p></td>
<td><p>dotdot.inode</p></td>
<td><p>inode number of parent directory.</p></td>
</tr>
<tr class="row-even"><td><p>0x10</p></td>
<td><p>__le16</p></td>
<td><p>dotdot.rec_len</p></td>
<td><p>block_size - 12. The record length is long enough to cover all htree
data.</p></td>
</tr>
<tr class="row-odd"><td><p>0x12</p></td>
<td><p>u8</p></td>
<td><p>dotdot.name_len</p></td>
<td><p>Length of the name, 2.</p></td>
</tr>
<tr class="row-even"><td><p>0x13</p></td>
<td><p>u8</p></td>
<td><p>dotdot.file_type</p></td>
<td><p>File type of this entry, 0x2 (directory) (if the feature flag is set).</p></td>
</tr>
<tr class="row-odd"><td><p>0x14</p></td>
<td><p>char</p></td>
<td><p>dotdot_name[4]</p></td>
<td><p>“..00”</p></td>
</tr>
<tr class="row-even"><td><p>0x18</p></td>
<td><p>__le32</p></td>
<td><p><code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_root_info</span></code>.reserved_zero</p></td>
<td><p>Zero.</p></td>
</tr>
<tr class="row-odd"><td><p>0x1C</p></td>
<td><p>u8</p></td>
<td><p><code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_root_info</span></code>.hash_version</p></td>
<td><p>Hash type, see <a class="reference internal" href="#dirhash">dirhash</a> table below.</p></td>
</tr>
<tr class="row-even"><td><p>0x1D</p></td>
<td><p>u8</p></td>
<td><p><code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_root_info</span></code>.info_length</p></td>
<td><p>Length of the tree information, 0x8.</p></td>
</tr>
<tr class="row-odd"><td><p>0x1E</p></td>
<td><p>u8</p></td>
<td><p><code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_root_info</span></code>.indirect_levels</p></td>
<td><p>Depth of the htree. Cannot be larger than 3 if the INCOMPAT_LARGEDIR
feature is set; cannot be larger than 2 otherwise.</p></td>
</tr>
<tr class="row-even"><td><p>0x1F</p></td>
<td><p>u8</p></td>
<td><p><code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_root_info</span></code>.unused_flags</p></td>
<td></td>
</tr>
<tr class="row-odd"><td><p>0x20</p></td>
<td><p>__le16</p></td>
<td><p>limit</p></td>
<td><p>Maximum number of dx_entries that can follow this header, plus 1 for
the header itself.</p></td>
</tr>
<tr class="row-even"><td><p>0x22</p></td>
<td><p>__le16</p></td>
<td><p>count</p></td>
<td><p>Actual number of dx_entries that follow this header, plus 1 for the
header itself.</p></td>
</tr>
<tr class="row-odd"><td><p>0x24</p></td>
<td><p>__le32</p></td>
<td><p>block</p></td>
<td><p>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.</p></td>
</tr>
<tr class="row-even"><td><p>0x28</p></td>
<td><p><code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_entry</span></code></p></td>
<td><p>entries[0]</p></td>
<td><p>As many 8-byte <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_entry</span></code> as fits in the rest of the data block.</p></td>
</tr>
</tbody>
</table>
<p id="dirhash">The directory hash is one of the following values:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 20.0%" />
<col style="width: 80.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Value</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>Legacy.</p></td>
</tr>
<tr class="row-odd"><td><p>0x1</p></td>
<td><p>Half MD4.</p></td>
</tr>
<tr class="row-even"><td><p>0x2</p></td>
<td><p>Tea.</p></td>
</tr>
<tr class="row-odd"><td><p>0x3</p></td>
<td><p>Legacy, unsigned.</p></td>
</tr>
<tr class="row-even"><td><p>0x4</p></td>
<td><p>Half MD4, unsigned.</p></td>
</tr>
<tr class="row-odd"><td><p>0x5</p></td>
<td><p>Tea, unsigned.</p></td>
</tr>
<tr class="row-even"><td><p>0x6</p></td>
<td><p>Siphash.</p></td>
</tr>
</tbody>
</table>
<p>Interior nodes of an htree are recorded as <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_node</span></code>, which is
also the full length of a data block:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Type</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>__le32</p></td>
<td><p>fake.inode</p></td>
<td><p>Zero, to make it look like this entry is not in use.</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le16</p></td>
<td><p>fake.rec_len</p></td>
<td><p>The size of the block, in order to hide all of the dx_node data.</p></td>
</tr>
<tr class="row-even"><td><p>0x6</p></td>
<td><p>u8</p></td>
<td><p>name_len</p></td>
<td><p>Zero. There is no name for this “unused” directory entry.</p></td>
</tr>
<tr class="row-odd"><td><p>0x7</p></td>
<td><p>u8</p></td>
<td><p>file_type</p></td>
<td><p>Zero. There is no file type for this “unused” directory entry.</p></td>
</tr>
<tr class="row-even"><td><p>0x8</p></td>
<td><p>__le16</p></td>
<td><p>limit</p></td>
<td><p>Maximum number of dx_entries that can follow this header, plus 1 for
the header itself.</p></td>
</tr>
<tr class="row-odd"><td><p>0xA</p></td>
<td><p>__le16</p></td>
<td><p>count</p></td>
<td><p>Actual number of dx_entries that follow this header, plus 1 for the
header itself.</p></td>
</tr>
<tr class="row-even"><td><p>0xE</p></td>
<td><p>__le32</p></td>
<td><p>block</p></td>
<td><p>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.</p></td>
</tr>
<tr class="row-odd"><td><p>0x12</p></td>
<td><p><code class="xref c c-struct broken_xref docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_entry</span></code></p></td>
<td><p>entries[0]</p></td>
<td><p>As many 8-byte <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_entry</span></code> as fits in the rest of the data block.</p></td>
</tr>
</tbody>
</table>
<p>The hash maps that exist in both <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_root</span></code> and
<code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_node</span></code> are recorded as <code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_entry</span></code>, which is 8 bytes
long:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Type</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>__le32</p></td>
<td><p>hash</p></td>
<td><p>Hash code.</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le32</p></td>
<td><p>block</p></td>
<td><p>Block number (within the directory file, not filesystem blocks) of the
next node in the htree.</p></td>
</tr>
</tbody>
</table>
<p>(If you think this is all quite clever and peculiar, so does the
author.)</p>
<p>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
<code class="docutils literal notranslate"><span class="pre">struct</span> <span class="pre">dx_tail</span></code>, which contains the checksum. The <code class="docutils literal notranslate"><span class="pre">limit</span></code> and
<code class="docutils literal notranslate"><span class="pre">count</span></code> 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:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 10.0%" />
<col style="width: 10.0%" />
<col style="width: 30.0%" />
<col style="width: 50.0%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Offset</p></th>
<th class="head"><p>Type</p></th>
<th class="head"><p>Name</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>0x0</p></td>
<td><p>u32</p></td>
<td><p>dt_reserved</p></td>
<td><p>Unused (but still part of the checksum curiously).</p></td>
</tr>
<tr class="row-odd"><td><p>0x4</p></td>
<td><p>__le32</p></td>
<td><p>dt_checksum</p></td>
<td><p>Checksum of the htree directory block.</p></td>
</tr>
</tbody>
</table>
<p>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.</p>
</section>
</section>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©The kernel development community.
|
Powered by <a href="https://www.sphinx-doc.org/">Sphinx 8.1.3</a>
& <a href="https://alabaster.readthedocs.io">Alabaster 0.7.16</a>
|
<a href="../../_sources/filesystems/ext4/directory.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>