BTreeAllocate.c   [plain text]


/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  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 1.0 (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.
 * 
 * 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."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
	File:		BTreeAllocate.c

	Contains:	BTree Node Allocation routines for the BTree Module.

	Version:	xxx put the technology version here xxx

	Written by:	Gordon Sheridan and Bill Bruffey

	Copyright:	© 1992-1999 by Apple Computer, Inc., all rights reserved.
*/

#include "BTreePrivate.h"

///////////////////// Routines Internal To BTreeAllocate.c //////////////////////

OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
						BlockDescriptor			 *nodePtr,
						UInt16					**mapPtr,
						UInt16					 *mapSize );

/////////////////////////////////////////////////////////////////////////////////

/*-------------------------------------------------------------------------------

Routine:	AllocateNode	-	Find Free Node, Mark It Used, and Return Node Number.

Function:	Searches the map records for the first free node, marks it "in use" and
			returns the node number found. This routine should really only be called
			when we know there are free blocks, otherwise it's just a waste of time.

Note:		We have to examine map nodes a word at a time rather than a long word
			because the External BTree Mgr used map records that were not an integral
			number of long words. Too bad. In our spare time could develop a more
			sophisticated algorithm that read map records by long words (and long
			word aligned) and handled the spare bytes at the beginning and end
			appropriately.

Input:		btreePtr	- pointer to control block for BTree file		

Output:		nodeNum		- number of node allocated
			
			
Result:		noErr			- success
			fsBTNoMoreMapNodesErr	- no free blocks were found
			!= noErr		- failure
-------------------------------------------------------------------------------*/

OSStatus	AllocateNode (BTreeControlBlockPtr		btreePtr, UInt32	*nodeNum)
{
	OSStatus		 err;
	BlockDescriptor	 node;
	UInt16			*mapPtr, *pos;
	UInt16			 mapSize, size;
	UInt16			 freeWord;
	UInt16			 mask;
	UInt16			 bitOffset;
	UInt32			 nodeNumber;
	
	
	nodeNumber		= 0;				// first node number of header map record
	node.buffer		= nil;				// clear node.buffer to get header node
										//	- and for ErrorExit
	
	while (true)
	{
		err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
		M_ExitOnError (err);
		
	//////////////////////// Find Word with Free Bit ////////////////////////////

		pos		= mapPtr;
		size	= mapSize;
		size  >>= 1;						// convert to number of words
						//¥¥ assumes mapRecords contain an integral number of words

		while ( size-- )
		{
			if ( *pos++ != 0xFFFF )			// assume test fails, and increment pos
				break;
		}

		--pos;								// whoa! backup

		if (*pos != 0xFFFF)					// hey, we got one!
			break;
		
		nodeNumber += mapSize << 3;			// covert to number of bits (nodes)
	}
	
	///////////////////////// Find Free Bit in Word /////////////////////////////

	freeWord	= *pos;
	bitOffset	=  15;
	mask		=  0x8000;
	
	do {
		if ( (freeWord & mask) == 0)
			break;
		mask >>= 1;
	} while (--bitOffset);

	////////////////////// Calculate Free Node Number ///////////////////////////
	
	nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset);	// (pos-mapPtr) = # of words!
	
	
	///////////////////////// Check for End of Map //////////////////////////////

	if (nodeNumber >= btreePtr->totalNodes)
	{
		err = fsBTFullErr;
		goto ErrorExit;
	}

	/////////////////////////// Allocate the Node ///////////////////////////////

	*pos |= mask;						// set the map bit for the node

	err = UpdateNode (btreePtr, &node);
	M_ExitOnError (err);
	
	--btreePtr->freeNodes;
	btreePtr->flags |= kBTHeaderDirty;
	*nodeNum = nodeNumber;
	
	return noErr;

////////////////////////////////// Error Exit ///////////////////////////////////

ErrorExit:
	
	(void) ReleaseNode (btreePtr, &node);
	*nodeNum = 0;
	
	return	err;
}



/*-------------------------------------------------------------------------------

Routine:	FreeNode	-	Clear allocation bit for node.

Function:	Finds the bit representing the node specified by nodeNum in the node
			map and clears the bit.


Input:		btreePtr	- pointer to control block for BTree file
			nodeNum		- number of node to mark free

Output:		none			
			
Result:		noErr			- success
			fsBTNoMoreMapNodesErr	- node number is beyond end of node map
			!= noErr		- GetNode or ReleaseNode encountered some difficulty
-------------------------------------------------------------------------------*/

