fs/xfs/scrub/refcount.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2017 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_format.h"
  10 #include "xfs_btree.h"
  11 #include "xfs_rmap.h"
  12 #include "xfs_refcount.h"
  13 #include "scrub/scrub.h"
  14 #include "scrub/common.h"
  15 #include "scrub/btree.h"
  16
  17 /*
  18  * Set us up to scrub reference count btrees.
  19  */
  20 int
  21 xchk_setup_ag_refcountbt(
  22         struct xfs_scrub        *sc)
  23 {
  24         return xchk_setup_ag_btree(sc, false);
  25 }
  26
  27 /* Reference count btree scrubber. */
  28
  29 /*
  30  * Confirming Reference Counts via Reverse Mappings
  31  *
  32  * We want to count the reverse mappings overlapping a refcount record
  33  * (bno, len, refcount), allowing for the possibility that some of the
  34  * overlap may come from smaller adjoining reverse mappings, while some
  35  * comes from single extents which overlap the range entirely.  The
  36  * outer loop is as follows:
  37  *
  38  * 1. For all reverse mappings overlapping the refcount extent,
  39  *    a. If a given rmap completely overlaps, mark it as seen.
  40  *    b. Otherwise, record the fragment (in agbno order) for later
  41  *       processing.
  42  *
  43  * Once we've seen all the rmaps, we know that for all blocks in the
  44  * refcount record we want to find $refcount owners and we've already
  45  * visited $seen extents that overlap all the blocks.  Therefore, we
  46  * need to find ($refcount - $seen) owners for every block in the
  47  * extent; call that quantity $target_nr.  Proceed as follows:
  48  *
  49  * 2. Pull the first $target_nr fragments from the list; all of them
  50  *    should start at or before the start of the extent.
  51  *    Call this subset of fragments the working set.
  52  * 3. Until there are no more unprocessed fragments,
  53  *    a. Find the shortest fragments in the set and remove them.
  54  *    b. Note the block number of the end of these fragments.
  55  *    c. Pull the same number of fragments from the list.  All of these
  56  *       fragments should start at the block number recorded in the
  57  *       previous step.
  58  *    d. Put those fragments in the set.
  59  * 4. Check that there are $target_nr fragments remaining in the list,
  60  *    and that they all end at or beyond the end of the refcount extent.
  61  *
  62  * If the refcount is correct, all the check conditions in the algorithm
  63  * should always hold true.  If not, the refcount is incorrect.
  64  */
  65 struct xchk_refcnt_frag {
  66         struct list_head        list;
  67         struct xfs_rmap_irec    rm;
  68 };
  69
  70 struct xchk_refcnt_check {
  71         struct xfs_scrub        *sc;
  72         struct list_head        fragments;
  73
  74         /* refcount extent we're examining */
  75         xfs_agblock_t           bno;
  76         xfs_extlen_t            len;
  77         xfs_nlink_t             refcount;
  78
  79         /* number of owners seen */
  80         xfs_nlink_t             seen;
  81 };
  82
  83 /*
  84  * Decide if the given rmap is large enough that we can redeem it
  85  * towards refcount verification now, or if it's a fragment, in
  86  * which case we'll hang onto it in the hopes that we'll later
  87  * discover that we've collected exactly the correct number of
  88  * fragments as the refcountbt says we should have.
  89  */
  90 STATIC int
  91 xchk_refcountbt_rmap_check(
  92         struct xfs_btree_cur            *cur,
  93         struct xfs_rmap_irec            *rec,
  94         void                            *priv)
  95 {
  96         struct xchk_refcnt_check        *refchk = priv;
  97         struct xchk_refcnt_frag         *frag;
  98         xfs_agblock_t                   rm_last;
  99         xfs_agblock_t                   rc_last;
 100         int                             error = 0;
 101
 102         if (xchk_should_terminate(refchk->sc, &error))
 103                 return error;
 104
 105         rm_last = rec->rm_startblock + rec->rm_blockcount - 1;
 106         rc_last = refchk->bno + refchk->len - 1;
 107
 108         /* Confirm that a single-owner refc extent is a CoW stage. */
 109         if (refchk->refcount == 1 && rec->rm_owner != XFS_RMAP_OWN_COW) {
 110                 xchk_btree_xref_set_corrupt(refchk->sc, cur, 0);
 111                 return 0;
 112         }
 113
 114         if (rec->rm_startblock <= refchk->bno && rm_last >= rc_last) {
 115                 /*
 116                  * The rmap overlaps the refcount record, so we can confirm
 117                  * one refcount owner seen.
 118                  */
 119                 refchk->seen++;
 120         } else {
 121                 /*
 122                  * This rmap covers only part of the refcount record, so
 123                  * save the fragment for later processing.  If the rmapbt
 124                  * is healthy each rmap_irec we see will be in agbno order
 125                  * so we don't need insertion sort here.
 126                  */
 127                 frag = kmem_alloc(sizeof(struct xchk_refcnt_frag),
 128                                 KM_MAYFAIL);
 129                 if (!frag)
 130                         return -ENOMEM;
 131                 memcpy(&frag->rm, rec, sizeof(frag->rm));
 132                 list_add_tail(&frag->list, &refchk->fragments);
 133         }
 134
 135         return 0;
 136 }
 137
 138 /*
 139  * Given a bunch of rmap fragments, iterate through them, keeping
 140  * a running tally of the refcount.  If this ever deviates from
 141  * what we expect (which is the refcountbt's refcount minus the
 142  * number of extents that totally covered the refcountbt extent),
 143  * we have a refcountbt error.
 144  */
 145 STATIC void
 146 xchk_refcountbt_process_rmap_fragments(
 147         struct xchk_refcnt_check        *refchk)
 148 {
 149         struct list_head                worklist;
 150         struct xchk_refcnt_frag         *frag;
 151         struct xchk_refcnt_frag         *n;
 152         xfs_agblock_t                   bno;
 153         xfs_agblock_t                   rbno;
 154         xfs_agblock_t                   next_rbno;
 155         xfs_nlink_t                     nr;
 156         xfs_nlink_t                     target_nr;
 157
 158         target_nr = refchk->refcount - refchk->seen;
 159         if (target_nr == 0)
 160                 return;
 161
 162         /*
 163          * There are (refchk->rc.rc_refcount - refchk->nr refcount)
 164          * references we haven't found yet.  Pull that many off the
 165          * fragment list and figure out where the smallest rmap ends
 166          * (and therefore the next rmap should start).  All the rmaps
 167          * we pull off should start at or before the beginning of the
 168          * refcount record's range.
 169          */
 170         INIT_LIST_HEAD(&worklist);
 171         rbno = NULLAGBLOCK;
 172
 173         /* Make sure the fragments actually /are/ in agbno order. */
 174         bno = 0;
 175         list_for_each_entry(frag, &refchk->fragments, list) {
 176                 if (frag->rm.rm_startblock < bno)
 177                         goto done;
 178                 bno = frag->rm.rm_startblock;
 179         }
 180
 181         /*
 182          * Find all the rmaps that start at or before the refc extent,
 183          * and put them on the worklist.
 184          */
 185         nr = 0;
 186         list_for_each_entry_safe(frag, n, &refchk->fragments, list) {
 187                 if (frag->rm.rm_startblock > refchk->bno || nr > target_nr)
 188                         break;
 189                 bno = frag->rm.rm_startblock + frag->rm.rm_blockcount;
 190                 if (bno < rbno)
 191                         rbno = bno;
 192                 list_move_tail(&frag->list, &worklist);
 193                 nr++;
 194         }
 195
 196         /*
 197          * We should have found exactly $target_nr rmap fragments starting
 198          * at or before the refcount extent.
 199          */
 200         if (nr != target_nr)
 201                 goto done;
 202
 203         while (!list_empty(&refchk->fragments)) {
 204                 /* Discard any fragments ending at rbno from the worklist. */
 205                 nr = 0;
 206                 next_rbno = NULLAGBLOCK;
 207                 list_for_each_entry_safe(frag, n, &worklist, list) {
 208                         bno = frag->rm.rm_startblock + frag->rm.rm_blockcount;
 209                         if (bno != rbno) {
 210                                 if (bno < next_rbno)
 211                                         next_rbno = bno;
 212                                 continue;
 213                         }
 214                         list_del(&frag->list);
 215                         kmem_free(frag);
 216                         nr++;
 217                 }
 218
 219                 /* Try to add nr rmaps starting at rbno to the worklist. */
 220                 list_for_each_entry_safe(frag, n, &refchk->fragments, list) {
 221                         bno = frag->rm.rm_startblock + frag->rm.rm_blockcount;
 222                         if (frag->rm.rm_startblock != rbno)
 223                                 goto done;
 224                         list_move_tail(&frag->list, &worklist);
 225                         if (next_rbno > bno)
 226                                 next_rbno = bno;
 227                         nr--;
 228                         if (nr == 0)
 229                                 break;
 230                 }
 231
 232                 /*
 233                  * If we get here and nr > 0, this means that we added fewer
 234                  * items to the worklist than we discarded because the fragment
 235                  * list ran out of items.  Therefore, we cannot maintain the
 236                  * required refcount.  Something is wrong, so we're done.
 237                  */
 238                 if (nr)
 239                         goto done;
 240
 241                 rbno = next_rbno;
 242         }
 243
 244         /*
 245          * Make sure the last extent we processed ends at or beyond
 246          * the end of the refcount extent.
 247          */
 248         if (rbno < refchk->bno + refchk->len)
 249                 goto done;
 250
 251         /* Actually record us having seen the remaining refcount. */
 252         refchk->seen = refchk->refcount;
 253 done:
 254         /* Delete fragments and work list. */
 255         list_for_each_entry_safe(frag, n, &worklist, list) {
 256                 list_del(&frag->list);
 257                 kmem_free(frag);
 258         }
 259         list_for_each_entry_safe(frag, n, &refchk->fragments, list) {
 260                 list_del(&frag->list);
 261                 kmem_free(frag);
 262         }
 263 }
 264
 265 /* Use the rmap entries covering this extent to verify the refcount. */
 266 STATIC void
 267 xchk_refcountbt_xref_rmap(
 268         struct xfs_scrub                *sc,
 269         xfs_agblock_t                   bno,
 270         xfs_extlen_t                    len,
 271         xfs_nlink_t                     refcount)
 272 {
 273         struct xchk_refcnt_check        refchk = {
 274                 .sc = sc,
 275                 .bno = bno,
 276                 .len = len,
 277                 .refcount = refcount,
 278                 .seen = 0,
 279         };
 280         struct xfs_rmap_irec            low;
 281         struct xfs_rmap_irec            high;
 282         struct xchk_refcnt_frag         *frag;
 283         struct xchk_refcnt_frag         *n;
 284         int                             error;
 285
 286         if (!sc->sa.rmap_cur || xchk_skip_xref(sc->sm))
 287                 return;
 288
 289         /* Cross-reference with the rmapbt to confirm the refcount. */
 290         memset(&low, 0, sizeof(low));
 291         low.rm_startblock = bno;
 292         memset(&high, 0xFF, sizeof(high));
 293         high.rm_startblock = bno + len - 1;
 294
 295         INIT_LIST_HEAD(&refchk.fragments);
 296         error = xfs_rmap_query_range(sc->sa.rmap_cur, &low, &high,
 297                         &xchk_refcountbt_rmap_check, &refchk);
 298         if (!xchk_should_check_xref(sc, &error, &sc->sa.rmap_cur))
 299                 goto out_free;
 300
 301         xchk_refcountbt_process_rmap_fragments(&refchk);
 302         if (refcount != refchk.seen)
 303                 xchk_btree_xref_set_corrupt(sc, sc->sa.rmap_cur, 0);
 304
 305 out_free:
 306         list_for_each_entry_safe(frag, n, &refchk.fragments, list) {
 307                 list_del(&frag->list);
 308                 kmem_free(frag);
 309         }
 310 }
 311
 312 /* Cross-reference with the other btrees. */
 313 STATIC void
 314 xchk_refcountbt_xref(
 315         struct xfs_scrub        *sc,
 316         xfs_agblock_t           agbno,
 317         xfs_extlen_t            len,
 318         xfs_nlink_t             refcount)
 319 {
 320         if (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT)
 321                 return;
 322
 323         xchk_xref_is_used_space(sc, agbno, len);
 324         xchk_xref_is_not_inode_chunk(sc, agbno, len);
 325         xchk_refcountbt_xref_rmap(sc, agbno, len, refcount);
 326 }
 327
 328 /* Scrub a refcountbt record. */
 329 STATIC int
 330 xchk_refcountbt_rec(
 331         struct xchk_btree       *bs,
 332         union xfs_btree_rec     *rec)
 333 {
 334         struct xfs_mount        *mp = bs->cur->bc_mp;
 335         xfs_agblock_t           *cow_blocks = bs->private;
 336         xfs_agnumber_t          agno = bs->cur->bc_ag.agno;
 337         xfs_agblock_t           bno;
 338         xfs_extlen_t            len;
 339         xfs_nlink_t             refcount;
 340         bool                    has_cowflag;
 341
 342         bno = be32_to_cpu(rec->refc.rc_startblock);
 343         len = be32_to_cpu(rec->refc.rc_blockcount);
 344         refcount = be32_to_cpu(rec->refc.rc_refcount);
 345
 346         /* Only CoW records can have refcount == 1. */
 347         has_cowflag = (bno & XFS_REFC_COW_START);
 348         if ((refcount == 1 && !has_cowflag) || (refcount != 1 && has_cowflag))
 349                 xchk_btree_set_corrupt(bs->sc, bs->cur, 0);
 350         if (has_cowflag)
 351                 (*cow_blocks) += len;
 352
 353         /* Check the extent. */
 354         bno &= ~XFS_REFC_COW_START;
 355         if (bno + len <= bno ||
 356             !xfs_verify_agbno(mp, agno, bno) ||
 357             !xfs_verify_agbno(mp, agno, bno + len - 1))
 358                 xchk_btree_set_corrupt(bs->sc, bs->cur, 0);
 359
 360         if (refcount == 0)
 361                 xchk_btree_set_corrupt(bs->sc, bs->cur, 0);
 362
 363         xchk_refcountbt_xref(bs->sc, bno, len, refcount);
 364
 365         return 0;
 366 }
 367
 368 /* Make sure we have as many refc blocks as the rmap says. */
 369 STATIC void
 370 xchk_refcount_xref_rmap(
 371         struct xfs_scrub        *sc,
 372         xfs_filblks_t           cow_blocks)
 373 {
 374         xfs_extlen_t            refcbt_blocks = 0;
 375         xfs_filblks_t           blocks;
 376         int                     error;
 377
 378         if (!sc->sa.rmap_cur || xchk_skip_xref(sc->sm))
 379                 return;
 380
 381         /* Check that we saw as many refcbt blocks as the rmap knows about. */
 382         error = xfs_btree_count_blocks(sc->sa.refc_cur, &refcbt_blocks);
 383         if (!xchk_btree_process_error(sc, sc->sa.refc_cur, 0, &error))
 384                 return;
 385         error = xchk_count_rmap_ownedby_ag(sc, sc->sa.rmap_cur,
 386                         &XFS_RMAP_OINFO_REFC, &blocks);
 387         if (!xchk_should_check_xref(sc, &error, &sc->sa.rmap_cur))
 388                 return;
 389         if (blocks != refcbt_blocks)
 390                 xchk_btree_xref_set_corrupt(sc, sc->sa.rmap_cur, 0);
 391
 392         /* Check that we saw as many cow blocks as the rmap knows about. */
 393         error = xchk_count_rmap_ownedby_ag(sc, sc->sa.rmap_cur,
 394                         &XFS_RMAP_OINFO_COW, &blocks);
 395         if (!xchk_should_check_xref(sc, &error, &sc->sa.rmap_cur))
 396                 return;
 397         if (blocks != cow_blocks)
 398                 xchk_btree_xref_set_corrupt(sc, sc->sa.rmap_cur, 0);
 399 }
 400
 401 /* Scrub the refcount btree for some AG. */
 402 int
 403 xchk_refcountbt(
 404         struct xfs_scrub        *sc)
 405 {
 406         xfs_agblock_t           cow_blocks = 0;
 407         int                     error;
 408
 409         error = xchk_btree(sc, sc->sa.refc_cur, xchk_refcountbt_rec,
 410                         &XFS_RMAP_OINFO_REFC, &cow_blocks);
 411         if (error)
 412                 return error;
 413
 414         xchk_refcount_xref_rmap(sc, cow_blocks);
 415
 416         return 0;
 417 }
 418
 419 /* xref check that a cow staging extent is marked in the refcountbt. */
 420 void
 421 xchk_xref_is_cow_staging(
 422         struct xfs_scrub                *sc,
 423         xfs_agblock_t                   agbno,
 424         xfs_extlen_t                    len)
 425 {
 426         struct xfs_refcount_irec        rc;
 427         bool                            has_cowflag;
 428         int                             has_refcount;
 429         int                             error;
 430
 431         if (!sc->sa.refc_cur || xchk_skip_xref(sc->sm))
 432                 return;
 433
 434         /* Find the CoW staging extent. */
 435         error = xfs_refcount_lookup_le(sc->sa.refc_cur,
 436                         agbno + XFS_REFC_COW_START, &has_refcount);
 437         if (!xchk_should_check_xref(sc, &error, &sc->sa.refc_cur))
 438                 return;
 439         if (!has_refcount) {
 440                 xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0);
 441                 return;
 442         }
 443
 444         error = xfs_refcount_get_rec(sc->sa.refc_cur, &rc, &has_refcount);
 445         if (!xchk_should_check_xref(sc, &error, &sc->sa.refc_cur))
 446                 return;
 447         if (!has_refcount) {
 448                 xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0);
 449                 return;
 450         }
 451
 452         /* CoW flag must be set, refcount must be 1. */
 453         has_cowflag = (rc.rc_startblock & XFS_REFC_COW_START);
 454         if (!has_cowflag || rc.rc_refcount != 1)
 455                 xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0);
 456
 457         /* Must be at least as long as what was passed in */
 458         if (rc.rc_blockcount < len)
 459                 xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0);
 460 }
 461
 462 /*
 463  * xref check that the extent is not shared.  Only file data blocks
 464  * can have multiple owners.
 465  */
 466 void
 467 xchk_xref_is_not_shared(
 468         struct xfs_scrub        *sc,
 469         xfs_agblock_t           agbno,
 470         xfs_extlen_t            len)
 471 {
 472         bool                    shared;
 473         int                     error;
 474
 475         if (!sc->sa.refc_cur || xchk_skip_xref(sc->sm))
 476                 return;
 477
 478         error = xfs_refcount_has_record(sc->sa.refc_cur, agbno, len, &shared);
 479         if (!xchk_should_check_xref(sc, &error, &sc->sa.refc_cur))
 480                 return;
 481         if (shared)
 482                 xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0);
 483 }