* [PATCH 01/22] docs: add skeleton of XFS Data Structures and Algorithms book
2018-10-04 3:25 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
@ 2018-10-04 3:25 ` Darrick J. Wong
2018-10-04 3:25 ` [PATCH 03/22] docs: add XFS self-describing metadata integrity doc to DS&A book Darrick J. Wong
` (5 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:25 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
From: Darrick J. Wong <darrick.wong@oracle.com>
Start adding the main TOC of the XFS data structures and algorithms
book. We'll add the individual sections in later patches.
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
Documentation/conf.py | 2
.../filesystems/xfs-data-structures/about.rst | 123 ++++++++++++++++++++
.../filesystems/xfs-data-structures/auxiliary.rst | 4 +
.../filesystems/xfs-data-structures/dynamic.rst | 4 +
.../filesystems/xfs-data-structures/globals.rst | 4 +
.../filesystems/xfs-data-structures/index.rst | 15 ++
.../filesystems/xfs-data-structures/overview.rst | 44 +++++++
Documentation/index.rst | 1
8 files changed, 197 insertions(+)
create mode 100644 Documentation/filesystems/xfs-data-structures/about.rst
create mode 100644 Documentation/filesystems/xfs-data-structures/auxiliary.rst
create mode 100644 Documentation/filesystems/xfs-data-structures/dynamic.rst
create mode 100644 Documentation/filesystems/xfs-data-structures/globals.rst
create mode 100644 Documentation/filesystems/xfs-data-structures/index.rst
create mode 100644 Documentation/filesystems/xfs-data-structures/overview.rst
diff --git a/Documentation/conf.py b/Documentation/conf.py
index add6788bbb8c..fbf8f5dce7d9 100644
--- a/Documentation/conf.py
+++ b/Documentation/conf.py
@@ -383,6 +383,8 @@ latex_documents = [
'The kernel development community', 'manual'),
('admin-guide/xfs', 'xfs-admin-guide.tex',
'XFS Administration Guide', 'XFS Community', 'manual'),
+ ('filesystems/xfs-data-structures/index', 'xfs-data-structures.tex',
+ 'XFS Data Structures and Algorithms', 'XFS Community', 'manual'),
('filesystems/index', 'filesystems.tex', 'Linux Filesystems API',
'The kernel development community', 'manual'),
('filesystems/ext4/index', 'ext4.tex', 'ext4 Filesystem',
diff --git a/Documentation/filesystems/xfs-data-structures/about.rst b/Documentation/filesystems/xfs-data-structures/about.rst
new file mode 100644
index 000000000000..7df40b637e2e
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/about.rst
@@ -0,0 +1,123 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+About this Book
+===============
+
+XFS is a high performance filesystem which was designed to maximize
+parallel throughput and to scale up to extremely large 64-bit storage
+systems. Originally developed by SGI in October 1993 for IRIX, XFS can
+handle large files, large filesystems, many inodes, large directories,
+large file attributes, and large allocations. Filesystems are optimized
+for parallel access by splitting the storage device into semi-autonomous
+allocation groups. XFS employs branching trees (B+ trees) to facilitate
+fast searches of large lists; it also uses delayed extent-based
+allocation to improve data contiguity and IO performance.
+
+This document describes the on-disk layout of an XFS filesystem and how
+to use the debugging tools ``xfs_db`` and ``xfs_logprint`` to inspect
+the metadata structures. It also describes how on-disk metadata relates
+to the higher level design goals.
+
+This book’s source code is available in the Linux kernel git tree.
+Feedback should be sent to the XFS mailing list, currently at:
+``linux-xfs@vger.kernel.org``.
+
+ **Note**
+
+ All fields in XFS metadata structures are in big-endian byte order
+ except for log items which are formatted in host order.
+
+Copyright
+---------
+© Copyright 2006 Silicon Graphics Inc. All rights reserved. Permission is
+granted to copy, distribute, and/or modify this document under the terms of the
+Creative Commons Attribution-Share Alike, Version 3.0 or any later version
+published by the Creative Commons Corp. A copy of the license is available at
+http://creativecommons.org/licenses/by-sa/3.0/us/ .
+
+Change Log
+----------
+
+.. list-table::
+ :widths: 8 12 14 46
+ :header-rows: 1
+
+ * - Version
+ - Date
+ - Author
+ - Description
+
+ * - 0.1
+ - 2006
+ - Silicon Graphics, Inc.
+ - Initial Release
+
+ * - 1.0
+ - Fri Jul 03 2009
+ - Ryan Lerch
+ - Publican Conversion
+
+ * - 1.1
+ - March 2010
+ - Eric Sandeen
+ - Community Release
+
+ * - 1.99
+ - February 2014
+ - Dave Chinner
+ - AsciiDoc Conversion
+
+ * - 3.0
+ - October 2015
+ - Darrick J. Wong
+ - Miscellaneous fixes.
+ Add missing field definitions.
+ Add some missing xfs_db examples.
+ Add an overview of XFS.
+ Document the journal format.
+ Document the realtime device.
+
+ * - 3.1
+ - October 2015
+ - Darrick J. Wong
+ - Add v5 fields.
+ Discuss metadata integrity.
+ Document the free inode B+tree.
+ Create an index of magic numbers.
+ Document sparse inodes.
+
+ * - 3.14
+ - January 2016
+ - Darrick J. Wong
+ - Document disk format change testing.
+
+ * - 3.141
+ - June 2016
+ - Darrick J. Wong
+ - Document the reverse-mapping btree.
+ Move the b+tree info to a separate chapter.
+ Discuss overlapping interval b+trees.
+ Discuss new log items for atomic updates.
+ Document the reference-count btree.
+ Discuss block sharing, reflink, & deduplication.
+
+ * - 3.1415
+ - July 2016
+ - Darrick J. Wong
+ - Document the real-time reverse-mapping btree.
+
+ * - 3.14159
+ - June 2017
+ - Darrick J. Wong
+ - Add the metadump file format.
+
+ * - 3.141592
+ - May 2018
+ - Darrick J. Wong
+ - Incorporate Dave Chinner's log design document.
+ Incorporate Dave Chinner's self-describing metadata design document.
+
+ * - 4.20
+ - September 2018
+ - Darrick J. Wong
+ - Convert to RestructuredText and move to the kernel source tree.
diff --git a/Documentation/filesystems/xfs-data-structures/auxiliary.rst b/Documentation/filesystems/xfs-data-structures/auxiliary.rst
new file mode 100644
index 000000000000..d2fd2f88ad0e
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/auxiliary.rst
@@ -0,0 +1,4 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Auxiliary Data Structures
+=========================
diff --git a/Documentation/filesystems/xfs-data-structures/dynamic.rst b/Documentation/filesystems/xfs-data-structures/dynamic.rst
new file mode 100644
index 000000000000..895c94e95889
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/dynamic.rst
@@ -0,0 +1,4 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Dynamic Allocated Structures
+============================
diff --git a/Documentation/filesystems/xfs-data-structures/globals.rst b/Documentation/filesystems/xfs-data-structures/globals.rst
new file mode 100644
index 000000000000..3499e0fcd4a8
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/globals.rst
@@ -0,0 +1,4 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Global Structures
+=================
diff --git a/Documentation/filesystems/xfs-data-structures/index.rst b/Documentation/filesystems/xfs-data-structures/index.rst
new file mode 100644
index 000000000000..bd164f62c387
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/index.rst
@@ -0,0 +1,15 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+==================================
+XFS Data Structures and Algorithms
+==================================
+
+.. toctree::
+ :maxdepth: 5
+ :numbered:
+
+ about.rst
+ overview.rst
+ globals.rst
+ dynamic.rst
+ auxiliary.rst
diff --git a/Documentation/filesystems/xfs-data-structures/overview.rst b/Documentation/filesystems/xfs-data-structures/overview.rst
new file mode 100644
index 000000000000..43b48f30f7e8
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/overview.rst
@@ -0,0 +1,44 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+High Level Design
+=================
+
+Overview
+--------
+
+XFS presents to users a standard Unix filesystem interface: a rooted tree of
+directories, files, symbolic links, and devices. All five of those entities
+are represented inside the filesystem by an index node, or "inode";
+each node is uniquely referenced by an inode number. Directories consist of
+(name, inode number) tuples and it is possible for multiple tuples to contain
+the same inode number. Data blocks are associated with files by means of a
+block map in each index node. It is also possible to attach (key, value)
+tuples to any index node; these are known as "extended attributes", which
+extend beyond the standard Unix file attributes.
+
+Internally, XFS filesystems are divided into a number of equally sized chunks
+called Allocation Groups. Each AG can almost be thought of as an individual
+filesystem that maintains its own space usage, index nodes, and other
+secondary metadata. Having multiple AGs allows XFS to handle most operations
+in parallel without degrading performance as the number of concurrent accesses
+increases. Each allocation group uses multiple B+trees to maintain bookkeeping
+records such as the locations of free blocks, the locations of allocated
+inodes, and the locations of free inodes.
+
+Files, symbolic links, and directories can have up to two block maps, or
+"forks", which associate filesystems blocks with a particular file or
+directory. The "attribute fork" tracks blocks used to store and index
+extended attributes, whereas the "data fork" tracks file data blocks,
+symbolic link targets, or directory blocks, depending on the type of the inode
+record. Both forks associate a logical offset with an extent of physical
+blocks, which makes sparse files and directories possible. Directory entries
+and extended attributes are contained inside a second-level data structure
+within the blocks that are mapped by the forks. This structure consists of
+variable-length directory or attribute records and possible a second B+tree to
+index these records.
+
+XFS employs a journalling log in which metadata changes are collected so that
+filesystem operations can be carried out atomically in the case of a crash.
+Furthermore, there is the concept of a real-time device wherein allocations
+are tracked more simply and in larger chunks to reduce jitter in allocation
+latency.
diff --git a/Documentation/index.rst b/Documentation/index.rst
index 5db7e87c7cb1..4136d2274fa6 100644
--- a/Documentation/index.rst
+++ b/Documentation/index.rst
@@ -115,6 +115,7 @@ subprojects.
:maxdepth: 2
filesystems/ext4/index
+ filesystems/xfs-data-structures/index
Translations
------------
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 03/22] docs: add XFS self-describing metadata integrity doc to DS&A book
2018-10-04 3:25 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
2018-10-04 3:25 ` [PATCH 01/22] docs: add skeleton of XFS Data Structures and Algorithms book Darrick J. Wong
@ 2018-10-04 3:25 ` Darrick J. Wong
2018-10-04 3:25 ` [PATCH 04/22] docs: add XFS delayed logging design " Darrick J. Wong
` (4 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:25 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
From: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
.../filesystems/xfs-data-structures/overview.rst | 2
.../self_describing_metadata.rst | 402 ++++++++++++++++++++
.../filesystems/xfs-self-describing-metadata.txt | 350 -----------------
3 files changed, 404 insertions(+), 350 deletions(-)
create mode 100644 Documentation/filesystems/xfs-data-structures/self_describing_metadata.rst
delete mode 100644 Documentation/filesystems/xfs-self-describing-metadata.txt
diff --git a/Documentation/filesystems/xfs-data-structures/overview.rst b/Documentation/filesystems/xfs-data-structures/overview.rst
index 43b48f30f7e8..8b3de9abcf39 100644
--- a/Documentation/filesystems/xfs-data-structures/overview.rst
+++ b/Documentation/filesystems/xfs-data-structures/overview.rst
@@ -42,3 +42,5 @@ filesystem operations can be carried out atomically in the case of a crash.
Furthermore, there is the concept of a real-time device wherein allocations
are tracked more simply and in larger chunks to reduce jitter in allocation
latency.
+
+.. include:: self_describing_metadata.rst
diff --git a/Documentation/filesystems/xfs-data-structures/self_describing_metadata.rst b/Documentation/filesystems/xfs-data-structures/self_describing_metadata.rst
new file mode 100644
index 000000000000..f9d41c76e1d5
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/self_describing_metadata.rst
@@ -0,0 +1,402 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Metadata Integrity
+------------------
+
+Introduction
+~~~~~~~~~~~~
+
+The largest scalability problem facing XFS is not one of algorithmic
+scalability, but of verification of the filesystem structure. Scalabilty of
+the structures and indexes on disk and the algorithms for iterating them are
+adequate for supporting PB scale filesystems with billions of inodes, however
+it is this very scalability that causes the verification problem.
+
+Almost all metadata on XFS is dynamically allocated. The only fixed location
+metadata is the allocation group headers (SB, AGF, AGFL and AGI), while all
+other metadata structures need to be discovered by walking the filesystem
+structure in different ways. While this is already done by userspace tools for
+validating and repairing the structure, there are limits to what they can
+verify, and this in turn limits the supportable size of an XFS filesystem.
+
+For example, it is entirely possible to manually use xfs\_db and a bit of
+scripting to analyse the structure of a 100TB filesystem when trying to
+determine the root cause of a corruption problem, but it is still mainly a
+manual task of verifying that things like single bit errors or misplaced
+writes weren’t the ultimate cause of a corruption event. It may take a few
+hours to a few days to perform such forensic analysis, so for at this scale
+root cause analysis is entirely possible.
+
+However, if we scale the filesystem up to 1PB, we now have 10x as much
+metadata to analyse and so that analysis blows out towards weeks/months of
+forensic work. Most of the analysis work is slow and tedious, so as the amount
+of analysis goes up, the more likely that the cause will be lost in the noise.
+Hence the primary concern for supporting PB scale filesystems is minimising
+the time and effort required for basic forensic analysis of the filesystem
+structure.
+
+Therefore, the version 5 disk format introduced larger headers for all
+metadata types, which enable the filesystem to check information being read
+from the disk more rigorously. Metadata integrity fields now include:
+
+- **Magic** numbers, to classify all types of metadata. This is unchanged
+ from v4.
+
+- A copy of the filesystem **UUID**, to confirm that a given disk block is
+ connected to the superblock.
+
+- The **owner**, to avoid accessing a piece of metadata which belongs to some
+ other part of the filesystem.
+
+- The filesystem **block number**, to detect misplaced writes.
+
+- The **log serial number** of the last write to this block, to avoid
+ replaying obsolete log entries.
+
+- A CRC32c **checksum** of the entire block, to detect minor corruption.
+
+Metadata integrity coverage has been extended to all metadata blocks in the
+filesystem, with the following notes:
+
+- Inodes can have multiple "owners" in the directory tree; therefore the
+ record contains the inode number instead of an owner or a block number.
+
+- Superblocks have no owners.
+
+- The disk quota file has no owner or block numbers.
+
+- Metadata owned by files list the inode number as the owner.
+
+- Per-AG data and B+tree blocks list the AG number as the owner.
+
+- Per-AG header sectors don’t list owners or block numbers, since they have
+ fixed locations.
+
+- Remote attribute blocks are not logged and therefore the LSN must be -1.
+
+This functionality enables XFS to decide that a block contents are so
+unexpected that it should stop immediately. Unfortunately checksums do not
+allow for automatic correction. Please keep regular backups, as always.
+
+Self Describing Metadata
+~~~~~~~~~~~~~~~~~~~~~~~~
+
+One of the problems with the current metadata format is that apart from the
+magic number in the metadata block, we have no other way of identifying what
+it is supposed to be. We can’t even identify if it is the right place. Put
+simply, you can’t look at a single metadata block in isolation and say "yes,
+it is supposed to be there and the contents are valid".
+
+Hence most of the time spent on forensic analysis is spent doing basic
+verification of metadata values, looking for values that are in range (and
+hence not detected by automated verification checks) but are not correct.
+Finding and understanding how things like cross linked block lists (e.g.
+sibling pointers in a btree end up with loops in them) are the key to
+understanding what went wrong, but it is impossible to tell what order the
+blocks were linked into each other or written to disk after the fact.
+
+Hence we need to record more information into the metadata to allow us to
+quickly determine if the metadata is intact and can be ignored for the purpose
+of analysis. We can’t protect against every possible type of error, but we can
+ensure that common types of errors are easily detectable. Hence the concept of
+self describing metadata.
+
+The first, fundamental requirement of self describing metadata is that the
+metadata object contains some form of unique identifier in a well known
+location. This allows us to identify the expected contents of the block and
+hence parse and verify the metadata object. IF we can’t independently identify
+the type of metadata in the object, then the metadata doesn’t describe itself
+very well at all!
+
+Luckily, almost all XFS metadata has magic numbers embedded already - only the
+AGFL, remote symlinks and remote attribute blocks do not contain identifying
+magic numbers. Hence we can change the on-disk format of all these objects to
+add more identifying information and detect this simply by changing the magic
+numbers in the metadata objects. That is, if it has the current magic number,
+the metadata isn’t self identifying. If it contains a new magic number, it is
+self identifying and we can do much more expansive automated verification of
+the metadata object at runtime, during forensic analysis or repair.
+
+As a primary concern, self describing metadata needs some form of overall
+integrity checking. We cannot trust the metadata if we cannot verify that it
+has not been changed as a result of external influences. Hence we need some
+form of integrity check, and this is done by adding CRC32c validation to the
+metadata block. If we can verify the block contains the metadata it was
+intended to contain, a large amount of the manual verification work can be
+skipped.
+
+CRC32c was selected as metadata cannot be more than 64k in length in XFS and
+hence a 32 bit CRC is more than sufficient to detect multi-bit errors in
+metadata blocks. CRC32c is also now hardware accelerated on common CPUs so it
+is fast. So while CRC32c is not the strongest of possible integrity checks
+that could be used, it is more than sufficient for our needs and has
+relatively little overhead. Adding support for larger integrity fields and/or
+algorithms does really provide any extra value over CRC32c, but it does add a
+lot of complexity and so there is no provision for changing the integrity
+checking mechanism.
+
+Self describing metadata needs to contain enough information so that the
+metadata block can be verified as being in the correct place without needing
+to look at any other metadata. This means it needs to contain location
+information. Just adding a block number to the metadata is not sufficient to
+protect against mis-directed writes - a write might be misdirected to the
+wrong LUN and so be written to the "correct block" of the wrong filesystem.
+Hence location information must contain a filesystem identifier as well as a
+block number.
+
+Another key information point in forensic analysis is knowing who the metadata
+block belongs to. We already know the type, the location, that it is valid
+and/or corrupted, and how long ago that it was last modified. Knowing the
+owner of the block is important as it allows us to find other related metadata
+to determine the scope of the corruption. For example, if we have a extent
+btree object, we don’t know what inode it belongs to and hence have to walk
+the entire filesystem to find the owner of the block. Worse, the corruption
+could mean that no owner can be found (i.e. it’s an orphan block), and so
+without an owner field in the metadata we have no idea of the scope of the
+corruption. If we have an owner field in the metadata object, we can
+immediately do top down validation to determine the scope of the problem.
+
+Different types of metadata have different owner identifiers. For example,
+directory, attribute and extent tree blocks are all owned by an inode, whilst
+freespace btree blocks are owned by an allocation group. Hence the size and
+contents of the owner field are determined by the type of metadata object we
+are looking at. The owner information can also identify misplaced writes (e.g.
+freespace btree block written to the wrong AG).
+
+Self describing metadata also needs to contain some indication of when it was
+written to the filesystem. One of the key information points when doing
+forensic analysis is how recently the block was modified. Correlation of set
+of corrupted metadata blocks based on modification times is important as it
+can indicate whether the corruptions are related, whether there’s been
+multiple corruption events that lead to the eventual failure, and even whether
+there are corruptions present that the run-time verification is not detecting.
+
+For example, we can determine whether a metadata object is supposed to be free
+space or still allocated if it is still referenced by its owner by looking at
+when the free space btree block that contains the block was last written
+compared to when the metadata object itself was last written. If the free
+space block is more recent than the object and the object’s owner, then there
+is a very good chance that the block should have been removed from the owner.
+
+To provide this "written timestamp", each metadata block gets the Log Sequence
+Number (LSN) of the most recent transaction it was modified on written into
+it. This number will always increase over the life of the filesystem, and the
+only thing that resets it is running xfs\_repair on the filesystem. Further,
+by use of the LSN we can tell if the corrupted metadata all belonged to the
+same log checkpoint and hence have some idea of how much modification occurred
+between the first and last instance of corrupt metadata on disk and, further,
+how much modification occurred between the corruption being written and when
+it was detected.
+
+Runtime Validation
+~~~~~~~~~~~~~~~~~~
+
+Validation of self-describing metadata takes place at runtime in two places:
+
+- immediately after a successful read from disk
+
+- immediately prior to write IO submission
+
+The verification is completely stateless - it is done independently of the
+modification process, and seeks only to check that the metadata is what it
+says it is and that the metadata fields are within bounds and internally
+consistent. As such, we cannot catch all types of corruption that can occur
+within a block as there may be certain limitations that operational state
+enforces of the metadata, or there may be corruption of interblock
+relationships (e.g. corrupted sibling pointer lists). Hence we still need
+stateful checking in the main code body, but in general most of the per-field
+validation is handled by the verifiers.
+
+For read verification, the caller needs to specify the expected type of
+metadata that it should see, and the IO completion process verifies that the
+metadata object matches what was expected. If the verification process fails,
+then it marks the object being read as EFSCORRUPTED. The caller needs to catch
+this error (same as for IO errors), and if it needs to take special action due
+to a verification error it can do so by catching the EFSCORRUPTED error value.
+If we need more discrimination of error type at higher levels, we can define
+new error numbers for different errors as necessary.
+
+The first step in read verification is checking the magic number and
+determining whether CRC validating is necessary. If it is, the CRC32c is
+calculated and compared against the value stored in the object itself. Once
+this is validated, further checks are made against the location information,
+followed by extensive object specific metadata validation. If any of these
+checks fail, then the buffer is considered corrupt and the EFSCORRUPTED error
+is set appropriately.
+
+Write verification is the opposite of the read verification - first the object
+is extensively verified and if it is OK we then update the LSN from the last
+modification made to the object, After this, we calculate the CRC and insert
+it into the object. Once this is done the write IO is allowed to continue. If
+any error occurs during this process, the buffer is again marked with a
+EFSCORRUPTED error for the higher layers to catch.
+
+Structures
+~~~~~~~~~~
+
+A typical on-disk structure needs to contain the following information:
+
+.. code:: c
+
+ struct xfs_ondisk_hdr {
+ __be32 magic; /* magic number */
+ __be32 crc; /* CRC, not logged */
+ uuid_t uuid; /* filesystem identifier */
+ __be64 owner; /* parent object */
+ __be64 blkno; /* location on disk */
+ __be64 lsn; /* last modification in log, not logged */
+ };
+
+Depending on the metadata, this information may be part of a header structure
+separate to the metadata contents, or may be distributed through an existing
+structure. The latter occurs with metadata that already contains some of this
+information, such as the superblock and AG headers.
+
+Other metadata may have different formats for the information, but the same
+level of information is generally provided. For example:
+
+- short btree blocks have a 32 bit owner (ag number) and a 32 bit block
+ number for location. The two of these combined provide the same information
+ as @owner and @blkno in eh above structure, but using 8 bytes less space on
+ disk.
+
+- directory/attribute node blocks have a 16 bit magic number, and the header
+ that contains the magic number has other information in it as well. hence
+ the additional metadata headers change the overall format of the metadata.
+
+A typical buffer read verifier is structured as follows:
+
+.. code:: c
+
+ #define XFS_FOO_CRC_OFF offsetof(struct xfs_ondisk_hdr, crc)
+
+ static void
+ xfs_foo_read_verify(
+ struct xfs_buf *bp)
+ {
+ struct xfs_mount *mp = bp->b_target->bt_mount;
+
+ if ((xfs_sb_version_hascrc(&mp->m_sb) &&
+ !xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
+ XFS_FOO_CRC_OFF)) ||
+ !xfs_foo_verify(bp)) {
+ XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
+ xfs_buf_ioerror(bp, EFSCORRUPTED);
+ }
+ }
+
+The code ensures that the CRC is only checked if the filesystem has CRCs
+enabled by checking the superblock of the feature bit, and then if the CRC
+verifies OK (or is not needed) it verifies the actual contents of the block.
+
+The verifier function will take a couple of different forms, depending on
+whether the magic number can be used to determine the format of the block. In
+the case it can’t, the code is structured as follows:
+
+.. code:: c
+
+ static bool
+ xfs_foo_verify(
+ struct xfs_buf *bp)
+ {
+ struct xfs_mount *mp = bp->b_target->bt_mount;
+ struct xfs_ondisk_hdr *hdr = bp->b_addr;
+
+ if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
+ return false;
+
+ if (!xfs_sb_version_hascrc(&mp->m_sb)) {
+ if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
+ return false;
+ if (bp->b_bn != be64_to_cpu(hdr->blkno))
+ return false;
+ if (hdr->owner == 0)
+ return false;
+ }
+
+ /* object specific verification checks here */
+
+ return true;
+ }
+
+If there are different magic numbers for the different formats, the verifier
+will look like:
+
+.. code:: c
+
+ static bool
+ xfs_foo_verify(
+ struct xfs_buf *bp)
+ {
+ struct xfs_mount *mp = bp->b_target->bt_mount;
+ struct xfs_ondisk_hdr *hdr = bp->b_addr;
+
+ if (hdr->magic == cpu_to_be32(XFS_FOO_CRC_MAGIC)) {
+ if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
+ return false;
+ if (bp->b_bn != be64_to_cpu(hdr->blkno))
+ return false;
+ if (hdr->owner == 0)
+ return false;
+ } else if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
+ return false;
+
+ /* object specific verification checks here */
+
+ return true;
+ }
+
+Write verifiers are very similar to the read verifiers, they just do things in
+the opposite order to the read verifiers. A typical write verifier:
+
+.. code:: c
+
+ static void
+ xfs_foo_write_verify(
+ struct xfs_buf *bp)
+ {
+ struct xfs_mount *mp = bp->b_target->bt_mount;
+ struct xfs_buf_log_item *bip = bp->b_fspriv;
+
+ if (!xfs_foo_verify(bp)) {
+ XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
+ xfs_buf_ioerror(bp, EFSCORRUPTED);
+ return;
+ }
+
+ if (!xfs_sb_version_hascrc(&mp->m_sb))
+ return;
+
+
+ if (bip) {
+ struct xfs_ondisk_hdr *hdr = bp->b_addr;
+ hdr->lsn = cpu_to_be64(bip->bli_item.li_lsn);
+ }
+ xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length), XFS_FOO_CRC_OFF);
+ }
+
+This will verify the internal structure of the metadata before we go any
+further, detecting corruptions that have occurred as the metadata has been
+modified in memory. If the metadata verifies OK, and CRCs are enabled, we then
+update the LSN field (when it was last modified) and calculate the CRC on the
+metadata. Once this is done, we can issue the IO.
+
+Inodes and Dquots
+~~~~~~~~~~~~~~~~~
+
+Inodes and dquots are special snowflakes. They have per-object CRC and
+self-identifiers, but they are packed so that there are multiple objects per
+buffer. Hence we do not use per-buffer verifiers to do the work of per-object
+verification and CRC calculations. The per-buffer verifiers simply perform
+basic identification of the buffer - that they contain inodes or dquots, and
+that there are magic numbers in all the expected spots. All further CRC and
+verification checks are done when each inode is read from or written back to
+the buffer.
+
+The structure of the verifiers and the identifiers checks is very similar to
+the buffer code described above. The only difference is where they are called.
+For example, inode read verification is done in xfs\_iread() when the inode is
+first read out of the buffer and the struct xfs\_inode is instantiated. The
+inode is already extensively verified during writeback in xfs\_iflush\_int, so
+the only addition here is to add the LSN and CRC to the inode as it is copied
+back into the buffer.
diff --git a/Documentation/filesystems/xfs-self-describing-metadata.txt b/Documentation/filesystems/xfs-self-describing-metadata.txt
deleted file mode 100644
index 05aa455163e3..000000000000
--- a/Documentation/filesystems/xfs-self-describing-metadata.txt
+++ /dev/null
@@ -1,350 +0,0 @@
-XFS Self Describing Metadata
-----------------------------
-
-Introduction
-------------
-
-The largest scalability problem facing XFS is not one of algorithmic
-scalability, but of verification of the filesystem structure. Scalabilty of the
-structures and indexes on disk and the algorithms for iterating them are
-adequate for supporting PB scale filesystems with billions of inodes, however it
-is this very scalability that causes the verification problem.
-
-Almost all metadata on XFS is dynamically allocated. The only fixed location
-metadata is the allocation group headers (SB, AGF, AGFL and AGI), while all
-other metadata structures need to be discovered by walking the filesystem
-structure in different ways. While this is already done by userspace tools for
-validating and repairing the structure, there are limits to what they can
-verify, and this in turn limits the supportable size of an XFS filesystem.
-
-For example, it is entirely possible to manually use xfs_db and a bit of
-scripting to analyse the structure of a 100TB filesystem when trying to
-determine the root cause of a corruption problem, but it is still mainly a
-manual task of verifying that things like single bit errors or misplaced writes
-weren't the ultimate cause of a corruption event. It may take a few hours to a
-few days to perform such forensic analysis, so for at this scale root cause
-analysis is entirely possible.
-
-However, if we scale the filesystem up to 1PB, we now have 10x as much metadata
-to analyse and so that analysis blows out towards weeks/months of forensic work.
-Most of the analysis work is slow and tedious, so as the amount of analysis goes
-up, the more likely that the cause will be lost in the noise. Hence the primary
-concern for supporting PB scale filesystems is minimising the time and effort
-required for basic forensic analysis of the filesystem structure.
-
-
-Self Describing Metadata
-------------------------
-
-One of the problems with the current metadata format is that apart from the
-magic number in the metadata block, we have no other way of identifying what it
-is supposed to be. We can't even identify if it is the right place. Put simply,
-you can't look at a single metadata block in isolation and say "yes, it is
-supposed to be there and the contents are valid".
-
-Hence most of the time spent on forensic analysis is spent doing basic
-verification of metadata values, looking for values that are in range (and hence
-not detected by automated verification checks) but are not correct. Finding and
-understanding how things like cross linked block lists (e.g. sibling
-pointers in a btree end up with loops in them) are the key to understanding what
-went wrong, but it is impossible to tell what order the blocks were linked into
-each other or written to disk after the fact.
-
-Hence we need to record more information into the metadata to allow us to
-quickly determine if the metadata is intact and can be ignored for the purpose
-of analysis. We can't protect against every possible type of error, but we can
-ensure that common types of errors are easily detectable. Hence the concept of
-self describing metadata.
-
-The first, fundamental requirement of self describing metadata is that the
-metadata object contains some form of unique identifier in a well known
-location. This allows us to identify the expected contents of the block and
-hence parse and verify the metadata object. IF we can't independently identify
-the type of metadata in the object, then the metadata doesn't describe itself
-very well at all!
-
-Luckily, almost all XFS metadata has magic numbers embedded already - only the
-AGFL, remote symlinks and remote attribute blocks do not contain identifying
-magic numbers. Hence we can change the on-disk format of all these objects to
-add more identifying information and detect this simply by changing the magic
-numbers in the metadata objects. That is, if it has the current magic number,
-the metadata isn't self identifying. If it contains a new magic number, it is
-self identifying and we can do much more expansive automated verification of the
-metadata object at runtime, during forensic analysis or repair.
-
-As a primary concern, self describing metadata needs some form of overall
-integrity checking. We cannot trust the metadata if we cannot verify that it has
-not been changed as a result of external influences. Hence we need some form of
-integrity check, and this is done by adding CRC32c validation to the metadata
-block. If we can verify the block contains the metadata it was intended to
-contain, a large amount of the manual verification work can be skipped.
-
-CRC32c was selected as metadata cannot be more than 64k in length in XFS and
-hence a 32 bit CRC is more than sufficient to detect multi-bit errors in
-metadata blocks. CRC32c is also now hardware accelerated on common CPUs so it is
-fast. So while CRC32c is not the strongest of possible integrity checks that
-could be used, it is more than sufficient for our needs and has relatively
-little overhead. Adding support for larger integrity fields and/or algorithms
-does really provide any extra value over CRC32c, but it does add a lot of
-complexity and so there is no provision for changing the integrity checking
-mechanism.
-
-Self describing metadata needs to contain enough information so that the
-metadata block can be verified as being in the correct place without needing to
-look at any other metadata. This means it needs to contain location information.
-Just adding a block number to the metadata is not sufficient to protect against
-mis-directed writes - a write might be misdirected to the wrong LUN and so be
-written to the "correct block" of the wrong filesystem. Hence location
-information must contain a filesystem identifier as well as a block number.
-
-Another key information point in forensic analysis is knowing who the metadata
-block belongs to. We already know the type, the location, that it is valid
-and/or corrupted, and how long ago that it was last modified. Knowing the owner
-of the block is important as it allows us to find other related metadata to
-determine the scope of the corruption. For example, if we have a extent btree
-object, we don't know what inode it belongs to and hence have to walk the entire
-filesystem to find the owner of the block. Worse, the corruption could mean that
-no owner can be found (i.e. it's an orphan block), and so without an owner field
-in the metadata we have no idea of the scope of the corruption. If we have an
-owner field in the metadata object, we can immediately do top down validation to
-determine the scope of the problem.
-
-Different types of metadata have different owner identifiers. For example,
-directory, attribute and extent tree blocks are all owned by an inode, whilst
-freespace btree blocks are owned by an allocation group. Hence the size and
-contents of the owner field are determined by the type of metadata object we are
-looking at. The owner information can also identify misplaced writes (e.g.
-freespace btree block written to the wrong AG).
-
-Self describing metadata also needs to contain some indication of when it was
-written to the filesystem. One of the key information points when doing forensic
-analysis is how recently the block was modified. Correlation of set of corrupted
-metadata blocks based on modification times is important as it can indicate
-whether the corruptions are related, whether there's been multiple corruption
-events that lead to the eventual failure, and even whether there are corruptions
-present that the run-time verification is not detecting.
-
-For example, we can determine whether a metadata object is supposed to be free
-space or still allocated if it is still referenced by its owner by looking at
-when the free space btree block that contains the block was last written
-compared to when the metadata object itself was last written. If the free space
-block is more recent than the object and the object's owner, then there is a
-very good chance that the block should have been removed from the owner.
-
-To provide this "written timestamp", each metadata block gets the Log Sequence
-Number (LSN) of the most recent transaction it was modified on written into it.
-This number will always increase over the life of the filesystem, and the only
-thing that resets it is running xfs_repair on the filesystem. Further, by use of
-the LSN we can tell if the corrupted metadata all belonged to the same log
-checkpoint and hence have some idea of how much modification occurred between
-the first and last instance of corrupt metadata on disk and, further, how much
-modification occurred between the corruption being written and when it was
-detected.
-
-Runtime Validation
-------------------
-
-Validation of self-describing metadata takes place at runtime in two places:
-
- - immediately after a successful read from disk
- - immediately prior to write IO submission
-
-The verification is completely stateless - it is done independently of the
-modification process, and seeks only to check that the metadata is what it says
-it is and that the metadata fields are within bounds and internally consistent.
-As such, we cannot catch all types of corruption that can occur within a block
-as there may be certain limitations that operational state enforces of the
-metadata, or there may be corruption of interblock relationships (e.g. corrupted
-sibling pointer lists). Hence we still need stateful checking in the main code
-body, but in general most of the per-field validation is handled by the
-verifiers.
-
-For read verification, the caller needs to specify the expected type of metadata
-that it should see, and the IO completion process verifies that the metadata
-object matches what was expected. If the verification process fails, then it
-marks the object being read as EFSCORRUPTED. The caller needs to catch this
-error (same as for IO errors), and if it needs to take special action due to a
-verification error it can do so by catching the EFSCORRUPTED error value. If we
-need more discrimination of error type at higher levels, we can define new
-error numbers for different errors as necessary.
-
-The first step in read verification is checking the magic number and determining
-whether CRC validating is necessary. If it is, the CRC32c is calculated and
-compared against the value stored in the object itself. Once this is validated,
-further checks are made against the location information, followed by extensive
-object specific metadata validation. If any of these checks fail, then the
-buffer is considered corrupt and the EFSCORRUPTED error is set appropriately.
-
-Write verification is the opposite of the read verification - first the object
-is extensively verified and if it is OK we then update the LSN from the last
-modification made to the object, After this, we calculate the CRC and insert it
-into the object. Once this is done the write IO is allowed to continue. If any
-error occurs during this process, the buffer is again marked with a EFSCORRUPTED
-error for the higher layers to catch.
-
-Structures
-----------
-
-A typical on-disk structure needs to contain the following information:
-
-struct xfs_ondisk_hdr {
- __be32 magic; /* magic number */
- __be32 crc; /* CRC, not logged */
- uuid_t uuid; /* filesystem identifier */
- __be64 owner; /* parent object */
- __be64 blkno; /* location on disk */
- __be64 lsn; /* last modification in log, not logged */
-};
-
-Depending on the metadata, this information may be part of a header structure
-separate to the metadata contents, or may be distributed through an existing
-structure. The latter occurs with metadata that already contains some of this
-information, such as the superblock and AG headers.
-
-Other metadata may have different formats for the information, but the same
-level of information is generally provided. For example:
-
- - short btree blocks have a 32 bit owner (ag number) and a 32 bit block
- number for location. The two of these combined provide the same
- information as @owner and @blkno in eh above structure, but using 8
- bytes less space on disk.
-
- - directory/attribute node blocks have a 16 bit magic number, and the
- header that contains the magic number has other information in it as
- well. hence the additional metadata headers change the overall format
- of the metadata.
-
-A typical buffer read verifier is structured as follows:
-
-#define XFS_FOO_CRC_OFF offsetof(struct xfs_ondisk_hdr, crc)
-
-static void
-xfs_foo_read_verify(
- struct xfs_buf *bp)
-{
- struct xfs_mount *mp = bp->b_target->bt_mount;
-
- if ((xfs_sb_version_hascrc(&mp->m_sb) &&
- !xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
- XFS_FOO_CRC_OFF)) ||
- !xfs_foo_verify(bp)) {
- XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
- xfs_buf_ioerror(bp, EFSCORRUPTED);
- }
-}
-
-The code ensures that the CRC is only checked if the filesystem has CRCs enabled
-by checking the superblock of the feature bit, and then if the CRC verifies OK
-(or is not needed) it verifies the actual contents of the block.
-
-The verifier function will take a couple of different forms, depending on
-whether the magic number can be used to determine the format of the block. In
-the case it can't, the code is structured as follows:
-
-static bool
-xfs_foo_verify(
- struct xfs_buf *bp)
-{
- struct xfs_mount *mp = bp->b_target->bt_mount;
- struct xfs_ondisk_hdr *hdr = bp->b_addr;
-
- if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
- return false;
-
- if (!xfs_sb_version_hascrc(&mp->m_sb)) {
- if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
- return false;
- if (bp->b_bn != be64_to_cpu(hdr->blkno))
- return false;
- if (hdr->owner == 0)
- return false;
- }
-
- /* object specific verification checks here */
-
- return true;
-}
-
-If there are different magic numbers for the different formats, the verifier
-will look like:
-
-static bool
-xfs_foo_verify(
- struct xfs_buf *bp)
-{
- struct xfs_mount *mp = bp->b_target->bt_mount;
- struct xfs_ondisk_hdr *hdr = bp->b_addr;
-
- if (hdr->magic == cpu_to_be32(XFS_FOO_CRC_MAGIC)) {
- if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
- return false;
- if (bp->b_bn != be64_to_cpu(hdr->blkno))
- return false;
- if (hdr->owner == 0)
- return false;
- } else if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
- return false;
-
- /* object specific verification checks here */
-
- return true;
-}
-
-Write verifiers are very similar to the read verifiers, they just do things in
-the opposite order to the read verifiers. A typical write verifier:
-
-static void
-xfs_foo_write_verify(
- struct xfs_buf *bp)
-{
- struct xfs_mount *mp = bp->b_target->bt_mount;
- struct xfs_buf_log_item *bip = bp->b_fspriv;
-
- if (!xfs_foo_verify(bp)) {
- XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
- xfs_buf_ioerror(bp, EFSCORRUPTED);
- return;
- }
-
- if (!xfs_sb_version_hascrc(&mp->m_sb))
- return;
-
-
- if (bip) {
- struct xfs_ondisk_hdr *hdr = bp->b_addr;
- hdr->lsn = cpu_to_be64(bip->bli_item.li_lsn);
- }
- xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length), XFS_FOO_CRC_OFF);
-}
-
-This will verify the internal structure of the metadata before we go any
-further, detecting corruptions that have occurred as the metadata has been
-modified in memory. If the metadata verifies OK, and CRCs are enabled, we then
-update the LSN field (when it was last modified) and calculate the CRC on the
-metadata. Once this is done, we can issue the IO.
-
-Inodes and Dquots
------------------
-
-Inodes and dquots are special snowflakes. They have per-object CRC and
-self-identifiers, but they are packed so that there are multiple objects per
-buffer. Hence we do not use per-buffer verifiers to do the work of per-object
-verification and CRC calculations. The per-buffer verifiers simply perform basic
-identification of the buffer - that they contain inodes or dquots, and that
-there are magic numbers in all the expected spots. All further CRC and
-verification checks are done when each inode is read from or written back to the
-buffer.
-
-The structure of the verifiers and the identifiers checks is very similar to the
-buffer code described above. The only difference is where they are called. For
-example, inode read verification is done in xfs_iread() when the inode is first
-read out of the buffer and the struct xfs_inode is instantiated. The inode is
-already extensively verified during writeback in xfs_iflush_int, so the only
-addition here is to add the LSN and CRC to the inode as it is copied back into
-the buffer.
-
-XXX: inode unlinked list modification doesn't recalculate the inode CRC! None of
-the unlinked list modifications check or update CRCs, neither during unlink nor
-log recovery. So, it's gone unnoticed until now. This won't matter immediately -
-repair will probably complain about it - but it needs to be fixed.
-
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 04/22] docs: add XFS delayed logging design doc to DS&A book
2018-10-04 3:25 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
2018-10-04 3:25 ` [PATCH 01/22] docs: add skeleton of XFS Data Structures and Algorithms book Darrick J. Wong
2018-10-04 3:25 ` [PATCH 03/22] docs: add XFS self-describing metadata integrity doc to DS&A book Darrick J. Wong
@ 2018-10-04 3:25 ` Darrick J. Wong
2018-10-04 3:25 ` [PATCH 05/22] docs: add XFS shared data block chapter " Darrick J. Wong
` (3 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:25 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
From: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
.../xfs-data-structures/delayed_logging.rst | 828 ++++++++++++++++++++
.../filesystems/xfs-data-structures/overview.rst | 1
.../filesystems/xfs-delayed-logging-design.txt | 793 -------------------
3 files changed, 829 insertions(+), 793 deletions(-)
create mode 100644 Documentation/filesystems/xfs-data-structures/delayed_logging.rst
delete mode 100644 Documentation/filesystems/xfs-delayed-logging-design.txt
diff --git a/Documentation/filesystems/xfs-data-structures/delayed_logging.rst b/Documentation/filesystems/xfs-data-structures/delayed_logging.rst
new file mode 100644
index 000000000000..a4ae343e7556
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/delayed_logging.rst
@@ -0,0 +1,828 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Delayed Logging
+---------------
+
+Introduction to Re-logging in XFS
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+XFS logging is a combination of logical and physical logging. Some objects,
+such as inodes and dquots, are logged in logical format where the details
+logged are made up of the changes to in-core structures rather than on-disk
+structures. Other objects - typically buffers - have their physical changes
+logged. The reason for these differences is to reduce the amount of log space
+required for objects that are frequently logged. Some parts of inodes are more
+frequently logged than others, and inodes are typically more frequently logged
+than any other object (except maybe the superblock buffer) so keeping the
+amount of metadata logged low is of prime importance.
+
+The reason that this is such a concern is that XFS allows multiple separate
+modifications to a single object to be carried in the log at any given time.
+This allows the log to avoid needing to flush each change to disk before
+recording a new change to the object. XFS does this via a method called
+"re-logging". Conceptually, this is quite simple - all it requires is that any
+new change to the object is recorded with a **new copy** of all the existing
+changes in the new transaction that is written to the log.
+
+That is, if we have a sequence of changes A through to F, and the object was
+written to disk after change D, we would see in the log the following series
+of transactions, their contents and the log sequence number (LSN) of the
+transaction:
+
+::
+
+ Transaction Contents LSN
+ A A X
+ B A+B X+n
+ C A+B+C X+n+m
+ D A+B+C+D X+n+m+o
+ <object written to disk>
+ E E Y (> X+n+m+o)
+ F E+F Y+p
+
+In other words, each time an object is relogged, the new transaction contains
+the aggregation of all the previous changes currently held only in the log.
+
+This relogging technique also allows objects to be moved forward in the log so
+that an object being relogged does not prevent the tail of the log from ever
+moving forward. This can be seen in the table above by the changing
+(increasing) LSN of each subsequent transaction - the LSN is effectively a
+direct encoding of the location in the log of the transaction.
+
+This relogging is also used to implement long-running, multiple-commit
+transactions. These transaction are known as rolling transactions, and require
+a special log reservation known as a permanent transaction reservation. A
+typical example of a rolling transaction is the removal of extents from an
+inode which can only be done at a rate of two extents per transaction because
+of reservation size limitations. Hence a rolling extent removal transaction
+keeps relogging the inode and btree buffers as they get modified in each
+removal operation. This keeps them moving forward in the log as the operation
+progresses, ensuring that current operation never gets blocked by itself if
+the log wraps around.
+
+Hence it can be seen that the relogging operation is fundamental to the
+correct working of the XFS journalling subsystem. From the above description,
+most people should be able to see why the XFS metadata operations writes so
+much to the log - repeated operations to the same objects write the same
+changes to the log over and over again. Worse is the fact that objects tend to
+get dirtier as they get relogged, so each subsequent transaction is writing
+more metadata into the log.
+
+Another feature of the XFS transaction subsystem is that most transactions are
+asynchronous. That is, they don’t commit to disk until either a log buffer is
+filled (a log buffer can hold multiple transactions) or a synchronous
+operation forces the log buffers holding the transactions to disk. This means
+that XFS is doing aggregation of transactions in memory - batching them, if
+you like - to minimise the impact of the log IO on transaction throughput.
+
+The limitation on asynchronous transaction throughput is the number and size
+of log buffers made available by the log manager. By default there are 8 log
+buffers available and the size of each is 32kB - the size can be increased up
+to 256kB by use of a mount option.
+
+Effectively, this gives us the maximum bound of outstanding metadata changes
+that can be made to the filesystem at any point in time - if all the log
+buffers are full and under IO, then no more transactions can be committed
+until the current batch completes. It is now common for a single current CPU
+core to be to able to issue enough transactions to keep the log buffers full
+and under IO permanently. Hence the XFS journalling subsystem can be
+considered to be IO bound.
+
+Delayed Logging Concepts
+~~~~~~~~~~~~~~~~~~~~~~~~
+
+The key thing to note about the asynchronous logging combined with the
+relogging technique XFS uses is that we can be relogging changed objects
+multiple times before they are committed to disk in the log buffers. If we
+return to the previous relogging example, it is entirely possible that
+transactions A through D are committed to disk in the same log buffer.
+
+That is, a single log buffer may contain multiple copies of the same object,
+but only one of those copies needs to be there - the last one "D", as it
+contains all the changes from the previous changes. In other words, we have
+one necessary copy in the log buffer, and three stale copies that are simply
+wasting space. When we are doing repeated operations on the same set of
+objects, these "stale objects" can be over 90% of the space used in the log
+buffers. It is clear that reducing the number of stale objects written to the
+log would greatly reduce the amount of metadata we write to the log, and this
+is the fundamental goal of delayed logging.
+
+From a conceptual point of view, XFS is already doing relogging in memory
+(where memory == log buffer), only it is doing it extremely inefficiently. It
+is using logical to physical formatting to do the relogging because there is
+no infrastructure to keep track of logical changes in memory prior to
+physically formatting the changes in a transaction to the log buffer. Hence we
+cannot avoid accumulating stale objects in the log buffers.
+
+Delayed logging is the name we’ve given to keeping and tracking transactional
+changes to objects in memory outside the log buffer infrastructure. Because of
+the relogging concept fundamental to the XFS journalling subsystem, this is
+actually relatively easy to do - all the changes to logged items are already
+tracked in the current infrastructure. The big problem is how to accumulate
+them and get them to the log in a consistent, recoverable manner. Describing
+the problems and how they have been solved is the focus of this document.
+
+One of the key changes that delayed logging makes to the operation of the
+journalling subsystem is that it disassociates the amount of outstanding
+metadata changes from the size and number of log buffers available. In other
+words, instead of there only being a maximum of 2MB of transaction changes not
+written to the log at any point in time, there may be a much greater amount
+being accumulated in memory. Hence the potential for loss of metadata on a
+crash is much greater than for the existing logging mechanism.
+
+It should be noted that this does not change the guarantee that log recovery
+will result in a consistent filesystem. What it does mean is that as far as
+the recovered filesystem is concerned, there may be many thousands of
+transactions that simply did not occur as a result of the crash. This makes it
+even more important that applications that care about their data use fsync()
+where they need to ensure application level data integrity is maintained.
+
+It should be noted that delayed logging is not an innovative new concept that
+warrants rigorous proofs to determine whether it is correct or not. The method
+of accumulating changes in memory for some period before writing them to the
+log is used effectively in many filesystems including ext3 and ext4. Hence no
+time is spent in this document trying to convince the reader that the concept
+is sound. Instead it is simply considered a "solved problem" and as such
+implementing it in XFS is purely an exercise in software engineering.
+
+The fundamental requirements for delayed logging in XFS are simple:
+
+1. Reduce the amount of metadata written to the log by at least an order of
+ magnitude.
+
+2. Supply sufficient statistics to validate Requirement #1.
+
+3. Supply sufficient new tracing infrastructure to be able to debug problems
+ with the new code.
+
+4. No on-disk format change (metadata or log format).
+
+5. Enable and disable with a mount option.
+
+6. No performance regressions for synchronous transaction workloads.
+
+Delayed Logging Design
+~~~~~~~~~~~~~~~~~~~~~~
+
+Storing Changes
+^^^^^^^^^^^^^^^
+
+The problem with accumulating changes at a logical level (i.e. just using the
+existing log item dirty region tracking) is that when it comes to writing the
+changes to the log buffers, we need to ensure that the object we are
+formatting is not changing while we do this. This requires locking the object
+to prevent concurrent modification. Hence flushing the logical changes to the
+log would require us to lock every object, format them, and then unlock them
+again.
+
+This introduces lots of scope for deadlocks with transactions that are already
+running. For example, a transaction has object A locked and modified, but
+needs the delayed logging tracking lock to commit the transaction. However,
+the flushing thread has the delayed logging tracking lock already held, and is
+trying to get the lock on object A to flush it to the log buffer. This appears
+to be an unsolvable deadlock condition, and it was solving this problem that
+was the barrier to implementing delayed logging for so long.
+
+The solution is relatively simple - it just took a long time to recognise it.
+Put simply, the current logging code formats the changes to each item into an
+vector array that points to the changed regions in the item. The log write
+code simply copies the memory these vectors point to into the log buffer
+during transaction commit while the item is locked in the transaction. Instead
+of using the log buffer as the destination of the formatting code, we can use
+an allocated memory buffer big enough to fit the formatted vector.
+
+If we then copy the vector into the memory buffer and rewrite the vector to
+point to the memory buffer rather than the object itself, we now have a copy
+of the changes in a format that is compatible with the log buffer writing
+code. that does not require us to lock the item to access. This formatting and
+rewriting can all be done while the object is locked during transaction
+commit, resulting in a vector that is transactionally consistent and can be
+accessed without needing to lock the owning item.
+
+Hence we avoid the need to lock items when we need to flush outstanding
+asynchronous transactions to the log. The differences between the existing
+formatting method and the delayed logging formatting can be seen in the
+diagram below.
+
+Current format log vector:
+
+::
+
+ Object +---------------------------------------------+
+ Vector 1 +----+
+ Vector 2 +----+
+ Vector 3 +----------+
+
+After formatting:
+
+::
+
+ Log Buffer +-V1-+-V2-+----V3----+
+
+Delayed logging vector:
+
+::
+
+ Object +---------------------------------------------+
+ Vector 1 +----+
+ Vector 2 +----+
+ Vector 3 +----------+
+
+After formatting:
+
+::
+
+ Memory Buffer +-V1-+-V2-+----V3----+
+ Vector 1 +----+
+ Vector 2 +----+
+ Vector 3 +----------+
+
+The memory buffer and associated vector need to be passed as a single object,
+but still need to be associated with the parent object so if the object is
+relogged we can replace the current memory buffer with a new memory buffer
+that contains the latest changes.
+
+The reason for keeping the vector around after we’ve formatted the memory
+buffer is to support splitting vectors across log buffer boundaries correctly.
+If we don’t keep the vector around, we do not know where the region boundaries
+are in the item, so we’d need a new encapsulation method for regions in the
+log buffer writing (i.e. double encapsulation). This would be an on-disk
+format change and as such is not desirable. It also means we’d have to write
+the log region headers in the formatting stage, which is problematic as there
+is per region state that needs to be placed into the headers during the log
+write.
+
+Hence we need to keep the vector, but by attaching the memory buffer to it and
+rewriting the vector addresses to point at the memory buffer we end up with a
+self-describing object that can be passed to the log buffer write code to be
+handled in exactly the same manner as the existing log vectors are handled.
+Hence we avoid needing a new on-disk format to handle items that have been
+relogged in memory.
+
+Tracking Changes
+^^^^^^^^^^^^^^^^
+
+Now that we can record transactional changes in memory in a form that allows
+them to be used without limitations, we need to be able to track and
+accumulate them so that they can be written to the log at some later point in
+time. The log item is the natural place to store this vector and buffer, and
+also makes sense to be the object that is used to track committed objects as
+it will always exist once the object has been included in a transaction.
+
+The log item is already used to track the log items that have been written to
+the log but not yet written to disk. Such log items are considered "active"
+and as such are stored in the Active Item List (AIL) which is a LSN-ordered
+double linked list. Items are inserted into this list during log buffer IO
+completion, after which they are unpinned and can be written to disk. An
+object that is in the AIL can be relogged, which causes the object to be
+pinned again and then moved forward in the AIL when the log buffer IO
+completes for that transaction.
+
+Essentially, this shows that an item that is in the AIL can still be modified
+and relogged, so any tracking must be separate to the AIL infrastructure. As
+such, we cannot reuse the AIL list pointers for tracking committed items, nor
+can we store state in any field that is protected by the AIL lock. Hence the
+committed item tracking needs it’s own locks, lists and state fields in the
+log item.
+
+Similar to the AIL, tracking of committed items is done through a new list
+called the Committed Item List (CIL). The list tracks log items that have been
+committed and have formatted memory buffers attached to them. It tracks
+objects in transaction commit order, so when an object is relogged it is
+removed from it’s place in the list and re-inserted at the tail. This is
+entirely arbitrary and done to make it easy for debugging - the last items in
+the list are the ones that are most recently modified. Ordering of the CIL is
+not necessary for transactional integrity (as discussed in the next section)
+so the ordering is done for convenience/sanity of the developers.
+
+Checkpoints
+^^^^^^^^^^^
+
+When we have a log synchronisation event, commonly known as a "log force", all
+the items in the CIL must be written into the log via the log buffers. We need
+to write these items in the order that they exist in the CIL, and they need to
+be written as an atomic transaction. The need for all the objects to be
+written as an atomic transaction comes from the requirements of relogging and
+log replay - all the changes in all the objects in a given transaction must
+either be completely replayed during log recovery, or not replayed at all. If
+a transaction is not replayed because it is not complete in the log, then no
+later transactions should be replayed, either.
+
+To fulfill this requirement, we need to write the entire CIL in a single log
+transaction. Fortunately, the XFS log code has no fixed limit on the size of a
+transaction, nor does the log replay code. The only fundamental limit is that
+the transaction cannot be larger than just under half the size of the log. The
+reason for this limit is that to find the head and tail of the log, there must
+be at least one complete transaction in the log at any given time. If a
+transaction is larger than half the log, then there is the possibility that a
+crash during the write of a such a transaction could partially overwrite the
+only complete previous transaction in the log. This will result in a recovery
+failure and an inconsistent filesystem and hence we must enforce the maximum
+size of a checkpoint to be slightly less than a half the log.
+
+Apart from this size requirement, a checkpoint transaction looks no different
+to any other transaction - it contains a transaction header, a series of
+formatted log items and a commit record at the tail. From a recovery
+perspective, the checkpoint transaction is also no different - just a lot
+bigger with a lot more items in it. The worst case effect of this is that we
+might need to tune the recovery transaction object hash size.
+
+Because the checkpoint is just another transaction and all the changes to log
+items are stored as log vectors, we can use the existing log buffer writing
+code to write the changes into the log. To do this efficiently, we need to
+minimise the time we hold the CIL locked while writing the checkpoint
+transaction. The current log write code enables us to do this easily with the
+way it separates the writing of the transaction contents (the log vectors)
+from the transaction commit record, but tracking this requires us to have a
+per-checkpoint context that travels through the log write process through to
+checkpoint completion.
+
+Hence a checkpoint has a context that tracks the state of the current
+checkpoint from initiation to checkpoint completion. A new context is
+initiated at the same time a checkpoint transaction is started. That is, when
+we remove all the current items from the CIL during a checkpoint operation, we
+move all those changes into the current checkpoint context. We then initialise
+a new context and attach that to the CIL for aggregation of new transactions.
+
+This allows us to unlock the CIL immediately after transfer of all the
+committed items and effectively allow new transactions to be issued while we
+are formatting the checkpoint into the log. It also allows concurrent
+checkpoints to be written into the log buffers in the case of log force heavy
+workloads, just like the existing transaction commit code does. This, however,
+requires that we strictly order the commit records in the log so that
+checkpoint sequence order is maintained during log replay.
+
+To ensure that we can be writing an item into a checkpoint transaction at the
+same time another transaction modifies the item and inserts the log item into
+the new CIL, then checkpoint transaction commit code cannot use log items to
+store the list of log vectors that need to be written into the transaction.
+Hence log vectors need to be able to be chained together to allow them to be
+detached from the log items. That is, when the CIL is flushed the memory
+buffer and log vector attached to each log item needs to be attached to the
+checkpoint context so that the log item can be released. In diagrammatic form,
+the CIL would look like this before the flush:
+
+::
+
+ CIL Head
+ |
+ V
+ Log Item <-> log vector 1 -> memory buffer
+ | -> vector array
+ V
+ Log Item <-> log vector 2 -> memory buffer
+ | -> vector array
+ V
+ ......
+ |
+ V
+ Log Item <-> log vector N-1 -> memory buffer
+ | -> vector array
+ V
+ Log Item <-> log vector N -> memory buffer
+ -> vector array
+
+And after the flush the CIL head is empty, and the checkpoint context log
+vector list would look like:
+
+::
+
+ Checkpoint Context
+ |
+ V
+ log vector 1 -> memory buffer
+ | -> vector array
+ | -> Log Item
+ V
+ log vector 2 -> memory buffer
+ | -> vector array
+ | -> Log Item
+ V
+ ......
+ |
+ V
+ log vector N-1 -> memory buffer
+ | -> vector array
+ | -> Log Item
+ V
+ log vector N -> memory buffer
+ -> vector array
+ -> Log Item
+
+Once this transfer is done, the CIL can be unlocked and new transactions can
+start, while the checkpoint flush code works over the log vector chain to
+commit the checkpoint.
+
+Once the checkpoint is written into the log buffers, the checkpoint context is
+attached to the log buffer that the commit record was written to along with a
+completion callback. Log IO completion will call that callback, which can then
+run transaction committed processing for the log items (i.e. insert into AIL
+and unpin) in the log vector chain and then free the log vector chain and
+checkpoint context.
+
+Discussion Point: I am uncertain as to whether the log item is the most
+efficient way to track vectors, even though it seems like the natural way to
+do it. The fact that we walk the log items (in the CIL) just to chain the log
+vectors and break the link between the log item and the log vector means that
+we take a cache line hit for the log item list modification, then another for
+the log vector chaining. If we track by the log vectors, then we only need to
+break the link between the log item and the log vector, which means we should
+dirty only the log item cachelines. Normally I wouldn’t be concerned about one
+vs two dirty cachelines except for the fact I’ve seen upwards of 80,000 log
+vectors in one checkpoint transaction. I’d guess this is a "measure and
+compare" situation that can be done after a working and reviewed
+implementation is in the dev tree.
+
+Checkpoint Sequencing
+^^^^^^^^^^^^^^^^^^^^^
+
+One of the key aspects of the XFS transaction subsystem is that it tags
+committed transactions with the log sequence number of the transaction commit.
+This allows transactions to be issued asynchronously even though there may be
+future operations that cannot be completed until that transaction is fully
+committed to the log. In the rare case that a dependent operation occurs (e.g.
+re-using a freed metadata extent for a data extent), a special, optimised log
+force can be issued to force the dependent transaction to disk immediately.
+
+To do this, transactions need to record the LSN of the commit record of the
+transaction. This LSN comes directly from the log buffer the transaction is
+written into. While this works just fine for the existing transaction
+mechanism, it does not work for delayed logging because transactions are not
+written directly into the log buffers. Hence some other method of sequencing
+transactions is required.
+
+As discussed in the checkpoint section, delayed logging uses per-checkpoint
+contexts, and as such it is simple to assign a sequence number to each
+checkpoint. Because the switching of checkpoint contexts must be done
+atomically, it is simple to ensure that each new context has a monotonically
+increasing sequence number assigned to it without the need for an external
+atomic counter - we can just take the current context sequence number and add
+one to it for the new context.
+
+Then, instead of assigning a log buffer LSN to the transaction commit LSN
+during the commit, we can assign the current checkpoint sequence. This allows
+operations that track transactions that have not yet completed know what
+checkpoint sequence needs to be committed before they can continue. As a
+result, the code that forces the log to a specific LSN now needs to ensure
+that the log forces to a specific checkpoint.
+
+To ensure that we can do this, we need to track all the checkpoint contexts
+that are currently committing to the log. When we flush a checkpoint, the
+context gets added to a "committing" list which can be searched. When a
+checkpoint commit completes, it is removed from the committing list. Because
+the checkpoint context records the LSN of the commit record for the
+checkpoint, we can also wait on the log buffer that contains the commit
+record, thereby using the existing log force mechanisms to execute synchronous
+forces.
+
+It should be noted that the synchronous forces may need to be extended with
+mitigation algorithms similar to the current log buffer code to allow
+aggregation of multiple synchronous transactions if there are already
+synchronous transactions being flushed. Investigation of the performance of
+the current design is needed before making any decisions here.
+
+The main concern with log forces is to ensure that all the previous
+checkpoints are also committed to disk before the one we need to wait for.
+Therefore we need to check that all the prior contexts in the committing list
+are also complete before waiting on the one we need to complete. We do this
+synchronisation in the log force code so that we don’t need to wait anywhere
+else for such serialisation - it only matters when we do a log force.
+
+The only remaining complexity is that a log force now also has to handle the
+case where the forcing sequence number is the same as the current context.
+That is, we need to flush the CIL and potentially wait for it to complete.
+This is a simple addition to the existing log forcing code to check the
+sequence numbers and push if required. Indeed, placing the current sequence
+checkpoint flush in the log force code enables the current mechanism for
+issuing synchronous transactions to remain untouched (i.e. commit an
+asynchronous transaction, then force the log at the LSN of that transaction)
+and so the higher level code behaves the same regardless of whether delayed
+logging is being used or not.
+
+Checkpoint Log Space Accounting
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+The big issue for a checkpoint transaction is the log space reservation for
+the transaction. We don’t know how big a checkpoint transaction is going to be
+ahead of time, nor how many log buffers it will take to write out, nor the
+number of split log vector regions are going to be used. We can track the
+amount of log space required as we add items to the commit item list, but we
+still need to reserve the space in the log for the checkpoint.
+
+A typical transaction reserves enough space in the log for the worst case
+space usage of the transaction. The reservation accounts for log record
+headers, transaction and region headers, headers for split regions, buffer
+tail padding, etc. as well as the actual space for all the changed metadata in
+the transaction. While some of this is fixed overhead, much of it is dependent
+on the size of the transaction and the number of regions being logged (the
+number of log vectors in the transaction).
+
+An example of the differences would be logging directory changes versus
+logging inode changes. If you modify lots of inode cores (e.g. chmod -R g+w
+\*), then there are lots of transactions that only contain an inode core and
+an inode log format structure. That is, two vectors totaling roughly 150
+bytes. If we modify 10,000 inodes, we have about 1.5MB of metadata to write in
+20,000 vectors. Each vector is 12 bytes, so the total to be logged is
+approximately 1.75MB. In comparison, if we are logging full directory buffers,
+they are typically 4KB each, so we in 1.5MB of directory buffers we’d have
+roughly 400 buffers and a buffer format structure for each buffer - roughly
+800 vectors or 1.51MB total space. From this, it should be obvious that a
+static log space reservation is not particularly flexible and is difficult to
+select the "optimal value" for all workloads.
+
+Further, if we are going to use a static reservation, which bit of the entire
+reservation does it cover? We account for space used by the transaction
+reservation by tracking the space currently used by the object in the CIL and
+then calculating the increase or decrease in space used as the object is
+relogged. This allows for a checkpoint reservation to only have to account for
+log buffer metadata used such as log header records.
+
+However, even using a static reservation for just the log metadata is
+problematic. Typically log record headers use at least 16KB of log space per
+1MB of log space consumed (512 bytes per 32k) and the reservation needs to be
+large enough to handle arbitrary sized checkpoint transactions. This
+reservation needs to be made before the checkpoint is started, and we need to
+be able to reserve the space without sleeping. For a 8MB checkpoint, we need a
+reservation of around 150KB, which is a non-trivial amount of space.
+
+A static reservation needs to manipulate the log grant counters - we can take
+a permanent reservation on the space, but we still need to make sure we
+refresh the write reservation (the actual space available to the transaction)
+after every checkpoint transaction completion. Unfortunately, if this space is
+not available when required, then the regrant code will sleep waiting for it.
+
+The problem with this is that it can lead to deadlocks as we may need to
+commit checkpoints to be able to free up log space (refer back to the
+description of rolling transactions for an example of this). Hence we **must**
+always have space available in the log if we are to use static reservations,
+and that is very difficult and complex to arrange. It is possible to do, but
+there is a simpler way.
+
+The simpler way of doing this is tracking the entire log space used by the
+items in the CIL and using this to dynamically calculate the amount of log
+space required by the log metadata. If this log metadata space changes as a
+result of a transaction commit inserting a new memory buffer into the CIL,
+then the difference in space required is removed from the transaction that
+causes the change. Transactions at this level will **always** have enough
+space available in their reservation for this as they have already reserved
+the maximal amount of log metadata space they require, and such a delta
+reservation will always be less than or equal to the maximal amount in the
+reservation.
+
+Hence we can grow the checkpoint transaction reservation dynamically as items
+are added to the CIL and avoid the need for reserving and regranting log space
+up front. This avoids deadlocks and removes a blocking point from the
+checkpoint flush code.
+
+As mentioned early, transactions can’t grow to more than half the size of the
+log. Hence as part of the reservation growing, we need to also check the size
+of the reservation against the maximum allowed transaction size. If we reach
+the maximum threshold, we need to push the CIL to the log. This is effectively
+a "background flush" and is done on demand. This is identical to a CIL push
+triggered by a log force, only that there is no waiting for the checkpoint
+commit to complete. This background push is checked and executed by
+transaction commit code.
+
+If the transaction subsystem goes idle while we still have items in the CIL,
+they will be flushed by the periodic log force issued by the xfssyncd. This
+log force will push the CIL to disk, and if the transaction subsystem stays
+idle, allow the idle log to be covered (effectively marked clean) in exactly
+the same manner that is done for the existing logging method. A discussion
+point is whether this log force needs to be done more frequently than the
+current rate which is once every 30s.
+
+Log Item Pinning
+^^^^^^^^^^^^^^^^
+
+Currently log items are pinned during transaction commit while the items are
+still locked. This happens just after the items are formatted, though it could
+be done any time before the items are unlocked. The result of this mechanism
+is that items get pinned once for every transaction that is committed to the
+log buffers. Hence items that are relogged in the log buffers will have a pin
+count for every outstanding transaction they were dirtied in. When each of
+these transactions is completed, they will unpin the item once. As a result,
+the item only becomes unpinned when all the transactions complete and there
+are no pending transactions. Thus the pinning and unpinning of a log item is
+symmetric as there is a 1:1 relationship with transaction commit and log item
+completion.
+
+For delayed logging, however, we have an asymmetric transaction commit to
+completion relationship. Every time an object is relogged in the CIL it goes
+through the commit process without a corresponding completion being
+registered. That is, we now have a many-to-one relationship between
+transaction commit and log item completion. The result of this is that pinning
+and unpinning of the log items becomes unbalanced if we retain the "pin on
+transaction commit, unpin on transaction completion" model.
+
+To keep pin/unpin symmetry, the algorithm needs to change to a "pin on
+insertion into the CIL, unpin on checkpoint completion". In other words, the
+pinning and unpinning becomes symmetric around a checkpoint context. We have
+to pin the object the first time it is inserted into the CIL - if it is
+already in the CIL during a transaction commit, then we do not pin it again.
+Because there can be multiple outstanding checkpoint contexts, we can still
+see elevated pin counts, but as each checkpoint completes the pin count will
+retain the correct value according to it’s context.
+
+Just to make matters more slightly more complex, this checkpoint level context
+for the pin count means that the pinning of an item must take place under the
+CIL commit/flush lock. If we pin the object outside this lock, we cannot
+guarantee which context the pin count is associated with. This is because of
+the fact pinning the item is dependent on whether the item is present in the
+current CIL or not. If we don’t pin the CIL first before we check and pin the
+object, we have a race with CIL being flushed between the check and the pin
+(or not pinning, as the case may be). Hence we must hold the CIL flush/commit
+lock to guarantee that we pin the items correctly.
+
+Concurrent Scalability
+^^^^^^^^^^^^^^^^^^^^^^
+
+A fundamental requirement for the CIL is that accesses through transaction
+commits must scale to many concurrent commits. The current transaction commit
+code does not break down even when there are transactions coming from 2048
+processors at once. The current transaction code does not go any faster than
+if there was only one CPU using it, but it does not slow down either.
+
+As a result, the delayed logging transaction commit code needs to be designed
+for concurrency from the ground up. It is obvious that there are serialisation
+points in the design - the three important ones are:
+
+1. Locking out new transaction commits while flushing the CIL
+
+2. Adding items to the CIL and updating item space accounting
+
+3. Checkpoint commit ordering
+
+Looking at the transaction commit and CIL flushing interactions, it is clear
+that we have a many-to-one interaction here. That is, the only restriction on
+the number of concurrent transactions that can be trying to commit at once is
+the amount of space available in the log for their reservations. The practical
+limit here is in the order of several hundred concurrent transactions for a
+128MB log, which means that it is generally one per CPU in a machine.
+
+The amount of time a transaction commit needs to hold out a flush is a
+relatively long period of time - the pinning of log items needs to be done
+while we are holding out a CIL flush, so at the moment that means it is held
+across the formatting of the objects into memory buffers (i.e. while memcpy()s
+are in progress). Ultimately a two pass algorithm where the formatting is done
+separately to the pinning of objects could be used to reduce the hold time of
+the transaction commit side.
+
+Because of the number of potential transaction commit side holders, the lock
+really needs to be a sleeping lock - if the CIL flush takes the lock, we do
+not want every other CPU in the machine spinning on the CIL lock. Given that
+flushing the CIL could involve walking a list of tens of thousands of log
+items, it will get held for a significant time and so spin contention is a
+significant concern. Preventing lots of CPUs spinning doing nothing is the
+main reason for choosing a sleeping lock even though nothing in either the
+transaction commit or CIL flush side sleeps with the lock held.
+
+It should also be noted that CIL flushing is also a relatively rare operation
+compared to transaction commit for asynchronous transaction workloads - only
+time will tell if using a read-write semaphore for exclusion will limit
+transaction commit concurrency due to cache line bouncing of the lock on the
+read side.
+
+The second serialisation point is on the transaction commit side where items
+are inserted into the CIL. Because transactions can enter this code
+concurrently, the CIL needs to be protected separately from the above
+commit/flush exclusion. It also needs to be an exclusive lock but it is only
+held for a very short time and so a spin lock is appropriate here. It is
+possible that this lock will become a contention point, but given the short
+hold time once per transaction I think that contention is unlikely.
+
+The final serialisation point is the checkpoint commit record ordering code
+that is run as part of the checkpoint commit and log force sequencing. The
+code path that triggers a CIL flush (i.e. whatever triggers the log force)
+will enter an ordering loop after writing all the log vectors into the log
+buffers but before writing the commit record. This loop walks the list of
+committing checkpoints and needs to block waiting for checkpoints to complete
+their commit record write. As a result it needs a lock and a wait variable.
+Log force sequencing also requires the same lock, list walk, and blocking
+mechanism to ensure completion of checkpoints.
+
+These two sequencing operations can use the mechanism even though the events
+they are waiting for are different. The checkpoint commit record sequencing
+needs to wait until checkpoint contexts contain a commit LSN (obtained through
+completion of a commit record write) while log force sequencing needs to wait
+until previous checkpoint contexts are removed from the committing list (i.e.
+they’ve completed). A simple wait variable and broadcast wakeups (thundering
+herds) has been used to implement these two serialisation queues. They use the
+same lock as the CIL, too. If we see too much contention on the CIL lock, or
+too many context switches as a result of the broadcast wakeups these
+operations can be put under a new spinlock and given separate wait lists to
+reduce lock contention and the number of processes woken by the wrong event.
+
+Lifecycle Changes
+^^^^^^^^^^^^^^^^^
+
+The existing log item life cycle is as follows:
+
+::
+
+ 1. Transaction allocate
+ 2. Transaction reserve
+ 3. Lock item
+ 4. Join item to transaction
+ If not already attached,
+ Allocate log item
+ Attach log item to owner item
+ Attach log item to transaction
+ 5. Modify item
+ Record modifications in log item
+ 6. Transaction commit
+ Pin item in memory
+ Format item into log buffer
+ Write commit LSN into transaction
+ Unlock item
+ Attach transaction to log buffer
+
+ <log buffer IO dispatched>
+ <log buffer IO completes>
+
+ 7. Transaction completion
+ Mark log item committed
+ Insert log item into AIL
+ Write commit LSN into log item
+ Unpin log item
+ 8. AIL traversal
+ Lock item
+ Mark log item clean
+ Flush item to disk
+
+ <item IO completion>
+
+ 9. Log item removed from AIL
+ Moves log tail
+ Item unlocked
+
+Essentially, steps 1-6 operate independently from step 7, which is also
+independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9 at
+the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur at the
+same time. If the log item is in the AIL or between steps 6 and 7 and steps
+1-6 are re-entered, then the item is relogged. Only when steps 8-9 are entered
+and completed is the object considered clean.
+
+With delayed logging, there are new steps inserted into the life cycle:
+
+::
+
+ 1. Transaction allocate
+ 2. Transaction reserve
+ 3. Lock item
+ 4. Join item to transaction
+ If not already attached,
+ Allocate log item
+ Attach log item to owner item
+ Attach log item to transaction
+ 5. Modify item
+ Record modifications in log item
+ 6. Transaction commit
+ Pin item in memory if not pinned in CIL
+ Format item into log vector + buffer
+ Attach log vector and buffer to log item
+ Insert log item into CIL
+ Write CIL context sequence into transaction
+ Unlock item
+
+ <next log force>
+
+ 7. CIL push
+ lock CIL flush
+ Chain log vectors and buffers together
+ Remove items from CIL
+ unlock CIL flush
+ write log vectors into log
+ sequence commit records
+ attach checkpoint context to log buffer
+
+ <log buffer IO dispatched>
+ <log buffer IO completes>
+
+ 8. Checkpoint completion
+ Mark log item committed
+ Insert item into AIL
+ Write commit LSN into log item
+ Unpin log item
+ 9. AIL traversal
+ Lock item
+ Mark log item clean
+ Flush item to disk
+ <item IO completion>
+ 10. Log item removed from AIL
+ Moves log tail
+ Item unlocked
+
+From this, it can be seen that the only life cycle differences between the two
+logging methods are in the middle of the life cycle - they still have the same
+beginning and end and execution constraints. The only differences are in the
+committing of the log items to the log itself and the completion processing.
+Hence delayed logging should not introduce any constraints on log item
+behaviour, allocation or freeing that don’t already exist.
+
+As a result of this zero-impact "insertion" of delayed logging infrastructure
+and the design of the internal structures to avoid on disk format changes, we
+can basically switch between delayed logging and the existing mechanism with a
+mount option. Fundamentally, there is no reason why the log manager would not
+be able to swap methods automatically and transparently depending on load
+characteristics, but this should not be necessary if delayed logging works as
+designed.
diff --git a/Documentation/filesystems/xfs-data-structures/overview.rst b/Documentation/filesystems/xfs-data-structures/overview.rst
index 8b3de9abcf39..457e81c0eb40 100644
--- a/Documentation/filesystems/xfs-data-structures/overview.rst
+++ b/Documentation/filesystems/xfs-data-structures/overview.rst
@@ -44,3 +44,4 @@ are tracked more simply and in larger chunks to reduce jitter in allocation
latency.
.. include:: self_describing_metadata.rst
+.. include:: delayed_logging.rst
diff --git a/Documentation/filesystems/xfs-delayed-logging-design.txt b/Documentation/filesystems/xfs-delayed-logging-design.txt
deleted file mode 100644
index 2ce36439c09f..000000000000
--- a/Documentation/filesystems/xfs-delayed-logging-design.txt
+++ /dev/null
@@ -1,793 +0,0 @@
-XFS Delayed Logging Design
---------------------------
-
-Introduction to Re-logging in XFS
----------------------------------
-
-XFS logging is a combination of logical and physical logging. Some objects,
-such as inodes and dquots, are logged in logical format where the details
-logged are made up of the changes to in-core structures rather than on-disk
-structures. Other objects - typically buffers - have their physical changes
-logged. The reason for these differences is to reduce the amount of log space
-required for objects that are frequently logged. Some parts of inodes are more
-frequently logged than others, and inodes are typically more frequently logged
-than any other object (except maybe the superblock buffer) so keeping the
-amount of metadata logged low is of prime importance.
-
-The reason that this is such a concern is that XFS allows multiple separate
-modifications to a single object to be carried in the log at any given time.
-This allows the log to avoid needing to flush each change to disk before
-recording a new change to the object. XFS does this via a method called
-"re-logging". Conceptually, this is quite simple - all it requires is that any
-new change to the object is recorded with a *new copy* of all the existing
-changes in the new transaction that is written to the log.
-
-That is, if we have a sequence of changes A through to F, and the object was
-written to disk after change D, we would see in the log the following series
-of transactions, their contents and the log sequence number (LSN) of the
-transaction:
-
- Transaction Contents LSN
- A A X
- B A+B X+n
- C A+B+C X+n+m
- D A+B+C+D X+n+m+o
- <object written to disk>
- E E Y (> X+n+m+o)
- F E+F Yٍ+p
-
-In other words, each time an object is relogged, the new transaction contains
-the aggregation of all the previous changes currently held only in the log.
-
-This relogging technique also allows objects to be moved forward in the log so
-that an object being relogged does not prevent the tail of the log from ever
-moving forward. This can be seen in the table above by the changing
-(increasing) LSN of each subsequent transaction - the LSN is effectively a
-direct encoding of the location in the log of the transaction.
-
-This relogging is also used to implement long-running, multiple-commit
-transactions. These transaction are known as rolling transactions, and require
-a special log reservation known as a permanent transaction reservation. A
-typical example of a rolling transaction is the removal of extents from an
-inode which can only be done at a rate of two extents per transaction because
-of reservation size limitations. Hence a rolling extent removal transaction
-keeps relogging the inode and btree buffers as they get modified in each
-removal operation. This keeps them moving forward in the log as the operation
-progresses, ensuring that current operation never gets blocked by itself if the
-log wraps around.
-
-Hence it can be seen that the relogging operation is fundamental to the correct
-working of the XFS journalling subsystem. From the above description, most
-people should be able to see why the XFS metadata operations writes so much to
-the log - repeated operations to the same objects write the same changes to
-the log over and over again. Worse is the fact that objects tend to get
-dirtier as they get relogged, so each subsequent transaction is writing more
-metadata into the log.
-
-Another feature of the XFS transaction subsystem is that most transactions are
-asynchronous. That is, they don't commit to disk until either a log buffer is
-filled (a log buffer can hold multiple transactions) or a synchronous operation
-forces the log buffers holding the transactions to disk. This means that XFS is
-doing aggregation of transactions in memory - batching them, if you like - to
-minimise the impact of the log IO on transaction throughput.
-
-The limitation on asynchronous transaction throughput is the number and size of
-log buffers made available by the log manager. By default there are 8 log
-buffers available and the size of each is 32kB - the size can be increased up
-to 256kB by use of a mount option.
-
-Effectively, this gives us the maximum bound of outstanding metadata changes
-that can be made to the filesystem at any point in time - if all the log
-buffers are full and under IO, then no more transactions can be committed until
-the current batch completes. It is now common for a single current CPU core to
-be to able to issue enough transactions to keep the log buffers full and under
-IO permanently. Hence the XFS journalling subsystem can be considered to be IO
-bound.
-
-Delayed Logging: Concepts
--------------------------
-
-The key thing to note about the asynchronous logging combined with the
-relogging technique XFS uses is that we can be relogging changed objects
-multiple times before they are committed to disk in the log buffers. If we
-return to the previous relogging example, it is entirely possible that
-transactions A through D are committed to disk in the same log buffer.
-
-That is, a single log buffer may contain multiple copies of the same object,
-but only one of those copies needs to be there - the last one "D", as it
-contains all the changes from the previous changes. In other words, we have one
-necessary copy in the log buffer, and three stale copies that are simply
-wasting space. When we are doing repeated operations on the same set of
-objects, these "stale objects" can be over 90% of the space used in the log
-buffers. It is clear that reducing the number of stale objects written to the
-log would greatly reduce the amount of metadata we write to the log, and this
-is the fundamental goal of delayed logging.
-
-From a conceptual point of view, XFS is already doing relogging in memory (where
-memory == log buffer), only it is doing it extremely inefficiently. It is using
-logical to physical formatting to do the relogging because there is no
-infrastructure to keep track of logical changes in memory prior to physically
-formatting the changes in a transaction to the log buffer. Hence we cannot avoid
-accumulating stale objects in the log buffers.
-
-Delayed logging is the name we've given to keeping and tracking transactional
-changes to objects in memory outside the log buffer infrastructure. Because of
-the relogging concept fundamental to the XFS journalling subsystem, this is
-actually relatively easy to do - all the changes to logged items are already
-tracked in the current infrastructure. The big problem is how to accumulate
-them and get them to the log in a consistent, recoverable manner.
-Describing the problems and how they have been solved is the focus of this
-document.
-
-One of the key changes that delayed logging makes to the operation of the
-journalling subsystem is that it disassociates the amount of outstanding
-metadata changes from the size and number of log buffers available. In other
-words, instead of there only being a maximum of 2MB of transaction changes not
-written to the log at any point in time, there may be a much greater amount
-being accumulated in memory. Hence the potential for loss of metadata on a
-crash is much greater than for the existing logging mechanism.
-
-It should be noted that this does not change the guarantee that log recovery
-will result in a consistent filesystem. What it does mean is that as far as the
-recovered filesystem is concerned, there may be many thousands of transactions
-that simply did not occur as a result of the crash. This makes it even more
-important that applications that care about their data use fsync() where they
-need to ensure application level data integrity is maintained.
-
-It should be noted that delayed logging is not an innovative new concept that
-warrants rigorous proofs to determine whether it is correct or not. The method
-of accumulating changes in memory for some period before writing them to the
-log is used effectively in many filesystems including ext3 and ext4. Hence
-no time is spent in this document trying to convince the reader that the
-concept is sound. Instead it is simply considered a "solved problem" and as
-such implementing it in XFS is purely an exercise in software engineering.
-
-The fundamental requirements for delayed logging in XFS are simple:
-
- 1. Reduce the amount of metadata written to the log by at least
- an order of magnitude.
- 2. Supply sufficient statistics to validate Requirement #1.
- 3. Supply sufficient new tracing infrastructure to be able to debug
- problems with the new code.
- 4. No on-disk format change (metadata or log format).
- 5. Enable and disable with a mount option.
- 6. No performance regressions for synchronous transaction workloads.
-
-Delayed Logging: Design
------------------------
-
-Storing Changes
-
-The problem with accumulating changes at a logical level (i.e. just using the
-existing log item dirty region tracking) is that when it comes to writing the
-changes to the log buffers, we need to ensure that the object we are formatting
-is not changing while we do this. This requires locking the object to prevent
-concurrent modification. Hence flushing the logical changes to the log would
-require us to lock every object, format them, and then unlock them again.
-
-This introduces lots of scope for deadlocks with transactions that are already
-running. For example, a transaction has object A locked and modified, but needs
-the delayed logging tracking lock to commit the transaction. However, the
-flushing thread has the delayed logging tracking lock already held, and is
-trying to get the lock on object A to flush it to the log buffer. This appears
-to be an unsolvable deadlock condition, and it was solving this problem that
-was the barrier to implementing delayed logging for so long.
-
-The solution is relatively simple - it just took a long time to recognise it.
-Put simply, the current logging code formats the changes to each item into an
-vector array that points to the changed regions in the item. The log write code
-simply copies the memory these vectors point to into the log buffer during
-transaction commit while the item is locked in the transaction. Instead of
-using the log buffer as the destination of the formatting code, we can use an
-allocated memory buffer big enough to fit the formatted vector.
-
-If we then copy the vector into the memory buffer and rewrite the vector to
-point to the memory buffer rather than the object itself, we now have a copy of
-the changes in a format that is compatible with the log buffer writing code.
-that does not require us to lock the item to access. This formatting and
-rewriting can all be done while the object is locked during transaction commit,
-resulting in a vector that is transactionally consistent and can be accessed
-without needing to lock the owning item.
-
-Hence we avoid the need to lock items when we need to flush outstanding
-asynchronous transactions to the log. The differences between the existing
-formatting method and the delayed logging formatting can be seen in the
-diagram below.
-
-Current format log vector:
-
-Object +---------------------------------------------+
-Vector 1 +----+
-Vector 2 +----+
-Vector 3 +----------+
-
-After formatting:
-
-Log Buffer +-V1-+-V2-+----V3----+
-
-Delayed logging vector:
-
-Object +---------------------------------------------+
-Vector 1 +----+
-Vector 2 +----+
-Vector 3 +----------+
-
-After formatting:
-
-Memory Buffer +-V1-+-V2-+----V3----+
-Vector 1 +----+
-Vector 2 +----+
-Vector 3 +----------+
-
-The memory buffer and associated vector need to be passed as a single object,
-but still need to be associated with the parent object so if the object is
-relogged we can replace the current memory buffer with a new memory buffer that
-contains the latest changes.
-
-The reason for keeping the vector around after we've formatted the memory
-buffer is to support splitting vectors across log buffer boundaries correctly.
-If we don't keep the vector around, we do not know where the region boundaries
-are in the item, so we'd need a new encapsulation method for regions in the log
-buffer writing (i.e. double encapsulation). This would be an on-disk format
-change and as such is not desirable. It also means we'd have to write the log
-region headers in the formatting stage, which is problematic as there is per
-region state that needs to be placed into the headers during the log write.
-
-Hence we need to keep the vector, but by attaching the memory buffer to it and
-rewriting the vector addresses to point at the memory buffer we end up with a
-self-describing object that can be passed to the log buffer write code to be
-handled in exactly the same manner as the existing log vectors are handled.
-Hence we avoid needing a new on-disk format to handle items that have been
-relogged in memory.
-
-
-Tracking Changes
-
-Now that we can record transactional changes in memory in a form that allows
-them to be used without limitations, we need to be able to track and accumulate
-them so that they can be written to the log at some later point in time. The
-log item is the natural place to store this vector and buffer, and also makes sense
-to be the object that is used to track committed objects as it will always
-exist once the object has been included in a transaction.
-
-The log item is already used to track the log items that have been written to
-the log but not yet written to disk. Such log items are considered "active"
-and as such are stored in the Active Item List (AIL) which is a LSN-ordered
-double linked list. Items are inserted into this list during log buffer IO
-completion, after which they are unpinned and can be written to disk. An object
-that is in the AIL can be relogged, which causes the object to be pinned again
-and then moved forward in the AIL when the log buffer IO completes for that
-transaction.
-
-Essentially, this shows that an item that is in the AIL can still be modified
-and relogged, so any tracking must be separate to the AIL infrastructure. As
-such, we cannot reuse the AIL list pointers for tracking committed items, nor
-can we store state in any field that is protected by the AIL lock. Hence the
-committed item tracking needs it's own locks, lists and state fields in the log
-item.
-
-Similar to the AIL, tracking of committed items is done through a new list
-called the Committed Item List (CIL). The list tracks log items that have been
-committed and have formatted memory buffers attached to them. It tracks objects
-in transaction commit order, so when an object is relogged it is removed from
-it's place in the list and re-inserted at the tail. This is entirely arbitrary
-and done to make it easy for debugging - the last items in the list are the
-ones that are most recently modified. Ordering of the CIL is not necessary for
-transactional integrity (as discussed in the next section) so the ordering is
-done for convenience/sanity of the developers.
-
-
-Delayed Logging: Checkpoints
-
-When we have a log synchronisation event, commonly known as a "log force",
-all the items in the CIL must be written into the log via the log buffers.
-We need to write these items in the order that they exist in the CIL, and they
-need to be written as an atomic transaction. The need for all the objects to be
-written as an atomic transaction comes from the requirements of relogging and
-log replay - all the changes in all the objects in a given transaction must
-either be completely replayed during log recovery, or not replayed at all. If
-a transaction is not replayed because it is not complete in the log, then
-no later transactions should be replayed, either.
-
-To fulfill this requirement, we need to write the entire CIL in a single log
-transaction. Fortunately, the XFS log code has no fixed limit on the size of a
-transaction, nor does the log replay code. The only fundamental limit is that
-the transaction cannot be larger than just under half the size of the log. The
-reason for this limit is that to find the head and tail of the log, there must
-be at least one complete transaction in the log at any given time. If a
-transaction is larger than half the log, then there is the possibility that a
-crash during the write of a such a transaction could partially overwrite the
-only complete previous transaction in the log. This will result in a recovery
-failure and an inconsistent filesystem and hence we must enforce the maximum
-size of a checkpoint to be slightly less than a half the log.
-
-Apart from this size requirement, a checkpoint transaction looks no different
-to any other transaction - it contains a transaction header, a series of
-formatted log items and a commit record at the tail. From a recovery
-perspective, the checkpoint transaction is also no different - just a lot
-bigger with a lot more items in it. The worst case effect of this is that we
-might need to tune the recovery transaction object hash size.
-
-Because the checkpoint is just another transaction and all the changes to log
-items are stored as log vectors, we can use the existing log buffer writing
-code to write the changes into the log. To do this efficiently, we need to
-minimise the time we hold the CIL locked while writing the checkpoint
-transaction. The current log write code enables us to do this easily with the
-way it separates the writing of the transaction contents (the log vectors) from
-the transaction commit record, but tracking this requires us to have a
-per-checkpoint context that travels through the log write process through to
-checkpoint completion.
-
-Hence a checkpoint has a context that tracks the state of the current
-checkpoint from initiation to checkpoint completion. A new context is initiated
-at the same time a checkpoint transaction is started. That is, when we remove
-all the current items from the CIL during a checkpoint operation, we move all
-those changes into the current checkpoint context. We then initialise a new
-context and attach that to the CIL for aggregation of new transactions.
-
-This allows us to unlock the CIL immediately after transfer of all the
-committed items and effectively allow new transactions to be issued while we
-are formatting the checkpoint into the log. It also allows concurrent
-checkpoints to be written into the log buffers in the case of log force heavy
-workloads, just like the existing transaction commit code does. This, however,
-requires that we strictly order the commit records in the log so that
-checkpoint sequence order is maintained during log replay.
-
-To ensure that we can be writing an item into a checkpoint transaction at
-the same time another transaction modifies the item and inserts the log item
-into the new CIL, then checkpoint transaction commit code cannot use log items
-to store the list of log vectors that need to be written into the transaction.
-Hence log vectors need to be able to be chained together to allow them to be
-detached from the log items. That is, when the CIL is flushed the memory
-buffer and log vector attached to each log item needs to be attached to the
-checkpoint context so that the log item can be released. In diagrammatic form,
-the CIL would look like this before the flush:
-
- CIL Head
- |
- V
- Log Item <-> log vector 1 -> memory buffer
- | -> vector array
- V
- Log Item <-> log vector 2 -> memory buffer
- | -> vector array
- V
- ......
- |
- V
- Log Item <-> log vector N-1 -> memory buffer
- | -> vector array
- V
- Log Item <-> log vector N -> memory buffer
- -> vector array
-
-And after the flush the CIL head is empty, and the checkpoint context log
-vector list would look like:
-
- Checkpoint Context
- |
- V
- log vector 1 -> memory buffer
- | -> vector array
- | -> Log Item
- V
- log vector 2 -> memory buffer
- | -> vector array
- | -> Log Item
- V
- ......
- |
- V
- log vector N-1 -> memory buffer
- | -> vector array
- | -> Log Item
- V
- log vector N -> memory buffer
- -> vector array
- -> Log Item
-
-Once this transfer is done, the CIL can be unlocked and new transactions can
-start, while the checkpoint flush code works over the log vector chain to
-commit the checkpoint.
-
-Once the checkpoint is written into the log buffers, the checkpoint context is
-attached to the log buffer that the commit record was written to along with a
-completion callback. Log IO completion will call that callback, which can then
-run transaction committed processing for the log items (i.e. insert into AIL
-and unpin) in the log vector chain and then free the log vector chain and
-checkpoint context.
-
-Discussion Point: I am uncertain as to whether the log item is the most
-efficient way to track vectors, even though it seems like the natural way to do
-it. The fact that we walk the log items (in the CIL) just to chain the log
-vectors and break the link between the log item and the log vector means that
-we take a cache line hit for the log item list modification, then another for
-the log vector chaining. If we track by the log vectors, then we only need to
-break the link between the log item and the log vector, which means we should
-dirty only the log item cachelines. Normally I wouldn't be concerned about one
-vs two dirty cachelines except for the fact I've seen upwards of 80,000 log
-vectors in one checkpoint transaction. I'd guess this is a "measure and
-compare" situation that can be done after a working and reviewed implementation
-is in the dev tree....
-
-Delayed Logging: Checkpoint Sequencing
-
-One of the key aspects of the XFS transaction subsystem is that it tags
-committed transactions with the log sequence number of the transaction commit.
-This allows transactions to be issued asynchronously even though there may be
-future operations that cannot be completed until that transaction is fully
-committed to the log. In the rare case that a dependent operation occurs (e.g.
-re-using a freed metadata extent for a data extent), a special, optimised log
-force can be issued to force the dependent transaction to disk immediately.
-
-To do this, transactions need to record the LSN of the commit record of the
-transaction. This LSN comes directly from the log buffer the transaction is
-written into. While this works just fine for the existing transaction
-mechanism, it does not work for delayed logging because transactions are not
-written directly into the log buffers. Hence some other method of sequencing
-transactions is required.
-
-As discussed in the checkpoint section, delayed logging uses per-checkpoint
-contexts, and as such it is simple to assign a sequence number to each
-checkpoint. Because the switching of checkpoint contexts must be done
-atomically, it is simple to ensure that each new context has a monotonically
-increasing sequence number assigned to it without the need for an external
-atomic counter - we can just take the current context sequence number and add
-one to it for the new context.
-
-Then, instead of assigning a log buffer LSN to the transaction commit LSN
-during the commit, we can assign the current checkpoint sequence. This allows
-operations that track transactions that have not yet completed know what
-checkpoint sequence needs to be committed before they can continue. As a
-result, the code that forces the log to a specific LSN now needs to ensure that
-the log forces to a specific checkpoint.
-
-To ensure that we can do this, we need to track all the checkpoint contexts
-that are currently committing to the log. When we flush a checkpoint, the
-context gets added to a "committing" list which can be searched. When a
-checkpoint commit completes, it is removed from the committing list. Because
-the checkpoint context records the LSN of the commit record for the checkpoint,
-we can also wait on the log buffer that contains the commit record, thereby
-using the existing log force mechanisms to execute synchronous forces.
-
-It should be noted that the synchronous forces may need to be extended with
-mitigation algorithms similar to the current log buffer code to allow
-aggregation of multiple synchronous transactions if there are already
-synchronous transactions being flushed. Investigation of the performance of the
-current design is needed before making any decisions here.
-
-The main concern with log forces is to ensure that all the previous checkpoints
-are also committed to disk before the one we need to wait for. Therefore we
-need to check that all the prior contexts in the committing list are also
-complete before waiting on the one we need to complete. We do this
-synchronisation in the log force code so that we don't need to wait anywhere
-else for such serialisation - it only matters when we do a log force.
-
-The only remaining complexity is that a log force now also has to handle the
-case where the forcing sequence number is the same as the current context. That
-is, we need to flush the CIL and potentially wait for it to complete. This is a
-simple addition to the existing log forcing code to check the sequence numbers
-and push if required. Indeed, placing the current sequence checkpoint flush in
-the log force code enables the current mechanism for issuing synchronous
-transactions to remain untouched (i.e. commit an asynchronous transaction, then
-force the log at the LSN of that transaction) and so the higher level code
-behaves the same regardless of whether delayed logging is being used or not.
-
-Delayed Logging: Checkpoint Log Space Accounting
-
-The big issue for a checkpoint transaction is the log space reservation for the
-transaction. We don't know how big a checkpoint transaction is going to be
-ahead of time, nor how many log buffers it will take to write out, nor the
-number of split log vector regions are going to be used. We can track the
-amount of log space required as we add items to the commit item list, but we
-still need to reserve the space in the log for the checkpoint.
-
-A typical transaction reserves enough space in the log for the worst case space
-usage of the transaction. The reservation accounts for log record headers,
-transaction and region headers, headers for split regions, buffer tail padding,
-etc. as well as the actual space for all the changed metadata in the
-transaction. While some of this is fixed overhead, much of it is dependent on
-the size of the transaction and the number of regions being logged (the number
-of log vectors in the transaction).
-
-An example of the differences would be logging directory changes versus logging
-inode changes. If you modify lots of inode cores (e.g. chmod -R g+w *), then
-there are lots of transactions that only contain an inode core and an inode log
-format structure. That is, two vectors totaling roughly 150 bytes. If we modify
-10,000 inodes, we have about 1.5MB of metadata to write in 20,000 vectors. Each
-vector is 12 bytes, so the total to be logged is approximately 1.75MB. In
-comparison, if we are logging full directory buffers, they are typically 4KB
-each, so we in 1.5MB of directory buffers we'd have roughly 400 buffers and a
-buffer format structure for each buffer - roughly 800 vectors or 1.51MB total
-space. From this, it should be obvious that a static log space reservation is
-not particularly flexible and is difficult to select the "optimal value" for
-all workloads.
-
-Further, if we are going to use a static reservation, which bit of the entire
-reservation does it cover? We account for space used by the transaction
-reservation by tracking the space currently used by the object in the CIL and
-then calculating the increase or decrease in space used as the object is
-relogged. This allows for a checkpoint reservation to only have to account for
-log buffer metadata used such as log header records.
-
-However, even using a static reservation for just the log metadata is
-problematic. Typically log record headers use at least 16KB of log space per
-1MB of log space consumed (512 bytes per 32k) and the reservation needs to be
-large enough to handle arbitrary sized checkpoint transactions. This
-reservation needs to be made before the checkpoint is started, and we need to
-be able to reserve the space without sleeping. For a 8MB checkpoint, we need a
-reservation of around 150KB, which is a non-trivial amount of space.
-
-A static reservation needs to manipulate the log grant counters - we can take a
-permanent reservation on the space, but we still need to make sure we refresh
-the write reservation (the actual space available to the transaction) after
-every checkpoint transaction completion. Unfortunately, if this space is not
-available when required, then the regrant code will sleep waiting for it.
-
-The problem with this is that it can lead to deadlocks as we may need to commit
-checkpoints to be able to free up log space (refer back to the description of
-rolling transactions for an example of this). Hence we *must* always have
-space available in the log if we are to use static reservations, and that is
-very difficult and complex to arrange. It is possible to do, but there is a
-simpler way.
-
-The simpler way of doing this is tracking the entire log space used by the
-items in the CIL and using this to dynamically calculate the amount of log
-space required by the log metadata. If this log metadata space changes as a
-result of a transaction commit inserting a new memory buffer into the CIL, then
-the difference in space required is removed from the transaction that causes
-the change. Transactions at this level will *always* have enough space
-available in their reservation for this as they have already reserved the
-maximal amount of log metadata space they require, and such a delta reservation
-will always be less than or equal to the maximal amount in the reservation.
-
-Hence we can grow the checkpoint transaction reservation dynamically as items
-are added to the CIL and avoid the need for reserving and regranting log space
-up front. This avoids deadlocks and removes a blocking point from the
-checkpoint flush code.
-
-As mentioned early, transactions can't grow to more than half the size of the
-log. Hence as part of the reservation growing, we need to also check the size
-of the reservation against the maximum allowed transaction size. If we reach
-the maximum threshold, we need to push the CIL to the log. This is effectively
-a "background flush" and is done on demand. This is identical to
-a CIL push triggered by a log force, only that there is no waiting for the
-checkpoint commit to complete. This background push is checked and executed by
-transaction commit code.
-
-If the transaction subsystem goes idle while we still have items in the CIL,
-they will be flushed by the periodic log force issued by the xfssyncd. This log
-force will push the CIL to disk, and if the transaction subsystem stays idle,
-allow the idle log to be covered (effectively marked clean) in exactly the same
-manner that is done for the existing logging method. A discussion point is
-whether this log force needs to be done more frequently than the current rate
-which is once every 30s.
-
-
-Delayed Logging: Log Item Pinning
-
-Currently log items are pinned during transaction commit while the items are
-still locked. This happens just after the items are formatted, though it could
-be done any time before the items are unlocked. The result of this mechanism is
-that items get pinned once for every transaction that is committed to the log
-buffers. Hence items that are relogged in the log buffers will have a pin count
-for every outstanding transaction they were dirtied in. When each of these
-transactions is completed, they will unpin the item once. As a result, the item
-only becomes unpinned when all the transactions complete and there are no
-pending transactions. Thus the pinning and unpinning of a log item is symmetric
-as there is a 1:1 relationship with transaction commit and log item completion.
-
-For delayed logging, however, we have an asymmetric transaction commit to
-completion relationship. Every time an object is relogged in the CIL it goes
-through the commit process without a corresponding completion being registered.
-That is, we now have a many-to-one relationship between transaction commit and
-log item completion. The result of this is that pinning and unpinning of the
-log items becomes unbalanced if we retain the "pin on transaction commit, unpin
-on transaction completion" model.
-
-To keep pin/unpin symmetry, the algorithm needs to change to a "pin on
-insertion into the CIL, unpin on checkpoint completion". In other words, the
-pinning and unpinning becomes symmetric around a checkpoint context. We have to
-pin the object the first time it is inserted into the CIL - if it is already in
-the CIL during a transaction commit, then we do not pin it again. Because there
-can be multiple outstanding checkpoint contexts, we can still see elevated pin
-counts, but as each checkpoint completes the pin count will retain the correct
-value according to it's context.
-
-Just to make matters more slightly more complex, this checkpoint level context
-for the pin count means that the pinning of an item must take place under the
-CIL commit/flush lock. If we pin the object outside this lock, we cannot
-guarantee which context the pin count is associated with. This is because of
-the fact pinning the item is dependent on whether the item is present in the
-current CIL or not. If we don't pin the CIL first before we check and pin the
-object, we have a race with CIL being flushed between the check and the pin
-(or not pinning, as the case may be). Hence we must hold the CIL flush/commit
-lock to guarantee that we pin the items correctly.
-
-Delayed Logging: Concurrent Scalability
-
-A fundamental requirement for the CIL is that accesses through transaction
-commits must scale to many concurrent commits. The current transaction commit
-code does not break down even when there are transactions coming from 2048
-processors at once. The current transaction code does not go any faster than if
-there was only one CPU using it, but it does not slow down either.
-
-As a result, the delayed logging transaction commit code needs to be designed
-for concurrency from the ground up. It is obvious that there are serialisation
-points in the design - the three important ones are:
-
- 1. Locking out new transaction commits while flushing the CIL
- 2. Adding items to the CIL and updating item space accounting
- 3. Checkpoint commit ordering
-
-Looking at the transaction commit and CIL flushing interactions, it is clear
-that we have a many-to-one interaction here. That is, the only restriction on
-the number of concurrent transactions that can be trying to commit at once is
-the amount of space available in the log for their reservations. The practical
-limit here is in the order of several hundred concurrent transactions for a
-128MB log, which means that it is generally one per CPU in a machine.
-
-The amount of time a transaction commit needs to hold out a flush is a
-relatively long period of time - the pinning of log items needs to be done
-while we are holding out a CIL flush, so at the moment that means it is held
-across the formatting of the objects into memory buffers (i.e. while memcpy()s
-are in progress). Ultimately a two pass algorithm where the formatting is done
-separately to the pinning of objects could be used to reduce the hold time of
-the transaction commit side.
-
-Because of the number of potential transaction commit side holders, the lock
-really needs to be a sleeping lock - if the CIL flush takes the lock, we do not
-want every other CPU in the machine spinning on the CIL lock. Given that
-flushing the CIL could involve walking a list of tens of thousands of log
-items, it will get held for a significant time and so spin contention is a
-significant concern. Preventing lots of CPUs spinning doing nothing is the
-main reason for choosing a sleeping lock even though nothing in either the
-transaction commit or CIL flush side sleeps with the lock held.
-
-It should also be noted that CIL flushing is also a relatively rare operation
-compared to transaction commit for asynchronous transaction workloads - only
-time will tell if using a read-write semaphore for exclusion will limit
-transaction commit concurrency due to cache line bouncing of the lock on the
-read side.
-
-The second serialisation point is on the transaction commit side where items
-are inserted into the CIL. Because transactions can enter this code
-concurrently, the CIL needs to be protected separately from the above
-commit/flush exclusion. It also needs to be an exclusive lock but it is only
-held for a very short time and so a spin lock is appropriate here. It is
-possible that this lock will become a contention point, but given the short
-hold time once per transaction I think that contention is unlikely.
-
-The final serialisation point is the checkpoint commit record ordering code
-that is run as part of the checkpoint commit and log force sequencing. The code
-path that triggers a CIL flush (i.e. whatever triggers the log force) will enter
-an ordering loop after writing all the log vectors into the log buffers but
-before writing the commit record. This loop walks the list of committing
-checkpoints and needs to block waiting for checkpoints to complete their commit
-record write. As a result it needs a lock and a wait variable. Log force
-sequencing also requires the same lock, list walk, and blocking mechanism to
-ensure completion of checkpoints.
-
-These two sequencing operations can use the mechanism even though the
-events they are waiting for are different. The checkpoint commit record
-sequencing needs to wait until checkpoint contexts contain a commit LSN
-(obtained through completion of a commit record write) while log force
-sequencing needs to wait until previous checkpoint contexts are removed from
-the committing list (i.e. they've completed). A simple wait variable and
-broadcast wakeups (thundering herds) has been used to implement these two
-serialisation queues. They use the same lock as the CIL, too. If we see too
-much contention on the CIL lock, or too many context switches as a result of
-the broadcast wakeups these operations can be put under a new spinlock and
-given separate wait lists to reduce lock contention and the number of processes
-woken by the wrong event.
-
-
-Lifecycle Changes
-
-The existing log item life cycle is as follows:
-
- 1. Transaction allocate
- 2. Transaction reserve
- 3. Lock item
- 4. Join item to transaction
- If not already attached,
- Allocate log item
- Attach log item to owner item
- Attach log item to transaction
- 5. Modify item
- Record modifications in log item
- 6. Transaction commit
- Pin item in memory
- Format item into log buffer
- Write commit LSN into transaction
- Unlock item
- Attach transaction to log buffer
-
- <log buffer IO dispatched>
- <log buffer IO completes>
-
- 7. Transaction completion
- Mark log item committed
- Insert log item into AIL
- Write commit LSN into log item
- Unpin log item
- 8. AIL traversal
- Lock item
- Mark log item clean
- Flush item to disk
-
- <item IO completion>
-
- 9. Log item removed from AIL
- Moves log tail
- Item unlocked
-
-Essentially, steps 1-6 operate independently from step 7, which is also
-independent of steps 8-9. An item can be locked in steps 1-6 or steps 8-9
-at the same time step 7 is occurring, but only steps 1-6 or 8-9 can occur
-at the same time. If the log item is in the AIL or between steps 6 and 7
-and steps 1-6 are re-entered, then the item is relogged. Only when steps 8-9
-are entered and completed is the object considered clean.
-
-With delayed logging, there are new steps inserted into the life cycle:
-
- 1. Transaction allocate
- 2. Transaction reserve
- 3. Lock item
- 4. Join item to transaction
- If not already attached,
- Allocate log item
- Attach log item to owner item
- Attach log item to transaction
- 5. Modify item
- Record modifications in log item
- 6. Transaction commit
- Pin item in memory if not pinned in CIL
- Format item into log vector + buffer
- Attach log vector and buffer to log item
- Insert log item into CIL
- Write CIL context sequence into transaction
- Unlock item
-
- <next log force>
-
- 7. CIL push
- lock CIL flush
- Chain log vectors and buffers together
- Remove items from CIL
- unlock CIL flush
- write log vectors into log
- sequence commit records
- attach checkpoint context to log buffer
-
- <log buffer IO dispatched>
- <log buffer IO completes>
-
- 8. Checkpoint completion
- Mark log item committed
- Insert item into AIL
- Write commit LSN into log item
- Unpin log item
- 9. AIL traversal
- Lock item
- Mark log item clean
- Flush item to disk
- <item IO completion>
- 10. Log item removed from AIL
- Moves log tail
- Item unlocked
-
-From this, it can be seen that the only life cycle differences between the two
-logging methods are in the middle of the life cycle - they still have the same
-beginning and end and execution constraints. The only differences are in the
-committing of the log items to the log itself and the completion processing.
-Hence delayed logging should not introduce any constraints on log item
-behaviour, allocation or freeing that don't already exist.
-
-As a result of this zero-impact "insertion" of delayed logging infrastructure
-and the design of the internal structures to avoid on disk format changes, we
-can basically switch between delayed logging and the existing mechanism with a
-mount option. Fundamentally, there is no reason why the log manager would not
-be able to swap methods automatically and transparently depending on load
-characteristics, but this should not be necessary if delayed logging works as
-designed.
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 05/22] docs: add XFS shared data block chapter to DS&A book
2018-10-04 3:25 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
` (2 preceding siblings ...)
2018-10-04 3:25 ` [PATCH 04/22] docs: add XFS delayed logging design " Darrick J. Wong
@ 2018-10-04 3:25 ` Darrick J. Wong
2018-10-04 3:25 ` [PATCH 06/22] docs: add XFS online repair " Darrick J. Wong
` (2 subsequent siblings)
6 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:25 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
From: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
.../filesystems/xfs-data-structures/overview.rst | 1
.../filesystems/xfs-data-structures/reflink.rst | 43 ++++++++++++++++++++
2 files changed, 44 insertions(+)
create mode 100644 Documentation/filesystems/xfs-data-structures/reflink.rst
diff --git a/Documentation/filesystems/xfs-data-structures/overview.rst b/Documentation/filesystems/xfs-data-structures/overview.rst
index 457e81c0eb40..d8d668ec6097 100644
--- a/Documentation/filesystems/xfs-data-structures/overview.rst
+++ b/Documentation/filesystems/xfs-data-structures/overview.rst
@@ -45,3 +45,4 @@ latency.
.. include:: self_describing_metadata.rst
.. include:: delayed_logging.rst
+.. include:: reflink.rst
diff --git a/Documentation/filesystems/xfs-data-structures/reflink.rst b/Documentation/filesystems/xfs-data-structures/reflink.rst
new file mode 100644
index 000000000000..653b3def7e6e
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/reflink.rst
@@ -0,0 +1,43 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Sharing Data Blocks
+-------------------
+
+On a traditional filesystem, there is a 1:1 mapping between a logical block
+offset in a file and a physical block on disk, which is to say that physical
+blocks are not shared. However, there exist various use cases for being able
+to share blocks between files — deduplicating files saves space on archival
+systems; creating space-efficient clones of disk images for virtual machines
+and containers facilitates efficient datacenters; and deferring the payment of
+the allocation cost of a file system tree copy as long as possible makes
+regular work faster. In all of these cases, a write to one of the shared
+copies **must** not affect the other shared copies, which means that writes to
+shared blocks must employ a copy-on-write strategy. Sharing blocks in this
+manner is commonly referred to as "reflinking".
+
+XFS implements block sharing in a fairly straightforward manner. All existing
+data fork structures remain unchanged, save for the addition of a
+per-allocation group `reference count B+tree <#reference-count-b-tree>`__. This
+data structure tracks reference counts for all shared physical blocks, with a
+few rules to maintain compatibility with existing code: If a block is free, it
+will be tracked in the free space B+trees. If a block is owned by a single
+file, it appears in neither the free space nor the reference count B+trees. If
+a block is shared, it will appear in the reference count B+tree with a
+reference count >= 2. The first two cases are established precedent in XFS, so
+the third case is the only behavioral change.
+
+When a filesystem block is shared, the block mapping in the destination file
+is updated to point to that filesystem block and the reference count B+tree
+records are updated to reflect the increased reference count. If a shared
+block is written, a new block will be allocated, the dirty data written to
+this new block, and the file’s block mapping updated to point to the new
+block. If a shared block is unmapped, the reference count records are updated
+to reflect the decreased reference count and the block is also freed if its
+reference count becomes zero. This enables users to create space efficient
+clones of disk images and to copy filesystem subtrees quickly, using the
+standard Linux coreutils packages.
+
+Deduplication employs the same mechanism to share blocks and copy them at
+write time. However, the kernel confirms that the contents of both files are
+identical before updating the destination file’s mapping. This enables XFS to
+be used by userspace deduplication programs such as duperemove.
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 06/22] docs: add XFS online repair chapter to DS&A book
2018-10-04 3:25 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
` (3 preceding siblings ...)
2018-10-04 3:25 ` [PATCH 05/22] docs: add XFS shared data block chapter " Darrick J. Wong
@ 2018-10-04 3:25 ` Darrick J. Wong
2018-10-04 3:26 ` [PATCH 07/22] docs: add XFS common types and magic numbers " Darrick J. Wong
2018-10-04 3:26 ` [PATCH 08/22] docs: add XFS testing chapter to the " Darrick J. Wong
6 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:25 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
From: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
.../filesystems/xfs-data-structures/overview.rst | 1
.../xfs-data-structures/reconstruction.rst | 68 ++++++++++++++++++++
2 files changed, 69 insertions(+)
create mode 100644 Documentation/filesystems/xfs-data-structures/reconstruction.rst
diff --git a/Documentation/filesystems/xfs-data-structures/overview.rst b/Documentation/filesystems/xfs-data-structures/overview.rst
index d8d668ec6097..b1b3f711638b 100644
--- a/Documentation/filesystems/xfs-data-structures/overview.rst
+++ b/Documentation/filesystems/xfs-data-structures/overview.rst
@@ -46,3 +46,4 @@ latency.
.. include:: self_describing_metadata.rst
.. include:: delayed_logging.rst
.. include:: reflink.rst
+.. include:: reconstruction.rst
diff --git a/Documentation/filesystems/xfs-data-structures/reconstruction.rst b/Documentation/filesystems/xfs-data-structures/reconstruction.rst
new file mode 100644
index 000000000000..10a7a728c50c
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/reconstruction.rst
@@ -0,0 +1,68 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Metadata Reconstruction
+-----------------------
+
+ **Note**
+
+ This is a theoretical discussion of how reconstruction could work; none of
+ this is implemented as of 2018.
+
+A simple UNIX filesystem can be thought of in terms of a directed acyclic
+graph. To a first approximation, there exists a root directory node, which
+points to other nodes. Those other nodes can themselves be directories or they
+can be files. Each file, in turn, points to data blocks.
+
+XFS adds a few more details to this picture:
+
+- The real root(s) of an XFS filesystem are the allocation group headers
+ (superblock, AGF, AGI, AGFL).
+
+- Each allocation group’s headers point to various per-AG B+trees (free
+ space, inode, free inodes, free list, etc.)
+
+- The free space B+trees point to unused extents;
+
+- The inode B+trees point to blocks containing inode chunks;
+
+- All superblocks point to the root directory and the log;
+
+- Hardlinks mean that multiple directories can point to a single file node;
+
+- File data block pointers are indexed by file offset;
+
+- Files and directories can have a second collection of pointers to data
+ blocks which contain extended attributes;
+
+- Large directories require multiple data blocks to store all the
+ subpointers;
+
+- Still larger directories use high-offset data blocks to store a B+tree of
+ hashes to directory entries;
+
+- Large extended attribute forks similarly use high-offset data blocks to
+ store a B+tree of hashes to attribute keys; and
+
+- Symbolic links can point to data blocks.
+
+The beauty of this massive graph structure is that under normal circumstances,
+everything known to the filesystem is discoverable (access controls
+notwithstanding) from the root. The major weakness of this structure of course
+is that breaking a edge in the graph can render entire subtrees inaccessible.
+xfs\_repair “recovers” from broken directories by scanning for unlinked inodes
+and connecting them to /lost+found, but this isn’t sufficiently general to
+recover from breaks in other parts of the graph structure. Wouldn’t it be
+useful to have back pointers as a secondary data structure? The current repair
+strategy is to reconstruct whatever can be rebuilt, but to scrap anything that
+doesn’t check out.
+
+The `reverse-mapping B+tree <#reverse-mapping-b-tree>`__ fills in part of the
+puzzle. Since it contains copies of every entry in each inode’s data and
+attribute forks, we can fix a corrupted block map with these records.
+Furthermore, if the inode B+trees become corrupt, it is possible to visit all
+inode chunks using the reverse-mapping data. Should XFS ever gain the ability
+to store parent directory information in each inode, it also becomes possible
+to resurrect damaged directory trees, which should reduce the complaints about
+inodes ending up in /lost+found. Everything else in the per-AG primary
+metadata can already be reconstructed via xfs\_repair. Hopefully,
+reconstruction will not turn out to be a fool’s errand.
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 07/22] docs: add XFS common types and magic numbers to DS&A book
2018-10-04 3:25 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
` (4 preceding siblings ...)
2018-10-04 3:25 ` [PATCH 06/22] docs: add XFS online repair " Darrick J. Wong
@ 2018-10-04 3:26 ` Darrick J. Wong
2018-10-04 3:26 ` [PATCH 08/22] docs: add XFS testing chapter to the " Darrick J. Wong
6 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:26 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
From: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
.../xfs-data-structures/common_types.rst | 61 ++++
.../filesystems/xfs-data-structures/magic.rst | 277 ++++++++++++++++++++
.../filesystems/xfs-data-structures/overview.rst | 2
3 files changed, 340 insertions(+)
create mode 100644 Documentation/filesystems/xfs-data-structures/common_types.rst
create mode 100644 Documentation/filesystems/xfs-data-structures/magic.rst
diff --git a/Documentation/filesystems/xfs-data-structures/common_types.rst b/Documentation/filesystems/xfs-data-structures/common_types.rst
new file mode 100644
index 000000000000..63de847924c6
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/common_types.rst
@@ -0,0 +1,61 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Common XFS Types
+----------------
+
+All the following XFS types can be found in xfs\_types.h. NULL values are
+always -1 on disk (ie. all bits for the value set to one).
+
+**xfs\_ino\_t**
+ Unsigned 64 bit absolute `inode number <#inode-numbers>`__.
+
+**xfs\_off\_t**
+ Signed 64 bit file offset.
+
+**xfs\_daddr\_t**
+ Signed 64 bit disk address (sectors).
+
+**xfs\_agnumber\_t**
+ Unsigned 32 bit `AG number <#allocation-groups>`__.
+
+**xfs\_agblock\_t**
+ Unsigned 32 bit AG relative block number.
+
+**xfs\_extlen\_t**
+ Unsigned 32 bit `extent <#data-extents>`__ length in blocks.
+
+**xfs\_extnum\_t**
+ Signed 32 bit number of extents in a data fork.
+
+**xfs\_aextnum\_t**
+ Signed 16 bit number of extents in an attribute fork.
+
+**xfs\_dablk\_t**
+ Unsigned 32 bit block number for `directories <#directories>`__ and
+ `extended attributes <#extended-attributes>`__.
+
+**xfs\_dahash\_t**
+ Unsigned 32 bit hash of a directory file name or extended attribute name.
+
+**xfs\_fsblock\_t**
+ Unsigned 64 bit filesystem block number combining `AG
+ number <#allocation-groups>`__ and block offset into the AG.
+
+**xfs\_rfsblock\_t**
+ Unsigned 64 bit raw filesystem block number.
+
+**xfs\_rtblock\_t**
+ Unsigned 64 bit extent number in the `real-time <#real-time-devices>`__
+ sub-volume.
+
+**xfs\_fileoff\_t**
+ Unsigned 64 bit block offset into a file.
+
+**xfs\_filblks\_t**
+ Unsigned 64 bit block count for a file.
+
+**uuid\_t**
+ 16-byte universally unique identifier (UUID).
+
+**xfs\_fsize\_t**
+ Signed 64 bit byte size of a file.
diff --git a/Documentation/filesystems/xfs-data-structures/magic.rst b/Documentation/filesystems/xfs-data-structures/magic.rst
new file mode 100644
index 000000000000..f5e57581645d
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/magic.rst
@@ -0,0 +1,277 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Magic Numbers
+-------------
+
+These are the magic numbers that are known to XFS, along with links to the
+relevant chapters. Magic numbers tend to have consistent locations:
+
+- 32-bit magic numbers are always at offset zero in the block.
+
+- 16-bit magic numbers for the directory and attribute B+tree are at offset
+ eight.
+
+- The quota magic number is at offset zero.
+
+- The inode magic is at the beginning of each inode.
+
+.. list-table::
+ :widths: 28 12 8 34
+ :header-rows: 1
+
+ * - Flag
+ - Hexadecimal
+ - ASCII
+ - Data structure
+ * - XFS_SB_MAGIC
+ - 0x58465342
+ - XFSB
+ - `Superblock <#superblocks>`__
+ * - XFS_AGF_MAGIC
+ - 0x58414746
+ - XAGF
+ - `Free Space <#ag-free-space-block>`__
+ * - XFS_AGI_MAGIC
+ - 0x58414749
+ - XAGI
+ - `Inode Information <#inode-information>`__
+ * - XFS_AGFL_MAGIC
+ - 0x5841464c
+ - XAFL
+ - `Free Space List <#ag-free-list>`__, v5 only
+ * - XFS_DINODE_MAGIC
+ - 0x494e
+ - IN
+ - `Inodes <#inode-core>`__
+ * - XFS_DQUOT_MAGIC
+ - 0x4451
+ - DQ
+ - `Quota Inodes <#quota-inodes>`__
+ * - XFS_SYMLINK_MAGIC
+ - 0x58534c4d
+ - XSLM
+ - `Symbolic Links <#extent-symbolic-links>`__
+ * - XFS_ABTB_MAGIC
+ - 0x41425442
+ - ABTB
+ - `Free Space by Block B+tree <#ag-free-space-b-trees>`__
+ * - XFS_ABTB_CRC_MAGIC
+ - 0x41423342
+ - AB3B
+ - `Free Space by Block B+tree <#ag-free-space-b-trees>`__, v5 only
+ * - XFS_ABTC_MAGIC
+ - 0x41425443
+ - ABTC
+ - `Free Space by Size B+tree <#ag-free-space-b-trees>`__
+ * - XFS_ABTC_CRC_MAGIC
+ - 0x41423343
+ - AB3C
+ - `Free Space by Size B+tree <#ag-free-space-b-trees>`__, v5 only
+ * - XFS_IBT_MAGIC
+ - 0x49414254
+ - IABT
+ - `Inode B+tree <#inode-b-trees>`__
+ * - XFS_IBT_CRC_MAGIC
+ - 0x49414233
+ - IAB3
+ - `Inode B+tree <#inode-b-trees>`__, v5 only
+ * - XFS_FIBT_MAGIC
+ - 0x46494254
+ - FIBT
+ - `Free Inode B+tree <#inode-b-trees>`__
+ * - XFS_FIBT_CRC_MAGIC
+ - 0x46494233
+ - FIB3
+ - `Free Inode B+tree <#inode-b-trees>`__, v5 only
+ * - XFS_BMAP_MAGIC
+ - 0x424d4150
+ - BMAP
+ - `B+Tree Extent List <#b-tree-extent-list>`__
+ * - XFS_BMAP_CRC_MAGIC
+ - 0x424d4133
+ - BMA3
+ - `B+Tree Extent List <#b-tree-extent-list>`__, v5 only
+ * - XLOG_HEADER_MAGIC_NUM
+ - 0xfeedbabe
+ -
+ - `Log Records <#log-records>`__
+ * - XFS_DA_NODE_MAGIC
+ - 0xfebe
+ -
+ - `Directory/Attribute Node <#directory-attribute-internal-node>`__
+ * - XFS_DA3_NODE_MAGIC
+ - 0x3ebe
+ -
+ - `Directory/Attribute Node <#directory-attribute-internal-node>`__, v5 only
+ * - XFS_DIR2_BLOCK_MAGIC
+ - 0x58443242
+ - XD2B
+ - `Block Directory Data <#block-directories>`__
+ * - XFS_DIR3_BLOCK_MAGIC
+ - 0x58444233
+ - XDB3
+ - `Block Directory Data <#block-directories>`__, v5 only
+ * - XFS_DIR2_DATA_MAGIC
+ - 0x58443244
+ - XD2D
+ - `Leaf Directory Data <#leaf-directories>`__
+ * - XFS_DIR3_DATA_MAGIC
+ - 0x58444433
+ - XDD3
+ - `Leaf Directory Data <#leaf-directories>`__, v5 only
+ * - XFS_DIR2_LEAF1_MAGIC
+ - 0xd2f1
+ -
+ - `Leaf Directory <#leaf-directories>`__
+ * - XFS_DIR3_LEAF1_MAGIC
+ - 0x3df1
+ -
+ - `Leaf Directory <#leaf-directories>`__, v5 only
+ * - XFS_DIR2_LEAFN_MAGIC
+ - 0xd2ff
+ -
+ - `Node Directory <#node-directories>`__
+ * - XFS_DIR3_LEAFN_MAGIC
+ - 0x3dff
+ -
+ - `Node Directory <#node-directories>`__, v5 only
+ * - XFS_DIR2_FREE_MAGIC
+ - 0x58443246
+ - XD2F
+ - `Node Directory Free Space <#node-directories>`__
+ * - XFS_DIR3_FREE_MAGIC
+ - 0x58444633
+ - XDF3
+ - `Node Directory Free Space <#node-directories>`__, v5 only
+ * - XFS_ATTR_LEAF_MAGIC
+ - 0xfbee
+ -
+ - `Leaf Attribute <#leaf-attributes>`__
+ * - XFS_ATTR3_LEAF_MAGIC
+ - 0x3bee
+ -
+ - `Leaf Attribute <#leaf-attributes>`__, v5 only
+ * - XFS_ATTR3_RMT_MAGIC
+ - 0x5841524d
+ - XARM
+ - `Remote Attribute Value <#remote-attribute-values>`__, v5 only
+ * - XFS_RMAP_CRC_MAGIC
+ - 0x524d4233
+ - RMB3
+ - `Reverse Mapping B+tree <#reverse-mapping-b-tree>`__, v5 only
+ * - XFS_RTRMAP_CRC_MAGIC
+ - 0x4d415052
+ - MAPR
+ - `Real-Time Reverse Mapping B+tree <#real-time-reverse-mapping-b-tree>`__, v5 only
+ * - XFS_REFC_CRC_MAGIC
+ - 0x52334643
+ - R3FC
+ - `Reference Count B+tree <#reference-count-b-tree>`__, v5 only
+ * - XFS_MD_MAGIC
+ - 0x5846534d
+ - XFSM
+ - `Metadata Dumps <#metadata-dumps>`__
+
+The magic numbers for log items are at offset zero in each log item, but items
+are not aligned to blocks.
+
+.. list-table::
+ :widths: 24 12 8 36
+ :header-rows: 1
+
+ * - Flag
+ - Hexadecimal
+ - ASCII
+ - Data structure
+ * - XFS_TRANS_HEADER_MAGIC
+ - 0x5452414e
+ - TRAN
+ - `Log Transactions <#transaction-headers>`__
+ * - XFS_LI_EFI
+ - 0x1236
+ -
+ - `Extent Freeing Intent Log Item <#intent-to-free-an-extent>`__
+ * - XFS_LI_EFD
+ - 0x1237
+ -
+ - `Extent Freeing Done Log Item <#completion-of-intent-to-free-an-extent>`__
+ * - XFS_LI_IUNLINK
+ - 0x1238
+ -
+ - Unknown?
+ * - XFS_LI_INODE
+ - 0x123b
+ -
+ - `Inode Updates Log Item <#inode-updates>`__
+ * - XFS_LI_BUF
+ - 0x123c
+ -
+ - `Buffer Writes Log Item <#buffer-log-item>`__
+ * - XFS_LI_DQUOT
+ - 0x123d
+ -
+ - `Update Quota Log Item <#quota-update-data-log-item>`__
+ * - XFS_LI_QUOTAOFF
+ - 0x123e
+ -
+ - `Quota Off Log Item <#disable-quota-log-item>`__
+ * - XFS_LI_ICREATE
+ - 0x123f
+ -
+ - `Inode Creation Log Item <#inode-creation-log-item>`__
+ * - XFS_LI_RUI
+ - 0x1240
+ -
+ - `Reverse Mapping Update Intent <#reverse-mapping-updates-intent>`__
+ * - XFS_LI_RUD
+ - 0x1241
+ -
+ - `Reverse Mapping Update Done <#completion-of-reverse-mapping-updates>`__
+ * - XFS_LI_CUI
+ - 0x1242
+ -
+ - `Reference Count Update Intent <#reference-count-updates-intent>`__
+ * - XFS_LI_CUD
+ - 0x1243
+ -
+ - `Reference Count Update Done <#completion-of-reference-count-updates>`__
+ * - XFS_LI_BUI
+ - 0x1244
+ -
+ - `File Block Mapping Update Intent <#file-block-mapping-intent>`__
+ * - XFS_LI_BUD
+ - 0x1245
+ -
+ - `File Block Mapping Update Done <#completion-of-file-block-mapping-updates>`__
+
+Theoretical Limits
+------------------
+
+XFS can create really big filesystems!
+
++---------------------+---------------------+---------------------+---------------------+
+| Item | 1KiB blocks | 4KiB blocks | 64KiB blocks |
++=====================+=====================+=====================+=====================+
+| Blocks | 2\ :sup:`52` | 2\ :sup:`52` | 2\ :sup:`52` |
++---------------------+---------------------+---------------------+---------------------+
+| Inodes | 2\ :sup:`63` | 2\ :sup:`63` | 2\ :sup:`64` |
++---------------------+---------------------+---------------------+---------------------+
+| Allocation Groups | 2\ :sup:`32` | 2\ :sup:`32` | 2\ :sup:`32` |
++---------------------+---------------------+---------------------+---------------------+
+| File System Size | 8EiB | 8EiB | 8EiB |
++---------------------+---------------------+---------------------+---------------------+
+| Blocks per AG | 2\ :sup:`31` | 2\ :sup:`31` | 2\ :sup:`31` |
++---------------------+---------------------+---------------------+---------------------+
+| Inodes per AG | 2\ :sup:`32` | 2\ :sup:`32` | 2\ :sup:`32` |
++---------------------+---------------------+---------------------+---------------------+
+| Max AG Size | 2TiB | 8TiB | 128TiB |
++---------------------+---------------------+---------------------+---------------------+
+| Blocks Per File | 2\ :sup:`54` | 2\ :sup:`54` | 2\ :sup:`54` |
++---------------------+---------------------+---------------------+---------------------+
+| File Size | 8EiB | 8EiB | 8EiB |
++---------------------+---------------------+---------------------+---------------------+
+| Max Dir Size | 32GiB | 32GiB | 32GiB |
++---------------------+---------------------+---------------------+---------------------+
+
+Linux doesn’t suppport files or devices larger than 8EiB, so the block
+limitations are largely ignorable.
diff --git a/Documentation/filesystems/xfs-data-structures/overview.rst b/Documentation/filesystems/xfs-data-structures/overview.rst
index b1b3f711638b..23eb71d65c93 100644
--- a/Documentation/filesystems/xfs-data-structures/overview.rst
+++ b/Documentation/filesystems/xfs-data-structures/overview.rst
@@ -47,3 +47,5 @@ latency.
.. include:: delayed_logging.rst
.. include:: reflink.rst
.. include:: reconstruction.rst
+.. include:: common_types.rst
+.. include:: magic.rst
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 08/22] docs: add XFS testing chapter to the DS&A book
2018-10-04 3:25 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
` (5 preceding siblings ...)
2018-10-04 3:26 ` [PATCH 07/22] docs: add XFS common types and magic numbers " Darrick J. Wong
@ 2018-10-04 3:26 ` Darrick J. Wong
6 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:26 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
From: Darrick J. Wong <darrick.wong@oracle.com>
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
.../filesystems/xfs-data-structures/overview.rst | 1 +
.../filesystems/xfs-data-structures/testing.rst | 25 ++++++++++++++++++++
2 files changed, 26 insertions(+)
create mode 100644 Documentation/filesystems/xfs-data-structures/testing.rst
diff --git a/Documentation/filesystems/xfs-data-structures/overview.rst b/Documentation/filesystems/xfs-data-structures/overview.rst
index 23eb71d65c93..d6711dc653d8 100644
--- a/Documentation/filesystems/xfs-data-structures/overview.rst
+++ b/Documentation/filesystems/xfs-data-structures/overview.rst
@@ -49,3 +49,4 @@ latency.
.. include:: reconstruction.rst
.. include:: common_types.rst
.. include:: magic.rst
+.. include:: testing.rst
diff --git a/Documentation/filesystems/xfs-data-structures/testing.rst b/Documentation/filesystems/xfs-data-structures/testing.rst
new file mode 100644
index 000000000000..3d3386854408
--- /dev/null
+++ b/Documentation/filesystems/xfs-data-structures/testing.rst
@@ -0,0 +1,25 @@
+.. SPDX-License-Identifier: CC-BY-SA-4.0
+
+Testing Filesystem Changes
+--------------------------
+
+People put a lot of trust in filesystems to preserve their data in a reliable
+fashion. To that end, it is very important that users and developers have
+access to a suite of regression tests that can be used to prove correct
+operation of any given filesystem code, or to analyze failures to fix problems
+found in the code. The XFS regression test suite, xfstests, is hosted at
+``git://git.kernel.org/pub/scm/fs/xfs/xfstests-dev.git``. Most tests apply to
+filesystems in general, but the suite also contains tests for features
+specific to each filesystem.
+
+When fixing bugs, it is important to provide a testcase exposing the bug so
+that the developers can avoid a future re-occurrence of the regression.
+Furthermore, if you’re developing a new user-visible feature for XFS, please
+help the rest of the development community to sustain and maintain the whole
+codebase by providing generous test coverage to check its behavior.
+
+When altering, adding, or removing an on-disk data structure, please remember
+to update both the in-kernel structure size checks in xfs\_ondisk.h and to
+ensure that your changes are reflected in xfstest xfs/122. These regression
+tests enable us to detect compiler bugs, alignment problems, and anything else
+that might result in the creation of incompatible filesystem images.
^ permalink raw reply related [flat|nested] 9+ messages in thread