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         xfs_btnum_t             btnum = XFS_BTNUM_BNOi;
 301
 302         if (!xfs_verify_magic(bp, block->bb_magic))
 303                 return __this_address;
 304
 305         if (xfs_sb_version_hascrc(&mp->m_sb)) {
 306                 fa = xfs_btree_sblock_v5hdr_verify(bp);
 307                 if (fa)
 308                         return fa;
 309         }
 310
 311         /*
 312          * The perag may not be attached during grow operations or fully
 313          * initialized from the AGF during log recovery. Therefore we can only
 314          * check against maximum tree depth from those contexts.
 315          *
 316          * Otherwise check against the per-tree limit. Peek at one of the
 317          * verifier magic values to determine the type of tree we're verifying
 318          * against.
 319          */
 320         level = be16_to_cpu(block->bb_level);
 321         if (bp->b_ops->magic[0] == cpu_to_be32(XFS_ABTC_MAGIC))
 322                 btnum = XFS_BTNUM_CNTi;
 323         if (pag && pag->pagf_init) {
 324                 if (level >= pag->pagf_levels[btnum])
 325                         return __this_address;
 326         } else if (level >= mp->m_ag_maxlevels)
 327                 return __this_address;
 328
 329         return xfs_btree_sblock_verify(bp, mp->m_alloc_mxr[level != 0]);
 330 }
 331
 332 static void
 333 xfs_allocbt_read_verify(
 334         struct xfs_buf  *bp)
 335 {
 336         xfs_failaddr_t  fa;
 337
 338         if (!xfs_btree_sblock_verify_crc(bp))
 339                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 340         else {
 341                 fa = xfs_allocbt_verify(bp);
 342                 if (fa)
 343                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 344         }
 345
 346         if (bp->b_error)
 347                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 348 }
 349
 350 static void
 351 xfs_allocbt_write_verify(
 352         struct xfs_buf  *bp)
 353 {
 354         xfs_failaddr_t  fa;
 355
 356         fa = xfs_allocbt_verify(bp);
 357         if (fa) {
 358                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 359                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 360                 return;
 361         }
 362         xfs_btree_sblock_calc_crc(bp);
 363
 364 }
 365
 366 const struct xfs_buf_ops xfs_bnobt_buf_ops = {
 367         .name = "xfs_bnobt",
 368         .magic = { cpu_to_be32(XFS_ABTB_MAGIC),
 369                    cpu_to_be32(XFS_ABTB_CRC_MAGIC) },
 370         .verify_read = xfs_allocbt_read_verify,
 371         .verify_write = xfs_allocbt_write_verify,
 372         .verify_struct = xfs_allocbt_verify,
 373 };
 374
 375 const struct xfs_buf_ops xfs_cntbt_buf_ops = {
 376         .name = "xfs_cntbt",
 377         .magic = { cpu_to_be32(XFS_ABTC_MAGIC),
 378                    cpu_to_be32(XFS_ABTC_CRC_MAGIC) },
 379         .verify_read = xfs_allocbt_read_verify,
 380         .verify_write = xfs_allocbt_write_verify,
 381         .verify_struct = xfs_allocbt_verify,
 382 };
 383
 384 STATIC int
 385 xfs_bnobt_keys_inorder(
 386         struct xfs_btree_cur    *cur,
 387         union xfs_btree_key     *k1,
 388         union xfs_btree_key     *k2)
 389 {
 390         return be32_to_cpu(k1->alloc.ar_startblock) <
 391                be32_to_cpu(k2->alloc.ar_startblock);
 392 }
 393
 394 STATIC int
 395 xfs_bnobt_recs_inorder(
 396         struct xfs_btree_cur    *cur,
 397         union xfs_btree_rec     *r1,
 398         union xfs_btree_rec     *r2)
 399 {
 400         return be32_to_cpu(r1->alloc.ar_startblock) +
 401                 be32_to_cpu(r1->alloc.ar_blockcount) <=
 402                 be32_to_cpu(r2->alloc.ar_startblock);
 403 }
 404
 405 STATIC int
 406 xfs_cntbt_keys_inorder(
 407         struct xfs_btree_cur    *cur,
 408         union xfs_btree_key     *k1,
 409         union xfs_btree_key     *k2)
 410 {
 411         return be32_to_cpu(k1->alloc.ar_blockcount) <
 412                 be32_to_cpu(k2->alloc.ar_blockcount) ||
 413                 (k1->alloc.ar_blockcount == k2->alloc.ar_blockcount &&
 414                  be32_to_cpu(k1->alloc.ar_startblock) <
 415                  be32_to_cpu(k2->alloc.ar_startblock));
 416 }
 417
 418 STATIC int
 419 xfs_cntbt_recs_inorder(
 420         struct xfs_btree_cur    *cur,
 421         union xfs_btree_rec     *r1,
 422         union xfs_btree_rec     *r2)
 423 {
 424         return be32_to_cpu(r1->alloc.ar_blockcount) <
 425                 be32_to_cpu(r2->alloc.ar_blockcount) ||
 426                 (r1->alloc.ar_blockcount == r2->alloc.ar_blockcount &&
 427                  be32_to_cpu(r1->alloc.ar_startblock) <
 428                  be32_to_cpu(r2->alloc.ar_startblock));
 429 }
 430
 431 static const struct xfs_btree_ops xfs_bnobt_ops = {
 432         .rec_len                = sizeof(xfs_alloc_rec_t),
 433         .key_len                = sizeof(xfs_alloc_key_t),
 434
 435         .dup_cursor             = xfs_allocbt_dup_cursor,
 436         .set_root               = xfs_allocbt_set_root,
 437         .alloc_block            = xfs_allocbt_alloc_block,
 438         .free_block             = xfs_allocbt_free_block,
 439         .update_lastrec         = xfs_allocbt_update_lastrec,
 440         .get_minrecs            = xfs_allocbt_get_minrecs,
 441         .get_maxrecs            = xfs_allocbt_get_maxrecs,
 442         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
 443         .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec,
 444         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
 445         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
 446         .key_diff               = xfs_bnobt_key_diff,
 447         .buf_ops                = &xfs_bnobt_buf_ops,
 448         .diff_two_keys          = xfs_bnobt_diff_two_keys,
 449         .keys_inorder           = xfs_bnobt_keys_inorder,
 450         .recs_inorder           = xfs_bnobt_recs_inorder,
 451 };
 452
 453 static const struct xfs_btree_ops xfs_cntbt_ops = {
 454         .rec_len                = sizeof(xfs_alloc_rec_t),
 455         .key_len                = sizeof(xfs_alloc_key_t),
 456
 457         .dup_cursor             = xfs_allocbt_dup_cursor,
 458         .set_root               = xfs_allocbt_set_root,
 459         .alloc_block            = xfs_allocbt_alloc_block,
 460         .free_block             = xfs_allocbt_free_block,
 461         .update_lastrec         = xfs_allocbt_update_lastrec,
 462         .get_minrecs            = xfs_allocbt_get_minrecs,
 463         .get_maxrecs            = xfs_allocbt_get_maxrecs,
 464         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
 465         .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec,
 466         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
 467         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
 468         .key_diff               = xfs_cntbt_key_diff,
 469         .buf_ops                = &xfs_cntbt_buf_ops,
 470         .diff_two_keys          = xfs_cntbt_diff_two_keys,
 471         .keys_inorder           = xfs_cntbt_keys_inorder,
 472         .recs_inorder           = xfs_cntbt_recs_inorder,
 473 };
 474
 475 /*
 476  * Allocate a new allocation btree cursor.
 477  */
 478 struct xfs_btree_cur *                  /* new alloc btree cursor */
 479 xfs_allocbt_init_cursor(
 480         struct xfs_mount        *mp,            /* file system mount point */
 481         struct xfs_trans        *tp,            /* transaction pointer */
 482         struct xfs_buf          *agbp,          /* buffer for agf structure */
 483         xfs_agnumber_t          agno,           /* allocation group number */
 484         xfs_btnum_t             btnum)          /* btree identifier */
 485 {
 486         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 487         struct xfs_btree_cur    *cur;
 488
 489         ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
 490
 491         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
 492
 493         cur->bc_tp = tp;
 494         cur->bc_mp = mp;
 495         cur->bc_btnum = btnum;
 496         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 497
 498         if (btnum == XFS_BTNUM_CNT) {
 499                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2);
 500                 cur->bc_ops = &xfs_cntbt_ops;
 501                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]);
 502                 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE;
 503         } else {
 504                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2);
 505                 cur->bc_ops = &xfs_bnobt_ops;
 506                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]);
 507         }
 508
 509         cur->bc_private.a.agbp = agbp;
 510         cur->bc_private.a.agno = agno;
 511
 512         if (xfs_sb_version_hascrc(&mp->m_sb))
 513                 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 514
 515         return cur;
 516 }
 517
 518 /*
 519  * Calculate number of records in an alloc btree block.
 520  */
 521 int
 522 xfs_allocbt_maxrecs(
 523         struct xfs_mount        *mp,
 524         int                     blocklen,
 525         int                     leaf)
 526 {
 527         blocklen -= XFS_ALLOC_BLOCK_LEN(mp);
 528
 529         if (leaf)
 530                 return blocklen / sizeof(xfs_alloc_rec_t);
 531         return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
 532 }
 533
 534 /* Calculate the freespace btree size for some records. */
 535 xfs_extlen_t
 536 xfs_allocbt_calc_size(
 537         struct xfs_mount        *mp,
 538         unsigned long long      len)
 539 {
 540         return xfs_btree_calc_size(mp->m_alloc_mnr, len);
 541 }