X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/d52fe63fc81f7e44faaae711812a211a78434976..3a60a9f5b85abb8c2cf24e1926c5c7b3f608a5e2:/bsd/hfs/hfscommon/BTree/BTree.c

diff --git a/bsd/hfs/hfscommon/BTree/BTree.c b/bsd/hfs/hfscommon/BTree/BTree.c
index 1cd262eef..9920c8742 100644
--- a/bsd/hfs/hfscommon/BTree/BTree.c
+++ b/bsd/hfs/hfscommon/BTree/BTree.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
  *
  * @APPLE_LICENSE_HEADER_START@
  * 
@@ -146,14 +146,18 @@
 
 #include "../headers/BTreesPrivate.h"
 
-#include "../headers/HFSInstrumentation.h"
-
 /* 
  * The amount that the BTree header leaf count can be wrong before we assume
  * it is in an infinite loop.
  */
 #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 ////////////////////////////////////
 
 
@@ -170,9 +174,6 @@ Function:	Create BTree control block for a file, if necessary. Validates the
 
 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
@@ -181,37 +182,31 @@ Result:		noErr				- success
 			!= 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;
 	BTHeaderRec				*header;
 	NodeRec					nodeRec;
 
-	LogStartTime(kTraceOpenBTree);
-
 	////////////////////// 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;							//€€ or E_BadHeader?
+		return fsBTInvalidFileErr;
 
 
 	//////////////////////// Allocate Control Block /////////////////////////////
@@ -223,9 +218,9 @@ OSStatus	BTOpenPath			(FCB					*filePtr,
 		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 ////////////////////////////////
@@ -237,15 +232,20 @@ OSStatus	BTOpenPath			(FCB					*filePtr,
 	/* 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 );
@@ -256,7 +256,7 @@ OSStatus	BTOpenPath			(FCB					*filePtr,
 		Panic("\pBTOpen: getNodeProc returned error getting header node.");
 		goto ErrorExit;
 	}
-
+	++btreePtr->numGetNodes;
 	header = (BTHeaderRec*) ((u_long)nodeRec.buffer + sizeof(BTNodeDescriptor));
 
 
@@ -279,9 +279,12 @@ OSStatus	BTOpenPath			(FCB					*filePtr,
 	btreePtr->maxKeyLength		= header->maxKeyLength;
 	btreePtr->totalNodes		= header->totalNodes;
 	btreePtr->freeNodes			= header->freeNodes;
-	// ignore					  header->clumpSize;	//€€ 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 )
@@ -293,40 +296,44 @@ OSStatus	BTOpenPath			(FCB					*filePtr,
 	btreePtr->flags				= 0;
 	btreePtr->writeCount		= 1;
 
-	btreePtr->numGetNodes		= 1;		// for earlier call to getNodeProc
-
 	/////////////////////////// Check Header Node ///////////////////////////////
 
-	//€€ set kBadClose attribute bit, and UpdateNode
-
-	// if nodeSize matches then we don't need to release, just CheckNode
+	// set kBadClose attribute bit, and UpdateNode
 
 	/* b-tree node size must be at least as big as the physical block size */
-	if (btreePtr->nodeSize < nodeRec.blockSize) {
-		err = fsBTBadNodeSize;
-		goto ErrorExit;
-	}
-
-	if ( btreePtr->nodeSize == nodeRec.blockSize )
+	if (btreePtr->nodeSize < nodeRec.blockSize)
 	{
-		err = CheckNode (btreePtr, nodeRec.buffer);
-		if (err)
-			VTOVCB(btreePtr->fileRefNum)->vcbFlags |= kHFS_DamagedVolume;
-		M_ExitOnError (err);
+		/*
+		 * If this tree has any records or the media is writeable then
+		 * we cannot mount using the current physical block size.
+		 */
+		if (btreePtr->leafRecords > 0 ||
+		    VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)		
+		{
+			err = fsBTBadNodeSize;
+			goto ErrorExit;
+		}
 	}
-	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);	//€€ 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);
 	}
 
