code:
.. SPDX-License-Identifier: GPL-2.0
.. include:: <isonum.txt>

=====
DLMFS
=====

A minimal DLM userspace interface implemented via a virtual file
system.

dlmfs is built with OCFS2 as it requires most of its infrastructure.

:Project web page:    http://ocfs2.wiki.kernel.org
:Tools web page:      https://github.com/markfasheh/ocfs2-tools
:OCFS2 mailing lists: https://oss.oracle.com/projects/ocfs2/mailman/

All code copyright 2005 Oracle except when otherwise noted.

Credits
=======

Some code taken from ramfs which is Copyright |copy| 2000 Linus Torvalds
and Transmeta Corp.

Mark Fasheh <mark.fasheh@oracle.com>

Caveats
=======
- Right now it only works with the OCFS2 DLM, though support for other
  DLM implementations should not be a major issue.

Mount options
=============
None

Usage
=====

If you're just interested in OCFS2, then please see ocfs2.txt. The
rest of this document will be geared towards those who want to use
dlmfs for easy to setup and easy to use clustered locking in
userspace.

Setup
=====

dlmfs requires that the OCFS2 cluster infrastructure be in
place. Please download ocfs2-tools from the above url and configure a
cluster.

You'll want to start heartbeating on a volume which all the nodes in
your lockspace can access. The easiest way to do this is via
ocfs2_hb_ctl (distributed with ocfs2-tools). Right now it requires
that an OCFS2 file system be in place so that it can automatically
find its heartbeat area, though it will eventually support heartbeat
against raw disks.

Please see the ocfs2_hb_ctl and mkfs.ocfs2 manual pages distributed
with ocfs2-tools.

Once you're heartbeating, DLM lock 'domains' can be easily created /
destroyed and locks within them accessed.

Locking
=======

Users may access dlmfs via standard file system calls, or they can use
'libo2dlm' (distributed with ocfs2-tools) which abstracts the file
system calls and presents a more traditional locking api.

dlmfs handles lock caching automatically for the user, so a lock
request for an already acquired lock will not generate another DLM
call. Userspace programs are assumed to handle their own local
locking.

Two levels of locks are supported - Shared Read, and Exclusive.
Also supported is a Trylock operation.

For information on the libo2dlm interface, please see o2dlm.h,
distributed with ocfs2-tools.

Lock value blocks can be read and written to a resource via read(2)
and write(2) against the fd obtained via your open(2) call. The
maximum currently supported LVB length is 64 bytes (though that is an
OCFS2 DLM limitation). Through this mechanism, users of dlmfs can share
small amounts of data amongst their nodes.

mkdir(2) signals dlmfs to join a domain (which will have the same name
as the resulting directory)

rmdir(2) signals dlmfs to leave the domain

Locks for a given domain are represented by regular inodes inside the
domain directory.  Locking against them is done via the open(2) system
call.

The open(2) call will not return until your lock has been granted or
an error has occurred, unless it has been instructed to do a trylock
operation. If the lock succeeds, you'll get an fd.

open(2) with O_CREAT to ensure the resource inode is created - dlmfs does
not automatically create inodes for existing lock resources.

============  ===========================
Open Flag     Lock Request Type
============  ===========================
O_RDONLY      Shared Read
O_RDWR        Exclusive
============  ===========================

============  ===========================
Open Flag     Resulting Locking Behavior
============  ===========================
O_NONBLOCK    Trylock operation
============  ===========================

You must provide exactly one of O_RDONLY or O_RDWR.

If O_NONBLOCK is also provided and the trylock operation was valid but
could not lock the resource then open(2) will return ETXTBUSY.

close(2) drops the lock associated with your fd.

Modes passed to mkdir(2) or open(2) are adhered to locally. Chown is
supported locally as well. This means you can use them to restrict
access to the resources via dlmfs on your local node only.

The resource LVB may be read from the fd in either Shared Read or
Exclusive modes via the read(2) system call. It can be written via
write(2) only when open in Exclusive mode.

Once written, an LVB will be visible to other nodes who obtain Read
Only or higher level locks on the resource.

See Also
========
http://opendlm.sourceforge.net/cvsmirror/opendlm/docs/dlmbook_final.pdf

For more information on the VMS distributed locking API.


code:
.. SPDX-License-Identifier: GPL-2.0

============================
Linux Directory Notification
============================

	   Stephen Rothwell <sfr@canb.auug.org.au>

The intention of directory notification is to allow user applications
to be notified when a directory, or any of the files in it, are changed.
The basic mechanism involves the application registering for notification
on a directory using a fcntl(2) call and the notifications themselves
being delivered using signals.

The application decides which "events" it wants to be notified about.
The currently defined events are:

	=========	=====================================================
	DN_ACCESS	A file in the directory was accessed (read)
	DN_MODIFY	A file in the directory was modified (write,truncate)
	DN_CREATE	A file was created in the directory
	DN_DELETE	A file was unlinked from directory
	DN_RENAME	A file in the directory was renamed
	DN_ATTRIB	A file in the directory had its attributes
			changed (chmod,chown)
	=========	=====================================================

Usually, the application must reregister after each notification, but
if DN_MULTISHOT is or'ed with the event mask, then the registration will
remain until explicitly removed (by registering for no events).

By default, SIGIO will be delivered to the process and no other useful
information.  However, if the F_SETSIG fcntl(2) call is used to let the
kernel know which signal to deliver, a siginfo structure will be passed to
the signal handler and the si_fd member of that structure will contain the
file descriptor associated with the directory in which the event occurred.

Preferably the application will choose one of the real time signals
(SIGRTMIN + <n>) so that the notifications may be queued.  This is
especially important if DN_MULTISHOT is specified.  Note that SIGRTMIN
is often blocked, so it is better to use (at least) SIGRTMIN + 1.

Implementation expectations (features and bugs :-))
---------------------------------------------------

The notification should work for any local access to files even if the
actual file system is on a remote server.  This implies that remote
access to files served by local user mode servers should be notified.
Also, remote accesses to files served by a local kernel NFS server should
be notified.

In order to make the impact on the file system code as small as possible,
the problem of hard links to files has been ignored.  So if a file (x)
exists in two directories (a and b) then a change to the file using the
name "a/x" should be notified to a program expecting notifications on
directory "a", but will not be notified to one expecting notifications on
directory "b".

Also, files that are unlinked, will still cause notifications in the
last directory that they were linked to.

Configuration
-------------

Dnotify is controlled via the CONFIG_DNOTIFY configuration option.  When
disabled, fcntl(fd, F_NOTIFY, ...) will return -EINVAL.

Example
-------
See tools/testing/selftests/filesystems/dnotify_test.c for an example.

NOTE
----
Beginning with Linux 2.6.13, dnotify has been replaced by inotify.
See Documentation/filesystems/inotify.rst for more information on it.

repo_name: angery/linux


code:
.. SPDX-License-Identifier: GPL-2.0

======================================================
eCryptfs: A stacked cryptographic filesystem for Linux
======================================================

eCryptfs is free software. Please see the file COPYING for details.
For documentation, please see the files in the doc/ subdirectory.  For
building and installation instructions please see the INSTALL file.

:Maintainer: Phillip Hellewell
:Lead developer: Michael A. Halcrow <mhalcrow@us.ibm.com>
:Developers: Michael C. Thompson
             Kent Yoder
:Web Site: http://ecryptfs.sf.net

This software is currently undergoing development. Make sure to
maintain a backup copy of any data you write into eCryptfs.

eCryptfs requires the userspace tools downloadable from the
SourceForge site:

http://sourceforge.net/projects/ecryptfs/

Userspace requirements include:

- David Howells' userspace keyring headers and libraries (version
  1.0 or higher), obtainable from
  http://people.redhat.com/~dhowells/keyutils/
- Libgcrypt

.. note::

   In the beta/experimental releases of eCryptfs, when you upgrade
   eCryptfs, you should copy the files to an unencrypted location and
   then copy the files back into the new eCryptfs mount to migrate the
   files.

Mount-wide Passphrase
=====================

Create a new directory into which eCryptfs will write its encrypted
files (i.e., /root/crypt).  Then, create the mount point directory
(i.e., /mnt/crypt).  Now it's time to mount eCryptfs::

    mount -t ecryptfs /root/crypt /mnt/crypt

You should be prompted for a passphrase and a salt (the salt may be
blank).

Try writing a new file::

    echo "Hello, World" > /mnt/crypt/hello.txt

The operation will complete.  Notice that there is a new file in
/root/crypt that is at least 12288 bytes in size (depending on your
host page size).  This is the encrypted underlying file for what you
just wrote.  To test reading, from start to finish, you need to clear
the user session keyring:

