1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (c) 2000-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_defer.h" 15 #include "xfs_inode.h" 16 #include "xfs_bmap.h" 17 #include "xfs_bmap_util.h" 18 #include "xfs_bmap_btree.h" 19 #include "xfs_alloc.h" 20 #include "xfs_error.h" 21 #include "xfs_trans.h" 22 #include "xfs_trans_space.h" 23 #include "xfs_trace.h" 24 #include "xfs_buf.h" 25 #include "xfs_icache.h" 26 #include "xfs_rtalloc.h" 27 28 29 /* 30 * Read and return the summary information for a given extent size, 31 * bitmap block combination. 32 * Keeps track of a current summary block, so we don't keep reading 33 * it from the buffer cache. 34 */ 35 static int 36 xfs_rtget_summary( 37 xfs_mount_t *mp, /* file system mount structure */ 38 xfs_trans_t *tp, /* transaction pointer */ 39 int log, /* log2 of extent size */ 40 xfs_rtblock_t bbno, /* bitmap block number */ 41 xfs_buf_t **rbpp, /* in/out: summary block buffer */ 42 xfs_fsblock_t *rsb, /* in/out: summary block number */ 43 xfs_suminfo_t *sum) /* out: summary info for this block */ 44 { 45 return xfs_rtmodify_summary_int(mp, tp, log, bbno, 0, rbpp, rsb, sum); 46 } 47 48 /* 49 * Return whether there are any free extents in the size range given 50 * by low and high, for the bitmap block bbno. 51 */ 52 STATIC int /* error */ 53 xfs_rtany_summary( 54 xfs_mount_t *mp, /* file system mount structure */ 55 xfs_trans_t *tp, /* transaction pointer */ 56 int low, /* low log2 extent size */ 57 int high, /* high log2 extent size */ 58 xfs_rtblock_t bbno, /* bitmap block number */ 59 xfs_buf_t **rbpp, /* in/out: summary block buffer */ 60 xfs_fsblock_t *rsb, /* in/out: summary block number */ 61 int *stat) /* out: any good extents here? */ 62 { 63 int error; /* error value */ 64 int log; /* loop counter, log2 of ext. size */ 65 xfs_suminfo_t sum; /* summary data */ 66 67 /* 68 * Loop over logs of extent sizes. Order is irrelevant. 69 */ 70 for (log = low; log <= high; log++) { 71 /* 72 * Get one summary datum. 73 */ 74 error = xfs_rtget_summary(mp, tp, log, bbno, rbpp, rsb, &sum); 75 if (error) { 76 return error; 77 } 78 /* 79 * If there are any, return success. 80 */ 81 if (sum) { 82 *stat = 1; 83 return 0; 84 } 85 } 86 /* 87 * Found nothing, return failure. 88 */ 89 *stat = 0; 90 return 0; 91 } 92 93 94 /* 95 * Copy and transform the summary file, given the old and new 96 * parameters in the mount structures. 97 */ 98 STATIC int /* error */ 99 xfs_rtcopy_summary( 100 xfs_mount_t *omp, /* old file system mount point */ 101 xfs_mount_t *nmp, /* new file system mount point */ 102 xfs_trans_t *tp) /* transaction pointer */ 103 { 104 xfs_rtblock_t bbno; /* bitmap block number */ 105 xfs_buf_t *bp; /* summary buffer */ 106 int error; /* error return value */ 107 int log; /* summary level number (log length) */ 108 xfs_suminfo_t sum; /* summary data */ 109 xfs_fsblock_t sumbno; /* summary block number */ 110 111 bp = NULL; 112 for (log = omp->m_rsumlevels - 1; log >= 0; log--) { 113 for (bbno = omp->m_sb.sb_rbmblocks - 1; 114 (xfs_srtblock_t)bbno >= 0; 115 bbno--) { 116 error = xfs_rtget_summary(omp, tp, log, bbno, &bp, 117 &sumbno, &sum); 118 if (error) 119 return error; 120 if (sum == 0) 121 continue; 122 error = xfs_rtmodify_summary(omp, tp, log, bbno, -sum, 123 &bp, &sumbno); 124 if (error) 125 return error; 126 error = xfs_rtmodify_summary(nmp, tp, log, bbno, sum, 127 &bp, &sumbno); 128 if (error) 129 return error; 130 ASSERT(sum > 0); 131 } 132 } 133 return 0; 134 } 135 /* 136 * Mark an extent specified by start and len allocated. 137 * Updates all the summary information as well as the bitmap. 138 */ 139 STATIC int /* error */ 140 xfs_rtallocate_range( 141 xfs_mount_t *mp, /* file system mount point */ 142 xfs_trans_t *tp, /* transaction pointer */ 143 xfs_rtblock_t start, /* start block to allocate */ 144 xfs_extlen_t len, /* length to allocate */ 145 xfs_buf_t **rbpp, /* in/out: summary block buffer */ 146 xfs_fsblock_t *rsb) /* in/out: summary block number */ 147 { 148 xfs_rtblock_t end; /* end of the allocated extent */ 149 int error; /* error value */ 150 xfs_rtblock_t postblock = 0; /* first block allocated > end */ 151 xfs_rtblock_t preblock = 0; /* first block allocated < start */ 152 153 end = start + len - 1; 154 /* 155 * Assume we're allocating out of the middle of a free extent. 156 * We need to find the beginning and end of the extent so we can 157 * properly update the summary. 158 */ 159 error = xfs_rtfind_back(mp, tp, start, 0, &preblock); 160 if (error) { 161 return error; 162 } 163 /* 164 * Find the next allocated block (end of free extent). 165 */ 166 error = xfs_rtfind_forw(mp, tp, end, mp->m_sb.sb_rextents - 1, 167 &postblock); 168 if (error) { 169 return error; 170 } 171 /* 172 * Decrement the summary information corresponding to the entire 173 * (old) free extent. 174 */ 175 error = xfs_rtmodify_summary(mp, tp, 176 XFS_RTBLOCKLOG(postblock + 1 - preblock), 177 XFS_BITTOBLOCK(mp, preblock), -1, rbpp, rsb); 178 if (error) { 179 return error; 180 } 181 /* 182 * If there are blocks not being allocated at the front of the 183 * old extent, add summary data for them to be free. 184 */ 185 if (preblock < start) { 186 error = xfs_rtmodify_summary(mp, tp, 187 XFS_RTBLOCKLOG(start - preblock), 188 XFS_BITTOBLOCK(mp, preblock), 1, rbpp, rsb); 189 if (error) { 190 return error; 191 } 192 } 193 /* 194 * If there are blocks not being allocated at the end of the 195 * old extent, add summary data for them to be free. 196 */ 197 if (postblock > end) { 198 error = xfs_rtmodify_summary(mp, tp, 199 XFS_RTBLOCKLOG(postblock - end), 200 XFS_BITTOBLOCK(mp, end + 1), 1, rbpp, rsb); 201 if (error) { 202 return error; 203 } 204 } 205 /* 206 * Modify the bitmap to mark this extent allocated. 207 */ 208 error = xfs_rtmodify_range(mp, tp, start, len, 0); 209 return error; 210 } 211 212 /* 213 * Attempt to allocate an extent minlen<=len<=maxlen starting from 214 * bitmap block bbno. If we don't get maxlen then use prod to trim 215 * the length, if given. Returns error; returns starting block in *rtblock. 216 * The lengths are all in rtextents. 217 */ 218 STATIC int /* error */ 219 xfs_rtallocate_extent_block( 220 xfs_mount_t *mp, /* file system mount point */ 221 xfs_trans_t *tp, /* transaction pointer */ 222 xfs_rtblock_t bbno, /* bitmap block number */ 223 xfs_extlen_t minlen, /* minimum length to allocate */ 224 xfs_extlen_t maxlen, /* maximum length to allocate */ 225 xfs_extlen_t *len, /* out: actual length allocated */ 226 xfs_rtblock_t *nextp, /* out: next block to try */ 227 xfs_buf_t **rbpp, /* in/out: summary block buffer */ 228 xfs_fsblock_t *rsb, /* in/out: summary block number */ 229 xfs_extlen_t prod, /* extent product factor */ 230 xfs_rtblock_t *rtblock) /* out: start block allocated */ 231 { 232 xfs_rtblock_t besti; /* best rtblock found so far */ 233 xfs_rtblock_t bestlen; /* best length found so far */ 234 xfs_rtblock_t end; /* last rtblock in chunk */ 235 int error; /* error value */ 236 xfs_rtblock_t i; /* current rtblock trying */ 237 xfs_rtblock_t next; /* next rtblock to try */ 238 int stat; /* status from internal calls */ 239 240 /* 241 * Loop over all the extents starting in this bitmap block, 242 * looking for one that's long enough. 243 */ 244 for (i = XFS_BLOCKTOBIT(mp, bbno), besti = -1, bestlen = 0, 245 end = XFS_BLOCKTOBIT(mp, bbno + 1) - 1; 246 i <= end; 247 i++) { 248 /* 249 * See if there's a free extent of maxlen starting at i. 250 * If it's not so then next will contain the first non-free. 251 */ 252 error = xfs_rtcheck_range(mp, tp, i, maxlen, 1, &next, &stat); 253 if (error) { 254 return error; 255 } 256 if (stat) { 257 /* 258 * i for maxlen is all free, allocate and return that. 259 */ 260 error = xfs_rtallocate_range(mp, tp, i, maxlen, rbpp, 261 rsb); 262 if (error) { 263 return error; 264 } 265 *len = maxlen; 266 *rtblock = i; 267 return 0; 268 } 269 /* 270 * In the case where we have a variable-sized allocation 271 * request, figure out how big this free piece is, 272 * and if it's big enough for the minimum, and the best 273 * so far, remember it. 274 */ 275 if (minlen < maxlen) { 276 xfs_rtblock_t thislen; /* this extent size */ 277 278 thislen = next - i; 279 if (thislen >= minlen && thislen > bestlen) { 280 besti = i; 281 bestlen = thislen; 282 } 283 } 284 /* 285 * If not done yet, find the start of the next free space. 286 */ 287 if (next < end) { 288 error = xfs_rtfind_forw(mp, tp, next, end, &i); 289 if (error) { 290 return error; 291 } 292 } else 293 break; 294 } 295 /* 296 * Searched the whole thing & didn't find a maxlen free extent. 297 */ 298 if (minlen < maxlen && besti != -1) { 299 xfs_extlen_t p; /* amount to trim length by */ 300 301 /* 302 * If size should be a multiple of prod, make that so. 303 */ 304 if (prod > 1) { 305 div_u64_rem(bestlen, prod, &p); 306 if (p) 307 bestlen -= p; 308 } 309 310 /* 311 * Allocate besti for bestlen & return that. 312 */ 313 error = xfs_rtallocate_range(mp, tp, besti, bestlen, rbpp, rsb); 314 if (error) { 315 return error; 316 } 317 *len = bestlen; 318 *rtblock = besti; 319 return 0; 320 } 321 /* 322 * Allocation failed. Set *nextp to the next block to try. 323 */ 324 *nextp = next; 325 *rtblock = NULLRTBLOCK; 326 return 0; 327 } 328 329 /* 330 * Allocate an extent of length minlen<=len<=maxlen, starting at block 331 * bno. If we don't get maxlen then use prod to trim the length, if given. 332 * Returns error; returns starting block in *rtblock. 333 * The lengths are all in rtextents. 334 */ 335 STATIC int /* error */ 336 xfs_rtallocate_extent_exact( 337 xfs_mount_t *mp, /* file system mount point */ 338 xfs_trans_t *tp, /* transaction pointer */ 339 xfs_rtblock_t bno, /* starting block number to allocate */ 340 xfs_extlen_t minlen, /* minimum length to allocate */ 341 xfs_extlen_t maxlen, /* maximum length to allocate */ 342 xfs_extlen_t *len, /* out: actual length allocated */ 343 xfs_buf_t **rbpp, /* in/out: summary block buffer */ 344 xfs_fsblock_t *rsb, /* in/out: summary block number */ 345 xfs_extlen_t prod, /* extent product factor */ 346 xfs_rtblock_t *rtblock) /* out: start block allocated */ 347 { 348 int error; /* error value */ 349 xfs_extlen_t i; /* extent length trimmed due to prod */ 350 int isfree; /* extent is free */ 351 xfs_rtblock_t next; /* next block to try (dummy) */ 352 353 ASSERT(minlen % prod == 0 && maxlen % prod == 0); 354 /* 355 * Check if the range in question (for maxlen) is free. 356 */ 357 error = xfs_rtcheck_range(mp, tp, bno, maxlen, 1, &next, &isfree); 358 if (error) { 359 return error; 360 } 361 if (isfree) { 362 /* 363 * If it is, allocate it and return success. 364 */ 365 error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb); 366 if (error) { 367 return error; 368 } 369 *len = maxlen; 370 *rtblock = bno; 371 return 0; 372 } 373 /* 374 * If not, allocate what there is, if it's at least minlen. 375 */ 376 maxlen = next - bno; 377 if (maxlen < minlen) { 378 /* 379 * Failed, return failure status. 380 */ 381 *rtblock = NULLRTBLOCK; 382 return 0; 383 } 384 /* 385 * Trim off tail of extent, if prod is specified. 386 */ 387 if (prod > 1 && (i = maxlen % prod)) { 388 maxlen -= i; 389 if (maxlen < minlen) { 390 /* 391 * Now we can't do it, return failure status. 392 */ 393 *rtblock = NULLRTBLOCK; 394 return 0; 395 } 396 } 397 /* 398 * Allocate what we can and return it. 399 */ 400 error = xfs_rtallocate_range(mp, tp, bno, maxlen, rbpp, rsb); 401 if (error) { 402 return error; 403 } 404 *len = maxlen; 405 *rtblock = bno; 406 return 0; 407 } 408 409 /* 410 * Allocate an extent of length minlen<=len<=maxlen, starting as near 411 * to bno as possible. If we don't get maxlen then use prod to trim 412 * the length, if given. The lengths are all in rtextents. 413 */ 414 STATIC int /* error */ 415 xfs_rtallocate_extent_near( 416 xfs_mount_t *mp, /* file system mount point */ 417 xfs_trans_t *tp, /* transaction pointer */ 418 xfs_rtblock_t bno, /* starting block number to allocate */ 419 xfs_extlen_t minlen, /* minimum length to allocate */ 420 xfs_extlen_t maxlen, /* maximum length to allocate */ 421 xfs_extlen_t *len, /* out: actual length allocated */ 422 xfs_buf_t **rbpp, /* in/out: summary block buffer */ 423 xfs_fsblock_t *rsb, /* in/out: summary block number */ 424 xfs_extlen_t prod, /* extent product factor */ 425 xfs_rtblock_t *rtblock) /* out: start block allocated */ 426 { 427 int any; /* any useful extents from summary */ 428 xfs_rtblock_t bbno; /* bitmap block number */ 429 int error; /* error value */ 430 int i; /* bitmap block offset (loop control) */ 431 int j; /* secondary loop control */ 432 int log2len; /* log2 of minlen */ 433 xfs_rtblock_t n; /* next block to try */ 434 xfs_rtblock_t r; /* result block */ 435 436 ASSERT(minlen % prod == 0 && maxlen % prod == 0); 437 /* 438 * If the block number given is off the end, silently set it to 439 * the last block. 440 */ 441 if (bno >= mp->m_sb.sb_rextents) 442 bno = mp->m_sb.sb_rextents - 1; 443 /* 444 * Try the exact allocation first. 445 */ 446 error = xfs_rtallocate_extent_exact(mp, tp, bno, minlen, maxlen, len, 447 rbpp, rsb, prod, &r); 448 if (error) { 449 return error; 450 } 451 /* 452 * If the exact allocation worked, return that. 453 */ 454 if (r != NULLRTBLOCK) { 455 *rtblock = r; 456 return 0; 457 } 458 bbno = XFS_BITTOBLOCK(mp, bno); 459 i = 0; 460 ASSERT(minlen != 0); 461 log2len = xfs_highbit32(minlen); 462 /* 463 * Loop over all bitmap blocks (bbno + i is current block). 464 */ 465 for (;;) { 466 /* 467 * Get summary information of extents of all useful levels 468 * starting in this bitmap block. 469 */ 470 error = xfs_rtany_summary(mp, tp, log2len, mp->m_rsumlevels - 1, 471 bbno + i, rbpp, rsb, &any); 472 if (error) { 473 return error; 474 } 475 /* 476 * If there are any useful extents starting here, try 477 * allocating one. 478 */ 479 if (any) { 480 /* 481 * On the positive side of the starting location. 482 */ 483 if (i >= 0) { 484 /* 485 * Try to allocate an extent starting in 486 * this block. 487 */ 488 error = xfs_rtallocate_extent_block(mp, tp, 489 bbno + i, minlen, maxlen, len, &n, rbpp, 490 rsb, prod, &r); 491 if (error) { 492 return error; 493 } 494 /* 495 * If it worked, return it. 496 */ 497 if (r != NULLRTBLOCK) { 498 *rtblock = r; 499 return 0; 500 } 501 } 502 /* 503 * On the negative side of the starting location. 504 */ 505 else { /* i < 0 */ 506 /* 507 * Loop backwards through the bitmap blocks from 508 * the starting point-1 up to where we are now. 509 * There should be an extent which ends in this 510 * bitmap block and is long enough. 511 */ 512 for (j = -1; j > i; j--) { 513 /* 514 * Grab the summary information for 515 * this bitmap block. 516 */ 517 error = xfs_rtany_summary(mp, tp, 518 log2len, mp->m_rsumlevels - 1, 519 bbno + j, rbpp, rsb, &any); 520 if (error) { 521 return error; 522 } 523 /* 524 * If there's no extent given in the 525 * summary that means the extent we 526 * found must carry over from an 527 * earlier block. If there is an 528 * extent given, we've already tried 529 * that allocation, don't do it again. 530 */ 531 if (any) 532 continue; 533 error = xfs_rtallocate_extent_block(mp, 534 tp, bbno + j, minlen, maxlen, 535 len, &n, rbpp, rsb, prod, &r); 536 if (error) { 537 return error; 538 } 539 /* 540 * If it works, return the extent. 541 */ 542 if (r != NULLRTBLOCK) { 543 *rtblock = r; 544 return 0; 545 } 546 } 547 /* 548 * There weren't intervening bitmap blocks 549 * with a long enough extent, or the 550 * allocation didn't work for some reason 551 * (i.e. it's a little * too short). 552 * Try to allocate from the summary block 553 * that we found. 554 */ 555 error = xfs_rtallocate_extent_block(mp, tp, 556 bbno + i, minlen, maxlen, len, &n, rbpp, 557 rsb, prod, &r); 558 if (error) { 559 return error; 560 } 561 /* 562 * If it works, return the extent. 563 */ 564 if (r != NULLRTBLOCK) { 565 *rtblock = r; 566 return 0; 567 } 568 } 569 } 570 /* 571 * Loop control. If we were on the positive side, and there's 572 * still more blocks on the negative side, go there. 573 */ 574 if (i > 0 && (int)bbno - i >= 0) 575 i = -i; 576 /* 577 * If positive, and no more negative, but there are more 578 * positive, go there. 579 */ 580 else if (i > 0 && (int)bbno + i < mp->m_sb.sb_rbmblocks - 1) 581 i++; 582 /* 583 * If negative or 0 (just started), and there are positive 584 * blocks to go, go there. The 0 case moves to block 1. 585 */ 586 else if (i <= 0 && (int)bbno - i < mp->m_sb.sb_rbmblocks - 1) 587 i = 1 - i; 588 /* 589 * If negative or 0 and there are more negative blocks, 590 * go there. 591 */ 592 else if (i <= 0 && (int)bbno + i > 0) 593 i--; 594 /* 595 * Must be done. Return failure. 596 */ 597 else 598 break; 599 } 600 *rtblock = NULLRTBLOCK; 601 return 0; 602 } 603 604 /* 605 * Allocate an extent of length minlen<=len<=maxlen, with no position 606 * specified. If we don't get maxlen then use prod to trim 607 * the length, if given. The lengths are all in rtextents. 608 */ 609 STATIC int /* error */ 610 xfs_rtallocate_extent_size( 611 xfs_mount_t *mp, /* file system mount point */ 612 xfs_trans_t *tp, /* transaction pointer */ 613 xfs_extlen_t minlen, /* minimum length to allocate */ 614 xfs_extlen_t maxlen, /* maximum length to allocate */ 615 xfs_extlen_t *len, /* out: actual length allocated */ 616 xfs_buf_t **rbpp, /* in/out: summary block buffer */ 617 xfs_fsblock_t *rsb, /* in/out: summary block number */ 618 xfs_extlen_t prod, /* extent product factor */ 619 xfs_rtblock_t *rtblock) /* out: start block allocated */ 620 { 621 int error; /* error value */ 622 int i; /* bitmap block number */ 623 int l; /* level number (loop control) */ 624 xfs_rtblock_t n; /* next block to be tried */ 625 xfs_rtblock_t r; /* result block number */ 626 xfs_suminfo_t sum; /* summary information for extents */ 627 628 ASSERT(minlen % prod == 0 && maxlen % prod == 0); 629 ASSERT(maxlen != 0); 630 631 /* 632 * Loop over all the levels starting with maxlen. 633 * At each level, look at all the bitmap blocks, to see if there 634 * are extents starting there that are long enough (>= maxlen). 635 * Note, only on the initial level can the allocation fail if 636 * the summary says there's an extent. 637 */ 638 for (l = xfs_highbit32(maxlen); l < mp->m_rsumlevels; l++) { 639 /* 640 * Loop over all the bitmap blocks. 641 */ 642 for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) { 643 /* 644 * Get the summary for this level/block. 645 */ 646 error = xfs_rtget_summary(mp, tp, l, i, rbpp, rsb, 647 &sum); 648 if (error) { 649 return error; 650 } 651 /* 652 * Nothing there, on to the next block. 653 */ 654 if (!sum) 655 continue; 656 /* 657 * Try allocating the extent. 658 */ 659 error = xfs_rtallocate_extent_block(mp, tp, i, maxlen, 660 maxlen, len, &n, rbpp, rsb, prod, &r); 661 if (error) { 662 return error; 663 } 664 /* 665 * If it worked, return that. 666 */ 667 if (r != NULLRTBLOCK) { 668 *rtblock = r; 669 return 0; 670 } 671 /* 672 * If the "next block to try" returned from the 673 * allocator is beyond the next bitmap block, 674 * skip to that bitmap block. 675 */ 676 if (XFS_BITTOBLOCK(mp, n) > i + 1) 677 i = XFS_BITTOBLOCK(mp, n) - 1; 678 } 679 } 680 /* 681 * Didn't find any maxlen blocks. Try smaller ones, unless 682 * we're asking for a fixed size extent. 683 */ 684 if (minlen > --maxlen) { 685 *rtblock = NULLRTBLOCK; 686 return 0; 687 } 688 ASSERT(minlen != 0); 689 ASSERT(maxlen != 0); 690 691 /* 692 * Loop over sizes, from maxlen down to minlen. 693 * This time, when we do the allocations, allow smaller ones 694 * to succeed. 695 */ 696 for (l = xfs_highbit32(maxlen); l >= xfs_highbit32(minlen); l--) { 697 /* 698 * Loop over all the bitmap blocks, try an allocation 699 * starting in that block. 700 */ 701 for (i = 0; i < mp->m_sb.sb_rbmblocks; i++) { 702 /* 703 * Get the summary information for this level/block. 704 */ 705 error = xfs_rtget_summary(mp, tp, l, i, rbpp, rsb, 706 &sum); 707 if (error) { 708 return error; 709 } 710 /* 711 * If nothing there, go on to next. 712 */ 713 if (!sum) 714 continue; 715 /* 716 * Try the allocation. Make sure the specified 717 * minlen/maxlen are in the possible range for 718 * this summary level. 719 */ 720 error = xfs_rtallocate_extent_block(mp, tp, i, 721 XFS_RTMAX(minlen, 1 << l), 722 XFS_RTMIN(maxlen, (1 << (l + 1)) - 1), 723 len, &n, rbpp, rsb, prod, &r); 724 if (error) { 725 return error; 726 } 727 /* 728 * If it worked, return that extent. 729 */ 730 if (r != NULLRTBLOCK) { 731 *rtblock = r; 732 return 0; 733 } 734 /* 735 * If the "next block to try" returned from the 736 * allocator is beyond the next bitmap block, 737 * skip to that bitmap block. 738 */ 739 if (XFS_BITTOBLOCK(mp, n) > i + 1) 740 i = XFS_BITTOBLOCK(mp, n) - 1; 741 } 742 } 743 /* 744 * Got nothing, return failure. 745 */ 746 *rtblock = NULLRTBLOCK; 747 return 0; 748 } 749 750 /* 751 * Allocate space to the bitmap or summary file, and zero it, for growfs. 752 */ 753 STATIC int 754 xfs_growfs_rt_alloc( 755 struct xfs_mount *mp, /* file system mount point */ 756 xfs_extlen_t oblocks, /* old count of blocks */ 757 xfs_extlen_t nblocks, /* new count of blocks */ 758 struct xfs_inode *ip) /* inode (bitmap/summary) */ 759 { 760 xfs_fileoff_t bno; /* block number in file */ 761 struct xfs_buf *bp; /* temporary buffer for zeroing */ 762 xfs_daddr_t d; /* disk block address */ 763 int error; /* error return value */ 764 xfs_fsblock_t firstblock;/* first block allocated in xaction */ 765 struct xfs_defer_ops dfops; /* list of freed blocks */ 766 xfs_fsblock_t fsbno; /* filesystem block for bno */ 767 struct xfs_bmbt_irec map; /* block map output */ 768 int nmap; /* number of block maps */ 769 int resblks; /* space reservation */ 770 struct xfs_trans *tp; 771 772 /* 773 * Allocate space to the file, as necessary. 774 */ 775 while (oblocks < nblocks) { 776 resblks = XFS_GROWFSRT_SPACE_RES(mp, nblocks - oblocks); 777 /* 778 * Reserve space & log for one extent added to the file. 779 */ 780 error = xfs_trans_alloc(mp, &M_RES(mp)->tr_growrtalloc, resblks, 781 0, 0, &tp); 782 if (error) 783 return error; 784 /* 785 * Lock the inode. 786 */ 787 xfs_ilock(ip, XFS_ILOCK_EXCL); 788 xfs_trans_ijoin(tp, ip, XFS_ILOCK_EXCL); 789 790 xfs_defer_init(&dfops, &firstblock); 791 /* 792 * Allocate blocks to the bitmap file. 793 */ 794 nmap = 1; 795 error = xfs_bmapi_write(tp, ip, oblocks, nblocks - oblocks, 796 XFS_BMAPI_METADATA, &firstblock, 797 resblks, &map, &nmap, &dfops); 798 if (!error && nmap < 1) 799 error = -ENOSPC; 800 if (error) 801 goto out_bmap_cancel; 802 /* 803 * Free any blocks freed up in the transaction, then commit. 804 */ 805 error = xfs_defer_finish(&tp, &dfops); 806 if (error) 807 goto out_bmap_cancel; 808 error = xfs_trans_commit(tp); 809 if (error) 810 return error; 811 /* 812 * Now we need to clear the allocated blocks. 813 * Do this one block per transaction, to keep it simple. 814 */ 815 for (bno = map.br_startoff, fsbno = map.br_startblock; 816 bno < map.br_startoff + map.br_blockcount; 817 bno++, fsbno++) { 818 /* 819 * Reserve log for one block zeroing. 820 */ 821 error = xfs_trans_alloc(mp, &M_RES(mp)->tr_growrtzero, 822 0, 0, 0, &tp); 823 if (error) 824 return error; 825 /* 826 * Lock the bitmap inode. 827 */ 828 xfs_ilock(ip, XFS_ILOCK_EXCL); 829 xfs_trans_ijoin(tp, ip, XFS_ILOCK_EXCL); 830 /* 831 * Get a buffer for the block. 832 */ 833 d = XFS_FSB_TO_DADDR(mp, fsbno); 834 bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, 835 mp->m_bsize, 0); 836 if (bp == NULL) { 837 error = -EIO; 838 goto out_trans_cancel; 839 } 840 memset(bp->b_addr, 0, mp->m_sb.sb_blocksize); 841 xfs_trans_log_buf(tp, bp, 0, mp->m_sb.sb_blocksize - 1); 842 /* 843 * Commit the transaction. 844 */ 845 error = xfs_trans_commit(tp); 846 if (error) 847 return error; 848 } 849 /* 850 * Go on to the next extent, if any. 851 */ 852 oblocks = map.br_startoff + map.br_blockcount; 853 } 854 855 return 0; 856 857 out_bmap_cancel: 858 xfs_defer_cancel(&dfops); 859 out_trans_cancel: 860 xfs_trans_cancel(tp); 861 return error; 862 } 863 864 /* 865 * Visible (exported) functions. 866 */ 867 868 /* 869 * Grow the realtime area of the filesystem. 870 */ 871 int 872 xfs_growfs_rt( 873 xfs_mount_t *mp, /* mount point for filesystem */ 874 xfs_growfs_rt_t *in) /* growfs rt input struct */ 875 { 876 xfs_rtblock_t bmbno; /* bitmap block number */ 877 xfs_buf_t *bp; /* temporary buffer */ 878 int error; /* error return value */ 879 xfs_mount_t *nmp; /* new (fake) mount structure */ 880 xfs_rfsblock_t nrblocks; /* new number of realtime blocks */ 881 xfs_extlen_t nrbmblocks; /* new number of rt bitmap blocks */ 882 xfs_rtblock_t nrextents; /* new number of realtime extents */ 883 uint8_t nrextslog; /* new log2 of sb_rextents */ 884 xfs_extlen_t nrsumblocks; /* new number of summary blocks */ 885 uint nrsumlevels; /* new rt summary levels */ 886 uint nrsumsize; /* new size of rt summary, bytes */ 887 xfs_sb_t *nsbp; /* new superblock */ 888 xfs_extlen_t rbmblocks; /* current number of rt bitmap blocks */ 889 xfs_extlen_t rsumblocks; /* current number of rt summary blks */ 890 xfs_sb_t *sbp; /* old superblock */ 891 xfs_fsblock_t sumbno; /* summary block number */ 892 893 sbp = &mp->m_sb; 894 /* 895 * Initial error checking. 896 */ 897 if (!capable(CAP_SYS_ADMIN)) 898 return -EPERM; 899 if (mp->m_rtdev_targp == NULL || mp->m_rbmip == NULL || 900 (nrblocks = in->newblocks) <= sbp->sb_rblocks || 901 (sbp->sb_rblocks && (in->extsize != sbp->sb_rextsize))) 902 return -EINVAL; 903 if ((error = xfs_sb_validate_fsb_count(sbp, nrblocks))) 904 return error; 905 /* 906 * Read in the last block of the device, make sure it exists. 907 */ 908 error = xfs_buf_read_uncached(mp->m_rtdev_targp, 909 XFS_FSB_TO_BB(mp, nrblocks - 1), 910 XFS_FSB_TO_BB(mp, 1), 0, &bp, NULL); 911 if (error) 912 return error; 913 xfs_buf_relse(bp); 914 915 /* 916 * Calculate new parameters. These are the final values to be reached. 917 */ 918 nrextents = nrblocks; 919 do_div(nrextents, in->extsize); 920 nrbmblocks = howmany_64(nrextents, NBBY * sbp->sb_blocksize); 921 nrextslog = xfs_highbit32(nrextents); 922 nrsumlevels = nrextslog + 1; 923 nrsumsize = (uint)sizeof(xfs_suminfo_t) * nrsumlevels * nrbmblocks; 924 nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize); 925 nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks); 926 /* 927 * New summary size can't be more than half the size of 928 * the log. This prevents us from getting a log overflow, 929 * since we'll log basically the whole summary file at once. 930 */ 931 if (nrsumblocks > (mp->m_sb.sb_logblocks >> 1)) 932 return -EINVAL; 933 /* 934 * Get the old block counts for bitmap and summary inodes. 935 * These can't change since other growfs callers are locked out. 936 */ 937 rbmblocks = XFS_B_TO_FSB(mp, mp->m_rbmip->i_d.di_size); 938 rsumblocks = XFS_B_TO_FSB(mp, mp->m_rsumip->i_d.di_size); 939 /* 940 * Allocate space to the bitmap and summary files, as necessary. 941 */ 942 error = xfs_growfs_rt_alloc(mp, rbmblocks, nrbmblocks, mp->m_rbmip); 943 if (error) 944 return error; 945 error = xfs_growfs_rt_alloc(mp, rsumblocks, nrsumblocks, mp->m_rsumip); 946 if (error) 947 return error; 948 /* 949 * Allocate a new (fake) mount/sb. 950 */ 951 nmp = kmem_alloc(sizeof(*nmp), KM_SLEEP); 952 /* 953 * Loop over the bitmap blocks. 954 * We will do everything one bitmap block at a time. 955 * Skip the current block if it is exactly full. 956 * This also deals with the case where there were no rtextents before. 957 */ 958 for (bmbno = sbp->sb_rbmblocks - 959 ((sbp->sb_rextents & ((1 << mp->m_blkbit_log) - 1)) != 0); 960 bmbno < nrbmblocks; 961 bmbno++) { 962 xfs_trans_t *tp; 963 964 *nmp = *mp; 965 nsbp = &nmp->m_sb; 966 /* 967 * Calculate new sb and mount fields for this round. 968 */ 969 nsbp->sb_rextsize = in->extsize; 970 nsbp->sb_rbmblocks = bmbno + 1; 971 nsbp->sb_rblocks = 972 XFS_RTMIN(nrblocks, 973 nsbp->sb_rbmblocks * NBBY * 974 nsbp->sb_blocksize * nsbp->sb_rextsize); 975 nsbp->sb_rextents = nsbp->sb_rblocks; 976 do_div(nsbp->sb_rextents, nsbp->sb_rextsize); 977 ASSERT(nsbp->sb_rextents != 0); 978 nsbp->sb_rextslog = xfs_highbit32(nsbp->sb_rextents); 979 nrsumlevels = nmp->m_rsumlevels = nsbp->sb_rextslog + 1; 980 nrsumsize = 981 (uint)sizeof(xfs_suminfo_t) * nrsumlevels * 982 nsbp->sb_rbmblocks; 983 nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize); 984 nmp->m_rsumsize = nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks); 985 /* 986 * Start a transaction, get the log reservation. 987 */ 988 error = xfs_trans_alloc(mp, &M_RES(mp)->tr_growrtfree, 0, 0, 0, 989 &tp); 990 if (error) 991 break; 992 /* 993 * Lock out other callers by grabbing the bitmap inode lock. 994 */ 995 xfs_ilock(mp->m_rbmip, XFS_ILOCK_EXCL); 996 xfs_trans_ijoin(tp, mp->m_rbmip, XFS_ILOCK_EXCL); 997 /* 998 * Update the bitmap inode's size. 999 */ 1000 mp->m_rbmip->i_d.di_size = 1001 nsbp->sb_rbmblocks * nsbp->sb_blocksize; 1002 xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE); 1003 /* 1004 * Get the summary inode into the transaction. 1005 */ 1006 xfs_ilock(mp->m_rsumip, XFS_ILOCK_EXCL); 1007 xfs_trans_ijoin(tp, mp->m_rsumip, XFS_ILOCK_EXCL); 1008 /* 1009 * Update the summary inode's size. 1010 */ 1011 mp->m_rsumip->i_d.di_size = nmp->m_rsumsize; 1012 xfs_trans_log_inode(tp, mp->m_rsumip, XFS_ILOG_CORE); 1013 /* 1014 * Copy summary data from old to new sizes. 1015 * Do this when the real size (not block-aligned) changes. 1016 */ 1017 if (sbp->sb_rbmblocks != nsbp->sb_rbmblocks || 1018 mp->m_rsumlevels != nmp->m_rsumlevels) { 1019 error = xfs_rtcopy_summary(mp, nmp, tp); 1020 if (error) 1021 goto error_cancel; 1022 } 1023 /* 1024 * Update superblock fields. 1025 */ 1026 if (nsbp->sb_rextsize != sbp->sb_rextsize) 1027 xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSIZE, 1028 nsbp->sb_rextsize - sbp->sb_rextsize); 1029 if (nsbp->sb_rbmblocks != sbp->sb_rbmblocks) 1030 xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBMBLOCKS, 1031 nsbp->sb_rbmblocks - sbp->sb_rbmblocks); 1032 if (nsbp->sb_rblocks != sbp->sb_rblocks) 1033 xfs_trans_mod_sb(tp, XFS_TRANS_SB_RBLOCKS, 1034 nsbp->sb_rblocks - sbp->sb_rblocks); 1035 if (nsbp->sb_rextents != sbp->sb_rextents) 1036 xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTENTS, 1037 nsbp->sb_rextents - sbp->sb_rextents); 1038 if (nsbp->sb_rextslog != sbp->sb_rextslog) 1039 xfs_trans_mod_sb(tp, XFS_TRANS_SB_REXTSLOG, 1040 nsbp->sb_rextslog - sbp->sb_rextslog); 1041 /* 1042 * Free new extent. 1043 */ 1044 bp = NULL; 1045 error = xfs_rtfree_range(nmp, tp, sbp->sb_rextents, 1046 nsbp->sb_rextents - sbp->sb_rextents, &bp, &sumbno); 1047 if (error) { 1048 error_cancel: 1049 xfs_trans_cancel(tp); 1050 break; 1051 } 1052 /* 1053 * Mark more blocks free in the superblock. 1054 */ 1055 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, 1056 nsbp->sb_rextents - sbp->sb_rextents); 1057 /* 1058 * Update mp values into the real mp structure. 1059 */ 1060 mp->m_rsumlevels = nrsumlevels; 1061 mp->m_rsumsize = nrsumsize; 1062 1063 error = xfs_trans_commit(tp); 1064 if (error) 1065 break; 1066 } 1067 1068 /* 1069 * Free the fake mp structure. 1070 */ 1071 kmem_free(nmp); 1072 1073 return error; 1074 } 1075 1076 /* 1077 * Allocate an extent in the realtime subvolume, with the usual allocation 1078 * parameters. The length units are all in realtime extents, as is the 1079 * result block number. 1080 */ 1081 int /* error */ 1082 xfs_rtallocate_extent( 1083 xfs_trans_t *tp, /* transaction pointer */ 1084 xfs_rtblock_t bno, /* starting block number to allocate */ 1085 xfs_extlen_t minlen, /* minimum length to allocate */ 1086 xfs_extlen_t maxlen, /* maximum length to allocate */ 1087 xfs_extlen_t *len, /* out: actual length allocated */ 1088 int wasdel, /* was a delayed allocation extent */ 1089 xfs_extlen_t prod, /* extent product factor */ 1090 xfs_rtblock_t *rtblock) /* out: start block allocated */ 1091 { 1092 xfs_mount_t *mp = tp->t_mountp; 1093 int error; /* error value */ 1094 xfs_rtblock_t r; /* result allocated block */ 1095 xfs_fsblock_t sb; /* summary file block number */ 1096 xfs_buf_t *sumbp; /* summary file block buffer */ 1097 1098 ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL)); 1099 ASSERT(minlen > 0 && minlen <= maxlen); 1100 1101 /* 1102 * If prod is set then figure out what to do to minlen and maxlen. 1103 */ 1104 if (prod > 1) { 1105 xfs_extlen_t i; 1106 1107 if ((i = maxlen % prod)) 1108 maxlen -= i; 1109 if ((i = minlen % prod)) 1110 minlen += prod - i; 1111 if (maxlen < minlen) { 1112 *rtblock = NULLRTBLOCK; 1113 return 0; 1114 } 1115 } 1116 1117 retry: 1118 sumbp = NULL; 1119 if (bno == 0) { 1120 error = xfs_rtallocate_extent_size(mp, tp, minlen, maxlen, len, 1121 &sumbp, &sb, prod, &r); 1122 } else { 1123 error = xfs_rtallocate_extent_near(mp, tp, bno, minlen, maxlen, 1124 len, &sumbp, &sb, prod, &r); 1125 } 1126 1127 if (error) 1128 return error; 1129 1130 /* 1131 * If it worked, update the superblock. 1132 */ 1133 if (r != NULLRTBLOCK) { 1134 long slen = (long)*len; 1135 1136 ASSERT(*len >= minlen && *len <= maxlen); 1137 if (wasdel) 1138 xfs_trans_mod_sb(tp, XFS_TRANS_SB_RES_FREXTENTS, -slen); 1139 else 1140 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FREXTENTS, -slen); 1141 } else if (prod > 1) { 1142 prod = 1; 1143 goto retry; 1144 } 1145 1146 *rtblock = r; 1147 return 0; 1148 } 1149 1150 /* 1151 * Initialize realtime fields in the mount structure. 1152 */ 1153 int /* error */ 1154 xfs_rtmount_init( 1155 struct xfs_mount *mp) /* file system mount structure */ 1156 { 1157 struct xfs_buf *bp; /* buffer for last block of subvolume */ 1158 struct xfs_sb *sbp; /* filesystem superblock copy in mount */ 1159 xfs_daddr_t d; /* address of last block of subvolume */ 1160 int error; 1161 1162 sbp = &mp->m_sb; 1163 if (sbp->sb_rblocks == 0) 1164 return 0; 1165 if (mp->m_rtdev_targp == NULL) { 1166 xfs_warn(mp, 1167 "Filesystem has a realtime volume, use rtdev=device option"); 1168 return -ENODEV; 1169 } 1170 mp->m_rsumlevels = sbp->sb_rextslog + 1; 1171 mp->m_rsumsize = 1172 (uint)sizeof(xfs_suminfo_t) * mp->m_rsumlevels * 1173 sbp->sb_rbmblocks; 1174 mp->m_rsumsize = roundup(mp->m_rsumsize, sbp->sb_blocksize); 1175 mp->m_rbmip = mp->m_rsumip = NULL; 1176 /* 1177 * Check that the realtime section is an ok size. 1178 */ 1179 d = (xfs_daddr_t)XFS_FSB_TO_BB(mp, mp->m_sb.sb_rblocks); 1180 if (XFS_BB_TO_FSB(mp, d) != mp->m_sb.sb_rblocks) { 1181 xfs_warn(mp, "realtime mount -- %llu != %llu", 1182 (unsigned long long) XFS_BB_TO_FSB(mp, d), 1183 (unsigned long long) mp->m_sb.sb_rblocks); 1184 return -EFBIG; 1185 } 1186 error = xfs_buf_read_uncached(mp->m_rtdev_targp, 1187 d - XFS_FSB_TO_BB(mp, 1), 1188 XFS_FSB_TO_BB(mp, 1), 0, &bp, NULL); 1189 if (error) { 1190 xfs_warn(mp, "realtime device size check failed"); 1191 return error; 1192 } 1193 xfs_buf_relse(bp); 1194 return 0; 1195 } 1196 1197 /* 1198 * Get the bitmap and summary inodes into the mount structure 1199 * at mount time. 1200 */ 1201 int /* error */ 1202 xfs_rtmount_inodes( 1203 xfs_mount_t *mp) /* file system mount structure */ 1204 { 1205 int error; /* error return value */ 1206 xfs_sb_t *sbp; 1207 1208 sbp = &mp->m_sb; 1209 if (sbp->sb_rbmino == NULLFSINO) 1210 return 0; 1211 error = xfs_iget(mp, NULL, sbp->sb_rbmino, 0, 0, &mp->m_rbmip); 1212 if (error) 1213 return error; 1214 ASSERT(mp->m_rbmip != NULL); 1215 ASSERT(sbp->sb_rsumino != NULLFSINO); 1216 error = xfs_iget(mp, NULL, sbp->sb_rsumino, 0, 0, &mp->m_rsumip); 1217 if (error) { 1218 IRELE(mp->m_rbmip); 1219 return error; 1220 } 1221 ASSERT(mp->m_rsumip != NULL); 1222 return 0; 1223 } 1224 1225 void 1226 xfs_rtunmount_inodes( 1227 struct xfs_mount *mp) 1228 { 1229 if (mp->m_rbmip) 1230 IRELE(mp->m_rbmip); 1231 if (mp->m_rsumip) 1232 IRELE(mp->m_rsumip); 1233 } 1234 1235 /* 1236 * Pick an extent for allocation at the start of a new realtime file. 1237 * Use the sequence number stored in the atime field of the bitmap inode. 1238 * Translate this to a fraction of the rtextents, and return the product 1239 * of rtextents and the fraction. 1240 * The fraction sequence is 0, 1/2, 1/4, 3/4, 1/8, ..., 7/8, 1/16, ... 1241 */ 1242 int /* error */ 1243 xfs_rtpick_extent( 1244 xfs_mount_t *mp, /* file system mount point */ 1245 xfs_trans_t *tp, /* transaction pointer */ 1246 xfs_extlen_t len, /* allocation length (rtextents) */ 1247 xfs_rtblock_t *pick) /* result rt extent */ 1248 { 1249 xfs_rtblock_t b; /* result block */ 1250 int log2; /* log of sequence number */ 1251 uint64_t resid; /* residual after log removed */ 1252 uint64_t seq; /* sequence number of file creation */ 1253 uint64_t *seqp; /* pointer to seqno in inode */ 1254 1255 ASSERT(xfs_isilocked(mp->m_rbmip, XFS_ILOCK_EXCL)); 1256 1257 seqp = (uint64_t *)&VFS_I(mp->m_rbmip)->i_atime; 1258 if (!(mp->m_rbmip->i_d.di_flags & XFS_DIFLAG_NEWRTBM)) { 1259 mp->m_rbmip->i_d.di_flags |= XFS_DIFLAG_NEWRTBM; 1260 *seqp = 0; 1261 } 1262 seq = *seqp; 1263 if ((log2 = xfs_highbit64(seq)) == -1) 1264 b = 0; 1265 else { 1266 resid = seq - (1ULL << log2); 1267 b = (mp->m_sb.sb_rextents * ((resid << 1) + 1ULL)) >> 1268 (log2 + 1); 1269 if (b >= mp->m_sb.sb_rextents) 1270 div64_u64_rem(b, mp->m_sb.sb_rextents, &b); 1271 if (b + len > mp->m_sb.sb_rextents) 1272 b = mp->m_sb.sb_rextents - len; 1273 } 1274 *seqp = seq + 1; 1275 xfs_trans_log_inode(tp, mp->m_rbmip, XFS_ILOG_CORE); 1276 *pick = b; 1277 return 0; 1278 } 1279