filesystems/xfs/xfs-online-fsck-design.rst

79 cross-references different types of metadata records with each other to look
364 - Inode records and indexes
383 errors and cross-references healthy records against other metadata to look for
424 Metadata structures in this category reflect records found in primary metadata,
510 compared the shadow records to the ondisk records.
520 metadata records.
590   coherent narrative cannot be formed from records collected, then the repair
594   designed to stage and validate all new records before committing the new
710 Targeted Fuzz Testing of Metadata Records
1077 The details of how these records are staged, written to disk, and committed
1154 - If the block contains records, do the records fit within the block?
1159 - Are the records contained inside the block free of obvious corruptions?
1168 Btree records spanning an interval of the btree keyspace are checked for
1200 cross-referencing records between metadata structures.
1210 keyspace is fully, sparsely, or not at all mapped to records.
1213 btree contains records mapping a certain extent of physical space without the
1222 - Do the records fit within the block?
1224 - Are the records contained inside the block free of obvious corruptions?
1238 Space allocation records are cross-referenced as follows:
1262 3. Free space btree records are cross-referenced as follows:
1274 4. Inode btree records are cross-referenced as follows:
1282    - Do set bits in the freemask correspond with inode records with zero link
1285 5. Inode records are cross-referenced as follows:
1295 6. File fork space mapping records are cross-referenced as follows:
1304 7. Reference count records are cross-referenced as follows:
1309      records mapped to a particular space extent and ignoring the owner info),
1310      are there the same number of reverse mapping records for each block as the
1319 …ernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/log/?h=scrub-detect-rmapbt-gaps>`_ records;
1321 `mergeable records
1322 ….kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/log/?h=scrub-detect-mergeable-records>`_;
1345 Leaf blocks contain attribute key records that point to the name and the value.
1390 Each data block contains variable-sized records associating a user-provided
1444 fixed-size metadata records -- each dabtree block contains a magic number, a
1446 The format of leaf and node records are the same -- each entry points to the
1447 next level down in the hierarchy, with dabtree node records pointing to dabtree
1448 leaf blocks, and dabtree leaf records pointing to non-dabtree blocks elsewhere
1458 - Do the records fit within the block?
1460 - Are the records contained inside the block free of obvious corruptions?
1862 * Linked lists of records introduce double pointer overhead which is very high
1870 memory, which means that individual records can be paged out if necessary.
1883 | The first edition of online repair inserted records into a new btree as  |
1899 1. Arrays of fixed-sized records (space management btrees, directory and
1902 2. Sparse arrays of fixed-sized records (quotas and link counts)
1923 complete records is important.
1984 Arrays of Fixed-Sized Records
1989 records indexed with a classic B+ tree.
1990 Directories have a set of fixed-size dirent records that point to the names,
1993 Quota counters and file link counters index records with numbers.
1994 During a repair, scrub needs to stage new records during the gathering step and
2000 iterator functions, and to deal with sparse records and sorting.
2001 The ``xfarray`` abstraction presents a linear array for fixed-size records atop
2010 Iteration of records is assumed to be necessary for all cases and will be
2013 The first type of caller handles records that are indexed by position.
2014 Gaps may exist between records, and a record may be updated multiple times
2017 The typical use case are quota records or file link count records.
2021 Gaps are defined to be null records, and null records are defined to be a
2023 Null records are detected by calling ``xfarray_element_is_null``.
2027 The second type of caller handles records that are not indexed by position
2030 These callers can add records to the array without caring about array indices
2033 For callers that require records to be presentable in a specific order (e.g.
2035 records; this function will be covered later.
2037 The third type of caller is a bag, which is useful for counting records.
2040 Records can be put in the bag in any order, they can be removed from the bag
2041 at any time, and uniqueness of records is left to callers.
2053 Most users of the xfarray require the ability to iterate the records stored in
2066 All users of this idiom must be prepared to handle null records or must already
2088 that for performance reasons, online repair ought to load batches of records
2089 into btree record blocks instead of inserting records into a new btree one at a
2092 of the records, so naturally the xfarray must also support sorting the record
2103 To sort records in a reasonably short amount of time, ``xfarray`` takes
2116 * Loading a small number of xfarray records from potentially disparate parts
2128 records into a memory buffer and using the kernel heapsort to identify the
2133 Typical ninther implementations pick three unique triads of records, sort each
2162 records: arbitrary byte sequences of finite length.
2212 mapping records: the existing rmap btree code!
2347 the incore records to be sorted prior to commit, but was very slow and leaked
2349 Loading records one at a time also meant that repair could not control the
2353 rebuilding a btree index from a collection of records -- bulk btree loading.
2366 be stored in the new btree, and sort the records.
2371 First, the geometry computation computes the minimum and maximum records that
2374 Roughly speaking, the maximum number of records is::
2379 which means the minimum number of records is half of maxrecs::
2425 - For inode-rooted btrees where the records in the top level do not fit in the
2430 - For inode-rooted btrees where the records in the top level can be stored in
2483 rest of the block with records, and adds the new leaf block to a list of
2580 1. Walk the reverse mapping records to generate ``struct xfs_inobt_rec``
2581    records from the inode chunk information and a bitmap of the old inode btree
2584 2. Append the records to an xfarray in inode order.
2593 5. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2604 inode records, which means that the inode btrees can be rebuilt from the
2606 Reverse mapping records with an owner of ``XFS_RMAP_OWN_INOBT`` marks the
2614 records in the free space btrees nor any records in the reference count btree.
2628 the inode btree with all inode chunk records, and a second time to populate the
2629 free inode btree with records for chunks that have free non-sparse inodes.
2630 The number of records for the inode btree is the number of xfarray records,
2632 records are stored in the xfarray.
2642 Reverse mapping records are used to rebuild the reference count information.
2660 the free space btree already records which blocks are free.
2661 Extents being used to stage copy-on-write operations should be the only records
2668 1. Walk the reverse mapping records to generate ``struct xfs_refcount_irec``
2669    records for any space having more than one reverse mapping and add them to
2671    Any records owned by ``XFS_RMAP_OWN_COW`` are also added to the xfarray
2675    Use any records owned by ``XFS_RMAP_OWN_REFC`` to create a bitmap of old
2678 2. Sort the records in physical extent order, putting the CoW staging extents
2680    This matches the sorting order of records in the refcount btree.
2687 5. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2695 generate refcount information from reverse mapping records.
2697 - Until the reverse mapping btree runs out of records:
2701   - Collect all records with the same starting block from the btree and put
2737 1. Walk the reverse mapping records to generate ``struct xfs_bmbt_rec``
2738    records from the reverse mapping records for that inode and fork.
2739    Append these records to an xfarray.
2741    records.
2746 3. Sort the records in file offset order.
2748 4. If the extent records would fit in the inode fork immediate area, commit the
2749    records to that immediate area and skip to step 8.
2753 6. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2789 As part of a repair, online fsck relies heavily on the reverse mapping records
2791 Cross referencing rmap records with other rmap records is necessary because
2819 4. For each candidate extent, count the number of reverse mapping records for
2862 rmap records with special owner codes: ``XFS_RMAP_OWN_REFC`` for the refcount
2882 mapping record walk that creates the records for the new btree.
2889 1. Walk the reverse mapping records to generate ``struct xfs_alloc_rec_incore``
2890    records from the gaps in the reverse mapping btree.
2892 2. Append the records to an xfarray.
2900 5. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2912 First, free space is not explicitly tracked in the reverse mapping records.
2913 Hence, the new free space records must be inferred from gaps in the physical
2926 information changes the number of free space records, repair must re-estimate
2939 Blocks put onto the AGFL have reverse mapping records with the owner
2943 When repair walks reverse mapping records to synthesize free space records, it
2945 ``XFS_RMAP_OWN_AG`` records.
2966 records with ``XFS_RMAP_OWN_AG`` as the owner.
2967 The full process of gathering reverse mapping records and building a new btree
2970 discussion is that the new rmap btree will not contain any records for the old
2973 corresponding to the gaps in the new rmap btree records, and then clearing the
3009 Inode records must be handled carefully, because they have both ondisk records
3042 Similar to inodes, quota records ("dquots") also have both ondisk records and
3186 (*itable*) of fixed-size records (*inodes*) describing a file's attributes and
3635 Therefore, online quotacheck records file resource usage to a shadow dquot
3708 filesystem, and per-file link count records are stored in a sparse ``xfarray``
3761 Case Study: Rebuilding Reverse Mapping Records
3765 walk the surviving ondisk metadata looking for replacement metadata records,
3784 scan for reverse mapping records.
3786 1. Set up an xfbtree to stage rmap records.
3825 8. Compute the new btree geometry using the number of rmap records in the
3848 information for the realtime volume, and quota records.
3855 structures (such as bitmaps and quota records) compute array element offsets in
3928 | - Directory entry blocks and quota records record the file fork offset   |
4023 The new log item records the progress of the exchange to ensure that once an
4027 in the superblock protects these new log item records from being replayed on
4040 | records that might not readable by all kernels that could mount this     |
4304 Each counter records the number of free extents that start in that bitmap block
4340 Attribute leaf blocks contain variable-sized records that associate
4683       3. Position one slab cursor at the start of the inode's records in the
4691          dirent_pos fields of the records under each cursor.
4718 2. The next pass records parent pointers pointing to the directories noted
4816    forks, inode indices, inode records, and the forks of every file on the
4827 e. The file forks depends on consistency within inode records and the space
4831 f. Inode records depends on consistency within the inode metadata indices.
4833 g. Realtime space metadata depend on the inode records and data forks of the
4890 consumption, inode btree records.