keyctl clear @u

Then umount /mnt/crypt and mount again per the instructions given
above.

::

    cat /mnt/crypt/hello.txt

Notes
=====

eCryptfs version 0.1 should only be mounted on (1) empty directories
or (2) directories containing files only created by eCryptfs. If you
mount a directory that has pre-existing files not created by eCryptfs,
then behavior is undefined. Do not run eCryptfs in higher verbosity
levels unless you are doing so for the sole purpose of debugging or
development, since secret values will be written out to the system log
in that case.

Mike Halcrow
mhalcrow@us.ibm.com


code:
.. SPDX-License-Identifier: GPL-2.0

=======================================
efivarfs - a (U)EFI variable filesystem
=======================================

The efivarfs filesystem was created to address the shortcomings of
using entries in sysfs to maintain EFI variables. The old sysfs EFI
variables code only supported variables of up to 1024 bytes. This
limitation existed in version 0.99 of the EFI specification, but was
removed before any full releases. Since variables can now be larger
than a single page, sysfs isn't the best interface for this.

Variables can be created, deleted and modified with the efivarfs
filesystem.

efivarfs is typically mounted like this::

	mount -t efivarfs none /sys/firmware/efi/efivars

Due to the presence of numerous firmware bugs where removing non-standard
UEFI variables causes the system firmware to fail to POST, efivarfs
files that are not well-known standardized variables are created
as immutable files.  This doesn't prevent removal - "chattr -i" will work -
but it does prevent this kind of failure from being accomplished
accidentally.

.. warning ::
      When a content of an UEFI variable in /sys/firmware/efi/efivars is
      displayed, for example using "hexdump", pay attention that the first
      4 bytes of the output represent the UEFI variable attributes,
      in little-endian format.

      Practically the output of each efivar is composed of:

          +-----------------------------------+
          |4_bytes_of_attributes + efivar_data|
          +-----------------------------------+

*See also:*

- Documentation/admin-guide/acpi/ssdt-overlays.rst
- Documentation/ABI/stable/sysfs-firmware-efi-vars


code:
.. SPDX-License-Identifier: GPL-2.0

======================================
EROFS - Enhanced Read-Only File System
======================================

Overview
========

EROFS filesystem stands for Enhanced Read-Only File System.  It aims to form a
generic read-only filesystem solution for various read-only use cases instead
of just focusing on storage space saving without considering any side effects
of runtime performance.

It is designed to meet the needs of flexibility, feature extendability and user
payload friendly, etc.  Apart from those, it is still kept as a simple
random-access friendly high-performance filesystem to get rid of unneeded I/O
amplification and memory-resident overhead compared to similar approaches.

It is implemented to be a better choice for the following scenarios:

 - read-only storage media or

 - part of a fully trusted read-only solution, which means it needs to be
   immutable and bit-for-bit identical to the official golden image for
   their releases due to security or other considerations and

 - hope to minimize extra storage space with guaranteed end-to-end performance
   by using compact layout, transparent file compression and direct access,
   especially for those embedded devices with limited memory and high-density
   hosts with numerous containers.

Here are the main features of EROFS:

 - Little endian on-disk design;

 - Block-based distribution and file-based distribution over fscache are
   supported;

 - Support multiple devices to refer to external blobs, which can be used
   for container images;

 - 4KiB block size and 32-bit block addresses for each device, therefore
   16TiB address space at most for now;

 - Two inode layouts for different requirements:

   =====================  ============  ======================================
                          compact (v1)  extended (v2)
   =====================  ============  ======================================
   Inode metadata size    32 bytes      64 bytes
   Max file size          4 GiB         16 EiB (also limited by max. vol size)
   Max uids/gids          65536         4294967296
   Per-inode timestamp    no            yes (64 + 32-bit timestamp)
   Max hardlinks          65536         4294967296
   Metadata reserved      8 bytes       18 bytes
   =====================  ============  ======================================

 - Support extended attributes as an option;

 - Support POSIX.1e ACLs by using extended attributes;

 - Support transparent data compression as an option:
   LZ4 and MicroLZMA algorithms can be used on a per-file basis; In addition,
   inplace decompression is also supported to avoid bounce compressed buffers
   and page cache thrashing.

 - Support chunk-based data deduplication and rolling-hash compressed data
   deduplication;

 - Support tailpacking inline compared to byte-addressed unaligned metadata
   or smaller block size alternatives;

 - Support merging tail-end data into a special inode as fragments.

 - Support large folios for uncompressed files.

 - Support direct I/O on uncompressed files to avoid double caching for loop
   devices;

 - Support FSDAX on uncompressed images for secure containers and ramdisks in
   order to get rid of unnecessary page cache.

 - Support file-based on-demand loading with the Fscache infrastructure.

The following git tree provides the file system user-space tools under
development, such as a formatting tool (mkfs.erofs), an on-disk consistency &
compatibility checking tool (fsck.erofs), and a debugging tool (dump.erofs):

- git://git.kernel.org/pub/scm/linux/kernel/git/xiang/erofs-utils.git

Bugs and patches are welcome, please kindly help us and send to the following
linux-erofs mailing list:

- linux-erofs mailing list   <linux-erofs@lists.ozlabs.org>

Mount options
=============

===================    =========================================================
(no)user_xattr         Setup Extended User Attributes. Note: xattr is enabled
                       by default if CONFIG_EROFS_FS_XATTR is selected.
(no)acl                Setup POSIX Access Control List. Note: acl is enabled
                       by default if CONFIG_EROFS_FS_POSIX_ACL is selected.
cache_strategy=%s      Select a strategy for cached decompression from now on:

		       ==========  =============================================
                         disabled  In-place I/O decompression only;
                        readahead  Cache the last incomplete compressed physical
                                   cluster for further reading. It still does
                                   in-place I/O decompression for the rest
                                   compressed physical clusters;
                       readaround  Cache the both ends of incomplete compressed
                                   physical clusters for further reading.
                                   It still does in-place I/O decompression
                                   for the rest compressed physical clusters.
		       ==========  =============================================
dax={always,never}     Use direct access (no page cache).  See
                       Documentation/filesystems/dax.rst.
dax                    A legacy option which is an alias for ``dax=always``.
device=%s              Specify a path to an extra device to be used together.
fsid=%s                Specify a filesystem image ID for Fscache back-end.
===================    =========================================================

Sysfs Entries
=============

Information about mounted erofs file systems can be found in /sys/fs/erofs.
Each mounted filesystem will have a directory in /sys/fs/erofs based on its
device name (i.e., /sys/fs/erofs/sda).
(see also Documentation/ABI/testing/sysfs-fs-erofs)

On-disk details
===============

Summary
-------
Different from other read-only file systems, an EROFS volume is designed
to be as simple as possible::

                                |-> aligned with the block size
   ____________________________________________________________
  | |SB| | ... | Metadata | ... | Data | Metadata | ... | Data |
  |_|__|_|_____|__________|_____|______|__________|_____|______|
  0 +1K

All data areas should be aligned with the block size, but metadata areas
may not. All metadatas can be now observed in two different spaces (views):

 1. Inode metadata space

    Each valid inode should be aligned with an inode slot, which is a fixed
    value (32 bytes) and designed to be kept in line with compact inode size.

    Each inode can be directly found with the following formula:
         inode offset = meta_blkaddr * block_size + 32 * nid

    ::

                                 |-> aligned with 8B
                                            |-> followed closely
     + meta_blkaddr blocks                                      |-> another slot
       _____________________________________________________________________
     |  ...   | inode |  xattrs  | extents  | data inline | ... | inode ...
     |________|_______|(optional)|(optional)|__(optional)_|_____|__________
              |-> aligned with the inode slot size
                   .                   .
                 .                         .
               .                              .
             .                                    .
           .                                         .
         .                                              .
       .____________________________________________________|-> aligned with 4B
       | xattr_ibody_header | shared xattrs | inline xattrs |
       |____________________|_______________|_______________|
       |->    12 bytes    <-|->x * 4 bytes<-|               .
                           .                .                 .
                     .                      .                   .
                .                           .                     .
            ._______________________________.______________________.
            | id | id | id | id |  ... | id | ent | ... | ent| ... |
            |____|____|____|____|______|____|_____|_____|____|_____|
                                            |-> aligned with 4B
                                                        |-> aligned with 4B

    Inode could be 32 or 64 bytes, which can be distinguished from a common
    field which all inode versions have -- i_format::

        __________________               __________________
       |     i_format     |             |     i_format     |
       |__________________|             |__________________|
       |        ...       |             |        ...       |
       |                  |             |                  |
       |__________________| 32 bytes    |                  |
                                        |                  |
                                        |__________________| 64 bytes

    Xattrs, extents, data inline are followed by the corresponding inode with
    proper alignment, and they could be optional for different data mappings.
    _currently_ total 5 data layouts are supported:

    ==  ====================================================================
     0  flat file data without data inline (no extent);
     1  fixed-sized output data compression (with non-compacted indexes);
     2  flat file data with tail packing data inline (no extent);
     3  fixed-sized output data compression (with compacted indexes, v5.3+);
     4  chunk-based file (v5.15+).
    ==  ====================================================================

    The size of the optional xattrs is indicated by i_xattr_count in inode
    header. Large xattrs or xattrs shared by many different files can be
    stored in shared xattrs metadata rather than inlined right after inode.

 2. Shared xattrs metadata space

    Shared xattrs space is similar to the above inode space, started with
    a specific block indicated by xattr_blkaddr, organized one by one with
    proper align.

    Each share xattr can also be directly found by the following formula:
         xattr offset = xattr_blkaddr * block_size + 4 * xattr_id

