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)
1919 complete records is important.
1977 Arrays of Fixed-Sized Records
1982 records indexed with a classic B+ tree.
1983 Directories have a set of fixed-size dirent records that point to the names,
1986 Quota counters and file link counters index records with numbers.
1987 During a repair, scrub needs to stage new records during the gathering step and
1993 iterator functions, and to deal with sparse records and sorting.
1994 The ``xfarray`` abstraction presents a linear array for fixed-size records atop
2003 Iteration of records is assumed to be necessary for all cases and will be
2006 The first type of caller handles records that are indexed by position.
2007 Gaps may exist between records, and a record may be updated multiple times
2010 The typical use case are quota records or file link count records.
2014 Gaps are defined to be null records, and null records are defined to be a
2016 Null records are detected by calling ``xfarray_element_is_null``.
2020 The second type of caller handles records that are not indexed by position
2023 These callers can add records to the array without caring about array indices
2026 For callers that require records to be presentable in a specific order (e.g.
2028 records; this function will be covered later.
2030 The third type of caller is a bag, which is useful for counting records.
2033 Records can be put in the bag in any order, they can be removed from the bag
2034 at any time, and uniqueness of records is left to callers.
2046 Most users of the xfarray require the ability to iterate the records stored in
2059 All users of this idiom must be prepared to handle null records or must already
2081 that for performance reasons, online repair ought to load batches of records
2082 into btree record blocks instead of inserting records into a new btree one at a
2085 of the records, so naturally the xfarray must also support sorting the record
2096 To sort records in a reasonably short amount of time, ``xfarray`` takes
2109 * Loading a small number of xfarray records from potentially disparate parts
2121 records into a memory buffer and using the kernel heapsort to identify the
2126 Typical ninther implementations pick three unique triads of records, sort each
2155 records: arbitrary byte sequences of finite length.
2205 mapping records: the existing rmap btree code!
2339 the incore records to be sorted prior to commit, but was very slow and leaked
2341 Loading records one at a time also meant that repair could not control the
2345 rebuilding a btree index from a collection of records -- bulk btree loading.
2358 be stored in the new btree, and sort the records.
2363 First, the geometry computation computes the minimum and maximum records that
2366 Roughly speaking, the maximum number of records is::
2371 which means the minimum number of records is half of maxrecs::
2417 - For inode-rooted btrees where the records in the top level do not fit in the
2422 - For inode-rooted btrees where the records in the top level can be stored in
2475 rest of the block with records, and adds the new leaf block to a list of
2572 1. Walk the reverse mapping records to generate ``struct xfs_inobt_rec``
2573    records from the inode chunk information and a bitmap of the old inode btree
2576 2. Append the records to an xfarray in inode order.
2585 5. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2596 inode records, which means that the inode btrees can be rebuilt from the
2598 Reverse mapping records with an owner of ``XFS_RMAP_OWN_INOBT`` marks the
2606 records in the free space btrees nor any records in the reference count btree.
2620 the inode btree with all inode chunk records, and a second time to populate the
2621 free inode btree with records for chunks that have free non-sparse inodes.
2622 The number of records for the inode btree is the number of xfarray records,
2624 records are stored in the xfarray.
2634 Reverse mapping records are used to rebuild the reference count information.
2652 the free space btree already records which blocks are free.
2653 Extents being used to stage copy-on-write operations should be the only records
2660 1. Walk the reverse mapping records to generate ``struct xfs_refcount_irec``
2661    records for any space having more than one reverse mapping and add them to
2663    Any records owned by ``XFS_RMAP_OWN_COW`` are also added to the xfarray
2667    Use any records owned by ``XFS_RMAP_OWN_REFC`` to create a bitmap of old
2670 2. Sort the records in physical extent order, putting the CoW staging extents
2672    This matches the sorting order of records in the refcount btree.
2679 5. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2687 generate refcount information from reverse mapping records.
2689 - Until the reverse mapping btree runs out of records:
2693   - Collect all records with the same starting block from the btree and put
2729 1. Walk the reverse mapping records to generate ``struct xfs_bmbt_rec``
2730    records from the reverse mapping records for that inode and fork.
2731    Append these records to an xfarray.
2733    records.
2738 3. Sort the records in file offset order.
2740 4. If the extent records would fit in the inode fork immediate area, commit the
2741    records to that immediate area and skip to step 8.
2745 6. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2781 As part of a repair, online fsck relies heavily on the reverse mapping records
2783 Cross referencing rmap records with other rmap records is necessary because
2812 4. For each candidate extent, count the number of reverse mapping records for
2855 rmap records with special owner codes: ``XFS_RMAP_OWN_REFC`` for the refcount
2875 mapping record walk that creates the records for the new btree.
2882 1. Walk the reverse mapping records to generate ``struct xfs_alloc_rec_incore``
2883    records from the gaps in the reverse mapping btree.
2885 2. Append the records to an xfarray.
2893 5. Use ``xfs_btree_bload`` to write the xfarray records to btree blocks and
2905 First, free space is not explicitly tracked in the reverse mapping records.
2906 Hence, the new free space records must be inferred from gaps in the physical
2919 information changes the number of free space records, repair must re-estimate
2932 Blocks put onto the AGFL have reverse mapping records with the owner
2936 When repair walks reverse mapping records to synthesize free space records, it
2938 ``XFS_RMAP_OWN_AG`` records.
2959 records with ``XFS_RMAP_OWN_AG`` as the owner.
2960 The full process of gathering reverse mapping records and building a new btree
2963 discussion is that the new rmap btree will not contain any records for the old
2966 corresponding to the gaps in the new rmap btree records, and then clearing the
3002 Inode records must be handled carefully, because they have both ondisk records
3035 Similar to inodes, quota records ("dquots") also have both ondisk records and
3179 (*itable*) of fixed-size records (*inodes*) describing a file's attributes and
3628 Therefore, online quotacheck records file resource usage to a shadow dquot
3701 filesystem, and per-file link count records are stored in a sparse ``xfarray``
3754 Case Study: Rebuilding Reverse Mapping Records
3758 walk the surviving ondisk metadata looking for replacement metadata records,
3777 scan for reverse mapping records.
3779 1. Set up an xfbtree to stage rmap records.
3818 8. Compute the new btree geometry using the number of rmap records in the
3841 information for the realtime volume, and quota records.
3848 structures (such as bitmaps and quota records) compute array element offsets in
3922 | - Directory entry blocks and quota records record the file fork offset   |
4016 the reverse-mapping extent swap code, but records intermedia progress in the
4021 The new log item records the progress of the exchange to ensure that once an
4025 in the superblock protects these new log item records from being replayed on
4038 | 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
4729       3. Position one slab cursor at the start of the inode's records in the
4737          ``name_hash``, and ``name_cookie`` fields of the records under each
4773 2. The next pass records parent pointers pointing to the directories noted
5003    forks, inode indices, inode records, and the forks of every file on the
5014 e. The file forks depends on consistency within inode records and the space
5018 f. Inode records depends on consistency within the inode metadata indices.
5020 g. Realtime space metadata depend on the inode records and data forks of the
5077 consumption, inode btree records.