FILE
xfs_ialloc.c
File preview with syntax highlighting.
linux-6.19.14/fs/xfs/libxfs/xfs_ialloc.c
1// SPDX-License-Identifier: GPL-2.0 2/* 3 * Copyright (c) 2000-2002,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_inode.h" 15#include "xfs_btree.h" 16#include "xfs_ialloc.h" 17#include "xfs_ialloc_btree.h" 18#include "xfs_alloc.h" 19#include "xfs_errortag.h" 20#include "xfs_error.h" 21#include "xfs_bmap.h" 22#include "xfs_trans.h" 23#include "xfs_buf_item.h" 24#include "xfs_icreate_item.h" 25#include "xfs_icache.h" 26#include "xfs_trace.h" 27#include "xfs_log.h" 28#include "xfs_rmap.h" 29#include "xfs_ag.h" 30#include "xfs_health.h" 31 32/* 33 * Lookup a record by ino in the btree given by cur. 34 */ 35int /* error */ 36xfs_inobt_lookup( 37 struct xfs_btree_cur *cur, /* btree cursor */ 38 xfs_agino_t ino, /* starting inode of chunk */ 39 xfs_lookup_t dir, /* <=, >=, == */ 40 int *stat) /* success/failure */ 41{ 42 cur->bc_rec.i.ir_startino = ino; 43 cur->bc_rec.i.ir_holemask = 0; 44 cur->bc_rec.i.ir_count = 0; 45 cur->bc_rec.i.ir_freecount = 0; 46 cur->bc_rec.i.ir_free = 0; 47 return xfs_btree_lookup(cur, dir, stat); 48} 49 50/* 51 * Update the record referred to by cur to the value given. 52 * This either works (return 0) or gets an EFSCORRUPTED error. 53 */ 54STATIC int /* error */ 55xfs_inobt_update( 56 struct xfs_btree_cur *cur, /* btree cursor */ 57 xfs_inobt_rec_incore_t *irec) /* btree record */ 58{ 59 union xfs_btree_rec rec; 60 61 rec.inobt.ir_startino = cpu_to_be32(irec->ir_startino); 62 if (xfs_has_sparseinodes(cur->bc_mp)) { 63 rec.inobt.ir_u.sp.ir_holemask = cpu_to_be16(irec->ir_holemask); 64 rec.inobt.ir_u.sp.ir_count = irec->ir_count; 65 rec.inobt.ir_u.sp.ir_freecount = irec->ir_freecount; 66 } else { 67 /* ir_holemask/ir_count not supported on-disk */ 68 rec.inobt.ir_u.f.ir_freecount = cpu_to_be32(irec->ir_freecount); 69 } 70 rec.inobt.ir_free = cpu_to_be64(irec->ir_free); 71 return xfs_btree_update(cur, &rec); 72} 73 74/* Convert on-disk btree record to incore inobt record. */ 75void 76xfs_inobt_btrec_to_irec( 77 struct xfs_mount *mp, 78 const union xfs_btree_rec *rec, 79 struct xfs_inobt_rec_incore *irec) 80{ 81 irec->ir_startino = be32_to_cpu(rec->inobt.ir_startino); 82 if (xfs_has_sparseinodes(mp)) { 83 irec->ir_holemask = be16_to_cpu(rec->inobt.ir_u.sp.ir_holemask); 84 irec->ir_count = rec->inobt.ir_u.sp.ir_count; 85 irec->ir_freecount = rec->inobt.ir_u.sp.ir_freecount; 86 } else { 87 /* 88 * ir_holemask/ir_count not supported on-disk. Fill in hardcoded 89 * values for full inode chunks. 90 */ 91 irec->ir_holemask = XFS_INOBT_HOLEMASK_FULL; 92 irec->ir_count = XFS_INODES_PER_CHUNK; 93 irec->ir_freecount = 94 be32_to_cpu(rec->inobt.ir_u.f.ir_freecount); 95 } 96 irec->ir_free = be64_to_cpu(rec->inobt.ir_free); 97} 98 99/* Compute the freecount of an incore inode record. */ 100uint8_t 101xfs_inobt_rec_freecount( 102 const struct xfs_inobt_rec_incore *irec) 103{ 104 uint64_t realfree = irec->ir_free; 105 106 if (xfs_inobt_issparse(irec->ir_holemask)) 107 realfree &= xfs_inobt_irec_to_allocmask(irec); 108 return hweight64(realfree); 109} 110 111/* Simple checks for inode records. */ 112xfs_failaddr_t 113xfs_inobt_check_irec( 114 struct xfs_perag *pag, 115 const struct xfs_inobt_rec_incore *irec) 116{ 117 /* Record has to be properly aligned within the AG. */ 118 if (!xfs_verify_agino(pag, irec->ir_startino)) 119 return __this_address; 120 if (!xfs_verify_agino(pag, 121 irec->ir_startino + XFS_INODES_PER_CHUNK - 1)) 122 return __this_address; 123 if (irec->ir_count < XFS_INODES_PER_HOLEMASK_BIT || 124 irec->ir_count > XFS_INODES_PER_CHUNK) 125 return __this_address; 126 if (irec->ir_freecount > XFS_INODES_PER_CHUNK) 127 return __this_address; 128 129 if (xfs_inobt_rec_freecount(irec) != irec->ir_freecount) 130 return __this_address; 131 132 return NULL; 133} 134 135static inline int 136xfs_inobt_complain_bad_rec( 137 struct xfs_btree_cur *cur, 138 xfs_failaddr_t fa, 139 const struct xfs_inobt_rec_incore *irec) 140{ 141 struct xfs_mount *mp = cur->bc_mp; 142 143 xfs_warn(mp, 144 "%sbt record corruption in AG %d detected at %pS!", 145 cur->bc_ops->name, cur->bc_group->xg_gno, fa); 146 xfs_warn(mp, 147"start inode 0x%x, count 0x%x, free 0x%x freemask 0x%llx, holemask 0x%x", 148 irec->ir_startino, irec->ir_count, irec->ir_freecount, 149 irec->ir_free, irec->ir_holemask); 150 xfs_btree_mark_sick(cur); 151 return -EFSCORRUPTED; 152} 153 154/* 155 * Get the data from the pointed-to record. 156 */ 157int 158xfs_inobt_get_rec( 159 struct xfs_btree_cur *cur, 160 struct xfs_inobt_rec_incore *irec, 161 int *stat) 162{ 163 struct xfs_mount *mp = cur->bc_mp; 164 union xfs_btree_rec *rec; 165 xfs_failaddr_t fa; 166 int error; 167 168 error = xfs_btree_get_rec(cur, &rec, stat); 169 if (error || *stat == 0) 170 return error; 171 172 xfs_inobt_btrec_to_irec(mp, rec, irec); 173 fa = xfs_inobt_check_irec(to_perag(cur->bc_group), irec); 174 if (fa) 175 return xfs_inobt_complain_bad_rec(cur, fa, irec); 176 177 return 0; 178} 179 180/* 181 * Insert a single inobt record. Cursor must already point to desired location. 182 */ 183int 184xfs_inobt_insert_rec( 185 struct xfs_btree_cur *cur, 186 uint16_t holemask, 187 uint8_t count, 188 int32_t freecount, 189 xfs_inofree_t free, 190 int *stat) 191{ 192 cur->bc_rec.i.ir_holemask = holemask; 193 cur->bc_rec.i.ir_count = count; 194 cur->bc_rec.i.ir_freecount = freecount; 195 cur->bc_rec.i.ir_free = free; 196 return xfs_btree_insert(cur, stat); 197} 198 199/* 200 * Insert records describing a newly allocated inode chunk into the inobt. 201 */ 202STATIC int 203xfs_inobt_insert( 204 struct xfs_perag *pag, 205 struct xfs_trans *tp, 206 struct xfs_buf *agbp, 207 xfs_agino_t newino, 208 xfs_agino_t newlen, 209 bool is_finobt) 210{ 211 struct xfs_btree_cur *cur; 212 xfs_agino_t thisino; 213 int i; 214 int error; 215 216 if (is_finobt) 217 cur = xfs_finobt_init_cursor(pag, tp, agbp); 218 else 219 cur = xfs_inobt_init_cursor(pag, tp, agbp); 220 221 for (thisino = newino; 222 thisino < newino + newlen; 223 thisino += XFS_INODES_PER_CHUNK) { 224 error = xfs_inobt_lookup(cur, thisino, XFS_LOOKUP_EQ, &i); 225 if (error) { 226 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 227 return error; 228 } 229 ASSERT(i == 0); 230 231 error = xfs_inobt_insert_rec(cur, XFS_INOBT_HOLEMASK_FULL, 232 XFS_INODES_PER_CHUNK, 233 XFS_INODES_PER_CHUNK, 234 XFS_INOBT_ALL_FREE, &i); 235 if (error) { 236 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 237 return error; 238 } 239 ASSERT(i == 1); 240 } 241 242 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 243 244 return 0; 245} 246 247/* 248 * Verify that the number of free inodes in the AGI is correct. 249 */ 250#ifdef DEBUG 251static int 252xfs_check_agi_freecount( 253 struct xfs_btree_cur *cur) 254{ 255 if (cur->bc_nlevels == 1) { 256 xfs_inobt_rec_incore_t rec; 257 int freecount = 0; 258 int error; 259 int i; 260 261 error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i); 262 if (error) 263 return error; 264 265 do { 266 error = xfs_inobt_get_rec(cur, &rec, &i); 267 if (error) 268 return error; 269 270 if (i) { 271 freecount += rec.ir_freecount; 272 error = xfs_btree_increment(cur, 0, &i); 273 if (error) 274 return error; 275 } 276 } while (i == 1); 277 278 if (!xfs_is_shutdown(cur->bc_mp)) { 279 ASSERT(freecount == 280 to_perag(cur->bc_group)->pagi_freecount); 281 } 282 } 283 return 0; 284} 285#else 286#define xfs_check_agi_freecount(cur) 0 287#endif 288 289/* 290 * Initialise a new set of inodes. When called without a transaction context 291 * (e.g. from recovery) we initiate a delayed write of the inode buffers rather 292 * than logging them (which in a transaction context puts them into the AIL 293 * for writeback rather than the xfsbufd queue). 294 */ 295int 296xfs_ialloc_inode_init( 297 struct xfs_mount *mp, 298 struct xfs_trans *tp, 299 struct list_head *buffer_list, 300 int icount, 301 xfs_agnumber_t agno, 302 xfs_agblock_t agbno, 303 xfs_agblock_t length, 304 unsigned int gen) 305{ 306 struct xfs_buf *fbuf; 307 struct xfs_dinode *free; 308 int nbufs; 309 int version; 310 int i, j; 311 xfs_daddr_t d; 312 xfs_ino_t ino = 0; 313 int error; 314 315 /* 316 * Loop over the new block(s), filling in the inodes. For small block 317 * sizes, manipulate the inodes in buffers which are multiples of the 318 * blocks size. 319 */ 320 nbufs = length / M_IGEO(mp)->blocks_per_cluster; 321 322 /* 323 * Figure out what version number to use in the inodes we create. If 324 * the superblock version has caught up to the one that supports the new 325 * inode format, then use the new inode version. Otherwise use the old 326 * version so that old kernels will continue to be able to use the file 327 * system. 328 * 329 * For v3 inodes, we also need to write the inode number into the inode, 330 * so calculate the first inode number of the chunk here as 331 * XFS_AGB_TO_AGINO() only works within a filesystem block, not 332 * across multiple filesystem blocks (such as a cluster) and so cannot 333 * be used in the cluster buffer loop below. 334 * 335 * Further, because we are writing the inode directly into the buffer 336 * and calculating a CRC on the entire inode, we have ot log the entire 337 * inode so that the entire range the CRC covers is present in the log. 338 * That means for v3 inode we log the entire buffer rather than just the 339 * inode cores. 340 */ 341 if (xfs_has_v3inodes(mp)) { 342 version = 3; 343 ino = XFS_AGINO_TO_INO(mp, agno, XFS_AGB_TO_AGINO(mp, agbno)); 344 345 /* 346 * log the initialisation that is about to take place as an 347 * logical operation. This means the transaction does not 348 * need to log the physical changes to the inode buffers as log 349 * recovery will know what initialisation is actually needed. 350 * Hence we only need to log the buffers as "ordered" buffers so 351 * they track in the AIL as if they were physically logged. 352 */ 353 if (tp) 354 xfs_icreate_log(tp, agno, agbno, icount, 355 mp->m_sb.sb_inodesize, length, gen); 356 } else 357 version = 2; 358 359 for (j = 0; j < nbufs; j++) { 360 /* 361 * Get the block. 362 */ 363 d = XFS_AGB_TO_DADDR(mp, agno, agbno + 364 (j * M_IGEO(mp)->blocks_per_cluster)); 365 error = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, 366 mp->m_bsize * M_IGEO(mp)->blocks_per_cluster, 367 0, &fbuf); 368 if (error) 369 return error; 370 371 /* Initialize the inode buffers and log them appropriately. */ 372 fbuf->b_ops = &xfs_inode_buf_ops; 373 xfs_buf_zero(fbuf, 0, BBTOB(fbuf->b_length)); 374 for (i = 0; i < M_IGEO(mp)->inodes_per_cluster; i++) { 375 int ioffset = i << mp->m_sb.sb_inodelog; 376 377 free = xfs_make_iptr(mp, fbuf, i); 378 free->di_magic = cpu_to_be16(XFS_DINODE_MAGIC); 379 free->di_version = version; 380 free->di_gen = cpu_to_be32(gen); 381 free->di_next_unlinked = cpu_to_be32(NULLAGINO); 382 383 if (version == 3) { 384 free->di_ino = cpu_to_be64(ino); 385 ino++; 386 uuid_copy(&free->di_uuid, 387 &mp->m_sb.sb_meta_uuid); 388 xfs_dinode_calc_crc(mp, free); 389 } else if (tp) { 390 /* just log the inode core */ 391 xfs_trans_log_buf(tp, fbuf, ioffset, 392 ioffset + XFS_DINODE_SIZE(mp) - 1); 393 } 394 } 395 396 if (tp) { 397 /* 398 * Mark the buffer as an inode allocation buffer so it 399 * sticks in AIL at the point of this allocation 400 * transaction. This ensures the they are on disk before 401 * the tail of the log can be moved past this 402 * transaction (i.e. by preventing relogging from moving 403 * it forward in the log). 404 */ 405 xfs_trans_inode_alloc_buf(tp, fbuf); 406 if (version == 3) { 407 /* 408 * Mark the buffer as ordered so that they are 409 * not physically logged in the transaction but 410 * still tracked in the AIL as part of the 411 * transaction and pin the log appropriately. 412 */ 413 xfs_trans_ordered_buf(tp, fbuf); 414 } 415 } else { 416 fbuf->b_flags |= XBF_DONE; 417 xfs_buf_delwri_queue(fbuf, buffer_list); 418 xfs_buf_relse(fbuf); 419 } 420 } 421 return 0; 422} 423 424/* 425 * Align startino and allocmask for a recently allocated sparse chunk such that 426 * they are fit for insertion (or merge) into the on-disk inode btrees. 427 * 428 * Background: 429 * 430 * When enabled, sparse inode support increases the inode alignment from cluster 431 * size to inode chunk size. This means that the minimum range between two 432 * non-adjacent inode records in the inobt is large enough for a full inode 433 * record. This allows for cluster sized, cluster aligned block allocation 434 * without need to worry about whether the resulting inode record overlaps with 435 * another record in the tree. Without this basic rule, we would have to deal 436 * with the consequences of overlap by potentially undoing recent allocations in 437 * the inode allocation codepath. 438 * 439 * Because of this alignment rule (which is enforced on mount), there are two 440 * inobt possibilities for newly allocated sparse chunks. One is that the 441 * aligned inode record for the chunk covers a range of inodes not already 442 * covered in the inobt (i.e., it is safe to insert a new sparse record). The 443 * other is that a record already exists at the aligned startino that considers 444 * the newly allocated range as sparse. In the latter case, record content is 445 * merged in hope that sparse inode chunks fill to full chunks over time. 446 */ 447STATIC void 448xfs_align_sparse_ino( 449 struct xfs_mount *mp, 450 xfs_agino_t *startino, 451 uint16_t *allocmask) 452{ 453 xfs_agblock_t agbno; 454 xfs_agblock_t mod; 455 int offset; 456 457 agbno = XFS_AGINO_TO_AGBNO(mp, *startino); 458 mod = agbno % mp->m_sb.sb_inoalignmt; 459 if (!mod) 460 return; 461 462 /* calculate the inode offset and align startino */ 463 offset = XFS_AGB_TO_AGINO(mp, mod); 464 *startino -= offset; 465 466 /* 467 * Since startino has been aligned down, left shift allocmask such that 468 * it continues to represent the same physical inodes relative to the 469 * new startino. 470 */ 471 *allocmask <<= offset / XFS_INODES_PER_HOLEMASK_BIT; 472} 473 474/* 475 * Determine whether the source inode record can merge into the target. Both 476 * records must be sparse, the inode ranges must match and there must be no 477 * allocation overlap between the records. 478 */ 479STATIC bool 480__xfs_inobt_can_merge( 481 struct xfs_inobt_rec_incore *trec, /* tgt record */ 482 struct xfs_inobt_rec_incore *srec) /* src record */ 483{ 484 uint64_t talloc; 485 uint64_t salloc; 486 487 /* records must cover the same inode range */ 488 if (trec->ir_startino != srec->ir_startino) 489 return false; 490 491 /* both records must be sparse */ 492 if (!xfs_inobt_issparse(trec->ir_holemask) || 493 !xfs_inobt_issparse(srec->ir_holemask)) 494 return false; 495 496 /* both records must track some inodes */ 497 if (!trec->ir_count || !srec->ir_count) 498 return false; 499 500 /* can't exceed capacity of a full record */ 501 if (trec->ir_count + srec->ir_count > XFS_INODES_PER_CHUNK) 502 return false; 503 504 /* verify there is no allocation overlap */ 505 talloc = xfs_inobt_irec_to_allocmask(trec); 506 salloc = xfs_inobt_irec_to_allocmask(srec); 507 if (talloc & salloc) 508 return false; 509 510 return true; 511} 512 513/* 514 * Merge the source inode record into the target. The caller must call 515 * __xfs_inobt_can_merge() to ensure the merge is valid. 516 */ 517STATIC void 518__xfs_inobt_rec_merge( 519 struct xfs_inobt_rec_incore *trec, /* target */ 520 struct xfs_inobt_rec_incore *srec) /* src */ 521{ 522 ASSERT(trec->ir_startino == srec->ir_startino); 523 524 /* combine the counts */ 525 trec->ir_count += srec->ir_count; 526 trec->ir_freecount += srec->ir_freecount; 527 528 /* 529 * Merge the holemask and free mask. For both fields, 0 bits refer to 530 * allocated inodes. We combine the allocated ranges with bitwise AND. 531 */ 532 trec->ir_holemask &= srec->ir_holemask; 533 trec->ir_free &= srec->ir_free; 534} 535 536/* 537 * Insert a new sparse inode chunk into the associated inode allocation btree. 538 * The inode record for the sparse chunk is pre-aligned to a startino that 539 * should match any pre-existing sparse inode record in the tree. This allows 540 * sparse chunks to fill over time. 541 * 542 * If no preexisting record exists, the provided record is inserted. 543 * If there is a preexisting record, the provided record is merged with the 544 * existing record and updated in place. The merged record is returned in nrec. 545 * 546 * It is considered corruption if a merge is requested and not possible. Given 547 * the sparse inode alignment constraints, this should never happen. 548 */ 549STATIC int 550xfs_inobt_insert_sprec( 551 struct xfs_perag *pag, 552 struct xfs_trans *tp, 553 struct xfs_buf *agbp, 554 struct xfs_inobt_rec_incore *nrec) /* in/out: new/merged rec. */ 555{ 556 struct xfs_mount *mp = pag_mount(pag); 557 struct xfs_btree_cur *cur; 558 int error; 559 int i; 560 struct xfs_inobt_rec_incore rec; 561 562 cur = xfs_inobt_init_cursor(pag, tp, agbp); 563 564 /* the new record is pre-aligned so we know where to look */ 565 error = xfs_inobt_lookup(cur, nrec->ir_startino, XFS_LOOKUP_EQ, &i); 566 if (error) 567 goto error; 568 /* if nothing there, insert a new record and return */ 569 if (i == 0) { 570 error = xfs_inobt_insert_rec(cur, nrec->ir_holemask, 571 nrec->ir_count, nrec->ir_freecount, 572 nrec->ir_free, &i); 573 if (error) 574 goto error; 575 if (XFS_IS_CORRUPT(mp, i != 1)) { 576 xfs_btree_mark_sick(cur); 577 error = -EFSCORRUPTED; 578 goto error; 579 } 580 581 goto out; 582 } 583 584 /* 585 * A record exists at this startino. Merge the records. 586 */ 587 error = xfs_inobt_get_rec(cur, &rec, &i); 588 if (error) 589 goto error; 590 if (XFS_IS_CORRUPT(mp, i != 1)) { 591 xfs_btree_mark_sick(cur); 592 error = -EFSCORRUPTED; 593 goto error; 594 } 595 if (XFS_IS_CORRUPT(mp, rec.ir_startino != nrec->ir_startino)) { 596 xfs_btree_mark_sick(cur); 597 error = -EFSCORRUPTED; 598 goto error; 599 } 600 601 /* 602 * This should never fail. If we have coexisting records that 603 * cannot merge, something is seriously wrong. 604 */ 605 if (XFS_IS_CORRUPT(mp, !__xfs_inobt_can_merge(nrec, &rec))) { 606 xfs_btree_mark_sick(cur); 607 error = -EFSCORRUPTED; 608 goto error; 609 } 610 611 trace_xfs_irec_merge_pre(pag, &rec, nrec); 612 613 /* merge to nrec to output the updated record */ 614 __xfs_inobt_rec_merge(nrec, &rec); 615 616 trace_xfs_irec_merge_post(pag, nrec); 617 618 error = xfs_inobt_rec_check_count(mp, nrec); 619 if (error) 620 goto error; 621 622 error = xfs_inobt_update(cur, nrec); 623 if (error) 624 goto error; 625 626out: 627 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 628 return 0; 629error: 630 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 631 return error; 632} 633 634/* 635 * Insert a new sparse inode chunk into the free inode btree. The inode 636 * record for the sparse chunk is pre-aligned to a startino that should match 637 * any pre-existing sparse inode record in the tree. This allows sparse chunks 638 * to fill over time. 639 * 640 * The new record is always inserted, overwriting a pre-existing record if 641 * there is one. 642 */ 643STATIC int 644xfs_finobt_insert_sprec( 645 struct xfs_perag *pag, 646 struct xfs_trans *tp, 647 struct xfs_buf *agbp, 648 struct xfs_inobt_rec_incore *nrec) /* in/out: new rec. */ 649{ 650 struct xfs_mount *mp = pag_mount(pag); 651 struct xfs_btree_cur *cur; 652 int error; 653 int i; 654 655 cur = xfs_finobt_init_cursor(pag, tp, agbp); 656 657 /* the new record is pre-aligned so we know where to look */ 658 error = xfs_inobt_lookup(cur, nrec->ir_startino, XFS_LOOKUP_EQ, &i); 659 if (error) 660 goto error; 661 /* if nothing there, insert a new record and return */ 662 if (i == 0) { 663 error = xfs_inobt_insert_rec(cur, nrec->ir_holemask, 664 nrec->ir_count, nrec->ir_freecount, 665 nrec->ir_free, &i); 666 if (error) 667 goto error; 668 if (XFS_IS_CORRUPT(mp, i != 1)) { 669 xfs_btree_mark_sick(cur); 670 error = -EFSCORRUPTED; 671 goto error; 672 } 673 } else { 674 error = xfs_inobt_update(cur, nrec); 675 if (error) 676 goto error; 677 } 678 679 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 680 return 0; 681error: 682 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 683 return error; 684} 685 686 687/* 688 * Allocate new inodes in the allocation group specified by agbp. Returns 0 if 689 * inodes were allocated in this AG; -EAGAIN if there was no space in this AG so 690 * the caller knows it can try another AG, a hard -ENOSPC when over the maximum 691 * inode count threshold, or the usual negative error code for other errors. 692 */ 693STATIC int 694xfs_ialloc_ag_alloc( 695 struct xfs_perag *pag, 696 struct xfs_trans *tp, 697 struct xfs_buf *agbp) 698{ 699 struct xfs_agi *agi; 700 struct xfs_alloc_arg args; 701 int error; 702 xfs_agino_t newino; /* new first inode's number */ 703 xfs_agino_t newlen; /* new number of inodes */ 704 int isaligned = 0; /* inode allocation at stripe */ 705 /* unit boundary */ 706 /* init. to full chunk */ 707 struct xfs_inobt_rec_incore rec; 708 struct xfs_ino_geometry *igeo = M_IGEO(tp->t_mountp); 709 uint16_t allocmask = (uint16_t) -1; 710 int do_sparse = 0; 711 712 memset(&args, 0, sizeof(args)); 713 args.tp = tp; 714 args.mp = tp->t_mountp; 715 args.fsbno = NULLFSBLOCK; 716 args.oinfo = XFS_RMAP_OINFO_INODES; 717 args.pag = pag; 718 719#ifdef DEBUG 720 /* randomly do sparse inode allocations */ 721 if (xfs_has_sparseinodes(tp->t_mountp) && 722 igeo->ialloc_min_blks < igeo->ialloc_blks) 723 do_sparse = get_random_u32_below(2); 724#endif 725 726 /* 727 * Locking will ensure that we don't have two callers in here 728 * at one time. 729 */ 730 newlen = igeo->ialloc_inos; 731 if (igeo->maxicount && 732 percpu_counter_read_positive(&args.mp->m_icount) + newlen > 733 igeo->maxicount) 734 return -ENOSPC; 735 args.minlen = args.maxlen = igeo->ialloc_blks; 736 /* 737 * First try to allocate inodes contiguous with the last-allocated 738 * chunk of inodes. If the filesystem is striped, this will fill 739 * an entire stripe unit with inodes. 740 */ 741 agi = agbp->b_addr; 742 newino = be32_to_cpu(agi->agi_newino); 743 args.agbno = XFS_AGINO_TO_AGBNO(args.mp, newino) + 744 igeo->ialloc_blks; 745 if (do_sparse) 746 goto sparse_alloc; 747 if (likely(newino != NULLAGINO && 748 (args.agbno < be32_to_cpu(agi->agi_length)))) { 749 args.prod = 1; 750 751 /* 752 * We need to take into account alignment here to ensure that 753 * we don't modify the free list if we fail to have an exact 754 * block. If we don't have an exact match, and every oher 755 * attempt allocation attempt fails, we'll end up cancelling 756 * a dirty transaction and shutting down. 757 * 758 * For an exact allocation, alignment must be 1, 759 * however we need to take cluster alignment into account when 760 * fixing up the freelist. Use the minalignslop field to 761 * indicate that extra blocks might be required for alignment, 762 * but not to use them in the actual exact allocation. 763 */ 764 args.alignment = 1; 765 args.minalignslop = igeo->cluster_align - 1; 766 767 /* Allow space for the inode btree to split. */ 768 args.minleft = igeo->inobt_maxlevels; 769 error = xfs_alloc_vextent_exact_bno(&args, 770 xfs_agbno_to_fsb(pag, args.agbno)); 771 if (error) 772 return error; 773 774 /* 775 * This request might have dirtied the transaction if the AG can 776 * satisfy the request, but the exact block was not available. 777 * If the allocation did fail, subsequent requests will relax 778 * the exact agbno requirement and increase the alignment 779 * instead. It is critical that the total size of the request 780 * (len + alignment + slop) does not increase from this point 781 * on, so reset minalignslop to ensure it is not included in 782 * subsequent requests. 783 */ 784 args.minalignslop = 0; 785 } 786 787 if (unlikely(args.fsbno == NULLFSBLOCK)) { 788 /* 789 * Set the alignment for the allocation. 790 * If stripe alignment is turned on then align at stripe unit 791 * boundary. 792 * If the cluster size is smaller than a filesystem block 793 * then we're doing I/O for inodes in filesystem block size 794 * pieces, so don't need alignment anyway. 795 */ 796 isaligned = 0; 797 if (igeo->ialloc_align) { 798 ASSERT(!xfs_has_noalign(args.mp)); 799 args.alignment = args.mp->m_dalign; 800 isaligned = 1; 801 } else 802 args.alignment = igeo->cluster_align; 803 /* 804 * Allocate a fixed-size extent of inodes. 805 */ 806 args.prod = 1; 807 /* 808 * Allow space for the inode btree to split. 809 */ 810 args.minleft = igeo->inobt_maxlevels; 811 error = xfs_alloc_vextent_near_bno(&args, 812 xfs_agbno_to_fsb(pag, 813 be32_to_cpu(agi->agi_root))); 814 if (error) 815 return error; 816 } 817 818 /* 819 * If stripe alignment is turned on, then try again with cluster 820 * alignment. 821 */ 822 if (isaligned && args.fsbno == NULLFSBLOCK) { 823 args.alignment = igeo->cluster_align; 824 error = xfs_alloc_vextent_near_bno(&args, 825 xfs_agbno_to_fsb(pag, 826 be32_to_cpu(agi->agi_root))); 827 if (error) 828 return error; 829 } 830 831 /* 832 * Finally, try a sparse allocation if the filesystem supports it and 833 * the sparse allocation length is smaller than a full chunk. 834 */ 835 if (xfs_has_sparseinodes(args.mp) && 836 igeo->ialloc_min_blks < igeo->ialloc_blks && 837 args.fsbno == NULLFSBLOCK) { 838sparse_alloc: 839 args.alignment = args.mp->m_sb.sb_spino_align; 840 args.prod = 1; 841 842 args.minlen = igeo->ialloc_min_blks; 843 args.maxlen = args.minlen; 844 845 /* 846 * The inode record will be aligned to full chunk size. We must 847 * prevent sparse allocation from AG boundaries that result in 848 * invalid inode records, such as records that start at agbno 0 849 * or extend beyond the AG. 850 * 851 * Set min agbno to the first chunk aligned, non-zero agbno and 852 * max to one less than the last chunk aligned agbno from the 853 * end of the AG. We subtract 1 from max so that the cluster 854 * allocation alignment takes over and allows allocation within 855 * the last full inode chunk in the AG. 856 */ 857 args.min_agbno = args.mp->m_sb.sb_inoalignmt; 858 args.max_agbno = round_down(xfs_ag_block_count(args.mp, 859 pag_agno(pag)), 860 args.mp->m_sb.sb_inoalignmt) - 1; 861 862 error = xfs_alloc_vextent_near_bno(&args, 863 xfs_agbno_to_fsb(pag, 864 be32_to_cpu(agi->agi_root))); 865 if (error) 866 return error; 867 868 newlen = XFS_AGB_TO_AGINO(args.mp, args.len); 869 ASSERT(newlen <= XFS_INODES_PER_CHUNK); 870 allocmask = (1 << (newlen / XFS_INODES_PER_HOLEMASK_BIT)) - 1; 871 } 872 873 if (args.fsbno == NULLFSBLOCK) 874 return -EAGAIN; 875 876 ASSERT(args.len == args.minlen); 877 878 /* 879 * Stamp and write the inode buffers. 880 * 881 * Seed the new inode cluster with a random generation number. This 882 * prevents short-term reuse of generation numbers if a chunk is 883 * freed and then immediately reallocated. We use random numbers 884 * rather than a linear progression to prevent the next generation 885 * number from being easily guessable. 886 */ 887 error = xfs_ialloc_inode_init(args.mp, tp, NULL, newlen, pag_agno(pag), 888 args.agbno, args.len, get_random_u32()); 889 890 if (error) 891 return error; 892 /* 893 * Convert the results. 894 */ 895 newino = XFS_AGB_TO_AGINO(args.mp, args.agbno); 896 897 if (xfs_inobt_issparse(~allocmask)) { 898 /* 899 * We've allocated a sparse chunk. Align the startino and mask. 900 */ 901 xfs_align_sparse_ino(args.mp, &newino, &allocmask); 902 903 rec.ir_startino = newino; 904 rec.ir_holemask = ~allocmask; 905 rec.ir_count = newlen; 906 rec.ir_freecount = newlen; 907 rec.ir_free = XFS_INOBT_ALL_FREE; 908 909 /* 910 * Insert the sparse record into the inobt and allow for a merge 911 * if necessary. If a merge does occur, rec is updated to the 912 * merged record. 913 */ 914 error = xfs_inobt_insert_sprec(pag, tp, agbp, &rec); 915 if (error == -EFSCORRUPTED) { 916 xfs_alert(args.mp, 917 "invalid sparse inode record: ino 0x%llx holemask 0x%x count %u", 918 xfs_agino_to_ino(pag, rec.ir_startino), 919 rec.ir_holemask, rec.ir_count); 920 xfs_force_shutdown(args.mp, SHUTDOWN_CORRUPT_INCORE); 921 } 922 if (error) 923 return error; 924 925 /* 926 * We can't merge the part we've just allocated as for the inobt 927 * due to finobt semantics. The original record may or may not 928 * exist independent of whether physical inodes exist in this 929 * sparse chunk. 930 * 931 * We must update the finobt record based on the inobt record. 932 * rec contains the fully merged and up to date inobt record 933 * from the previous call. Set merge false to replace any 934 * existing record with this one. 935 */ 936 if (xfs_has_finobt(args.mp)) { 937 error = xfs_finobt_insert_sprec(pag, tp, agbp, &rec); 938 if (error) 939 return error; 940 } 941 } else { 942 /* full chunk - insert new records to both btrees */ 943 error = xfs_inobt_insert(pag, tp, agbp, newino, newlen, false); 944 if (error) 945 return error; 946 947 if (xfs_has_finobt(args.mp)) { 948 error = xfs_inobt_insert(pag, tp, agbp, newino, 949 newlen, true); 950 if (error) 951 return error; 952 } 953 } 954 955 /* 956 * Update AGI counts and newino. 957 */ 958 be32_add_cpu(&agi->agi_count, newlen); 959 be32_add_cpu(&agi->agi_freecount, newlen); 960 pag->pagi_freecount += newlen; 961 pag->pagi_count += newlen; 962 agi->agi_newino = cpu_to_be32(newino); 963 964 /* 965 * Log allocation group header fields 966 */ 967 xfs_ialloc_log_agi(tp, agbp, 968 XFS_AGI_COUNT | XFS_AGI_FREECOUNT | XFS_AGI_NEWINO); 969 /* 970 * Modify/log superblock values for inode count and inode free count. 971 */ 972 xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, (long)newlen); 973 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, (long)newlen); 974 return 0; 975} 976 977/* 978 * Try to retrieve the next record to the left/right from the current one. 979 */ 980STATIC int 981xfs_ialloc_next_rec( 982 struct xfs_btree_cur *cur, 983 xfs_inobt_rec_incore_t *rec, 984 int *done, 985 int left) 986{ 987 int error; 988 int i; 989 990 if (left) 991 error = xfs_btree_decrement(cur, 0, &i); 992 else 993 error = xfs_btree_increment(cur, 0, &i); 994 995 if (error) 996 return error; 997 *done = !i; 998 if (i) { 999 error = xfs_inobt_get_rec(cur, rec, &i); 1000 if (error) 1001 return error; 1002 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { 1003 xfs_btree_mark_sick(cur); 1004 return -EFSCORRUPTED; 1005 } 1006 } 1007 1008 return 0; 1009} 1010 1011STATIC int 1012xfs_ialloc_get_rec( 1013 struct xfs_btree_cur *cur, 1014 xfs_agino_t agino, 1015 xfs_inobt_rec_incore_t *rec, 1016 int *done) 1017{ 1018 int error; 1019 int i; 1020 1021 error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_EQ, &i); 1022 if (error) 1023 return error; 1024 *done = !i; 1025 if (i) { 1026 error = xfs_inobt_get_rec(cur, rec, &i); 1027 if (error) 1028 return error; 1029 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { 1030 xfs_btree_mark_sick(cur); 1031 return -EFSCORRUPTED; 1032 } 1033 } 1034 1035 return 0; 1036} 1037 1038/* 1039 * Return the offset of the first free inode in the record. If the inode chunk 1040 * is sparsely allocated, we convert the record holemask to inode granularity 1041 * and mask off the unallocated regions from the inode free mask. 1042 */ 1043STATIC int 1044xfs_inobt_first_free_inode( 1045 struct xfs_inobt_rec_incore *rec) 1046{ 1047 xfs_inofree_t realfree; 1048 1049 /* if there are no holes, return the first available offset */ 1050 if (!xfs_inobt_issparse(rec->ir_holemask)) 1051 return xfs_lowbit64(rec->ir_free); 1052 1053 realfree = xfs_inobt_irec_to_allocmask(rec); 1054 realfree &= rec->ir_free; 1055 1056 return xfs_lowbit64(realfree); 1057} 1058 1059/* 1060 * If this AG has corrupt inodes, check if allocating this inode would fail 1061 * with corruption errors. Returns 0 if we're clear, or EAGAIN to try again 1062 * somewhere else. 1063 */ 1064static int 1065xfs_dialloc_check_ino( 1066 struct xfs_perag *pag, 1067 struct xfs_trans *tp, 1068 xfs_ino_t ino) 1069{ 1070 struct xfs_imap imap; 1071 struct xfs_buf *bp; 1072 int error; 1073 1074 error = xfs_imap(pag, tp, ino, &imap, 0); 1075 if (error) 1076 return -EAGAIN; 1077 1078 error = xfs_imap_to_bp(pag_mount(pag), tp, &imap, &bp); 1079 if (error) 1080 return -EAGAIN; 1081 1082 xfs_trans_brelse(tp, bp); 1083 return 0; 1084} 1085 1086/* 1087 * Allocate an inode using the inobt-only algorithm. 1088 */ 1089STATIC int 1090xfs_dialloc_ag_inobt( 1091 struct xfs_perag *pag, 1092 struct xfs_trans *tp, 1093 struct xfs_buf *agbp, 1094 xfs_ino_t parent, 1095 xfs_ino_t *inop) 1096{ 1097 struct xfs_mount *mp = tp->t_mountp; 1098 struct xfs_agi *agi = agbp->b_addr; 1099 xfs_agnumber_t pagno = XFS_INO_TO_AGNO(mp, parent); 1100 xfs_agino_t pagino = XFS_INO_TO_AGINO(mp, parent); 1101 struct xfs_btree_cur *cur, *tcur; 1102 struct xfs_inobt_rec_incore rec, trec; 1103 xfs_ino_t ino; 1104 int error; 1105 int offset; 1106 int i, j; 1107 int searchdistance = 10; 1108 1109 ASSERT(xfs_perag_initialised_agi(pag)); 1110 ASSERT(xfs_perag_allows_inodes(pag)); 1111 ASSERT(pag->pagi_freecount > 0); 1112 1113 restart_pagno: 1114 cur = xfs_inobt_init_cursor(pag, tp, agbp); 1115 /* 1116 * If pagino is 0 (this is the root inode allocation) use newino. 1117 * This must work because we've just allocated some. 1118 */ 1119 if (!pagino) 1120 pagino = be32_to_cpu(agi->agi_newino); 1121 1122 error = xfs_check_agi_freecount(cur); 1123 if (error) 1124 goto error0; 1125 1126 /* 1127 * If in the same AG as the parent, try to get near the parent. 1128 */ 1129 if (pagno == pag_agno(pag)) { 1130 int doneleft; /* done, to the left */ 1131 int doneright; /* done, to the right */ 1132 1133 error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i); 1134 if (error) 1135 goto error0; 1136 if (XFS_IS_CORRUPT(mp, i != 1)) { 1137 xfs_btree_mark_sick(cur); 1138 error = -EFSCORRUPTED; 1139 goto error0; 1140 } 1141 1142 error = xfs_inobt_get_rec(cur, &rec, &j); 1143 if (error) 1144 goto error0; 1145 if (XFS_IS_CORRUPT(mp, j != 1)) { 1146 xfs_btree_mark_sick(cur); 1147 error = -EFSCORRUPTED; 1148 goto error0; 1149 } 1150 1151 if (rec.ir_freecount > 0) { 1152 /* 1153 * Found a free inode in the same chunk 1154 * as the parent, done. 1155 */ 1156 goto alloc_inode; 1157 } 1158 1159 1160 /* 1161 * In the same AG as parent, but parent's chunk is full. 1162 */ 1163 1164 /* duplicate the cursor, search left & right simultaneously */ 1165 error = xfs_btree_dup_cursor(cur, &tcur); 1166 if (error) 1167 goto error0; 1168 1169 /* 1170 * Skip to last blocks looked up if same parent inode. 1171 */ 1172 if (pagino != NULLAGINO && 1173 pag->pagl_pagino == pagino && 1174 pag->pagl_leftrec != NULLAGINO && 1175 pag->pagl_rightrec != NULLAGINO) { 1176 error = xfs_ialloc_get_rec(tcur, pag->pagl_leftrec, 1177 &trec, &doneleft); 1178 if (error) 1179 goto error1; 1180 1181 error = xfs_ialloc_get_rec(cur, pag->pagl_rightrec, 1182 &rec, &doneright); 1183 if (error) 1184 goto error1; 1185 } else { 1186 /* search left with tcur, back up 1 record */ 1187 error = xfs_ialloc_next_rec(tcur, &trec, &doneleft, 1); 1188 if (error) 1189 goto error1; 1190 1191 /* search right with cur, go forward 1 record. */ 1192 error = xfs_ialloc_next_rec(cur, &rec, &doneright, 0); 1193 if (error) 1194 goto error1; 1195 } 1196 1197 /* 1198 * Loop until we find an inode chunk with a free inode. 1199 */ 1200 while (--searchdistance > 0 && (!doneleft || !doneright)) { 1201 int useleft; /* using left inode chunk this time */ 1202 1203 /* figure out the closer block if both are valid. */ 1204 if (!doneleft && !doneright) { 1205 useleft = pagino - 1206 (trec.ir_startino + XFS_INODES_PER_CHUNK - 1) < 1207 rec.ir_startino - pagino; 1208 } else { 1209 useleft = !doneleft; 1210 } 1211 1212 /* free inodes to the left? */ 1213 if (useleft && trec.ir_freecount) { 1214 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 1215 cur = tcur; 1216 1217 pag->pagl_leftrec = trec.ir_startino; 1218 pag->pagl_rightrec = rec.ir_startino; 1219 pag->pagl_pagino = pagino; 1220 rec = trec; 1221 goto alloc_inode; 1222 } 1223 1224 /* free inodes to the right? */ 1225 if (!useleft && rec.ir_freecount) { 1226 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 1227 1228 pag->pagl_leftrec = trec.ir_startino; 1229 pag->pagl_rightrec = rec.ir_startino; 1230 pag->pagl_pagino = pagino; 1231 goto alloc_inode; 1232 } 1233 1234 /* get next record to check */ 1235 if (useleft) { 1236 error = xfs_ialloc_next_rec(tcur, &trec, 1237 &doneleft, 1); 1238 } else { 1239 error = xfs_ialloc_next_rec(cur, &rec, 1240 &doneright, 0); 1241 } 1242 if (error) 1243 goto error1; 1244 } 1245 1246 if (searchdistance <= 0) { 1247 /* 1248 * Not in range - save last search 1249 * location and allocate a new inode 1250 */ 1251 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 1252 pag->pagl_leftrec = trec.ir_startino; 1253 pag->pagl_rightrec = rec.ir_startino; 1254 pag->pagl_pagino = pagino; 1255 1256 } else { 1257 /* 1258 * We've reached the end of the btree. because 1259 * we are only searching a small chunk of the 1260 * btree each search, there is obviously free 1261 * inodes closer to the parent inode than we 1262 * are now. restart the search again. 1263 */ 1264 pag->pagl_pagino = NULLAGINO; 1265 pag->pagl_leftrec = NULLAGINO; 1266 pag->pagl_rightrec = NULLAGINO; 1267 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR); 1268 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 1269 goto restart_pagno; 1270 } 1271 } 1272 1273 /* 1274 * In a different AG from the parent. 1275 * See if the most recently allocated block has any free. 1276 */ 1277 if (agi->agi_newino != cpu_to_be32(NULLAGINO)) { 1278 error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino), 1279 XFS_LOOKUP_EQ, &i); 1280 if (error) 1281 goto error0; 1282 1283 if (i == 1) { 1284 error = xfs_inobt_get_rec(cur, &rec, &j); 1285 if (error) 1286 goto error0; 1287 1288 if (j == 1 && rec.ir_freecount > 0) { 1289 /* 1290 * The last chunk allocated in the group 1291 * still has a free inode. 1292 */ 1293 goto alloc_inode; 1294 } 1295 } 1296 } 1297 1298 /* 1299 * None left in the last group, search the whole AG 1300 */ 1301 error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i); 1302 if (error) 1303 goto error0; 1304 if (XFS_IS_CORRUPT(mp, i != 1)) { 1305 xfs_btree_mark_sick(cur); 1306 error = -EFSCORRUPTED; 1307 goto error0; 1308 } 1309 1310 for (;;) { 1311 error = xfs_inobt_get_rec(cur, &rec, &i); 1312 if (error) 1313 goto error0; 1314 if (XFS_IS_CORRUPT(mp, i != 1)) { 1315 xfs_btree_mark_sick(cur); 1316 error = -EFSCORRUPTED; 1317 goto error0; 1318 } 1319 if (rec.ir_freecount > 0) 1320 break; 1321 error = xfs_btree_increment(cur, 0, &i); 1322 if (error) 1323 goto error0; 1324 if (XFS_IS_CORRUPT(mp, i != 1)) { 1325 xfs_btree_mark_sick(cur); 1326 error = -EFSCORRUPTED; 1327 goto error0; 1328 } 1329 } 1330 1331alloc_inode: 1332 offset = xfs_inobt_first_free_inode(&rec); 1333 ASSERT(offset >= 0); 1334 ASSERT(offset < XFS_INODES_PER_CHUNK); 1335 ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) % 1336 XFS_INODES_PER_CHUNK) == 0); 1337 ino = xfs_agino_to_ino(pag, rec.ir_startino + offset); 1338 1339 if (xfs_ag_has_sickness(pag, XFS_SICK_AG_INODES)) { 1340 error = xfs_dialloc_check_ino(pag, tp, ino); 1341 if (error) 1342 goto error0; 1343 } 1344 1345 rec.ir_free &= ~XFS_INOBT_MASK(offset); 1346 rec.ir_freecount--; 1347 error = xfs_inobt_update(cur, &rec); 1348 if (error) 1349 goto error0; 1350 be32_add_cpu(&agi->agi_freecount, -1); 1351 xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT); 1352 pag->pagi_freecount--; 1353 1354 error = xfs_check_agi_freecount(cur); 1355 if (error) 1356 goto error0; 1357 1358 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 1359 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1); 1360 *inop = ino; 1361 return 0; 1362error1: 1363 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR); 1364error0: 1365 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 1366 return error; 1367} 1368 1369/* 1370 * Use the free inode btree to allocate an inode based on distance from the 1371 * parent. Note that the provided cursor may be deleted and replaced. 1372 */ 1373STATIC int 1374xfs_dialloc_ag_finobt_near( 1375 xfs_agino_t pagino, 1376 struct xfs_btree_cur **ocur, 1377 struct xfs_inobt_rec_incore *rec) 1378{ 1379 struct xfs_btree_cur *lcur = *ocur; /* left search cursor */ 1380 struct xfs_btree_cur *rcur; /* right search cursor */ 1381 struct xfs_inobt_rec_incore rrec; 1382 int error; 1383 int i, j; 1384 1385 error = xfs_inobt_lookup(lcur, pagino, XFS_LOOKUP_LE, &i); 1386 if (error) 1387 return error; 1388 1389 if (i == 1) { 1390 error = xfs_inobt_get_rec(lcur, rec, &i); 1391 if (error) 1392 return error; 1393 if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1)) { 1394 xfs_btree_mark_sick(lcur); 1395 return -EFSCORRUPTED; 1396 } 1397 1398 /* 1399 * See if we've landed in the parent inode record. The finobt 1400 * only tracks chunks with at least one free inode, so record 1401 * existence is enough. 1402 */ 1403 if (pagino >= rec->ir_startino && 1404 pagino < (rec->ir_startino + XFS_INODES_PER_CHUNK)) 1405 return 0; 1406 } 1407 1408 error = xfs_btree_dup_cursor(lcur, &rcur); 1409 if (error) 1410 return error; 1411 1412 error = xfs_inobt_lookup(rcur, pagino, XFS_LOOKUP_GE, &j); 1413 if (error) 1414 goto error_rcur; 1415 if (j == 1) { 1416 error = xfs_inobt_get_rec(rcur, &rrec, &j); 1417 if (error) 1418 goto error_rcur; 1419 if (XFS_IS_CORRUPT(lcur->bc_mp, j != 1)) { 1420 xfs_btree_mark_sick(lcur); 1421 error = -EFSCORRUPTED; 1422 goto error_rcur; 1423 } 1424 } 1425 1426 if (XFS_IS_CORRUPT(lcur->bc_mp, i != 1 && j != 1)) { 1427 xfs_btree_mark_sick(lcur); 1428 error = -EFSCORRUPTED; 1429 goto error_rcur; 1430 } 1431 if (i == 1 && j == 1) { 1432 /* 1433 * Both the left and right records are valid. Choose the closer 1434 * inode chunk to the target. 1435 */ 1436 if ((pagino - rec->ir_startino + XFS_INODES_PER_CHUNK - 1) > 1437 (rrec.ir_startino - pagino)) { 1438 *rec = rrec; 1439 xfs_btree_del_cursor(lcur, XFS_BTREE_NOERROR); 1440 *ocur = rcur; 1441 } else { 1442 xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR); 1443 } 1444 } else if (j == 1) { 1445 /* only the right record is valid */ 1446 *rec = rrec; 1447 xfs_btree_del_cursor(lcur, XFS_BTREE_NOERROR); 1448 *ocur = rcur; 1449 } else if (i == 1) { 1450 /* only the left record is valid */ 1451 xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR); 1452 } 1453 1454 return 0; 1455 1456error_rcur: 1457 xfs_btree_del_cursor(rcur, XFS_BTREE_ERROR); 1458 return error; 1459} 1460 1461/* 1462 * Use the free inode btree to find a free inode based on a newino hint. If 1463 * the hint is NULL, find the first free inode in the AG. 1464 */ 1465STATIC int 1466xfs_dialloc_ag_finobt_newino( 1467 struct xfs_agi *agi, 1468 struct xfs_btree_cur *cur, 1469 struct xfs_inobt_rec_incore *rec) 1470{ 1471 int error; 1472 int i; 1473 1474 if (agi->agi_newino != cpu_to_be32(NULLAGINO)) { 1475 error = xfs_inobt_lookup(cur, be32_to_cpu(agi->agi_newino), 1476 XFS_LOOKUP_EQ, &i); 1477 if (error) 1478 return error; 1479 if (i == 1) { 1480 error = xfs_inobt_get_rec(cur, rec, &i); 1481 if (error) 1482 return error; 1483 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { 1484 xfs_btree_mark_sick(cur); 1485 return -EFSCORRUPTED; 1486 } 1487 return 0; 1488 } 1489 } 1490 1491 /* 1492 * Find the first inode available in the AG. 1493 */ 1494 error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i); 1495 if (error) 1496 return error; 1497 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { 1498 xfs_btree_mark_sick(cur); 1499 return -EFSCORRUPTED; 1500 } 1501 1502 error = xfs_inobt_get_rec(cur, rec, &i); 1503 if (error) 1504 return error; 1505 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { 1506 xfs_btree_mark_sick(cur); 1507 return -EFSCORRUPTED; 1508 } 1509 1510 return 0; 1511} 1512 1513/* 1514 * Update the inobt based on a modification made to the finobt. Also ensure that 1515 * the records from both trees are equivalent post-modification. 1516 */ 1517STATIC int 1518xfs_dialloc_ag_update_inobt( 1519 struct xfs_btree_cur *cur, /* inobt cursor */ 1520 struct xfs_inobt_rec_incore *frec, /* finobt record */ 1521 int offset) /* inode offset */ 1522{ 1523 struct xfs_inobt_rec_incore rec; 1524 int error; 1525 int i; 1526 1527 error = xfs_inobt_lookup(cur, frec->ir_startino, XFS_LOOKUP_EQ, &i); 1528 if (error) 1529 return error; 1530 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { 1531 xfs_btree_mark_sick(cur); 1532 return -EFSCORRUPTED; 1533 } 1534 1535 error = xfs_inobt_get_rec(cur, &rec, &i); 1536 if (error) 1537 return error; 1538 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) { 1539 xfs_btree_mark_sick(cur); 1540 return -EFSCORRUPTED; 1541 } 1542 ASSERT((XFS_AGINO_TO_OFFSET(cur->bc_mp, rec.ir_startino) % 1543 XFS_INODES_PER_CHUNK) == 0); 1544 1545 rec.ir_free &= ~XFS_INOBT_MASK(offset); 1546 rec.ir_freecount--; 1547 1548 if (XFS_IS_CORRUPT(cur->bc_mp, 1549 rec.ir_free != frec->ir_free || 1550 rec.ir_freecount != frec->ir_freecount)) { 1551 xfs_btree_mark_sick(cur); 1552 return -EFSCORRUPTED; 1553 } 1554 1555 return xfs_inobt_update(cur, &rec); 1556} 1557 1558/* 1559 * Allocate an inode using the free inode btree, if available. Otherwise, fall 1560 * back to the inobt search algorithm. 1561 * 1562 * The caller selected an AG for us, and made sure that free inodes are 1563 * available. 1564 */ 1565static int 1566xfs_dialloc_ag( 1567 struct xfs_perag *pag, 1568 struct xfs_trans *tp, 1569 struct xfs_buf *agbp, 1570 xfs_ino_t parent, 1571 xfs_ino_t *inop) 1572{ 1573 struct xfs_mount *mp = tp->t_mountp; 1574 struct xfs_agi *agi = agbp->b_addr; 1575 xfs_agnumber_t pagno = XFS_INO_TO_AGNO(mp, parent); 1576 xfs_agino_t pagino = XFS_INO_TO_AGINO(mp, parent); 1577 struct xfs_btree_cur *cur; /* finobt cursor */ 1578 struct xfs_btree_cur *icur; /* inobt cursor */ 1579 struct xfs_inobt_rec_incore rec; 1580 xfs_ino_t ino; 1581 int error; 1582 int offset; 1583 int i; 1584 1585 if (!xfs_has_finobt(mp)) 1586 return xfs_dialloc_ag_inobt(pag, tp, agbp, parent, inop); 1587 1588 /* 1589 * If pagino is 0 (this is the root inode allocation) use newino. 1590 * This must work because we've just allocated some. 1591 */ 1592 if (!pagino) 1593 pagino = be32_to_cpu(agi->agi_newino); 1594 1595 cur = xfs_finobt_init_cursor(pag, tp, agbp); 1596 1597 error = xfs_check_agi_freecount(cur); 1598 if (error) 1599 goto error_cur; 1600 1601 /* 1602 * The search algorithm depends on whether we're in the same AG as the 1603 * parent. If so, find the closest available inode to the parent. If 1604 * not, consider the agi hint or find the first free inode in the AG. 1605 */ 1606 if (pag_agno(pag) == pagno) 1607 error = xfs_dialloc_ag_finobt_near(pagino, &cur, &rec); 1608 else 1609 error = xfs_dialloc_ag_finobt_newino(agi, cur, &rec); 1610 if (error) 1611 goto error_cur; 1612 1613 offset = xfs_inobt_first_free_inode(&rec); 1614 ASSERT(offset >= 0); 1615 ASSERT(offset < XFS_INODES_PER_CHUNK); 1616 ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) % 1617 XFS_INODES_PER_CHUNK) == 0); 1618 ino = xfs_agino_to_ino(pag, rec.ir_startino + offset); 1619 1620 if (xfs_ag_has_sickness(pag, XFS_SICK_AG_INODES)) { 1621 error = xfs_dialloc_check_ino(pag, tp, ino); 1622 if (error) 1623 goto error_cur; 1624 } 1625 1626 /* 1627 * Modify or remove the finobt record. 1628 */ 1629 rec.ir_free &= ~XFS_INOBT_MASK(offset); 1630 rec.ir_freecount--; 1631 if (rec.ir_freecount) 1632 error = xfs_inobt_update(cur, &rec); 1633 else 1634 error = xfs_btree_delete(cur, &i); 1635 if (error) 1636 goto error_cur; 1637 1638 /* 1639 * The finobt has now been updated appropriately. We haven't updated the 1640 * agi and superblock yet, so we can create an inobt cursor and validate 1641 * the original freecount. If all is well, make the equivalent update to 1642 * the inobt using the finobt record and offset information. 1643 */ 1644 icur = xfs_inobt_init_cursor(pag, tp, agbp); 1645 1646 error = xfs_check_agi_freecount(icur); 1647 if (error) 1648 goto error_icur; 1649 1650 error = xfs_dialloc_ag_update_inobt(icur, &rec, offset); 1651 if (error) 1652 goto error_icur; 1653 1654 /* 1655 * Both trees have now been updated. We must update the perag and 1656 * superblock before we can check the freecount for each btree. 1657 */ 1658 be32_add_cpu(&agi->agi_freecount, -1); 1659 xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT); 1660 pag->pagi_freecount--; 1661 1662 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1); 1663 1664 error = xfs_check_agi_freecount(icur); 1665 if (error) 1666 goto error_icur; 1667 error = xfs_check_agi_freecount(cur); 1668 if (error) 1669 goto error_icur; 1670 1671 xfs_btree_del_cursor(icur, XFS_BTREE_NOERROR); 1672 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 1673 *inop = ino; 1674 return 0; 1675 1676error_icur: 1677 xfs_btree_del_cursor(icur, XFS_BTREE_ERROR); 1678error_cur: 1679 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 1680 return error; 1681} 1682 1683static int 1684xfs_dialloc_roll( 1685 struct xfs_trans **tpp, 1686 struct xfs_buf *agibp) 1687{ 1688 struct xfs_trans *tp = *tpp; 1689 struct xfs_dquot_acct *dqinfo; 1690 int error; 1691 1692 /* 1693 * Hold to on to the agibp across the commit so no other allocation can 1694 * come in and take the free inodes we just allocated for our caller. 1695 */ 1696 xfs_trans_bhold(tp, agibp); 1697 1698 /* 1699 * We want the quota changes to be associated with the next transaction, 1700 * NOT this one. So, detach the dqinfo from this and attach it to the 1701 * next transaction. 1702 */ 1703 dqinfo = tp->t_dqinfo; 1704 tp->t_dqinfo = NULL; 1705 1706 error = xfs_trans_roll(&tp); 1707 1708 /* Re-attach the quota info that we detached from prev trx. */ 1709 tp->t_dqinfo = dqinfo; 1710 1711 /* 1712 * Join the buffer even on commit error so that the buffer is released 1713 * when the caller cancels the transaction and doesn't have to handle 1714 * this error case specially. 1715 */ 1716 xfs_trans_bjoin(tp, agibp); 1717 *tpp = tp; 1718 return error; 1719} 1720 1721static bool 1722xfs_dialloc_good_ag( 1723 struct xfs_perag *pag, 1724 struct xfs_trans *tp, 1725 umode_t mode, 1726 int flags, 1727 bool ok_alloc) 1728{ 1729 struct xfs_mount *mp = tp->t_mountp; 1730 xfs_extlen_t ineed; 1731 xfs_extlen_t longest = 0; 1732 int needspace; 1733 int error; 1734 1735 if (!pag) 1736 return false; 1737 if (!xfs_perag_allows_inodes(pag)) 1738 return false; 1739 1740 if (!xfs_perag_initialised_agi(pag)) { 1741 error = xfs_ialloc_read_agi(pag, tp, 0, NULL); 1742 if (error) 1743 return false; 1744 } 1745 1746 if (pag->pagi_freecount) 1747 return true; 1748 if (!ok_alloc) 1749 return false; 1750 1751 if (!xfs_perag_initialised_agf(pag)) { 1752 error = xfs_alloc_read_agf(pag, tp, flags, NULL); 1753 if (error) 1754 return false; 1755 } 1756 1757 /* 1758 * Check that there is enough free space for the file plus a chunk of 1759 * inodes if we need to allocate some. If this is the first pass across 1760 * the AGs, take into account the potential space needed for alignment 1761 * of inode chunks when checking the longest contiguous free space in 1762 * the AG - this prevents us from getting ENOSPC because we have free 1763 * space larger than ialloc_blks but alignment constraints prevent us 1764 * from using it. 1765 * 1766 * If we can't find an AG with space for full alignment slack to be 1767 * taken into account, we must be near ENOSPC in all AGs. Hence we 1768 * don't include alignment for the second pass and so if we fail 1769 * allocation due to alignment issues then it is most likely a real 1770 * ENOSPC condition. 1771 * 1772 * XXX(dgc): this calculation is now bogus thanks to the per-ag 1773 * reservations that xfs_alloc_fix_freelist() now does via 1774 * xfs_alloc_space_available(). When the AG fills up, pagf_freeblks will 1775 * be more than large enough for the check below to succeed, but 1776 * xfs_alloc_space_available() will fail because of the non-zero 1777 * metadata reservation and hence we won't actually be able to allocate 1778 * more inodes in this AG. We do soooo much unnecessary work near ENOSPC 1779 * because of this. 1780 */ 1781 ineed = M_IGEO(mp)->ialloc_min_blks; 1782 if (flags && ineed > 1) 1783 ineed += M_IGEO(mp)->cluster_align; 1784 longest = pag->pagf_longest; 1785 if (!longest) 1786 longest = pag->pagf_flcount > 0; 1787 needspace = S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode); 1788 1789 if (pag->pagf_freeblks < needspace + ineed || longest < ineed) 1790 return false; 1791 return true; 1792} 1793 1794static int 1795xfs_dialloc_try_ag( 1796 struct xfs_perag *pag, 1797 struct xfs_trans **tpp, 1798 xfs_ino_t parent, 1799 xfs_ino_t *new_ino, 1800 bool ok_alloc) 1801{ 1802 struct xfs_buf *agbp; 1803 xfs_ino_t ino; 1804 int error; 1805 1806 /* 1807 * Then read in the AGI buffer and recheck with the AGI buffer 1808 * lock held. 1809 */ 1810 error = xfs_ialloc_read_agi(pag, *tpp, 0, &agbp); 1811 if (error) 1812 return error; 1813 1814 if (!pag->pagi_freecount) { 1815 if (!ok_alloc) { 1816 error = -EAGAIN; 1817 goto out_release; 1818 } 1819 1820 error = xfs_ialloc_ag_alloc(pag, *tpp, agbp); 1821 if (error < 0) 1822 goto out_release; 1823 1824 /* 1825 * We successfully allocated space for an inode cluster in this 1826 * AG. Roll the transaction so that we can allocate one of the 1827 * new inodes. 1828 */ 1829 ASSERT(pag->pagi_freecount > 0); 1830 error = xfs_dialloc_roll(tpp, agbp); 1831 if (error) 1832 goto out_release; 1833 } 1834 1835 /* Allocate an inode in the found AG */ 1836 error = xfs_dialloc_ag(pag, *tpp, agbp, parent, &ino); 1837 if (!error) 1838 *new_ino = ino; 1839 return error; 1840 1841out_release: 1842 xfs_trans_brelse(*tpp, agbp); 1843 return error; 1844} 1845 1846/* 1847 * Pick an AG for the new inode. 1848 * 1849 * Directories, symlinks, and regular files frequently allocate at least one 1850 * block, so factor that potential expansion when we examine whether an AG has 1851 * enough space for file creation. Try to keep metadata files all in the same 1852 * AG. 1853 */ 1854static inline xfs_agnumber_t 1855xfs_dialloc_pick_ag( 1856 struct xfs_mount *mp, 1857 struct xfs_inode *dp, 1858 umode_t mode) 1859{ 1860 xfs_agnumber_t start_agno; 1861 1862 if (!dp) 1863 return 0; 1864 if (xfs_is_metadir_inode(dp)) { 1865 if (mp->m_sb.sb_logstart) 1866 return XFS_FSB_TO_AGNO(mp, mp->m_sb.sb_logstart); 1867 return 0; 1868 } 1869 1870 if (S_ISDIR(mode)) 1871 return (atomic_inc_return(&mp->m_agirotor) - 1) % mp->m_maxagi; 1872 1873 start_agno = XFS_INO_TO_AGNO(mp, dp->i_ino); 1874 if (start_agno >= mp->m_maxagi) 1875 start_agno = 0; 1876 1877 return start_agno; 1878} 1879 1880/* 1881 * Allocate an on-disk inode. 1882 * 1883 * Mode is used to tell whether the new inode is a directory and hence where to 1884 * locate it. The on-disk inode that is allocated will be returned in @new_ino 1885 * on success, otherwise an error will be set to indicate the failure (e.g. 1886 * -ENOSPC). 1887 */ 1888int 1889xfs_dialloc( 1890 struct xfs_trans **tpp, 1891 const struct xfs_icreate_args *args, 1892 xfs_ino_t *new_ino) 1893{ 1894 struct xfs_mount *mp = (*tpp)->t_mountp; 1895 struct xfs_perag *pag; 1896 struct xfs_ino_geometry *igeo = M_IGEO(mp); 1897 xfs_ino_t ino = NULLFSINO; 1898 xfs_ino_t parent = args->pip ? args->pip->i_ino : 0; 1899 xfs_agnumber_t agno; 1900 xfs_agnumber_t start_agno; 1901 umode_t mode = args->mode & S_IFMT; 1902 bool ok_alloc = true; 1903 bool low_space = false; 1904 int flags; 1905 int error = 0; 1906 1907 start_agno = xfs_dialloc_pick_ag(mp, args->pip, mode); 1908 1909 /* 1910 * If we have already hit the ceiling of inode blocks then clear 1911 * ok_alloc so we scan all available agi structures for a free 1912 * inode. 1913 * 1914 * Read rough value of mp->m_icount by percpu_counter_read_positive, 1915 * which will sacrifice the preciseness but improve the performance. 1916 */ 1917 if (igeo->maxicount && 1918 percpu_counter_read_positive(&mp->m_icount) + igeo->ialloc_inos 1919 > igeo->maxicount) { 1920 ok_alloc = false; 1921 } 1922 1923 /* 1924 * If we are near to ENOSPC, we want to prefer allocation from AGs that 1925 * have free inodes in them rather than use up free space allocating new 1926 * inode chunks. Hence we turn off allocation for the first non-blocking 1927 * pass through the AGs if we are near ENOSPC to consume free inodes 1928 * that we can immediately allocate, but then we allow allocation on the 1929 * second pass if we fail to find an AG with free inodes in it. 1930 */ 1931 if (xfs_estimate_freecounter(mp, XC_FREE_BLOCKS) < 1932 mp->m_low_space[XFS_LOWSP_1_PCNT]) { 1933 ok_alloc = false; 1934 low_space = true; 1935 } 1936 1937 /* 1938 * Loop until we find an allocation group that either has free inodes 1939 * or in which we can allocate some inodes. Iterate through the 1940 * allocation groups upward, wrapping at the end. 1941 */ 1942 flags = XFS_ALLOC_FLAG_TRYLOCK; 1943retry: 1944 for_each_perag_wrap_at(mp, start_agno, mp->m_maxagi, agno, pag) { 1945 if (xfs_dialloc_good_ag(pag, *tpp, mode, flags, ok_alloc)) { 1946 error = xfs_dialloc_try_ag(pag, tpp, parent, 1947 &ino, ok_alloc); 1948 if (error != -EAGAIN) 1949 break; 1950 error = 0; 1951 } 1952 1953 if (xfs_is_shutdown(mp)) { 1954 error = -EFSCORRUPTED; 1955 break; 1956 } 1957 } 1958 if (pag) 1959 xfs_perag_rele(pag); 1960 if (error) 1961 return error; 1962 if (ino == NULLFSINO) { 1963 if (flags) { 1964 flags = 0; 1965 if (low_space) 1966 ok_alloc = true; 1967 goto retry; 1968 } 1969 return -ENOSPC; 1970 } 1971 1972 /* 1973 * Protect against obviously corrupt allocation btree records. Later 1974 * xfs_iget checks will catch re-allocation of other active in-memory 1975 * and on-disk inodes. If we don't catch reallocating the parent inode 1976 * here we will deadlock in xfs_iget() so we have to do these checks 1977 * first. 1978 */ 1979 if (ino == parent || !xfs_verify_dir_ino(mp, ino)) { 1980 xfs_alert(mp, "Allocated a known in-use inode 0x%llx!", ino); 1981 xfs_agno_mark_sick(mp, XFS_INO_TO_AGNO(mp, ino), 1982 XFS_SICK_AG_INOBT); 1983 return -EFSCORRUPTED; 1984 } 1985 1986 *new_ino = ino; 1987 return 0; 1988} 1989 1990/* 1991 * Free the blocks of an inode chunk. We must consider that the inode chunk 1992 * might be sparse and only free the regions that are allocated as part of the 1993 * chunk. 1994 */ 1995static int 1996xfs_difree_inode_chunk( 1997 struct xfs_trans *tp, 1998 struct xfs_perag *pag, 1999 struct xfs_inobt_rec_incore *rec) 2000{ 2001 struct xfs_mount *mp = tp->t_mountp; 2002 xfs_agblock_t sagbno = XFS_AGINO_TO_AGBNO(mp, 2003 rec->ir_startino); 2004 int startidx, endidx; 2005 int nextbit; 2006 xfs_agblock_t agbno; 2007 int contigblk; 2008 DECLARE_BITMAP(holemask, XFS_INOBT_HOLEMASK_BITS); 2009 2010 if (!xfs_inobt_issparse(rec->ir_holemask)) { 2011 /* not sparse, calculate extent info directly */ 2012 return xfs_free_extent_later(tp, xfs_agbno_to_fsb(pag, sagbno), 2013 M_IGEO(mp)->ialloc_blks, &XFS_RMAP_OINFO_INODES, 2014 XFS_AG_RESV_NONE, 0); 2015 } 2016 2017 /* holemask is only 16-bits (fits in an unsigned long) */ 2018 ASSERT(sizeof(rec->ir_holemask) <= sizeof(holemask[0])); 2019 holemask[0] = rec->ir_holemask; 2020 2021 /* 2022 * Find contiguous ranges of zeroes (i.e., allocated regions) in the 2023 * holemask and convert the start/end index of each range to an extent. 2024 * We start with the start and end index both pointing at the first 0 in 2025 * the mask. 2026 */ 2027 startidx = endidx = find_first_zero_bit(holemask, 2028 XFS_INOBT_HOLEMASK_BITS); 2029 nextbit = startidx + 1; 2030 while (startidx < XFS_INOBT_HOLEMASK_BITS) { 2031 int error; 2032 2033 nextbit = find_next_zero_bit(holemask, XFS_INOBT_HOLEMASK_BITS, 2034 nextbit); 2035 /* 2036 * If the next zero bit is contiguous, update the end index of 2037 * the current range and continue. 2038 */ 2039 if (nextbit != XFS_INOBT_HOLEMASK_BITS && 2040 nextbit == endidx + 1) { 2041 endidx = nextbit; 2042 goto next; 2043 } 2044 2045 /* 2046 * nextbit is not contiguous with the current end index. Convert 2047 * the current start/end to an extent and add it to the free 2048 * list. 2049 */ 2050 agbno = sagbno + (startidx * XFS_INODES_PER_HOLEMASK_BIT) / 2051 mp->m_sb.sb_inopblock; 2052 contigblk = ((endidx - startidx + 1) * 2053 XFS_INODES_PER_HOLEMASK_BIT) / 2054 mp->m_sb.sb_inopblock; 2055 2056 ASSERT(agbno % mp->m_sb.sb_spino_align == 0); 2057 ASSERT(contigblk % mp->m_sb.sb_spino_align == 0); 2058 error = xfs_free_extent_later(tp, xfs_agbno_to_fsb(pag, agbno), 2059 contigblk, &XFS_RMAP_OINFO_INODES, 2060 XFS_AG_RESV_NONE, 0); 2061 if (error) 2062 return error; 2063 2064 /* reset range to current bit and carry on... */ 2065 startidx = endidx = nextbit; 2066 2067next: 2068 nextbit++; 2069 } 2070 return 0; 2071} 2072 2073STATIC int 2074xfs_difree_inobt( 2075 struct xfs_perag *pag, 2076 struct xfs_trans *tp, 2077 struct xfs_buf *agbp, 2078 xfs_agino_t agino, 2079 struct xfs_icluster *xic, 2080 struct xfs_inobt_rec_incore *orec) 2081{ 2082 struct xfs_mount *mp = pag_mount(pag); 2083 struct xfs_agi *agi = agbp->b_addr; 2084 struct xfs_btree_cur *cur; 2085 struct xfs_inobt_rec_incore rec; 2086 int ilen; 2087 int error; 2088 int i; 2089 int off; 2090 2091 ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC)); 2092 ASSERT(XFS_AGINO_TO_AGBNO(mp, agino) < be32_to_cpu(agi->agi_length)); 2093 2094 /* 2095 * Initialize the cursor. 2096 */ 2097 cur = xfs_inobt_init_cursor(pag, tp, agbp); 2098 2099 error = xfs_check_agi_freecount(cur); 2100 if (error) 2101 goto error0; 2102 2103 /* 2104 * Look for the entry describing this inode. 2105 */ 2106 if ((error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i))) { 2107 xfs_warn(mp, "%s: xfs_inobt_lookup() returned error %d.", 2108 __func__, error); 2109 goto error0; 2110 } 2111 if (XFS_IS_CORRUPT(mp, i != 1)) { 2112 xfs_btree_mark_sick(cur); 2113 error = -EFSCORRUPTED; 2114 goto error0; 2115 } 2116 error = xfs_inobt_get_rec(cur, &rec, &i); 2117 if (error) { 2118 xfs_warn(mp, "%s: xfs_inobt_get_rec() returned error %d.", 2119 __func__, error); 2120 goto error0; 2121 } 2122 if (XFS_IS_CORRUPT(mp, i != 1)) { 2123 xfs_btree_mark_sick(cur); 2124 error = -EFSCORRUPTED; 2125 goto error0; 2126 } 2127 /* 2128 * Get the offset in the inode chunk. 2129 */ 2130 off = agino - rec.ir_startino; 2131 ASSERT(off >= 0 && off < XFS_INODES_PER_CHUNK); 2132 ASSERT(!(rec.ir_free & XFS_INOBT_MASK(off))); 2133 /* 2134 * Mark the inode free & increment the count. 2135 */ 2136 rec.ir_free |= XFS_INOBT_MASK(off); 2137 rec.ir_freecount++; 2138 2139 /* 2140 * When an inode chunk is free, it becomes eligible for removal. Don't 2141 * remove the chunk if the block size is large enough for multiple inode 2142 * chunks (that might not be free). 2143 */ 2144 if (rec.ir_free == XFS_INOBT_ALL_FREE && 2145 mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) { 2146 xic->deleted = true; 2147 xic->first_ino = xfs_agino_to_ino(pag, rec.ir_startino); 2148 xic->alloc = xfs_inobt_irec_to_allocmask(&rec); 2149 2150 /* 2151 * Remove the inode cluster from the AGI B+Tree, adjust the 2152 * AGI and Superblock inode counts, and mark the disk space 2153 * to be freed when the transaction is committed. 2154 */ 2155 ilen = rec.ir_freecount; 2156 be32_add_cpu(&agi->agi_count, -ilen); 2157 be32_add_cpu(&agi->agi_freecount, -(ilen - 1)); 2158 xfs_ialloc_log_agi(tp, agbp, XFS_AGI_COUNT | XFS_AGI_FREECOUNT); 2159 pag->pagi_freecount -= ilen - 1; 2160 pag->pagi_count -= ilen; 2161 xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen); 2162 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1)); 2163 2164 if ((error = xfs_btree_delete(cur, &i))) { 2165 xfs_warn(mp, "%s: xfs_btree_delete returned error %d.", 2166 __func__, error); 2167 goto error0; 2168 } 2169 2170 error = xfs_difree_inode_chunk(tp, pag, &rec); 2171 if (error) 2172 goto error0; 2173 } else { 2174 xic->deleted = false; 2175 2176 error = xfs_inobt_update(cur, &rec); 2177 if (error) { 2178 xfs_warn(mp, "%s: xfs_inobt_update returned error %d.", 2179 __func__, error); 2180 goto error0; 2181 } 2182 2183 /* 2184 * Change the inode free counts and log the ag/sb changes. 2185 */ 2186 be32_add_cpu(&agi->agi_freecount, 1); 2187 xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT); 2188 pag->pagi_freecount++; 2189 xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, 1); 2190 } 2191 2192 error = xfs_check_agi_freecount(cur); 2193 if (error) 2194 goto error0; 2195 2196 *orec = rec; 2197 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 2198 return 0; 2199 2200error0: 2201 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 2202 return error; 2203} 2204 2205/* 2206 * Free an inode in the free inode btree. 2207 */ 2208STATIC int 2209xfs_difree_finobt( 2210 struct xfs_perag *pag, 2211 struct xfs_trans *tp, 2212 struct xfs_buf *agbp, 2213 xfs_agino_t agino, 2214 struct xfs_inobt_rec_incore *ibtrec) /* inobt record */ 2215{ 2216 struct xfs_mount *mp = pag_mount(pag); 2217 struct xfs_btree_cur *cur; 2218 struct xfs_inobt_rec_incore rec; 2219 int offset = agino - ibtrec->ir_startino; 2220 int error; 2221 int i; 2222 2223 cur = xfs_finobt_init_cursor(pag, tp, agbp); 2224 2225 error = xfs_inobt_lookup(cur, ibtrec->ir_startino, XFS_LOOKUP_EQ, &i); 2226 if (error) 2227 goto error; 2228 if (i == 0) { 2229 /* 2230 * If the record does not exist in the finobt, we must have just 2231 * freed an inode in a previously fully allocated chunk. If not, 2232 * something is out of sync. 2233 */ 2234 if (XFS_IS_CORRUPT(mp, ibtrec->ir_freecount != 1)) { 2235 xfs_btree_mark_sick(cur); 2236 error = -EFSCORRUPTED; 2237 goto error; 2238 } 2239 2240 error = xfs_inobt_insert_rec(cur, ibtrec->ir_holemask, 2241 ibtrec->ir_count, 2242 ibtrec->ir_freecount, 2243 ibtrec->ir_free, &i); 2244 if (error) 2245 goto error; 2246 ASSERT(i == 1); 2247 2248 goto out; 2249 } 2250 2251 /* 2252 * Read and update the existing record. We could just copy the ibtrec 2253 * across here, but that would defeat the purpose of having redundant 2254 * metadata. By making the modifications independently, we can catch 2255 * corruptions that we wouldn't see if we just copied from one record 2256 * to another. 2257 */ 2258 error = xfs_inobt_get_rec(cur, &rec, &i); 2259 if (error) 2260 goto error; 2261 if (XFS_IS_CORRUPT(mp, i != 1)) { 2262 xfs_btree_mark_sick(cur); 2263 error = -EFSCORRUPTED; 2264 goto error; 2265 } 2266 2267 rec.ir_free |= XFS_INOBT_MASK(offset); 2268 rec.ir_freecount++; 2269 2270 if (XFS_IS_CORRUPT(mp, 2271 rec.ir_free != ibtrec->ir_free || 2272 rec.ir_freecount != ibtrec->ir_freecount)) { 2273 xfs_btree_mark_sick(cur); 2274 error = -EFSCORRUPTED; 2275 goto error; 2276 } 2277 2278 /* 2279 * The content of inobt records should always match between the inobt 2280 * and finobt. The lifecycle of records in the finobt is different from 2281 * the inobt in that the finobt only tracks records with at least one 2282 * free inode. Hence, if all of the inodes are free and we aren't 2283 * keeping inode chunks permanently on disk, remove the record. 2284 * Otherwise, update the record with the new information. 2285 * 2286 * Note that we currently can't free chunks when the block size is large 2287 * enough for multiple chunks. Leave the finobt record to remain in sync 2288 * with the inobt. 2289 */ 2290 if (rec.ir_free == XFS_INOBT_ALL_FREE && 2291 mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) { 2292 error = xfs_btree_delete(cur, &i); 2293 if (error) 2294 goto error; 2295 ASSERT(i == 1); 2296 } else { 2297 error = xfs_inobt_update(cur, &rec); 2298 if (error) 2299 goto error; 2300 } 2301 2302out: 2303 error = xfs_check_agi_freecount(cur); 2304 if (error) 2305 goto error; 2306 2307 xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR); 2308 return 0; 2309 2310error: 2311 xfs_btree_del_cursor(cur, XFS_BTREE_ERROR); 2312 return error; 2313} 2314 2315/* 2316 * Free disk inode. Carefully avoids touching the incore inode, all 2317 * manipulations incore are the caller's responsibility. 2318 * The on-disk inode is not changed by this operation, only the 2319 * btree (free inode mask) is changed. 2320 */ 2321int 2322xfs_difree( 2323 struct xfs_trans *tp, 2324 struct xfs_perag *pag, 2325 xfs_ino_t inode, 2326 struct xfs_icluster *xic) 2327{ 2328 /* REFERENCED */ 2329 xfs_agblock_t agbno; /* block number containing inode */ 2330 struct xfs_buf *agbp; /* buffer for allocation group header */ 2331 xfs_agino_t agino; /* allocation group inode number */ 2332 int error; /* error return value */ 2333 struct xfs_mount *mp = tp->t_mountp; 2334 struct xfs_inobt_rec_incore rec;/* btree record */ 2335 2336 /* 2337 * Break up inode number into its components. 2338 */ 2339 if (pag_agno(pag) != XFS_INO_TO_AGNO(mp, inode)) { 2340 xfs_warn(mp, "%s: agno != pag_agno(pag) (%d != %d).", 2341 __func__, XFS_INO_TO_AGNO(mp, inode), pag_agno(pag)); 2342 ASSERT(0); 2343 return -EINVAL; 2344 } 2345 agino = XFS_INO_TO_AGINO(mp, inode); 2346 if (inode != xfs_agino_to_ino(pag, agino)) { 2347 xfs_warn(mp, "%s: inode != xfs_agino_to_ino() (%llu != %llu).", 2348 __func__, (unsigned long long)inode, 2349 (unsigned long long)xfs_agino_to_ino(pag, agino)); 2350 ASSERT(0); 2351 return -EINVAL; 2352 } 2353 agbno = XFS_AGINO_TO_AGBNO(mp, agino); 2354 if (agbno >= xfs_ag_block_count(mp, pag_agno(pag))) { 2355 xfs_warn(mp, "%s: agbno >= xfs_ag_block_count (%d >= %d).", 2356 __func__, agbno, xfs_ag_block_count(mp, pag_agno(pag))); 2357 ASSERT(0); 2358 return -EINVAL; 2359 } 2360 /* 2361 * Get the allocation group header. 2362 */ 2363 error = xfs_ialloc_read_agi(pag, tp, 0, &agbp); 2364 if (error) { 2365 xfs_warn(mp, "%s: xfs_ialloc_read_agi() returned error %d.", 2366 __func__, error); 2367 return error; 2368 } 2369 2370 /* 2371 * Fix up the inode allocation btree. 2372 */ 2373 error = xfs_difree_inobt(pag, tp, agbp, agino, xic, &rec); 2374 if (error) 2375 goto error0; 2376 2377 /* 2378 * Fix up the free inode btree. 2379 */ 2380 if (xfs_has_finobt(mp)) { 2381 error = xfs_difree_finobt(pag, tp, agbp, agino, &rec); 2382 if (error) 2383 goto error0; 2384 } 2385 2386 return 0; 2387 2388error0: 2389 return error; 2390} 2391 2392STATIC int 2393xfs_imap_lookup( 2394 struct xfs_perag *pag, 2395 struct xfs_trans *tp, 2396 xfs_agino_t agino, 2397 xfs_agblock_t agbno, 2398 xfs_agblock_t *chunk_agbno, 2399 xfs_agblock_t *offset_agbno, 2400 int flags) 2401{ 2402 struct xfs_mount *mp = pag_mount(pag); 2403 struct xfs_inobt_rec_incore rec; 2404 struct xfs_btree_cur *cur; 2405 struct xfs_buf *agbp; 2406 int error; 2407 int i; 2408 2409 error = xfs_ialloc_read_agi(pag, tp, 0, &agbp); 2410 if (error) { 2411 xfs_alert(mp, 2412 "%s: xfs_ialloc_read_agi() returned error %d, agno %d", 2413 __func__, error, pag_agno(pag)); 2414 return error; 2415 } 2416 2417 /* 2418 * Lookup the inode record for the given agino. If the record cannot be 2419 * found, then it's an invalid inode number and we should abort. Once 2420 * we have a record, we need to ensure it contains the inode number 2421 * we are looking up. 2422 */ 2423 cur = xfs_inobt_init_cursor(pag, tp, agbp); 2424 error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i); 2425 if (!error) { 2426 if (i) 2427 error = xfs_inobt_get_rec(cur, &rec, &i); 2428 if (!error && i == 0) 2429 error = -EINVAL; 2430 } 2431 2432 xfs_trans_brelse(tp, agbp); 2433 xfs_btree_del_cursor(cur, error); 2434 if (error) 2435 return error; 2436 2437 /* check that the returned record contains the required inode */ 2438 if (rec.ir_startino > agino || 2439 rec.ir_startino + M_IGEO(mp)->ialloc_inos <= agino) 2440 return -EINVAL; 2441 2442 /* for untrusted inodes check it is allocated first */ 2443 if ((flags & XFS_IGET_UNTRUSTED) && 2444 (rec.ir_free & XFS_INOBT_MASK(agino - rec.ir_startino))) 2445 return -EINVAL; 2446 2447 *chunk_agbno = XFS_AGINO_TO_AGBNO(mp, rec.ir_startino); 2448 *offset_agbno = agbno - *chunk_agbno; 2449 return 0; 2450} 2451 2452/* 2453 * Return the location of the inode in imap, for mapping it into a buffer. 2454 */ 2455int 2456xfs_imap( 2457 struct xfs_perag *pag, 2458 struct xfs_trans *tp, 2459 xfs_ino_t ino, /* inode to locate */ 2460 struct xfs_imap *imap, /* location map structure */ 2461 uint flags) /* flags for inode btree lookup */ 2462{ 2463 struct xfs_mount *mp = pag_mount(pag); 2464 xfs_agblock_t agbno; /* block number of inode in the alloc group */ 2465 xfs_agino_t agino; /* inode number within alloc group */ 2466 xfs_agblock_t chunk_agbno; /* first block in inode chunk */ 2467 xfs_agblock_t cluster_agbno; /* first block in inode cluster */ 2468 int error; /* error code */ 2469 int offset; /* index of inode in its buffer */ 2470 xfs_agblock_t offset_agbno; /* blks from chunk start to inode */ 2471 2472 ASSERT(ino != NULLFSINO); 2473 2474 /* 2475 * Split up the inode number into its parts. 2476 */ 2477 agino = XFS_INO_TO_AGINO(mp, ino); 2478 agbno = XFS_AGINO_TO_AGBNO(mp, agino); 2479 if (agbno >= xfs_ag_block_count(mp, pag_agno(pag)) || 2480 ino != xfs_agino_to_ino(pag, agino)) { 2481 error = -EINVAL; 2482#ifdef DEBUG 2483 /* 2484 * Don't output diagnostic information for untrusted inodes 2485 * as they can be invalid without implying corruption. 2486 */ 2487 if (flags & XFS_IGET_UNTRUSTED) 2488 return error; 2489 if (agbno >= xfs_ag_block_count(mp, pag_agno(pag))) { 2490 xfs_alert(mp, 2491 "%s: agbno (0x%llx) >= mp->m_sb.sb_agblocks (0x%lx)", 2492 __func__, (unsigned long long)agbno, 2493 (unsigned long)xfs_ag_block_count(mp, 2494 pag_agno(pag))); 2495 } 2496 if (ino != xfs_agino_to_ino(pag, agino)) { 2497 xfs_alert(mp, 2498 "%s: ino (0x%llx) != xfs_agino_to_ino() (0x%llx)", 2499 __func__, ino, 2500 xfs_agino_to_ino(pag, agino)); 2501 } 2502 xfs_stack_trace(); 2503#endif /* DEBUG */ 2504 return error; 2505 } 2506 2507 /* 2508 * For bulkstat and handle lookups, we have an untrusted inode number 2509 * that we have to verify is valid. We cannot do this just by reading 2510 * the inode buffer as it may have been unlinked and removed leaving 2511 * inodes in stale state on disk. Hence we have to do a btree lookup 2512 * in all cases where an untrusted inode number is passed. 2513 */ 2514 if (flags & XFS_IGET_UNTRUSTED) { 2515 error = xfs_imap_lookup(pag, tp, agino, agbno, 2516 &chunk_agbno, &offset_agbno, flags); 2517 if (error) 2518 return error; 2519 goto out_map; 2520 } 2521 2522 /* 2523 * If the inode cluster size is the same as the blocksize or 2524 * smaller we get to the buffer by simple arithmetics. 2525 */ 2526 if (M_IGEO(mp)->blocks_per_cluster == 1) { 2527 offset = XFS_INO_TO_OFFSET(mp, ino); 2528 ASSERT(offset < mp->m_sb.sb_inopblock); 2529 2530 imap->im_blkno = xfs_agbno_to_daddr(pag, agbno); 2531 imap->im_len = XFS_FSB_TO_BB(mp, 1); 2532 imap->im_boffset = (unsigned short)(offset << 2533 mp->m_sb.sb_inodelog); 2534 return 0; 2535 } 2536 2537 /* 2538 * If the inode chunks are aligned then use simple maths to 2539 * find the location. Otherwise we have to do a btree 2540 * lookup to find the location. 2541 */ 2542 if (M_IGEO(mp)->inoalign_mask) { 2543 offset_agbno = agbno & M_IGEO(mp)->inoalign_mask; 2544 chunk_agbno = agbno - offset_agbno; 2545 } else { 2546 error = xfs_imap_lookup(pag, tp, agino, agbno, 2547 &chunk_agbno, &offset_agbno, flags); 2548 if (error) 2549 return error; 2550 } 2551 2552out_map: 2553 ASSERT(agbno >= chunk_agbno); 2554 cluster_agbno = chunk_agbno + 2555 ((offset_agbno / M_IGEO(mp)->blocks_per_cluster) * 2556 M_IGEO(mp)->blocks_per_cluster); 2557 offset = ((agbno - cluster_agbno) * mp->m_sb.sb_inopblock) + 2558 XFS_INO_TO_OFFSET(mp, ino); 2559 2560 imap->im_blkno = xfs_agbno_to_daddr(pag, cluster_agbno); 2561 imap->im_len = XFS_FSB_TO_BB(mp, M_IGEO(mp)->blocks_per_cluster); 2562 imap->im_boffset = (unsigned short)(offset << mp->m_sb.sb_inodelog); 2563 2564 /* 2565 * If the inode number maps to a block outside the bounds 2566 * of the file system then return NULL rather than calling 2567 * read_buf and panicing when we get an error from the 2568 * driver. 2569 */ 2570 if ((imap->im_blkno + imap->im_len) > 2571 XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks)) { 2572 xfs_alert(mp, 2573 "%s: (im_blkno (0x%llx) + im_len (0x%llx)) > sb_dblocks (0x%llx)", 2574 __func__, (unsigned long long) imap->im_blkno, 2575 (unsigned long long) imap->im_len, 2576 XFS_FSB_TO_BB(mp, mp->m_sb.sb_dblocks)); 2577 return -EINVAL; 2578 } 2579 return 0; 2580} 2581 2582/* 2583 * Log specified fields for the ag hdr (inode section). The growth of the agi 2584 * structure over time requires that we interpret the buffer as two logical 2585 * regions delineated by the end of the unlinked list. This is due to the size 2586 * of the hash table and its location in the middle of the agi. 2587 * 2588 * For example, a request to log a field before agi_unlinked and a field after 2589 * agi_unlinked could cause us to log the entire hash table and use an excessive 2590 * amount of log space. To avoid this behavior, log the region up through 2591 * agi_unlinked in one call and the region after agi_unlinked through the end of 2592 * the structure in another. 2593 */ 2594void 2595xfs_ialloc_log_agi( 2596 struct xfs_trans *tp, 2597 struct xfs_buf *bp, 2598 uint32_t fields) 2599{ 2600 int first; /* first byte number */ 2601 int last; /* last byte number */ 2602 static const short offsets[] = { /* field starting offsets */ 2603 /* keep in sync with bit definitions */ 2604 offsetof(xfs_agi_t, agi_magicnum), 2605 offsetof(xfs_agi_t, agi_versionnum), 2606 offsetof(xfs_agi_t, agi_seqno), 2607 offsetof(xfs_agi_t, agi_length), 2608 offsetof(xfs_agi_t, agi_count), 2609 offsetof(xfs_agi_t, agi_root), 2610 offsetof(xfs_agi_t, agi_level), 2611 offsetof(xfs_agi_t, agi_freecount), 2612 offsetof(xfs_agi_t, agi_newino), 2613 offsetof(xfs_agi_t, agi_dirino), 2614 offsetof(xfs_agi_t, agi_unlinked), 2615 offsetof(xfs_agi_t, agi_free_root), 2616 offsetof(xfs_agi_t, agi_free_level), 2617 offsetof(xfs_agi_t, agi_iblocks), 2618 sizeof(xfs_agi_t) 2619 }; 2620#ifdef DEBUG 2621 struct xfs_agi *agi = bp->b_addr; 2622 2623 ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC)); 2624#endif 2625 2626 /* 2627 * Compute byte offsets for the first and last fields in the first 2628 * region and log the agi buffer. This only logs up through 2629 * agi_unlinked. 2630 */ 2631 if (fields & XFS_AGI_ALL_BITS_R1) { 2632 xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R1, 2633 &first, &last); 2634 xfs_trans_log_buf(tp, bp, first, last); 2635 } 2636 2637 /* 2638 * Mask off the bits in the first region and calculate the first and 2639 * last field offsets for any bits in the second region. 2640 */ 2641 fields &= ~XFS_AGI_ALL_BITS_R1; 2642 if (fields) { 2643 xfs_btree_offsets(fields, offsets, XFS_AGI_NUM_BITS_R2, 2644 &first, &last); 2645 xfs_trans_log_buf(tp, bp, first, last); 2646 } 2647} 2648 2649static xfs_failaddr_t 2650xfs_agi_verify( 2651 struct xfs_buf *bp) 2652{ 2653 struct xfs_mount *mp = bp->b_mount; 2654 struct xfs_agi *agi = bp->b_addr; 2655 xfs_failaddr_t fa; 2656 uint32_t agi_seqno = be32_to_cpu(agi->agi_seqno); 2657 uint32_t agi_length = be32_to_cpu(agi->agi_length); 2658 int i; 2659 2660 if (xfs_has_crc(mp)) { 2661 if (!uuid_equal(&agi->agi_uuid, &mp->m_sb.sb_meta_uuid)) 2662 return __this_address; 2663 if (!xfs_log_check_lsn(mp, be64_to_cpu(agi->agi_lsn))) 2664 return __this_address; 2665 } 2666 2667 /* 2668 * Validate the magic number of the agi block. 2669 */ 2670 if (!xfs_verify_magic(bp, agi->agi_magicnum)) 2671 return __this_address; 2672 if (!XFS_AGI_GOOD_VERSION(be32_to_cpu(agi->agi_versionnum))) 2673 return __this_address; 2674 2675 fa = xfs_validate_ag_length(bp, agi_seqno, agi_length); 2676 if (fa) 2677 return fa; 2678 2679 if (be32_to_cpu(agi->agi_level) < 1 || 2680 be32_to_cpu(agi->agi_level) > M_IGEO(mp)->inobt_maxlevels) 2681 return __this_address; 2682 2683 if (xfs_has_finobt(mp) && 2684 (be32_to_cpu(agi->agi_free_level) < 1 || 2685 be32_to_cpu(agi->agi_free_level) > M_IGEO(mp)->inobt_maxlevels)) 2686 return __this_address; 2687 2688 for (i = 0; i < XFS_AGI_UNLINKED_BUCKETS; i++) { 2689 if (agi->agi_unlinked[i] == cpu_to_be32(NULLAGINO)) 2690 continue; 2691 if (!xfs_verify_ino(mp, be32_to_cpu(agi->agi_unlinked[i]))) 2692 return __this_address; 2693 } 2694 2695 return NULL; 2696} 2697 2698static void 2699xfs_agi_read_verify( 2700 struct xfs_buf *bp) 2701{ 2702 struct xfs_mount *mp = bp->b_mount; 2703 xfs_failaddr_t fa; 2704 2705 if (xfs_has_crc(mp) && 2706 !xfs_buf_verify_cksum(bp, XFS_AGI_CRC_OFF)) 2707 xfs_verifier_error(bp, -EFSBADCRC, __this_address); 2708 else { 2709 fa = xfs_agi_verify(bp); 2710 if (fa || XFS_TEST_ERROR(mp, XFS_ERRTAG_IALLOC_READ_AGI)) 2711 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 2712 } 2713} 2714 2715static void 2716xfs_agi_write_verify( 2717 struct xfs_buf *bp) 2718{ 2719 struct xfs_mount *mp = bp->b_mount; 2720 struct xfs_buf_log_item *bip = bp->b_log_item; 2721 struct xfs_agi *agi = bp->b_addr; 2722 xfs_failaddr_t fa; 2723 2724 fa = xfs_agi_verify(bp); 2725 if (fa) { 2726 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 2727 return; 2728 } 2729 2730 if (!xfs_has_crc(mp)) 2731 return; 2732 2733 if (bip) 2734 agi->agi_lsn = cpu_to_be64(bip->bli_item.li_lsn); 2735 xfs_buf_update_cksum(bp, XFS_AGI_CRC_OFF); 2736} 2737 2738const struct xfs_buf_ops xfs_agi_buf_ops = { 2739 .name = "xfs_agi", 2740 .magic = { cpu_to_be32(XFS_AGI_MAGIC), cpu_to_be32(XFS_AGI_MAGIC) }, 2741 .verify_read = xfs_agi_read_verify, 2742 .verify_write = xfs_agi_write_verify, 2743 .verify_struct = xfs_agi_verify, 2744}; 2745 2746/* 2747 * Read in the allocation group header (inode allocation section) 2748 */ 2749int 2750xfs_read_agi( 2751 struct xfs_perag *pag, 2752 struct xfs_trans *tp, 2753 xfs_buf_flags_t flags, 2754 struct xfs_buf **agibpp) 2755{ 2756 struct xfs_mount *mp = pag_mount(pag); 2757 int error; 2758 2759 trace_xfs_read_agi(pag); 2760 2761 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, 2762 XFS_AG_DADDR(mp, pag_agno(pag), XFS_AGI_DADDR(mp)), 2763 XFS_FSS_TO_BB(mp, 1), flags, agibpp, &xfs_agi_buf_ops); 2764 if (xfs_metadata_is_sick(error)) 2765 xfs_ag_mark_sick(pag, XFS_SICK_AG_AGI); 2766 if (error) 2767 return error; 2768 if (tp) 2769 xfs_trans_buf_set_type(tp, *agibpp, XFS_BLFT_AGI_BUF); 2770 2771 xfs_buf_set_ref(*agibpp, XFS_AGI_REF); 2772 return 0; 2773} 2774 2775/* 2776 * Read in the agi and initialise the per-ag data. If the caller supplies a 2777 * @agibpp, return the locked AGI buffer to them, otherwise release it. 2778 */ 2779int 2780xfs_ialloc_read_agi( 2781 struct xfs_perag *pag, 2782 struct xfs_trans *tp, 2783 int flags, 2784 struct xfs_buf **agibpp) 2785{ 2786 struct xfs_buf *agibp; 2787 struct xfs_agi *agi; 2788 int error; 2789 2790 trace_xfs_ialloc_read_agi(pag); 2791 2792 error = xfs_read_agi(pag, tp, 2793 (flags & XFS_IALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0, 2794 &agibp); 2795 if (error) 2796 return error; 2797 2798 agi = agibp->b_addr; 2799 if (!xfs_perag_initialised_agi(pag)) { 2800 pag->pagi_freecount = be32_to_cpu(agi->agi_freecount); 2801 pag->pagi_count = be32_to_cpu(agi->agi_count); 2802 set_bit(XFS_AGSTATE_AGI_INIT, &pag->pag_opstate); 2803 } 2804 2805#ifdef DEBUG 2806 /* 2807 * It's possible for the AGF to be out of sync if the block device is 2808 * silently dropping writes. This can happen in fstests with dmflakey 2809 * enabled, which allows the buffer to be cleaned and reclaimed by 2810 * memory pressure and then re-read from disk here. We will get a 2811 * stale version of the AGF from disk, and nothing good can happen from 2812 * here. Hence if we detect this situation, immediately shut down the 2813 * filesystem. 2814 * 2815 * This can also happen if we are already in the middle of a forced 2816 * shutdown, so don't bother checking if we are already shut down. 2817 */ 2818 if (!xfs_is_shutdown(pag_mount(pag))) { 2819 bool ok = true; 2820 2821 ok &= pag->pagi_freecount == be32_to_cpu(agi->agi_freecount); 2822 ok &= pag->pagi_count == be32_to_cpu(agi->agi_count); 2823 2824 if (XFS_IS_CORRUPT(pag_mount(pag), !ok)) { 2825 xfs_ag_mark_sick(pag, XFS_SICK_AG_AGI); 2826 xfs_trans_brelse(tp, agibp); 2827 xfs_force_shutdown(pag_mount(pag), 2828 SHUTDOWN_CORRUPT_ONDISK); 2829 return -EFSCORRUPTED; 2830 } 2831 } 2832#endif /* DEBUG */ 2833 2834 if (agibpp) 2835 *agibpp = agibp; 2836 else 2837 xfs_trans_brelse(tp, agibp); 2838 return 0; 2839} 2840 2841/* How many inodes are backed by inode clusters ondisk? */ 2842STATIC int 2843xfs_ialloc_count_ondisk( 2844 struct xfs_btree_cur *cur, 2845 xfs_agino_t low, 2846 xfs_agino_t high, 2847 unsigned int *allocated) 2848{ 2849 struct xfs_inobt_rec_incore irec; 2850 unsigned int ret = 0; 2851 int has_record; 2852 int error; 2853 2854 error = xfs_inobt_lookup(cur, low, XFS_LOOKUP_LE, &has_record); 2855 if (error) 2856 return error; 2857 2858 while (has_record) { 2859 unsigned int i, hole_idx; 2860 2861 error = xfs_inobt_get_rec(cur, &irec, &has_record); 2862 if (error) 2863 return error; 2864 if (irec.ir_startino > high) 2865 break; 2866 2867 for (i = 0; i < XFS_INODES_PER_CHUNK; i++) { 2868 if (irec.ir_startino + i < low) 2869 continue; 2870 if (irec.ir_startino + i > high) 2871 break; 2872 2873 hole_idx = i / XFS_INODES_PER_HOLEMASK_BIT; 2874 if (!(irec.ir_holemask & (1U << hole_idx))) 2875 ret++; 2876 } 2877 2878 error = xfs_btree_increment(cur, 0, &has_record); 2879 if (error) 2880 return error; 2881 } 2882 2883 *allocated = ret; 2884 return 0; 2885} 2886 2887/* Is there an inode record covering a given extent? */ 2888int 2889xfs_ialloc_has_inodes_at_extent( 2890 struct xfs_btree_cur *cur, 2891 xfs_agblock_t bno, 2892 xfs_extlen_t len, 2893 enum xbtree_recpacking *outcome) 2894{ 2895 xfs_agino_t agino; 2896 xfs_agino_t last_agino; 2897 unsigned int allocated; 2898 int error; 2899 2900 agino = XFS_AGB_TO_AGINO(cur->bc_mp, bno); 2901 last_agino = XFS_AGB_TO_AGINO(cur->bc_mp, bno + len) - 1; 2902 2903 error = xfs_ialloc_count_ondisk(cur, agino, last_agino, &allocated); 2904 if (error) 2905 return error; 2906 2907 if (allocated == 0) 2908 *outcome = XBTREE_RECPACKING_EMPTY; 2909 else if (allocated == last_agino - agino + 1) 2910 *outcome = XBTREE_RECPACKING_FULL; 2911 else 2912 *outcome = XBTREE_RECPACKING_SPARSE; 2913 return 0; 2914} 2915 2916struct xfs_ialloc_count_inodes { 2917 xfs_agino_t count; 2918 xfs_agino_t freecount; 2919}; 2920 2921/* Record inode counts across all inobt records. */ 2922STATIC int 2923xfs_ialloc_count_inodes_rec( 2924 struct xfs_btree_cur *cur, 2925 const union xfs_btree_rec *rec, 2926 void *priv) 2927{ 2928 struct xfs_inobt_rec_incore irec; 2929 struct xfs_ialloc_count_inodes *ci = priv; 2930 xfs_failaddr_t fa; 2931 2932 xfs_inobt_btrec_to_irec(cur->bc_mp, rec, &irec); 2933 fa = xfs_inobt_check_irec(to_perag(cur->bc_group), &irec); 2934 if (fa) 2935 return xfs_inobt_complain_bad_rec(cur, fa, &irec); 2936 2937 ci->count += irec.ir_count; 2938 ci->freecount += irec.ir_freecount; 2939 2940 return 0; 2941} 2942 2943/* Count allocated and free inodes under an inobt. */ 2944int 2945xfs_ialloc_count_inodes( 2946 struct xfs_btree_cur *cur, 2947 xfs_agino_t *count, 2948 xfs_agino_t *freecount) 2949{ 2950 struct xfs_ialloc_count_inodes ci = {0}; 2951 int error; 2952 2953 ASSERT(xfs_btree_is_ino(cur->bc_ops)); 2954 error = xfs_btree_query_all(cur, xfs_ialloc_count_inodes_rec, &ci); 2955 if (error) 2956 return error; 2957 2958 *count = ci.count; 2959 *freecount = ci.freecount; 2960 return 0; 2961} 2962 2963/* 2964 * Initialize inode-related geometry information. 2965 * 2966 * Compute the inode btree min and max levels and set maxicount. 2967 * 2968 * Set the inode cluster size. This may still be overridden by the file 2969 * system block size if it is larger than the chosen cluster size. 2970 * 2971 * For v5 filesystems, scale the cluster size with the inode size to keep a 2972 * constant ratio of inode per cluster buffer, but only if mkfs has set the 2973 * inode alignment value appropriately for larger cluster sizes. 2974 * 2975 * Then compute the inode cluster alignment information. 2976 */ 2977void 2978xfs_ialloc_setup_geometry( 2979 struct xfs_mount *mp) 2980{ 2981 struct xfs_sb *sbp = &mp->m_sb; 2982 struct xfs_ino_geometry *igeo = M_IGEO(mp); 2983 uint64_t icount; 2984 uint inodes; 2985 2986 igeo->new_diflags2 = 0; 2987 if (xfs_has_bigtime(mp)) 2988 igeo->new_diflags2 |= XFS_DIFLAG2_BIGTIME; 2989 if (xfs_has_large_extent_counts(mp)) 2990 igeo->new_diflags2 |= XFS_DIFLAG2_NREXT64; 2991 2992 /* Compute inode btree geometry. */ 2993 igeo->agino_log = sbp->sb_inopblog + sbp->sb_agblklog; 2994 igeo->inobt_mxr[0] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, true); 2995 igeo->inobt_mxr[1] = xfs_inobt_maxrecs(mp, sbp->sb_blocksize, false); 2996 igeo->inobt_mnr[0] = igeo->inobt_mxr[0] / 2; 2997 igeo->inobt_mnr[1] = igeo->inobt_mxr[1] / 2; 2998 2999 igeo->ialloc_inos = max_t(uint16_t, XFS_INODES_PER_CHUNK, 3000 sbp->sb_inopblock); 3001 igeo->ialloc_blks = igeo->ialloc_inos >> sbp->sb_inopblog; 3002 3003 if (sbp->sb_spino_align) 3004 igeo->ialloc_min_blks = sbp->sb_spino_align; 3005 else 3006 igeo->ialloc_min_blks = igeo->ialloc_blks; 3007 3008 /* Compute and fill in value of m_ino_geo.inobt_maxlevels. */ 3009 inodes = (1LL << XFS_INO_AGINO_BITS(mp)) >> XFS_INODES_PER_CHUNK_LOG; 3010 igeo->inobt_maxlevels = xfs_btree_compute_maxlevels(igeo->inobt_mnr, 3011 inodes); 3012 ASSERT(igeo->inobt_maxlevels <= xfs_iallocbt_maxlevels_ondisk()); 3013 3014 /* 3015 * Set the maximum inode count for this filesystem, being careful not 3016 * to use obviously garbage sb_inopblog/sb_inopblock values. Regular 3017 * users should never get here due to failing sb verification, but 3018 * certain users (xfs_db) need to be usable even with corrupt metadata. 3019 */ 3020 if (sbp->sb_imax_pct && igeo->ialloc_blks) { 3021 /* 3022 * Make sure the maximum inode count is a multiple 3023 * of the units we allocate inodes in. 3024 */ 3025 icount = sbp->sb_dblocks * sbp->sb_imax_pct; 3026 do_div(icount, 100); 3027 do_div(icount, igeo->ialloc_blks); 3028 igeo->maxicount = XFS_FSB_TO_INO(mp, 3029 icount * igeo->ialloc_blks); 3030 } else { 3031 igeo->maxicount = 0; 3032 } 3033 3034 /* 3035 * Compute the desired size of an inode cluster buffer size, which 3036 * starts at 8K and (on v5 filesystems) scales up with larger inode 3037 * sizes. 3038 * 3039 * Preserve the desired inode cluster size because the sparse inodes 3040 * feature uses that desired size (not the actual size) to compute the 3041 * sparse inode alignment. The mount code validates this value, so we 3042 * cannot change the behavior. 3043 */ 3044 igeo->inode_cluster_size_raw = XFS_INODE_BIG_CLUSTER_SIZE; 3045 if (xfs_has_v3inodes(mp)) { 3046 int new_size = igeo->inode_cluster_size_raw; 3047 3048 new_size *= mp->m_sb.sb_inodesize / XFS_DINODE_MIN_SIZE; 3049 if (mp->m_sb.sb_inoalignmt >= XFS_B_TO_FSBT(mp, new_size)) 3050 igeo->inode_cluster_size_raw = new_size; 3051 } 3052 3053 /* Calculate inode cluster ratios. */ 3054 if (igeo->inode_cluster_size_raw > mp->m_sb.sb_blocksize) 3055 igeo->blocks_per_cluster = XFS_B_TO_FSBT(mp, 3056 igeo->inode_cluster_size_raw); 3057 else 3058 igeo->blocks_per_cluster = 1; 3059 igeo->inode_cluster_size = XFS_FSB_TO_B(mp, igeo->blocks_per_cluster); 3060 igeo->inodes_per_cluster = XFS_FSB_TO_INO(mp, igeo->blocks_per_cluster); 3061 3062 /* Calculate inode cluster alignment. */ 3063 if (xfs_has_align(mp) && 3064 mp->m_sb.sb_inoalignmt >= igeo->blocks_per_cluster) 3065 igeo->cluster_align = mp->m_sb.sb_inoalignmt; 3066 else 3067 igeo->cluster_align = 1; 3068 igeo->inoalign_mask = igeo->cluster_align - 1; 3069 igeo->cluster_align_inodes = XFS_FSB_TO_INO(mp, igeo->cluster_align); 3070 3071 /* 3072 * If we are using stripe alignment, check whether 3073 * the stripe unit is a multiple of the inode alignment 3074 */ 3075 if (mp->m_dalign && igeo->inoalign_mask && 3076 !(mp->m_dalign & igeo->inoalign_mask)) 3077 igeo->ialloc_align = mp->m_dalign; 3078 else 3079 igeo->ialloc_align = 0; 3080 3081 if (mp->m_sb.sb_blocksize > PAGE_SIZE) 3082 igeo->min_folio_order = mp->m_sb.sb_blocklog - PAGE_SHIFT; 3083 else 3084 igeo->min_folio_order = 0; 3085} 3086 3087/* Compute the location of the root directory inode that is laid out by mkfs. */ 3088xfs_ino_t 3089xfs_ialloc_calc_rootino( 3090 struct xfs_mount *mp, 3091 int sunit) 3092{ 3093 struct xfs_ino_geometry *igeo = M_IGEO(mp); 3094 xfs_agblock_t first_bno; 3095 3096 /* 3097 * Pre-calculate the geometry of AG 0. We know what it looks like 3098 * because libxfs knows how to create allocation groups now. 3099 * 3100 * first_bno is the first block in which mkfs could possibly have 3101 * allocated the root directory inode, once we factor in the metadata 3102 * that mkfs formats before it. Namely, the four AG headers... 3103 */ 3104 first_bno = howmany(4 * mp->m_sb.sb_sectsize, mp->m_sb.sb_blocksize); 3105 3106 /* ...the two free space btree roots... */ 3107 first_bno += 2; 3108 3109 /* ...the inode btree root... */ 3110 first_bno += 1; 3111 3112 /* ...the initial AGFL... */ 3113 first_bno += xfs_alloc_min_freelist(mp, NULL); 3114 3115 /* ...the free inode btree root... */ 3116 if (xfs_has_finobt(mp)) 3117 first_bno++; 3118 3119 /* ...the reverse mapping btree root... */ 3120 if (xfs_has_rmapbt(mp)) 3121 first_bno++; 3122 3123 /* ...the reference count btree... */ 3124 if (xfs_has_reflink(mp)) 3125 first_bno++; 3126 3127 /* 3128 * ...and the log, if it is allocated in the first allocation group. 3129 * 3130 * This can happen with filesystems that only have a single 3131 * allocation group, or very odd geometries created by old mkfs 3132 * versions on very small filesystems. 3133 */ 3134 if (xfs_ag_contains_log(mp, 0)) 3135 first_bno += mp->m_sb.sb_logblocks; 3136 3137 /* 3138 * Now round first_bno up to whatever allocation alignment is given 3139 * by the filesystem or was passed in. 3140 */ 3141 if (xfs_has_dalign(mp) && igeo->ialloc_align > 0) 3142 first_bno = roundup(first_bno, sunit); 3143 else if (xfs_has_align(mp) && 3144 mp->m_sb.sb_inoalignmt > 1) 3145 first_bno = roundup(first_bno, mp->m_sb.sb_inoalignmt); 3146 3147 return XFS_AGINO_TO_INO(mp, 0, XFS_AGB_TO_AGINO(mp, first_bno)); 3148} 3149 3150/* 3151 * Ensure there are not sparse inode clusters that cross the new EOAG. 3152 * 3153 * This is a no-op for non-spinode filesystems since clusters are always fully 3154 * allocated and checking the bnobt suffices. However, a spinode filesystem 3155 * could have a record where the upper inodes are free blocks. If those blocks 3156 * were removed from the filesystem, the inode record would extend beyond EOAG, 3157 * which will be flagged as corruption. 3158 */ 3159int 3160xfs_ialloc_check_shrink( 3161 struct xfs_perag *pag, 3162 struct xfs_trans *tp, 3163 struct xfs_buf *agibp, 3164 xfs_agblock_t new_length) 3165{ 3166 struct xfs_inobt_rec_incore rec; 3167 struct xfs_btree_cur *cur; 3168 xfs_agino_t agino; 3169 int has; 3170 int error; 3171 3172 if (!xfs_has_sparseinodes(pag_mount(pag))) 3173 return 0; 3174 3175 cur = xfs_inobt_init_cursor(pag, tp, agibp); 3176 3177 /* Look up the inobt record that would correspond to the new EOFS. */ 3178 agino = XFS_AGB_TO_AGINO(pag_mount(pag), new_length); 3179 error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &has); 3180 if (error || !has) 3181 goto out; 3182 3183 error = xfs_inobt_get_rec(cur, &rec, &has); 3184 if (error) 3185 goto out; 3186 3187 if (!has) { 3188 xfs_ag_mark_sick(pag, XFS_SICK_AG_INOBT); 3189 error = -EFSCORRUPTED; 3190 goto out; 3191 } 3192 3193 /* If the record covers inodes that would be beyond EOFS, bail out. */ 3194 if (rec.ir_startino + XFS_INODES_PER_CHUNK > agino) { 3195 error = -ENOSPC; 3196 goto out; 3197 } 3198out: 3199 xfs_btree_del_cursor(cur, error); 3200 return error; 3201}
~/
Read-only file preview.