/*
 * Copyright (c) 2000-2003, 2005-2009 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * 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.
 * 
 * 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, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_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.

	File Ownership:

		DRI:				Don Brady

		Other Contact:		Mark Day

		Technology:			File Systems

	Writers:

		(djb)	Don Brady
		(ser)	Scott Roberts
		(msd)	Mark Day

	Change History (most recent first):

	   <MOSXS>	  6/1/99	djb		Sync up with Mac OS 8.6.
	   <CS3>	11/24/97	djb		Remove some debug code (Panic calls).
	   <CS2>	 7/24/97	djb		CallbackProcs now take refnum instead of an FCB.
	   <CS1>	 4/23/97	djb		first checked in

	  <HFS2>	 2/19/97	djb		Change E_BadNodeType to fsBTBadNodeType.
	  <HFS1>	12/19/96	djb		first checked in

	History applicable to original Scarecrow Design:

		 <4>	10/25/96	ser		Changing for new VFPI
		 <3>	10/18/96	ser		Converting over VFPI changes
		 <2>	 1/10/96	msd		Change 64-bit math to use real function names from Math64.i.
		 <1>	10/18/95	rst		Moved from Scarecrow project.

		 <8>	 1/12/95	wjk		Adopt Model FileSystem changes in D5.
		 <7>	 9/30/94	prp		Get in sync with D2 interface changes.
		 <6>	 7/22/94	wjk		Convert to the new set of header files.
		 <5>	 8/31/93	prp		Use U64SetU instead of S64Set.
		 <4>	 5/21/93	gs		Fix ExtendBTree bug.
		 <3>	 5/10/93	gs		Fix pointer arithmetic bug in AllocateNode.
		 <2>	 3/23/93	gs		finish ExtendBTree routine.
		 <1>	  2/8/93	gs		first checked in
		 <0>	  1/1/93	gs		begin AllocateNode and FreeNode

*/

#include "../../hfs_btreeio.h"
#include "../../hfs_endian.h"
#include "../headers/BTreesPrivate.h"

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

static OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
						BlockDescriptor			 *nodePtr,
						u_int16_t					**mapPtr,
						u_int16_t					 *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, u_int32_t	*nodeNum)
{
	OSStatus		 err;
	BlockDescriptor	 node;
	u_int16_t		*mapPtr, *pos;
	u_int16_t		 mapSize, size;
	u_int16_t		 freeWord;
	u_int16_t		 mask;
	u_int16_t		 bitOffset;
	u_int32_t		 nodeNumber;
	
	
	nodeNumber		= 0;				// first node number of header map record
	node.buffer		= nil;				// clear node.buffer to get header node
										//	- and for ErrorExit
	node.blockHeader = nil;
	
	while (true)
	{
		err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
		M_ExitOnError (err);
		
		// XXXdbg
		ModifyBlockStart(btreePtr->fileRefNum, &node);
								
	//////////////////////// 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	= SWAP_BE16 (*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 |= SWAP_BE16 (mask);				// set the map bit for the node

	err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
	M_ExitOnError (err);
	
	--btreePtr->freeNodes;
	btreePtr->flags |= kBTHeaderDirty;
	
	/* Account for allocations from node reserve */
	BTUpdateReserve(btreePtr, 1);

	*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, u_int32_t	nodeNum)
{
	OSStatus		 err;
	BlockDescriptor	 node;
	u_int32_t		 nodeIndex;
	u_int16_t		 mapSize;
	u_int16_t		*mapPos;
	u_int16_t		 bitOffset;
	

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

	// XXXdbg
	ModifyBlockStart(btreePtr->fileRefNum, &node);
								
	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_SWAP_BE16_ClearBitNum (*mapPos, bitOffset);		// clear it
    
	err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
	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,
						 u_int32_t				newTotalNodes )
{
	OSStatus				 err;
	FCB						*filePtr;
	FSSize					 minEOF, maxEOF;	
	u_int16_t				 nodeSize;
	u_int32_t				 oldTotalNodes;
	u_int32_t				 newMapNodes;
	u_int32_t				 mapBits, totalMapBits;
	u_int32_t				 recStartBit;
	u_int32_t				 nodeNum, nextNodeNum;
	u_int32_t				 firstNewMapNodeNum, lastNewMapNodeNum;
	BlockDescriptor			 mapNode, newNode;
	u_int16_t				*mapPos;
	u_int16_t				*mapStart;
	u_int16_t				 mapSize;
	u_int16_t				 mapNodeRecSize;
	u_int32_t				 bitInWord, bitInRecord;
	u_int16_t				 mapIndex;


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

	nodeSize			= btreePtr->nodeSize;
	filePtr				= GetFileControlBlock(btreePtr->fileRefNum);
	
	mapNode.buffer		= nil;
	mapNode.blockHeader = nil;
	newNode.buffer		= nil;
	newNode.blockHeader = nil;

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


	//////////////////////// 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 ("ExtendBTree: totalMapBits != CalcMapBits");
		
	/////////////////////// Extend LEOF If Necessary ////////////////////////////

	minEOF = (u_int64_t)newTotalNodes * (u_int64_t)nodeSize;
	if ( (u_int64_t)filePtr->fcbEOF < minEOF )
	{
		maxEOF = (u_int64_t)0x7fffffffLL * (u_int64_t)nodeSize;

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

	
	//////////////////// Calc New Total Number Of Nodes /////////////////////////
	
	newTotalNodes = filePtr->fcbEOF / 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 ////////////////////////////
	// XXXdbg - this is the correct place for this:
	ModifyBlockStart(btreePtr->fileRefNum, &mapNode);

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

	nodeNum		= firstNewMapNodeNum;
	while (true)
	{
		err = GetNewNode (btreePtr, nodeNum, &newNode);
		M_ExitOnError (err);
		
		// XXXdbg
		ModifyBlockStart(btreePtr->fileRefNum, &newNode);

		((NodeDescPtr)newNode.buffer)->numRecords	= 1;
		((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
		
		// set free space offset
		*(u_int16_t *)((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, 0, kLockTransaction);
		M_ExitOnError (err);
	}
	
	err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
	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, 0, kLockTransaction);
			M_ExitOnError (err);
			
			err = GetNode (btreePtr, nextNodeNum, 0, &mapNode);
			M_ExitOnError (err);
			
			// XXXdbg
			ModifyBlockStart(btreePtr->fileRefNum, &mapNode);

			mapIndex = 0;
			
			mapStart	 = (u_int16_t *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
			mapSize		 = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
			
			if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
			{
				Panic ("ExtendBTree: 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_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
        
		++nodeNum;
		
	} while (nodeNum <= lastNewMapNodeNum);

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

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

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

	btreePtr->flags			|= kBTHeaderDirty;		//€€ how about a macro for this

	/* Force the b-tree header changes to disk */
	(void) UpdateHeader (btreePtr, true);
	
	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
-------------------------------------------------------------------------------*/

static
OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
						BlockDescriptor			 *nodePtr,
						u_int16_t				**mapPtr, 			
						u_int16_t				 *mapSize )
{
	OSStatus	err;
	u_int16_t	mapIndex;
	u_int32_t	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, 0, nodePtr);
		M_ExitOnError (err);
		
		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
		{
			err = fsBTBadNodeType;
			goto ErrorExit;
		}
		
		++btreePtr->numMapNodesRead;
		mapIndex = 0;
	} else {
		err = GetNode (btreePtr, kHeaderNodeNum, 0, nodePtr);
		M_ExitOnError (err);
		
		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
		{
			err = fsBTInvalidHeaderErr;				//€€ or fsBTBadNodeType
			goto ErrorExit;
		}
		
		mapIndex = 2;
	}
	
		
	*mapPtr		= (u_int16_t *) 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 //////////////////////////////////

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


/*-------------------------------------------------------------------------------
Routine:	BTZeroUnusedNodes

Function:	Write zeros to all nodes in the B-tree that are not currently in use.
-------------------------------------------------------------------------------*/
int
BTZeroUnusedNodes(FCB *filePtr)
{
	int						err;
	vnode_t					vp;
	BTreeControlBlockPtr	btreePtr;
	BlockDescriptor			mapNode;
	buf_t					bp;
	u_int32_t				nodeNumber;
	u_int16_t				*mapPtr, *pos;
	u_int16_t				mapSize, size;
	u_int16_t				mask;
	u_int16_t				bitNumber;
	u_int16_t				word;
	int						numWritten;
	
	vp = FTOV(filePtr);
	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
	bp = NULL;
	nodeNumber = 0;
	mapNode.buffer = nil;
	mapNode.blockHeader = nil;
	numWritten = 0;
	
	/* Iterate over map nodes. */
	while (true)
	{
		err = GetMapNode (btreePtr, &mapNode, &mapPtr, &mapSize);
		if (err)
		{
			err = MacToVFSError(err);
			goto ErrorExit;
		}
		
		pos		= mapPtr;
		size	= mapSize;
		size  >>= 1;					/* convert to number of 16-bit words */

		/* Iterate over 16-bit words in the map record. */
		while (size--)
		{
			if (*pos != 0xFFFF)			/* Anything free in this word? */
			{
				word = SWAP_BE16(*pos);
				
				/* Iterate over bits in the word. */
				for (bitNumber = 0, mask = 0x8000;
				     bitNumber < 16;
				     ++bitNumber, mask >>= 1)
				{
					if (word & mask)
						continue;				/* This node is in use. */
					
					if (nodeNumber + bitNumber >= btreePtr->totalNodes)
					{
						/* We've processed all of the nodes. */
						goto done;
					}
					
					/*
					 * Get a buffer full of zeros and write it to the unused
					 * node.  Since we'll probably be writing a lot of nodes,
					 * bypass the journal (to avoid a transaction that's too
					 * big).  Instead, this behaves more like clearing out
					 * nodes when extending a B-tree (eg., ClearBTNodes).
					 */
					bp = buf_getblk(vp, nodeNumber + bitNumber, btreePtr->nodeSize, 0, 0, BLK_META);
					if (bp == NULL)
					{
						printf("hfs: BTZeroUnusedNodes: unable to read node %u\n", nodeNumber + bitNumber);
						err = EIO;
						goto ErrorExit;
					}

					if (buf_flags(bp) & B_LOCKED) {
						/* 
						 * This node is already part of a transaction and will be written when
						 * the transaction is committed, so don't write it here.  If we did, then
						 * we'd hit a panic in hfs_vnop_bwrite because the B_LOCKED bit is still set.
						 */
						buf_brelse(bp);
						continue;
					}
					
					buf_clear(bp);
					buf_markaged(bp);
					
					/*
					 * Try not to hog the buffer cache.  Wait for the write
					 * every 32 nodes.   If VNOP_BWRITE reports an error, bail out and bubble
					 * it up to the function calling us.  If we tried to update a read-only 
					 * mount on read-only media, for example, catching the error will let 
					 * us alert the callers of this function that they should maintain 
					 * the mount in read-only mode.

					 */
					++numWritten;
					if (numWritten % 32 == 0) {
						err = VNOP_BWRITE(bp);
						if (err) {
							goto ErrorExit;
						}
					}
					else {
						buf_bawrite(bp);
					}
				}
			}
			
			/* Go to the next word in the bitmap */
			++pos;
			nodeNumber += 16;
		}
	}

ErrorExit:
done:
	(void) ReleaseNode(btreePtr, &mapNode);
	
	return err;
}