1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 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 walks 20 * towards the right edge of the tree. Therefore, we know that we can walk up 21 * the btree cursor towards the root; if the pointer for a given level points 22 * 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 * 4 28 * / | \ 29 * 1 2 3 30 * 31 * Pretend for this example that each leaf block has 100 btree records. For 32 * the first btree record, we'll observe that bc_levels[0].ptr == 1, so we 33 * record that we saw block 1. Then we observe that bc_levels[1].ptr == 1, so 34 * 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 exit 37 * the loop. The list remains [1, 4]. 38 * 39 * For the 101st btree record, we've moved onto leaf block 2. Now 40 * bc_levels[0].ptr == 1 again, so we record that we saw block 2. We see that 41 * 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. */ 52 STATIC int 53 xagb_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. */ 74 int 75 xagb_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 already 85 * engaged in a btree walk should call this function to capture the list of 86 * blocks going from the leaf towards the root. 87 */ 88 int 89 xagb_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