1 /* 2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc. 3 * All Rights Reserved. 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public License as 7 * published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it would be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 #include "xfs.h" 19 #include "xfs_fs.h" 20 #include "xfs_shared.h" 21 #include "xfs_format.h" 22 #include "xfs_log_format.h" 23 #include "xfs_trans_resv.h" 24 #include "xfs_bit.h" 25 #include "xfs_mount.h" 26 #include "xfs_inode.h" 27 #include "xfs_btree.h" 28 #include "xfs_ialloc.h" 29 #include "xfs_ialloc_btree.h" 30 #include "xfs_alloc.h" 31 #include "xfs_error.h" 32 #include "xfs_trace.h" 33 #include "xfs_cksum.h" 34 #include "xfs_trans.h" 35 #include "xfs_rmap.h" 36 37 38 STATIC int 39 xfs_inobt_get_minrecs( 40 struct xfs_btree_cur *cur, 41 int level) 42 { 43 return cur->bc_mp->m_inobt_mnr[level != 0]; 44 } 45 46 STATIC struct xfs_btree_cur * 47 xfs_inobt_dup_cursor( 48 struct xfs_btree_cur *cur) 49 { 50 return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp, 51 cur->bc_private.a.agbp, cur->bc_private.a.agno, 52 cur->bc_btnum); 53 } 54 55 STATIC void 56 xfs_inobt_set_root( 57 struct xfs_btree_cur *cur, 58 union xfs_btree_ptr *nptr, 59 int inc) /* level change */ 60 { 61 struct xfs_buf *agbp = cur->bc_private.a.agbp; 62 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 63 64 agi->agi_root = nptr->s; 65 be32_add_cpu(&agi->agi_level, inc); 66 xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL); 67 } 68 69 STATIC void 70 xfs_finobt_set_root( 71 struct xfs_btree_cur *cur, 72 union xfs_btree_ptr *nptr, 73 int inc) /* level change */ 74 { 75 struct xfs_buf *agbp = cur->bc_private.a.agbp; 76 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 77 78 agi->agi_free_root = nptr->s; 79 be32_add_cpu(&agi->agi_free_level, inc); 80 xfs_ialloc_log_agi(cur->bc_tp, agbp, 81 XFS_AGI_FREE_ROOT | XFS_AGI_FREE_LEVEL); 82 } 83 84 STATIC int 85 __xfs_inobt_alloc_block( 86 struct xfs_btree_cur *cur, 87 union xfs_btree_ptr *start, 88 union xfs_btree_ptr *new, 89 int *stat, 90 enum xfs_ag_resv_type resv) 91 { 92 xfs_alloc_arg_t args; /* block allocation args */ 93 int error; /* error return value */ 94 xfs_agblock_t sbno = be32_to_cpu(start->s); 95 96 memset(&args, 0, sizeof(args)); 97 args.tp = cur->bc_tp; 98 args.mp = cur->bc_mp; 99 xfs_rmap_ag_owner(&args.oinfo, XFS_RMAP_OWN_INOBT); 100 args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno); 101 args.minlen = 1; 102 args.maxlen = 1; 103 args.prod = 1; 104 args.type = XFS_ALLOCTYPE_NEAR_BNO; 105 args.resv = resv; 106 107 error = xfs_alloc_vextent(&args); 108 if (error) 109 return error; 110 111 if (args.fsbno == NULLFSBLOCK) { 112 *stat = 0; 113 return 0; 114 } 115 ASSERT(args.len == 1); 116 117 new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno)); 118 *stat = 1; 119 return 0; 120 } 121 122 STATIC int 123 xfs_inobt_alloc_block( 124 struct xfs_btree_cur *cur, 125 union xfs_btree_ptr *start, 126 union xfs_btree_ptr *new, 127 int *stat) 128 { 129 return __xfs_inobt_alloc_block(cur, start, new, stat, XFS_AG_RESV_NONE); 130 } 131 132 STATIC int 133 xfs_finobt_alloc_block( 134 struct xfs_btree_cur *cur, 135 union xfs_btree_ptr *start, 136 union xfs_btree_ptr *new, 137 int *stat) 138 { 139 if (cur->bc_mp->m_inotbt_nores) 140 return xfs_inobt_alloc_block(cur, start, new, stat); 141 return __xfs_inobt_alloc_block(cur, start, new, stat, 142 XFS_AG_RESV_METADATA); 143 } 144 145 STATIC int 146 __xfs_inobt_free_block( 147 struct xfs_btree_cur *cur, 148 struct xfs_buf *bp, 149 enum xfs_ag_resv_type resv) 150 { 151 struct xfs_owner_info oinfo; 152 153 xfs_rmap_ag_owner(&oinfo, XFS_RMAP_OWN_INOBT); 154 return xfs_free_extent(cur->bc_tp, 155 XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp)), 1, 156 &oinfo, resv); 157 } 158 159 STATIC int 160 xfs_inobt_free_block( 161 struct xfs_btree_cur *cur, 162 struct xfs_buf *bp) 163 { 164 return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_NONE); 165 } 166 167 STATIC int 168 xfs_finobt_free_block( 169 struct xfs_btree_cur *cur, 170 struct xfs_buf *bp) 171 { 172 if (cur->bc_mp->m_inotbt_nores) 173 return xfs_inobt_free_block(cur, bp); 174 return __xfs_inobt_free_block(cur, bp, XFS_AG_RESV_METADATA); 175 } 176 177 STATIC int 178 xfs_inobt_get_maxrecs( 179 struct xfs_btree_cur *cur, 180 int level) 181 { 182 return cur->bc_mp->m_inobt_mxr[level != 0]; 183 } 184 185 STATIC void 186 xfs_inobt_init_key_from_rec( 187 union xfs_btree_key *key, 188 union xfs_btree_rec *rec) 189 { 190 key->inobt.ir_startino = rec->inobt.ir_startino; 191 } 192 193 STATIC void 194 xfs_inobt_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->inobt.ir_startino); 201 x += XFS_INODES_PER_CHUNK - 1; 202 key->inobt.ir_startino = cpu_to_be32(x); 203 } 204 205 STATIC void 206 xfs_inobt_init_rec_from_cur( 207 struct xfs_btree_cur *cur, 208 union xfs_btree_rec *rec) 209 { 210 rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino); 211 if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) { 212 rec->inobt.ir_u.sp.ir_holemask = 213 cpu_to_be16(cur->bc_rec.i.ir_holemask); 214 rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count; 215 rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount; 216 } else { 217 /* ir_holemask/ir_count not supported on-disk */ 218 rec->inobt.ir_u.f.ir_freecount = 219 cpu_to_be32(cur->bc_rec.i.ir_freecount); 220 } 221 rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free); 222 } 223 224 /* 225 * initial value of ptr for lookup 226 */ 227 STATIC void 228 xfs_inobt_init_ptr_from_cur( 229 struct xfs_btree_cur *cur, 230 union xfs_btree_ptr *ptr) 231 { 232 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 233 234 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 235 236 ptr->s = agi->agi_root; 237 } 238 239 STATIC void 240 xfs_finobt_init_ptr_from_cur( 241 struct xfs_btree_cur *cur, 242 union xfs_btree_ptr *ptr) 243 { 244 struct xfs_agi *agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp); 245 246 ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno)); 247 ptr->s = agi->agi_free_root; 248 } 249 250 STATIC int64_t 251 xfs_inobt_key_diff( 252 struct xfs_btree_cur *cur, 253 union xfs_btree_key *key) 254 { 255 return (int64_t)be32_to_cpu(key->inobt.ir_startino) - 256 cur->bc_rec.i.ir_startino; 257 } 258 259 STATIC int64_t 260 xfs_inobt_diff_two_keys( 261 struct xfs_btree_cur *cur, 262 union xfs_btree_key *k1, 263 union xfs_btree_key *k2) 264 { 265 return (int64_t)be32_to_cpu(k1->inobt.ir_startino) - 266 be32_to_cpu(k2->inobt.ir_startino); 267 } 268 269 static xfs_failaddr_t 270 xfs_inobt_verify( 271 struct xfs_buf *bp) 272 { 273 struct xfs_mount *mp = bp->b_target->bt_mount; 274 struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); 275 xfs_failaddr_t fa; 276 unsigned int level; 277 278 /* 279 * During growfs operations, we can't verify the exact owner as the 280 * perag is not fully initialised and hence not attached to the buffer. 281 * 282 * Similarly, during log recovery we will have a perag structure 283 * attached, but the agi information will not yet have been initialised 284 * from the on disk AGI. We don't currently use any of this information, 285 * but beware of the landmine (i.e. need to check pag->pagi_init) if we 286 * ever do. 287 */ 288 switch (block->bb_magic) { 289 case cpu_to_be32(XFS_IBT_CRC_MAGIC): 290 case cpu_to_be32(XFS_FIBT_CRC_MAGIC): 291 fa = xfs_btree_sblock_v5hdr_verify(bp); 292 if (fa) 293 return fa; 294 /* fall through */ 295 case cpu_to_be32(XFS_IBT_MAGIC): 296 case cpu_to_be32(XFS_FIBT_MAGIC): 297 break; 298 default: 299 return NULL; 300 } 301 302 /* level verification */ 303 level = be16_to_cpu(block->bb_level); 304 if (level >= mp->m_in_maxlevels) 305 return __this_address; 306 307 return xfs_btree_sblock_verify(bp, mp->m_inobt_mxr[level != 0]); 308 } 309 310 static void 311 xfs_inobt_read_verify( 312 struct xfs_buf *bp) 313 { 314 xfs_failaddr_t fa; 315 316 if (!xfs_btree_sblock_verify_crc(bp)) 317 xfs_verifier_error(bp, -EFSBADCRC, __this_address); 318 else { 319 fa = xfs_inobt_verify(bp); 320 if (fa) 321 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 322 } 323 324 if (bp->b_error) 325 trace_xfs_btree_corrupt(bp, _RET_IP_); 326 } 327 328 static void 329 xfs_inobt_write_verify( 330 struct xfs_buf *bp) 331 { 332 xfs_failaddr_t fa; 333 334 fa = xfs_inobt_verify(bp); 335 if (fa) { 336 trace_xfs_btree_corrupt(bp, _RET_IP_); 337 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 338 return; 339 } 340 xfs_btree_sblock_calc_crc(bp); 341 342 } 343 344 const struct xfs_buf_ops xfs_inobt_buf_ops = { 345 .name = "xfs_inobt", 346 .verify_read = xfs_inobt_read_verify, 347 .verify_write = xfs_inobt_write_verify, 348 .verify_struct = xfs_inobt_verify, 349 }; 350 351 STATIC int 352 xfs_inobt_keys_inorder( 353 struct xfs_btree_cur *cur, 354 union xfs_btree_key *k1, 355 union xfs_btree_key *k2) 356 { 357 return be32_to_cpu(k1->inobt.ir_startino) < 358 be32_to_cpu(k2->inobt.ir_startino); 359 } 360 361 STATIC int 362 xfs_inobt_recs_inorder( 363 struct xfs_btree_cur *cur, 364 union xfs_btree_rec *r1, 365 union xfs_btree_rec *r2) 366 { 367 return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <= 368 be32_to_cpu(r2->inobt.ir_startino); 369 } 370 371 static const struct xfs_btree_ops xfs_inobt_ops = { 372 .rec_len = sizeof(xfs_inobt_rec_t), 373 .key_len = sizeof(xfs_inobt_key_t), 374 375 .dup_cursor = xfs_inobt_dup_cursor, 376 .set_root = xfs_inobt_set_root, 377 .alloc_block = xfs_inobt_alloc_block, 378 .free_block = xfs_inobt_free_block, 379 .get_minrecs = xfs_inobt_get_minrecs, 380 .get_maxrecs = xfs_inobt_get_maxrecs, 381 .init_key_from_rec = xfs_inobt_init_key_from_rec, 382 .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec, 383 .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 384 .init_ptr_from_cur = xfs_inobt_init_ptr_from_cur, 385 .key_diff = xfs_inobt_key_diff, 386 .buf_ops = &xfs_inobt_buf_ops, 387 .diff_two_keys = xfs_inobt_diff_two_keys, 388 .keys_inorder = xfs_inobt_keys_inorder, 389 .recs_inorder = xfs_inobt_recs_inorder, 390 }; 391 392 static const struct xfs_btree_ops xfs_finobt_ops = { 393 .rec_len = sizeof(xfs_inobt_rec_t), 394 .key_len = sizeof(xfs_inobt_key_t), 395 396 .dup_cursor = xfs_inobt_dup_cursor, 397 .set_root = xfs_finobt_set_root, 398 .alloc_block = xfs_finobt_alloc_block, 399 .free_block = xfs_finobt_free_block, 400 .get_minrecs = xfs_inobt_get_minrecs, 401 .get_maxrecs = xfs_inobt_get_maxrecs, 402 .init_key_from_rec = xfs_inobt_init_key_from_rec, 403 .init_high_key_from_rec = xfs_inobt_init_high_key_from_rec, 404 .init_rec_from_cur = xfs_inobt_init_rec_from_cur, 405 .init_ptr_from_cur = xfs_finobt_init_ptr_from_cur, 406 .key_diff = xfs_inobt_key_diff, 407 .buf_ops = &xfs_inobt_buf_ops, 408 .diff_two_keys = xfs_inobt_diff_two_keys, 409 .keys_inorder = xfs_inobt_keys_inorder, 410 .recs_inorder = xfs_inobt_recs_inorder, 411 }; 412 413 /* 414 * Allocate a new inode btree cursor. 415 */ 416 struct xfs_btree_cur * /* new inode btree cursor */ 417 xfs_inobt_init_cursor( 418 struct xfs_mount *mp, /* file system mount point */ 419 struct xfs_trans *tp, /* transaction pointer */ 420 struct xfs_buf *agbp, /* buffer for agi structure */ 421 xfs_agnumber_t agno, /* allocation group number */ 422 xfs_btnum_t btnum) /* ialloc or free ino btree */ 423 { 424 struct xfs_agi *agi = XFS_BUF_TO_AGI(agbp); 425 struct xfs_btree_cur *cur; 426 427 cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS); 428 429 cur->bc_tp = tp; 430 cur->bc_mp = mp; 431 cur->bc_btnum = btnum; 432 if (btnum == XFS_BTNUM_INO) { 433 cur->bc_nlevels = be32_to_cpu(agi->agi_level); 434 cur->bc_ops = &xfs_inobt_ops; 435 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_ibt_2); 436 } else { 437 cur->bc_nlevels = be32_to_cpu(agi->agi_free_level); 438 cur->bc_ops = &xfs_finobt_ops; 439 cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_fibt_2); 440 } 441 442 cur->bc_blocklog = mp->m_sb.sb_blocklog; 443 444 if (xfs_sb_version_hascrc(&mp->m_sb)) 445 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS; 446 447 cur->bc_private.a.agbp = agbp; 448 cur->bc_private.a.agno = agno; 449 450 return cur; 451 } 452 453 /* 454 * Calculate number of records in an inobt btree block. 455 */ 456 int 457 xfs_inobt_maxrecs( 458 struct xfs_mount *mp, 459 int blocklen, 460 int leaf) 461 { 462 blocklen -= XFS_INOBT_BLOCK_LEN(mp); 463 464 if (leaf) 465 return blocklen / sizeof(xfs_inobt_rec_t); 466 return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); 467 } 468 469 /* 470 * Convert the inode record holemask to an inode allocation bitmap. The inode 471 * allocation bitmap is inode granularity and specifies whether an inode is 472 * physically allocated on disk (not whether the inode is considered allocated 473 * or free by the fs). 474 * 475 * A bit value of 1 means the inode is allocated, a value of 0 means it is free. 476 */ 477 uint64_t 478 xfs_inobt_irec_to_allocmask( 479 struct xfs_inobt_rec_incore *rec) 480 { 481 uint64_t bitmap = 0; 482 uint64_t inodespbit; 483 int nextbit; 484 uint allocbitmap; 485 486 /* 487 * The holemask has 16-bits for a 64 inode record. Therefore each 488 * holemask bit represents multiple inodes. Create a mask of bits to set 489 * in the allocmask for each holemask bit. 490 */ 491 inodespbit = (1 << XFS_INODES_PER_HOLEMASK_BIT) - 1; 492 493 /* 494 * Allocated inodes are represented by 0 bits in holemask. Invert the 0 495 * bits to 1 and convert to a uint so we can use xfs_next_bit(). Mask 496 * anything beyond the 16 holemask bits since this casts to a larger 497 * type. 498 */ 499 allocbitmap = ~rec->ir_holemask & ((1 << XFS_INOBT_HOLEMASK_BITS) - 1); 500 501 /* 502 * allocbitmap is the inverted holemask so every set bit represents 503 * allocated inodes. To expand from 16-bit holemask granularity to 504 * 64-bit (e.g., bit-per-inode), set inodespbit bits in the target 505 * bitmap for every holemask bit. 506 */ 507 nextbit = xfs_next_bit(&allocbitmap, 1, 0); 508 while (nextbit != -1) { 509 ASSERT(nextbit < (sizeof(rec->ir_holemask) * NBBY)); 510 511 bitmap |= (inodespbit << 512 (nextbit * XFS_INODES_PER_HOLEMASK_BIT)); 513 514 nextbit = xfs_next_bit(&allocbitmap, 1, nextbit + 1); 515 } 516 517 return bitmap; 518 } 519 520 #if defined(DEBUG) || defined(XFS_WARN) 521 /* 522 * Verify that an in-core inode record has a valid inode count. 523 */ 524 int 525 xfs_inobt_rec_check_count( 526 struct xfs_mount *mp, 527 struct xfs_inobt_rec_incore *rec) 528 { 529 int inocount = 0; 530 int nextbit = 0; 531 uint64_t allocbmap; 532 int wordsz; 533 534 wordsz = sizeof(allocbmap) / sizeof(unsigned int); 535 allocbmap = xfs_inobt_irec_to_allocmask(rec); 536 537 nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, nextbit); 538 while (nextbit != -1) { 539 inocount++; 540 nextbit = xfs_next_bit((uint *) &allocbmap, wordsz, 541 nextbit + 1); 542 } 543 544 if (inocount != rec->ir_count) 545 return -EFSCORRUPTED; 546 547 return 0; 548 } 549 #endif /* DEBUG */ 550 551 static xfs_extlen_t 552 xfs_inobt_max_size( 553 struct xfs_mount *mp) 554 { 555 /* Bail out if we're uninitialized, which can happen in mkfs. */ 556 if (mp->m_inobt_mxr[0] == 0) 557 return 0; 558 559 return xfs_btree_calc_size(mp->m_inobt_mnr, 560 (uint64_t)mp->m_sb.sb_agblocks * mp->m_sb.sb_inopblock / 561 XFS_INODES_PER_CHUNK); 562 } 563 564 static int 565 xfs_inobt_count_blocks( 566 struct xfs_mount *mp, 567 xfs_agnumber_t agno, 568 xfs_btnum_t btnum, 569 xfs_extlen_t *tree_blocks) 570 { 571 struct xfs_buf *agbp; 572 struct xfs_btree_cur *cur; 573 int error; 574 575 error = xfs_ialloc_read_agi(mp, NULL, agno, &agbp); 576 if (error) 577 return error; 578 579 cur = xfs_inobt_init_cursor(mp, NULL, agbp, agno, btnum); 580 error = xfs_btree_count_blocks(cur, tree_blocks); 581 xfs_btree_del_cursor(cur, error ? XFS_BTREE_ERROR : XFS_BTREE_NOERROR); 582 xfs_buf_relse(agbp); 583 584 return error; 585 } 586 587 /* 588 * Figure out how many blocks to reserve and how many are used by this btree. 589 */ 590 int 591 xfs_finobt_calc_reserves( 592 struct xfs_mount *mp, 593 xfs_agnumber_t agno, 594 xfs_extlen_t *ask, 595 xfs_extlen_t *used) 596 { 597 xfs_extlen_t tree_len = 0; 598 int error; 599 600 if (!xfs_sb_version_hasfinobt(&mp->m_sb)) 601 return 0; 602 603 error = xfs_inobt_count_blocks(mp, agno, XFS_BTNUM_FINO, &tree_len); 604 if (error) 605 return error; 606 607 *ask += xfs_inobt_max_size(mp); 608 *used += tree_len; 609 return 0; 610 } 611