X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/d7e50217d7adf6e52786a38bcaa4cd698cb9a79e..935ed37a5c468c8a1c07408573c08b8b7ef80e8b:/bsd/hfs/hfscommon/Misc/VolumeAllocation.c diff --git a/bsd/hfs/hfscommon/Misc/VolumeAllocation.c b/bsd/hfs/hfscommon/Misc/VolumeAllocation.c index 8908358e5..0a999100e 100644 --- a/bsd/hfs/hfscommon/Misc/VolumeAllocation.c +++ b/bsd/hfs/hfscommon/Misc/VolumeAllocation.c @@ -1,16 +1,19 @@ /* - * Copyright (c) 2000-2002 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2000-2007 Apple Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ - * - * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * * This file contains Original Code and/or Modifications of Original Code * as defined in and that are subject to the Apple Public Source License * Version 2.0 (the 'License'). You may not use this file except in - * compliance with the License. Please obtain a copy of the License at - * http://www.opensource.apple.com/apsl/ and read it before using this - * file. + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. + * + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. * * The Original Code and all software distributed under the License are * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER @@ -20,7 +23,7 @@ * Please see the License for the specific language governing rights and * limitations under the License. * - * @APPLE_LICENSE_HEADER_END@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ /* File: VolumeAllocation.c @@ -107,55 +110,48 @@ enum { static OSErr ReadBitmapBlock( ExtendedVCB *vcb, - UInt32 bit, - UInt32 **buffer, - UInt32 *blockRef); + u_int32_t bit, + u_int32_t **buffer, + u_int32_t *blockRef); static OSErr ReleaseBitmapBlock( ExtendedVCB *vcb, - UInt32 blockRef, + u_int32_t blockRef, Boolean dirty); static OSErr BlockAllocateAny( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 endingBlock, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks); + u_int32_t startingBlock, + u_int32_t endingBlock, + u_int32_t maxBlocks, + Boolean useMetaZone, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks); static OSErr BlockAllocateContig( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks); + u_int32_t startingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, + Boolean useMetaZone, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks); static OSErr BlockFindContiguous( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 endingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks); - -static OSErr BlockMarkAllocated( - ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 numBlocks); - -static OSErr BlockMarkFree( - ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 numBlocks); + u_int32_t startingBlock, + u_int32_t endingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, + Boolean useMetaZone, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks); static OSErr BlockAllocateKnown( ExtendedVCB *vcb, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks); + u_int32_t maxBlocks, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks); /* @@ -175,19 +171,17 @@ static OSErr BlockAllocateKnown( ; the volume's allocation block pointer will be used as a starting ; point. ; -; All requests will be rounded up to the next highest clump size, as -; indicated in the file's FCB. -; ; Input Arguments: ; vcb - Pointer to ExtendedVCB for the volume to allocate space on ; fcb - Pointer to FCB for the file for which storage is being allocated ; startingBlock - Preferred starting allocation block, 0 = no preference ; forceContiguous - Force contiguous flag - if bit 0 set (NE), allocation is contiguous ; or an error is returned -; bytesRequested - Number of bytes requested. If the allocation is non-contiguous, +; useMetaZone - +; minBlocks - Number of blocks requested. If the allocation is non-contiguous, ; less than this may actually be allocated -; bytesMaximum - The maximum number of bytes to allocate. If there is additional free -; space after bytesRequested, then up to bytesMaximum bytes should really +; maxBlocks - The maximum number of blocks to allocate. If there is additional free +; space after bytesRequested, then up to maxBlocks bytes should really ; be allocated. (Used by ExtendFileC to round up allocations to a multiple ; of the file's clump size.) ; @@ -201,21 +195,22 @@ static OSErr BlockAllocateKnown( ;________________________________________________________________________________ */ +__private_extern__ OSErr BlockAllocate ( ExtendedVCB *vcb, /* which volume to allocate space on */ - UInt32 startingBlock, /* preferred starting block, or 0 for no preference */ - SInt64 bytesRequested, /* desired number of BYTES to allocate */ - SInt64 bytesMaximum, /* maximum number of bytes to allocate */ + u_int32_t startingBlock, /* preferred starting block, or 0 for no preference */ + u_int32_t minBlocks, /* desired number of blocks to allocate */ + u_int32_t maxBlocks, /* maximum number of blocks to allocate */ Boolean forceContiguous, /* non-zero to force contiguous allocation and to force */ - /* bytesRequested bytes to actually be allocated */ - UInt32 *actualStartBlock, /* actual first block of allocation */ - UInt32 *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */ - /* was zero, then this may represent fewer than bytesRequested */ - /* bytes */ + /* minBlocks bytes to actually be allocated */ + + Boolean useMetaZone, + u_int32_t *actualStartBlock, /* actual first block of allocation */ + u_int32_t *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */ + /* was zero, then this may represent fewer than minBlocks */ { + u_int32_t freeBlocks; OSErr err; - UInt32 minBlocks; // minimum number of allocation blocks requested - UInt32 maxBlocks; // number of allocation blocks requested, rounded to clump size Boolean updateAllocPtr = false; // true if nextAllocation needs to be updated // @@ -223,48 +218,62 @@ OSErr BlockAllocate ( // *actualStartBlock = 0; *actualNumBlocks = 0; - - // - // Compute the number of allocation blocks requested, and maximum - // - minBlocks = FileBytesToBlocks(bytesRequested, vcb->blockSize); - maxBlocks = FileBytesToBlocks(bytesMaximum, vcb->blockSize); + freeBlocks = hfs_freeblks(VCBTOHFS(vcb), 0); // // If the disk is already full, don't bother. // - if (hfs_freeblks(VCBTOHFS(vcb), 0) == 0) { + if (freeBlocks == 0) { err = dskFulErr; goto Exit; } - if (forceContiguous && hfs_freeblks(VCBTOHFS(vcb), 0) < minBlocks) { + if (forceContiguous && freeBlocks < minBlocks) { err = dskFulErr; goto Exit; } - + /* + * Clip if necessary so we don't over-subscribe the free blocks. + */ + if (minBlocks > freeBlocks) { + minBlocks = freeBlocks; + } + if (maxBlocks > freeBlocks) { + maxBlocks = freeBlocks; + } + // // If caller didn't specify a starting block number, then use the volume's // next block to allocate from. // if (startingBlock == 0) { - VCB_LOCK(vcb); + HFS_MOUNT_LOCK(vcb, TRUE); startingBlock = vcb->nextAllocation; - VCB_UNLOCK(vcb); + HFS_MOUNT_UNLOCK(vcb, TRUE); updateAllocPtr = true; } + if (startingBlock >= vcb->allocLimit) { + startingBlock = 0; /* overflow so start at beginning */ + } // // If the request must be contiguous, then find a sequence of free blocks // that is long enough. Otherwise, find the first free block. // if (forceContiguous) { - err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks, actualStartBlock, actualNumBlocks); + err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks, + useMetaZone, actualStartBlock, actualNumBlocks); /* * If we allocated from a new position then - * also update the roving allocatior. + * also update the roving allocator. */ - if ((err == noErr) && (*actualStartBlock > startingBlock)) - vcb->nextAllocation = *actualStartBlock; + if ((err == noErr) && + (*actualStartBlock > startingBlock) && + ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) || + (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) { + HFS_MOUNT_LOCK(vcb, TRUE); + HFS_UPDATE_NEXT_ALLOCATION(vcb, *actualStartBlock); + HFS_MOUNT_UNLOCK(vcb, TRUE); + } } else { /* * Scan the bitmap once, gather the N largest free extents, then @@ -275,12 +284,22 @@ OSErr BlockAllocate ( */ err = BlockAllocateKnown(vcb, maxBlocks, actualStartBlock, actualNumBlocks); if (err == dskFulErr) - err = BlockAllocateAny(vcb, startingBlock, vcb->totalBlocks, maxBlocks, actualStartBlock, actualNumBlocks); + err = BlockAllocateAny(vcb, startingBlock, vcb->allocLimit, + maxBlocks, useMetaZone, actualStartBlock, + actualNumBlocks); if (err == dskFulErr) - err = BlockAllocateAny(vcb, 0, startingBlock, maxBlocks, actualStartBlock, actualNumBlocks); + err = BlockAllocateAny(vcb, 1, startingBlock, maxBlocks, + useMetaZone, actualStartBlock, + actualNumBlocks); } - if (err == noErr) { +Exit: + // if we actually allocated something then go update the + // various bits of state that we maintain regardless of + // whether there was an error (i.e. partial allocations + // still need to update things like the free block count). + // + if (*actualNumBlocks != 0) { // // If we used the volume's roving allocation pointer, then we need to update it. // Adding in the length of the current allocation might reduce the next allocate @@ -289,22 +308,23 @@ OSErr BlockAllocate ( // the file is closed or its EOF changed. Leaving the allocation pointer at the // start of the last allocation will avoid unnecessary fragmentation in this case. // - VCB_LOCK(vcb); + HFS_MOUNT_LOCK(vcb, TRUE); - if (updateAllocPtr) - vcb->nextAllocation = *actualStartBlock; - + if (updateAllocPtr && + ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) || + (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) { + HFS_UPDATE_NEXT_ALLOCATION(vcb, *actualStartBlock); + } // // Update the number of free blocks on the volume // vcb->freeBlocks -= *actualNumBlocks; - VCB_UNLOCK(vcb); - MarkVCBDirty(vcb); + HFS_MOUNT_UNLOCK(vcb, TRUE); + + hfs_generate_volume_notifications(VCBTOHFS(vcb)); } -Exit: - return err; } @@ -329,10 +349,11 @@ Exit: ;________________________________________________________________________________ */ +__private_extern__ OSErr BlockDeallocate ( ExtendedVCB *vcb, // Which volume to deallocate space on - UInt32 firstBlock, // First block in range to deallocate - UInt32 numBlocks) // Number of contiguous blocks to deallocate + u_int32_t firstBlock, // First block in range to deallocate + u_int32_t numBlocks) // Number of contiguous blocks to deallocate { OSErr err; @@ -354,46 +375,102 @@ OSErr BlockDeallocate ( // // Update the volume's free block count, and mark the VCB as dirty. // - VCB_LOCK(vcb); + HFS_MOUNT_LOCK(vcb, TRUE); vcb->freeBlocks += numBlocks; if (vcb->nextAllocation == (firstBlock + numBlocks)) - vcb->nextAllocation -= numBlocks; - VCB_UNLOCK(vcb); + HFS_UPDATE_NEXT_ALLOCATION(vcb, (vcb->nextAllocation - numBlocks)); MarkVCBDirty(vcb); + HFS_MOUNT_UNLOCK(vcb, TRUE); + hfs_generate_volume_notifications(VCBTOHFS(vcb)); Exit: return err; } -/* -;_______________________________________________________________________ -; -; Routine: FileBytesToBlocks -; -; Function: Divide numerator by denominator, rounding up the result if there -; was a remainder. This is frequently used for computing the number -; of whole and/or partial blocks used by some count of bytes. -; Actuall divides a 64 bit by a 32 bit into a 32bit result -; -; CAREFULL!!! THIS CAN CAUSE OVERFLOW....USER BEWARE!!! -;_______________________________________________________________________ -*/ -UInt32 FileBytesToBlocks( - SInt64 numerator, - UInt32 denominator) +u_int8_t freebitcount[16] = { + 4, 3, 3, 2, 3, 2, 2, 1, /* 0 1 2 3 4 5 6 7 */ + 3, 2, 2, 1, 2, 1, 1, 0, /* 8 9 A B C D E F */ +}; + +__private_extern__ +u_int32_t +MetaZoneFreeBlocks(ExtendedVCB *vcb) { - UInt32 quotient; - - quotient = (UInt32)(numerator / denominator); - if (quotient * denominator != numerator) - quotient++; + u_int32_t freeblocks; + u_int32_t *currCache; + u_int32_t blockRef; + u_int32_t bit; + u_int32_t lastbit; + int bytesleft; + int bytesperblock; + u_int8_t byte; + u_int8_t *buffer; + + blockRef = 0; + bytesleft = freeblocks = 0; + buffer = NULL; + bit = VCBTOHFS(vcb)->hfs_metazone_start; + if (bit == 1) + bit = 0; - return quotient; + lastbit = VCBTOHFS(vcb)->hfs_metazone_end; + bytesperblock = vcb->vcbVBMIOSize; + + /* + * Count all the bits from bit to lastbit. + */ + while (bit < lastbit) { + /* + * Get next bitmap block. + */ + if (bytesleft == 0) { + if (blockRef) { + (void) ReleaseBitmapBlock(vcb, blockRef, false); + blockRef = 0; + } + if (ReadBitmapBlock(vcb, bit, &currCache, &blockRef) != 0) { + return (0); + } + buffer = (u_int8_t *)currCache; + bytesleft = bytesperblock; + } + byte = *buffer++; + freeblocks += freebitcount[byte & 0x0F]; + freeblocks += freebitcount[(byte >> 4) & 0x0F]; + bit += kBitsPerByte; + --bytesleft; + } + if (blockRef) + (void) ReleaseBitmapBlock(vcb, blockRef, false); + + return (freeblocks); } +/* + * Obtain the next allocation block (bit) that's + * outside the metadata allocation zone. + */ +static u_int32_t NextBitmapBlock( + ExtendedVCB *vcb, + u_int32_t bit) +{ + struct hfsmount *hfsmp = VCBTOHFS(vcb); + + if ((hfsmp->hfs_flags & HFS_METADATA_ZONE) == 0) + return (bit); + /* + * Skip over metadata allocation zone. + */ + if ((bit >= hfsmp->hfs_metazone_start) && + (bit <= hfsmp->hfs_metazone_end)) { + bit = hfsmp->hfs_metazone_end + 1; + } + return (bit); +} + /* ;_______________________________________________________________________ @@ -414,42 +491,42 @@ UInt32 FileBytesToBlocks( */ static OSErr ReadBitmapBlock( ExtendedVCB *vcb, - UInt32 bit, - UInt32 **buffer, - UInt32 *blockRef) + u_int32_t bit, + u_int32_t **buffer, + u_int32_t *blockRef) { OSErr err; struct buf *bp = NULL; struct vnode *vp = NULL; - UInt32 block; - UInt32 blockSize; + daddr64_t block; + u_int32_t blockSize; /* - * volume bitmap blocks are protected by the Extents B-tree lock + * volume bitmap blocks are protected by the allocation file lock */ - REQUIRE_FILE_LOCK(vcb->extentsRefNum, false); + REQUIRE_FILE_LOCK(vcb->hfs_allocation_vp, false); - blockSize = (UInt32)vcb->vcbVBMIOSize; - block = bit / (blockSize * kBitsPerByte); + blockSize = (u_int32_t)vcb->vcbVBMIOSize; + block = (daddr64_t)(bit / (blockSize * kBitsPerByte)); if (vcb->vcbSigWord == kHFSPlusSigWord) { - vp = vcb->allocationsRefNum; /* use allocation file vnode */ + vp = vcb->hfs_allocation_vp; /* use allocation file vnode */ } else /* hfs */ { vp = VCBTOHFS(vcb)->hfs_devvp; /* use device I/O vnode */ block += vcb->vcbVBMSt; /* map to physical block */ } - err = meta_bread(vp, block, blockSize, NOCRED, &bp); + err = (int)buf_meta_bread(vp, block, blockSize, NOCRED, &bp); if (bp) { if (err) { - brelse(bp); - *blockRef = NULL; + buf_brelse(bp); + *blockRef = 0; *buffer = NULL; } else { - *blockRef = (UInt32)bp; - *buffer = (UInt32 *)bp->b_data; + *blockRef = (u_int32_t)bp; + *buffer = (u_int32_t *)buf_dataptr(bp); } } @@ -472,10 +549,16 @@ static OSErr ReadBitmapBlock( */ static OSErr ReleaseBitmapBlock( ExtendedVCB *vcb, - UInt32 blockRef, + u_int32_t blockRef, Boolean dirty) { struct buf *bp = (struct buf *)blockRef; + + if (blockRef == 0) { + if (dirty) + panic("ReleaseBitmapBlock: missing bp"); + return (0); + } if (bp) { if (dirty) { @@ -483,12 +566,12 @@ static OSErr ReleaseBitmapBlock( struct hfsmount *hfsmp = VCBTOHFS(vcb); if (hfsmp->jnl) { - journal_modify_block_end(hfsmp->jnl, bp); + journal_modify_block_end(hfsmp->jnl, bp, NULL, NULL); } else { - bdwrite(bp); + buf_bdwrite(bp); } } else { - brelse(bp); + buf_brelse(bp); } } @@ -511,6 +594,7 @@ Inputs: startingBlock Preferred first block for allocation minBlocks Minimum number of contiguous blocks to allocate maxBlocks Maximum number of contiguous blocks to allocate + useMetaZone Outputs: actualStartBlock First block of range allocated, or 0 if error @@ -519,11 +603,12 @@ _______________________________________________________________________ */ static OSErr BlockAllocateContig( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + u_int32_t startingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, + Boolean useMetaZone, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks) { OSErr err; @@ -541,28 +626,21 @@ static OSErr BlockAllocateContig( * with the free extent cache, this can lead to duplicate entries * in the cache, causing the same blocks to be allocated twice. */ - err = BlockFindContiguous(vcb, startingBlock, vcb->totalBlocks, minBlocks, maxBlocks, - actualStartBlock, actualNumBlocks); + err = BlockFindContiguous(vcb, startingBlock, vcb->allocLimit, minBlocks, + maxBlocks, useMetaZone, actualStartBlock, actualNumBlocks); if (err == dskFulErr && startingBlock != 0) { /* * Constrain the endingBlock so we don't bother looking for ranges * that would overlap those found in the previous call. */ - err = BlockFindContiguous(vcb, 0, startingBlock, minBlocks, maxBlocks, - actualStartBlock, actualNumBlocks); + err = BlockFindContiguous(vcb, 1, startingBlock, minBlocks, maxBlocks, + useMetaZone, actualStartBlock, actualNumBlocks); } - if (err != noErr) goto Exit; - // // Now mark those blocks allocated. // - err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks); - -Exit: - if (err != noErr) { - *actualStartBlock = 0; - *actualNumBlocks = 0; - } + if (err == noErr) + err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks); return err; } @@ -582,6 +660,7 @@ Inputs: startingBlock Preferred first block for allocation endingBlock Last block to check + 1 maxBlocks Maximum number of contiguous blocks to allocate + useMetaZone Outputs: actualStartBlock First block of range allocated, or 0 if error @@ -590,25 +669,44 @@ _______________________________________________________________________ */ static OSErr BlockAllocateAny( ExtendedVCB *vcb, - UInt32 startingBlock, - register UInt32 endingBlock, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + u_int32_t startingBlock, + register u_int32_t endingBlock, + u_int32_t maxBlocks, + Boolean useMetaZone, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks) { OSErr err; - register UInt32 block; // current block number - register UInt32 currentWord; // Pointer to current word within bitmap block - register UInt32 bitMask; // Word with given bits already set (ready to OR in) - register UInt32 wordsLeft; // Number of words left in this bitmap block - UInt32 *buffer = NULL; - UInt32 *currCache = NULL; - UInt32 blockRef; - UInt32 bitsPerBlock; - UInt32 wordsPerBlock; + register u_int32_t block; // current block number + register u_int32_t currentWord; // Pointer to current word within bitmap block + register u_int32_t bitMask; // Word with given bits already set (ready to OR in) + register u_int32_t wordsLeft; // Number of words left in this bitmap block + u_int32_t *buffer = NULL; + u_int32_t *currCache = NULL; + u_int32_t blockRef; + u_int32_t bitsPerBlock; + u_int32_t wordsPerBlock; Boolean dirty = false; struct hfsmount *hfsmp = VCBTOHFS(vcb); + /* + * When we're skipping the metadata zone and the start/end + * range overlaps with the metadata zone then adjust the + * start to be outside of the metadata zone. If the range + * is entirely inside the metadata zone then we can deny the + * request (dskFulErr). + */ + if (!useMetaZone && (vcb->hfs_flags & HFS_METADATA_ZONE)) { + if (startingBlock <= vcb->hfs_metazone_end) { + if (endingBlock > (vcb->hfs_metazone_end + 2)) + startingBlock = vcb->hfs_metazone_end + 1; + else { + err = dskFulErr; + goto Exit; + } + } + } + // Since this routine doesn't wrap around if (maxBlocks > (endingBlock - startingBlock)) { maxBlocks = endingBlock - startingBlock; @@ -617,15 +715,15 @@ static OSErr BlockAllocateAny( // // Pre-read the first bitmap block // - err = ReadBitmapBlock(vcb, startingBlock, &currCache, &blockRef); + err = ReadBitmapBlock(vcb, startingBlock, &currCache, &blockRef); if (err != noErr) goto Exit; - buffer = currCache; + buffer = currCache; // // Set up the current position within the block // { - UInt32 wordIndexInBlock; + u_int32_t wordIndexInBlock; bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte; wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord; @@ -644,7 +742,7 @@ static OSErr BlockAllocateAny( while (block < endingBlock) { if ((currentWord & bitMask) == 0) break; - + // Next bit ++block; bitMask >>= 1; @@ -652,27 +750,37 @@ static OSErr BlockAllocateAny( // Next word bitMask = kHighBitInWordMask; ++buffer; - + if (--wordsLeft == 0) { // Next block - buffer = currCache = NULL; + buffer = currCache = NULL; err = ReleaseBitmapBlock(vcb, blockRef, false); if (err != noErr) goto Exit; - err = ReadBitmapBlock(vcb, block, &currCache, &blockRef); + /* + * Skip over metadata blocks. + */ + if (!useMetaZone) { + block = NextBitmapBlock(vcb, block); + } + if (block >= endingBlock) { + err = dskFulErr; + goto Exit; + } + + err = ReadBitmapBlock(vcb, block, &currCache, &blockRef); if (err != noErr) goto Exit; - buffer = currCache; + buffer = currCache; wordsLeft = wordsPerBlock; } - currentWord = SWAP_BE32 (*buffer); } } // Did we get to the end of the bitmap before finding a free block? // If so, then couldn't allocate anything. - if (block == endingBlock) { + if (block >= endingBlock) { err = dskFulErr; goto Exit; } @@ -717,13 +825,25 @@ static OSErr BlockAllocateAny( if (--wordsLeft == 0) { // Next block - buffer = currCache = NULL; + buffer = currCache = NULL; err = ReleaseBitmapBlock(vcb, blockRef, true); if (err != noErr) goto Exit; - err = ReadBitmapBlock(vcb, block, &currCache, &blockRef); + /* + * Skip over metadata blocks. + */ + if (!useMetaZone) { + u_int32_t nextBlock; + + nextBlock = NextBitmapBlock(vcb, block); + if (nextBlock != block) { + goto Exit; /* allocation gap, so stop */ + } + } + + err = ReadBitmapBlock(vcb, block, &currCache, &blockRef); if (err != noErr) goto Exit; - buffer = currCache; + buffer = currCache; // XXXdbg if (hfsmp->jnl) { @@ -741,6 +861,10 @@ static OSErr BlockAllocateAny( Exit: if (err == noErr) { *actualNumBlocks = block - *actualStartBlock; + + // sanity check + if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit) + panic("BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN); } else { *actualStartBlock = 0; @@ -776,13 +900,14 @@ _______________________________________________________________________ */ static OSErr BlockAllocateKnown( ExtendedVCB *vcb, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + u_int32_t maxBlocks, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks) { - UInt32 i; - UInt32 foundBlocks; - UInt32 newStartBlock, newBlockCount; + OSErr err; + u_int32_t i; + u_int32_t foundBlocks; + u_int32_t newStartBlock, newBlockCount; if (vcb->vcbFreeExtCnt == 0) return dskFulErr; @@ -828,10 +953,24 @@ static OSErr BlockAllocateKnown( vcb->vcbFreeExt[i-1].blockCount = newBlockCount; } - // - // Now mark the found extent in the bitmap - // - return BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks); + // sanity check + if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit) + { + printf ("hfs: BlockAllocateKnown() found allocation overflow on \"%s\"", vcb->vcbVN); + hfs_mark_volume_inconsistent(vcb); + *actualStartBlock = 0; + *actualNumBlocks = 0; + err = EIO; + } + else + { + // + // Now mark the found extent in the bitmap + // + err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks); + } + + return err; } @@ -851,24 +990,26 @@ Inputs: numBlocks Number of blocks to mark as allocated _______________________________________________________________________ */ -static OSErr BlockMarkAllocated( +__private_extern__ +OSErr BlockMarkAllocated( ExtendedVCB *vcb, - UInt32 startingBlock, - register UInt32 numBlocks) + u_int32_t startingBlock, + register u_int32_t numBlocks) { OSErr err; - register UInt32 *currentWord; // Pointer to current word within bitmap block - register UInt32 wordsLeft; // Number of words left in this bitmap block - register UInt32 bitMask; // Word with given bits already set (ready to OR in) - UInt32 firstBit; // Bit index within word of first bit to allocate - UInt32 numBits; // Number of bits in word to allocate - UInt32 *buffer = NULL; - UInt32 blockRef; - UInt32 bitsPerBlock; - UInt32 wordsPerBlock; + register u_int32_t *currentWord; // Pointer to current word within bitmap block + register u_int32_t wordsLeft; // Number of words left in this bitmap block + register u_int32_t bitMask; // Word with given bits already set (ready to OR in) + u_int32_t firstBit; // Bit index within word of first bit to allocate + u_int32_t numBits; // Number of bits in word to allocate + u_int32_t *buffer = NULL; + u_int32_t blockRef; + u_int32_t bitsPerBlock; + u_int32_t wordsPerBlock; // XXXdbg struct hfsmount *hfsmp = VCBTOHFS(vcb); + // // Pre-read the bitmap block containing the first word of allocation // @@ -879,7 +1020,7 @@ static OSErr BlockMarkAllocated( // Initialize currentWord, and wordsLeft. // { - UInt32 wordIndexInBlock; + u_int32_t wordIndexInBlock; bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte; wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord; @@ -1018,24 +1159,37 @@ Inputs: numBlocks Number of blocks to mark as freed _______________________________________________________________________ */ -static OSErr BlockMarkFree( +__private_extern__ +OSErr BlockMarkFree( ExtendedVCB *vcb, - UInt32 startingBlock, - register UInt32 numBlocks) + u_int32_t startingBlock, + register u_int32_t numBlocks) { OSErr err; - register UInt32 *currentWord; // Pointer to current word within bitmap block - register UInt32 wordsLeft; // Number of words left in this bitmap block - register UInt32 bitMask; // Word with given bits already set (ready to OR in) - UInt32 firstBit; // Bit index within word of first bit to allocate - UInt32 numBits; // Number of bits in word to allocate - UInt32 *buffer = NULL; - UInt32 blockRef; - UInt32 bitsPerBlock; - UInt32 wordsPerBlock; + register u_int32_t *currentWord; // Pointer to current word within bitmap block + register u_int32_t wordsLeft; // Number of words left in this bitmap block + register u_int32_t bitMask; // Word with given bits already set (ready to OR in) + u_int32_t firstBit; // Bit index within word of first bit to allocate + u_int32_t numBits; // Number of bits in word to allocate + u_int32_t *buffer = NULL; + u_int32_t blockRef; + u_int32_t bitsPerBlock; + u_int32_t wordsPerBlock; // XXXdbg struct hfsmount *hfsmp = VCBTOHFS(vcb); + /* + * NOTE: We use vcb->totalBlocks instead of vcb->allocLimit because we + * need to be able to free blocks being relocated during hfs_truncatefs. + */ + if (startingBlock + numBlocks > vcb->totalBlocks) { + printf ("hfs: BlockMarkFree() trying to free non-existent blocks starting at %u (numBlock=%u) on volume %s\n", startingBlock, numBlocks, vcb->vcbVN); + hfs_mark_volume_inconsistent(vcb); + err = EIO; + goto Exit; + } + + // // Pre-read the bitmap block containing the first word of allocation // @@ -1051,7 +1205,7 @@ static OSErr BlockMarkFree( // Initialize currentWord, and wordsLeft. // { - UInt32 wordIndexInBlock; + u_int32_t wordIndexInBlock; bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte; wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord; @@ -1075,11 +1229,9 @@ static OSErr BlockMarkFree( numBits = numBlocks; // entire allocation is inside this one word bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last } -#if DEBUG_BUILD if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) { - panic("BlockMarkFree: blocks not allocated!"); + goto Corruption; } -#endif *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap numBlocks -= numBits; // adjust number of blocks left to free @@ -1112,12 +1264,9 @@ static OSErr BlockMarkFree( currentWord = buffer; wordsLeft = wordsPerBlock; } - -#if DEBUG_BUILD if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) { - panic("BlockMarkFree: blocks not allocated!"); + goto Corruption; } -#endif *currentWord = 0; // clear the entire word numBlocks -= kBitsPerWord; @@ -1151,11 +1300,9 @@ static OSErr BlockMarkFree( currentWord = buffer; wordsLeft = wordsPerBlock; } -#if DEBUG_BUILD if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) { - panic("BlockMarkFree: blocks not allocated!"); + goto Corruption; } -#endif *currentWord &= SWAP_BE32 (~bitMask); // clear the bits in the bitmap // No need to update currentWord or wordsLeft @@ -1167,6 +1314,16 @@ Exit: (void)ReleaseBitmapBlock(vcb, blockRef, true); return err; + +Corruption: +#if DEBUG_BUILD + panic("BlockMarkFree: blocks not allocated!"); +#else + printf ("hfs: BlockMarkFree() trying to free unallocated blocks on volume %s\n", vcb->vcbVN); + hfs_mark_volume_inconsistent(vcb); + err = EIO; + goto Exit; +#endif } @@ -1185,6 +1342,7 @@ Inputs: endingBlock Last possible block in range + 1 minBlocks Minimum number of blocks needed. Must be > 0. maxBlocks Maximum (ideal) number of blocks desired + useMetaZone OK to dip into metadata allocation zone Outputs: actualStartBlock First block of range found, or 0 if error @@ -1198,25 +1356,42 @@ _______________________________________________________________________ static OSErr BlockFindContiguous( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 endingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + u_int32_t startingBlock, + u_int32_t endingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, + Boolean useMetaZone, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks) { OSErr err; - register UInt32 currentBlock; // Block we're currently looking at. - UInt32 firstBlock; // First free block in current extent. - UInt32 stopBlock; // If we get to this block, stop searching for first free block. - UInt32 foundBlocks; // Number of contiguous free blocks in current extent. - UInt32 *buffer = NULL; - register UInt32 *currentWord; - register UInt32 bitMask; - register UInt32 wordsLeft; - register UInt32 tempWord; - UInt32 blockRef; - UInt32 wordsPerBlock; + register u_int32_t currentBlock; // Block we're currently looking at. + u_int32_t firstBlock; // First free block in current extent. + u_int32_t stopBlock; // If we get to this block, stop searching for first free block. + u_int32_t foundBlocks; // Number of contiguous free blocks in current extent. + u_int32_t *buffer = NULL; + register u_int32_t *currentWord; + register u_int32_t bitMask; + register u_int32_t wordsLeft; + register u_int32_t tempWord; + u_int32_t blockRef; + u_int32_t wordsPerBlock; + + /* + * When we're skipping the metadata zone and the start/end + * range overlaps with the metadata zone then adjust the + * start to be outside of the metadata zone. If the range + * is entirely inside the metadata zone then we can deny the + * request (dskFulErr). + */ + if (!useMetaZone && (vcb->hfs_flags & HFS_METADATA_ZONE)) { + if (startingBlock <= vcb->hfs_metazone_end) { + if (endingBlock > (vcb->hfs_metazone_end + 2)) + startingBlock = vcb->hfs_metazone_end + 1; + else + goto DiskFull; + } + } if ((endingBlock - startingBlock) < minBlocks) { @@ -1228,7 +1403,13 @@ static OSErr BlockFindContiguous( stopBlock = endingBlock - minBlocks + 1; currentBlock = startingBlock; firstBlock = 0; - + + /* + * Skip over metadata blocks. + */ + if (!useMetaZone) + currentBlock = NextBitmapBlock(vcb, currentBlock); + // // Pre-read the first bitmap block. // @@ -1240,7 +1421,7 @@ static OSErr BlockFindContiguous( // wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord; - wordsLeft = (startingBlock / kBitsPerWord) & (wordsPerBlock-1); // Current index into buffer + wordsLeft = (currentBlock / kBitsPerWord) & (wordsPerBlock-1); // Current index into buffer currentWord = buffer + wordsLeft; wordsLeft = wordsPerBlock - wordsLeft; @@ -1287,6 +1468,16 @@ static OSErr BlockFindContiguous( err = ReleaseBitmapBlock(vcb, blockRef, false); if (err != noErr) goto ErrorExit; + /* + * Skip over metadata blocks. + */ + if (!useMetaZone) { + currentBlock = NextBitmapBlock(vcb, currentBlock); + if (currentBlock >= stopBlock) { + goto LoopExit; + } + } + err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef); if ( err != noErr ) goto ErrorExit; @@ -1363,6 +1554,18 @@ FoundUnused: err = ReleaseBitmapBlock(vcb, blockRef, false); if (err != noErr) goto ErrorExit; + /* + * Skip over metadata blocks. + */ + if (!useMetaZone) { + u_int32_t nextBlock; + + nextBlock = NextBitmapBlock(vcb, currentBlock); + if (nextBlock != currentBlock) { + goto LoopExit; /* allocation gap, so stop */ + } + } + err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef); if ( err != noErr ) goto ErrorExit; @@ -1428,7 +1631,7 @@ FoundUsed: ++vcb->vcbFreeExtCnt; } } while (currentBlock < stopBlock); - +LoopExit: // Return the outputs. if (foundBlocks < minBlocks) @@ -1444,6 +1647,14 @@ ErrorExit: err = noErr; *actualStartBlock = firstBlock; *actualNumBlocks = foundBlocks; + /* + * Sanity check for overflow + */ + if ((firstBlock + foundBlocks) > vcb->allocLimit) { + panic("blk allocation overflow on \"%s\" sb:0x%08x eb:0x%08x cb:0x%08x fb:0x%08x stop:0x%08x min:0x%08x found:0x%08x", + vcb->vcbVN, startingBlock, endingBlock, currentBlock, + firstBlock, stopBlock, minBlocks, foundBlocks); + } } if (buffer) @@ -1452,4 +1663,125 @@ ErrorExit: return err; } +/* + * Test to see if any blocks in a range are allocated. + * + * The journal or allocation file lock must be held. + */ +__private_extern__ +int +hfs_isallocated(struct hfsmount *hfsmp, u_long startingBlock, u_long numBlocks) +{ + u_int32_t *currentWord; // Pointer to current word within bitmap block + u_int32_t wordsLeft; // Number of words left in this bitmap block + u_int32_t bitMask; // Word with given bits already set (ready to test) + u_int32_t firstBit; // Bit index within word of first bit to allocate + u_int32_t numBits; // Number of bits in word to allocate + u_int32_t *buffer = NULL; + u_int32_t blockRef; + u_int32_t bitsPerBlock; + u_int32_t wordsPerBlock; + int inuse = 0; + int error; + + /* + * Pre-read the bitmap block containing the first word of allocation + */ + error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef); + if (error) + return (error); + + /* + * Initialize currentWord, and wordsLeft. + */ + { + u_int32_t wordIndexInBlock; + + bitsPerBlock = hfsmp->vcbVBMIOSize * kBitsPerByte; + wordsPerBlock = hfsmp->vcbVBMIOSize / kBytesPerWord; + + wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord; + currentWord = buffer + wordIndexInBlock; + wordsLeft = wordsPerBlock - wordIndexInBlock; + } + + /* + * First test any non word aligned bits. + */ + firstBit = startingBlock % kBitsPerWord; + if (firstBit != 0) { + bitMask = kAllBitsSetInWord >> firstBit; + numBits = kBitsPerWord - firstBit; + if (numBits > numBlocks) { + numBits = numBlocks; + bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); + } + if ((*currentWord & SWAP_BE32 (bitMask)) != 0) { + inuse = 1; + goto Exit; + } + numBlocks -= numBits; + ++currentWord; + --wordsLeft; + } + + /* + * Test whole words (32 blocks) at a time. + */ + while (numBlocks >= kBitsPerWord) { + if (wordsLeft == 0) { + /* Read in the next bitmap block. */ + startingBlock += bitsPerBlock; + + buffer = NULL; + error = ReleaseBitmapBlock(hfsmp, blockRef, false); + if (error) goto Exit; + + error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef); + if (error) goto Exit; + + /* Readjust currentWord and wordsLeft. */ + currentWord = buffer; + wordsLeft = wordsPerBlock; + } + if (*currentWord != 0) { + inuse = 1; + goto Exit; + } + numBlocks -= kBitsPerWord; + ++currentWord; + --wordsLeft; + } + + /* + * Test any remaining blocks. + */ + if (numBlocks != 0) { + bitMask = ~(kAllBitsSetInWord >> numBlocks); + if (wordsLeft == 0) { + /* Read in the next bitmap block */ + startingBlock += bitsPerBlock; + + buffer = NULL; + error = ReleaseBitmapBlock(hfsmp, blockRef, false); + if (error) goto Exit; + + error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef); + if (error) goto Exit; + + currentWord = buffer; + wordsLeft = wordsPerBlock; + } + if ((*currentWord & SWAP_BE32 (bitMask)) != 0) { + inuse = 1; + goto Exit; + } + } +Exit: + if (buffer) { + (void)ReleaseBitmapBlock(hfsmp, blockRef, false); + } + return (inuse); +} +