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