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