Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /*
3 : * Copyright (C) 2017-2023 Oracle. All Rights Reserved.
4 : * Author: Darrick J. Wong <djwong@kernel.org>
5 : */
6 : #include "xfs.h"
7 : #include "xfs_fs.h"
8 : #include "xfs_shared.h"
9 : #include "xfs_format.h"
10 : #include "xfs_trans_resv.h"
11 : #include "xfs_mount.h"
12 : #include "xfs_inode.h"
13 : #include "xfs_btree.h"
14 : #include "xfs_log_format.h"
15 : #include "xfs_ag.h"
16 : #include "scrub/scrub.h"
17 : #include "scrub/common.h"
18 : #include "scrub/btree.h"
19 : #include "scrub/trace.h"
20 :
21 : /* btree scrubbing */
22 :
23 : /* Figure out which block the btree cursor was pointing to. */
24 : static inline xfs_fsblock_t
25 0 : xchk_btree_cur_fsbno(
26 : struct xfs_btree_cur *cur,
27 : int level)
28 : {
29 0 : if (level < cur->bc_nlevels && cur->bc_levels[level].bp)
30 0 : return XFS_DADDR_TO_FSB(cur->bc_mp,
31 : xfs_buf_daddr(cur->bc_levels[level].bp));
32 0 : else if (level == cur->bc_nlevels - 1 &&
33 0 : (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
34 0 : return XFS_INO_TO_FSB(cur->bc_mp, cur->bc_ino.ip->i_ino);
35 0 : else if (!(cur->bc_flags & XFS_BTREE_LONG_PTRS))
36 0 : return XFS_AGB_TO_FSB(cur->bc_mp, cur->bc_ag.pag->pag_agno, 0);
37 : return NULLFSBLOCK;
38 : }
39 :
40 : static inline void
41 0 : process_error_whine(
42 : struct xfs_scrub *sc,
43 : struct xfs_btree_cur *cur,
44 : int level,
45 : int *error,
46 : __u32 errflag,
47 : void *ret_ip)
48 : {
49 0 : xfs_fsblock_t fsbno = xchk_btree_cur_fsbno(cur, level);
50 :
51 0 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
52 0 : xchk_whine(sc->mp, "ino 0x%llx fork %d type %s btnum %d level %d ptr %d agno 0x%x agbno 0x%x error %d errflag 0x%x ret_ip %pS",
53 0 : cur->bc_ino.ip->i_ino,
54 0 : cur->bc_ino.whichfork,
55 0 : xchk_type_string(sc->sm->sm_type),
56 0 : cur->bc_btnum,
57 : level,
58 0 : cur->bc_levels[level].ptr,
59 0 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
60 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
61 : *error,
62 : errflag,
63 : ret_ip);
64 0 : return;
65 : }
66 :
67 0 : xchk_whine(sc->mp, "type %s btnum %d level %d ptr %d agno 0x%x agbno 0x%x error %d errflag 0x%x ret_ip %pS",
68 0 : xchk_type_string(sc->sm->sm_type),
69 0 : cur->bc_btnum,
70 : level,
71 0 : cur->bc_levels[level].ptr,
72 0 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
73 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
74 : *error,
75 : errflag,
76 : ret_ip);
77 : }
78 :
79 : /*
80 : * Check for btree operation errors. See the section about handling
81 : * operational errors in common.c.
82 : */
83 : static bool
84 178883963 : __xchk_btree_process_error(
85 : struct xfs_scrub *sc,
86 : struct xfs_btree_cur *cur,
87 : int level,
88 : int *error,
89 : __u32 errflag,
90 : void *ret_ip)
91 : {
92 178883963 : if (*error == 0)
93 : return true;
94 :
95 0 : switch (*error) {
96 0 : case -EDEADLOCK:
97 : case -ECHRNG:
98 : /* Used to restart an op with deadlock avoidance. */
99 0 : trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
100 0 : break;
101 0 : case -EFSBADCRC:
102 : case -EFSCORRUPTED:
103 : /* Note the badness but don't abort. */
104 0 : sc->sm->sm_flags |= errflag;
105 0 : process_error_whine(sc, cur, level, error, errflag, ret_ip);
106 0 : *error = 0;
107 0 : fallthrough;
108 0 : default:
109 0 : if (*error)
110 0 : process_error_whine(sc, cur, level, error, errflag,
111 : ret_ip);
112 0 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
113 0 : trace_xchk_ifork_btree_op_error(sc, cur, level,
114 : *error, ret_ip);
115 : else
116 0 : trace_xchk_btree_op_error(sc, cur, level,
117 : *error, ret_ip);
118 : break;
119 : }
120 : return false;
121 : }
122 :
123 : bool
124 229390 : xchk_btree_process_error(
125 : struct xfs_scrub *sc,
126 : struct xfs_btree_cur *cur,
127 : int level,
128 : int *error)
129 : {
130 79898222 : return __xchk_btree_process_error(sc, cur, level, error,
131 : XFS_SCRUB_OFLAG_CORRUPT, __return_address);
132 : }
133 :
134 : bool
135 90541563 : xchk_btree_xref_process_error(
136 : struct xfs_scrub *sc,
137 : struct xfs_btree_cur *cur,
138 : int level,
139 : int *error)
140 : {
141 98986687 : return __xchk_btree_process_error(sc, cur, level, error,
142 : XFS_SCRUB_OFLAG_XFAIL, __return_address);
143 : }
144 :
145 : /* Record btree block corruption. */
146 : static void
147 0 : __xchk_btree_set_corrupt(
148 : struct xfs_scrub *sc,
149 : struct xfs_btree_cur *cur,
150 : int level,
151 : __u32 errflag,
152 : void *ret_ip)
153 : {
154 0 : sc->sm->sm_flags |= errflag;
155 :
156 0 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
157 : {
158 0 : xfs_fsblock_t fsbno = xchk_btree_cur_fsbno(cur, level);
159 0 : xchk_whine(sc->mp, "ino 0x%llx fork %d type %s btnum %d level %d ptr %d agno 0x%x agbno 0x%x errflag 0x%x ret_ip %pS",
160 0 : cur->bc_ino.ip->i_ino,
161 0 : cur->bc_ino.whichfork,
162 0 : xchk_type_string(sc->sm->sm_type),
163 0 : cur->bc_btnum,
164 : level,
165 0 : cur->bc_levels[level].ptr,
166 0 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
167 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
168 : errflag,
169 : ret_ip);
170 0 : trace_xchk_ifork_btree_error(sc, cur, level,
171 : ret_ip);
172 : }
173 : else
174 : {
175 0 : xfs_fsblock_t fsbno = xchk_btree_cur_fsbno(cur, level);
176 0 : xchk_whine(sc->mp, "type %s btnum %d level %d ptr %d agno 0x%x agbno 0x%x errflag 0x%x ret_ip %pS",
177 0 : xchk_type_string(sc->sm->sm_type),
178 0 : cur->bc_btnum,
179 : level,
180 0 : cur->bc_levels[level].ptr,
181 0 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
182 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
183 : errflag,
184 : ret_ip);
185 0 : trace_xchk_btree_error(sc, cur, level,
186 : ret_ip);
187 : }
188 0 : }
189 :
190 : void
191 0 : xchk_btree_set_corrupt(
192 : struct xfs_scrub *sc,
193 : struct xfs_btree_cur *cur,
194 : int level)
195 : {
196 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
197 : __return_address);
198 0 : }
199 :
200 : void
201 0 : xchk_btree_xref_set_corrupt(
202 : struct xfs_scrub *sc,
203 : struct xfs_btree_cur *cur,
204 : int level)
205 : {
206 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
207 : __return_address);
208 0 : }
209 :
210 : void
211 0 : xchk_btree_set_preen(
212 : struct xfs_scrub *sc,
213 : struct xfs_btree_cur *cur,
214 : int level)
215 : {
216 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_PREEN,
217 : __return_address);
218 0 : }
219 :
220 : /*
221 : * Make sure this record is in order and doesn't stray outside of the parent
222 : * keys.
223 : */
224 : STATIC void
225 2513491765 : xchk_btree_rec(
226 : struct xchk_btree *bs)
227 : {
228 2513491765 : struct xfs_btree_cur *cur = bs->cur;
229 2513491765 : union xfs_btree_rec *rec;
230 2513491765 : union xfs_btree_key key;
231 2513491765 : union xfs_btree_key hkey;
232 2513491765 : union xfs_btree_key *keyp;
233 2513491765 : struct xfs_btree_block *block;
234 2513491765 : struct xfs_btree_block *keyblock;
235 2513491765 : struct xfs_buf *bp;
236 :
237 2513491765 : block = xfs_btree_get_block(cur, 0, &bp);
238 2513560856 : rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);
239 :
240 2513593553 : trace_xchk_btree_rec(bs->sc, cur, 0);
241 :
242 : /* Are all records across all record blocks in order? */
243 5024636654 : if (bs->lastrec_valid &&
244 2511119052 : !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
245 0 : xchk_btree_set_corrupt(bs->sc, cur, 0);
246 5027035204 : memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
247 2513517602 : bs->lastrec_valid = true;
248 :
249 2513517602 : if (cur->bc_nlevels == 1)
250 1004961758 : return;
251 :
252 : /* Is low_key(rec) at least as large as the parent low key? */
253 2492281683 : cur->bc_ops->init_key_from_rec(&key, rec);
254 2492338897 : keyblock = xfs_btree_get_block(cur, 1, &bp);
255 2492369317 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
256 2492400389 : if (xfs_btree_keycmp_lt(cur, &key, keyp))
257 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
258 :
259 2492402202 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
260 : return;
261 :
262 : /* Is high_key(rec) no larger than the parent high key? */
263 1508676363 : cur->bc_ops->init_high_key_from_rec(&hkey, rec);
264 1508680720 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
265 1508685621 : if (xfs_btree_keycmp_lt(cur, keyp, &hkey))
266 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
267 : }
268 :
269 : /*
270 : * Make sure this key is in order and doesn't stray outside of the parent
271 : * keys.
272 : */
273 : STATIC void
274 16109056 : xchk_btree_key(
275 : struct xchk_btree *bs,
276 : int level)
277 : {
278 16109056 : struct xfs_btree_cur *cur = bs->cur;
279 16109056 : union xfs_btree_key *key;
280 16109056 : union xfs_btree_key *keyp;
281 16109056 : struct xfs_btree_block *block;
282 16109056 : struct xfs_btree_block *keyblock;
283 16109056 : struct xfs_buf *bp;
284 :
285 16109056 : block = xfs_btree_get_block(cur, level, &bp);
286 16109063 : key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
287 :
288 16109044 : trace_xchk_btree_key(bs->sc, cur, level);
289 :
290 : /* Are all low keys across all node blocks in order? */
291 30380608 : if (bs->lastkey[level - 1].valid &&
292 14271554 : !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key))
293 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
294 32218108 : memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len);
295 16109054 : bs->lastkey[level - 1].valid = true;
296 :
297 16109054 : if (level + 1 >= cur->bc_nlevels)
298 6544282 : return;
299 :
300 : /* Is this block's low key at least as large as the parent low key? */
301 11673619 : keyblock = xfs_btree_get_block(cur, level + 1, &bp);
302 11673619 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);
303 11673622 : if (xfs_btree_keycmp_lt(cur, key, keyp))
304 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
305 :
306 11673622 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
307 : return;
308 :
309 : /* Is this block's high key no larger than the parent high key? */
310 9564775 : key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);
311 9564776 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
312 : keyblock);
313 9564776 : if (xfs_btree_keycmp_lt(cur, keyp, key))
314 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
315 : }
316 :
317 : /*
318 : * Check a btree pointer. Returns true if it's ok to use this pointer.
319 : * Callers do not need to set the corrupt flag.
320 : */
321 : static bool
322 47450449 : xchk_btree_ptr_ok(
323 : struct xchk_btree *bs,
324 : int level,
325 : union xfs_btree_ptr *ptr)
326 : {
327 47450449 : bool res;
328 :
329 : /* A btree rooted in an inode has no block pointer to the root. */
330 47450449 : if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
331 23715058 : level == bs->cur->bc_nlevels)
332 : return true;
333 :
334 : /* Otherwise, check the pointers. */
335 45904743 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
336 22169355 : res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
337 : else
338 47470776 : res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
339 45904733 : if (!res)
340 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
341 :
342 : return res;
343 : }
344 :
345 : /* Check that a btree block's sibling matches what we expect it. */
346 : STATIC int
347 32218109 : xchk_btree_block_check_sibling(
348 : struct xchk_btree *bs,
349 : int level,
350 : int direction,
351 : union xfs_btree_ptr *sibling)
352 : {
353 32218109 : struct xfs_btree_cur *cur = bs->cur;
354 32218109 : struct xfs_btree_block *pblock;
355 32218109 : struct xfs_buf *pbp;
356 32218109 : struct xfs_btree_cur *ncur = NULL;
357 32218109 : union xfs_btree_ptr *pp;
358 32218109 : int success;
359 32218109 : int error;
360 :
361 32218109 : error = xfs_btree_dup_cursor(cur, &ncur);
362 64436269 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
363 32218138 : !ncur)
364 0 : return error;
365 :
366 : /*
367 : * If the pointer is null, we shouldn't be able to move the upper
368 : * level pointer anywhere.
369 : */
370 32218138 : if (xfs_btree_ptr_is_null(cur, sibling)) {
371 3675036 : if (direction > 0)
372 1837515 : error = xfs_btree_increment(ncur, level + 1, &success);
373 : else
374 1837521 : error = xfs_btree_decrement(ncur, level + 1, &success);
375 3675030 : if (error == 0 && success)
376 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
377 3675030 : error = 0;
378 3675030 : goto out;
379 : }
380 :
381 : /* Increment upper level pointer. */
382 28543114 : if (direction > 0)
383 14271555 : error = xfs_btree_increment(ncur, level + 1, &success);
384 : else
385 14271559 : error = xfs_btree_decrement(ncur, level + 1, &success);
386 57086212 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
387 0 : goto out;
388 28543102 : if (!success) {
389 0 : xchk_btree_set_corrupt(bs->sc, cur, level + 1);
390 0 : goto out;
391 : }
392 :
393 : /* Compare upper level pointer to sibling pointer. */
394 28543102 : pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
395 28543104 : pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);
396 28543110 : if (!xchk_btree_ptr_ok(bs, level + 1, pp))
397 0 : goto out;
398 28543104 : if (pbp)
399 28011240 : xchk_buffer_recheck(bs->sc, pbp);
400 :
401 28543104 : if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
402 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
403 28543102 : out:
404 32218132 : xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
405 32218143 : return error;
406 : }
407 :
408 : /* Check the siblings of a btree block. */
409 : STATIC int
410 18907583 : xchk_btree_block_check_siblings(
411 : struct xchk_btree *bs,
412 : struct xfs_btree_block *block)
413 : {
414 18907583 : struct xfs_btree_cur *cur = bs->cur;
415 18907583 : union xfs_btree_ptr leftsib;
416 18907583 : union xfs_btree_ptr rightsib;
417 18907583 : int level;
418 18907583 : int error = 0;
419 :
420 18907583 : xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
421 18907582 : xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
422 18907581 : level = xfs_btree_get_level(block);
423 :
424 : /* Root block should never have siblings. */
425 18907581 : if (level == cur->bc_nlevels - 1) {
426 5597016 : if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
427 2798499 : !xfs_btree_ptr_is_null(cur, &rightsib))
428 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
429 2798500 : goto out;
430 : }
431 :
432 : /*
433 : * Does the left & right sibling pointers match the adjacent
434 : * parent level pointers?
435 : * (These function absorbs error codes for us.)
436 : */
437 16109065 : error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
438 16109075 : if (error)
439 : return error;
440 16109075 : error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
441 16109082 : if (error)
442 0 : return error;
443 16109082 : out:
444 : return error;
445 : }
446 :
447 : struct check_owner {
448 : struct list_head list;
449 : xfs_daddr_t daddr;
450 : int level;
451 : };
452 :
453 : /*
454 : * Make sure this btree block isn't in the free list and that there's
455 : * an rmap record for it.
456 : */
457 : STATIC int
458 17361847 : xchk_btree_check_block_owner(
459 : struct xchk_btree *bs,
460 : int level,
461 : xfs_daddr_t daddr)
462 : {
463 17361847 : xfs_agnumber_t agno;
464 17361847 : xfs_agblock_t agbno;
465 17361847 : xfs_btnum_t btnum;
466 17361847 : bool init_sa;
467 17361847 : int error = 0;
468 :
469 17361847 : if (!bs->cur)
470 : return 0;
471 :
472 17361847 : btnum = bs->cur->bc_btnum;
473 17361847 : agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
474 17361847 : agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
475 :
476 17361847 : init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
477 17361847 : if (init_sa) {
478 8445137 : error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
479 16890253 : if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
480 : level, &error))
481 0 : goto out_free;
482 : }
483 :
484 17361840 : xchk_xref_is_used_space(bs->sc, agbno, 1);
485 : /*
486 : * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
487 : * have to nullify it (to shut down further block owner checks) if
488 : * self-xref encounters problems.
489 : */
490 17361877 : if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
491 0 : bs->cur = NULL;
492 :
493 17361877 : xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo);
494 17361891 : if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
495 0 : bs->cur = NULL;
496 :
497 17361891 : out_free:
498 17361891 : if (init_sa)
499 8445135 : xchk_ag_free(bs->sc, &bs->sc->sa);
500 :
501 17361894 : return error;
502 : }
503 :
504 : /* Check the owner of a btree block. */
505 : STATIC int
506 18907529 : xchk_btree_check_owner(
507 : struct xchk_btree *bs,
508 : int level,
509 : struct xfs_buf *bp)
510 : {
511 18907529 : struct xfs_btree_cur *cur = bs->cur;
512 :
513 : /*
514 : * In theory, xfs_btree_get_block should only give us a null buffer
515 : * pointer for the root of a root-in-inode btree type, but we need
516 : * to check defensively here in case the cursor state is also screwed
517 : * up.
518 : */
519 18907529 : if (bp == NULL) {
520 1545699 : if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
521 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
522 1545699 : return 0;
523 : }
524 :
525 : /*
526 : * We want to cross-reference each btree block with the bnobt
527 : * and the rmapbt. We cannot cross-reference the bnobt or
528 : * rmapbt while scanning the bnobt or rmapbt, respectively,
529 : * because we cannot alter the cursor and we'd prefer not to
530 : * duplicate cursors. Therefore, save the buffer daddr for
531 : * later scanning.
532 : */
533 17361830 : if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
534 7357934 : struct check_owner *co;
535 :
536 7357934 : co = kmalloc(sizeof(struct check_owner), XCHK_GFP_FLAGS);
537 7357940 : if (!co)
538 : return -ENOMEM;
539 :
540 7357940 : INIT_LIST_HEAD(&co->list);
541 7357940 : co->level = level;
542 7357940 : co->daddr = xfs_buf_daddr(bp);
543 7357940 : list_add_tail(&co->list, &bs->to_check);
544 7357940 : return 0;
545 : }
546 :
547 10003896 : return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp));
548 : }
549 :
550 : /* Decide if we want to check minrecs of a btree block in the inode root. */
551 : static inline bool
552 1350720 : xchk_btree_check_iroot_minrecs(
553 : struct xchk_btree *bs)
554 : {
555 : /*
556 : * xfs_bmap_add_attrfork_btree had an implementation bug wherein it
557 : * would miscalculate the space required for the data fork bmbt root
558 : * when adding an attr fork, and promote the iroot contents to an
559 : * external block unnecessarily. This went unnoticed for many years
560 : * until scrub found filesystems in this state. Inode rooted btrees are
561 : * not supposed to have immediate child blocks that are small enough
562 : * that the contents could fit in the inode root, but we can't fail
563 : * existing filesystems, so instead we disable the check for data fork
564 : * bmap btrees when there's an attr fork.
565 : */
566 1350720 : if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
567 1319687 : bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
568 1319663 : xfs_inode_has_attr_fork(bs->sc->ip))
569 1319606 : return false;
570 :
571 : return true;
572 : }
573 :
574 : /*
575 : * Check that this btree block has at least minrecs records or is one of the
576 : * special blocks that don't require that.
577 : */
578 : STATIC void
579 18907570 : xchk_btree_check_minrecs(
580 : struct xchk_btree *bs,
581 : int level,
582 : struct xfs_btree_block *block)
583 : {
584 18907570 : struct xfs_btree_cur *cur = bs->cur;
585 18907570 : unsigned int root_level = cur->bc_nlevels - 1;
586 18907570 : unsigned int numrecs = be16_to_cpu(block->bb_numrecs);
587 :
588 : /* More records than minrecs means the block is ok. */
589 18907570 : if (numrecs >= cur->bc_ops->get_minrecs(cur, level))
590 : return;
591 :
592 : /*
593 : * For btrees rooted in the inode, it's possible that the root block
594 : * contents spilled into a regular ondisk block because there wasn't
595 : * enough space in the inode root. The number of records in that
596 : * child block might be less than the standard minrecs, but that's ok
597 : * provided that there's only one direct child of the root.
598 : */
599 2545668 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
600 1350721 : level == cur->bc_nlevels - 2) {
601 1350722 : struct xfs_btree_block *root_block;
602 1350722 : struct xfs_buf *root_bp;
603 1350722 : int root_maxrecs;
604 :
605 1350722 : root_block = xfs_btree_get_block(cur, root_level, &root_bp);
606 1350719 : root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
607 1350719 : if (xchk_btree_check_iroot_minrecs(bs) &&
608 31116 : (be16_to_cpu(root_block->bb_numrecs) != 1 ||
609 31116 : numrecs <= root_maxrecs))
610 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
611 1350719 : return;
612 : }
613 :
614 : /*
615 : * Otherwise, only the root level is allowed to have fewer than minrecs
616 : * records or keyptrs.
617 : */
618 1194946 : if (level < root_level)
619 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
620 : }
621 :
622 : /*
623 : * If this btree block has a parent, make sure that the parent's keys capture
624 : * the keyspace contained in this block.
625 : */
626 : STATIC void
627 18907570 : xchk_btree_block_check_keys(
628 : struct xchk_btree *bs,
629 : int level,
630 : struct xfs_btree_block *block)
631 : {
632 18907570 : union xfs_btree_key block_key;
633 18907570 : union xfs_btree_key *block_high_key;
634 18907570 : union xfs_btree_key *parent_low_key, *parent_high_key;
635 18907570 : struct xfs_btree_cur *cur = bs->cur;
636 18907570 : struct xfs_btree_block *parent_block;
637 18907570 : struct xfs_buf *bp;
638 :
639 18907570 : if (level == cur->bc_nlevels - 1)
640 7891463 : return;
641 :
642 16109080 : xfs_btree_get_keys(cur, block, &block_key);
643 :
644 : /* Make sure the low key of this block matches the parent. */
645 16109054 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
646 16109058 : parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
647 : parent_block);
648 16109071 : if (xfs_btree_keycmp_ne(cur, &block_key, parent_low_key)) {
649 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
650 0 : return;
651 : }
652 :
653 16109067 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
654 : return;
655 :
656 : /* Make sure the high key of this block matches the parent. */
657 11016094 : parent_high_key = xfs_btree_high_key_addr(cur,
658 11016094 : cur->bc_levels[level + 1].ptr, parent_block);
659 11016099 : block_high_key = xfs_btree_high_key_from_key(cur, &block_key);
660 11016098 : if (xfs_btree_keycmp_ne(cur, block_high_key, parent_high_key))
661 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
662 : }
663 :
664 : /*
665 : * Grab and scrub a btree block given a btree pointer. Returns block
666 : * and buffer pointers (if applicable) if they're ok to use.
667 : */
668 : STATIC int
669 18907564 : xchk_btree_get_block(
670 : struct xchk_btree *bs,
671 : int level,
672 : union xfs_btree_ptr *pp,
673 : struct xfs_btree_block **pblock,
674 : struct xfs_buf **pbp)
675 : {
676 18907564 : xfs_failaddr_t failed_at;
677 18907564 : int error;
678 :
679 18907564 : *pblock = NULL;
680 18907564 : *pbp = NULL;
681 :
682 18907564 : error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
683 37815179 : if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
684 18907574 : !*pblock)
685 0 : return error;
686 :
687 18907574 : xfs_btree_get_block(bs->cur, level, pbp);
688 18907567 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
689 9990833 : failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
690 : level, *pbp);
691 : else
692 8916734 : failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
693 : level, *pbp);
694 18907572 : if (failed_at) {
695 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
696 0 : return 0;
697 : }
698 18907572 : if (*pbp)
699 17361859 : xchk_buffer_recheck(bs->sc, *pbp);
700 :
701 18907542 : xchk_btree_check_minrecs(bs, level, *pblock);
702 :
703 : /*
704 : * Check the block's owner; this function absorbs error codes
705 : * for us.
706 : */
707 18907519 : error = xchk_btree_check_owner(bs, level, *pbp);
708 18907594 : if (error)
709 : return error;
710 :
711 : /*
712 : * Check the block's siblings; this function absorbs error codes
713 : * for us.
714 : */
715 18907597 : error = xchk_btree_block_check_siblings(bs, *pblock);
716 18907556 : if (error)
717 : return error;
718 :
719 18907557 : xchk_btree_block_check_keys(bs, level, *pblock);
720 18907557 : return 0;
721 : }
722 :
723 : /*
724 : * Check that the low and high keys of this block match the keys stored
725 : * in the parent block.
726 : */
727 : STATIC void
728 18907573 : xchk_btree_block_keys(
729 : struct xchk_btree *bs,
730 : int level,
731 : struct xfs_btree_block *block)
732 : {
733 18907573 : union xfs_btree_key block_keys;
734 18907573 : struct xfs_btree_cur *cur = bs->cur;
735 18907573 : union xfs_btree_key *high_bk;
736 18907573 : union xfs_btree_key *parent_keys;
737 18907573 : union xfs_btree_key *high_pk;
738 18907573 : struct xfs_btree_block *parent_block;
739 18907573 : struct xfs_buf *bp;
740 :
741 18907573 : if (level >= cur->bc_nlevels - 1)
742 7891478 : return;
743 :
744 : /* Calculate the keys for this block. */
745 16109075 : xfs_btree_get_keys(cur, block, &block_keys);
746 :
747 : /* Obtain the parent's copy of the keys for this block. */
748 16109071 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
749 16109071 : parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
750 : parent_block);
751 :
752 16109076 : if (xfs_btree_keycmp_ne(cur, &block_keys, parent_keys))
753 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
754 :
755 16109073 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
756 : return;
757 :
758 : /* Get high keys */
759 11016093 : high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
760 11016094 : high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
761 : parent_block);
762 :
763 11016100 : if (xfs_btree_keycmp_ne(cur, high_bk, high_pk))
764 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
765 : }
766 :
767 : /*
768 : * Visit all nodes and leaves of a btree. Check that all pointers and
769 : * records are in order, that the keys reflect the records, and use a callback
770 : * so that the caller can verify individual records.
771 : */
772 : int
773 2798457 : xchk_btree(
774 : struct xfs_scrub *sc,
775 : struct xfs_btree_cur *cur,
776 : xchk_btree_rec_fn scrub_fn,
777 : const struct xfs_owner_info *oinfo,
778 : void *private)
779 : {
780 2798457 : union xfs_btree_ptr ptr;
781 2798457 : struct xchk_btree *bs;
782 2798457 : union xfs_btree_ptr *pp;
783 2798457 : union xfs_btree_rec *recp;
784 2798457 : struct xfs_btree_block *block;
785 2798457 : struct xfs_buf *bp;
786 2798457 : struct check_owner *co;
787 2798457 : struct check_owner *n;
788 2798457 : size_t cur_sz;
789 2798457 : int level;
790 2798457 : int error = 0;
791 :
792 : /*
793 : * Allocate the btree scrub context from the heap, because this
794 : * structure can get rather large. Don't let a caller feed us a
795 : * totally absurd size.
796 : */
797 2798457 : cur_sz = xchk_btree_sizeof(cur->bc_nlevels);
798 2798457 : if (cur_sz > PAGE_SIZE) {
799 0 : xchk_btree_set_corrupt(sc, cur, 0);
800 0 : return 0;
801 : }
802 2798457 : bs = kzalloc(cur_sz, XCHK_GFP_FLAGS);
803 2798517 : if (!bs)
804 : return -ENOMEM;
805 2798517 : bs->cur = cur;
806 2798517 : bs->scrub_rec = scrub_fn;
807 2798517 : bs->oinfo = oinfo;
808 2798517 : bs->private = private;
809 2798517 : bs->sc = sc;
810 :
811 : /* Initialize scrub state */
812 2798517 : INIT_LIST_HEAD(&bs->to_check);
813 :
814 : /*
815 : * Load the root of the btree. The helper function absorbs
816 : * error codes for us.
817 : */
818 2798517 : level = cur->bc_nlevels - 1;
819 2798517 : cur->bc_ops->init_ptr_from_cur(cur, &ptr);
820 2798464 : if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))
821 0 : goto out;
822 2798466 : error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);
823 2798481 : if (error || !block)
824 0 : goto out;
825 :
826 2798481 : cur->bc_levels[level].ptr = 1;
827 :
828 2551403184 : while (level < cur->bc_nlevels) {
829 2548604664 : block = xfs_btree_get_block(cur, level, &bp);
830 :
831 2548519825 : if (level == 0) {
832 : /* End of leaf, pop back towards the root. */
833 2530468018 : if (cur->bc_levels[level].ptr >
834 2530468018 : be16_to_cpu(block->bb_numrecs)) {
835 16964834 : xchk_btree_block_keys(bs, level, block);
836 16964818 : if (level < cur->bc_nlevels - 1)
837 15901473 : cur->bc_levels[level + 1].ptr++;
838 16964818 : level++;
839 16964818 : continue;
840 : }
841 :
842 : /* Records in order for scrub? */
843 2513503184 : xchk_btree_rec(bs);
844 :
845 : /* Call out to the record checker. */
846 2513539011 : recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
847 : block);
848 2513590336 : error = bs->scrub_rec(bs, recp);
849 2513478024 : if (error)
850 : break;
851 2513478023 : if (xchk_should_terminate(sc, &error) ||
852 2513588053 : (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
853 : break;
854 :
855 2513588053 : cur->bc_levels[level].ptr++;
856 2513588053 : continue;
857 : }
858 :
859 : /* End of node, pop back towards the root. */
860 18051807 : if (cur->bc_levels[level].ptr >
861 18051807 : be16_to_cpu(block->bb_numrecs)) {
862 1942755 : xchk_btree_block_keys(bs, level, block);
863 1942761 : if (level < cur->bc_nlevels - 1)
864 207598 : cur->bc_levels[level + 1].ptr++;
865 1942761 : level++;
866 1942761 : continue;
867 : }
868 :
869 : /* Keys in order for scrub? */
870 16109052 : xchk_btree_key(bs, level);
871 :
872 : /* Drill another level deeper. */
873 16109066 : pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
874 16109051 : if (!xchk_btree_ptr_ok(bs, level, pp)) {
875 0 : cur->bc_levels[level].ptr++;
876 0 : continue;
877 : }
878 16109057 : level--;
879 16109057 : error = xchk_btree_get_block(bs, level, pp, &block, &bp);
880 16109071 : if (error || !block)
881 0 : goto out;
882 :
883 16109071 : cur->bc_levels[level].ptr = 1;
884 : }
885 :
886 2798521 : out:
887 : /* Process deferred owner checks on btree blocks. */
888 10156465 : list_for_each_entry_safe(co, n, &bs->to_check, list) {
889 7357945 : if (!error && bs->cur)
890 7357948 : error = xchk_btree_check_block_owner(bs, co->level,
891 : co->daddr);
892 7357943 : list_del(&co->list);
893 7357945 : kfree(co);
894 : }
895 2798520 : kfree(bs);
896 :
897 2798516 : return error;
898 : }
|
