fs/xfs/scrub/agb_bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Copyright (C) 2018-2023 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <[email protected]>
   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 }