// SPDX-License-Identifier: GPL-2.0-or-later /* * Copyright (C) 2018-2023 Oracle. All Rights Reserved. * Author: Darrick J. Wong <[email protected]> */ #include "xfs.h" #include "xfs_fs.h" #include "xfs_shared.h" #include "xfs_format.h" #include "xfs_trans_resv.h" #include "xfs_mount.h" #include "xfs_defer.h" #include "xfs_btree.h" #include "xfs_btree_staging.h" #include "xfs_inode.h" #include "xfs_bit.h" #include "xfs_log_format.h" #include "xfs_trans.h" #include "xfs_sb.h" #include "xfs_alloc.h" #include "xfs_ialloc.h" #include "xfs_rmap.h" #include "xfs_rmap_btree.h" #include "xfs_refcount.h" #include "xfs_refcount_btree.h" #include "xfs_error.h" #include "xfs_ag.h" #include "xfs_health.h" #include "scrub/xfs_scrub.h" #include "scrub/scrub.h" #include "scrub/common.h" #include "scrub/btree.h" #include "scrub/trace.h" #include "scrub/repair.h" #include "scrub/bitmap.h" #include "scrub/agb_bitmap.h" #include "scrub/xfile.h" #include "scrub/xfarray.h" #include "scrub/newbt.h" #include "scrub/reap.h" #include "scrub/rcbag.h" /* * Rebuilding the Reference Count Btree * ==================================== * * This algorithm is "borrowed" from xfs_repair. Imagine the rmap * entries as rectangles representing extents of physical blocks, and * that the rectangles can be laid down to allow them to overlap each * other; then we know that we must emit a refcnt btree entry wherever * the amount of overlap changes, i.e. the emission stimulus is * level-triggered: * * - --- * -- ----- ---- --- ------ * -- ---- ----------- ---- --------- * -------------------------------- ----------- * ^ ^ ^^ ^^ ^ ^^ ^^^ ^^^^ ^ ^^ ^ ^ ^ * 2 1 23 21 3 43 234 2123 1 01 2 3 0 * * For our purposes, a rmap is a tuple (startblock, len, fileoff, owner). * * Note that in the actual refcnt btree we don't store the refcount < 2 * cases because the bnobt tells us which blocks are free; single-use * blocks aren't recorded in the bnobt or the refcntbt. If the rmapbt * supports storing multiple entries covering a given block we could * theoretically dispense with the refcntbt and simply count rmaps, but * that's inefficient in the (hot) write path, so we'll take the cost of * the extra tree to save time. Also there's no guarantee that rmap * will be enabled. * * Given an array of rmaps sorted by physical block number, a starting * physical block (sp), a bag to hold rmaps that cover sp, and the next * physical block where the level changes (np), we can reconstruct the * refcount btree as follows: * * While there are still unprocessed rmaps in the array, * - Set sp to the physical block (pblk) of the next unprocessed rmap. * - Add to the bag all rmaps in the array where startblock == sp. * - Set np to the physical block where the bag size will change. This * is the minimum of (the pblk of the next unprocessed rmap) and * (startblock + len of each rmap in the bag). * - Record the bag size as old_bag_size. * * - While the bag isn't empty, * - Remove from the bag all rmaps where startblock + len == np. * - Add to the bag all rmaps in the array where startblock == np. * - If the bag size isn't old_bag_size, store the refcount entry * (sp, np - sp, bag_size) in the refcnt btree. * - If the bag is empty, break out of the inner loop. * - Set old_bag_size to the bag size * - Set sp = np. * - Set np to the physical block where the bag size will change. * This is the minimum of (the pblk of the next unprocessed rmap) * and (startblock + len of each rmap in the bag). * * Like all the other repairers, we make a list of all the refcount * records we need, then reinitialize the refcount btree root and * insert all the records. */ struct xrep_refc { … }; /* Set us up to repair refcount btrees. */ int xrep_setup_ag_refcountbt( struct xfs_scrub *sc) { … } /* Check for any obvious conflicts with this shared/CoW staging extent. */ STATIC int xrep_refc_check_ext( struct xfs_scrub *sc, const struct xfs_refcount_irec *rec) { … } /* Record a reference count extent. */ STATIC int xrep_refc_stash( struct xrep_refc *rr, enum xfs_refc_domain domain, xfs_agblock_t agbno, xfs_extlen_t len, uint64_t refcount) { … } /* Record a CoW staging extent. */ STATIC int xrep_refc_stash_cow( struct xrep_refc *rr, xfs_agblock_t agbno, xfs_extlen_t len) { … } /* Decide if an rmap could describe a shared extent. */ static inline bool xrep_refc_rmap_shareable( struct xfs_mount *mp, const struct xfs_rmap_irec *rmap) { … } /* * Walk along the reverse mapping records until we find one that could describe * a shared extent. */ STATIC int xrep_refc_walk_rmaps( struct xrep_refc *rr, struct xfs_rmap_irec *rmap, bool *have_rec) { … } static inline uint32_t xrep_refc_encode_startblock( const struct xfs_refcount_irec *irec) { … } /* Sort in the same order as the ondisk records. */ static int xrep_refc_extent_cmp( const void *a, const void *b) { … } /* * Sort the refcount extents by startblock or else the btree records will be in * the wrong order. Make sure the records do not overlap in physical space. */ STATIC int xrep_refc_sort_records( struct xrep_refc *rr) { … } /* * Walk forward through the rmap btree to collect all rmaps starting at * @bno in @rmap_bag. These represent the file(s) that share ownership of * the current block. Upon return, the rmap cursor points to the last record * satisfying the startblock constraint. */ static int xrep_refc_push_rmaps_at( struct xrep_refc *rr, struct rcbag *rcstack, xfs_agblock_t bno, struct xfs_rmap_irec *rmap, bool *have) { … } /* Iterate all the rmap records to generate reference count data. */ STATIC int xrep_refc_find_refcounts( struct xrep_refc *rr) { … } /* Retrieve refcountbt data for bulk load. */ STATIC int xrep_refc_get_records( struct xfs_btree_cur *cur, unsigned int idx, struct xfs_btree_block *block, unsigned int nr_wanted, void *priv) { … } /* Feed one of the new btree blocks to the bulk loader. */ STATIC int xrep_refc_claim_block( struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr, void *priv) { … } /* Update the AGF counters. */ STATIC int xrep_refc_reset_counters( struct xrep_refc *rr) { … } /* * Use the collected refcount information to stage a new refcount btree. If * this is successful we'll return with the new btree root information logged * to the repair transaction but not yet committed. */ STATIC int xrep_refc_build_new_tree( struct xrep_refc *rr) { … } /* * Now that we've logged the roots of the new btrees, invalidate all of the * old blocks and free them. */ STATIC int xrep_refc_remove_old_tree( struct xrep_refc *rr) { … } /* Rebuild the refcount btree. */ int xrep_refcountbt( struct xfs_scrub *sc) { … }
Codebase Browser
linux