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