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 2 : xchk_btree_cur_fsbno(
26 : struct xfs_btree_cur *cur,
27 : int level)
28 : {
29 2 : if (level < cur->bc_nlevels && cur->bc_levels[level].bp)
30 2 : 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 2 : 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 2 : xfs_fsblock_t fsbno = xchk_btree_cur_fsbno(cur, level);
50 :
51 2 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
52 8 : 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 2 : cur->bc_ino.ip->i_ino,
54 2 : cur->bc_ino.whichfork,
55 2 : xchk_type_string(sc->sm->sm_type),
56 2 : cur->bc_btnum,
57 : level,
58 2 : cur->bc_levels[level].ptr,
59 2 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
60 2 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
61 : *error,
62 : errflag,
63 : ret_ip);
64 2 : 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 198982757 : __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 198982757 : if (*error == 0)
93 : return true;
94 :
95 2 : 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 2 : fallthrough;
108 2 : default:
109 2 : if (*error)
110 2 : process_error_whine(sc, cur, level, error, errflag,
111 : ret_ip);
112 2 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
113 2 : 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 481084 : xchk_btree_process_error(
125 : struct xfs_scrub *sc,
126 : struct xfs_btree_cur *cur,
127 : int level,
128 : int *error)
129 : {
130 99921950 : return __xchk_btree_process_error(sc, cur, level, error,
131 : XFS_SCRUB_OFLAG_CORRUPT, __return_address);
132 : }
133 :
134 : bool
135 87595987 : xchk_btree_xref_process_error(
136 : struct xfs_scrub *sc,
137 : struct xfs_btree_cur *cur,
138 : int level,
139 : int *error)
140 : {
141 99063798 : 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 3046827006 : xchk_btree_rec(
226 : struct xchk_btree *bs)
227 : {
228 3046827006 : struct xfs_btree_cur *cur = bs->cur;
229 3046827006 : union xfs_btree_rec *rec;
230 3046827006 : union xfs_btree_key key;
231 3046827006 : union xfs_btree_key hkey;
232 3046827006 : union xfs_btree_key *keyp;
233 3046827006 : struct xfs_btree_block *block;
234 3046827006 : struct xfs_btree_block *keyblock;
235 3046827006 : struct xfs_buf *bp;
236 :
237 3046827006 : block = xfs_btree_get_block(cur, 0, &bp);
238 3046682446 : rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);
239 :
240 3046566802 : trace_xchk_btree_rec(bs->sc, cur, 0);
241 :
242 : /* Are all records across all record blocks in order? */
243 6088190168 : if (bs->lastrec_valid &&
244 3041402130 : !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
245 0 : xchk_btree_set_corrupt(bs->sc, cur, 0);
246 6093576076 : memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
247 3046788038 : bs->lastrec_valid = true;
248 :
249 3046788038 : if (cur->bc_nlevels == 1)
250 1315238129 : return;
251 :
252 : /* Is low_key(rec) at least as large as the parent low key? */
253 3012387101 : cur->bc_ops->init_key_from_rec(&key, rec);
254 3012006702 : keyblock = xfs_btree_get_block(cur, 1, &bp);
255 3012049938 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
256 3011491188 : if (xfs_btree_keycmp_lt(cur, &key, keyp))
257 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
258 :
259 3011488263 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
260 : return;
261 :
262 : /* Is high_key(rec) no larger than the parent high key? */
263 1730651071 : cur->bc_ops->init_high_key_from_rec(&hkey, rec);
264 1730762457 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
265 1730839812 : 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 19984842 : xchk_btree_key(
275 : struct xchk_btree *bs,
276 : int level)
277 : {
278 19984842 : struct xfs_btree_cur *cur = bs->cur;
279 19984842 : union xfs_btree_key *key;
280 19984842 : union xfs_btree_key *keyp;
281 19984842 : struct xfs_btree_block *block;
282 19984842 : struct xfs_btree_block *keyblock;
283 19984842 : struct xfs_buf *bp;
284 :
285 19984842 : block = xfs_btree_get_block(cur, level, &bp);
286 19984945 : key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
287 :
288 19984745 : trace_xchk_btree_key(bs->sc, cur, level);
289 :
290 : /* Are all low keys across all node blocks in order? */
291 36929000 : if (bs->lastkey[level - 1].valid &&
292 16944165 : !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key))
293 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
294 39969670 : memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len);
295 19984835 : bs->lastkey[level - 1].valid = true;
296 :
297 19984835 : if (level + 1 >= cur->bc_nlevels)
298 9203352 : return;
299 :
300 : /* Is this block's low key at least as large as the parent low key? */
301 13331765 : keyblock = xfs_btree_get_block(cur, level + 1, &bp);
302 13331773 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);
303 13331751 : if (xfs_btree_keycmp_lt(cur, key, keyp))
304 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
305 :
306 13331776 : 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 10781494 : key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);
311 10781487 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
312 : keyblock);
313 10781495 : 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 59466846 : xchk_btree_ptr_ok(
323 : struct xchk_btree *bs,
324 : int level,
325 : union xfs_btree_ptr *ptr)
326 : {
327 59466846 : bool res;
328 :
329 : /* A btree rooted in an inode has no block pointer to the root. */
330 59466846 : if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
331 31771540 : level == bs->cur->bc_nlevels)
332 : return true;
333 :
334 : /* Otherwise, check the pointers. */
335 56688010 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
336 28992739 : res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
337 : else
338 27695271 : res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
339 56687589 : 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 39970889 : xchk_btree_block_check_sibling(
348 : struct xchk_btree *bs,
349 : int level,
350 : int direction,
351 : union xfs_btree_ptr *sibling)
352 : {
353 39970889 : struct xfs_btree_cur *cur = bs->cur;
354 39970889 : struct xfs_btree_block *pblock;
355 39970889 : struct xfs_buf *pbp;
356 39970889 : struct xfs_btree_cur *ncur = NULL;
357 39970889 : union xfs_btree_ptr *pp;
358 39970889 : int success;
359 39970889 : int error;
360 :
361 39970889 : error = xfs_btree_dup_cursor(cur, &ncur);
362 79941305 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
363 39970645 : !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 39970645 : if (xfs_btree_ptr_is_null(cur, sibling)) {
371 6082600 : if (direction > 0)
372 3041358 : error = xfs_btree_increment(ncur, level + 1, &success);
373 : else
374 3041242 : error = xfs_btree_decrement(ncur, level + 1, &success);
375 6082359 : if (error == 0 && success)
376 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
377 6082359 : error = 0;
378 6082359 : goto out;
379 : }
380 :
381 : /* Increment upper level pointer. */
382 33888057 : if (direction > 0)
383 16944076 : error = xfs_btree_increment(ncur, level + 1, &success);
384 : else
385 16943981 : error = xfs_btree_decrement(ncur, level + 1, &success);
386 67776225 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
387 0 : goto out;
388 33888070 : 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 33888070 : pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
395 33887928 : pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);
396 33888052 : if (!xchk_btree_ptr_ok(bs, level + 1, pp))
397 0 : goto out;
398 33888104 : if (pbp)
399 32466158 : xchk_buffer_recheck(bs->sc, pbp);
400 :
401 33888218 : if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
402 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
403 33888018 : out:
404 39970377 : xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
405 39970861 : return error;
406 : }
407 :
408 : /* Check the siblings of a btree block. */
409 : STATIC int
410 25579022 : xchk_btree_block_check_siblings(
411 : struct xchk_btree *bs,
412 : struct xfs_btree_block *block)
413 : {
414 25579022 : struct xfs_btree_cur *cur = bs->cur;
415 25579022 : union xfs_btree_ptr leftsib;
416 25579022 : union xfs_btree_ptr rightsib;
417 25579022 : int level;
418 25579022 : int error = 0;
419 :
420 25579022 : xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
421 25578817 : xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
422 25579091 : level = xfs_btree_get_level(block);
423 :
424 : /* Root block should never have siblings. */
425 25579091 : if (level == cur->bc_nlevels - 1) {
426 11187150 : if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
427 5592547 : !xfs_btree_ptr_is_null(cur, &rightsib))
428 173 : xchk_btree_set_corrupt(bs->sc, cur, level);
429 5593721 : 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 19985662 : error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
438 19985409 : if (error)
439 : return error;
440 19985345 : error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
441 19985556 : if (error)
442 0 : return error;
443 19985556 : 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 22799139 : xchk_btree_check_block_owner(
459 : struct xchk_btree *bs,
460 : int level,
461 : xfs_daddr_t daddr)
462 : {
463 22799139 : xfs_agnumber_t agno;
464 22799139 : xfs_agblock_t agbno;
465 22799139 : xfs_btnum_t btnum;
466 22799139 : bool init_sa;
467 22799139 : int error = 0;
468 :
469 22799139 : if (!bs->cur)
470 : return 0;
471 :
472 22799139 : btnum = bs->cur->bc_btnum;
473 22799139 : agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
474 22797107 : agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
475 :
476 22796950 : init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
477 22796950 : if (init_sa) {
478 11466563 : error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
479 22935512 : if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
480 : level, &error))
481 2 : goto out_free;
482 : }
483 :
484 22798084 : 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 22801366 : if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
491 0 : bs->cur = NULL;
492 :
493 22801366 : xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo);
494 22802122 : if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
495 0 : bs->cur = NULL;
496 :
497 22802122 : out_free:
498 22802124 : if (init_sa)
499 11467771 : xchk_ag_free(bs->sc, &bs->sc->sa);
500 :
501 22802243 : return error;
502 : }
503 :
504 : /* Check the owner of a btree block. */
505 : STATIC int
506 25576814 : xchk_btree_check_owner(
507 : struct xchk_btree *bs,
508 : int level,
509 : struct xfs_buf *bp)
510 : {
511 25576814 : 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 25576814 : if (bp == NULL) {
520 2778464 : if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
521 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
522 2778464 : 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 22798350 : if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
534 8497192 : struct check_owner *co;
535 :
536 8497192 : co = kmalloc(sizeof(struct check_owner), XCHK_GFP_FLAGS);
537 8497262 : if (!co)
538 : return -ENOMEM;
539 :
540 8497262 : INIT_LIST_HEAD(&co->list);
541 8497262 : co->level = level;
542 8497262 : co->daddr = xfs_buf_daddr(bp);
543 8497262 : list_add_tail(&co->list, &bs->to_check);
544 8497262 : return 0;
545 : }
546 :
547 14301158 : 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 2260225 : 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 2260225 : if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
567 2202388 : bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
568 2202257 : xfs_inode_has_attr_fork(bs->sc->ip))
569 2193178 : 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 25577463 : xchk_btree_check_minrecs(
580 : struct xchk_btree *bs,
581 : int level,
582 : struct xfs_btree_block *block)
583 : {
584 25577463 : struct xfs_btree_cur *cur = bs->cur;
585 25577463 : unsigned int root_level = cur->bc_nlevels - 1;
586 25577463 : unsigned int numrecs = be16_to_cpu(block->bb_numrecs);
587 :
588 : /* More records than minrecs means the block is ok. */
589 25577463 : 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 4991700 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
600 2260091 : level == cur->bc_nlevels - 2) {
601 2259993 : struct xfs_btree_block *root_block;
602 2259993 : struct xfs_buf *root_bp;
603 2259993 : int root_maxrecs;
604 :
605 2259993 : root_block = xfs_btree_get_block(cur, root_level, &root_bp);
606 2260459 : root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
607 2260393 : if (xchk_btree_check_iroot_minrecs(bs) &&
608 67223 : (be16_to_cpu(root_block->bb_numrecs) != 1 ||
609 67223 : numrecs <= root_maxrecs))
610 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
611 2260393 : return;
612 : }
613 :
614 : /*
615 : * Otherwise, only the root level is allowed to have fewer than minrecs
616 : * records or keyptrs.
617 : */
618 2731707 : 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 25578060 : xchk_btree_block_check_keys(
628 : struct xchk_btree *bs,
629 : int level,
630 : struct xfs_btree_block *block)
631 : {
632 25578060 : union xfs_btree_key block_key;
633 25578060 : union xfs_btree_key *block_high_key;
634 25578060 : union xfs_btree_key *parent_low_key, *parent_high_key;
635 25578060 : struct xfs_btree_cur *cur = bs->cur;
636 25578060 : struct xfs_btree_block *parent_block;
637 25578060 : struct xfs_buf *bp;
638 :
639 25578060 : if (level == cur->bc_nlevels - 1)
640 12768551 : return;
641 :
642 19985444 : xfs_btree_get_keys(cur, block, &block_key);
643 :
644 : /* Make sure the low key of this block matches the parent. */
645 19985215 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
646 19985305 : parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
647 : parent_block);
648 19985265 : 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 19985205 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
654 : return;
655 :
656 : /* Make sure the high key of this block matches the parent. */
657 12809270 : parent_high_key = xfs_btree_high_key_addr(cur,
658 12809270 : cur->bc_levels[level + 1].ptr, parent_block);
659 12809261 : block_high_key = xfs_btree_high_key_from_key(cur, &block_key);
660 12809270 : 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 25578877 : 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 25578877 : xfs_failaddr_t failed_at;
677 25578877 : int error;
678 :
679 25578877 : *pblock = NULL;
680 25578877 : *pbp = NULL;
681 :
682 25578877 : error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
683 51162367 : if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
684 25580285 : !*pblock)
685 0 : return error;
686 :
687 25580285 : xfs_btree_get_block(bs->cur, level, pbp);
688 25579290 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
689 14246199 : failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
690 : level, *pbp);
691 : else
692 11333091 : failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
693 : level, *pbp);
694 25579346 : if (failed_at) {
695 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
696 0 : return 0;
697 : }
698 25579346 : if (*pbp)
699 22800885 : xchk_buffer_recheck(bs->sc, *pbp);
700 :
701 25575854 : 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 25575429 : error = xchk_btree_check_owner(bs, level, *pbp);
708 25579063 : if (error)
709 : return error;
710 :
711 : /*
712 : * Check the block's siblings; this function absorbs error codes
713 : * for us.
714 : */
715 25578677 : error = xchk_btree_block_check_siblings(bs, *pblock);
716 25578821 : if (error)
717 : return error;
718 :
719 25578858 : xchk_btree_block_check_keys(bs, level, *pblock);
720 25578858 : 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 25581272 : xchk_btree_block_keys(
729 : struct xchk_btree *bs,
730 : int level,
731 : struct xfs_btree_block *block)
732 : {
733 25581272 : union xfs_btree_key block_keys;
734 25581272 : struct xfs_btree_cur *cur = bs->cur;
735 25581272 : union xfs_btree_key *high_bk;
736 25581272 : union xfs_btree_key *parent_keys;
737 25581272 : union xfs_btree_key *high_pk;
738 25581272 : struct xfs_btree_block *parent_block;
739 25581272 : struct xfs_buf *bp;
740 :
741 25581272 : if (level >= cur->bc_nlevels - 1)
742 12772067 : return;
743 :
744 : /* Calculate the keys for this block. */
745 19985548 : xfs_btree_get_keys(cur, block, &block_keys);
746 :
747 : /* Obtain the parent's copy of the keys for this block. */
748 19985654 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
749 19985651 : parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
750 : parent_block);
751 :
752 19985636 : if (xfs_btree_keycmp_ne(cur, &block_keys, parent_keys))
753 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
754 :
755 19985642 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
756 : return;
757 :
758 : /* Get high keys */
759 12809299 : high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
760 12809296 : high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
761 : parent_block);
762 :
763 12809301 : 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 5594104 : 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 5594104 : union xfs_btree_ptr ptr;
781 5594104 : struct xchk_btree *bs;
782 5594104 : union xfs_btree_ptr *pp;
783 5594104 : union xfs_btree_rec *recp;
784 5594104 : struct xfs_btree_block *block;
785 5594104 : struct xfs_buf *bp;
786 5594104 : struct check_owner *co;
787 5594104 : struct check_owner *n;
788 5594104 : size_t cur_sz;
789 5594104 : int level;
790 5594104 : 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 5594104 : cur_sz = xchk_btree_sizeof(cur->bc_nlevels);
798 5594104 : if (cur_sz > PAGE_SIZE) {
799 0 : xchk_btree_set_corrupt(sc, cur, 0);
800 0 : return 0;
801 : }
802 5594104 : bs = kzalloc(cur_sz, XCHK_GFP_FLAGS);
803 5593165 : if (!bs)
804 : return -ENOMEM;
805 5593165 : bs->cur = cur;
806 5593165 : bs->scrub_rec = scrub_fn;
807 5593165 : bs->oinfo = oinfo;
808 5593165 : bs->private = private;
809 5593165 : bs->sc = sc;
810 :
811 : /* Initialize scrub state */
812 5593165 : 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 5593165 : level = cur->bc_nlevels - 1;
819 5593165 : cur->bc_ops->init_ptr_from_cur(cur, &ptr);
820 5593795 : if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))
821 0 : goto out;
822 5593540 : error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);
823 5592813 : if (error || !block)
824 0 : goto out;
825 :
826 5592813 : cur->bc_levels[level].ptr = 1;
827 :
828 3098429466 : while (level < cur->bc_nlevels) {
829 3092834096 : block = xfs_btree_get_block(cur, level, &bp);
830 :
831 3092464799 : if (level == 0) {
832 : /* End of leaf, pop back towards the root. */
833 3091728780 : if (cur->bc_levels[level].ptr >
834 3069314116 : be16_to_cpu(block->bb_numrecs)) {
835 22415783 : xchk_btree_block_keys(bs, level, block);
836 22414664 : if (level < cur->bc_nlevels - 1)
837 19759464 : cur->bc_levels[level + 1].ptr++;
838 22414664 : level++;
839 22414664 : continue;
840 : }
841 :
842 : /* Records in order for scrub? */
843 3046898333 : xchk_btree_rec(bs);
844 :
845 : /* Call out to the record checker. */
846 3046402473 : recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
847 : block);
848 3046056777 : error = bs->scrub_rec(bs, recp);
849 3047177793 : if (error)
850 : break;
851 3047177792 : if (xchk_should_terminate(sc, &error) ||
852 3047270820 : (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
853 : break;
854 :
855 3047270820 : cur->bc_levels[level].ptr++;
856 3047270820 : continue;
857 : }
858 :
859 : /* End of node, pop back towards the root. */
860 26316545 : if (cur->bc_levels[level].ptr >
861 23150683 : be16_to_cpu(block->bb_numrecs)) {
862 3165872 : xchk_btree_block_keys(bs, level, block);
863 3165862 : if (level < cur->bc_nlevels - 1)
864 226172 : cur->bc_levels[level + 1].ptr++;
865 3165862 : level++;
866 3165862 : continue;
867 : }
868 :
869 : /* Keys in order for scrub? */
870 19984811 : xchk_btree_key(bs, level);
871 :
872 : /* Drill another level deeper. */
873 19984790 : pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
874 19984882 : if (!xchk_btree_ptr_ok(bs, level, pp)) {
875 0 : cur->bc_levels[level].ptr++;
876 0 : continue;
877 : }
878 19984689 : level--;
879 19984689 : error = xchk_btree_get_block(bs, level, pp, &block, &bp);
880 19985309 : if (error || !block)
881 2 : goto out;
882 :
883 19985307 : cur->bc_levels[level].ptr = 1;
884 : }
885 :
886 5595385 : out:
887 : /* Process deferred owner checks on btree blocks. */
888 14093548 : list_for_each_entry_safe(co, n, &bs->to_check, list) {
889 8497774 : if (!error && bs->cur)
890 8497344 : error = xchk_btree_check_block_owner(bs, co->level,
891 : co->daddr);
892 8498177 : list_del(&co->list);
893 8497774 : kfree(co);
894 : }
895 5595774 : kfree(bs);
896 :
897 5595501 : return error;
898 : }
|