::

                           |-> aligned by  4 bytes
    + xattr_blkaddr blocks                     |-> aligned with 4 bytes
     _________________________________________________________________________
    |  ...   | xattr_entry |  xattr data | ... |  xattr_entry | xattr data  ...
    |________|_____________|_____________|_____|______________|_______________

Directories
-----------
All directories are now organized in a compact on-disk format. Note that
each directory block is divided into index and name areas in order to support
random file lookup, and all directory entries are _strictly_ recorded in
alphabetical order in order to support improved prefix binary search
algorithm (could refer to the related source code).

::

                  ___________________________
                 /                           |
                /              ______________|________________
               /              /              | nameoff1       | nameoffN-1
  ____________.______________._______________v________________v__________
 | dirent | dirent | ... | dirent | filename | filename | ... | filename |
 |___.0___|____1___|_____|___N-1__|____0_____|____1_____|_____|___N-1____|
      \                           ^
       \                          |                           * could have
        \                         |                             trailing '\0'
         \________________________| nameoff0
                             Directory block

Note that apart from the offset of the first filename, nameoff0 also indicates
the total number of directory entries in this block since it is no need to
introduce another on-disk field at all.

Chunk-based files
-----------------
In order to support chunk-based data deduplication, a new inode data layout has
been supported since Linux v5.15: Files are split in equal-sized data chunks
with ``extents`` area of the inode metadata indicating how to get the chunk
data: these can be simply as a 4-byte block address array or in the 8-byte
chunk index form (see struct erofs_inode_chunk_index in erofs_fs.h for more
details.)

By the way, chunk-based files are all uncompressed for now.

Data compression
----------------
EROFS implements fixed-sized output compression which generates fixed-sized
compressed data blocks from variable-sized input in contrast to other existing
fixed-sized input solutions. Relatively higher compression ratios can be gotten
by using fixed-sized output compression since nowadays popular data compression
algorithms are mostly LZ77-based and such fixed-sized output approach can be
benefited from the historical dictionary (aka. sliding window).

In details, original (uncompressed) data is turned into several variable-sized
extents and in the meanwhile, compressed into physical clusters (pclusters).
In order to record each variable-sized extent, logical clusters (lclusters) are
introduced as the basic unit of compress indexes to indicate whether a new
extent is generated within the range (HEAD) or not (NONHEAD). Lclusters are now
fixed in block size, as illustrated below::

          |<-    variable-sized extent    ->|<-       VLE         ->|
        clusterofs                        clusterofs              clusterofs
          |                                 |                       |
 _________v_________________________________v_______________________v________
 ... |    .         |              |        .     |              |  .   ...
 ____|____._________|______________|________.___ _|______________|__.________
     |-> lcluster <-|-> lcluster <-|-> lcluster <-|-> lcluster <-|
          (HEAD)        (NONHEAD)       (HEAD)        (NONHEAD)    .
           .             CBLKCNT            .                    .
            .                               .                  .
             .                              .                .
       _______._____________________________.______________._________________
          ... |              |              |              | ...
       _______|______________|______________|______________|_________________
              |->      big pcluster       <-|-> pcluster <-|

A physical cluster can be seen as a container of physical compressed blocks
which contains compressed data. Previously, only lcluster-sized (4KB) pclusters
were supported. After big pcluster feature is introduced (available since
Linux v5.13), pcluster can be a multiple of lcluster size.

For each HEAD lcluster, clusterofs is recorded to indicate where a new extent
starts and blkaddr is used to seek the compressed data. For each NONHEAD
lcluster, delta0 and delta1 are available instead of blkaddr to indicate the
distance to its HEAD lcluster and the next HEAD lcluster. A PLAIN lcluster is
also a HEAD lcluster except that its data is uncompressed. See the comments
around "struct z_erofs_vle_decompressed_index" in erofs_fs.h for more details.

If big pcluster is enabled, pcluster size in lclusters needs to be recorded as
well. Let the delta0 of the first NONHEAD lcluster store the compressed block
count with a special flag as a new called CBLKCNT NONHEAD lcluster. It's easy
to understand its delta0 is constantly 1, as illustrated below::

   __________________________________________________________
  | HEAD |  NONHEAD  | NONHEAD | ... | NONHEAD | HEAD | HEAD |
  |__:___|_(CBLKCNT)_|_________|_____|_________|__:___|____:_|
     |<----- a big pcluster (with CBLKCNT) ------>|<--  -->|
           a lcluster-sized pcluster (without CBLKCNT) ^

If another HEAD follows a HEAD lcluster, there is no room to record CBLKCNT,
but it's easy to know the size of such pcluster is 1 lcluster as well.

Since Linux v6.1, each pcluster can be used for multiple variable-sized extents,
therefore it can be used for compressed data deduplication.


code:
.. SPDX-License-Identifier: GPL-2.0

==============================
The Second Extended Filesystem
==============================

ext2 was originally released in January 1993.  Written by R\'emy Card,
Theodore Ts'o and Stephen Tweedie, it was a major rewrite of the
Extended Filesystem.  It is currently still (April 2001) the predominant
filesystem in use by Linux.  There are also implementations available
for NetBSD, FreeBSD, the GNU HURD, Windows 95/98/NT, OS/2 and RISC OS.

Options
=======

Most defaults are determined by the filesystem superblock, and can be
set using tune2fs(8). Kernel-determined defaults are indicated by (*).

====================    ===     ================================================
bsddf			(*)	Makes ``df`` act like BSD.
minixdf				Makes ``df`` act like Minix.

check=none, nocheck	(*)	Don't do extra checking of bitmaps on mount
				(check=normal and check=strict options removed)

dax				Use direct access (no page cache).  See
				Documentation/filesystems/dax.rst.

debug				Extra debugging information is sent to the
				kernel syslog.  Useful for developers.

errors=continue			Keep going on a filesystem error.
errors=remount-ro		Remount the filesystem read-only on an error.
errors=panic			Panic and halt the machine if an error occurs.

grpid, bsdgroups		Give objects the same group ID as their parent.
nogrpid, sysvgroups		New objects have the group ID of their creator.

nouid32				Use 16-bit UIDs and GIDs.

oldalloc			Enable the old block allocator. Orlov should
				have better performance, we'd like to get some
				feedback if it's the contrary for you.
orlov			(*)	Use the Orlov block allocator.
				(See http://lwn.net/Articles/14633/ and
				http://lwn.net/Articles/14446/.)

resuid=n			The user ID which may use the reserved blocks.
resgid=n			The group ID which may use the reserved blocks.

sb=n				Use alternate superblock at this location.

user_xattr			Enable "user." POSIX Extended Attributes
				(requires CONFIG_EXT2_FS_XATTR).
nouser_xattr			Don't support "user." extended attributes.

acl				Enable POSIX Access Control Lists support
				(requires CONFIG_EXT2_FS_POSIX_ACL).
noacl				Don't support POSIX ACLs.

quota, usrquota			Enable user disk quota support
				(requires CONFIG_QUOTA).

grpquota			Enable group disk quota support
				(requires CONFIG_QUOTA).
====================    ===     ================================================

noquota option ls silently ignored by ext2.

Specification
=============

ext2 shares many properties with traditional Unix filesystems.  It has
the concepts of blocks, inodes and directories.  It has space in the
specification for Access Control Lists (ACLs), fragments, undeletion and
compression though these are not yet implemented (some are available as
separate patches).  There is also a versioning mechanism to allow new
features (such as journalling) to be added in a maximally compatible
manner.

Blocks
------

The space in the device or file is split up into blocks.  These are
a fixed size, of 1024, 2048 or 4096 bytes (8192 bytes on Alpha systems),
which is decided when the filesystem is created.  Smaller blocks mean
less wasted space per file, but require slightly more accounting overhead,
and also impose other limits on the size of files and the filesystem.

Block Groups
------------

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.

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.

The Superblock
--------------

The superblock contains all the information about the configuration of
the filing system.  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.
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.

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 (see the Revisions section below)
and which OS created it.

If the filesystem is revision 1 or higher, then there are extra fields,
such as a volume name, a unique identification number, the inode size,
and space for optional filesystem features to store configuration info.

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.

Inodes
------

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).

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 more bits.

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).

