VolumeAllocation.c [plain text]
#include "../../hfs_macos_defs.h"
#include <sys/types.h>
#include <sys/buf.h>
#include <sys/systm.h>
#include <sys/disk.h>
#include "../../hfs.h"
#include "../../hfs_dbg.h"
#include "../../hfs_format.h"
#include "../../hfs_endian.h"
#include "../headers/FileMgrInternal.h"
enum {
kBytesPerWord = 4,
kBitsPerByte = 8,
kBitsPerWord = 32,
kBitsWithinWordMask = kBitsPerWord-1
};
#define kLowBitInWordMask 0x00000001ul
#define kHighBitInWordMask 0x80000000ul
#define kAllBitsSetInWord 0xFFFFFFFFul
static OSErr ReadBitmapBlock(
ExtendedVCB *vcb,
u_int32_t bit,
u_int32_t **buffer,
uintptr_t *blockRef);
static OSErr ReleaseBitmapBlock(
ExtendedVCB *vcb,
uintptr_t blockRef,
Boolean dirty);
static OSErr BlockAllocateAny(
ExtendedVCB *vcb,
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,
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,
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,
u_int32_t maxBlocks,
u_int32_t *actualStartBlock,
u_int32_t *actualNumBlocks);
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,
u_int32_t startingBlock,
u_int32_t minBlocks,
u_int32_t maxBlocks,
Boolean forceContiguous,
Boolean useMetaZone,
u_int32_t *actualStartBlock,
u_int32_t *actualNumBlocks)
{
u_int32_t freeBlocks;
OSErr err;
Boolean updateAllocPtr = false;
*actualStartBlock = 0;
*actualNumBlocks = 0;
freeBlocks = hfs_freeblks(VCBTOHFS(vcb), 0);
if (freeBlocks == 0) {
err = dskFulErr;
goto Exit;
}
if (forceContiguous && freeBlocks < minBlocks) {
err = dskFulErr;
goto Exit;
}
if (minBlocks > freeBlocks) {
minBlocks = freeBlocks;
}
if (maxBlocks > freeBlocks) {
maxBlocks = freeBlocks;
}
if (startingBlock == 0) {
HFS_MOUNT_LOCK(vcb, TRUE);
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->allocLimit) {
startingBlock = 0;
}
if (forceContiguous) {
err = BlockAllocateContig(vcb, startingBlock, minBlocks, maxBlocks,
useMetaZone, actualStartBlock, actualNumBlocks);
if ((err == noErr) &&
(*actualStartBlock > startingBlock) &&
((*actualStartBlock < VCBTOHFS(vcb)->hfs_metazone_start) ||
(*actualStartBlock > VCBTOHFS(vcb)->hfs_metazone_end))) {
updateAllocPtr = true;
}
} else {
err = BlockAllocateKnown(vcb, maxBlocks, actualStartBlock, actualNumBlocks);
if (err == dskFulErr)
err = BlockAllocateAny(vcb, startingBlock, vcb->allocLimit,
maxBlocks, useMetaZone, actualStartBlock,
actualNumBlocks);
if (err == dskFulErr)
err = BlockAllocateAny(vcb, 1, startingBlock, maxBlocks,
useMetaZone, actualStartBlock,
actualNumBlocks);
}
Exit:
if (*actualNumBlocks != 0) {
int i,j;
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))) {
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--;
}
}
vcb->freeBlocks -= *actualNumBlocks;
MarkVCBDirty(vcb);
HFS_MOUNT_UNLOCK(vcb, TRUE);
sanity_check_free_ext(vcb, 1);
hfs_generate_volume_notifications(VCBTOHFS(vcb));
}
return err;
}
__private_extern__
OSErr BlockDeallocate (
ExtendedVCB *vcb, u_int32_t firstBlock, u_int32_t numBlocks) {
OSErr err;
u_int32_t tempWord;
if (numBlocks == 0) {
err = noErr;
goto Exit;
}
err = BlockMarkFree(vcb, firstBlock, numBlocks);
if (err)
goto Exit;
HFS_MOUNT_LOCK(vcb, TRUE);
vcb->freeBlocks += 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;
if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) {
if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].startBlock > firstBlock)
--tempWord;
if (tempWord < kMaxFreeExtents)
{
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 {
if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < numBlocks)
--tempWord;
if (tempWord < kMaxFreeExtents)
{
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:
return err;
}
u_int8_t freebitcount[16] = {
4, 3, 3, 2, 3, 2, 2, 1,
3, 2, 2, 1, 2, 1, 1, 0,
};
__private_extern__
u_int32_t
MetaZoneFreeBlocks(ExtendedVCB *vcb)
{
u_int32_t freeblocks;
u_int32_t *currCache;
uintptr_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;
lastbit = VCBTOHFS(vcb)->hfs_metazone_end;
bytesperblock = vcb->vcbVBMIOSize;
while (bit < lastbit) {
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);
}
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);
if ((bit >= hfsmp->hfs_metazone_start) &&
(bit <= hfsmp->hfs_metazone_end)) {
bit = hfsmp->hfs_metazone_end + 1;
}
return (bit);
}
static OSErr ReadBitmapBlock(
ExtendedVCB *vcb,
u_int32_t bit,
u_int32_t **buffer,
uintptr_t *blockRef)
{
OSErr err;
struct buf *bp = NULL;
struct vnode *vp = NULL;
daddr64_t block;
u_int32_t blockSize;
REQUIRE_FILE_LOCK(vcb->hfs_allocation_vp, false);
blockSize = (u_int32_t)vcb->vcbVBMIOSize;
block = (daddr64_t)(bit / (blockSize * kBitsPerByte));
if (vcb->vcbSigWord == kHFSPlusSigWord) {
vp = vcb->hfs_allocation_vp;
} else {
vp = VCBTOHFS(vcb)->hfs_devvp;
block += vcb->vcbVBMSt;
}
err = (int)buf_meta_bread(vp, block, blockSize, NOCRED, &bp);
if (bp) {
if (err) {
buf_brelse(bp);
*blockRef = 0;
*buffer = NULL;
} else {
*blockRef = (uintptr_t)bp;
*buffer = (u_int32_t *)buf_dataptr(bp);
}
}
return err;
}
static OSErr ReleaseBitmapBlock(
ExtendedVCB *vcb,
uintptr_t blockRef,
Boolean dirty)
{
struct buf *bp = (struct buf *)blockRef;
if (blockRef == 0) {
if (dirty)
panic("hfs: ReleaseBitmapBlock: missing bp");
return (0);
}
if (bp) {
if (dirty) {
struct hfsmount *hfsmp = VCBTOHFS(vcb);
if (hfsmp->jnl) {
journal_modify_block_end(hfsmp->jnl, bp, NULL, NULL);
} else {
buf_bdwrite(bp);
}
} else {
buf_brelse(bp);
}
}
return (0);
}
static OSErr BlockAllocateContig(
ExtendedVCB *vcb,
u_int32_t startingBlock,
u_int32_t minBlocks,
u_int32_t maxBlocks,
Boolean useMetaZone,
u_int32_t *actualStartBlock,
u_int32_t *actualNumBlocks)
{
OSErr err;
err = BlockFindContiguous(vcb, startingBlock, vcb->allocLimit, minBlocks,
maxBlocks, useMetaZone, actualStartBlock, actualNumBlocks);
if (err == dskFulErr && startingBlock != 0) {
err = BlockFindContiguous(vcb, 1, startingBlock, minBlocks, maxBlocks,
useMetaZone, actualStartBlock, actualNumBlocks);
}
if (err == noErr)
err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
return err;
}
static OSErr BlockAllocateAny(
ExtendedVCB *vcb,
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 u_int32_t block; register u_int32_t currentWord; register u_int32_t bitMask; register u_int32_t wordsLeft; 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);
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;
}
}
}
if (maxBlocks > (endingBlock - startingBlock)) {
maxBlocks = endingBlock - startingBlock;
}
err = ReadBitmapBlock(vcb, startingBlock, &currCache, &blockRef);
if (err != noErr) goto Exit;
buffer = currCache;
{
u_int32_t wordIndexInBlock;
bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
buffer += wordIndexInBlock;
wordsLeft = wordsPerBlock - wordIndexInBlock;
currentWord = SWAP_BE32 (*buffer);
bitMask = kHighBitInWordMask >> (startingBlock & kBitsWithinWordMask);
}
block=startingBlock;
while (block < endingBlock) {
if ((currentWord & bitMask) == 0)
break;
++block;
bitMask >>= 1;
if (bitMask == 0) {
bitMask = kHighBitInWordMask;
++buffer;
if (--wordsLeft == 0) {
buffer = currCache = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, false);
if (err != noErr) goto Exit;
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;
wordsLeft = wordsPerBlock;
}
currentWord = SWAP_BE32 (*buffer);
}
}
if (block >= endingBlock) {
err = dskFulErr;
goto Exit;
}
*actualStartBlock = block;
dirty = true;
if (block < (endingBlock-maxBlocks)) {
endingBlock = block + maxBlocks; }
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
while ((currentWord & bitMask) == 0) {
currentWord |= bitMask;
++block;
if (block == endingBlock)
break;
bitMask >>= 1;
if (bitMask == 0) {
*buffer = SWAP_BE32 (currentWord);
bitMask = kHighBitInWordMask;
++buffer;
if (--wordsLeft == 0) {
buffer = currCache = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, true);
if (err != noErr) goto Exit;
if (!useMetaZone) {
u_int32_t nextBlock;
nextBlock = NextBitmapBlock(vcb, block);
if (nextBlock != block) {
goto Exit;
}
}
err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
if (err != noErr) goto Exit;
buffer = currCache;
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
wordsLeft = wordsPerBlock;
}
currentWord = SWAP_BE32 (*buffer);
}
}
*buffer = SWAP_BE32 (currentWord);
Exit:
if (err == noErr) {
*actualNumBlocks = block - *actualStartBlock;
if ((*actualStartBlock + *actualNumBlocks) > vcb->allocLimit)
panic("hfs: BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN);
}
else {
*actualStartBlock = 0;
*actualNumBlocks = 0;
}
if (currCache)
(void) ReleaseBitmapBlock(vcb, blockRef, dirty);
return err;
}
static OSErr BlockAllocateKnown(
ExtendedVCB *vcb,
u_int32_t maxBlocks,
u_int32_t *actualStartBlock,
u_int32_t *actualNumBlocks)
{
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;
*actualStartBlock = vcb->vcbFreeExt[0].startBlock;
foundBlocks = vcb->vcbFreeExt[0].blockCount;
if (foundBlocks > maxBlocks)
foundBlocks = maxBlocks;
*actualNumBlocks = foundBlocks;
if (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE) {
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;
}
newStartBlock = vcb->vcbFreeExt[0].startBlock + foundBlocks;
newBlockCount = vcb->vcbFreeExt[0].blockCount - foundBlocks;
for (i=1; i<vcb->vcbFreeExtCnt; ++i)
{
if (vcb->vcbFreeExt[i].blockCount > newBlockCount)
{
vcb->vcbFreeExt[i-1].startBlock = vcb->vcbFreeExt[i].startBlock;
vcb->vcbFreeExt[i-1].blockCount = vcb->vcbFreeExt[i].blockCount;
}
else
{
break;
}
}
if (newBlockCount == 0)
{
--vcb->vcbFreeExtCnt;
}
else
{
vcb->vcbFreeExt[i-1].startBlock = newStartBlock;
vcb->vcbFreeExt[i-1].blockCount = newBlockCount;
}
done:
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
{
err = BlockMarkAllocated(vcb, *actualStartBlock, *actualNumBlocks);
}
sanity_check_free_ext(vcb, 1);
return err;
}
__private_extern__
OSErr BlockMarkAllocated(
ExtendedVCB *vcb,
u_int32_t startingBlock,
register u_int32_t numBlocks)
{
OSErr err;
register u_int32_t *currentWord; register u_int32_t wordsLeft; register u_int32_t bitMask; u_int32_t firstBit; u_int32_t numBits; u_int32_t *buffer = NULL;
uintptr_t blockRef;
u_int32_t bitsPerBlock;
u_int32_t wordsPerBlock;
struct hfsmount *hfsmp = VCBTOHFS(vcb);
err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
if (err != noErr) goto Exit;
{
u_int32_t wordIndexInBlock;
bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
currentWord = buffer + wordIndexInBlock;
wordsLeft = wordsPerBlock - wordIndexInBlock;
}
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
firstBit = startingBlock % kBitsPerWord;
if (firstBit != 0) {
bitMask = kAllBitsSetInWord >> firstBit; numBits = kBitsPerWord - firstBit; if (numBits > numBlocks) {
numBits = numBlocks; bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); }
#if DEBUG_BUILD
if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
panic("hfs: BlockMarkAllocated: blocks already allocated!");
}
#endif
*currentWord |= SWAP_BE32 (bitMask); numBlocks -= numBits;
++currentWord; --wordsLeft; }
bitMask = kAllBitsSetInWord; while (numBlocks >= kBitsPerWord) {
if (wordsLeft == 0) {
startingBlock += bitsPerBlock;
buffer = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, true);
if (err != noErr) goto Exit;
err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
if (err != noErr) goto Exit;
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
currentWord = buffer;
wordsLeft = wordsPerBlock;
}
#if DEBUG_BUILD
if (*currentWord != 0) {
panic("hfs: BlockMarkAllocated: blocks already allocated!");
}
#endif
*currentWord = SWAP_BE32 (bitMask);
numBlocks -= kBitsPerWord;
++currentWord; --wordsLeft; }
if (numBlocks != 0) {
bitMask = ~(kAllBitsSetInWord >> numBlocks); if (wordsLeft == 0) {
startingBlock += bitsPerBlock;
buffer = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, true);
if (err != noErr) goto Exit;
err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
if (err != noErr) goto Exit;
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
currentWord = buffer;
wordsLeft = wordsPerBlock;
}
#if DEBUG_BUILD
if ((*currentWord & SWAP_BE32 (bitMask)) != 0) {
panic("hfs: BlockMarkAllocated: blocks already allocated!");
}
#endif
*currentWord |= SWAP_BE32 (bitMask);
}
Exit:
if (buffer)
(void)ReleaseBitmapBlock(vcb, blockRef, true);
return err;
}
__private_extern__
OSErr BlockMarkFree(
ExtendedVCB *vcb,
u_int32_t startingBlock,
register u_int32_t numBlocks)
{
OSErr err;
register u_int32_t *currentWord; register u_int32_t wordsLeft; register u_int32_t bitMask; u_int32_t firstBit; u_int32_t numBits; u_int32_t *buffer = NULL;
uintptr_t blockRef;
u_int32_t bitsPerBlock;
u_int32_t wordsPerBlock;
struct hfsmount *hfsmp = VCBTOHFS(vcb);
dk_discard_t discard;
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;
}
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;
err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
if (err != noErr) goto Exit;
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
{
u_int32_t wordIndexInBlock;
bitsPerBlock = vcb->vcbVBMIOSize * kBitsPerByte;
wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
currentWord = buffer + wordIndexInBlock;
wordsLeft = wordsPerBlock - wordIndexInBlock;
}
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)) != SWAP_BE32 (bitMask)) {
goto Corruption;
}
*currentWord &= SWAP_BE32 (~bitMask); numBlocks -= numBits;
++currentWord; --wordsLeft; }
while (numBlocks >= kBitsPerWord) {
if (wordsLeft == 0) {
startingBlock += bitsPerBlock;
buffer = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, true);
if (err != noErr) goto Exit;
err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
if (err != noErr) goto Exit;
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
currentWord = buffer;
wordsLeft = wordsPerBlock;
}
if (*currentWord != SWAP_BE32 (kAllBitsSetInWord)) {
goto Corruption;
}
*currentWord = 0; numBlocks -= kBitsPerWord;
++currentWord; --wordsLeft; }
if (numBlocks != 0) {
bitMask = ~(kAllBitsSetInWord >> numBlocks); if (wordsLeft == 0) {
startingBlock += bitsPerBlock;
buffer = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, true);
if (err != noErr) goto Exit;
err = ReadBitmapBlock(vcb, startingBlock, &buffer, &blockRef);
if (err != noErr) goto Exit;
if (hfsmp->jnl) {
journal_modify_block_start(hfsmp->jnl, (struct buf *)blockRef);
}
currentWord = buffer;
wordsLeft = wordsPerBlock;
}
if ((*currentWord & SWAP_BE32 (bitMask)) != SWAP_BE32 (bitMask)) {
goto Corruption;
}
*currentWord &= SWAP_BE32 (~bitMask);
}
Exit:
if (buffer)
(void)ReleaseBitmapBlock(vcb, blockRef, true);
if (err == noErr) {
VNOP_IOCTL(vcb->hfs_devvp, DKIOCDISCARD, (caddr_t)&discard, 0, vfs_context_kernel());
}
return err;
Corruption:
#if DEBUG_BUILD
panic("hfs: 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
}
static OSErr BlockFindContiguous(
ExtendedVCB *vcb,
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 u_int32_t currentBlock; u_int32_t firstBlock; u_int32_t stopBlock; u_int32_t foundBlocks; 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;
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)
{
goto DiskFull;
}
stopBlock = endingBlock - minBlocks + 1;
currentBlock = startingBlock;
firstBlock = 0;
if (!useMetaZone)
currentBlock = NextBitmapBlock(vcb, currentBlock);
err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
if ( err != noErr ) goto ErrorExit;
wordsPerBlock = vcb->vcbVBMIOSize / kBytesPerWord;
wordsLeft = (currentBlock / kBitsPerWord) & (wordsPerBlock-1); currentWord = buffer + wordsLeft;
wordsLeft = wordsPerBlock - wordsLeft;
do
{
foundBlocks = 0;
bitMask = currentBlock & kBitsWithinWordMask;
if (bitMask)
{
tempWord = SWAP_BE32(*currentWord); bitMask = kHighBitInWordMask >> bitMask;
while (tempWord & bitMask)
{
bitMask >>= 1;
++currentBlock;
}
if (bitMask)
goto FoundUnused;
++currentWord;
--wordsLeft;
}
while (currentBlock < stopBlock)
{
if (wordsLeft == 0)
{
buffer = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, false);
if (err != noErr) goto ErrorExit;
if (!useMetaZone) {
currentBlock = NextBitmapBlock(vcb, currentBlock);
if (currentBlock >= stopBlock) {
goto LoopExit;
}
}
err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
if ( err != noErr ) goto ErrorExit;
currentWord = buffer;
wordsLeft = wordsPerBlock;
}
if ((tempWord = SWAP_BE32(*currentWord)) + 1) {
bitMask = kHighBitInWordMask;
while (tempWord & bitMask)
{
bitMask >>= 1;
++currentBlock;
}
break; }
currentBlock += kBitsPerWord;
++currentWord;
--wordsLeft;
}
FoundUnused:
if (currentBlock >= stopBlock)
{
break;
}
firstBlock = currentBlock;
bitMask = currentBlock & kBitsWithinWordMask;
if (bitMask)
{
tempWord = SWAP_BE32(*currentWord); bitMask = kHighBitInWordMask >> bitMask;
while (bitMask && !(tempWord & bitMask))
{
bitMask >>= 1;
++currentBlock;
}
if (bitMask)
goto FoundUsed;
++currentWord;
--wordsLeft;
}
while (currentBlock < endingBlock)
{
if (wordsLeft == 0)
{
buffer = NULL;
err = ReleaseBitmapBlock(vcb, blockRef, false);
if (err != noErr) goto ErrorExit;
if (!useMetaZone) {
u_int32_t nextBlock;
nextBlock = NextBitmapBlock(vcb, currentBlock);
if (nextBlock != currentBlock) {
goto LoopExit;
}
}
err = ReadBitmapBlock(vcb, currentBlock, &buffer, &blockRef);
if ( err != noErr ) goto ErrorExit;
currentWord = buffer;
wordsLeft = wordsPerBlock;
}
if ((tempWord = SWAP_BE32(*currentWord)) != 0)
{
bitMask = kHighBitInWordMask;
while (!(tempWord & bitMask))
{
bitMask >>= 1;
++currentBlock;
}
break; }
currentBlock += kBitsPerWord;
++currentWord;
--wordsLeft;
if ((currentBlock - firstBlock) >= maxBlocks)
break;
}
FoundUsed:
if (currentBlock > endingBlock)
currentBlock = endingBlock;
foundBlocks = currentBlock - firstBlock;
if (foundBlocks > maxBlocks)
foundBlocks = maxBlocks;
if (foundBlocks >= minBlocks)
break;
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)) {
break;
}
}
if (j >= vcb->vcbFreeExtCnt) {
really_add = 1;
}
tempWord = vcb->vcbFreeExtCnt;
if (really_add && (vcb->hfs_flags & HFS_HAS_SPARSE_DEVICE)) {
if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].startBlock > firstBlock)
--tempWord;
if (tempWord < kMaxFreeExtents)
{
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;
}
} else if (really_add) {
if (tempWord == kMaxFreeExtents && vcb->vcbFreeExt[kMaxFreeExtents-1].blockCount < foundBlocks)
--tempWord;
if (tempWord < kMaxFreeExtents)
{
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;
}
updated_free_extents = 1;
}
}
sanity_check_free_ext(vcb, 0);
} while (currentBlock < stopBlock);
LoopExit:
if (foundBlocks < minBlocks)
{
DiskFull:
err = dskFulErr;
ErrorExit:
*actualStartBlock = 0;
*actualNumBlocks = 0;
}
else
{
err = noErr;
*actualStartBlock = firstBlock;
*actualNumBlocks = foundBlocks;
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;
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;
}
__private_extern__
int
hfs_isallocated(struct hfsmount *hfsmp, u_int32_t startingBlock, u_int32_t numBlocks)
{
u_int32_t *currentWord; u_int32_t wordsLeft; u_int32_t bitMask; u_int32_t firstBit; u_int32_t numBits; u_int32_t *buffer = NULL;
uintptr_t blockRef;
u_int32_t bitsPerBlock;
u_int32_t wordsPerBlock;
int inuse = 0;
int error;
error = ReadBitmapBlock(hfsmp, startingBlock, &buffer, &blockRef);
if (error)
return (error);
{
u_int32_t wordIndexInBlock;
bitsPerBlock = hfsmp->vcbVBMIOSize * kBitsPerByte;
wordsPerBlock = hfsmp->vcbVBMIOSize / kBytesPerWord;
wordIndexInBlock = (startingBlock & (bitsPerBlock-1)) / kBitsPerWord;
currentWord = buffer + wordIndexInBlock;
wordsLeft = wordsPerBlock - wordIndexInBlock;
}
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;
}
while (numBlocks >= kBitsPerWord) {
if (wordsLeft == 0) {
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 != 0) {
inuse = 1;
goto Exit;
}
numBlocks -= kBitsPerWord;
++currentWord;
--wordsLeft;
}
if (numBlocks != 0) {
bitMask = ~(kAllBitsSetInWord >> numBlocks);
if (wordsLeft == 0) {
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);
}