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 1 : xchk_btree_cur_fsbno(
26 : struct xfs_btree_cur *cur,
27 : int level)
28 : {
29 1 : if (level < cur->bc_nlevels && cur->bc_levels[level].bp)
30 1 : 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 1 : 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 1 : xfs_fsblock_t fsbno = xchk_btree_cur_fsbno(cur, level);
50 :
51 1 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
52 4 : 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 1 : cur->bc_ino.ip->i_ino,
54 1 : cur->bc_ino.whichfork,
55 1 : xchk_type_string(sc->sm->sm_type),
56 1 : cur->bc_btnum,
57 : level,
58 1 : cur->bc_levels[level].ptr,
59 1 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
60 1 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
61 : *error,
62 : errflag,
63 : ret_ip);
64 1 : 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 0 : 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 137647201 : __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 137647201 : if (*error == 0)
93 : return true;
94 :
95 1 : 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 1 : fallthrough;
108 1 : default:
109 1 : if (*error)
110 1 : process_error_whine(sc, cur, level, error, errflag,
111 : ret_ip);
112 1 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
113 1 : 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 216010 : xchk_btree_process_error(
125 : struct xfs_scrub *sc,
126 : struct xfs_btree_cur *cur,
127 : int level,
128 : int *error)
129 : {
130 46817101 : return __xchk_btree_process_error(sc, cur, level, error,
131 : XFS_SCRUB_OFLAG_CORRUPT, __return_address);
132 : }
133 :
134 : bool
135 87610359 : xchk_btree_xref_process_error(
136 : struct xfs_scrub *sc,
137 : struct xfs_btree_cur *cur,
138 : int level,
139 : int *error)
140 : {
141 90832666 : 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 0 : 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 0 : 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 1451242231 : xchk_btree_rec(
226 : struct xchk_btree *bs)
227 : {
228 1451242231 : struct xfs_btree_cur *cur = bs->cur;
229 1451242231 : union xfs_btree_rec *rec;
230 1451242231 : union xfs_btree_key key;
231 1451242231 : union xfs_btree_key hkey;
232 1451242231 : union xfs_btree_key *keyp;
233 1451242231 : struct xfs_btree_block *block;
234 1451242231 : struct xfs_btree_block *keyblock;
235 1451242231 : struct xfs_buf *bp;
236 :
237 1451242231 : block = xfs_btree_get_block(cur, 0, &bp);
238 1451105684 : rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);
239 :
240 1451040194 : trace_xchk_btree_rec(bs->sc, cur, 0);
241 :
242 : /* Are all records across all record blocks in order? */
243 2898430827 : if (bs->lastrec_valid &&
244 1447275011 : !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
245 0 : xchk_btree_set_corrupt(bs->sc, cur, 0);
246 2902311632 : memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
247 1451155816 : bs->lastrec_valid = true;
248 :
249 1451155816 : if (cur->bc_nlevels == 1)
250 811006739 : return;
251 :
252 : /* Is low_key(rec) at least as large as the parent low key? */
253 1420622742 : cur->bc_ops->init_key_from_rec(&key, rec);
254 1420485978 : keyblock = xfs_btree_get_block(cur, 1, &bp);
255 1420536631 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
256 1420324694 : if (xfs_btree_keycmp_lt(cur, &key, keyp))
257 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
258 :
259 1420359354 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
260 : return;
261 :
262 : /* Is high_key(rec) no larger than the parent high key? */
263 639885689 : cur->bc_ops->init_high_key_from_rec(&hkey, rec);
264 639915275 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
265 639974269 : 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 9529393 : xchk_btree_key(
275 : struct xchk_btree *bs,
276 : int level)
277 : {
278 9529393 : struct xfs_btree_cur *cur = bs->cur;
279 9529393 : union xfs_btree_key *key;
280 9529393 : union xfs_btree_key *keyp;
281 9529393 : struct xfs_btree_block *block;
282 9529393 : struct xfs_btree_block *keyblock;
283 9529393 : struct xfs_buf *bp;
284 :
285 9529393 : block = xfs_btree_get_block(cur, level, &bp);
286 9529602 : key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
287 :
288 9529165 : trace_xchk_btree_key(bs->sc, cur, level);
289 :
290 : /* Are all low keys across all node blocks in order? */
291 16458842 : if (bs->lastkey[level - 1].valid &&
292 6929489 : !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key))
293 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
294 19058706 : memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len);
295 9529353 : bs->lastkey[level - 1].valid = true;
296 :
297 9529353 : if (level + 1 >= cur->bc_nlevels)
298 5528336 : return;
299 :
300 : /* Is this block's low key at least as large as the parent low key? */
301 4920171 : keyblock = xfs_btree_get_block(cur, level + 1, &bp);
302 4920173 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);
303 4920169 : if (xfs_btree_keycmp_lt(cur, key, keyp))
304 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
305 :
306 4920171 : 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 4001017 : key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);
311 4001015 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
312 : keyblock);
313 4001018 : 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 27538085 : xchk_btree_ptr_ok(
323 : struct xchk_btree *bs,
324 : int level,
325 : union xfs_btree_ptr *ptr)
326 : {
327 27538085 : bool res;
328 :
329 : /* A btree rooted in an inode has no block pointer to the root. */
330 27538085 : if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
331 7317007 : level == bs->cur->bc_nlevels)
332 : return true;
333 :
334 : /* Otherwise, check the pointers. */
335 25205877 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
336 4984778 : res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
337 : else
338 20221099 : res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
339 25205116 : 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 19060419 : xchk_btree_block_check_sibling(
348 : struct xchk_btree *bs,
349 : int level,
350 : int direction,
351 : union xfs_btree_ptr *sibling)
352 : {
353 19060419 : struct xfs_btree_cur *cur = bs->cur;
354 19060419 : struct xfs_btree_block *pblock;
355 19060419 : struct xfs_buf *pbp;
356 19060419 : struct xfs_btree_cur *ncur = NULL;
357 19060419 : union xfs_btree_ptr *pp;
358 19060419 : int success;
359 19060419 : int error;
360 :
361 19060419 : error = xfs_btree_dup_cursor(cur, &ncur);
362 38121199 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
363 19060663 : !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 19060663 : if (xfs_btree_ptr_is_null(cur, sibling)) {
371 5201420 : if (direction > 0)
372 2601107 : error = xfs_btree_increment(ncur, level + 1, &success);
373 : else
374 2600313 : error = xfs_btree_decrement(ncur, level + 1, &success);
375 5200603 : if (error == 0 && success)
376 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
377 5200603 : error = 0;
378 5200603 : goto out;
379 : }
380 :
381 : /* Increment upper level pointer. */
382 13858959 : if (direction > 0)
383 6929499 : error = xfs_btree_increment(ncur, level + 1, &success);
384 : else
385 6929460 : error = xfs_btree_decrement(ncur, level + 1, &success);
386 27717673 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
387 0 : goto out;
388 13858827 : 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 13858827 : pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
395 13858818 : pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);
396 13858794 : if (!xchk_btree_ptr_ok(bs, level + 1, pp))
397 0 : goto out;
398 13858774 : if (pbp)
399 13613197 : xchk_buffer_recheck(bs->sc, pbp);
400 :
401 13858881 : if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
402 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
403 13858814 : out:
404 19059417 : xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
405 19060394 : return error;
406 : }
407 :
408 : /* Check the siblings of a btree block. */
409 : STATIC int
410 13679323 : xchk_btree_block_check_siblings(
411 : struct xchk_btree *bs,
412 : struct xfs_btree_block *block)
413 : {
414 13679323 : struct xfs_btree_cur *cur = bs->cur;
415 13679323 : union xfs_btree_ptr leftsib;
416 13679323 : union xfs_btree_ptr rightsib;
417 13679323 : int level;
418 13679323 : int error = 0;
419 :
420 13679323 : xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
421 13677066 : xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
422 13677960 : level = xfs_btree_get_level(block);
423 :
424 : /* Root block should never have siblings. */
425 13677960 : if (level == cur->bc_nlevels - 1) {
426 8295743 : if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
427 4147383 : !xfs_btree_ptr_is_null(cur, &rightsib))
428 99 : xchk_btree_set_corrupt(bs->sc, cur, level);
429 4148374 : 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 9530591 : error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
438 9530206 : if (error)
439 : return error;
440 9529983 : error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
441 9530412 : if (error)
442 0 : return error;
443 9530412 : 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 11346170 : xchk_btree_check_block_owner(
459 : struct xchk_btree *bs,
460 : int level,
461 : xfs_daddr_t daddr)
462 : {
463 11346170 : xfs_agnumber_t agno;
464 11346170 : xfs_agblock_t agbno;
465 11346170 : xfs_btnum_t btnum;
466 11346170 : bool init_sa;
467 11346170 : int error = 0;
468 :
469 11346170 : if (!bs->cur)
470 : return 0;
471 :
472 11346170 : btnum = bs->cur->bc_btnum;
473 11346170 : agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
474 11344205 : agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
475 :
476 11343955 : init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
477 11343955 : if (init_sa) {
478 3220518 : error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
479 6444460 : if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
480 : level, &error))
481 1 : goto out_free;
482 : }
483 :
484 11345584 : 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 11348586 : if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
491 0 : bs->cur = NULL;
492 :
493 11348586 : xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo);
494 11348259 : if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
495 0 : bs->cur = NULL;
496 :
497 11348259 : out_free:
498 11348260 : if (init_sa)
499 3221669 : xchk_ag_free(bs->sc, &bs->sc->sa);
500 :
501 11349007 : return error;
502 : }
503 :
504 : /* Check the owner of a btree block. */
505 : STATIC int
506 13676655 : xchk_btree_check_owner(
507 : struct xchk_btree *bs,
508 : int level,
509 : struct xfs_buf *bp)
510 : {
511 13676655 : 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 13676655 : if (bp == NULL) {
520 2331572 : if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
521 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
522 2331572 : 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 11345083 : if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
534 5893654 : struct check_owner *co;
535 :
536 5893654 : co = kmalloc(sizeof(struct check_owner), XCHK_GFP_FLAGS);
537 5894213 : if (!co)
538 : return -ENOMEM;
539 :
540 5894213 : INIT_LIST_HEAD(&co->list);
541 5894213 : co->level = level;
542 5894213 : co->daddr = xfs_buf_daddr(bp);
543 5894213 : list_add_tail(&co->list, &bs->to_check);
544 5894213 : return 0;
545 : }
546 :
547 5451429 : 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 2268288 : 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 2268288 : if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
567 2268244 : bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
568 2268118 : xfs_inode_has_attr_fork(bs->sc->ip))
569 2243838 : 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 13676894 : xchk_btree_check_minrecs(
580 : struct xchk_btree *bs,
581 : int level,
582 : struct xfs_btree_block *block)
583 : {
584 13676894 : struct xfs_btree_cur *cur = bs->cur;
585 13676894 : unsigned int root_level = cur->bc_nlevels - 1;
586 13676894 : unsigned int numrecs = be16_to_cpu(block->bb_numrecs);
587 :
588 : /* More records than minrecs means the block is ok. */
589 13676894 : 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 4018035 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
600 2267807 : level == cur->bc_nlevels - 2) {
601 2268001 : struct xfs_btree_block *root_block;
602 2268001 : struct xfs_buf *root_bp;
603 2268001 : int root_maxrecs;
604 :
605 2268001 : root_block = xfs_btree_get_block(cur, root_level, &root_bp);
606 2268747 : root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
607 2268381 : if (xchk_btree_check_iroot_minrecs(bs) &&
608 24600 : (be16_to_cpu(root_block->bb_numrecs) != 1 ||
609 24600 : numrecs <= root_maxrecs))
610 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
611 2268381 : return;
612 : }
613 :
614 : /*
615 : * Otherwise, only the root level is allowed to have fewer than minrecs
616 : * records or keyptrs.
617 : */
618 1750034 : 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 13678140 : xchk_btree_block_check_keys(
628 : struct xchk_btree *bs,
629 : int level,
630 : struct xfs_btree_block *block)
631 : {
632 13678140 : union xfs_btree_key block_key;
633 13678140 : union xfs_btree_key *block_high_key;
634 13678140 : union xfs_btree_key *parent_low_key, *parent_high_key;
635 13678140 : struct xfs_btree_cur *cur = bs->cur;
636 13678140 : struct xfs_btree_block *parent_block;
637 13678140 : struct xfs_buf *bp;
638 :
639 13678140 : if (level == cur->bc_nlevels - 1)
640 8907551 : return;
641 :
642 9530241 : xfs_btree_get_keys(cur, block, &block_key);
643 :
644 : /* Make sure the low key of this block matches the parent. */
645 9529420 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
646 9529608 : parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
647 : parent_block);
648 9529640 : 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 9529658 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
654 : return;
655 :
656 : /* Make sure the high key of this block matches the parent. */
657 4770006 : parent_high_key = xfs_btree_high_key_addr(cur,
658 4770006 : cur->bc_levels[level + 1].ptr, parent_block);
659 4770000 : block_high_key = xfs_btree_high_key_from_key(cur, &block_key);
660 4770001 : 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 13678764 : 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 13678764 : xfs_failaddr_t failed_at;
677 13678764 : int error;
678 :
679 13678764 : *pblock = NULL;
680 13678764 : *pbp = NULL;
681 :
682 13678764 : error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
683 27362214 : if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
684 13680469 : !*pblock)
685 0 : return error;
686 :
687 13680469 : xfs_btree_get_block(bs->cur, level, pbp);
688 13680240 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
689 5554147 : failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
690 : level, *pbp);
691 : else
692 8126093 : failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
693 : level, *pbp);
694 13679262 : if (failed_at) {
695 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
696 0 : return 0;
697 : }
698 13679262 : if (*pbp)
699 11347820 : xchk_buffer_recheck(bs->sc, *pbp);
700 :
701 13674516 : 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 13675966 : error = xchk_btree_check_owner(bs, level, *pbp);
708 13679163 : if (error)
709 : return error;
710 :
711 : /*
712 : * Check the block's siblings; this function absorbs error codes
713 : * for us.
714 : */
715 13678876 : error = xchk_btree_block_check_siblings(bs, *pblock);
716 13678784 : if (error)
717 : return error;
718 :
719 13678800 : xchk_btree_block_check_keys(bs, level, *pblock);
720 13678800 : 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 13681434 : xchk_btree_block_keys(
729 : struct xchk_btree *bs,
730 : int level,
731 : struct xfs_btree_block *block)
732 : {
733 13681434 : union xfs_btree_key block_keys;
734 13681434 : struct xfs_btree_cur *cur = bs->cur;
735 13681434 : union xfs_btree_key *high_bk;
736 13681434 : union xfs_btree_key *parent_keys;
737 13681434 : union xfs_btree_key *high_pk;
738 13681434 : struct xfs_btree_block *parent_block;
739 13681434 : struct xfs_buf *bp;
740 :
741 13681434 : if (level >= cur->bc_nlevels - 1)
742 8911412 : return;
743 :
744 : /* Calculate the keys for this block. */
745 9530686 : xfs_btree_get_keys(cur, block, &block_keys);
746 :
747 : /* Obtain the parent's copy of the keys for this block. */
748 9530703 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
749 9530700 : parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
750 : parent_block);
751 :
752 9530665 : if (xfs_btree_keycmp_ne(cur, &block_keys, parent_keys))
753 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
754 :
755 9530669 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
756 : return;
757 :
758 : /* Get high keys */
759 4770005 : high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
760 4770005 : high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
761 : parent_block);
762 :
763 4770006 : 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 4149913 : 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 4149913 : union xfs_btree_ptr ptr;
781 4149913 : struct xchk_btree *bs;
782 4149913 : union xfs_btree_ptr *pp;
783 4149913 : union xfs_btree_rec *recp;
784 4149913 : struct xfs_btree_block *block;
785 4149913 : struct xfs_buf *bp;
786 4149913 : struct check_owner *co;
787 4149913 : struct check_owner *n;
788 4149913 : size_t cur_sz;
789 4149913 : int level;
790 4149913 : 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 4149913 : cur_sz = xchk_btree_sizeof(cur->bc_nlevels);
798 4149913 : if (cur_sz > PAGE_SIZE) {
799 0 : xchk_btree_set_corrupt(sc, cur, 0);
800 0 : return 0;
801 : }
802 4149913 : bs = kzalloc(cur_sz, XCHK_GFP_FLAGS);
803 4148431 : if (!bs)
804 : return -ENOMEM;
805 4148431 : bs->cur = cur;
806 4148431 : bs->scrub_rec = scrub_fn;
807 4148431 : bs->oinfo = oinfo;
808 4148431 : bs->private = private;
809 4148431 : bs->sc = sc;
810 :
811 : /* Initialize scrub state */
812 4148431 : 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 4148431 : level = cur->bc_nlevels - 1;
819 4148431 : cur->bc_ops->init_ptr_from_cur(cur, &ptr);
820 4149346 : if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))
821 0 : goto out;
822 4148846 : error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);
823 4148004 : if (error || !block)
824 0 : goto out;
825 :
826 4148004 : cur->bc_levels[level].ptr = 1;
827 :
828 1478729311 : while (level < cur->bc_nlevels) {
829 1474579035 : block = xfs_btree_get_block(cur, level, &bp);
830 :
831 1474521931 : if (level == 0) {
832 : /* End of leaf, pop back towards the root. */
833 1473379307 : if (cur->bc_levels[level].ptr >
834 1462345391 : be16_to_cpu(block->bb_numrecs)) {
835 11034920 : xchk_btree_block_keys(bs, level, block);
836 11033916 : if (level < cur->bc_nlevels - 1)
837 9463535 : cur->bc_levels[level + 1].ptr++;
838 11033916 : level++;
839 11033916 : continue;
840 : }
841 :
842 : /* Records in order for scrub? */
843 1451310471 : xchk_btree_rec(bs);
844 :
845 : /* Call out to the record checker. */
846 1451050887 : recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
847 : block);
848 1450961003 : error = bs->scrub_rec(bs, recp);
849 1451396368 : if (error)
850 : break;
851 1451396367 : if (xchk_should_terminate(sc, &error) ||
852 1451370958 : (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
853 : break;
854 :
855 1451370958 : cur->bc_levels[level].ptr++;
856 1451370958 : continue;
857 : }
858 :
859 : /* End of node, pop back towards the root. */
860 14823472 : if (cur->bc_levels[level].ptr >
861 12176540 : be16_to_cpu(block->bb_numrecs)) {
862 2646983 : xchk_btree_block_keys(bs, level, block);
863 2646932 : if (level < cur->bc_nlevels - 1)
864 67113 : cur->bc_levels[level + 1].ptr++;
865 2646932 : level++;
866 2646932 : continue;
867 : }
868 :
869 : /* Keys in order for scrub? */
870 9529557 : xchk_btree_key(bs, level);
871 :
872 : /* Drill another level deeper. */
873 9529308 : pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
874 9529753 : if (!xchk_btree_ptr_ok(bs, level, pp)) {
875 0 : cur->bc_levels[level].ptr++;
876 0 : continue;
877 : }
878 9529366 : level--;
879 9529366 : error = xchk_btree_get_block(bs, level, pp, &block, &bp);
880 9529502 : if (error || !block)
881 1 : goto out;
882 :
883 9529501 : cur->bc_levels[level].ptr = 1;
884 : }
885 :
886 4150283 : out:
887 : /* Process deferred owner checks on btree blocks. */
888 10044608 : list_for_each_entry_safe(co, n, &bs->to_check, list) {
889 5894009 : if (!error && bs->cur)
890 5893964 : error = xchk_btree_check_block_owner(bs, co->level,
891 : co->daddr);
892 5894418 : list_del(&co->list);
893 5894165 : kfree(co);
894 : }
895 4150599 : kfree(bs);
896 :
897 4150735 : return error;
898 : }
|