The flags field contains some ext2-specific flags which aren't catered
for by the standard chmod flags.  These flags can be listed with lsattr
and changed with the chattr command, and allow 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.  Not all
of these are supported yet.

Directories
-----------

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
(support for taking advantage of this feature does not yet exist in
Glibc 2.2).

The inode allocation code tries to assign inodes which are in the same
block group as the directory in which they are first created.

The current implementation of ext2 uses a singly-linked list to store
the filenames in the directory; a pending enhancement uses hashing of the
filenames to allow lookup without the need to scan the entire directory.

The current implementation never removes empty directory blocks once they
have been allocated to hold more files.

Special files
-------------

Symbolic links are also filesystem objects with inodes.  They deserve
special mention because the data for them is stored within the inode
itself if the symlink is less than 60 bytes long.  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.

Character and block special devices never have data blocks assigned to
them.  Instead, their device number is stored in the inode, again reusing
the fields which would be used to point to the data blocks.

Reserved Space
--------------

In ext2, there is a mechanism for reserving a certain number of blocks
for a particular user (normally the super-user).  This is intended to
allow for the system to continue functioning even if non-privileged users
fill up all the space available to them (this is independent of filesystem
quotas).  It also keeps the filesystem from filling up entirely which
helps combat fragmentation.

Filesystem check
----------------

At boot time, most systems run a consistency check (e2fsck) on their
filesystems.  The superblock of the ext2 filesystem contains several
fields which indicate whether fsck should actually run (since checking
the filesystem at boot can take a long time if it is large).  fsck will
run if the filesystem was not cleanly unmounted, if the maximum mount
count has been exceeded or if the maximum time between checks has been
exceeded.

Feature Compatibility
---------------------

The compatibility feature mechanism used in ext2 is sophisticated.
It safely allows features to be added to the filesystem, without
unnecessarily sacrificing compatibility with older versions of the
filesystem code.  The feature compatibility mechanism is not supported by
the original revision 0 (EXT2_GOOD_OLD_REV) of ext2, but was introduced in
revision 1.  There are three 32-bit fields, one for compatible features
(COMPAT), one for read-only compatible (RO_COMPAT) features and one for
incompatible (INCOMPAT) features.

These feature flags have specific meanings for the kernel as follows:

A COMPAT flag indicates that a feature is present in the filesystem,
but the on-disk format is 100% compatible with older on-disk formats, so
a kernel which didn't know anything about this feature could read/write
the filesystem without any chance of corrupting the filesystem (or even
making it inconsistent).  This is essentially just a flag which says
"this filesystem has a (hidden) feature" that the kernel or e2fsck may
want to be aware of (more on e2fsck and feature flags later).  The ext3
HAS_JOURNAL feature is a COMPAT flag because the ext3 journal is simply
a regular file with data blocks in it so the kernel does not need to
take any special notice of it if it doesn't understand ext3 journaling.

An RO_COMPAT flag indicates that the on-disk format is 100% compatible
with older on-disk formats for reading (i.e. the feature does not change
the visible on-disk format).  However, an old kernel writing to such a
filesystem would/could corrupt the filesystem, so this is prevented. The
most common such feature, SPARSE_SUPER, is an RO_COMPAT feature because
sparse groups allow file data blocks where superblock/group descriptor
backups used to live, and ext2_free_blocks() refuses to free these blocks,
which would leading to inconsistent bitmaps.  An old kernel would also
get an error if it tried to free a series of blocks which crossed a group
boundary, but this is a legitimate layout in a SPARSE_SUPER filesystem.

An INCOMPAT flag indicates the on-disk format has changed in some
way that makes it unreadable by older kernels, or would otherwise
cause a problem if an old kernel tried to mount it.  FILETYPE is an
INCOMPAT flag because older kernels would think a filename was longer
than 256 characters, which would lead to corrupt directory listings.
The COMPRESSION flag is an obvious INCOMPAT flag - if the kernel
doesn't understand compression, you would just get garbage back from
read() instead of it automatically decompressing your data.  The ext3
RECOVER flag is needed to prevent a kernel which does not understand the
ext3 journal from mounting the filesystem without replaying the journal.

For e2fsck, it needs to be more strict with the handling of these
flags than the kernel.  If it doesn't understand ANY of the COMPAT,
RO_COMPAT, or INCOMPAT flags it will refuse to check the filesystem,
because it has no way of verifying whether a given feature is valid
or not.  Allowing e2fsck to succeed on a filesystem with an unknown
feature is a false sense of security for the user.  Refusing to check
a filesystem with unknown features is a good incentive for the user to
update to the latest e2fsck.  This also means that anyone adding feature
flags to ext2 also needs to update e2fsck to verify these features.

Metadata
--------

It is frequently claimed that the ext2 implementation of writing
asynchronous metadata is faster than the ffs synchronous metadata
scheme but less reliable.  Both methods are equally resolvable by their
respective fsck programs.

If you're exceptionally paranoid, there are 3 ways of making metadata
writes synchronous on ext2:

- per-file if you have the program source: use the O_SYNC flag to open()
- per-file if you don't have the source: use "chattr +S" on the file
- per-filesystem: add the "sync" option to mount (or in /etc/fstab)

the first and last are not ext2 specific but do force the metadata to
be written synchronously.  See also Journaling below.

Limitations
-----------

There are various limits imposed by the on-disk layout of ext2.  Other
limits are imposed by the current implementation of the kernel code.
Many of the limits are determined at the time the filesystem is first
created, and depend upon the block size chosen.  The ratio of inodes to
data blocks is fixed at filesystem creation time, so the only way to
increase the number of inodes is to increase the size of the filesystem.
No tools currently exist which can change the ratio of inodes to blocks.

Most of these limits could be overcome with slight changes in the on-disk
format and using a compatibility flag to signal the format change (at
the expense of some compatibility).

=====================  =======    =======    =======   ========
Filesystem block size      1kB        2kB        4kB        8kB
=====================  =======    =======    =======   ========
File size limit           16GB      256GB     2048GB     2048GB
Filesystem size limit   2047GB     8192GB    16384GB    32768GB
=====================  =======    =======    =======   ========

There is a 2.4 kernel limit of 2048GB for a single block device, so no
filesystem larger than that can be created at this time.  There is also
an upper limit on the block size imposed by the page size of the kernel,
so 8kB blocks are only allowed on Alpha systems (and other architectures
which support larger pages).

There is an upper limit of 32000 subdirectories in a single directory.

There is a "soft" upper limit of about 10-15k files in a single directory
with the current linear linked-list directory implementation.  This limit
stems from performance problems when creating and deleting (and also
finding) files in such large directories.  Using a hashed directory index
(under development) allows 100k-1M+ files in a single directory without
performance problems (although RAM size becomes an issue at this point).

The (meaningless) absolute upper limit of files in a single directory
(imposed by the file size, the realistic limit is obviously much less)
is over 130 trillion files.  It would be higher except there are not
enough 4-character names to make up unique directory entries, so they
have to be 8 character filenames, even then we are fairly close to
running out of unique filenames.

Journaling
----------

A journaling extension to the ext2 code has been developed by Stephen
Tweedie.  It avoids the risks of metadata corruption and the need to
wait for e2fsck to complete after a crash, without requiring a change
to the on-disk ext2 layout.  In a nutshell, the journal is a regular
file which stores whole metadata (and optionally data) blocks that have
been modified, prior to writing them into the filesystem.  This means
it is possible to add a journal to an existing ext2 filesystem without
the need for data conversion.

When changes to the filesystem (e.g. a file is renamed) they are stored in
a transaction in the journal and can either be complete or incomplete at
the time of a crash.  If a transaction is complete at the time of a crash
(or in the normal case where the system does not crash), then any blocks
in that transaction are guaranteed to represent a valid filesystem state,
and are copied into the filesystem.  If a transaction is incomplete at
the time of the crash, then there is no guarantee of consistency for
the blocks in that transaction so they are discarded (which means any
filesystem changes they represent are also lost).
Check Documentation/filesystems/ext4/ if you want to read more about
ext4 and journaling.

References
==========

