Loading...
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_log_format.h"
13#include "xfs_trans.h"
14#include "xfs_inode.h"
15#include "xfs_dir2.h"
16#include "xfs_dir2_priv.h"
17#include "xfs_attr_leaf.h"
18#include "scrub/scrub.h"
19#include "scrub/common.h"
20#include "scrub/trace.h"
21#include "scrub/dabtree.h"
22
23/* Directory/Attribute Btree */
24
25/*
26 * Check for da btree operation errors. See the section about handling
27 * operational errors in common.c.
28 */
29bool
30xchk_da_process_error(
31 struct xchk_da_btree *ds,
32 int level,
33 int *error)
34{
35 struct xfs_scrub *sc = ds->sc;
36
37 if (*error == 0)
38 return true;
39
40 switch (*error) {
41 case -EDEADLOCK:
42 case -ECHRNG:
43 /* Used to restart an op with deadlock avoidance. */
44 trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
45 break;
46 case -EFSBADCRC:
47 case -EFSCORRUPTED:
48 /* Note the badness but don't abort. */
49 sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT;
50 *error = 0;
51 fallthrough;
52 default:
53 trace_xchk_file_op_error(sc, ds->dargs.whichfork,
54 xfs_dir2_da_to_db(ds->dargs.geo,
55 ds->state->path.blk[level].blkno),
56 *error, __return_address);
57 break;
58 }
59 return false;
60}
61
62/*
63 * Check for da btree corruption. See the section about handling
64 * operational errors in common.c.
65 */
66void
67xchk_da_set_corrupt(
68 struct xchk_da_btree *ds,
69 int level)
70{
71 struct xfs_scrub *sc = ds->sc;
72
73 sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT;
74
75 trace_xchk_fblock_error(sc, ds->dargs.whichfork,
76 xfs_dir2_da_to_db(ds->dargs.geo,
77 ds->state->path.blk[level].blkno),
78 __return_address);
79}
80
81static struct xfs_da_node_entry *
82xchk_da_btree_node_entry(
83 struct xchk_da_btree *ds,
84 int level)
85{
86 struct xfs_da_state_blk *blk = &ds->state->path.blk[level];
87 struct xfs_da3_icnode_hdr hdr;
88
89 ASSERT(blk->magic == XFS_DA_NODE_MAGIC);
90
91 xfs_da3_node_hdr_from_disk(ds->sc->mp, &hdr, blk->bp->b_addr);
92 return hdr.btree + blk->index;
93}
94
95/* Scrub a da btree hash (key). */
96int
97xchk_da_btree_hash(
98 struct xchk_da_btree *ds,
99 int level,
100 __be32 *hashp)
101{
102 struct xfs_da_node_entry *entry;
103 xfs_dahash_t hash;
104 xfs_dahash_t parent_hash;
105
106 /* Is this hash in order? */
107 hash = be32_to_cpu(*hashp);
108 if (hash < ds->hashes[level])
109 xchk_da_set_corrupt(ds, level);
110 ds->hashes[level] = hash;
111
112 if (level == 0)
113 return 0;
114
115 /* Is this hash no larger than the parent hash? */
116 entry = xchk_da_btree_node_entry(ds, level - 1);
117 parent_hash = be32_to_cpu(entry->hashval);
118 if (parent_hash < hash)
119 xchk_da_set_corrupt(ds, level);
120
121 return 0;
122}
123
124/*
125 * Check a da btree pointer. Returns true if it's ok to use this
126 * pointer.
127 */
128STATIC bool
129xchk_da_btree_ptr_ok(
130 struct xchk_da_btree *ds,
131 int level,
132 xfs_dablk_t blkno)
133{
134 if (blkno < ds->lowest || (ds->highest != 0 && blkno >= ds->highest)) {
135 xchk_da_set_corrupt(ds, level);
136 return false;
137 }
138
139 return true;
140}
141
142/*
143 * The da btree scrubber can handle leaf1 blocks as a degenerate
144 * form of leafn blocks. Since the regular da code doesn't handle
145 * leaf1, we must multiplex the verifiers.
146 */
147static void
148xchk_da_btree_read_verify(
149 struct xfs_buf *bp)
150{
151 struct xfs_da_blkinfo *info = bp->b_addr;
152
153 switch (be16_to_cpu(info->magic)) {
154 case XFS_DIR2_LEAF1_MAGIC:
155 case XFS_DIR3_LEAF1_MAGIC:
156 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
157 bp->b_ops->verify_read(bp);
158 return;
159 default:
160 /*
161 * xfs_da3_node_buf_ops already know how to handle
162 * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
163 */
164 bp->b_ops = &xfs_da3_node_buf_ops;
165 bp->b_ops->verify_read(bp);
166 return;
167 }
168}
169static void
170xchk_da_btree_write_verify(
171 struct xfs_buf *bp)
172{
173 struct xfs_da_blkinfo *info = bp->b_addr;
174
175 switch (be16_to_cpu(info->magic)) {
176 case XFS_DIR2_LEAF1_MAGIC:
177 case XFS_DIR3_LEAF1_MAGIC:
178 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
179 bp->b_ops->verify_write(bp);
180 return;
181 default:
182 /*
183 * xfs_da3_node_buf_ops already know how to handle
184 * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
185 */
186 bp->b_ops = &xfs_da3_node_buf_ops;
187 bp->b_ops->verify_write(bp);
188 return;
189 }
190}
191static void *
192xchk_da_btree_verify(
193 struct xfs_buf *bp)
194{
195 struct xfs_da_blkinfo *info = bp->b_addr;
196
197 switch (be16_to_cpu(info->magic)) {
198 case XFS_DIR2_LEAF1_MAGIC:
199 case XFS_DIR3_LEAF1_MAGIC:
200 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
201 return bp->b_ops->verify_struct(bp);
202 default:
203 bp->b_ops = &xfs_da3_node_buf_ops;
204 return bp->b_ops->verify_struct(bp);
205 }
206}
207
208static const struct xfs_buf_ops xchk_da_btree_buf_ops = {
209 .name = "xchk_da_btree",
210 .verify_read = xchk_da_btree_read_verify,
211 .verify_write = xchk_da_btree_write_verify,
212 .verify_struct = xchk_da_btree_verify,
213};
214
215/* Check a block's sibling. */
216STATIC int
217xchk_da_btree_block_check_sibling(
218 struct xchk_da_btree *ds,
219 int level,
220 int direction,
221 xfs_dablk_t sibling)
222{
223 struct xfs_da_state_path *path = &ds->state->path;
224 struct xfs_da_state_path *altpath = &ds->state->altpath;
225 int retval;
226 int plevel;
227 int error;
228
229 memcpy(altpath, path, sizeof(ds->state->altpath));
230
231 /*
232 * If the pointer is null, we shouldn't be able to move the upper
233 * level pointer anywhere.
234 */
235 if (sibling == 0) {
236 error = xfs_da3_path_shift(ds->state, altpath, direction,
237 false, &retval);
238 if (error == 0 && retval == 0)
239 xchk_da_set_corrupt(ds, level);
240 error = 0;
241 goto out;
242 }
243
244 /* Move the alternate cursor one block in the direction given. */
245 error = xfs_da3_path_shift(ds->state, altpath, direction, false,
246 &retval);
247 if (!xchk_da_process_error(ds, level, &error))
248 goto out;
249 if (retval) {
250 xchk_da_set_corrupt(ds, level);
251 goto out;
252 }
253 if (altpath->blk[level].bp)
254 xchk_buffer_recheck(ds->sc, altpath->blk[level].bp);
255
256 /* Compare upper level pointer to sibling pointer. */
257 if (altpath->blk[level].blkno != sibling)
258 xchk_da_set_corrupt(ds, level);
259
260out:
261 /* Free all buffers in the altpath that aren't referenced from path. */
262 for (plevel = 0; plevel < altpath->active; plevel++) {
263 if (altpath->blk[plevel].bp == NULL ||
264 (plevel < path->active &&
265 altpath->blk[plevel].bp == path->blk[plevel].bp))
266 continue;
267
268 xfs_trans_brelse(ds->dargs.trans, altpath->blk[plevel].bp);
269 altpath->blk[plevel].bp = NULL;
270 }
271
272 return error;
273}
274
275/* Check a block's sibling pointers. */
276STATIC int
277xchk_da_btree_block_check_siblings(
278 struct xchk_da_btree *ds,
279 int level,
280 struct xfs_da_blkinfo *hdr)
281{
282 xfs_dablk_t forw;
283 xfs_dablk_t back;
284 int error = 0;
285
286 forw = be32_to_cpu(hdr->forw);
287 back = be32_to_cpu(hdr->back);
288
289 /* Top level blocks should not have sibling pointers. */
290 if (level == 0) {
291 if (forw != 0 || back != 0)
292 xchk_da_set_corrupt(ds, level);
293 return 0;
294 }
295
296 /*
297 * Check back (left) and forw (right) pointers. These functions
298 * absorb error codes for us.
299 */
300 error = xchk_da_btree_block_check_sibling(ds, level, 0, back);
301 if (error)
302 goto out;
303 error = xchk_da_btree_block_check_sibling(ds, level, 1, forw);
304
305out:
306 memset(&ds->state->altpath, 0, sizeof(ds->state->altpath));
307 return error;
308}
309
310/* Load a dir/attribute block from a btree. */
311STATIC int
312xchk_da_btree_block(
313 struct xchk_da_btree *ds,
314 int level,
315 xfs_dablk_t blkno)
316{
317 struct xfs_da_state_blk *blk;
318 struct xfs_da_intnode *node;
319 struct xfs_da_node_entry *btree;
320 struct xfs_da3_blkinfo *hdr3;
321 struct xfs_da_args *dargs = &ds->dargs;
322 struct xfs_inode *ip = ds->dargs.dp;
323 xfs_ino_t owner;
324 int *pmaxrecs;
325 struct xfs_da3_icnode_hdr nodehdr;
326 int error = 0;
327
328 blk = &ds->state->path.blk[level];
329 ds->state->path.active = level + 1;
330
331 /* Release old block. */
332 if (blk->bp) {
333 xfs_trans_brelse(dargs->trans, blk->bp);
334 blk->bp = NULL;
335 }
336
337 /* Check the pointer. */
338 blk->blkno = blkno;
339 if (!xchk_da_btree_ptr_ok(ds, level, blkno))
340 goto out_nobuf;
341
342 /* Read the buffer. */
343 error = xfs_da_read_buf(dargs->trans, dargs->dp, blk->blkno,
344 XFS_DABUF_MAP_HOLE_OK, &blk->bp, dargs->whichfork,
345 &xchk_da_btree_buf_ops);
346 if (!xchk_da_process_error(ds, level, &error))
347 goto out_nobuf;
348 if (blk->bp)
349 xchk_buffer_recheck(ds->sc, blk->bp);
350
351 /*
352 * We didn't find a dir btree root block, which means that
353 * there's no LEAF1/LEAFN tree (at least not where it's supposed
354 * to be), so jump out now.
355 */
356 if (ds->dargs.whichfork == XFS_DATA_FORK && level == 0 &&
357 blk->bp == NULL)
358 goto out_nobuf;
359
360 /* It's /not/ ok for attr trees not to have a da btree. */
361 if (blk->bp == NULL) {
362 xchk_da_set_corrupt(ds, level);
363 goto out_nobuf;
364 }
365
366 hdr3 = blk->bp->b_addr;
367 blk->magic = be16_to_cpu(hdr3->hdr.magic);
368 pmaxrecs = &ds->maxrecs[level];
369
370 /* We only started zeroing the header on v5 filesystems. */
371 if (xfs_has_crc(ds->sc->mp) && hdr3->hdr.pad)
372 xchk_da_set_corrupt(ds, level);
373
374 /* Check the owner. */
375 if (xfs_has_crc(ip->i_mount)) {
376 owner = be64_to_cpu(hdr3->owner);
377 if (owner != ip->i_ino)
378 xchk_da_set_corrupt(ds, level);
379 }
380
381 /* Check the siblings. */
382 error = xchk_da_btree_block_check_siblings(ds, level, &hdr3->hdr);
383 if (error)
384 goto out;
385
386 /* Interpret the buffer. */
387 switch (blk->magic) {
388 case XFS_ATTR_LEAF_MAGIC:
389 case XFS_ATTR3_LEAF_MAGIC:
390 xfs_trans_buf_set_type(dargs->trans, blk->bp,
391 XFS_BLFT_ATTR_LEAF_BUF);
392 blk->magic = XFS_ATTR_LEAF_MAGIC;
393 blk->hashval = xfs_attr_leaf_lasthash(blk->bp, pmaxrecs);
394 if (ds->tree_level != 0)
395 xchk_da_set_corrupt(ds, level);
396 break;
397 case XFS_DIR2_LEAFN_MAGIC:
398 case XFS_DIR3_LEAFN_MAGIC:
399 xfs_trans_buf_set_type(dargs->trans, blk->bp,
400 XFS_BLFT_DIR_LEAFN_BUF);
401 blk->magic = XFS_DIR2_LEAFN_MAGIC;
402 blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
403 if (ds->tree_level != 0)
404 xchk_da_set_corrupt(ds, level);
405 break;
406 case XFS_DIR2_LEAF1_MAGIC:
407 case XFS_DIR3_LEAF1_MAGIC:
408 xfs_trans_buf_set_type(dargs->trans, blk->bp,
409 XFS_BLFT_DIR_LEAF1_BUF);
410 blk->magic = XFS_DIR2_LEAF1_MAGIC;
411 blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
412 if (ds->tree_level != 0)
413 xchk_da_set_corrupt(ds, level);
414 break;
415 case XFS_DA_NODE_MAGIC:
416 case XFS_DA3_NODE_MAGIC:
417 xfs_trans_buf_set_type(dargs->trans, blk->bp,
418 XFS_BLFT_DA_NODE_BUF);
419 blk->magic = XFS_DA_NODE_MAGIC;
420 node = blk->bp->b_addr;
421 xfs_da3_node_hdr_from_disk(ip->i_mount, &nodehdr, node);
422 btree = nodehdr.btree;
423 *pmaxrecs = nodehdr.count;
424 blk->hashval = be32_to_cpu(btree[*pmaxrecs - 1].hashval);
425 if (level == 0) {
426 if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
427 xchk_da_set_corrupt(ds, level);
428 goto out_freebp;
429 }
430 ds->tree_level = nodehdr.level;
431 } else {
432 if (ds->tree_level != nodehdr.level) {
433 xchk_da_set_corrupt(ds, level);
434 goto out_freebp;
435 }
436 }
437
438 /* XXX: Check hdr3.pad32 once we know how to fix it. */
439 break;
440 default:
441 xchk_da_set_corrupt(ds, level);
442 goto out_freebp;
443 }
444
445 /*
446 * If we've been handed a block that is below the dabtree root, does
447 * its hashval match what the parent block expected to see?
448 */
449 if (level > 0) {
450 struct xfs_da_node_entry *key;
451
452 key = xchk_da_btree_node_entry(ds, level - 1);
453 if (be32_to_cpu(key->hashval) != blk->hashval) {
454 xchk_da_set_corrupt(ds, level);
455 goto out_freebp;
456 }
457 }
458
459out:
460 return error;
461out_freebp:
462 xfs_trans_brelse(dargs->trans, blk->bp);
463 blk->bp = NULL;
464out_nobuf:
465 blk->blkno = 0;
466 return error;
467}
468
469/* Visit all nodes and leaves of a da btree. */
470int
471xchk_da_btree(
472 struct xfs_scrub *sc,
473 int whichfork,
474 xchk_da_btree_rec_fn scrub_fn,
475 void *private)
476{
477 struct xchk_da_btree *ds;
478 struct xfs_mount *mp = sc->mp;
479 struct xfs_da_state_blk *blks;
480 struct xfs_da_node_entry *key;
481 xfs_dablk_t blkno;
482 int level;
483 int error;
484
485 /* Skip short format data structures; no btree to scan. */
486 if (!xfs_ifork_has_extents(xfs_ifork_ptr(sc->ip, whichfork)))
487 return 0;
488
489 /* Set up initial da state. */
490 ds = kzalloc(sizeof(struct xchk_da_btree), XCHK_GFP_FLAGS);
491 if (!ds)
492 return -ENOMEM;
493 ds->dargs.dp = sc->ip;
494 ds->dargs.whichfork = whichfork;
495 ds->dargs.trans = sc->tp;
496 ds->dargs.op_flags = XFS_DA_OP_OKNOENT;
497 ds->state = xfs_da_state_alloc(&ds->dargs);
498 ds->sc = sc;
499 ds->private = private;
500 if (whichfork == XFS_ATTR_FORK) {
501 ds->dargs.geo = mp->m_attr_geo;
502 ds->lowest = 0;
503 ds->highest = 0;
504 } else {
505 ds->dargs.geo = mp->m_dir_geo;
506 ds->lowest = ds->dargs.geo->leafblk;
507 ds->highest = ds->dargs.geo->freeblk;
508 }
509 blkno = ds->lowest;
510 level = 0;
511
512 /* Find the root of the da tree, if present. */
513 blks = ds->state->path.blk;
514 error = xchk_da_btree_block(ds, level, blkno);
515 if (error)
516 goto out_state;
517 /*
518 * We didn't find a block at ds->lowest, which means that there's
519 * no LEAF1/LEAFN tree (at least not where it's supposed to be),
520 * so jump out now.
521 */
522 if (blks[level].bp == NULL)
523 goto out_state;
524
525 blks[level].index = 0;
526 while (level >= 0 && level < XFS_DA_NODE_MAXDEPTH) {
527 /* Handle leaf block. */
528 if (blks[level].magic != XFS_DA_NODE_MAGIC) {
529 /* End of leaf, pop back towards the root. */
530 if (blks[level].index >= ds->maxrecs[level]) {
531 if (level > 0)
532 blks[level - 1].index++;
533 ds->tree_level++;
534 level--;
535 continue;
536 }
537
538 /* Dispatch record scrubbing. */
539 error = scrub_fn(ds, level);
540 if (error)
541 break;
542 if (xchk_should_terminate(sc, &error) ||
543 (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
544 break;
545
546 blks[level].index++;
547 continue;
548 }
549
550
551 /* End of node, pop back towards the root. */
552 if (blks[level].index >= ds->maxrecs[level]) {
553 if (level > 0)
554 blks[level - 1].index++;
555 ds->tree_level++;
556 level--;
557 continue;
558 }
559
560 /* Hashes in order for scrub? */
561 key = xchk_da_btree_node_entry(ds, level);
562 error = xchk_da_btree_hash(ds, level, &key->hashval);
563 if (error)
564 goto out;
565
566 /* Drill another level deeper. */
567 blkno = be32_to_cpu(key->before);
568 level++;
569 if (level >= XFS_DA_NODE_MAXDEPTH) {
570 /* Too deep! */
571 xchk_da_set_corrupt(ds, level - 1);
572 break;
573 }
574 ds->tree_level--;
575 error = xchk_da_btree_block(ds, level, blkno);
576 if (error)
577 goto out;
578 if (blks[level].bp == NULL)
579 goto out;
580
581 blks[level].index = 0;
582 }
583
584out:
585 /* Release all the buffers we're tracking. */
586 for (level = 0; level < XFS_DA_NODE_MAXDEPTH; level++) {
587 if (blks[level].bp == NULL)
588 continue;
589 xfs_trans_brelse(sc->tp, blks[level].bp);
590 blks[level].bp = NULL;
591 }
592
593out_state:
594 xfs_da_state_free(ds->state);
595 kfree(ds);
596 return error;
597}
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_log_format.h"
13#include "xfs_trans.h"
14#include "xfs_inode.h"
15#include "xfs_dir2.h"
16#include "xfs_dir2_priv.h"
17#include "xfs_attr_leaf.h"
18#include "scrub/scrub.h"
19#include "scrub/common.h"
20#include "scrub/trace.h"
21#include "scrub/dabtree.h"
22
23/* Directory/Attribute Btree */
24
25/*
26 * Check for da btree operation errors. See the section about handling
27 * operational errors in common.c.
28 */
29bool
30xchk_da_process_error(
31 struct xchk_da_btree *ds,
32 int level,
33 int *error)
34{
35 struct xfs_scrub *sc = ds->sc;
36
37 if (*error == 0)
38 return true;
39
40 switch (*error) {
41 case -EDEADLOCK:
42 case -ECHRNG:
43 /* Used to restart an op with deadlock avoidance. */
44 trace_xchk_deadlock_retry(sc->ip, sc->sm, *error);
45 break;
46 case -EFSBADCRC:
47 case -EFSCORRUPTED:
48 /* Note the badness but don't abort. */
49 sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT;
50 *error = 0;
51 fallthrough;
52 default:
53 trace_xchk_file_op_error(sc, ds->dargs.whichfork,
54 xfs_dir2_da_to_db(ds->dargs.geo,
55 ds->state->path.blk[level].blkno),
56 *error, __return_address);
57 break;
58 }
59 return false;
60}
61
62/*
63 * Check for da btree corruption. See the section about handling
64 * operational errors in common.c.
65 */
66void
67xchk_da_set_corrupt(
68 struct xchk_da_btree *ds,
69 int level)
70{
71 struct xfs_scrub *sc = ds->sc;
72
73 sc->sm->sm_flags |= XFS_SCRUB_OFLAG_CORRUPT;
74
75 trace_xchk_fblock_error(sc, ds->dargs.whichfork,
76 xfs_dir2_da_to_db(ds->dargs.geo,
77 ds->state->path.blk[level].blkno),
78 __return_address);
79}
80
81/* Flag a da btree node in need of optimization. */
82void
83xchk_da_set_preen(
84 struct xchk_da_btree *ds,
85 int level)
86{
87 struct xfs_scrub *sc = ds->sc;
88
89 sc->sm->sm_flags |= XFS_SCRUB_OFLAG_PREEN;
90 trace_xchk_fblock_preen(sc, ds->dargs.whichfork,
91 xfs_dir2_da_to_db(ds->dargs.geo,
92 ds->state->path.blk[level].blkno),
93 __return_address);
94}
95
96/* Find an entry at a certain level in a da btree. */
97static struct xfs_da_node_entry *
98xchk_da_btree_node_entry(
99 struct xchk_da_btree *ds,
100 int level)
101{
102 struct xfs_da_state_blk *blk = &ds->state->path.blk[level];
103 struct xfs_da3_icnode_hdr hdr;
104
105 ASSERT(blk->magic == XFS_DA_NODE_MAGIC);
106
107 xfs_da3_node_hdr_from_disk(ds->sc->mp, &hdr, blk->bp->b_addr);
108 return hdr.btree + blk->index;
109}
110
111/* Scrub a da btree hash (key). */
112int
113xchk_da_btree_hash(
114 struct xchk_da_btree *ds,
115 int level,
116 __be32 *hashp)
117{
118 struct xfs_da_node_entry *entry;
119 xfs_dahash_t hash;
120 xfs_dahash_t parent_hash;
121
122 /* Is this hash in order? */
123 hash = be32_to_cpu(*hashp);
124 if (hash < ds->hashes[level])
125 xchk_da_set_corrupt(ds, level);
126 ds->hashes[level] = hash;
127
128 if (level == 0)
129 return 0;
130
131 /* Is this hash no larger than the parent hash? */
132 entry = xchk_da_btree_node_entry(ds, level - 1);
133 parent_hash = be32_to_cpu(entry->hashval);
134 if (parent_hash < hash)
135 xchk_da_set_corrupt(ds, level);
136
137 return 0;
138}
139
140/*
141 * Check a da btree pointer. Returns true if it's ok to use this
142 * pointer.
143 */
144STATIC bool
145xchk_da_btree_ptr_ok(
146 struct xchk_da_btree *ds,
147 int level,
148 xfs_dablk_t blkno)
149{
150 if (blkno < ds->lowest || (ds->highest != 0 && blkno >= ds->highest)) {
151 xchk_da_set_corrupt(ds, level);
152 return false;
153 }
154
155 return true;
156}
157
158/*
159 * The da btree scrubber can handle leaf1 blocks as a degenerate
160 * form of leafn blocks. Since the regular da code doesn't handle
161 * leaf1, we must multiplex the verifiers.
162 */
163static void
164xchk_da_btree_read_verify(
165 struct xfs_buf *bp)
166{
167 struct xfs_da_blkinfo *info = bp->b_addr;
168
169 switch (be16_to_cpu(info->magic)) {
170 case XFS_DIR2_LEAF1_MAGIC:
171 case XFS_DIR3_LEAF1_MAGIC:
172 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
173 bp->b_ops->verify_read(bp);
174 return;
175 default:
176 /*
177 * xfs_da3_node_buf_ops already know how to handle
178 * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
179 */
180 bp->b_ops = &xfs_da3_node_buf_ops;
181 bp->b_ops->verify_read(bp);
182 return;
183 }
184}
185static void
186xchk_da_btree_write_verify(
187 struct xfs_buf *bp)
188{
189 struct xfs_da_blkinfo *info = bp->b_addr;
190
191 switch (be16_to_cpu(info->magic)) {
192 case XFS_DIR2_LEAF1_MAGIC:
193 case XFS_DIR3_LEAF1_MAGIC:
194 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
195 bp->b_ops->verify_write(bp);
196 return;
197 default:
198 /*
199 * xfs_da3_node_buf_ops already know how to handle
200 * DA*_NODE, ATTR*_LEAF, and DIR*_LEAFN blocks.
201 */
202 bp->b_ops = &xfs_da3_node_buf_ops;
203 bp->b_ops->verify_write(bp);
204 return;
205 }
206}
207static void *
208xchk_da_btree_verify(
209 struct xfs_buf *bp)
210{
211 struct xfs_da_blkinfo *info = bp->b_addr;
212
213 switch (be16_to_cpu(info->magic)) {
214 case XFS_DIR2_LEAF1_MAGIC:
215 case XFS_DIR3_LEAF1_MAGIC:
216 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
217 return bp->b_ops->verify_struct(bp);
218 default:
219 bp->b_ops = &xfs_da3_node_buf_ops;
220 return bp->b_ops->verify_struct(bp);
221 }
222}
223
224static const struct xfs_buf_ops xchk_da_btree_buf_ops = {
225 .name = "xchk_da_btree",
226 .verify_read = xchk_da_btree_read_verify,
227 .verify_write = xchk_da_btree_write_verify,
228 .verify_struct = xchk_da_btree_verify,
229};
230
231/* Check a block's sibling. */
232STATIC int
233xchk_da_btree_block_check_sibling(
234 struct xchk_da_btree *ds,
235 int level,
236 int direction,
237 xfs_dablk_t sibling)
238{
239 struct xfs_da_state_path *path = &ds->state->path;
240 struct xfs_da_state_path *altpath = &ds->state->altpath;
241 int retval;
242 int plevel;
243 int error;
244
245 memcpy(altpath, path, sizeof(ds->state->altpath));
246
247 /*
248 * If the pointer is null, we shouldn't be able to move the upper
249 * level pointer anywhere.
250 */
251 if (sibling == 0) {
252 error = xfs_da3_path_shift(ds->state, altpath, direction,
253 false, &retval);
254 if (error == 0 && retval == 0)
255 xchk_da_set_corrupt(ds, level);
256 error = 0;
257 goto out;
258 }
259
260 /* Move the alternate cursor one block in the direction given. */
261 error = xfs_da3_path_shift(ds->state, altpath, direction, false,
262 &retval);
263 if (!xchk_da_process_error(ds, level, &error))
264 goto out;
265 if (retval) {
266 xchk_da_set_corrupt(ds, level);
267 goto out;
268 }
269 if (altpath->blk[level].bp)
270 xchk_buffer_recheck(ds->sc, altpath->blk[level].bp);
271
272 /* Compare upper level pointer to sibling pointer. */
273 if (altpath->blk[level].blkno != sibling)
274 xchk_da_set_corrupt(ds, level);
275
276out:
277 /* Free all buffers in the altpath that aren't referenced from path. */
278 for (plevel = 0; plevel < altpath->active; plevel++) {
279 if (altpath->blk[plevel].bp == NULL ||
280 (plevel < path->active &&
281 altpath->blk[plevel].bp == path->blk[plevel].bp))
282 continue;
283
284 xfs_trans_brelse(ds->dargs.trans, altpath->blk[plevel].bp);
285 altpath->blk[plevel].bp = NULL;
286 }
287
288 return error;
289}
290
291/* Check a block's sibling pointers. */
292STATIC int
293xchk_da_btree_block_check_siblings(
294 struct xchk_da_btree *ds,
295 int level,
296 struct xfs_da_blkinfo *hdr)
297{
298 xfs_dablk_t forw;
299 xfs_dablk_t back;
300 int error = 0;
301
302 forw = be32_to_cpu(hdr->forw);
303 back = be32_to_cpu(hdr->back);
304
305 /* Top level blocks should not have sibling pointers. */
306 if (level == 0) {
307 if (forw != 0 || back != 0)
308 xchk_da_set_corrupt(ds, level);
309 return 0;
310 }
311
312 /*
313 * Check back (left) and forw (right) pointers. These functions
314 * absorb error codes for us.
315 */
316 error = xchk_da_btree_block_check_sibling(ds, level, 0, back);
317 if (error)
318 goto out;
319 error = xchk_da_btree_block_check_sibling(ds, level, 1, forw);
320
321out:
322 memset(&ds->state->altpath, 0, sizeof(ds->state->altpath));
323 return error;
324}
325
326/* Load a dir/attribute block from a btree. */
327STATIC int
328xchk_da_btree_block(
329 struct xchk_da_btree *ds,
330 int level,
331 xfs_dablk_t blkno)
332{
333 struct xfs_da_state_blk *blk;
334 struct xfs_da_intnode *node;
335 struct xfs_da_node_entry *btree;
336 struct xfs_da3_blkinfo *hdr3;
337 struct xfs_da_args *dargs = &ds->dargs;
338 struct xfs_inode *ip = ds->dargs.dp;
339 xfs_failaddr_t fa;
340 xfs_ino_t owner;
341 int *pmaxrecs;
342 struct xfs_da3_icnode_hdr nodehdr;
343 int error = 0;
344
345 blk = &ds->state->path.blk[level];
346 ds->state->path.active = level + 1;
347
348 /* Release old block. */
349 if (blk->bp) {
350 xfs_trans_brelse(dargs->trans, blk->bp);
351 blk->bp = NULL;
352 }
353
354 /* Check the pointer. */
355 blk->blkno = blkno;
356 if (!xchk_da_btree_ptr_ok(ds, level, blkno))
357 goto out_nobuf;
358
359 /* Read the buffer. */
360 error = xfs_da_read_buf(dargs->trans, dargs->dp, blk->blkno,
361 XFS_DABUF_MAP_HOLE_OK, &blk->bp, dargs->whichfork,
362 &xchk_da_btree_buf_ops);
363 if (!xchk_da_process_error(ds, level, &error))
364 goto out_nobuf;
365 if (blk->bp)
366 xchk_buffer_recheck(ds->sc, blk->bp);
367
368 /*
369 * We didn't find a dir btree root block, which means that
370 * there's no LEAF1/LEAFN tree (at least not where it's supposed
371 * to be), so jump out now.
372 */
373 if (ds->dargs.whichfork == XFS_DATA_FORK && level == 0 &&
374 blk->bp == NULL)
375 goto out_nobuf;
376
377 /* It's /not/ ok for attr trees not to have a da btree. */
378 if (blk->bp == NULL) {
379 xchk_da_set_corrupt(ds, level);
380 goto out_nobuf;
381 }
382
383 hdr3 = blk->bp->b_addr;
384 blk->magic = be16_to_cpu(hdr3->hdr.magic);
385 pmaxrecs = &ds->maxrecs[level];
386
387 /* We only started zeroing the header on v5 filesystems. */
388 if (xfs_has_crc(ds->sc->mp) && hdr3->hdr.pad)
389 xchk_da_set_corrupt(ds, level);
390
391 /* Check the owner. */
392 if (xfs_has_crc(ip->i_mount)) {
393 owner = be64_to_cpu(hdr3->owner);
394 if (owner != ip->i_ino)
395 xchk_da_set_corrupt(ds, level);
396 }
397
398 /* Check the siblings. */
399 error = xchk_da_btree_block_check_siblings(ds, level, &hdr3->hdr);
400 if (error)
401 goto out;
402
403 /* Interpret the buffer. */
404 switch (blk->magic) {
405 case XFS_ATTR_LEAF_MAGIC:
406 case XFS_ATTR3_LEAF_MAGIC:
407 xfs_trans_buf_set_type(dargs->trans, blk->bp,
408 XFS_BLFT_ATTR_LEAF_BUF);
409 blk->magic = XFS_ATTR_LEAF_MAGIC;
410 blk->hashval = xfs_attr_leaf_lasthash(blk->bp, pmaxrecs);
411 if (ds->tree_level != 0)
412 xchk_da_set_corrupt(ds, level);
413 break;
414 case XFS_DIR2_LEAFN_MAGIC:
415 case XFS_DIR3_LEAFN_MAGIC:
416 xfs_trans_buf_set_type(dargs->trans, blk->bp,
417 XFS_BLFT_DIR_LEAFN_BUF);
418 blk->magic = XFS_DIR2_LEAFN_MAGIC;
419 blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
420 if (ds->tree_level != 0)
421 xchk_da_set_corrupt(ds, level);
422 break;
423 case XFS_DIR2_LEAF1_MAGIC:
424 case XFS_DIR3_LEAF1_MAGIC:
425 xfs_trans_buf_set_type(dargs->trans, blk->bp,
426 XFS_BLFT_DIR_LEAF1_BUF);
427 blk->magic = XFS_DIR2_LEAF1_MAGIC;
428 blk->hashval = xfs_dir2_leaf_lasthash(ip, blk->bp, pmaxrecs);
429 if (ds->tree_level != 0)
430 xchk_da_set_corrupt(ds, level);
431 break;
432 case XFS_DA_NODE_MAGIC:
433 case XFS_DA3_NODE_MAGIC:
434 xfs_trans_buf_set_type(dargs->trans, blk->bp,
435 XFS_BLFT_DA_NODE_BUF);
436 blk->magic = XFS_DA_NODE_MAGIC;
437 node = blk->bp->b_addr;
438 xfs_da3_node_hdr_from_disk(ip->i_mount, &nodehdr, node);
439 btree = nodehdr.btree;
440 *pmaxrecs = nodehdr.count;
441 blk->hashval = be32_to_cpu(btree[*pmaxrecs - 1].hashval);
442 if (level == 0) {
443 if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
444 xchk_da_set_corrupt(ds, level);
445 goto out_freebp;
446 }
447 ds->tree_level = nodehdr.level;
448 } else {
449 if (ds->tree_level != nodehdr.level) {
450 xchk_da_set_corrupt(ds, level);
451 goto out_freebp;
452 }
453 }
454
455 /* XXX: Check hdr3.pad32 once we know how to fix it. */
456 break;
457 default:
458 xchk_da_set_corrupt(ds, level);
459 goto out_freebp;
460 }
461
462 fa = xfs_da3_header_check(blk->bp, dargs->owner);
463 if (fa) {
464 xchk_da_set_corrupt(ds, level);
465 goto out_freebp;
466 }
467
468 /*
469 * If we've been handed a block that is below the dabtree root, does
470 * its hashval match what the parent block expected to see?
471 */
472 if (level > 0) {
473 struct xfs_da_node_entry *key;
474
475 key = xchk_da_btree_node_entry(ds, level - 1);
476 if (be32_to_cpu(key->hashval) != blk->hashval) {
477 xchk_da_set_corrupt(ds, level);
478 goto out_freebp;
479 }
480 }
481
482out:
483 return error;
484out_freebp:
485 xfs_trans_brelse(dargs->trans, blk->bp);
486 blk->bp = NULL;
487out_nobuf:
488 blk->blkno = 0;
489 return error;
490}
491
492/* Visit all nodes and leaves of a da btree. */
493int
494xchk_da_btree(
495 struct xfs_scrub *sc,
496 int whichfork,
497 xchk_da_btree_rec_fn scrub_fn,
498 void *private)
499{
500 struct xchk_da_btree *ds;
501 struct xfs_mount *mp = sc->mp;
502 struct xfs_da_state_blk *blks;
503 struct xfs_da_node_entry *key;
504 xfs_dablk_t blkno;
505 int level;
506 int error;
507
508 /* Skip short format data structures; no btree to scan. */
509 if (!xfs_ifork_has_extents(xfs_ifork_ptr(sc->ip, whichfork)))
510 return 0;
511
512 /* Set up initial da state. */
513 ds = kzalloc(sizeof(struct xchk_da_btree), XCHK_GFP_FLAGS);
514 if (!ds)
515 return -ENOMEM;
516 ds->dargs.dp = sc->ip;
517 ds->dargs.whichfork = whichfork;
518 ds->dargs.trans = sc->tp;
519 ds->dargs.op_flags = XFS_DA_OP_OKNOENT;
520 ds->dargs.owner = sc->ip->i_ino;
521 ds->state = xfs_da_state_alloc(&ds->dargs);
522 ds->sc = sc;
523 ds->private = private;
524 if (whichfork == XFS_ATTR_FORK) {
525 ds->dargs.geo = mp->m_attr_geo;
526 ds->lowest = 0;
527 ds->highest = 0;
528 } else {
529 ds->dargs.geo = mp->m_dir_geo;
530 ds->lowest = ds->dargs.geo->leafblk;
531 ds->highest = ds->dargs.geo->freeblk;
532 }
533 blkno = ds->lowest;
534 level = 0;
535
536 /* Find the root of the da tree, if present. */
537 blks = ds->state->path.blk;
538 error = xchk_da_btree_block(ds, level, blkno);
539 if (error)
540 goto out_state;
541 /*
542 * We didn't find a block at ds->lowest, which means that there's
543 * no LEAF1/LEAFN tree (at least not where it's supposed to be),
544 * so jump out now.
545 */
546 if (blks[level].bp == NULL)
547 goto out_state;
548
549 blks[level].index = 0;
550 while (level >= 0 && level < XFS_DA_NODE_MAXDEPTH) {
551 /* Handle leaf block. */
552 if (blks[level].magic != XFS_DA_NODE_MAGIC) {
553 /* End of leaf, pop back towards the root. */
554 if (blks[level].index >= ds->maxrecs[level]) {
555 if (level > 0)
556 blks[level - 1].index++;
557 ds->tree_level++;
558 level--;
559 continue;
560 }
561
562 /* Dispatch record scrubbing. */
563 error = scrub_fn(ds, level);
564 if (error)
565 break;
566 if (xchk_should_terminate(sc, &error) ||
567 (sc->sm->sm_flags & XFS_SCRUB_OFLAG_CORRUPT))
568 break;
569
570 blks[level].index++;
571 continue;
572 }
573
574
575 /* End of node, pop back towards the root. */
576 if (blks[level].index >= ds->maxrecs[level]) {
577 if (level > 0)
578 blks[level - 1].index++;
579 ds->tree_level++;
580 level--;
581 continue;
582 }
583
584 /* Hashes in order for scrub? */
585 key = xchk_da_btree_node_entry(ds, level);
586 error = xchk_da_btree_hash(ds, level, &key->hashval);
587 if (error)
588 goto out;
589
590 /* Drill another level deeper. */
591 blkno = be32_to_cpu(key->before);
592 level++;
593 if (level >= XFS_DA_NODE_MAXDEPTH) {
594 /* Too deep! */
595 xchk_da_set_corrupt(ds, level - 1);
596 break;
597 }
598 ds->tree_level--;
599 error = xchk_da_btree_block(ds, level, blkno);
600 if (error)
601 goto out;
602 if (blks[level].bp == NULL)
603 goto out;
604
605 blks[level].index = 0;
606 }
607
608out:
609 /* Release all the buffers we're tracking. */
610 for (level = 0; level < XFS_DA_NODE_MAXDEPTH; level++) {
611 if (blks[level].bp == NULL)
612 continue;
613 xfs_trans_brelse(sc->tp, blks[level].bp);
614 blks[level].bp = NULL;
615 }
616
617out_state:
618 xfs_da_state_free(ds->state);
619 kfree(ds);
620 return error;
621}