OSStatus	FreeNode (BTreeControlBlockPtr		btreePtr, UInt32	nodeNum)
{
	OSStatus		 err;
	BlockDescriptor	 node;
	UInt32			 nodeIndex;
	UInt16			 mapSize;
	UInt16			*mapPos;
	UInt16			 bitOffset;
	

	//////////////////////////// Find Map Record ////////////////////////////////
	nodeIndex			= 0;				// first node number of header map record
	node.buffer			= nil;				// invalidate node.buffer to get header node
	
	while (nodeNum >= nodeIndex)
	{
		err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
		M_ExitOnError (err);
		
		nodeIndex += mapSize << 3;			// covert to number of bits (nodes)
	}
	
	//////////////////////////// Mark Node Free /////////////////////////////////

	nodeNum -= (nodeIndex - (mapSize << 3));			// relative to this map record
	bitOffset = 15 - (nodeNum & 0x0000000F);			// last 4 bits are bit offset
	mapPos += nodeNum >> 4;								// point to word containing map bit
	M_ClearBitNum (*mapPos, bitOffset);					// clear it
	
	err = UpdateNode (btreePtr, &node);
	M_ExitOnError (err);
	

	++btreePtr->freeNodes;
	btreePtr->flags |= kBTHeaderDirty;					//¥¥ how about a macro for this

	return noErr;

ErrorExit:

	(void) ReleaseNode (btreePtr, &node);

	return	err;
}



/*-------------------------------------------------------------------------------

Routine:	ExtendBTree	-	Call FSAgent to extend file, and allocate necessary map nodes.

Function:	This routine calls the the FSAgent to extend the end of fork, if necessary,
			to accomodate the number of nodes requested. It then allocates as many
			map nodes as are necessary to account for all the nodes in the B*Tree.
			If newTotalNodes is less than the current number of nodes, no action is
			taken.

Note:		Internal HFS File Manager BTree Module counts on an integral number of
			long words in map records, although they are not long word aligned.

Input:		btreePtr		- pointer to control block for BTree file
			newTotalNodes	- total number of nodes the B*Tree is to extended to
			
Output:		none
			
Result:		noErr		- success
			!= noErr	- failure
-------------------------------------------------------------------------------*/

