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