1 // SPDX-License-Identifier: GPL-2.0+
3 * Copyright (C) 2016 Oracle. All Rights Reserved.
4 * Author: Darrick J. Wong <darrick.wong@oracle.com>
6 #include "libxfs_priv.h"
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_log_format.h"
11 #include "xfs_trans_resv.h"
13 #include "xfs_mount.h"
14 #include "xfs_btree.h"
16 #include "xfs_refcount_btree.h"
17 #include "xfs_alloc.h"
18 #include "xfs_trace.h"
19 #include "xfs_cksum.h"
20 #include "xfs_trans.h"
24 static struct xfs_btree_cur
*
25 xfs_refcountbt_dup_cursor(
26 struct xfs_btree_cur
*cur
)
28 return xfs_refcountbt_init_cursor(cur
->bc_mp
, cur
->bc_tp
,
29 cur
->bc_private
.a
.agbp
, cur
->bc_private
.a
.agno
);
33 xfs_refcountbt_set_root(
34 struct xfs_btree_cur
*cur
,
35 union xfs_btree_ptr
*ptr
,
38 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
39 struct xfs_agf
*agf
= XFS_BUF_TO_AGF(agbp
);
40 xfs_agnumber_t seqno
= be32_to_cpu(agf
->agf_seqno
);
41 struct xfs_perag
*pag
= xfs_perag_get(cur
->bc_mp
, seqno
);
45 agf
->agf_refcount_root
= ptr
->s
;
46 be32_add_cpu(&agf
->agf_refcount_level
, inc
);
47 pag
->pagf_refcount_level
+= inc
;
50 xfs_alloc_log_agf(cur
->bc_tp
, agbp
,
51 XFS_AGF_REFCOUNT_ROOT
| XFS_AGF_REFCOUNT_LEVEL
);
55 xfs_refcountbt_alloc_block(
56 struct xfs_btree_cur
*cur
,
57 union xfs_btree_ptr
*start
,
58 union xfs_btree_ptr
*new,
61 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
62 struct xfs_agf
*agf
= XFS_BUF_TO_AGF(agbp
);
63 struct xfs_alloc_arg args
; /* block allocation args */
64 int error
; /* error return value */
66 memset(&args
, 0, sizeof(args
));
69 args
.type
= XFS_ALLOCTYPE_NEAR_BNO
;
70 args
.fsbno
= XFS_AGB_TO_FSB(cur
->bc_mp
, cur
->bc_private
.a
.agno
,
71 xfs_refc_block(args
.mp
));
72 args
.oinfo
= XFS_RMAP_OINFO_REFC
;
73 args
.minlen
= args
.maxlen
= args
.prod
= 1;
74 args
.resv
= XFS_AG_RESV_METADATA
;
76 error
= xfs_alloc_vextent(&args
);
79 trace_xfs_refcountbt_alloc_block(cur
->bc_mp
, cur
->bc_private
.a
.agno
,
81 if (args
.fsbno
== NULLFSBLOCK
) {
85 ASSERT(args
.agno
== cur
->bc_private
.a
.agno
);
86 ASSERT(args
.len
== 1);
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
);
100 xfs_refcountbt_free_block(
101 struct xfs_btree_cur
*cur
,
104 struct xfs_mount
*mp
= cur
->bc_mp
;
105 struct xfs_buf
*agbp
= cur
->bc_private
.a
.agbp
;
106 struct xfs_agf
*agf
= XFS_BUF_TO_AGF(agbp
);
107 xfs_fsblock_t fsbno
= XFS_DADDR_TO_FSB(mp
, XFS_BUF_ADDR(bp
));
110 trace_xfs_refcountbt_free_block(cur
->bc_mp
, cur
->bc_private
.a
.agno
,
111 XFS_FSB_TO_AGBNO(cur
->bc_mp
, fsbno
), 1);
112 be32_add_cpu(&agf
->agf_refcount_blocks
, -1);
113 xfs_alloc_log_agf(cur
->bc_tp
, agbp
, XFS_AGF_REFCOUNT_BLOCKS
);
114 error
= xfs_free_extent(cur
->bc_tp
, fsbno
, 1, &XFS_RMAP_OINFO_REFC
,
115 XFS_AG_RESV_METADATA
);
123 xfs_refcountbt_get_minrecs(
124 struct xfs_btree_cur
*cur
,
127 return cur
->bc_mp
->m_refc_mnr
[level
!= 0];
131 xfs_refcountbt_get_maxrecs(
132 struct xfs_btree_cur
*cur
,
135 return cur
->bc_mp
->m_refc_mxr
[level
!= 0];
139 xfs_refcountbt_init_key_from_rec(
140 union xfs_btree_key
*key
,
141 union xfs_btree_rec
*rec
)
143 key
->refc
.rc_startblock
= rec
->refc
.rc_startblock
;
147 xfs_refcountbt_init_high_key_from_rec(
148 union xfs_btree_key
*key
,
149 union xfs_btree_rec
*rec
)
153 x
= be32_to_cpu(rec
->refc
.rc_startblock
);
154 x
+= be32_to_cpu(rec
->refc
.rc_blockcount
) - 1;
155 key
->refc
.rc_startblock
= cpu_to_be32(x
);
159 xfs_refcountbt_init_rec_from_cur(
160 struct xfs_btree_cur
*cur
,
161 union xfs_btree_rec
*rec
)
163 rec
->refc
.rc_startblock
= cpu_to_be32(cur
->bc_rec
.rc
.rc_startblock
);
164 rec
->refc
.rc_blockcount
= cpu_to_be32(cur
->bc_rec
.rc
.rc_blockcount
);
165 rec
->refc
.rc_refcount
= cpu_to_be32(cur
->bc_rec
.rc
.rc_refcount
);
169 xfs_refcountbt_init_ptr_from_cur(
170 struct xfs_btree_cur
*cur
,
171 union xfs_btree_ptr
*ptr
)
173 struct xfs_agf
*agf
= XFS_BUF_TO_AGF(cur
->bc_private
.a
.agbp
);
175 ASSERT(cur
->bc_private
.a
.agno
== be32_to_cpu(agf
->agf_seqno
));
177 ptr
->s
= agf
->agf_refcount_root
;
181 xfs_refcountbt_key_diff(
182 struct xfs_btree_cur
*cur
,
183 union xfs_btree_key
*key
)
185 struct xfs_refcount_irec
*rec
= &cur
->bc_rec
.rc
;
186 struct xfs_refcount_key
*kp
= &key
->refc
;
188 return (int64_t)be32_to_cpu(kp
->rc_startblock
) - rec
->rc_startblock
;
192 xfs_refcountbt_diff_two_keys(
193 struct xfs_btree_cur
*cur
,
194 union xfs_btree_key
*k1
,
195 union xfs_btree_key
*k2
)
197 return (int64_t)be32_to_cpu(k1
->refc
.rc_startblock
) -
198 be32_to_cpu(k2
->refc
.rc_startblock
);
201 STATIC xfs_failaddr_t
202 xfs_refcountbt_verify(
205 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
206 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
207 struct xfs_perag
*pag
= bp
->b_pag
;
211 if (block
->bb_magic
!= cpu_to_be32(XFS_REFC_CRC_MAGIC
))
212 return __this_address
;
214 if (!xfs_sb_version_hasreflink(&mp
->m_sb
))
215 return __this_address
;
216 fa
= xfs_btree_sblock_v5hdr_verify(bp
);
220 level
= be16_to_cpu(block
->bb_level
);
221 if (pag
&& pag
->pagf_init
) {
222 if (level
>= pag
->pagf_refcount_level
)
223 return __this_address
;
224 } else if (level
>= mp
->m_refc_maxlevels
)
225 return __this_address
;
227 return xfs_btree_sblock_verify(bp
, mp
->m_refc_mxr
[level
!= 0]);
231 xfs_refcountbt_read_verify(
236 if (!xfs_btree_sblock_verify_crc(bp
))
237 xfs_verifier_error(bp
, -EFSBADCRC
, __this_address
);
239 fa
= xfs_refcountbt_verify(bp
);
241 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
245 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
249 xfs_refcountbt_write_verify(
254 fa
= xfs_refcountbt_verify(bp
);
256 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
257 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
260 xfs_btree_sblock_calc_crc(bp
);
264 const struct xfs_buf_ops xfs_refcountbt_buf_ops
= {
265 .name
= "xfs_refcountbt",
266 .verify_read
= xfs_refcountbt_read_verify
,
267 .verify_write
= xfs_refcountbt_write_verify
,
268 .verify_struct
= xfs_refcountbt_verify
,
272 xfs_refcountbt_keys_inorder(
273 struct xfs_btree_cur
*cur
,
274 union xfs_btree_key
*k1
,
275 union xfs_btree_key
*k2
)
277 return be32_to_cpu(k1
->refc
.rc_startblock
) <
278 be32_to_cpu(k2
->refc
.rc_startblock
);
282 xfs_refcountbt_recs_inorder(
283 struct xfs_btree_cur
*cur
,
284 union xfs_btree_rec
*r1
,
285 union xfs_btree_rec
*r2
)
287 return be32_to_cpu(r1
->refc
.rc_startblock
) +
288 be32_to_cpu(r1
->refc
.rc_blockcount
) <=
289 be32_to_cpu(r2
->refc
.rc_startblock
);
292 static const struct xfs_btree_ops xfs_refcountbt_ops
= {
293 .rec_len
= sizeof(struct xfs_refcount_rec
),
294 .key_len
= sizeof(struct xfs_refcount_key
),
296 .dup_cursor
= xfs_refcountbt_dup_cursor
,
297 .set_root
= xfs_refcountbt_set_root
,
298 .alloc_block
= xfs_refcountbt_alloc_block
,
299 .free_block
= xfs_refcountbt_free_block
,
300 .get_minrecs
= xfs_refcountbt_get_minrecs
,
301 .get_maxrecs
= xfs_refcountbt_get_maxrecs
,
302 .init_key_from_rec
= xfs_refcountbt_init_key_from_rec
,
303 .init_high_key_from_rec
= xfs_refcountbt_init_high_key_from_rec
,
304 .init_rec_from_cur
= xfs_refcountbt_init_rec_from_cur
,
305 .init_ptr_from_cur
= xfs_refcountbt_init_ptr_from_cur
,
306 .key_diff
= xfs_refcountbt_key_diff
,
307 .buf_ops
= &xfs_refcountbt_buf_ops
,
308 .diff_two_keys
= xfs_refcountbt_diff_two_keys
,
309 .keys_inorder
= xfs_refcountbt_keys_inorder
,
310 .recs_inorder
= xfs_refcountbt_recs_inorder
,
314 * Allocate a new refcount btree cursor.
316 struct xfs_btree_cur
*
317 xfs_refcountbt_init_cursor(
318 struct xfs_mount
*mp
,
319 struct xfs_trans
*tp
,
320 struct xfs_buf
*agbp
,
323 struct xfs_agf
*agf
= XFS_BUF_TO_AGF(agbp
);
324 struct xfs_btree_cur
*cur
;
326 ASSERT(agno
!= NULLAGNUMBER
);
327 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
328 cur
= kmem_zone_zalloc(xfs_btree_cur_zone
, KM_NOFS
);
332 cur
->bc_btnum
= XFS_BTNUM_REFC
;
333 cur
->bc_blocklog
= mp
->m_sb
.sb_blocklog
;
334 cur
->bc_ops
= &xfs_refcountbt_ops
;
335 cur
->bc_statoff
= XFS_STATS_CALC_INDEX(xs_refcbt_2
);
337 cur
->bc_nlevels
= be32_to_cpu(agf
->agf_refcount_level
);
339 cur
->bc_private
.a
.agbp
= agbp
;
340 cur
->bc_private
.a
.agno
= agno
;
341 cur
->bc_flags
|= XFS_BTREE_CRC_BLOCKS
;
343 cur
->bc_private
.a
.priv
.refc
.nr_ops
= 0;
344 cur
->bc_private
.a
.priv
.refc
.shape_changes
= 0;
350 * Calculate the number of records in a refcount btree block.
353 xfs_refcountbt_maxrecs(
357 blocklen
-= XFS_REFCOUNT_BLOCK_LEN
;
360 return blocklen
/ sizeof(struct xfs_refcount_rec
);
361 return blocklen
/ (sizeof(struct xfs_refcount_key
) +
362 sizeof(xfs_refcount_ptr_t
));
365 /* Compute the maximum height of a refcount btree. */
367 xfs_refcountbt_compute_maxlevels(
368 struct xfs_mount
*mp
)
370 mp
->m_refc_maxlevels
= xfs_btree_compute_maxlevels(
371 mp
->m_refc_mnr
, mp
->m_sb
.sb_agblocks
);
374 /* Calculate the refcount btree size for some records. */
376 xfs_refcountbt_calc_size(
377 struct xfs_mount
*mp
,
378 unsigned long long len
)
380 return xfs_btree_calc_size(mp
->m_refc_mnr
, len
);
384 * Calculate the maximum refcount btree size.
387 xfs_refcountbt_max_size(
388 struct xfs_mount
*mp
,
389 xfs_agblock_t agblocks
)
391 /* Bail out if we're uninitialized, which can happen in mkfs. */
392 if (mp
->m_refc_mxr
[0] == 0)
395 return xfs_refcountbt_calc_size(mp
, agblocks
);
399 * Figure out how many blocks to reserve and how many are used by this btree.
402 xfs_refcountbt_calc_reserves(
403 struct xfs_mount
*mp
,
404 struct xfs_trans
*tp
,
409 struct xfs_buf
*agbp
;
411 xfs_agblock_t agblocks
;
412 xfs_extlen_t tree_len
;
415 if (!xfs_sb_version_hasreflink(&mp
->m_sb
))
419 error
= xfs_alloc_read_agf(mp
, tp
, agno
, 0, &agbp
);
423 agf
= XFS_BUF_TO_AGF(agbp
);
424 agblocks
= be32_to_cpu(agf
->agf_length
);
425 tree_len
= be32_to_cpu(agf
->agf_refcount_blocks
);
426 xfs_trans_brelse(tp
, agbp
);
428 *ask
+= xfs_refcountbt_max_size(mp
, agblocks
);