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