fs/xfs/libxfs/xfs_refcount_btree.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * Copyright (C) 2016 Oracle.  All Rights Reserved.
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   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"
  12 #include "xfs_sb.h"
  13 #include "xfs_mount.h"
  14 #include "xfs_btree.h"
  15 #include "xfs_btree_staging.h"
  16 #include "xfs_refcount_btree.h"
  17 #include "xfs_alloc.h"
  18 #include "xfs_error.h"
  19 #include "xfs_trace.h"
  20 #include "xfs_trans.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_rmap.h"
  23
  24 static struct xfs_btree_cur *
  25 xfs_refcountbt_dup_cursor(
  26         struct xfs_btree_cur    *cur)
  27 {
  28         return xfs_refcountbt_init_cursor(cur->bc_mp, cur->bc_tp,
  29                         cur->bc_ag.agbp, cur->bc_ag.agno);
  30 }
  31
  32 STATIC void
  33 xfs_refcountbt_set_root(
  34         struct xfs_btree_cur    *cur,
  35         union xfs_btree_ptr     *ptr,
  36         int                     inc)
  37 {
  38         struct xfs_buf          *agbp = cur->bc_ag.agbp;
  39         struct xfs_agf          *agf = agbp->b_addr;
  40         struct xfs_perag        *pag = agbp->b_pag;
  41
  42         ASSERT(ptr->s != 0);
  43
  44         agf->agf_refcount_root = ptr->s;
  45         be32_add_cpu(&agf->agf_refcount_level, inc);
  46         pag->pagf_refcount_level += inc;
  47
  48         xfs_alloc_log_agf(cur->bc_tp, agbp,
  49                         XFS_AGF_REFCOUNT_ROOT | XFS_AGF_REFCOUNT_LEVEL);
  50 }
  51
  52 STATIC int
  53 xfs_refcountbt_alloc_block(
  54         struct xfs_btree_cur    *cur,
  55         union xfs_btree_ptr     *start,
  56         union xfs_btree_ptr     *new,
  57         int                     *stat)
  58 {
  59         struct xfs_buf          *agbp = cur->bc_ag.agbp;
  60         struct xfs_agf          *agf = agbp->b_addr;
  61         struct xfs_alloc_arg    args;           /* block allocation args */
  62         int                     error;          /* error return value */
  63
  64         memset(&args, 0, sizeof(args));
  65         args.tp = cur->bc_tp;
  66         args.mp = cur->bc_mp;
  67         args.type = XFS_ALLOCTYPE_NEAR_BNO;
  68         args.fsbno = XFS_AGB_TO_FSB(cur->bc_mp, cur->bc_ag.agno,
  69                         xfs_refc_block(args.mp));
  70         args.oinfo = XFS_RMAP_OINFO_REFC;
  71         args.minlen = args.maxlen = args.prod = 1;
  72         args.resv = XFS_AG_RESV_METADATA;
  73
  74         error = xfs_alloc_vextent(&args);
  75         if (error)
  76                 goto out_error;
  77         trace_xfs_refcountbt_alloc_block(cur->bc_mp, cur->bc_ag.agno,
  78                         args.agbno, 1);
  79         if (args.fsbno == NULLFSBLOCK) {
  80                 *stat = 0;
  81                 return 0;
  82         }
  83         ASSERT(args.agno == cur->bc_ag.agno);
  84         ASSERT(args.len == 1);
  85
  86         new->s = cpu_to_be32(args.agbno);
  87         be32_add_cpu(&agf->agf_refcount_blocks, 1);
  88         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
  89
  90         *stat = 1;
  91         return 0;
  92
  93 out_error:
  94         return error;
  95 }
  96
  97 STATIC int
  98 xfs_refcountbt_free_block(
  99         struct xfs_btree_cur    *cur,
 100         struct xfs_buf          *bp)
 101 {
 102         struct xfs_mount        *mp = cur->bc_mp;
 103         struct xfs_buf          *agbp = cur->bc_ag.agbp;
 104         struct xfs_agf          *agf = agbp->b_addr;
 105         xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
 106         int                     error;
 107
 108         trace_xfs_refcountbt_free_block(cur->bc_mp, cur->bc_ag.agno,
 109                         XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno), 1);
 110         be32_add_cpu(&agf->agf_refcount_blocks, -1);
 111         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
 112         error = xfs_free_extent(cur->bc_tp, fsbno, 1, &XFS_RMAP_OINFO_REFC,
 113                         XFS_AG_RESV_METADATA);
 114         if (error)
 115                 return error;
 116
 117         return error;
 118 }
 119
 120 STATIC int
 121 xfs_refcountbt_get_minrecs(
 122         struct xfs_btree_cur    *cur,
 123         int                     level)
 124 {
 125         return cur->bc_mp->m_refc_mnr[level != 0];
 126 }
 127
 128 STATIC int
 129 xfs_refcountbt_get_maxrecs(
 130         struct xfs_btree_cur    *cur,
 131         int                     level)
 132 {
 133         return cur->bc_mp->m_refc_mxr[level != 0];
 134 }
 135
 136 STATIC void
 137 xfs_refcountbt_init_key_from_rec(
 138         union xfs_btree_key     *key,
 139         union xfs_btree_rec     *rec)
 140 {
 141         key->refc.rc_startblock = rec->refc.rc_startblock;
 142 }
 143
 144 STATIC void
 145 xfs_refcountbt_init_high_key_from_rec(
 146         union xfs_btree_key     *key,
 147         union xfs_btree_rec     *rec)
 148 {
 149         __u32                   x;
 150
 151         x = be32_to_cpu(rec->refc.rc_startblock);
 152         x += be32_to_cpu(rec->refc.rc_blockcount) - 1;
 153         key->refc.rc_startblock = cpu_to_be32(x);
 154 }
 155
 156 STATIC void
 157 xfs_refcountbt_init_rec_from_cur(
 158         struct xfs_btree_cur    *cur,
 159         union xfs_btree_rec     *rec)
 160 {
 161         rec->refc.rc_startblock = cpu_to_be32(cur->bc_rec.rc.rc_startblock);
 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 {
 171         struct xfs_agf          *agf = cur->bc_ag.agbp->b_addr;
 172
 173         ASSERT(cur->bc_ag.agno == be32_to_cpu(agf->agf_seqno));
 174
 175         ptr->s = agf->agf_refcount_root;
 176 }
 177
 178 STATIC int64_t
 179 xfs_refcountbt_key_diff(
 180         struct xfs_btree_cur    *cur,
 181         union xfs_btree_key     *key)
 182 {
 183         struct xfs_refcount_irec        *rec = &cur->bc_rec.rc;
 184         struct xfs_refcount_key         *kp = &key->refc;
 185
 186         return (int64_t)be32_to_cpu(kp->rc_startblock) - rec->rc_startblock;
 187 }
 188
 189 STATIC int64_t
 190 xfs_refcountbt_diff_two_keys(
 191         struct xfs_btree_cur    *cur,
 192         union xfs_btree_key     *k1,
 193         union xfs_btree_key     *k2)
 194 {
 195         return (int64_t)be32_to_cpu(k1->refc.rc_startblock) -
 196                           be32_to_cpu(k2->refc.rc_startblock);
 197 }
 198
 199 STATIC xfs_failaddr_t
 200 xfs_refcountbt_verify(
 201         struct xfs_buf          *bp)
 202 {
 203         struct xfs_mount        *mp = bp->b_mount;
 204         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 205         struct xfs_perag        *pag = bp->b_pag;
 206         xfs_failaddr_t          fa;
 207         unsigned int            level;
 208
 209         if (!xfs_verify_magic(bp, block->bb_magic))
 210                 return __this_address;
 211
 212         if (!xfs_sb_version_hasreflink(&mp->m_sb))
 213                 return __this_address;
 214         fa = xfs_btree_sblock_v5hdr_verify(bp);
 215         if (fa)
 216                 return fa;
 217
 218         level = be16_to_cpu(block->bb_level);
 219         if (pag && pag->pagf_init) {
 220                 if (level >= pag->pagf_refcount_level)
 221                         return __this_address;
 222         } else if (level >= mp->m_refc_maxlevels)
 223                 return __this_address;
 224
 225         return xfs_btree_sblock_verify(bp, mp->m_refc_mxr[level != 0]);
 226 }
 227
 228 STATIC void
 229 xfs_refcountbt_read_verify(
 230         struct xfs_buf  *bp)
 231 {
 232         xfs_failaddr_t  fa;
 233
 234         if (!xfs_btree_sblock_verify_crc(bp))
 235                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 236         else {
 237                 fa = xfs_refcountbt_verify(bp);
 238                 if (fa)
 239                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 240         }
 241
 242         if (bp->b_error)
 243                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 244 }
 245
 246 STATIC void
 247 xfs_refcountbt_write_verify(
 248         struct xfs_buf  *bp)
 249 {
 250         xfs_failaddr_t  fa;
 251
 252         fa = xfs_refcountbt_verify(bp);
 253         if (fa) {
 254                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 255                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 256                 return;
 257         }
 258         xfs_btree_sblock_calc_crc(bp);
 259
 260 }
 261
 262 const struct xfs_buf_ops xfs_refcountbt_buf_ops = {
 263         .name                   = "xfs_refcountbt",
 264         .magic                  = { 0, cpu_to_be32(XFS_REFC_CRC_MAGIC) },
 265         .verify_read            = xfs_refcountbt_read_verify,
 266         .verify_write           = xfs_refcountbt_write_verify,
 267         .verify_struct          = xfs_refcountbt_verify,
 268 };
 269
 270 STATIC int
 271 xfs_refcountbt_keys_inorder(
 272         struct xfs_btree_cur    *cur,
 273         union xfs_btree_key     *k1,
 274         union xfs_btree_key     *k2)
 275 {
 276         return be32_to_cpu(k1->refc.rc_startblock) <
 277                be32_to_cpu(k2->refc.rc_startblock);
 278 }
 279
 280 STATIC int
 281 xfs_refcountbt_recs_inorder(
 282         struct xfs_btree_cur    *cur,
 283         union xfs_btree_rec     *r1,
 284         union xfs_btree_rec     *r2)
 285 {
 286         return  be32_to_cpu(r1->refc.rc_startblock) +
 287                 be32_to_cpu(r1->refc.rc_blockcount) <=
 288                 be32_to_cpu(r2->refc.rc_startblock);
 289 }
 290
 291 static const struct xfs_btree_ops xfs_refcountbt_ops = {
 292         .rec_len                = sizeof(struct xfs_refcount_rec),
 293         .key_len                = sizeof(struct xfs_refcount_key),
 294
 295         .dup_cursor             = xfs_refcountbt_dup_cursor,
 296         .set_root               = xfs_refcountbt_set_root,
 297         .alloc_block            = xfs_refcountbt_alloc_block,
 298         .free_block             = xfs_refcountbt_free_block,
 299         .get_minrecs            = xfs_refcountbt_get_minrecs,
 300         .get_maxrecs            = xfs_refcountbt_get_maxrecs,
 301         .init_key_from_rec      = xfs_refcountbt_init_key_from_rec,
 302         .init_high_key_from_rec = xfs_refcountbt_init_high_key_from_rec,
 303         .init_rec_from_cur      = xfs_refcountbt_init_rec_from_cur,
 304         .init_ptr_from_cur      = xfs_refcountbt_init_ptr_from_cur,
 305         .key_diff               = xfs_refcountbt_key_diff,
 306         .buf_ops                = &xfs_refcountbt_buf_ops,
 307         .diff_two_keys          = xfs_refcountbt_diff_two_keys,
 308         .keys_inorder           = xfs_refcountbt_keys_inorder,
 309         .recs_inorder           = xfs_refcountbt_recs_inorder,
 310 };
 311
 312 /*
 313  * Initialize a new refcount btree cursor.
 314  */
 315 static struct xfs_btree_cur *
 316 xfs_refcountbt_init_common(
 317         struct xfs_mount        *mp,
 318         struct xfs_trans        *tp,
 319         xfs_agnumber_t          agno)
 320 {
 321         struct xfs_btree_cur    *cur;
 322
 323         ASSERT(agno != NULLAGNUMBER);
 324         ASSERT(agno < mp->m_sb.sb_agcount);
 325
 326         cur = kmem_cache_zalloc(xfs_btree_cur_zone, GFP_NOFS | __GFP_NOFAIL);
 327         cur->bc_tp = tp;
 328         cur->bc_mp = mp;
 329         cur->bc_btnum = XFS_BTNUM_REFC;
 330         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 331         cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_refcbt_2);
 332
 333         cur->bc_ag.agno = agno;
 334         cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 335
 336         cur->bc_ag.refc.nr_ops = 0;
 337         cur->bc_ag.refc.shape_changes = 0;
 338         cur->bc_ops = &xfs_refcountbt_ops;
 339         return cur;
 340 }
 341
 342 /* Create a btree cursor. */
 343 struct xfs_btree_cur *
 344 xfs_refcountbt_init_cursor(
 345         struct xfs_mount        *mp,
 346         struct xfs_trans        *tp,
 347         struct xfs_buf          *agbp,
 348         xfs_agnumber_t          agno)
 349 {
 350         struct xfs_agf          *agf = agbp->b_addr;
 351         struct xfs_btree_cur    *cur;
 352
 353         cur = xfs_refcountbt_init_common(mp, tp, agno);
 354         cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level);
 355         cur->bc_ag.agbp = agbp;
 356         return cur;
 357 }
 358
 359 /* Create a btree cursor with a fake root for staging. */
 360 struct xfs_btree_cur *
 361 xfs_refcountbt_stage_cursor(
 362         struct xfs_mount        *mp,
 363         struct xbtree_afakeroot *afake,
 364         xfs_agnumber_t          agno)
 365 {
 366         struct xfs_btree_cur    *cur;
 367
 368         cur = xfs_refcountbt_init_common(mp, NULL, agno);
 369         xfs_btree_stage_afakeroot(cur, afake);
 370         return cur;
 371 }
 372
 373 /*
 374  * Swap in the new btree root.  Once we pass this point the newly rebuilt btree
 375  * is in place and we have to kill off all the old btree blocks.
 376  */
 377 void
 378 xfs_refcountbt_commit_staged_btree(
 379         struct xfs_btree_cur    *cur,
 380         struct xfs_trans        *tp,
 381         struct xfs_buf          *agbp)
 382 {
 383         struct xfs_agf          *agf = agbp->b_addr;
 384         struct xbtree_afakeroot *afake = cur->bc_ag.afake;
 385
 386         ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
 387
 388         agf->agf_refcount_root = cpu_to_be32(afake->af_root);
 389         agf->agf_refcount_level = cpu_to_be32(afake->af_levels);
 390         agf->agf_refcount_blocks = cpu_to_be32(afake->af_blocks);
 391         xfs_alloc_log_agf(tp, agbp, XFS_AGF_REFCOUNT_BLOCKS |
 392                                     XFS_AGF_REFCOUNT_ROOT |
 393                                     XFS_AGF_REFCOUNT_LEVEL);
 394         xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_refcountbt_ops);
 395 }
 396
 397 /*
 398  * Calculate the number of records in a refcount btree block.
 399  */
 400 int
 401 xfs_refcountbt_maxrecs(
 402         int                     blocklen,
 403         bool                    leaf)
 404 {
 405         blocklen -= XFS_REFCOUNT_BLOCK_LEN;
 406
 407         if (leaf)
 408                 return blocklen / sizeof(struct xfs_refcount_rec);
 409         return blocklen / (sizeof(struct xfs_refcount_key) +
 410                            sizeof(xfs_refcount_ptr_t));
 411 }
 412
 413 /* Compute the maximum height of a refcount btree. */
 414 void
 415 xfs_refcountbt_compute_maxlevels(
 416         struct xfs_mount                *mp)
 417 {
 418         mp->m_refc_maxlevels = xfs_btree_compute_maxlevels(
 419                         mp->m_refc_mnr, mp->m_sb.sb_agblocks);
 420 }
 421
 422 /* Calculate the refcount btree size for some records. */
 423 xfs_extlen_t
 424 xfs_refcountbt_calc_size(
 425         struct xfs_mount        *mp,
 426         unsigned long long      len)
 427 {
 428         return xfs_btree_calc_size(mp->m_refc_mnr, len);
 429 }
 430
 431 /*
 432  * Calculate the maximum refcount btree size.
 433  */
 434 xfs_extlen_t
 435 xfs_refcountbt_max_size(
 436         struct xfs_mount        *mp,
 437         xfs_agblock_t           agblocks)
 438 {
 439         /* Bail out if we're uninitialized, which can happen in mkfs. */
 440         if (mp->m_refc_mxr[0] == 0)
 441                 return 0;
 442
 443         return xfs_refcountbt_calc_size(mp, agblocks);
 444 }
 445
 446 /*
 447  * Figure out how many blocks to reserve and how many are used by this btree.
 448  */
 449 int
 450 xfs_refcountbt_calc_reserves(
 451         struct xfs_mount        *mp,
 452         struct xfs_trans        *tp,
 453         xfs_agnumber_t          agno,
 454         xfs_extlen_t            *ask,
 455         xfs_extlen_t            *used)
 456 {
 457         struct xfs_buf          *agbp;
 458         struct xfs_agf          *agf;
 459         xfs_agblock_t           agblocks;
 460         xfs_extlen_t            tree_len;
 461         int                     error;
 462
 463         if (!xfs_sb_version_hasreflink(&mp->m_sb))
 464                 return 0;
 465
 466
 467         error = xfs_alloc_read_agf(mp, tp, agno, 0, &agbp);
 468         if (error)
 469                 return error;
 470
 471         agf = agbp->b_addr;
 472         agblocks = be32_to_cpu(agf->agf_length);
 473         tree_len = be32_to_cpu(agf->agf_refcount_blocks);
 474         xfs_trans_brelse(tp, agbp);
 475
 476         /*
 477          * The log is permanently allocated, so the space it occupies will
 478          * never be available for the kinds of things that would require btree
 479          * expansion.  We therefore can pretend the space isn't there.
 480          */
 481         if (mp->m_sb.sb_logstart &&
 482             XFS_FSB_TO_AGNO(mp, mp->m_sb.sb_logstart) == agno)
 483                 agblocks -= mp->m_sb.sb_logblocks;
 484
 485         *ask += xfs_refcountbt_max_size(mp, agblocks);
 486         *used += tree_len;
 487
 488         return error;
 489 }