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"
12 #include "xfs_mount.h"
13 #include "xfs_btree.h"
14 #include "xfs_btree_staging.h"
15 #include "xfs_refcount_btree.h"
16 #include "xfs_refcount.h"
17 #include "xfs_alloc.h"
18 #include "xfs_trace.h"
19 #include "xfs_trans.h"
24 static struct kmem_cache
*xfs_refcountbt_cur_cache
;
26 static struct xfs_btree_cur
*
27 xfs_refcountbt_dup_cursor(
28 struct xfs_btree_cur
*cur
)
30 return xfs_refcountbt_init_cursor(cur
->bc_mp
, cur
->bc_tp
,
31 cur
->bc_ag
.agbp
, cur
->bc_ag
.pag
);
35 xfs_refcountbt_set_root(
36 struct xfs_btree_cur
*cur
,
37 const union xfs_btree_ptr
*ptr
,
40 struct xfs_buf
*agbp
= cur
->bc_ag
.agbp
;
41 struct xfs_agf
*agf
= agbp
->b_addr
;
42 struct xfs_perag
*pag
= agbp
->b_pag
;
46 agf
->agf_refcount_root
= ptr
->s
;
47 be32_add_cpu(&agf
->agf_refcount_level
, inc
);
48 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 const union xfs_btree_ptr
*start
,
58 union xfs_btree_ptr
*new,
61 struct xfs_buf
*agbp
= cur
->bc_ag
.agbp
;
62 struct xfs_agf
*agf
= agbp
->b_addr
;
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_ag
.pag
->pag_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_ag
.pag
->pag_agno
,
81 if (args
.fsbno
== NULLFSBLOCK
) {
85 ASSERT(args
.agno
== cur
->bc_ag
.pag
->pag_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_ag
.agbp
;
106 struct xfs_agf
*agf
= agbp
->b_addr
;
107 xfs_fsblock_t fsbno
= XFS_DADDR_TO_FSB(mp
, xfs_buf_daddr(bp
));
110 trace_xfs_refcountbt_free_block(cur
->bc_mp
, cur
->bc_ag
.pag
->pag_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 const 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 const 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 const struct xfs_refcount_irec
*irec
= &cur
->bc_rec
.rc
;
166 start
= xfs_refcount_encode_startblock(irec
->rc_startblock
,
168 rec
->refc
.rc_startblock
= cpu_to_be32(start
);
169 rec
->refc
.rc_blockcount
= cpu_to_be32(cur
->bc_rec
.rc
.rc_blockcount
);
170 rec
->refc
.rc_refcount
= cpu_to_be32(cur
->bc_rec
.rc
.rc_refcount
);
174 xfs_refcountbt_init_ptr_from_cur(
175 struct xfs_btree_cur
*cur
,
176 union xfs_btree_ptr
*ptr
)
178 struct xfs_agf
*agf
= cur
->bc_ag
.agbp
->b_addr
;
180 ASSERT(cur
->bc_ag
.pag
->pag_agno
== be32_to_cpu(agf
->agf_seqno
));
182 ptr
->s
= agf
->agf_refcount_root
;
186 xfs_refcountbt_key_diff(
187 struct xfs_btree_cur
*cur
,
188 const union xfs_btree_key
*key
)
190 const struct xfs_refcount_key
*kp
= &key
->refc
;
191 const struct xfs_refcount_irec
*irec
= &cur
->bc_rec
.rc
;
194 start
= xfs_refcount_encode_startblock(irec
->rc_startblock
,
196 return (int64_t)be32_to_cpu(kp
->rc_startblock
) - start
;
200 xfs_refcountbt_diff_two_keys(
201 struct xfs_btree_cur
*cur
,
202 const union xfs_btree_key
*k1
,
203 const union xfs_btree_key
*k2
)
205 return (int64_t)be32_to_cpu(k1
->refc
.rc_startblock
) -
206 be32_to_cpu(k2
->refc
.rc_startblock
);
209 STATIC xfs_failaddr_t
210 xfs_refcountbt_verify(
213 struct xfs_mount
*mp
= bp
->b_mount
;
214 struct xfs_btree_block
*block
= XFS_BUF_TO_BLOCK(bp
);
215 struct xfs_perag
*pag
= bp
->b_pag
;
219 if (!xfs_verify_magic(bp
, block
->bb_magic
))
220 return __this_address
;
222 if (!xfs_has_reflink(mp
))
223 return __this_address
;
224 fa
= xfs_btree_sblock_v5hdr_verify(bp
);
228 level
= be16_to_cpu(block
->bb_level
);
229 if (pag
&& xfs_perag_initialised_agf(pag
)) {
230 if (level
>= pag
->pagf_refcount_level
)
231 return __this_address
;
232 } else if (level
>= mp
->m_refc_maxlevels
)
233 return __this_address
;
235 return xfs_btree_sblock_verify(bp
, mp
->m_refc_mxr
[level
!= 0]);
239 xfs_refcountbt_read_verify(
244 if (!xfs_btree_sblock_verify_crc(bp
))
245 xfs_verifier_error(bp
, -EFSBADCRC
, __this_address
);
247 fa
= xfs_refcountbt_verify(bp
);
249 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
253 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
257 xfs_refcountbt_write_verify(
262 fa
= xfs_refcountbt_verify(bp
);
264 trace_xfs_btree_corrupt(bp
, _RET_IP_
);
265 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
268 xfs_btree_sblock_calc_crc(bp
);
272 const struct xfs_buf_ops xfs_refcountbt_buf_ops
= {
273 .name
= "xfs_refcountbt",
274 .magic
= { 0, cpu_to_be32(XFS_REFC_CRC_MAGIC
) },
275 .verify_read
= xfs_refcountbt_read_verify
,
276 .verify_write
= xfs_refcountbt_write_verify
,
277 .verify_struct
= xfs_refcountbt_verify
,
281 xfs_refcountbt_keys_inorder(
282 struct xfs_btree_cur
*cur
,
283 const union xfs_btree_key
*k1
,
284 const union xfs_btree_key
*k2
)
286 return be32_to_cpu(k1
->refc
.rc_startblock
) <
287 be32_to_cpu(k2
->refc
.rc_startblock
);
291 xfs_refcountbt_recs_inorder(
292 struct xfs_btree_cur
*cur
,
293 const union xfs_btree_rec
*r1
,
294 const union xfs_btree_rec
*r2
)
296 return be32_to_cpu(r1
->refc
.rc_startblock
) +
297 be32_to_cpu(r1
->refc
.rc_blockcount
) <=
298 be32_to_cpu(r2
->refc
.rc_startblock
);
301 static const struct xfs_btree_ops xfs_refcountbt_ops
= {
302 .rec_len
= sizeof(struct xfs_refcount_rec
),
303 .key_len
= sizeof(struct xfs_refcount_key
),
305 .dup_cursor
= xfs_refcountbt_dup_cursor
,
306 .set_root
= xfs_refcountbt_set_root
,
307 .alloc_block
= xfs_refcountbt_alloc_block
,
308 .free_block
= xfs_refcountbt_free_block
,
309 .get_minrecs
= xfs_refcountbt_get_minrecs
,
310 .get_maxrecs
= xfs_refcountbt_get_maxrecs
,
311 .init_key_from_rec
= xfs_refcountbt_init_key_from_rec
,
312 .init_high_key_from_rec
= xfs_refcountbt_init_high_key_from_rec
,
313 .init_rec_from_cur
= xfs_refcountbt_init_rec_from_cur
,
314 .init_ptr_from_cur
= xfs_refcountbt_init_ptr_from_cur
,
315 .key_diff
= xfs_refcountbt_key_diff
,
316 .buf_ops
= &xfs_refcountbt_buf_ops
,
317 .diff_two_keys
= xfs_refcountbt_diff_two_keys
,
318 .keys_inorder
= xfs_refcountbt_keys_inorder
,
319 .recs_inorder
= xfs_refcountbt_recs_inorder
,
323 * Initialize a new refcount btree cursor.
325 static struct xfs_btree_cur
*
326 xfs_refcountbt_init_common(
327 struct xfs_mount
*mp
,
328 struct xfs_trans
*tp
,
329 struct xfs_perag
*pag
)
331 struct xfs_btree_cur
*cur
;
333 ASSERT(pag
->pag_agno
< mp
->m_sb
.sb_agcount
);
335 cur
= xfs_btree_alloc_cursor(mp
, tp
, XFS_BTNUM_REFC
,
336 mp
->m_refc_maxlevels
, xfs_refcountbt_cur_cache
);
337 cur
->bc_statoff
= XFS_STATS_CALC_INDEX(xs_refcbt_2
);
339 cur
->bc_flags
|= XFS_BTREE_CRC_BLOCKS
;
341 /* take a reference for the cursor */
342 atomic_inc(&pag
->pag_ref
);
343 cur
->bc_ag
.pag
= pag
;
345 cur
->bc_ag
.refc
.nr_ops
= 0;
346 cur
->bc_ag
.refc
.shape_changes
= 0;
347 cur
->bc_ops
= &xfs_refcountbt_ops
;
351 /* Create a btree cursor. */
352 struct xfs_btree_cur
*
353 xfs_refcountbt_init_cursor(
354 struct xfs_mount
*mp
,
355 struct xfs_trans
*tp
,
356 struct xfs_buf
*agbp
,
357 struct xfs_perag
*pag
)
359 struct xfs_agf
*agf
= agbp
->b_addr
;
360 struct xfs_btree_cur
*cur
;
362 cur
= xfs_refcountbt_init_common(mp
, tp
, pag
);
363 cur
->bc_nlevels
= be32_to_cpu(agf
->agf_refcount_level
);
364 cur
->bc_ag
.agbp
= agbp
;
368 /* Create a btree cursor with a fake root for staging. */
369 struct xfs_btree_cur
*
370 xfs_refcountbt_stage_cursor(
371 struct xfs_mount
*mp
,
372 struct xbtree_afakeroot
*afake
,
373 struct xfs_perag
*pag
)
375 struct xfs_btree_cur
*cur
;
377 cur
= xfs_refcountbt_init_common(mp
, NULL
, pag
);
378 xfs_btree_stage_afakeroot(cur
, afake
);
383 * Swap in the new btree root. Once we pass this point the newly rebuilt btree
384 * is in place and we have to kill off all the old btree blocks.
387 xfs_refcountbt_commit_staged_btree(
388 struct xfs_btree_cur
*cur
,
389 struct xfs_trans
*tp
,
390 struct xfs_buf
*agbp
)
392 struct xfs_agf
*agf
= agbp
->b_addr
;
393 struct xbtree_afakeroot
*afake
= cur
->bc_ag
.afake
;
395 ASSERT(cur
->bc_flags
& XFS_BTREE_STAGING
);
397 agf
->agf_refcount_root
= cpu_to_be32(afake
->af_root
);
398 agf
->agf_refcount_level
= cpu_to_be32(afake
->af_levels
);
399 agf
->agf_refcount_blocks
= cpu_to_be32(afake
->af_blocks
);
400 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_REFCOUNT_BLOCKS
|
401 XFS_AGF_REFCOUNT_ROOT
|
402 XFS_AGF_REFCOUNT_LEVEL
);
403 xfs_btree_commit_afakeroot(cur
, tp
, agbp
, &xfs_refcountbt_ops
);
406 /* Calculate number of records in a refcount btree block. */
407 static inline unsigned int
408 xfs_refcountbt_block_maxrecs(
409 unsigned int blocklen
,
413 return blocklen
/ sizeof(struct xfs_refcount_rec
);
414 return blocklen
/ (sizeof(struct xfs_refcount_key
) +
415 sizeof(xfs_refcount_ptr_t
));
419 * Calculate the number of records in a refcount btree block.
422 xfs_refcountbt_maxrecs(
426 blocklen
-= XFS_REFCOUNT_BLOCK_LEN
;
427 return xfs_refcountbt_block_maxrecs(blocklen
, leaf
);
430 /* Compute the max possible height of the maximally sized refcount btree. */
432 xfs_refcountbt_maxlevels_ondisk(void)
434 unsigned int minrecs
[2];
435 unsigned int blocklen
;
437 blocklen
= XFS_MIN_CRC_BLOCKSIZE
- XFS_BTREE_SBLOCK_CRC_LEN
;
439 minrecs
[0] = xfs_refcountbt_block_maxrecs(blocklen
, true) / 2;
440 minrecs
[1] = xfs_refcountbt_block_maxrecs(blocklen
, false) / 2;
442 return xfs_btree_compute_maxlevels(minrecs
, XFS_MAX_CRC_AG_BLOCKS
);
445 /* Compute the maximum height of a refcount btree. */
447 xfs_refcountbt_compute_maxlevels(
448 struct xfs_mount
*mp
)
450 if (!xfs_has_reflink(mp
)) {
451 mp
->m_refc_maxlevels
= 0;
455 mp
->m_refc_maxlevels
= xfs_btree_compute_maxlevels(
456 mp
->m_refc_mnr
, mp
->m_sb
.sb_agblocks
);
457 ASSERT(mp
->m_refc_maxlevels
<= xfs_refcountbt_maxlevels_ondisk());
460 /* Calculate the refcount btree size for some records. */
462 xfs_refcountbt_calc_size(
463 struct xfs_mount
*mp
,
464 unsigned long long len
)
466 return xfs_btree_calc_size(mp
->m_refc_mnr
, len
);
470 * Calculate the maximum refcount btree size.
473 xfs_refcountbt_max_size(
474 struct xfs_mount
*mp
,
475 xfs_agblock_t agblocks
)
477 /* Bail out if we're uninitialized, which can happen in mkfs. */
478 if (mp
->m_refc_mxr
[0] == 0)
481 return xfs_refcountbt_calc_size(mp
, agblocks
);
485 * Figure out how many blocks to reserve and how many are used by this btree.
488 xfs_refcountbt_calc_reserves(
489 struct xfs_mount
*mp
,
490 struct xfs_trans
*tp
,
491 struct xfs_perag
*pag
,
495 struct xfs_buf
*agbp
;
497 xfs_agblock_t agblocks
;
498 xfs_extlen_t tree_len
;
501 if (!xfs_has_reflink(mp
))
504 error
= xfs_alloc_read_agf(pag
, tp
, 0, &agbp
);
509 agblocks
= be32_to_cpu(agf
->agf_length
);
510 tree_len
= be32_to_cpu(agf
->agf_refcount_blocks
);
511 xfs_trans_brelse(tp
, agbp
);
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.
518 if (xfs_ag_contains_log(mp
, pag
->pag_agno
))
519 agblocks
-= mp
->m_sb
.sb_logblocks
;
521 *ask
+= xfs_refcountbt_max_size(mp
, agblocks
);
528 xfs_refcountbt_init_cur_cache(void)
530 xfs_refcountbt_cur_cache
= kmem_cache_create("xfs_refcbt_cur",
531 xfs_btree_cur_sizeof(xfs_refcountbt_maxlevels_ondisk()),
534 if (!xfs_refcountbt_cur_cache
)
540 xfs_refcountbt_destroy_cur_cache(void)
542 kmem_cache_destroy(xfs_refcountbt_cur_cache
);
543 xfs_refcountbt_cur_cache
= NULL
;