X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/0c530ab8987f0ae6a1a3d9284f40182b88852816..b0d623f7f2ae71ed96e60569f61f9a9a27016e80:/bsd/hfs/hfscommon/Misc/VolumeAllocation.c diff --git a/bsd/hfs/hfscommon/Misc/VolumeAllocation.c b/bsd/hfs/hfscommon/Misc/VolumeAllocation.c index 55bec894b..9ea66862c 100644 --- a/bsd/hfs/hfscommon/Misc/VolumeAllocation.c +++ b/bsd/hfs/hfscommon/Misc/VolumeAllocation.c @@ -1,23 +1,29 @@ /* - * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2000-2008 Apple Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * - * The contents of this file constitute Original Code as defined in and - * are subject to the Apple Public Source License Version 1.1 (the - * "License"). You may not use this file except in compliance with the - * License. Please obtain a copy of the License at - * http://www.apple.com/publicsource and read it before using this file. + * 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. 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. * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * 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 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * 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 @@ -80,6 +86,7 @@ Internal routines: #include #include #include +#include #include "../../hfs.h" #include "../../hfs_dbg.h" @@ -104,48 +111,48 @@ enum { static OSErr ReadBitmapBlock( ExtendedVCB *vcb, - UInt32 bit, - UInt32 **buffer, - UInt32 *blockRef); + u_int32_t bit, + u_int32_t **buffer, + uintptr_t *blockRef); static OSErr ReleaseBitmapBlock( ExtendedVCB *vcb, - UInt32 blockRef, + uintptr_t blockRef, Boolean dirty); static OSErr BlockAllocateAny( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 endingBlock, - UInt32 maxBlocks, + u_int32_t startingBlock, + u_int32_t endingBlock, + u_int32_t maxBlocks, Boolean useMetaZone, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks); + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks); static OSErr BlockAllocateContig( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, + u_int32_t startingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, Boolean useMetaZone, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks); + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks); static OSErr BlockFindContiguous( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 endingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, + u_int32_t startingBlock, + u_int32_t endingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, Boolean useMetaZone, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks); + 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); /* @@ -188,22 +195,55 @@ static OSErr BlockAllocateKnown( ; The volume bitmap is read and updated; the volume bitmap cache may be changed. ;________________________________________________________________________________ */ +static void +sanity_check_free_ext(__unused ExtendedVCB *vcb, __unused int check_allocated) +{ +#if DEBUG + u_int32_t i, j; + + for(i=0; i < vcb->vcbFreeExtCnt; i++) { + u_int32_t start, nblocks; + + start = vcb->vcbFreeExt[i].startBlock; + nblocks = vcb->vcbFreeExt[i].blockCount; + + + if (nblocks == 0) { + panic("hfs: %p: slot %d in the free extent array had a zero count (%d)\n", vcb, i, start); + } + + if (check_allocated && hfs_isallocated(vcb, start, nblocks)) { + panic("hfs: %p: slot %d in the free extent array is bad (%d / %d)\n", + vcb, i, start, nblocks); + } + + for(j=i+1; j < vcb->vcbFreeExtCnt; j++) { + if (start == vcb->vcbFreeExt[j].startBlock) { + panic("hfs: %p: slot %d/%d are dups?! (%d / %d ; %d / %d)\n", + vcb, i, j, start, nblocks, vcb->vcbFreeExt[i].startBlock, + vcb->vcbFreeExt[i].blockCount); + } + } + } +#endif +} + __private_extern__ OSErr BlockAllocate ( ExtendedVCB *vcb, /* which volume to allocate space on */ - UInt32 startingBlock, /* preferred starting block, or 0 for no preference */ - UInt32 minBlocks, /* desired number of blocks to allocate */ - UInt32 maxBlocks, /* maximum number of blocks 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 */ /* minBlocks bytes to actually be allocated */ Boolean useMetaZone, - UInt32 *actualStartBlock, /* actual first block of allocation */ - UInt32 *actualNumBlocks) /* number of blocks actually allocated; if forceContiguous */ + 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 */ { - UInt32 freeBlocks; + u_int32_t freeBlocks; OSErr err; Boolean updateAllocPtr = false; // true if nextAllocation needs to be updated @@ -241,11 +281,15 @@ OSErr BlockAllocate ( // if (startingBlock == 0) { HFS_MOUNT_LOCK(vcb, TRUE); - startingBlock = vcb->nextAllocation; + if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) { + startingBlock = vcb->sparseAllocation; + } else { + startingBlock = vcb->nextAllocation; + } HFS_MOUNT_UNLOCK(vcb, TRUE); updateAllocPtr = true; } - if (startingBlock >= vcb->totalBlocks) { + if (startingBlock >= vcb->allocLimit) { startingBlock = 0; /* overflow so start at beginning */ } @@ -258,15 +302,14 @@ OSErr BlockAllocate ( 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) && ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) || (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) { - HFS_MOUNT_LOCK(vcb, TRUE); - vcb->nextAllocation = *actualStartBlock; - HFS_MOUNT_UNLOCK(vcb, TRUE); + + updateAllocPtr = true; } } else { /* @@ -278,7 +321,7 @@ OSErr BlockAllocate ( */ err = BlockAllocateKnown(vcb, maxBlocks, actualStartBlock, actualNumBlocks); if (err == dskFulErr) - err = BlockAllocateAny(vcb, startingBlock, vcb->totalBlocks, + err = BlockAllocateAny(vcb, startingBlock, vcb->allocLimit, maxBlocks, useMetaZone, actualStartBlock, actualNumBlocks); if (err == dskFulErr) @@ -294,6 +337,8 @@ Exit: // still need to update things like the free block count). // if (*actualNumBlocks != 0) { + int i,j; + // // 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 @@ -304,11 +349,42 @@ Exit: // HFS_MOUNT_LOCK(vcb, TRUE); + if (vcb->vcbFreeExtCnt == 0 && vcb->hfs_freed_block_count == 0) { + vcb->sparseAllocation = *actualStartBlock; + } + if (*actualNumBlocks < vcb->hfs_freed_block_count) { + vcb->hfs_freed_block_count -= *actualNumBlocks; + } else { + vcb->hfs_freed_block_count = 0; + } + if (updateAllocPtr && ((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) || (*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) { - vcb->nextAllocation = *actualStartBlock; + HFS_UPDATE_NEXT_ALLOCATION(vcb, *actualStartBlock); + } + + for(i=0; i < (int)vcb->vcbFreeExtCnt; i++) { + u_int32_t start, end; + + start = vcb->vcbFreeExt[i].startBlock; + end = start + vcb->vcbFreeExt[i].blockCount; + + if ( (*actualStartBlock >= start && *actualStartBlock < end) + || ((*actualStartBlock + *actualNumBlocks) > start && *actualStartBlock < start)) { + + for(j=i; j < (int)vcb->vcbFreeExtCnt-1; j++) { + vcb->vcbFreeExt[j] = vcb->vcbFreeExt[j+1]; + } + + vcb->vcbFreeExtCnt--; + i--; // so we'll check the guy we just copied down... + + // keep looping because we may have invalidated more + // than one entry in the array + } } + // // Update the number of free blocks on the volume // @@ -316,6 +392,8 @@ Exit: MarkVCBDirty(vcb); HFS_MOUNT_UNLOCK(vcb, TRUE); + sanity_check_free_ext(vcb, 1); + hfs_generate_volume_notifications(VCBTOHFS(vcb)); } @@ -346,10 +424,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; + u_int32_t tempWord; // // If no blocks to deallocate, then exit early @@ -371,11 +450,68 @@ OSErr BlockDeallocate ( // HFS_MOUNT_LOCK(vcb, TRUE); vcb->freeBlocks += numBlocks; - if (vcb->nextAllocation == (firstBlock + numBlocks)) - vcb->nextAllocation -= numBlocks; + vcb->hfs_freed_block_count += numBlocks; + if (firstBlock < vcb->sparseAllocation) { + vcb->sparseAllocation = firstBlock; + } + + if (vcb->nextAllocation == (firstBlock + numBlocks)) { + HFS_UPDATE_NEXT_ALLOCATION(vcb, (vcb->nextAllocation - numBlocks)); + } + + tempWord = vcb->vcbFreeExtCnt; + // Add this free chunk to the free extent list + if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) { + // Sorted by start block + if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].startBlock > firstBlock) + --tempWord; + if (tempWord < kMaxFreeExtents) + { + // We're going to add this extent. Bubble any smaller extents down in the list. + while (tempWord && vcb->vcbFreeExt[tempWord-1].startBlock > firstBlock) + { + vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1]; + if (vcb->vcbFreeExt[tempWord].startBlock < vcb->sparseAllocation) { + vcb->sparseAllocation = vcb->vcbFreeExt[tempWord].startBlock; + } + --tempWord; + } + vcb->vcbFreeExt[tempWord].startBlock = firstBlock; + vcb->vcbFreeExt[tempWord].blockCount = numBlocks; + + if (vcb->vcbFreeExtCnt < kMaxFreeExtents) { + ++vcb->vcbFreeExtCnt; + } + } + } else { + // Sorted by num blocks + if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < numBlocks) + --tempWord; + if (tempWord < kMaxFreeExtents) + { + // We're going to add this extent. Bubble any smaller extents down in the list. + while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < numBlocks) + { + vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1]; + if (vcb->vcbFreeExt[tempWord].startBlock < vcb->sparseAllocation) { + vcb->sparseAllocation = vcb->vcbFreeExt[tempWord].startBlock; + } + --tempWord; + } + vcb->vcbFreeExt[tempWord].startBlock = firstBlock; + vcb->vcbFreeExt[tempWord].blockCount = numBlocks; + + if (vcb->vcbFreeExtCnt < kMaxFreeExtents) { + ++vcb->vcbFreeExtCnt; + } + } + } + MarkVCBDirty(vcb); HFS_MOUNT_UNLOCK(vcb, TRUE); + sanity_check_free_ext(vcb, 1); + hfs_generate_volume_notifications(VCBTOHFS(vcb)); Exit: @@ -383,24 +519,24 @@ Exit: } -UInt8 freebitcount[16] = { +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__ -UInt32 +u_int32_t MetaZoneFreeBlocks(ExtendedVCB *vcb) { - UInt32 freeblocks; - UInt32 *currCache; - UInt32 blockRef; - UInt32 bit; - UInt32 lastbit; + u_int32_t freeblocks; + u_int32_t *currCache; + uintptr_t blockRef; + u_int32_t bit; + u_int32_t lastbit; int bytesleft; int bytesperblock; - UInt8 byte; - UInt8 *buffer; + u_int8_t byte; + u_int8_t *buffer; blockRef = 0; bytesleft = freeblocks = 0; @@ -427,7 +563,7 @@ MetaZoneFreeBlocks(ExtendedVCB *vcb) if (ReadBitmapBlock(vcb, bit, &currCache, &blockRef) != 0) { return (0); } - buffer = (UInt8 *)currCache; + buffer = (u_int8_t *)currCache; bytesleft = bytesperblock; } byte = *buffer++; @@ -447,9 +583,9 @@ MetaZoneFreeBlocks(ExtendedVCB *vcb) * Obtain the next allocation block (bit) that's * outside the metadata allocation zone. */ -static UInt32 NextBitmapBlock( +static u_int32_t NextBitmapBlock( ExtendedVCB *vcb, - UInt32 bit) + u_int32_t bit) { struct hfsmount *hfsmp = VCBTOHFS(vcb); @@ -485,22 +621,22 @@ static UInt32 NextBitmapBlock( */ static OSErr ReadBitmapBlock( ExtendedVCB *vcb, - UInt32 bit, - UInt32 **buffer, - UInt32 *blockRef) + u_int32_t bit, + u_int32_t **buffer, + uintptr_t *blockRef) { OSErr err; struct buf *bp = NULL; struct vnode *vp = NULL; daddr64_t block; - UInt32 blockSize; + u_int32_t blockSize; /* * volume bitmap blocks are protected by the allocation file lock */ REQUIRE_FILE_LOCK(vcb->hfs_allocation_vp, false); - blockSize = (UInt32)vcb->vcbVBMIOSize; + blockSize = (u_int32_t)vcb->vcbVBMIOSize; block = (daddr64_t)(bit / (blockSize * kBitsPerByte)); if (vcb->vcbSigWord == kHFSPlusSigWord) { @@ -516,11 +652,11 @@ static OSErr ReadBitmapBlock( if (bp) { if (err) { buf_brelse(bp); - *blockRef = NULL; + *blockRef = 0; *buffer = NULL; } else { - *blockRef = (UInt32)bp; - *buffer = (UInt32 *)buf_dataptr(bp); + *blockRef = (uintptr_t)bp; + *buffer = (u_int32_t *)buf_dataptr(bp); } } @@ -543,14 +679,14 @@ static OSErr ReadBitmapBlock( */ static OSErr ReleaseBitmapBlock( ExtendedVCB *vcb, - UInt32 blockRef, + uintptr_t blockRef, Boolean dirty) { struct buf *bp = (struct buf *)blockRef; if (blockRef == 0) { if (dirty) - panic("ReleaseBitmapBlock: missing bp"); + panic("hfs: ReleaseBitmapBlock: missing bp"); return (0); } @@ -560,7 +696,7 @@ 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 { buf_bdwrite(bp); } @@ -597,12 +733,12 @@ _______________________________________________________________________ */ static OSErr BlockAllocateContig( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, + u_int32_t startingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, Boolean useMetaZone, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks) { OSErr err; @@ -620,7 +756,7 @@ 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, + err = BlockFindContiguous(vcb, startingBlock, vcb->allocLimit, minBlocks, maxBlocks, useMetaZone, actualStartBlock, actualNumBlocks); if (err == dskFulErr && startingBlock != 0) { /* @@ -630,22 +766,11 @@ static OSErr BlockAllocateContig( err = BlockFindContiguous(vcb, 1, startingBlock, minBlocks, maxBlocks, useMetaZone, actualStartBlock, actualNumBlocks); } - if (err != noErr) goto Exit; - - // sanity check - if ((*actualStartBlock + *actualNumBlocks) > vcb->totalBlocks) - panic("BlockAllocateContig: allocation overflow on \"%s\"", vcb->vcbVN); - // // 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; } @@ -674,37 +799,49 @@ _______________________________________________________________________ */ static OSErr BlockAllocateAny( ExtendedVCB *vcb, - UInt32 startingBlock, - register UInt32 endingBlock, - UInt32 maxBlocks, + u_int32_t startingBlock, + register u_int32_t endingBlock, + u_int32_t maxBlocks, Boolean useMetaZone, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + 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; + uintptr_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; } - /* - * Skip over metadata blocks. - */ - if (!useMetaZone) - startingBlock = NextBitmapBlock(vcb, startingBlock); - // // Pre-read the first bitmap block // @@ -716,7 +853,7 @@ static OSErr BlockAllocateAny( // Set up the current position within the block // { - UInt32 wordIndexInBlock; + u_int32_t wordIndexInBlock; bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte; wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord; @@ -755,11 +892,12 @@ static OSErr BlockAllocateAny( */ if (!useMetaZone) { block = NextBitmapBlock(vcb, block); - if (block >= endingBlock) { - err = dskFulErr; - goto Exit; - } } + if (block >= endingBlock) { + err = dskFulErr; + goto Exit; + } + err = ReadBitmapBlock(vcb, block, &currCache, &blockRef); if (err != noErr) goto Exit; buffer = currCache; @@ -825,7 +963,7 @@ static OSErr BlockAllocateAny( * Skip over metadata blocks. */ if (!useMetaZone) { - UInt32 nextBlock; + u_int32_t nextBlock; nextBlock = NextBitmapBlock(vcb, block); if (nextBlock != block) { @@ -855,8 +993,8 @@ Exit: *actualNumBlocks = block - *actualStartBlock; // sanity check - if ((*actualStartBlock + *actualNumBlocks) > vcb->totalBlocks) - panic("BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN); + if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit) + panic("hfs: BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN); } else { *actualStartBlock = 0; @@ -890,18 +1028,19 @@ Returns: dskFulErr Free extent cache is empty _______________________________________________________________________ */ + static OSErr BlockAllocateKnown( ExtendedVCB *vcb, - UInt32 maxBlocks, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + u_int32_t maxBlocks, + u_int32_t *actualStartBlock, + u_int32_t *actualNumBlocks) { - OSErr err; - UInt32 i; - UInt32 foundBlocks; - UInt32 newStartBlock, newBlockCount; - - if (vcb->vcbFreeExtCnt == 0) + OSErr err; + u_int32_t i; + u_int32_t foundBlocks; + u_int32_t newStartBlock, newBlockCount; + + if (vcb->vcbFreeExtCnt == 0 || vcb->vcbFreeExt[0].blockCount == 0) return dskFulErr; // Just grab up to maxBlocks of the first (largest) free exent. @@ -911,9 +1050,26 @@ static OSErr BlockAllocateKnown( foundBlocks = maxBlocks; *actualNumBlocks = foundBlocks; + if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) { + // since sparse volumes keep the free extent list sorted by starting + // block number, the list won't get re-ordered, it may only shrink + // + vcb->vcbFreeExt[0].startBlock += foundBlocks; + vcb->vcbFreeExt[0].blockCount -= foundBlocks; + if (vcb->vcbFreeExt[0].blockCount == 0) { + for(i=1; i < vcb->vcbFreeExtCnt; i++) { + vcb->vcbFreeExt[i-1] = vcb->vcbFreeExt[i]; + } + vcb->vcbFreeExtCnt--; + } + + goto done; + } + // Adjust the start and length of that extent. newStartBlock = vcb->vcbFreeExt[0].startBlock + foundBlocks; newBlockCount = vcb->vcbFreeExt[0].blockCount - foundBlocks; + // The first extent might not be the largest anymore. Bubble up any // (now larger) extents to the top of the list. @@ -933,9 +1089,9 @@ static OSErr BlockAllocateKnown( // If this is now the smallest known free extent, then it might be smaller than // other extents we didn't keep track of. So, just forget about this extent. // After the previous loop, (i-1) is the index of the extent we just allocated from. - if (i == vcb->vcbFreeExtCnt) + if (newBlockCount == 0) { - // It's now the smallest extent, so forget about it + // then just reduce the number of free extents since this guy got deleted --vcb->vcbFreeExtCnt; } else @@ -944,24 +1100,28 @@ static OSErr BlockAllocateKnown( vcb->vcbFreeExt[i-1].startBlock = newStartBlock; vcb->vcbFreeExt[i-1].blockCount = newBlockCount; } - + +done: // sanity check - if ((*actualStartBlock + *actualNumBlocks) > vcb->totalBlocks) + if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit) { - printf("BlockAllocateKnown: allocation overflow on \"%s\"", vcb->vcbVN); + printf ("hfs: BlockAllocateKnown() found allocation overflow on \"%s\"", vcb->vcbVN); + hfs_mark_volume_inconsistent(vcb); *actualStartBlock = 0; *actualNumBlocks = 0; err = EIO; - } - - else + } + else { // // Now mark the found extent in the bitmap // - err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks); + err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks); } - return err; + + sanity_check_free_ext(vcb, 1); + + return err; } @@ -984,19 +1144,19 @@ _______________________________________________________________________ __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; + uintptr_t blockRef; + u_int32_t bitsPerBlock; + u_int32_t wordsPerBlock; // XXXdbg struct hfsmount *hfsmp = VCBTOHFS(vcb); @@ -1011,7 +1171,7 @@ OSErr BlockMarkAllocated( // Initialize currentWord, and wordsLeft. // { - UInt32 wordIndexInBlock; + u_int32_t wordIndexInBlock; bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte; wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord; @@ -1042,7 +1202,7 @@ OSErr BlockMarkAllocated( } #if DEBUG_BUILD if ((*currentWord & SWAP_BE32 (bitMask)) != 0) { - panic("BlockMarkAllocated: blocks already allocated!"); + panic("hfs: BlockMarkAllocated: blocks already allocated!"); } #endif *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap @@ -1080,7 +1240,7 @@ OSErr BlockMarkAllocated( } #if DEBUG_BUILD if (*currentWord != 0) { - panic("BlockMarkAllocated: blocks already allocated!"); + panic("hfs: BlockMarkAllocated: blocks already allocated!"); } #endif *currentWord = SWAP_BE32 (bitMask); @@ -1118,7 +1278,7 @@ OSErr BlockMarkAllocated( } #if DEBUG_BUILD if ((*currentWord & SWAP_BE32 (bitMask)) != 0) { - panic("BlockMarkAllocated: blocks already allocated!"); + panic("hfs: BlockMarkAllocated: blocks already allocated!"); } #endif *currentWord |= SWAP_BE32 (bitMask); // set the bits in the bitmap @@ -1153,29 +1313,38 @@ _______________________________________________________________________ __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; + uintptr_t blockRef; + u_int32_t bitsPerBlock; + u_int32_t wordsPerBlock; // XXXdbg struct hfsmount *hfsmp = VCBTOHFS(vcb); + dk_discard_t discard; + /* + * 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: block mark free: trying to free non-existent blocks (%d %d %d)\n", - startingBlock, numBlocks, vcb->totalBlocks); - err = EIO; - goto Exit; + 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; } + memset(&discard, 0, sizeof(dk_discard_t)); + discard.offset = (uint64_t)startingBlock * (uint64_t)vcb->blockSize; + discard.length = (uint64_t)numBlocks * (uint64_t)vcb->blockSize; + // // Pre-read the bitmap block containing the first word of allocation @@ -1192,7 +1361,7 @@ OSErr BlockMarkFree( // Initialize currentWord, and wordsLeft. // { - UInt32 wordIndexInBlock; + u_int32_t wordIndexInBlock; bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte; wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord; @@ -1300,15 +1469,20 @@ Exit: if (buffer) (void)ReleaseBitmapBlock(vcb, blockRef, true); + if (err == noErr) { + // it doesn't matter if this fails, it's just informational anyway + VNOP_IOCTL(vcb->hfs_devvp, DKIOCDISCARD, (caddr_t)&discard, 0, vfs_context_kernel()); + } + + return err; Corruption: #if DEBUG_BUILD - panic("BlockMarkFree: blocks not allocated!"); + panic("hfs: BlockMarkFree: blocks not allocated!"); #else - printf("hfs: WARNING - blocks on volume %s not allocated!\n", vcb->vcbVN); - vcb->vcbAtrb |= kHFSVolumeInconsistentMask; - MarkVCBDirty(vcb); + printf ("hfs: BlockMarkFree() trying to free unallocated blocks on volume %s\n", vcb->vcbVN); + hfs_mark_volume_inconsistent(vcb); err = EIO; goto Exit; #endif @@ -1344,26 +1518,27 @@ _______________________________________________________________________ static OSErr BlockFindContiguous( ExtendedVCB *vcb, - UInt32 startingBlock, - UInt32 endingBlock, - UInt32 minBlocks, - UInt32 maxBlocks, + u_int32_t startingBlock, + u_int32_t endingBlock, + u_int32_t minBlocks, + u_int32_t maxBlocks, Boolean useMetaZone, - UInt32 *actualStartBlock, - UInt32 *actualNumBlocks) + 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; + uintptr_t blockRef; + u_int32_t wordsPerBlock; + u_int32_t j, updated_free_extents = 0, really_add; /* * When we're skipping the metadata zone and the start/end @@ -1546,7 +1721,7 @@ FoundUnused: * Skip over metadata blocks. */ if (!useMetaZone) { - UInt32 nextBlock; + u_int32_t nextBlock; nextBlock = NextBitmapBlock(vcb, currentBlock); if (nextBlock != currentBlock) { @@ -1601,23 +1776,71 @@ FoundUsed: // This free chunk wasn't big enough. Try inserting it into the free extent cache in case // the allocation wasn't forced contiguous. + really_add = 0; + for(j=0; j < vcb->vcbFreeExtCnt; j++) { + u_int32_t start, end; + + start = vcb->vcbFreeExt[j].startBlock; + end = start + vcb->vcbFreeExt[j].blockCount; + + if ( (firstBlock >= start && firstBlock < end) + || ((firstBlock + foundBlocks) > start && firstBlock < start)) { + + // there's overlap with an existing entry so do not add this + break; + } + + } + + if (j >= vcb->vcbFreeExtCnt) { + really_add = 1; + } + tempWord = vcb->vcbFreeExtCnt; - if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks) - --tempWord; - if (tempWord < kMaxFreeExtents) - { - // We're going to add this extent. Bubble any smaller extents down in the list. - while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < foundBlocks) - { - vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1]; + if (really_add && (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE)) { + // Sorted by starting block + if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].startBlock > firstBlock) --tempWord; + if (tempWord < kMaxFreeExtents) + { + // We're going to add this extent. Bubble any smaller extents down in the list. + while (tempWord && vcb->vcbFreeExt[tempWord-1].startBlock > firstBlock) + { + vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1]; + --tempWord; + } + vcb->vcbFreeExt[tempWord].startBlock = firstBlock; + vcb->vcbFreeExt[tempWord].blockCount = foundBlocks; + + if (vcb->vcbFreeExtCnt < kMaxFreeExtents) { + ++vcb->vcbFreeExtCnt; + } + updated_free_extents = 1; } - vcb->vcbFreeExt[tempWord].startBlock = firstBlock; - vcb->vcbFreeExt[tempWord].blockCount = foundBlocks; + } else if (really_add) { + // Sorted by blockCount + if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks) + --tempWord; + if (tempWord < kMaxFreeExtents) + { + // We're going to add this extent. Bubble any smaller extents down in the list. + while (tempWord && vcb->vcbFreeExt[tempWord-1].blockCount < foundBlocks) + { + vcb->vcbFreeExt[tempWord] = vcb->vcbFreeExt[tempWord-1]; + --tempWord; + } + vcb->vcbFreeExt[tempWord].startBlock = firstBlock; + vcb->vcbFreeExt[tempWord].blockCount = foundBlocks; - if (vcb->vcbFreeExtCnt < kMaxFreeExtents) - ++vcb->vcbFreeExtCnt; + if (vcb->vcbFreeExtCnt < kMaxFreeExtents) { + ++vcb->vcbFreeExtCnt; + } + updated_free_extents = 1; + } } + + sanity_check_free_ext(vcb, 0); + } while (currentBlock < stopBlock); LoopExit: @@ -1635,11 +1858,42 @@ ErrorExit: err = noErr; *actualStartBlock = firstBlock; *actualNumBlocks = foundBlocks; + /* + * Sanity check for overflow + */ + if ((firstBlock + foundBlocks) > vcb->allocLimit) { + panic("hfs: 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 (updated_free_extents && (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE)) { + int i; + u_int32_t min_start = vcb->totalBlocks; + + // set the nextAllocation pointer to the smallest free block number + // we've seen so on the next mount we won't rescan unnecessarily + for(i=0; i < (int)vcb->vcbFreeExtCnt; i++) { + if (vcb->vcbFreeExt[i].startBlock < min_start) { + min_start = vcb->vcbFreeExt[i].startBlock; + } + } + if (min_start != vcb->totalBlocks) { + if (min_start < vcb->nextAllocation) { + vcb->nextAllocation = min_start; + } + if (min_start < vcb->sparseAllocation) { + vcb->sparseAllocation = min_start; + } + } } if (buffer) (void) ReleaseBitmapBlock(vcb, blockRef, false); + sanity_check_free_ext(vcb, 1); + return err; } @@ -1650,17 +1904,17 @@ ErrorExit: */ __private_extern__ int -hfs_isallocated(struct hfsmount *hfsmp, u_long startingBlock, u_long numBlocks) +hfs_isallocated(struct hfsmount *hfsmp, u_int32_t startingBlock, u_int32_t numBlocks) { - UInt32 *currentWord; // Pointer to current word within bitmap block - UInt32 wordsLeft; // Number of words left in this bitmap block - UInt32 bitMask; // Word with given bits already set (ready to test) - 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; + 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; + uintptr_t blockRef; + u_int32_t bitsPerBlock; + u_int32_t wordsPerBlock; int inuse = 0; int error; @@ -1675,7 +1929,7 @@ hfs_isallocated(struct hfsmount *hfsmp, u_long startingBlock, u_long numBlocks) * Initialize currentWord, and wordsLeft. */ { - UInt32 wordIndexInBlock; + u_int32_t wordIndexInBlock; bitsPerBlock = hfsmp->vcbVBMIOSize * kBitsPerByte; wordsPerBlock = hfsmp->vcbVBMIOSize / kBytesPerWord;