/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
*/
#define kNumLeafRecSlack 10
+/* BTree accessor routines */
+extern OSStatus GetBTreeBlock(FileReference vp, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block);
+extern OSStatus SetBTreeBlockSize(FileReference vp, ByteCount blockSize, ItemCount minBlockCount);
+extern OSStatus ExtendBTreeFile(FileReference vp, FSSize minEOF, FSSize maxEOF);
+extern OSStatus ReleaseBTreeBlock(FileReference vp, BlockDescPtr blockPtr, ReleaseBlockOptions options);
+
//////////////////////////////////// Globals ////////////////////////////////////
Input: filePtr - pointer to file to open as a B-tree
keyCompareProc - pointer to client's KeyCompare function
- getBlockProc - pointer to client's GetBlock function
- releaseBlockProc - pointer to client's ReleaseBlock function
- setEndOfForkProc - pointer to client's SetEOF function
Result: noErr - success
paramErr - required ptr was nil
!= noErr - failure
-------------------------------------------------------------------------------*/
-OSStatus BTOpenPath (FCB *filePtr,
- KeyCompareProcPtr keyCompareProc,
- GetBlockProcPtr getBlockProc,
- ReleaseBlockProcPtr releaseBlockProc,
- SetEndOfForkProcPtr setEndOfForkProc,
- SetBlockSizeProcPtr setBlockSizeProc )
+OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc)
{
OSStatus err;
BTreeControlBlockPtr btreePtr;
////////////////////// Preliminary Error Checking ///////////////////////////
- if ( filePtr == nil ||
- getBlockProc == nil ||
- releaseBlockProc == nil ||
- setEndOfForkProc == nil ||
- setBlockSizeProc == nil )
+ if ( filePtr == nil )
{
return paramErr;
}
- if ( filePtr->fcbBTCBPtr != nil ) // already has a BTreeCB
+ /*
+ * Subsequent opens allow key compare proc to be changed.
+ */
+ if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) {
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ btreePtr->keyCompareProc = keyCompareProc;
return noErr;
+ }
- // is file large enough to contain header node?
if ( filePtr->fcbEOF < kMinNodeSize )
- return fsBTInvalidFileErr; //\80\80 or E_BadHeader?
+ return fsBTInvalidFileErr;
//////////////////////// Allocate Control Block /////////////////////////////
return memFullErr;
}
- btreePtr->getBlockProc = getBlockProc;
- btreePtr->releaseBlockProc = releaseBlockProc;
- btreePtr->setEndOfForkProc = setEndOfForkProc;
+ btreePtr->getBlockProc = GetBTreeBlock;
+ btreePtr->releaseBlockProc = ReleaseBTreeBlock;
+ btreePtr->setEndOfForkProc = ExtendBTreeFile;
btreePtr->keyCompareProc = keyCompareProc;
/////////////////////////// Read Header Node ////////////////////////////////
/* The minimum node size is the physical block size */
nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
+ /* Start with the allocation block size for regular files. */
+ if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+ {
+ nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize;
+ }
REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
// it is now safe to call M_ExitOnError (err)
- err = setBlockSizeProc (btreePtr->fileRefNum, nodeRec.blockSize, 1);
+ err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1);
M_ExitOnError (err);
- err = getBlockProc (btreePtr->fileRefNum,
+ err = GetBTreeBlock(btreePtr->fileRefNum,
kHeaderNodeNum,
kGetBlock,
&nodeRec );
btreePtr->maxKeyLength = header->maxKeyLength;
btreePtr->totalNodes = header->totalNodes;
btreePtr->freeNodes = header->freeNodes;
- // ignore header->clumpSize; //\80\80 rename this field?
+ if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+ filePtr->ff_clumpsize = header->clumpSize;
btreePtr->btreeType = header->btreeType;
+ btreePtr->keyCompareType = header->keyCompareType;
+
btreePtr->attributes = header->attributes;
if ( btreePtr->maxKeyLength > 40 )
* we cannot mount using the current physical block size.
*/
if (btreePtr->leafRecords > 0 ||
- VTOHFS(btreePtr->fileRefNum)->hfs_media_writeable)
+ VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)
{
err = fsBTBadNodeSize;
goto ErrorExit;
}
else
{
- err = setBlockSizeProc (btreePtr->fileRefNum, btreePtr->nodeSize, 32); //\80\80 we should try and get this down to 8
+ err = SetBTreeBlockSize (btreePtr->fileRefNum, btreePtr->nodeSize, 32);
M_ExitOnError (err);
/*
* Need to use kTrashBlock option to force the
* buffer cache to read the entire node
*/
- err = releaseBlockProc(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
+ err = ReleaseBTreeBlock(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
++btreePtr->numReleaseNodes;
M_ExitOnError (err);
err = ReleaseNode (btreePtr, &nodeRec);
M_ExitOnError (err);
+ /*
+ * Under Mac OS, b-tree nodes can be non-contiguous on disk when the
+ * allocation block size is smaller than the b-tree node size.
+ *
+ * If journaling is turned on for this volume we can't deal with this
+ * situation and so we bail out. If journaling isn't on it's ok as
+ * hfs_strategy_fragmented() deals with it. Journaling can't support
+ * this because it assumes that if you give it a block that it's
+ * contiguous on disk.
+ */
+ if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) {
+ return fsBTInvalidNodeErr;
+ }
+
//////////////////////////////// Success ////////////////////////////////////
//\80\80 align LEOF to multiple of node size? - just on close
if (filePtr == nil) return paramErr;
if (searchIterator == nil) return paramErr;
+ node.buffer = nil;
+ node.blockHeader = nil;
+
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil) return fsBTInvalidFileErr;
////////////////////////// Priliminary Checks ///////////////////////////////
- left.buffer = nil;
- right.buffer = nil;
- node.buffer = nil;
+ left.buffer = nil;
+ left.blockHeader = nil;
+ right.buffer = nil;
+ right.blockHeader = nil;
+ node.buffer = nil;
+ node.blockHeader = nil;
if (filePtr == nil)
////////////////////////// Priliminary Checks ///////////////////////////////
- left.buffer = nil;
- right.buffer = nil;
- node.buffer = nil;
+ left.buffer = nil;
+ left.blockHeader = nil;
+ right.buffer = nil;
+ right.blockHeader = nil;
+ node.buffer = nil;
+ node.blockHeader = nil;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
UInt16 index;
Boolean recordFit;
-
////////////////////////// Priliminary Checks ///////////////////////////////
nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
case fsBTEmptyErr: // if tree empty add 1st leaf node
- if (btreePtr->freeNodes == 0)
+ if (BTAvailableNodes(btreePtr) == 0)
{
err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
M_ExitOnError (err);
err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
M_ExitOnError (err);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
((NodeDescPtr)nodeRec.buffer)->height = 1;
btreePtr->rootNode = insertNodeNum;
btreePtr->firstLeafNode = insertNodeNum;
btreePtr->lastLeafNode = insertNodeNum;
+
M_BTreeHeaderDirty (btreePtr);
goto Success;
if (index > 0)
{
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
&iterator->key, KeyLength(btreePtr, &iterator->key),
record->bufferAddress, recordLen);
/////////////////////// Extend File If Necessary ////////////////////////////
- nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //\80\80 math limit
+ nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
if (nodesNeeded > 0)
{
- nodesNeeded += btreePtr->totalNodes;
+ nodesNeeded += (SInt32)btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
++nodesNeeded;
++btreePtr->writeCount;
++btreePtr->leafRecords;
M_BTreeHeaderDirty (btreePtr);
-
+
// create hint
iterator->hint.writeCount = btreePtr->writeCount;
iterator->hint.nodeNum = insertNodeNum;
////////////////////////// Priliminary Checks ///////////////////////////////
nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
err = CheckInsertParams (filePtr, iterator, record, recordLen);
if (err != noErr)
err = GetNode (btreePtr, insertNodeNum, &nodeRec);
if( err == noErr )
{
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
// optimization - if simple replace will work then don't extend btree
// \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
M_ExitOnError (err);
//////////////////////////// Make Some Room /////////////////////////////////
- nodesNeeded = btreePtr->treeDepth + 1 - btreePtr->freeNodes; //\80\80 math limit
+ nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
if (nodesNeeded > 0)
{
- nodesNeeded += btreePtr->totalNodes;
+ nodesNeeded += (SInt32)btreePtr->totalNodes;
if (nodesNeeded > CalcMapBits (btreePtr)) // we'll need to add a map node too!
++nodesNeeded;
M_ExitOnError (err);
}
-
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
////////////////////////// Priliminary Checks ///////////////////////////////
nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
M_ExitOnError (err);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
M_ExitOnError (err);
err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
M_ExitOnError (err);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
M_ExitOnError (err);
BTreeControlBlockPtr btreePtr;
TreePathTable treePathTable;
BlockDescriptor nodeRec;
+ SInt32 nodesNeeded;
UInt32 nodeNum;
UInt16 index;
////////////////////////// Priliminary Checks ///////////////////////////////
nodeRec.buffer = nil; // so we can call ReleaseNode
+ nodeRec.blockHeader = nil;
M_ReturnErrorIf (filePtr == nil, paramErr);
M_ReturnErrorIf (iterator == nil, paramErr);
M_ExitOnError (err); // record must exit for Delete
+ /////////////////////// Extend File If Necessary ////////////////////////////
+
+ nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
+ if ((btreePtr->attributes & kBTVariableIndexKeysMask) && (nodesNeeded > 0))
+ {
+ nodesNeeded += (SInt32)btreePtr->totalNodes;
+ if (nodesNeeded > CalcMapBits (btreePtr))
+ ++nodesNeeded;
+
+ err = ExtendBTree (btreePtr, nodesNeeded);
+ M_ExitOnError (err);
+ }
+
///////////////////////////// Delete Record /////////////////////////////////
err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
++btreePtr->writeCount;
--btreePtr->leafRecords;
M_BTreeHeaderDirty (btreePtr);
-
+
iterator->hint.nodeNum = 0;
return noErr;
info->numNodes = btreePtr->totalNodes;
info->numFreeNodes = btreePtr->freeNodes;
info->lastfsync = btreePtr->lastfsync;
- info->reserved = 0;
-
+ info->keyCompareType = btreePtr->keyCompareType;
return noErr;
}
+// XXXdbg
+__private_extern__
+OSStatus
+BTIsDirty(FCB *filePtr)
+{
+ BTreeControlBlockPtr btreePtr;
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ return TreeIsDirty(btreePtr);
+}
/*-------------------------------------------------------------------------------
Routine: BTFlushPath - Flush BTreeControlBlock to Header Node.
BTHeaderRec *header;
+ node.buffer = nil;
+ node.blockHeader = nil;
+
btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
if (btreePtr == nil)
return (fsBTInvalidFileErr);
}
+__private_extern__
+OSStatus BTHasContiguousNodes (FCB *filePtr)
+{
+ BTreeControlBlockPtr btreePtr;
+
+
+ M_ReturnErrorIf (filePtr == nil, paramErr);
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+ M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
+
+ return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine: BTGetUserData
+
+Function: Read the user data area of the b-tree header node.
+
+-------------------------------------------------------------------------------*/
+__private_extern__
+OSStatus
+BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize)
+{
+ BTreeControlBlockPtr btreePtr;
+ BlockDescriptor node;
+ char * offset;
+ OSStatus err;
+
+ if (dataSize > kBTreeHeaderUserBytes)
+ return (EINVAL);
+ node.buffer = nil;
+ node.blockHeader = nil;
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ if (btreePtr == nil)
+ return (fsBTInvalidFileErr);
+
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+ err = GetNode(btreePtr, kHeaderNodeNum, &node);
+ if (err)
+ return (err);
+
+ offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+ bcopy(offset, dataPtr, dataSize);
+
+ (void) ReleaseNode(btreePtr, &node);
+
+ return (0);
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine: BTSetUserData
+
+Function: Write the user data area of the b-tree header node.
+-------------------------------------------------------------------------------*/
+__private_extern__
+OSStatus
+BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize)
+{
+ BTreeControlBlockPtr btreePtr;
+ BlockDescriptor node;
+ char * offset;
+ OSStatus err;
+
+ if (dataSize > kBTreeHeaderUserBytes)
+ return (EINVAL);
+ node.buffer = nil;
+ node.blockHeader = nil;
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ if (btreePtr == nil)
+ return (fsBTInvalidFileErr);
+
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+ err = GetNode(btreePtr, kHeaderNodeNum, &node);
+ if (err)
+ return (err);
+
+ ModifyBlockStart(btreePtr->fileRefNum, &node);
+
+ offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+ bcopy(dataPtr, offset, dataSize);
+
+ err = UpdateNode (btreePtr, &node, 0, 0);
+
+ return (err);
+}
+
projects / apple / xnu.git / blobdiff