104 lines · c
1// SPDX-License-Identifier: GPL-2.0-or-later2/*3 * Copyright (C) 2018-2023 Oracle. All Rights Reserved.4 * Author: Darrick J. Wong <djwong@kernel.org>5 */6#include "xfs.h"7#include "xfs_shared.h"8#include "xfs_bit.h"9#include "xfs_format.h"10#include "xfs_trans_resv.h"11#include "xfs_mount.h"12#include "xfs_btree.h"13#include "bitmap.h"14#include "scrub/agb_bitmap.h"15 16/*17 * Record all btree blocks seen while iterating all records of a btree.18 *19 * We know that the btree query_all function starts at the left edge and walks20 * towards the right edge of the tree. Therefore, we know that we can walk up21 * the btree cursor towards the root; if the pointer for a given level points22 * to the first record/key in that block, we haven't seen this block before;23 * and therefore we need to remember that we saw this block in the btree.24 *25 * So if our btree is:26 *27 * 428 * / | \29 * 1 2 330 *31 * Pretend for this example that each leaf block has 100 btree records. For32 * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we33 * record that we saw block 1. Then we observe that bc_levels[1].ptr == 1, so34 * we record block 4. The list is [1, 4].35 *36 * For the second btree record, we see that bc_levels[0].ptr == 2, so we exit37 * the loop. The list remains [1, 4].38 *39 * For the 101st btree record, we've moved onto leaf block 2. Now40 * bc_levels[0].ptr == 1 again, so we record that we saw block 2. We see that41 * bc_levels[1].ptr == 2, so we exit the loop. The list is now [1, 4, 2].42 *43 * For the 102nd record, bc_levels[0].ptr == 2, so we continue.44 *45 * For the 201st record, we've moved on to leaf block 3.46 * bc_levels[0].ptr == 1, so we add 3 to the list. Now it is [1, 4, 2, 3].47 *48 * For the 300th record we just exit, with the list being [1, 4, 2, 3].49 */50 51/* Mark a btree block to the agblock bitmap. */52STATIC int53xagb_bitmap_visit_btblock(54 struct xfs_btree_cur *cur,55 int level,56 void *priv)57{58 struct xagb_bitmap *bitmap = priv;59 struct xfs_buf *bp;60 xfs_fsblock_t fsbno;61 xfs_agblock_t agbno;62 63 xfs_btree_get_block(cur, level, &bp);64 if (!bp)65 return 0;66 67 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));68 agbno = XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno);69 70 return xagb_bitmap_set(bitmap, agbno, 1);71}72 73/* Mark all (per-AG) btree blocks in the agblock bitmap. */74int75xagb_bitmap_set_btblocks(76 struct xagb_bitmap *bitmap,77 struct xfs_btree_cur *cur)78{79 return xfs_btree_visit_blocks(cur, xagb_bitmap_visit_btblock,80 XFS_BTREE_VISIT_ALL, bitmap);81}82 83/*84 * Record all the buffers pointed to by the btree cursor. Callers already85 * engaged in a btree walk should call this function to capture the list of86 * blocks going from the leaf towards the root.87 */88int89xagb_bitmap_set_btcur_path(90 struct xagb_bitmap *bitmap,91 struct xfs_btree_cur *cur)92{93 int i;94 int error;95 96 for (i = 0; i < cur->bc_nlevels && cur->bc_levels[i].ptr == 1; i++) {97 error = xagb_bitmap_visit_btblock(cur, i, bitmap);98 if (error)99 return error;100 }101 102 return 0;103}104