fsck_hfs/dfalib/SExtents.c

   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 ============================================================
  41 Public (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 ============================================================
  81 Internal 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
 100 enum
 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
 112 static OSErr ExtentsToExtDataRec(
 113         HFSPlusExtentRecord     oldExtents,
 114         HFSExtentRecord         newExtents);
 115
 116 OSErr 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
 126 OSErr DeleteExtentRecord(
 127         const SVCB              *vcb,
 128         UInt8                                   forkType,
 129         UInt32                                  fileID,
 130         UInt32                                  startBlock);
 131
 132 static OSErr CreateExtentRecord(
 133         const SVCB              *vcb,
 134         HFSPlusExtentKey                        *key,
 135         HFSPlusExtentRecord             extents,
 136         UInt32                                  *hint);
 137
 138 OSErr GetFCBExtentRecord(
 139         const SVCB              *vcb,
 140         const SFCB                      *fcb,
 141         HFSPlusExtentRecord             extents);
 142
 143 static OSErr SetFCBExtentRecord(
 144         const SVCB                      *vcb,
 145         SFCB                            *fcb,
 146         HFSPlusExtentRecord             extents);
 147
 148 static 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
 158 static 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
 168 static OSErr DeallocateFork(
 169         SVCB            *vcb,
 170         HFSCatalogNodeID                fileID,
 171         UInt8                           forkType,
 172         HFSPlusExtentRecord     catalogExtents,
 173         Boolean *                       recordDeleted);
 174
 175 static OSErr TruncateExtents(
 176         SVCB                    *vcb,
 177         UInt8                           forkType,
 178         UInt32                          fileID,
 179         UInt32                          startBlock,
 180         Boolean *                       recordDeleted);
 181 #endif
 182
 183 static 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
 191 static 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 //_________________________________________________________________________________
 219 OSErr 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
 331 static 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
 362 OSErr 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
 421 OSErr 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
 513 OSErr 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
 574 static 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 //ÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑ
 615 static 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
 643 OSErr 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
 671 OSErr 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
 748 OSErr 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
 996 ErrorExit:
 997 Exit:
 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
1037 OSErr 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
1197 Done:
1198 ErrorExit:
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
1236 static 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
1337 static 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
1409 Exit:
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
1434 OSErr 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
1491 void 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
1515 static 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
1542 OSErr 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
1556 static 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 //ÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑÑ
1597 static 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
1695 OSErr   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
1734 BAIL:
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
1751 static 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
1790 Boolean 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 }