Return to VolumeAllocation.c CVS log

Up to [Apple XNU] / XNU / bsd / hfs / hfscommon / Misc

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

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

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