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_trans_resv.h"
11 #include "xfs_mount.h"
12 #include "xfs_inode.h"
13 #include "xfs_btree.h"
14 #include "scrub/scrub.h"
15 #include "scrub/common.h"
16 #include "scrub/btree.h"
17 #include "scrub/trace.h"
18
19 /* btree scrubbing */
20
21 /*
22 * Check for btree operation errors. See the section about handling
23 * operational errors in common.c.
24 */
25 static bool
__xchk_btree_process_error(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,int * error,__u32 errflag,void * ret_ip)26 __xchk_btree_process_error(
27 struct xfs_scrub *sc,
28 struct xfs_btree_cur *cur,
29 int level,
30 int *error,
31 __u32 errflag,
32 void *ret_ip)
33 {
34 if (*error == 0)
35 return true;
36
37 switch (*error) {
38 case -EDEADLOCK:
39 /* Used to restart an op with deadlock avoidance. */
40 trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
41 break;
42 case -EFSBADCRC:
43 case -EFSCORRUPTED:
44 /* Note the badness but don't abort. */
45 sc->sm->sm_flags |= errflag;
46 *error = 0;
47 fallthrough;
48 default:
49 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
50 trace_xchk_ifork_btree_op_error(sc, cur, level,
51 *error, ret_ip);
52 else
53 trace_xchk_btree_op_error(sc, cur, level,
54 *error, ret_ip);
55 break;
56 }
57 return false;
58 }
59
60 bool
xchk_btree_process_error(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,int * error)61 xchk_btree_process_error(
62 struct xfs_scrub *sc,
63 struct xfs_btree_cur *cur,
64 int level,
65 int *error)
66 {
67 return __xchk_btree_process_error(sc, cur, level, error,
68 XFS_SCRUB_OFLAG_CORRUPT, __return_address);
69 }
70
71 bool
xchk_btree_xref_process_error(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,int * error)72 xchk_btree_xref_process_error(
73 struct xfs_scrub *sc,
74 struct xfs_btree_cur *cur,
75 int level,
76 int *error)
77 {
78 return __xchk_btree_process_error(sc, cur, level, error,
79 XFS_SCRUB_OFLAG_XFAIL, __return_address);
80 }
81
82 /* Record btree block corruption. */
83 static void
__xchk_btree_set_corrupt(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level,__u32 errflag,void * ret_ip)84 __xchk_btree_set_corrupt(
85 struct xfs_scrub *sc,
86 struct xfs_btree_cur *cur,
87 int level,
88 __u32 errflag,
89 void *ret_ip)
90 {
91 sc->sm->sm_flags |= errflag;
92
93 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
94 trace_xchk_ifork_btree_error(sc, cur, level,
95 ret_ip);
96 else
97 trace_xchk_btree_error(sc, cur, level,
98 ret_ip);
99 }
100
101 void
xchk_btree_set_corrupt(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level)102 xchk_btree_set_corrupt(
103 struct xfs_scrub *sc,
104 struct xfs_btree_cur *cur,
105 int level)
106 {
107 __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
108 __return_address);
109 }
110
111 void
xchk_btree_xref_set_corrupt(struct xfs_scrub * sc,struct xfs_btree_cur * cur,int level)112 xchk_btree_xref_set_corrupt(
113 struct xfs_scrub *sc,
114 struct xfs_btree_cur *cur,
115 int level)
116 {
117 __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
118 __return_address);
119 }
120
121 /*
122 * Make sure this record is in order and doesn't stray outside of the parent
123 * keys.
124 */
125 STATIC void
xchk_btree_rec(struct xchk_btree * bs)126 xchk_btree_rec(
127 struct xchk_btree *bs)
128 {
129 struct xfs_btree_cur *cur = bs->cur;
130 union xfs_btree_rec *rec;
131 union xfs_btree_key key;
132 union xfs_btree_key hkey;
133 union xfs_btree_key *keyp;
134 struct xfs_btree_block *block;
135 struct xfs_btree_block *keyblock;
136 struct xfs_buf *bp;
137
138 block = xfs_btree_get_block(cur, 0, &bp);
139 rec = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
140
141 trace_xchk_btree_rec(bs->sc, cur, 0);
142
143 /* If this isn't the first record, are they in order? */
144 if (!bs->firstrec && !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
145 xchk_btree_set_corrupt(bs->sc, cur, 0);
146 bs->firstrec = false;
147 memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
148
149 if (cur->bc_nlevels == 1)
150 return;
151
152 /* Is this at least as large as the parent low key? */
153 cur->bc_ops->init_key_from_rec(&key, rec);
154 keyblock = xfs_btree_get_block(cur, 1, &bp);
155 keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[1], keyblock);
156 if (cur->bc_ops->diff_two_keys(cur, &key, keyp) < 0)
157 xchk_btree_set_corrupt(bs->sc, cur, 1);
158
159 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
160 return;
161
162 /* Is this no larger than the parent high key? */
163 cur->bc_ops->init_high_key_from_rec(&hkey, rec);
164 keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[1], keyblock);
165 if (cur->bc_ops->diff_two_keys(cur, keyp, &hkey) < 0)
166 xchk_btree_set_corrupt(bs->sc, cur, 1);
167 }
168
169 /*
170 * Make sure this key is in order and doesn't stray outside of the parent
171 * keys.
172 */
173 STATIC void
xchk_btree_key(struct xchk_btree * bs,int level)174 xchk_btree_key(
175 struct xchk_btree *bs,
176 int level)
177 {
178 struct xfs_btree_cur *cur = bs->cur;
179 union xfs_btree_key *key;
180 union xfs_btree_key *keyp;
181 struct xfs_btree_block *block;
182 struct xfs_btree_block *keyblock;
183 struct xfs_buf *bp;
184
185 block = xfs_btree_get_block(cur, level, &bp);
186 key = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block);
187
188 trace_xchk_btree_key(bs->sc, cur, level);
189
190 /* If this isn't the first key, are they in order? */
191 if (!bs->firstkey[level] &&
192 !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level], key))
193 xchk_btree_set_corrupt(bs->sc, cur, level);
194 bs->firstkey[level] = false;
195 memcpy(&bs->lastkey[level], key, cur->bc_ops->key_len);
196
197 if (level + 1 >= cur->bc_nlevels)
198 return;
199
200 /* Is this at least as large as the parent low key? */
201 keyblock = xfs_btree_get_block(cur, level + 1, &bp);
202 keyp = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
203 if (cur->bc_ops->diff_two_keys(cur, key, keyp) < 0)
204 xchk_btree_set_corrupt(bs->sc, cur, level);
205
206 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
207 return;
208
209 /* Is this no larger than the parent high key? */
210 key = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block);
211 keyp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1], keyblock);
212 if (cur->bc_ops->diff_two_keys(cur, keyp, key) < 0)
213 xchk_btree_set_corrupt(bs->sc, cur, level);
214 }
215
216 /*
217 * Check a btree pointer. Returns true if it's ok to use this pointer.
218 * Callers do not need to set the corrupt flag.
219 */
220 static bool
xchk_btree_ptr_ok(struct xchk_btree * bs,int level,union xfs_btree_ptr * ptr)221 xchk_btree_ptr_ok(
222 struct xchk_btree *bs,
223 int level,
224 union xfs_btree_ptr *ptr)
225 {
226 bool res;
227
228 /* A btree rooted in an inode has no block pointer to the root. */
229 if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
230 level == bs->cur->bc_nlevels)
231 return true;
232
233 /* Otherwise, check the pointers. */
234 if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
235 res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
236 else
237 res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
238 if (!res)
239 xchk_btree_set_corrupt(bs->sc, bs->cur, level);
240
241 return res;
242 }
243
244 /* Check that a btree block's sibling matches what we expect it. */
245 STATIC int
xchk_btree_block_check_sibling(struct xchk_btree * bs,int level,int direction,union xfs_btree_ptr * sibling)246 xchk_btree_block_check_sibling(
247 struct xchk_btree *bs,
248 int level,
249 int direction,
250 union xfs_btree_ptr *sibling)
251 {
252 struct xfs_btree_cur *cur = bs->cur;
253 struct xfs_btree_block *pblock;
254 struct xfs_buf *pbp;
255 struct xfs_btree_cur *ncur = NULL;
256 union xfs_btree_ptr *pp;
257 int success;
258 int error;
259
260 error = xfs_btree_dup_cursor(cur, &ncur);
261 if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
262 !ncur)
263 return error;
264
265 /*
266 * If the pointer is null, we shouldn't be able to move the upper
267 * level pointer anywhere.
268 */
269 if (xfs_btree_ptr_is_null(cur, sibling)) {
270 if (direction > 0)
271 error = xfs_btree_increment(ncur, level + 1, &success);
272 else
273 error = xfs_btree_decrement(ncur, level + 1, &success);
274 if (error == 0 && success)
275 xchk_btree_set_corrupt(bs->sc, cur, level);
276 error = 0;
277 goto out;
278 }
279
280 /* Increment upper level pointer. */
281 if (direction > 0)
282 error = xfs_btree_increment(ncur, level + 1, &success);
283 else
284 error = xfs_btree_decrement(ncur, level + 1, &success);
285 if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
286 goto out;
287 if (!success) {
288 xchk_btree_set_corrupt(bs->sc, cur, level + 1);
289 goto out;
290 }
291
292 /* Compare upper level pointer to sibling pointer. */
293 pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
294 pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock);
295 if (!xchk_btree_ptr_ok(bs, level + 1, pp))
296 goto out;
297 if (pbp)
298 xchk_buffer_recheck(bs->sc, pbp);
299
300 if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
301 xchk_btree_set_corrupt(bs->sc, cur, level);
302 out:
303 xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
304 return error;
305 }
306
307 /* Check the siblings of a btree block. */
308 STATIC int
xchk_btree_block_check_siblings(struct xchk_btree * bs,struct xfs_btree_block * block)309 xchk_btree_block_check_siblings(
310 struct xchk_btree *bs,
311 struct xfs_btree_block *block)
312 {
313 struct xfs_btree_cur *cur = bs->cur;
314 union xfs_btree_ptr leftsib;
315 union xfs_btree_ptr rightsib;
316 int level;
317 int error = 0;
318
319 xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
320 xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
321 level = xfs_btree_get_level(block);
322
323 /* Root block should never have siblings. */
324 if (level == cur->bc_nlevels - 1) {
325 if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
326 !xfs_btree_ptr_is_null(cur, &rightsib))
327 xchk_btree_set_corrupt(bs->sc, cur, level);
328 goto out;
329 }
330
331 /*
332 * Does the left & right sibling pointers match the adjacent
333 * parent level pointers?
334 * (These function absorbs error codes for us.)
335 */
336 error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
337 if (error)
338 return error;
339 error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
340 if (error)
341 return error;
342 out:
343 return error;
344 }
345
346 struct check_owner {
347 struct list_head list;
348 xfs_daddr_t daddr;
349 int level;
350 };
351
352 /*
353 * Make sure this btree block isn't in the free list and that there's
354 * an rmap record for it.
355 */
356 STATIC int
xchk_btree_check_block_owner(struct xchk_btree * bs,int level,xfs_daddr_t daddr)357 xchk_btree_check_block_owner(
358 struct xchk_btree *bs,
359 int level,
360 xfs_daddr_t daddr)
361 {
362 xfs_agnumber_t agno;
363 xfs_agblock_t agbno;
364 xfs_btnum_t btnum;
365 bool init_sa;
366 int error = 0;
367
368 if (!bs->cur)
369 return 0;
370
371 btnum = bs->cur->bc_btnum;
372 agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
373 agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
374
375 init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
376 if (init_sa) {
377 error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
378 if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
379 level, &error))
380 goto out_free;
381 }
382
383 xchk_xref_is_used_space(bs->sc, agbno, 1);
384 /*
385 * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
386 * have to nullify it (to shut down further block owner checks) if
387 * self-xref encounters problems.
388 */
389 if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
390 bs->cur = NULL;
391
392 xchk_xref_is_owned_by(bs->sc, agbno, 1, bs->oinfo);
393 if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
394 bs->cur = NULL;
395
396 out_free:
397 if (init_sa)
398 xchk_ag_free(bs->sc, &bs->sc->sa);
399
400 return error;
401 }
402
403 /* Check the owner of a btree block. */
404 STATIC int
xchk_btree_check_owner(struct xchk_btree * bs,int level,struct xfs_buf * bp)405 xchk_btree_check_owner(
406 struct xchk_btree *bs,
407 int level,
408 struct xfs_buf *bp)
409 {
410 struct xfs_btree_cur *cur = bs->cur;
411 struct check_owner *co;
412
413 /*
414 * In theory, xfs_btree_get_block should only give us a null buffer
415 * pointer for the root of a root-in-inode btree type, but we need
416 * to check defensively here in case the cursor state is also screwed
417 * up.
418 */
419 if (bp == NULL) {
420 if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
421 xchk_btree_set_corrupt(bs->sc, bs->cur, level);
422 return 0;
423 }
424
425 /*
426 * We want to cross-reference each btree block with the bnobt
427 * and the rmapbt. We cannot cross-reference the bnobt or
428 * rmapbt while scanning the bnobt or rmapbt, respectively,
429 * because we cannot alter the cursor and we'd prefer not to
430 * duplicate cursors. Therefore, save the buffer daddr for
431 * later scanning.
432 */
433 if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
434 co = kmem_alloc(sizeof(struct check_owner),
435 KM_MAYFAIL);
436 if (!co)
437 return -ENOMEM;
438 co->level = level;
439 co->daddr = xfs_buf_daddr(bp);
440 list_add_tail(&co->list, &bs->to_check);
441 return 0;
442 }
443
444 return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp));
445 }
446
447 /* Decide if we want to check minrecs of a btree block in the inode root. */
448 static inline bool
xchk_btree_check_iroot_minrecs(struct xchk_btree * bs)449 xchk_btree_check_iroot_minrecs(
450 struct xchk_btree *bs)
451 {
452 /*
453 * xfs_bmap_add_attrfork_btree had an implementation bug wherein it
454 * would miscalculate the space required for the data fork bmbt root
455 * when adding an attr fork, and promote the iroot contents to an
456 * external block unnecessarily. This went unnoticed for many years
457 * until scrub found filesystems in this state. Inode rooted btrees are
458 * not supposed to have immediate child blocks that are small enough
459 * that the contents could fit in the inode root, but we can't fail
460 * existing filesystems, so instead we disable the check for data fork
461 * bmap btrees when there's an attr fork.
462 */
463 if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
464 bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
465 XFS_IFORK_Q(bs->sc->ip))
466 return false;
467
468 return true;
469 }
470
471 /*
472 * Check that this btree block has at least minrecs records or is one of the
473 * special blocks that don't require that.
474 */
475 STATIC void
xchk_btree_check_minrecs(struct xchk_btree * bs,int level,struct xfs_btree_block * block)476 xchk_btree_check_minrecs(
477 struct xchk_btree *bs,
478 int level,
479 struct xfs_btree_block *block)
480 {
481 struct xfs_btree_cur *cur = bs->cur;
482 unsigned int root_level = cur->bc_nlevels - 1;
483 unsigned int numrecs = be16_to_cpu(block->bb_numrecs);
484
485 /* More records than minrecs means the block is ok. */
486 if (numrecs >= cur->bc_ops->get_minrecs(cur, level))
487 return;
488
489 /*
490 * For btrees rooted in the inode, it's possible that the root block
491 * contents spilled into a regular ondisk block because there wasn't
492 * enough space in the inode root. The number of records in that
493 * child block might be less than the standard minrecs, but that's ok
494 * provided that there's only one direct child of the root.
495 */
496 if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
497 level == cur->bc_nlevels - 2) {
498 struct xfs_btree_block *root_block;
499 struct xfs_buf *root_bp;
500 int root_maxrecs;
501
502 root_block = xfs_btree_get_block(cur, root_level, &root_bp);
503 root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
504 if (xchk_btree_check_iroot_minrecs(bs) &&
505 (be16_to_cpu(root_block->bb_numrecs) != 1 ||
506 numrecs <= root_maxrecs))
507 xchk_btree_set_corrupt(bs->sc, cur, level);
508 return;
509 }
510
511 /*
512 * Otherwise, only the root level is allowed to have fewer than minrecs
513 * records or keyptrs.
514 */
515 if (level < root_level)
516 xchk_btree_set_corrupt(bs->sc, cur, level);
517 }
518
519 /*
520 * Grab and scrub a btree block given a btree pointer. Returns block
521 * and buffer pointers (if applicable) if they're ok to use.
522 */
523 STATIC int
xchk_btree_get_block(struct xchk_btree * bs,int level,union xfs_btree_ptr * pp,struct xfs_btree_block ** pblock,struct xfs_buf ** pbp)524 xchk_btree_get_block(
525 struct xchk_btree *bs,
526 int level,
527 union xfs_btree_ptr *pp,
528 struct xfs_btree_block **pblock,
529 struct xfs_buf **pbp)
530 {
531 xfs_failaddr_t failed_at;
532 int error;
533
534 *pblock = NULL;
535 *pbp = NULL;
536
537 error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
538 if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
539 !*pblock)
540 return error;
541
542 xfs_btree_get_block(bs->cur, level, pbp);
543 if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
544 failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
545 level, *pbp);
546 else
547 failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
548 level, *pbp);
549 if (failed_at) {
550 xchk_btree_set_corrupt(bs->sc, bs->cur, level);
551 return 0;
552 }
553 if (*pbp)
554 xchk_buffer_recheck(bs->sc, *pbp);
555
556 xchk_btree_check_minrecs(bs, level, *pblock);
557
558 /*
559 * Check the block's owner; this function absorbs error codes
560 * for us.
561 */
562 error = xchk_btree_check_owner(bs, level, *pbp);
563 if (error)
564 return error;
565
566 /*
567 * Check the block's siblings; this function absorbs error codes
568 * for us.
569 */
570 return xchk_btree_block_check_siblings(bs, *pblock);
571 }
572
573 /*
574 * Check that the low and high keys of this block match the keys stored
575 * in the parent block.
576 */
577 STATIC void
xchk_btree_block_keys(struct xchk_btree * bs,int level,struct xfs_btree_block * block)578 xchk_btree_block_keys(
579 struct xchk_btree *bs,
580 int level,
581 struct xfs_btree_block *block)
582 {
583 union xfs_btree_key block_keys;
584 struct xfs_btree_cur *cur = bs->cur;
585 union xfs_btree_key *high_bk;
586 union xfs_btree_key *parent_keys;
587 union xfs_btree_key *high_pk;
588 struct xfs_btree_block *parent_block;
589 struct xfs_buf *bp;
590
591 if (level >= cur->bc_nlevels - 1)
592 return;
593
594 /* Calculate the keys for this block. */
595 xfs_btree_get_keys(cur, block, &block_keys);
596
597 /* Obtain the parent's copy of the keys for this block. */
598 parent_block = xfs_btree_get_block(cur, level + 1, &bp);
599 parent_keys = xfs_btree_key_addr(cur, cur->bc_ptrs[level + 1],
600 parent_block);
601
602 if (cur->bc_ops->diff_two_keys(cur, &block_keys, parent_keys) != 0)
603 xchk_btree_set_corrupt(bs->sc, cur, 1);
604
605 if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
606 return;
607
608 /* Get high keys */
609 high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
610 high_pk = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level + 1],
611 parent_block);
612
613 if (cur->bc_ops->diff_two_keys(cur, high_bk, high_pk) != 0)
614 xchk_btree_set_corrupt(bs->sc, cur, 1);
615 }
616
617 /*
618 * Visit all nodes and leaves of a btree. Check that all pointers and
619 * records are in order, that the keys reflect the records, and use a callback
620 * so that the caller can verify individual records.
621 */
622 int
xchk_btree(struct xfs_scrub * sc,struct xfs_btree_cur * cur,xchk_btree_rec_fn scrub_fn,const struct xfs_owner_info * oinfo,void * private)623 xchk_btree(
624 struct xfs_scrub *sc,
625 struct xfs_btree_cur *cur,
626 xchk_btree_rec_fn scrub_fn,
627 const struct xfs_owner_info *oinfo,
628 void *private)
629 {
630 struct xchk_btree bs = {
631 .cur = cur,
632 .scrub_rec = scrub_fn,
633 .oinfo = oinfo,
634 .firstrec = true,
635 .private = private,
636 .sc = sc,
637 };
638 union xfs_btree_ptr ptr;
639 union xfs_btree_ptr *pp;
640 union xfs_btree_rec *recp;
641 struct xfs_btree_block *block;
642 int level;
643 struct xfs_buf *bp;
644 struct check_owner *co;
645 struct check_owner *n;
646 int i;
647 int error = 0;
648
649 /* Initialize scrub state */
650 for (i = 0; i < XFS_BTREE_MAXLEVELS; i++)
651 bs.firstkey[i] = true;
652 INIT_LIST_HEAD(&bs.to_check);
653
654 /* Don't try to check a tree with a height we can't handle. */
655 if (cur->bc_nlevels > XFS_BTREE_MAXLEVELS) {
656 xchk_btree_set_corrupt(sc, cur, 0);
657 goto out;
658 }
659
660 /*
661 * Load the root of the btree. The helper function absorbs
662 * error codes for us.
663 */
664 level = cur->bc_nlevels - 1;
665 cur->bc_ops->init_ptr_from_cur(cur, &ptr);
666 if (!xchk_btree_ptr_ok(&bs, cur->bc_nlevels, &ptr))
667 goto out;
668 error = xchk_btree_get_block(&bs, level, &ptr, &block, &bp);
669 if (error || !block)
670 goto out;
671
672 cur->bc_ptrs[level] = 1;
673
674 while (level < cur->bc_nlevels) {
675 block = xfs_btree_get_block(cur, level, &bp);
676
677 if (level == 0) {
678 /* End of leaf, pop back towards the root. */
679 if (cur->bc_ptrs[level] >
680 be16_to_cpu(block->bb_numrecs)) {
681 xchk_btree_block_keys(&bs, level, block);
682 if (level < cur->bc_nlevels - 1)
683 cur->bc_ptrs[level + 1]++;
684 level++;
685 continue;
686 }
687
688 /* Records in order for scrub? */
689 xchk_btree_rec(&bs);
690
691 /* Call out to the record checker. */
692 recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
693 error = bs.scrub_rec(&bs, recp);
694 if (error)
695 break;
696 if (xchk_should_terminate(sc, &error) ||
697 (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
698 break;
699
700 cur->bc_ptrs[level]++;
701 continue;
702 }
703
704 /* End of node, pop back towards the root. */
705 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
706 xchk_btree_block_keys(&bs, level, block);
707 if (level < cur->bc_nlevels - 1)
708 cur->bc_ptrs[level + 1]++;
709 level++;
710 continue;
711 }
712
713 /* Keys in order for scrub? */
714 xchk_btree_key(&bs, level);
715
716 /* Drill another level deeper. */
717 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
718 if (!xchk_btree_ptr_ok(&bs, level, pp)) {
719 cur->bc_ptrs[level]++;
720 continue;
721 }
722 level--;
723 error = xchk_btree_get_block(&bs, level, pp, &block, &bp);
724 if (error || !block)
725 goto out;
726
727 cur->bc_ptrs[level] = 1;
728 }
729
730 out:
731 /* Process deferred owner checks on btree blocks. */
732 list_for_each_entry_safe(co, n, &bs.to_check, list) {
733 if (!error && bs.cur)
734 error = xchk_btree_check_block_owner(&bs,
735 co->level, co->daddr);
736 list_del(&co->list);
737 kmem_free(co);
738 }
739
740 return error;
741 }
742