/*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2004 Apple Computer, 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: BTree.c
*/
#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;
}
}
- // if nodeSize Matches then we don't need to release, just CheckNode
- if ( btreePtr->nodeSize == nodeRec.blockSize )
- {
- err = CheckNode (btreePtr, nodeRec.buffer);
- if (err)
- VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
- M_ExitOnError (err);
- }
- else
+ /*
+ * If the actual node size is different than the amount we read,
+ * then release and trash this block, and re-read with the correct
+ * node size.
+ */
+ if ( btreePtr->nodeSize != nodeRec.blockSize )
{
- 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 = GetNode (btreePtr, kHeaderNodeNum, &nodeRec ); // calls CheckNode...
+ err = GetNode (btreePtr, kHeaderNodeNum, &nodeRec );
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;
}
while (err == 0) {
- if (callBackProc(keyPtr, recordPtr, len, callBackState) == 0)
+ if (callBackProc(keyPtr, recordPtr, callBackState) == 0)
break;
if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
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;
goto ErrorExit;
}
- err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
- M_ExitOnError (err);
-
- // update BTreeControlBlock
+ /*
+ * Update the B-tree control block. Do this before
+ * calling UpdateNode since it will compare the node's
+ * height with treeDepth.
+ */
btreePtr->treeDepth = 1;
btreePtr->rootNode = insertNodeNum;
btreePtr->firstLeafNode = insertNodeNum;
btreePtr->lastLeafNode = insertNodeNum;
+
+ err = UpdateNode (btreePtr, &nodeRec, 0, kLockTransaction);
+ M_ExitOnError (err);
+
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;
- REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
////////////////////////////// Take A Hint //////////////////////////////////
err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
M_ExitOnError (err);
- err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
+ err = callBackProc(keyPtr, recordPtr, callBackState);
M_ExitOnError (err);
err = UpdateNode (btreePtr, &nodeRec, 0, 0);
err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
M_ExitOnError (err);
- err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+
+ err = callBackProc(keyPtr, recordPtr, callBackState);
M_ExitOnError (err);
err = UpdateNode (btreePtr, &nodeRec, 0, 0);
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.
M_ReturnErrorIf (btreePtr == nil, fsBTInvalidFileErr);
- REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+ REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
err = UpdateHeader (btreePtr, false);
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