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         memset(&args, 0, sizeof(args));
  82         args.tp = cur->bc_tp;
  83         args.mp = cur->bc_mp;
  84         args.type = XFS_ALLOCTYPE_NEAR_BNO;
  85         args.fsbno = XFS_AGB_TO_FSB(cur->bc_mp, cur->bc_private.a.agno,
  86                         xfs_refc_block(args.mp));
  87         args.firstblock = args.fsbno;
  88         xfs_rmap_ag_owner(&args.oinfo, XFS_RMAP_OWN_REFC);
  89         args.minlen = args.maxlen = args.prod = 1;
  90
  91         error = xfs_alloc_vextent(&args);
  92         if (error)
  93                 goto out_error;
  94         trace_xfs_refcountbt_alloc_block(cur->bc_mp, cur->bc_private.a.agno,
  95                         args.agbno, 1);
  96         if (args.fsbno == NULLFSBLOCK) {
  97                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
  98                 *stat = 0;
  99                 return 0;
 100         }
 101         ASSERT(args.agno == cur->bc_private.a.agno);
 102         ASSERT(args.len == 1);
 103
 104         new->s = cpu_to_be32(args.agbno);
 105         be32_add_cpu(&agf->agf_refcount_blocks, 1);
 106         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
 107
 108         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 109         *stat = 1;
 110         return 0;
 111
 112 out_error:
 113         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 114         return error;
 115 }
 116
 117 STATIC int
 118 xfs_refcountbt_free_block(
 119         struct xfs_btree_cur    *cur,
 120         struct xfs_buf          *bp)
 121 {
 122         struct xfs_mount        *mp = cur->bc_mp;
 123         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
 124         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 125         xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
 126         struct xfs_owner_info   oinfo;
 127
 128         trace_xfs_refcountbt_free_block(cur->bc_mp, cur->bc_private.a.agno,
 129                         XFS_FSB_TO_AGBNO(cur->bc_mp, fsbno), 1);
 130         xfs_rmap_ag_owner(&oinfo, XFS_RMAP_OWN_REFC);
 131         be32_add_cpu(&agf->agf_refcount_blocks, -1);
 132         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_REFCOUNT_BLOCKS);
 133         xfs_bmap_add_free(mp, cur->bc_private.a.dfops, fsbno, 1,
 134                         &oinfo);
 135
 136         return 0;
 137 }
 138
 139 STATIC int
 140 xfs_refcountbt_get_minrecs(
 141         struct xfs_btree_cur    *cur,
 142         int                     level)
 143 {
 144         return cur->bc_mp->m_refc_mnr[level != 0];
 145 }
 146
 147 STATIC int
 148 xfs_refcountbt_get_maxrecs(
 149         struct xfs_btree_cur    *cur,
 150         int                     level)
 151 {
 152         return cur->bc_mp->m_refc_mxr[level != 0];
 153 }
 154
 155 STATIC void
 156 xfs_refcountbt_init_key_from_rec(
 157         union xfs_btree_key     *key,
 158         union xfs_btree_rec     *rec)
 159 {
 160         key->refc.rc_startblock = rec->refc.rc_startblock;
 161 }
 162
 163 STATIC void
 164 xfs_refcountbt_init_high_key_from_rec(
 165         union xfs_btree_key     *key,
 166         union xfs_btree_rec     *rec)
 167 {
 168         __u32                   x;
 169
 170         x = be32_to_cpu(rec->refc.rc_startblock);
 171         x += be32_to_cpu(rec->refc.rc_blockcount) - 1;
 172         key->refc.rc_startblock = cpu_to_be32(x);
 173 }
 174
 175 STATIC void
 176 xfs_refcountbt_init_rec_from_cur(
 177         struct xfs_btree_cur    *cur,
 178         union xfs_btree_rec     *rec)
 179 {
 180         rec->refc.rc_startblock = cpu_to_be32(cur->bc_rec.rc.rc_startblock);
 181         rec->refc.rc_blockcount = cpu_to_be32(cur->bc_rec.rc.rc_blockcount);
 182         rec->refc.rc_refcount = cpu_to_be32(cur->bc_rec.rc.rc_refcount);
 183 }
 184
 185 STATIC void
 186 xfs_refcountbt_init_ptr_from_cur(
 187         struct xfs_btree_cur    *cur,
 188         union xfs_btree_ptr     *ptr)
 189 {
 190         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 191
 192         ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
 193         ASSERT(agf->agf_refcount_root != 0);
 194
 195         ptr->s = agf->agf_refcount_root;
 196 }
 197
 198 STATIC __int64_t
 199 xfs_refcountbt_key_diff(
 200         struct xfs_btree_cur    *cur,
 201         union xfs_btree_key     *key)
 202 {
 203         struct xfs_refcount_irec        *rec = &cur->bc_rec.rc;
 204         struct xfs_refcount_key         *kp = &key->refc;
 205
 206         return (__int64_t)be32_to_cpu(kp->rc_startblock) - rec->rc_startblock;
 207 }
 208
 209 STATIC __int64_t
 210 xfs_refcountbt_diff_two_keys(
 211         struct xfs_btree_cur    *cur,
 212         union xfs_btree_key     *k1,
 213         union xfs_btree_key     *k2)
 214 {
 215         return (__int64_t)be32_to_cpu(k1->refc.rc_startblock) -
 216                           be32_to_cpu(k2->refc.rc_startblock);
 217 }
 218
 219 STATIC bool
 220 xfs_refcountbt_verify(
 221         struct xfs_buf          *bp)
 222 {
 223         struct xfs_mount        *mp = bp->b_target->bt_mount;
 224         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 225         struct xfs_perag        *pag = bp->b_pag;
 226         unsigned int            level;
 227
 228         if (block->bb_magic != cpu_to_be32(XFS_REFC_CRC_MAGIC))
 229                 return false;
 230
 231         if (!xfs_sb_version_hasreflink(&mp->m_sb))
 232                 return false;
 233         if (!xfs_btree_sblock_v5hdr_verify(bp))
 234                 return false;
 235
 236         level = be16_to_cpu(block->bb_level);
 237         if (pag && pag->pagf_init) {
 238                 if (level >= pag->pagf_refcount_level)
 239                         return false;
 240         } else if (level >= mp->m_refc_maxlevels)
 241                 return false;
 242
 243         return xfs_btree_sblock_verify(bp, mp->m_refc_mxr[level != 0]);
 244 }
 245
 246 STATIC void
 247 xfs_refcountbt_read_verify(
 248         struct xfs_buf  *bp)
 249 {
 250         if (!xfs_btree_sblock_verify_crc(bp))
 251                 xfs_buf_ioerror(bp, -EFSBADCRC);
 252         else if (!xfs_refcountbt_verify(bp))
 253                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 254
 255         if (bp->b_error) {
 256                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 257                 xfs_verifier_error(bp);
 258         }
 259 }
 260
 261 STATIC void
 262 xfs_refcountbt_write_verify(
 263         struct xfs_buf  *bp)
 264 {
 265         if (!xfs_refcountbt_verify(bp)) {
 266                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 267                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 268                 xfs_verifier_error(bp);
 269                 return;
 270         }
 271         xfs_btree_sblock_calc_crc(bp);
 272
 273 }
 274
 275 const struct xfs_buf_ops xfs_refcountbt_buf_ops = {
 276         .name                   = "xfs_refcountbt",
 277         .verify_read            = xfs_refcountbt_read_verify,
 278         .verify_write           = xfs_refcountbt_write_verify,
 279 };
 280
 281 #if defined(DEBUG) || defined(XFS_WARN)
 282 STATIC int
 283 xfs_refcountbt_keys_inorder(
 284         struct xfs_btree_cur    *cur,
 285         union xfs_btree_key     *k1,
 286         union xfs_btree_key     *k2)
 287 {
 288         return be32_to_cpu(k1->refc.rc_startblock) <
 289                be32_to_cpu(k2->refc.rc_startblock);
 290 }
 291
 292 STATIC int
 293 xfs_refcountbt_recs_inorder(
 294         struct xfs_btree_cur    *cur,
 295         union xfs_btree_rec     *r1,
 296         union xfs_btree_rec     *r2)
 297 {
 298         return  be32_to_cpu(r1->refc.rc_startblock) +
 299                 be32_to_cpu(r1->refc.rc_blockcount) <=
 300                 be32_to_cpu(r2->refc.rc_startblock);
 301 }
 302 #endif
 303
 304 static const struct xfs_btree_ops xfs_refcountbt_ops = {
 305         .rec_len                = sizeof(struct xfs_refcount_rec),
 306         .key_len                = sizeof(struct xfs_refcount_key),
 307
 308         .dup_cursor             = xfs_refcountbt_dup_cursor,
 309         .set_root               = xfs_refcountbt_set_root,
 310         .alloc_block            = xfs_refcountbt_alloc_block,
 311         .free_block             = xfs_refcountbt_free_block,
 312         .get_minrecs            = xfs_refcountbt_get_minrecs,
 313         .get_maxrecs            = xfs_refcountbt_get_maxrecs,
 314         .init_key_from_rec      = xfs_refcountbt_init_key_from_rec,
 315         .init_high_key_from_rec = xfs_refcountbt_init_high_key_from_rec,
 316         .init_rec_from_cur      = xfs_refcountbt_init_rec_from_cur,
 317         .init_ptr_from_cur      = xfs_refcountbt_init_ptr_from_cur,
 318         .key_diff               = xfs_refcountbt_key_diff,
 319         .buf_ops                = &xfs_refcountbt_buf_ops,
 320         .diff_two_keys          = xfs_refcountbt_diff_two_keys,
 321 #if defined(DEBUG) || defined(XFS_WARN)
 322         .keys_inorder           = xfs_refcountbt_keys_inorder,
 323         .recs_inorder           = xfs_refcountbt_recs_inorder,
 324 #endif
 325 };
 326
 327 /*
 328  * Allocate a new refcount btree cursor.
 329  */
 330 struct xfs_btree_cur *
 331 xfs_refcountbt_init_cursor(
 332         struct xfs_mount        *mp,
 333         struct xfs_trans        *tp,
 334         struct xfs_buf          *agbp,
 335         xfs_agnumber_t          agno,
 336         struct xfs_defer_ops    *dfops)
 337 {
 338         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 339         struct xfs_btree_cur    *cur;
 340
 341         ASSERT(agno != NULLAGNUMBER);
 342         ASSERT(agno < mp->m_sb.sb_agcount);
 343         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
 344
 345         cur->bc_tp = tp;
 346         cur->bc_mp = mp;
 347         cur->bc_btnum = XFS_BTNUM_REFC;
 348         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 349         cur->bc_ops = &xfs_refcountbt_ops;
 350
 351         cur->bc_nlevels = be32_to_cpu(agf->agf_refcount_level);
 352
 353         cur->bc_private.a.agbp = agbp;
 354         cur->bc_private.a.agno = agno;
 355         cur->bc_private.a.dfops = dfops;
 356         cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 357
 358         cur->bc_private.a.priv.refc.nr_ops = 0;
 359         cur->bc_private.a.priv.refc.shape_changes = 0;
 360
 361         return cur;
 362 }
 363
 364 /*
 365  * Calculate the number of records in a refcount btree block.
 366  */
 367 int
 368 xfs_refcountbt_maxrecs(
 369         struct xfs_mount        *mp,
 370         int                     blocklen,
 371         bool                    leaf)
 372 {
 373         blocklen -= XFS_REFCOUNT_BLOCK_LEN;
 374
 375         if (leaf)
 376                 return blocklen / sizeof(struct xfs_refcount_rec);
 377         return blocklen / (sizeof(struct xfs_refcount_key) +
 378                            sizeof(xfs_refcount_ptr_t));
 379 }
 380
 381 /* Compute the maximum height of a refcount btree. */
 382 void
 383 xfs_refcountbt_compute_maxlevels(
 384         struct xfs_mount                *mp)
 385 {
 386         mp->m_refc_maxlevels = xfs_btree_compute_maxlevels(mp,
 387                         mp->m_refc_mnr, mp->m_sb.sb_agblocks);
 388 }