1/* 2 * Copyright (c) 1999-2002, 2005, 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: SExtents.c 25 26 Contains: Routines to map file positions to volume positions, and manipulate the extents B-Tree. 27 28 Version: HFS Plus 1.0 29 30 Written by: Dave Heller, Mark Day 31 32 Copyright: � 1996-1999 by Apple Computer, Inc., all rights reserved. 33*/ 34 35 36#include "BTree.h" 37#include "Scavenger.h" 38 39/* 40============================================================ 41Public (Exported) Routines: 42============================================================ 43 DeallocateFile Deallocate all disk space allocated to a specified file. 44 Both forks are deallocated. 45 46 ExtendFileC Allocate more space to a given file. 47 48 49 MapFileBlockC Convert (map) an offset within a given file into a 50 physical disk address. 51 52 TruncateFileC Truncates the disk space allocated to a file. The file 53 space is truncated to a specified new physical EOF, rounded 54 up to the next allocation block boundry. There is an option 55 to truncate to the end of the extent containing the new EOF. 56 57 FlushExtentFile 58 Flush the extents file for a given volume. 59 60 AdjustEOF 61 Copy EOF, physical length, and extent records from one FCB 62 to all other FCBs for that fork. This is used when a file is 63 grown or shrunk as the result of a Write, SetEOF, or Allocate. 64 65 MapLogicalToPhysical 66 Map some position in a file to a volume block number. Also 67 returns the number of contiguous bytes that are mapped there. 68 This is a queued HFSDispatch call that does the equivalent of 69 MapFileBlockC, using a parameter block. 70 71 UpdateExtentRecord 72 If the extent record came from the extents file, write out 73 the updated record; otherwise, copy the updated record into 74 the FCB resident extent record. If the record has no extents, 75 and was in the extents file, then delete the record instead. 76 77 ReleaseExtents 78 Deallocate all allocation blocks in all extents of an extent 79 data record. 80============================================================ 81Internal Routines: 82============================================================ 83 FindExtentRecord 84 Search the extents BTree for a particular extent record. 85 SearchExtentFile 86 Search the FCB and extents file for an extent record that 87 contains a given file position (in bytes). 88 SearchExtentRecord 89 Search a given extent record to see if it contains a given 90 file position (in bytes). Used by SearchExtentFile. 91 TruncateExtents 92 Deallocate blocks and delete extent records for all allocation 93 blocks beyond a certain point in a file. The starting point 94 must be the first file allocation block for some extent record 95 for the file. 96 DeallocateFork 97 Deallocate all allocation blocks belonging to a given fork. 98*/ 99 100enum 101{ 102 kTwoGigSectors = 0x00400000, 103 104 kDataForkType = 0, 105 kResourceForkType = 0xFF, 106 107 kPreviousRecord = -1, 108 109 kSectorSize = 512 // Size of a physical sector 110}; 111 112static OSErr ExtentsToExtDataRec( 113 HFSPlusExtentRecord oldExtents, 114 HFSExtentRecord newExtents); 115 116OSErr FindExtentRecord( 117 const SVCB *vcb, 118 UInt8 forkType, 119 UInt32 fileID, 120 UInt32 startBlock, 121 Boolean allowPrevious, 122 HFSPlusExtentKey *foundKey, 123 HFSPlusExtentRecord foundData, 124 UInt32 *foundHint); 125 126OSErr DeleteExtentRecord( 127 const SVCB *vcb, 128 UInt8 forkType, 129 UInt32 fileID, 130 UInt32 startBlock); 131 132static OSErr CreateExtentRecord( 133 const SVCB *vcb, 134 HFSPlusExtentKey *key, 135 HFSPlusExtentRecord extents, 136 UInt32 *hint); 137 138OSErr GetFCBExtentRecord( 139 const SVCB *vcb, 140 const SFCB *fcb, 141 HFSPlusExtentRecord extents); 142 143static OSErr SetFCBExtentRecord( 144 const SVCB *vcb, 145 SFCB *fcb, 146 HFSPlusExtentRecord extents); 147 148static OSErr SearchExtentFile( 149 const SVCB *vcb, 150 const SFCB *fcb, 151 UInt64 filePosition, 152 HFSPlusExtentKey *foundExtentKey, 153 HFSPlusExtentRecord foundExtentData, 154 UInt32 *foundExtentDataIndex, 155 UInt32 *extentBTreeHint, 156 UInt32 *endingFABNPlusOne ); 157 158static OSErr SearchExtentRecord( 159 const SVCB *vcb, 160 UInt32 searchFABN, 161 const HFSPlusExtentRecord extentData, 162 UInt32 extentDataStartFABN, 163 UInt32 *foundExtentDataOffset, 164 UInt32 *endingFABNPlusOne, 165 Boolean *noMoreExtents); 166 167#if 0 168static OSErr DeallocateFork( 169 SVCB *vcb, 170 HFSCatalogNodeID fileID, 171 UInt8 forkType, 172 HFSPlusExtentRecord catalogExtents, 173 Boolean * recordDeleted); 174 175static OSErr TruncateExtents( 176 SVCB *vcb, 177 UInt8 forkType, 178 UInt32 fileID, 179 UInt32 startBlock, 180 Boolean * recordDeleted); 181#endif 182 183static OSErr MapFileBlockFromFCB( 184 const SVCB *vcb, 185 const SFCB *fcb, 186 UInt64 offset, // Desired offset in bytes from start of file 187 UInt32 *firstFABN, // FABN of first block of found extent 188 UInt32 *firstBlock, // Corresponding allocation block number 189 UInt32 *nextFABN); // FABN of block after end of extent 190 191static Boolean ExtentsAreIntegral( 192 const HFSPlusExtentRecord extentRecord, 193 UInt32 mask, 194 UInt32 *blocksChecked, 195 Boolean *checkedLastExtent); 196 197//_________________________________________________________________________________ 198// 199// Routine: FindExtentRecord 200// 201// Purpose: Search the extents BTree for an extent record matching the given 202// FileID, fork, and starting file allocation block number. 203// 204// Inputs: 205// vcb Volume to search 206// forkType 0 = data fork, -1 = resource fork 207// fileID File's FileID (HFSCatalogNodeID) 208// startBlock Starting file allocation block number 209// allowPrevious If the desired record isn't found and this flag is set, 210// then see if the previous record belongs to the same fork. 211// If so, then return it. 212// 213// Outputs: 214// foundKey The key data for the record actually found 215// foundData The extent record actually found (NOTE: on an HFS volume, the 216// fourth entry will be zeroes. 217// foundHint The BTree hint to find the node again 218//_________________________________________________________________________________ 219OSErr FindExtentRecord( 220 const SVCB *vcb, 221 UInt8 forkType, 222 UInt32 fileID, 223 UInt32 startBlock, 224 Boolean allowPrevious, 225 HFSPlusExtentKey *foundKey, 226 HFSPlusExtentRecord foundData, 227 UInt32 *foundHint) 228{ 229 OSErr err; 230 UInt16 foundSize; 231 232 err = noErr; 233 234 if (vcb->vcbSignature == kHFSSigWord) { 235 HFSExtentKey key; 236 HFSExtentKey extentKey; 237 HFSExtentRecord extentData; 238 239 key.keyLength = kHFSExtentKeyMaximumLength; 240 key.forkType = forkType; 241 key.fileID = fileID; 242 key.startBlock = startBlock; 243 244 err = SearchBTreeRecord(vcb->vcbExtentsFile, &key, kNoHint, &extentKey, &extentData, 245 &foundSize, foundHint); 246 247 if (err == btNotFound && allowPrevious) { 248 err = GetBTreeRecord(vcb->vcbExtentsFile, kPreviousRecord, &extentKey, &extentData, 249 &foundSize, foundHint); 250 251 // A previous record may not exist, so just return btNotFound (like we would if 252 // it was for the wrong file/fork). 253 if (err == (OSErr) fsBTStartOfIterationErr) //�� fsBTStartOfIterationErr is type unsigned long 254 err = btNotFound; 255 256 if (err == noErr) { 257 // Found a previous record. Does it belong to the same fork of the same file? 258 if (extentKey.fileID != fileID || extentKey.forkType != forkType) 259 err = btNotFound; 260 } 261 } 262 263 if (err == noErr) { 264 UInt16 i; 265 266 // Copy the found key back for the caller 267 foundKey->keyLength = kHFSPlusExtentKeyMaximumLength; 268 foundKey->forkType = extentKey.forkType; 269 foundKey->pad = 0; 270 foundKey->fileID = extentKey.fileID; 271 foundKey->startBlock = extentKey.startBlock; 272 273 // Copy the found data back for the caller 274 foundData[0].startBlock = extentData[0].startBlock; 275 foundData[0].blockCount = extentData[0].blockCount; 276 foundData[1].startBlock = extentData[1].startBlock; 277 foundData[1].blockCount = extentData[1].blockCount; 278 foundData[2].startBlock = extentData[2].startBlock; 279 foundData[2].blockCount = extentData[2].blockCount; 280 281 for (i = 3; i < kHFSPlusExtentDensity; ++i) 282 { 283 foundData[i].startBlock = 0; 284 foundData[i].blockCount = 0; 285 } 286 } 287 } 288 else { // HFS Plus volume 289 HFSPlusExtentKey key; 290 HFSPlusExtentKey extentKey; 291 HFSPlusExtentRecord extentData; 292 293 key.keyLength = kHFSPlusExtentKeyMaximumLength; 294 key.forkType = forkType; 295 key.pad = 0; 296 key.fileID = fileID; 297 key.startBlock = startBlock; 298 299 err = SearchBTreeRecord(vcb->vcbExtentsFile, &key, kNoHint, &extentKey, &extentData, 300 &foundSize, foundHint); 301 302 if (err == btNotFound && allowPrevious) { 303 err = GetBTreeRecord(vcb->vcbExtentsFile, kPreviousRecord, &extentKey, &extentData, 304 &foundSize, foundHint); 305 306 // A previous record may not exist, so just return btNotFound (like we would if 307 // it was for the wrong file/fork). 308 if (err == (OSErr) fsBTStartOfIterationErr) //�� fsBTStartOfIterationErr is type unsigned long 309 err = btNotFound; 310 311 if (err == noErr) { 312 // Found a previous record. Does it belong to the same fork of the same file? 313 if (extentKey.fileID != fileID || extentKey.forkType != forkType) 314 err = btNotFound; 315 } 316 } 317 318 if (err == noErr) { 319 // Copy the found key back for the caller 320 CopyMemory(&extentKey, foundKey, sizeof(HFSPlusExtentKey)); 321 // Copy the found data back for the caller 322 CopyMemory(&extentData, foundData, sizeof(HFSPlusExtentRecord)); 323 } 324 } 325 326 return err; 327} 328 329 330 331static OSErr CreateExtentRecord( 332 const SVCB *vcb, 333 HFSPlusExtentKey *key, 334 HFSPlusExtentRecord extents, 335 UInt32 *hint) 336{ 337 OSErr err; 338 339 err = noErr; 340 341 if (vcb->vcbSignature == kHFSSigWord) { 342 HFSExtentKey hfsKey; 343 HFSExtentRecord data; 344 345 hfsKey.keyLength = kHFSExtentKeyMaximumLength; 346 hfsKey.forkType = key->forkType; 347 hfsKey.fileID = key->fileID; 348 hfsKey.startBlock = key->startBlock; 349 350 err = ExtentsToExtDataRec(extents, data); 351 if (err == noErr) 352 err = InsertBTreeRecord(vcb->vcbExtentsFile, &hfsKey, data, sizeof(HFSExtentRecord), hint); 353 } 354 else { // HFS Plus volume 355 err = InsertBTreeRecord(vcb->vcbExtentsFile, key, extents, sizeof(HFSPlusExtentRecord), hint); 356 } 357 358 return err; 359} 360 361 362OSErr DeleteExtentRecord( 363 const SVCB *vcb, 364 UInt8 forkType, 365 UInt32 fileID, 366 UInt32 startBlock) 367{ 368 OSErr err; 369 370 err = noErr; 371 372 if (vcb->vcbSignature == kHFSSigWord) { 373 HFSExtentKey key; 374 375 key.keyLength = kHFSExtentKeyMaximumLength; 376 key.forkType = forkType; 377 key.fileID = fileID; 378 key.startBlock = startBlock; 379 380 err = DeleteBTreeRecord( vcb->vcbExtentsFile, &key ); 381 } 382 else { // HFS Plus volume 383 HFSPlusExtentKey key; 384 385 key.keyLength = kHFSPlusExtentKeyMaximumLength; 386 key.forkType = forkType; 387 key.pad = 0; 388 key.fileID = fileID; 389 key.startBlock = startBlock; 390 391 err = DeleteBTreeRecord( vcb->vcbExtentsFile, &key ); 392 } 393 394 return err; 395} 396 397 398 399//_________________________________________________________________________________ 400// 401// Routine: MapFileBlock 402// 403// Function: Maps a file position into a physical disk address. 404// 405// Input: A2.L - VCB pointer 406// (A1,D1.W) - FCB pointer 407// D4.L - number of bytes desired 408// D5.L - file position (byte address) 409// 410// Output: D3.L - physical start block 411// D6.L - number of contiguous bytes available (up to D4 bytes) 412// D0.L - result code <01Oct85> 413// 0 = ok 414// FXRangeErr = file position beyond mapped range <17Oct85> 415// FXOvFlErr = extents file overflow <17Oct85> 416// other = error <17Oct85> 417// 418// Called By: Log2Phys (read/write in place), Cache (map a file block). 419//_________________________________________________________________________________ 420 421OSErr MapFileBlockC ( 422 SVCB *vcb, // volume that file resides on 423 SFCB *fcb, // FCB of file 424 UInt32 numberOfBytes, // number of contiguous bytes desired 425 UInt64 sectorOffset, // starting offset within file (in 512-byte sectors) 426 UInt64 *startSector, // first 512-byte volume sector (NOT an allocation block) 427 UInt32 *availableBytes) // number of contiguous bytes (up to numberOfBytes) 428{ 429 OSErr err; 430 UInt32 allocBlockSize; // Size of the volume's allocation block, in sectors 431 HFSPlusExtentKey foundKey; 432 HFSPlusExtentRecord foundData; 433 UInt32 foundIndex; 434 UInt32 hint; 435 UInt32 firstFABN = 0; // file allocation block of first block in found extent 436 UInt32 nextFABN; // file allocation block of block after end of found extent 437 UInt64 dataEnd; // (offset) end of range that is contiguous (in sectors) 438 UInt32 startBlock = 0; // volume allocation block corresponding to firstFABN 439 UInt64 temp; 440 441 442// LogStartTime(kTraceMapFileBlock); 443 444 allocBlockSize = vcb->vcbBlockSize >> kSectorShift; 445 446 err = MapFileBlockFromFCB(vcb, fcb, sectorOffset, &firstFABN, &startBlock, &nextFABN); 447 if (err != noErr) { 448 err = SearchExtentFile(vcb, fcb, sectorOffset, &foundKey, foundData, &foundIndex, &hint, &nextFABN); 449 if (err == noErr) { 450 startBlock = foundData[foundIndex].startBlock; 451 firstFABN = nextFABN - foundData[foundIndex].blockCount; 452 } 453 } 454 455 if (err != noErr) 456 { 457 // LogEndTime(kTraceMapFileBlock, err); 458 459 return err; 460 } 461 462 // 463 // Determine the end of the available space. It will either be the end of the extent, 464 // or the file's PEOF, whichever is smaller. 465 // 466 467 // Get fork's physical size, in sectors 468 temp = fcb->fcbPhysicalSize >> kSectorShift; 469 dataEnd = (UInt64) nextFABN * allocBlockSize; // Assume valid data through end of this extent 470 if (temp < dataEnd) // Is PEOF shorter? 471 dataEnd = temp; // Yes, so only map up to PEOF 472 473 // 474 // Compute the absolute sector number that contains the offset of the given file 475 // 476 temp = sectorOffset - ((UInt64) firstFABN * allocBlockSize); // offset in sectors from start of this extent 477 temp += (UInt64)startBlock * (UInt64)allocBlockSize; // offset in sectors from start of allocation block space 478 if (vcb->vcbSignature == kHFSPlusSigWord) 479 temp += vcb->vcbEmbeddedOffset/512; // offset into the wrapper 480 else 481 temp += vcb->vcbAlBlSt; // offset in sectors from start of volume 482 483 // Return the desired sector for file position "offset" 484 *startSector = temp; 485 486 // 487 // Determine the number of contiguous sectors until the end of the extent 488 // (or the amount they asked for, whichever comes first). In any case, 489 // we never map more than 2GB per call. 490 // 491 temp = dataEnd - sectorOffset; 492 if (temp >= kTwoGigSectors) 493 temp = kTwoGigSectors-1; // never map more than 2GB per call 494 temp <<= kSectorShift; // convert sectors to bytes 495 if (temp > numberOfBytes) 496 *availableBytes = numberOfBytes; // more there than they asked for, so pin the output 497 else 498 *availableBytes = temp; 499 500// LogEndTime(kTraceMapFileBlock, noErr); 501 502 return noErr; 503} 504 505 506//������������������������������������������������������������������������������� 507// Routine: ReleaseExtents 508// 509// Function: Release the extents of a single extent data record. 510//������������������������������������������������������������������������������� 511 512#if 1 513OSErr ReleaseExtents( 514 SVCB *vcb, 515 const HFSPlusExtentRecord extentRecord, 516 UInt32 *numReleasedAllocationBlocks, 517 Boolean *releasedLastExtent) 518{ 519 UInt32 extentIndex; 520 UInt32 numberOfExtents; 521 OSErr err = noErr; 522 523 *numReleasedAllocationBlocks = 0; 524 *releasedLastExtent = false; 525 526 if (vcb->vcbSignature == kHFSPlusSigWord) 527 numberOfExtents = kHFSPlusExtentDensity; 528 else 529 numberOfExtents = kHFSExtentDensity; 530 531 for( extentIndex = 0; extentIndex < numberOfExtents; extentIndex++) 532 { 533 UInt32 numAllocationBlocks; 534 535 // Loop over the extent record and release the blocks associated with each extent. 536 537 numAllocationBlocks = extentRecord[extentIndex].blockCount; 538 if ( numAllocationBlocks == 0 ) 539 { 540 *releasedLastExtent = true; 541 break; 542 } 543 544 err = ReleaseBitmapBits( extentRecord[extentIndex].startBlock, numAllocationBlocks ); 545 if ( err != noErr ) 546 break; 547 548 *numReleasedAllocationBlocks += numAllocationBlocks; // bump FABN to beg of next extent 549 } 550 551 return( err ); 552} 553#endif 554 555 556//������������������������������������������������������������������������������� 557// Routine: TruncateExtents 558// 559// Purpose: Delete extent records whose starting file allocation block number 560// is greater than or equal to a given starting block number. The 561// allocation blocks represented by the extents are deallocated. 562// 563// Inputs: 564// vcb Volume to operate on 565// fileID Which file to operate on 566// startBlock Starting file allocation block number for first extent 567// record to delete. 568// 569// Outputs: 570// recordDeleted Set to true if any extents B-tree record was deleted. 571// Unchanged otherwise. 572//������������������������������������������������������������������������������� 573 574static OSErr TruncateExtents( 575 SVCB *vcb, 576 UInt8 forkType, 577 UInt32 fileID, 578 UInt32 startBlock, 579 Boolean * recordDeleted) 580{ 581 OSErr err; 582 Boolean releasedLastExtent; 583 UInt32 numberExtentsReleased; 584 UInt32 hint; 585 HFSPlusExtentKey key; 586 HFSPlusExtentRecord extents; 587 588 while (true) { 589 err = FindExtentRecord(vcb, forkType, fileID, startBlock, false, &key, extents, &hint); 590 if (err != noErr) { 591 if (err == btNotFound) 592 err = noErr; 593 break; 594 } 595 596 err = ReleaseExtents( vcb, extents, &numberExtentsReleased, &releasedLastExtent ); 597 if (err != noErr) break; 598 599 err = DeleteExtentRecord(vcb, forkType, fileID, startBlock); 600 if (err != noErr) break; 601 602 *recordDeleted = true; // We did delete a record 603 startBlock += numberExtentsReleased; 604 } 605 606 return err; 607} 608 609 610//������������������������������������������������������������������������������� 611// Routine: DeallocateFork 612// 613// Function: De-allocates all disk space allocated to a specified fork. 614//������������������������������������������������������������������������������� 615static OSErr DeallocateFork( 616 SVCB *vcb, 617 HFSCatalogNodeID fileID, 618 UInt8 forkType, 619 HFSPlusExtentRecord catalogExtents, 620 Boolean * recordDeleted) // set to true if any record was deleted 621{ 622 OSErr err; 623 UInt32 numReleasedAllocationBlocks; 624 Boolean releasedLastExtent; 625 626 // Release the catalog extents 627 err = ReleaseExtents( vcb, catalogExtents, &numReleasedAllocationBlocks, &releasedLastExtent ); 628 629 // Release the extra extents, if present 630 if (err == noErr && !releasedLastExtent) 631 err = TruncateExtents(vcb, forkType, fileID, numReleasedAllocationBlocks, recordDeleted); 632 633 return( err ); 634} 635 636 637//������������������������������������������������������������������������������� 638// Routine: FlushExtentFile 639// 640// Function: Flushes the extent file for a specified volume 641//������������������������������������������������������������������������������� 642 643OSErr FlushExtentFile( SVCB *vcb ) 644{ 645 OSErr err; 646 647 err = BTFlushPath(vcb->vcbExtentsFile); 648 if ( err == noErr ) 649 { 650 // If the FCB for the extent "file" is dirty, mark the VCB as dirty. 651 652 if( ( vcb->vcbExtentsFile->fcbFlags & fcbModifiedMask ) != 0 ) 653 { 654 (void) MarkVCBDirty( vcb ); 655 err = FlushVolumeControlBlock( vcb ); 656 } 657 } 658 659 return( err ); 660} 661 662 663//������������������������������������������������������������������������������� 664// Routine: DeallocateFile 665// 666// Function: De-allocates all disk space allocated to a specified file. 667// The space occupied by both forks is deallocated. 668// 669//������������������������������������������������������������������������������� 670 671OSErr DeallocateFile(SVCB *vcb, CatalogRecord * fileRec) 672{ 673 int i; 674 OSErr errDF, errRF; 675 Boolean recordDeleted = false; 676 677 errDF = errRF = 0; 678 679 if (fileRec->recordType == kHFSFileRecord) { 680 HFSPlusExtentRecord dataForkExtents; 681 HFSPlusExtentRecord rsrcForkExtents; 682 683 for (i = 0; i < kHFSExtentDensity; ++i) { 684 dataForkExtents[i].startBlock = 685 (UInt32) (fileRec->hfsFile.dataExtents[i].startBlock); 686 dataForkExtents[i].blockCount = 687 (UInt32) (fileRec->hfsFile.dataExtents[i].blockCount); 688 689 rsrcForkExtents[i].startBlock = 690 (UInt32) (fileRec->hfsFile.rsrcExtents[i].startBlock); 691 rsrcForkExtents[i].blockCount = 692 (UInt32) (fileRec->hfsFile.rsrcExtents[i].blockCount); 693 } 694 ClearMemory(&dataForkExtents[i].startBlock, 695 sizeof(HFSPlusExtentRecord) - sizeof(HFSExtentRecord)); 696 697 ClearMemory(&rsrcForkExtents[i].startBlock, 698 sizeof(HFSPlusExtentRecord) - sizeof(HFSExtentRecord)); 699 700 errDF = DeallocateFork(vcb, fileRec->hfsFile.fileID, kDataForkType, 701 dataForkExtents, &recordDeleted ); 702 703 errRF = DeallocateFork(vcb, fileRec->hfsFile.fileID, kResourceForkType, 704 rsrcForkExtents, &recordDeleted ); 705 } 706 else if (fileRec->recordType == kHFSPlusFileRecord) { 707 errDF = DeallocateFork(vcb, fileRec->hfsPlusFile.fileID, kDataForkType, 708 fileRec->hfsPlusFile.dataFork.extents, &recordDeleted ); 709 710 errRF = DeallocateFork(vcb, fileRec->hfsPlusFile.fileID, kResourceForkType, 711 fileRec->hfsPlusFile.resourceFork.extents, &recordDeleted ); 712 } 713 714 if (recordDeleted) 715 (void) FlushExtentFile(vcb); 716 717 MarkVCBDirty(vcb); 718 719 return (errDF ? errDF : errRF); 720} 721 722 723//_________________________________________________________________________________ 724// 725// Routine: Extendfile 726// 727// Function: Extends the disk space allocated to a file. 728// 729// Input: A2.L - VCB pointer 730// A1.L - pointer to FCB array 731// D1.W - file refnum 732// D3.B - option flags 733// kEFContigMask - force contiguous allocation 734// kEFAllMask - allocate all requested bytes or none 735// NOTE: You may not set both options. 736// D4.L - number of additional bytes to allocate 737// 738// Output: D0.W - result code 739// 0 = ok 740// -n = IO error 741// D6.L - number of bytes allocated 742// 743// Called by: FileAloc,FileWrite,SetEof 744// 745// Note: ExtendFile updates the PEOF in the FCB. 746//_________________________________________________________________________________ 747 748OSErr ExtendFileC ( 749 SVCB *vcb, // volume that file resides on 750 SFCB *fcb, // FCB of file to truncate 751 UInt32 sectorsToAdd, // number of sectors to allocate 752 UInt32 flags, // EFContig and/or EFAll 753 UInt32 *actualSectorsAdded)// number of bytes actually allocated 754{ 755 OSErr err; 756 Boolean wantContig; 757 Boolean needsFlush; 758 UInt32 sectorsPerBlock; 759 UInt32 blocksToAdd; // number of blocks we'd like to add 760 UInt32 blocksPerClump; // number of blocks in clump size 761 UInt32 maxBlocksToAdd; // max blocks we want to add 762 UInt32 eofBlocks; // current EOF in blocks 763 HFSPlusExtentKey foundKey; // from SearchExtentFile 764 HFSPlusExtentRecord foundData; 765 UInt32 foundIndex; // from SearchExtentFile 766 UInt32 hint; // from SearchExtentFile 767 UInt32 nextBlock; // from SearchExtentFile 768 UInt32 startBlock; 769 UInt32 actualStartBlock; 770 UInt32 actualNumBlocks; 771 UInt32 numExtentsPerRecord; 772 UInt32 blocksAdded; 773 774 needsFlush = false; // Assume the B-tree header doesn't need to be updated 775 blocksAdded = 0; 776 *actualSectorsAdded = 0; 777 778 if (vcb->vcbSignature == kHFSPlusSigWord) 779 numExtentsPerRecord = kHFSPlusExtentDensity; 780 else 781 numExtentsPerRecord = kHFSExtentDensity; 782 783 // 784 // Round up the request to whole allocation blocks 785 // 786 sectorsPerBlock = vcb->vcbBlockSize >> kSectorShift; 787 blocksToAdd = DivideAndRoundUp(sectorsToAdd, sectorsPerBlock); 788 789 // 790 // Determine the physical EOF in allocation blocks 791 // 792 eofBlocks = fcb->fcbPhysicalSize / vcb->vcbBlockSize; 793 794 // 795 // Make sure the request won't make the file too big (>=2GB). 796 // [2350148] Always limit HFS files. 797 // �� Shouldn't really fail if allOrNothing is false 798 // �� Adjust for clump size here? 799 // 800 if ( vcb->vcbSignature == kHFSPlusSigWord ) 801 { 802 // Allow it to grow beyond 2GB. 803 } 804 else 805 { 806 UInt32 maxFileBlocks; // max legal EOF, in blocks 807 maxFileBlocks = (kTwoGigSectors-1) / sectorsPerBlock; 808 if (blocksToAdd > maxFileBlocks || (blocksToAdd + eofBlocks) > maxFileBlocks) { 809 err = fileBoundsErr; 810 goto ErrorExit; 811 } 812 } 813 814 // 815 // If allocation is all-or-nothing, then make sure there 816 // are enough free blocks. (A quick test) 817 // 818 if ((flags & kEFAllMask) && blocksToAdd > vcb->vcbFreeBlocks) { 819 err = dskFulErr; 820 goto ErrorExit; 821 } 822 823 // 824 // There may be blocks allocated beyond the physical EOF 825 // (because we allocated the rest of the clump size, or 826 // because of a PBAllocate or PBAllocContig call). 827 // If these extra blocks exist, then use them to satisfy 828 // part or all of the request. 829 // 830 // �� What, if anything, would break if the physical EOF always 831 // �� represented ALL extents allocated to the file (including 832 // �� the clump size roundup)? 833 // 834 // Note: (blocks * sectorsPerBlock - 1) is the sector offset 835 // of the last sector in the last block. 836 // 837 err = SearchExtentFile(vcb, fcb, (eofBlocks+blocksToAdd) * sectorsPerBlock - 1, &foundKey, foundData, &foundIndex, &hint, &nextBlock); 838 if (err == noErr) { 839 // Enough blocks are already allocated. Just update the FCB to reflect the new length. 840 eofBlocks += blocksToAdd; // new EOF, in blocks 841 blocksAdded += blocksToAdd; 842 goto Exit; 843 } 844 if (err != fxRangeErr) // Any real error? 845 goto ErrorExit; // Yes, so exit immediately 846 847 // 848 // There wasn't enough already allocated. But there might have been 849 // a few allocated blocks beyond the physical EOF. So, set the physical 850 // EOF to match the end of the last extent. 851 // 852 if (nextBlock > eofBlocks) { 853 // There were (nextBlock - eofBlocks) extra blocks past physical EOF 854 blocksAdded += nextBlock - eofBlocks; 855 blocksToAdd -= nextBlock - eofBlocks; 856 eofBlocks = nextBlock; 857 } 858 859 // 860 // We still need to allocate more blocks. 861 // 862 // First try a contiguous allocation (of the whole amount). 863 // If that fails, get whatever we can. 864 // If forceContig, then take whatever we got 865 // else, keep getting bits and pieces (non-contig) 866 // 867 // �� Need to do clump size calculations 868 // 869 blocksPerClump = fcb->fcbClumpSize / vcb->vcbBlockSize; 870 if (blocksPerClump == 0) 871 blocksPerClump = 1; 872 873 err = noErr; 874 wantContig = true; 875 do { 876 // Make maxBlocksToAdd equal to blocksToAdd rounded up to a multiple 877 // of the file's clump size. This gives the file room to grow some 878 // more without fragmenting. 879 if (flags & kEFNoClumpMask) { 880 // Caller said not to round up, so only allocate what was asked for. 881 maxBlocksToAdd = blocksToAdd; 882 } 883 else { 884 // Round up to multiple of clump size 885 maxBlocksToAdd = DivideAndRoundUp(blocksToAdd, blocksPerClump); 886 maxBlocksToAdd *= blocksPerClump; 887 } 888 889 // Try to allocate the new space contiguous with the end of the previous 890 // extent. If this succeeds, the last extent grows and the file does not 891 // become any more fragmented. 892 startBlock = foundData[foundIndex].startBlock + foundData[foundIndex].blockCount; 893 err = BlockAllocate(vcb, startBlock, blocksToAdd, maxBlocksToAdd, wantContig, &actualStartBlock, &actualNumBlocks); 894 if (err == dskFulErr) { 895 if (flags & kEFContigMask) 896 break; // AllocContig failed because not enough contiguous space 897 if (wantContig) { 898 // Couldn't get one big chunk, so get whatever we can. 899 err = noErr; 900 wantContig = false; 901 continue; 902 } 903 if (actualNumBlocks != 0) 904 err = noErr; 905 } 906 if (err == noErr) { 907 // Add the new extent to the existing extent record, or create a new one. 908 if (actualStartBlock == startBlock) { 909 // We grew the file's last extent, so just adjust the number of blocks. 910 foundData[foundIndex].blockCount += actualNumBlocks; 911 err = UpdateExtentRecord(vcb, fcb, &foundKey, foundData, hint); 912 if (err != noErr) break; 913 } 914 else { 915 UInt16 i; 916 917 // Need to add a new extent. See if there is room in the current record. 918 if (foundData[foundIndex].blockCount != 0) // Is current extent free to use? 919 ++foundIndex; // No, so use the next one. 920 if (foundIndex == numExtentsPerRecord) { 921 // This record is full. Need to create a new one. 922 if (fcb->fcbFileID == kHFSExtentsFileID || (flags & kEFNoExtOvflwMask)) { 923 (void) BlockDeallocate(vcb, actualStartBlock, actualNumBlocks); 924 err = fxOvFlErr; // Oops. Can't extend extents file past first record. 925 break; 926 } 927 928 foundKey.keyLength = kHFSPlusExtentKeyMaximumLength; 929 if (fcb->fcbFlags & fcbResourceMask) 930 foundKey.forkType = kResourceForkType; 931 else 932 foundKey.forkType = kDataForkType; 933 foundKey.pad = 0; 934 foundKey.fileID = fcb->fcbFileID; 935 foundKey.startBlock = nextBlock; 936 937 foundData[0].startBlock = actualStartBlock; 938 foundData[0].blockCount = actualNumBlocks; 939 940 // zero out remaining extents... 941 for (i = 1; i < kHFSPlusExtentDensity; ++i) 942 { 943 foundData[i].startBlock = 0; 944 foundData[i].blockCount = 0; 945 } 946 947 foundIndex = 0; 948 949 err = CreateExtentRecord(vcb, &foundKey, foundData, &hint); 950 if (err == fxOvFlErr) { 951 // We couldn't create an extent record because extents B-tree 952 // couldn't grow. Dellocate the extent just allocated and 953 // return a disk full error. 954 (void) BlockDeallocate(vcb, actualStartBlock, actualNumBlocks); 955 err = dskFulErr; 956 } 957 if (err != noErr) break; 958 959 needsFlush = true; // We need to update the B-tree header 960 } 961 else { 962 // Add a new extent into this record and update. 963 foundData[foundIndex].startBlock = actualStartBlock; 964 foundData[foundIndex].blockCount = actualNumBlocks; 965 err = UpdateExtentRecord(vcb, fcb, &foundKey, foundData, hint); 966 if (err != noErr) break; 967 } 968 } 969 970 // Figure out how many bytes were actually allocated. 971 // NOTE: BlockAllocate could have allocated more than the minimum 972 // we asked for (up to our requested maximum). 973 // Don't set the PEOF beyond what our client asked for. 974 nextBlock += actualNumBlocks; 975 if (actualNumBlocks > blocksToAdd) { 976 blocksAdded += blocksToAdd; 977 eofBlocks += blocksToAdd; 978 blocksToAdd = 0; 979 } 980 else { 981 blocksAdded += actualNumBlocks; 982 blocksToAdd -= actualNumBlocks; 983 eofBlocks += actualNumBlocks; 984 } 985 986 // If contiguous allocation was requested, then we've already got one contiguous 987 // chunk. If we didn't get all we wanted, then adjust the error to disk full. 988 if (flags & kEFContigMask) { 989 if (blocksToAdd != 0) 990 err = dskFulErr; 991 break; // We've already got everything that's contiguous 992 } 993 } 994 } while (err == noErr && blocksToAdd); 995 996ErrorExit: 997Exit: 998 *actualSectorsAdded = blocksAdded * sectorsPerBlock; 999 if (blocksAdded) { 1000 fcb->fcbPhysicalSize = (UInt64)eofBlocks * (UInt64)vcb->vcbBlockSize; 1001 fcb->fcbFlags |= fcbModifiedMask; 1002 } 1003 1004 // [2355121] If we created a new extent record, then update the B-tree header 1005 if (needsFlush) 1006 (void) FlushExtentFile(vcb); 1007 1008 return err; 1009} 1010 1011 1012 1013//_________________________________________________________________________________ 1014// 1015// Routine: TruncateFileC 1016// 1017// Function: Truncates the disk space allocated to a file. The file space is 1018// truncated to a specified new PEOF rounded up to the next allocation 1019// block boundry. If the 'TFTrunExt' option is specified, the file is 1020// truncated to the end of the extent containing the new PEOF. 1021// 1022// Input: A2.L - VCB pointer 1023// A1.L - pointer to FCB array 1024// D1.W - file refnum 1025// D2.B - option flags 1026// TFTrunExt - truncate to the extent containing new PEOF 1027// D3.L - new PEOF 1028// 1029// Output: D0.W - result code 1030// 0 = ok 1031// -n = IO error 1032// 1033// Note: TruncateFile updates the PEOF in the FCB. 1034//_________________________________________________________________________________ 1035 1036#if 0 1037OSErr TruncateFileC ( 1038 SVCB *vcb, // volume that file resides on 1039 SFCB *fcb, // FCB of file to truncate 1040 UInt32 eofSectors, // new physical size for file 1041 Boolean truncateToExtent) // if true, truncate to end of extent containing newPEOF 1042{ 1043 OSErr err; 1044 UInt32 nextBlock; // next file allocation block to consider 1045 UInt32 startBlock; // Physical (volume) allocation block number of start of a range 1046 UInt32 physNumBlocks; // Number of allocation blocks in file (according to PEOF) 1047 UInt32 numBlocks; 1048 HFSPlusExtentKey key; // key for current extent record; key->keyLength == 0 if FCB's extent record 1049 UInt32 hint; // BTree hint corresponding to key 1050 HFSPlusExtentRecord extentRecord; 1051 UInt32 extentIndex; 1052 UInt32 extentNextBlock; 1053 UInt32 numExtentsPerRecord; 1054 UInt32 sectorsPerBlock; 1055 UInt8 forkType; 1056 Boolean extentChanged; // true if we actually changed an extent 1057 Boolean recordDeleted; // true if an extent record got deleted 1058 1059 recordDeleted = false; 1060 sectorsPerBlock = vcb->vcbBlockSize >> kSectorShift; 1061 1062 if (vcb->vcbSignature == kHFSPlusSigWord) 1063 numExtentsPerRecord = kHFSPlusExtentDensity; 1064 else 1065 numExtentsPerRecord = kHFSExtentDensity; 1066 1067 if (fcb->fcbFlags & fcbResourceMask) 1068 forkType = kResourceForkType; 1069 else 1070 forkType = kDataForkType; 1071 1072 // Compute number of allocation blocks currently in file 1073 physNumBlocks = fcb->fcbPhysicalSize / vcb->vcbBlockSize; 1074 1075 // 1076 // Round newPEOF up to a multiple of the allocation block size. If new size is 1077 // two gigabytes or more, then round down by one allocation block (??? really? 1078 // shouldn't that be an error?). 1079 // 1080 nextBlock = DivideAndRoundUp(eofSectors, sectorsPerBlock); // number of allocation blocks to remain in file 1081 eofSectors = nextBlock * sectorsPerBlock; // rounded up to multiple of block size 1082 if ((fcb->fcbFlags & fcbLargeFileMask) == 0 && eofSectors >= kTwoGigSectors) { 1083 #if DEBUG_BUILD 1084 DebugStr("\pHFS: Trying to truncate a file to 2GB or more"); 1085 #endif 1086 err = fileBoundsErr; 1087 goto ErrorExit; 1088 } 1089 1090 // 1091 // Update FCB's length 1092 // 1093 fcb->fcbPhysicalSize = (UInt64)nextBlock * (UInt64)vcb->vcbBlockSize; 1094 fcb->fcbFlags |= fcbModifiedMask; 1095 1096 // 1097 // If the new PEOF is 0, then truncateToExtent has no meaning (we should always deallocate 1098 // all storage). 1099 // 1100 if (eofSectors == 0) { 1101 int i; 1102 1103 // Find the catalog extent record 1104 err = GetFCBExtentRecord(vcb, fcb, extentRecord); 1105 if (err != noErr) goto ErrorExit; // got some error, so return it 1106 1107 // Deallocate all the extents for this fork 1108 err = DeallocateFork(vcb, fcb->fcbFileID, forkType, extentRecord, &recordDeleted); 1109 if (err != noErr) goto ErrorExit; // got some error, so return it 1110 1111 // Update the catalog extent record (making sure it's zeroed out) 1112 if (err == noErr) { 1113 for (i=0; i < numExtentsPerRecord; i++) { 1114 extentRecord[i].startBlock = 0; 1115 extentRecord[i].blockCount = 0; 1116 } 1117 } 1118 err = SetFCBExtentRecord((VCB *) vcb, fcb, extentRecord); 1119 goto Done; 1120 } 1121 1122 // 1123 // Find the extent containing byte (peof-1). This is the last extent we'll keep. 1124 // (If truncateToExtent is true, we'll keep the whole extent; otherwise, we'll only 1125 // keep up through peof). The search will tell us how many allocation blocks exist 1126 // in the found extent plus all previous extents. 1127 // 1128 err = SearchExtentFile(vcb, fcb, eofSectors-1, &key, extentRecord, &extentIndex, &hint, &extentNextBlock); 1129 if (err != noErr) goto ErrorExit; 1130 1131 extentChanged = false; // haven't changed the extent yet 1132 1133 if (!truncateToExtent) { 1134 // 1135 // Shorten this extent. It may be the case that the entire extent gets 1136 // freed here. 1137 // 1138 numBlocks = extentNextBlock - nextBlock; // How many blocks in this extent to free up 1139 if (numBlocks != 0) { 1140 // Compute first volume allocation block to free 1141 startBlock = extentRecord[extentIndex].startBlock + extentRecord[extentIndex].blockCount - numBlocks; 1142 // Free the blocks in bitmap 1143 err = BlockDeallocate(vcb, startBlock, numBlocks); 1144 if (err != noErr) goto ErrorExit; 1145 // Adjust length of this extent 1146 extentRecord[extentIndex].blockCount -= numBlocks; 1147 // If extent is empty, set start block to 0 1148 if (extentRecord[extentIndex].blockCount == 0) 1149 extentRecord[extentIndex].startBlock = 0; 1150 // Remember that we changed the extent record 1151 extentChanged = true; 1152 } 1153 } 1154 1155 // 1156 // Now move to the next extent in the record, and set up the file allocation block number 1157 // 1158 nextBlock = extentNextBlock; // Next file allocation block to free 1159 ++extentIndex; // Its index within the extent record 1160 1161 // 1162 // Release all following extents in this extent record. Update the record. 1163 // 1164 while (extentIndex < numExtentsPerRecord && extentRecord[extentIndex].blockCount != 0) { 1165 numBlocks = extentRecord[extentIndex].blockCount; 1166 // Deallocate this extent 1167 err = BlockDeallocate(vcb, extentRecord[extentIndex].startBlock, numBlocks); 1168 if (err != noErr) goto ErrorExit; 1169 // Update next file allocation block number 1170 nextBlock += numBlocks; 1171 // Zero out start and length of this extent to delete it from record 1172 extentRecord[extentIndex].startBlock = 0; 1173 extentRecord[extentIndex].blockCount = 0; 1174 // Remember that we changed an extent 1175 extentChanged = true; 1176 // Move to next extent in record 1177 ++extentIndex; 1178 } 1179 1180 // 1181 // If any of the extents in the current record were changed, then update that 1182 // record (in the FCB, or extents file). 1183 // 1184 if (extentChanged) { 1185 err = UpdateExtentRecord(vcb, fcb, &key, extentRecord, hint); 1186 if (err != noErr) goto ErrorExit; 1187 } 1188 1189 // 1190 // If there are any following allocation blocks, then we need 1191 // to seach for their extent records and delete those allocation 1192 // blocks. 1193 // 1194 if (nextBlock < physNumBlocks) 1195 err = TruncateExtents(vcb, forkType, fcb->fcbFileID, nextBlock, &recordDeleted); 1196 1197Done: 1198ErrorExit: 1199 1200#if DEBUG_BUILD 1201 if (err == fxRangeErr) 1202 DebugStr("\pAbout to return fxRangeErr"); 1203#endif 1204 1205 // [2355121] If we actually deleted extent records, then update the B-tree header 1206 if (recordDeleted) 1207 (void) FlushExtentFile(vcb); 1208 1209 return err; 1210} 1211#endif 1212 1213 1214//������������������������������������������������������������������������������� 1215// Routine: SearchExtentRecord (was XRSearch) 1216// 1217// Function: Searches extent record for the extent mapping a given file 1218// allocation block number (FABN). 1219// 1220// Input: searchFABN - desired FABN 1221// extentData - pointer to extent data record (xdr) 1222// extentDataStartFABN - beginning FABN for extent record 1223// 1224// Output: foundExtentDataOffset - offset to extent entry within xdr 1225// result = noErr, offset to extent mapping desired FABN 1226// result = FXRangeErr, offset to last extent in record 1227// endingFABNPlusOne - ending FABN +1 1228// noMoreExtents - True if the extent was not found, and the 1229// extent record was not full (so don't bother 1230// looking in subsequent records); false otherwise. 1231// 1232// Result: noErr = ok 1233// FXRangeErr = desired FABN > last mapped FABN in record 1234//������������������������������������������������������������������������������� 1235 1236static OSErr SearchExtentRecord( 1237 const SVCB *vcb, 1238 UInt32 searchFABN, 1239 const HFSPlusExtentRecord extentData, 1240 UInt32 extentDataStartFABN, 1241 UInt32 *foundExtentIndex, 1242 UInt32 *endingFABNPlusOne, 1243 Boolean *noMoreExtents) 1244{ 1245 OSErr err = noErr; 1246 UInt32 extentIndex; 1247 UInt32 numberOfExtents; 1248 UInt32 numAllocationBlocks; 1249 Boolean foundExtent; 1250 1251 *endingFABNPlusOne = extentDataStartFABN; 1252 *noMoreExtents = false; 1253 foundExtent = false; 1254 1255 if (vcb->vcbSignature == kHFSPlusSigWord) 1256 numberOfExtents = kHFSPlusExtentDensity; 1257 else 1258 numberOfExtents = kHFSExtentDensity; 1259 1260 for( extentIndex = 0; extentIndex < numberOfExtents; ++extentIndex ) 1261 { 1262 1263 // Loop over the extent record and find the search FABN. 1264 1265 numAllocationBlocks = extentData[extentIndex].blockCount; 1266 if ( numAllocationBlocks == 0 ) 1267 { 1268 break; 1269 } 1270 1271 *endingFABNPlusOne += numAllocationBlocks; 1272 1273 if( searchFABN < *endingFABNPlusOne ) 1274 { 1275 // Found the extent. 1276 foundExtent = true; 1277 break; 1278 } 1279 } 1280 1281 if( foundExtent ) 1282 { 1283 // Found the extent. Note the extent offset 1284 *foundExtentIndex = extentIndex; 1285 } 1286 else 1287 { 1288 // Did not find the extent. Set foundExtentDataOffset accordingly 1289 if( extentIndex > 0 ) 1290 { 1291 *foundExtentIndex = extentIndex - 1; 1292 } 1293 else 1294 { 1295 *foundExtentIndex = 0; 1296 } 1297 1298 // If we found an empty extent, then set noMoreExtents. 1299 if (extentIndex < numberOfExtents) 1300 *noMoreExtents = true; 1301 1302 // Finally, return an error to the caller 1303 err = fxRangeErr; 1304 } 1305 1306 return( err ); 1307} 1308 1309//������������������������������������������������������������������������������� 1310// Routine: SearchExtentFile (was XFSearch) 1311// 1312// Function: Searches extent file (including the FCB resident extent record) 1313// for the extent mapping a given file position. 1314// 1315// Input: vcb - VCB pointer 1316// fcb - FCB pointer 1317// filePosition - file position (byte address) 1318// 1319// Output: foundExtentKey - extent key record (xkr) 1320// If extent was found in the FCB's resident extent record, 1321// then foundExtentKey->keyLength will be set to 0. 1322// foundExtentData - extent data record(xdr) 1323// foundExtentIndex - index to extent entry in xdr 1324// result = 0, offset to extent mapping desired FABN 1325// result = FXRangeErr, offset to last extent in record 1326// (i.e., kNumExtentsPerRecord-1) 1327// extentBTreeHint - BTree hint for extent record 1328// kNoHint = Resident extent record 1329// endingFABNPlusOne - ending FABN +1 1330// 1331// Result: 1332// noErr Found an extent that contains the given file position 1333// FXRangeErr Given position is beyond the last allocated extent 1334// (other) (some other internal I/O error) 1335//������������������������������������������������������������������������������� 1336 1337static OSErr SearchExtentFile( 1338 const SVCB *vcb, 1339 const SFCB *fcb, 1340 UInt64 sectorOffset, 1341 HFSPlusExtentKey *foundExtentKey, 1342 HFSPlusExtentRecord foundExtentData, 1343 UInt32 *foundExtentIndex, 1344 UInt32 *extentBTreeHint, 1345 UInt32 *endingFABNPlusOne ) 1346{ 1347 OSErr err; 1348 UInt32 filePositionBlock; 1349 Boolean noMoreExtents = true; 1350 1351 filePositionBlock = sectorOffset / (vcb->vcbBlockSize >> kSectorShift); 1352 1353 // Search the resident FCB first. 1354 err = GetFCBExtentRecord(vcb, fcb, foundExtentData); 1355 if (err == noErr) 1356 err = SearchExtentRecord( vcb, filePositionBlock, foundExtentData, 0, 1357 foundExtentIndex, endingFABNPlusOne, &noMoreExtents ); 1358 1359 if( err == noErr ) { 1360 // Found the extent. Set results accordingly 1361 *extentBTreeHint = kNoHint; // no hint, because not in the BTree 1362 foundExtentKey->keyLength = 0; // 0 = the FCB itself 1363 1364 goto Exit; 1365 } 1366 1367 // Didn't find extent in FCB. If FCB's extent record wasn't full, there's no point 1368 // in searching the extents file. Note that SearchExtentRecord left us pointing at 1369 // the last valid extent (or the first one, if none were valid). This means we need 1370 // to fill in the hint and key outputs, just like the "if" statement above. 1371 if ( noMoreExtents ) { 1372 *extentBTreeHint = kNoHint; // no hint, because not in the BTree 1373 foundExtentKey->keyLength = 0; // 0 = the FCB itself 1374 err = fxRangeErr; // There are no more extents, so must be beyond PEOF 1375 goto Exit; 1376 } 1377 1378 // 1379 // Find the desired record, or the previous record if it is the same fork 1380 // 1381 err = FindExtentRecord(vcb, (fcb->fcbFlags & fcbResourceMask) ? kResourceForkType : kDataForkType, 1382 fcb->fcbFileID, filePositionBlock, true, foundExtentKey, foundExtentData, extentBTreeHint); 1383 1384 if (err == btNotFound) { 1385 // 1386 // If we get here, the desired position is beyond the extents in the FCB, and there are no extents 1387 // in the extents file. Return the FCB's extents and a range error. 1388 // 1389 *extentBTreeHint = kNoHint; 1390 foundExtentKey->keyLength = 0; 1391 err = GetFCBExtentRecord(vcb, fcb, foundExtentData); 1392 // Note: foundExtentIndex and endingFABNPlusOne have already been set as a result of the very 1393 // first SearchExtentRecord call in this function (when searching in the FCB's extents, and 1394 // we got a range error). 1395 1396 return fxRangeErr; 1397 } 1398 1399 // 1400 // If we get here, there was either a BTree error, or we found an appropriate record. 1401 // If we found a record, then search it for the correct index into the extents. 1402 // 1403 if (err == noErr) { 1404 // Find appropriate index into extent record 1405 err = SearchExtentRecord(vcb, filePositionBlock, foundExtentData, foundExtentKey->startBlock, 1406 foundExtentIndex, endingFABNPlusOne, &noMoreExtents); 1407 } 1408 1409Exit: 1410 return err; 1411} 1412 1413 1414 1415//������������������������������������������������������������������������������� 1416// Routine: UpdateExtentRecord 1417// 1418// Function: Write new extent data to an existing extent record with a given key. 1419// If all of the extents are empty, and the extent record is in the 1420// extents file, then the record is deleted. 1421// 1422// Input: vcb - the volume containing the extents 1423// fcb - the file that owns the extents 1424// extentFileKey - pointer to extent key record (xkr) 1425// If the key length is 0, then the extents are actually part 1426// of the catalog record, stored in the FCB. 1427// extentData - pointer to extent data record (xdr) 1428// extentBTreeHint - hint for given key, or kNoHint 1429// 1430// Result: noErr = ok 1431// (other) = error from BTree 1432//������������������������������������������������������������������������������� 1433 1434OSErr UpdateExtentRecord ( 1435 const SVCB *vcb, 1436 SFCB *fcb, 1437 const HFSPlusExtentKey *extentFileKey, 1438 HFSPlusExtentRecord extentData, 1439 UInt32 extentBTreeHint) 1440{ 1441 OSErr err; 1442 UInt32 foundHint; 1443 UInt16 foundDataSize; 1444 1445 if (extentFileKey->keyLength == 0) { // keyLength == 0 means the FCB's extent record 1446 err = SetFCBExtentRecord(vcb, fcb, extentData); 1447 fcb->fcbFlags |= fcbModifiedMask; 1448 } 1449 else { 1450 // 1451 // Need to find and change a record in Extents BTree 1452 // 1453 if (vcb->vcbSignature == kHFSSigWord) { 1454 HFSExtentKey key; // Actual extent key used on disk in HFS 1455 HFSExtentKey foundKey; // The key actually found during search 1456 HFSExtentRecord foundData; // The extent data actually found 1457 1458 key.keyLength = kHFSExtentKeyMaximumLength; 1459 key.forkType = extentFileKey->forkType; 1460 key.fileID = extentFileKey->fileID; 1461 key.startBlock = extentFileKey->startBlock; 1462 1463 err = SearchBTreeRecord(vcb->vcbExtentsFile, &key, extentBTreeHint, 1464 &foundKey, &foundData, &foundDataSize, &foundHint); 1465 1466 if (err == noErr) 1467 err = ExtentsToExtDataRec(extentData, (HFSExtentDescriptor *)&foundData); 1468 1469 if (err == noErr) 1470 err = ReplaceBTreeRecord(vcb->vcbExtentsFile, &foundKey, foundHint, &foundData, foundDataSize, &foundHint); 1471 } 1472 else { // HFS Plus volume 1473 HFSPlusExtentKey foundKey; // The key actually found during search 1474 HFSPlusExtentRecord foundData; // The extent data actually found 1475 1476 err = SearchBTreeRecord(vcb->vcbExtentsFile, extentFileKey, extentBTreeHint, 1477 &foundKey, &foundData, &foundDataSize, &foundHint); 1478 1479 if (err == noErr) 1480 CopyMemory(extentData, &foundData, sizeof(HFSPlusExtentRecord)); 1481 1482 if (err == noErr) 1483 err = ReplaceBTreeRecord(vcb->vcbExtentsFile, &foundKey, foundHint, &foundData, foundDataSize, &foundHint); 1484 } 1485 } 1486 1487 return err; 1488} 1489 1490 1491void ExtDataRecToExtents( 1492 const HFSExtentRecord oldExtents, 1493 HFSPlusExtentRecord newExtents) 1494{ 1495 UInt32 i; 1496 1497 // copy the first 3 extents 1498 newExtents[0].startBlock = oldExtents[0].startBlock; 1499 newExtents[0].blockCount = oldExtents[0].blockCount; 1500 newExtents[1].startBlock = oldExtents[1].startBlock; 1501 newExtents[1].blockCount = oldExtents[1].blockCount; 1502 newExtents[2].startBlock = oldExtents[2].startBlock; 1503 newExtents[2].blockCount = oldExtents[2].blockCount; 1504 1505 // zero out the remaining ones 1506 for (i = 3; i < kHFSPlusExtentDensity; ++i) 1507 { 1508 newExtents[i].startBlock = 0; 1509 newExtents[i].blockCount = 0; 1510 } 1511} 1512 1513 1514 1515static OSErr ExtentsToExtDataRec( 1516 HFSPlusExtentRecord oldExtents, 1517 HFSExtentRecord newExtents) 1518{ 1519 OSErr err; 1520 1521 err = noErr; 1522 1523 // copy the first 3 extents 1524 newExtents[0].startBlock = oldExtents[0].startBlock; 1525 newExtents[0].blockCount = oldExtents[0].blockCount; 1526 newExtents[1].startBlock = oldExtents[1].startBlock; 1527 newExtents[1].blockCount = oldExtents[1].blockCount; 1528 newExtents[2].startBlock = oldExtents[2].startBlock; 1529 newExtents[2].blockCount = oldExtents[2].blockCount; 1530 1531 #if DEBUG_BUILD 1532 if (oldExtents[3].startBlock || oldExtents[3].blockCount) { 1533 DebugStr("\pExtentRecord with > 3 extents is invalid for HFS"); 1534 err = fsDSIntErr; 1535 } 1536 #endif 1537 1538 return err; 1539} 1540 1541 1542OSErr GetFCBExtentRecord( 1543 const SVCB *vcb, 1544 const SFCB *fcb, 1545 HFSPlusExtentRecord extents) 1546{ 1547 if (vcb->vcbSignature == kHFSPlusSigWord) 1548 CopyMemory(fcb->fcbExtents32, extents, sizeof(HFSPlusExtentRecord)); 1549 else 1550 ExtDataRecToExtents(fcb->fcbExtents16, extents); 1551 return noErr; 1552} 1553 1554 1555 1556static OSErr SetFCBExtentRecord( 1557 const SVCB *vcb, 1558 SFCB *fcb, 1559 HFSPlusExtentRecord extents) 1560{ 1561 1562 #if DEBUG_BUILD 1563 if (fcb->fcbVolume != vcb) 1564 DebugStr("\pVCB does not match FCB"); 1565 #endif 1566 1567 if (vcb->vcbSignature == kHFSPlusSigWord) 1568 CopyMemory(extents, fcb->fcbExtents32, sizeof(HFSPlusExtentRecord)); 1569 else 1570 (void) ExtentsToExtDataRec(extents, fcb->fcbExtents16); 1571 1572 return noErr; 1573} 1574 1575 1576 1577//������������������������������������������������������������������������������� 1578// Routine: MapFileBlockFromFCB 1579// 1580// Function: Determine if the given file offset is within the set of extents 1581// stored in the FCB. If so, return the file allocation 1582// block number of the start of the extent, volume allocation block number 1583// of the start of the extent, and file allocation block number immediately 1584// following the extent. 1585// 1586// Input: vcb - the volume containing the extents 1587// fcb - the file that owns the extents 1588// offset - desired offset in 512-byte sectors 1589// 1590// Output: firstFABN - file alloc block number of start of extent 1591// firstBlock - volume alloc block number of start of extent 1592// nextFABN - file alloc block number of next extent 1593// 1594// Result: noErr = ok 1595// fxRangeErr = beyond FCB's extents 1596//������������������������������������������������������������������������������� 1597static OSErr MapFileBlockFromFCB( 1598 const SVCB *vcb, 1599 const SFCB *fcb, 1600 UInt64 sectorOffset, // Desired offset in sectors from start of file 1601 UInt32 *firstFABN, // FABN of first block of found extent 1602 UInt32 *firstBlock, // Corresponding allocation block number 1603 UInt32 *nextFABN) // FABN of block after end of extent 1604{ 1605 UInt32 index; 1606 UInt32 offsetBlocks; 1607 1608 offsetBlocks = sectorOffset / (vcb->vcbBlockSize >> kSectorShift); 1609 1610 if (vcb->vcbSignature == kHFSSigWord) { 1611 const HFSExtentDescriptor *extent; 1612 UInt32 blockCount; 1613 UInt32 currentFABN; 1614 1615 extent = fcb->fcbExtents16; 1616 currentFABN = 0; 1617 1618 for (index=0; index<kHFSExtentDensity; index++) { 1619 1620 blockCount = extent->blockCount; 1621 1622 if (blockCount == 0) 1623 return fxRangeErr; // ran out of extents! 1624 1625 // Is it in this extent? 1626 if (offsetBlocks < blockCount) { 1627 *firstFABN = currentFABN; 1628 *firstBlock = extent->startBlock; 1629 currentFABN += blockCount; // faster to add these as UInt16 first, then extend to UInt32 1630 *nextFABN = currentFABN; 1631 return noErr; // found the right extent 1632 } 1633 1634 // Not in current extent, so adjust counters and loop again 1635 offsetBlocks -= blockCount; 1636 currentFABN += blockCount; 1637 extent++; 1638 } 1639 } 1640 else { 1641 const HFSPlusExtentDescriptor *extent; 1642 UInt32 blockCount; 1643 UInt32 currentFABN; 1644 1645 extent = fcb->fcbExtents32; 1646 currentFABN = 0; 1647 1648 for (index=0; index<kHFSPlusExtentDensity; index++) { 1649 1650 blockCount = extent->blockCount; 1651 1652 if (blockCount == 0) 1653 return fxRangeErr; // ran out of extents! 1654 1655 // Is it in this extent? 1656 if (offsetBlocks < blockCount) { 1657 *firstFABN = currentFABN; 1658 *firstBlock = extent->startBlock; 1659 *nextFABN = currentFABN + blockCount; 1660 return noErr; // found the right extent 1661 } 1662 1663 // Not in current extent, so adjust counters and loop again 1664 offsetBlocks -= blockCount; 1665 currentFABN += blockCount; 1666 extent++; 1667 } 1668 } 1669 1670 // If we fall through here, the extent record was full, but the offset was 1671 // beyond those extents. 1672 1673 return fxRangeErr; 1674} 1675 1676 1677//������������������������������������������������������������������������������� 1678// Routine: ZeroFileBlocks 1679// 1680// Function: Write all zeros to a range of a file. Currently used when 1681// extending a B-Tree, so that all the new allocation blocks 1682// contain zeros (to prevent them from accidentally looking 1683// like real data). 1684// 1685// Input: vcb - the volume 1686// fcb - the file 1687// startingSector - the first 512-byte sector to write 1688// numberOfSectors - the number of sectors to zero 1689// 1690// Result: noErr = ok 1691// fxRangeErr = beyond FCB's extents 1692//������������������������������������������������������������������������������� 1693#define FSBufferSize 32768 1694 1695OSErr ZeroFileBlocks( SVCB *vcb, SFCB *fcb, UInt32 startingSector, UInt32 numberOfSectors ) 1696{ 1697 Ptr buffer; 1698 OSErr err; 1699 HIOParam iopb; 1700 UInt32 requestedBytes; 1701 UInt32 actualBytes; // Bytes actually read by CacheReadInPlace 1702 UInt32 bufferSizeSectors = FSBufferSize >> kSectorShift; 1703 UInt64 currentPosition = startingSector << kSectorShift; 1704 1705 buffer = AllocateMemory(FSBufferSize); 1706 if ( buffer == NULL ) 1707 return( fileBoundsErr ); 1708 1709 ClearMemory( buffer, FSBufferSize ); // Zero our buffer 1710 ClearMemory( &iopb, sizeof(iopb) ); // Zero our param block 1711 1712 iopb.ioRefNum = ResolveFileRefNum( fcb ); 1713 iopb.ioBuffer = buffer; 1714 iopb.ioPosMode |= noCacheMask; // OR with the high byte 1715 1716 do 1717 { 1718 if ( numberOfSectors > bufferSizeSectors ) 1719 requestedBytes = FSBufferSize; 1720 else 1721 requestedBytes = numberOfSectors << kSectorShift; 1722 1723 err = CacheWriteInPlace( vcb, iopb.ioRefNum, &iopb, currentPosition, requestedBytes, &actualBytes ); 1724 1725 if ( err || actualBytes == 0 ) 1726 goto BAIL; 1727 1728 // Don't update ioActCount to force writing from beginning of zero buffer 1729 currentPosition += actualBytes; 1730 numberOfSectors -= (actualBytes >> kSectorShift); 1731 1732 } while( numberOfSectors > 0 ); 1733 1734BAIL: 1735 DisposeMemory(buffer); 1736 1737 if ( err == noErr && numberOfSectors != 0 ) 1738 err = eofErr; 1739 1740 return( err ); 1741} 1742 1743//_________________________________________________________________________________ 1744// 1745// Routine: ExtentsAreIntegral 1746// 1747// Purpose: Ensure that each extent can hold an integral number of nodes 1748// Called by the NodesAreContiguous function 1749//_________________________________________________________________________________ 1750 1751static Boolean ExtentsAreIntegral( 1752 const HFSPlusExtentRecord extentRecord, 1753 UInt32 mask, 1754 UInt32 *blocksChecked, 1755 Boolean *checkedLastExtent) 1756{ 1757 UInt32 blocks; 1758 UInt32 extentIndex; 1759 1760 *blocksChecked = 0; 1761 *checkedLastExtent = false; 1762 1763 for(extentIndex = 0; extentIndex < kHFSPlusExtentDensity; extentIndex++) 1764 { 1765 blocks = extentRecord[extentIndex].blockCount; 1766 1767 if ( blocks == 0 ) 1768 { 1769 *checkedLastExtent = true; 1770 break; 1771 } 1772 1773 *blocksChecked += blocks; 1774 1775 if (blocks & mask) 1776 return false; 1777 } 1778 1779 return true; 1780} 1781 1782//_________________________________________________________________________________ 1783// 1784// Routine: NodesAreContiguous 1785// 1786// Purpose: Ensure that all b-tree nodes are contiguous on disk 1787// Called by BTOpenPath during volume mount 1788//_________________________________________________________________________________ 1789 1790Boolean NodesAreContiguous( 1791 SFCB *fcb, 1792 UInt32 nodeSize) 1793{ 1794 SVCB *vcb; 1795 UInt32 mask; 1796 UInt32 startBlock; 1797 UInt32 blocksChecked; 1798 UInt32 hint; 1799 HFSPlusExtentKey key; 1800 HFSPlusExtentRecord extents; 1801 OSErr result; 1802 Boolean lastExtentReached; 1803 1804 1805 vcb = (SVCB *)fcb->fcbVolume; 1806 1807 if (vcb->vcbBlockSize >= nodeSize) 1808 return true; 1809 1810 mask = (nodeSize / vcb->vcbBlockSize) - 1; 1811 1812 // check the local extents 1813 (void) GetFCBExtentRecord(vcb, fcb, extents); 1814 if ( !ExtentsAreIntegral(extents, mask, &blocksChecked, &lastExtentReached) ) 1815 return false; 1816 1817 if (lastExtentReached || ((UInt64)blocksChecked * (UInt64)vcb->vcbBlockSize) >= fcb->fcbPhysicalSize) 1818 return true; 1819 1820 startBlock = blocksChecked; 1821 1822 // check the overflow extents (if any) 1823 while ( !lastExtentReached ) 1824 { 1825 result = FindExtentRecord(vcb, kDataForkType, fcb->fcbFileID, startBlock, false, &key, extents, &hint); 1826 if (result) break; 1827 1828 if ( !ExtentsAreIntegral(extents, mask, &blocksChecked, &lastExtentReached) ) 1829 return false; 1830 1831 startBlock += blocksChecked; 1832 } 1833 1834 return true; 1835} 1836