libxfs/xfs_ialloc_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_bit.h"
  13 #include "xfs_mount.h"
  14 #include "xfs_btree.h"
  15 #include "xfs_btree_staging.h"
  16 #include "xfs_ialloc.h"
  17 #include "xfs_ialloc_btree.h"
  18 #include "xfs_alloc.h"
  19 #include "xfs_error.h"
  20 #include "xfs_trace.h"
  21 #include "xfs_trans.h"
  22 #include "xfs_rmap.h"
  23 #include "xfs_ag.h"
  24
  25 static struct kmem_cache        *xfs_inobt_cur_cache;
  26
  27 STATIC int
  28 xfs_inobt_get_minrecs(
  29         struct xfs_btree_cur    *cur,
  30         int                     level)
  31 {
  32         return M_IGEO(cur->bc_mp)->inobt_mnr[level != 0];
  33 }
  34
  35 STATIC struct xfs_btree_cur *
  36 xfs_inobt_dup_cursor(
  37         struct xfs_btree_cur    *cur)
  38 {
  39         return xfs_inobt_init_cursor(cur->bc_ag.pag, cur->bc_tp,
  40                         cur->bc_ag.agbp, cur->bc_btnum);
  41 }
  42
  43 STATIC void
  44 xfs_inobt_set_root(
  45         struct xfs_btree_cur            *cur,
  46         const union xfs_btree_ptr       *nptr,
  47         int                             inc)    /* level change */
  48 {
  49         struct xfs_buf          *agbp = cur->bc_ag.agbp;
  50         struct xfs_agi          *agi = agbp->b_addr;
  51
  52         agi->agi_root = nptr->s;
  53         be32_add_cpu(&agi->agi_level, inc);
  54         xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
  55 }
  56
  57 STATIC void
  58 xfs_finobt_set_root(
  59         struct xfs_btree_cur            *cur,
  60         const union xfs_btree_ptr       *nptr,
  61         int                             inc)    /* level change */
  62 {
  63         struct xfs_buf          *agbp = cur->bc_ag.agbp;
  64         struct xfs_agi          *agi = agbp->b_addr;
  65
  66         agi->agi_free_root = nptr->s;
  67         be32_add_cpu(&agi->agi_free_level, inc);
  68         xfs_ialloc_log_agi(cur->bc_tp, agbp,
  69                            XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL);
  70 }
  71
  72 /* Update the inode btree block counter for this btree. */
  73 static inline void
  74 xfs_inobt_mod_blockcount(
  75         struct xfs_btree_cur    *cur,
  76         int                     howmuch)
  77 {
  78         struct xfs_buf          *agbp = cur->bc_ag.agbp;
  79         struct xfs_agi          *agi = agbp->b_addr;
  80
  81         if (!xfs_has_inobtcounts(cur->bc_mp))
  82                 return;
  83
  84         if (cur->bc_btnum == XFS_BTNUM_FINO)
  85                 be32_add_cpu(&agi->agi_fblocks, howmuch);
  86         else if (cur->bc_btnum == XFS_BTNUM_INO)
  87                 be32_add_cpu(&agi->agi_iblocks, howmuch);
  88         xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_IBLOCKS);
  89 }
  90
  91 STATIC int
  92 __xfs_inobt_alloc_block(
  93         struct xfs_btree_cur            *cur,
  94         const union xfs_btree_ptr       *start,
  95         union xfs_btree_ptr             *new,
  96         int                             *stat,
  97         enum xfs_ag_resv_type           resv)
  98 {
  99         xfs_alloc_arg_t         args;           /* block allocation args */
 100         int                     error;          /* error return value */
 101         xfs_agblock_t           sbno = be32_to_cpu(start->s);
 102
 103         memset(&args, 0, sizeof(args));
 104         args.tp = cur->bc_tp;
 105         args.mp = cur->bc_mp;
 106         args.pag = cur->bc_ag.pag;
 107         args.oinfo = XFS_RMAP_OINFO_INOBT;
 108         args.minlen = 1;
 109         args.maxlen = 1;
 110         args.prod = 1;
 111         args.resv = resv;
 112
 113         error = xfs_alloc_vextent_near_bno(&args,
 114                         XFS_AGB_TO_FSB(args.mp, args.pag->pag_agno, sbno));
 115         if (error)
 116                 return error;
 117
 118         if (args.fsbno == NULLFSBLOCK) {
 119                 *stat = 0;
 120                 return 0;
 121         }
 122         ASSERT(args.len == 1);
 123
 124         new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
 125         *stat = 1;
 126         xfs_inobt_mod_blockcount(cur, 1);
 127         return 0;
 128 }
 129
 130 STATIC int
 131 xfs_inobt_alloc_block(
 132         struct xfs_btree_cur            *cur,
 133         const union xfs_btree_ptr       *start,
 134         union xfs_btree_ptr             *new,
 135         int                             *stat)
 136 {
 137         return __xfs_inobt_alloc_block(cur, start, new, stat, XFS_AG_RESV_NONE);
 138 }
 139
 140 STATIC int
 141 xfs_finobt_alloc_block(
 142         struct xfs_btree_cur            *cur,
 143         const union xfs_btree_ptr       *start,
 144         union xfs_btree_ptr             *new,
 145         int                             *stat)
 146 {
 147         if (cur->bc_mp->m_finobt_nores)
 148                 return xfs_inobt_alloc_block(cur, start, new, stat);
 149         return __xfs_inobt_alloc_block(cur, start, new, stat,
 150                         XFS_AG_RESV_METADATA);
 151 }
 152
 153 STATIC int
 154 __xfs_inobt_free_block(
 155         struct xfs_btree_cur    *cur,
 156         struct xfs_buf          *bp,
 157         enum xfs_ag_resv_type   resv)
 158 {
 159         xfs_fsblock_t           fsbno;
 160
 161         xfs_inobt_mod_blockcount(cur, -1);
 162         fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, xfs_buf_daddr(bp));
 163         return xfs_free_extent_later(cur->bc_tp, fsbno, 1,
 164                         &XFS_RMAP_OINFO_INOBT, resv, false);
 165 }
 166
 167 STATIC int
 168 xfs_inobt_free_block(
 169         struct xfs_btree_cur    *cur,
 170         struct xfs_buf          *bp)
 171 {
 172         return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_NONE);
 173 }
 174
 175 STATIC int
 176 xfs_finobt_free_block(
 177         struct xfs_btree_cur    *cur,
 178         struct xfs_buf          *bp)
 179 {
 180         if (cur->bc_mp->m_finobt_nores)
 181                 return xfs_inobt_free_block(cur, bp);
 182         return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_METADATA);
 183 }
 184
 185 STATIC int
 186 xfs_inobt_get_maxrecs(
 187         struct xfs_btree_cur    *cur,
 188         int                     level)
 189 {
 190         return M_IGEO(cur->bc_mp)->inobt_mxr[level != 0];
 191 }
 192
 193 STATIC void
 194 xfs_inobt_init_key_from_rec(
 195         union xfs_btree_key             *key,
 196         const union xfs_btree_rec       *rec)
 197 {
 198         key->inobt.ir_startino = rec->inobt.ir_startino;
 199 }
 200
 201 STATIC void
 202 xfs_inobt_init_high_key_from_rec(
 203         union xfs_btree_key             *key,
 204         const union xfs_btree_rec       *rec)
 205 {
 206         __u32                           x;
 207
 208         x = be32_to_cpu(rec->inobt.ir_startino);
 209         x += XFS_INODES_PER_CHUNK - 1;
 210         key->inobt.ir_startino = cpu_to_be32(x);
 211 }
 212
 213 STATIC void
 214 xfs_inobt_init_rec_from_cur(
 215         struct xfs_btree_cur    *cur,
 216         union xfs_btree_rec     *rec)
 217 {
 218         rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
 219         if (xfs_has_sparseinodes(cur->bc_mp)) {
 220                 rec->inobt.ir_u.sp.ir_holemask =
 221                                         cpu_to_be16(cur->bc_rec.i.ir_holemask);
 222                 rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count;
 223                 rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount;
 224         } else {
 225                 /* ir_holemask/ir_count not supported on-disk */
 226                 rec->inobt.ir_u.f.ir_freecount =
 227                                         cpu_to_be32(cur->bc_rec.i.ir_freecount);
 228         }
 229         rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
 230 }
 231
 232 /*
 233  * initial value of ptr for lookup
 234  */
 235 STATIC void
 236 xfs_inobt_init_ptr_from_cur(
 237         struct xfs_btree_cur    *cur,
 238         union xfs_btree_ptr     *ptr)
 239 {
 240         struct xfs_agi          *agi = cur->bc_ag.agbp->b_addr;
 241
 242         ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agi->agi_seqno));
 243
 244         ptr->s = agi->agi_root;
 245 }
 246
 247 STATIC void
 248 xfs_finobt_init_ptr_from_cur(
 249         struct xfs_btree_cur    *cur,
 250         union xfs_btree_ptr     *ptr)
 251 {
 252         struct xfs_agi          *agi = cur->bc_ag.agbp->b_addr;
 253
 254         ASSERT(cur->bc_ag.pag->pag_agno == be32_to_cpu(agi->agi_seqno));
 255         ptr->s = agi->agi_free_root;
 256 }
 257
 258 STATIC int64_t
 259 xfs_inobt_key_diff(
 260         struct xfs_btree_cur            *cur,
 261         const union xfs_btree_key       *key)
 262 {
 263         return (int64_t)be32_to_cpu(key->inobt.ir_startino) -
 264                           cur->bc_rec.i.ir_startino;
 265 }
 266
 267 STATIC int64_t
 268 xfs_inobt_diff_two_keys(
 269         struct xfs_btree_cur            *cur,
 270         const union xfs_btree_key       *k1,
 271         const union xfs_btree_key       *k2,
 272         const union xfs_btree_key       *mask)
 273 {
 274         ASSERT(!mask || mask->inobt.ir_startino);
 275
 276         return (int64_t)be32_to_cpu(k1->inobt.ir_startino) -
 277                         be32_to_cpu(k2->inobt.ir_startino);
 278 }
 279
 280 static xfs_failaddr_t
 281 xfs_inobt_verify(
 282         struct xfs_buf          *bp)
 283 {
 284         struct xfs_mount        *mp = bp->b_mount;
 285         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 286         xfs_failaddr_t          fa;
 287         unsigned int            level;
 288
 289         if (!xfs_verify_magic(bp, block->bb_magic))
 290                 return __this_address;
 291
 292         /*
 293          * During growfs operations, we can't verify the exact owner as the
 294          * perag is not fully initialised and hence not attached to the buffer.
 295          *
 296          * Similarly, during log recovery we will have a perag structure
 297          * attached, but the agi information will not yet have been initialised
 298          * from the on disk AGI. We don't currently use any of this information,
 299          * but beware of the landmine (i.e. need to check
 300          * xfs_perag_initialised_agi(pag)) if we ever do.
 301          */
 302         if (xfs_has_crc(mp)) {
 303                 fa = xfs_btree_sblock_v5hdr_verify(bp);
 304                 if (fa)
 305                         return fa;
 306         }
 307
 308         /* level verification */
 309         level = be16_to_cpu(block->bb_level);
 310         if (level >= M_IGEO(mp)->inobt_maxlevels)
 311                 return __this_address;
 312
 313         return xfs_btree_sblock_verify(bp,
 314                         M_IGEO(mp)->inobt_mxr[level != 0]);
 315 }
 316
 317 static void
 318 xfs_inobt_read_verify(
 319         struct xfs_buf  *bp)
 320 {
 321         xfs_failaddr_t  fa;
 322
 323         if (!xfs_btree_sblock_verify_crc(bp))
 324                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 325         else {
 326                 fa = xfs_inobt_verify(bp);
 327                 if (fa)
 328                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 329         }
 330
 331         if (bp->b_error)
 332                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 333 }
 334
 335 static void
 336 xfs_inobt_write_verify(
 337         struct xfs_buf  *bp)
 338 {
 339         xfs_failaddr_t  fa;
 340
 341         fa = xfs_inobt_verify(bp);
 342         if (fa) {
 343                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 344                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 345                 return;
 346         }
 347         xfs_btree_sblock_calc_crc(bp);
 348
 349 }
 350
 351 const struct xfs_buf_ops xfs_inobt_buf_ops = {
 352         .name = "xfs_inobt",
 353         .magic = { cpu_to_be32(XFS_IBT_MAGIC), cpu_to_be32(XFS_IBT_CRC_MAGIC) },
 354         .verify_read = xfs_inobt_read_verify,
 355         .verify_write = xfs_inobt_write_verify,
 356         .verify_struct = xfs_inobt_verify,
 357 };
 358
 359 const struct xfs_buf_ops xfs_finobt_buf_ops = {
 360         .name = "xfs_finobt",
 361         .magic = { cpu_to_be32(XFS_FIBT_MAGIC),
 362                    cpu_to_be32(XFS_FIBT_CRC_MAGIC) },
 363         .verify_read = xfs_inobt_read_verify,
 364         .verify_write = xfs_inobt_write_verify,
 365         .verify_struct = xfs_inobt_verify,
 366 };
 367
 368 STATIC int
 369 xfs_inobt_keys_inorder(
 370         struct xfs_btree_cur            *cur,
 371         const union xfs_btree_key       *k1,
 372         const union xfs_btree_key       *k2)
 373 {
 374         return be32_to_cpu(k1->inobt.ir_startino) <
 375                 be32_to_cpu(k2->inobt.ir_startino);
 376 }
 377
 378 STATIC int
 379 xfs_inobt_recs_inorder(
 380         struct xfs_btree_cur            *cur,
 381         const union xfs_btree_rec       *r1,
 382         const union xfs_btree_rec       *r2)
 383 {
 384         return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
 385                 be32_to_cpu(r2->inobt.ir_startino);
 386 }
 387
 388 STATIC enum xbtree_key_contig
 389 xfs_inobt_keys_contiguous(
 390         struct xfs_btree_cur            *cur,
 391         const union xfs_btree_key       *key1,
 392         const union xfs_btree_key       *key2,
 393         const union xfs_btree_key       *mask)
 394 {
 395         ASSERT(!mask || mask->inobt.ir_startino);
 396
 397         return xbtree_key_contig(be32_to_cpu(key1->inobt.ir_startino),
 398                                  be32_to_cpu(key2->inobt.ir_startino));
 399 }
 400
 401 static const struct xfs_btree_ops xfs_inobt_ops = {
 402         .rec_len                = sizeof(xfs_inobt_rec_t),
 403         .key_len                = sizeof(xfs_inobt_key_t),
 404
 405         .dup_cursor             = xfs_inobt_dup_cursor,
 406         .set_root               = xfs_inobt_set_root,
 407         .alloc_block            = xfs_inobt_alloc_block,
 408         .free_block             = xfs_inobt_free_block,
 409         .get_minrecs            = xfs_inobt_get_minrecs,
 410         .get_maxrecs            = xfs_inobt_get_maxrecs,
 411         .init_key_from_rec      = xfs_inobt_init_key_from_rec,
 412         .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec,
 413         .init_rec_from_cur      = xfs_inobt_init_rec_from_cur,
 414         .init_ptr_from_cur      = xfs_inobt_init_ptr_from_cur,
 415         .key_diff               = xfs_inobt_key_diff,
 416         .buf_ops                = &xfs_inobt_buf_ops,
 417         .diff_two_keys          = xfs_inobt_diff_two_keys,
 418         .keys_inorder           = xfs_inobt_keys_inorder,
 419         .recs_inorder           = xfs_inobt_recs_inorder,
 420         .keys_contiguous        = xfs_inobt_keys_contiguous,
 421 };
 422
 423 static const struct xfs_btree_ops xfs_finobt_ops = {
 424         .rec_len                = sizeof(xfs_inobt_rec_t),
 425         .key_len                = sizeof(xfs_inobt_key_t),
 426
 427         .dup_cursor             = xfs_inobt_dup_cursor,
 428         .set_root               = xfs_finobt_set_root,
 429         .alloc_block            = xfs_finobt_alloc_block,
 430         .free_block             = xfs_finobt_free_block,
 431         .get_minrecs            = xfs_inobt_get_minrecs,
 432         .get_maxrecs            = xfs_inobt_get_maxrecs,
 433         .init_key_from_rec      = xfs_inobt_init_key_from_rec,
 434         .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec,
 435         .init_rec_from_cur      = xfs_inobt_init_rec_from_cur,
 436         .init_ptr_from_cur      = xfs_finobt_init_ptr_from_cur,
 437         .key_diff               = xfs_inobt_key_diff,
 438         .buf_ops                = &xfs_finobt_buf_ops,
 439         .diff_two_keys          = xfs_inobt_diff_two_keys,
 440         .keys_inorder           = xfs_inobt_keys_inorder,
 441         .recs_inorder           = xfs_inobt_recs_inorder,
 442         .keys_contiguous        = xfs_inobt_keys_contiguous,
 443 };
 444
 445 /*
 446  * Initialize a new inode btree cursor.
 447  */
 448 static struct xfs_btree_cur *
 449 xfs_inobt_init_common(
 450         struct xfs_perag        *pag,
 451         struct xfs_trans        *tp,            /* transaction pointer */
 452         xfs_btnum_t             btnum)          /* ialloc or free ino btree */
 453 {
 454         struct xfs_mount        *mp = pag->pag_mount;
 455         struct xfs_btree_cur    *cur;
 456
 457         cur = xfs_btree_alloc_cursor(mp, tp, btnum,
 458                         M_IGEO(mp)->inobt_maxlevels, xfs_inobt_cur_cache);
 459         if (btnum == XFS_BTNUM_INO) {
 460                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_ibt_2);
 461                 cur->bc_ops = &xfs_inobt_ops;
 462         } else {
 463                 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_fibt_2);
 464                 cur->bc_ops = &xfs_finobt_ops;
 465         }
 466
 467         if (xfs_has_crc(mp))
 468                 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 469
 470         cur->bc_ag.pag = xfs_perag_hold(pag);
 471         return cur;
 472 }
 473
 474 /* Create an inode btree cursor. */
 475 struct xfs_btree_cur *
 476 xfs_inobt_init_cursor(
 477         struct xfs_perag        *pag,
 478         struct xfs_trans        *tp,
 479         struct xfs_buf          *agbp,
 480         xfs_btnum_t             btnum)
 481 {
 482         struct xfs_btree_cur    *cur;
 483         struct xfs_agi          *agi = agbp->b_addr;
 484
 485         cur = xfs_inobt_init_common(pag, tp, btnum);
 486         if (btnum == XFS_BTNUM_INO)
 487                 cur->bc_nlevels = be32_to_cpu(agi->agi_level);
 488         else
 489                 cur->bc_nlevels = be32_to_cpu(agi->agi_free_level);
 490         cur->bc_ag.agbp = agbp;
 491         return cur;
 492 }
 493
 494 /* Create an inode btree cursor with a fake root for staging. */
 495 struct xfs_btree_cur *
 496 xfs_inobt_stage_cursor(
 497         struct xfs_perag        *pag,
 498         struct xbtree_afakeroot *afake,
 499         xfs_btnum_t             btnum)
 500 {
 501         struct xfs_btree_cur    *cur;
 502
 503         cur = xfs_inobt_init_common(pag, NULL, btnum);
 504         xfs_btree_stage_afakeroot(cur, afake);
 505         return cur;
 506 }
 507
 508 /*
 509  * Install a new inobt btree root.  Caller is responsible for invalidating
 510  * and freeing the old btree blocks.
 511  */
 512 void
 513 xfs_inobt_commit_staged_btree(
 514         struct xfs_btree_cur    *cur,
 515         struct xfs_trans        *tp,
 516         struct xfs_buf          *agbp)
 517 {
 518         struct xfs_agi          *agi = agbp->b_addr;
 519         struct xbtree_afakeroot *afake = cur->bc_ag.afake;
 520         int                     fields;
 521
 522         ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
 523
 524         if (cur->bc_btnum == XFS_BTNUM_INO) {
 525                 fields = XFS_AGI_ROOT | XFS_AGI_LEVEL;
 526                 agi->agi_root = cpu_to_be32(afake->af_root);
 527                 agi->agi_level = cpu_to_be32(afake->af_levels);
 528                 if (xfs_has_inobtcounts(cur->bc_mp)) {
 529                         agi->agi_iblocks = cpu_to_be32(afake->af_blocks);
 530                         fields |= XFS_AGI_IBLOCKS;
 531                 }
 532                 xfs_ialloc_log_agi(tp, agbp, fields);
 533                 xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_inobt_ops);
 534         } else {
 535                 fields = XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL;
 536                 agi->agi_free_root = cpu_to_be32(afake->af_root);
 537                 agi->agi_free_level = cpu_to_be32(afake->af_levels);
 538                 if (xfs_has_inobtcounts(cur->bc_mp)) {
 539                         agi->agi_fblocks = cpu_to_be32(afake->af_blocks);
 540                         fields |= XFS_AGI_IBLOCKS;
 541                 }
 542                 xfs_ialloc_log_agi(tp, agbp, fields);
 543                 xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_finobt_ops);
 544         }
 545 }
 546
 547 /* Calculate number of records in an inode btree block. */
 548 static inline unsigned int
 549 xfs_inobt_block_maxrecs(
 550         unsigned int            blocklen,
 551         bool                    leaf)
 552 {
 553         if (leaf)
 554                 return blocklen / sizeof(xfs_inobt_rec_t);
 555         return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
 556 }
 557
 558 /*
 559  * Calculate number of records in an inobt btree block.
 560  */
 561 int
 562 xfs_inobt_maxrecs(
 563         struct xfs_mount        *mp,
 564         int                     blocklen,
 565         int                     leaf)
 566 {
 567         blocklen -= XFS_INOBT_BLOCK_LEN(mp);
 568         return xfs_inobt_block_maxrecs(blocklen, leaf);
 569 }
 570
 571 /*
 572  * Maximum number of inode btree records per AG.  Pretend that we can fill an
 573  * entire AG completely full of inodes except for the AG headers.
 574  */
 575 #define XFS_MAX_INODE_RECORDS \
 576         ((XFS_MAX_AG_BYTES - (4 * BBSIZE)) / XFS_DINODE_MIN_SIZE) / \
 577                         XFS_INODES_PER_CHUNK
 578
 579 /* Compute the max possible height for the inode btree. */
 580 static inline unsigned int
 581 xfs_inobt_maxlevels_ondisk(void)
 582 {
 583         unsigned int            minrecs[2];
 584         unsigned int            blocklen;
 585
 586         blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN,
 587                        XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN);
 588
 589         minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2;
 590         minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2;
 591
 592         return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS);
 593 }
 594
 595 /* Compute the max possible height for the free inode btree. */
 596 static inline unsigned int
 597 xfs_finobt_maxlevels_ondisk(void)
 598 {
 599         unsigned int            minrecs[2];
 600         unsigned int            blocklen;
 601
 602         blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN;
 603
 604         minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2;
 605         minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2;
 606
 607         return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS);
 608 }
 609
 610 /* Compute the max possible height for either inode btree. */
 611 unsigned int
 612 xfs_iallocbt_maxlevels_ondisk(void)
 613 {
 614         return max(xfs_inobt_maxlevels_ondisk(),
 615                    xfs_finobt_maxlevels_ondisk());
 616 }
 617
 618 /*
 619  * Convert the inode record holemask to an inode allocation bitmap. The inode
 620  * allocation bitmap is inode granularity and specifies whether an inode is
 621  * physically allocated on disk (not whether the inode is considered allocated
 622  * or free by the fs).
 623  *
 624  * A bit value of 1 means the inode is allocated, a value of 0 means it is free.
 625  */
 626 uint64_t
 627 xfs_inobt_irec_to_allocmask(
 628         const struct xfs_inobt_rec_incore       *rec)
 629 {
 630         uint64_t                        bitmap = 0;
 631         uint64_t                        inodespbit;
 632         int                             nextbit;
 633         uint                            allocbitmap;
 634
 635         /*
 636          * The holemask has 16-bits for a 64 inode record. Therefore each
 637          * holemask bit represents multiple inodes. Create a mask of bits to set
 638          * in the allocmask for each holemask bit.
 639          */
 640         inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1;
 641
 642         /*
 643          * Allocated inodes are represented by 0 bits in holemask. Invert the 0
 644          * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask
 645          * anything beyond the 16 holemask bits since this casts to a larger
 646          * type.
 647          */
 648         allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1);
 649
 650         /*
 651          * allocbitmap is the inverted holemask so every set bit represents
 652          * allocated inodes. To expand from 16-bit holemask granularity to
 653          * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target
 654          * bitmap for every holemask bit.
 655          */
 656         nextbit = xfs_next_bit(&allocbitmap, 1, 0);
 657         while (nextbit != -1) {
 658                 ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY));
 659
 660                 bitmap |= (inodespbit <<
 661                            (nextbit * XFS_INODES_PER_HOLEMASK_BIT));
 662
 663                 nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1);
 664         }
 665
 666         return bitmap;
 667 }
 668
 669 #if defined(DEBUG) || defined(XFS_WARN)
 670 /*
 671  * Verify that an in-core inode record has a valid inode count.
 672  */
 673 int
 674 xfs_inobt_rec_check_count(
 675         struct xfs_mount                *mp,
 676         struct xfs_inobt_rec_incore     *rec)
 677 {
 678         int                             inocount = 0;
 679         int                             nextbit = 0;
 680         uint64_t                        allocbmap;
 681         int                             wordsz;
 682
 683         wordsz = sizeof(allocbmap) / sizeof(unsigned int);
 684         allocbmap = xfs_inobt_irec_to_allocmask(rec);
 685
 686         nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit);
 687         while (nextbit != -1) {
 688                 inocount++;
 689                 nextbit = xfs_next_bit((uint *) &allocbmap, wordsz,
 690                                        nextbit + 1);
 691         }
 692
 693         if (inocount != rec->ir_count)
 694                 return -EFSCORRUPTED;
 695
 696         return 0;
 697 }
 698 #endif  /* DEBUG */
 699
 700 static xfs_extlen_t
 701 xfs_inobt_max_size(
 702         struct xfs_perag        *pag)
 703 {
 704         struct xfs_mount        *mp = pag->pag_mount;
 705         xfs_agblock_t           agblocks = pag->block_count;
 706
 707         /* Bail out if we're uninitialized, which can happen in mkfs. */
 708         if (M_IGEO(mp)->inobt_mxr[0] == 0)
 709                 return 0;
 710
 711         /*
 712          * The log is permanently allocated, so the space it occupies will
 713          * never be available for the kinds of things that would require btree
 714          * expansion.  We therefore can pretend the space isn't there.
 715          */
 716         if (xfs_ag_contains_log(mp, pag->pag_agno))
 717                 agblocks -= mp->m_sb.sb_logblocks;
 718
 719         return xfs_btree_calc_size(M_IGEO(mp)->inobt_mnr,
 720                                 (uint64_t)agblocks * mp->m_sb.sb_inopblock /
 721                                         XFS_INODES_PER_CHUNK);
 722 }
 723
 724 /* Read AGI and create inobt cursor. */
 725 int
 726 xfs_inobt_cur(
 727         struct xfs_perag        *pag,
 728         struct xfs_trans        *tp,
 729         xfs_btnum_t             which,
 730         struct xfs_btree_cur    **curpp,
 731         struct xfs_buf          **agi_bpp)
 732 {
 733         struct xfs_btree_cur    *cur;
 734         int                     error;
 735
 736         ASSERT(*agi_bpp == NULL);
 737         ASSERT(*curpp == NULL);
 738
 739         error = xfs_ialloc_read_agi(pag, tp, agi_bpp);
 740         if (error)
 741                 return error;
 742
 743         cur = xfs_inobt_init_cursor(pag, tp, *agi_bpp, which);
 744         *curpp = cur;
 745         return 0;
 746 }
 747
 748 static int
 749 xfs_inobt_count_blocks(
 750         struct xfs_perag        *pag,
 751         struct xfs_trans        *tp,
 752         xfs_btnum_t             btnum,
 753         xfs_extlen_t            *tree_blocks)
 754 {
 755         struct xfs_buf          *agbp = NULL;
 756         struct xfs_btree_cur    *cur = NULL;
 757         int                     error;
 758
 759         error = xfs_inobt_cur(pag, tp, btnum, &cur, &agbp);
 760         if (error)
 761                 return error;
 762
 763         error = xfs_btree_count_blocks(cur, tree_blocks);
 764         xfs_btree_del_cursor(cur, error);
 765         xfs_trans_brelse(tp, agbp);
 766
 767         return error;
 768 }
 769
 770 /* Read finobt block count from AGI header. */
 771 static int
 772 xfs_finobt_read_blocks(
 773         struct xfs_perag        *pag,
 774         struct xfs_trans        *tp,
 775         xfs_extlen_t            *tree_blocks)
 776 {
 777         struct xfs_buf          *agbp;
 778         struct xfs_agi          *agi;
 779         int                     error;
 780
 781         error = xfs_ialloc_read_agi(pag, tp, &agbp);
 782         if (error)
 783                 return error;
 784
 785         agi = agbp->b_addr;
 786         *tree_blocks = be32_to_cpu(agi->agi_fblocks);
 787         xfs_trans_brelse(tp, agbp);
 788         return 0;
 789 }
 790
 791 /*
 792  * Figure out how many blocks to reserve and how many are used by this btree.
 793  */
 794 int
 795 xfs_finobt_calc_reserves(
 796         struct xfs_perag        *pag,
 797         struct xfs_trans        *tp,
 798         xfs_extlen_t            *ask,
 799         xfs_extlen_t            *used)
 800 {
 801         xfs_extlen_t            tree_len = 0;
 802         int                     error;
 803
 804         if (!xfs_has_finobt(pag->pag_mount))
 805                 return 0;
 806
 807         if (xfs_has_inobtcounts(pag->pag_mount))
 808                 error = xfs_finobt_read_blocks(pag, tp, &tree_len);
 809         else
 810                 error = xfs_inobt_count_blocks(pag, tp, XFS_BTNUM_FINO,
 811                                 &tree_len);
 812         if (error)
 813                 return error;
 814
 815         *ask += xfs_inobt_max_size(pag);
 816         *used += tree_len;
 817         return 0;
 818 }
 819
 820 /* Calculate the inobt btree size for some records. */
 821 xfs_extlen_t
 822 xfs_iallocbt_calc_size(
 823         struct xfs_mount        *mp,
 824         unsigned long long      len)
 825 {
 826         return xfs_btree_calc_size(M_IGEO(mp)->inobt_mnr, len);
 827 }
 828
 829 int __init
 830 xfs_inobt_init_cur_cache(void)
 831 {
 832         xfs_inobt_cur_cache = kmem_cache_create("xfs_inobt_cur",
 833                         xfs_btree_cur_sizeof(xfs_inobt_maxlevels_ondisk()),
 834                         0, 0, NULL);
 835
 836         if (!xfs_inobt_cur_cache)
 837                 return -ENOMEM;
 838         return 0;
 839 }
 840
 841 void
 842 xfs_inobt_destroy_cur_cache(void)
 843 {
 844         kmem_cache_destroy(xfs_inobt_cur_cache);
 845         xfs_inobt_cur_cache = NULL;
 846 }