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