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_mount.h"
  13 #include "xfs_btree.h"
  14 #include "xfs_btree_staging.h"
  15 #include "xfs_alloc_btree.h"
  16 #include "xfs_alloc.h"
  17 #include "xfs_trace.h"
  18 #include "xfs_trans.h"
  19 #include "xfs_ag.h"
  20
  21 static struct kmem_cache        *xfs_allocbt_cur_cache;
  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_ag.agbp, cur->bc_ag.pag, cur->bc_btnum);
  29 }
  30
  31 STATIC void
  32 xfs_allocbt_set_root(
  33         struct xfs_btree_cur            *cur,
  34         const union xfs_btree_ptr       *ptr,
  35         int                             inc)
  36 {
  37         struct xfs_buf          *agbp = cur->bc_ag.agbp;
  38         struct xfs_agf          *agf = agbp->b_addr;
  39         int                     btnum = cur->bc_btnum;
  40
  41         ASSERT(ptr->s != 0);
  42
  43         agf->agf_roots[btnum] = ptr->s;
  44         be32_add_cpu(&agf->agf_levels[btnum], inc);
  45         cur->bc_ag.pag->pagf_levels[btnum] += inc;
  46
  47         xfs_alloc_log_agf(cur->bc_tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
  48 }
  49
  50 STATIC int
  51 xfs_allocbt_alloc_block(
  52         struct xfs_btree_cur            *cur,
  53         const union xfs_btree_ptr       *start,
  54         union xfs_btree_ptr             *new,
  55         int                             *stat)
  56 {
  57         int                     error;
  58         xfs_agblock_t           bno;
  59
  60         /* Allocate the new block from the freelist. If we can't, give up.  */
  61         error = xfs_alloc_get_freelist(cur->bc_ag.pag, cur->bc_tp,
  62                         cur->bc_ag.agbp, &bno, 1);
  63         if (error)
  64                 return error;
  65
  66         if (bno == NULLAGBLOCK) {
  67                 *stat = 0;
  68                 return 0;
  69         }
  70
  71         atomic64_inc(&cur->bc_mp->m_allocbt_blks);
  72         xfs_extent_busy_reuse(cur->bc_mp, cur->bc_ag.pag, bno, 1, false);
  73
  74         new->s = cpu_to_be32(bno);
  75
  76         *stat = 1;
  77         return 0;
  78 }
  79
  80 STATIC int
  81 xfs_allocbt_free_block(
  82         struct xfs_btree_cur    *cur,
  83         struct xfs_buf          *bp)
  84 {
  85         struct xfs_buf          *agbp = cur->bc_ag.agbp;
  86         xfs_agblock_t           bno;
  87         int                     error;
  88
  89         bno = xfs_daddr_to_agbno(cur->bc_mp, xfs_buf_daddr(bp));
  90         error = xfs_alloc_put_freelist(cur->bc_ag.pag, cur->bc_tp, agbp, NULL,
  91                         bno, 1);
  92         if (error)
  93                 return error;
  94
  95         atomic64_dec(&cur->bc_mp->m_allocbt_blks);
  96         xfs_extent_busy_insert(cur->bc_tp, agbp->b_pag, bno, 1,
  97                               XFS_EXTENT_BUSY_SKIP_DISCARD);
  98         return 0;
  99 }
 100
 101 /*
 102  * Update the longest extent in the AGF
 103  */
 104 STATIC void
 105 xfs_allocbt_update_lastrec(
 106         struct xfs_btree_cur            *cur,
 107         const struct xfs_btree_block    *block,
 108         const union xfs_btree_rec       *rec,
 109         int                             ptr,
 110         int                             reason)
 111 {
 112         struct xfs_agf          *agf = cur->bc_ag.agbp->b_addr;
 113         struct xfs_perag        *pag;
 114         __be32                  len;
 115         int                     numrecs;
 116
 117         ASSERT(cur->bc_btnum == XFS_BTNUM_CNT);
 118
 119         switch (reason) {
 120         case LASTREC_UPDATE:
 121                 /*
 122                  * If this is the last leaf block and it's the last record,
 123                  * then update the size of the longest extent in the AG.
 124                  */
 125                 if (ptr != xfs_btree_get_numrecs(block))
 126                         return;
 127                 len = rec->alloc.ar_blockcount;
 128                 break;
 129         case LASTREC_INSREC:
 130                 if (be32_to_cpu(rec->alloc.ar_blockcount) <=
 131                     be32_to_cpu(agf->agf_longest))
 132                         return;
 133                 len = rec->alloc.ar_blockcount;
 134                 break;
 135         case LASTREC_DELREC:
 136                 numrecs = xfs_btree_get_numrecs(block);
 137                 if (ptr <= numrecs)
 138                         return;
 139                 ASSERT(ptr == numrecs + 1);
 140
 141                 if (numrecs) {
 142                         xfs_alloc_rec_t *rrp;
 143
 144                         rrp = XFS_ALLOC_REC_ADDR(cur->bc_mp, block, numrecs);
 145                         len = rrp->ar_blockcount;
 146                 } else {
 147                         len = 0;
 148                 }
 149
 150                 break;
 151         default:
 152                 ASSERT(0);
 153                 return;
 154         }
 155
 156         agf->agf_longest = len;
 157         pag = cur->bc_ag.agbp->b_pag;
 158         pag->pagf_longest = be32_to_cpu(len);
 159         xfs_alloc_log_agf(cur->bc_tp, cur->bc_ag.agbp, XFS_AGF_LONGEST);
 160 }
 161
 162 STATIC int
 163 xfs_allocbt_get_minrecs(
 164         struct xfs_btree_cur    *cur,
 165         int                     level)
 166 {
 167         return cur->bc_mp->m_alloc_mnr[level != 0];
 168 }
 169
 170 STATIC int
 171 xfs_allocbt_get_maxrecs(
 172         struct xfs_btree_cur    *cur,
 173         int                     level)
 174 {
 175         return cur->bc_mp->m_alloc_mxr[level != 0];
 176 }
 177
 178 STATIC void
 179 xfs_allocbt_init_key_from_rec(
 180         union xfs_btree_key             *key,
 181         const union xfs_btree_rec       *rec)
 182 {
 183         key->alloc.ar_startblock = rec->alloc.ar_startblock;
 184         key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
 185 }
 186
 187 STATIC void
 188 xfs_bnobt_init_high_key_from_rec(
 189         union xfs_btree_key             *key,
 190         const union xfs_btree_rec       *rec)
 191 {
 192         __u32                           x;
 193
 194         x = be32_to_cpu(rec->alloc.ar_startblock);
 195         x += be32_to_cpu(rec->alloc.ar_blockcount) - 1;
 196         key->alloc.ar_startblock = cpu_to_be32(x);
 197         key->alloc.ar_blockcount = 0;
 198 }
 199
 200 STATIC void
 201 xfs_cntbt_init_high_key_from_rec(
 202         union xfs_btree_key             *key,
 203         const union xfs_btree_rec       *rec)
 204 {
 205         key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
 206         key->alloc.ar_startblock = 0;
 207 }
 208
 209 STATIC void
 210 xfs_allocbt_init_rec_from_cur(
 211         struct xfs_btree_cur    *cur,
 212         union xfs_btree_rec     *rec)
 213 {
 214         rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
 215         rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
 216 }
 217
 218 STATIC void
 219 xfs_allocbt_init_ptr_from_cur(
 220         struct xfs_btree_cur    *cur,
 221         union xfs_btree_ptr     *ptr)
 222 {
 223         struct xfs_agf          *agf = cur->bc_ag.agbp->b_addr;
 224
 225         ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agf->agf_seqno));
 226
 227         ptr->s = agf->agf_roots[cur->bc_btnum];
 228 }
 229
 230 STATIC int64_t
 231 xfs_bnobt_key_diff(
 232         struct xfs_btree_cur            *cur,
 233         const union xfs_btree_key       *key)
 234 {
 235         struct xfs_alloc_rec_incore     *rec = &cur->bc_rec.a;
 236         const struct xfs_alloc_rec      *kp = &key->alloc;
 237
 238         return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
 239 }
 240
 241 STATIC int64_t
 242 xfs_cntbt_key_diff(
 243         struct xfs_btree_cur            *cur,
 244         const union xfs_btree_key       *key)
 245 {
 246         struct xfs_alloc_rec_incore     *rec = &cur->bc_rec.a;
 247         const struct xfs_alloc_rec      *kp = &key->alloc;
 248         int64_t                         diff;
 249
 250         diff = (int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
 251         if (diff)
 252                 return diff;
 253
 254         return (int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
 255 }
 256
 257 STATIC int64_t
 258 xfs_bnobt_diff_two_keys(
 259         struct xfs_btree_cur            *cur,
 260         const union xfs_btree_key       *k1,
 261         const union xfs_btree_key       *k2,
 262         const union xfs_btree_key       *mask)
 263 {
 264         ASSERT(!mask || mask->alloc.ar_startblock);
 265
 266         return (int64_t)be32_to_cpu(k1->alloc.ar_startblock) -
 267                         be32_to_cpu(k2->alloc.ar_startblock);
 268 }
 269
 270 STATIC int64_t
 271 xfs_cntbt_diff_two_keys(
 272         struct xfs_btree_cur            *cur,
 273         const union xfs_btree_key       *k1,
 274         const union xfs_btree_key       *k2,
 275         const union xfs_btree_key       *mask)
 276 {
 277         int64_t                         diff;
 278
 279         ASSERT(!mask || (mask->alloc.ar_blockcount &&
 280                          mask->alloc.ar_startblock));
 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_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_has_crc(mp)) {
 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 && xfs_perag_initialised_agf(pag)) {
 324                 if (level >= pag->pagf_levels[btnum])
 325                         return __this_address;
 326         } else if (level >= mp->m_alloc_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         const union xfs_btree_key       *k1,
 388         const 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         const union xfs_btree_rec       *r1,
 398         const 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         const union xfs_btree_key       *k1,
 409         const 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         const union xfs_btree_rec       *r1,
 422         const 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 enum xbtree_key_contig
 432 xfs_allocbt_keys_contiguous(
 433         struct xfs_btree_cur            *cur,
 434         const union xfs_btree_key       *key1,
 435         const union xfs_btree_key       *key2,
 436         const union xfs_btree_key       *mask)
 437 {
 438         ASSERT(!mask || mask->alloc.ar_startblock);
 439
 440         return xbtree_key_contig(be32_to_cpu(key1->alloc.ar_startblock),
 441                                  be32_to_cpu(key2->alloc.ar_startblock));
 442 }
 443
 444 static const struct xfs_btree_ops xfs_bnobt_ops = {
 445         .rec_len                = sizeof(xfs_alloc_rec_t),
 446         .key_len                = sizeof(xfs_alloc_key_t),
 447
 448         .dup_cursor             = xfs_allocbt_dup_cursor,
 449         .set_root               = xfs_allocbt_set_root,
 450         .alloc_block            = xfs_allocbt_alloc_block,
 451         .free_block             = xfs_allocbt_free_block,
 452         .update_lastrec         = xfs_allocbt_update_lastrec,
 453         .get_minrecs            = xfs_allocbt_get_minrecs,
 454         .get_maxrecs            = xfs_allocbt_get_maxrecs,
 455         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
 456         .init_high_key_from_rec = xfs_bnobt_init_high_key_from_rec,
 457         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
 458         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
 459         .key_diff               = xfs_bnobt_key_diff,
 460         .buf_ops                = &xfs_bnobt_buf_ops,
 461         .diff_two_keys          = xfs_bnobt_diff_two_keys,
 462         .keys_inorder           = xfs_bnobt_keys_inorder,
 463         .recs_inorder           = xfs_bnobt_recs_inorder,
 464         .keys_contiguous        = xfs_allocbt_keys_contiguous,
 465 };
 466
 467 static const struct xfs_btree_ops xfs_cntbt_ops = {
 468         .rec_len                = sizeof(xfs_alloc_rec_t),
 469         .key_len                = sizeof(xfs_alloc_key_t),
 470
 471         .dup_cursor             = xfs_allocbt_dup_cursor,
 472         .set_root               = xfs_allocbt_set_root,
 473         .alloc_block            = xfs_allocbt_alloc_block,
 474         .free_block             = xfs_allocbt_free_block,
 475         .update_lastrec         = xfs_allocbt_update_lastrec,
 476         .get_minrecs            = xfs_allocbt_get_minrecs,
 477         .get_maxrecs            = xfs_allocbt_get_maxrecs,
 478         .init_key_from_rec      = xfs_allocbt_init_key_from_rec,
 479         .init_high_key_from_rec = xfs_cntbt_init_high_key_from_rec,
 480         .init_rec_from_cur      = xfs_allocbt_init_rec_from_cur,
 481         .init_ptr_from_cur      = xfs_allocbt_init_ptr_from_cur,
 482         .key_diff               = xfs_cntbt_key_diff,
 483         .buf_ops                = &xfs_cntbt_buf_ops,
 484         .diff_two_keys          = xfs_cntbt_diff_two_keys,
 485         .keys_inorder           = xfs_cntbt_keys_inorder,
 486         .recs_inorder           = xfs_cntbt_recs_inorder,
 487         .keys_contiguous        = NULL, /* not needed right now */
 488 };
 489
 490 /* Allocate most of a new allocation btree cursor. */
 491 STATIC struct xfs_btree_cur *
 492 xfs_allocbt_init_common(
 493         struct xfs_mount        *mp,
 494         struct xfs_trans        *tp,
 495         struct xfs_perag        *pag,
 496         xfs_btnum_t             btnum)
 497 {
 498         struct xfs_btree_cur    *cur;
 499
 500         ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
 501
 502         cur = xfs_btree_alloc_cursor(mp, tp, btnum, mp->m_alloc_maxlevels,
 503                         xfs_allocbt_cur_cache);
 504         cur->bc_ag.abt.active = false;
 505
 506         if (btnum == XFS_BTNUM_CNT) {
 507                 cur->bc_ops = &xfs_cntbt_ops;
 508                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtc_2);
 509                 cur->bc_flags = XFS_BTREE_LASTREC_UPDATE;
 510         } else {
 511                 cur->bc_ops = &xfs_bnobt_ops;
 512                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_abtb_2);
 513         }
 514
 515         cur->bc_ag.pag = xfs_perag_hold(pag);
 516
 517         if (xfs_has_crc(mp))
 518                 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 519
 520         return cur;
 521 }
 522
 523 /*
 524  * Allocate a new allocation btree cursor.
 525  */
 526 struct xfs_btree_cur *                  /* new alloc btree cursor */
 527 xfs_allocbt_init_cursor(
 528         struct xfs_mount        *mp,            /* file system mount point */
 529         struct xfs_trans        *tp,            /* transaction pointer */
 530         struct xfs_buf          *agbp,          /* buffer for agf structure */
 531         struct xfs_perag        *pag,
 532         xfs_btnum_t             btnum)          /* btree identifier */
 533 {
 534         struct xfs_agf          *agf = agbp->b_addr;
 535         struct xfs_btree_cur    *cur;
 536
 537         cur = xfs_allocbt_init_common(mp, tp, pag, btnum);
 538         if (btnum == XFS_BTNUM_CNT)
 539                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]);
 540         else
 541                 cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]);
 542
 543         cur->bc_ag.agbp = agbp;
 544
 545         return cur;
 546 }
 547
 548 /* Create a free space btree cursor with a fake root for staging. */
 549 struct xfs_btree_cur *
 550 xfs_allocbt_stage_cursor(
 551         struct xfs_mount        *mp,
 552         struct xbtree_afakeroot *afake,
 553         struct xfs_perag        *pag,
 554         xfs_btnum_t             btnum)
 555 {
 556         struct xfs_btree_cur    *cur;
 557
 558         cur = xfs_allocbt_init_common(mp, NULL, pag, btnum);
 559         xfs_btree_stage_afakeroot(cur, afake);
 560         return cur;
 561 }
 562
 563 /*
 564  * Install a new free space btree root.  Caller is responsible for invalidating
 565  * and freeing the old btree blocks.
 566  */
 567 void
 568 xfs_allocbt_commit_staged_btree(
 569         struct xfs_btree_cur    *cur,
 570         struct xfs_trans        *tp,
 571         struct xfs_buf          *agbp)
 572 {
 573         struct xfs_agf          *agf = agbp->b_addr;
 574         struct xbtree_afakeroot *afake = cur->bc_ag.afake;
 575
 576         ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
 577
 578         agf->agf_roots[cur->bc_btnum] = cpu_to_be32(afake->af_root);
 579         agf->agf_levels[cur->bc_btnum] = cpu_to_be32(afake->af_levels);
 580         xfs_alloc_log_agf(tp, agbp, XFS_AGF_ROOTS | XFS_AGF_LEVELS);
 581
 582         if (cur->bc_btnum == XFS_BTNUM_BNO) {
 583                 xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_bnobt_ops);
 584         } else {
 585                 cur->bc_flags |= XFS_BTREE_LASTREC_UPDATE;
 586                 xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_cntbt_ops);
 587         }
 588 }
 589
 590 /* Calculate number of records in an alloc btree block. */
 591 static inline unsigned int
 592 xfs_allocbt_block_maxrecs(
 593         unsigned int            blocklen,
 594         bool                    leaf)
 595 {
 596         if (leaf)
 597                 return blocklen / sizeof(xfs_alloc_rec_t);
 598         return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
 599 }
 600
 601 /*
 602  * Calculate number of records in an alloc btree block.
 603  */
 604 int
 605 xfs_allocbt_maxrecs(
 606         struct xfs_mount        *mp,
 607         int                     blocklen,
 608         int                     leaf)
 609 {
 610         blocklen -= XFS_ALLOC_BLOCK_LEN(mp);
 611         return xfs_allocbt_block_maxrecs(blocklen, leaf);
 612 }
 613
 614 /* Free space btrees are at their largest when every other block is free. */
 615 #define XFS_MAX_FREESP_RECORDS  ((XFS_MAX_AG_BLOCKS + 1) / 2)
 616
 617 /* Compute the max possible height for free space btrees. */
 618 unsigned int
 619 xfs_allocbt_maxlevels_ondisk(void)
 620 {
 621         unsigned int            minrecs[2];
 622         unsigned int            blocklen;
 623
 624         blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN,
 625                        XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN);
 626
 627         minrecs[0] = xfs_allocbt_block_maxrecs(blocklen, true) / 2;
 628         minrecs[1] = xfs_allocbt_block_maxrecs(blocklen, false) / 2;
 629
 630         return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_FREESP_RECORDS);
 631 }
 632
 633 /* Calculate the freespace btree size for some records. */
 634 xfs_extlen_t
 635 xfs_allocbt_calc_size(
 636         struct xfs_mount        *mp,
 637         unsigned long long      len)
 638 {
 639         return xfs_btree_calc_size(mp->m_alloc_mnr, len);
 640 }
 641
 642 int __init
 643 xfs_allocbt_init_cur_cache(void)
 644 {
 645         xfs_allocbt_cur_cache = kmem_cache_create("xfs_bnobt_cur",
 646                         xfs_btree_cur_sizeof(xfs_allocbt_maxlevels_ondisk()),
 647                         0, 0, NULL);
 648
 649         if (!xfs_allocbt_cur_cache)
 650                 return -ENOMEM;
 651         return 0;
 652 }
 653
 654 void
 655 xfs_allocbt_destroy_cur_cache(void)
 656 {
 657         kmem_cache_destroy(xfs_allocbt_cur_cache);
 658         xfs_allocbt_cur_cache = NULL;
 659 }