diff options
| l--------- | build/ext2-doc/DC-ext2-doc | 1 | ||||
| -rw-r--r-- | build/ext2-doc/ext2-doc.html | 1318 | ||||
| -rw-r--r-- | build/ext2-doc/ext2-doc_color_en.pdf | bin | 0 -> 317396 bytes | |||
| -rw-r--r-- | makefile | 37 |
4 files changed, 1319 insertions, 37 deletions
diff --git a/build/ext2-doc/DC-ext2-doc b/build/ext2-doc/DC-ext2-doc new file mode 120000 index 0000000..f193e5d --- /dev/null +++ b/build/ext2-doc/DC-ext2-doc @@ -0,0 +1 @@ +/dockerShare/DC-ext2-doc
\ No newline at end of file diff --git a/build/ext2-doc/ext2-doc.html b/build/ext2-doc/ext2-doc.html new file mode 100644 index 0000000..bda8f96 --- /dev/null +++ b/build/ext2-doc/ext2-doc.html @@ -0,0 +1,1318 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>The Second Extended File System</title><meta name="generator" content="DocBook XSL Stylesheets V1.78.1" /></head><body><div xml:lang="en" class="book" lang="en"><div class="titlepage"><div><div><h1 class="title"><a id="Ext2.Internals"></a>The Second Extended File System</h1></div><div><h2 class="subtitle">Internal Layout</h2></div><div><div class="authorgroup"><div class="author"><h3 class="author"><span class="firstname">Dave</span> <span class="surname">Poirier</span></h3><div class="affiliation"><div class="address"><p><br /> + <code class="email"><<a class="email" href="mailto:[email protected]">[email protected]</a>></code><br /> + </p></div></div></div></div></div><div><p class="copyright">Copyright © 2001-2019 Dave Poirier</p></div><div><div class="legalnotice"><a id="idm140660450229376"></a><p> + Permission is granted to copy, distribute and/or modify this document + under the terms of the GNU Free Documentation License, Version 1.1 + or any later version published by the Free Software Foundation; + with no Invariant Sections, with no Front-Cover Texts, and with no + Back-Cover Texts. A copy of the license can be acquired electronically + from http://www.fsf.org/licenses/fdl.html or by writing to + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + </p></div></div></div><hr /></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="preface"><a href="#idm140660448989936">About this book</a></span></dt><dt><span class="chapter"><a href="#history">1. Historical Background</a></span></dt><dt><span class="chapter"><a href="#Definitions">2. Definitions</a></span></dt><dd><dl><dt><span class="sect1"><a href="#def-blocks">Blocks</a></span></dt><dt><span class="sect1"><a href="#def-block-groups">Block Groups</a></span></dt><dt><span class="sect1"><a href="#def-directories">Directories</a></span></dt><dt><span class="sect1"><a href="#def-inodes">Inodes</a></span></dt><dt><span class="sect1"><a href="#def-superblock">Superblocks</a></span></dt><dt><span class="sect1"><a href="#def-symbolic-links">Symbolic Links</a></span></dt></dl></dd><dt><span class="chapter"><a href="#disk-organisation">3. Disk Organization</a></span></dt><dd><dl><dt><span class="sect1"><a href="#superblock">Superblock</a></span></dt><dd><dl><dt><span class="sect2"><a href="#s-inodes-count">s_inodes_count</a></span></dt><dt><span class="sect2"><a href="#s-blocks-count">s_blocks_count</a></span></dt><dt><span class="sect2"><a href="#s-r-blocks-count">s_r_blocks_count</a></span></dt><dt><span class="sect2"><a href="#s-free-blocks-count">s_free_blocks_count</a></span></dt><dt><span class="sect2"><a href="#s-free-inodes-count">s_free_inodes_count</a></span></dt><dt><span class="sect2"><a href="#s-first-data-block">s_first_data_block</a></span></dt><dt><span class="sect2"><a href="#s-log-block-size">s_log_block_size</a></span></dt><dt><span class="sect2"><a href="#s-log-frag-size">s_log_frag_size</a></span></dt><dt><span class="sect2"><a href="#s-blocks-per-group">s_blocks_per_group</a></span></dt><dt><span class="sect2"><a href="#s-frags-per-group">s_frags_per_group</a></span></dt><dt><span class="sect2"><a href="#s-inodes-per-group">s_inodes_per_group</a></span></dt><dt><span class="sect2"><a href="#s-mtime">s_mtime</a></span></dt><dt><span class="sect2"><a href="#s-wtime">s_wtime</a></span></dt><dt><span class="sect2"><a href="#s-mnt-count">s_mnt_count</a></span></dt><dt><span class="sect2"><a href="#s-max-mnt-count">s_max_mnt_count</a></span></dt><dt><span class="sect2"><a href="#s-magic">s_magic</a></span></dt><dt><span class="sect2"><a href="#s-state">s_state</a></span></dt><dt><span class="sect2"><a href="#s-errors">s_errors</a></span></dt><dt><span class="sect2"><a href="#s-minor-rev-level">s_minor_rev_level</a></span></dt><dt><span class="sect2"><a href="#s-lastcheck">s_lastcheck</a></span></dt><dt><span class="sect2"><a href="#s-checkinterval">s_checkinterval</a></span></dt><dt><span class="sect2"><a href="#s-creator-os">s_creator_os</a></span></dt><dt><span class="sect2"><a href="#s-rev-level">s_rev_level</a></span></dt><dt><span class="sect2"><a href="#s-def-resuid">s_def_resuid</a></span></dt><dt><span class="sect2"><a href="#s-def-resgid">s_def_resgid</a></span></dt><dt><span class="sect2"><a href="#s-first-ino">s_first_ino</a></span></dt><dt><span class="sect2"><a href="#s-inode-size">s_inode_size</a></span></dt><dt><span class="sect2"><a href="#s-block-group-nr">s_block_group_nr</a></span></dt><dt><span class="sect2"><a href="#s-feature-compat">s_feature_compat</a></span></dt><dt><span class="sect2"><a href="#s-feature-incompat">s_feature_incompat</a></span></dt><dt><span class="sect2"><a href="#s-feature-ro-compat">s_feature_ro_compat</a></span></dt><dt><span class="sect2"><a href="#s-uuid">s_uuid</a></span></dt><dt><span class="sect2"><a href="#s-volume-name">s_volume_name</a></span></dt><dt><span class="sect2"><a href="#s-last-mounted">s_last_mounted</a></span></dt><dt><span class="sect2"><a href="#s-algo-bitmap">s_algo_bitmap</a></span></dt><dt><span class="sect2"><a href="#s-prealloc-blocks">s_prealloc_blocks</a></span></dt><dt><span class="sect2"><a href="#s-prealloc-dir-blocks">s_prealloc_dir_blocks</a></span></dt><dt><span class="sect2"><a href="#s-journal-uuid">s_journal_uuid</a></span></dt><dt><span class="sect2"><a href="#s-journal-inum">s_journal_inum</a></span></dt><dt><span class="sect2"><a href="#s-journal-dev">s_journal_dev</a></span></dt><dt><span class="sect2"><a href="#s-last-orphan">s_last_orphan</a></span></dt><dt><span class="sect2"><a href="#s-hash-seed">s_hash_seed</a></span></dt><dt><span class="sect2"><a href="#s-def-hash-version">s_def_hash_version</a></span></dt><dt><span class="sect2"><a href="#s-default-mount-options">s_default_mount_options</a></span></dt><dt><span class="sect2"><a href="#s-first-meta-bg">s_first_meta_bg</a></span></dt></dl></dd><dt><span class="sect1"><a href="#block-group-descriptor-table">Block Group Descriptor Table</a></span></dt><dd><dl><dt><span class="sect2"><a href="#bg-block-bitmap">bg_block_bitmap</a></span></dt><dt><span class="sect2"><a href="#bg-inode-bitmap">bg_inode_bitmap</a></span></dt><dt><span class="sect2"><a href="#bg-inode-table">bg_inode_table</a></span></dt><dt><span class="sect2"><a href="#bg-free-blocks-count">bg_free_blocks_count</a></span></dt><dt><span class="sect2"><a href="#bg-free-inodes-count">bg_free_inodes_count</a></span></dt><dt><span class="sect2"><a href="#bg-used-dirs-count">bg_used_dirs_count</a></span></dt><dt><span class="sect2"><a href="#bg-pad">bg_pad</a></span></dt><dt><span class="sect2"><a href="#bg-reserved">bg_reserved</a></span></dt></dl></dd><dt><span class="sect1"><a href="#block-bitmap">Block Bitmap</a></span></dt><dt><span class="sect1"><a href="#inode-bitmap">Inode Bitmap</a></span></dt><dt><span class="sect1"><a href="#inode-table">Inode Table</a></span></dt><dd><dl><dt><span class="sect2"><a href="#i-mode">i_mode</a></span></dt><dt><span class="sect2"><a href="#i-uid">i_uid</a></span></dt><dt><span class="sect2"><a href="#i-size">i_size</a></span></dt><dt><span class="sect2"><a href="#i-atime">i_atime</a></span></dt><dt><span class="sect2"><a href="#i-ctime">i_ctime</a></span></dt><dt><span class="sect2"><a href="#i-mtime">i_mtime</a></span></dt><dt><span class="sect2"><a href="#i-dtime">i_dtime</a></span></dt><dt><span class="sect2"><a href="#i-gid">i_gid</a></span></dt><dt><span class="sect2"><a href="#i-links-count">i_links_count</a></span></dt><dt><span class="sect2"><a href="#i-blocks">i_blocks</a></span></dt><dt><span class="sect2"><a href="#i-flags">i_flags</a></span></dt><dt><span class="sect2"><a href="#i-osd1">i_osd1</a></span></dt><dt><span class="sect2"><a href="#i-block">i_block</a></span></dt><dt><span class="sect2"><a href="#i-generation">i_generation</a></span></dt><dt><span class="sect2"><a href="#i-file-acl">i_file_acl</a></span></dt><dt><span class="sect2"><a href="#i-dir-acl">i_dir_acl</a></span></dt><dt><span class="sect2"><a href="#i-faddr">i_faddr</a></span></dt><dt><span class="sect2"><a href="#i-osd2">Inode i_osd2 Structure</a></span></dt></dl></dd><dt><span class="sect1"><a href="#idm140660447281728">Locating an Inode</a></span></dt></dl></dd><dt><span class="chapter"><a href="#directory">4. Directory Structure</a></span></dt><dd><dl><dt><span class="sect1"><a href="#linked-directories">Linked List Directory</a></span></dt><dd><dl><dt><span class="sect2"><a href="#ifdir-inode">inode</a></span></dt><dt><span class="sect2"><a href="#ifdir-rec-len">rec_len</a></span></dt><dt><span class="sect2"><a href="#ifdir-name-len">name_len</a></span></dt><dt><span class="sect2"><a href="#ifdir-file-type">file_type</a></span></dt><dt><span class="sect2"><a href="#ifdir-name">name</a></span></dt><dt><span class="sect2"><a href="#dir-sample">Sample Directory</a></span></dt></dl></dd><dt><span class="sect1"><a href="#indexed-directory">Indexed Directory Format</a></span></dt><dd><dl><dt><span class="sect2"><a href="#dx-root">Indexed Directory Root</a></span></dt><dt><span class="sect2"><a href="#dx-entry">Indexed Directory Entry</a></span></dt><dt><span class="sect2"><a href="#contrib-lookup-algorithm">Lookup Algorithm</a></span></dt><dt><span class="sect2"><a href="#contrib-insert-algorithm">Insert Algorithm</a></span></dt><dt><span class="sect2"><a href="#contrib-splitting">Splitting</a></span></dt><dt><span class="sect2"><a href="#contrib-key-collisions">Key Collisions</a></span></dt><dt><span class="sect2"><a href="#contrib-hash-function">Hash Function</a></span></dt><dt><span class="sect2"><a href="#contrib-performance">Performance</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="#idm140660446981504">5. File Attributes</a></span></dt><dd><dl><dt><span class="sect1"><a href="#idm140660446979776">Standard Attributes</a></span></dt><dd><dl><dt><span class="sect2"><a href="#idm140660446979264">SUID, SGID and -rwxrwxrwx</a></span></dt><dt><span class="sect2"><a href="#idm140660446977504">File Size</a></span></dt><dt><span class="sect2"><a href="#idm140660446975776">Owner and Group</a></span></dt></dl></dd><dt><span class="sect1"><a href="#contrib-extended-attributes">Extended Attributes</a></span></dt><dd><dl><dt><span class="sect2"><a href="#extended-attribute-layout">Extended Attribute Block Layout</a></span></dt><dt><span class="sect2"><a href="#attribute-block-header">Extended Attribute Block Header</a></span></dt><dt><span class="sect2"><a href="#idm140660446913440">Attribute Entry Header</a></span></dt></dl></dd><dt><span class="sect1"><a href="#behaviour-flags">Behaviour Control Flags</a></span></dt><dd><dl><dt><span class="sect2"><a href="#ext2-secrm-fl">EXT2_SECRM_FL - Secure Deletion</a></span></dt><dt><span class="sect2"><a href="#ext2-unrm-fl">EXT2_UNRM_FL - Record for Undelete</a></span></dt><dt><span class="sect2"><a href="#ext2-compr-fl">EXT2_COMPR_FL - Compressed File</a></span></dt><dt><span class="sect2"><a href="#ext2-sync-fl">EXT2_SYNC_FL - Synchronous Updates</a></span></dt><dt><span class="sect2"><a href="#ext2-immutable-fl">EXT2_IMMUTABLE_FL - Immutable File</a></span></dt><dt><span class="sect2"><a href="#ext2-append-fl">EXT2_APPEND_FL - Append Only</a></span></dt><dt><span class="sect2"><a href="#ext2-nodump-fl">EXT2_NODUMP_FL - Do No Dump/Delete</a></span></dt><dt><span class="sect2"><a href="#ext2-noatime-fl">EXT2_NOATIME_FL - Do Not Update .i_atime</a></span></dt><dt><span class="sect2"><a href="#ext2-dirty-fl">EXT2_DIRTY_FL - Dirty</a></span></dt><dt><span class="sect2"><a href="#ext2-comprblk-fl">EXT2_COMPRBLK_FL - Compressed Blocks</a></span></dt><dt><span class="sect2"><a href="#ext2-nocompr-fl">EXT2_NOCOMPR_FL - Access Raw Compressed Data</a></span></dt><dt><span class="sect2"><a href="#ext2-ecompr-fl">EXT2_ECOMPR_FL - Compression Error</a></span></dt><dt><span class="sect2"><a href="#ext2-btree-fl">EXT2_BTREE_FL - B-Tree Format Directory</a></span></dt><dt><span class="sect2"><a href="#ext2-index-fl">EXT2_INDEX_FL - Hash Indexed Directory</a></span></dt><dt><span class="sect2"><a href="#ext2-imagic-fl">EXT2_IMAGIC_FL - </a></span></dt><dt><span class="sect2"><a href="#ext3-journal-data-fl">EXT2_JOURNAL_DATA_FL - Journal File Data</a></span></dt><dt><span class="sect2"><a href="#ext2-reserved-fl">EXT2_RESERVED_FL - Reserved</a></span></dt></dl></dd></dl></dd><dt><span class="appendix"><a href="#idm140660446838800">A. Credits</a></span></dt></dl></div><div class="list-of-figures"><p><strong>List of Figures</strong></p><dl><dt>4.1. <a href="#idm140660446987040">Performance of Indexed Directories</a></dt><dt>5.1. <a href="#idm140660446912928">ext2_xattr_header structure</a></dt></dl></div><div class="list-of-tables"><p><strong>List of Tables</strong></p><dl><dt>2.1. <a href="#block-size-impact">Impact of Block Sizes</a></dt><dt>3.1. <a href="#disk-layout-sample-floppy">Sample Floppy Disk Layout, 1KiB blocks</a></dt><dt>3.2. <a href="#disk-layout-sample-20mb">Sample 20mb Partition Layout</a></dt><dt>3.3. <a href="#superblock-structure">Superblock Structure</a></dt><dt>3.4. <a href="#s-state-values">Defined s_state Values</a></dt><dt>3.5. <a href="#ext2-errors">Defined s_errors Values</a></dt><dt>3.6. <a href="#s-creator-os-values">Defined s_creator_os Values</a></dt><dt>3.7. <a href="#s-rev-level-values">Defined s_rev_level Values</a></dt><dt>3.8. <a href="#s-feature-compat-values">Defined s_feature_compat Values</a></dt><dt>3.9. <a href="#s-feature-incompat-values">Defined s_feature_incompat Values</a></dt><dt>3.10. <a href="#s-feature-ro-compat-values">Defined s_feature_ro_compat Values</a></dt><dt>3.11. <a href="#s-algo-bitmap-values">Defined s_algo_bitmap Values</a></dt><dt>3.12. <a href="#block-group-descriptor-structure">Block Group Descriptor Structure</a></dt><dt>3.13. <a href="#inode-structure">Inode Structure</a></dt><dt>3.14. <a href="#reserved-inodes-values">Defined Reserved Inodes</a></dt><dt>3.15. <a href="#idm140660447480672">Defined i_mode Values</a></dt><dt>3.16. <a href="#defined-i-flags-values">Defined i_flags Values</a></dt><dt>3.17. <a href="#i-osd2-hurd-structure">Inode i_osd2 Structure: Hurd</a></dt><dt>3.18. <a href="#i-osd2-linux-structure">Inode i_osd2 Structure: Linux</a></dt><dt>3.19. <a href="#i-osd2-masix-structure">Inode i_osd2 Structure: Masix</a></dt><dt>3.20. <a href="#inode-computation-sample">Sample Inode Computations</a></dt><dt>4.1. <a href="#linked-directory-entry-structure">Linked Directory Entry Structure</a></dt><dt>4.2. <a href="#ifdir-file-type-values">Defined Inode File Type Values</a></dt><dt>4.3. <a href="#sample-linked-directory-data">Sample Linked Directory Data Layout, 4KiB blocks</a></dt><dt>4.4. <a href="#dx-root-structure">Indexed Directory Root Structure</a></dt><dt>4.5. <a href="#defined-dx-hash-version-values">Defined Indexed Directory Hash Versions</a></dt><dt>4.6. <a href="#dx-entry-structure">Indexed Directory Entry Structure (dx_entry)</a></dt><dt>4.7. <a href="#dx-entry-countlimit">Indexed Directory Entry Count and Limit Structure</a></dt><dt>5.1. <a href="#extended-attribute-block-layout">Extended Attribute Block Layout</a></dt><dt>5.2. <a href="#attribute-block-header-structure">ext2_xattr_header structure</a></dt><dt>5.3. <a href="#idm140660446894752">Behaviour Control Flags</a></dt></dl></div><div class="preface"><div class="titlepage"><div><div><h1 class="title"><a id="idm140660448989936"></a>About this book</h1></div></div></div><p> + The latest version of this document may be downloaded from + https://www.nongnu.org/ext2-doc/ + </p><p> + This book is intended as an introduction and guide to the Second + Extended File System, also known as Ext2. The reader should have a + good understanding of the purpose of a file system as well as the + associated vocabulary (file, directory, partition, etc). + </p><p> + Implementing file system drivers is already a daunting task, unfortunately + except for tidbits of information here and there most of the documentation + for the Second Extended Filesystem is in source files. + </p><p> + Hopefully this document will fix this problem, may it be of help to as + many of you as possible. + </p><p> + <span class="emphasis"><em>Unless otherwise stated, all values are stored in little + endian byte order.</em></span> + </p></div><div class="chapter"><div class="titlepage"><div><div><h1 class="title"><a id="history"></a>Chapter 1. Historical Background</h1></div></div></div><p> + Written by Remy Card, Theodore Ts'o and Stephen Tweedie as a major rewrite + of the Extended Filesystem, it was first released to the public on January + 1993 as part of the Linux kernel. One of its greatest achievement is the + ability to extend the file system functionalities while maintaining the + internal structures. This allowed an easier development of the Third + Extended Filesystem (ext3) and the Fourth Extended Filesystem (ext4). + </p><p> + There are implementations available in most operating system including but + not limited to NetBSD, FreeBSD, the GNU HURD, Microsoft Windows, IBM OS/2 + and RISC OS. + </p><p> + Although newer file systems have been designed, such as Ext3 and Ext4, the + Second Extended Filesystem is still prefered on flash drives as it requires + fewer write operations (since it has no journal). The structures of Ext3 + and Ext4 are based on Ext2 and add some additional options such as journaling, + journal checksums, extents, online defragmentation, delayed allocations and + larger directories to name but a few. + </p></div><div class="chapter"><div class="titlepage"><div><div><h1 class="title"><a id="Definitions"></a>Chapter 2. Definitions</h1></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="sect1"><a href="#def-blocks">Blocks</a></span></dt><dt><span class="sect1"><a href="#def-block-groups">Block Groups</a></span></dt><dt><span class="sect1"><a href="#def-directories">Directories</a></span></dt><dt><span class="sect1"><a href="#def-inodes">Inodes</a></span></dt><dt><span class="sect1"><a href="#def-superblock">Superblocks</a></span></dt><dt><span class="sect1"><a href="#def-symbolic-links">Symbolic Links</a></span></dt></dl></div><p> + The Second Extended Filesystem uses blocks as the basic unit of storage, + inodes as the mean of keeping track of files and system objects, block groups + to logically split the disk into more manageable sections, directories to + provide a hierarchical organization of files, block and inode bitmaps to keep + track of allocated blocks and inodes, and superblocks to define + the parameters of the file system and its overall state. + </p><p> + Ext2 shares many properties with traditional Unix filesystems. It has space + in the specification for Access Control Lists (ACLs), fragments, undeletion + and compression. There is also a versioning mechanism to allow new + features (such as journalling) to be added in a maximally compatible + manner; such as in Ext3 and Ext4. + </p><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="def-blocks"></a>Blocks</h2></div></div></div><p> + A partition, disk, file or block device formated with a Second Extended + Filesystem is divided into small groups of sectors called <span class="quote">“<span class="quote">blocks</span>”</span>. These blocks are then grouped into larger units called block groups. + </p><p> + The size of the blocks are usually determined when formatting the disk + and will have an impact on performance, maximum file size, and maximum + file system size. Block sizes commonly implemented include 1KiB, + 2KiB, 4KiB and 8KiB although provisions in the superblock allow for + block sizes as big as 1024 * (2^31)-1 (see + <a class="link" href="#s-log-block-size" title="s_log_block_size">s_log_block_size</a>). + </p><p> + Depending on the implementation, some architectures may impose limits on + which block sizes are supported. For example, a Linux 2.6 + implementation on DEC Alpha uses blocks of 8KiB but the same + implementation on a Intel 386 processor will support a maximum block + size of 4KiB. + </p><div class="table"><a id="block-size-impact"></a><p class="title"><strong>Table 2.1. Impact of Block Sizes</strong></p><div class="table-contents"><table summary="Impact of Block Sizes" width="100%" border="1"><colgroup><col /><col /><col /><col /><col /></colgroup><thead><tr><th align="left">Upper Limits</th><th align="left">1KiB</th><th align="left">2KiB</th><th align="left">4KiB</th><th align="left">8KiB</th></tr></thead><tbody><tr><td align="left">file system blocks</td><td align="left">2,147,483,647</td><td align="left">2,147,483,647</td><td align="left">2,147,483,647</td><td align="left">2,147,483,647</td></tr><tr><td align="left">blocks per block group</td><td align="left">8,192</td><td align="left">16,384</td><td align="left">32,768</td><td align="left">65,536</td></tr><tr><td align="left">inodes per block group</td><td align="left">8,192</td><td align="left">16,384</td><td align="left">32,768</td><td align="left">65,536</td></tr><tr><td align="left">bytes per block group</td><td align="left">8,388,608 (8MiB)</td><td align="left">33,554,432 (32MiB)</td><td align="left">134,217,728 (128MiB)</td><td align="left">536,870,912 (512MiB)</td></tr><tr><td align="left">file system size (real)</td><td align="left">4,398,046,509,056 (4TiB)</td><td align="left">8,796,093,018,112 (8TiB)</td><td align="left">17,592,186,036,224 (16TiB)</td><td align="left">35,184,372,080,640 (32TiB)</td></tr><tr><td align="left">file system size (Linux)</td><td align="left">2,199,023,254,528 (2TiB) + <a href="#ftn.idm140660453588896" class="footnote" id="idm140660453588896"><sup class="footnote">[a]</sup></a> + </td><td align="left">8,796,093,018,112 (8TiB)</td><td align="left">17,592,186,036,224 (16TiB)</td><td align="left">35,184,372,080,640 (32TiB)</td></tr><tr><td align="left">blocks per file</td><td align="left">16,843,020</td><td align="left">134,217,728</td><td align="left">1,074,791,436</td><td align="left">8,594,130,956</td></tr><tr><td align="left">file size (real)</td><td align="left">17,247,252,480 (16GiB)</td><td align="left">274,877,906,944 (256GiB)</td><td align="left">2,199,023,255,552 (2TiB)</td><td align="left">2,199,023,255,552 (2TiB)</td></tr><tr><td align="left">file size (Linux 2.6.28)</td><td align="left">17,247,252,480 (16GiB)</td><td align="left">274,877,906,944 (256GiB)</td><td align="left">2,199,023,255,552 (2TiB)</td><td align="left">2,199,023,255,552 (2TiB)</td></tr></tbody><tbody class="footnotes"><tr><td colspan="5"><div id="ftn.idm140660453588896" class="footnote"><p><a href="#idm140660453588896" class="para"><sup class="para">[a] </sup></a> + This limit comes from the maximum size of a block device in + Linux 2.4; it is unclear whether a Linux 2.6 kernel using a 1KiB block + size could properly format and mount a Ext2 partition larger than 2TiB. + </p></div></td></tr></tbody></table></div></div><br class="table-break" /><p> + Note: the 2TiB file size is limited by the i_blocks value in the inode which indicates the number of 512-bytes sector rather than the actual number of ext2 blocks allocated. + </p></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="def-block-groups"></a>Block Groups</h2></div></div></div><div class="epigraph"><p> + This definition comes from the Linux Kernel Documentation. + </p></div><p> + Blocks are clustered into block groups in order to reduce fragmentation + and minimise the amount of head seeking when reading a large amount + of consecutive data. Information about each block group is kept in a + descriptor table stored in the block(s) immediately after the superblock. + Two blocks near the start of each group are reserved for the block usage + bitmap and the inode usage bitmap which show which blocks and inodes + are in use. Since each bitmap is limited to a single block, this means + that the maximum size of a block group is 8 times the size of a block. + </p><p> + The block(s) following the bitmaps in each block group are designated + as the inode table for that block group and the remainder are the data + blocks. The block allocation algorithm attempts to allocate data blocks + in the same block group as the inode which contains them. + </p></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="def-directories"></a>Directories</h2></div></div></div><div class="epigraph"><p> + This definition comes from the Linux Kernel Documentation with some minor + alterations. + </p></div><p> + A directory is a filesystem object and has an inode just like a file. + It is a specially formatted file containing records which associate + each name with an inode number. Later revisions of the filesystem also + encode the type of the object (file, directory, symlink, device, fifo, + socket) to avoid the need to check the inode itself for this information + </p><p> + The inode allocation code should try to assign inodes which are in the same + block group as the directory in which they are first created. + </p><p> + The original Ext2 revision used singly-linked list to store + the filenames in the directory; newer revisions are able to use hashes + and binary trees. + </p><p> + Also note that as directory grows additional blocks are assigned to + store the additional file records. When filenames are removed, some + implementations do not free these additional blocks. + </p></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="def-inodes"></a>Inodes</h2></div></div></div><div class="epigraph"><p> + This definition comes from the Linux Kernel Documentation with some minor + alterations. + </p></div><p> + The inode (index node) is a fundamental concept in the ext2 filesystem. + Each object in the filesystem is represented by an inode. The inode + structure contains pointers to the filesystem blocks which contain the + data held in the object and all of the metadata about an object except + its name. The metadata about an object includes the permissions, owner, + group, flags, size, number of blocks used, access time, change time, + modification time, deletion time, number of links, fragments, version + (for NFS) and extended attributes (EAs) and/or Access Control Lists (ACLs). + </p><p> + There are some reserved fields which are currently unused in the inode + structure and several which are overloaded. One field is reserved for the + directory ACL if the inode is a directory and alternately for the top 32 + bits of the file size if the inode is a regular file (allowing file sizes + larger than 2GB). The translator field is unused under Linux, but is used + by the HURD to reference the inode of a program which will be used to + interpret this object. Most of the remaining reserved fields have been + used up for both Linux and the HURD for larger owner and group fields, + The HURD also has a larger mode field so it uses another of the remaining + fields to store the extra bits. + </p><p> + There are pointers to the first 12 blocks which contain the file's data + in the inode. There is a pointer to an indirect block (which contains + pointers to the next set of blocks), a pointer to a doubly-indirect + block (which contains pointers to indirect blocks) and a pointer to a + trebly-indirect block (which contains pointers to doubly-indirect blocks). + </p><p> + Some filesystem specific behaviour flags are also stored and allow for + specific filesystem behaviour on a per-file basis. There are flags for + secure deletion, undeletable, compression, synchronous updates, + immutability, append-only, dumpable, no-atime, indexed directories, and + data-journaling. + </p><p> + Many of the filesystem specific behaviour flags, like journaling, have been + implemented in newer filesystems like Ext3 and Ext4, while some other + are still under development. + </p><p> + All the inodes are stored in inode tables, with one inode table per block group. + </p></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="def-superblock"></a>Superblocks</h2></div></div></div><div class="epigraph"><p> + This definition comes from the Linux Kernel Documentation with some minor + alterations. + </p></div><p> + The superblock contains all the information about the configuration of + the filesystem. The information in the superblock contains fields + such as the total number of inodes and blocks in the filesystem and how + many are free, how many inodes and blocks are in each block group, when + the filesystem was mounted (and if it was cleanly unmounted), when it + was modified, what version of the filesystem it is and which OS created + it. + </p><p> + The primary copy of the superblock is stored at an offset of 1024 bytes + from the start of the device, and it is essential to mounting the + filesystem. Since it is so important, backup copies of the superblock + are stored in block groups throughout the filesystem. + </p><p> + The first version of ext2 (revision 0) stores a copy at the start of + every block group, along with backups of the group descriptor block(s). + Because this can consume a considerable amount of space for large + filesystems, later revisions can optionally reduce the number of backup + copies by only putting backups in specific groups (this is the sparse + superblock feature). The groups chosen are 0, 1 and powers of 3, 5 and 7. + </p><p> + Revision 1 and higher of the filesystem also store extra fields, such as + a volume name, a unique identification number, the inode size, and space + for optional filesystem features to store configuration info. + </p><p> + All fields in the superblock (as in all other ext2 structures) are stored + on the disc in little endian format, so a filesystem is portable between + machines without having to know what machine it was created on. + </p></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="def-symbolic-links"></a>Symbolic Links</h2></div></div></div><div class="epigraph"><p> + This definition comes from Wikipedia.org with some minor + alterations. + </p></div><p> + A symbolic link (also symlink or soft link) is a special type of file that + contains a reference to another file or directory in the form of an + absolute or relative path and that affects pathname resolution. + </p><p> + Symbolic links operate transparently for most operations: programs which + read or write to files named by a symbolic link will behave as if + operating directly on the target file. However, programs that need to + handle symbolic links specially (e.g., backup utilities) may identify + and manipulate them directly. + </p><p> + A symbolic link merely contains a text string that is interpreted and + followed by the operating system as a path to another file or directory. + It is a file on its own and can exist independently of its target. The + symbolic links do not affect an inode link count. If a symbolic link is + deleted, its target remains unaffected. If the target is moved, renamed + or deleted, any symbolic link that used to point to it continues to exist + but now points to a non-existing file. Symbolic links pointing to + non-existing files are sometimes called <span class="quote">“<span class="quote">orphaned</span>”</span> or + <span class="quote">“<span class="quote">dangling</span>”</span>. + </p><p> + Symbolic links are also filesystem objects with inodes. For all symlink + shorter than 60 bytes long, the data is stored within the inode itself; it + uses the fields which would normally be used to store the pointers to data + blocks. This is a worthwhile optimisation as it we avoid allocating a full + block for the symlink, and most symlinks are less than 60 characters long. + </p><p> + Symbolic links can also point to files or directories of other partitions + and file systems. + </p></div></div><div class="chapter"><div class="titlepage"><div><div><h1 class="title"><a id="disk-organisation"></a>Chapter 3. Disk Organization</h1></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="sect1"><a href="#superblock">Superblock</a></span></dt><dd><dl><dt><span class="sect2"><a href="#s-inodes-count">s_inodes_count</a></span></dt><dt><span class="sect2"><a href="#s-blocks-count">s_blocks_count</a></span></dt><dt><span class="sect2"><a href="#s-r-blocks-count">s_r_blocks_count</a></span></dt><dt><span class="sect2"><a href="#s-free-blocks-count">s_free_blocks_count</a></span></dt><dt><span class="sect2"><a href="#s-free-inodes-count">s_free_inodes_count</a></span></dt><dt><span class="sect2"><a href="#s-first-data-block">s_first_data_block</a></span></dt><dt><span class="sect2"><a href="#s-log-block-size">s_log_block_size</a></span></dt><dt><span class="sect2"><a href="#s-log-frag-size">s_log_frag_size</a></span></dt><dt><span class="sect2"><a href="#s-blocks-per-group">s_blocks_per_group</a></span></dt><dt><span class="sect2"><a href="#s-frags-per-group">s_frags_per_group</a></span></dt><dt><span class="sect2"><a href="#s-inodes-per-group">s_inodes_per_group</a></span></dt><dt><span class="sect2"><a href="#s-mtime">s_mtime</a></span></dt><dt><span class="sect2"><a href="#s-wtime">s_wtime</a></span></dt><dt><span class="sect2"><a href="#s-mnt-count">s_mnt_count</a></span></dt><dt><span class="sect2"><a href="#s-max-mnt-count">s_max_mnt_count</a></span></dt><dt><span class="sect2"><a href="#s-magic">s_magic</a></span></dt><dt><span class="sect2"><a href="#s-state">s_state</a></span></dt><dt><span class="sect2"><a href="#s-errors">s_errors</a></span></dt><dt><span class="sect2"><a href="#s-minor-rev-level">s_minor_rev_level</a></span></dt><dt><span class="sect2"><a href="#s-lastcheck">s_lastcheck</a></span></dt><dt><span class="sect2"><a href="#s-checkinterval">s_checkinterval</a></span></dt><dt><span class="sect2"><a href="#s-creator-os">s_creator_os</a></span></dt><dt><span class="sect2"><a href="#s-rev-level">s_rev_level</a></span></dt><dt><span class="sect2"><a href="#s-def-resuid">s_def_resuid</a></span></dt><dt><span class="sect2"><a href="#s-def-resgid">s_def_resgid</a></span></dt><dt><span class="sect2"><a href="#s-first-ino">s_first_ino</a></span></dt><dt><span class="sect2"><a href="#s-inode-size">s_inode_size</a></span></dt><dt><span class="sect2"><a href="#s-block-group-nr">s_block_group_nr</a></span></dt><dt><span class="sect2"><a href="#s-feature-compat">s_feature_compat</a></span></dt><dt><span class="sect2"><a href="#s-feature-incompat">s_feature_incompat</a></span></dt><dt><span class="sect2"><a href="#s-feature-ro-compat">s_feature_ro_compat</a></span></dt><dt><span class="sect2"><a href="#s-uuid">s_uuid</a></span></dt><dt><span class="sect2"><a href="#s-volume-name">s_volume_name</a></span></dt><dt><span class="sect2"><a href="#s-last-mounted">s_last_mounted</a></span></dt><dt><span class="sect2"><a href="#s-algo-bitmap">s_algo_bitmap</a></span></dt><dt><span class="sect2"><a href="#s-prealloc-blocks">s_prealloc_blocks</a></span></dt><dt><span class="sect2"><a href="#s-prealloc-dir-blocks">s_prealloc_dir_blocks</a></span></dt><dt><span class="sect2"><a href="#s-journal-uuid">s_journal_uuid</a></span></dt><dt><span class="sect2"><a href="#s-journal-inum">s_journal_inum</a></span></dt><dt><span class="sect2"><a href="#s-journal-dev">s_journal_dev</a></span></dt><dt><span class="sect2"><a href="#s-last-orphan">s_last_orphan</a></span></dt><dt><span class="sect2"><a href="#s-hash-seed">s_hash_seed</a></span></dt><dt><span class="sect2"><a href="#s-def-hash-version">s_def_hash_version</a></span></dt><dt><span class="sect2"><a href="#s-default-mount-options">s_default_mount_options</a></span></dt><dt><span class="sect2"><a href="#s-first-meta-bg">s_first_meta_bg</a></span></dt></dl></dd><dt><span class="sect1"><a href="#block-group-descriptor-table">Block Group Descriptor Table</a></span></dt><dd><dl><dt><span class="sect2"><a href="#bg-block-bitmap">bg_block_bitmap</a></span></dt><dt><span class="sect2"><a href="#bg-inode-bitmap">bg_inode_bitmap</a></span></dt><dt><span class="sect2"><a href="#bg-inode-table">bg_inode_table</a></span></dt><dt><span class="sect2"><a href="#bg-free-blocks-count">bg_free_blocks_count</a></span></dt><dt><span class="sect2"><a href="#bg-free-inodes-count">bg_free_inodes_count</a></span></dt><dt><span class="sect2"><a href="#bg-used-dirs-count">bg_used_dirs_count</a></span></dt><dt><span class="sect2"><a href="#bg-pad">bg_pad</a></span></dt><dt><span class="sect2"><a href="#bg-reserved">bg_reserved</a></span></dt></dl></dd><dt><span class="sect1"><a href="#block-bitmap">Block Bitmap</a></span></dt><dt><span class="sect1"><a href="#inode-bitmap">Inode Bitmap</a></span></dt><dt><span class="sect1"><a href="#inode-table">Inode Table</a></span></dt><dd><dl><dt><span class="sect2"><a href="#i-mode">i_mode</a></span></dt><dt><span class="sect2"><a href="#i-uid">i_uid</a></span></dt><dt><span class="sect2"><a href="#i-size">i_size</a></span></dt><dt><span class="sect2"><a href="#i-atime">i_atime</a></span></dt><dt><span class="sect2"><a href="#i-ctime">i_ctime</a></span></dt><dt><span class="sect2"><a href="#i-mtime">i_mtime</a></span></dt><dt><span class="sect2"><a href="#i-dtime">i_dtime</a></span></dt><dt><span class="sect2"><a href="#i-gid">i_gid</a></span></dt><dt><span class="sect2"><a href="#i-links-count">i_links_count</a></span></dt><dt><span class="sect2"><a href="#i-blocks">i_blocks</a></span></dt><dt><span class="sect2"><a href="#i-flags">i_flags</a></span></dt><dt><span class="sect2"><a href="#i-osd1">i_osd1</a></span></dt><dt><span class="sect2"><a href="#i-block">i_block</a></span></dt><dt><span class="sect2"><a href="#i-generation">i_generation</a></span></dt><dt><span class="sect2"><a href="#i-file-acl">i_file_acl</a></span></dt><dt><span class="sect2"><a href="#i-dir-acl">i_dir_acl</a></span></dt><dt><span class="sect2"><a href="#i-faddr">i_faddr</a></span></dt><dt><span class="sect2"><a href="#i-osd2">Inode i_osd2 Structure</a></span></dt></dl></dd><dt><span class="sect1"><a href="#idm140660447281728">Locating an Inode</a></span></dt></dl></div><p> + An Ext2 file systems starts with a <a class="link" href="#superblock" title="Superblock">superblock</a> + located at byte offset 1024 from the start of the volume. This is block 1 + for a 1KiB block formatted volume or within block 0 for larger block sizes. Note that the size of the superblock is constant regardless of the block size. + </p><p> + On the next block(s) following the superblock, is the + Block Group Descriptor Table; which provides an overview of how the volume + is split into block groups and where to find the inode bitmap, the block bitmap, + and the inode table for each block group. + </p><p> + In revision 0 of Ext2, each block group consists of a copy superblock, a copy of the + block group descriptor table, a block bitmap, an inode bitmap, an inode table, + and data blocks. + </p><p> + With the introduction of revision 1 and the sparse superblock feature in Ext2, + only specific block groups contain copies of the superblock and block group + descriptor table. All block groups still contain the block bitmap, inode + bitmap, inode table, and data blocks. The shadow copies of the superblock can + be located in block groups 0, 1 and powers of 3, 5 and 7. + </p><p> + The block bitmap and inode bitmap are limited to 1 block each per block group, + so the total blocks per block group is therefore limited. (More information in + the <a class="link" href="#block-size-impact" title="Table 2.1. Impact of Block Sizes">Block Size Impact</a> table). + </p><p> + Each data block may also be further divided into <span class="quote">“<span class="quote">fragments</span>”</span>. As of + Linux 2.6.28, support for fragment was still not implemented in the kernel; + it is therefore suggested to ensure the fragment size is equal to the + block size so as to maintain compatibility. + </p><div class="table"><a id="disk-layout-sample-floppy"></a><p class="title"><strong>Table 3.1. Sample Floppy Disk Layout, 1KiB blocks</strong></p><div class="table-contents"><table summary="Sample Floppy Disk Layout, 1KiB blocks" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Block Offset</th><th>Length</th><th>Description</th></tr></thead><tbody><tr><td>byte 0</td><td>512 bytes</td><td>boot record (if present)</td></tr><tr><td>byte 512</td><td>512 bytes</td><td>additional boot record data (if present)</td></tr><tr><td colspan="3" align="left">-- block group 0, blocks 1 to 1439 --</td></tr><tr><td>byte 1024</td><td>1024 bytes</td><td><a class="link" href="#superblock" title="Superblock">superblock</a></td></tr><tr><td>block 2</td><td>1 block</td><td><a class="link" href="#block-group-descriptor-table" title="Block Group Descriptor Table">block group descriptor table</a></td></tr><tr><td>block 3</td><td>1 block</td><td><a class="link" href="#block-bitmap" title="Block Bitmap">block bitmap</a></td></tr><tr><td>block 4</td><td>1 block</td><td><a class="link" href="#inode-bitmap" title="Inode Bitmap">inode bitmap</a></td></tr><tr><td>block 5</td><td>23 blocks</td><td><a class="link" href="#inode-table" title="Inode Table">inode table</a></td></tr><tr><td>block 28</td><td>1412 blocks</td><td>data blocks</td></tr></tbody></table></div></div><br class="table-break" /><p> + For the curious, block 0 always points to the first sector of the disk + or partition and will always contain the boot record if one is present. + </p><p> + The superblock is always located at byte offset 1024 from the start of + the disk or partition. In a 1KiB block-size formatted file system, this is + block 1, but it will always be block 0 (at 1024 bytes within block 0) in + larger block size file systems. + </p><p> + And here's the organisation of a 20MB ext2 file system, using 1KiB blocks: + </p><div class="table"><a id="disk-layout-sample-20mb"></a><p class="title"><strong>Table 3.2. Sample 20mb Partition Layout</strong></p><div class="table-contents"><table summary="Sample 20mb Partition Layout" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Block Offset</th><th>Length</th><th>Description</th></tr></thead><tbody><tr><td>byte 0</td><td>512 bytes</td><td>boot record (if present)</td></tr><tr><td>byte 512</td><td>512 bytes</td><td>additional boot record data (if present)</td></tr><tr><td colspan="3" align="left">-- block group 0, blocks 1 to 8192 --</td></tr><tr><td>byte 1024</td><td>1024 bytes</td><td><a class="link" href="#superblock" title="Superblock">superblock</a></td></tr><tr><td>block 2</td><td>1 block</td><td><a class="link" href="#block-group-descriptor-table" title="Block Group Descriptor Table">block group descriptor table</a></td></tr><tr><td>block 3</td><td>1 block</td><td><a class="link" href="#block-bitmap" title="Block Bitmap">block bitmap</a></td></tr><tr><td>block 4</td><td>1 block</td><td><a class="link" href="#inode-bitmap" title="Inode Bitmap">inode bitmap</a></td></tr><tr><td>block 5</td><td>214 blocks</td><td><a class="link" href="#inode-table" title="Inode Table">inode table</a></td></tr><tr><td>block 219</td><td>7974 blocks</td><td>data blocks</td></tr><tr><td colspan="3" align="left">-- block group 1, blocks 8193 to 16384 --</td></tr><tr><td>block 8193</td><td>1 block</td><td><a class="link" href="#superblock" title="Superblock">superblock</a> backup</td></tr><tr><td>block 8194</td><td>1 block</td><td><a class="link" href="#block-group-descriptor-table" title="Block Group Descriptor Table">block group descriptor table</a> backup</td></tr><tr><td>block 8195</td><td>1 block</td><td><a class="link" href="#block-bitmap" title="Block Bitmap">block bitmap</a></td></tr><tr><td>block 8196</td><td>1 block</td><td><a class="link" href="#inode-bitmap" title="Inode Bitmap">inode bitmap</a></td></tr><tr><td>block 8197</td><td>214 blocks</td><td><a class="link" href="#inode-table" title="Inode Table">inode table</a></td></tr><tr><td>block 8408</td><td>7974 blocks</td><td>data blocks</td></tr><tr><td colspan="3" align="left">-- block group 2, blocks 16385 to 24576 --</td></tr><tr><td>block 16385</td><td>1 block</td><td><a class="link" href="#block-bitmap" title="Block Bitmap">block bitmap</a></td></tr><tr><td>block 16386</td><td>1 block</td><td><a class="link" href="#inode-bitmap" title="Inode Bitmap">inode bitmap</a></td></tr><tr><td>block 16387</td><td>214 blocks</td><td><a class="link" href="#inode-table" title="Inode Table">inode table</a></td></tr><tr><td>block 16601</td><td>3879 blocks</td><td>data blocks</td></tr></tbody></table></div></div><br class="table-break" /><p> + The layout on disk is very predictable as long as you know a few basic + information; block size, blocks per group, inodes per group. This + information is all located in, or can be computed from, the + <span class="structname">superblock</span> structure. + </p><p> + Nevertheless, unless the image was crafted with controlled parameters, + the position of the various structures on disk (except the superblock) + should never be assumed. Always load the superblock first. + </p><p> + Notice how block 0 is not part of the block group 0 in 1KiB block + size file systems. The reason for this is block group 0 always starts + with the block containing the superblock. Hence, on 1KiB block systems, + block group 0 starts at block 1, but on larger block sizes it starts on + block 0. For more information, see the + <a class="link" href="#s-first-data-block" title="s_first_data_block">s_first_data_block</a> superblock + entry. + </p><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="superblock"></a>Superblock</h2></div></div></div><p> + The <a class="link" href="#def-superblock" title="Superblocks">superblock</a> is always located at + byte offset 1024 from the beginning of the file, block device or + partition formatted with Ext2 and later variants (Ext3, Ext4). + </p><p> + Its structure is mostly constant from Ext2 to Ext3 and Ext4 with only + some minor changes. + </p><div class="table"><a id="superblock-structure"></a><p class="title"><strong>Table 3.3. Superblock Structure</strong></p><div class="table-contents"><table summary="Superblock Structure" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>4</td><td><a class="link" href="#s-inodes-count" title="s_inodes_count">s_inodes_count</a></td></tr><tr><td>4</td><td>4</td><td><a class="link" href="#s-blocks-count" title="s_blocks_count">s_blocks_count</a></td></tr><tr><td>8</td><td>4</td><td><a class="link" href="#s-r-blocks-count" title="s_r_blocks_count">s_r_blocks_count</a></td></tr><tr><td>12</td><td>4</td><td><a class="link" href="#s-free-blocks-count" title="s_free_blocks_count">s_free_blocks_count</a></td></tr><tr><td>16</td><td>4</td><td><a class="link" href="#s-free-inodes-count" title="s_free_inodes_count">s_free_inodes_count</a></td></tr><tr><td>20</td><td>4</td><td><a class="link" href="#s-first-data-block" title="s_first_data_block">s_first_data_block</a></td></tr><tr><td>24</td><td>4</td><td><a class="link" href="#s-log-block-size" title="s_log_block_size">s_log_block_size</a></td></tr><tr><td>28</td><td>4</td><td><a class="link" href="#s-log-frag-size" title="s_log_frag_size">s_log_frag_size</a></td></tr><tr><td>32</td><td>4</td><td><a class="link" href="#s-blocks-per-group" title="s_blocks_per_group">s_blocks_per_group</a></td></tr><tr><td>36</td><td>4</td><td><a class="link" href="#s-frags-per-group" title="s_frags_per_group">s_frags_per_group</a></td></tr><tr><td>40</td><td>4</td><td><a class="link" href="#s-inodes-per-group" title="s_inodes_per_group">s_inodes_per_group</a></td></tr><tr><td>44</td><td>4</td><td><a class="link" href="#s-mtime" title="s_mtime">s_mtime</a></td></tr><tr><td>48</td><td>4</td><td><a class="link" href="#s-wtime" title="s_wtime">s_wtime</a></td></tr><tr><td>52</td><td>2</td><td><a class="link" href="#s-mnt-count" title="s_mnt_count">s_mnt_count</a></td></tr><tr><td>54</td><td>2</td><td><a class="link" href="#s-max-mnt-count" title="s_max_mnt_count">s_max_mnt_count</a></td></tr><tr><td>56</td><td>2</td><td><a class="link" href="#s-magic" title="s_magic">s_magic</a></td></tr><tr><td>58</td><td>2</td><td><a class="link" href="#s-state" title="s_state">s_state</a></td></tr><tr><td>60</td><td>2</td><td><a class="link" href="#s-errors" title="s_errors">s_errors</a></td></tr><tr><td>62</td><td>2</td><td><a class="link" href="#s-minor-rev-level" title="s_minor_rev_level">s_minor_rev_level</a></td></tr><tr><td>64</td><td>4</td><td><a class="link" href="#s-lastcheck" title="s_lastcheck">s_lastcheck</a></td></tr><tr><td>68</td><td>4</td><td><a class="link" href="#s-checkinterval" title="s_checkinterval">s_checkinterval</a></td></tr><tr><td>72</td><td>4</td><td><a class="link" href="#s-creator-os" title="s_creator_os">s_creator_os</a></td></tr><tr><td>76</td><td>4</td><td><a class="link" href="#s-rev-level" title="s_rev_level">s_rev_level</a></td></tr><tr><td>80</td><td>2</td><td><a class="link" href="#s-def-resuid" title="s_def_resuid">s_def_resuid</a></td></tr><tr><td>82</td><td>2</td><td><a class="link" href="#s-def-resgid" title="s_def_resgid">s_def_resgid</a></td></tr><tr><td colspan="3" align="left">-- EXT2_DYNAMIC_REV Specific --</td></tr><tr><td>84</td><td>4</td><td><a class="link" href="#s-first-ino" title="s_first_ino">s_first_ino</a></td></tr><tr><td>88</td><td>2</td><td><a class="link" href="#s-inode-size" title="s_inode_size">s_inode_size</a></td></tr><tr><td>90</td><td>2</td><td><a class="link" href="#s-block-group-nr" title="s_block_group_nr">s_block_group_nr</a></td></tr><tr><td>92</td><td>4</td><td><a class="link" href="#s-feature-compat" title="s_feature_compat">s_feature_compat</a></td></tr><tr><td>96</td><td>4</td><td><a class="link" href="#s-feature-incompat" title="s_feature_incompat">s_feature_incompat</a></td></tr><tr><td>100</td><td>4</td><td><a class="link" href="#s-feature-ro-compat" title="s_feature_ro_compat">s_feature_ro_compat</a></td></tr><tr><td>104</td><td>16</td><td><a class="link" href="#s-uuid" title="s_uuid">s_uuid</a></td></tr><tr><td>120</td><td>16</td><td><a class="link" href="#s-volume-name" title="s_volume_name">s_volume_name</a></td></tr><tr><td>136</td><td>64</td><td><a class="link" href="#s-last-mounted" title="s_last_mounted">s_last_mounted</a></td></tr><tr><td>200</td><td>4</td><td><a class="link" href="#s-algo-bitmap" title="s_algo_bitmap">s_algo_bitmap</a></td></tr><tr><td colspan="3" align="left">-- Performance Hints --</td></tr><tr><td>204</td><td>1</td><td><a class="link" href="#s-prealloc-blocks" title="s_prealloc_blocks">s_prealloc_blocks</a></td></tr><tr><td>205</td><td>1</td><td><a class="link" href="#s-prealloc-dir-blocks" title="s_prealloc_dir_blocks">s_prealloc_dir_blocks</a></td></tr><tr><td>206</td><td>2</td><td>(alignment)</td></tr><tr><td colspan="3" align="left">-- Journaling Support --</td></tr><tr><td>208</td><td>16</td><td><a class="link" href="#s-journal-uuid" title="s_journal_uuid">s_journal_uuid</a></td></tr><tr><td>224</td><td>4</td><td><a class="link" href="#s-journal-inum" title="s_journal_inum">s_journal_inum</a></td></tr><tr><td>228</td><td>4</td><td><a class="link" href="#s-journal-dev" title="s_journal_dev">s_journal_dev</a></td></tr><tr><td>232</td><td>4</td><td><a class="link" href="#s-last-orphan" title="s_last_orphan">s_last_orphan</a></td></tr><tr><td colspan="3" align="left">-- Directory Indexing Support --</td></tr><tr><td>236</td><td>4 x 4</td><td><a class="link" href="#s-hash-seed" title="s_hash_seed">s_hash_seed</a></td></tr><tr><td>252</td><td>1</td><td><a class="link" href="#s-def-hash-version" title="s_def_hash_version">s_def_hash_version</a></td></tr><tr><td>253</td><td>3</td><td>padding - reserved for future expansion</td></tr><tr><td colspan="3" align="left">-- Other options --</td></tr><tr><td>256</td><td>4</td><td><a class="link" href="#s-default-mount-options" title="s_default_mount_options">s_default_mount_options</a></td></tr><tr><td>260</td><td>4</td><td><a class="link" href="#s-first-meta-bg" title="s_first_meta_bg">s_first_meta_bg</a></td></tr><tr><td>264</td><td>760</td><td>Unused - reserved for future revisions</td></tr></tbody></table></div></div><br class="table-break" /><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-inodes-count"></a>s_inodes_count</h3></div></div></div><p> + 32bit value indicating the total number of inodes, both used and free, + in the file system. This value must be lower or equal to + (s_inodes_per_group * number of block groups). It must be equal to the + sum of the inodes defined in each block group. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-blocks-count"></a>s_blocks_count</h3></div></div></div><p> + 32bit value indicating the total number of blocks in the system including + all used, free and reserved. This value must be lower or equal to + (s_blocks_per_group * number of block groups). It can be lower than + the previous calculation if the last block group has a smaller number of + blocks than s_blocks_per_group du to volume size. It must be equal to + the sum of the blocks defined in each block group. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-r-blocks-count"></a>s_r_blocks_count</h3></div></div></div><p> + 32bit value indicating the total number of blocks reserved for the + usage of the super user. This is most useful if for some reason a + user, maliciously or not, fill the file system to capacity; the super + user will have this specified amount of free blocks at his disposal so + he can edit and save configuration files. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-free-blocks-count"></a>s_free_blocks_count</h3></div></div></div><p> + 32bit value indicating the total number of free blocks, including the + number of reserved blocks (see + <a class="link" href="#s-r-blocks-count" title="s_r_blocks_count">s_r_blocks_count</a>). This is a sum + of all free blocks of all the block groups. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-free-inodes-count"></a>s_free_inodes_count</h3></div></div></div><p> + 32bit value indicating the total number of free inodes. This is a sum + of all free inodes of all the block groups. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-first-data-block"></a>s_first_data_block</h3></div></div></div><p> + 32bit value identifying the first data block, in other word the id of + the block containing the <span class="structname">superblock</span> structure. + </p><p> + Note that this value is always 0 for file systems with a block size + larger than 1KB, and always 1 for file systems with a block size of + 1KB. The <span class="structname">superblock</span> is <span class="emphasis"><em>always</em></span> starting at + the 1024th byte of the disk, which normally happens to be the first + byte of the 3rd sector. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-log-block-size"></a>s_log_block_size</h3></div></div></div><p> + The block size is computed using this 32bit value as the number of + bits to shift left the value 1024. This value may only be non-negative. + </p><pre class="programlisting"> +block size = 1024 << s_log_block_size; + </pre><p> + Common block sizes include 1KiB, 2KiB, 4KiB and 8Kib. For information + about the impact of selecting a block size, see + <a class="link" href="#block-size-impact" title="Table 2.1. Impact of Block Sizes">Impact of Block Sizes</a>. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + In Linux, at least up to 2.6.28, the block size must be at least as + large as the sector size of the block device, and cannot be larger than + the supported memory page of the architecture. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-log-frag-size"></a>s_log_frag_size</h3></div></div></div><p> + The fragment size is computed using this 32bit value as the number of + bits to shift left the value 1024. Note that a negative value would + shift the bit right rather than left. + </p><pre class="programlisting"> +if( positive ) + fragmnet size = 1024 << s_log_frag_size; +else + framgnet size = 1024 >> -s_log_frag_size; + </pre><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + As of Linux 2.6.28 no support exists for an Ext2 + partition with fragment size smaller than the block size, as this feature + seems to not be available. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-blocks-per-group"></a>s_blocks_per_group</h3></div></div></div><p> + 32bit value indicating the total number of blocks per group. This + value in combination with + <a class="link" href="#s-first-data-block" title="s_first_data_block">s_first_data_block</a> can be used + to determine the block groups boundaries. Due to volume size boundaries, + the last block group might have a smaller number of blocks than what is + specified in this field. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-frags-per-group"></a>s_frags_per_group</h3></div></div></div><p> + 32bit value indicating the total number of fragments per group. It is + also used to determine the size of the <span class="structname">block bitmap</span> of + each block group. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-inodes-per-group"></a>s_inodes_per_group</h3></div></div></div><p> + 32bit value indicating the total number of inodes per group. This is + also used to determine the size of the <span class="structname">inode bitmap</span> of + each block group. Note that you cannot have more than + (block size in bytes * 8) inodes per group as the inode bitmap + must fit within a single block. This value must be a perfect multiple + of the number of inodes that can fit in a block + ((1024<<s_log_block_size)/s_inode_size). + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-mtime"></a>s_mtime</h3></div></div></div><p> + Unix time, as defined by POSIX, of the last time the file system was + mounted. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-wtime"></a>s_wtime</h3></div></div></div><p> + Unix time, as defined by POSIX, of the last write access to the file + system. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-mnt-count"></a>s_mnt_count</h3></div></div></div><p> + 16bit value indicating how many time the file system was mounted + since the last time it was fully verified. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-max-mnt-count"></a>s_max_mnt_count</h3></div></div></div><p> + 16bit value indicating the maximum number of times that the file + system may be mounted before a full check is performed. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-magic"></a>s_magic</h3></div></div></div><p> + 16bit value identifying the file system as Ext2. The value is + currently fixed to <code class="constant">EXT2_SUPER_MAGIC</code> of value 0xEF53. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-state"></a>s_state</h3></div></div></div><p> + 16bit value indicating the file system state. When the file system is + mounted, this state is set to <code class="constant">EXT2_ERROR_FS</code>. After the + file system was cleanly unmounted, this value is set to <code class="constant">EXT2_VALID_FS</code>. + </p><p> + When mounting the file system, if a valid of <code class="constant">EXT2_ERROR_FS</code> is + encountered it means the file system was not cleanly unmounted and most + likely contain errors that will need to be fixed. Typically under Linux + this means running fsck. + </p><div class="table"><a id="s-state-values"></a><p class="title"><strong>Table 3.4. Defined s_state Values</strong></p><div class="table-contents"><table summary="Defined s_state Values" width="100%" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td align="left">EXT2_VALID_FS</td><td align="left">1</td><td align="left">Unmounted cleanly</td></tr><tr><td align="left">EXT2_ERROR_FS</td><td align="left">2</td><td align="left">Errors detected</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-errors"></a>s_errors</h3></div></div></div><p> + 16bit value indicating what the file system driver should do when an + error is detected. The following values have been defined: + </p><div class="table"><a id="ext2-errors"></a><p class="title"><strong>Table 3.5. Defined s_errors Values</strong></p><div class="table-contents"><table summary="Defined s_errors Values" width="100%" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td align="left">EXT2_ERRORS_CONTINUE</td><td align="left">1</td><td align="left">continue as if nothing happened</td></tr><tr><td align="left">EXT2_ERRORS_RO</td><td align="left">2</td><td align="left">remount read-only</td></tr><tr><td align="left">EXT2_ERRORS_PANIC</td><td align="left">3</td><td align="left">cause a kernel panic</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-minor-rev-level"></a>s_minor_rev_level</h3></div></div></div><p> + 16bit value identifying the minor revision level within its + <a class="link" href="#s-rev-level" title="s_rev_level">revision level</a>. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-lastcheck"></a>s_lastcheck</h3></div></div></div><p> + Unix time, as defined by POSIX, of the last file system check. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-checkinterval"></a>s_checkinterval</h3></div></div></div><p> + Maximum Unix time interval, as defined by POSIX, allowed between file + system checks. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-creator-os"></a>s_creator_os</h3></div></div></div><p> + 32bit identifier of the os that created the file system. Defined + values are: + </p><div class="table"><a id="s-creator-os-values"></a><p class="title"><strong>Table 3.6. Defined s_creator_os Values</strong></p><div class="table-contents"><table summary="Defined s_creator_os Values" width="100%" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td align="left">EXT2_OS_LINUX</td><td align="left">0</td><td align="left">Linux</td></tr><tr><td align="left">EXT2_OS_HURD</td><td align="left">1</td><td align="left">GNU HURD</td></tr><tr><td align="left">EXT2_OS_MASIX</td><td align="left">2</td><td align="left">MASIX</td></tr><tr><td align="left">EXT2_OS_FREEBSD</td><td align="left">3</td><td align="left">FreeBSD</td></tr><tr><td align="left">EXT2_OS_LITES</td><td align="left">4</td><td align="left">Lites</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-rev-level"></a>s_rev_level</h3></div></div></div><p> + 32bit revision level value. + </p><div class="table"><a id="s-rev-level-values"></a><p class="title"><strong>Table 3.7. Defined s_rev_level Values</strong></p><div class="table-contents"><table summary="Defined s_rev_level Values" width="100%" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td align="left">EXT2_GOOD_OLD_REV</td><td align="left">0</td><td align="left">Revision 0</td></tr><tr><td align="left">EXT2_DYNAMIC_REV</td><td align="left">1</td><td align="left">Revision 1 with variable inode sizes, extended attributes, etc.</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-def-resuid"></a>s_def_resuid</h3></div></div></div><p> + 16bit value used as the default user id for reserved blocks. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + In Linux this defaults to <code class="constant">EXT2_DEF_RESUID</code> of 0. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-def-resgid"></a>s_def_resgid</h3></div></div></div><p> + 16bit value used as the default group id for reserved blocks. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + In Linux this defaults to <code class="constant">EXT2_DEF_RESGID</code> of 0. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-first-ino"></a>s_first_ino</h3></div></div></div><p> + 32bit value used as index to the first inode useable for standard + files. In revision 0, the first non-reserved inode is fixed to + 11 (<code class="constant">EXT2_GOOD_OLD_FIRST_INO</code>). In revision 1 and later + this value may be set to any value. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-inode-size"></a>s_inode_size</h3></div></div></div><p> + 16bit value indicating the size of the inode structure. In revision 0, this + value is always 128 (<code class="constant">EXT2_GOOD_OLD_INODE_SIZE</code>). In revision 1 + and later, this value must be a perfect power of 2 and must be smaller or + equal to the block size (1<<s_log_block_size). + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-block-group-nr"></a>s_block_group_nr</h3></div></div></div><p> + 16bit value used to indicate the block group number hosting this + superblock structure. This can be used to rebuild the file system + from any superblock backup. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-feature-compat"></a>s_feature_compat</h3></div></div></div><p> + 32bit bitmask of compatible features. The file system implementation + is free to support them or not without risk of damaging the meta-data. + </p><div class="table"><a id="s-feature-compat-values"></a><p class="title"><strong>Table 3.8. Defined s_feature_compat Values</strong></p><div class="table-contents"><table summary="Defined s_feature_compat Values" width="100%" border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td colspan="3" align="left">EXT2_FEATURE_COMPAT_DIR_PREALLOC</td></tr><tr><td align="left"> </td><td align="left">0x0001</td><td align="left">Block pre-allocation for new directories</td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_COMPAT_IMAGIC_INODES</td></tr><tr><td align="left"> </td><td align="left">0x0002</td><td align="left"> </td></tr><tr><td colspan="3" align="left">EXT3_FEATURE_COMPAT_HAS_JOURNAL</td></tr><tr><td align="left"> </td><td align="left">0x0004</td><td align="left">An Ext3 journal exists</td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_COMPAT_EXT_ATTR</td></tr><tr><td align="left"> </td><td align="left">0x0008</td><td align="left">Extended inode attributes are present</td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_COMPAT_RESIZE_INO</td></tr><tr><td align="left"> </td><td align="left">0x0010</td><td align="left">Non-standard inode size used</td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_COMPAT_DIR_INDEX</td></tr><tr><td align="left"> </td><td align="left">0x0020</td><td align="left">Directory indexing (HTree)</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-feature-incompat"></a>s_feature_incompat</h3></div></div></div><p> + 32bit bitmask of incompatible features. The file system + implementation should refuse to mount the file system if any of + the indicated feature is unsupported. + </p><p> + An implementation not supporting these features would be unable to + properly use the file system. For example, if compression is being + used and an executable file would be unusable after being read from + the disk if the system does not know how to uncompress it. + </p><div class="table"><a id="s-feature-incompat-values"></a><p class="title"><strong>Table 3.9. Defined s_feature_incompat Values</strong></p><div class="table-contents"><table summary="Defined s_feature_incompat Values" width="100%" border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td colspan="3" align="left">EXT2_FEATURE_INCOMPAT_COMPRESSION</td></tr><tr><td align="left"> </td><td align="left">0x0001</td><td align="left">Disk/File compression is used</td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_INCOMPAT_FILETYPE</td></tr><tr><td align="left"> </td><td align="left">0x0002</td><td align="left"> </td></tr><tr><td colspan="3" align="left">EXT3_FEATURE_INCOMPAT_RECOVER</td></tr><tr><td align="left"> </td><td align="left">0x0004</td><td align="left"> </td></tr><tr><td colspan="3" align="left">EXT3_FEATURE_INCOMPAT_JOURNAL_DEV</td></tr><tr><td align="left"> </td><td align="left">0x0008</td><td align="left"> </td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_INCOMPAT_META_BG</td></tr><tr><td align="left"> </td><td align="left">0x0010</td><td align="left"> </td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-feature-ro-compat"></a>s_feature_ro_compat</h3></div></div></div><p> + 32bit bitmask of <span class="quote">“<span class="quote">read-only</span>”</span> features. The file system + implementation should mount as read-only if any of the indicated + feature is unsupported. + </p><div class="table"><a id="s-feature-ro-compat-values"></a><p class="title"><strong>Table 3.10. Defined s_feature_ro_compat Values</strong></p><div class="table-contents"><table summary="Defined s_feature_ro_compat Values" width="100%" border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td colspan="3" align="left">EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER</td></tr><tr><td align="left"> </td><td align="left">0x0001</td><td align="left">Sparse Superblock</td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_RO_COMPAT_LARGE_FILE</td></tr><tr><td align="left"> </td><td align="left">0x0002</td><td align="left">Large file support, 64-bit file size</td></tr><tr><td colspan="3" align="left">EXT2_FEATURE_RO_COMPAT_BTREE_DIR</td></tr><tr><td align="left"> </td><td align="left">0x0004</td><td align="left">Binary tree sorted directory files</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-uuid"></a>s_uuid</h3></div></div></div><p> + 128bit value used as the volume id. This should, as much as possible, + be unique for each file system formatted. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-volume-name"></a>s_volume_name</h3></div></div></div><p> + 16 bytes volume name, mostly unusued. A valid volume name would consist + of only ISO-Latin-1 characters and be 0 terminated. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-last-mounted"></a>s_last_mounted</h3></div></div></div><p> + 64 bytes directory path where the file system was last mounted. While + not normally used, it could serve for auto-finding the mountpoint when + not indicated on the command line. Again the path should be zero + terminated for compatibility reasons. Valid path is constructed from + ISO-Latin-1 characters. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-algo-bitmap"></a>s_algo_bitmap</h3></div></div></div><p> + 32bit value used by compression algorithms to determine the compression + method(s) used. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + Compression is supported in Linux 2.4 and 2.6 via the e2compr patch. For + more information, visit http://e2compr.sourceforge.net/ + </p></div><div class="table"><a id="s-algo-bitmap-values"></a><p class="title"><strong>Table 3.11. Defined s_algo_bitmap Values</strong></p><div class="table-contents"><table summary="Defined s_algo_bitmap Values" width="100%" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Bit Number</th><th align="left">Description</th></tr></thead><tbody><tr><td align="left">EXT2_LZV1_ALG</td><td align="left">0</td><td align="left">Binary value of 0x00000001</td></tr><tr><td align="left">EXT2_LZRW3A_ALG</td><td align="left">1</td><td align="left">Binary value of 0x00000002</td></tr><tr><td align="left">EXT2_GZIP_ALG</td><td align="left">2</td><td align="left">Binary value of 0x00000004</td></tr><tr><td align="left">EXT2_BZIP2_ALG</td><td align="left">3</td><td align="left">Binary value of 0x00000008</td></tr><tr><td align="left">EXT2_LZO_ALG</td><td align="left">4</td><td align="left">Binary value of 0x00000010</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-prealloc-blocks"></a>s_prealloc_blocks</h3></div></div></div><p> + 8-bit value representing the number of blocks the implementation should + attempt to pre-allocate when creating a new regular file. + </p><p> + Linux 2.6.28 will only perform pre-allocation using Ext4 although no + problem is expected if any version of Linux encounters a file with more + blocks present than required. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-prealloc-dir-blocks"></a>s_prealloc_dir_blocks</h3></div></div></div><p> + 8-bit value representing the number of blocks the implementation should + attempt to pre-allocate when creating a new directory. + </p><p> + Linux 2.6.28 will only perform pre-allocation using Ext4 and only if + the <code class="constant">EXT4_FEATURE_COMPAT_DIR_PREALLOC</code> flag is present. Since + Linux does not de-allocate blocks from directories after they were + allocated, it should be safe to perform pre-allocation and maintain + compatibility with Linux. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-journal-uuid"></a>s_journal_uuid</h3></div></div></div><p> + 16-byte value containing the uuid of the journal superblock. See Ext3 + Journaling for more information. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-journal-inum"></a>s_journal_inum</h3></div></div></div><p> + 32-bit inode number of the journal file. See Ext3 Journaling for more + information. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-journal-dev"></a>s_journal_dev</h3></div></div></div><p> + 32-bit device number of the journal file. See Ext3 Journaling for more + information. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-last-orphan"></a>s_last_orphan</h3></div></div></div><p> + 32-bit inode number, pointing to the first inode in the list of inodes + to delete. See Ext3 Journaling for more information. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-hash-seed"></a>s_hash_seed</h3></div></div></div><p> + An array of 4 32bit values containing the seeds used for the hash + algorithm for directory indexing. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-def-hash-version"></a>s_def_hash_version</h3></div></div></div><p> + An 8bit value containing the default hash version used for directory indexing. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-default-mount-options"></a>s_default_mount_options</h3></div></div></div><p> + A 32bit value containing the default mount options for this file system. TODO: Add more information here! + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="s-first-meta-bg"></a>s_first_meta_bg</h3></div></div></div><p> + A 32bit value indicating the block group ID of the first meta block group. TODO: Research if this is an Ext3-only extension. + </p></div></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="block-group-descriptor-table"></a>Block Group Descriptor Table</h2></div></div></div><p> + The block group descriptor table is an array of + <a class="link" href="#block-group-descriptor-structure" title="Table 3.12. Block Group Descriptor Structure">block group descriptor</a>, + used to define parameters of all the + <a class="link" href="#def-block-groups" title="Block Groups">block groups</a>. It provides the location + of the inode bitmap and inode table, block bitmap, number of free blocks and + inodes, and some other useful information. + </p><p> + The block group descriptor table starts on the first block following the + superblock. This would be the third block on a 1KiB block file system, or the + second block for 2KiB and larger block file systems. Shadow copies of the + block group descriptor table are also stored with every copy of the + superblock. + </p><p> + Depending on how many block groups are defined, this table can require + multiple blocks of storage. Always refer to the superblock in case of + doubt. + </p><p> + The layout of a block group descriptor is as follows: + </p><div class="table"><a id="block-group-descriptor-structure"></a><p class="title"><strong>Table 3.12. Block Group Descriptor Structure</strong></p><div class="table-contents"><table summary="Block Group Descriptor Structure" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>4</td><td><a class="link" href="#bg-block-bitmap" title="bg_block_bitmap">bg_block_bitmap</a></td></tr><tr><td>4</td><td>4</td><td><a class="link" href="#bg-inode-bitmap" title="bg_inode_bitmap">bg_inode_bitmap</a></td></tr><tr><td>8</td><td>4</td><td><a class="link" href="#bg-inode-table" title="bg_inode_table">bg_inode_table</a></td></tr><tr><td>12</td><td>2</td><td><a class="link" href="#bg-free-blocks-count" title="bg_free_blocks_count">bg_free_blocks_count</a></td></tr><tr><td>14</td><td>2</td><td><a class="link" href="#bg-free-inodes-count" title="bg_free_inodes_count">bg_free_inodes_count</a></td></tr><tr><td>16</td><td>2</td><td><a class="link" href="#bg-used-dirs-count" title="bg_used_dirs_count">bg_used_dirs_count</a></td></tr><tr><td>18</td><td>2</td><td><a class="link" href="#bg-pad" title="bg_pad">bg_pad</a></td></tr><tr><td>20</td><td>12</td><td><a class="link" href="#bg-reserved" title="bg_reserved">bg_reserved</a></td></tr></tbody></table></div></div><br class="table-break" /><p> + For each block group in the file system, such a <span class="structname">group_desc</span> is + created. Each represent a single block group within the + file system and the information within any one of them is pertinent + only to the group it is describing. Every block group descriptor table + contains all the information about all the block groups. + </p><p> + NOTE: All indicated <span class="quote">“<span class="quote">block id</span>”</span> are absolute. + </p><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-block-bitmap"></a>bg_block_bitmap</h3></div></div></div><p> + 32bit block id of the first block of the + <span class="quote">“<span class="quote"><a class="link" href="#block-bitmap" title="Block Bitmap">block bitmap</a></span>”</span> + for the group represented. + </p><p> + The actual block bitmap is located within its own allocated blocks + starting at the block ID specified by this value. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-inode-bitmap"></a>bg_inode_bitmap</h3></div></div></div><p> + 32bit block id of the first block of the + <span class="quote">“<span class="quote"><a class="link" href="#inode-bitmap" title="Inode Bitmap">inode bitmap</a></span>”</span> + for the group represented. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-inode-table"></a>bg_inode_table</h3></div></div></div><p> + 32bit block id of the first block of the + <span class="quote">“<span class="quote"><a class="link" href="#inode-table" title="Inode Table">inode table</a></span>”</span> + for the group represented. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-free-blocks-count"></a>bg_free_blocks_count</h3></div></div></div><p> + 16bit value indicating the total number of free blocks for + the represented group. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-free-inodes-count"></a>bg_free_inodes_count</h3></div></div></div><p> + 16bit value indicating the total number of free inodes for + the represented group. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-used-dirs-count"></a>bg_used_dirs_count</h3></div></div></div><p> + 16bit value indicating the number of inodes allocated to + directories for the represented group. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-pad"></a>bg_pad</h3></div></div></div><p> + 16bit value used for padding the structure on a 32bit boundary. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="bg-reserved"></a>bg_reserved</h3></div></div></div><p> + 12 bytes of reserved space for future revisions. + </p></div></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="block-bitmap"></a>Block Bitmap</h2></div></div></div><p> + On small file systems, the <span class="quote">“<span class="quote">Block Bitmap</span>”</span> is normally located + at the first block, or second block if a superblock backup is present, + of each block group. Its official location can be determined by reading the + <span class="quote">“<span class="quote"><a class="link" href="#bg-block-bitmap" title="bg_block_bitmap">bg_block_bitmap</a></span>”</span> + in its associated <a class="link" href="#block-group-descriptor-table" title="Block Group Descriptor Table">group descriptor</a>. + </p><p> + Each bit represent the current state of a block within that block group, + where 1 means <span class="quote">“<span class="quote">used</span>”</span> and 0 <span class="quote">“<span class="quote">free/available</span>”</span>. The + first block of this block group is represented by bit 0 of byte 0, + the second by bit 1 of byte 0. The 8th block is represented by bit 7 + (most significant bit) of byte 0 while the 9th block is represented by + bit 0 (least significant bit) of byte 1. + </p></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="inode-bitmap"></a>Inode Bitmap</h2></div></div></div><p> + The <span class="quote">“<span class="quote">Inode Bitmap</span>”</span> works in a similar way as the + <span class="quote">“<span class="quote"><a class="link" href="#block-bitmap" title="Block Bitmap">Block Bitmap</a></span>”</span>, + difference being in each bit representing an inode in the + <span class="quote">“<span class="quote"><a class="link" href="#inode-table" title="Inode Table">Inode Table</a></span>”</span> rather + than a block. Since inode numbers start from 1 rather than 0, the + first bit in the first block group's inode bitmap represent inode + number 1. + </p><p> + There is one inode bitmap per group and its location may be + determined by reading the + <span class="quote">“<span class="quote"><a class="link" href="#bg-inode-bitmap" title="bg_inode_bitmap">bg_inode_bitmap</a></span>”</span> + in its associated <a class="link" href="#block-group-descriptor-table" title="Block Group Descriptor Table">group descriptor</a>. + </p><p> + When the inode table is created, all the reserved inodes are marked + as used. In revision 0 this is the first 11 inodes. + </p></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="inode-table"></a>Inode Table</h2></div></div></div><p> + The inode table is used to keep track of every directory, + regular file, symbolic link, or special file; their + location, size, type and access rights are all stored in inodes. There + is no filename stored in the inode itself, names are contained in + <a class="link" href="#directory" title="Chapter 4. Directory Structure">directory</a> files only. + </p><p> + There is one inode table per block group and it can be located by reading the + <a class="link" href="#bg-inode-table" title="bg_inode_table">bg_inode_table</a> + in its associated <a class="link" href="#block-group-descriptor-table" title="Block Group Descriptor Table">group descriptor</a>. + There are <a class="link" href="#s-inodes-per-group" title="s_inodes_per_group">s_inodes_per_group</a> + inodes per table. + </p><p> + Each inode contain the information about a single physical file on the + system. A file can be a directory, a socket, a buffer, character or + block device, symbolic link or a regular file. So an inode can be + seen as a block of information related to an entity, describing its + location on disk, its size and its owner. An inode looks like this: + </p><div class="table"><a id="inode-structure"></a><p class="title"><strong>Table 3.13. Inode Structure</strong></p><div class="table-contents"><table summary="Inode Structure" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>2</td><td><a class="link" href="#i-mode" title="i_mode">i_mode</a></td></tr><tr><td>2</td><td>2</td><td><a class="link" href="#i-uid" title="i_uid">i_uid</a></td></tr><tr><td>4</td><td>4</td><td><a class="link" href="#i-size" title="i_size">i_size</a></td></tr><tr><td>8</td><td>4</td><td><a class="link" href="#i-atime" title="i_atime">i_atime</a></td></tr><tr><td>12</td><td>4</td><td><a class="link" href="#i-ctime" title="i_ctime">i_ctime</a></td></tr><tr><td>16</td><td>4</td><td><a class="link" href="#i-mtime" title="i_mtime">i_mtime</a></td></tr><tr><td>20</td><td>4</td><td><a class="link" href="#i-dtime" title="i_dtime">i_dtime</a></td></tr><tr><td>24</td><td>2</td><td><a class="link" href="#i-gid" title="i_gid">i_gid</a></td></tr><tr><td>26</td><td>2</td><td><a class="link" href="#i-links-count" title="i_links_count">i_links_count</a></td></tr><tr><td>28</td><td>4</td><td><a class="link" href="#i-blocks" title="i_blocks">i_blocks</a></td></tr><tr><td>32</td><td>4</td><td><a class="link" href="#i-flags" title="i_flags">i_flags</a></td></tr><tr><td>36</td><td>4</td><td><a class="link" href="#i-osd1" title="i_osd1">i_osd1</a></td></tr><tr><td>40</td><td>15 x 4</td><td><a class="link" href="#i-block" title="i_block">i_block</a></td></tr><tr><td>100</td><td>4</td><td><a class="link" href="#i-generation" title="i_generation">i_generation</a></td></tr><tr><td>104</td><td>4</td><td><a class="link" href="#i-file-acl" title="i_file_acl">i_file_acl</a></td></tr><tr><td>108</td><td>4</td><td><a class="link" href="#i-dir-acl" title="i_dir_acl">i_dir_acl</a></td></tr><tr><td>112</td><td>4</td><td><a class="link" href="#i-faddr" title="i_faddr">i_faddr</a></td></tr><tr><td>116</td><td>12</td><td><a class="link" href="#i-osd2" title="Inode i_osd2 Structure">i_osd2</a></td></tr></tbody></table></div></div><br class="table-break" /><p> + The first few entries of the inode tables are reserved. In revision + 0 there are 11 entries reserved while in revision 1 + (EXT2_DYNAMIC_REV) and later the number of reserved inodes entries is + specified in the <a class="link" href="#s-first-ino" title="s_first_ino">s_first_ino</a> of the + superblock structure. Here's a listing of the known reserved inode + entries: + </p><div class="table"><a id="reserved-inodes-values"></a><p class="title"><strong>Table 3.14. Defined Reserved Inodes</strong></p><div class="table-contents"><table summary="Defined Reserved Inodes" width="100%" border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td align="left">EXT2_BAD_INO</td><td align="left">1</td><td align="left">bad blocks inode</td></tr><tr><td align="left">EXT2_ROOT_INO</td><td align="left">2</td><td align="left">root directory inode</td></tr><tr><td align="left">EXT2_ACL_IDX_INO</td><td align="left">3</td><td align="left">ACL index inode (deprecated?)</td></tr><tr><td align="left">EXT2_ACL_DATA_INO</td><td align="left">4</td><td align="left">ACL data inode (deprecated?)</td></tr><tr><td align="left">EXT2_BOOT_LOADER_INO</td><td align="left">5</td><td align="left">boot loader inode</td></tr><tr><td align="left">EXT2_UNDEL_DIR_INO</td><td align="left">6</td><td align="left">undelete directory inode</td></tr></tbody></table></div></div><br class="table-break" /><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-mode"></a>i_mode</h3></div></div></div><p> + 16bit value used to indicate the format of the described file and the + access rights. Here are the possible values, which can be combined + in various ways: + </p><div class="table"><a id="idm140660447480672"></a><p class="title"><strong>Table 3.15. Defined i_mode Values</strong></p><div class="table-contents"><table summary="Defined i_mode Values" width="100%" border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left">Constant</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td colspan="3" align="left">-- file format --</td></tr><tr><td align="left">EXT2_S_IFSOCK</td><td align="left">0xC000</td><td align="left">socket</td></tr><tr><td align="left">EXT2_S_IFLNK</td><td align="left">0xA000</td><td align="left">symbolic link</td></tr><tr><td align="left">EXT2_S_IFREG</td><td align="left">0x8000</td><td align="left">regular file</td></tr><tr><td align="left">EXT2_S_IFBLK</td><td align="left">0x6000</td><td align="left">block device</td></tr><tr><td align="left">EXT2_S_IFDIR</td><td align="left">0x4000</td><td align="left">directory</td></tr><tr><td align="left">EXT2_S_IFCHR</td><td align="left">0x2000</td><td align="left">character device</td></tr><tr><td align="left">EXT2_S_IFIFO</td><td align="left">0x1000</td><td align="left">fifo</td></tr><tr><td colspan="3" align="left">-- process execution user/group override --</td></tr><tr><td align="left">EXT2_S_ISUID</td><td align="left">0x0800</td><td align="left">Set process User ID</td></tr><tr><td align="left">EXT2_S_ISGID</td><td align="left">0x0400</td><td align="left">Set process Group ID</td></tr><tr><td align="left">EXT2_S_ISVTX</td><td align="left">0x0200</td><td align="left">sticky bit</td></tr><tr><td colspan="3" align="left">-- access rights --</td></tr><tr><td align="left">EXT2_S_IRUSR</td><td align="left">0x0100</td><td align="left">user read</td></tr><tr><td align="left">EXT2_S_IWUSR</td><td align="left">0x0080</td><td align="left">user write</td></tr><tr><td align="left">EXT2_S_IXUSR</td><td align="left">0x0040</td><td align="left">user execute</td></tr><tr><td align="left">EXT2_S_IRGRP</td><td align="left">0x0020</td><td align="left">group read</td></tr><tr><td align="left">EXT2_S_IWGRP</td><td align="left">0x0010</td><td align="left">group write</td></tr><tr><td align="left">EXT2_S_IXGRP</td><td align="left">0x0008</td><td align="left">group execute</td></tr><tr><td align="left">EXT2_S_IROTH</td><td align="left">0x0004</td><td align="left">others read</td></tr><tr><td align="left">EXT2_S_IWOTH</td><td align="left">0x0002</td><td align="left">others write</td></tr><tr><td align="left">EXT2_S_IXOTH</td><td align="left">0x0001</td><td align="left">others execute</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-uid"></a>i_uid</h3></div></div></div><p> + 16bit user id associated with the file. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-size"></a>i_size</h3></div></div></div><p> + In revision 0, (signed) 32bit value indicating the size of the file in + bytes. In revision 1 and later revisions, and only for regular files, this + represents the lower 32-bit of the file size; the upper 32-bit is located + in the i_dir_acl. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-atime"></a>i_atime</h3></div></div></div><p> + 32bit value representing the number of seconds since january 1st 1970 + of the last time this inode was accessed. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-ctime"></a>i_ctime</h3></div></div></div><p> + 32bit value representing the number of seconds since january 1st 1970, of + when the inode was created. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-mtime"></a>i_mtime</h3></div></div></div><p> + 32bit value representing the number of seconds since january 1st 1970, + of the last time this inode was modified. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-dtime"></a>i_dtime</h3></div></div></div><p> + 32bit value representing the number of seconds since january 1st 1970, of + when the inode was deleted. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-gid"></a>i_gid</h3></div></div></div><p> + 16bit value of the POSIX group having access to this file. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-links-count"></a>i_links_count</h3></div></div></div><p> + 16bit value indicating how many times this particular inode is linked + (referred to). Most files will have a link count of 1. Files with hard + links pointing to them will have an additional count for each hard link. + </p><p> + Symbolic links do not affect the link count of an inode. When the link count + reaches 0 the inode and all its associated blocks are freed. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-blocks"></a>i_blocks</h3></div></div></div><p> + 32-bit value representing the total number of 512-bytes blocks reserved to contain the + data of this inode, regardless if these blocks are used or not. The block + numbers of these reserved blocks are contained in the + <a class="link" href="#i-block" title="i_block">i_block</a> array. + </p><p> + Since this value represents 512-byte blocks and not file system blocks, + this value should not be directly used as an index to the i_block array. + Rather, the maximum index of the i_block array should be computed from + i_blocks / ((1024<<s_log_block_size)/512), or once simplified, i_blocks/(2<<s_log_block_size). + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-flags"></a>i_flags</h3></div></div></div><p> + 32bit value indicating how the ext2 implementation should behave when + accessing the data for this inode. + </p><div class="table"><a id="defined-i-flags-values"></a><p class="title"><strong>Table 3.16. Defined i_flags Values</strong></p><div class="table-contents"><table summary="Defined i_flags Values" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Constant Name</th><th>Value</th><th>Description</th></tr></thead><tbody><tr><td><a class="link" href="#ext2-secrm-fl" title="EXT2_SECRM_FL - Secure Deletion">EXT2_SECRM_FL</a></td><td>0x00000001</td><td>secure deletion</td></tr><tr><td><a class="link" href="#ext2-unrm-fl" title="EXT2_UNRM_FL - Record for Undelete">EXT2_UNRM_FL</a></td><td>0x00000002</td><td>record for undelete</td></tr><tr><td><a class="link" href="#ext2-compr-fl" title="EXT2_COMPR_FL - Compressed File">EXT2_COMPR_FL</a></td><td>0x00000004</td><td>compressed file</td></tr><tr><td><a class="link" href="#ext2-sync-fl" title="EXT2_SYNC_FL - Synchronous Updates">EXT2_SYNC_FL</a></td><td>0x00000008</td><td>synchronous updates</td></tr><tr><td><a class="link" href="#ext2-immutable-fl" title="EXT2_IMMUTABLE_FL - Immutable File">EXT2_IMMUTABLE_FL</a></td><td>0x00000010</td><td>immutable file</td></tr><tr><td><a class="link" href="#ext2-append-fl" title="EXT2_APPEND_FL - Append Only">EXT2_APPEND_FL</a></td><td>0x00000020</td><td>append only</td></tr><tr><td><a class="link" href="#ext2-nodump-fl" title="EXT2_NODUMP_FL - Do No Dump/Delete">EXT2_NODUMP_FL</a></td><td>0x00000040</td><td>do not dump/delete file</td></tr><tr><td><a class="link" href="#ext2-noatime-fl" title="EXT2_NOATIME_FL - Do Not Update .i_atime">EXT2_NOATIME_FL</a></td><td>0x00000080</td><td>do not update .i_atime</td></tr><tr><td colspan="3" align="left">-- Reserved for compression usage --</td></tr><tr><td><a class="link" href="#ext2-dirty-fl" title="EXT2_DIRTY_FL - Dirty">EXT2_DIRTY_FL</a></td><td>0x00000100</td><td>Dirty (modified)</td></tr><tr><td><a class="link" href="#ext2-comprblk-fl" title="EXT2_COMPRBLK_FL - Compressed Blocks">EXT2_COMPRBLK_FL</a></td><td>0x00000200</td><td>compressed blocks</td></tr><tr><td><a class="link" href="#ext2-nocompr-fl" title="EXT2_NOCOMPR_FL - Access Raw Compressed Data">EXT2_NOCOMPR_FL</a></td><td>0x00000400</td><td>access raw compressed data</td></tr><tr><td><a class="link" href="#ext2-ecompr-fl" title="EXT2_ECOMPR_FL - Compression Error">EXT2_ECOMPR_FL</a></td><td>0x00000800</td><td>compression error</td></tr><tr><td colspan="3" align="left">-- End of compression flags --</td></tr><tr><td><a class="link" href="#ext2-btree-fl" title="EXT2_BTREE_FL - B-Tree Format Directory">EXT2_BTREE_FL</a></td><td>0x00001000</td><td>b-tree format directory</td></tr><tr><td><a class="link" href="#ext2-index-fl" title="EXT2_INDEX_FL - Hash Indexed Directory">EXT2_INDEX_FL</a></td><td>0x00001000</td><td>hash indexed directory</td></tr><tr><td><a class="link" href="#ext2-imagic-fl" title="EXT2_IMAGIC_FL -">EXT2_IMAGIC_FL</a></td><td>0x00002000</td><td>AFS directory</td></tr><tr><td><a class="link" href="#ext3-journal-data-fl" title="EXT2_JOURNAL_DATA_FL - Journal File Data">EXT3_JOURNAL_DATA_FL</a></td><td>0x00004000</td><td>journal file data</td></tr><tr><td><a class="link" href="#ext2-reserved-fl" title="EXT2_RESERVED_FL - Reserved">EXT2_RESERVED_FL</a></td><td>0x80000000</td><td>reserved for ext2 library</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-osd1"></a>i_osd1</h3></div></div></div><p> + 32bit OS dependant value. + </p><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="i-osd1-hurd"></a>Hurd</h4></div></div></div><p> + 32bit value labeled as <span class="quote">“<span class="quote">translator</span>”</span>. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="i-osd1-linux"></a>Linux</h4></div></div></div><p> + 32bit value currently reserved. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="i-osd1-masix"></a>Masix</h4></div></div></div><p> + 32bit value currently reserved. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-block"></a>i_block</h3></div></div></div><p> + 15 x 32bit block numbers pointing to the blocks containing the data for + this inode. The first 12 blocks are direct blocks. The 13th entry in this + array is the block number of the first indirect block; which is a block + containing an array of block ID containing the data. Therefore, the 13th + block of the file will be the first block ID contained in the indirect block. + With a 1KiB block size, blocks 13 to 268 of the file data are contained + in this indirect block. + </p><p> + The 14th entry in this array is the block number of the first doubly-indirect + block; which is a block containing an array of indirect block IDs, with each + of those indirect blocks containing an array of blocks containing the data. + In a 1KiB block size, there would be 256 indirect blocks per doubly-indirect + block, with 256 direct blocks per indirect block for a total of 65536 blocks + per doubly-indirect block. + </p><p> + The 15th entry in this array is the block number of the triply-indirect + block; which is a block containing an array of doubly-indrect block IDs, + with each of those doubly-indrect block containing an array of indrect block, + and each of those indirect block containing an array of direct block. In a + 1KiB file system, this would be a total of 16777216 blocks per + triply-indirect block. + </p><p> + In the original implementation of Ext2, a value of 0 in this array effectively + terminated it with no further block defined. In sparse files, it is possible + to have some blocks allocated and some others not yet allocated with the value 0 + being used to indicate which blocks are not yet allocated for this file. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-generation"></a>i_generation</h3></div></div></div><p> + 32bit value used to indicate the file version (used by NFS). + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-file-acl"></a>i_file_acl</h3></div></div></div><p> + 32bit value indicating the block number containing the extended + attributes. In revision 0 this value is always 0. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + Patches and implementation status of ACL under Linux can generally be found at http://acl.bestbits.at/ + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-dir-acl"></a>i_dir_acl</h3></div></div></div><p> + In revision 0 this 32bit value is always 0. In revision 1, for regular + files this 32bit value contains the high 32 bits of the 64bit file size. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + Linux sets this value to 0 if the file is not a regular file (i.e. block + devices, directories, etc). In theory, this value could be set to point + to a block containing extended attributes of the directory or special file. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-faddr"></a>i_faddr</h3></div></div></div><p> + 32bit value indicating the location of the file fragment. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + In Linux and GNU HURD, since fragments are unsupported this value is always + 0. In Ext4 this value is now marked as obsolete. + </p><p> + In theory, this should contain the block number which hosts the + actual fragment. The fragment number and its size would be contained + in the <a class="link" href="#i-osd2" title="Inode i_osd2 Structure">i_osd2</a> structure. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="i-osd2"></a>Inode i_osd2 Structure</h3></div></div></div><p> + 96bit OS dependant structure. + </p><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="i-osd2-hurd"></a>Hurd</h4></div></div></div><div class="table"><a id="i-osd2-hurd-structure"></a><p class="title"><strong>Table 3.17. Inode i_osd2 Structure: Hurd</strong></p><div class="table-contents"><table summary="Inode i_osd2 Structure: Hurd" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>1</td><td><a class="link" href="#h-i-frag" title="h_i_frag">h_i_frag</a></td></tr><tr><td>1</td><td>1</td><td><a class="link" href="#h-i-fsize" title="h_i_fsize">h_i_fsize</a></td></tr><tr><td>2</td><td>2</td><td><a class="link" href="#h-i-mode-high" title="h_i_mode_high">h_i_mode_high</a></td></tr><tr><td>4</td><td>2</td><td><a class="link" href="#h-i-uid-high" title="h_i_uid_high">h_i_uid_high</a></td></tr><tr><td>6</td><td>2</td><td><a class="link" href="#h-i-gid-high" title="h_i_gid_high">h_i_gid_high</a></td></tr><tr><td>8</td><td>4</td><td><a class="link" href="#h-i-author" title="h_i_author">h_i_author</a></td></tr></tbody></table></div></div><br class="table-break" /><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="h-i-frag"></a>h_i_frag</h5></div></div></div><p> + 8bit fragment number. Always 0 GNU HURD since fragments are + not supported. Obsolete with Ext4. + </p></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="h-i-fsize"></a>h_i_fsize</h5></div></div></div><p> + 8bit fragment size. Always 0 in GNU HURD since fragments are + not supported. Obsolete with Ext4. + </p></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="h-i-mode-high"></a>h_i_mode_high</h5></div></div></div><p> + High 16bit of the 32bit mode. + </p></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="h-i-uid-high"></a>h_i_uid_high</h5></div></div></div><p> + High 16bit of <a class="link" href="#i-uid" title="i_uid">user id</a>. + </p></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="h-i-gid-high"></a>h_i_gid_high</h5></div></div></div><p> + High 16bit of <a class="link" href="#i-gid" title="i_gid">group id</a>. + </p></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="h-i-author"></a>h_i_author</h5></div></div></div><p> + 32bit user id of the assigned file author. If this value is set to -1, the + POSIX <a class="link" href="#i-uid" title="i_uid">user id</a> will be used. + </p></div></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="i-osd2-linux"></a>Linux</h4></div></div></div><div class="table"><a id="i-osd2-linux-structure"></a><p class="title"><strong>Table 3.18. Inode i_osd2 Structure: Linux</strong></p><div class="table-contents"><table summary="Inode i_osd2 Structure: Linux" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>1</td><td><a class="link" href="#l-i-frag" title="l_i_frag">l_i_frag</a></td></tr><tr><td>1</td><td>1</td><td><a class="link" href="#l-i-fsize" title="l_i_fsize">l_i_fsize</a></td></tr><tr><td>2</td><td>2</td><td>reserved</td></tr><tr><td>4</td><td>2</td><td><a class="link" href="#l-i-uid-high" title="l_i_uid_high">l_i_uid_high</a></td></tr><tr><td>6</td><td>2</td><td><a class="link" href="#l-i-gid-high" title="l_i_gid_high">l_i_gid_high</a></td></tr><tr><td>8</td><td>4</td><td>reserved</td></tr></tbody></table></div></div><br class="table-break" /><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="l-i-frag"></a>l_i_frag</h5></div></div></div><p> + 8bit fragment number. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + Always 0 in Linux since fragments are not supported. + </p></div><div class="important" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Important</h3><p> + A new implementation of Ext2 should completely disregard this field + if the <a class="link" href="#i-faddr" title="i_faddr">i_faddr</a> value is 0; in Ext4 this + field is combined with <a class="link" href="#l-i-fsize" title="l_i_fsize">l_i_fsize</a> to + become the high 16bit of the 48bit blocks count for the inode data. + </p></div></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="l-i-fsize"></a>l_i_fsize</h5></div></div></div><p> + 8bit fragment size. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + Always 0 in Linux since fragments are not supported. + </p></div><div class="important" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Important</h3><p> + A new implementation of Ext2 should completely disregard this field + if the <a class="link" href="#i-faddr" title="i_faddr">i_faddr</a> value is 0; in Ext4 this + field is combined with <a class="link" href="#l-i-frag" title="l_i_frag">l_i_frag</a> to + become the high 16bit of the 48bit blocks count for the inode data. + </p></div></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="l-i-uid-high"></a>l_i_uid_high</h5></div></div></div><p> + High 16bit of <a class="link" href="#i-uid" title="i_uid">user id</a>. + </p></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="l-i-gid-high"></a>l_i_gid_high</h5></div></div></div><p> + High 16bit of <a class="link" href="#i-gid" title="i_gid">group id</a>. + </p></div></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="i-osd2-masix"></a>Masix</h4></div></div></div><div class="table"><a id="i-osd2-masix-structure"></a><p class="title"><strong>Table 3.19. Inode i_osd2 Structure: Masix</strong></p><div class="table-contents"><table summary="Inode i_osd2 Structure: Masix" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>1</td><td><a class="link" href="#m-i-frag" title="m_i_frag">m_i_frag</a></td></tr><tr><td>1</td><td>1</td><td><a class="link" href="#m-i-fsize" title="m_i_fsize">m_i_fsize</a></td></tr><tr><td>2</td><td>10</td><td>reserved</td></tr></tbody></table></div></div><br class="table-break" /><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="m-i-frag"></a>m_i_frag</h5></div></div></div><p> + 8bit fragment number. Always 0 in Masix as framgents are not + supported. Obsolete with Ext4. + </p></div><div class="sect4"><div class="titlepage"><div><div><h5 class="title"><a id="m-i-fsize"></a>m_i_fsize</h5></div></div></div><p> + 8bit fragment size. Always 0 in Masix as fragments are not + supported. Obsolete with Ext4. + </p></div></div></div></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="idm140660447281728"></a>Locating an Inode</h2></div></div></div><p> + Inodes are all numerically ordered. The <span class="quote">“<span class="quote">inode number</span>”</span> is + an index in the <a class="link" href="#inode-table" title="Inode Table">inode table</a> to an + <a class="link" href="#inode-structure" title="Table 3.13. Inode Structure">inode</a> structure. The size of the + inode table is fixed at format time; it is built to hold a maximum + number of entries. Due to the large amount of entries + created, the table is quite big and thus, it is split equally among + all the <a class="link" href="#block-group-descriptor-table" title="Block Group Descriptor Table">block groups</a> + (see <a class="xref" href="#disk-organisation" title="Chapter 3. Disk Organization">Chapter 3, <em>Disk Organization</em></a> for more information). + </p><p> + The <a class="link" href="#s-inodes-per-group" title="s_inodes_per_group">s_inodes_per_group</a> field in + the <a class="link" href="#superblock" title="Superblock">superblock</a> structure tells us how many + inodes are defined per group. Knowing that inode 1 is the first inode + defined in the inode table, one can use the following formulaes: + </p><pre class="programlisting"> +block group = (inode - 1) / s_inodes_per_group + </pre><p> + Once the block is identified, the local inode index for the local inode + table can be identified using: + </p><pre class="programlisting"> +local inode index = (inode - 1) % s_inodes_per_group + </pre><p> + Here are a couple of sample values that could be used to test + your implementation: + </p><div class="table"><a id="inode-computation-sample"></a><p class="title"><strong>Table 3.20. Sample Inode Computations</strong></p><div class="table-contents"><table summary="Sample Inode Computations" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Inode Number</th><th>Block Group Number</th><th>Local Inode Index</th></tr></thead><tbody><tr><td colspan="3">s_inodes_per_group = 1712</td></tr><tr><td>1</td><td>0</td><td>0</td></tr><tr><td>963</td><td>0</td><td>962</td></tr><tr><td>1712</td><td>0</td><td>1711</td></tr><tr><td>1713</td><td>1</td><td>0</td></tr><tr><td>3424</td><td>1</td><td>1711</td></tr><tr><td>3425</td><td>2</td><td>0</td></tr></tbody></table></div></div><br class="table-break" /><p> + As many of you are most likely already familiar with, an index of 0 + means the first entry. The reason behind using 0 rather than 1 is that + it can more easily be multiplied by the structure size to find the + final byte offset of its location in memory or on disk. + </p></div></div><div class="chapter"><div class="titlepage"><div><div><h1 class="title"><a id="directory"></a>Chapter 4. Directory Structure</h1></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="sect1"><a href="#linked-directories">Linked List Directory</a></span></dt><dd><dl><dt><span class="sect2"><a href="#ifdir-inode">inode</a></span></dt><dt><span class="sect2"><a href="#ifdir-rec-len">rec_len</a></span></dt><dt><span class="sect2"><a href="#ifdir-name-len">name_len</a></span></dt><dt><span class="sect2"><a href="#ifdir-file-type">file_type</a></span></dt><dt><span class="sect2"><a href="#ifdir-name">name</a></span></dt><dt><span class="sect2"><a href="#dir-sample">Sample Directory</a></span></dt></dl></dd><dt><span class="sect1"><a href="#indexed-directory">Indexed Directory Format</a></span></dt><dd><dl><dt><span class="sect2"><a href="#dx-root">Indexed Directory Root</a></span></dt><dt><span class="sect2"><a href="#dx-entry">Indexed Directory Entry</a></span></dt><dt><span class="sect2"><a href="#contrib-lookup-algorithm">Lookup Algorithm</a></span></dt><dt><span class="sect2"><a href="#contrib-insert-algorithm">Insert Algorithm</a></span></dt><dt><span class="sect2"><a href="#contrib-splitting">Splitting</a></span></dt><dt><span class="sect2"><a href="#contrib-key-collisions">Key Collisions</a></span></dt><dt><span class="sect2"><a href="#contrib-hash-function">Hash Function</a></span></dt><dt><span class="sect2"><a href="#contrib-performance">Performance</a></span></dt></dl></dd></dl></div><p> + Directories are used to hierarchically organize files. Each directory + can contain other directories, regular files and special files. + </p><p> + Directories are stored as data block and referenced by an inode. They + can be identified by the file type + <code class="constant">EXT2_S_IFDIR</code> stored in the <a class="link" href="#i-mode" title="i_mode">i_mode</a> + field of the <a class="link" href="#inode-structure" title="Table 3.13. Inode Structure">inode</a> structure. + </p><p> + The second entry of the <a class="link" href="#inode-table" title="Inode Table">Inode table</a> contains + the inode pointing to the data of the root directory; as defined by the + <code class="constant">EXT2_ROOT_INO</code> constant. + </p><p> + In revision 0 directories could only be stored in a linked list. Revision 1 + and later introduced indexed directories. The indexed directory is backward + compatible with the linked list directory; this is achieved by inserting + empty directory entry records to skip over the hash indexes. + </p><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="linked-directories"></a>Linked List Directory</h2></div></div></div><p> + A directory file is a linked list of + <a class="link" href="#linked-directory-entry-structure" title="Table 4.1. Linked Directory Entry Structure">directory entry</a> + structures. Each structure contains the name of the entry, the inode + associated with the data of this entry, and the distance within the + directory file to the next entry. + </p><p> + In revision 0, the type of the entry (file, directory, special file, etc) + has to be looked up in the inode of the file. In revision 0.5 and later, + the file type is also contained in the + <a class="link" href="#linked-directory-entry-structure" title="Table 4.1. Linked Directory Entry Structure">directory entry</a> structure. + </p><div class="table"><a id="linked-directory-entry-structure"></a><p class="title"><strong>Table 4.1. Linked Directory Entry Structure</strong></p><div class="table-contents"><table summary="Linked Directory Entry Structure" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>4</td><td><a class="link" href="#ifdir-inode" title="inode">inode</a></td></tr><tr><td>4</td><td>2</td><td><a class="link" href="#ifdir-rec-len" title="rec_len">rec_len</a></td></tr><tr><td>6</td><td>1</td><td><a class="link" href="#ifdir-name-len" title="name_len">name_len</a><a href="#ftn.idm140660447232656" class="footnote" id="idm140660447232656"><sup class="footnote">[a]</sup></a></td></tr><tr><td>7</td><td>1</td><td><a class="link" href="#ifdir-file-type" title="file_type">file_type</a><a href="#ftn.idm140660447228944" class="footnote" id="idm140660447228944"><sup class="footnote">[b]</sup></a></td></tr><tr><td>8</td><td>0-255</td><td><a class="link" href="#ifdir-name" title="name">name</a></td></tr></tbody><tbody class="footnotes"><tr><td colspan="3"><div id="ftn.idm140660447232656" class="footnote"><p><a href="#idm140660447232656" class="para"><sup class="para">[a] </sup></a> + Revision 0 of Ext2 used a 16bit <em class="structfield"><code>name_len</code></em>; + since most implementations restricted filenames to a maximum of 255 + characters this value was truncated to 8bit with the upper 8bit + recycled as <a class="link" href="#ifdir-file-type" title="file_type">file_type</a>. + </p></div><div id="ftn.idm140660447228944" class="footnote"><p><a href="#idm140660447228944" class="para"><sup class="para">[b] </sup></a> + Not available in revision 0; this field was part of the 16bit + <a class="link" href="#ifdir-name-len" title="name_len">name_len</a> field. + </p></div></td></tr></tbody></table></div></div><br class="table-break" /><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ifdir-inode"></a>inode</h3></div></div></div><p> + 32bit inode number of the file entry. A value of 0 indicate that the entry + is not used. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ifdir-rec-len"></a>rec_len</h3></div></div></div><p> + 16bit unsigned displacement to the next directory entry from the start of the + current directory entry. This field must have a value at least equal to the + length of the current record. + </p><p> + The directory entries must be aligned on 4 bytes boundaries and there cannot + be any directory entry spanning multiple data blocks. If an entry cannot + completely fit in one block, it must be pushed to the next data block and the + rec_len of the previous entry properly adjusted. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + Since this value cannot be negative, when a file is removed the previous + record within the block has to be modified to point to the next valid record + within the block or to the end of the block when no other directory entry is + present. + </p><p> + If the first entry within the block is removed, a blank record + will be created and point to the next directory entry or to the end of the + block. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ifdir-name-len"></a>name_len</h3></div></div></div><p> + 8bit unsigned value indicating how many bytes of character data are contained in the name. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + This value must never be larger than rec_len - 8. If the directory entry + name is updated and cannot fit in the existing directory entry, the entry may + have to be relocated in a new directory entry of sufficient size and + possibly stored in a new data block. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ifdir-file-type"></a>file_type</h3></div></div></div><p> + 8bit unsigned value used to indicate file type. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + In revision 0, this field was the upper 8-bit of the then 16-bit name_len. + Since all implementations still limited the file names to 255 characters this + 8-bit value was always 0. + </p><p> + This value must match the inode type defined in the related inode entry. + </p></div><div class="table"><a id="ifdir-file-type-values"></a><p class="title"><strong>Table 4.2. Defined Inode File Type Values</strong></p><div class="table-contents"><table summary="Defined Inode File Type Values" width="100%" border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left">Constant Name</th><th align="left">Value</th><th align="left">Description</th></tr></thead><tbody><tr><td align="left">EXT2_FT_UNKNOWN</td><td align="left">0</td><td align="left">Unknown File Type</td></tr><tr><td align="left">EXT2_FT_REG_FILE</td><td align="left">1</td><td align="left">Regular File</td></tr><tr><td align="left">EXT2_FT_DIR</td><td align="left">2</td><td align="left">Directory File</td></tr><tr><td align="left">EXT2_FT_CHRDEV</td><td align="left">3</td><td align="left">Character Device</td></tr><tr><td align="left">EXT2_FT_BLKDEV</td><td align="left">4</td><td align="left">Block Device</td></tr><tr><td align="left">EXT2_FT_FIFO</td><td align="left">5</td><td align="left">Buffer File</td></tr><tr><td align="left">EXT2_FT_SOCK</td><td align="left">6</td><td align="left">Socket File</td></tr><tr><td align="left">EXT2_FT_SYMLINK</td><td align="left">7</td><td align="left">Symbolic Link</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ifdir-name"></a>name</h3></div></div></div><p> + Name of the entry. The ISO-Latin-1 character set is expected in most system. + The name must be no longer than 255 bytes after encoding. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="dir-sample"></a>Sample Directory</h3></div></div></div><p> + Here's a sample of the home directory of one user on my system: + </p><pre class="programlisting"> +$ ls -1a ~ +. +.. +.bash_profile +.bashrc +mbox +public_html +tmp + </pre><p> + For which the following data representation can be found on the storage + device: + </p><div class="table"><a id="sample-linked-directory-data"></a><p class="title"><strong>Table 4.3. Sample Linked Directory Data Layout, 4KiB blocks</strong></p><div class="table-contents"><table summary="Sample Linked Directory Data Layout, 4KiB blocks" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td colspan="3" align="left">Directory Entry 0</td></tr><tr><td>0</td><td>4</td><td>inode number: 783362</td></tr><tr><td>4</td><td>2</td><td>record length: 12</td></tr><tr><td>6</td><td>1</td><td>name length: 1</td></tr><tr><td>7</td><td>1</td><td>file type: <code class="constant">EXT2_FT_DIR</code>=2</td></tr><tr><td>8</td><td>1</td><td>name: .</td></tr><tr><td>9</td><td>3</td><td>padding</td></tr><tr><td colspan="3" align="left">Directory Entry 1</td></tr><tr><td>12</td><td>4</td><td>inode number: 1109761</td></tr><tr><td>16</td><td>2</td><td>record length: 12</td></tr><tr><td>18</td><td>1</td><td>name length: 2</td></tr><tr><td>19</td><td>1</td><td>file type: <code class="constant">EXT2_FT_DIR</code>=2</td></tr><tr><td>20</td><td>2</td><td>name: ..</td></tr><tr><td>22</td><td>2</td><td>padding</td></tr><tr><td colspan="3" align="left">Directory Entry 2</td></tr><tr><td>24</td><td>4</td><td>inode number: 783364</td></tr><tr><td>28</td><td>2</td><td>record length: 24</td></tr><tr><td>30</td><td>1</td><td>name length: 13</td></tr><tr><td>31</td><td>1</td><td>file type: <code class="constant">EXT2_FT_REG_FILE</code></td></tr><tr><td>32</td><td>13</td><td>name: .bash_profile</td></tr><tr><td>45</td><td>3</td><td>padding</td></tr><tr><td colspan="3" align="left">Directory Entry 3</td></tr><tr><td>48</td><td>4</td><td>inode number: 783363</td></tr><tr><td>52</td><td>2</td><td>record length: 16</td></tr><tr><td>54</td><td>1</td><td>name length: 7</td></tr><tr><td>55</td><td>1</td><td>file type: <code class="constant">EXT2_FT_REG_FILE</code></td></tr><tr><td>56</td><td>7</td><td>name: .bashrc</td></tr><tr><td>63</td><td>1</td><td>padding</td></tr><tr><td colspan="3" align="left">Directory Entry 4</td></tr><tr><td>64</td><td>4</td><td>inode number: 783377</td></tr><tr><td>68</td><td>2</td><td>record length: 12</td></tr><tr><td>70</td><td>1</td><td>name length: 4</td></tr><tr><td>71</td><td>1</td><td>file type: <code class="constant">EXT2_FT_REG_FILE</code></td></tr><tr><td>72</td><td>4</td><td>name: mbox</td></tr><tr><td colspan="3" align="left">Directory Entry 5</td></tr><tr><td>76</td><td>4</td><td>inode number: 783545</td></tr><tr><td>80</td><td>2</td><td>record length: 20</td></tr><tr><td>82</td><td>1</td><td>name length: 11</td></tr><tr><td>83</td><td>1</td><td>file type: <code class="constant">EXT2_FT_DIR</code>=2</td></tr><tr><td>84</td><td>11</td><td>name: public_html</td></tr><tr><td>95</td><td>1</td><td>padding</td></tr><tr><td colspan="3" align="left">Directory Entry 6</td></tr><tr><td>96</td><td>4</td><td>inode number: 669354</td></tr><tr><td>100</td><td>2</td><td>record length: 12</td></tr><tr><td>102</td><td>1</td><td>name length: 3</td></tr><tr><td>103</td><td>1</td><td>file type: <code class="constant">EXT2_FT_DIR</code>=2</td></tr><tr><td>104</td><td>3</td><td>name: tmp</td></tr><tr><td>107</td><td>1</td><td>padding</td></tr><tr><td colspan="3" align="left">Directory Entry 7</td></tr><tr><td>108</td><td>4</td><td>inode number: 0</td></tr><tr><td>112</td><td>2</td><td>record length: 3988</td></tr><tr><td>114</td><td>1</td><td>name length: 0</td></tr><tr><td>115</td><td>1</td><td>file type: <code class="constant">EXT2_FT_UNKNOWN</code></td></tr><tr><td>116</td><td>0</td><td>name:</td></tr><tr><td>116</td><td>3980</td><td>padding</td></tr></tbody></table></div></div><br class="table-break" /></div></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="indexed-directory"></a>Indexed Directory Format</h2></div></div></div><p> + Using the standard linked list directory format can become very slow + once the number of files starts growing. To improve performances in + such a system, a hashed index is used, which allow to quickly + locate the particular file searched. + </p><p> + Bit <a class="link" href="#ext2-index-fl" title="EXT2_INDEX_FL - Hash Indexed Directory">EXT2_INDEX_FL</a> in the + <a class="link" href="#i-flags" title="i_flags">i_flags</a> of the directory inode + is set if the indexed directory format is used. + </p><p> + In order to maintain backward compatibility with older implementations, + the indexed directory also maintains a linked directory format side-by-side. + In case there's any discrepency between the indexed and linked directories, + the linked directory is preferred. + </p><p> + This backward compatibility is achieved by placing a fake directory entries + at the beginning of block 0 of the indexed directory data blocks. These + fake entries are part of the <a class="link" href="#dx-root-structure" title="Table 4.4. Indexed Directory Root Structure">dx_root</a> + structure and host the linked directory information for the "." and ".." + folder entries. + </p><p> + Immediately following the <a class="xref" href="#dx-root" title="Indexed Directory Root">the section called “Indexed Directory Root”</a> structure is an array + of <a class="xref" href="#dx-entry" title="Indexed Directory Entry">the section called “Indexed Directory Entry”</a> up to the end of the data block or until + all files have been indexed. + </p><p> + When the number of files to be indexed exceeds the number of <a class="xref" href="#dx-entry" title="Indexed Directory Entry">the section called “Indexed Directory Entry”</a> + that can fit in a block (<a class="xref" href="#dx-entry-countlimit-limit" title="limit">the section called “limit”</a>), a level + of indirect indexes is created. An indirect index is another data block allocated + to the directory inode that contains directory entries. + </p><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="dx-root"></a>Indexed Directory Root</h3></div></div></div><div class="table"><a id="dx-root-structure"></a><p class="title"><strong>Table 4.4. Indexed Directory Root Structure</strong></p><div class="table-contents"><table summary="Indexed Directory Root Structure" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td colspan="3" align="left">-- Linked Directory Entry: . --</td></tr><tr><td>0</td><td>4</td><td>inode: this directory</td></tr><tr><td>4</td><td>2</td><td>rec_len: 12</td></tr><tr><td>6</td><td>1</td><td>name_len: 1</td></tr><tr><td>7</td><td>1</td><td>file_type: <code class="constant">EXT2_FT_DIR</code>=2</td></tr><tr><td>8</td><td>1</td><td>name: .</td></tr><tr><td>9</td><td>3</td><td>padding</td></tr><tr><td colspan="3" align="left">-- Linked Directory Entry: .. --</td></tr><tr><td>12</td><td>4</td><td>inode: parent directory</td></tr><tr><td>16</td><td>2</td><td>rec_len: (blocksize - this entry's length(12))</td></tr><tr><td>18</td><td>1</td><td>name_len: 2</td></tr><tr><td>19</td><td>1</td><td>file_type: <code class="constant">EXT2_FT_DIR</code>=2</td></tr><tr><td>20</td><td>2</td><td>name: ..</td></tr><tr><td>22</td><td>2</td><td>padding</td></tr><tr><td colspan="3" align="left">-- Indexed Directory Root Information Structure --</td></tr><tr><td>24</td><td>4</td><td>reserved, zero</td></tr><tr><td>28</td><td>1</td><td><a class="link" href="#dx-hash-version" title="hash_version">hash_version</a></td></tr><tr><td>29</td><td>1</td><td><a class="link" href="#dx-info-length" title="info_length">info_length</a></td></tr><tr><td>30</td><td>1</td><td><a class="link" href="#dx-indirect-levels" title="indirect_levels">indirect_levels</a></td></tr><tr><td>31</td><td>1</td><td>reserved - unused flags</td></tr></tbody></table></div></div><br class="table-break" /><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="dx-hash-version"></a>hash_version</h4></div></div></div><p> + 8bit value representing the hash version used in this indexed directory. + </p><div class="table"><a id="defined-dx-hash-version-values"></a><p class="title"><strong>Table 4.5. Defined Indexed Directory Hash Versions</strong></p><div class="table-contents"><table summary="Defined Indexed Directory Hash Versions" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Constant Name</th><th>Value</th><th>Description</th></tr></thead><tbody><tr><td>DX_HASH_LEGACY</td><td>0</td><td>TODO: link to section</td></tr><tr><td>DX_HASH_HALF_MD4</td><td>1</td><td>TODO: link to section</td></tr><tr><td>DX_HASH_TEA</td><td>2</td><td>TODO: link to section</td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="dx-info-length"></a>info_length</h4></div></div></div><p> + 8bit length of the indexed directory information structure (dx_root); + currently equal to 8. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="dx-indirect-levels"></a>indirect_levels</h4></div></div></div><p> + 8bit value indicating how many indirect levels of indexing are present in + this hash. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + In Linux, as of 2.6.28, the maximum indirect levels value supported is 1. + </p></div></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="dx-entry"></a>Indexed Directory Entry</h3></div></div></div><p> + The indexed directory entries are used to quickly lookup the inode number + associated with the hash of a filename. These entries are located immediately + following the fake linked directory entry of the directory data blocks, or + immediately following the <a class="xref" href="#dx-root" title="Indexed Directory Root">the section called “Indexed Directory Root”</a>. + </p><p> + The first indexed directory entry, rather than containing an actual hash and + block number, contains the maximum number of indexed directory entries that + can fit in the block and the actual number of indexed directory entries + stored in the block. The format of this special entry is detailed in + <a class="xref" href="#dx-entry-countlimit" title="Table 4.7. Indexed Directory Entry Count and Limit Structure">Table 4.7, “Indexed Directory Entry Count and Limit Structure”</a>. + </p><p> + The other directory entries are sorted by hash value starting from the + smallest to the largest numerical value. + </p><div class="table"><a id="dx-entry-structure"></a><p class="title"><strong>Table 4.6. Indexed Directory Entry Structure (dx_entry)</strong></p><div class="table-contents"><table summary="Indexed Directory Entry Structure (dx_entry)" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>4</td><td><a class="link" href="#dx-entry-hash" title="hash">hash</a></td></tr><tr><td>4</td><td>4</td><td><a class="link" href="#dx-entry-block" title="block">block</a></td></tr></tbody></table></div></div><br class="table-break" /><div class="table"><a id="dx-entry-countlimit"></a><p class="title"><strong>Table 4.7. Indexed Directory Entry Count and Limit Structure</strong></p><div class="table-contents"><table summary="Indexed Directory Entry Count and Limit Structure" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytes)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>2</td><td><a class="link" href="#dx-entry-countlimit-limit" title="limit">limit</a></td></tr><tr><td>2</td><td>2</td><td><a class="link" href="#dx-entry-countlimit-count" title="count">count</a></td></tr></tbody></table></div></div><br class="table-break" /><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="dx-entry-hash"></a>hash</h4></div></div></div><p> + 32bit hash of the filename represented by this entry. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="dx-entry-block"></a>block</h4></div></div></div><p> + 32bit block index of the directory inode data block containing the (linked) directory entry for the filename. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="dx-entry-countlimit-limit"></a>limit</h4></div></div></div><p> + 16bit value representing the total number of indexed directory entries that + fit within the block, after removing the other structures, but including + the count/limit entry. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="dx-entry-countlimit-count"></a>count</h4></div></div></div><p> + 16bit value representing the total number of indexed directory entries + present in the block. TODO: Research if this value includes the count/limit entry. + </p></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="contrib-lookup-algorithm"></a>Lookup Algorithm</h3></div></div></div><p> + Lookup is straightforword: + </p><pre class="programlisting"> +- Compute a hash of the name +- Read the index root +- Use binary search (linear in the current code) to find the + first index or leaf block that could contain the target hash + (in tree order) +- Repeat the above until the lowest tree level is reached +- Read the leaf directory entry block and do a normal Ext2 + directory block search in it. +- If the name is found, return its directory entry and buffer +- Otherwise, if the collision bit of the next directory entry is + set, continue searching in the successor block + </pre><p> + Normally, two logical blocks of the file will need to be accessed, and + one or two metadata index blocks. The effect of the metadata index + blocks can largely be ignored in terms of disk access time since these + blocks are unlikely to be evicted from cache. There is some small CPU + cost that can be addressed by moving the whole directory into the page + cache. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="contrib-insert-algorithm"></a>Insert Algorithm</h3></div></div></div><p> + Insertion of new entries into the directory is considerably more + complex than lookup, due to the need to split leaf blocks when they + become full, and to satisfy the conditions that allow hash key + collisions to be handled reliably and efficiently. I'll just summarize + here: + </p><pre class="programlisting"> +- Probe the index as for lookup +- If the target leaf block is full, split it and note the block + that will receive the new entry +- Insert the new entry in the leaf block using the normal Ext2 + directory entry insertion code. + </pre><p> + The details of splitting and hash collision handling are somewhat + messy, but I will be happy to dwell on them at length if anyone is + interested. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="contrib-splitting"></a>Splitting</h3></div></div></div><p> + In brief, when a leaf node fills up and we want to put a new entry into + it the leaf has to be split, and its share of the hash space has to + be partitioned. The most straightforward way to do this is to sort the + entrys by hash value and split somewhere in the middle of the sorted + list. This operation is log(number_of_entries_in_leaf) and is not a + great cost so long as an efficient sorter is used. I used Combsort + for this, although Quicksort would have been just as good in this + case since average case performance is more important than worst case. + </p><p> + An alternative approach would be just to guess a median value for the + hash key, and the partition could be done in linear time, but the + resulting poorer partitioning of hash key space outweighs the small + advantage of the linear partition algorithm. In any event, the number + of entries needing sorting is bounded by the number that fit in a leaf. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="contrib-key-collisions"></a>Key Collisions</h3></div></div></div><p> + Some complexity is introduced by the need to handle sequences of hash + key collisions. It is desireable to avoid splitting such sequences + between blocks, so the split point of a block is adjusted with this in + mind. But the possibility still remains that if the block fills up + with identically-hashed entries, the sequence may still have to be + split. This situation is flagged by placing a 1 in the low bit of the + index entry that points at the sucessor block, which is naturally + interpreted by the index probe as an intermediate value without any + special coding. Thus, handling the collision problem imposes no real + processing overhead, just come extra code and a slight reduction in the + hash key space. The hash key space remains sufficient for any + conceivable number of directory entries, up into the billions. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="contrib-hash-function"></a>Hash Function</h3></div></div></div><p> + The exact properties of the hash function critically affect the + performance of this indexing strategy, as I learned by trying a number + of poor hash functions, at times intentionally. A poor hash function + will result in many collisions or poor partitioning of the hash space. + To illustrate why the latter is a problem, consider what happens when a + block is split such that it covers just a few distinct hash values. + The probability of later index entries hashing into the same, small + hash space is very small. In practice, once a block is split, if its + hash space is too small it tends to stay half full forever, an effect I + observed in practice. + </p><p> + After some experimentation I came up with a hash function that gives + reasonably good dispersal of hash keys across the entire 31 bit key + space. This improved the average fullness of leaf blocks considerably, + getting much closer to the theoretical average of 3/4 full. + </p><p> + But the current hash function is just a place holder, waiting for + an better version based on some solid theory. I currently favor the + idea of using crc32 as the default hash function, but I welcome + suggestions. + </p><p> + Inevitably, no matter how good a hash function I come up with, somebody + will come up with a better one later. For this reason the design + allows for additional hash functiones to be added, with backward + compatibility. This is accomplished simply, by including a hash + function number in the index root. If a new, improved hash function is + added, all the previous versions remain available, and previously + created indexes remain readable. + </p><p> + Of course, the best strategy is to have a good hash function right from + the beginning. The initial, quick hack has produced results that + certainly have not been disappointing. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="contrib-performance"></a>Performance</h3></div></div></div><p> + OK, if you have read this far then this is no doubt the part you've + been waiting for. In short, the performance improvement over normal + Ext2 has been stunning. With very small directories performance is + similar to standard Ext2, but as directory size increases standard + Ext2 quickly blows up quadratically, while htree-enhanced Ext2 + continues to scale linearly. + </p><p> + Uli Luckas ran benchmarks for file creation in various sizes of + directories ranging from 10,000 to 90,000 files. The results are + pleasing: total file creation time stays very close to linear, versus + quadratic increase with normal Ext2. + </p><p> + Time to create: + </p><div class="figure"><a id="idm140660446987040"></a><p class="title"><strong>Figure 4.1. Performance of Indexed Directories</strong></p><div class="figure-contents"><pre class="programlisting"> + Indexed Normal + ======= ====== +10000 Files: 0m1.350s 0m23.670s +20000 Files: 0m2.720s 1m20.470s +30000 Files: 0m4.330s 3m9.320s +40000 Files: 0m5.890s 5m48.750s +50000 Files: 0m7.040s 9m31.270s +60000 Files: 0m8.610s 13m52.250s +70000 Files: 0m9.980s 19m24.070s +80000 Files: 0m12.060s 25m36.730s +90000 Files: 0m13.400s 33m18.550s + </pre></div></div><br class="figure-break" /><p> + The original paper by Daniel Phillips is at https://www.kernel.org/doc/ols/2002/ols2002-pages-425-438.pdf + </p><p> + All of these tests are CPU-bound, which may come as a surprise. The + directories fit easily in cache, and the limiting factor in the case of + standard Ext2 is the looking up of directory blocks in buffer cache, + and the low level scan of directory entries. In the case of htree + indexing there are a number of costs to be considered, all of them + pretty well bounded. Notwithstanding, there are a few obvious + optimizations to be done: + </p><pre class="programlisting"> +- Use binary search instead of linear search in the interior index + nodes. + +- If there is only one leaf block in a directory, bypass the index + probe, go straight to the block. + +- Map the directory into the page cache instead of the buffer cache. + </pre><p> + Each of these optimizations will produce a noticeable improvement in + performance, but naturally it will never be anything like the big jump + going from N**2 to Log512(N), ~= N. In time the optimizations will be + applied and we can expect to see another doubling or so in performance. + </p><p> + There will be a very slight performance hit when the directory gets big + enough to need a second level. Because of caching this will be very + small. Traversing the directories metadata index blocks will be a + bigger cost, and once again, this cost can be reduced by moving the + directory blocks into the page cache. + </p><p> + Typically, we will traverse 3 blocks to read or write a directory + entry, and that number increases to 4-5 with really huge directories. + But this is really nothing compared to normal Ext2, which traverses + several hundred blocks in the same situation. + </p></div></div></div><div class="chapter"><div class="titlepage"><div><div><h1 class="title"><a id="idm140660446981504"></a>Chapter 5. File Attributes</h1></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="sect1"><a href="#idm140660446979776">Standard Attributes</a></span></dt><dd><dl><dt><span class="sect2"><a href="#idm140660446979264">SUID, SGID and -rwxrwxrwx</a></span></dt><dt><span class="sect2"><a href="#idm140660446977504">File Size</a></span></dt><dt><span class="sect2"><a href="#idm140660446975776">Owner and Group</a></span></dt></dl></dd><dt><span class="sect1"><a href="#contrib-extended-attributes">Extended Attributes</a></span></dt><dd><dl><dt><span class="sect2"><a href="#extended-attribute-layout">Extended Attribute Block Layout</a></span></dt><dt><span class="sect2"><a href="#attribute-block-header">Extended Attribute Block Header</a></span></dt><dt><span class="sect2"><a href="#idm140660446913440">Attribute Entry Header</a></span></dt></dl></dd><dt><span class="sect1"><a href="#behaviour-flags">Behaviour Control Flags</a></span></dt><dd><dl><dt><span class="sect2"><a href="#ext2-secrm-fl">EXT2_SECRM_FL - Secure Deletion</a></span></dt><dt><span class="sect2"><a href="#ext2-unrm-fl">EXT2_UNRM_FL - Record for Undelete</a></span></dt><dt><span class="sect2"><a href="#ext2-compr-fl">EXT2_COMPR_FL - Compressed File</a></span></dt><dt><span class="sect2"><a href="#ext2-sync-fl">EXT2_SYNC_FL - Synchronous Updates</a></span></dt><dt><span class="sect2"><a href="#ext2-immutable-fl">EXT2_IMMUTABLE_FL - Immutable File</a></span></dt><dt><span class="sect2"><a href="#ext2-append-fl">EXT2_APPEND_FL - Append Only</a></span></dt><dt><span class="sect2"><a href="#ext2-nodump-fl">EXT2_NODUMP_FL - Do No Dump/Delete</a></span></dt><dt><span class="sect2"><a href="#ext2-noatime-fl">EXT2_NOATIME_FL - Do Not Update .i_atime</a></span></dt><dt><span class="sect2"><a href="#ext2-dirty-fl">EXT2_DIRTY_FL - Dirty</a></span></dt><dt><span class="sect2"><a href="#ext2-comprblk-fl">EXT2_COMPRBLK_FL - Compressed Blocks</a></span></dt><dt><span class="sect2"><a href="#ext2-nocompr-fl">EXT2_NOCOMPR_FL - Access Raw Compressed Data</a></span></dt><dt><span class="sect2"><a href="#ext2-ecompr-fl">EXT2_ECOMPR_FL - Compression Error</a></span></dt><dt><span class="sect2"><a href="#ext2-btree-fl">EXT2_BTREE_FL - B-Tree Format Directory</a></span></dt><dt><span class="sect2"><a href="#ext2-index-fl">EXT2_INDEX_FL - Hash Indexed Directory</a></span></dt><dt><span class="sect2"><a href="#ext2-imagic-fl">EXT2_IMAGIC_FL - </a></span></dt><dt><span class="sect2"><a href="#ext3-journal-data-fl">EXT2_JOURNAL_DATA_FL - Journal File Data</a></span></dt><dt><span class="sect2"><a href="#ext2-reserved-fl">EXT2_RESERVED_FL - Reserved</a></span></dt></dl></dd></dl></div><p> + Most of the file (also directory, symlink, device...) attributes are + located in the <a class="link" href="#inode-table" title="Inode Table">inode</a> associated with the file. + Some other attributes are only available as extended attributes. + </p><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="idm140660446979776"></a>Standard Attributes</h2></div></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="idm140660446979264"></a>SUID, SGID and -rwxrwxrwx</h3></div></div></div><p> + There isn't much to say about those, they are located with the SGID and SUID bits in + <a class="link" href="#i-mode" title="i_mode">ext2_inode.i_mode</a>. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="idm140660446977504"></a>File Size</h3></div></div></div><p> + The size of a file can be determined by looking at the + <a class="link" href="#i-size" title="i_size">ext2_inode.i_size</a> field. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="idm140660446975776"></a>Owner and Group</h3></div></div></div><p> + Under most implementations, the owner and group are 16bit values, but on + some recent Linux and Hurd implementations the owner and group id are + 32bit. When 16bit values are used, only the <span class="quote">“<span class="quote">low</span>”</span> part should + be used as valid, while when using 32bit value, both the <span class="quote">“<span class="quote">low</span>”</span> + and <span class="quote">“<span class="quote">high</span>”</span> part should be used, the high part being shifted left + 16 places then added to the low part. + </p><p> + The low part of owner and group are located in + <a class="link" href="#i-uid" title="i_uid">ext2_inode.i_uid</a> and + <a class="link" href="#i-gid" title="i_gid">ext2_inode.i_gid</a> respectively. + </p><p> + The high part of owner and group are located in + <a class="link" href="#h-i-uid-high" title="h_i_uid_high">ext2_inode.osd2.hurd.h_i_uid_high</a> and + <a class="link" href="#l-i-gid-high" title="l_i_gid_high">ext2_inode.osd2.hurd.h_i_gid_high</a>, + respectively, for Hurd and located in + <a class="link" href="#l-i-uid-high" title="l_i_uid_high">ext2_inode.osd2.linux.l_i_uid_high</a> and + <a class="link" href="#l-i-gid-high" title="l_i_gid_high">ext2_inode.osd2.linux.l_i_gid_high</a>, + respectively, for Linux. + </p></div></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="contrib-extended-attributes"></a>Extended Attributes</h2></div></div></div><p> + Extended attributes are name:value pairs associated permanently with + files and directories, similar to the environment strings associated + with a process. An attribute may be defined or undefined. If it is + defined, its value may be empty or non-empty. + </p><p> + Extended attributes are extensions to the normal attributes which are + associated with all inodes in the system. They are often used to + provide additional functionality to a filesystem - for example, + additional security features such as Access Control Lists (ACLs) may + be implemented using extended attributes. + </p><p> + Extended attributes are accessed as atomic objects. Reading retrieves + the whole value of an attribute and stores it in a buffer. Writing + replaces any previous value with the new value. + </p><p> + Extended attributes are stored on disk blocks allocated outside of + any inode. The <a class="link" href="#i-file-acl" title="i_file_acl">i_file_acl</a> field (for + regular files) or the <a class="link" href="#i-dir-acl" title="i_dir_acl">i_dir_acl</a> field + (for directories) fields contain the block number of the allocated data + block used to store the extended attributes. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + Inodes which have all identical extended attributes may share the same + extended attribute block. + </p></div><p> + The attribute values are on the same block as their attribute entry + descriptions, aligned to the end of the attribute block. This allows + for additional attributes to be added more easily. The size of entry + headers varies with the length of the attribute name. + </p><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="extended-attribute-layout"></a>Extended Attribute Block Layout</h3></div></div></div><p> + The block header is followed by multiple entry descriptors. These entry + descriptors are variable in size, and aligned to <code class="constant">EXT2_XATTR_PAD</code> + (4) byte boundaries. The entry descriptors are sorted by attribute name, + so that two extended attribute blocks can be compared efficiently. + </p><p> + Attribute values are aligned to the end of the block, stored in + no specific order. They are also padded to <code class="constant">EXT2_XATTR_PAD</code> (4) + byte boundaries. No additional gaps are left between them. + </p><div class="table"><a id="extended-attribute-block-layout"></a><p class="title"><strong>Table 5.1. Extended Attribute Block Layout</strong></p><div class="table-contents"><table summary="Extended Attribute Block Layout" width="100%" border="1"><colgroup><col class="c1" /><col align="center" class="c2" /><col class="c3" /></colgroup><tbody><tr><td>Attribute Block Header</td><td class="auto-generated"> </td><td class="auto-generated"> </td></tr><tr><td>Attribute Entry 1</td><td align="center">|</td><td class="auto-generated"> </td></tr><tr><td>Attribute Entry 2</td><td align="center">|</td><td>growing downwards</td></tr><tr><td>Attribute Entry 3</td><td align="center">V</td><td class="auto-generated"> </td></tr><tr><td>4 null bytes</td><td class="auto-generated"> </td><td class="auto-generated"> </td></tr><tr><td>unused space...</td><td class="auto-generated"> </td><td class="auto-generated"> </td></tr><tr><td>Attribute Value 1</td><td align="center">^</td><td class="auto-generated"> </td></tr><tr><td>Attribute Value 3</td><td align="center">|</td><td>growing upwards</td></tr><tr><td>Attribute Value 2</td><td align="center">|</td><td class="auto-generated"> </td></tr></tbody></table></div></div><br class="table-break" /></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="attribute-block-header"></a>Extended Attribute Block Header</h3></div></div></div><div class="table"><a id="attribute-block-header-structure"></a><p class="title"><strong>Table 5.2. ext2_xattr_header structure</strong></p><div class="table-contents"><table summary="ext2_xattr_header structure" width="100%" border="1"><colgroup><col class="c1" /><col class="c2" /><col class="c3" /></colgroup><thead><tr><th>Offset (bytes)</th><th>Size (bytse)</th><th>Description</th></tr></thead><tbody><tr><td>0</td><td>4</td><td><a class="link" href="#xattr-h-magic" title="h_magic">h_magic</a></td></tr><tr><td>4</td><td>4</td><td><a class="link" href="#xattr-h-refcount" title="h_refcount">h_refcount</a></td></tr><tr><td>8</td><td>4</td><td><a class="link" href="#xattr-h-blocks" title="h_blocks">h_blocks</a></td></tr><tr><td>12</td><td>4</td><td><a class="link" href="#xattr-h-hash" title="h_hash">h_hash</a></td></tr><tr><td>16</td><td>16</td><td>reserved</td></tr></tbody></table></div></div><br class="table-break" /><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-h-magic"></a>h_magic</h4></div></div></div><p> + 32bit magic number of identification, <code class="constant">EXT2_XATTR_MAGIC</code> = 0xEA020000. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-h-refcount"></a>h_refcount</h4></div></div></div><p> + 32bit value used as reference count. This value is incremented everytime + a link is created to this attribute block and decremented when a link is + destroyed. Whenever this value reaches 0 the attribute block can be freed. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-h-blocks"></a>h_blocks</h4></div></div></div><p> + 32bit value indicating how many blocks are currently used by the + extended attributes. + </p><div class="note" style="margin-left: 0.5in; margin-right: 0.5in;"><h3 class="title">Note</h3><p> + In Linux a value of h_blocks higher than 1 is considered invalid. This + effectively restrict the amount of extended attributes to what can be + fit in a single block. + </p><p> + There does not seem to be any support for extended attributes in Ext2 under + GNU HURD. + </p></div></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-h-hash"></a>h_hash</h4></div></div></div><p> + 32bit hash value of all attribute entry header hashes. + </p><div class="procedure"><a id="xattr-h-hash-procedure"></a><p class="title"><strong>Procedure 5.1. Procedure to compute Extended Attribute Header Hash</strong></p><ol class="procedure" type="1"><li class="step"><p>Initialize the 32bit hash to 0</p></li><li class="step"><a id="xattr-h-hash-procedure-loop"></a><p>Check if there are any extended + attribute entry to process, if not we are done.</p></li><li class="step"><p>Do a cyclic bit shift of 16 bits to the left of the + 32bits hash value, effectively swapping the upper and lower 16bits of the hash</p></li><li class="step"><p>Perform a bitwise OR between the extended attribute entry + <a class="link" href="#xattr-e-hash" title="e_hash">hash</a> and the header hash being computed.</p></li><li class="step"><p>Go back to <a class="xref" href="#xattr-h-hash-procedure-loop" title="Step 2">Step 2</a>.</p></li></ol></div></div></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="idm140660446913440"></a>Attribute Entry Header</h3></div></div></div><div class="figure"><a id="idm140660446912928"></a><p class="title"><strong>Figure 5.1. ext2_xattr_header structure</strong></p><div class="figure-contents"><pre class="programlisting"> +offset size description +------- ------- ----------- + 0 1 <a class="link" href="#xattr-e-name-len" title="e_name_len">e_name_len</a> + 1 1 <a class="link" href="#xattr-e-name-index" title="e_name_index">e_name_index</a> + 2 2 <a class="link" href="#xattr-e-value-offs" title="e_value_offs">e_value_offs</a> + 4 4 <a class="link" href="#xattr-e-value-block" title="e_value_block">e_value_block</a> + 8 4 <a class="link" href="#xattr-e-value-size" title="e_value_size">e_value_size</a> + 12 4 <a class="link" href="#xattr-e-hash" title="e_hash">e_hash</a> + 16 ... <a class="link" href="#xattr-e-name" title="e_name">e_name</a> + </pre></div></div><br class="figure-break" /><p> + The total size of an attribute entry is always rounded to the + next 4-bytes boundary. + </p><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-e-name-len"></a>e_name_len</h4></div></div></div><p> + 8bit unsigned value indicating the length of the name. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-e-name-index"></a>e_name_index</h4></div></div></div><p> + 8bit unsigned value used as attribute name index. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-e-value-offs"></a>e_value_offs</h4></div></div></div><p> + 16bit unsigned offset to the value within the value block. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-e-value-block"></a>e_value_block</h4></div></div></div><p> + 32bit id of the block holding the value. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-e-value-size"></a>e_value_size</h4></div></div></div><p> + 32bit unsigned value indicating the size of the attribute value. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-e-hash"></a>e_hash</h4></div></div></div><p> + 32bit hash of attribute name and value. + </p></div><div class="sect3"><div class="titlepage"><div><div><h4 class="title"><a id="xattr-e-name"></a>e_name</h4></div></div></div><p> + Attribute name. + </p></div></div></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="behaviour-flags"></a>Behaviour Control Flags</h2></div></div></div><p> + The <a class="link" href="#i-flags" title="i_flags">i_flags</a> value in the + <a class="link" href="#inode-structure" title="Table 3.13. Inode Structure">inode</a> structure allows to specify how the + file system should behave in regard to the file. The following bits + are currently defined: + </p><div class="table"><a id="idm140660446894752"></a><p class="title"><strong>Table 5.3. Behaviour Control Flags</strong></p><div class="table-contents"><table summary="Behaviour Control Flags" width="100%" border="1"><colgroup><col align="left" /><col align="left" /><col align="left" /></colgroup><tbody><tr><td align="left"><a class="link" href="#ext2-secrm-fl" title="EXT2_SECRM_FL - Secure Deletion">EXT2_SECRM_FL</a></td><td align="left">0x00000001</td><td align="left">secure deletion</td></tr><tr><td align="left"><a class="link" href="#ext2-unrm-fl" title="EXT2_UNRM_FL - Record for Undelete">EXT2_UNRM_FL</a></td><td align="left">0x00000002</td><td align="left">record for undelete</td></tr><tr><td align="left"><a class="link" href="#ext2-compr-fl" title="EXT2_COMPR_FL - Compressed File">EXT2_COMPR_FL</a></td><td align="left">0x00000004</td><td align="left">compressed file</td></tr><tr><td align="left"><a class="link" href="#ext2-sync-fl" title="EXT2_SYNC_FL - Synchronous Updates">EXT2_SYNC_FL</a></td><td align="left">0x00000008</td><td align="left">synchronous updates</td></tr><tr><td align="left"><a class="link" href="#ext2-immutable-fl" title="EXT2_IMMUTABLE_FL - Immutable File">EXT2_IMMUTABLE_FL</a></td><td align="left">0x00000010</td><td align="left">immutable file</td></tr><tr><td align="left"><a class="link" href="#ext2-append-fl" title="EXT2_APPEND_FL - Append Only">EXT2_APPEND_FL</a></td><td align="left">0x00000020</td><td align="left">append only</td></tr><tr><td align="left"><a class="link" href="#ext2-nodump-fl" title="EXT2_NODUMP_FL - Do No Dump/Delete">EXT2_NODUMP_FL</a></td><td align="left">0x00000040</td><td align="left">do not dump/delete file</td></tr><tr><td align="left"><a class="link" href="#ext2-noatime-fl" title="EXT2_NOATIME_FL - Do Not Update .i_atime">EXT2_NOATIME_FL</a></td><td align="left">0x00000080</td><td align="left">do not update .i_atime</td></tr><tr><td align="left"><a class="link" href="#ext2-dirty-fl" title="EXT2_DIRTY_FL - Dirty">EXT2_DIRTY_FL</a></td><td align="left">0x00000100</td><td align="left">dirty (file is in use?)</td></tr><tr><td align="left"><a class="link" href="#ext2-comprblk-fl" title="EXT2_COMPRBLK_FL - Compressed Blocks">EXT2_COMPRBLK_FL</a></td><td align="left">0x00000200</td><td align="left">compressed blocks</td></tr><tr><td align="left"><a class="link" href="#ext2-nocompr-fl" title="EXT2_NOCOMPR_FL - Access Raw Compressed Data">EXT2_NOCOMPR_FL</a></td><td align="left">0x00000400</td><td align="left">access raw compressed data</td></tr><tr><td align="left"><a class="link" href="#ext2-ecompr-fl" title="EXT2_ECOMPR_FL - Compression Error">EXT2_ECOMPR_FL</a></td><td align="left">0x00000800</td><td align="left">compression error</td></tr><tr><td align="left"><a class="link" href="#ext2-btree-fl" title="EXT2_BTREE_FL - B-Tree Format Directory">EXT2_BTREE_FL</a></td><td align="left">0x00001000</td><td align="left">b-tree format directory</td></tr><tr><td align="left"><a class="link" href="#ext2-index-fl" title="EXT2_INDEX_FL - Hash Indexed Directory">EXT2_INDEX_FL</a></td><td align="left">0x00001000</td><td align="left">Hash indexed directory</td></tr><tr><td align="left"><a class="link" href="#ext2-imagic-fl" title="EXT2_IMAGIC_FL -">EXT2_IMAGIC_FL</a></td><td align="left">0x00002000</td><td align="left">?</td></tr><tr><td align="left"><a class="link" href="#ext3-journal-data-fl" title="EXT2_JOURNAL_DATA_FL - Journal File Data">EXT3_JOURNAL_DATA_FL</a></td><td align="left">0x00004000</td><td align="left">journal file data</td></tr><tr><td align="left"><a class="link" href="#ext2-reserved-fl" title="EXT2_RESERVED_FL - Reserved">EXT2_RESERVED_FL</a></td><td align="left">0x80000000</td><td align="left">reserved for ext2 implementation</td></tr></tbody></table></div></div><br class="table-break" /><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-secrm-fl"></a>EXT2_SECRM_FL - Secure Deletion</h3></div></div></div><p> + Enabling this bit will cause random data to be written over the file's + content several times before the blocks are unlinked. Note that this + is highly implementation dependant and as such, it should not be assumed + to be 100% secure. Make sure to study the implementation notes before + relying on this option. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-unrm-fl"></a>EXT2_UNRM_FL - Record for Undelete</h3></div></div></div><p> + When supported by the implementation, setting this bit will cause the + deleted data to be moved to a temporary location, where the user can + restore the original file without any risk of data lost. This is most + useful when using ext2 on a desktop or workstation. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-compr-fl"></a>EXT2_COMPR_FL - Compressed File</h3></div></div></div><p> + The file's content is compressed. There is no note about the particular + algorithm used other than maybe the + <a class="link" href="#s-algo-bitmap" title="s_algo_bitmap">s_algo_bitmap</a> field of the + <a class="link" href="#superblock" title="Superblock">superblock</a> structure. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-sync-fl"></a>EXT2_SYNC_FL - Synchronous Updates</h3></div></div></div><p> + The file's content in memory will be constantly synchronized with the + content on disk. This is mostly used for very sensitive boot files + or encryption keys that you do not want to lose in case of a crash. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-immutable-fl"></a>EXT2_IMMUTABLE_FL - Immutable File</h3></div></div></div><p> + The blocks associated with the file will not be exchanged. If for + any reason a file system defragmentation is launched, such files will + not be moved. Mostly used for stage2 and stage1.5 boot loaders. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-append-fl"></a>EXT2_APPEND_FL - Append Only</h3></div></div></div><p> + Writing can only be used to append content at the end of the file and + not modify the current content. Example of such use could be mailboxes, + where anybody could send a message to a user but not modify any already + present. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-nodump-fl"></a>EXT2_NODUMP_FL - Do No Dump/Delete</h3></div></div></div><p> + Setting this bit will protect the file from deletion. As long as this + bit is set, even if the <a class="link" href="#i-links-count" title="i_links_count">i_links_count</a> + is 0, the file will not be removed. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-noatime-fl"></a>EXT2_NOATIME_FL - Do Not Update .i_atime</h3></div></div></div><p> + The <a class="link" href="#i-atime" title="i_atime">i_atime</a> field of the + <a class="link" href="#inode-structure" title="Table 3.13. Inode Structure">inode</a> structure will not be modified when the + file is accessed if this bit is set. The only good use I can think of + that are related to security. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-dirty-fl"></a>EXT2_DIRTY_FL - Dirty</h3></div></div></div><p> + I do not have information at this moment about the use of this bit. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-comprblk-fl"></a>EXT2_COMPRBLK_FL - Compressed Blocks</h3></div></div></div><p> + This flag is set if one or more blocks are compressed. You can have + more information about compression on ext2 at + http://www.netspace.net.au/~reiter/e2compr/ Note that the project has + not been updated since 1999. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-nocompr-fl"></a>EXT2_NOCOMPR_FL - Access Raw Compressed Data</h3></div></div></div><p> + When this flag is set, the file system implementation will not uncompress + the data before fowarding it to the application but will rather give it as + is. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-ecompr-fl"></a>EXT2_ECOMPR_FL - Compression Error</h3></div></div></div><p> + This flag is set if an error was detected when trying to uncompress the + file. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-btree-fl"></a>EXT2_BTREE_FL - B-Tree Format Directory</h3></div></div></div><p> + + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-index-fl"></a>EXT2_INDEX_FL - Hash Indexed Directory</h3></div></div></div><p> + When this bit is set, the format of the directory file is hash indexed. + This is covered in details in <a class="xref" href="#indexed-directory" title="Indexed Directory Format">the section called “Indexed Directory Format”</a>. + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-imagic-fl"></a>EXT2_IMAGIC_FL - </h3></div></div></div><p> + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext3-journal-data-fl"></a>EXT2_JOURNAL_DATA_FL - Journal File Data</h3></div></div></div><p> + </p></div><div class="sect2"><div class="titlepage"><div><div><h3 class="title"><a id="ext2-reserved-fl"></a>EXT2_RESERVED_FL - Reserved</h3></div></div></div><p> + </p></div></div></div><div class="appendix"><div class="titlepage"><div><div><h1 class="title"><a id="idm140660446838800"></a>Appendix A. Credits</h1></div></div></div><p> + I would like to personally thank everybody who contributed to this document, + you are numerous and in many cases I haven't kept track of all of you. Be + sure that if you are not in this list, it's a mistake and do not hesitate + to contact me, it will be a pleasure to add your name to the list. + </p><pre class="programlisting"> +Peter Rottengatter ([email protected]) + Corrections to <a class="xref" href="#s-inodes-per-group" title="s_inodes_per_group">the section called “s_inodes_per_group”</a> + Corrections to <a class="xref" href="#disk-layout-sample-floppy" title="Table 3.1. Sample Floppy Disk Layout, 1KiB blocks">Table 3.1, “Sample Floppy Disk Layout, 1KiB blocks”</a> and <a class="xref" href="#disk-layout-sample-20mb" title="Table 3.2. Sample 20mb Partition Layout">Table 3.2, “Sample 20mb Partition Layout”</a> + Corrections to <a class="xref" href="#block-group-descriptor-table" title="Block Group Descriptor Table">the section called “Block Group Descriptor Table”</a> + +Ryan Cuthbertson ([email protected]) + Corrections to <a class="xref" href="#i-blocks" title="i_blocks">the section called “i_blocks”</a> + Corrections to <a class="xref" href="#disk-organisation" title="Chapter 3. Disk Organization">Chapter 3, <em>Disk Organization</em></a> + +Andreas Gruenbacher ([email protected]) + <a class="xref" href="#contrib-extended-attributes" title="Extended Attributes">the section called “Extended Attributes”</a> + +Daniel Phillips ([email protected]) + <a class="xref" href="#contrib-lookup-algorithm" title="Lookup Algorithm">the section called “Lookup Algorithm”</a> + <a class="xref" href="#contrib-insert-algorithm" title="Insert Algorithm">the section called “Insert Algorithm”</a> + <a class="xref" href="#contrib-splitting" title="Splitting">the section called “Splitting”</a> + <a class="xref" href="#contrib-key-collisions" title="Key Collisions">the section called “Key Collisions”</a> + <a class="xref" href="#contrib-hash-function" title="Hash Function">the section called “Hash Function”</a> + <a class="xref" href="#contrib-performance" title="Performance">the section called “Performance”</a> + +Jeremy Stanley of Access Data Inc. + Pointed out the inversed values for EXT2_S_IFSOCK and EXT2_S_IFLNK + +Ahmed S. Darwish ([email protected]) + Clarification on <a class="xref" href="#inode-bitmap" title="Inode Bitmap">the section called “Inode Bitmap”</a> + +Sami Besalel ([email protected]) + Typography correction in <a class="xref" href="#ext2-secrm-fl" title="EXT2_SECRM_FL - Secure Deletion">the section called “EXT2_SECRM_FL - Secure Deletion”</a>. + +Kwan Fong ([email protected]) + Improvement to wording in <a class="xref" href="#s-log-block-size" title="s_log_block_size">the section called “s_log_block_size”</a> + +Jonatan Schroeder ([email protected]) + Corrections to <a class="xref" href="#i-block" title="i_block">the section called “i_block”</a> with sparse files. + + </pre></div></div></body></html>
\ No newline at end of file diff --git a/build/ext2-doc/ext2-doc_color_en.pdf b/build/ext2-doc/ext2-doc_color_en.pdf Binary files differnew file mode 100644 index 0000000..e7864fa --- /dev/null +++ b/build/ext2-doc/ext2-doc_color_en.pdf diff --git a/makefile b/makefile deleted file mode 100644 index cd0aa8e..0000000 --- a/makefile +++ /dev/null @@ -1,37 +0,0 @@ -DOC = ext2 -SRC = ext2.sgml - -.PHONY: all pdf dvi ps html rtf clean - -all: pdf ps html rtf dvi - -pdf: $(DOC).pdf -dvi: $(DOC).dvi -ps: $(DOC).ps -html: $(DOC).html -rtf: $(DOC).rtf - -$(DOC).pdf: $(SRC) makefile - db2pdf $(SRC) - -$(DOC).dvi: $(SRC) makefile - db2dvi $(SRC) - -$(DOC).ps: $(SRC) makefile - db2ps $(SRC) - -$(DOC).html: $(SRC) makefile - db2html -u $(SRC) - mv ext2/ext2.html . - rm -rf ext2.junk ext2 - -$(DOC).rtf: $(SRC) makefile - db2rtf $(SRC) - -clean: - rm -rf $(DOC) $(DOC).pdf $(DOC).ps $(DOC).rtf $(DOC).dvi $(DOC).html - -install: - mv -f $(DOC).pdf $(DOC).ps $(DOC).rtf $(DOC).dvi $(DOC).html ../../web/ext2-doc/ - - |