fs/xfs/libxfs/xfs_refcount_btree.c

   1 /*
   2  * Copyright (C) 2016 Oracle.  All Rights Reserved.
   3  *
   4  * Author: Darrick J. Wong <darrick.wong@oracle.com>
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version 2
   9  * of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it would be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write the Free Software Foundation,
  18  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA.
  19  */
  20 #include "xfs.h"
  21 #include "xfs_fs.h"
  22 #include "xfs_shared.h"
  23 #include "xfs_format.h"
  24 #include "xfs_log_format.h"
  25 #include "xfs_trans_resv.h"
  26 #include "xfs_sb.h"
  27 #include "xfs_mount.h"
  28 #include "xfs_btree.h"
  29 #include "xfs_bmap.h"
  30 #include "xfs_refcount_btree.h"
  31 #include "xfs_alloc.h"
  32 #include "xfs_error.h"
  33 #include "xfs_trace.h"
  34 #include "xfs_cksum.h"
  35 #include "xfs_trans.h"
  36 #include "xfs_bit.h"
  37 #include "xfs_rmap.h"
  38
  39 static struct xfs_btree_cur *
  40 xfs_refcountbt_dup_cursor(
  41         struct xfs_btree_cur    *cur)
  42 {
  43         return xfs_refcountbt_init_cursor(cur->bc_mp, cur->bc_tp,
  44                         cur->bc_private.a.agbp, cur->bc_private.a.agno,
  45                         cur->bc_private.a.dfops);
  46 }
  47
  48 STATIC void
  49 xfs_refcountbt_set_root(
  50         struct xfs_btree_cur    *cur,
  51         union xfs_btree_ptr     *ptr,
  52         int                     inc)
  53 {
  54         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
  55         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
  56         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
  57         struct xfs_perag        *pag = xfs_perag_get(cur->bc_mp, seqno);
  58
  59         ASSERT(ptr->s != 0);
  60
  61         agf->agf_refcount_root = ptr->s;
  62         be32_add_cpu(&agf->agf_refcount_level, inc);
  63         pag->pagf_refcount_level += inc;
  64         xfs_perag_put(pag);
  65
  66         xfs_alloc_log_agf(cur->bc_tp, agbp,
  67                         XFS_AGF_REFCOUNT_ROOT | XFS_AGF_REFCOUNT_LEVEL);
  68 }
  69
  70 STATIC int
  71 xfs_refcountbt_alloc_block(
  72         struct xfs_btree_cur    *cur,
  73         union xfs_btree_ptr     *start,
  74         union xfs_btree_ptr     *new,
  75         int                     *stat)
  76 {
  77         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
  78         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
  79         struct xfs_alloc_arg    args;           /* block allocation args */
  80         int                     error;          /* error return value */
  81
  82         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
  83
  84         memset(&args, 0, sizeof(args));
  85         args.tp = cur->bc_tp;
  86         args.mp = cur->bc_mp;
  87         args.type = XFS_ALLOCTYPE_NEAR_BNO;
  88         args.fsbno = XFS_AGB_TO_FSB(cur->bc_mp, cur->bc_private.a.agno,
  89                         xfs_refc_block(args.mp));
  90         args.firstblock = args.fsbno;
  91         xfs_rmap_ag_owner(&args.oinfo, XFS_RMAP_OWN_REFC);
  92         args.minlen = args.maxlen = args.prod = 1;
  93         args.resv = XFS_AG_RESV_METADATA;
  94
  95         error = xfs_alloc_vextent(&args);
  96         if (error)
  97                 goto out_error;
  98         trace_xfs_refcountbt_alloc_block(cur->bc_mp, cur->bc_private.a.agno,
  99                         args.agbno, 1);
 100         if (args.fsbno == NULLFSBLOCK) {
 101                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 102                 *stat = 0;
 103                 return 0;
 104         }
 105         ASSERT(args.agno == cur->bc_private.a.agno);
 106         ASSERT(args.len == 1);
 107
 108         new->s = cpu_to_be32(args.agbno);
 109         be32_add_cpu(&agf->agf_refcount_blocks, 1);
 110         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
 111
 112         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 113         *stat = 1;
 114         return 0;
 115
 116 out_error:
 117         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 118         return error;
 119 }
 120
 121 STATIC int
 122 xfs_refcountbt_free_block(
 123         struct xfs_btree_cur    *cur,
 124         struct xfs_buf          *bp)
 125 {
 126         struct xfs_mount        *mp = cur->bc_mp;
 127         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
 128         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 129         xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
 130         struct xfs_owner_info   oinfo;
 131         int                     error;
 132
 133         trace_xfs_refcountbt_free_block(cur->bc_mp, cur->bc_private.a.agno,
 134                         XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno), 1);
 135         xfs_rmap_ag_owner(&oinfo, XFS_RMAP_OWN_REFC);
 136         be32_add_cpu(&agf->agf_refcount_blocks, -1);
 137         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
 138         error = xfs_free_extent(cur->bc_tp, fsbno, 1, &oinfo,
 139                         XFS_AG_RESV_METADATA);
 140         if (error)
 141                 return error;
 142
 143         return error;
 144 }
 145
 146 STATIC int
 147 xfs_refcountbt_get_minrecs(
 148         struct xfs_btree_cur    *cur,
 149         int                     level)
 150 {
 151         return cur->bc_mp->m_refc_mnr[level != 0];
 152 }
 153
 154 STATIC int
 155 xfs_refcountbt_get_maxrecs(
 156         struct xfs_btree_cur    *cur,
 157         int                     level)
 158 {
 159         return cur->bc_mp->m_refc_mxr[level != 0];
 160 }
 161
 162 STATIC void
 163 xfs_refcountbt_init_key_from_rec(
 164         union xfs_btree_key     *key,
 165         union xfs_btree_rec     *rec)
 166 {
 167         key->refc.rc_startblock = rec->refc.rc_startblock;
 168 }
 169
 170 STATIC void
 171 xfs_refcountbt_init_high_key_from_rec(
 172         union xfs_btree_key     *key,
 173         union xfs_btree_rec     *rec)
 174 {
 175         __u32                   x;
 176
 177         x = be32_to_cpu(rec->refc.rc_startblock);
 178         x += be32_to_cpu(rec->refc.rc_blockcount) - 1;
 179         key->refc.rc_startblock = cpu_to_be32(x);
 180 }
 181
 182 STATIC void
 183 xfs_refcountbt_init_rec_from_cur(
 184         struct xfs_btree_cur    *cur,
 185         union xfs_btree_rec     *rec)
 186 {
 187         rec->refc.rc_startblock = cpu_to_be32(cur->bc_rec.rc.rc_startblock);
 188         rec->refc.rc_blockcount = cpu_to_be32(cur->bc_rec.rc.rc_blockcount);
 189         rec->refc.rc_refcount = cpu_to_be32(cur->bc_rec.rc.rc_refcount);
 190 }
 191
 192 STATIC void
 193 xfs_refcountbt_init_ptr_from_cur(
 194         struct xfs_btree_cur    *cur,
 195         union xfs_btree_ptr     *ptr)
 196 {
 197         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 198
 199         ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
 200         ASSERT(agf->agf_refcount_root != 0);
 201
 202         ptr->s = agf->agf_refcount_root;
 203 }
 204
 205 STATIC int64_t
 206 xfs_refcountbt_key_diff(
 207         struct xfs_btree_cur    *cur,
 208         union xfs_btree_key     *key)
 209 {
 210         struct xfs_refcount_irec        *rec = &cur->bc_rec.rc;
 211         struct xfs_refcount_key         *kp = &key->refc;
 212
 213         return (int64_t)be32_to_cpu(kp->rc_startblock) - rec->rc_startblock;
 214 }
 215
 216 STATIC int64_t
 217 xfs_refcountbt_diff_two_keys(
 218         struct xfs_btree_cur    *cur,
 219         union xfs_btree_key     *k1,
 220         union xfs_btree_key     *k2)
 221 {
 222         return (int64_t)be32_to_cpu(k1->refc.rc_startblock) -
 223                           be32_to_cpu(k2->refc.rc_startblock);
 224 }
 225
 226 STATIC bool
 227 xfs_refcountbt_verify(
 228         struct xfs_buf          *bp)
 229 {
 230         struct xfs_mount        *mp = bp->b_target->bt_mount;
 231         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 232         struct xfs_perag        *pag = bp->b_pag;
 233         unsigned int            level;
 234
 235         if (block->bb_magic != cpu_to_be32(XFS_REFC_CRC_MAGIC))
 236                 return false;
 237
 238         if (!xfs_sb_version_hasreflink(&mp->m_sb))
 239                 return false;
 240         if (!xfs_btree_sblock_v5hdr_verify(bp))
 241                 return false;
 242
 243         level = be16_to_cpu(block->bb_level);
 244         if (pag && pag->pagf_init) {
 245                 if (level >= pag->pagf_refcount_level)
 246                         return false;
 247         } else if (level >= mp->m_refc_maxlevels)
 248                 return false;
 249
 250         return xfs_btree_sblock_verify(bp, mp->m_refc_mxr[level != 0]);
 251 }
 252
 253 STATIC void
 254 xfs_refcountbt_read_verify(
 255         struct xfs_buf  *bp)
 256 {
 257         if (!xfs_btree_sblock_verify_crc(bp))
 258                 xfs_buf_ioerror(bp, -EFSBADCRC);
 259         else if (!xfs_refcountbt_verify(bp))
 260                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 261
 262         if (bp->b_error) {
 263                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 264                 xfs_verifier_error(bp);
 265         }
 266 }
 267
 268 STATIC void
 269 xfs_refcountbt_write_verify(
 270         struct xfs_buf  *bp)
 271 {
 272         if (!xfs_refcountbt_verify(bp)) {
 273                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 274                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 275                 xfs_verifier_error(bp);
 276                 return;
 277         }
 278         xfs_btree_sblock_calc_crc(bp);
 279
 280 }
 281
 282 const struct xfs_buf_ops xfs_refcountbt_buf_ops = {
 283         .name                   = "xfs_refcountbt",
 284         .verify_read            = xfs_refcountbt_read_verify,
 285         .verify_write           = xfs_refcountbt_write_verify,
 286 };
 287
 288 STATIC int
 289 xfs_refcountbt_keys_inorder(
 290         struct xfs_btree_cur    *cur,
 291         union xfs_btree_key     *k1,
 292         union xfs_btree_key     *k2)
 293 {
 294         return be32_to_cpu(k1->refc.rc_startblock) <
 295                be32_to_cpu(k2->refc.rc_startblock);
 296 }
 297
 298 STATIC int
 299 xfs_refcountbt_recs_inorder(
 300         struct xfs_btree_cur    *cur,
 301         union xfs_btree_rec     *r1,
 302         union xfs_btree_rec     *r2)
 303 {
 304         return  be32_to_cpu(r1->refc.rc_startblock) +
 305                 be32_to_cpu(r1->refc.rc_blockcount) <=
 306                 be32_to_cpu(r2->refc.rc_startblock);
 307 }
 308
 309 static const struct xfs_btree_ops xfs_refcountbt_ops = {
 310         .rec_len                = sizeof(struct xfs_refcount_rec),
 311         .key_len                = sizeof(struct xfs_refcount_key),
 312
 313         .dup_cursor             = xfs_refcountbt_dup_cursor,
 314         .set_root               = xfs_refcountbt_set_root,
 315         .alloc_block            = xfs_refcountbt_alloc_block,
 316         .free_block             = xfs_refcountbt_free_block,
 317         .get_minrecs            = xfs_refcountbt_get_minrecs,
 318         .get_maxrecs            = xfs_refcountbt_get_maxrecs,
 319         .init_key_from_rec      = xfs_refcountbt_init_key_from_rec,
 320         .init_high_key_from_rec = xfs_refcountbt_init_high_key_from_rec,
 321         .init_rec_from_cur      = xfs_refcountbt_init_rec_from_cur,
 322         .init_ptr_from_cur      = xfs_refcountbt_init_ptr_from_cur,
 323         .key_diff               = xfs_refcountbt_key_diff,
 324         .buf_ops                = &xfs_refcountbt_buf_ops,
 325         .diff_two_keys          = xfs_refcountbt_diff_two_keys,
 326         .keys_inorder           = xfs_refcountbt_keys_inorder,
 327         .recs_inorder           = xfs_refcountbt_recs_inorder,
 328 };
 329
 330 /*
 331  * Allocate a new refcount btree cursor.
 332  */
 333 struct xfs_btree_cur *
 334 xfs_refcountbt_init_cursor(
 335         struct xfs_mount        *mp,
 336         struct xfs_trans        *tp,
 337         struct xfs_buf          *agbp,
 338         xfs_agnumber_t          agno,
 339         struct xfs_defer_ops    *dfops)
 340 {
 341         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 342         struct xfs_btree_cur    *cur;
 343
 344         ASSERT(agno != NULLAGNUMBER);
 345         ASSERT(agno < mp->m_sb.sb_agcount);
 346         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
 347
 348         cur->bc_tp = tp;
 349         cur->bc_mp = mp;
 350         cur->bc_btnum = XFS_BTNUM_REFC;
 351         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 352         cur->bc_ops = &xfs_refcountbt_ops;
 353         cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_refcbt_2);
 354
 355         cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level);
 356
 357         cur->bc_private.a.agbp = agbp;
 358         cur->bc_private.a.agno = agno;
 359         cur->bc_private.a.dfops = dfops;
 360         cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 361
 362         cur->bc_private.a.priv.refc.nr_ops = 0;
 363         cur->bc_private.a.priv.refc.shape_changes = 0;
 364
 365         return cur;
 366 }
 367
 368 /*
 369  * Calculate the number of records in a refcount btree block.
 370  */
 371 int
 372 xfs_refcountbt_maxrecs(
 373         struct xfs_mount        *mp,
 374         int                     blocklen,
 375         bool                    leaf)
 376 {
 377         blocklen -= XFS_REFCOUNT_BLOCK_LEN;
 378
 379         if (leaf)
 380                 return blocklen / sizeof(struct xfs_refcount_rec);
 381         return blocklen / (sizeof(struct xfs_refcount_key) +
 382                            sizeof(xfs_refcount_ptr_t));
 383 }
 384
 385 /* Compute the maximum height of a refcount btree. */
 386 void
 387 xfs_refcountbt_compute_maxlevels(
 388         struct xfs_mount                *mp)
 389 {
 390         mp->m_refc_maxlevels = xfs_btree_compute_maxlevels(mp,
 391                         mp->m_refc_mnr, mp->m_sb.sb_agblocks);
 392 }
 393
 394 /* Calculate the refcount btree size for some records. */
 395 xfs_extlen_t
 396 xfs_refcountbt_calc_size(
 397         struct xfs_mount        *mp,
 398         unsigned long long      len)
 399 {
 400         return xfs_btree_calc_size(mp, mp->m_refc_mnr, len);
 401 }
 402
 403 /*
 404  * Calculate the maximum refcount btree size.
 405  */
 406 xfs_extlen_t
 407 xfs_refcountbt_max_size(
 408         struct xfs_mount        *mp,
 409         xfs_agblock_t           agblocks)
 410 {
 411         /* Bail out if we're uninitialized, which can happen in mkfs. */
 412         if (mp->m_refc_mxr[0] == 0)
 413                 return 0;
 414
 415         return xfs_refcountbt_calc_size(mp, agblocks);
 416 }
 417
 418 /*
 419  * Figure out how many blocks to reserve and how many are used by this btree.
 420  */
 421 int
 422 xfs_refcountbt_calc_reserves(
 423         struct xfs_mount        *mp,
 424         xfs_agnumber_t          agno,
 425         xfs_extlen_t            *ask,
 426         xfs_extlen_t            *used)
 427 {
 428         struct xfs_buf          *agbp;
 429         struct xfs_agf          *agf;
 430         xfs_agblock_t           agblocks;
 431         xfs_extlen_t            tree_len;
 432         int                     error;
 433
 434         if (!xfs_sb_version_hasreflink(&mp->m_sb))
 435                 return 0;
 436
 437
 438         error = xfs_alloc_read_agf(mp, NULL, agno, 0, &agbp);
 439         if (error)
 440                 return error;
 441
 442         agf = XFS_BUF_TO_AGF(agbp);
 443         agblocks = be32_to_cpu(agf->agf_length);
 444         tree_len = be32_to_cpu(agf->agf_refcount_blocks);
 445         xfs_buf_relse(agbp);
 446
 447         *ask += xfs_refcountbt_max_size(mp, agblocks);
 448         *used += tree_len;
 449
 450         return error;
 451 }