=======================	===============================================
The kernel source	file:/usr/src/linux/fs/ext2/
e2fsprogs (e2fsck)	http://e2fsprogs.sourceforge.net/
Design & Implementation	http://e2fsprogs.sourceforge.net/ext2intro.html
Journaling (ext3)	ftp://ftp.uk.linux.org/pub/linux/sct/fs/jfs/
Filesystem Resizing	http://ext2resize.sourceforge.net/
Compression [1]_	http://e2compr.sourceforge.net/
=======================	===============================================

Implementations for:

=======================	===========================================================
Windows 95/98/NT/2000	http://www.chrysocome.net/explore2fs
Windows 95 [1]_		http://www.yipton.net/content.html#FSDEXT2
DOS client [1]_		ftp://metalab.unc.edu/pub/Linux/system/filesystems/ext2/
OS/2 [2]_		ftp://metalab.unc.edu/pub/Linux/system/filesystems/ext2/
RISC OS client		http://www.esw-heim.tu-clausthal.de/~marco/smorbrod/IscaFS/
=======================	===========================================================

.. [1] no longer actively developed/supported (as of Apr 2001)
.. [2] no longer actively developed/supported (as of Mar 2009)


code:
.. SPDX-License-Identifier: GPL-2.0

===============
Ext3 Filesystem
===============

Ext3 was originally released in September 1999. Written by Stephen Tweedie
for the 2.2 branch, and ported to 2.4 kernels by Peter Braam, Andreas Dilger,
Andrew Morton, Alexander Viro, Ted Ts'o and Stephen Tweedie.

Ext3 is the ext2 filesystem enhanced with journalling capabilities. The
filesystem is a subset of ext4 filesystem so use ext4 driver for accessing
ext3 filesystems.


code:
.. SPDX-License-Identifier: GPL-2.0

About this Book
===============

This document attempts to describe the on-disk format for ext4
filesystems. The same general ideas should apply to ext2/3 filesystems
as well, though they do not support all the features that ext4 supports,
and the fields will be shorter.

**NOTE**: This is a work in progress, based on notes that the author
(djwong) made while picking apart a filesystem by hand. The data
structure definitions should be current as of Linux 4.18 and
e2fsprogs-1.44. All comments and corrections are welcome, since there is
undoubtedly plenty of lore that might not be reflected in freshly
created demonstration filesystems.

License
-------
This book is licensed under the terms of the GNU Public License, v2.

Terminology
-----------

ext4 divides a storage device into an array of logical blocks both to
reduce bookkeeping overhead and to increase throughput by forcing larger
transfer sizes. Generally, the block size will be 4KiB (the same size as
pages on x86 and the block layer's default block size), though the
actual size is calculated as 2 ^ (10 + ``sb.s_log_block_size``) bytes.
Throughout this document, disk locations are given in terms of these
logical blocks, not raw LBAs, and not 1024-byte blocks. For the sake of
convenience, the logical block size will be referred to as
``$block_size`` throughout the rest of the document.

When referenced in ``preformatted text`` blocks, ``sb`` refers to fields
in the super block, and ``inode`` refers to fields in an inode table
entry.

Other References
----------------

Also see https://www.nongnu.org/ext2-doc/ for quite a collection of
information about ext2/3. Here's another old reference:
http://wiki.osdev.org/Ext2


code:
.. SPDX-License-Identifier: GPL-2.0

Block and Inode Allocation Policy
---------------------------------

ext4 recognizes (better than ext3, anyway) that data locality is
generally a desirably quality of a filesystem. On a spinning disk,
keeping related blocks near each other reduces the amount of movement
that the head actuator and disk must perform to access a data block,
thus speeding up disk IO. On an SSD there of course are no moving parts,
but locality can increase the size of each transfer request while
reducing the total number of requests. This locality may also have the
effect of concentrating writes on a single erase block, which can speed
up file rewrites significantly. Therefore, it is useful to reduce
fragmentation whenever possible.

The first tool that ext4 uses to combat fragmentation is the multi-block
allocator. When a file is first created, the block allocator
speculatively allocates 8KiB of disk space to the file on the assumption
that the space will get written soon. When the file is closed, the
unused speculative allocations are of course freed, but if the
speculation is correct (typically the case for full writes of small
files) then the file data gets written out in a single multi-block
extent. A second related trick that ext4 uses is delayed allocation.
Under this scheme, when a file needs more blocks to absorb file writes,
the filesystem defers deciding the exact placement on the disk until all
the dirty buffers are being written out to disk. By not committing to a
particular placement until it's absolutely necessary (the commit timeout
is hit, or sync() is called, or the kernel runs out of memory), the hope
is that the filesystem can make better location decisions.

The third trick that ext4 (and ext3) uses is that it tries to keep a
file's data blocks in the same block group as its inode. This cuts down
on the seek penalty when the filesystem first has to read a file's inode
to learn where the file's data blocks live and then seek over to the
file's data blocks to begin I/O operations.

The fourth trick is that all the inodes in a directory are placed in the
same block group as the directory, when feasible. The working assumption
here is that all the files in a directory might be related, therefore it
is useful to try to keep them all together.

The fifth trick is that the disk volume is cut up into 128MB block
groups; these mini-containers are used as outlined above to try to
maintain data locality. However, there is a deliberate quirk -- when a
directory is created in the root directory, the inode allocator scans
the block groups and puts that directory into the least heavily loaded
block group that it can find. This encourages directories to spread out
over a disk; as the top-level directory/file blobs fill up one block
group, the allocators simply move on to the next block group. Allegedly
this scheme evens out the loading on the block groups, though the author
suspects that the directories which are so unlucky as to land towards
the end of a spinning drive get a raw deal performance-wise.

Of course if all of these mechanisms fail, one can always use e4defrag
to defragment files.


code:
.. SPDX-License-Identifier: GPL-2.0

Extended Attributes
-------------------

Extended attributes (xattrs) are typically stored in a separate data
block on the disk and referenced from inodes via ``inode.i_file_acl*``.
The first use of extended attributes seems to have been for storing file
ACLs and other security data (selinux). With the ``user_xattr`` mount
option it is possible for users to store extended attributes so long as
all attribute names begin with “user”; this restriction seems to have
disappeared as of Linux 3.0.

There are two places where extended attributes can be found. The first
place is between the end of each inode entry and the beginning of the
next inode entry. For example, if inode.i_extra_isize = 28 and
sb.inode_size = 256, then there are 256 - (128 + 28) = 100 bytes
available for in-inode extended attribute storage. The second place
where extended attributes can be found is in the block pointed to by
``inode.i_file_acl``. As of Linux 3.11, it is not possible for this
block to contain a pointer to a second extended attribute block (or even
the remaining blocks of a cluster). In theory it is possible for each
attribute's value to be stored in a separate data block, though as of
Linux 3.11 the code does not permit this.

Keys are generally assumed to be ASCIIZ strings, whereas values can be
strings or binary data.

Extended attributes, when stored after the inode, have a header
``ext4_xattr_ibody_header`` that is 4 bytes long:

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

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - __le32
     - h_magic
     - Magic number for identification, 0xEA020000. This value is set by the
       Linux driver, though e2fsprogs doesn't seem to check it(?)

The beginning of an extended attribute block is in
``struct ext4_xattr_header``, which is 32 bytes long:

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

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - __le32
     - h_magic
     - Magic number for identification, 0xEA020000.
   * - 0x4
     - __le32
     - h_refcount
     - Reference count.
   * - 0x8
     - __le32
     - h_blocks
     - Number of disk blocks used.
   * - 0xC
     - __le32
     - h_hash
     - Hash value of all attributes.
   * - 0x10
     - __le32
     - h_checksum
     - Checksum of the extended attribute block.
   * - 0x14
     - __u32
     - h_reserved[3]
     - Zero.

The checksum is calculated against the FS UUID, the 64-bit block number
of the extended attribute block, and the entire block (header +
entries).

Following the ``struct ext4_xattr_header`` or
``struct ext4_xattr_ibody_header`` is an array of
``struct ext4_xattr_entry``; each of these entries is at least 16 bytes
long. When stored in an external block, the ``struct ext4_xattr_entry``
entries must be stored in sorted order. The sort order is
``e_name_index``, then ``e_name_len``, and finally ``e_name``.
Attributes stored inside an inode do not need be stored in sorted order.

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

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - __u8
     - e_name_len
     - Length of name.
   * - 0x1
     - __u8
     - e_name_index
     - Attribute name index. There is a discussion of this below.
   * - 0x2
     - __le16
     - e_value_offs
     - Location of this attribute's value on the disk block where it is stored.
       Multiple attributes can share the same value. For an inode attribute
       this value is relative to the start of the first entry; for a block this
       value is relative to the start of the block (i.e. the header).
   * - 0x4
     - __le32
     - e_value_inum
     - The inode where the value is stored. Zero indicates the value is in the
       same block as this entry. This field is only used if the
       INCOMPAT_EA_INODE feature is enabled.
   * - 0x8
     - __le32
     - e_value_size
     - Length of attribute value.
   * - 0xC
     - __le32
     - e_hash
     - Hash value of attribute name and attribute value. The kernel doesn't
       update the hash for in-inode attributes, so for that case this value
       must be zero, because e2fsck validates any non-zero hash regardless of
       where the xattr lives.
   * - 0x10
     - char
     - e_name[e_name_len]
     - Attribute name. Does not include trailing NULL.

