VolumeBitmapCheck.c [plain text]
#include "Scavenger.h"
#include <sys/disk.h>
#include <bitstring.h>
#define bit_dealloc(p) free(p)
#define _VBC_DEBUG_ 0
enum {
kBitsPerByte = 8,
kBitsPerWord = 32,
kBitsPerSegment = 1024,
kBytesPerSegment = kBitsPerSegment / kBitsPerByte,
kWordsPerSegment = kBitsPerSegment / kBitsPerWord,
kBitsWithinWordMask = kBitsPerWord-1,
kBitsWithinSegmentMask = kBitsPerSegment-1,
kBMS_NodesPerPool = 450,
kBMS_PoolMax = 2000
};
#define kAllBitsSetInWord 0xFFFFFFFFu
#define kMSBBitSetInWord 0x80000000u
enum {
kSettingBits = 1,
kClearingBits = 2,
kTestingBits = 3
};
#define kEmptySegment 0
#define kFullSegment 1
int gBitMapInited = 0;
bitstr_t* gFullSegmentList;
UInt32 gBitsMarked;
UInt32 gTotalBits;
UInt32 gTotalSegments;
UInt32* gFullBitmapSegment;
UInt32* gEmptyBitmapSegment;
typedef struct BMS_Node {
struct BMS_Node *left;
struct BMS_Node *right;
UInt32 segment;
UInt32 bitmap[kWordsPerSegment];
} BMS_Node;
BMS_Node *gBMS_Root;
BMS_Node *gBMS_FreeNodes;
BMS_Node *gBMS_PoolList[kBMS_PoolMax];
int gBMS_PoolCount;
static int FindContigClearedBitmapBits (SVCB *vcb, UInt32 numBlocks, UInt32 *actualStartBlock);
static int BMS_InitTree(void);
static int BMS_DisposeTree(void);
static BMS_Node * BMS_Lookup(UInt32 segment);
static BMS_Node * BMS_Insert(UInt32 segment, int segmentType);
static BMS_Node * BMS_Delete(UInt32 segment);
static void BMS_GrowNodePool(void);
#if _VBC_DEBUG_
static void BMS_PrintTree(BMS_Node * root);
static void BMS_MaxDepth(BMS_Node * root, int depth, int *maxdepth);
#endif
int BitMapCheckBegin(SGlobPtr g)
{
Boolean isHFSPlus;
if (gBitMapInited)
return (0);
isHFSPlus = VolumeObjectIsHFSPlus( );
gFullBitmapSegment = (UInt32 *)malloc(kBytesPerSegment);
memset((void *)gFullBitmapSegment, 0xff, kBytesPerSegment);
gEmptyBitmapSegment = (UInt32 *)malloc(kBytesPerSegment);
memset((void *)gEmptyBitmapSegment, 0x00, kBytesPerSegment);
gTotalBits = g->calculatedVCB->vcbTotalBlocks;
gTotalSegments = (gTotalBits / kBitsPerSegment);
if (gTotalBits % kBitsPerSegment)
++gTotalSegments;
gFullSegmentList = bit_alloc(gTotalSegments);
bit_nclear(gFullSegmentList, 0, gTotalSegments - 1);
BMS_InitTree();
gBitMapInited = 1;
gBitsMarked = 0;
if (isHFSPlus) {
UInt16 alignBits;
if (g->calculatedVCB->vcbBlockSize == 512)
alignBits = 2;
else if (g->calculatedVCB->vcbBlockSize == 1024)
alignBits = 1;
else
alignBits = 0;
(void) CaptureBitmapBits(0, 1 + alignBits);
if (g->calculatedVCB->vcbBlockSize == 512)
alignBits = 1;
else
alignBits = 0;
(void) CaptureBitmapBits(gTotalBits - 1 - alignBits, 1 + alignBits);
}
return (0);
}
int gFullSegments = 0;
int gSegmentNodes = 0;
int BitMapCheckEnd(void)
{
if (gBitMapInited) {
#if _VBC_DEBUG_
int maxdepth = 0;
BMS_MaxDepth(gBMS_Root, 0, &maxdepth);
plog(" %d full segments, %d segment nodes (max depth was %d nodes)\n",
gFullSegments, gSegmentNodes, maxdepth);
#endif
free(gFullBitmapSegment);
gFullBitmapSegment = NULL;
free(gEmptyBitmapSegment);
gEmptyBitmapSegment = NULL;
bit_dealloc(gFullSegmentList);
gFullSegmentList = NULL;
BMS_DisposeTree();
gBitMapInited = 0;
}
return (0);
}
static int GetSegmentBitmap(UInt32 startBit, UInt32 **buffer, int bitOperation)
{
UInt32 segment;
BMS_Node *segNode = NULL;
*buffer = NULL;
segment = startBit / kBitsPerSegment;
if (bit_test(gFullSegmentList, segment)) {
if (bitOperation == kClearingBits) {
bit_clear(gFullSegmentList, segment);
--gFullSegments;
if ((segNode = BMS_Insert(segment, kFullSegment)) != NULL)
*buffer = &segNode->bitmap[0];
} else
*buffer = gFullBitmapSegment;
} else if ((segNode = BMS_Lookup(segment)) != NULL) {
*buffer = &segNode->bitmap[0];
} else {
if (bitOperation == kSettingBits) {
if ((segNode = BMS_Insert(segment, kEmptySegment)) != NULL)
*buffer = &segNode->bitmap[0];
} else
*buffer = gEmptyBitmapSegment;
}
if (*buffer == NULL) {
#if _VBC_DEBUG_
plog("GetSegmentBitmap: couldn't get a node for block %d, segment %d\n", startBit, segment);
#endif
return (-1);
}
#if 0
if (segNode) {
int i;
plog(" segment %d: L=0x%08x, R=0x%08x \n< ",
(int)segNode->segment, (int)segNode->left, segNode->right);
for (i = 0; i < kWordsPerSegment; ++i) {
plog("0x%08x ", segNode->bitmap[i]);
if ((i & 0x3) == 0x3)
plog("\n ");
}
plog("\n");
}
if (bitOperation == kSettingBits && *buffer && bcmp(*buffer, gFullBitmapSegment, kBytesPerSegment) == 0) {
plog("*** segment %d (start blk %d) is already full!\n", segment, startBit);
exit(5);
}
if (bitOperation == kClearingBits && *buffer && bcmp(*buffer, gEmptyBitmapSegment, kBytesPerSegment) == 0) {
plog("*** segment %d (start blk %d) is already empty!\n", segment, startBit);
exit(5);
}
#endif
return (0);
}
void TestSegmentBitmap(UInt32 startBit)
{
UInt32 segment;
BMS_Node *segNode = NULL;
segment = startBit / kBitsPerSegment;
if (bit_test(gFullSegmentList, segment))
return;
if ((segNode = BMS_Lookup(segment)) != NULL) {
#if 0
int i;
plog("> ");
for (i = 0; i < kWordsPerSegment; ++i) {
plog("0x%08x ", segNode->bitmap[i]);
if ((i & 0x3) == 0x3)
plog("\n ");
}
plog("\n");
#endif
if (segment != 0 && bcmp(&segNode->bitmap[0], gFullBitmapSegment, kBytesPerSegment) == 0) {
if (BMS_Delete(segment) != NULL) {
bit_set(gFullSegmentList, segment);
++gFullSegments;
--gSegmentNodes;
}
}
if (segment != 0 && bcmp(&segNode->bitmap[0], gEmptyBitmapSegment, kBytesPerSegment) == 0) {
if (BMS_Delete(segment) != NULL) {
--gSegmentNodes;
}
}
}
}
int CaptureBitmapBits(UInt32 startBit, UInt32 bitCount)
{
Boolean overlap;
OSErr err;
UInt32 wordsLeft;
UInt32 bitMask;
UInt32 firstBit;
UInt32 numBits;
UInt32 *buffer;
UInt32 *currentWord;
overlap = false;
if (bitCount == 0)
return (0);
if ((startBit + bitCount) > gTotalBits) {
err = vcInvalidExtentErr;
goto Exit;
}
gBitsMarked += bitCount;
err = GetSegmentBitmap(startBit, &buffer, kSettingBits);
if (err != noErr) goto Exit;
{
UInt32 wordIndexInSegment;
wordIndexInSegment = (startBit & kBitsWithinSegmentMask) / kBitsPerWord;
currentWord = buffer + wordIndexInSegment;
wordsLeft = kWordsPerSegment - wordIndexInSegment;
}
firstBit = startBit % kBitsPerWord;
if (firstBit != 0) {
bitMask = kAllBitsSetInWord >> firstBit; numBits = kBitsPerWord - firstBit; if (numBits > bitCount) {
numBits = bitCount; bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); }
if (SWAP_BE32(*currentWord) & bitMask) {
overlap = true;
}
*currentWord |= SWAP_BE32(bitMask);
bitCount -= numBits;
++currentWord;
--wordsLeft;
if (wordsLeft == 0 || bitCount == 0)
TestSegmentBitmap(startBit);
}
bitMask = kAllBitsSetInWord;
while (bitCount >= kBitsPerWord) {
if (wordsLeft == 0) {
startBit += kBitsPerSegment;
err = GetSegmentBitmap(startBit, &buffer, kSettingBits);
if (err != noErr) goto Exit;
currentWord = buffer;
wordsLeft = kWordsPerSegment;
}
if (SWAP_BE32(*currentWord) & bitMask) {
overlap = true;
}
*currentWord |= SWAP_BE32(bitMask);
bitCount -= kBitsPerWord;
++currentWord;
--wordsLeft;
if (wordsLeft == 0 || bitCount == 0)
TestSegmentBitmap(startBit);
}
if (bitCount != 0) {
bitMask = ~(kAllBitsSetInWord >> bitCount); if (wordsLeft == 0) {
startBit += kBitsPerSegment;
err = GetSegmentBitmap(startBit, &buffer, kSettingBits);
if (err != noErr) goto Exit;
currentWord = buffer;
wordsLeft = kWordsPerSegment;
}
if (SWAP_BE32(*currentWord) & bitMask) {
overlap = true;
}
*currentWord |= SWAP_BE32(bitMask);
TestSegmentBitmap(startBit);
}
Exit:
return (overlap ? E_OvlExt : err);
}
int ReleaseBitmapBits(UInt32 startBit, UInt32 bitCount)
{
Boolean overlap;
OSErr err;
UInt32 wordsLeft;
UInt32 bitMask;
UInt32 firstBit;
UInt32 numBits;
UInt32 *buffer;
UInt32 *currentWord;
overlap = false;
if (bitCount == 0)
return (0);
if ((startBit + bitCount) > gTotalBits) {
err = vcInvalidExtentErr;
goto Exit;
}
gBitsMarked -= bitCount;
err = GetSegmentBitmap(startBit, &buffer, kClearingBits);
if (err != noErr) goto Exit;
{
UInt32 wordIndexInSegment;
wordIndexInSegment = (startBit & kBitsWithinSegmentMask) / kBitsPerWord;
currentWord = buffer + wordIndexInSegment;
wordsLeft = kWordsPerSegment - wordIndexInSegment;
}
firstBit = startBit % kBitsPerWord;
if (firstBit != 0) {
bitMask = kAllBitsSetInWord >> firstBit; numBits = kBitsPerWord - firstBit; if (numBits > bitCount) {
numBits = bitCount; bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); }
if ((SWAP_BE32(*currentWord) & bitMask) != bitMask) {
overlap = true;
}
*currentWord &= SWAP_BE32(~bitMask);
bitCount -= numBits;
++currentWord;
--wordsLeft;
if (wordsLeft == 0 || bitCount == 0)
TestSegmentBitmap(startBit);
}
bitMask = kAllBitsSetInWord;
while (bitCount >= kBitsPerWord) {
if (wordsLeft == 0) {
startBit += kBitsPerSegment;
err = GetSegmentBitmap(startBit, &buffer, kClearingBits);
if (err != noErr) goto Exit;
currentWord = buffer;
wordsLeft = kWordsPerSegment;
}
if ((SWAP_BE32(*currentWord) & bitMask) != bitMask) {
overlap = true;
}
*currentWord &= SWAP_BE32(~bitMask);
bitCount -= kBitsPerWord;
++currentWord;
--wordsLeft;
if (wordsLeft == 0 || bitCount == 0)
TestSegmentBitmap(startBit);
}
if (bitCount != 0) {
bitMask = ~(kAllBitsSetInWord >> bitCount); if (wordsLeft == 0) {
startBit += kBitsPerSegment;
err = GetSegmentBitmap(startBit, &buffer, kClearingBits);
if (err != noErr) goto Exit;
currentWord = buffer;
wordsLeft = kWordsPerSegment;
}
if ((SWAP_BE32(*currentWord) & bitMask) != bitMask) {
overlap = true;
}
*currentWord &= SWAP_BE32(~bitMask);
TestSegmentBitmap(startBit);
}
Exit:
return (overlap ? E_OvlExt : err);
}
int CheckVolumeBitMap(SGlobPtr g, Boolean repair)
{
UInt8 *vbmBlockP;
UInt32 *buffer;
UInt64 bit;
UInt32 bitsWithinFileBlkMask;
UInt32 fileBlk;
BlockDescriptor block;
ReleaseBlockOptions relOpt;
SFCB * fcb;
SVCB * vcb;
Boolean isHFSPlus;
Boolean foundOverAlloc = false;
int err = 0;
vcb = g->calculatedVCB;
fcb = g->calculatedAllocationsFCB;
isHFSPlus = VolumeObjectIsHFSPlus( );
if ( vcb->vcbFreeBlocks != (vcb->vcbTotalBlocks - gBitsMarked) ) {
vcb->vcbFreeBlocks = vcb->vcbTotalBlocks - gBitsMarked;
MarkVCBDirty(vcb);
}
vbmBlockP = (UInt8 *)NULL;
block.buffer = (void *)NULL;
relOpt = kReleaseBlock;
if ( isHFSPlus )
bitsWithinFileBlkMask = (fcb->fcbBlockSize * 8) - 1;
else
bitsWithinFileBlkMask = (kHFSBlockSize * 8) - 1;
fileBlk = (isHFSPlus ? 0 : vcb->vcbVBMSt);
for (bit = 0; bit < gTotalBits; bit += kBitsPerSegment) {
(void) GetSegmentBitmap(bit, &buffer, kTestingBits);
if ((bit & bitsWithinFileBlkMask) == 0) {
if (isHFSPlus) {
if (block.buffer) {
err = ReleaseFileBlock(fcb, &block, relOpt);
ReturnIfError(err);
}
err = GetFileBlock(fcb, fileBlk, kGetBlock, &block);
} else {
if (block.buffer) {
err = ReleaseVolumeBlock(vcb, &block, relOpt | kSkipEndianSwap);
ReturnIfError(err);
}
err = GetVolumeBlock(vcb, fileBlk, kGetBlock | kSkipEndianSwap, &block);
}
ReturnIfError(err);
vbmBlockP = (UInt8 *) block.buffer;
relOpt = kReleaseBlock;
g->TarBlock = fileBlk;
++fileBlk;
}
if (memcmp(buffer, vbmBlockP + (bit & bitsWithinFileBlkMask)/8, kBytesPerSegment) == 0)
continue;
if (repair) {
bcopy(buffer, vbmBlockP + (bit & bitsWithinFileBlkMask)/8, kBytesPerSegment);
relOpt = kForceWriteBlock;
} else {
int underalloc = 0;
int indx;
#if _VBC_DEBUG_
int i, j;
UInt32 *disk_buffer;
UInt32 dummy, block_num;
plog(" disk buffer + %d\n", (bit & bitsWithinFileBlkMask)/8);
plog("start block number for segment = %qu\n", bit);
plog("segment %qd\n", bit / kBitsPerSegment);
plog("Memory:\n");
for (i = 0; i < kWordsPerSegment; ++i) {
plog("0x%08x ", buffer[i]);
if ((i & 0x7) == 0x7)
plog("\n");
}
disk_buffer = (UInt32*) (vbmBlockP + (bit & bitsWithinFileBlkMask)/8);
plog("Disk:\n");
for (i = 0; i < kWordsPerSegment; ++i) {
plog("0x%08x ", disk_buffer[i]);
if ((i & 0x7) == 0x7)
plog("\n");
}
plog ("\n");
for (i = 0; i < kWordsPerSegment; ++i) {
if (buffer[i] != disk_buffer[i]) {
dummy = 0x80000000;
for (j = 0; j < kBitsPerWord; ++j) {
if ((buffer[i] & dummy) != (disk_buffer[i] & dummy)) {
block_num = bit + (i * kBitsPerWord) + j;
if (buffer[i] & dummy) {
plog ("Allocation block %u should be marked used on disk.\n", block_num);
} else {
plog ("Allocation block %u should be marked free on disk.\n", block_num);
}
}
dummy = dummy >> 1;
}
}
}
#endif
for (indx = 0; indx < kBytesPerSegment; indx++) {
uint8_t *bufp, *diskp;
bufp = (uint8_t *)buffer;
diskp = vbmBlockP + (bit & bitsWithinFileBlkMask)/8;
if (bufp[indx] & ~diskp[indx]) {
underalloc++;
break;
}
}
g->VIStat = g->VIStat | S_VBM;
if (underalloc) {
fsckPrint(g->context, E_VBMDamaged);
break;
} else if (!foundOverAlloc) {
fsckPrint(g->context, E_VBMDamagedOverAlloc);
foundOverAlloc = true;
}
}
++g->itemsProcessed;
}
if (block.buffer) {
if (isHFSPlus)
(void) ReleaseFileBlock(fcb, &block, relOpt);
else
(void) ReleaseVolumeBlock(vcb, &block, relOpt | kSkipEndianSwap);
}
return (0);
}
void UpdateFreeBlockCount(SGlobPtr g)
{
int i;
UInt32 newBitsMarked = 0;
UInt32 bit;
UInt32 *buffer;
UInt32 curWord;
SVCB * vcb = g->calculatedVCB;
for (bit = 0; bit < gTotalBits; bit += kBitsPerSegment) {
(void) GetSegmentBitmap(bit, &buffer, kTestingBits);
if (buffer == gFullBitmapSegment) {
newBitsMarked += kBitsPerSegment;
continue;
}
if (buffer == gEmptyBitmapSegment) {
continue;
}
for (i = 0; i < kWordsPerSegment; i++) {
if (buffer[i] == kAllBitsSetInWord) {
newBitsMarked += kBitsPerWord;
} else {
curWord = SWAP_BE32(buffer[i]);
while (curWord) {
newBitsMarked += curWord & 1;
curWord >>= 1;
}
}
}
}
if (gBitsMarked != newBitsMarked) {
gBitsMarked = newBitsMarked;
}
if (vcb->vcbFreeBlocks != (vcb->vcbTotalBlocks - gBitsMarked)) {
vcb->vcbFreeBlocks = vcb->vcbTotalBlocks - gBitsMarked;
MarkVCBDirty(vcb);
}
}
static int FindContigClearedBitmapBits (SVCB *vcb, UInt32 numBlocks, UInt32 *actualStartBlock)
{
int i, j;
int retval = ENOSPC;
UInt32 bit;
UInt32 *buffer;
UInt32 curWord;
UInt32 validBitsInSegment;
UInt32 validBitsInWord;
UInt32 bitsRemain = numBlocks;
UInt32 startBlock = 0;
validBitsInSegment = kBitsPerSegment;
validBitsInWord = kBitsPerWord;
for (bit = 0; bit < gTotalBits; bit += kBitsPerSegment) {
(void) GetSegmentBitmap(bit, &buffer, kTestingBits);
if ((gTotalBits - bit) < kBitsPerSegment) {
validBitsInSegment = gTotalBits - bit;
}
if (buffer == gFullBitmapSegment) {
startBlock = 0;
bitsRemain = numBlocks;
continue;
}
if (buffer == gEmptyBitmapSegment) {
if (bitsRemain == numBlocks) {
startBlock = bit;
}
if (bitsRemain > validBitsInSegment) {
bitsRemain -= validBitsInSegment;
continue;
} else {
bitsRemain = 0;
break;
}
}
for (i = 0; i < kWordsPerSegment; i++) {
if (buffer[i] == kAllBitsSetInWord) {
startBlock = 0;
bitsRemain = numBlocks;
} else {
if (validBitsInSegment != kBitsPerSegment) {
if ((validBitsInSegment - (i * kBitsPerWord)) < kBitsPerWord) {
validBitsInWord = validBitsInSegment - (i * kBitsPerWord);
}
}
curWord = SWAP_BE32(buffer[i]);
for (j = 0; j < validBitsInWord; j++) {
if (curWord & kMSBBitSetInWord) {
startBlock = 0;
bitsRemain = numBlocks;
} else {
if (bitsRemain == numBlocks) {
startBlock = bit + (i * kBitsPerWord) + j;
}
bitsRemain--;
if (bitsRemain == 0) {
goto out;
}
}
curWord <<= 1;
}
if (validBitsInWord != kBitsPerWord) {
goto out;
}
}
}
}
out:
if (bitsRemain == 0) {
*actualStartBlock = startBlock;
retval = 0;
} else {
*actualStartBlock = 0;
}
return retval;
}
int AllocateContigBitmapBits (SVCB *vcb, UInt32 numBlocks, UInt32 *actualStartBlock)
{
int error;
error = FindContigClearedBitmapBits (vcb, numBlocks, actualStartBlock);
if (error == noErr) {
error = CaptureBitmapBits (*actualStartBlock, numBlocks);
}
return error;
}
enum { kMaxTrimExtents = 256 };
dk_extent_t gTrimExtents[kMaxTrimExtents];
dk_unmap_t gTrimData;
static void TrimInit(void)
{
bzero(&gTrimData, sizeof(gTrimData));
gTrimData.extents = gTrimExtents;
}
static void TrimFlush(void)
{
int err;
if (gTrimData.extentsCount == 0)
{
DPRINTF(d_info|d_trim, "TrimFlush: nothing to flush\n");
return;
}
err = ioctl(fsreadfd, DKIOCUNMAP, &gTrimData);
if (err == -1)
{
DPRINTF(d_error|d_trim, "TrimFlush: error %d\n", errno);
}
gTrimData.extentsCount = 0;
}
static void TrimExtent(SGlobPtr g, UInt32 startBlock, UInt32 blockCount)
{
UInt64 offset;
UInt64 length;
DPRINTF(d_info|d_trim, "Trimming: startBlock=%10u, blockCount=%10u\n", startBlock, blockCount);
offset = (UInt64) startBlock * g->calculatedVCB->vcbBlockSize;
if (VolumeObjectIsHFSPlus())
offset += g->calculatedVCB->vcbEmbeddedOffset;
else
offset += g->calculatedVCB->vcbAlBlSt * 512ULL;
length = (UInt64) blockCount * g->calculatedVCB->vcbBlockSize;
gTrimExtents[gTrimData.extentsCount].offset = offset;
gTrimExtents[gTrimData.extentsCount].length = length;
if (++gTrimData.extentsCount == kMaxTrimExtents)
TrimFlush();
}
void TrimFreeBlocks(SGlobPtr g)
{
UInt32 *buffer;
UInt32 bit;
UInt32 wordWithinSegment;
UInt32 bitWithinWordMask;
UInt32 currentWord;
UInt32 startBlock;
UInt32 blockCount;
UInt32 totalTrimmed = 0;
TrimInit();
startBlock = 0;
blockCount = 0;
for (bit = 0; bit < gTotalBits; ) {
assert((bit % kBitsPerSegment) == 0);
(void) GetSegmentBitmap(bit, &buffer, kTestingBits);
if (buffer == gFullBitmapSegment) {
if (blockCount != 0) {
TrimExtent(g, startBlock, blockCount);
totalTrimmed += blockCount;
blockCount = 0;
}
bit += kBitsPerSegment;
continue;
}
if (buffer == gEmptyBitmapSegment) {
if (blockCount == 0) {
startBlock = bit;
}
if (gTotalBits - bit < kBitsPerSegment) {
blockCount += gTotalBits - bit;
} else {
blockCount += kBitsPerSegment;
}
bit += kBitsPerSegment;
continue;
}
for (wordWithinSegment = 0;
wordWithinSegment < kWordsPerSegment && bit < gTotalBits;
++wordWithinSegment)
{
assert((bit % kBitsPerWord) == 0);
currentWord = SWAP_BE32(buffer[wordWithinSegment]);
for (bitWithinWordMask = kMSBBitSetInWord;
bitWithinWordMask != 0 && bit < gTotalBits;
++bit, bitWithinWordMask >>= 1)
{
if (currentWord & bitWithinWordMask) {
if (blockCount != 0) {
TrimExtent(g, startBlock, blockCount);
totalTrimmed += blockCount;
blockCount = 0;
}
} else {
if (blockCount == 0) {
startBlock = bit;
}
++blockCount;
}
}
}
}
if (blockCount != 0) {
TrimExtent(g, startBlock, blockCount);
totalTrimmed += blockCount;
blockCount = 0;
}
TrimFlush();
DPRINTF(d_info|d_trim, "Trimmed %u allocation blocks.\n", totalTrimmed);
}
int IsTrimSupported(void)
{
int err;
uint32_t features = 0;
err = ioctl(fsreadfd, DKIOCGETFEATURES, &features);
if (err < 0)
{
return 0;
}
return features & DK_FEATURE_UNMAP;
}
static int
BMS_InitTree(void)
{
gBMS_PoolCount = 0;
BMS_GrowNodePool();
gBMS_Root = gBMS_FreeNodes;
gBMS_FreeNodes = gBMS_FreeNodes->right;
gBMS_Root->right = NULL;
return (0);
}
static int
BMS_DisposeTree(void)
{
while(gBMS_PoolCount > 0)
free(gBMS_PoolList[--gBMS_PoolCount]);
gBMS_Root = gBMS_FreeNodes = 0;
return (0);
}
static BMS_Node *
BMS_Lookup(UInt32 segment)
{
BMS_Node *ptree = gBMS_Root;
while (ptree && ptree->segment != segment) {
if (segment > ptree->segment)
ptree = ptree->right;
else
ptree = ptree->left;
}
return ((BMS_Node *)ptree);
}
static BMS_Node *
BMS_InsertTree(BMS_Node *NewEntry)
{
BMS_Node *ptree;
register UInt32 segment;
segment = NewEntry->segment;
ptree = gBMS_Root;
if (ptree == (BMS_Node *)NULL) {
*ptree = *NewEntry;
return (NewEntry);
}
while (ptree) {
if (segment > ptree->segment) {
if (ptree->right)
ptree = ptree->right;
else {
ptree->right = NewEntry;
return (ptree);
}
}
else {
if (ptree->left)
ptree = ptree->left;
else {
ptree->left = NewEntry;
return (ptree);
}
}
}
return ((BMS_Node *)NULL);
}
static BMS_Node *
BMS_Insert(UInt32 segment, int segmentType)
{
BMS_Node *new;
if ((new = gBMS_FreeNodes) == NULL) {
BMS_GrowNodePool();
if ((new = gBMS_FreeNodes) == NULL)
return ((BMS_Node *)NULL);
}
gBMS_FreeNodes = gBMS_FreeNodes->right;
++gSegmentNodes;
new->right = NULL;
new->segment = segment;
if (segmentType == kFullSegment)
bcopy(gFullBitmapSegment, new->bitmap, kBytesPerSegment);
else
bzero(new->bitmap, sizeof(new->bitmap));
if (BMS_InsertTree(new) != NULL)
return (new);
else
return ((BMS_Node *)NULL);
}
static BMS_Node *
BMS_Delete(UInt32 segment)
{
BMS_Node *seg_found, *pprevious, *pnext, *pnextl, *psub;
pprevious = NULL;
seg_found = gBMS_Root;
if (seg_found->segment == segment)
return ((BMS_Node *)NULL);
while (seg_found && seg_found->segment != segment) {
pprevious = seg_found;
if (segment > seg_found->segment)
seg_found = seg_found->right;
else
seg_found = seg_found->left;
}
if (seg_found) {
if ((pnext = seg_found->right)) {
psub = pnext;
while ((pnextl = psub->left))
psub = pnextl;
psub->left = seg_found->left;
} else {
pnext = seg_found->left;
}
if (pprevious->left == seg_found)
pprevious->left = pnext;
else
pprevious->right = pnext;
bzero(seg_found, sizeof(BMS_Node));
seg_found->right = gBMS_FreeNodes;
gBMS_FreeNodes = seg_found;
}
return (seg_found);
}
static void
BMS_GrowNodePool(void)
{
BMS_Node *nodePool;
short i;
if (gBMS_PoolCount > kBMS_PoolMax)
return;
nodePool = (BMS_Node *)malloc(sizeof(BMS_Node) * kBMS_NodesPerPool);
if (nodePool != NULL) {
bzero(&nodePool[0], sizeof(BMS_Node) * kBMS_NodesPerPool);
for (i = 1 ; i < kBMS_NodesPerPool ; i++) {
(&nodePool[i-1])->right = &nodePool[i];
}
gBMS_FreeNodes = &nodePool[0];
gBMS_PoolList[gBMS_PoolCount++] = nodePool;
}
}
#if _VBC_DEBUG_
static void
BMS_MaxDepth(BMS_Node * root, int depth, int *maxdepth)
{
if (root) {
depth++;
if (depth > *maxdepth)
*maxdepth = depth;
BMS_MaxDepth(root->left, depth, maxdepth);
BMS_MaxDepth(root->right, depth, maxdepth);
}
}
static void
BMS_PrintTree(BMS_Node * root)
{
if (root) {
BMS_PrintTree(root->left);
plog("seg %d\n", root->segment);
BMS_PrintTree(root->right);
}
}
#endif