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