Attribute values can follow the end of the entry table. There appears to
be a requirement that they be aligned to 4-byte boundaries. The values
are stored starting at the end of the block and grow towards the
xattr_header/xattr_entry table. When the two collide, the overflow is
put into a separate disk block. If the disk block fills up, the
filesystem returns -ENOSPC.

The first four fields of the ``ext4_xattr_entry`` are set to zero to
mark the end of the key list.

Attribute Name Indices
~~~~~~~~~~~~~~~~~~~~~~

Logically speaking, extended attributes are a series of key=value pairs.
The keys are assumed to be NULL-terminated strings. To reduce the amount
of on-disk space that the keys consume, the beginning of the key string
is matched against the attribute name index. If a match is found, the
attribute name index field is set, and matching string is removed from
the key name. Here is a map of name index values to key prefixes:

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

   * - Name Index
     - Key Prefix
   * - 0
     - (no prefix)
   * - 1
     - “user.”
   * - 2
     - “system.posix_acl_access”
   * - 3
     - “system.posix_acl_default”
   * - 4
     - “trusted.”
   * - 6
     - “security.”
   * - 7
     - “system.” (inline_data only?)
   * - 8
     - “system.richacl” (SuSE kernels only?)

For example, if the attribute key is “user.fubar”, the attribute name
index is set to 1 and the “fubar” name is recorded on disk.

POSIX ACLs
~~~~~~~~~~

