1/* 2 * Copyright (c) 1999-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23/* 24 File: SAllocate.c 25 26 Contains: Routines for accessing and modifying the volume bitmap. 27 28 Version: HFS Plus 1.0 29 30 Copyright: � 1996-1999 by Apple Computer, Inc., all rights reserved. 31 32*/ 33 34/* 35Public routines: 36 BlockAllocate 37 Allocate space on a volume. Can allocate space contiguously. 38 If not contiguous, then allocation may be less than what was 39 asked for. Returns the starting block number, and number of 40 blocks. (Will only do a single extent???) 41 BlockDeallocate 42 Deallocate a contiguous run of allocation blocks. 43 44Internal routines: 45 BlockAllocateAny 46 Find and allocate a contiguous range of blocks up to a given size. The 47 first range of contiguous free blocks found are allocated, even if there 48 are fewer blocks than requested (and even if a contiguous range of blocks 49 of the given size exists elsewhere). 50 51 BlockMarkFree 52 Mark a contiguous range of blocks as free. The corresponding 53 bits in the volume bitmap will be cleared. 54 BlockMarkAllocated 55 Mark a contiguous range of blocks as allocated. The cor- 56 responding bits in the volume bitmap are set. Also tests to see 57 if any of the blocks were previously unallocated. 58 FindContiguous 59 Find a contiguous range of blocks of a given size. The caller 60 specifies where to begin the search (by block number). The 61 block number of the first block in the range is returned. 62 BlockAllocateContig 63 Find and allocate a contiguous range of blocks of a given size. If 64 a contiguous range of free blocks of the given size isn't found, then 65 the allocation fails (i.e. it is "all or nothing"). 66 ReadBitmapBlock 67 Given an allocation block number, read the bitmap block that 68 contains that allocation block into a caller-supplied buffer. 69*/ 70 71#include "Scavenger.h" 72 73 74enum { 75 kBitsPerByte = 8, 76 kBitsPerWord = 32, 77 kBitsWithinWordMask = kBitsPerWord-1 78}; 79 80#define kBytesPerBlock ( (vcb->vcbSignature == kHFSSigWord) ? kHFSBlockSize : vcb->vcbAllocationFile->fcbBlockSize ) 81#define kWordsPerBlock ( kBytesPerBlock / 4 ) 82#define kBitsPerBlock ( kBytesPerBlock * kBitsPerByte ) 83#define kBitsWithinBlockMask ( kBitsPerBlock - 1 ) 84#define kWordsWithinBlockMask ( kWordsPerBlock - 1 ) 85 86#define kLowBitInWordMask 0x00000001u 87#define kHighBitInWordMask 0x80000000u 88#define kAllBitsSetInWord 0xFFFFFFFFu 89 90 91static OSErr ReadBitmapBlock( 92 SVCB *vcb, 93 UInt32 bit, 94 BlockDescriptor *block); 95 96static OSErr ReleaseBitmapBlock( 97 SVCB *vcb, 98 OptionBits options, 99 BlockDescriptor *block); 100 101static OSErr BlockAllocateContig( 102 SVCB *vcb, 103 UInt32 startingBlock, 104 UInt32 minBlocks, 105 UInt32 maxBlocks, 106 UInt32 *actualStartBlock, 107 UInt32 *actualNumBlocks); 108 109static OSErr BlockAllocateAny( 110 SVCB *vcb, 111 UInt32 startingBlock, 112 register UInt32 endingBlock, 113 UInt32 maxBlocks, 114 UInt32 *actualStartBlock, 115 UInt32 *actualNumBlocks); 116 117static OSErr BlockFindContiguous( 118 SVCB *vcb, 119 UInt32 startingBlock, 120 UInt32 endingBlock, 121 UInt32 minBlocks, 122 UInt32 maxBlocks, 123 UInt32 *actualStartBlock, 124 UInt32 *actualNumBlocks); 125 126static OSErr BlockMarkAllocated( 127 SVCB *vcb, 128 UInt32 startingBlock, 129 UInt32 numBlocks); 130 131static OSErr BlockMarkFree( 132 SVCB *vcb, 133 UInt32 startingBlock, 134 UInt32 numBlocks); 135 136/* 137;________________________________________________________________________________ 138; 139; Routine: BlockAllocate 140; 141; Function: Allocate space on a volume. If contiguous allocation is requested, 142; at least the requested number of bytes will be allocated or an 143; error will be returned. If contiguous allocation is not forced, 144; the space will be allocated at the first free fragment following 145; the requested starting allocation block. If there is not enough 146; room there, a block of less than the requested size will be 147; allocated. 148; 149; If the requested starting block is 0 (for new file allocations), 150; the volume's allocation block pointer will be used as a starting 151; point. 152; 153; The function uses on-disk volume bitmap for allocation 154; and updates it with newly allocated blocks. It also 155; updates the in-memory volume bitmap. 156; 157; Input Arguments: 158; vcb - Pointer to SVCB for the volume to allocate space on 159; fcb - Pointer to FCB for the file for which storage is being allocated 160; startingBlock - Preferred starting allocation block, 0 = no preference 161; forceContiguous - Force contiguous flag - if bit 0 set, allocation is contiguous 162; or an error is returned 163; blocksRequested - Number of allocation blocks requested. If the allocation is 164; non-contiguous, less than this may actually be allocated 165; blocksMaximum - The maximum number of allocation blocks to allocate. If there 166; is additional free space after blocksRequested, then up to 167; blocksMaximum blocks should really be allocated. (Used by 168; ExtendFileC to round up allocations to a multiple of the 169; file's clump size.) 170; 171; Output: 172; (result) - Error code, zero for successful allocation 173; *startBlock - Actual starting allocation block 174; *actualBlocks - Actual number of allocation blocks allocated 175; 176; Side effects: 177; The volume bitmap is read and updated; the volume bitmap cache may be changed. 178; 179; Modification history: 180;________________________________________________________________________________ 181*/ 182 183OSErr BlockAllocate ( 184 SVCB *vcb, /* which volume to allocate space on */ 185 UInt32 startingBlock, /* preferred starting block, or 0 for no preference */ 186 UInt32 blocksRequested, /* desired number of BYTES to allocate */ 187 UInt32 blocksMaximum, /* maximum number of bytes to allocate */ 188 Boolean forceContiguous, /* non-zero to force contiguous allocation and to force */ 189 /* bytesRequested bytes to actually be allocated */ 190 UInt32 *actualStartBlock, /* actual first block of allocation */ 191 UInt32 *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */ 192 /* was zero, then this may represent fewer than bytesRequested */ 193 /* bytes */ 194{ 195 OSErr err; 196 Boolean updateAllocPtr = false; // true if nextAllocation needs to be updated 197 198 // 199 // Initialize outputs in case we get an error 200 // 201 *actualStartBlock = 0; 202 *actualNumBlocks = 0; 203 204 // 205 // If the disk is already full, don't bother. 206 // 207 if (vcb->vcbFreeBlocks == 0) { 208 err = dskFulErr; 209 goto Exit; 210 } 211 if (forceContiguous && vcb->vcbFreeBlocks < blocksRequested) { 212 err = dskFulErr; 213 goto Exit; 214 } 215 216 // 217 // If caller didn't specify a starting block number, then use the volume's 218 // next block to allocate from. 219 // 220 if (startingBlock == 0) { 221 startingBlock = vcb->vcbNextAllocation; 222 updateAllocPtr = true; 223 } 224 225 // 226 // If the request must be contiguous, then find a sequence of free blocks 227 // that is long enough. Otherwise, find the first free block. 228 // 229 if (forceContiguous) 230 err = BlockAllocateContig(vcb, startingBlock, blocksRequested, blocksMaximum, actualStartBlock, actualNumBlocks); 231 else { 232 // We'll try to allocate contiguous space first. If that fails, we'll fall back to finding whatever tiny 233 // extents we can find. It would be nice if we kept track of the largest N free extents so that falling 234 // back grabbed a small number of large extents. 235 err = BlockAllocateContig(vcb, startingBlock, blocksRequested, blocksMaximum, actualStartBlock, actualNumBlocks); 236 if (err == dskFulErr) 237 err = BlockAllocateAny(vcb, startingBlock, vcb->vcbTotalBlocks, blocksMaximum, actualStartBlock, actualNumBlocks); 238 if (err == dskFulErr) 239 err = BlockAllocateAny(vcb, 0, startingBlock, blocksMaximum, actualStartBlock, actualNumBlocks); 240 } 241 242 if (err == noErr) { 243 // 244 // If we used the volume's roving allocation pointer, then we need to update it. 245 // Adding in the length of the current allocation might reduce the next allocate 246 // call by avoiding a re-scan of the already allocated space. However, the clump 247 // just allocated can quite conceivably end up being truncated or released when 248 // the file is closed or its EOF changed. Leaving the allocation pointer at the 249 // start of the last allocation will avoid unnecessary fragmentation in this case. 250 // 251 if (updateAllocPtr) 252 vcb->vcbNextAllocation = *actualStartBlock; 253 254 // 255 // Update the number of free blocks on the volume 256 // 257 vcb->vcbFreeBlocks -= *actualNumBlocks; 258 MarkVCBDirty(vcb); 259 } 260 261Exit: 262 263 return err; 264} 265 266 267 268/* 269;________________________________________________________________________________ 270; 271; Routine: BlockDeallocate 272; 273; Function: Update the bitmap to deallocate a run of disk allocation blocks 274; The on-disk volume bitmap is read and updated; the in-memory volume bitmap 275; is also updated. 276; 277; Input Arguments: 278; vcb - Pointer to SVCB for the volume to free space on 279; firstBlock - First allocation block to be freed 280; numBlocks - Number of allocation blocks to free up (must be > 0!) 281; 282; Output: 283; (result) - Result code 284; 285; Side effects: 286; The on-disk volume bitmap is read and updated; the in-memory volume bitmap 287; is also changed. 288; 289; Modification history: 290; 291; <06Oct85> PWD Changed to check for error after calls to ReadBM and NextWord 292; Now calls NextBit to read successive bits from the bitmap 293;________________________________________________________________________________ 294*/ 295 296OSErr BlockDeallocate ( 297 SVCB *vcb, // Which volume to deallocate space on 298 UInt32 firstBlock, // First block in range to deallocate 299 UInt32 numBlocks) // Number of contiguous blocks to deallocate 300{ 301 OSErr err; 302 303 304 // 305 // If no blocks to deallocate, then exit early 306 // 307 if (numBlocks == 0) { 308 err = noErr; 309 goto Exit; 310 } 311 312 // 313 // Call internal routine to free the sequence of blocks 314 // 315 err = BlockMarkFree(vcb, firstBlock, numBlocks); 316 if (err) 317 goto Exit; 318 319 // 320 // Update the volume's free block count, and mark the VCB as dirty. 321 // 322 vcb->vcbFreeBlocks += numBlocks; 323 MarkVCBDirty(vcb); 324 325Exit: 326 327 return err; 328} 329 330 331/* 332;_______________________________________________________________________ 333; 334; Routine: DivideAndRoundUp 335; 336; Function: Divide numerator by denominator, rounding up the result if there 337; was a remainder. This is frequently used for computing the number 338; of whole and/or partial blocks used by some count of bytes. 339;_______________________________________________________________________ 340*/ 341UInt32 DivideAndRoundUp( 342 UInt32 numerator, 343 UInt32 denominator) 344{ 345 UInt32 quotient; 346 347 quotient = numerator / denominator; 348 if (quotient * denominator != numerator) 349 quotient++; 350 351 return quotient; 352} 353 354 355 356/* 357;_______________________________________________________________________ 358; 359; Routine: ReadBitmapBlock 360; 361; Function: Read in a bitmap block corresponding to a given allocation 362; block. Return a pointer to the bitmap block. 363; 364; Inputs: 365; vcb -- Pointer to SVCB 366; block -- Allocation block whose bitmap block is desired 367; 368; Outputs: 369; buffer -- Pointer to bitmap block corresonding to "block" 370;_______________________________________________________________________ 371*/ 372static OSErr ReadBitmapBlock( 373 SVCB *vcb, 374 UInt32 bit, 375 BlockDescriptor *block) 376{ 377 OSErr err = noErr; 378 UInt64 blockNum; 379 380 if (vcb->vcbSignature == kHFSSigWord) { 381 // 382 // HFS: Turn block number into physical block offset within the 383 // bitmap, and then the physical block within the volume. 384 // 385 blockNum = bit / kBitsPerBlock; /* block offset within bitmap */ 386 blockNum += vcb->vcbVBMSt; /* block within whole volume */ 387 388 err = GetVolumeBlock(vcb, blockNum, kGetBlock | kSkipEndianSwap, block); 389 390 } else { 391 // HFS+: "bit" is the allocation block number that we are looking for 392 // in the allocation bit map. GetFileBlock wants a file block number 393 // so we calculate how many bits (kBitsPerBlock) fit in a file 394 // block then convert that to a file block number (bit / kBitsPerBlock) 395 // for our call. 396 err = GetFileBlock( vcb->vcbAllocationFile, (bit / kBitsPerBlock), kGetBlock, block ); 397 } 398 399 return err; 400} 401 402 403 404static OSErr ReleaseBitmapBlock( 405 SVCB *vcb, 406 OptionBits options, 407 BlockDescriptor *block) 408{ 409 OSErr err; 410 411 if (vcb->vcbSignature == kHFSSigWord) 412 err = ReleaseVolumeBlock (vcb, block, options | kSkipEndianSwap); 413 else 414 err = ReleaseFileBlock (vcb->vcbAllocationFile, block, options); 415 416 return err; 417} 418 419 420 421/* 422_______________________________________________________________________ 423 424Routine: BlockAllocateContig 425 426Function: Allocate a contiguous group of allocation blocks. The 427 allocation is all-or-nothing. The caller guarantees that 428 there are enough free blocks (though they may not be 429 contiguous, in which case this call will fail). 430 431 The function uses on-disk volume bitmap for allocation 432 and updates it with newly allocated blocks. It also 433 updates the in-memory volume bitmap. 434 435Inputs: 436 vcb Pointer to volume where space is to be allocated 437 startingBlock Preferred first block for allocation 438 minBlocks Minimum number of contiguous blocks to allocate 439 maxBlocks Maximum number of contiguous blocks to allocate 440 441Outputs: 442 actualStartBlock First block of range allocated, or 0 if error 443 actualNumBlocks Number of blocks allocated, or 0 if error 444_______________________________________________________________________ 445*/ 446static OSErr BlockAllocateContig( 447 SVCB *vcb, 448 UInt32 startingBlock, 449 UInt32 minBlocks, 450 UInt32 maxBlocks, 451 UInt32 *actualStartBlock, 452 UInt32 *actualNumBlocks) 453{ 454 OSErr err; 455 456 // 457 // Find a contiguous group of blocks at least minBlocks long. 458 // Determine the number of contiguous blocks available (up 459 // to maxBlocks). 460 // 461 err = BlockFindContiguous(vcb, startingBlock, vcb->vcbTotalBlocks, minBlocks, maxBlocks, 462 actualStartBlock, actualNumBlocks); 463 if (err == dskFulErr) { 464 //�� Should constrain the endingBlock here, so we don't bother looking for ranges 465 //�� that start after startingBlock, since we already checked those. 466 err = BlockFindContiguous(vcb, 0, vcb->vcbTotalBlocks, minBlocks, maxBlocks, 467 actualStartBlock, actualNumBlocks); 468 } 469 if (err != noErr) goto Exit; 470 471 // 472 // Now mark those blocks allocated. 473 // 474 err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks); 475 476Exit: 477 if (err != noErr) { 478 *actualStartBlock = 0; 479 *actualNumBlocks = 0; 480 } 481 482 return err; 483} 484 485 486 487/* 488_______________________________________________________________________ 489 490Routine: BlockAllocateAny 491 492Function: Allocate one or more allocation blocks. If there are fewer 493 free blocks than requested, all free blocks will be 494 allocated. The caller guarantees that there is at least 495 one free block. 496 497 The function uses on-disk volume bitmap for allocation 498 and updates it with newly allocated blocks. It also 499 updates the in-memory volume bitmap. 500 501Inputs: 502 vcb Pointer to volume where space is to be allocated 503 startingBlock Preferred first block for allocation 504 endingBlock Last block to check + 1 505 maxBlocks Maximum number of contiguous blocks to allocate 506 507Outputs: 508 actualStartBlock First block of range allocated, or 0 if error 509 actualNumBlocks Number of blocks allocated, or 0 if error 510_______________________________________________________________________ 511*/ 512static OSErr BlockAllocateAny( 513 SVCB *vcb, 514 UInt32 startingBlock, 515 register UInt32 endingBlock, 516 UInt32 maxBlocks, 517 UInt32 *actualStartBlock, 518 UInt32 *actualNumBlocks) 519{ 520 OSErr err; 521 register UInt32 block = 0; // current block number 522 register UInt32 currentWord; // Pointer to current word within bitmap block 523 register UInt32 bitMask; // Word with given bits already set (ready to OR in) 524 register UInt32 wordsLeft; // Number of words left in this bitmap block 525 UInt32 *buffer; 526 BlockDescriptor bd = {0}; 527 OptionBits relOpt = kReleaseBlock; 528 529 // Since this routine doesn't wrap around 530 if (maxBlocks > (endingBlock - startingBlock)) { 531 maxBlocks = endingBlock - startingBlock; 532 } 533 534 // 535 // Pre-read the first bitmap block 536 // 537 538 err = ReadBitmapBlock(vcb, startingBlock, &bd); 539 if (err != noErr) goto Exit; 540 relOpt = kMarkBlockDirty; 541 buffer = (UInt32 *) bd.buffer; 542 543 // 544 // Set up the current position within the block 545 // 546 { 547 UInt32 wordIndexInBlock; 548 549 wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord; 550 buffer += wordIndexInBlock; 551 wordsLeft = kWordsPerBlock - wordIndexInBlock; 552 currentWord = SWAP_BE32(*buffer); 553 bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask); 554 } 555 556 // 557 // Find the first unallocated block 558 // 559 block = startingBlock; 560 while (block < endingBlock) { 561 if ((currentWord & bitMask) == 0) 562 break; 563 564 // Next bit 565 ++block; 566 bitMask >>= 1; 567 if (bitMask == 0) { 568 // Next word 569 bitMask = kHighBitInWordMask; 570 ++buffer; 571 572 if (--wordsLeft == 0) { 573 // Next block 574 err = ReleaseBitmapBlock(vcb, relOpt, &bd); 575 bd.buffer = NULL; 576 if (err != noErr) goto Exit; 577 578 err = ReadBitmapBlock(vcb, block, &bd); 579 if (err != noErr) goto Exit; 580 buffer = (UInt32 *) bd.buffer; 581 relOpt = kMarkBlockDirty; 582 583 wordsLeft = kWordsPerBlock; 584 } 585 currentWord = SWAP_BE32(*buffer); 586 } 587 } 588 589 // Did we get to the end of the bitmap before finding a free block? 590 // If so, then couldn't allocate anything. 591 if (block == endingBlock) { 592 err = dskFulErr; 593 goto Exit; 594 } 595 596 // Return the first block in the allocated range 597 *actualStartBlock = block; 598 599 // If we could get the desired number of blocks before hitting endingBlock, 600 // then adjust endingBlock so we won't keep looking. Ideally, the comparison 601 // would be (block + maxBlocks) < endingBlock, but that could overflow. The 602 // comparison below yields identical results, but without overflow. 603 if (block < (endingBlock-maxBlocks)) { 604 endingBlock = block + maxBlocks; // if we get this far, we've found enough 605 } 606 607 // 608 // Allocate all of the consecutive blocks 609 // 610 while ((currentWord & bitMask) == 0) { 611 // Allocate this block 612 currentWord |= bitMask; 613 614 // Move to the next block. If no more, then exit. 615 ++block; 616 if (block == endingBlock) 617 break; 618 619 // Next bit 620 bitMask >>= 1; 621 if (bitMask == 0) { 622 *buffer = SWAP_BE32(currentWord); // update value in bitmap 623 624 // Next word 625 bitMask = kHighBitInWordMask; 626 ++buffer; 627 628 if (--wordsLeft == 0) { 629 // Next block 630 err = ReleaseBitmapBlock(vcb, relOpt, &bd); 631 if (err != noErr) goto Exit; 632 bd.buffer = NULL; 633 634 err = ReadBitmapBlock(vcb, block, &bd); 635 if (err != noErr) goto Exit; 636 buffer = (UInt32 *) bd.buffer; 637 relOpt = kMarkBlockDirty; 638 639 wordsLeft = kWordsPerBlock; 640 } 641 currentWord = SWAP_BE32(*buffer); 642 } 643 } 644 *buffer = SWAP_BE32(currentWord); // update the last change 645 646Exit: 647 if (err == noErr) { 648 *actualNumBlocks = block - *actualStartBlock; 649 650 /* Update the in-memory copy of bitmap */ 651 (void) CaptureBitmapBits (*actualStartBlock, *actualNumBlocks); 652 } 653 else { 654 *actualStartBlock = 0; 655 *actualNumBlocks = 0; 656 } 657 658 if (bd.buffer != NULL) 659 (void) ReleaseBitmapBlock(vcb, relOpt, &bd); 660 661 return err; 662} 663 664 665 666/* 667_______________________________________________________________________ 668 669Routine: BlockMarkAllocated 670 671Function: Mark a contiguous group of blocks as allocated (set in the 672 bitmap). The function sets the bit independent of the 673 previous state (set/clear) of the bit. 674 675 The function uses on-disk volume bitmap for allocation 676 and updates it with newly allocated blocks. It also 677 updates the in-memory volume bitmap. 678 679Inputs: 680 vcb Pointer to volume where space is to be allocated 681 startingBlock First block number to mark as allocated 682 numBlocks Number of blocks to mark as allocated 683_______________________________________________________________________ 684*/ 685static OSErr BlockMarkAllocated( 686 SVCB *vcb, 687 UInt32 startingBlock, 688 register UInt32 numBlocks) 689{ 690 OSErr err; 691 register UInt32 *currentWord; // Pointer to current word within bitmap block 692 register UInt32 wordsLeft; // Number of words left in this bitmap block 693 register UInt32 bitMask; // Word with given bits already set (ready to OR in) 694 UInt32 firstBit; // Bit index within word of first bit to allocate 695 UInt32 numBits; // Number of bits in word to allocate 696 UInt32 *buffer; 697 BlockDescriptor bd = {0}; 698 OptionBits relOpt = kReleaseBlock; 699 700 UInt32 saveNumBlocks = numBlocks; 701 UInt32 saveStartingBlock = startingBlock; 702 703 // 704 // Pre-read the bitmap block containing the first word of allocation 705 // 706 707 err = ReadBitmapBlock(vcb, startingBlock, &bd); 708 if (err != noErr) goto Exit; 709 buffer = (UInt32 *) bd.buffer; 710 relOpt = kMarkBlockDirty; 711 712 // 713 // Initialize currentWord, and wordsLeft. 714 // 715 { 716 UInt32 wordIndexInBlock; 717 718 wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord; 719 currentWord = buffer + wordIndexInBlock; 720 wordsLeft = kWordsPerBlock - wordIndexInBlock; 721 } 722 723 // 724 // If the first block to allocate doesn't start on a word 725 // boundary in the bitmap, then treat that first word 726 // specially. 727 // 728 729 firstBit = startingBlock % kBitsPerWord; 730 if (firstBit != 0) { 731 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit 732 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word 733 if (numBits > numBlocks) { 734 numBits = numBlocks; // entire allocation is inside this one word 735 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last 736 } 737#if DEBUG_BUILD 738 if ((*currentWord & SWAP_BE32(bitMask)) != 0) { 739 DebugStr("\pFATAL: blocks already allocated!"); 740 err = fsDSIntErr; 741 goto Exit; 742 } 743#endif 744 *currentWord |= SWAP_BE32(bitMask); // set the bits in the bitmap 745 numBlocks -= numBits; // adjust number of blocks left to allocate 746 747 ++currentWord; // move to next word 748 --wordsLeft; // one less word left in this block 749 } 750 751 // 752 // Allocate whole words (32 blocks) at a time. 753 // 754 755 bitMask = kAllBitsSetInWord; // put this in a register for 68K 756 while (numBlocks >= kBitsPerWord) { 757 if (wordsLeft == 0) { 758 // Read in the next bitmap block 759 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block 760 761 err = ReleaseBitmapBlock(vcb, relOpt, &bd); 762 if (err != noErr) goto Exit; 763 bd.buffer = NULL; 764 765 err = ReadBitmapBlock(vcb, startingBlock, &bd); 766 if (err != noErr) goto Exit; 767 buffer = (UInt32 *) bd.buffer; 768 relOpt = kMarkBlockDirty; 769 770 // Readjust currentWord and wordsLeft 771 currentWord = buffer; 772 wordsLeft = kWordsPerBlock; 773 } 774#if DEBUG_BUILD 775 if (*currentWord != 0) { 776 DebugStr("\pFATAL: blocks already allocated!"); 777 err = fsDSIntErr; 778 goto Exit; 779 } 780#endif 781 *currentWord = SWAP_BE32(bitMask); 782 numBlocks -= kBitsPerWord; 783 784 ++currentWord; // move to next word 785 --wordsLeft; // one less word left in this block 786 } 787 788 // 789 // Allocate any remaining blocks. 790 // 791 792 if (numBlocks != 0) { 793 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits 794 if (wordsLeft == 0) { 795 // Read in the next bitmap block 796 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block 797 798 err = ReleaseBitmapBlock(vcb, relOpt, &bd); 799 if (err != noErr) goto Exit; 800 bd.buffer = NULL; 801 802 err = ReadBitmapBlock(vcb, startingBlock, &bd); 803 if (err != noErr) goto Exit; 804 buffer = (UInt32 *) bd.buffer; 805 relOpt = kMarkBlockDirty; 806 807 // Readjust currentWord and wordsLeft 808 currentWord = buffer; 809 wordsLeft = kWordsPerBlock; 810 } 811#if DEBUG_BUILD 812 if ((*currentWord & SWAP_BE32(bitMask)) != 0) { 813 DebugStr("\pFATAL: blocks already allocated!"); 814 err = fsDSIntErr; 815 goto Exit; 816 } 817#endif 818 *currentWord |= SWAP_BE32(bitMask); // set the bits in the bitmap 819 820 // No need to update currentWord or wordsLeft 821 } 822 823 /* Update the in-memory copy of the volume bitmap */ 824 (void) CaptureBitmapBits(saveStartingBlock, saveNumBlocks); 825 826Exit: 827 if (bd.buffer != NULL) 828 (void) ReleaseBitmapBlock(vcb, relOpt, &bd); 829 830 return err; 831} 832 833 834 835/* 836_______________________________________________________________________ 837 838Routine: BlockMarkFree 839 840Function: Mark a contiguous group of blocks as free (clear in the 841 bitmap). The function clears the bit independent of the 842 previous state (set/clear) of the bit. 843 844 This function uses the on-disk bitmap and also updates 845 the in-memory bitmap with the deallocated blocks 846 847Inputs: 848 vcb Pointer to volume where space is to be freed 849 startingBlock First block number to mark as freed 850 numBlocks Number of blocks to mark as freed 851_______________________________________________________________________ 852*/ 853static OSErr BlockMarkFree( 854 SVCB *vcb, 855 UInt32 startingBlock, 856 register UInt32 numBlocks) 857{ 858 OSErr err; 859 register UInt32 *currentWord; // Pointer to current word within bitmap block 860 register UInt32 wordsLeft; // Number of words left in this bitmap block 861 register UInt32 bitMask; // Word with given bits already set (ready to OR in) 862 UInt32 firstBit; // Bit index within word of first bit to allocate 863 UInt32 numBits; // Number of bits in word to allocate 864 UInt32 *buffer; 865 BlockDescriptor bd = {0}; 866 OptionBits relOpt = kReleaseBlock; 867 868 UInt32 saveNumBlocks = numBlocks; 869 UInt32 saveStartingBlock = startingBlock; 870 871 // 872 // Pre-read the bitmap block containing the first word of allocation 873 // 874 875 err = ReadBitmapBlock(vcb, startingBlock, &bd); 876 if (err != noErr) goto Exit; 877 buffer = (UInt32 *) bd.buffer; 878 relOpt = kMarkBlockDirty; 879 880 // 881 // Initialize currentWord, and wordsLeft. 882 // 883 { 884 UInt32 wordIndexInBlock; 885 886 wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord; 887 currentWord = buffer + wordIndexInBlock; 888 wordsLeft = kWordsPerBlock - wordIndexInBlock; 889 } 890 891 // 892 // If the first block to free doesn't start on a word 893 // boundary in the bitmap, then treat that first word 894 // specially. 895 // 896 897 firstBit = startingBlock % kBitsPerWord; 898 if (firstBit != 0) { 899 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit 900 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word 901 if (numBits > numBlocks) { 902 numBits = numBlocks; // entire allocation is inside this one word 903 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last 904 } 905#if DEBUG_BUILD 906 if ((*currentWord & SWAP_BE32(bitMask)) != SWAP_BE32(bitMask)) { 907 DebugStr("\pFATAL: blocks not allocated!"); 908 err = fsDSIntErr; 909 goto Exit; 910 } 911#endif 912 *currentWord &= SWAP_BE32(~bitMask); // clear the bits in the bitmap 913 numBlocks -= numBits; // adjust number of blocks left to free 914 915 ++currentWord; // move to next word 916 --wordsLeft; // one less word left in this block 917 } 918 919 // 920 // Allocate whole words (32 blocks) at a time. 921 // 922 923 while (numBlocks >= kBitsPerWord) { 924 if (wordsLeft == 0) { 925 // Read in the next bitmap block 926 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block 927 928 err = ReleaseBitmapBlock(vcb, relOpt, &bd); 929 if (err != noErr) goto Exit; 930 bd.buffer = NULL; 931 932 err = ReadBitmapBlock(vcb, startingBlock, &bd); 933 if (err != noErr) goto Exit; 934 buffer = (UInt32 *) bd.buffer; 935 relOpt = kMarkBlockDirty; 936 937 // Readjust currentWord and wordsLeft 938 currentWord = buffer; 939 wordsLeft = kWordsPerBlock; 940 } 941#if DEBUG_BUILD 942 if (*currentWord != kAllBitsSetInWord) { 943 DebugStr("\pFATAL: blocks not allocated!"); 944 err = fsDSIntErr; 945 goto Exit; 946 } 947#endif 948 *currentWord = 0; // clear the entire word 949 numBlocks -= kBitsPerWord; 950 951 ++currentWord; // move to next word 952 --wordsLeft; // one less word left in this block 953 } 954 955 // 956 // Allocate any remaining blocks. 957 // 958 959 if (numBlocks != 0) { 960 bitMask = ~(kAllBitsSetInWord >> numBlocks); // set first numBlocks bits 961 if (wordsLeft == 0) { 962 // Read in the next bitmap block 963 startingBlock += kBitsPerBlock; // generate a block number in the next bitmap block 964 965 err = ReleaseBitmapBlock(vcb, relOpt, &bd); 966 if (err != noErr) goto Exit; 967 bd.buffer = NULL; 968 969 err = ReadBitmapBlock(vcb, startingBlock, &bd); 970 if (err != noErr) goto Exit; 971 buffer = (UInt32 *) bd.buffer; 972 relOpt = kMarkBlockDirty; 973 974 // Readjust currentWord and wordsLeft 975 currentWord = buffer; 976 wordsLeft = kWordsPerBlock; 977 } 978#if DEBUG_BUILD 979 if ((*currentWord & SWAP_BE32(bitMask)) != SWAP_BE32(bitMask)) { 980 DebugStr("\pFATAL: blocks not allocated!"); 981 err = fsDSIntErr; 982 goto Exit; 983 } 984#endif 985 *currentWord &= SWAP_BE32(~bitMask); // clear the bits in the bitmap 986 987 // No need to update currentWord or wordsLeft 988 } 989 990 /* Update the in-memory copy of the volume bitmap */ 991 (void) ReleaseBitmapBits(saveStartingBlock, saveNumBlocks); 992 993Exit: 994 if (bd.buffer != NULL) 995 (void) ReleaseBitmapBlock(vcb, relOpt, &bd); 996 997 return err; 998} 999 1000 1001/* 1002_______________________________________________________________________ 1003 1004Routine: BlockFindContiguous 1005 1006Function: Find a contiguous range of blocks that are free (bits 1007 clear in the bitmap). If a contiguous range of the 1008 minimum size can't be found, an error will be returned. 1009 1010 �� It would be nice if we could skip over whole words 1011 �� with all bits set. 1012 1013 �� When we find a bit set, and are about to set freeBlocks 1014 �� to 0, we should check to see whether there are still 1015 �� minBlocks bits left in the bitmap. 1016 1017Inputs: 1018 vcb Pointer to volume where space is to be allocated 1019 startingBlock Preferred first block of range 1020 endingBlock Last possible block in range + 1 1021 minBlocks Minimum number of blocks needed. Must be > 0. 1022 maxBlocks Maximum (ideal) number of blocks desired 1023 1024Outputs: 1025 actualStartBlock First block of range found, or 0 if error 1026 actualNumBlocks Number of blocks found, or 0 if error 1027_______________________________________________________________________ 1028*/ 1029/* 1030_________________________________________________________________________________________ 1031 (DSH) 5/8/97 Description of BlockFindContiguous() algorithm 1032 Finds a contiguous range of free blocks by searching back to front. This 1033 allows us to skip ranges of bits knowing that they are not candidates for 1034 a match because they are too small. The below ascii diagrams illustrate 1035 the algorithm in action. 1036 1037 Representation of a piece of a volume bitmap file 1038 If BlockFindContiguous() is called with minBlocks == 10, maxBlocks == 20 1039 1040 1041Fig. 1 initialization of variables, "<--" represents direction of travel 1042 1043startingBlock (passed in) 1044 | 1045 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1046 | <--| 1047stopBlock currentBlock freeBlocks == 0 1048 countedFreeBlocks == 0 1049 1050Fig. 2 dirty bit found 1051 1052 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1053 | | 1054stopBlock currentBlock freeBlocks == 3 1055 countedFreeBlocks == 0 1056 1057Fig. 3 reset variables to search for remainder of minBlocks 1058 1059 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1060 |_________________| | | 1061 Unsearched stopBlock currentBlock freeBlocks == 0 1062 countedFreeBlocks == 3 1063 1064Fig. 4 minBlocks contiguous blocks found, *actualStartBlock is set 1065 1066 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1067 |_________________| | 1068 Unsearched stopBlock freeBlocks == 7 1069 currentBlock countedFreeBlocks == 3 1070 1071Fig. 5 Now run it forwards trying to accumalate up to maxBlocks if possible 1072 1073 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1074 |_________________| | --> 1075 Unsearched currentBlock 1076 *actualNumBlocks == 10 1077 1078Fig. 6 Dirty bit is found, return actual number of contiguous blocks found 1079 1080 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1081 |_________________| | 1082 Unsearched currentBlock 1083 *actualNumBlocks == 16 1084_________________________________________________________________________________________ 1085*/ 1086static OSErr BlockFindContiguous( 1087 SVCB *vcb, 1088 UInt32 startingBlock, 1089 register UInt32 endingBlock, 1090 UInt32 minBlocks, 1091 UInt32 maxBlocks, 1092 UInt32 *actualStartBlock, 1093 UInt32 *actualNumBlocks) 1094{ 1095 OSErr err; 1096 register UInt32 bitMask; // mask of bit within word for currentBlock 1097 register UInt32 tempWord; // bitmap word currently being examined 1098 register UInt32 freeBlocks; // number of contiguous free blocks so far 1099 register UInt32 currentBlock; // block number we're currently examining 1100 UInt32 wordsLeft; // words remaining in bitmap block 1101 UInt32 *buffer = NULL; 1102 register UInt32 *currentWord; 1103 1104 UInt32 stopBlock; // when all blocks until stopBlock are free, we found enough 1105 UInt32 countedFreeBlocks; // how many contiguous free block behind stopBlock 1106 UInt32 currentSector; // which allocations file sector 1107 BlockDescriptor bd = {0}; 1108 1109 if ((endingBlock - startingBlock) < minBlocks) { 1110 // The set of blocks we're checking is smaller than the minimum number 1111 // of blocks, so we couldn't possibly find a good range. 1112 err = dskFulErr; 1113 goto Exit; 1114 } 1115 1116 // Search for min blocks from back to front. 1117 // If min blocks is found, advance the allocation pointer up to max blocks 1118 1119 // 1120 // Pre-read the bitmap block containing currentBlock 1121 // 1122 stopBlock = startingBlock; 1123 currentBlock = startingBlock + minBlocks - 1; // (-1) to include startingBlock 1124 1125 err = ReadBitmapBlock(vcb, currentBlock, &bd); 1126 if ( err != noErr ) goto Exit; 1127 buffer = (UInt32 *) bd.buffer; 1128 // 1129 // Init buffer, currentWord, wordsLeft, and bitMask 1130 // 1131 { 1132 UInt32 wordIndexInBlock; 1133 1134 wordIndexInBlock = ( currentBlock & kBitsWithinBlockMask ) / kBitsPerWord; 1135 currentWord = buffer + wordIndexInBlock; 1136 1137 wordsLeft = wordIndexInBlock; 1138 tempWord = SWAP_BE32(*currentWord); 1139 bitMask = kHighBitInWordMask >> ( currentBlock & kBitsWithinWordMask ); 1140 currentSector = currentBlock / kBitsPerBlock; 1141 } 1142 1143 // 1144 // Look for maxBlocks free blocks. If we find an allocated block, 1145 // see if we've found minBlocks. 1146 // 1147 freeBlocks = 0; 1148 countedFreeBlocks = 0; 1149 1150 while ( currentBlock >= stopBlock ) 1151 { 1152 // Check current bit 1153 if ((tempWord & bitMask) == 0) 1154 { 1155 ++freeBlocks; 1156 } 1157 else // Used bitmap block found 1158 { 1159 if ( ( freeBlocks + countedFreeBlocks ) >= minBlocks ) 1160 { 1161 break; // Found enough 1162 } 1163 else 1164 { 1165 // We found a dirty bit, so we want to check if the next (minBlocks-freeBlocks) blocks 1166 // are free beyond what we have already checked. At Fig.2 setting up for Fig.3 1167 1168 stopBlock = currentBlock + 1 + freeBlocks; // Advance stop condition 1169 currentBlock += minBlocks; 1170 if ( currentBlock >= endingBlock ) break; 1171 countedFreeBlocks = freeBlocks; 1172 freeBlocks = 0; // Not enough; look for another range 1173 1174 if ( currentSector != currentBlock / kBitsPerBlock ) 1175 { 1176 err = ReleaseBitmapBlock(vcb, kReleaseBlock, &bd); 1177 if (err != noErr) goto Exit; 1178 bd.buffer = NULL; 1179 1180 err = ReadBitmapBlock( vcb, currentBlock, &bd ); 1181 if (err != noErr) goto Exit; 1182 buffer = (UInt32 *) bd.buffer; 1183 currentSector = currentBlock / kBitsPerBlock; 1184 } 1185 1186 wordsLeft = ( currentBlock & kBitsWithinBlockMask ) / kBitsPerWord; 1187 currentWord = buffer + wordsLeft; 1188 tempWord = SWAP_BE32(*currentWord); 1189 bitMask = kHighBitInWordMask >> ( currentBlock & kBitsWithinWordMask ); 1190 1191 continue; // Back to the while loop 1192 } 1193 } 1194 1195 // Move to next bit 1196 --currentBlock; 1197 bitMask <<= 1; 1198 if (bitMask == 0) // On a word boundry, start masking words 1199 { 1200 bitMask = kLowBitInWordMask; 1201 1202 // Move to next word 1203NextWord: 1204 if ( wordsLeft != 0 ) 1205 { 1206 --currentWord; 1207 --wordsLeft; 1208 } 1209 else 1210 { 1211 // Read in the next bitmap block 1212 err = ReleaseBitmapBlock(vcb, kReleaseBlock, &bd); 1213 if (err != noErr) goto Exit; 1214 bd.buffer = NULL; 1215 1216 err = ReadBitmapBlock( vcb, currentBlock, &bd ); 1217 if (err != noErr) goto Exit; 1218 buffer = (UInt32 *) bd.buffer; 1219 // Adjust currentWord, wordsLeft, currentSector 1220 currentSector = currentBlock / kBitsPerBlock; 1221 currentWord = buffer + kWordsPerBlock - 1; // Last word in buffer 1222 wordsLeft = kWordsPerBlock - 1; 1223 } 1224 1225 tempWord = SWAP_BE32(*currentWord); // Grab the current word 1226 1227 // 1228 // If we found a whole word of free blocks, quickly skip over it. 1229 // NOTE: we could actually go beyond the end of the bitmap if the 1230 // number of allocation blocks on the volume is not a multiple of 1231 // 32. If this happens, we'll adjust currentBlock and freeBlocks 1232 // after the loop. 1233 // 1234 if ( tempWord == 0 ) 1235 { 1236 freeBlocks += kBitsPerWord; 1237 currentBlock -= kBitsPerWord; 1238 if ( freeBlocks + countedFreeBlocks >= minBlocks ) 1239 break; // Found enough 1240 goto NextWord; 1241 } 1242 } 1243 } 1244 1245 if ( freeBlocks + countedFreeBlocks < minBlocks ) 1246 { 1247 *actualStartBlock = 0; 1248 *actualNumBlocks = 0; 1249 err = dskFulErr; 1250 goto Exit; 1251 } 1252 1253 // 1254 // When we get here, we know we've found minBlocks continuous space. 1255 // At Fig.4, setting up for Fig.5 1256 // From here we do a forward search accumalating additional free blocks. 1257 // 1258 1259 *actualNumBlocks = minBlocks; 1260 *actualStartBlock = stopBlock - countedFreeBlocks; // ActualStartBlock is set to return to the user 1261 currentBlock = *actualStartBlock + minBlocks; // Right after found free space 1262 1263 // Now lets see if we can run the actualNumBlocks number all the way up to maxBlocks 1264 if ( currentSector != currentBlock / kBitsPerBlock ) 1265 { 1266 err = ReleaseBitmapBlock(vcb, kReleaseBlock, &bd); 1267 if (err != noErr) goto Exit; 1268 bd.buffer = NULL; 1269 1270 err = ReadBitmapBlock( vcb, currentBlock, &bd ); 1271 if (err != noErr) 1272 { 1273 err = noErr; // We already found the space 1274 goto Exit; 1275 } 1276 buffer = (UInt32 *) bd.buffer; 1277 currentSector = currentBlock / kBitsPerBlock; 1278 } 1279 1280 // 1281 // Init buffer, currentWord, wordsLeft, and bitMask 1282 // 1283 { 1284 UInt32 wordIndexInBlock; 1285 1286 wordIndexInBlock = (currentBlock & kBitsWithinBlockMask) / kBitsPerWord; 1287 currentWord = buffer + wordIndexInBlock; 1288 tempWord = SWAP_BE32(*currentWord); 1289 wordsLeft = kWordsPerBlock - wordIndexInBlock; 1290 bitMask = kHighBitInWordMask >> (currentBlock & kBitsWithinWordMask); 1291 } 1292 1293 if ( *actualNumBlocks < maxBlocks ) 1294 { 1295 while ( currentBlock < endingBlock ) 1296 { 1297 1298 if ( (tempWord & bitMask) == 0 ) 1299 { 1300 *actualNumBlocks += 1; 1301 1302 if ( *actualNumBlocks == maxBlocks ) 1303 break; 1304 } 1305 else 1306 { 1307 break; 1308 } 1309 1310 // Move to next bit 1311 ++currentBlock; 1312 bitMask >>= 1; 1313 if (bitMask == 0) 1314 { 1315 bitMask = kHighBitInWordMask; 1316 ++currentWord; 1317 1318 if ( --wordsLeft == 0) 1319 { 1320 err = ReleaseBitmapBlock(vcb, kReleaseBlock, &bd); 1321 if (err != noErr) goto Exit; 1322 bd.buffer = NULL; 1323 1324 err = ReadBitmapBlock(vcb, currentBlock, &bd); 1325 if (err != noErr) break; 1326 buffer = (UInt32 *) bd.buffer; 1327 1328 // Adjust currentWord, wordsLeft 1329 currentWord = buffer; 1330 wordsLeft = kWordsPerBlock; 1331 } 1332 tempWord = SWAP_BE32(*currentWord); // grab the current word 1333 } 1334 } 1335 } 1336 1337Exit: 1338 1339 if (bd.buffer != NULL) 1340 (void) ReleaseBitmapBlock(vcb, kReleaseBlock, &bd); 1341 1342 return err; 1343} 1344 1345/* 1346 * Find the smallest extent in the array. 1347 */ 1348static int 1349FindMinExt(HFSPlusExtentDescriptor *exts) 1350{ 1351 int minIndx = -1; 1352 UInt32 min = (UInt32)-1; 1353 int i; 1354 1355 for (i = 0; i < kHFSPlusExtentDensity; i++) { 1356 if (exts[i].blockCount < min) { 1357 min = exts[i].blockCount; 1358 minIndx = i; 1359 } 1360 } 1361 return minIndx; 1362} 1363 1364/* 1365 * Truncate any excess extents. There should be only one, 1366 * but we'll go through them all to make sure. 1367 */ 1368static void 1369PruneExtents(HFSPlusExtentDescriptor *exts, UInt32 needed) 1370{ 1371 int i; 1372 UInt32 total = 0; 1373 UInt32 excess = 0; 1374 1375 for (i = 0; i < kHFSPlusExtentDensity; i++) { 1376 if (excess) { 1377 exts[i].startBlock = exts[i].blockCount = 0; 1378 continue; 1379 } 1380 total += exts[i].blockCount; 1381 if (total > needed) { 1382 exts[i].blockCount -= total - needed; 1383 excess = 1; 1384 } 1385 } 1386 return; 1387} 1388 1389/* 1390 * A much more specialized function: simply find the 8 largest extents 1391 * to hold the needed size. It will either find enough blocks to 1392 * fit the needed size, or it will fail. 1393 */ 1394OSErr 1395BlockFindAll( 1396 SFCB *fcb, 1397 UInt32 needed) 1398{ 1399 OSErr err; 1400 SVCB *vcb; 1401 register UInt32 bitMask; // mask of bit within word for currentBlock 1402 register UInt32 tempWord; // bitmap word currently being examined 1403 HFSPlusExtentDescriptor *exts = fcb->fcbExtents32; 1404 int minIndx; 1405 UInt32 total = 0; 1406 1407 UInt32 firstFreeBlock; 1408 UInt32 freeBlocks = 0; 1409 UInt32 currentBlock; 1410 UInt32 endingBlock; 1411 UInt32 wordsLeft; // words remaining in bitmap block 1412 UInt32 *buffer = NULL; 1413 UInt32 contigSize = 1; 1414 register UInt32 *currentWord; 1415 struct BlockDescriptor bd = { 0 }; 1416 1417 vcb = fcb->fcbVolume; 1418 1419 if (vcb->vcbFreeBlocks < needed) { 1420 // Nothing to do 1421 if (debug) 1422 plog("%s: %u blocks free, but need %u; ignoring for now\n", __FUNCTION__, vcb->vcbFreeBlocks, needed); 1423 } 1424 1425 memset(exts, 0, sizeof(fcb->fcbExtents32)); // Zero out the extents. 1426 minIndx = 0; 1427 if (vcb->vcbBlockSize < fcb->fcbBlockSize) { 1428 contigSize = fcb->fcbBlockSize / vcb->vcbBlockSize; // Number of volume blocks in a btree block 1429 } 1430 1431 currentBlock = 0; 1432 endingBlock = vcb->vcbTotalBlocks; 1433 1434 freeBlocks = 0; 1435 1436 err = ReadBitmapBlock(vcb, currentBlock, &bd); 1437 if ( err != noErr ) goto done; 1438 buffer = (UInt32 *) bd.buffer; 1439 // 1440 // Init buffer, currentWord, wordsLeft, and bitMask 1441 // 1442 { 1443 UInt32 wordIndexInBlock; 1444 1445 wordIndexInBlock = ( currentBlock & kBitsWithinBlockMask ) / kBitsPerWord; 1446 currentWord = buffer + wordIndexInBlock; 1447 1448 wordsLeft = kWordsPerBlock - wordIndexInBlock - 1; 1449 tempWord = SWAP_BE32(*currentWord); 1450 bitMask = kHighBitInWordMask >> ( currentBlock & kBitsWithinWordMask ); 1451 } 1452 1453 /* 1454 * This macro is used to cycle through the allocation bitmap. 1455 * We examine one bit in a word at a time; when we're done with that word, 1456 * we go to the next word in the block; when we're done with that block, 1457 * we get the next one. Until we're out of blocks. 1458 */ 1459#define nextblock() do { \ 1460 currentBlock++; \ 1461 if (currentBlock == endingBlock) goto done; \ 1462 bitMask >>= 1; \ 1463 if (bitMask == 0) { \ 1464 bitMask = kHighBitInWordMask; \ 1465 if (wordsLeft != 0) { \ 1466 ++currentWord; \ 1467 --wordsLeft; \ 1468 } else { \ 1469 err = ReleaseBitmapBlock(vcb, kReleaseBlock, &bd); \ 1470 if (err != noErr) goto done; \ 1471 bd.buffer = NULL; \ 1472 err = ReadBitmapBlock(vcb, currentBlock, &bd); \ 1473 if (err != noErr) goto done; \ 1474 buffer = (UInt32*)bd.buffer; \ 1475 currentWord = buffer + ((currentBlock & kBitsWithinBlockMask) / kBitsPerWord); \ 1476 wordsLeft = kWordsPerBlock - 1; \ 1477 } \ 1478 tempWord = SWAP_BE32(*currentWord); \ 1479 } \ 1480 } while (0) 1481 1482loop: 1483 1484 /* 1485 * We have two while loops here. The first one, at the top, looks for 1486 * used blocks. We ignore those. The second while loop then looks 1487 * for empty blocks, and keeps track of the length of the run. It creates 1488 * an extent from these, and puts them into the exts array. We use 1489 * the funciton FindMinExt() to find the smallest one in the array, and 1490 * we only replace it if the new extent is larger. (When first starting, 1491 * all of the extents will be 0 bytes long.) 1492 * 1493 * We stop when we've run out of blocks (the nextblock macro will jump 1494 * to done at that point), or when we've got enough total blocks to 1495 * fit our needs. 1496 */ 1497 freeBlocks = 0; 1498 while ((tempWord & bitMask) != 0) { 1499 nextblock(); 1500 } 1501 firstFreeBlock = currentBlock; 1502 while ((tempWord & bitMask) == 0) { 1503 ++freeBlocks; 1504 if (freeBlocks >= needed) 1505 break; 1506 nextblock(); 1507 } 1508 1509 /* 1510 * We need to ensure that nodes are not split across 1511 * volume blocks -- journaling will cause an error 1512 * if this happens. 1513 */ 1514 freeBlocks -= freeBlocks % contigSize; 1515 1516 if (freeBlocks > exts[minIndx].blockCount) { 1517 total -= exts[minIndx].blockCount; 1518 exts[minIndx].blockCount = freeBlocks; 1519 exts[minIndx].startBlock = firstFreeBlock; 1520 total += freeBlocks; 1521 minIndx = FindMinExt(exts); 1522 } 1523 1524 if (total >= needed) { 1525 goto done; 1526 } 1527 1528 goto loop; 1529 1530done: 1531 if (bd.buffer) { 1532 (void)ReleaseBitmapBlock(vcb, kReleaseBlock, &bd); 1533 } 1534 if (err == noErr) { 1535 1536 if (total < needed) { 1537 if (debug) 1538 plog("%s: found %u blocks but needed %u\n", __FUNCTION__, total, needed); 1539 err = dskFulErr; 1540 } else { 1541 /* 1542 * If we've got enough blocks, we need to prune any extra. 1543 * PruneExtents() will decrement the extents in the array to 1544 * ensure we have only as much as we need. After that, we 1545 * mark them as allocated, and return. 1546 */ 1547 int i; 1548 if (total > needed) { 1549 PruneExtents(exts, needed); 1550 } 1551 for (i = 0; i < kHFSPlusExtentDensity; i++) { 1552 if (exts[i].blockCount) { 1553 BlockMarkAllocated(vcb, exts[i].startBlock, exts[i].blockCount); 1554 vcb->vcbFreeBlocks -= exts[i].blockCount; 1555 } 1556 } 1557 MarkVCBDirty(vcb); 1558 } 1559 } 1560 return err; 1561} 1562