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: 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: 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: 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}
622

source code of linux/fs/xfs/scrub/dabtree.c