libxfs/xfs_alloc_btree.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6 #include "libxfs_priv.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_alloc_btree.h"
  16 #include "xfs_alloc.h"
  17 #include "xfs_trace.h"
  18 #include "xfs_cksum.h"
  19 #include "xfs_trans.h"
  20
  21
  22 STATIC struct xfs_btree_cur *
  23 xfs_allocbt_dup_cursor(
  24         struct xfs_btree_cur    *cur)
  25 {
  26         return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp,
  27                         cur->bc_private.a.agbp, cur->bc_private.a.agno,
  28                         cur->bc_btnum);
  29 }
  30
  31 STATIC void
  32 xfs_allocbt_set_root(
  33         struct xfs_btree_cur    *cur,
  34         union xfs_btree_ptr     *ptr,
  35         int                     inc)
  36 {
  37         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
  38         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
  39         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
  40         int                     btnum = cur->bc_btnum;
  41         struct xfs_perag        *pag = xfs_perag_get(cur->bc_mp, seqno);
  42
  43         ASSERT(ptr->s != 0);
  44
  45         agf->agf_roots[btnum] = ptr->s;
  46         be32_add_cpu(&agf->agf_levels[btnum], inc);
  47         pag->pagf_levels[btnum] += inc;
  48         xfs_perag_put(pag);
  49
  50         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
  51 }
  52
  53 STATIC int
  54 xfs_allocbt_alloc_block(
  55         struct xfs_btree_cur    *cur,
  56         union xfs_btree_ptr     *start,
  57         union xfs_btree_ptr     *new,
  58         int                     *stat)
  59 {
  60         int                     error;
  61         xfs_agblock_t           bno;
  62
  63         /* Allocate the new block from the freelist. If we can't, give up.  */
  64         error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
  65                                        &bno, 1);
  66         if (error)
  67                 return error;
  68
  69         if (bno == NULLAGBLOCK) {
  70                 *stat = 0;
  71                 return 0;
  72         }
  73
  74         xfs_extent_busy_reuse(cur->bc_mp, cur->bc_private.a.agno, bno, 1, false);
  75
  76         xfs_trans_agbtree_delta(cur->bc_tp, 1);
  77         new->s = cpu_to_be32(bno);
  78
  79         *stat = 1;
  80         return 0;
  81 }
  82
  83 STATIC int
  84 xfs_allocbt_free_block(
  85         struct xfs_btree_cur    *cur,
  86         struct xfs_buf          *bp)
  87 {
  88         struct xfs_buf          *agbp = cur->bc_private.a.agbp;
  89         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
  90         xfs_agblock_t           bno;
  91         int                     error;
  92
  93         bno = xfs_daddr_to_agbno(cur->bc_mp, XFS_BUF_ADDR(bp));
  94         error = xfs_alloc_put_freelist(cur->bc_tp, agbp, NULL, bno, 1);
  95         if (error)
  96                 return error;
  97
  98         xfs_extent_busy_insert(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1,
  99                               XFS_EXTENT_BUSY_SKIP_DISCARD);
 100         xfs_trans_agbtree_delta(cur->bc_tp, -1);
 101         return 0;
 102 }
 103
 104 /*
 105  * Update the longest extent in the AGF
 106  */
 107 STATIC void
 108 xfs_allocbt_update_lastrec(
 109         struct xfs_btree_cur    *cur,
 110         struct xfs_btree_block  *block,
 111         union xfs_btree_rec     *rec,
 112         int                     ptr,
 113         int                     reason)
 114 {
 115         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 116         xfs_agnumber_t          seqno = be32_to_cpu(agf->agf_seqno);
 117         struct xfs_perag        *pag;
 118         __be32                  len;
 119         int                     numrecs;
 120
 121         ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);
 122
 123         switch (reason) {
 124         case LASTREC_UPDATE:
 125                 /*
 126                  * If this is the last leaf block and it's the last record,
 127                  * then update the size of the longest extent in the AG.
 128                  */
 129                 if (ptr != xfs_btree_get_numrecs(block))
 130                         return;
 131                 len = rec->alloc.ar_blockcount;
 132                 break;
 133         case LASTREC_INSREC:
 134                 if (be32_to_cpu(rec->alloc.ar_blockcount) <=
 135                     be32_to_cpu(agf->agf_longest))
 136                         return;
 137                 len = rec->alloc.ar_blockcount;
 138                 break;
 139         case LASTREC_DELREC:
 140                 numrecs = xfs_btree_get_numrecs(block);
 141                 if (ptr <= numrecs)
 142                         return;
 143                 ASSERT(ptr == numrecs + 1);
 144
 145                 if (numrecs) {
 146                         xfs_alloc_rec_t *rrp;
 147
 148                         rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs);
 149                         len = rrp->ar_blockcount;
 150                 } else {
 151                         len = 0;
 152                 }
 153
 154                 break;
 155         default:
 156                 ASSERT(0);
 157                 return;
 158         }
 159
 160         agf->agf_longest = len;
 161         pag = xfs_perag_get(cur->bc_mp, seqno);
 162         pag->pagf_longest = be32_to_cpu(len);
 163         xfs_perag_put(pag);
 164         xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp, XFS_AGF_LONGEST);
 165 }
 166
 167 STATIC int
 168 xfs_allocbt_get_minrecs(
 169         struct xfs_btree_cur    *cur,
 170         int                     level)
 171 {
 172         return cur->bc_mp->m_alloc_mnr[level != 0];
 173 }
 174
 175 STATIC int
 176 xfs_allocbt_get_maxrecs(
 177         struct xfs_btree_cur    *cur,
 178         int                     level)
 179 {
 180         return cur->bc_mp->m_alloc_mxr[level != 0];
 181 }
 182
 183 STATIC void
 184 xfs_allocbt_init_key_from_rec(
 185         union xfs_btree_key     *key,
 186         union xfs_btree_rec     *rec)
 187 {
 188         key->alloc.ar_startblock = rec->alloc.ar_startblock;
 189         key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
 190 }
 191
 192 STATIC void
 193 xfs_bnobt_init_high_key_from_rec(
 194         union xfs_btree_key     *key,
 195         union xfs_btree_rec     *rec)
 196 {
 197         __u32                   x;
 198
 199         x = be32_to_cpu(rec->alloc.ar_startblock);
 200         x += be32_to_cpu(rec->alloc.ar_blockcount) - 1;
 201         key->alloc.ar_startblock = cpu_to_be32(x);
 202         key->alloc.ar_blockcount = 0;
 203 }
 204
 205 STATIC void
 206 xfs_cntbt_init_high_key_from_rec(
 207         union xfs_btree_key     *key,
 208         union xfs_btree_rec     *rec)
 209 {
 210         key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
 211         key->alloc.ar_startblock = 0;
 212 }
 213
 214 STATIC void
 215 xfs_allocbt_init_rec_from_cur(
 216         struct xfs_btree_cur    *cur,
 217         union xfs_btree_rec     *rec)
 218 {
 219         rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
 220         rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
 221 }
 222
 223 STATIC void
 224 xfs_allocbt_init_ptr_from_cur(
 225         struct xfs_btree_cur    *cur,
 226         union xfs_btree_ptr     *ptr)
 227 {
 228         struct xfs_agf          *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
 229
 230         ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
 231
 232         ptr->s = agf->agf_roots[cur->bc_btnum];
 233 }
 234
 235 STATIC int64_t
 236 xfs_bnobt_key_diff(
 237         struct xfs_btree_cur    *cur,
 238         union xfs_btree_key     *key)
 239 {
 240         xfs_alloc_rec_incore_t  *rec = &cur->bc_rec.a;
 241         xfs_alloc_key_t         *kp = &key->alloc;
 242
 243         return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
 244 }
 245
 246 STATIC int64_t
 247 xfs_cntbt_key_diff(
 248         struct xfs_btree_cur    *cur,
 249         union xfs_btree_key     *key)
 250 {
 251         xfs_alloc_rec_incore_t  *rec = &cur->bc_rec.a;
 252         xfs_alloc_key_t         *kp = &key->alloc;
 253         int64_t                 diff;
 254
 255         diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
 256         if (diff)
 257                 return diff;
 258
 259         return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
 260 }
 261
 262 STATIC int64_t
 263 xfs_bnobt_diff_two_keys(
 264         struct xfs_btree_cur    *cur,
 265         union xfs_btree_key     *k1,
 266         union xfs_btree_key     *k2)
 267 {
 268         return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) -
 269                           be32_to_cpu(k2->alloc.ar_startblock);
 270 }
 271
 272 STATIC int64_t
 273 xfs_cntbt_diff_two_keys(
 274         struct xfs_btree_cur    *cur,
 275         union xfs_btree_key     *k1,
 276         union xfs_btree_key     *k2)
 277 {
 278         int64_t                 diff;
 279
 280         diff =  be32_to_cpu(k1->alloc.ar_blockcount) -
 281                 be32_to_cpu(k2->alloc.ar_blockcount);
 282         if (diff)
 283                 return diff;
 284
 285         return  be32_to_cpu(k1->alloc.ar_startblock) -
 286                 be32_to_cpu(k2->alloc.ar_startblock);
 287 }
 288
 289 static xfs_failaddr_t
 290 xfs_allocbt_verify(
 291         struct xfs_buf          *bp)
 292 {
 293         struct xfs_mount        *mp = bp->b_target->bt_mount;
 294         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 295         struct xfs_perag        *pag = bp->b_pag;
 296         xfs_failaddr_t          fa;
 297         unsigned int            level;
 298
 299         /*
 300          * magic number and level verification
 301          *
 302          * During growfs operations, we can't verify the exact level or owner as
 303          * the perag is not fully initialised and hence not attached to the
 304          * buffer.  In this case, check against the maximum tree depth.
 305          *
 306          * Similarly, during log recovery we will have a perag structure
 307          * attached, but the agf information will not yet have been initialised
 308          * from the on disk AGF. Again, we can only check against maximum limits
 309          * in this case.
 310          */
 311         level = be16_to_cpu(block->bb_level);
 312         switch (block->bb_magic) {
 313         case cpu_to_be32(XFS_ABTB_CRC_MAGIC):
 314                 fa = xfs_btree_sblock_v5hdr_verify(bp);
 315                 if (fa)
 316                         return fa;
 317                 /* fall through */
 318         case cpu_to_be32(XFS_ABTB_MAGIC):
 319                 if (pag && pag->pagf_init) {
 320                         if (level >= pag->pagf_levels[XFS_BTNUM_BNOi])
 321                                 return __this_address;
 322                 } else if (level >= mp->m_ag_maxlevels)
 323                         return __this_address;
 324                 break;
 325         case cpu_to_be32(XFS_ABTC_CRC_MAGIC):
 326                 fa = xfs_btree_sblock_v5hdr_verify(bp);
 327                 if (fa)
 328                         return fa;
 329                 /* fall through */
 330         case cpu_to_be32(XFS_ABTC_MAGIC):
 331                 if (pag && pag->pagf_init) {
 332                         if (level >= pag->pagf_levels[XFS_BTNUM_CNTi])
 333                                 return __this_address;
 334                 } else if (level >= mp->m_ag_maxlevels)
 335                         return __this_address;
 336                 break;
 337         default:
 338                 return __this_address;
 339         }
 340
 341         return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]);
 342 }
 343
 344 static void
 345 xfs_allocbt_read_verify(
 346         struct xfs_buf  *bp)
 347 {
 348         xfs_failaddr_t  fa;
 349
 350         if (!xfs_btree_sblock_verify_crc(bp))
 351                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 352         else {
 353                 fa = xfs_allocbt_verify(bp);
 354                 if (fa)
 355                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 356         }
 357
 358         if (bp->b_error)
 359                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 360 }
 361
 362 static void
 363 xfs_allocbt_write_verify(
 364         struct xfs_buf  *bp)
 365 {
 366         xfs_failaddr_t  fa;
 367
 368         fa = xfs_allocbt_verify(bp);
 369         if (fa) {
 370                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 371                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 372                 return;
 373         }
 374         xfs_btree_sblock_calc_crc(bp);
 375
 376 }
 377
 378 const struct xfs_buf_ops xfs_allocbt_buf_ops = {
 379         .name = "xfs_allocbt",
 380         .verify_read = xfs_allocbt_read_verify,
 381         .verify_write = xfs_allocbt_write_verify,
 382         .verify_struct = xfs_allocbt_verify,
 383 };
 384
 385
 386 STATIC int
 387 xfs_bnobt_keys_inorder(
 388         struct xfs_btree_cur    *cur,
 389         union xfs_btree_key     *k1,
 390         union xfs_btree_key     *k2)
 391 {
 392         return be32_to_cpu(k1->alloc.ar_startblock) <
 393                be32_to_cpu(k2->alloc.ar_startblock);
 394 }
 395
 396 STATIC int
 397 xfs_bnobt_recs_inorder(
 398         struct xfs_btree_cur    *cur,
 399         union xfs_btree_rec     *r1,
 400         union xfs_btree_rec     *r2)
 401 {
 402         return be32_to_cpu(r1->alloc.ar_startblock) +
 403                 be32_to_cpu(r1->alloc.ar_blockcount) <=
 404                 be32_to_cpu(r2->alloc.ar_startblock);
 405 }
 406
 407 STATIC int
 408 xfs_cntbt_keys_inorder(
 409         struct xfs_btree_cur    *cur,
 410         union xfs_btree_key     *k1,
 411         union xfs_btree_key     *k2)
 412 {
 413         return be32_to_cpu(k1->alloc.ar_blockcount) <
 414                 be32_to_cpu(k2->alloc.ar_blockcount) ||
 415                 (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount &&
 416                  be32_to_cpu(k1->alloc.ar_startblock) <
 417                  be32_to_cpu(k2->alloc.ar_startblock));
 418 }
 419
 420 STATIC int
 421 xfs_cntbt_recs_inorder(
 422         struct xfs_btree_cur    *cur,
 423         union xfs_btree_rec     *r1,
 424         union xfs_btree_rec     *r2)
 425 {
 426         return be32_to_cpu(r1->alloc.ar_blockcount) <
 427                 be32_to_cpu(r2->alloc.ar_blockcount) ||
 428                 (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount &&
 429                  be32_to_cpu(r1->alloc.ar_startblock) <
 430                  be32_to_cpu(r2->alloc.ar_startblock));
 431 }
 432
 433 static const struct xfs_btree_ops xfs_bnobt_ops = {
 434         .rec_len                = sizeof(xfs_alloc_rec_t),
 435         .key_len                = sizeof(xfs_alloc_key_t),
 436
 437         .dup_cursor             = xfs_allocbt_dup_cursor,
 438         .set_root               = xfs_allocbt_set_root,
 439         .alloc_block            = xfs_allocbt_alloc_block,
 440         .free_block             = xfs_allocbt_free_block,
 441         .update_lastrec         = xfs_allocbt_update_lastrec,
 442         .get_minrecs            = xfs_allocbt_get_minrecs,
 443         .get_maxrecs            = xfs_allocbt_get_maxrecs,
 444         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
 445         .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec,
 446         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
 447         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
 448         .key_diff               = xfs_bnobt_key_diff,
 449         .buf_ops                = &xfs_allocbt_buf_ops,
 450         .diff_two_keys          = xfs_bnobt_diff_two_keys,
 451         .keys_inorder           = xfs_bnobt_keys_inorder,
 452         .recs_inorder           = xfs_bnobt_recs_inorder,
 453 };
 454
 455 static const struct xfs_btree_ops xfs_cntbt_ops = {
 456         .rec_len                = sizeof(xfs_alloc_rec_t),
 457         .key_len                = sizeof(xfs_alloc_key_t),
 458
 459         .dup_cursor             = xfs_allocbt_dup_cursor,
 460         .set_root               = xfs_allocbt_set_root,
 461         .alloc_block            = xfs_allocbt_alloc_block,
 462         .free_block             = xfs_allocbt_free_block,
 463         .update_lastrec         = xfs_allocbt_update_lastrec,
 464         .get_minrecs            = xfs_allocbt_get_minrecs,
 465         .get_maxrecs            = xfs_allocbt_get_maxrecs,
 466         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
 467         .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec,
 468         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
 469         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
 470         .key_diff               = xfs_cntbt_key_diff,
 471         .buf_ops                = &xfs_allocbt_buf_ops,
 472         .diff_two_keys          = xfs_cntbt_diff_two_keys,
 473         .keys_inorder           = xfs_cntbt_keys_inorder,
 474         .recs_inorder           = xfs_cntbt_recs_inorder,
 475 };
 476
 477 /*
 478  * Allocate a new allocation btree cursor.
 479  */
 480 struct xfs_btree_cur *                  /* new alloc btree cursor */
 481 xfs_allocbt_init_cursor(
 482         struct xfs_mount        *mp,            /* file system mount point */
 483         struct xfs_trans        *tp,            /* transaction pointer */
 484         struct xfs_buf          *agbp,          /* buffer for agf structure */
 485         xfs_agnumber_t          agno,           /* allocation group number */
 486         xfs_btnum_t             btnum)          /* btree identifier */
 487 {
 488         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 489         struct xfs_btree_cur    *cur;
 490
 491         ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
 492
 493         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
 494
 495         cur->bc_tp = tp;
 496         cur->bc_mp = mp;
 497         cur->bc_btnum = btnum;
 498         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 499
 500         if (btnum == XFS_BTNUM_CNT) {
 501                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2);
 502                 cur->bc_ops = &xfs_cntbt_ops;
 503                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]);
 504                 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE;
 505         } else {
 506                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2);
 507                 cur->bc_ops = &xfs_bnobt_ops;
 508                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]);
 509         }
 510
 511         cur->bc_private.a.agbp = agbp;
 512         cur->bc_private.a.agno = agno;
 513
 514         if (xfs_sb_version_hascrc(&mp->m_sb))
 515                 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 516
 517         return cur;
 518 }
 519
 520 /*
 521  * Calculate number of records in an alloc btree block.
 522  */
 523 int
 524 xfs_allocbt_maxrecs(
 525         struct xfs_mount        *mp,
 526         int                     blocklen,
 527         int                     leaf)
 528 {
 529         blocklen -= XFS_ALLOC_BLOCK_LEN(mp);
 530
 531         if (leaf)
 532                 return blocklen / sizeof(xfs_alloc_rec_t);
 533         return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
 534 }
 535
 536 /* Calculate the freespace btree size for some records. */
 537 xfs_extlen_t
 538 xfs_allocbt_calc_size(
 539         struct xfs_mount        *mp,
 540         unsigned long long      len)
 541 {
 542         return xfs_btree_calc_size(mp->m_alloc_mnr, len);
 543 }