Dave Chinner | 0b61f8a | 2018-06-05 19:42:14 -0700 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0+ |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 2 | /* |
| 3 | * Copyright (C) 2016 Oracle. All Rights Reserved. |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 4 | * Author: Darrick J. Wong <darrick.wong@oracle.com> |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 5 | */ |
| 6 | #include "xfs.h" |
| 7 | #include "xfs_fs.h" |
| 8 | #include "xfs_shared.h" |
| 9 | #include "xfs_format.h" |
| 10 | #include "xfs_log_format.h" |
| 11 | #include "xfs_trans_resv.h" |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 12 | #include "xfs_mount.h" |
| 13 | #include "xfs_btree.h" |
Darrick J. Wong | 56e9816 | 2020-03-11 11:09:06 -0700 | [diff] [blame] | 14 | #include "xfs_btree_staging.h" |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 15 | #include "xfs_refcount_btree.h" |
Darrick J. Wong | 9a50ee4 | 2022-10-10 09:06:24 -0700 | [diff] [blame] | 16 | #include "xfs_refcount.h" |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 17 | #include "xfs_alloc.h" |
| 18 | #include "xfs_error.h" |
Christoph Hellwig | 7f47734 | 2024-02-22 12:39:47 -0800 | [diff] [blame] | 19 | #include "xfs_health.h" |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 20 | #include "xfs_trace.h" |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 21 | #include "xfs_trans.h" |
| 22 | #include "xfs_bit.h" |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 23 | #include "xfs_rmap.h" |
Dave Chinner | 9bbafc71 | 2021-06-02 10:48:24 +1000 | [diff] [blame] | 24 | #include "xfs_ag.h" |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 25 | |
Darrick J. Wong | e7720afa | 2021-09-27 14:26:19 -0700 | [diff] [blame] | 26 | static struct kmem_cache *xfs_refcountbt_cur_cache; |
Darrick J. Wong | 9fa47bd | 2021-09-23 12:21:37 -0700 | [diff] [blame] | 27 | |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 28 | static struct xfs_btree_cur * |
| 29 | xfs_refcountbt_dup_cursor( |
| 30 | struct xfs_btree_cur *cur) |
| 31 | { |
| 32 | return xfs_refcountbt_init_cursor(cur->bc_mp, cur->bc_tp, |
Dave Chinner | a81a062 | 2021-06-02 10:48:24 +1000 | [diff] [blame] | 33 | cur->bc_ag.agbp, cur->bc_ag.pag); |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 34 | } |
| 35 | |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 36 | STATIC void |
| 37 | xfs_refcountbt_set_root( |
Darrick J. Wong | b5a6e5f | 2021-08-12 09:49:03 -0700 | [diff] [blame] | 38 | struct xfs_btree_cur *cur, |
| 39 | const union xfs_btree_ptr *ptr, |
| 40 | int inc) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 41 | { |
Dave Chinner | 576af73 | 2020-03-10 17:51:15 -0700 | [diff] [blame] | 42 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
Christoph Hellwig | 9798f61 | 2020-03-10 08:57:29 -0700 | [diff] [blame] | 43 | struct xfs_agf *agf = agbp->b_addr; |
Gao Xiang | 92a0054 | 2020-07-13 09:13:00 -0700 | [diff] [blame] | 44 | struct xfs_perag *pag = agbp->b_pag; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 45 | |
| 46 | ASSERT(ptr->s != 0); |
| 47 | |
| 48 | agf->agf_refcount_root = ptr->s; |
| 49 | be32_add_cpu(&agf->agf_refcount_level, inc); |
| 50 | pag->pagf_refcount_level += inc; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 51 | |
| 52 | xfs_alloc_log_agf(cur->bc_tp, agbp, |
| 53 | XFS_AGF_REFCOUNT_ROOT | XFS_AGF_REFCOUNT_LEVEL); |
| 54 | } |
| 55 | |
| 56 | STATIC int |
| 57 | xfs_refcountbt_alloc_block( |
Darrick J. Wong | deb06b9 | 2021-08-12 09:53:27 -0700 | [diff] [blame] | 58 | struct xfs_btree_cur *cur, |
| 59 | const union xfs_btree_ptr *start, |
| 60 | union xfs_btree_ptr *new, |
| 61 | int *stat) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 62 | { |
Dave Chinner | 576af73 | 2020-03-10 17:51:15 -0700 | [diff] [blame] | 63 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
Christoph Hellwig | 9798f61 | 2020-03-10 08:57:29 -0700 | [diff] [blame] | 64 | struct xfs_agf *agf = agbp->b_addr; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 65 | struct xfs_alloc_arg args; /* block allocation args */ |
| 66 | int error; /* error return value */ |
| 67 | |
| 68 | memset(&args, 0, sizeof(args)); |
| 69 | args.tp = cur->bc_tp; |
| 70 | args.mp = cur->bc_mp; |
Dave Chinner | 74c36a8 | 2023-02-13 09:14:53 +1100 | [diff] [blame] | 71 | args.pag = cur->bc_ag.pag; |
Darrick J. Wong | 7280fed | 2018-12-12 08:46:23 -0800 | [diff] [blame] | 72 | args.oinfo = XFS_RMAP_OINFO_REFC; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 73 | args.minlen = args.maxlen = args.prod = 1; |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 74 | args.resv = XFS_AG_RESV_METADATA; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 75 | |
Dave Chinner | db4710f | 2023-02-13 09:14:54 +1100 | [diff] [blame] | 76 | error = xfs_alloc_vextent_near_bno(&args, |
| 77 | XFS_AGB_TO_FSB(args.mp, args.pag->pag_agno, |
| 78 | xfs_refc_block(args.mp))); |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 79 | if (error) |
| 80 | goto out_error; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 81 | if (args.fsbno == NULLFSBLOCK) { |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 82 | *stat = 0; |
| 83 | return 0; |
| 84 | } |
Dave Chinner | 50f02fe | 2021-06-02 10:48:24 +1000 | [diff] [blame] | 85 | ASSERT(args.agno == cur->bc_ag.pag->pag_agno); |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 86 | ASSERT(args.len == 1); |
| 87 | |
| 88 | new->s = cpu_to_be32(args.agbno); |
| 89 | be32_add_cpu(&agf->agf_refcount_blocks, 1); |
| 90 | xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS); |
| 91 | |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 92 | *stat = 1; |
| 93 | return 0; |
| 94 | |
| 95 | out_error: |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 96 | return error; |
| 97 | } |
| 98 | |
| 99 | STATIC int |
| 100 | xfs_refcountbt_free_block( |
| 101 | struct xfs_btree_cur *cur, |
| 102 | struct xfs_buf *bp) |
| 103 | { |
| 104 | struct xfs_mount *mp = cur->bc_mp; |
Dave Chinner | 576af73 | 2020-03-10 17:51:15 -0700 | [diff] [blame] | 105 | struct xfs_buf *agbp = cur->bc_ag.agbp; |
Christoph Hellwig | 9798f61 | 2020-03-10 08:57:29 -0700 | [diff] [blame] | 106 | struct xfs_agf *agf = agbp->b_addr; |
Dave Chinner | 04fcad8 | 2021-08-18 18:46:57 -0700 | [diff] [blame] | 107 | xfs_fsblock_t fsbno = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp)); |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 108 | |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 109 | be32_add_cpu(&agf->agf_refcount_blocks, -1); |
| 110 | xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS); |
Dave Chinner | b742d7b4 | 2023-06-28 11:04:32 -0700 | [diff] [blame] | 111 | return xfs_free_extent_later(cur->bc_tp, fsbno, 1, |
Darrick J. Wong | 980faec | 2024-07-02 11:22:51 -0700 | [diff] [blame] | 112 | &XFS_RMAP_OINFO_REFC, XFS_AG_RESV_METADATA, 0); |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 113 | } |
| 114 | |
| 115 | STATIC int |
| 116 | xfs_refcountbt_get_minrecs( |
| 117 | struct xfs_btree_cur *cur, |
| 118 | int level) |
| 119 | { |
| 120 | return cur->bc_mp->m_refc_mnr[level != 0]; |
| 121 | } |
| 122 | |
| 123 | STATIC int |
| 124 | xfs_refcountbt_get_maxrecs( |
| 125 | struct xfs_btree_cur *cur, |
| 126 | int level) |
| 127 | { |
| 128 | return cur->bc_mp->m_refc_mxr[level != 0]; |
| 129 | } |
| 130 | |
| 131 | STATIC void |
| 132 | xfs_refcountbt_init_key_from_rec( |
Darrick J. Wong | 23825cd | 2021-08-10 17:02:16 -0700 | [diff] [blame] | 133 | union xfs_btree_key *key, |
| 134 | const union xfs_btree_rec *rec) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 135 | { |
| 136 | key->refc.rc_startblock = rec->refc.rc_startblock; |
| 137 | } |
| 138 | |
| 139 | STATIC void |
| 140 | xfs_refcountbt_init_high_key_from_rec( |
Darrick J. Wong | 23825cd | 2021-08-10 17:02:16 -0700 | [diff] [blame] | 141 | union xfs_btree_key *key, |
| 142 | const union xfs_btree_rec *rec) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 143 | { |
Darrick J. Wong | 23825cd | 2021-08-10 17:02:16 -0700 | [diff] [blame] | 144 | __u32 x; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 145 | |
| 146 | x = be32_to_cpu(rec->refc.rc_startblock); |
| 147 | x += be32_to_cpu(rec->refc.rc_blockcount) - 1; |
| 148 | key->refc.rc_startblock = cpu_to_be32(x); |
| 149 | } |
| 150 | |
| 151 | STATIC void |
| 152 | xfs_refcountbt_init_rec_from_cur( |
| 153 | struct xfs_btree_cur *cur, |
| 154 | union xfs_btree_rec *rec) |
| 155 | { |
Darrick J. Wong | 9a50ee4 | 2022-10-10 09:06:24 -0700 | [diff] [blame] | 156 | const struct xfs_refcount_irec *irec = &cur->bc_rec.rc; |
| 157 | uint32_t start; |
| 158 | |
| 159 | start = xfs_refcount_encode_startblock(irec->rc_startblock, |
| 160 | irec->rc_domain); |
| 161 | rec->refc.rc_startblock = cpu_to_be32(start); |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 162 | rec->refc.rc_blockcount = cpu_to_be32(cur->bc_rec.rc.rc_blockcount); |
| 163 | rec->refc.rc_refcount = cpu_to_be32(cur->bc_rec.rc.rc_refcount); |
| 164 | } |
| 165 | |
| 166 | STATIC void |
| 167 | xfs_refcountbt_init_ptr_from_cur( |
| 168 | struct xfs_btree_cur *cur, |
| 169 | union xfs_btree_ptr *ptr) |
| 170 | { |
Dave Chinner | 576af73 | 2020-03-10 17:51:15 -0700 | [diff] [blame] | 171 | struct xfs_agf *agf = cur->bc_ag.agbp->b_addr; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 172 | |
Dave Chinner | 50f02fe | 2021-06-02 10:48:24 +1000 | [diff] [blame] | 173 | ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno)); |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 174 | |
| 175 | ptr->s = agf->agf_refcount_root; |
| 176 | } |
| 177 | |
Darrick J. Wong | c8ce540 | 2017-06-16 11:00:05 -0700 | [diff] [blame] | 178 | STATIC int64_t |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 179 | xfs_refcountbt_key_diff( |
Darrick J. Wong | d29d557 | 2021-08-10 17:02:15 -0700 | [diff] [blame] | 180 | struct xfs_btree_cur *cur, |
| 181 | const union xfs_btree_key *key) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 182 | { |
Darrick J. Wong | d29d557 | 2021-08-10 17:02:15 -0700 | [diff] [blame] | 183 | const struct xfs_refcount_key *kp = &key->refc; |
Darrick J. Wong | 9a50ee4 | 2022-10-10 09:06:24 -0700 | [diff] [blame] | 184 | const struct xfs_refcount_irec *irec = &cur->bc_rec.rc; |
| 185 | uint32_t start; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 186 | |
Darrick J. Wong | 9a50ee4 | 2022-10-10 09:06:24 -0700 | [diff] [blame] | 187 | start = xfs_refcount_encode_startblock(irec->rc_startblock, |
| 188 | irec->rc_domain); |
| 189 | return (int64_t)be32_to_cpu(kp->rc_startblock) - start; |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 190 | } |
| 191 | |
Darrick J. Wong | c8ce540 | 2017-06-16 11:00:05 -0700 | [diff] [blame] | 192 | STATIC int64_t |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 193 | xfs_refcountbt_diff_two_keys( |
Darrick J. Wong | d29d557 | 2021-08-10 17:02:15 -0700 | [diff] [blame] | 194 | struct xfs_btree_cur *cur, |
| 195 | const union xfs_btree_key *k1, |
Darrick J. Wong | 4a200a0 | 2023-04-11 19:00:11 -0700 | [diff] [blame] | 196 | const union xfs_btree_key *k2, |
| 197 | const union xfs_btree_key *mask) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 198 | { |
Darrick J. Wong | 4a200a0 | 2023-04-11 19:00:11 -0700 | [diff] [blame] | 199 | ASSERT(!mask || mask->refc.rc_startblock); |
| 200 | |
Darrick J. Wong | c8ce540 | 2017-06-16 11:00:05 -0700 | [diff] [blame] | 201 | return (int64_t)be32_to_cpu(k1->refc.rc_startblock) - |
Darrick J. Wong | 4a200a0 | 2023-04-11 19:00:11 -0700 | [diff] [blame] | 202 | be32_to_cpu(k2->refc.rc_startblock); |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 203 | } |
| 204 | |
Darrick J. Wong | a6a781a | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 205 | STATIC xfs_failaddr_t |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 206 | xfs_refcountbt_verify( |
| 207 | struct xfs_buf *bp) |
| 208 | { |
Christoph Hellwig | dbd329f1 | 2019-06-28 19:27:29 -0700 | [diff] [blame] | 209 | struct xfs_mount *mp = bp->b_mount; |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 210 | struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); |
| 211 | struct xfs_perag *pag = bp->b_pag; |
Darrick J. Wong | a6a781a | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 212 | xfs_failaddr_t fa; |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 213 | unsigned int level; |
| 214 | |
Brian Foster | 39708c2 | 2019-02-07 10:45:48 -0800 | [diff] [blame] | 215 | if (!xfs_verify_magic(bp, block->bb_magic)) |
Darrick J. Wong | a6a781a | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 216 | return __this_address; |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 217 | |
Dave Chinner | 38c26bf | 2021-08-18 18:46:37 -0700 | [diff] [blame] | 218 | if (!xfs_has_reflink(mp)) |
Darrick J. Wong | a6a781a | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 219 | return __this_address; |
Christoph Hellwig | 5ef819c | 2024-02-22 12:40:58 -0800 | [diff] [blame] | 220 | fa = xfs_btree_agblock_v5hdr_verify(bp); |
Darrick J. Wong | a6a781a | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 221 | if (fa) |
| 222 | return fa; |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 223 | |
| 224 | level = be16_to_cpu(block->bb_level); |
Dave Chinner | 7ac2ff8 | 2023-02-13 09:14:52 +1100 | [diff] [blame] | 225 | if (pag && xfs_perag_initialised_agf(pag)) { |
Darrick J. Wong | 9099cd38 | 2023-12-15 10:03:33 -0800 | [diff] [blame] | 226 | unsigned int maxlevel = pag->pagf_refcount_level; |
| 227 | |
| 228 | #ifdef CONFIG_XFS_ONLINE_REPAIR |
| 229 | /* |
| 230 | * Online repair could be rewriting the refcount btree, so |
| 231 | * we'll validate against the larger of either tree while this |
| 232 | * is going on. |
| 233 | */ |
| 234 | maxlevel = max_t(unsigned int, maxlevel, |
| 235 | pag->pagf_repair_refcount_level); |
| 236 | #endif |
| 237 | if (level >= maxlevel) |
Darrick J. Wong | a6a781a | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 238 | return __this_address; |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 239 | } else if (level >= mp->m_refc_maxlevels) |
Darrick J. Wong | a6a781a | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 240 | return __this_address; |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 241 | |
Christoph Hellwig | 5ef819c | 2024-02-22 12:40:58 -0800 | [diff] [blame] | 242 | return xfs_btree_agblock_verify(bp, mp->m_refc_mxr[level != 0]); |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 243 | } |
| 244 | |
| 245 | STATIC void |
| 246 | xfs_refcountbt_read_verify( |
| 247 | struct xfs_buf *bp) |
| 248 | { |
Darrick J. Wong | bc1a09b | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 249 | xfs_failaddr_t fa; |
| 250 | |
Christoph Hellwig | 5ef819c | 2024-02-22 12:40:58 -0800 | [diff] [blame] | 251 | if (!xfs_btree_agblock_verify_crc(bp)) |
Darrick J. Wong | bc1a09b | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 252 | xfs_verifier_error(bp, -EFSBADCRC, __this_address); |
| 253 | else { |
| 254 | fa = xfs_refcountbt_verify(bp); |
| 255 | if (fa) |
| 256 | xfs_verifier_error(bp, -EFSCORRUPTED, fa); |
| 257 | } |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 258 | |
Darrick J. Wong | 31ca03c | 2018-01-08 10:51:02 -0800 | [diff] [blame] | 259 | if (bp->b_error) |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 260 | trace_xfs_btree_corrupt(bp, _RET_IP_); |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 261 | } |
| 262 | |
| 263 | STATIC void |
| 264 | xfs_refcountbt_write_verify( |
| 265 | struct xfs_buf *bp) |
| 266 | { |
Darrick J. Wong | bc1a09b | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 267 | xfs_failaddr_t fa; |
| 268 | |
| 269 | fa = xfs_refcountbt_verify(bp); |
| 270 | if (fa) { |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 271 | trace_xfs_btree_corrupt(bp, _RET_IP_); |
Darrick J. Wong | bc1a09b | 2018-01-08 10:51:03 -0800 | [diff] [blame] | 272 | xfs_verifier_error(bp, -EFSCORRUPTED, fa); |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 273 | return; |
| 274 | } |
Christoph Hellwig | 5ef819c | 2024-02-22 12:40:58 -0800 | [diff] [blame] | 275 | xfs_btree_agblock_calc_crc(bp); |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 276 | |
| 277 | } |
| 278 | |
| 279 | const struct xfs_buf_ops xfs_refcountbt_buf_ops = { |
| 280 | .name = "xfs_refcountbt", |
Brian Foster | 39708c2 | 2019-02-07 10:45:48 -0800 | [diff] [blame] | 281 | .magic = { 0, cpu_to_be32(XFS_REFC_CRC_MAGIC) }, |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 282 | .verify_read = xfs_refcountbt_read_verify, |
| 283 | .verify_write = xfs_refcountbt_write_verify, |
Darrick J. Wong | b557259 | 2018-01-08 10:51:08 -0800 | [diff] [blame] | 284 | .verify_struct = xfs_refcountbt_verify, |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 285 | }; |
| 286 | |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 287 | STATIC int |
| 288 | xfs_refcountbt_keys_inorder( |
Darrick J. Wong | 8e38dc8 | 2021-08-10 17:02:17 -0700 | [diff] [blame] | 289 | struct xfs_btree_cur *cur, |
| 290 | const union xfs_btree_key *k1, |
| 291 | const union xfs_btree_key *k2) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 292 | { |
| 293 | return be32_to_cpu(k1->refc.rc_startblock) < |
| 294 | be32_to_cpu(k2->refc.rc_startblock); |
| 295 | } |
| 296 | |
| 297 | STATIC int |
| 298 | xfs_refcountbt_recs_inorder( |
Darrick J. Wong | 8e38dc8 | 2021-08-10 17:02:17 -0700 | [diff] [blame] | 299 | struct xfs_btree_cur *cur, |
| 300 | const union xfs_btree_rec *r1, |
| 301 | const union xfs_btree_rec *r2) |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 302 | { |
| 303 | return be32_to_cpu(r1->refc.rc_startblock) + |
| 304 | be32_to_cpu(r1->refc.rc_blockcount) <= |
| 305 | be32_to_cpu(r2->refc.rc_startblock); |
| 306 | } |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 307 | |
Darrick J. Wong | 6abc7ae | 2023-04-11 19:00:10 -0700 | [diff] [blame] | 308 | STATIC enum xbtree_key_contig |
| 309 | xfs_refcountbt_keys_contiguous( |
| 310 | struct xfs_btree_cur *cur, |
| 311 | const union xfs_btree_key *key1, |
Darrick J. Wong | 4a200a0 | 2023-04-11 19:00:11 -0700 | [diff] [blame] | 312 | const union xfs_btree_key *key2, |
| 313 | const union xfs_btree_key *mask) |
Darrick J. Wong | 6abc7ae | 2023-04-11 19:00:10 -0700 | [diff] [blame] | 314 | { |
Darrick J. Wong | 4a200a0 | 2023-04-11 19:00:11 -0700 | [diff] [blame] | 315 | ASSERT(!mask || mask->refc.rc_startblock); |
| 316 | |
Darrick J. Wong | 6abc7ae | 2023-04-11 19:00:10 -0700 | [diff] [blame] | 317 | return xbtree_key_contig(be32_to_cpu(key1->refc.rc_startblock), |
| 318 | be32_to_cpu(key2->refc.rc_startblock)); |
| 319 | } |
| 320 | |
Darrick J. Wong | d8d6df4 | 2024-02-22 12:35:15 -0800 | [diff] [blame] | 321 | const struct xfs_btree_ops xfs_refcountbt_ops = { |
Christoph Hellwig | 77953b9 | 2024-02-22 12:39:47 -0800 | [diff] [blame] | 322 | .name = "refcount", |
Christoph Hellwig | 4f0cd5a | 2024-02-22 12:36:17 -0800 | [diff] [blame] | 323 | .type = XFS_BTREE_TYPE_AG, |
| 324 | |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 325 | .rec_len = sizeof(struct xfs_refcount_rec), |
| 326 | .key_len = sizeof(struct xfs_refcount_key), |
Darrick J. Wong | 1a9d262 | 2024-02-22 12:35:36 -0800 | [diff] [blame] | 327 | .ptr_len = XFS_BTREE_SHORT_PTR_LEN, |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 328 | |
Darrick J. Wong | 90cfae8 | 2024-02-22 12:35:20 -0800 | [diff] [blame] | 329 | .lru_refs = XFS_REFC_BTREE_REF, |
Christoph Hellwig | 07b7f2e | 2024-02-22 12:35:21 -0800 | [diff] [blame] | 330 | .statoff = XFS_STATS_CALC_INDEX(xs_refcbt_2), |
Christoph Hellwig | 7f47734 | 2024-02-22 12:39:47 -0800 | [diff] [blame] | 331 | .sick_mask = XFS_SICK_AG_REFCNTBT, |
Darrick J. Wong | 90cfae8 | 2024-02-22 12:35:20 -0800 | [diff] [blame] | 332 | |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 333 | .dup_cursor = xfs_refcountbt_dup_cursor, |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 334 | .set_root = xfs_refcountbt_set_root, |
| 335 | .alloc_block = xfs_refcountbt_alloc_block, |
| 336 | .free_block = xfs_refcountbt_free_block, |
| 337 | .get_minrecs = xfs_refcountbt_get_minrecs, |
| 338 | .get_maxrecs = xfs_refcountbt_get_maxrecs, |
| 339 | .init_key_from_rec = xfs_refcountbt_init_key_from_rec, |
| 340 | .init_high_key_from_rec = xfs_refcountbt_init_high_key_from_rec, |
| 341 | .init_rec_from_cur = xfs_refcountbt_init_rec_from_cur, |
| 342 | .init_ptr_from_cur = xfs_refcountbt_init_ptr_from_cur, |
| 343 | .key_diff = xfs_refcountbt_key_diff, |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 344 | .buf_ops = &xfs_refcountbt_buf_ops, |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 345 | .diff_two_keys = xfs_refcountbt_diff_two_keys, |
Darrick J. Wong | bdf2863 | 2016-10-03 09:11:19 -0700 | [diff] [blame] | 346 | .keys_inorder = xfs_refcountbt_keys_inorder, |
| 347 | .recs_inorder = xfs_refcountbt_recs_inorder, |
Darrick J. Wong | 6abc7ae | 2023-04-11 19:00:10 -0700 | [diff] [blame] | 348 | .keys_contiguous = xfs_refcountbt_keys_contiguous, |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 349 | }; |
| 350 | |
| 351 | /* |
Christoph Hellwig | 4f2dc69 | 2024-02-22 12:39:39 -0800 | [diff] [blame] | 352 | * Create a new refcount btree cursor. |
| 353 | * |
| 354 | * For staging cursors tp and agbp are NULL. |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 355 | */ |
Christoph Hellwig | 4f2dc69 | 2024-02-22 12:39:39 -0800 | [diff] [blame] | 356 | struct xfs_btree_cur * |
| 357 | xfs_refcountbt_init_cursor( |
Darrick J. Wong | 56e9816 | 2020-03-11 11:09:06 -0700 | [diff] [blame] | 358 | struct xfs_mount *mp, |
| 359 | struct xfs_trans *tp, |
Christoph Hellwig | 4f2dc69 | 2024-02-22 12:39:39 -0800 | [diff] [blame] | 360 | struct xfs_buf *agbp, |
Dave Chinner | be9fb17 | 2021-06-02 10:48:24 +1000 | [diff] [blame] | 361 | struct xfs_perag *pag) |
Darrick J. Wong | 56e9816 | 2020-03-11 11:09:06 -0700 | [diff] [blame] | 362 | { |
| 363 | struct xfs_btree_cur *cur; |
| 364 | |
Dave Chinner | a81a062 | 2021-06-02 10:48:24 +1000 | [diff] [blame] | 365 | ASSERT(pag->pag_agno < mp->m_sb.sb_agcount); |
Darrick J. Wong | 56e9816 | 2020-03-11 11:09:06 -0700 | [diff] [blame] | 366 | |
Christoph Hellwig | ec793e6 | 2024-02-22 12:40:51 -0800 | [diff] [blame] | 367 | cur = xfs_btree_alloc_cursor(mp, tp, &xfs_refcountbt_ops, |
| 368 | mp->m_refc_maxlevels, xfs_refcountbt_cur_cache); |
Darrick J. Wong | 9b2e5a2 | 2023-04-11 18:59:55 -0700 | [diff] [blame] | 369 | cur->bc_ag.pag = xfs_perag_hold(pag); |
Christoph Hellwig | 88ee2f4 | 2024-02-22 12:37:03 -0800 | [diff] [blame] | 370 | cur->bc_refc.nr_ops = 0; |
| 371 | cur->bc_refc.shape_changes = 0; |
Dave Chinner | 576af73 | 2020-03-10 17:51:15 -0700 | [diff] [blame] | 372 | cur->bc_ag.agbp = agbp; |
Christoph Hellwig | 4f2dc69 | 2024-02-22 12:39:39 -0800 | [diff] [blame] | 373 | if (agbp) { |
| 374 | struct xfs_agf *agf = agbp->b_addr; |
| 375 | |
| 376 | cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level); |
| 377 | } |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 378 | return cur; |
| 379 | } |
| 380 | |
Darrick J. Wong | 56e9816 | 2020-03-11 11:09:06 -0700 | [diff] [blame] | 381 | /* |
| 382 | * Swap in the new btree root. Once we pass this point the newly rebuilt btree |
| 383 | * is in place and we have to kill off all the old btree blocks. |
| 384 | */ |
| 385 | void |
| 386 | xfs_refcountbt_commit_staged_btree( |
| 387 | struct xfs_btree_cur *cur, |
| 388 | struct xfs_trans *tp, |
| 389 | struct xfs_buf *agbp) |
| 390 | { |
| 391 | struct xfs_agf *agf = agbp->b_addr; |
| 392 | struct xbtree_afakeroot *afake = cur->bc_ag.afake; |
| 393 | |
| 394 | ASSERT(cur->bc_flags & XFS_BTREE_STAGING); |
| 395 | |
| 396 | agf->agf_refcount_root = cpu_to_be32(afake->af_root); |
| 397 | agf->agf_refcount_level = cpu_to_be32(afake->af_levels); |
| 398 | agf->agf_refcount_blocks = cpu_to_be32(afake->af_blocks); |
| 399 | xfs_alloc_log_agf(tp, agbp, XFS_AGF_REFCOUNT_BLOCKS | |
| 400 | XFS_AGF_REFCOUNT_ROOT | |
| 401 | XFS_AGF_REFCOUNT_LEVEL); |
Christoph Hellwig | 2b9e7f2 | 2024-02-22 12:37:35 -0800 | [diff] [blame] | 402 | xfs_btree_commit_afakeroot(cur, tp, agbp); |
Darrick J. Wong | 56e9816 | 2020-03-11 11:09:06 -0700 | [diff] [blame] | 403 | } |
| 404 | |
Darrick J. Wong | 0ed5f73 | 2021-09-23 10:32:06 -0700 | [diff] [blame] | 405 | /* Calculate number of records in a refcount btree block. */ |
| 406 | static inline unsigned int |
| 407 | xfs_refcountbt_block_maxrecs( |
| 408 | unsigned int blocklen, |
| 409 | bool leaf) |
| 410 | { |
| 411 | if (leaf) |
| 412 | return blocklen / sizeof(struct xfs_refcount_rec); |
| 413 | return blocklen / (sizeof(struct xfs_refcount_key) + |
| 414 | sizeof(xfs_refcount_ptr_t)); |
| 415 | } |
| 416 | |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 417 | /* |
| 418 | * Calculate the number of records in a refcount btree block. |
| 419 | */ |
Darrick J. Wong | 411a712 | 2024-08-30 15:37:21 -0700 | [diff] [blame] | 420 | unsigned int |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 421 | xfs_refcountbt_maxrecs( |
Darrick J. Wong | 411a712 | 2024-08-30 15:37:21 -0700 | [diff] [blame] | 422 | struct xfs_mount *mp, |
| 423 | unsigned int blocklen, |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 424 | bool leaf) |
| 425 | { |
| 426 | blocklen -= XFS_REFCOUNT_BLOCK_LEN; |
Darrick J. Wong | 0ed5f73 | 2021-09-23 10:32:06 -0700 | [diff] [blame] | 427 | return xfs_refcountbt_block_maxrecs(blocklen, leaf); |
| 428 | } |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 429 | |
Darrick J. Wong | 0ed5f73 | 2021-09-23 10:32:06 -0700 | [diff] [blame] | 430 | /* Compute the max possible height of the maximally sized refcount btree. */ |
| 431 | unsigned int |
| 432 | xfs_refcountbt_maxlevels_ondisk(void) |
| 433 | { |
| 434 | unsigned int minrecs[2]; |
| 435 | unsigned int blocklen; |
| 436 | |
| 437 | blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN; |
| 438 | |
| 439 | minrecs[0] = xfs_refcountbt_block_maxrecs(blocklen, true) / 2; |
| 440 | minrecs[1] = xfs_refcountbt_block_maxrecs(blocklen, false) / 2; |
| 441 | |
| 442 | return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_CRC_AG_BLOCKS); |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 443 | } |
| 444 | |
| 445 | /* Compute the maximum height of a refcount btree. */ |
| 446 | void |
| 447 | xfs_refcountbt_compute_maxlevels( |
| 448 | struct xfs_mount *mp) |
| 449 | { |
Darrick J. Wong | 0ed5f73 | 2021-09-23 10:32:06 -0700 | [diff] [blame] | 450 | if (!xfs_has_reflink(mp)) { |
| 451 | mp->m_refc_maxlevels = 0; |
| 452 | return; |
| 453 | } |
| 454 | |
Eric Sandeen | a1f6941 | 2018-04-06 10:09:42 -0700 | [diff] [blame] | 455 | mp->m_refc_maxlevels = xfs_btree_compute_maxlevels( |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 456 | mp->m_refc_mnr, mp->m_sb.sb_agblocks); |
Darrick J. Wong | 0ed5f73 | 2021-09-23 10:32:06 -0700 | [diff] [blame] | 457 | ASSERT(mp->m_refc_maxlevels <= xfs_refcountbt_maxlevels_ondisk()); |
Darrick J. Wong | 1946b91 | 2016-10-03 09:11:18 -0700 | [diff] [blame] | 458 | } |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 459 | |
| 460 | /* Calculate the refcount btree size for some records. */ |
| 461 | xfs_extlen_t |
| 462 | xfs_refcountbt_calc_size( |
| 463 | struct xfs_mount *mp, |
| 464 | unsigned long long len) |
| 465 | { |
Eric Sandeen | a1f6941 | 2018-04-06 10:09:42 -0700 | [diff] [blame] | 466 | return xfs_btree_calc_size(mp->m_refc_mnr, len); |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 467 | } |
| 468 | |
| 469 | /* |
| 470 | * Calculate the maximum refcount btree size. |
| 471 | */ |
| 472 | xfs_extlen_t |
| 473 | xfs_refcountbt_max_size( |
Darrick J. Wong | 20e73b0 | 2017-01-03 18:39:33 -0800 | [diff] [blame] | 474 | struct xfs_mount *mp, |
| 475 | xfs_agblock_t agblocks) |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 476 | { |
| 477 | /* Bail out if we're uninitialized, which can happen in mkfs. */ |
| 478 | if (mp->m_refc_mxr[0] == 0) |
| 479 | return 0; |
| 480 | |
Darrick J. Wong | 20e73b0 | 2017-01-03 18:39:33 -0800 | [diff] [blame] | 481 | return xfs_refcountbt_calc_size(mp, agblocks); |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 482 | } |
| 483 | |
| 484 | /* |
| 485 | * Figure out how many blocks to reserve and how many are used by this btree. |
| 486 | */ |
| 487 | int |
| 488 | xfs_refcountbt_calc_reserves( |
| 489 | struct xfs_mount *mp, |
Darrick J. Wong | ebcbef3 | 2018-07-29 22:37:08 -0700 | [diff] [blame] | 490 | struct xfs_trans *tp, |
Dave Chinner | 3093312 | 2021-06-02 10:48:24 +1000 | [diff] [blame] | 491 | struct xfs_perag *pag, |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 492 | xfs_extlen_t *ask, |
| 493 | xfs_extlen_t *used) |
| 494 | { |
| 495 | struct xfs_buf *agbp; |
| 496 | struct xfs_agf *agf; |
Darrick J. Wong | 20e73b0 | 2017-01-03 18:39:33 -0800 | [diff] [blame] | 497 | xfs_agblock_t agblocks; |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 498 | xfs_extlen_t tree_len; |
| 499 | int error; |
| 500 | |
Dave Chinner | 38c26bf | 2021-08-18 18:46:37 -0700 | [diff] [blame] | 501 | if (!xfs_has_reflink(mp)) |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 502 | return 0; |
| 503 | |
Dave Chinner | 08d3e84 | 2022-07-07 19:07:40 +1000 | [diff] [blame] | 504 | error = xfs_alloc_read_agf(pag, tp, 0, &agbp); |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 505 | if (error) |
| 506 | return error; |
| 507 | |
Christoph Hellwig | 9798f61 | 2020-03-10 08:57:29 -0700 | [diff] [blame] | 508 | agf = agbp->b_addr; |
Darrick J. Wong | 20e73b0 | 2017-01-03 18:39:33 -0800 | [diff] [blame] | 509 | agblocks = be32_to_cpu(agf->agf_length); |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 510 | tree_len = be32_to_cpu(agf->agf_refcount_blocks); |
Darrick J. Wong | ebcbef3 | 2018-07-29 22:37:08 -0700 | [diff] [blame] | 511 | xfs_trans_brelse(tp, agbp); |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 512 | |
Darrick J. Wong | 5cd213b | 2019-05-20 11:25:39 -0700 | [diff] [blame] | 513 | /* |
| 514 | * The log is permanently allocated, so the space it occupies will |
| 515 | * never be available for the kinds of things that would require btree |
| 516 | * expansion. We therefore can pretend the space isn't there. |
| 517 | */ |
Dave Chinner | 36029de | 2022-07-07 19:13:21 +1000 | [diff] [blame] | 518 | if (xfs_ag_contains_log(mp, pag->pag_agno)) |
Darrick J. Wong | 5cd213b | 2019-05-20 11:25:39 -0700 | [diff] [blame] | 519 | agblocks -= mp->m_sb.sb_logblocks; |
| 520 | |
Darrick J. Wong | 20e73b0 | 2017-01-03 18:39:33 -0800 | [diff] [blame] | 521 | *ask += xfs_refcountbt_max_size(mp, agblocks); |
Darrick J. Wong | 84d6961 | 2016-10-03 09:11:44 -0700 | [diff] [blame] | 522 | *used += tree_len; |
| 523 | |
| 524 | return error; |
| 525 | } |
Darrick J. Wong | 9fa47bd | 2021-09-23 12:21:37 -0700 | [diff] [blame] | 526 | |
| 527 | int __init |
| 528 | xfs_refcountbt_init_cur_cache(void) |
| 529 | { |
| 530 | xfs_refcountbt_cur_cache = kmem_cache_create("xfs_refcbt_cur", |
| 531 | xfs_btree_cur_sizeof(xfs_refcountbt_maxlevels_ondisk()), |
| 532 | 0, 0, NULL); |
| 533 | |
| 534 | if (!xfs_refcountbt_cur_cache) |
| 535 | return -ENOMEM; |
| 536 | return 0; |
| 537 | } |
| 538 | |
| 539 | void |
| 540 | xfs_refcountbt_destroy_cur_cache(void) |
| 541 | { |
| 542 | kmem_cache_destroy(xfs_refcountbt_cur_cache); |
| 543 | xfs_refcountbt_cur_cache = NULL; |
| 544 | } |