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 2 : 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 : 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 : 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 141146839 : __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 141146839 : 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 109389 : xchk_btree_process_error(
125 : struct xfs_scrub *sc,
126 : struct xfs_btree_cur *cur,
127 : int level,
128 : int *error)
129 : {
130 40684547 : return __xchk_btree_process_error(sc, cur, level, error,
131 : XFS_SCRUB_OFLAG_CORRUPT, __return_address);
132 : }
133 :
134 : bool
135 98346850 : xchk_btree_xref_process_error(
136 : struct xfs_scrub *sc,
137 : struct xfs_btree_cur *cur,
138 : int level,
139 : int *error)
140 : {
141 100463071 : return __xchk_btree_process_error(sc, cur, level, error,
142 : XFS_SCRUB_OFLAG_XFAIL, __return_address);
143 : }
144 :
145 : /* Record btree block corruption. */
146 : static void
147 0 : __xchk_btree_set_corrupt(
148 : struct xfs_scrub *sc,
149 : struct xfs_btree_cur *cur,
150 : int level,
151 : __u32 errflag,
152 : void *ret_ip)
153 : {
154 0 : sc->sm->sm_flags |= errflag;
155 :
156 0 : if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
157 : {
158 0 : xfs_fsblock_t fsbno = xchk_btree_cur_fsbno(cur, level);
159 0 : xchk_whine(sc->mp, "ino 0x%llx fork %d type %s btnum %d level %d ptr %d agno 0x%x agbno 0x%x errflag 0x%x ret_ip %pS",
160 0 : cur->bc_ino.ip->i_ino,
161 0 : cur->bc_ino.whichfork,
162 0 : xchk_type_string(sc->sm->sm_type),
163 0 : cur->bc_btnum,
164 : level,
165 0 : cur->bc_levels[level].ptr,
166 0 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
167 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
168 : errflag,
169 : ret_ip);
170 0 : trace_xchk_ifork_btree_error(sc, cur, level,
171 : ret_ip);
172 : }
173 : else
174 : {
175 0 : xfs_fsblock_t fsbno = xchk_btree_cur_fsbno(cur, level);
176 0 : xchk_whine(sc->mp, "type %s btnum %d level %d ptr %d agno 0x%x agbno 0x%x errflag 0x%x ret_ip %pS",
177 0 : xchk_type_string(sc->sm->sm_type),
178 0 : cur->bc_btnum,
179 : level,
180 0 : cur->bc_levels[level].ptr,
181 0 : XFS_FSB_TO_AGNO(cur->bc_mp, fsbno),
182 : XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno),
183 : errflag,
184 : ret_ip);
185 0 : trace_xchk_btree_error(sc, cur, level,
186 : ret_ip);
187 : }
188 0 : }
189 :
190 : void
191 0 : xchk_btree_set_corrupt(
192 : struct xfs_scrub *sc,
193 : struct xfs_btree_cur *cur,
194 : int level)
195 : {
196 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_CORRUPT,
197 : __return_address);
198 0 : }
199 :
200 : void
201 0 : xchk_btree_xref_set_corrupt(
202 : struct xfs_scrub *sc,
203 : struct xfs_btree_cur *cur,
204 : int level)
205 : {
206 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_XCORRUPT,
207 : __return_address);
208 0 : }
209 :
210 : void
211 0 : xchk_btree_set_preen(
212 : struct xfs_scrub *sc,
213 : struct xfs_btree_cur *cur,
214 : int level)
215 : {
216 0 : __xchk_btree_set_corrupt(sc, cur, level, XFS_SCRUB_OFLAG_PREEN,
217 : __return_address);
218 0 : }
219 :
220 : /*
221 : * Make sure this record is in order and doesn't stray outside of the parent
222 : * keys.
223 : */
224 : STATIC void
225 1304410744 : xchk_btree_rec(
226 : struct xchk_btree *bs)
227 : {
228 1304410744 : struct xfs_btree_cur *cur = bs->cur;
229 1304410744 : union xfs_btree_rec *rec;
230 1304410744 : union xfs_btree_key key;
231 1304410744 : union xfs_btree_key hkey;
232 1304410744 : union xfs_btree_key *keyp;
233 1304410744 : struct xfs_btree_block *block;
234 1304410744 : struct xfs_btree_block *keyblock;
235 1304410744 : struct xfs_buf *bp;
236 :
237 1304410744 : block = xfs_btree_get_block(cur, 0, &bp);
238 1304438187 : rec = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr, block);
239 :
240 1304413881 : trace_xchk_btree_rec(bs->sc, cur, 0);
241 :
242 : /* Are all records across all record blocks in order? */
243 2606531365 : if (bs->lastrec_valid &&
244 1302124901 : !cur->bc_ops->recs_inorder(cur, &bs->lastrec, rec))
245 0 : xchk_btree_set_corrupt(bs->sc, cur, 0);
246 2608812928 : memcpy(&bs->lastrec, rec, cur->bc_ops->rec_len);
247 1304406464 : bs->lastrec_valid = true;
248 :
249 1304406464 : if (cur->bc_nlevels == 1)
250 626484731 : return;
251 :
252 : /* Is low_key(rec) at least as large as the parent low key? */
253 1281703631 : cur->bc_ops->init_key_from_rec(&key, rec);
254 1281721316 : keyblock = xfs_btree_get_block(cur, 1, &bp);
255 1281750870 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
256 1281763629 : if (xfs_btree_keycmp_lt(cur, &key, keyp))
257 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
258 :
259 1281733341 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
260 : return;
261 :
262 : /* Is high_key(rec) no larger than the parent high key? */
263 677951443 : cur->bc_ops->init_high_key_from_rec(&hkey, rec);
264 677957628 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[1].ptr, keyblock);
265 677958495 : 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 8324209 : xchk_btree_key(
275 : struct xchk_btree *bs,
276 : int level)
277 : {
278 8324209 : struct xfs_btree_cur *cur = bs->cur;
279 8324209 : union xfs_btree_key *key;
280 8324209 : union xfs_btree_key *keyp;
281 8324209 : struct xfs_btree_block *block;
282 8324209 : struct xfs_btree_block *keyblock;
283 8324209 : struct xfs_buf *bp;
284 :
285 8324209 : block = xfs_btree_get_block(cur, level, &bp);
286 8324215 : key = xfs_btree_key_addr(cur, cur->bc_levels[level].ptr, block);
287 :
288 8324203 : trace_xchk_btree_key(bs->sc, cur, level);
289 :
290 : /* Are all low keys across all node blocks in order? */
291 14908114 : if (bs->lastkey[level - 1].valid &&
292 6583899 : !cur->bc_ops->keys_inorder(cur, &bs->lastkey[level - 1].key, key))
293 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
294 16648430 : memcpy(&bs->lastkey[level - 1].key, key, cur->bc_ops->key_len);
295 8324215 : bs->lastkey[level - 1].valid = true;
296 :
297 8324215 : if (level + 1 >= cur->bc_nlevels)
298 3806000 : return;
299 :
300 : /* Is this block's low key at least as large as the parent low key? */
301 5060148 : keyblock = xfs_btree_get_block(cur, level + 1, &bp);
302 5060150 : keyp = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr, keyblock);
303 5060149 : if (xfs_btree_keycmp_lt(cur, key, keyp))
304 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
305 :
306 5060149 : 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 4518216 : key = xfs_btree_high_key_addr(cur, cur->bc_levels[level].ptr, block);
311 4518218 : keyp = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
312 : keyblock);
313 4518218 : 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 23926562 : xchk_btree_ptr_ok(
323 : struct xchk_btree *bs,
324 : int level,
325 : union xfs_btree_ptr *ptr)
326 : {
327 23926562 : bool res;
328 :
329 : /* A btree rooted in an inode has no block pointer to the root. */
330 23926562 : if ((bs->cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
331 4805123 : level == bs->cur->bc_nlevels)
332 : return true;
333 :
334 : /* Otherwise, check the pointers. */
335 22401968 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
336 3280531 : res = xfs_btree_check_lptr(bs->cur, be64_to_cpu(ptr->l), level);
337 : else
338 38242874 : res = xfs_btree_check_sptr(bs->cur, be32_to_cpu(ptr->s), level);
339 22401955 : 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 16648457 : xchk_btree_block_check_sibling(
348 : struct xchk_btree *bs,
349 : int level,
350 : int direction,
351 : union xfs_btree_ptr *sibling)
352 : {
353 16648457 : struct xfs_btree_cur *cur = bs->cur;
354 16648457 : struct xfs_btree_block *pblock;
355 16648457 : struct xfs_buf *pbp;
356 16648457 : struct xfs_btree_cur *ncur = NULL;
357 16648457 : union xfs_btree_ptr *pp;
358 16648457 : int success;
359 16648457 : int error;
360 :
361 16648457 : error = xfs_btree_dup_cursor(cur, &ncur);
362 33296883 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error) ||
363 16648428 : !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 16648428 : if (xfs_btree_ptr_is_null(cur, sibling)) {
371 3480677 : if (direction > 0)
372 1740338 : error = xfs_btree_increment(ncur, level + 1, &success);
373 : else
374 1740339 : error = xfs_btree_decrement(ncur, level + 1, &success);
375 3480678 : if (error == 0 && success)
376 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
377 3480678 : error = 0;
378 3480678 : goto out;
379 : }
380 :
381 : /* Increment upper level pointer. */
382 13167800 : if (direction > 0)
383 6583900 : error = xfs_btree_increment(ncur, level + 1, &success);
384 : else
385 6583900 : error = xfs_btree_decrement(ncur, level + 1, &success);
386 26335580 : if (!xchk_btree_process_error(bs->sc, cur, level + 1, &error))
387 0 : goto out;
388 13167786 : 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 13167786 : pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
395 13167792 : pp = xfs_btree_ptr_addr(ncur, ncur->bc_levels[level + 1].ptr, pblock);
396 13167789 : if (!xchk_btree_ptr_ok(bs, level + 1, pp))
397 0 : goto out;
398 13167793 : if (pbp)
399 13045713 : xchk_buffer_recheck(bs->sc, pbp);
400 :
401 13167791 : if (xfs_btree_diff_two_ptrs(cur, pp, sibling))
402 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
403 13167791 : out:
404 16648469 : xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
405 16648474 : return error;
406 : }
407 :
408 : /* Check the siblings of a btree block. */
409 : STATIC int
410 10758882 : xchk_btree_block_check_siblings(
411 : struct xchk_btree *bs,
412 : struct xfs_btree_block *block)
413 : {
414 10758882 : struct xfs_btree_cur *cur = bs->cur;
415 10758882 : union xfs_btree_ptr leftsib;
416 10758882 : union xfs_btree_ptr rightsib;
417 10758882 : int level;
418 10758882 : int error = 0;
419 :
420 10758882 : xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
421 10758866 : xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
422 10758864 : level = xfs_btree_get_level(block);
423 :
424 : /* Root block should never have siblings. */
425 10758864 : if (level == cur->bc_nlevels - 1) {
426 4869271 : if (!xfs_btree_ptr_is_null(cur, &leftsib) ||
427 2434690 : !xfs_btree_ptr_is_null(cur, &rightsib))
428 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
429 2434598 : 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 8324191 : error = xchk_btree_block_check_sibling(bs, level, -1, &leftsib);
438 8324241 : if (error)
439 : return error;
440 8324241 : error = xchk_btree_block_check_sibling(bs, level, 1, &rightsib);
441 8324243 : if (error)
442 0 : return error;
443 8324243 : 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 9234304 : xchk_btree_check_block_owner(
459 : struct xchk_btree *bs,
460 : int level,
461 : xfs_daddr_t daddr)
462 : {
463 9234304 : xfs_agnumber_t agno;
464 9234304 : xfs_agblock_t agbno;
465 9234304 : xfs_btnum_t btnum;
466 9234304 : bool init_sa;
467 9234304 : int error = 0;
468 :
469 9234304 : if (!bs->cur)
470 : return 0;
471 :
472 9234304 : btnum = bs->cur->bc_btnum;
473 9234304 : agno = xfs_daddr_to_agno(bs->cur->bc_mp, daddr);
474 9234304 : agbno = xfs_daddr_to_agbno(bs->cur->bc_mp, daddr);
475 :
476 9234304 : init_sa = bs->cur->bc_flags & XFS_BTREE_LONG_PTRS;
477 9234304 : if (init_sa) {
478 2116227 : error = xchk_ag_init_existing(bs->sc, agno, &bs->sc->sa);
479 4232443 : if (!xchk_btree_xref_process_error(bs->sc, bs->cur,
480 : level, &error))
481 1 : goto out_free;
482 : }
483 :
484 9234298 : 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 9234333 : if (!bs->sc->sa.bno_cur && btnum == XFS_BTNUM_BNO)
491 0 : bs->cur = NULL;
492 :
493 9234333 : xchk_xref_is_only_owned_by(bs->sc, agbno, 1, bs->oinfo);
494 9234317 : if (!bs->sc->sa.rmap_cur && btnum == XFS_BTNUM_RMAP)
495 0 : bs->cur = NULL;
496 :
497 9234317 : out_free:
498 9234318 : if (init_sa)
499 2116221 : xchk_ag_free(bs->sc, &bs->sc->sa);
500 :
501 9234326 : return error;
502 : }
503 :
504 : /* Check the owner of a btree block. */
505 : STATIC int
506 10758850 : xchk_btree_check_owner(
507 : struct xchk_btree *bs,
508 : int level,
509 : struct xfs_buf *bp)
510 : {
511 10758850 : 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 10758850 : if (bp == NULL) {
520 1524599 : if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE))
521 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
522 1524599 : 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 9234251 : if (cur->bc_btnum == XFS_BTNUM_BNO || cur->bc_btnum == XFS_BTNUM_RMAP) {
534 5724874 : struct check_owner *co;
535 :
536 5724874 : co = kmalloc(sizeof(struct check_owner), XCHK_GFP_FLAGS);
537 5724890 : if (!co)
538 : return -ENOMEM;
539 :
540 5724890 : INIT_LIST_HEAD(&co->list);
541 5724890 : co->level = level;
542 5724890 : co->daddr = xfs_buf_daddr(bp);
543 5724890 : list_add_tail(&co->list, &bs->to_check);
544 5724890 : return 0;
545 : }
546 :
547 3509377 : 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 1496832 : 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 1496832 : if (bs->cur->bc_btnum == XFS_BTNUM_BMAP &&
567 1496833 : bs->cur->bc_ino.whichfork == XFS_DATA_FORK &&
568 1496809 : xfs_inode_has_attr_fork(bs->sc->ip))
569 1480294 : 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 10758844 : xchk_btree_check_minrecs(
580 : struct xchk_btree *bs,
581 : int level,
582 : struct xfs_btree_block *block)
583 : {
584 10758844 : struct xfs_btree_cur *cur = bs->cur;
585 10758844 : unsigned int root_level = cur->bc_nlevels - 1;
586 10758844 : unsigned int numrecs = be16_to_cpu(block->bb_numrecs);
587 :
588 : /* More records than minrecs means the block is ok. */
589 10758844 : 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 2359096 : if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
600 1496829 : level == cur->bc_nlevels - 2) {
601 1496831 : struct xfs_btree_block *root_block;
602 1496831 : struct xfs_buf *root_bp;
603 1496831 : int root_maxrecs;
604 :
605 1496831 : root_block = xfs_btree_get_block(cur, root_level, &root_bp);
606 1496832 : root_maxrecs = cur->bc_ops->get_dmaxrecs(cur, root_level);
607 1496832 : if (xchk_btree_check_iroot_minrecs(bs) &&
608 16536 : (be16_to_cpu(root_block->bb_numrecs) != 1 ||
609 16536 : numrecs <= root_maxrecs))
610 0 : xchk_btree_set_corrupt(bs->sc, cur, level);
611 1496832 : return;
612 : }
613 :
614 : /*
615 : * Otherwise, only the root level is allowed to have fewer than minrecs
616 : * records or keyptrs.
617 : */
618 862265 : 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 10758891 : xchk_btree_block_check_keys(
628 : struct xchk_btree *bs,
629 : int level,
630 : struct xfs_btree_block *block)
631 : {
632 10758891 : union xfs_btree_key block_key;
633 10758891 : union xfs_btree_key *block_high_key;
634 10758891 : union xfs_btree_key *parent_low_key, *parent_high_key;
635 10758891 : struct xfs_btree_cur *cur = bs->cur;
636 10758891 : struct xfs_btree_block *parent_block;
637 10758891 : struct xfs_buf *bp;
638 :
639 10758891 : if (level == cur->bc_nlevels - 1)
640 5828272 : return;
641 :
642 8324244 : xfs_btree_get_keys(cur, block, &block_key);
643 :
644 : /* Make sure the low key of this block matches the parent. */
645 8324214 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
646 8324228 : parent_low_key = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
647 : parent_block);
648 8324219 : 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 8324211 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
654 : return;
655 :
656 : /* Make sure the high key of this block matches the parent. */
657 4930586 : parent_high_key = xfs_btree_high_key_addr(cur,
658 4930586 : cur->bc_levels[level + 1].ptr, parent_block);
659 4930586 : block_high_key = xfs_btree_high_key_from_key(cur, &block_key);
660 4930589 : 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 10758905 : 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 10758905 : xfs_failaddr_t failed_at;
677 10758905 : int error;
678 :
679 10758905 : *pblock = NULL;
680 10758905 : *pbp = NULL;
681 :
682 10758905 : error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
683 21517817 : if (!xchk_btree_process_error(bs->sc, bs->cur, level, &error) ||
684 10758889 : !*pblock)
685 0 : return error;
686 :
687 10758889 : xfs_btree_get_block(bs->cur, level, pbp);
688 10758886 : if (bs->cur->bc_flags & XFS_BTREE_LONG_PTRS)
689 3640805 : failed_at = __xfs_btree_check_lblock(bs->cur, *pblock,
690 : level, *pbp);
691 : else
692 7118081 : failed_at = __xfs_btree_check_sblock(bs->cur, *pblock,
693 : level, *pbp);
694 10758874 : if (failed_at) {
695 0 : xchk_btree_set_corrupt(bs->sc, bs->cur, level);
696 0 : return 0;
697 : }
698 10758874 : if (*pbp)
699 9234285 : xchk_buffer_recheck(bs->sc, *pbp);
700 :
701 10758827 : 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 10758796 : error = xchk_btree_check_owner(bs, level, *pbp);
708 10758884 : if (error)
709 : return error;
710 :
711 : /*
712 : * Check the block's siblings; this function absorbs error codes
713 : * for us.
714 : */
715 10758884 : error = xchk_btree_block_check_siblings(bs, *pblock);
716 10758835 : if (error)
717 : return error;
718 :
719 10758836 : xchk_btree_block_check_keys(bs, level, *pblock);
720 10758836 : 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 10758883 : xchk_btree_block_keys(
729 : struct xchk_btree *bs,
730 : int level,
731 : struct xfs_btree_block *block)
732 : {
733 10758883 : union xfs_btree_key block_keys;
734 10758883 : struct xfs_btree_cur *cur = bs->cur;
735 10758883 : union xfs_btree_key *high_bk;
736 10758883 : union xfs_btree_key *parent_keys;
737 10758883 : union xfs_btree_key *high_pk;
738 10758883 : struct xfs_btree_block *parent_block;
739 10758883 : struct xfs_buf *bp;
740 :
741 10758883 : if (level >= cur->bc_nlevels - 1)
742 5828301 : return;
743 :
744 : /* Calculate the keys for this block. */
745 8324231 : xfs_btree_get_keys(cur, block, &block_keys);
746 :
747 : /* Obtain the parent's copy of the keys for this block. */
748 8324232 : parent_block = xfs_btree_get_block(cur, level + 1, &bp);
749 8324219 : parent_keys = xfs_btree_key_addr(cur, cur->bc_levels[level + 1].ptr,
750 : parent_block);
751 :
752 8324232 : if (xfs_btree_keycmp_ne(cur, &block_keys, parent_keys))
753 0 : xchk_btree_set_corrupt(bs->sc, cur, 1);
754 :
755 8324237 : if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
756 : return;
757 :
758 : /* Get high keys */
759 4930588 : high_bk = xfs_btree_high_key_from_key(cur, &block_keys);
760 4930588 : high_pk = xfs_btree_high_key_addr(cur, cur->bc_levels[level + 1].ptr,
761 : parent_block);
762 :
763 4930589 : 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 2434636 : 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 2434636 : union xfs_btree_ptr ptr;
781 2434636 : struct xchk_btree *bs;
782 2434636 : union xfs_btree_ptr *pp;
783 2434636 : union xfs_btree_rec *recp;
784 2434636 : struct xfs_btree_block *block;
785 2434636 : struct xfs_buf *bp;
786 2434636 : struct check_owner *co;
787 2434636 : struct check_owner *n;
788 2434636 : size_t cur_sz;
789 2434636 : int level;
790 2434636 : 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 2434636 : cur_sz = xchk_btree_sizeof(cur->bc_nlevels);
798 2434636 : if (cur_sz > PAGE_SIZE) {
799 0 : xchk_btree_set_corrupt(sc, cur, 0);
800 0 : return 0;
801 : }
802 2434636 : bs = kzalloc(cur_sz, XCHK_GFP_FLAGS);
803 2434684 : if (!bs)
804 : return -ENOMEM;
805 2434684 : bs->cur = cur;
806 2434684 : bs->scrub_rec = scrub_fn;
807 2434684 : bs->oinfo = oinfo;
808 2434684 : bs->private = private;
809 2434684 : bs->sc = sc;
810 :
811 : /* Initialize scrub state */
812 2434684 : 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 2434684 : level = cur->bc_nlevels - 1;
819 2434684 : cur->bc_ops->init_ptr_from_cur(cur, &ptr);
820 2434621 : if (!xchk_btree_ptr_ok(bs, cur->bc_nlevels, &ptr))
821 0 : goto out;
822 2434605 : error = xchk_btree_get_block(bs, level, &ptr, &block, &bp);
823 2434694 : if (error || !block)
824 0 : goto out;
825 :
826 2434694 : cur->bc_levels[level].ptr = 1;
827 :
828 1325964811 : while (level < cur->bc_nlevels) {
829 1323530133 : block = xfs_btree_get_block(cur, level, &bp);
830 :
831 1323502515 : if (level == 0) {
832 : /* End of leaf, pop back towards the root. */
833 1313388385 : if (cur->bc_levels[level].ptr >
834 1313388385 : be16_to_cpu(block->bb_numrecs)) {
835 8968999 : xchk_btree_block_keys(bs, level, block);
836 8968975 : if (level < cur->bc_nlevels - 1)
837 8250226 : cur->bc_levels[level + 1].ptr++;
838 8968975 : level++;
839 8968975 : continue;
840 : }
841 :
842 : /* Records in order for scrub? */
843 1304419386 : xchk_btree_rec(bs);
844 :
845 : /* Call out to the record checker. */
846 1304437000 : recp = xfs_btree_rec_addr(cur, cur->bc_levels[0].ptr,
847 : block);
848 1304433064 : error = bs->scrub_rec(bs, recp);
849 1304413222 : if (error)
850 : break;
851 1304413222 : if (xchk_should_terminate(sc, &error) ||
852 1304446994 : (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
853 : break;
854 :
855 1304446994 : cur->bc_levels[level].ptr++;
856 1304446994 : continue;
857 : }
858 :
859 : /* End of node, pop back towards the root. */
860 10114130 : if (cur->bc_levels[level].ptr >
861 10114130 : be16_to_cpu(block->bb_numrecs)) {
862 1789911 : xchk_btree_block_keys(bs, level, block);
863 1789914 : if (level < cur->bc_nlevels - 1)
864 73997 : cur->bc_levels[level + 1].ptr++;
865 1789914 : level++;
866 1789914 : continue;
867 : }
868 :
869 : /* Keys in order for scrub? */
870 8324219 : xchk_btree_key(bs, level);
871 :
872 : /* Drill another level deeper. */
873 8324223 : pp = xfs_btree_ptr_addr(cur, cur->bc_levels[level].ptr, block);
874 8324207 : if (!xchk_btree_ptr_ok(bs, level, pp)) {
875 0 : cur->bc_levels[level].ptr++;
876 0 : continue;
877 : }
878 8324230 : level--;
879 8324230 : error = xchk_btree_get_block(bs, level, pp, &block, &bp);
880 8324235 : if (error || !block)
881 1 : goto out;
882 :
883 8324234 : cur->bc_levels[level].ptr = 1;
884 : }
885 :
886 2434678 : out:
887 : /* Process deferred owner checks on btree blocks. */
888 8159581 : list_for_each_entry_safe(co, n, &bs->to_check, list) {
889 5724915 : if (!error && bs->cur)
890 5724914 : error = xchk_btree_check_block_owner(bs, co->level,
891 : co->daddr);
892 5724895 : list_del(&co->list);
893 5724888 : kfree(co);
894 : }
895 2434666 : kfree(bs);
896 :
897 2434655 : return error;
898 : }
|