POSIX ACLs are stored in a reduced version of the Linux kernel (and
libacl's) internal ACL format. The key difference is that the version
number is different (1) and the ``e_id`` field is only stored for named
user and group ACLs.


code:
.. SPDX-License-Identifier: GPL-2.0

Bigalloc
--------

At the moment, the default size of a block is 4KiB, which is a commonly
supported page size on most MMU-capable hardware. This is fortunate, as
ext4 code is not prepared to handle the case where the block size
exceeds the page size. However, for a filesystem of mostly huge files,
it is desirable to be able to allocate disk blocks in units of multiple
blocks to reduce both fragmentation and metadata overhead. The
bigalloc feature provides exactly this ability.

The bigalloc feature (EXT4_FEATURE_RO_COMPAT_BIGALLOC) changes ext4 to
use clustered allocation, so that each bit in the ext4 block allocation
bitmap addresses a power of two number of blocks. For example, if the
file system is mainly going to be storing large files in the 4-32
megabyte range, it might make sense to set a cluster size of 1 megabyte.
This means that each bit in the block allocation bitmap now addresses
256 4k blocks. This shrinks the total size of the block allocation
bitmaps for a 2T file system from 64 megabytes to 256 kilobytes. It also
means that a block group addresses 32 gigabytes instead of 128 megabytes,
also shrinking the amount of file system overhead for metadata.

The administrator can set a block cluster size at mkfs time (which is
stored in the s_log_cluster_size field in the superblock); from then
on, the block bitmaps track clusters, not individual blocks. This means
that block groups can be several gigabytes in size (instead of just
128MiB); however, the minimum allocation unit becomes a cluster, not a
block, even for directories. TaoBao had a patchset to extend the “use
units of clusters instead of blocks” to the extent tree, though it is
not clear where those patches went-- they eventually morphed into
“extent tree v2” but that code has not landed as of May 2015.


code:
.. SPDX-License-Identifier: GPL-2.0

Block and inode Bitmaps
-----------------------

The data block bitmap tracks the usage of data blocks within the block
group.

The inode bitmap records which entries in the inode table are in use.

As with most bitmaps, one bit represents the usage status of one data
block or inode table entry. This implies a block group size of 8 *
number_of_bytes_in_a_logical_block.

NOTE: If ``BLOCK_UNINIT`` is set for a given block group, various parts
of the kernel and e2fsprogs code pretends that the block bitmap contains
zeros (i.e. all blocks in the group are free). However, it is not
necessarily the case that no blocks are in use -- if ``meta_bg`` is set,
the bitmaps and group descriptor live inside the group. Unfortunately,
ext2fs_test_block_bitmap2() will return '0' for those locations,
which produces confusing debugfs output.

Inode Table
-----------
Inode tables are statically allocated at mkfs time.  Each block group
descriptor points to the start of the table, and the superblock records
the number of inodes per group.  See the section on inodes for more
information.


code:
.. SPDX-License-Identifier: GPL-2.0

Layout
------

The layout of a standard block group is approximately as follows (each
of these fields is discussed in a separate section below):

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

   * - Group 0 Padding
     - ext4 Super Block
     - Group Descriptors
     - Reserved GDT Blocks
     - Data Block Bitmap
     - inode Bitmap
     - inode Table
     - Data Blocks
   * - 1024 bytes
     - 1 block
     - many blocks
     - many blocks
     - 1 block
     - 1 block
     - many blocks
     - many more blocks

For the special case of block group 0, the first 1024 bytes are unused,
to allow for the installation of x86 boot sectors and other oddities.
The superblock will start at offset 1024 bytes, whichever block that
happens to be (usually 0). However, if for some reason the block size =
1024, then block 0 is marked in use and the superblock goes in block 1.
For all other block groups, there is no padding.

The ext4 driver primarily works with the superblock and the group
descriptors that are found in block group 0. Redundant copies of the
superblock and group descriptors are written to some of the block groups
across the disk in case the beginning of the disk gets trashed, though
not all block groups necessarily host a redundant copy (see following
paragraph for more details). If the group does not have a redundant
copy, the block group begins with the data block bitmap. Note also that
when the filesystem is freshly formatted, mkfs will allocate “reserve
GDT block” space after the block group descriptors and before the start
of the block bitmaps to allow for future expansion of the filesystem. By
default, a filesystem is allowed to increase in size by a factor of
1024x over the original filesystem size.

The location of the inode table is given by ``grp.bg_inode_table_*``. It
is continuous range of blocks large enough to contain
``sb.s_inodes_per_group * sb.s_inode_size`` bytes.

As for the ordering of items in a block group, it is generally
established that the super block and the group descriptor table, if
present, will be at the beginning of the block group. The bitmaps and
the inode table can be anywhere, and it is quite possible for the
bitmaps to come after the inode table, or for both to be in different
groups (flex_bg). Leftover space is used for file data blocks, indirect
block maps, extent tree blocks, and extended attributes.

Flexible Block Groups
---------------------

Starting in ext4, there is a new feature called flexible block groups
(flex_bg). In a flex_bg, several block groups are tied together as one
logical block group; the bitmap spaces and the inode table space in the
first block group of the flex_bg are expanded to include the bitmaps
and inode tables of all other block groups in the flex_bg. For example,
if the flex_bg size is 4, then group 0 will contain (in order) the
superblock, group descriptors, data block bitmaps for groups 0-3, inode
bitmaps for groups 0-3, inode tables for groups 0-3, and the remaining
space in group 0 is for file data. The effect of this is to group the
block group metadata close together for faster loading, and to enable
large files to be continuous on disk. Backup copies of the superblock
and group descriptors are always at the beginning of block groups, even
if flex_bg is enabled. The number of block groups that make up a
flex_bg is given by 2 ^ ``sb.s_log_groups_per_flex``.

Meta Block Groups
-----------------

Without the option META_BG, for safety concerns, all block group
descriptors copies are kept in the first block group. Given the default
128MiB(2^27 bytes) block group size and 64-byte group descriptors, ext4
can have at most 2^27/64 = 2^21 block groups. This limits the entire
filesystem size to 2^21 * 2^27 = 2^48bytes or 256TiB.

The solution to this problem is to use the metablock group feature
(META_BG), which is already in ext3 for all 2.6 releases. With the
META_BG feature, ext4 filesystems are partitioned into many metablock
groups. Each metablock group is a cluster of block groups whose group
descriptor structures can be stored in a single disk block. For ext4
filesystems with 4 KB block size, a single metablock group partition
includes 64 block groups, or 8 GiB of disk space. The metablock group
feature moves the location of the group descriptors from the congested
first block group of the whole filesystem into the first group of each
metablock group itself. The backups are in the second and last group of
each metablock group. This increases the 2^21 maximum block groups limit
to the hard limit 2^32, allowing support for a 512PiB filesystem.

The change in the filesystem format replaces the current scheme where
the superblock is followed by a variable-length set of block group
descriptors. Instead, the superblock and a single block group descriptor
block is placed at the beginning of the first, second, and last block
groups in a meta-block group. A meta-block group is a collection of
block groups which can be described by a single block group descriptor
block. Since the size of the block group descriptor structure is 32
bytes, a meta-block group contains 32 block groups for filesystems with
a 1KB block size, and 128 block groups for filesystems with a 4KB
blocksize. Filesystems can either be created using this new block group
descriptor layout, or existing filesystems can be resized on-line, and
the field s_first_meta_bg in the superblock will indicate the first
block group using this new layout.

Please see an important note about ``BLOCK_UNINIT`` in the section about
block and inode bitmaps.

Lazy Block Group Initialization
-------------------------------

A new feature for ext4 are three block group descriptor flags that
enable mkfs to skip initializing other parts of the block group
metadata. Specifically, the INODE_UNINIT and BLOCK_UNINIT flags mean
that the inode and block bitmaps for that group can be calculated and
therefore the on-disk bitmap blocks are not initialized. This is
generally the case for an empty block group or a block group containing
only fixed-location block group metadata. The INODE_ZEROED flag means
that the inode table has been initialized; mkfs will unset this flag and
rely on the kernel to initialize the inode tables in the background.

By not writing zeroes to the bitmaps and inode table, mkfs time is
reduced considerably. Note the feature flag is RO_COMPAT_GDT_CSUM,
but the dumpe2fs output prints this as “uninit_bg”. They are the same
thing.


code:
.. SPDX-License-Identifier: GPL-2.0

Blocks
------

ext4 allocates storage space in units of “blocks”. A block is a group of
sectors between 1KiB and 64KiB, and the number of sectors must be an
integral power of 2. Blocks are in turn grouped into larger units called
block groups. Block size is specified at mkfs time and typically is
4KiB. You may experience mounting problems if block size is greater than
page size (i.e. 64KiB blocks on a i386 which only has 4KiB memory
pages). By default a filesystem can contain 2^32 blocks; if the '64bit'
feature is enabled, then a filesystem can have 2^64 blocks. The location
of structures is stored in terms of the block number the structure lives
in and not the absolute offset on disk.

For 32-bit filesystems, limits are as follows:

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

   * - Item
     - 1KiB
     - 2KiB
     - 4KiB
     - 64KiB
   * - Blocks
     - 2^32
     - 2^32
     - 2^32
     - 2^32
   * - Inodes
     - 2^32
     - 2^32
     - 2^32
     - 2^32
   * - File System Size
     - 4TiB
     - 8TiB
     - 16TiB
     - 256TiB
   * - Blocks Per Block Group
     - 8,192
     - 16,384
     - 32,768
     - 524,288
   * - Inodes Per Block Group
     - 8,192
     - 16,384
     - 32,768
     - 524,288
   * - Block Group Size
     - 8MiB
     - 32MiB
     - 128MiB
     - 32GiB
   * - Blocks Per File, Extents
     - 2^32
     - 2^32
     - 2^32
     - 2^32
   * - Blocks Per File, Block Maps
     - 16,843,020
     - 134,480,396
     - 1,074,791,436
     - 4,398,314,962,956 (really 2^32 due to field size limitations)
   * - File Size, Extents
     - 4TiB
     - 8TiB
     - 16TiB
     - 256TiB
   * - File Size, Block Maps
     - 16GiB
     - 256GiB
     - 4TiB
     - 256TiB

For 64-bit filesystems, limits are as follows:

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

   * - Item
     - 1KiB
     - 2KiB
     - 4KiB
     - 64KiB
   * - Blocks
     - 2^64
     - 2^64
     - 2^64
     - 2^64
   * - Inodes
     - 2^32
     - 2^32
     - 2^32
     - 2^32
   * - File System Size
     - 16ZiB
     - 32ZiB
     - 64ZiB
     - 1YiB
   * - Blocks Per Block Group
     - 8,192
     - 16,384
     - 32,768
     - 524,288
   * - Inodes Per Block Group
     - 8,192
     - 16,384
     - 32,768
     - 524,288
   * - Block Group Size
     - 8MiB
     - 32MiB
     - 128MiB
     - 32GiB
   * - Blocks Per File, Extents
     - 2^32
     - 2^32
     - 2^32
     - 2^32
   * - Blocks Per File, Block Maps
     - 16,843,020
     - 134,480,396
     - 1,074,791,436
     - 4,398,314,962,956 (really 2^32 due to field size limitations)
   * - File Size, Extents
     - 4TiB
     - 8TiB
     - 16TiB
     - 256TiB
   * - File Size, Block Maps
     - 16GiB
     - 256GiB
     - 4TiB
     - 256TiB

Note: Files not using extents (i.e. files using block maps) must be
placed within the first 2^32 blocks of a filesystem. Files with extents
must be placed within the first 2^48 blocks of a filesystem. It's not
clear what happens with larger filesystems.


code:
.. SPDX-License-Identifier: GPL-2.0

Checksums
---------

Starting in early 2012, metadata checksums were added to all major ext4
and jbd2 data structures. The associated feature flag is metadata_csum.
The desired checksum algorithm is indicated in the superblock, though as
of October 2012 the only supported algorithm is crc32c. Some data
structures did not have space to fit a full 32-bit checksum, so only the
lower 16 bits are stored. Enabling the 64bit feature increases the data
structure size so that full 32-bit checksums can be stored for many data
structures. However, existing 32-bit filesystems cannot be extended to
enable 64bit mode, at least not without the experimental resize2fs
patches to do so.

Existing filesystems can have checksumming added by running
``tune2fs -O metadata_csum`` against the underlying device. If tune2fs
encounters directory blocks that lack sufficient empty space to add a
checksum, it will request that you run ``e2fsck -D`` to have the
directories rebuilt with checksums. This has the added benefit of
removing slack space from the directory files and rebalancing the htree
indexes. If you _ignore_ this step, your directories will not be
protected by a checksum!

The following table describes the data elements that go into each type
of checksum. The checksum function is whatever the superblock describes
(crc32c as of October 2013) unless noted otherwise.

.. list-table::
   :widths: 20 8 50
   :header-rows: 1

   * - Metadata
     - Length
     - Ingredients
   * - Superblock
     - __le32
     - The entire superblock up to the checksum field. The UUID lives inside
       the superblock.
   * - MMP
     - __le32
     - UUID + the entire MMP block up to the checksum field.
   * - Extended Attributes
     - __le32
     - UUID + the entire extended attribute block. The checksum field is set to
       zero.
   * - Directory Entries
     - __le32
     - UUID + inode number + inode generation + the directory block up to the
       fake entry enclosing the checksum field.
   * - HTREE Nodes
     - __le32
     - UUID + inode number + inode generation + all valid extents + HTREE tail.
       The checksum field is set to zero.
   * - Extents
     - __le32
     - UUID + inode number + inode generation + the entire extent block up to
       the checksum field.
   * - Bitmaps
     - __le32 or __le16
     - UUID + the entire bitmap. Checksums are stored in the group descriptor,
       and truncated if the group descriptor size is 32 bytes (i.e. ^64bit)
   * - Inodes
     - __le32
     - UUID + inode number + inode generation + the entire inode. The checksum
       field is set to zero. Each inode has its own checksum.
   * - Group Descriptors
     - __le16
     - If metadata_csum, then UUID + group number + the entire descriptor;
       else if gdt_csum, then crc16(UUID + group number + the entire
       descriptor). In all cases, only the lower 16 bits are stored.


code:
.. SPDX-License-Identifier: GPL-2.0

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

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

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

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

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

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

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

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

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

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

.. _ftype:

The directory file type is one of the following values:

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

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

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

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

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

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

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

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

The leaf directory block checksum is calculated against the FS UUID, the
directory's inode number, the directory's inode generation number, and
the entire directory entry block up to (but not including) the fake
directory entry.

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

A linear array of directory entries isn't great for performance, so a
new feature was added to ext3 to provide a faster (but peculiar)
balanced tree keyed off a hash of the directory entry name. If the
EXT4_INDEX_FL (0x1000) flag is set in the inode, this directory uses a
hashed btree (htree) to organize and find directory entries. For
backwards read-only compatibility with ext2, this tree is actually
hidden inside the directory file, masquerading as “empty” directory data
blocks! It was stated previously that the end of the linear directory
entry table was signified with an entry pointing to inode 0; this is
(ab)used to fool the old linear-scan algorithm into thinking that the
rest of the directory block is empty so that it moves on.

The root of the tree always lives in the first data block of the
directory. By ext2 custom, the '.' and '..' entries must appear at the
beginning of this first block, so they are put here as two
``struct ext4_dir_entry_2`` s and not stored in the tree. The rest of
the root node contains metadata about the tree and finally a hash->block
map to find nodes that are lower in the htree. If
``dx_root.info.indirect_levels`` is non-zero then the htree has two
levels; the data block pointed to by the root node's map is an interior
node, which is indexed by a minor hash. Interior nodes in this tree
contains a zeroed out ``struct ext4_dir_entry_2`` followed by a
minor_hash->block map to find leafe nodes. Leaf nodes contain a linear
array of all ``struct ext4_dir_entry_2``; all of these entries
(presumably) hash to the same value. If there is an overflow, the
entries simply overflow into the next leaf node, and the
least-significant bit of the hash (in the interior node map) that gets
us to this next leaf node is set.

To traverse the directory as a htree, the code calculates the hash of
the desired file name and uses it to find the corresponding block
number. If the tree is flat, the block is a linear array of directory
entries that can be searched; otherwise, the minor hash of the file name
is computed and used against this second block to find the corresponding
third block number. That third block number will be a linear array of
directory entries.

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

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

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

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

.. _dirhash:

The directory hash is one of the following values:

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

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

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

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

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

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

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

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

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

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

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

   * - Offset
     - Type
     - Name
     - Description
   * - 0x0
     - u32
     - dt_reserved
     - Zero.
   * - 0x4
     - __le32
     - dt_checksum
     - Checksum of the htree directory block.

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


code:
.. SPDX-License-Identifier: GPL-2.0

Dynamic Structures
==================

Dynamic metadata are created on the fly when files and blocks are
allocated to files.

.. include:: inodes.rst
.. include:: ifork.rst
.. include:: directory.rst
.. include:: attributes.rst


code:
.. SPDX-License-Identifier: GPL-2.0

Large Extended Attribute Values
-------------------------------

To enable ext4 to store extended attribute values that do not fit in the
inode or in the single extended attribute block attached to an inode,
the EA_INODE feature allows us to store the value in the data blocks of
a regular file inode. This “EA inode” is linked only from the extended
attribute name index and must not appear in a directory entry. The
inode's i_atime field is used to store a checksum of the xattr value;
and i_ctime/i_version store a 64-bit reference count, which enables
sharing of large xattr values between multiple owning inodes. For
backward compatibility with older versions of this feature, the
i_mtime/i_generation *may* store a back-reference to the inode number
and i_generation of the **one** owning inode (in cases where the EA
inode is not referenced by multiple inodes) to verify that the EA inode
is the correct one being accessed.


code:
.. SPDX-License-Identifier: GPL-2.0

Global Structures
=================

The filesystem is sharded into a number of block groups, each of which
have static metadata at fixed locations.

.. include:: super.rst
.. include:: group_descr.rst
.. include:: bitmaps.rst
.. include:: mmp.rst
.. include:: journal.rst
.. include:: orphan.rst


code:
.. SPDX-License-Identifier: GPL-2.0

Block Group Descriptors
-----------------------

Each block group on the filesystem has one of these descriptors
associated with it. As noted in the Layout section above, the group
descriptors (if present) are the second item in the block group. The
standard configuration is for each block group to contain a full copy of
the block group descriptor table unless the sparse_super feature flag
is set.

Notice how the group descriptor records the location of both bitmaps and
the inode table (i.e. they can float). This means that within a block
group, the only data structures with fixed locations are the superblock
and the group descriptor table. The flex_bg mechanism uses this
property to group several block groups into a flex group and lay out all
of the groups' bitmaps and inode tables into one long run in the first
group of the flex group.

If the meta_bg feature flag is set, then several block groups are
grouped together into a meta group. Note that in the meta_bg case,
however, the first and last two block groups within the larger meta
group contain only group descriptors for the groups inside the meta
group.

flex_bg and meta_bg do not appear to be mutually exclusive features.

In ext2, ext3, and ext4 (when the 64bit feature is not enabled), the
block group descriptor was only 32 bytes long and therefore ends at
bg_checksum. On an ext4 filesystem with the 64bit feature enabled, the
block group descriptor expands to at least the 64 bytes described below;
the size is stored in the superblock.

If gdt_csum is set and metadata_csum is not set, the block group
checksum is the crc16 of the FS UUID, the group number, and the group
descriptor structure. If metadata_csum is set, then the block group
checksum is the lower 16 bits of the checksum of the FS UUID, the group
number, and the group descriptor structure. Both block and inode bitmap
checksums are calculated against the FS UUID, the group number, and the
entire bitmap.

The block group descriptor is laid out in ``struct ext4_group_desc``.

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

   * - Offset
     - Size
     - Name
     - Description
   * - 0x0
     - __le32
     - bg_block_bitmap_lo
     - Lower 32-bits of location of block bitmap.
   * - 0x4
     - __le32
     - bg_inode_bitmap_lo
     - Lower 32-bits of location of inode bitmap.
   * - 0x8
     - __le32
     - bg_inode_table_lo
     - Lower 32-bits of location of inode table.
   * - 0xC
     - __le16
     - bg_free_blocks_count_lo
     - Lower 16-bits of free block count.
   * - 0xE
     - __le16
     - bg_free_inodes_count_lo
     - Lower 16-bits of free inode count.
   * - 0x10
     - __le16
     - bg_used_dirs_count_lo
     - Lower 16-bits of directory count.
   * - 0x12
     - __le16
     - bg_flags
     - Block group flags. See the bgflags_ table below.
   * - 0x14
     - __le32
     - bg_exclude_bitmap_lo
     - Lower 32-bits of location of snapshot exclusion bitmap.
   * - 0x18
     - __le16
     - bg_block_bitmap_csum_lo
     - Lower 16-bits of the block bitmap checksum.
   * - 0x1A
     - __le16
     - bg_inode_bitmap_csum_lo
     - Lower 16-bits of the inode bitmap checksum.
   * - 0x1C
     - __le16
     - bg_itable_unused_lo
     - Lower 16-bits of unused inode count. If set, we needn't scan past the
       ``(sb.s_inodes_per_group - gdt.bg_itable_unused)`` th entry in the
       inode table for this group.
   * - 0x1E
     - __le16
     - bg_checksum
     - Group descriptor checksum; crc16(sb_uuid+group_num+bg_desc) if the
       RO_COMPAT_GDT_CSUM feature is set, or
       crc32c(sb_uuid+group_num+bg_desc) & 0xFFFF if the
       RO_COMPAT_METADATA_CSUM feature is set.  The bg_checksum
       field in bg_desc is skipped when calculating crc16 checksum,
       and set to zero if crc32c checksum is used.
   * -
     -
     -
     - These fields only exist if the 64bit feature is enabled and s_desc_size
       > 32.
   * - 0x20
     - __le32
     - bg_block_bitmap_hi
     - Upper 32-bits of location of block bitmap.
   * - 0x24
     - __le32
     - bg_inode_bitmap_hi
     - Upper 32-bits of location of inodes bitmap.
   * - 0x28
     - __le32
     - bg_inode_table_hi
     - Upper 32-bits of location of inodes table.
   * - 0x2C
     - __le16
     - bg_free_blocks_count_hi
     - Upper 16-bits of free block count.
   * - 0x2E
     - __le16
     - bg_free_inodes_count_hi
     - Upper 16-bits of free inode count.
   * - 0x30
     - __le16
     - bg_used_dirs_count_hi
     - Upper 16-bits of directory count.
   * - 0x32
     - __le16
     - bg_itable_unused_hi
     - Upper 16-bits of unused inode count.
   * - 0x34
     - __le32
     - bg_exclude_bitmap_hi
     - Upper 32-bits of location of snapshot exclusion bitmap.
   * - 0x38
     - __le16
     - bg_block_bitmap_csum_hi
     - Upper 16-bits of the block bitmap checksum.
   * - 0x3A
     - __le16
     - bg_inode_bitmap_csum_hi
     - Upper 16-bits of the inode bitmap checksum.
   * - 0x3C
     - __u32
     - bg_reserved
     - Padding to 64 bytes.

.. _bgflags:

Block group flags can be any combination of the following:

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

   * - Value
     - Description
   * - 0x1
     - inode table and bitmap are not initialized (EXT4_BG_INODE_UNINIT).
   * - 0x2
     - block bitmap is not initialized (EXT4_BG_BLOCK_UNINIT).
   * - 0x4
     - inode table is zeroed (EXT4_BG_INODE_ZEROED).