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 "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
26 126114144 : __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 126114144 : if (*error == 0)
35 : return true;
36 :
37 4 : switch (*error) {
38 0 : case -EDEADLOCK:
39 : case -ECHRNG:
40 : /* Used to restart an op with deadlock avoidance. */
41 0 : trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
42 0 : break;
43 0 : case -EFSBADCRC:
44 : case -EFSCORRUPTED:
45 : /* Note the badness but don't abort. */
46 0 : sc->sm->sm_flags |= errflag;
47 0 : *error = 0;
48 4 : fallthrough;
49 4 : default:
50 4 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
51 4 : trace_xchk_ifork_btree_op_error(sc, cur, level,
52 : *error, ret_ip);
53 : else
54 0 : trace_xchk_btree_op_error(sc, cur, level,
55 : *error, ret_ip);
56 : break;
57 : }
58 : return false;
59 : }
60 :
61 : bool
62 552576 : xchk_btree_process_error(
63 : struct xfs_scrub *sc,
64 : struct xfs_btree_cur *cur,
65 : int level,
66 : int *error)
67 : {
68 51382855 : return __xchk_btree_process_error(sc, cur, level, error,
69 : XFS_SCRUB_OFLAG_CORRUPT, __return_address);
70 : }
71 :
72 : bool
73 69949453 : xchk_btree_xref_process_error(
74 : struct xfs_scrub *sc,
75 : struct xfs_btree_cur *cur,
76 : int level,
77 : int *error)
78 : {
79 74732666 : return __xchk_btree_process_error(sc, cur, level, error,
80 : XFS_SCRUB_OFLAG_XFAIL, __return_address);
81 : }
82 :
83 : /* Record btree block corruption. */
84 : static void
85 0 : __xchk_btree_set_corrupt(
86 : struct xfs_scrub *sc,
87 : struct xfs_btree_cur *cur,
88 : int level,
89 : __u32 errflag,
90 : void *ret_ip)
91 : {
92 0 : sc->sm->sm_flags |= errflag;
93 :
94 0 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
95 0 : trace_xchk_ifork_btree_error(sc, cur, level,
96 : ret_ip);
97 : else
98 0 : trace_xchk_btree_error(sc, cur, level,
99 : ret_ip);
100 0 : }
101 :
102 : void
103 0 : xchk_btree_set_corrupt(
104 : struct xfs_scrub *sc,
105 : struct xfs_btree_cur *cur,
106 : int level)
107 : {
108 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
109 : __return_address);
110 0 : }
111 :
112 : void
113 0 : xchk_btree_xref_set_corrupt(
114 : struct xfs_scrub *sc,
115 : struct xfs_btree_cur *cur,
116 : int level)
117 : {
118 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
119 : __return_address);
120 0 : }
121 :
122 : void
123 0 : xchk_btree_set_preen(
124 : struct xfs_scrub *sc,
125 : struct xfs_btree_cur *cur,
126 : int level)
127 : {
128 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_PREEN,
129 : __return_address);
130 0 : }
131 :
132 : /*
133 : * Make sure this record is in order and doesn't stray outside of the parent
134 : * keys.
135 : */
136 : STATIC void
137 1295561532 : xchk_btree_rec(
138 : struct xchk_btree *bs)
139 : {
140 1295561532 : struct xfs_btree_cur *cur = bs->cur;
141 1295561532 : union xfs_btree_rec *rec;
142 1295561532 : union xfs_btree_key key;
143 1295561532 : union xfs_btree_key hkey;
144 1295561532 : union xfs_btree_key *keyp;
145 1295561532 : struct xfs_btree_block *block;
146 1295561532 : struct xfs_btree_block *keyblock;
147 1295561532 : struct xfs_buf *bp;
148 :
149 1295561532 : block = xfs_btree_get_block(cur, 0, &bp);
150 1294913840 : rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);
151 :
152 1294796742 : trace_xchk_btree_rec(bs->sc, cur, 0);
153 :
154 : /* Are all records across all record blocks in order? */
155 2582761686 : if (bs->lastrec_valid &&
156 1287709613 : !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
157 0 : xchk_btree_set_corrupt(bs->sc, cur, 0);
158 2590104146 : memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
159 1295052073 : bs->lastrec_valid = true;
160 :
161 1295052073 : if (cur->bc_nlevels == 1)
162 725967875 : return;
163 :
164 : /* Is low_key(rec) at least as large as the parent low key? */
165 1261182481 : cur->bc_ops->init_key_from_rec(&key, rec);
166 1261133031 : keyblock = xfs_btree_get_block(cur, 1, &bp);
167 1260920324 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
168 1260462811 : if (xfs_btree_keycmp_lt(cur, &key, keyp))
169 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
170 :
171 1260494245 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
172 : return;
173 :
174 : /* Is high_key(rec) no larger than the parent high key? */
175 568395962 : cur->bc_ops->init_high_key_from_rec(&hkey, rec);
176 568687660 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
177 568972872 : if (xfs_btree_keycmp_lt(cur, keyp, &hkey))
178 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
179 : }
180 :
181 : /*
182 : * Make sure this key is in order and doesn't stray outside of the parent
183 : * keys.
184 : */
185 : STATIC void
186 10137022 : xchk_btree_key(
187 : struct xchk_btree *bs,
188 : int level)
189 : {
190 10137022 : struct xfs_btree_cur *cur = bs->cur;
191 10137022 : union xfs_btree_key *key;
192 10137022 : union xfs_btree_key *keyp;
193 10137022 : struct xfs_btree_block *block;
194 10137022 : struct xfs_btree_block *keyblock;
195 10137022 : struct xfs_buf *bp;
196 :
197 10137022 : block = xfs_btree_get_block(cur, level, &bp);
198 10136833 : key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
199 :
200 10136715 : trace_xchk_btree_key(bs->sc, cur, level);
201 :
202 : /* Are all low keys across all node blocks in order? */
203 16072396 : if (bs->lastkey[level - 1].valid &&
204 5935295 : !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key))
205 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
206 20274202 : memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len);
207 10137101 : bs->lastkey[level - 1].valid = true;
208 :
209 10137101 : if (level + 1 >= cur->bc_nlevels)
210 6704926 : return;
211 :
212 : /* Is this block's low key at least as large as the parent low key? */
213 4210075 : keyblock = xfs_btree_get_block(cur, level + 1, &bp);
214 4210072 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);
215 4210077 : if (xfs_btree_keycmp_lt(cur, key, keyp))
216 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
217 :
218 4210078 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
219 : return;
220 :
221 : /* Is this block's high key no larger than the parent high key? */
222 3432178 : key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);
223 3432169 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
224 : keyblock);
225 3432173 : if (xfs_btree_keycmp_lt(cur, keyp, key))
226 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
227 : }
228 :
229 : /*
230 : * Check a btree pointer. Returns true if it's ok to use this pointer.
231 : * Callers do not need to set the corrupt flag.
232 : */
233 : static bool
234 30549088 : xchk_btree_ptr_ok(
235 : struct xchk_btree *bs,
236 : int level,
237 : union xfs_btree_ptr *ptr)
238 : {
239 30549088 : bool res;
240 :
241 : /* A btree rooted in an inode has no block pointer to the root. */
242 30549088 : if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
243 10348334 : level == bs->cur->bc_nlevels)
244 : return true;
245 :
246 : /* Otherwise, check the pointers. */
247 26564332 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
248 6363678 : res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
249 : else
250 20200654 : res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
251 26562426 : if (!res)
252 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
253 :
254 : return res;
255 : }
256 :
257 : /* Check that a btree block's sibling matches what we expect it. */
258 : STATIC int
259 20274867 : xchk_btree_block_check_sibling(
260 : struct xchk_btree *bs,
261 : int level,
262 : int direction,
263 : union xfs_btree_ptr *sibling)
264 : {
265 20274867 : struct xfs_btree_cur *cur = bs->cur;
266 20274867 : struct xfs_btree_block *pblock;
267 20274867 : struct xfs_buf *pbp;
268 20274867 : struct xfs_btree_cur *ncur = NULL;
269 20274867 : union xfs_btree_ptr *pp;
270 20274867 : int success;
271 20274867 : int error;
272 :
273 20274867 : error = xfs_btree_dup_cursor(cur, &ncur);
274 40548710 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
275 20274524 : !ncur)
276 0 : return error;
277 :
278 : /*
279 : * If the pointer is null, we shouldn't be able to move the upper
280 : * level pointer anywhere.
281 : */
282 20274524 : if (xfs_btree_ptr_is_null(cur, sibling)) {
283 8403915 : if (direction > 0)
284 4202660 : error = xfs_btree_increment(ncur, level + 1, &success);
285 : else
286 4201255 : error = xfs_btree_decrement(ncur, level + 1, &success);
287 8403834 : if (error == 0 && success)
288 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
289 8403834 : error = 0;
290 8403834 : goto out;
291 : }
292 :
293 : /* Increment upper level pointer. */
294 11870274 : if (direction > 0)
295 5935187 : error = xfs_btree_increment(ncur, level + 1, &success);
296 : else
297 5935087 : error = xfs_btree_decrement(ncur, level + 1, &success);
298 23740689 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
299 0 : goto out;
300 11870345 : if (!success) {
301 0 : xchk_btree_set_corrupt(bs->sc, cur, level + 1);
302 0 : goto out;
303 : }
304 :
305 : /* Compare upper level pointer to sibling pointer. */
306 11870345 : pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
307 11870253 : pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);
308 11870254 : if (!xchk_btree_ptr_ok(bs, level + 1, pp))
309 0 : goto out;
310 11870210 : if (pbp)
311 11605188 : xchk_buffer_recheck(bs->sc, pbp);
312 :
313 11870351 : if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
314 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
315 11870212 : out:
316 20274046 : xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
317 20274788 : return error;
318 : }
319 :
320 : /* Check the siblings of a btree block. */
321 : STATIC int
322 18682024 : xchk_btree_block_check_siblings(
323 : struct xchk_btree *bs,
324 : struct xfs_btree_block *block)
325 : {
326 18682024 : struct xfs_btree_cur *cur = bs->cur;
327 18682024 : union xfs_btree_ptr leftsib;
328 18682024 : union xfs_btree_ptr rightsib;
329 18682024 : int level;
330 18682024 : int error = 0;
331 :
332 18682024 : xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
333 18673325 : xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
334 18674274 : level = xfs_btree_get_level(block);
335 :
336 : /* Root block should never have siblings. */
337 18674274 : if (level == cur->bc_nlevels - 1) {
338 17075722 : if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
339 8536364 : !xfs_btree_ptr_is_null(cur, &rightsib))
340 32 : xchk_btree_set_corrupt(bs->sc, cur, level);
341 8539535 : goto out;
342 : }
343 :
344 : /*
345 : * Does the left & right sibling pointers match the adjacent
346 : * parent level pointers?
347 : * (These function absorbs error codes for us.)
348 : */
349 10138087 : error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
350 10137167 : if (error)
351 : return error;
352 10137042 : error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
353 10137875 : if (error)
354 0 : return error;
355 10137875 : out:
356 : return error;
357 : }
358 :
359 : struct check_owner {
360 : struct list_head list;
361 : xfs_daddr_t daddr;
362 : int level;
363 : };
364 :
365 : /*
366 : * Make sure this btree block isn't in the free list and that there's
367 : * an rmap record for it.
368 : */
369 : STATIC int
370 14697397 : xchk_btree_check_block_owner(
371 : struct xchk_btree *bs,
372 : int level,
373 : xfs_daddr_t daddr)
374 : {
375 14697397 : xfs_agnumber_t agno;
376 14697397 : xfs_agblock_t agbno;
377 14697397 : xfs_btnum_t btnum;
378 14697397 : bool init_sa;
379 14697397 : int error = 0;
380 :
381 14697397 : if (!bs->cur)
382 : return 0;
383 :
384 14697397 : btnum = bs->cur->bc_btnum;
385 14697397 : agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
386 14694003 : agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
387 :
388 14693472 : init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
389 14693472 : if (init_sa) {
390 4781111 : error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
391 9566227 : if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
392 : level, &error))
393 4 : goto out_free;
394 : }
395 :
396 14695364 : xchk_xref_is_used_space(bs->sc, agbno, 1);
397 : /*
398 : * The bnobt scrubber aliases bs->cur to bs->sc->sa.bno_cur, so we
399 : * have to nullify it (to shut down further block owner checks) if
400 : * self-xref encounters problems.
401 : */
402 14698239 : if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
403 0 : bs->cur = NULL;
404 :
405 14698239 : xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo);
406 14696003 : if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
407 0 : bs->cur = NULL;
408 :
409 14696003 : out_free:
410 14696007 : if (init_sa)
411 4781787 : xchk_ag_free(bs->sc, &bs->sc->sa);
412 :
413 14697644 : return error;
414 : }
415 :
416 : /* Check the owner of a btree block. */
417 : STATIC int
418 18679792 : xchk_btree_check_owner(
419 : struct xchk_btree *bs,
420 : int level,
421 : struct xfs_buf *bp)
422 : {
423 18679792 : struct xfs_btree_cur *cur = bs->cur;
424 :
425 : /*
426 : * In theory, xfs_btree_get_block should only give us a null buffer
427 : * pointer for the root of a root-in-inode btree type, but we need
428 : * to check defensively here in case the cursor state is also screwed
429 : * up.
430 : */
431 18679792 : if (bp == NULL) {
432 3984007 : if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
433 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
434 3984007 : return 0;
435 : }
436 :
437 : /*
438 : * We want to cross-reference each btree block with the bnobt
439 : * and the rmapbt. We cannot cross-reference the bnobt or
440 : * rmapbt while scanning the bnobt or rmapbt, respectively,
441 : * because we cannot alter the cursor and we'd prefer not to
442 : * duplicate cursors. Therefore, save the buffer daddr for
443 : * later scanning.
444 : */
445 14695785 : if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
446 6023701 : struct check_owner *co;
447 :
448 6023701 : co = kmalloc(sizeof(struct check_owner), XCHK_GFP_FLAGS);
449 6026407 : if (!co)
450 : return -ENOMEM;
451 :
452 6026407 : INIT_LIST_HEAD(&co->list);
453 6026407 : co->level = level;
454 6026407 : co->daddr = xfs_buf_daddr(bp);
455 6026407 : list_add_tail(&co->list, &bs->to_check);
456 6026407 : return 0;
457 : }
458 :
459 8672084 : return xchk_btree_check_block_owner(bs, level, xfs_buf_daddr(bp));
460 : }
461 :
462 : /* Decide if we want to check minrecs of a btree block in the inode root. */
463 : static inline bool
464 3918209 : xchk_btree_check_iroot_minrecs(
465 : struct xchk_btree *bs)
466 : {
467 : /*
468 : * xfs_bmap_add_attrfork_btree had an implementation bug wherein it
469 : * would miscalculate the space required for the data fork bmbt root
470 : * when adding an attr fork, and promote the iroot contents to an
471 : * external block unnecessarily. This went unnoticed for many years
472 : * until scrub found filesystems in this state. Inode rooted btrees are
473 : * not supposed to have immediate child blocks that are small enough
474 : * that the contents could fit in the inode root, but we can't fail
475 : * existing filesystems, so instead we disable the check for data fork
476 : * bmap btrees when there's an attr fork.
477 : */
478 3918209 : if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
479 3918491 : bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
480 3918381 : xfs_inode_has_attr_fork(bs->sc->ip))
481 2603210 : return false;
482 :
483 : return true;
484 : }
485 :
486 : /*
487 : * Check that this btree block has at least minrecs records or is one of the
488 : * special blocks that don't require that.
489 : */
490 : STATIC void
491 18672164 : xchk_btree_check_minrecs(
492 : struct xchk_btree *bs,
493 : int level,
494 : struct xfs_btree_block *block)
495 : {
496 18672164 : struct xfs_btree_cur *cur = bs->cur;
497 18672164 : unsigned int root_level = cur->bc_nlevels - 1;
498 18672164 : unsigned int numrecs = be16_to_cpu(block->bb_numrecs);
499 :
500 : /* More records than minrecs means the block is ok. */
501 18672164 : if (numrecs >= cur->bc_ops->get_minrecs(cur, level))
502 : return;
503 :
504 : /*
505 : * For btrees rooted in the inode, it's possible that the root block
506 : * contents spilled into a regular ondisk block because there wasn't
507 : * enough space in the inode root. The number of records in that
508 : * child block might be less than the standard minrecs, but that's ok
509 : * provided that there's only one direct child of the root.
510 : */
511 8411036 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
512 3917636 : level == cur->bc_nlevels - 2) {
513 3917772 : struct xfs_btree_block *root_block;
514 3917772 : struct xfs_buf *root_bp;
515 3917772 : int root_maxrecs;
516 :
517 3917772 : root_block = xfs_btree_get_block(cur, root_level, &root_bp);
518 3918632 : root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
519 3918702 : if (xchk_btree_check_iroot_minrecs(bs) &&
520 1315927 : (be16_to_cpu(root_block->bb_numrecs) != 1 ||
521 1315927 : numrecs <= root_maxrecs))
522 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
523 3918702 : return;
524 : }
525 :
526 : /*
527 : * Otherwise, only the root level is allowed to have fewer than minrecs
528 : * records or keyptrs.
529 : */
530 4493264 : if (level < root_level)
531 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
532 : }
533 :
534 : /*
535 : * If this btree block has a parent, make sure that the parent's keys capture
536 : * the keyspace contained in this block.
537 : */
538 : STATIC void
539 18673806 : xchk_btree_block_check_keys(
540 : struct xchk_btree *bs,
541 : int level,
542 : struct xfs_btree_block *block)
543 : {
544 18673806 : union xfs_btree_key block_key;
545 18673806 : union xfs_btree_key *block_high_key;
546 18673806 : union xfs_btree_key *parent_low_key, *parent_high_key;
547 18673806 : struct xfs_btree_cur *cur = bs->cur;
548 18673806 : struct xfs_btree_block *parent_block;
549 18673806 : struct xfs_buf *bp;
550 :
551 18673806 : if (level == cur->bc_nlevels - 1)
552 14458950 : return;
553 :
554 10137444 : xfs_btree_get_keys(cur, block, &block_key);
555 :
556 : /* Make sure the low key of this block matches the parent. */
557 10135736 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
558 10136548 : parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
559 : parent_block);
560 10136549 : if (xfs_btree_keycmp_ne(cur, &block_key, parent_low_key)) {
561 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
562 0 : return;
563 : }
564 :
565 10136470 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
566 : return;
567 :
568 : /* Make sure the high key of this block matches the parent. */
569 4213882 : parent_high_key = xfs_btree_high_key_addr(cur,
570 4213882 : cur->bc_levels[level + 1].ptr, parent_block);
571 4213883 : block_high_key = xfs_btree_high_key_from_key(cur, &block_key);
572 4213884 : if (xfs_btree_keycmp_ne(cur, block_high_key, parent_high_key))
573 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
574 : }
575 :
576 : /*
577 : * Grab and scrub a btree block given a btree pointer. Returns block
578 : * and buffer pointers (if applicable) if they're ok to use.
579 : */
580 : STATIC int
581 18679219 : xchk_btree_get_block(
582 : struct xchk_btree *bs,
583 : int level,
584 : union xfs_btree_ptr *pp,
585 : struct xfs_btree_block **pblock,
586 : struct xfs_buf **pbp)
587 : {
588 18679219 : xfs_failaddr_t failed_at;
589 18679219 : int error;
590 :
591 18679219 : *pblock = NULL;
592 18679219 : *pbp = NULL;
593 :
594 18679219 : error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
595 37366897 : if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
596 18681079 : !*pblock)
597 0 : return error;
598 :
599 18681079 : xfs_btree_get_block(bs->cur, level, pbp);
600 18677851 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
601 8767062 : failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
602 : level, *pbp);
603 : else
604 9910789 : failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
605 : level, *pbp);
606 18680699 : if (failed_at) {
607 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
608 0 : return 0;
609 : }
610 18680699 : if (*pbp)
611 14696950 : xchk_buffer_recheck(bs->sc, *pbp);
612 :
613 18669754 : xchk_btree_check_minrecs(bs, level, *pblock);
614 :
615 : /*
616 : * Check the block's owner; this function absorbs error codes
617 : * for us.
618 : */
619 18670934 : error = xchk_btree_check_owner(bs, level, *pbp);
620 18681289 : if (error)
621 : return error;
622 :
623 : /*
624 : * Check the block's siblings; this function absorbs error codes
625 : * for us.
626 : */
627 18680917 : error = xchk_btree_block_check_siblings(bs, *pblock);
628 18678542 : if (error)
629 : return error;
630 :
631 18678580 : xchk_btree_block_check_keys(bs, level, *pblock);
632 18678580 : return 0;
633 : }
634 :
635 : /*
636 : * Check that the low and high keys of this block match the keys stored
637 : * in the parent block.
638 : */
639 : STATIC void
640 18686985 : xchk_btree_block_keys(
641 : struct xchk_btree *bs,
642 : int level,
643 : struct xfs_btree_block *block)
644 : {
645 18686985 : union xfs_btree_key block_keys;
646 18686985 : struct xfs_btree_cur *cur = bs->cur;
647 18686985 : union xfs_btree_key *high_bk;
648 18686985 : union xfs_btree_key *parent_keys;
649 18686985 : union xfs_btree_key *high_pk;
650 18686985 : struct xfs_btree_block *parent_block;
651 18686985 : struct xfs_buf *bp;
652 :
653 18686985 : if (level >= cur->bc_nlevels - 1)
654 14473108 : return;
655 :
656 : /* Calculate the keys for this block. */
657 10138283 : xfs_btree_get_keys(cur, block, &block_keys);
658 :
659 : /* Obtain the parent's copy of the keys for this block. */
660 10138324 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
661 10138315 : parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
662 : parent_block);
663 :
664 10138290 : if (xfs_btree_keycmp_ne(cur, &block_keys, parent_keys))
665 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
666 :
667 10138300 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
668 : return;
669 :
670 : /* Get high keys */
671 4213894 : high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
672 4213891 : high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
673 : parent_block);
674 :
675 4213890 : if (xfs_btree_keycmp_ne(cur, high_bk, high_pk))
676 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
677 : }
678 :
679 : /*
680 : * Visit all nodes and leaves of a btree. Check that all pointers and
681 : * records are in order, that the keys reflect the records, and use a callback
682 : * so that the caller can verify individual records.
683 : */
684 : int
685 8544105 : xchk_btree(
686 : struct xfs_scrub *sc,
687 : struct xfs_btree_cur *cur,
688 : xchk_btree_rec_fn scrub_fn,
689 : const struct xfs_owner_info *oinfo,
690 : void *private)
691 : {
692 8544105 : union xfs_btree_ptr ptr;
693 8544105 : struct xchk_btree *bs;
694 8544105 : union xfs_btree_ptr *pp;
695 8544105 : union xfs_btree_rec *recp;
696 8544105 : struct xfs_btree_block *block;
697 8544105 : struct xfs_buf *bp;
698 8544105 : struct check_owner *co;
699 8544105 : struct check_owner *n;
700 8544105 : size_t cur_sz;
701 8544105 : int level;
702 8544105 : int error = 0;
703 :
704 : /*
705 : * Allocate the btree scrub context from the heap, because this
706 : * structure can get rather large. Don't let a caller feed us a
707 : * totally absurd size.
708 : */
709 8544105 : cur_sz = xchk_btree_sizeof(cur->bc_nlevels);
710 8544105 : if (cur_sz > PAGE_SIZE) {
711 0 : xchk_btree_set_corrupt(sc, cur, 0);
712 0 : return 0;
713 : }
714 8544105 : bs = kzalloc(cur_sz, XCHK_GFP_FLAGS);
715 8542784 : if (!bs)
716 : return -ENOMEM;
717 8542784 : bs->cur = cur;
718 8542784 : bs->scrub_rec = scrub_fn;
719 8542784 : bs->oinfo = oinfo;
720 8542784 : bs->private = private;
721 8542784 : bs->sc = sc;
722 :
723 : /* Initialize scrub state */
724 8542784 : INIT_LIST_HEAD(&bs->to_check);
725 :
726 : /*
727 : * Load the root of the btree. The helper function absorbs
728 : * error codes for us.
729 : */
730 8542784 : level = cur->bc_nlevels - 1;
731 8542784 : cur->bc_ops->init_ptr_from_cur(cur, &ptr);
732 8541128 : if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))
733 0 : goto out;
734 8539869 : error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);
735 8538256 : if (error || !block)
736 0 : goto out;
737 :
738 8538256 : cur->bc_levels[level].ptr = 1;
739 :
740 1332915541 : while (level < cur->bc_nlevels) {
741 1324369527 : block = xfs_btree_get_block(cur, level, &bp);
742 :
743 1324209088 : if (level == 0) {
744 : /* End of leaf, pop back towards the root. */
745 1324274235 : if (cur->bc_levels[level].ptr >
746 1309830644 : be16_to_cpu(block->bb_numrecs)) {
747 14446430 : xchk_btree_block_keys(bs, level, block);
748 14443591 : if (level < cur->bc_nlevels - 1)
749 10080234 : cur->bc_levels[level + 1].ptr++;
750 14443591 : level++;
751 14443591 : continue;
752 : }
753 :
754 : /* Records in order for scrub? */
755 1295384214 : xchk_btree_rec(bs);
756 :
757 : /* Call out to the record checker. */
758 1294917071 : recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
759 : block);
760 1294763787 : error = bs->scrub_rec(bs, recp);
761 1295305181 : if (error)
762 : break;
763 1295305180 : if (xchk_should_terminate(sc, &error) ||
764 1295555635 : (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
765 : break;
766 :
767 1295555635 : cur->bc_levels[level].ptr++;
768 1295555635 : continue;
769 : }
770 :
771 : /* End of node, pop back towards the root. */
772 18619728 : if (cur->bc_levels[level].ptr >
773 14378444 : be16_to_cpu(block->bb_numrecs)) {
774 4241391 : xchk_btree_block_keys(bs, level, block);
775 4241284 : if (level < cur->bc_nlevels - 1)
776 58025 : cur->bc_levels[level + 1].ptr++;
777 4241284 : level++;
778 4241284 : continue;
779 : }
780 :
781 : /* Keys in order for scrub? */
782 10137053 : xchk_btree_key(bs, level);
783 :
784 : /* Drill another level deeper. */
785 10136546 : pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
786 10136411 : if (!xchk_btree_ptr_ok(bs, level, pp)) {
787 0 : cur->bc_levels[level].ptr++;
788 0 : continue;
789 : }
790 10136798 : level--;
791 10136798 : error = xchk_btree_get_block(bs, level, pp, &block, &bp);
792 10136779 : if (error || !block)
793 4 : goto out;
794 :
795 10136775 : cur->bc_levels[level].ptr = 1;
796 : }
797 :
798 8546018 : out:
799 : /* Process deferred owner checks on btree blocks. */
800 14572686 : list_for_each_entry_safe(co, n, &bs->to_check, list) {
801 6025793 : if (!error && bs->cur)
802 6024623 : error = xchk_btree_check_block_owner(bs, co->level,
803 : co->daddr);
804 6026549 : list_del(&co->list);
805 6024044 : kfree(co);
806 : }
807 8546893 : kfree(bs);
808 :
809 8547597 : return error;
810 : }
|
