VolumeBitmapCheck.c [plain text]
#include "Scavenger.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 0xFFFFFFFFul
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 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)
{
if (gBitMapInited)
return (0);
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 (g->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);
printf(" %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_
printf("GetSegmentBitmap: couldn't get a node for block %d, segment %d\n", startBit, segment);
#endif
return (-1);
}
#if 0
if (segNode) {
int i;
printf(" segment %d: L=0x%08x, R=0x%08x \n< ",
(int)segNode->segment, (int)segNode->left, segNode->right);
for (i = 0; i < kWordsPerSegment; ++i) {
printf("0x%08x ", segNode->bitmap[i]);
if ((i & 0x3) == 0x3)
printf("\n ");
}
printf("\n");
}
if (bitOperation == kSettingBits && *buffer && bcmp(*buffer, gFullBitmapSegment, kBytesPerSegment) == 0) {
printf("*** segment %d (start blk %d) is already full!\n", segment, startBit);
exit(5);
}
if (bitOperation == kClearingBits && *buffer && bcmp(*buffer, gEmptyBitmapSegment, kBytesPerSegment) == 0) {
printf("*** 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;
printf("> ");
for (i = 0; i < kWordsPerSegment; ++i) {
printf("0x%08x ", segNode->bitmap[i]);
if ((i & 0x3) == 0x3)
printf("\n ");
}
printf("\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 (*currentWord & bitMask) {
overlap = true;
}
*currentWord |= 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 (*currentWord & bitMask) {
overlap = true;
}
*currentWord |= 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 (*currentWord & bitMask) {
overlap = true;
}
*currentWord |= 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 ((*currentWord & bitMask) != bitMask) {
overlap = true;
}
*currentWord &= ~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 ((*currentWord & bitMask) != bitMask) {
overlap = true;
}
*currentWord &= ~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 ((*currentWord & bitMask) != bitMask) {
overlap = true;
}
*currentWord &= ~bitMask;
TestSegmentBitmap(startBit);
}
Exit:
return (overlap ? E_OvlExt : err);
}
int
CheckVolumeBitMap(SGlobPtr g, Boolean repair)
{
UInt8 *vbmBlockP;
UInt32 *buffer;
UInt32 bit;
UInt32 bitsWithinFileBlkMask;
UInt32 fileBlk;
BlockDescriptor block;
ReleaseBlockOptions relOpt;
SFCB * fcb;
SVCB * vcb;
int err = 0;
vcb = g->calculatedVCB;
fcb = g->calculatedAllocationsFCB;
if ( vcb->vcbFreeBlocks != (vcb->vcbTotalBlocks - gBitsMarked) ) {
vcb->vcbFreeBlocks = vcb->vcbTotalBlocks - gBitsMarked;
MarkVCBDirty(vcb);
}
vbmBlockP = (UInt8 *)NULL;
block.buffer = (void *)NULL;
relOpt = kReleaseBlock;
if ( g->isHFSPlus )
bitsWithinFileBlkMask = (fcb->fcbBlockSize * 8) - 1;
else
bitsWithinFileBlkMask = (kHFSBlockSize * 8) - 1;
fileBlk = (g->isHFSPlus ? 0 : vcb->vcbVBMSt);
for (bit = 0; bit < gTotalBits; bit += kBitsPerSegment) {
(void) GetSegmentBitmap(bit, &buffer, kTestingBits);
if ((bit & bitsWithinFileBlkMask) == 0) {
if (g->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);
ReturnIfError(err);
}
err = GetVolumeBlock(vcb, fileBlk, kGetBlock, &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 {
#if _VBC_DEBUG_
int i;
printf(" disk buffer + %d\n", (bit & bitsWithinFileBlkMask)/8);
printf(" segment %d\nM ", bit / kBitsPerSegment);
for (i = 0; i < kWordsPerSegment; ++i) {
printf("0x%08x ", buffer[i]);
if ((i & 0x7) == 0x7)
printf("\n ");
}
buffer = (UInt32*) (vbmBlockP + (bit & bitsWithinFileBlkMask)/8);
printf("\nD ");
for (i = 0; i < kWordsPerSegment; ++i) {
printf("0x%08x ", buffer[i]);
if ((i & 0x7) == 0x7)
printf("\n ");
}
#endif
PrintError(g, E_VBMDamaged, 0);
g->VIStat = g->VIStat | S_VBM;
break;
}
++g->itemsProcessed;
}
if (block.buffer) {
if (g->isHFSPlus)
(void) ReleaseFileBlock(fcb, &block, relOpt);
else
(void) ReleaseVolumeBlock(vcb, &block, relOpt);
}
return (0);
}
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);
printf("seg %d\n", root->segment);
BMS_PrintTree(root->right);
}
}
#endif