OSStatus	ExtendBTree	(BTreeControlBlockPtr	btreePtr,
						 UInt32					newTotalNodes )
{
	OSStatus				 err;
	SFCB					*filePtr;
	FSSize					 minEOF, maxEOF;	
	UInt16					 nodeSize;
	UInt32					 oldTotalNodes;
	UInt32					 newMapNodes;
	UInt32					 mapBits, totalMapBits;
	UInt32					 recStartBit;
	UInt32					 nodeNum, nextNodeNum;
	UInt32					 firstNewMapNodeNum, lastNewMapNodeNum;
	BlockDescriptor			 mapNode, newNode;
	UInt16					*mapPos;
	UInt16					*mapStart;
	UInt16					 mapSize;
	UInt16					 mapNodeRecSize;
	UInt32					 bitInWord, bitInRecord;
	UInt16					 mapIndex;


	oldTotalNodes	 	= btreePtr->totalNodes;
	if (newTotalNodes  <= oldTotalNodes)				// we're done!
		return	noErr;

	nodeSize			= btreePtr->nodeSize;
	filePtr				= btreePtr->fcbPtr;
	
	mapNode.buffer		= nil;
	newNode.buffer		= nil;

	mapNodeRecSize	= nodeSize - sizeof(BTNodeDescriptor) - 6;	// 2 bytes of free space (see note)

	//¥¥ update for proper 64 bit arithmetic!!


	//////////////////////// Count Bits In Node Map /////////////////////////////
	
	totalMapBits = 0;
	do {
		err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
		M_ExitOnError (err);
		
		mapBits		= mapSize << 3;				// mapSize (in bytes) * 8
		recStartBit	= totalMapBits;				// bit number of first bit in map record
		totalMapBits  += mapBits;
		
	} while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );

	if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
		Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
		
	/////////////////////// Extend LEOF If Necessary ////////////////////////////

	minEOF = newTotalNodes * nodeSize;
	if ( filePtr->fcbLogicalSize < minEOF )
	{
		//¥¥
		//¥¥	???? Does this B*Tree pack stop working when LEOF > 2^32-1?
		//¥¥
		maxEOF = ((UInt32)0xFFFFFFFFL);

		err = btreePtr->setEndOfForkProc (btreePtr->fcbPtr, minEOF, maxEOF);
		M_ExitOnError (err);
	}

	
	//////////////////// Calc New Total Number Of Nodes /////////////////////////
	
	newTotalNodes = filePtr->fcbLogicalSize / nodeSize;		//¥¥ hack!
	//¥¥ do we wish to perform any verification of newTotalNodes at this point?

	btreePtr->totalNodes = newTotalNodes;		//¥¥ do we need to update freeNodes here too?


	////////////// Calculate Number Of New Map Nodes Required ///////////////////

	newMapNodes		= 0;
	if (newTotalNodes > totalMapBits)
	{
		newMapNodes			= (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
		firstNewMapNodeNum	= oldTotalNodes;
		lastNewMapNodeNum	= firstNewMapNodeNum + newMapNodes - 1;
	}
	else
	{
		err = ReleaseNode (btreePtr, &mapNode);
		M_ExitOnError (err);
	
		goto Success;
	}
	

	/////////////////////// Initialize New Map Nodes ////////////////////////////

	((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;

	nodeNum		= firstNewMapNodeNum;
	while (true)
	{
		err = GetNewNode (btreePtr, nodeNum, &newNode);
		M_ExitOnError (err);
		
		((NodeDescPtr)newNode.buffer)->numRecords	= 1;
		((NodeDescPtr)newNode.buffer)->kind			= kBTMapNode;
		
		// set free space offset
		*(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;

		if (nodeNum++ == lastNewMapNodeNum)
			break;

		((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum;	// point to next map node
			
		err = UpdateNode (btreePtr, &newNode);
		M_ExitOnError (err);
	}
	
	err = UpdateNode (btreePtr, &newNode);
	M_ExitOnError (err);
		

	///////////////////// Mark New Map Nodes Allocated //////////////////////////

	nodeNum = firstNewMapNodeNum;
	do {	
		bitInRecord	= nodeNum - recStartBit;

		while (bitInRecord >= mapBits)
		{
			nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
			if ( nextNodeNum == 0)
			{
				err = fsBTNoMoreMapNodesErr;
				goto ErrorExit;
			}
			
			err = UpdateNode (btreePtr, &mapNode);
			M_ExitOnError (err);
			
			err = GetNode (btreePtr, nextNodeNum, &mapNode);
			M_ExitOnError (err);
			
			mapIndex = 0;
			
			mapStart	 = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
			mapSize		 = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
			
			if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
			{
				Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
			}
			
			mapBits		= mapSize << 3;		// mapSize (in bytes) * 8
			recStartBit	= totalMapBits;		// bit number of first bit in map record
			totalMapBits  += mapBits;

			bitInRecord	= nodeNum - recStartBit;
		}

		mapPos		= mapStart + ((nodeNum - recStartBit) >> 4);
		bitInWord	= 15 - ((nodeNum - recStartBit) & 0x0000000F);
		M_SetBitNum (*mapPos, bitInWord);
		
		++nodeNum;
		
	} while (nodeNum <= lastNewMapNodeNum);

	err = UpdateNode (btreePtr, &mapNode);
	M_ExitOnError (err);

	
	//////////////////////////////// Success ////////////////////////////////////

Success:
	
	btreePtr->totalNodes	 =  newTotalNodes;
	btreePtr->freeNodes		+= (newTotalNodes - oldTotalNodes) - newMapNodes;

	btreePtr->flags			|= kBTHeaderDirty;		//¥¥ how about a macro for this
	
	return	noErr;


	////////////////////////////// Error Exit ///////////////////////////////////

ErrorExit:

	(void) ReleaseNode (btreePtr, &mapNode);
	(void) ReleaseNode (btreePtr, &newNode);
	
	return	err;
}



/*-------------------------------------------------------------------------------

Routine:	GetMapNode	-	Get the next map node and pointer to the map record.

Function:	Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
			it and gets the next node. If nodePtr->buffer is nil, then the header
			node is retrieved.


Input:		btreePtr	- pointer to control block for BTree file
			nodePtr		- pointer to a BlockDescriptor of a map node
			
Output:		nodePtr		- pointer to the BlockDescriptor for the next map node
			mapPtr		- pointer to the map record within the map node
			mapSize		- number of bytes in the map record
			
Result:		noErr			- success
			fsBTNoMoreMapNodesErr	- we've run out of map nodes
			fsBTInvalidNodeErr			- bad node, or not node type kMapNode
			!= noErr		- failure
-------------------------------------------------------------------------------*/

OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
						BlockDescriptor			 *nodePtr,
						UInt16					**mapPtr,
						UInt16					 *mapSize )
{
	OSStatus	err;
	UInt16		mapIndex;
	UInt32		nextNodeNum;
	
	if (nodePtr->buffer != nil)		// if iterator is valid...
	{
		nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
		if (nextNodeNum == 0)
		{
			err = fsBTNoMoreMapNodesErr;
			goto ErrorExit;
		}
		
		err = ReleaseNode (btreePtr, nodePtr);
		M_ExitOnError (err);
		
		err = GetNode (btreePtr, nextNodeNum, nodePtr);
		M_ExitOnError (err);
		
		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
		{
			err = fsBTBadNodeType;
			goto ErrorExit;
		}
		
		++btreePtr->numMapNodesRead;
		mapIndex = 0;
	} else {
		err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
		M_ExitOnError (err);
		
		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
		{
			err = fsBTInvalidHeaderErr;				//¥¥ or fsBTBadNodeType
			goto ErrorExit;
		}
		
		mapIndex = 2;
	}
	
		
	*mapPtr		= (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
	*mapSize	= GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
	
	return noErr;
	
	
ErrorExit:
	
	(void) ReleaseNode (btreePtr, nodePtr);
	
	*mapPtr		= nil;
	*mapSize	= 0;
	
	return	err;
}



////////////////////////////////// CalcMapBits //////////////////////////////////

UInt32		CalcMapBits	(BTreeControlBlockPtr	 btreePtr)
{
	UInt32		mapBits;
	
	mapBits		= M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
	
	while (mapBits < btreePtr->totalNodes)
		mapBits	+= M_MapRecordSize (btreePtr->nodeSize) << 3;
	
	return	mapBits;
}