* [PATCH v2 00/22] xfs-4.20: major documentation surgery
@ 2018-10-04 3:25 Darrick J. Wong
2018-10-04 3:25 ` [PATCH 01/22] docs: add skeleton of XFS Data Structures and Algorithms book Darrick J. Wong
` (6 more replies)
0 siblings, 7 replies; 18+ messages in thread
From: Darrick J. Wong @ 2018-10-04 3:25 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
Hi all,
This series converts the existing in-kernel xfs documentation to rst
format, links it in with the rest of the kernel's rst documetation, and
then begins pulling in the contents of the Data Structures & Algorithms
book from the xfs-documentation git tree. No changes are made to the
text during the import process except to fix things that the conversion
process (asciidoctor + pandoc) didn't do correctly. The goal of this
series is to tie together the XFS code with the on-disk format
documentation for the features supported by the code.
I've built the docs and put them here, in case you hate reading rst:
https://djwong.org/docs/kdoc/admin-guide/xfs.html
https://djwong.org/docs/kdoc/filesystems/xfs-data-structures/index.html
I've posted a branch here because the png import patch is huge:
https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/log/?h=docs-4.20-merge
The patchset should apply cleanly against 4.19-rc6. Comments and
questions are, as always, welcome.
--D
^ permalink raw reply [flat|nested] 18+ messages in thread
* [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; 18+ 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] 18+ 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; 18+ 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] 18+ 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; 18+ 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] 18+ 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; 18+ 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] 18+ 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; 18+ 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] 18+ 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; 18+ 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] 18+ 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; 18+ 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] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-15 9:55 ` Christoph Hellwig
@ 2018-10-15 14:28 ` Jonathan Corbet
0 siblings, 0 replies; 18+ messages in thread
From: Jonathan Corbet @ 2018-10-15 14:28 UTC (permalink / raw)
To: Christoph Hellwig
Cc: Dave Chinner, Darrick J. Wong, linux-xfs, linux-doc, Matthew Wilcox
On Mon, 15 Oct 2018 02:55:49 -0700
Christoph Hellwig <hch@infradead.org> wrote:
> > OK, I've had a long conversation with the LF lawyer, and she said clearly
> > that we really should not be introducing CC-SA material into the kernel
> > source tree. It's a pain; I really do like CC-SA better for
> > documentation, but it's not GPL-compatible, and that creates a problem for
> > the processed docs.
>
> That was exactly my concern with this patchset.
>
> Btw, I think we have the same issue with idr.rst, and unless we can
> relicense it we should drop it from the tree, as it actually includes
> kernel source files.
...and a significant DOC section at that, not just function prototypes.
I'd already asked Willy [CC'd] about this once, haven't gotten an answer
yet. Hopefully we can address this once he comes back around.
Thanks,
jon
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-11 17:27 ` Jonathan Corbet
2018-10-12 1:33 ` Dave Chinner
@ 2018-10-15 9:55 ` Christoph Hellwig
2018-10-15 14:28 ` Jonathan Corbet
1 sibling, 1 reply; 18+ messages in thread
From: Christoph Hellwig @ 2018-10-15 9:55 UTC (permalink / raw)
To: Jonathan Corbet; +Cc: Dave Chinner, Darrick J. Wong, linux-xfs, linux-doc
On Thu, Oct 11, 2018 at 11:27:35AM -0600, Jonathan Corbet wrote:
> On Sat, 6 Oct 2018 10:51:54 +1000
> Dave Chinner <david@fromorbit.com> wrote:
>
> > Can you let us know whether the CC-by-SA 4.0 license is acceptible
> > or not? That's really the only thing that we need clarified at this
> > point - if it's OK I'll to pull this into the XFS tree for the 4.20
> > merge window. If not, we'll go back to the drawing board....
>
> OK, I've had a long conversation with the LF lawyer, and she said clearly
> that we really should not be introducing CC-SA material into the kernel
> source tree. It's a pain; I really do like CC-SA better for
> documentation, but it's not GPL-compatible, and that creates a problem for
> the processed docs.
That was exactly my concern with this patchset.
Btw, I think we have the same issue with idr.rst, and unless we can
relicense it we should drop it from the tree, as it actually includes
kernel source files.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-11 17:27 ` Jonathan Corbet
@ 2018-10-12 1:33 ` Dave Chinner
2018-10-15 9:55 ` Christoph Hellwig
1 sibling, 0 replies; 18+ messages in thread
From: Dave Chinner @ 2018-10-12 1:33 UTC (permalink / raw)
To: Jonathan Corbet; +Cc: Darrick J. Wong, linux-xfs, linux-doc
On Thu, Oct 11, 2018 at 11:27:35AM -0600, Jonathan Corbet wrote:
> On Sat, 6 Oct 2018 10:51:54 +1000 Dave Chinner
> <david@fromorbit.com> wrote:
>
> > Can you let us know whether the CC-by-SA 4.0 license is
> > acceptible or not? That's really the only thing that we need
> > clarified at this point - if it's OK I'll to pull this into the
> > XFS tree for the 4.20 merge window. If not, we'll go back to the
> > drawing board....
>
> OK, I've had a long conversation with the LF lawyer, and she said
> clearly that we really should not be introducing CC-SA material
> into the kernel source tree. It's a pain; I really do like CC-SA
> better for documentation, but it's not GPL-compatible, and that
> creates a problem for the processed docs.
Ok, thanks for following upon this, Jon. We'll just keep it all in
the existing external repo and work out what to do from there.
Cheers,
Dave.
--
Dave Chinner
david@fromorbit.com
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-06 0:51 ` Dave Chinner
2018-10-06 1:01 ` Jonathan Corbet
2018-10-06 13:29 ` Matthew Wilcox
@ 2018-10-11 17:27 ` Jonathan Corbet
2018-10-12 1:33 ` Dave Chinner
2018-10-15 9:55 ` Christoph Hellwig
2 siblings, 2 replies; 18+ messages in thread
From: Jonathan Corbet @ 2018-10-11 17:27 UTC (permalink / raw)
To: Dave Chinner; +Cc: Darrick J. Wong, linux-xfs, linux-doc
On Sat, 6 Oct 2018 10:51:54 +1000
Dave Chinner <david@fromorbit.com> wrote:
> Can you let us know whether the CC-by-SA 4.0 license is acceptible
> or not? That's really the only thing that we need clarified at this
> point - if it's OK I'll to pull this into the XFS tree for the 4.20
> merge window. If not, we'll go back to the drawing board....
OK, I've had a long conversation with the LF lawyer, and she said clearly
that we really should not be introducing CC-SA material into the kernel
source tree. It's a pain; I really do like CC-SA better for
documentation, but it's not GPL-compatible, and that creates a problem for
the processed docs.
Sorry,
jon
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-06 13:29 ` Matthew Wilcox
@ 2018-10-06 14:10 ` Jonathan Corbet
0 siblings, 0 replies; 18+ messages in thread
From: Jonathan Corbet @ 2018-10-06 14:10 UTC (permalink / raw)
To: Matthew Wilcox; +Cc: Dave Chinner, Darrick J. Wong, linux-xfs, linux-doc
On Sat, 6 Oct 2018 06:29:51 -0700
Matthew Wilcox <willy@infradead.org> wrote:
> I had an informal chat with Bradley Kuhn at LinuxCon Japan about using
> CC-BY-SA-4.0 and he indicated that I was probably better off using the
> GPL-2(+) for documentation. I've changed the XArray documentation from
> CC-BY-SA-4.0 to GPL-2+.
Would you consider doing the same for Documentation/core-api/idr.rst?
That's the only CC-SA SPDX tag in the kernel now, and it's a clear
example of just what I'm worried about: it pulls in a nice DOC section
from the code when you run Sphinx on it, so we're not just talking
function prototypes here. I was likely to come knocking on your door
after my upcoming conversation anyway...:)
Thanks,
jon
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-06 0:51 ` Dave Chinner
2018-10-06 1:01 ` Jonathan Corbet
@ 2018-10-06 13:29 ` Matthew Wilcox
2018-10-06 14:10 ` Jonathan Corbet
2018-10-11 17:27 ` Jonathan Corbet
2 siblings, 1 reply; 18+ messages in thread
From: Matthew Wilcox @ 2018-10-06 13:29 UTC (permalink / raw)
To: Dave Chinner; +Cc: Darrick J. Wong, linux-xfs, linux-doc, corbet
On Sat, Oct 06, 2018 at 10:51:54AM +1000, Dave Chinner wrote:
> On Wed, Oct 03, 2018 at 09:18:11PM -0700, Darrick J. Wong wrote:
> > Hi all,
> >
> > This series converts the existing in-kernel xfs documentation to rst
> > format, links it in with the rest of the kernel's rst documetation, and
> > then begins pulling in the contents of the Data Structures & Algorithms
> > book from the xfs-documentation git tree. No changes are made to the
> > text during the import process except to fix things that the conversion
> > process (asciidoctor + pandoc) didn't do correctly. The goal of this
> > series is to tie together the XFS code with the on-disk format
> > documentation for the features supported by the code.
> >
> > I've built the docs and put them here, in case you hate reading rst:
> > https://djwong.org/docs/kdoc/admin-guide/xfs.html
> > https://djwong.org/docs/kdoc/filesystems/xfs-data-structures/index.html
> >
> > I've posted a branch here because the png import patch is huge:
> > https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/log/?h=docs-4.20-merge
> >
> > The patchset should apply cleanly against 4.19-rc6. Comments and
> > questions are, as always, welcome.
>
> Jon,
>
> Can you let us know whether the CC-by-SA 4.0 license is acceptible
> or not? That's really the only thing that we need clarified at this
> point - if it's OK I'll to pull this into the XFS tree for the 4.20
> merge window. If not, we'll go back to the drawing board....
This is (obviously) not legal advice.
I had an informal chat with Bradley Kuhn at LinuxCon Japan about using
CC-BY-SA-4.0 and he indicated that I was probably better off using the
GPL-2(+) for documentation. I've changed the XArray documentation from
CC-BY-SA-4.0 to GPL-2+.
YMMV, defer to the LF lawyer, but I thought it worth providing a data
point.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-06 1:01 ` Jonathan Corbet
@ 2018-10-06 1:09 ` Dave Chinner
0 siblings, 0 replies; 18+ messages in thread
From: Dave Chinner @ 2018-10-06 1:09 UTC (permalink / raw)
To: Jonathan Corbet; +Cc: Darrick J. Wong, linux-xfs, linux-doc
On Fri, Oct 05, 2018 at 07:01:20PM -0600, Jonathan Corbet wrote:
> On Sat, 6 Oct 2018 10:51:54 +1000
> Dave Chinner <david@fromorbit.com> wrote:
>
> > Can you let us know whether the CC-by-SA 4.0 license is acceptible
> > or not? That's really the only thing that we need clarified at this
> > point - if it's OK I'll to pull this into the XFS tree for the 4.20
> > merge window. If not, we'll go back to the drawing board....
>
> I remain pretty concerned about it, to tell the truth. Rather than
> continue to guess, though, I've called for help, and will be talking with
> the LF lawyer about this next Thursday. Before then, I can't say anything
> except "I don't think this works..."
>
> Will let you know what I hear.
Thanks for the update, Jon. I'll put this on the backburner until I
hear back from you.
Cheers,
Dave.
--
Dave Chinner
david@fromorbit.com
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-06 0:51 ` Dave Chinner
@ 2018-10-06 1:01 ` Jonathan Corbet
2018-10-06 1:09 ` Dave Chinner
2018-10-06 13:29 ` Matthew Wilcox
2018-10-11 17:27 ` Jonathan Corbet
2 siblings, 1 reply; 18+ messages in thread
From: Jonathan Corbet @ 2018-10-06 1:01 UTC (permalink / raw)
To: Dave Chinner; +Cc: Darrick J. Wong, linux-xfs, linux-doc
On Sat, 6 Oct 2018 10:51:54 +1000
Dave Chinner <david@fromorbit.com> wrote:
> Can you let us know whether the CC-by-SA 4.0 license is acceptible
> or not? That's really the only thing that we need clarified at this
> point - if it's OK I'll to pull this into the XFS tree for the 4.20
> merge window. If not, we'll go back to the drawing board....
I remain pretty concerned about it, to tell the truth. Rather than
continue to guess, though, I've called for help, and will be talking with
the LF lawyer about this next Thursday. Before then, I can't say anything
except "I don't think this works..."
Will let you know what I hear.
jon
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v2 00/22] xfs-4.20: major documentation surgery
2018-10-04 4:18 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
@ 2018-10-06 0:51 ` Dave Chinner
2018-10-06 1:01 ` Jonathan Corbet
` (2 more replies)
0 siblings, 3 replies; 18+ messages in thread
From: Dave Chinner @ 2018-10-06 0:51 UTC (permalink / raw)
To: Darrick J. Wong; +Cc: linux-xfs, linux-doc, corbet
On Wed, Oct 03, 2018 at 09:18:11PM -0700, Darrick J. Wong wrote:
> Hi all,
>
> This series converts the existing in-kernel xfs documentation to rst
> format, links it in with the rest of the kernel's rst documetation, and
> then begins pulling in the contents of the Data Structures & Algorithms
> book from the xfs-documentation git tree. No changes are made to the
> text during the import process except to fix things that the conversion
> process (asciidoctor + pandoc) didn't do correctly. The goal of this
> series is to tie together the XFS code with the on-disk format
> documentation for the features supported by the code.
>
> I've built the docs and put them here, in case you hate reading rst:
> https://djwong.org/docs/kdoc/admin-guide/xfs.html
> https://djwong.org/docs/kdoc/filesystems/xfs-data-structures/index.html
>
> I've posted a branch here because the png import patch is huge:
> https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/log/?h=docs-4.20-merge
>
> The patchset should apply cleanly against 4.19-rc6. Comments and
> questions are, as always, welcome.
Jon,
Can you let us know whether the CC-by-SA 4.0 license is acceptible
or not? That's really the only thing that we need clarified at this
point - if it's OK I'll to pull this into the XFS tree for the 4.20
merge window. If not, we'll go back to the drawing board....
Cheers,
Dave.
--
Dave Chinner
david@fromorbit.com
^ permalink raw reply [flat|nested] 18+ messages in thread
* [PATCH v2 00/22] xfs-4.20: major documentation surgery
@ 2018-10-04 4:18 Darrick J. Wong
2018-10-06 0:51 ` Dave Chinner
0 siblings, 1 reply; 18+ messages in thread
From: Darrick J. Wong @ 2018-10-04 4:18 UTC (permalink / raw)
To: darrick.wong; +Cc: linux-xfs, linux-doc, corbet
Hi all,
This series converts the existing in-kernel xfs documentation to rst
format, links it in with the rest of the kernel's rst documetation, and
then begins pulling in the contents of the Data Structures & Algorithms
book from the xfs-documentation git tree. No changes are made to the
text during the import process except to fix things that the conversion
process (asciidoctor + pandoc) didn't do correctly. The goal of this
series is to tie together the XFS code with the on-disk format
documentation for the features supported by the code.
I've built the docs and put them here, in case you hate reading rst:
https://djwong.org/docs/kdoc/admin-guide/xfs.html
https://djwong.org/docs/kdoc/filesystems/xfs-data-structures/index.html
I've posted a branch here because the png import patch is huge:
https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/log/?h=docs-4.20-merge
The patchset should apply cleanly against 4.19-rc6. Comments and
questions are, as always, welcome.
--D
^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2018-10-15 22:14 UTC | newest]
Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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 ` [PATCH 04/22] docs: add XFS delayed logging design " Darrick J. Wong
2018-10-04 3:25 ` [PATCH 05/22] docs: add XFS shared data block chapter " Darrick J. Wong
2018-10-04 3:25 ` [PATCH 06/22] docs: add XFS online repair " 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
2018-10-04 4:18 [PATCH v2 00/22] xfs-4.20: major documentation surgery Darrick J. Wong
2018-10-06 0:51 ` Dave Chinner
2018-10-06 1:01 ` Jonathan Corbet
2018-10-06 1:09 ` Dave Chinner
2018-10-06 13:29 ` Matthew Wilcox
2018-10-06 14:10 ` Jonathan Corbet
2018-10-11 17:27 ` Jonathan Corbet
2018-10-12 1:33 ` Dave Chinner
2018-10-15 9:55 ` Christoph Hellwig
2018-10-15 14:28 ` Jonathan Corbet
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.