Return to VolumeAllocation.c CVS log

Up to [Apple Darwin 0.x] / kernel / bsd / hfs / hfscommon / Misc

Annotation of kernel/bsd/hfs/hfscommon/Misc/VolumeAllocation.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
        !             7:  * Reserved.  This file contains Original Code and/or Modifications of
        !             8:  * Original Code as defined in and that are subject to the Apple Public
        !             9:  * Source License Version 1.1 (the "License").  You may not use this file
        !            10:  * except in compliance with the License.  Please obtain a copy of the
        !            11:  * License at http://www.apple.com/publicsource and read it before using
        !            12:  * this file.
        !            13:  * 
        !            14:  * The Original Code and all software distributed under the License are
        !            15:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            16:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            17:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            18:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            19:  * License for the specific language governing rights and limitations
        !            20:  * under the License.
        !            21:  * 
        !            22:  * @APPLE_LICENSE_HEADER_END@
        !            23:  */
        !            24: 
        !            25: /*
        !            26:        File:           VolumeAllocation.c
        !            27: 
        !            28:        Contains:       Routines for accessing and modifying the volume bitmap.
        !            29: 
        !            30:        Version:        HFS Plus 1.0
        !            31: 
        !            32:        Copyright:      � 1996-1997 by Apple Computer, Inc., all rights reserved.
        !            33: 
        !            34:        File Ownership:
        !            35: 
        !            36:                DRI:                            Mark Day
        !            37: 
        !            38:                Other Contact:          Greg Parks
        !            39: 
        !            40:                Technology:                     HFS+
        !            41: 
        !            42:        Writers:
        !            43: 
        !            44:                (djb)   Don Brady
        !            45:                (DSH)   Deric Horn
        !            46:                (msd)   Mark Day
        !            47: 
        !            48:        Change History (most recent first):
        !            49:          <Rhap>         4/27/98        djb             Remove unneccessary DebugStr in BlockVerifyAllocated.
        !            50:          <Rhap>         4/17/98        djb             Add VCB locking.
        !            51:          <Rhap>         4/13/98        djb             Add RequireFileLock checking to ReadBitmapBlock.
        !            52:          <Rhap>         3/31/98        djb             Sync up with final HFSVolumes.h header file.
        !            53: 
        !            54:          <12>  1       0/31/97         DSH             Modify BlockVerifyAllocated() so DFA can call without actually
        !            55:                                                                        writing to the disk.
        !            56:          <CS11>        10/20/97        msd             The way BlockAllocate rounds up to a multiple of the clump size
        !            57:                                                                        is wrong. ExtendFileC should do the round-up and pass the result
        !            58:                                                                        into BlockAllocate. Removed the fcb parameter to BlockAllocate;
        !            59:                                                                        added a bytesMaximum parameter.
        !            60:          <CS10>        10/17/97        msd             Conditionalize DebugStrs.
        !            61:           <CS9>          9/4/97        djb             Add logging to BlockAllocate.
        !            62:           <CS8>          9/4/97        msd             Add a histogram of allocation sizes. Use DEBUG_BUILD instead of
        !            63:                                                                        VSM_DEBUG to generate DebugStr messages.
        !            64:           <CS7>         8/14/97        msd             Bug 1662332. Don't mark blocks dirty in UpdateFreeCount. In
        !            65:                                                                        BlockVerifyAllocated, only mark blocks dirty if they've actually
        !            66:                                                                        changed.
        !            67:           <CS6>         7/16/97        DSH             FilesInternal.i renamed FileMgrInternal.i to avoid name
        !            68:                                                                        collision
        !            69:           <CS5>          7/8/97        DSH             Loading PrecompiledHeaders from define passed in on C line
        !            70:           <CS4>         6/12/97        msd             Export BlockAllocateAny and UpdateVCBFreeBlks.
        !            71:                 <3>      5/8/97        DSH             Added comments and ascii diagram of new BlockFindContiguous()
        !            72:                                                                        algorithm.
        !            73:                 <2>      5/7/97        DSH             New faster BlockFindContiguous algorithm.  It searches backwards
        !            74:                                                                        until a dirty bit is found instead of forwards.
        !            75:           <CS1>         4/25/97        djb             first checked in
        !            76: 
        !            77:         <HFS21>         4/14/97        msd             Fix UpdateVCBFreeBlks so free space calculation doesn't overflow
        !            78:                                                                        on volumes bigger than 4GB.
        !            79:         <HFS20>          4/4/97        djb             Get in sync with volume format changes.
        !            80:         <HFS19>         1/27/97        msd             Speed up BlockCheck and UpdateFreeCount. Removed DebugStr from
        !            81:                                                                        BlockCheck; there are now DebugStr's in BlockVerifyAllocated,
        !            82:                                                                        before the bitmap gets fixed (so potential problems can be
        !            83:                                                                        debugged easier). Adjusted comments about internal routines.
        !            84:                                                                        Changed names of "Fast" routines back to their original names
        !            85:                                                                        (since the originals are now removed).
        !            86:         <HFS18>         1/24/97        msd             Speed up allocation and deallocation.
        !            87:         <HFS17>         1/21/97        msd             Add instrumentation for function entry/exit.  BlockAllocate and
        !            88:                                                                        ReadBitMapBlock use the event tag to log bytes requested and
        !            89:                                                                        block number (respectively).
        !            90:         <HFS16>         1/15/97        djb             Add HFS+ supprt to BlockCheck (for MountCheck).
        !            91:         <HFS15>         1/13/97        DSH             Use vcb->nextAllocation instead of vcbAllocPtr.
        !            92:         <HFS14>          1/9/97        djb             UpdateVCBFreeBlks is not converting correctly.
        !            93:         <HFS13>          1/6/97        djb             Use vcb's allocationsRefNum to access allocation file.
        !            94:         <HFS12>          1/2/97        DSH             Added UpdateVCBFreeBlks() to update vcbFreeBks whenever we
        !            95:                                                                        update vcb->freeblocks.
        !            96:         <HFS11>        12/19/96        DSH             All refs to VCB are now refs to ExtendedVCB
        !            97:         <HFS10>        12/12/96        msd             DivideAndRoundUp should not be declared as static.
        !            98:          <HFS9>        12/10/96        msd             Check PRAGMA_LOAD_SUPPORTED before loading precompiled headers.
        !            99:          <HFS8>         12/4/96        DSH             PrecompiledHeaders
        !           100:          <HFS7>        11/27/96        djb             Added AllocateFreeSpace for HFS wrapper support.
        !           101:          <HFS6>        11/27/96        msd             Changed ReadBitmapBlock to read from HFS+ allocation file.
        !           102:                                                                        Temporarily uses the vcbVBMSt field of the VCB as the allocation
        !           103:                                                                        file's refnum until extended VCB changes are checked in.
        !           104:          <HFS5>        11/26/96        msd             VSM and FileExtentMapping routines use FCB instead of FCBRec.
        !           105:          <HFS4>        11/20/96        DSH             Changed a parameter in GetBlock_glue, so I also changed the
        !           106:                                                                        caller.
        !           107:          <HFS3>        11/20/96        msd             Include FilesInternal.h. Remove definition of MarkVCBDirty
        !           108:                                                                        (since it is now in FilesInternal.h).
        !           109:          <HFS2>        11/12/96        msd             Need to bound allocations to be within the last allocation block
        !           110:                                                                        of the volume (function AllocateAt).
        !           111:          <HFS1>        11/11/96        msd             first checked in
        !           112: */
        !           113: 
        !           114: /*
        !           115: Public routines:
        !           116:        BlockAllocate
        !           117:                                        Allocate space on a volume.  Can allocate space contiguously.
        !           118:                                        If not contiguous, then allocation may be less than what was
        !           119:                                        asked for.  Returns the starting block number, and number of
        !           120:                                        blocks.  (Will only do a single extent???)
        !           121:        BlockDeallocate
        !           122:                                        Deallocate a contiguous run of allocation blocks.
        !           123:        BlockCheck
        !           124:                                        Makes sure that the blocks associated with an extent record
        !           125:                                        are in fact allocated in the bitmap.  The bits will be set
        !           126:                                        if needed.  Returns whether any bits needed to be set.
        !           127:        UpdateFreeCount
        !           128:                                        Computes the number of free allocation blocks on a volume.
        !           129:                                        The vcb's free block count is updated.
        !           130: 
        !           131:        AllocateFreeSpace
        !           132:                                        Allocates all the remaining free space (used for embedding HFS+ volumes).
        !           133: 
        !           134:        BlockAllocateAny
        !           135:                                        Find and allocate a contiguous range of blocks up to a given size.  The
        !           136:                                        first range of contiguous free blocks found are allocated, even if there
        !           137:                                        are fewer blocks than requested (and even if a contiguous range of blocks
        !           138:                                        of the given size exists elsewhere).
        !           139: 
        !           140:        UpdateVCBFreeBlks
        !           141:                                        Given an ExtenddVCB, calculate the vcbFreeBks value
        !           142:                                        so that vcbFreeBks*vcbAlBlkSiz == freeBlocks*blockSize.
        !           143: 
        !           144: Internal routines:
        !           145:        BlockVerifyAllocated
        !           146:                                        Makes sure that a contiguous range of blocks are marked as used
        !           147:                                        in the bitmap.  If not, those blocks will be marked as used.  A
        !           148:                                        boolean is returned to indicate whether any unmarked blocks were
        !           149:                                        found (and fixed).
        !           150:        BlockMarkFree
        !           151:                                        Mark a contiguous range of blocks as free.  The corresponding
        !           152:                                        bits in the volume bitmap will be cleared.
        !           153:        BlockMarkAllocated
        !           154:                                        Mark a contiguous range of blocks as allocated.  The cor-
        !           155:                                        responding bits in the volume bitmap are set.  Also tests to see
        !           156:                                        if any of the blocks were previously unallocated.
        !           157:        FindContiguous
        !           158:                                        Find a contiguous range of blocks of a given size.  The caller
        !           159:                                        specifies where to begin the search (by block number).  The
        !           160:                                        block number of the first block in the range is returned.
        !           161:        BlockAllocateContig
        !           162:                                        Find and allocate a contiguous range of blocks of a given size.  If
        !           163:                                        a contiguous range of free blocks of the given size isn't found, then
        !           164:                                        the allocation fails (i.e. it is "all or nothing").
        !           165:        ReadBitmapBlock
        !           166:                                        Given an allocation block number, read the bitmap block that
        !           167:                                        contains that allocation block into a caller-supplied buffer.
        !           168: */
        !           169: 
        !           170: #include "../headers/system/ConditionalMacros.h"
        !           171: 
        !           172: #if ( PRAGMA_LOAD_SUPPORTED )
        !           173:         #pragma        load    PrecompiledHeaders
        !           174: #else
        !           175:        #if TARGET_OS_MAC
        !           176:                #include <FSM.h>
        !           177:        #else
        !           178:         #include "../headers/system/MacOSStubs.h"
        !           179: #include <sys/types.h>
        !           180: #include <sys/buf.h>
        !           181: #include <sys/systm.h>
        !           182: 
        !           183: #include "../../hfs.h"
        !           184: #include "../../hfs_dbg.h"
        !           185:        #endif  /* TARGET_OS_MAC */
        !           186: #endif /* PRAGMA_LOAD_SUPPORTED */
        !           187: 
        !           188: 
        !           189: #if HFSInstrumentation
        !           190:        #include "Instrumentation.h"
        !           191: #endif
        !           192:        
        !           193: #include "../headers/HFSVolumes.h"
        !           194: #include "../headers/FileMgrInternal.h"
        !           195: 
        !           196: #include "../headers/system/HFSInstrumentation.h"
        !           197: 
        !           198: #if TARGET_OS_RHAPSODY
        !           199: #define EXPLICIT_BUFFER_RELEASES 1
        !           200: #endif
        !           201: 
        !           202: enum {
        !           203:        kBitsPerByte                    =       8,
        !           204:        kBitsPerWord                    =       32,
        !           205:        kWordsPerBlock                  =       128,
        !           206:        kBytesPerBlock                  =       512,
        !           207:        kBitsPerBlock                   =       4096,
        !           208:        
        !           209:        kBitsWithinWordMask             =       kBitsPerWord-1,
        !           210:        kBitsWithinBlockMask    =       kBitsPerBlock-1,
        !           211:        kWordsWithinBlockMask   =       kWordsPerBlock-1,
        !           212:        
        !           213:        kExtentsPerRecord               =       3
        !           214: };
        !           215: 
        !           216: #define kLowBitInWordMask      0x00000001ul
        !           217: #define kHighBitInWordMask     0x80000000ul
        !           218: #define kAllBitsSetInWord      0xFFFFFFFFul
        !           219: 
        !           220: 
        !           221: static OSErr BlockVerifyAllocated(
        !           222:        ExtendedVCB             *vcb,
        !           223:        UInt32                  startBlock,
        !           224:        UInt32                  blockCount,
        !           225:        Boolean                 *foundUnmarkedBlock);
        !           226: 
        !           227: static OSErr ReadBitmapBlock(
        !           228:        ExtendedVCB             *vcb,
        !           229:        UInt32                  block,
        !           230:        UInt32                  **buffer);
        !           231: 
        !           232: static OSErr BlockAllocateContig(
        !           233:        ExtendedVCB             *vcb,
        !           234:        UInt32                  startingBlock,
        !           235:        UInt32                  minBlocks,
        !           236:        UInt32                  maxBlocks,
        !           237:        UInt32                  *actualStartBlock,
        !           238:        UInt32                  *actualNumBlocks);
        !           239: 
        !           240: static OSErr BlockFindContiguous(
        !           241:        ExtendedVCB             *vcb,
        !           242:        UInt32                  startingBlock,
        !           243:        UInt32                  endingBlock,
        !           244:        UInt32                  minBlocks,
        !           245:        UInt32                  maxBlocks,
        !           246:        UInt32                  *actualStartBlock,
        !           247:        UInt32                  *actualNumBlocks);
        !           248: 
        !           249: static OSErr BlockMarkAllocated(
        !           250:        ExtendedVCB             *vcb,
        !           251:        UInt32                  startingBlock,
        !           252:        UInt32                  numBlocks);
        !           253: 
        !           254: static OSErr BlockMarkFree(
        !           255:        ExtendedVCB             *vcb,
        !           256:        UInt32                  startingBlock,
        !           257:        UInt32                  numBlocks);
        !           258: 
        !           259: #if TARGET_OS_RHAPSODY && DIAGNOSTIC
        !           260:        #if DIAGNOSTIC
        !           261:                extern void RequireFileLock(FileReference file, int shareable);
        !           262:        #else
        !           263:                #define RequireFileLock(f)
        !           264:        #endif
        !           265: #endif
        !           266: 
        !           267: /*
        !           268: ;________________________________________________________________________________
        !           269: ;
        !           270: ; Routine:        BlkAlloc
        !           271: ;
        !           272: ; Function:    Allocate space on a volume.     If contiguous allocation is requested,
        !           273: ;                         at least the requested number of bytes will be allocated or an
        !           274: ;                         error will be returned.      If contiguous allocation is not forced,
        !           275: ;                         the space will be allocated at the first free fragment following
        !           276: ;                         the requested starting allocation block.  If there is not enough
        !           277: ;                         room there, a block of less than the requested size will be
        !           278: ;                         allocated.
        !           279: ;
        !           280: ;                         If the requested starting block is 0 (for new file allocations),
        !           281: ;                         the volume's allocation block pointer will be used as a starting
        !           282: ;                         point.
        !           283: ;
        !           284: ;                         All requests will be rounded up to the next highest clump size, as
        !           285: ;                         indicated in the file's FCB.
        !           286: ;
        !           287: ; Input Arguments:
        !           288: ;       vcb                     - Pointer to ExtendedVCB for the volume to allocate space on
        !           289: ;       fcb                     - Pointer to FCB for the file for which storage is being allocated
        !           290: ;       startingBlock   - Preferred starting allocation block, 0 = no preference
        !           291: ;       forceContiguous - Force contiguous flag - if bit 0 set (NE), allocation is contiguous
        !           292: ;                                         or an error is returned
        !           293: ;       bytesRequested  - Number of bytes requested.   If the allocation is non-contiguous,
        !           294: ;                                         less than this may actually be allocated
        !           295: ;       bytesMaximum    - The maximum number of bytes to allocate.  If there is additional free
        !           296: ;                                         space after bytesRequested, then up to bytesMaximum bytes should really
        !           297: ;                                         be allocated.  (Used by ExtendFileC to round up allocations to a multiple
        !           298: ;                                         of the file's clump size.)
        !           299: ;
        !           300: ; Output:
        !           301: ;       (result)                - Error code, zero for successful allocation
        !           302: ;       *startBlock     - Actual starting allocation block
        !           303: ;       *actualBlocks   - Actual number of allocation blocks allocated
        !           304: ;
        !           305: ; Side effects:
        !           306: ;       The volume bitmap is read and updated; the volume bitmap cache may be changed.
        !           307: ;
        !           308: ; Modification history:
        !           309: ;      <06Oct85>  PWD  Changed to check for errors after calls to ReadBM and NextWord
        !           310: ;                                      Relocated call to MarkBlock in allocation loop
        !           311: ;                                      Changed to call NextBit
        !           312: ; <21Oct85>   PWD      Changed to check VCBFreeBks before attempting to allocate any block.
        !           313: ;                                      Speed up scan for free space by checking for all 1's.
        !           314: ;________________________________________________________________________________
        !           315: */
        !           316: 
        !           317: OSErr BlockAllocate (
        !           318:        ExtendedVCB             *vcb,                           /* which volume to allocate space on */
        !           319:        UInt32                  startingBlock,          /* preferred starting block, or 0 for no preference */
        !           320:        UInt32                  bytesRequested,         /* desired number of BYTES to allocate */
        !           321:        UInt32                  bytesMaximum,           /* maximum number of bytes to allocate */
        !           322:        Boolean                 forceContiguous,        /* non-zero to force contiguous allocation and to force */
        !           323:                                                                                /* bytesRequested bytes to actually be allocated */
        !           324:        UInt32                  *actualStartBlock,      /* actual first block of allocation */
        !           325:        UInt32                  *actualNumBlocks)       /* number of blocks actually allocated; if forceContiguous */
        !           326:                                                                                /* was zero, then this may represent fewer than bytesRequested */
        !           327:                                                                                /* bytes */
        !           328: {
        !           329:        OSErr                   err;
        !           330:        UInt32                  minBlocks;                                      //      minimum number of allocation blocks requested
        !           331:        UInt32                  maxBlocks;                                      //      number of allocation blocks requested, rounded to clump size
        !           332:        Boolean                 updateAllocPtr = false;         //      true if nextAllocation needs to be updated
        !           333: 
        !           334:        LogStartTime(kTraceBlockAllocate);
        !           335: 
        !           336: #if HFSInstrumentation
        !           337:        InstSplitHistogramClassRef      histogram;
        !           338:        InstTraceClassRef                       trace;
        !           339:        InstEventTag                            eventTag;
        !           340:        
        !           341:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockAllocate", 'hfs+', kInstEnableClassMask, &trace);
        !           342:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !           343: 
        !           344:        err = InstCreateSplitHistogramClass(kInstRootClassRef, "HFS:VSM:BlockAllocate size", 0, 512, 16384, 262144, 16384,
        !           345:                                                                                kInstEnableClassMask, &histogram);
        !           346:        if (err != noErr) DebugStr("\pError from InstCreateHistogramClass");
        !           347: 
        !           348:        eventTag = bytesRequested;              // a cheap way to get bytesRequested into the log
        !           349:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !           350:        InstUpdateHistogram( histogram, bytesRequested, 1);
        !           351: #endif
        !           352: 
        !           353:        //
        !           354:        //      Initialize outputs in case we get an error
        !           355:        //
        !           356:        *actualStartBlock = 0;
        !           357:        *actualNumBlocks = 0;
        !           358:        
        !           359:        //
        !           360:        //      Compute the number of allocation blocks requested, and maximum
        !           361:        //
        !           362:        minBlocks = DivideAndRoundUp(bytesRequested, vcb->blockSize);
        !           363:        maxBlocks = DivideAndRoundUp(bytesMaximum, vcb->blockSize);
        !           364:        
        !           365:        //
        !           366:        //      If the disk is already full, don't bother.
        !           367:        //
        !           368:        if (vcb->freeBlocks == 0) {
        !           369:                err = dskFulErr;
        !           370:                goto Exit;
        !           371:        }
        !           372:        if (forceContiguous && vcb->freeBlocks < minBlocks) {
        !           373:                err = dskFulErr;
        !           374:                goto Exit;
        !           375:        }
        !           376:        
        !           377:        //
        !           378:        //      If caller didn't specify a starting block number, then use the volume's
        !           379:        //      next block to allocate from.
        !           380:        //
        !           381:        if (startingBlock == 0) {
        !           382:                VCB_LOCK(vcb);
        !           383:                startingBlock = vcb->nextAllocation;
        !           384:                VCB_UNLOCK(vcb);
        !           385:                updateAllocPtr = true;
        !           386:        }
        !           387:        
        !           388:        //
        !           389:        //      If the request must be contiguous, then find a sequence of free blocks
        !           390:        //      that is long enough.  Otherwise, find the first free block.
        !           391:        //
        !           392:        if (forceContiguous) {
        !           393:                err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks, actualStartBlock, actualNumBlocks);
        !           394:        } else {
        !           395:                err = BlockAllocateAny(vcb, startingBlock, vcb->totalBlocks, maxBlocks, actualStartBlock, actualNumBlocks);
        !           396:                if (err == dskFulErr) {
        !           397:                        err = BlockAllocateAny(vcb, 0, startingBlock, maxBlocks, actualStartBlock, actualNumBlocks);
        !           398:                        };
        !           399:        }
        !           400: 
        !           401:        if (err == noErr) {
        !           402:                //
        !           403:                //      If we used the volume's roving allocation pointer, then we need to update it.
        !           404:                //      Adding in the length of the current allocation might reduce the next allocate
        !           405:                //      call by avoiding a re-scan of the already allocated space.  However, the clump
        !           406:                //      just allocated can quite conceivably end up being truncated or released when
        !           407:                //      the file is closed or its EOF changed.  Leaving the allocation pointer at the
        !           408:                //      start of the last allocation will avoid unnecessary fragmentation in this case.
        !           409:                //
        !           410:                VCB_LOCK(vcb);
        !           411: 
        !           412:                if (updateAllocPtr)
        !           413:                        vcb->nextAllocation = *actualStartBlock;
        !           414:                
        !           415:                //
        !           416:                //      Update the number of free blocks on the volume
        !           417:                //
        !           418:                vcb->freeBlocks -= *actualNumBlocks;
        !           419:                VCB_UNLOCK(vcb);
        !           420: 
        !           421:                UpdateVCBFreeBlks( vcb );
        !           422:                MarkVCBDirty(vcb);
        !           423:        }
        !           424:        
        !           425: Exit:
        !           426: 
        !           427: #if HFSInstrumentation
        !           428:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !           429: #endif
        !           430:        LogEndTime(kTraceBlockAllocate, err);
        !           431: 
        !           432:        return err;
        !           433: }
        !           434: 
        !           435: 
        !           436: /*
        !           437: ;________________________________________________________________________________
        !           438: ;
        !           439: ; Routine:        UpdateVCBFreeBlks
        !           440: ;
        !           441: ; Function:    Whenever the freeBlocks field in the ExtendedVCB is updated,
        !           442: ;                         we must also recalculate the (UInt16) vcbFreeBks field in the
        !           443: ;                         traditional HFS VCB structure.
        !           444: ;
        !           445: ; Input Arguments:
        !           446: ;       vcb            - Pointer to ExtendedVCB for the volume to free space on
        !           447: ;________________________________________________________________________________
        !           448: */
        !           449: void UpdateVCBFreeBlks( ExtendedVCB *vcb )
        !           450: {
        !           451:        UInt32  hfsCompatabilityFreeBlocks;
        !           452:        UInt32  plusBlockSize;
        !           453:        UInt32  hfsBlockSize;
        !           454:        
        !           455:        #if DEBUG_BUILD
        !           456:                if ( vcb->vcbSigWord == kHFSSigWord && vcb->freeBlocks > 0xFFFF )
        !           457:                        DebugStr("\p UpdateVCBFreeBlks: freeBlocks overflow!");
        !           458:        #endif
        !           459:        
        !           460:        //
        !           461:        //�� The following calculation will overflow on volumes 2 TB or bigger.
        !           462:        //
        !           463:        //      We divide both the true allocation block size and HFS-compatible allocation block size
        !           464:        //      by 512 since that reduces the magnitude of the numbers (with no overflow until
        !           465:        //      4 GB * 512 = 2 TB).  Since allocation blocks for both HFS and HFS Plus must be a
        !           466:        //      multiple of 512, then there will be no roundoff error.
        !           467:        //
        !           468:        plusBlockSize = vcb->blockSize >> 9;                            //      Divide by 512
        !           469:        hfsBlockSize = ((UInt32) vcb->vcbAlBlkSiz) >> 9;        //      Divide by 512
        !           470:        
        !           471:        hfsCompatabilityFreeBlocks = (vcb->freeBlocks * plusBlockSize) / hfsBlockSize;
        !           472:        
        !           473:        if ( hfsCompatabilityFreeBlocks > 0xFFFF )
        !           474:                vcb->vcbFreeBks = 0xFFFF;
        !           475:        else
        !           476:                vcb->vcbFreeBks = (UInt16) hfsCompatabilityFreeBlocks;
        !           477: }
        !           478: 
        !           479: 
        !           480: /*
        !           481: ;________________________________________________________________________________
        !           482: ;
        !           483: ; Routine:        BlkDealloc
        !           484: ;
        !           485: ; Function:    Update the bitmap to deallocate a run of disk allocation blocks
        !           486: ;
        !           487: ; Input Arguments:
        !           488: ;       vcb            - Pointer to ExtendedVCB for the volume to free space on
        !           489: ;       firstBlock     - First allocation block to be freed
        !           490: ;       numBlocks      - Number of allocation blocks to free up (must be > 0!)
        !           491: ;
        !           492: ; Output:
        !           493: ;       (result)       - Result code
        !           494: ;
        !           495: ; Side effects:
        !           496: ;       The volume bitmap is read and updated; the volume bitmap cache may be changed.
        !           497: ;
        !           498: ; Modification history:
        !           499: ;
        !           500: ;      <06Oct85>  PWD  Changed to check for error after calls to ReadBM and NextWord
        !           501: ;                                      Now calls NextBit to read successive bits from the bitmap
        !           502: ;________________________________________________________________________________
        !           503: */
        !           504: 
        !           505: OSErr BlockDeallocate (
        !           506:        ExtendedVCB             *vcb,                   //      Which volume to deallocate space on
        !           507:        UInt32                  firstBlock,             //      First block in range to deallocate
        !           508:        UInt32                  numBlocks)              //      Number of contiguous blocks to deallocate
        !           509: {
        !           510:        OSErr                   err;
        !           511:        
        !           512: #if HFSInstrumentation
        !           513:        InstTraceClassRef       trace;
        !           514:        InstEventTag            eventTag;
        !           515:        
        !           516:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockDeallocate", 'hfs+', kInstEnableClassMask, &trace);
        !           517:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !           518: 
        !           519:        eventTag = InstCreateEventTag();
        !           520:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !           521: #endif
        !           522: 
        !           523:        //
        !           524:        //      If no blocks to deallocate, then exit early
        !           525:        //
        !           526:        if (numBlocks == 0) {
        !           527:                err = noErr;
        !           528:                goto Exit;
        !           529:        }
        !           530: 
        !           531:        //
        !           532:        //      Call internal routine to free the sequence of blocks
        !           533:        //
        !           534:        err = BlockMarkFree(vcb, firstBlock, numBlocks);
        !           535:        if (err)
        !           536:                goto Exit;
        !           537: 
        !           538:        //
        !           539:        //      Update the volume's free block count, and mark the VCB as dirty.
        !           540:        //
        !           541:        VCB_LOCK(vcb);
        !           542:        vcb->freeBlocks += numBlocks;
        !           543:        VCB_UNLOCK(vcb);
        !           544:        UpdateVCBFreeBlks( vcb );
        !           545:        MarkVCBDirty(vcb);
        !           546: 
        !           547: Exit:
        !           548: 
        !           549: #if HFSInstrumentation
        !           550:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !           551: #endif
        !           552: 
        !           553:        return err;
        !           554: }
        !           555: 
        !           556: 
        !           557: 
        !           558: /*
        !           559: ;_______________________________________________________________________
        !           560: ;
        !           561: ; Routine:             BlkChk
        !           562: ;
        !           563: ; Input Arguments:
        !           564: ;      extents         -- pointer to extent record
        !           565: ;      vcb                     -- ExtendedVCB for volume
        !           566: ;
        !           567: ; Output:
        !           568: ;      (result)        -- 0 if block was already allocated
        !           569: ;                                                                 -1 otherwise
        !           570: ;
        !           571: ; Called By:   MountVol
        !           572: ; Function:    Make sure the extents in the extent record are marked as
        !           573: ;                              allocated in the volume bitmap.  The allocation blocks mapped
        !           574: ;                              by the extent record are marked in the bitmap if they weren't
        !           575: ;                              already marked (in which case D0 is set).
        !           576: ;
        !           577: ; Modification History:
        !           578: ;        3-Jul-85      PWD  New today.
        !           579: ;       <06Oct85>      PWD  Added check for errors after calls to ReadBM and NextWord
        !           580: ;_______________________________________________________________________
        !           581: */
        !           582: 
        !           583: SInt32 BlockCheck (
        !           584:        ExtendedVCB                     *vcb,                   //      Volume to check
        !           585:        HFSPlusExtentRecord     extents)                //      List of extents to verify as allocated
        !           586: {
        !           587:        OSErr   err;
        !           588:        Boolean trouble = false;                //      Assume everything went OK
        !           589:        Boolean foundUnmarkedBlock;     
        !           590:        int             i, extentsPerRecord;
        !           591: 
        !           592: #if HFSInstrumentation
        !           593:        InstTraceClassRef       trace;
        !           594:        InstEventTag            eventTag;
        !           595:        
        !           596:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockCheck", 'hfs+', kInstEnableClassMask, &trace);
        !           597:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !           598: 
        !           599:        eventTag = InstCreateEventTag();
        !           600:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !           601: #endif
        !           602: 
        !           603:        if (vcb->vcbSigWord == kHFSPlusSigWord)
        !           604:                extentsPerRecord = kHFSPlusExtentDensity;
        !           605:        else
        !           606:                extentsPerRecord = kHFSExtentDensity;
        !           607:        
        !           608: 
        !           609: 
        !           610:        for (i = 0; i < extentsPerRecord; i++) {
        !           611:                if (extents[i].blockCount != 0) {               //      if no blocks, then no extent to check
        !           612:                        err = BlockVerifyAllocated(vcb, extents[i].startBlock, extents[i].blockCount, &foundUnmarkedBlock);
        !           613:                        if (err)
        !           614:                                return err;
        !           615:                        trouble |= foundUnmarkedBlock;
        !           616:                }
        !           617:        }
        !           618: 
        !           619: #if HFSInstrumentation
        !           620:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !           621: #endif
        !           622: 
        !           623:        if (trouble)
        !           624:                return -1;
        !           625:        else
        !           626:                return 0;
        !           627: }
        !           628: 
        !           629: 
        !           630: 
        !           631: /*
        !           632: ;_______________________________________________________________________
        !           633: ;
        !           634: ; Routine:             UpdateFree
        !           635: ; Arguments:   vcb     -- ExtendedVCB for volume
        !           636: ;
        !           637: ; Called By:   MountVol
        !           638: ; Function:    This routine is used as part of the MountVol consistency check
        !           639: ;                              to figure out the number of free allocation blocks in the volume.
        !           640: ;
        !           641: ; Modification History:
        !           642: ;      <08Sep85>  LAK  New today.
        !           643: ;      <06Oct85>  PWD  Added explicit check for errors after calls to ReadBM, NextWord
        !           644: ;                                      Now calls NextBit.
        !           645: ;_______________________________________________________________________
        !           646: */
        !           647: 
        !           648: OSErr UpdateFreeCount (
        !           649:        ExtendedVCB     *vcb)                           //      Volume whose free block count should be updated
        !           650: {
        !           651:        OSErr                   err;
        !           652:        register UInt32 wordsLeft;              //      Number of words left in this bitmap block
        !           653:        register UInt32 numBlocks;              //      Number of blocks left to scan
        !           654:        register UInt32 freeCount;              //      Running count of free blocks found so far
        !           655:        register UInt32 temp;
        !           656:        UInt32                  blockNum;               //      Block number of first block in this bitmap block
        !           657:        UInt32                  *buffer = NULL; //      Pointer to bitmap block
        !           658:        register UInt32 *currentWord;   //      Pointer to current word in bitmap block
        !           659:        
        !           660: #if HFSInstrumentation
        !           661:        InstTraceClassRef       trace;
        !           662:        InstEventTag            eventTag;
        !           663:        
        !           664:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:UpdateFreeCount", 'hfs+', kInstEnableClassMask, &trace);
        !           665:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !           666: 
        !           667:        eventTag = InstCreateEventTag();
        !           668:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !           669: #endif
        !           670: 
        !           671:        //
        !           672:        //      Pre-read the first bitmap block
        !           673:        //
        !           674: 
        !           675:        err = ReadBitmapBlock(vcb, 0, &buffer);
        !           676:        if (err != noErr) goto Exit;
        !           677: 
        !           678:        //
        !           679:        //      Initialize buffer stuff
        !           680:        //
        !           681:        currentWord = buffer;
        !           682:        wordsLeft = kWordsPerBlock;
        !           683:        numBlocks = vcb->totalBlocks;
        !           684:        freeCount = 0;
        !           685:        blockNum = 0;
        !           686:        
        !           687:        //
        !           688:        //      Scan whole words first
        !           689:        //
        !           690:        
        !           691:        while (numBlocks >= kBitsPerWord) {
        !           692:                //      See if it's time to move to the next bitmap block
        !           693:                if (wordsLeft == 0) {
        !           694:                        //      Read in the next bitmap block
        !           695:                        blockNum += kBitsPerBlock;                              //      generate a block number in the next bitmap block
        !           696:                        
        !           697: #if EXPLICIT_BUFFER_RELEASES
        !           698:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !           699:                        if (err != noErr) goto Exit;
        !           700:                        buffer = NULL;
        !           701: #endif
        !           702:                        err = ReadBitmapBlock(vcb, blockNum, &buffer);
        !           703:                        if (err != noErr) goto Exit;
        !           704:                        
        !           705:                        //      Readjust currentWord, wordsLeft
        !           706:                        currentWord = buffer;
        !           707:                        wordsLeft = kWordsPerBlock;
        !           708:                }
        !           709:                
        !           710:                //      We count free blocks by inverting the word in the bitmap and counting set bits.
        !           711:                temp = ~(*currentWord);
        !           712:                while (temp) {
        !           713:                        ++freeCount;
        !           714:                        temp &= temp-1;                 //      this clears least significant bit that is currently set
        !           715:                }
        !           716: 
        !           717:                numBlocks -= kBitsPerWord;
        !           718:                ++currentWord;                                                          //      move to next word
        !           719:                --wordsLeft;                                                            //      one less word left in this block
        !           720:        }
        !           721:        
        !           722:        //
        !           723:        //      Check any remaining blocks.
        !           724:        //
        !           725:        
        !           726:        if (numBlocks != 0) {
        !           727:                if (wordsLeft == 0) {
        !           728:                        //      Read in the next bitmap block
        !           729:                        blockNum += kBitsPerBlock;                              //      generate a block number in the next bitmap block
        !           730:                        
        !           731: #if EXPLICIT_BUFFER_RELEASES
        !           732:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !           733:                        if (err != noErr) goto Exit;
        !           734:                        buffer = NULL;
        !           735: #endif
        !           736:                        err = ReadBitmapBlock(vcb, blockNum, &buffer);
        !           737:                        if (err != noErr) goto Exit;
        !           738:                        
        !           739:                        //      Readjust currentWord, wordsLeft
        !           740:                        currentWord = buffer;
        !           741:                        wordsLeft = kWordsPerBlock;
        !           742:                }
        !           743:                
        !           744:                //      We count free blocks by inverting the word in the bitmap and counting set bits.
        !           745:                temp = ~(*currentWord);
        !           746:                while (numBlocks != 0) {
        !           747:                        if (temp & kHighBitInWordMask)
        !           748:                                ++freeCount;
        !           749:                        temp <<= 1;
        !           750:                        --numBlocks;
        !           751:                }
        !           752:        }
        !           753: 
        !           754:        VCB_LOCK(vcb);
        !           755:        vcb->freeBlocks = freeCount;
        !           756:        VCB_UNLOCK(vcb);
        !           757:        UpdateVCBFreeBlks( vcb );
        !           758: 
        !           759: Exit:
        !           760: 
        !           761: #if EXPLICIT_BUFFER_RELEASES
        !           762:        if (buffer) {
        !           763:                (void)RelBlock_glue((Ptr)buffer, rbDefault);            /* Ignore any additional errors */
        !           764:        };
        !           765: #endif
        !           766: 
        !           767: #if HFSInstrumentation
        !           768:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !           769: #endif
        !           770: 
        !           771:        return err;
        !           772: }
        !           773: 
        !           774: 
        !           775: 
        !           776: /*
        !           777: ;_______________________________________________________________________
        !           778: ;
        !           779: ; Routine:             AllocateFreeSpace
        !           780: ; Arguments:   vcb     -- ExtendedVCB for volume
        !           781: ;
        !           782: ; Called By:   HFSDiskInitComponent
        !           783: ; Function:    This routine is used as part of DiskInit to create an
        !           784: ;                              embedded HFS+ volume.
        !           785: ;
        !           786: ; Note: Assumes that the free space is contiguous (true for a freshly erased disk)
        !           787: ;_______________________________________________________________________
        !           788: */
        !           789: 
        !           790: OSErr AllocateFreeSpace (
        !           791:        ExtendedVCB             *vcb,                           //      Volume whose free space is about to be expropriated
        !           792:        UInt32                  *startBlock,            // return where free space starts
        !           793:        UInt32                  *actualBlocks)          // return the number of blocks in free space
        !           794: {
        !           795:        OSErr                   err;
        !           796: 
        !           797:        err = BlockAllocateAny(vcb, 0, vcb->totalBlocks, vcb->freeBlocks, startBlock, actualBlocks);
        !           798: 
        !           799:        if (err == noErr) {
        !           800:                VCB_LOCK(vcb);
        !           801:                vcb->freeBlocks = 0;    // sorry, no more blocks left!
        !           802:                vcb->vcbFreeBks = 0;
        !           803:                VCB_UNLOCK(vcb);
        !           804:                MarkVCBDirty(vcb);
        !           805:        }
        !           806:        
        !           807:        return err;
        !           808: }
        !           809: 
        !           810: /*
        !           811: ;_______________________________________________________________________
        !           812: ;
        !           813: ; Routine:     DivideAndRoundUp
        !           814: ;
        !           815: ; Function:    Divide numerator by denominator, rounding up the result if there
        !           816: ;                      was a remainder.  This is frequently used for computing the number
        !           817: ;                      of whole and/or partial blocks used by some count of bytes.
        !           818: ;_______________________________________________________________________
        !           819: */
        !           820: UInt32 DivideAndRoundUp(
        !           821:        UInt32 numerator,
        !           822:        UInt32 denominator)
        !           823: {
        !           824:        UInt32  quotient;
        !           825:        
        !           826:        quotient = numerator / denominator;
        !           827:        if (quotient * denominator != numerator)
        !           828:                quotient++;
        !           829:        
        !           830:        return quotient;
        !           831: }
        !           832: 
        !           833: 
        !           834: 
        !           835: /*
        !           836: ;_______________________________________________________________________
        !           837: ;
        !           838: ; Routine:     ReadBitmapBlock
        !           839: ;
        !           840: ; Function:    Read in a bitmap block corresponding to a given allocation
        !           841: ;                      block.  Return a pointer to the bitmap block.
        !           842: ;
        !           843: ; Inputs:
        !           844: ;      vcb                     --      Pointer to ExtendedVCB
        !           845: ;      block           --      Allocation block whose bitmap block is desired
        !           846: ;
        !           847: ; Outputs:
        !           848: ;      buffer          --      Pointer to bitmap block corresonding to "block"
        !           849: ;_______________________________________________________________________
        !           850: */
        !           851: static OSErr ReadBitmapBlock(
        !           852:        ExtendedVCB             *vcb,
        !           853:        UInt32                  block,
        !           854:        UInt32                  **buffer)
        !           855: {
        !           856:        OSErr                   err;
        !           857: 
        !           858: #if HFSInstrumentation
        !           859:        InstTraceClassRef       trace;
        !           860:        InstEventTag            eventTag;
        !           861:        
        !           862:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:ReadBitmapBlock", 'hfs+', kInstEnableClassMask, &trace);
        !           863:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !           864: 
        !           865:        eventTag = block;               // a cheap way to get the block number into the log
        !           866:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !           867: #endif
        !           868: 
        !           869:        err = noErr;
        !           870: 
        !           871:   #if TARGET_OS_RHAPSODY
        !           872:        RequireFileLock(vcb->extentsRefNum, false);     /* bitmap blocks are covered by the Extents B-tree lock */
        !           873:   #endif
        !           874: 
        !           875:        if (vcb->vcbSigWord == kHFSSigWord) {
        !           876:                //
        !           877:                //      HFS: Turn block number into physical block offset within the
        !           878:                //      bitmap, and then the physical block within the volume.
        !           879:                //
        !           880:                block /= kBitsPerBlock;         // block offset within bitmap
        !           881:                block += vcb->vcbVBMSt;         // block within whole volume
        !           882:        }
        !           883:        else {
        !           884:                FCB             *allocFile;
        !           885:                UInt32  startBlock;
        !           886:                UInt32  availableBytes;
        !           887:                
        !           888:                //
        !           889:                //      HFS+: Read from allocation file.  We simply convert the block number into a byte
        !           890:                //      offset within the allocation file and then determine which block that byte is in.
        !           891:                //
        !           892:                allocFile = GetFileControlBlock(vcb->allocationsRefNum);
        !           893: 
        !           894:                //
        !           895:                //      Find out which physical block holds byte #offset in allocation file.  Note that we
        !           896:                //      map only 1 byte (the one we asked for).
        !           897:                //
        !           898:                err = MapFileBlockC(vcb, allocFile, 1, block/kBitsPerByte, &startBlock, &availableBytes);
        !           899:                block = startBlock;
        !           900:        }
        !           901: 
        !           902:        if (err == noErr) {
        !           903: #if TARGET_OS_MAC
        !           904:             err = GetBlock_glue(
        !           905: #if EXPLICIT_BUFFER_RELEASES
        !           906:                                                                0,                                              // No options
        !           907: #else
        !           908:                                 gbReleaseMask,                 // Release block immediately.  We only work on one
        !           909:                                                                                //      block at a time.  Call MarkBlock later if dirty.
        !           910: #endif
        !           911:                                 block,                                 // Physical block on volume
        !           912:                                 (Ptr *) buffer,                        //      A place to return the buffer pointer
        !           913:                                 vcb->vcbVRefNum,               //      Which volume to read from
        !           914:                                 vcb);                                  //      Cache queue header for volume bitmap
        !           915: #else
        !           916:             err = GetBlock_glue(
        !           917: #if EXPLICIT_BUFFER_RELEASES
        !           918:                                                                0,                                              // No options
        !           919: #else
        !           920:                                 gbReleaseMask,                 // Release block immediately.  We only work on one
        !           921:                                                                                                                // block at a time.  Call MarkBlock later if dirty.
        !           922: #endif
        !           923:                                 block,                                 // Physical block on volume
        !           924:                                 (Ptr *) buffer,                        // A place to return the buffer pointer
        !           925:                                 kNoFileReference,              // Not a file read
        !           926:                                 vcb);                                  // Volume to read from
        !           927: #endif
        !           928:        }
        !           929: 
        !           930: #if HFSInstrumentation
        !           931:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !           932: #endif
        !           933: 
        !           934:        return err;
        !           935: }
        !           936: 
        !           937: 
        !           938: 
        !           939: /*
        !           940: _______________________________________________________________________
        !           941: 
        !           942: Routine:       BlockAllocateContig
        !           943: 
        !           944: Function:      Allocate a contiguous group of allocation blocks.  The
        !           945:                        allocation is all-or-nothing.  The caller guarantees that
        !           946:                        there are enough free blocks (though they may not be
        !           947:                        contiguous, in which case this call will fail).
        !           948: 
        !           949: Inputs:
        !           950:        vcb                             Pointer to volume where space is to be allocated
        !           951:        startingBlock   Preferred first block for allocation
        !           952:        minBlocks               Minimum number of contiguous blocks to allocate
        !           953:        maxBlocks               Maximum number of contiguous blocks to allocate
        !           954: 
        !           955: Outputs:
        !           956:        actualStartBlock        First block of range allocated, or 0 if error
        !           957:        actualNumBlocks         Number of blocks allocated, or 0 if error
        !           958: _______________________________________________________________________
        !           959: */
        !           960: static OSErr BlockAllocateContig(
        !           961:        ExtendedVCB             *vcb,
        !           962:        UInt32                  startingBlock,
        !           963:        UInt32                  minBlocks,
        !           964:        UInt32                  maxBlocks,
        !           965:        UInt32                  *actualStartBlock,
        !           966:        UInt32                  *actualNumBlocks)
        !           967: {
        !           968:        OSErr   err;
        !           969: 
        !           970:        //
        !           971:        //      Find a contiguous group of blocks at least minBlocks long.
        !           972:        //      Determine the number of contiguous blocks available (up
        !           973:        //      to maxBlocks).
        !           974:        //
        !           975:        err = BlockFindContiguous(vcb, startingBlock, vcb->totalBlocks, minBlocks, maxBlocks,
        !           976:                                                                  actualStartBlock, actualNumBlocks);
        !           977:        if (err == dskFulErr) {
        !           978:                //�� Should constrain the endingBlock here, so we don't bother looking for ranges
        !           979:                //�� that start after startingBlock, since we already checked those.
        !           980:                err = BlockFindContiguous(vcb, 0, vcb->totalBlocks, minBlocks, maxBlocks,
        !           981:                                                                          actualStartBlock, actualNumBlocks);
        !           982:        }
        !           983:        if (err != noErr) goto Exit;
        !           984: 
        !           985:        //
        !           986:        //      Now mark those blocks allocated.
        !           987:        //
        !           988:        err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
        !           989:        
        !           990: Exit:
        !           991:        if (err != noErr) {
        !           992:                *actualStartBlock = 0;
        !           993:                *actualNumBlocks = 0;
        !           994:        }
        !           995:        
        !           996:        return err;
        !           997: }
        !           998: 
        !           999: extern OSErr LookupBufferMapping(caddr_t bufferAddress, struct buf **bpp, int *mappingIndexPtr);
        !          1000: 
        !          1001: /*
        !          1002: _______________________________________________________________________
        !          1003: 
        !          1004: Routine:       BlockAllocateAny
        !          1005: 
        !          1006: Function:      Allocate one or more allocation blocks.  If there are fewer
        !          1007:                        free blocks than requested, all free blocks will be
        !          1008:                        allocated.  The caller guarantees that there is at least
        !          1009:                        one free block.
        !          1010: 
        !          1011: Inputs:
        !          1012:        vcb                             Pointer to volume where space is to be allocated
        !          1013:        startingBlock   Preferred first block for allocation
        !          1014:        endingBlock             Last block to check + 1
        !          1015:        maxBlocks               Maximum number of contiguous blocks to allocate
        !          1016: 
        !          1017: Outputs:
        !          1018:        actualStartBlock        First block of range allocated, or 0 if error
        !          1019:        actualNumBlocks         Number of blocks allocated, or 0 if error
        !          1020: _______________________________________________________________________
        !          1021: */
        !          1022: OSErr BlockAllocateAny(
        !          1023:        ExtendedVCB             *vcb,
        !          1024:        UInt32                  startingBlock,
        !          1025:        register UInt32 endingBlock,
        !          1026:        UInt32                  maxBlocks,
        !          1027:        UInt32                  *actualStartBlock,
        !          1028:        UInt32                  *actualNumBlocks)
        !          1029: {
        !          1030:        OSErr                   err;
        !          1031:        register UInt32 block;                  //      current block number
        !          1032:        register UInt32 currentWord;    //      Pointer to current word within bitmap block
        !          1033:        register UInt32 bitMask;                //      Word with given bits already set (ready to OR in)
        !          1034:        register UInt32 wordsLeft;              //      Number of words left in this bitmap block
        !          1035:     UInt32                     *buffer = NULL;
        !          1036:     UInt32                     *currCache = NULL;
        !          1037: 
        !          1038: #if DIAGNOSTIC
        !          1039:     struct buf *bp = NULL;
        !          1040:     int mappingEntry;
        !          1041: #endif
        !          1042: 
        !          1043:        //      Since this routine doesn't wrap around
        !          1044:        if (maxBlocks > (endingBlock - startingBlock)) {
        !          1045:                maxBlocks = endingBlock - startingBlock;
        !          1046:        }
        !          1047: 
        !          1048:     DBG_TREE (("\nAllocating starting at %ld, maxblocks %ld\n", startingBlock, maxBlocks));    
        !          1049:        //
        !          1050:        //      Pre-read the first bitmap block
        !          1051:        //
        !          1052:     err = ReadBitmapBlock(vcb, startingBlock, &currCache);
        !          1053:     DBG_TREE (("\n1. Read bit map at %ld, buffer is 0x%x\n", startingBlock, (int)currCache));  
        !          1054:        if (err != noErr) goto Exit;
        !          1055:     buffer = currCache;
        !          1056:     MarkBlock_glue((Ptr) currCache);           //      this block will be dirty
        !          1057:     DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
        !          1058: 
        !          1059:        //
        !          1060:        //      Set up the current position within the block
        !          1061:        //
        !          1062:        {
        !          1063:                UInt32 wordIndexInBlock;
        !          1064: 
        !          1065:                wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord;
        !          1066:                buffer += wordIndexInBlock;
        !          1067:                wordsLeft = kWordsPerBlock - wordIndexInBlock;
        !          1068:                currentWord = *buffer;
        !          1069:                bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask);
        !          1070:        }
        !          1071:        
        !          1072:        //
        !          1073:        //      Find the first unallocated block
        !          1074:        //
        !          1075:        block=startingBlock;
        !          1076:        while (block < endingBlock) {
        !          1077:                if ((currentWord & bitMask) == 0)
        !          1078:                        break;
        !          1079:                
        !          1080:                //      Next bit
        !          1081:                ++block;
        !          1082:                bitMask >>= 1;
        !          1083:                if (bitMask == 0) {
        !          1084:                        //      Next word
        !          1085:                        bitMask = kHighBitInWordMask;
        !          1086:                        ++buffer;
        !          1087:                        
        !          1088:                        if (--wordsLeft == 0) {
        !          1089:                                //      Next block
        !          1090: #if EXPLICIT_BUFFER_RELEASES
        !          1091:                DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
        !          1092:                err = RelBlock_glue((Ptr)currCache, rbDefault);
        !          1093:                                if (err != noErr) goto Exit;
        !          1094:                 buffer = currCache = NULL;
        !          1095: #endif
        !          1096:                 err = ReadBitmapBlock(vcb, block, &currCache);
        !          1097:                                if (err != noErr) goto Exit;
        !          1098:                 buffer = currCache;
        !          1099:                 DBG_TREE (("\n2. Read bit map at %ld, buffer is 0x%x\n", block, (int)currCache));      
        !          1100:                 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
        !          1101:                 MarkBlock_glue((Ptr) currCache);               //      this block will be dirty
        !          1102: 
        !          1103:                                wordsLeft = kWordsPerBlock;
        !          1104:                        }
        !          1105:                        
        !          1106:                        currentWord = *buffer;
        !          1107:                }
        !          1108:        }
        !          1109: 
        !          1110:        //      Did we get to the end of the bitmap before finding a free block?
        !          1111:        //      If so, then couldn't allocate anything.
        !          1112:        if (block == endingBlock) {
        !          1113:                err = dskFulErr;
        !          1114:                goto Exit;
        !          1115:        }
        !          1116: 
        !          1117:        //      Return the first block in the allocated range
        !          1118:        *actualStartBlock = block;
        !          1119:        
        !          1120:        //      If we could get the desired number of blocks before hitting endingBlock,
        !          1121:        //      then adjust endingBlock so we won't keep looking.  Ideally, the comparison
        !          1122:        //      would be (block + maxBlocks) < endingBlock, but that could overflow.  The
        !          1123:        //      comparison below yields identical results, but without overflow.
        !          1124:        if (block < (endingBlock-maxBlocks)) {
        !          1125:                endingBlock = block + maxBlocks;        //      if we get this far, we've found enough
        !          1126:        }
        !          1127:        
        !          1128:        //
        !          1129:        //      Allocate all of the consecutive blocks
        !          1130:        //
        !          1131:        while ((currentWord & bitMask) == 0) {
        !          1132:                //      Allocate this block
        !          1133:                currentWord |= bitMask;
        !          1134:                
        !          1135:                //      Move to the next block.  If no more, then exit.
        !          1136:                ++block;
        !          1137:                if (block == endingBlock)
        !          1138:                        break;
        !          1139: 
        !          1140:                //      Next bit
        !          1141:                bitMask >>= 1;
        !          1142:                if (bitMask == 0) {
        !          1143:                        *buffer = currentWord;                                  //      update value in bitmap
        !          1144:                        
        !          1145:                        //      Next word
        !          1146:                        bitMask = kHighBitInWordMask;
        !          1147:                        ++buffer;
        !          1148:                        
        !          1149:                        if (--wordsLeft == 0) {
        !          1150:                                //      Next block
        !          1151: #if EXPLICIT_BUFFER_RELEASES
        !          1152:                DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
        !          1153:                        err = RelBlock_glue((Ptr)currCache, rbDefault);
        !          1154:                                if (err != noErr) goto Exit;
        !          1155:                 buffer = currCache = NULL;
        !          1156: #endif
        !          1157:                 err = ReadBitmapBlock(vcb, block, &currCache);
        !          1158:                                if (err != noErr) goto Exit;
        !          1159:                 buffer = currCache;
        !          1160:                 DBG_TREE (("\n3. Read bit map at %ld, buffer is 0x%x\n", block, (int)currCache));      
        !          1161:                 DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
        !          1162:                 MarkBlock_glue((Ptr) currCache);               //      this block will be dirty
        !          1163: 
        !          1164:                                wordsLeft = kWordsPerBlock;
        !          1165:                        }
        !          1166:                        
        !          1167:                        currentWord = *buffer;
        !          1168:                }
        !          1169:        }
        !          1170:        *buffer = currentWord;                                                  //      update the last change
        !          1171: 
        !          1172: Exit:
        !          1173:        if (err == noErr) {
        !          1174:                *actualNumBlocks = block - *actualStartBlock;
        !          1175:        }
        !          1176:        else {
        !          1177:                *actualStartBlock = 0;
        !          1178:                *actualNumBlocks = 0;
        !          1179:        }
        !          1180:        
        !          1181: #if EXPLICIT_BUFFER_RELEASES
        !          1182:     if (currCache) {
        !          1183:         DBG_ASSERT(! LookupBufferMapping((caddr_t)currCache, &bp, &mappingEntry));
        !          1184:         (void)RelBlock_glue((Ptr)currCache, rbDefault);                /* Ignore any additional errors */
        !          1185:         };
        !          1186: #endif
        !          1187: 
        !          1188:        return err;
        !          1189: }
        !          1190: 
        !          1191: 
        !          1192: 
        !          1193: /*
        !          1194: _______________________________________________________________________
        !          1195: 
        !          1196: Routine:       BlockMarkAllocated
        !          1197: 
        !          1198: Function:      Mark a contiguous group of blocks as allocated (set in the
        !          1199:                        bitmap).  It assumes those bits are currently marked
        !          1200:                        deallocated (clear in the bitmap).
        !          1201: 
        !          1202: Inputs:
        !          1203:        vcb                             Pointer to volume where space is to be allocated
        !          1204:        startingBlock   First block number to mark as allocated
        !          1205:        numBlocks               Number of blocks to mark as allocated
        !          1206: _______________________________________________________________________
        !          1207: */
        !          1208: static OSErr BlockMarkAllocated(
        !          1209:        ExtendedVCB             *vcb,
        !          1210:        UInt32                  startingBlock,
        !          1211:        register UInt32 numBlocks)
        !          1212: {
        !          1213:        OSErr                   err;
        !          1214:        register UInt32 *currentWord;   //      Pointer to current word within bitmap block
        !          1215:        register UInt32 wordsLeft;              //      Number of words left in this bitmap block
        !          1216:        register UInt32 bitMask;                //      Word with given bits already set (ready to OR in)
        !          1217:        UInt32                  firstBit;               //      Bit index within word of first bit to allocate
        !          1218:        UInt32                  numBits;                //      Number of bits in word to allocate
        !          1219:        UInt32                  *buffer = NULL;
        !          1220: 
        !          1221: #if HFSInstrumentation
        !          1222:        InstTraceClassRef       trace;
        !          1223:        InstEventTag            eventTag;
        !          1224:        
        !          1225:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockMarkAllocated", 'hfs+', kInstEnableClassMask, &trace);
        !          1226:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !          1227: 
        !          1228:        eventTag = InstCreateEventTag();
        !          1229:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !          1230: #endif
        !          1231: 
        !          1232:        //
        !          1233:        //      Pre-read the bitmap block containing the first word of allocation
        !          1234:        //
        !          1235: 
        !          1236:        err = ReadBitmapBlock(vcb, startingBlock, &buffer);
        !          1237:        if (err != noErr) goto Exit;
        !          1238:        MarkBlock_glue((Ptr) buffer);           //      this block will be dirty
        !          1239: 
        !          1240:        //
        !          1241:        //      Initialize currentWord, and wordsLeft.
        !          1242:        //
        !          1243:        {
        !          1244:                UInt32 wordIndexInBlock;
        !          1245: 
        !          1246:                wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord;
        !          1247:                currentWord = buffer + wordIndexInBlock;
        !          1248:                wordsLeft = kWordsPerBlock - wordIndexInBlock;
        !          1249:        }
        !          1250:        
        !          1251:        //
        !          1252:        //      If the first block to allocate doesn't start on a word
        !          1253:        //      boundary in the bitmap, then treat that first word
        !          1254:        //      specially.
        !          1255:        //
        !          1256: 
        !          1257:        firstBit = startingBlock % kBitsPerWord;
        !          1258:        if (firstBit != 0) {
        !          1259:                bitMask = kAllBitsSetInWord >> firstBit;        //      turn off all bits before firstBit
        !          1260:                numBits = kBitsPerWord - firstBit;                      //      number of remaining bits in this word
        !          1261:                if (numBits > numBlocks) {
        !          1262:                        numBits = numBlocks;                                    //      entire allocation is inside this one word
        !          1263:                        bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits));        //      turn off bits after last
        !          1264:                }
        !          1265: #if DEBUG_BUILD
        !          1266:                if ((*currentWord & bitMask) != 0) {
        !          1267:                        DebugStr("\pFATAL: blocks already allocated!");
        !          1268:                        //err = fsDSIntErr;
        !          1269:                        //goto Exit;
        !          1270:                }
        !          1271: #endif
        !          1272:                *currentWord |= bitMask;                                        //      set the bits in the bitmap
        !          1273:                numBlocks -= numBits;                                           //      adjust number of blocks left to allocate
        !          1274: 
        !          1275:                ++currentWord;                                                          //      move to next word
        !          1276:                --wordsLeft;                                                            //      one less word left in this block
        !          1277:        }
        !          1278: 
        !          1279:        //
        !          1280:        //      Allocate whole words (32 blocks) at a time.
        !          1281:        //
        !          1282: 
        !          1283:        bitMask = kAllBitsSetInWord;                                    //      put this in a register for 68K
        !          1284:        while (numBlocks >= kBitsPerWord) {
        !          1285:                if (wordsLeft == 0) {
        !          1286:                        //      Read in the next bitmap block
        !          1287:                        startingBlock += kBitsPerBlock;                 //      generate a block number in the next bitmap block
        !          1288:                        
        !          1289: #if EXPLICIT_BUFFER_RELEASES
        !          1290:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1291:                        if (err != noErr) goto Exit;
        !          1292:                        buffer = NULL;
        !          1293: #endif
        !          1294:                        err = ReadBitmapBlock(vcb, startingBlock, &buffer);
        !          1295:                        if (err != noErr) goto Exit;
        !          1296:                        MarkBlock_glue((Ptr) buffer);                   //      this block will be dirty
        !          1297:                        
        !          1298:                        //      Readjust currentWord and wordsLeft
        !          1299:                        currentWord = buffer;
        !          1300:                        wordsLeft = kWordsPerBlock;
        !          1301:                }
        !          1302: #if DEBUG_BUILD
        !          1303:                if (*currentWord != 0) {
        !          1304:                        DebugStr("\pFATAL: blocks already allocated!");
        !          1305:                        //err = fsDSIntErr;
        !          1306:                        //goto Exit;
        !          1307:                }
        !          1308: #endif
        !          1309:                *currentWord = bitMask;
        !          1310:                numBlocks -= kBitsPerWord;
        !          1311: 
        !          1312:                ++currentWord;                                                          //      move to next word
        !          1313:                --wordsLeft;                                                            //      one less word left in this block
        !          1314:        }
        !          1315:        
        !          1316:        //
        !          1317:        //      Allocate any remaining blocks.
        !          1318:        //
        !          1319:        
        !          1320:        if (numBlocks != 0) {
        !          1321:                bitMask = ~(kAllBitsSetInWord >> numBlocks);    //      set first numBlocks bits
        !          1322:                if (wordsLeft == 0) {
        !          1323:                        //      Read in the next bitmap block
        !          1324:                        startingBlock += kBitsPerBlock;                         //      generate a block number in the next bitmap block
        !          1325:                        
        !          1326: #if EXPLICIT_BUFFER_RELEASES
        !          1327:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1328:                        if (err != noErr) goto Exit;
        !          1329:                        buffer = NULL;
        !          1330: #endif
        !          1331:                        err = ReadBitmapBlock(vcb, startingBlock, &buffer);
        !          1332:                        if (err != noErr) goto Exit;
        !          1333:                        MarkBlock_glue((Ptr) buffer);                           //      this block will be dirty
        !          1334:                        
        !          1335:                        //      Readjust currentWord and wordsLeft
        !          1336:                        currentWord = buffer;
        !          1337:                        wordsLeft = kWordsPerBlock;
        !          1338:                }
        !          1339: #if DEBUG_BUILD
        !          1340:                if ((*currentWord & bitMask) != 0) {
        !          1341:                        DebugStr("\pFATAL: blocks already allocated!");
        !          1342:                        //err = fsDSIntErr;
        !          1343:                        //goto Exit;
        !          1344:                }
        !          1345: #endif
        !          1346:                *currentWord |= bitMask;                                                //      set the bits in the bitmap
        !          1347: 
        !          1348:                //      No need to update currentWord or wordsLeft
        !          1349:        }
        !          1350: 
        !          1351: Exit:
        !          1352: 
        !          1353: #if EXPLICIT_BUFFER_RELEASES
        !          1354:        if (buffer) {
        !          1355:                (void)RelBlock_glue((Ptr)buffer, rbDefault);            /* Ignore any additional errors */
        !          1356:        };
        !          1357: #endif
        !          1358: 
        !          1359: #if HFSInstrumentation
        !          1360:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !          1361: #endif
        !          1362: 
        !          1363:        return err;
        !          1364: }
        !          1365: 
        !          1366: 
        !          1367: 
        !          1368: /*
        !          1369: _______________________________________________________________________
        !          1370: 
        !          1371: Routine:       BlockMarkFree
        !          1372: 
        !          1373: Function:      Mark a contiguous group of blocks as free (clear in the
        !          1374:                        bitmap).  It assumes those bits are currently marked
        !          1375:                        allocated (set in the bitmap).
        !          1376: 
        !          1377: Inputs:
        !          1378:        vcb                             Pointer to volume where space is to be freed
        !          1379:        startingBlock   First block number to mark as freed
        !          1380:        numBlocks               Number of blocks to mark as freed
        !          1381: _______________________________________________________________________
        !          1382: */
        !          1383: static OSErr BlockMarkFree(
        !          1384:        ExtendedVCB             *vcb,
        !          1385:        UInt32                  startingBlock,
        !          1386:        register UInt32 numBlocks)
        !          1387: {
        !          1388:        OSErr                   err;
        !          1389:        register UInt32 *currentWord;   //      Pointer to current word within bitmap block
        !          1390:        register UInt32 wordsLeft;              //      Number of words left in this bitmap block
        !          1391:        register UInt32 bitMask;                //      Word with given bits already set (ready to OR in)
        !          1392:        UInt32                  firstBit;               //      Bit index within word of first bit to allocate
        !          1393:        UInt32                  numBits;                //      Number of bits in word to allocate
        !          1394:        UInt32                  *buffer = NULL;
        !          1395: 
        !          1396: #if HFSInstrumentation
        !          1397:        InstTraceClassRef       trace;
        !          1398:        InstEventTag            eventTag;
        !          1399:        
        !          1400:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockMarkFree", 'hfs+', kInstEnableClassMask, &trace);
        !          1401:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !          1402: 
        !          1403:        eventTag = InstCreateEventTag();
        !          1404:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !          1405: #endif
        !          1406: 
        !          1407:        //
        !          1408:        //      Pre-read the bitmap block containing the first word of allocation
        !          1409:        //
        !          1410: 
        !          1411:        err = ReadBitmapBlock(vcb, startingBlock, &buffer);
        !          1412:        if (err != noErr) goto Exit;
        !          1413:        MarkBlock_glue((Ptr) buffer);           //      this block will be dirty
        !          1414: 
        !          1415:        //
        !          1416:        //      Initialize currentWord, and wordsLeft.
        !          1417:        //
        !          1418:        {
        !          1419:                UInt32 wordIndexInBlock;
        !          1420: 
        !          1421:                wordIndexInBlock = (startingBlock & kBitsWithinBlockMask) / kBitsPerWord;
        !          1422:                currentWord = buffer + wordIndexInBlock;
        !          1423:                wordsLeft = kWordsPerBlock - wordIndexInBlock;
        !          1424:        }
        !          1425:        
        !          1426:        //
        !          1427:        //      If the first block to free doesn't start on a word
        !          1428:        //      boundary in the bitmap, then treat that first word
        !          1429:        //      specially.
        !          1430:        //
        !          1431: 
        !          1432:        firstBit = startingBlock % kBitsPerWord;
        !          1433:        if (firstBit != 0) {
        !          1434:                bitMask = kAllBitsSetInWord >> firstBit;        //      turn off all bits before firstBit
        !          1435:                numBits = kBitsPerWord - firstBit;                      //      number of remaining bits in this word
        !          1436:                if (numBits > numBlocks) {
        !          1437:                        numBits = numBlocks;                                    //      entire allocation is inside this one word
        !          1438:                        bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits));        //      turn off bits after last
        !          1439:                }
        !          1440: #if DEBUG_BUILD
        !          1441:                if ((*currentWord & bitMask) != bitMask) {
        !          1442:                        DebugStr("\pFATAL: blocks not allocated!");
        !          1443:                        //err = fsDSIntErr;
        !          1444:                        //goto Exit;
        !          1445:                }
        !          1446: #endif
        !          1447:                *currentWord &= ~bitMask;                                       //      clear the bits in the bitmap
        !          1448:                numBlocks -= numBits;                                           //      adjust number of blocks left to free
        !          1449: 
        !          1450:                ++currentWord;                                                          //      move to next word
        !          1451:                --wordsLeft;                                                            //      one less word left in this block
        !          1452:        }
        !          1453: 
        !          1454:        //
        !          1455:        //      Allocate whole words (32 blocks) at a time.
        !          1456:        //
        !          1457: 
        !          1458:        while (numBlocks >= kBitsPerWord) {
        !          1459:                if (wordsLeft == 0) {
        !          1460:                        //      Read in the next bitmap block
        !          1461:                        startingBlock += kBitsPerBlock;                 //      generate a block number in the next bitmap block
        !          1462:                        
        !          1463: #if EXPLICIT_BUFFER_RELEASES
        !          1464:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1465:                        if (err != noErr) goto Exit;
        !          1466:                        buffer = NULL;
        !          1467: #endif
        !          1468:                        err = ReadBitmapBlock(vcb, startingBlock, &buffer);
        !          1469:                        if (err != noErr) goto Exit;
        !          1470:                        MarkBlock_glue((Ptr) buffer);                   //      this block will be dirty
        !          1471:                        
        !          1472:                        //      Readjust currentWord and wordsLeft
        !          1473:                        currentWord = buffer;
        !          1474:                        wordsLeft = kWordsPerBlock;
        !          1475:                }
        !          1476: 
        !          1477: #if DEBUG_BUILD
        !          1478:                if (*currentWord != kAllBitsSetInWord) {
        !          1479:                        DebugStr("\pFATAL: blocks not allocated!");
        !          1480:                        //err = fsDSIntErr;
        !          1481:                        //goto Exit;
        !          1482:                }
        !          1483: #endif
        !          1484:                *currentWord = 0;                                                       //      clear the entire word
        !          1485:                numBlocks -= kBitsPerWord;
        !          1486:                
        !          1487:                ++currentWord;                                                          //      move to next word
        !          1488:                --wordsLeft;                                                            //      one less word left in this block
        !          1489:        }
        !          1490:        
        !          1491:        //
        !          1492:        //      Allocate any remaining blocks.
        !          1493:        //
        !          1494:        
        !          1495:        if (numBlocks != 0) {
        !          1496:                bitMask = ~(kAllBitsSetInWord >> numBlocks);    //      set first numBlocks bits
        !          1497:                if (wordsLeft == 0) {
        !          1498:                        //      Read in the next bitmap block
        !          1499:                        startingBlock += kBitsPerBlock;                         //      generate a block number in the next bitmap block
        !          1500:                        
        !          1501: #if EXPLICIT_BUFFER_RELEASES
        !          1502:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1503:                        if (err != noErr) goto Exit;
        !          1504:                        buffer = NULL;
        !          1505: #endif
        !          1506:                        err = ReadBitmapBlock(vcb, startingBlock, &buffer);
        !          1507:                        if (err != noErr) goto Exit;
        !          1508:                        MarkBlock_glue((Ptr) buffer);                           //      this block will be dirty
        !          1509:                        
        !          1510:                        //      Readjust currentWord and wordsLeft
        !          1511:                        currentWord = buffer;
        !          1512:                        wordsLeft = kWordsPerBlock;
        !          1513:                }
        !          1514: #if DEBUG_BUILD
        !          1515:                if ((*currentWord & bitMask) != bitMask) {
        !          1516:                        DebugStr("\pFATAL: blocks not allocated!");
        !          1517:                        //err = fsDSIntErr;
        !          1518:                        //goto Exit;
        !          1519:                }
        !          1520: #endif
        !          1521:                *currentWord &= ~bitMask;                                               //      clear the bits in the bitmap
        !          1522: 
        !          1523:                //      No need to update currentWord or wordsLeft
        !          1524:        }
        !          1525: 
        !          1526: Exit:
        !          1527: 
        !          1528: #if EXPLICIT_BUFFER_RELEASES
        !          1529:        if (buffer) {
        !          1530:                (void)RelBlock_glue((Ptr)buffer, rbDefault);            /* Ignore any additional errors */
        !          1531:        };
        !          1532: #endif
        !          1533: 
        !          1534: #if HFSInstrumentation
        !          1535:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !          1536: #endif
        !          1537: 
        !          1538:        return err;
        !          1539: }
        !          1540: 
        !          1541: 
        !          1542: 
        !          1543: static OSErr BlockVerifyAllocated(
        !          1544:        ExtendedVCB             *vcb,
        !          1545:        UInt32                  startBlock,
        !          1546:        register UInt32 numBlocks,
        !          1547:        Boolean                 *foundUnmarkedBlock)
        !          1548: {
        !          1549:        OSErr                   err;
        !          1550:        register UInt32 wordsLeft;              //      Number of words left in this bitmap block
        !          1551:        register UInt32 bitMask;                //      Word with given bits already set (ready to OR in)
        !          1552:        UInt32                  firstBit;               //      Bit index within word of first bit to allocate
        !          1553:        UInt32                  numBits;                //      Number of bits in word to allocate
        !          1554:        UInt32                  *buffer = NULL; //      Pointer to bitmap block
        !          1555:        register UInt32 *currentWord;   //      Pointer to current word in bitmap block
        !          1556:        
        !          1557: #if HFSInstrumentation
        !          1558:        InstTraceClassRef       trace;
        !          1559:        InstEventTag            eventTag;
        !          1560:        
        !          1561:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockVerifyAllocated", 'hfs+', kInstEnableClassMask, &trace);
        !          1562:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !          1563: 
        !          1564:        eventTag = startBlock;
        !          1565:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !          1566: #endif
        !          1567: 
        !          1568:        //
        !          1569:        //      Assume everything's OK
        !          1570:        //
        !          1571:        *foundUnmarkedBlock = false;
        !          1572: 
        !          1573:        //
        !          1574:        //      Pre-read the bitmap block containing the first word to check
        !          1575:        //
        !          1576: 
        !          1577:        err = ReadBitmapBlock(vcb, startBlock, &buffer);
        !          1578:        if (err != noErr) goto Exit;
        !          1579: 
        !          1580:        //
        !          1581:        //      Initialize buffer stuff
        !          1582:        //
        !          1583:        {
        !          1584:                UInt32 wordIndexInBlock;
        !          1585: 
        !          1586:                wordIndexInBlock = (startBlock & kBitsWithinBlockMask) / kBitsPerWord;
        !          1587:                currentWord = buffer + wordIndexInBlock;
        !          1588:                wordsLeft = kWordsPerBlock - wordIndexInBlock;
        !          1589:        }
        !          1590:        
        !          1591:        //
        !          1592:        //      If the first block to check doesn't start on a word
        !          1593:        //      boundary in the bitmap, then treat that first word
        !          1594:        //      specially.
        !          1595:        //
        !          1596: 
        !          1597:        firstBit = startBlock % kBitsPerWord;
        !          1598:        if (firstBit != 0) {
        !          1599:                bitMask = kAllBitsSetInWord >> firstBit;        //      turn off all bits before firstBit
        !          1600:                numBits = kBitsPerWord - firstBit;                      //      number of remaining bits in this word
        !          1601:                if (numBits > numBlocks) {
        !          1602:                        numBits = numBlocks;                                    //      entire allocation is inside this one word
        !          1603:                        bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits));        //      turn off bits after last
        !          1604:                }
        !          1605: 
        !          1606:                //      Make sure all the bits are set
        !          1607:                if ((*currentWord & bitMask) != bitMask) {
        !          1608:                        *foundUnmarkedBlock = true;                             //      found an error
        !          1609:                        if ( (!FORDISKFIRSTAID) || (GetDFAStage() == kRepairStage) )
        !          1610:                        {
        !          1611:                                *currentWord |= bitMask;                        // set the bits in the bitmap
        !          1612:                                MarkBlock_glue((Ptr) buffer);           // this block is now dirty
        !          1613:                        }
        !          1614:                }
        !          1615:                
        !          1616:                numBlocks -= numBits;                                           //      adjust number of blocks left to check
        !          1617:                ++currentWord;                                                          //      move to next word
        !          1618:                --wordsLeft;                                                            //      one less word left in this block
        !          1619:        }
        !          1620: 
        !          1621:        //
        !          1622:        //      Check whole words (32 blocks) at a time.
        !          1623:        //
        !          1624: 
        !          1625:        bitMask = kAllBitsSetInWord;                                    //      put this in a register for 68K
        !          1626:        while (numBlocks >= kBitsPerWord) {
        !          1627:                //      See if it's time to move to the next bitmap block
        !          1628:                if (wordsLeft == 0) {
        !          1629:                        //      Read in the next bitmap block
        !          1630:                        startBlock += kBitsPerBlock;                    //      generate a block number in the next bitmap block
        !          1631:                        
        !          1632: #if EXPLICIT_BUFFER_RELEASES
        !          1633:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1634:                        if (err != noErr) goto Exit;
        !          1635:                        buffer = NULL;
        !          1636: #endif
        !          1637:                        err = ReadBitmapBlock(vcb, startBlock, &buffer);
        !          1638:                        if (err != noErr) goto Exit;
        !          1639:                        
        !          1640:                        //      Readjust currentWord, wordsLeft
        !          1641:                        currentWord = buffer;
        !          1642:                        wordsLeft = kWordsPerBlock;
        !          1643:                }
        !          1644:                
        !          1645:                //      Make sure all the blocks are allocated
        !          1646:                if (*currentWord != bitMask) {
        !          1647:                        *foundUnmarkedBlock = true;                             //      found an error
        !          1648:                        if ( (!FORDISKFIRSTAID) || (GetDFAStage() == kRepairStage) )
        !          1649:                        {
        !          1650:                                *currentWord = bitMask;                         // update the bitmap
        !          1651:                                MarkBlock_glue((Ptr) buffer);           // this block is now dirty
        !          1652:                        }
        !          1653:                }
        !          1654: 
        !          1655:                numBlocks -= kBitsPerWord;
        !          1656:                ++currentWord;                                                          //      move to next word
        !          1657:                --wordsLeft;                                                            // one less word left in this block
        !          1658:        }
        !          1659:        
        !          1660:        //
        !          1661:        //      Check any remaining blocks.
        !          1662:        //
        !          1663:        
        !          1664:        if (numBlocks != 0) {
        !          1665:                bitMask = ~(kAllBitsSetInWord >> numBlocks);    //      set first numBlocks bits
        !          1666:                if (wordsLeft == 0) {
        !          1667:                        //      Read in the next bitmap block
        !          1668:                        startBlock += kBitsPerBlock;                            //      generate a block number in the next bitmap block
        !          1669:                        
        !          1670: #if EXPLICIT_BUFFER_RELEASES
        !          1671:                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1672:                        if (err != noErr) goto Exit;
        !          1673:                        buffer = NULL;
        !          1674: #endif
        !          1675:                        err = ReadBitmapBlock(vcb, startBlock, &buffer);
        !          1676:                        if (err != noErr) goto Exit;
        !          1677:                        
        !          1678:                        //      Readjust currentWord, wordsLeft
        !          1679:                        currentWord = buffer;
        !          1680:                        wordsLeft = kWordsPerBlock;
        !          1681:                }
        !          1682:                
        !          1683:                //      Make sure all the bits are set
        !          1684:                if ((*currentWord & bitMask) != bitMask) {
        !          1685:                        *foundUnmarkedBlock = true;                                     //      found an error
        !          1686:                        if ( (!FORDISKFIRSTAID) || (GetDFAStage() == kRepairStage) )
        !          1687:                        {
        !          1688:                                *currentWord |= bitMask;                                //      set the bits in the bitmap
        !          1689:                                MarkBlock_glue((Ptr) buffer);                   //      this block is now dirty
        !          1690:                        }
        !          1691:                }
        !          1692:                
        !          1693:                //      No need to update buffer pointer, etc.
        !          1694:        }
        !          1695: 
        !          1696: Exit:
        !          1697: 
        !          1698: #if EXPLICIT_BUFFER_RELEASES
        !          1699:        if (buffer) {
        !          1700:                (void)RelBlock_glue((Ptr)buffer, rbDefault);            /* Ignore any additional errors */
        !          1701:        };
        !          1702: #endif
        !          1703: 
        !          1704: #if HFSInstrumentation
        !          1705:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !          1706: #endif
        !          1707: 
        !          1708:        return err;
        !          1709: }
        !          1710: 
        !          1711: 
        !          1712: 
        !          1713: /*
        !          1714: _______________________________________________________________________
        !          1715: 
        !          1716: Routine:       BlockFindContiguous
        !          1717: 
        !          1718: Function:      Find a contiguous range of blocks that are free (bits
        !          1719:                        clear in the bitmap).  If a contiguous range of the
        !          1720:                        minimum size can't be found, an error will be returned.
        !          1721:                        
        !          1722:                        �� It would be nice if we could skip over whole words
        !          1723:                        �� with all bits set.
        !          1724:                        
        !          1725:                        �� When we find a bit set, and are about to set freeBlocks
        !          1726:                        �� to 0, we should check to see whether there are still
        !          1727:                        �� minBlocks bits left in the bitmap.
        !          1728: 
        !          1729: Inputs:
        !          1730:        vcb                             Pointer to volume where space is to be allocated
        !          1731:        startingBlock   Preferred first block of range
        !          1732:        endingBlock             Last possible block in range + 1
        !          1733:        minBlocks               Minimum number of blocks needed.  Must be > 0.
        !          1734:        maxBlocks               Maximum (ideal) number of blocks desired
        !          1735: 
        !          1736: Outputs:
        !          1737:        actualStartBlock        First block of range found, or 0 if error
        !          1738:        actualNumBlocks         Number of blocks found, or 0 if error
        !          1739: _______________________________________________________________________
        !          1740: */
        !          1741: /*
        !          1742: _________________________________________________________________________________________
        !          1743:        (DSH) 5/8/97 Description of BlockFindContiguous() algorithm
        !          1744:        Finds a contiguous range of free blocks by searching back to front.  This
        !          1745:        allows us to skip ranges of bits knowing that they are not candidates for
        !          1746:        a match because they are too small.  The below ascii diagrams illustrate
        !          1747:        the algorithm in action.
        !          1748:        
        !          1749:        Representation of a piece of a volume bitmap file
        !          1750:        If BlockFindContiguous() is called with minBlocks == 10, maxBlocks == 20
        !          1751: 
        !          1752: 
        !          1753: Fig. 1 initialization of variables, "<--" represents direction of travel
        !          1754: 
        !          1755: startingBlock (passed in)
        !          1756:        |
        !          1757:        1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
        !          1758:        |                       <--|
        !          1759: stopBlock                 currentBlock                        freeBlocks == 0
        !          1760:                                                               countedFreeBlocks == 0
        !          1761: 
        !          1762: Fig. 2 dirty bit found
        !          1763: 
        !          1764:        1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
        !          1765:        |                 |
        !          1766: stopBlock        currentBlock                                 freeBlocks == 3
        !          1767:                                                               countedFreeBlocks == 0
        !          1768: 
        !          1769: Fig. 3 reset variables to search for remainder of minBlocks
        !          1770: 
        !          1771:        1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
        !          1772:        |_________________|           |                 |
        !          1773:             Unsearched            stopBlock        currentBlock    freeBlocks == 0
        !          1774:                                                                    countedFreeBlocks == 3
        !          1775: 
        !          1776: Fig. 4 minBlocks contiguous blocks found, *actualStartBlock is set
        !          1777: 
        !          1778:        1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
        !          1779:        |_________________|           |
        !          1780:             Unsearched            stopBlock                      freeBlocks == 7
        !          1781:                                  currentBlock                    countedFreeBlocks == 3
        !          1782: 
        !          1783: Fig. 5 Now run it forwards trying to accumalate up to maxBlocks if possible
        !          1784: 
        !          1785:        1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
        !          1786:        |_________________|                                | -->
        !          1787:             Unsearched                               currentBlock
        !          1788:                                                                      *actualNumBlocks == 10
        !          1789: 
        !          1790: Fig. 6 Dirty bit is found, return actual number of contiguous blocks found
        !          1791: 
        !          1792:        1  0  1  0  1  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
        !          1793:        |_________________|                                                  |
        !          1794:             Unsearched                                                 currentBlock
        !          1795:                                                                      *actualNumBlocks == 16
        !          1796: _________________________________________________________________________________________
        !          1797: */
        !          1798: 
        !          1799: static OSErr BlockFindContiguous(
        !          1800:        ExtendedVCB             *vcb,
        !          1801:        UInt32                  startingBlock,
        !          1802:        register UInt32 endingBlock,
        !          1803:        UInt32                  minBlocks,
        !          1804:        UInt32                  maxBlocks,
        !          1805:        UInt32                  *actualStartBlock,
        !          1806:        UInt32                  *actualNumBlocks)
        !          1807: {
        !          1808:        OSErr                   err;
        !          1809:        register UInt32 bitMask;                        //      mask of bit within word for currentBlock
        !          1810:        register UInt32 tempWord;                       //      bitmap word currently being examined
        !          1811:        register UInt32 freeBlocks;                     //      number of contiguous free blocks so far
        !          1812:        register UInt32 currentBlock;           //      block number we're currently examining
        !          1813:        UInt32                  wordsLeft;                      //      words remaining in bitmap block
        !          1814:        UInt32                  *buffer = NULL;
        !          1815:        register UInt32 *currentWord;
        !          1816:        
        !          1817:        UInt32                  stopBlock;                      //      when all blocks until stopBlock are free, we found enough
        !          1818:        UInt32                  countedFreeBlocks;      //      how many contiguous free block behind stopBlock
        !          1819:        UInt32                  currentSector;          //      which allocations file sector
        !          1820: 
        !          1821: #if HFSInstrumentation
        !          1822:        InstTraceClassRef               trace;
        !          1823:        InstEventTag                    eventTag;
        !          1824:        
        !          1825:        err = InstCreateTraceClass(kInstRootClassRef, "HFS:VSM:BlockFindContiguous", 'hfs+', kInstEnableClassMask, &trace);
        !          1826:        if (err != noErr) DebugStr("\pError from InstCreateTraceClass");
        !          1827: 
        !          1828:        eventTag = InstCreateEventTag();
        !          1829:        InstLogTraceEvent( trace, eventTag, kInstStartEvent);
        !          1830: #endif
        !          1831: 
        !          1832:        if ((endingBlock - startingBlock) < minBlocks) {
        !          1833:                //      The set of blocks we're checking is smaller than the minimum number
        !          1834:                //      of blocks, so we couldn't possibly find a good range.
        !          1835:                err = dskFulErr;
        !          1836:                goto Exit;
        !          1837:        }
        !          1838:        
        !          1839:        //      Search for min blocks from back to front.
        !          1840:        //      If min blocks is found, advance the allocation pointer up to max blocks
        !          1841:        
        !          1842:        //
        !          1843:        //      Pre-read the bitmap block containing currentBlock
        !          1844:        //
        !          1845:        stopBlock               = startingBlock;
        !          1846:        currentBlock    = startingBlock + minBlocks - 1;                //      (-1) to include startingBlock
        !          1847:        
        !          1848:        err = ReadBitmapBlock( vcb, currentBlock, &buffer );
        !          1849:        if ( err != noErr ) goto Exit;
        !          1850:        
        !          1851:        //
        !          1852:        //      Init buffer, currentWord, wordsLeft, and bitMask
        !          1853:        //
        !          1854:        {
        !          1855:                UInt32 wordIndexInBlock;
        !          1856: 
        !          1857:                wordIndexInBlock = ( currentBlock & kBitsWithinBlockMask ) / kBitsPerWord;
        !          1858:                currentWord             = buffer + wordIndexInBlock;
        !          1859:                                
        !          1860:                wordsLeft               = wordIndexInBlock;
        !          1861:                tempWord                = *currentWord;
        !          1862:                bitMask                 = kHighBitInWordMask >> ( currentBlock & kBitsWithinWordMask );
        !          1863:                currentSector   = currentBlock / kBitsPerBlock;
        !          1864:        }
        !          1865:        
        !          1866:        //
        !          1867:        //      Look for maxBlocks free blocks.  If we find an allocated block,
        !          1868:        //      see if we've found minBlocks.
        !          1869:        //
        !          1870:        freeBlocks                      = 0;
        !          1871:        countedFreeBlocks       = 0;
        !          1872: 
        !          1873:        while ( currentBlock >= stopBlock )
        !          1874:        {
        !          1875:                //      Check current bit
        !          1876:                if ((tempWord & bitMask) == 0)
        !          1877:                {
        !          1878:                        ++freeBlocks;
        !          1879:                }
        !          1880:                else                                                                                                                    //      Used bitmap block found
        !          1881:                {
        !          1882:                        if ( ( freeBlocks +  countedFreeBlocks ) >= minBlocks )
        !          1883:                        {
        !          1884:                                break;                                                                                                  //      Found enough
        !          1885:                        }
        !          1886:                        else
        !          1887:                        {
        !          1888:                                //      We found a dirty bit, so we want to check if the next (minBlocks-freeBlocks) blocks
        !          1889:                                //      are free beyond what we have already checked. At Fig.2 setting up for Fig.3
        !          1890:                                
        !          1891:                                stopBlock                       = currentBlock + 1 + freeBlocks;        //      Advance stop condition
        !          1892:                                currentBlock            += minBlocks;
        !          1893:                                if ( currentBlock >= endingBlock ) break;
        !          1894:                                countedFreeBlocks       = freeBlocks;
        !          1895:                                freeBlocks                      = 0;                                                            //      Not enough; look for another range
        !          1896: 
        !          1897:                                if ( currentSector != currentBlock / kBitsPerBlock )
        !          1898:                                {
        !          1899: #if EXPLICIT_BUFFER_RELEASES
        !          1900:                                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1901:                                        if (err != noErr) goto Exit;
        !          1902:                                        buffer = NULL;
        !          1903: #endif
        !          1904:                                        err = ReadBitmapBlock( vcb, currentBlock, &buffer );
        !          1905:                                        if (err != noErr) goto Exit;
        !          1906:                                        currentSector = currentBlock / kBitsPerBlock;
        !          1907:                                }
        !          1908:                                        
        !          1909:                                wordsLeft       = ( currentBlock & kBitsWithinBlockMask ) / kBitsPerWord;
        !          1910:                                currentWord     = buffer + wordsLeft;
        !          1911:                                tempWord        = *currentWord;
        !          1912:                                bitMask         = kHighBitInWordMask >> ( currentBlock & kBitsWithinWordMask );
        !          1913: 
        !          1914:                                continue;                                                                                               //      Back to the while loop
        !          1915:                        }
        !          1916:                }
        !          1917:                
        !          1918:                //      Move to next bit
        !          1919:                --currentBlock;
        !          1920:                bitMask <<= 1;
        !          1921:                if (bitMask == 0)                                                                                               //      On a word boundry, start masking words
        !          1922:                {
        !          1923:                        bitMask = kLowBitInWordMask;
        !          1924: 
        !          1925:                        //      Move to next word
        !          1926: NextWord:
        !          1927:                        if ( wordsLeft != 0 )
        !          1928:                        {
        !          1929:                                --currentWord;
        !          1930:                                --wordsLeft;
        !          1931:                        }
        !          1932:                        else
        !          1933:                        {
        !          1934:                                //      Read in the next bitmap block
        !          1935: #if EXPLICIT_BUFFER_RELEASES
        !          1936:                                err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1937:                                if (err != noErr) goto Exit;
        !          1938:                                buffer = NULL;
        !          1939: #endif
        !          1940:                                err = ReadBitmapBlock( vcb, currentBlock, &buffer );
        !          1941:                                if (err != noErr) goto Exit;
        !          1942:                                
        !          1943:                                //      Adjust currentWord, wordsLeft, currentSector
        !          1944:                                currentSector   = currentBlock / kBitsPerBlock;
        !          1945:                                currentWord             = buffer + kWordsPerBlock - 1;  //      Last word in buffer
        !          1946:                                wordsLeft               = kWordsPerBlock - 1;
        !          1947:                        }
        !          1948:                        
        !          1949:                        tempWord = *currentWord;                                                        //      Grab the current word
        !          1950: 
        !          1951:                        //
        !          1952:                        //      If we found a whole word of free blocks, quickly skip over it.
        !          1953:                        //      NOTE: we could actually go beyond the end of the bitmap if the
        !          1954:                        //      number of allocation blocks on the volume is not a multiple of
        !          1955:                        //      32.  If this happens, we'll adjust currentBlock and freeBlocks
        !          1956:                        //      after the loop.
        !          1957:                        //
        !          1958:                        if ( tempWord == 0 )
        !          1959:                        {
        !          1960:                                freeBlocks              += kBitsPerWord;
        !          1961:                                currentBlock    -= kBitsPerWord;
        !          1962:                                if ( freeBlocks + countedFreeBlocks >= minBlocks )
        !          1963:                                        break;                                                                  //      Found enough
        !          1964:                                goto NextWord;
        !          1965:                        }
        !          1966:                }
        !          1967:        }
        !          1968: 
        !          1969:        if ( freeBlocks + countedFreeBlocks < minBlocks )
        !          1970:        {
        !          1971:                *actualStartBlock       = 0;
        !          1972:                *actualNumBlocks        = 0;
        !          1973:                err                                     = dskFulErr;
        !          1974:                goto Exit;
        !          1975:        }
        !          1976: 
        !          1977:        //
        !          1978:        //      When we get here, we know we've found minBlocks continuous space.
        !          1979:        //      At Fig.4, setting up for Fig.5
        !          1980:        //      From here we do a forward search accumalating additional free blocks.
        !          1981:        //
        !          1982:        
        !          1983:        *actualNumBlocks        = minBlocks;
        !          1984:        *actualStartBlock       = stopBlock - countedFreeBlocks;        //      ActualStartBlock is set to return to the user
        !          1985:        currentBlock            = *actualStartBlock + minBlocks;        //      Right after found free space
        !          1986:        
        !          1987:        //      Now lets see if we can run the actualNumBlocks number all the way up to maxBlocks
        !          1988:        if ( currentSector != currentBlock / kBitsPerBlock )
        !          1989:        {
        !          1990: #if EXPLICIT_BUFFER_RELEASES
        !          1991:                err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          1992:                if (err != noErr) goto Exit;
        !          1993:                buffer = NULL;
        !          1994: #endif
        !          1995:                err = ReadBitmapBlock( vcb, currentBlock, &buffer );
        !          1996:                if (err != noErr)
        !          1997:                {
        !          1998:                        err     = noErr;                                                                        //      We already found the space
        !          1999:                        goto Exit;
        !          2000:                }
        !          2001:                
        !          2002:                currentSector = currentBlock / kBitsPerBlock;
        !          2003:        }
        !          2004: 
        !          2005:        //
        !          2006:        //      Init buffer, currentWord, wordsLeft, and bitMask
        !          2007:        //
        !          2008:        {
        !          2009:                UInt32 wordIndexInBlock;
        !          2010: 
        !          2011:                wordIndexInBlock = (currentBlock & kBitsWithinBlockMask) / kBitsPerWord;
        !          2012:                currentWord             = buffer + wordIndexInBlock;
        !          2013:                tempWord                = *currentWord;
        !          2014:                wordsLeft               = kWordsPerBlock - wordIndexInBlock;
        !          2015:                bitMask                 = kHighBitInWordMask >> (currentBlock & kBitsWithinWordMask);
        !          2016:        }
        !          2017: 
        !          2018:        if ( *actualNumBlocks < maxBlocks )
        !          2019:        {
        !          2020:                while ( currentBlock < endingBlock )
        !          2021:                {
        !          2022:                                
        !          2023:                        if ( (tempWord & bitMask) == 0 )
        !          2024:                        {
        !          2025:                                *actualNumBlocks        += 1;
        !          2026:                                
        !          2027:                                if ( *actualNumBlocks == maxBlocks )
        !          2028:                                        break;
        !          2029:                        }
        !          2030:                        else
        !          2031:                        {
        !          2032:                                break;
        !          2033:                        }
        !          2034:        
        !          2035:                        //      Move to next bit
        !          2036:                        ++currentBlock;
        !          2037:                        bitMask >>= 1;
        !          2038:                        if (bitMask == 0)
        !          2039:                        {
        !          2040:                                bitMask = kHighBitInWordMask;
        !          2041:                                ++currentWord;
        !          2042:        
        !          2043:                                if ( --wordsLeft == 0)
        !          2044:                                {
        !          2045: #if EXPLICIT_BUFFER_RELEASES
        !          2046:                                        err = RelBlock_glue((Ptr)buffer, rbDefault);
        !          2047:                                        if (err != noErr) goto Exit;
        !          2048:                                        buffer = NULL;
        !          2049: #endif
        !          2050:                                        err = ReadBitmapBlock(vcb, currentBlock, &buffer);
        !          2051:                                        if (err != noErr) break;
        !          2052:                                        
        !          2053:                                        //      Adjust currentWord, wordsLeft
        !          2054:                                        currentWord             = buffer;
        !          2055:                                        wordsLeft               = kWordsPerBlock;
        !          2056:                                }
        !          2057:                                tempWord = *currentWord;                        //      grab the current word
        !          2058:                        }
        !          2059:                }
        !          2060:        }
        !          2061:        
        !          2062: Exit:
        !          2063: 
        !          2064: #if EXPLICIT_BUFFER_RELEASES
        !          2065:        if (buffer) {
        !          2066:                (void)RelBlock_glue((Ptr)buffer, rbDefault);            /* Ignore any additional errors */
        !          2067:        };
        !          2068: #endif
        !          2069: 
        !          2070: #if HFSInstrumentation
        !          2071:        InstLogTraceEvent( trace, eventTag, kInstEndEvent);
        !          2072: #endif
        !          2073: 
        !          2074:        return err;
        !          2075: }
        !          2076: 
        !          2077: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.