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