On Wed, Jan 18, 2023 at 12:03:09AM +0000, Allison Henderson wrote: > On Wed, 2023-01-11 at 11:10 -0800, Darrick J. Wong wrote: > > On Sat, Jan 07, 2023 at 05:01:54AM +0000, Allison Henderson wrote: > > > On Fri, 2022-12-30 at 14:10 -0800, Darrick J. Wong wrote: > > > > From: Darrick J. Wong <djwong@xxxxxxxxxx> > > > > > > > > Start the first chapter of the online fsck design documentation. > > > > This covers the motivations for creating this in the first place. > > > > > > > > Signed-off-by: Darrick J. Wong <djwong@xxxxxxxxxx> > > > > --- > > > > Documentation/filesystems/index.rst | 1 > > > > .../filesystems/xfs-online-fsck-design.rst | 199 > > > > ++++++++++++++++++++ > > > > 2 files changed, 200 insertions(+) > > > > create mode 100644 Documentation/filesystems/xfs-online-fsck- > > > > design.rst > > > > > > > > > > > > diff --git a/Documentation/filesystems/index.rst > > > > b/Documentation/filesystems/index.rst > > > > index bee63d42e5ec..fbb2b5ada95b 100644 > > > > --- a/Documentation/filesystems/index.rst > > > > +++ b/Documentation/filesystems/index.rst > > > > @@ -123,4 +123,5 @@ Documentation for filesystem implementations. > > > > vfat > > > > xfs-delayed-logging-design > > > > xfs-self-describing-metadata > > > > + xfs-online-fsck-design > > > > zonefs > > > > diff --git a/Documentation/filesystems/xfs-online-fsck-design.rst > > > > b/Documentation/filesystems/xfs-online-fsck-design.rst > > > > new file mode 100644 > > > > index 000000000000..25717ebb5f80 > > > > --- /dev/null > > > > +++ b/Documentation/filesystems/xfs-online-fsck-design.rst > > > > @@ -0,0 +1,199 @@ > > > > +.. SPDX-License-Identifier: GPL-2.0 > > > > +.. _xfs_online_fsck_design: > > > > + > > > > +.. > > > > + Mapping of heading styles within this document: > > > > + Heading 1 uses "====" above and below > > > > + Heading 2 uses "====" > > > > + Heading 3 uses "----" > > > > + Heading 4 uses "````" > > > > + Heading 5 uses "^^^^" > > > > + Heading 6 uses "~~~~" > > > > + Heading 7 uses "...." > > > > + > > > > + Sections are manually numbered because apparently that's > > > > what everyone > > > > + does in the kernel. > > > > + > > > > +====================== > > > > +XFS Online Fsck Design > > > > +====================== > > > > + > > > > +This document captures the design of the online filesystem check > > > > feature for > > > > +XFS. > > > > +The purpose of this document is threefold: > > > > + > > > > +- To help kernel distributors understand exactly what the XFS > > > > online > > > > fsck > > > > + feature is, and issues about which they should be aware. > > > > + > > > > +- To help people reading the code to familiarize themselves with > > > > the > > > > relevant > > > > + concepts and design points before they start digging into the > > > > code. > > > > + > > > > +- To help developers maintaining the system by capturing the > > > > reasons > > > > + supporting higher level decisionmaking. > > > nit: decision making > > > > Fixed. > > > > > > + > > > > +As the online fsck code is merged, the links in this document to > > > > topic branches > > > > +will be replaced with links to code. > > > > + > > > > +This document is licensed under the terms of the GNU Public > > > > License, > > > > v2. > > > > +The primary author is Darrick J. Wong. > > > > + > > > > +This design document is split into seven parts. > > > > +Part 1 defines what fsck tools are and the motivations for > > > > writing a > > > > new one. > > > > +Parts 2 and 3 present a high level overview of how online fsck > > > > process works > > > > +and how it is tested to ensure correct functionality. > > > > +Part 4 discusses the user interface and the intended usage modes > > > > of > > > > the new > > > > +program. > > > > +Parts 5 and 6 show off the high level components and how they > > > > fit > > > > together, and > > > > +then present case studies of how each repair function actually > > > > works. > > > > +Part 7 sums up what has been discussed so far and speculates > > > > about > > > > what else > > > > +might be built atop online fsck. > > > > + > > > > +.. contents:: Table of Contents > > > > + :local: > > > > + > > > > > > Something that I've noticed in my training sessions is that often > > > times, less is more. People really only absorb so much over a > > > particular duration of time, so sometimes having too much detail in > > > the > > > context is not as helpful as you might think. A lot of times, > > > paraphrasing excerpts to reflect the same info in a more compact > > > format > > > will help you keep audience on track (a little longer at least). > > > > > > > +1. What is a Filesystem Check? > > > > +============================== > > > > + > > > > +A Unix filesystem has three main jobs: to provide a hierarchy of > > > > names through > > > > +which application programs can associate arbitrary blobs of data > > > > for > > > > any > > > > +length of time, to virtualize physical storage media across > > > > those > > > > names, and > > > > +to retrieve the named data blobs at any time. > > > Consider the following paraphrase: > > > > > > A Unix filesystem has three main jobs: > > > * Provide a hierarchy of names by which applications access data > > > for a > > > length of time. > > > * Store or retrieve that data at any time. > > > * Virtualize physical storage media across those names > > > > Ooh, listifying. I did quite a bit of that to break up the walls of > > text in earlier revisions, but apparently I missed this one. > > > > > Also... I dont think it would be inappropriate to just skip the > > > above, > > > and jump right into fsck. That's a very limited view of a > > > filesystem, > > > likely a reader seeking an fsck doc probably has some idea of what > > > a fs > > > is otherwise supposed to be doing. > > > > This will become part of the general kernel documentation, so we > > can't > > assume that all readers are going to know what a fs really does. > > > > "A Unix filesystem has four main responsibilities: > > > > - Provide a hierarchy of names through which application programs can > > associate arbitrary blobs of data for any length of time, > > > > - Virtualize physical storage media across those names, and > > > > - Retrieve the named data blobs at any time. > > > > - Examine resource usage. > > > > "Metadata directly supporting these functions (e.g. files, > > directories, > > space mappings) are sometimes called primary metadata. > > Secondary metadata (e.g. reverse mapping and directory parent > > pointers) > > support operations internal to the filesystem, such as internal > > consistency checking and reorganization." > Sure, I think that sounds good and helps to set up the metadata > concepts that are discussed later. > > > > (I added those last two sentences in response to a point you made > > below.) > > > > > > +The filesystem check (fsck) tool examines all the metadata in a > > > > filesystem > > > > +to look for errors. > > > > +Simple tools only check for obvious corruptions, but the more > > > > sophisticated > > > > +ones cross-reference metadata records to look for > > > > inconsistencies. > > > > +People do not like losing data, so most fsck tools also contains > > > > some ability > > > > +to deal with any problems found. > > > > > > While simple tools can detect data corruptions, a filesystem check > > > (fsck) uses metadata records as a cross-reference to find and > > > correct > > > more inconsistencies. > > > > > > ? > > > > Let's be careful with the term 'data corruption' here -- a lot of > > people > > (well ok me) will see that as *user* data corruption, whereas we're > > talking about *metadata* corruption. > > > > I think I'll rework that second sentence further: > > > > "In addition to looking for obvious metadata corruptions, fsck also > > cross-references different types of metadata records with each other > > to > > look for inconsistencies." > > > Alrighty, that sounds good > > > Since the really dumb fscks of the 1970s are a long ways past now. > > > > > > +As a word of caution -- the primary goal of most Linux fsck > > > > tools is > > > > to restore > > > > +the filesystem metadata to a consistent state, not to maximize > > > > the > > > > data > > > > +recovered. > > > > +That precedent will not be challenged here. > > > > + > > > > +Filesystems of the 20th century generally lacked any redundancy > > > > in > > > > the ondisk > > > > +format, which means that fsck can only respond to errors by > > > > erasing > > > > files until > > > > +errors are no longer detected. > > > > +System administrators avoid data loss by increasing the number > > > > of > > > > separate > > > > +storage systems through the creation of backups; > > > > > > > > > > and they avoid downtime by > > > > +increasing the redundancy of each storage system through the > > > > creation of RAID. > > > Mmm, raids help more for hardware failures right? They dont really > > > have a notion of when the fs is corrupted. > > > > Right. > > > > > While an fsck can help > > > navigate around a corruption possibly caused by a hardware failure, > > > I > > > think it's really a different kind of redundancy. I think I'd > > > probably > > > drop the last line and keep the selling point focused online > > > repair. > > > > Yes, RAIDs provide a totally different type of redundancy. I decided > > to > > make this point specifically to counter the people who argue that > > RAID > > makes them impervious to corruption problems, etc. > > > > This attitude seemed rather prevalent in the early days of btrfs and > > a > > certain other filesystem that Shall Not Be Named, even though the > > btrfs > > developers themselves acknowledge this distinction, given the > > existence > > of `btrfs scrub' and `btrfs check'. > > > > However you do have a good point that this sentence doesn't add much > > where it is. I think I'll add it as a sidebar at the end of the > > paragraph. > > > > > > +More recent filesystem designs contain enough redundancy in > > > > their > > > > metadata that > > > > +it is now possible to regenerate data structures when non- > > > > catastrophic errors > > > > +occur; > > > > > > > > > > this capability aids both strategies. > > > > +Over the past few years, XFS has added a storage space reverse > > > > mapping index to > > > > +make it easy to find which files or metadata objects think they > > > > own > > > > a > > > > +particular range of storage. > > > > +Efforts are under way to develop a similar reverse mapping index > > > > for > > > > the naming > > > > +hierarchy, which will involve storing directory parent pointers > > > > in > > > > each file. > > > > +With these two pieces in place, XFS uses secondary information > > > > to > > > > perform more > > > > +sophisticated repairs. > > > This part here I think I would either let go or relocate. The > > > topic of > > > this section is supposed to discuss roughly what a filesystem check > > > is. > > > Ideally so we can start talking about how ofsck is different. It > > > feels > > > like a bit of a jump to suddenly hop into rmap and pptrs, and for > > > "sophisticated repairs" that we havn't really gotten into the > > > details > > > of yet. So I think it would read easier if we saved this part > > > until we > > > start talking about how they are used later. > > > > Agreed. > > > > > > + > > > > +TLDR; Show Me the Code! > > > > +----------------------- > > > > + > > > > +Code is posted to the kernel.org git trees as follows: > > > > +`kernel changes > > > > < > > > > https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.g > > > > it > > > > /log/?h=repair-symlink>`_, > > > > +`userspace changes > > > > <https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfsprogs- > > > > dev. > > > > git/log/?h=scrub-media-scan-service>`_, and > > > > +`QA test changes > > > > <https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfstests- > > > > dev. > > > > git/log/?h=repair-dirs>`_. > > > > +Each kernel patchset adding an online repair function will use > > > > the > > > > same branch > > > > +name across the kernel, xfsprogs, and fstests git repos. > > > > + > > > > +Existing Tools > > > > +-------------- > > > > + > > > > +The online fsck tool described here will be the third tool in > > > > the > > > > history of > > > > +XFS (on Linux) to check and repair filesystems. > > > > +Two programs precede it: > > > > + > > > > +The first program, ``xfs_check``, was created as part of the XFS > > > > debugger > > > > +(``xfs_db``) and can only be used with unmounted filesystems. > > > > +It walks all metadata in the filesystem looking for > > > > inconsistencies > > > > in the > > > > +metadata, though it lacks any ability to repair what it finds. > > > > +Due to its high memory requirements and inability to repair > > > > things, > > > > this > > > > +program is now deprecated and will not be discussed further. > > > > + > > > > +The second program, ``xfs_repair``, was created to be faster and > > > > more robust > > > > +than the first program. > > > > +Like its predecessor, it can only be used with unmounted > > > > filesystems. > > > > +It uses extent-based in-memory data structures to reduce memory > > > > consumption, > > > > +and tries to schedule readahead IO appropriately to reduce I/O > > > > waiting time > > > > +while it scans the metadata of the entire filesystem. > > > > +The most important feature of this tool is its ability to > > > > respond to > > > > +inconsistencies in file metadata and directory tree by erasing > > > > things as needed > > > > +to eliminate problems. > > > > +Space usage metadata are rebuilt from the observed file > > > > metadata. > > > > + > > > > +Problem Statement > > > > +----------------- > > > > + > > > > +The current XFS tools leave several problems unsolved: > > > > + > > > > +1. **User programs** suddenly **lose access** to information in > > > > the > > > > computer > > > > + when unexpected shutdowns occur as a result of silent > > > > corruptions > > > > in the > > > > + filesystem metadata. > > > > + These occur **unpredictably** and often without warning. > > > > > > > > > 1. **User programs** suddenly **lose access** to the filesystem > > > when unexpected shutdowns occur as a result of silent > > > corruptions > > > that could have otherwise been avoided with an online repair > > > > > > While some of these issues are not untrue, I think it makes sense > > > to > > > limit them to the issue you plan to solve, and therefore discuss. > > > > Fair enough, it's not like one loses /all/ the data in the computer. > > > > That said, we're still in the problem definition phase, so I don't > > want > > to mention online repair just yet. > > > > > > +2. **Users** experience a **total loss of service** during the > > > > recovery period > > > > + after an **unexpected shutdown** occurs. > > > > + > > > > +3. **Users** experience a **total loss of service** if the > > > > filesystem is taken > > > > + offline to **look for problems** proactively. > > > > + > > > > +4. **Data owners** cannot **check the integrity** of their > > > > stored > > > > data without > > > > + reading all of it. > > > > > > > + This may expose them to substantial billing costs when a > > > > linear > > > > media scan > > > > + might suffice. > > > Ok, I had to re-read this one a few times, but I think this reads a > > > little cleaner: > > > > > > Customers that are billed for data egress may incur unnecessary > > > cost when a background media scan on the host may have sufficed > > > > > > ? > > > > "...when a linear media scan performed by the storage system > > administrator would suffice." > > > That sounds fine to me > > > I was tempted to say "storage owner" instead of "storage system > > administrator" but that sounded a little too IBM. > > > > > > +5. **System administrators** cannot **schedule** a maintenance > > > > window to deal > > > > + with corruptions if they **lack the means** to assess > > > > filesystem > > > > health > > > > + while the filesystem is online. > > > > + > > > > +6. **Fleet monitoring tools** cannot **automate periodic > > > > checks** of > > > > filesystem > > > > + health when doing so requires **manual intervention** and > > > > downtime. > > > > + > > > > +7. **Users** can be tricked into **doing things they do not > > > > desire** > > > > when > > > > + malicious actors **exploit quirks of Unicode** to place > > > > misleading names > > > > + in directories. > > > hrmm, I guess I'm not immediately extrapolating what things users > > > are > > > being tricked into doing, or how ofsck solves this? Otherwise I > > > might > > > drop the last one here, I think the rest of the bullets are plenty > > > of > > > motivation. > > > > The doc gets into this later[1], but it's possible to create two > > entries > > within the same directory that have different byte sequences in the > > name > > but render identically in file choosers. These pathnames: > > > > /home/djwong/Downloads/rustup.sh > > /home/djwong/Downloads/rus<zero width space>tup.sh > > > > refer to different files, but a naïve file open dialog will render > > them > > identically as "rustup.sh". If the first is the Rust installer and > > the > > second name is actually a ransomware payload, I can victimize you by > > tricking you into opening the wrong one. > > > > Firefox had a whole CVE over this in 2018: > > https://bugzilla.mozilla.org/show_bug.cgi?id=1438025 > > > > xfs_scrub is (so far) the only linux filesystem fsck tool that will > > warn > > system administrators about this kind of thing. > > > > See generic/453 and generic/454. > > > > [1] https://djwong.org/docs/xfs-online-fsck-design/#id108 > > > hmm ok, how about: > > 7. Malicious attacks may use uncommon unicode characters to create file > names that resemble normal files, which may go undetected until the > filesystem is scanned. They resemble *other filenames* in the same directory, normal or otherwise. Note that xattrs have the same problem -- a listing of attrs will show two names that render identically but map to different things. There's less double-click danger there, at least. Another class of unicode problem is that you can use directional controls to spoof file extensions. The sequence: pu<right to left>txt.pl renders as "pulp.txt" if you're not careful, but file managers think it's actually a perl script file! Granted, nobody should allow execution of random a-x downloaded scripts. There are enough weird twists to this sort of deception that I left #7 worded as broadly as I needed. --D > > ? > > > > > + > > > > +Given this definition of the problems to be solved and the > > > > actors > > > > who would > > > > +benefit, the proposed solution is a third fsck tool that acts on > > > > a > > > > running > > > > +filesystem. > > > > + > > > > +This new third program has three components: an in-kernel > > > > facility > > > > to check > > > > +metadata, an in-kernel facility to repair metadata, and a > > > > userspace > > > > driver > > > > +program to drive fsck activity on a live filesystem. > > > > +``xfs_scrub`` is the name of the driver program. > > > > +The rest of this document presents the goals and use cases of > > > > the > > > > new fsck > > > > +tool, describes its major design points in connection to those > > > > goals, and > > > > +discusses the similarities and differences with existing tools. > > > > + > > > > ++--------------------------------------------------------------- > > > > ---- > > > > -------+ > > > > +| > > > > **Note**: > > > > > > > > | > > > > ++--------------------------------------------------------------- > > > > ---- > > > > -------+ > > > > +| Throughout this document, the existing offline fsck tool can > > > > also > > > > be | > > > > +| referred to by its current name > > > > "``xfs_repair``". | > > > > +| The userspace driver program for the new online fsck tool can > > > > be | > > > > +| referred to as > > > > "``xfs_scrub``". | > > > > +| The kernel portion of online fsck that validates metadata is > > > > called | > > > > +| "online scrub", and portion of the kernel that fixes metadata > > > > is > > > > called | > > > > +| "online > > > > repair". > > > > | > > > > ++--------------------------------------------------------------- > > > > ---- > > > > -------+ > > > > Errr ^^^^ is Evolution doing line wrapping here? > > > > > Hmm, maybe here might be a good spot to move rmap and pptrs? It's > > > not > > > otherwise clear to me what "secondary metadata" is. If that is > > > what it > > > is meant to refer to, I think the reader will more intuitively make > > > the > > > connection if those two blurbs appear in the same context. > > > > Ooh, you found a significant gap-- nowhere in this chapter do I > > actually > > define what is primary metadata. Or secondary metadata. > > > > > > + > > > > +Secondary metadata indices enable the reconstruction of parts of > > > > a > > > > damaged > > > > +primary metadata object from secondary information. > > > > > > I would take out this blurb... > > > > +XFS filesystems shard themselves into multiple primary objects > > > > to > > > > enable better > > > > +performance on highly threaded systems and to contain the blast > > > > radius when > > > > +problems happen. > > > > > > > > > > +The naming hierarchy is broken up into objects known as > > > > directories > > > > and files; > > > > +and the physical space is split into pieces known as allocation > > > > groups. > > > And add here: > > > > > > "This enables better performance on highly threaded systems and > > > helps > > > to contain corruptions when they occur." > > > > > > I think that reads cleaner > > > > Ok. Mind if I reword this slightly? The entire paragraph now reads > > like this: > > > > "The naming hierarchy is broken up into objects known as directories > > and > > files and the physical space is split into pieces known as allocation > > groups. Sharding enables better performance on highly parallel > > systems > > and helps to contain the damage when corruptions occur. The division > > of > > the filesystem into principal objects (allocation groups and inodes) > > means that there are ample opportunities to perform targeted checks > > and > > repairs on a subset of the filesystem." > I think that sounds cleaner > > > > > > > +The division of the filesystem into principal objects > > > > (allocation > > > > groups and > > > > +inodes) means that there are ample opportunities to perform > > > > targeted > > > > checks and > > > > +repairs on a subset of the filesystem. > > > > +While this is going on, other parts continue processing IO > > > > requests. > > > > +Even if a piece of filesystem metadata can only be regenerated > > > > by > > > > scanning the > > > > +entire system, the scan can still be done in the background > > > > while > > > > other file > > > > +operations continue. > > > > + > > > > +In summary, online fsck takes advantage of resource sharding and > > > > redundant > > > > +metadata to enable targeted checking and repair operations while > > > > the > > > > system > > > > +is running. > > > > +This capability will be coupled to automatic system management > > > > so > > > > that > > > > +autonomous self-healing of XFS maximizes service availability. > > > > > > > > > > Nits and paraphrases aside, I think this looks pretty good? > > > > Woot. Thanks for digging in! :) > > > Sure, no problem! > > > > Allison > > > >
