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