@@ -339,16 +346,21 @@ OSStatus	BTOpenPath			(FCB					*filePtr,
 	/*
 	 * 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 ( !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) )
+	if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) {
 		return fsBTInvalidNodeErr;
+	}
 
 	//////////////////////////////// Success ////////////////////////////////////
 
 	//€€ align LEOF to multiple of node size?	- just on close
 
-	LogEndTime(kTraceOpenBTree, noErr);
-
 	return noErr;
 
 
@@ -360,8 +372,6 @@ ErrorExit:
 	(void) ReleaseNode (btreePtr, &nodeRec);
 	DisposePtr( (Ptr) btreePtr );
 
-	LogEndTime(kTraceOpenBTree, err);
-
 	return err;
 }
 
@@ -387,8 +397,6 @@ OSStatus	BTClosePath			(FCB					*filePtr)
 	OSStatus				err;
 	BTreeControlBlockPtr	btreePtr;
 
-	LogStartTime(kTraceCloseBTree);
-
 	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
 	if (btreePtr == nil)
@@ -405,16 +413,12 @@ OSStatus	BTClosePath			(FCB					*filePtr)
 	DisposePtr( (Ptr) btreePtr );
 	filePtr->fcbBTCBPtr = nil;
 
-	LogEndTime(kTraceCloseBTree, noErr);
-
 	return	noErr;
 
 	/////////////////////// Error - Clean Up and Exit ///////////////////////////
 
 ErrorExit:
 
-	LogEndTime(kTraceCloseBTree, err);
-
 	return	err;
 }
 
@@ -451,7 +455,6 @@ Result:		noErr			- success, record contains copy of record found
 
 OSStatus	BTSearchRecord		(FCB						*filePtr,
 								 BTreeIterator				*searchIterator,
-								 UInt32						heuristicHint,
 								 FSBufferDescriptor			*record,
 								 UInt16						*recordLen,
 								 BTreeIterator				*resultIterator )
@@ -468,12 +471,12 @@ OSStatus	BTSearchRecord		(FCB						*filePtr,
 	Boolean					foundRecord;
 	Boolean					validHint;
 
-
-	LogStartTime(kTraceSearchBTree);
-
 	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;
 
@@ -516,30 +519,6 @@ OSStatus	BTSearchRecord		(FCB						*filePtr,
 			(void) BTInvalidateHint( searchIterator );
 	}
 
-	////////////////////////////// Try the heuristicHint //////////////////////////////////
-
-	if ( (foundRecord == false) && (heuristicHint != kInvalidMRUCacheKey) && (nodeNum != heuristicHint) )
-	{
-		LogStartTime(kHeuristicHint);
-		nodeNum = heuristicHint;
-		
-		err = GetNode (btreePtr, nodeNum, &node);
-		if( err == noErr )
-		{
-			if ( ((BTNodeDescriptor*) node.buffer)->kind == kBTLeafNode &&
-				 ((BTNodeDescriptor*) node.buffer)->numRecords	>  0 )
-			{
-				foundRecord = SearchNode (btreePtr, node.buffer, &searchIterator->key, &index);
-			}
-
-			if (foundRecord == false)
-			{
-				err = ReleaseNode (btreePtr, &node);
-				M_ExitOnError (err);
-			}
-		}
-		LogEndTime(kHeuristicHint, (foundRecord == false));
-	}
 
 	//////////////////////////// Search The Tree ////////////////////////////////
 
@@ -600,8 +579,6 @@ OSStatus	BTSearchRecord		(FCB						*filePtr,
 	err = ReleaseNode (btreePtr, &node);
 	M_ExitOnError (err);
 
-	LogEndTime(kTraceSearchBTree, (foundRecord == false));
-
 	if (foundRecord == false)	return	fsBTRecordNotFoundErr;
 	else						return	noErr;
 
@@ -629,8 +606,6 @@ ErrorExit:
 	if ( err == fsBTEmptyErr )
 		err = fsBTRecordNotFoundErr;
 
-	LogEndTime(kTraceSearchBTree, err);
-
 	return err;
 }
 
@@ -673,13 +648,14 @@ OSStatus	BTIterateRecord		(FCB						*filePtr,
 	UInt16						index;
 
 
-	LogStartTime(kTraceGetBTreeRecord);
-
 	////////////////////////// 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)
@@ -909,8 +885,6 @@ CopyData:
 		M_ExitOnError (err);
 	}
 
-	LogEndTime(kTraceGetBTreeRecord, noErr);
-
 	return noErr;
 
 	/////////////////////// Error - Clean Up and Exit ///////////////////////////
@@ -940,8 +914,6 @@ ErrorExit:
 	if ( err == fsBTEmptyErr || err == fsBTEndOfIterationErr )
 		err = fsBTRecordNotFoundErr;
 
-	LogEndTime(kTraceGetBTreeRecord, err);
-
 	return err;
 }
 
@@ -980,9 +952,12 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator
 
 	////////////////////////// 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;
 
@@ -1039,6 +1014,8 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator
 
 	err = FindIteratorPosition(btreePtr, iterator, &left, &node, &right,
 				   &nodeNum, &index, &foundRecord);
+	if (err == fsBTRecordNotFoundErr)
+		err = 0;
 	M_ExitOnError(err);
 
 
@@ -1134,9 +1111,13 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator
 
 ProcessData:
 	err = GetRecordByIndex(btreePtr, node.buffer, index, &keyPtr, &recordPtr, &len);
+	if (err) {
+		err = btBadNode;
+		goto ErrorExit;
+	}
 	
 	while (err == 0) {
-		if (callBackProc(keyPtr, recordPtr, len, callBackState) == 0)
+		if (callBackProc(keyPtr, recordPtr, callBackState) == 0)
 			break;
 		
 		if ((index+1) < ((NodeDescPtr)node.buffer)->numRecords) {
@@ -1166,6 +1147,10 @@ ProcessData:
 		}
 		err = GetRecordByIndex(btreePtr, node.buffer, index,
 						&keyPtr, &recordPtr, &len);
+		if (err) {
+			err = btBadNode;
+			goto ErrorExit;
+		}
 	}
 
 
@@ -1243,17 +1228,15 @@ OSStatus	BTInsertRecord		(FCB						*filePtr,
 	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)
 		return	err;
 
-	LogStartTime(kTraceInsertBTreeRecord);
-
 	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
 	REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
@@ -1273,7 +1256,7 @@ OSStatus	BTInsertRecord		(FCB						*filePtr,
 
 		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);
@@ -1285,6 +1268,9 @@ OSStatus	BTInsertRecord		(FCB						*filePtr,
 								err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
 								M_ExitOnError (err);
 
+								// XXXdbg
+								ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+								
 								((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
 								((NodeDescPtr)nodeRec.buffer)->height	= 1;
 
@@ -1297,14 +1283,19 @@ OSStatus	BTInsertRecord		(FCB						*filePtr,
 									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;
@@ -1314,6 +1305,9 @@ OSStatus	BTInsertRecord		(FCB						*filePtr,
 
 	if (index > 0)
 	{
+		// XXXdbg
+		ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+								
 		recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
 										&iterator->key, KeyLength(btreePtr, &iterator->key),
 										record->bufferAddress, recordLen);
@@ -1328,10 +1322,10 @@ OSStatus	BTInsertRecord		(FCB						*filePtr,
 
 	/////////////////////// Extend File If Necessary ////////////////////////////
 
-	nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;	//€€ 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;
 
@@ -1352,7 +1346,7 @@ Success:
 	++btreePtr->writeCount;
 	++btreePtr->leafRecords;
 	M_BTreeHeaderDirty (btreePtr);
-
+		
 	// create hint
 	iterator->hint.writeCount 	= btreePtr->writeCount;
 	iterator->hint.nodeNum		= insertNodeNum;
@@ -1360,8 +1354,6 @@ Success:
 	iterator->hint.reserved1	= 0;
 	iterator->hint.reserved2	= 0;
 
-	LogEndTime(kTraceInsertBTreeRecord, noErr);
-
 	return noErr;
 
 
@@ -1380,8 +1372,6 @@ ErrorExit:
 	if (err == fsBTEmptyErr)
 		err = fsBTRecordNotFoundErr;
 
-	LogEndTime(kTraceInsertBTreeRecord, err);
-
 	return err;
 }
 
@@ -1407,13 +1397,12 @@ OSStatus	BTReplaceRecord		(FCB						*filePtr,
 	////////////////////////// Priliminary Checks ///////////////////////////////
 
 	nodeRec.buffer = nil;					// so we can call ReleaseNode
+	nodeRec.blockHeader = nil;
 
 	err = CheckInsertParams (filePtr, iterator, record, recordLen);
 	if (err != noErr)
 		return err;
 
-	LogStartTime(kTraceReplaceBTreeRecord);
-
 	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
 	REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
@@ -1430,6 +1419,9 @@ OSStatus	BTReplaceRecord		(FCB						*filePtr,
 		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);
 
@@ -1465,6 +1457,9 @@ OSStatus	BTReplaceRecord		(FCB						*filePtr,
 	// optimization - if simple replace will work then don't extend btree
 	// €€ 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);
 
@@ -1479,10 +1474,10 @@ OSStatus	BTReplaceRecord		(FCB						*filePtr,
 
 	//////////////////////////// Make Some Room /////////////////////////////////
 
-	nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;	//€€ 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;
 
@@ -1490,7 +1485,9 @@ OSStatus	BTReplaceRecord		(FCB						*filePtr,
 		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,
@@ -1507,8 +1504,6 @@ Success:
 	iterator->hint.reserved1	= 0;
 	iterator->hint.reserved2	= 0;
 
-	LogEndTime(kTraceReplaceBTreeRecord, noErr);
-
 	return noErr;
 
 
@@ -1524,9 +1519,120 @@ ErrorExit:
 	iterator->hint.reserved1	= 0;
 	iterator->hint.reserved2	= 0;
 
+	return err;
+}
+
+
 
-	LogEndTime(kTraceReplaceBTreeRecord, err);
+//////////////////////////////// BTUpdateRecord ////////////////////////////////
 
+OSStatus
+BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
+               IterateCallBackProcPtr callBackProc, void * callBackState)
+{
+	OSStatus				err;
+	BTreeControlBlockPtr	btreePtr;
+	TreePathTable			treePathTable;
+	BlockDescriptor			nodeRec;
+	RecordPtr				recordPtr;
+	BTreeKeyPtr				keyPtr;
+	UInt32					insertNodeNum;
+	UInt16					recordLen;
+	UInt16					index;
+	Boolean					validHint;
+
+
+	////////////////////////// Priliminary Checks ///////////////////////////////
+
+	nodeRec.buffer = nil;					// so we can call ReleaseNode
+	nodeRec.blockHeader = nil;
+
+	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+
+	REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+	////////////////////////////// Take A Hint //////////////////////////////////
+
+	err = IsItAHint (btreePtr, iterator, &validHint);
+	M_ExitOnError (err);
+
+	if (validHint)
+	{
+		insertNodeNum = iterator->hint.nodeNum;
+
+		err = GetNode (btreePtr, insertNodeNum, &nodeRec);
+		if (err == noErr)
+		{
+			if (((NodeDescPtr)nodeRec.buffer)->kind == kBTLeafNode &&
+			    SearchNode (btreePtr, nodeRec.buffer, &iterator->key, &index))
+			{
+				err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
+				M_ExitOnError (err);
+
+				// XXXdbg
+				ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+								
+				err = callBackProc(keyPtr, recordPtr, callBackState);
+				M_ExitOnError (err);
+
+				err = UpdateNode (btreePtr, &nodeRec, 0, 0);
+				M_ExitOnError (err);
+
+				++btreePtr->numValidHints;
+
+				goto Success;
+			}
+			else
+			{
+				(void) BTInvalidateHint( iterator );
+			}
+			
+			err = ReleaseNode (btreePtr, &nodeRec);
+			M_ExitOnError (err);
+		}
+		else
+		{
+			(void) BTInvalidateHint( iterator );
+		}
+	}
+
+	////////////////////////////// Get A Clue ///////////////////////////////////
+
+	err = SearchTree (btreePtr, &iterator->key, treePathTable, &insertNodeNum, &nodeRec, &index);
+	M_ExitOnError (err);
+
+	err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
+	M_ExitOnError (err);
+
+	// XXXdbg
+	ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+								
+	err = callBackProc(keyPtr, recordPtr, callBackState);
+	M_ExitOnError (err);
+
+	err = UpdateNode (btreePtr, &nodeRec, 0, 0);
+	M_ExitOnError (err);
+
+Success:
+	// create hint
+	iterator->hint.writeCount 	= btreePtr->writeCount;
+	iterator->hint.nodeNum		= insertNodeNum;
+	iterator->hint.index		= 0;
+	iterator->hint.reserved1	= 0;
+	iterator->hint.reserved2	= 0;
+	return noErr;
+
+	////////////////////////////// Error Exit ///////////////////////////////////
+
+ErrorExit:
+
+	(void) ReleaseNode (btreePtr, &nodeRec);
+
+	iterator->hint.writeCount 	= 0;
+	iterator->hint.nodeNum		= 0;
+	iterator->hint.index		= 0;
+	iterator->hint.reserved1	= 0;
+	iterator->hint.reserved2	= 0;
 	return err;
 }
 
@@ -1541,14 +1647,15 @@ OSStatus	BTDeleteRecord		(FCB						*filePtr,
 	BTreeControlBlockPtr	btreePtr;
 	TreePathTable			treePathTable;
 	BlockDescriptor			nodeRec;
+	SInt32 nodesNeeded;
 	UInt32					nodeNum;
 	UInt16					index;
 
-	LogStartTime(kTraceDeleteBTreeRecord);
 
 	////////////////////////// Priliminary Checks ///////////////////////////////
 
 	nodeRec.buffer = nil;					// so we can call ReleaseNode
+	nodeRec.blockHeader = nil;
 
 	M_ReturnErrorIf (filePtr == nil, 	paramErr);
 	M_ReturnErrorIf (iterator == nil,	paramErr);
@@ -1571,6 +1678,19 @@ OSStatus	BTDeleteRecord		(FCB						*filePtr,
 	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);
@@ -1579,11 +1699,9 @@ OSStatus	BTDeleteRecord		(FCB						*filePtr,
 	++btreePtr->writeCount;
 	--btreePtr->leafRecords;
 	M_BTreeHeaderDirty (btreePtr);
-
+		
 	iterator->hint.nodeNum	= 0;
 
-	LogEndTime(kTraceDeleteBTreeRecord, noErr);
-
 	return noErr;
 
 	////////////////////////////// Error Exit ///////////////////////////////////
@@ -1591,8 +1709,6 @@ OSStatus	BTDeleteRecord		(FCB						*filePtr,
 ErrorExit:
 	(void) ReleaseNode (btreePtr, &nodeRec);
 
-	LogEndTime(kTraceDeleteBTreeRecord, err);
-
 	return	err;
 }
 
@@ -1630,12 +1746,20 @@ OSStatus	BTGetInformation	(FCB					*filePtr,
 	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.
@@ -1657,20 +1781,16 @@ OSStatus	BTFlushPath				(FCB					*filePtr)
 	BTreeControlBlockPtr	btreePtr;
 
 
-	LogStartTime(kTraceFlushBTree);
-
 	M_ReturnErrorIf (filePtr == nil, 	paramErr);
 
 	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
 	M_ReturnErrorIf (btreePtr == nil,	fsBTInvalidFileErr);
 
-	REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+	REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
 
 	err = UpdateHeader (btreePtr, false);
 
-	LogEndTime(kTraceFlushBTree, err);
-
 	return	err;
 }
 
@@ -1700,6 +1820,9 @@ BTReloadData(FCB *filePtr)
 	BTHeaderRec *header;	
 
 
+	node.buffer = nil;
+	node.blockHeader = nil;
+
 	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 	if (btreePtr == nil)
 		return (fsBTInvalidFileErr);
@@ -1834,3 +1957,99 @@ OSStatus	BTSetLastSync		(FCB					*filePtr,
 }
 
 
+__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);
+}
+