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 } 484