xnu-1228.7.58.tar.gz

[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTreeScanner.c

/*
 * Copyright (c) 1996-2008 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@
 *
 *	@(#)BTreeScanner.c
 */
#include <sys/kernel.h>
#include "../../hfs_endian.h"

#include "../headers/BTreeScanner.h"

static int FindNextLeafNode(	BTScanState *scanState, Boolean avoidIO );
static int ReadMultipleNodes( 	BTScanState *scanState );


//_________________________________________________________________________________
//
//	Routine:	BTScanNextRecord
//
//	Purpose:	Return the next leaf record in a scan.
//
//	Inputs:
//		scanState		Scanner's current state
//		avoidIO			If true, don't do any I/O to refill the buffer
//
//	Outputs:
//		key				Key of found record (points into buffer)
//		data			Data of found record (points into buffer)
//		dataSize		Size of data in found record
//
//	Result:
//		noErr			Found a valid record
//		btNotFound		No more records
//		???				Needed to do I/O to get next node, but avoidIO set
//
//	Notes:
//		This routine returns pointers to the found record's key and data.  It
//		does not copy the key or data to a caller-supplied buffer (like
//		GetBTreeRecord would).  The caller must not modify the key or data.
//_________________________________________________________________________________

int BTScanNextRecord(	BTScanState *	scanState,
						Boolean			avoidIO,
						void * *		key,
						void * *		data,
						u_int32_t *		dataSize  )
{
	int				err;
	u_int16_t		dataSizeShort;
	
	err = noErr;

	//
	//	If this is the first call, there won't be any nodes in the buffer, so go
	//	find the first first leaf node (if any).
	//	
	if ( scanState->nodesLeftInBuffer == 0 )
	{
		err = FindNextLeafNode( scanState, avoidIO );
	}

	while ( err == noErr ) 
	{ 
		//	See if we have a record in the current node
		err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr, 
								scanState->recordNum, (KeyPtr *) key, 
								(u_int8_t **) data, &dataSizeShort  );

		if ( err == noErr )
		{
			++scanState->recordsFound;
			++scanState->recordNum;
			if (dataSize != NULL)
				*dataSize = dataSizeShort;
			return noErr;
		}
		else if (err > 0)
		{
			//	We didn't get the node through the cache, so we can't invalidate it.
			//XXX Should we do something else to avoid seeing the same record again?
			return err;
		}
		
		//	We're done with the current node.  See if we've returned all the records
		if ( scanState->recordsFound >= scanState->btcb->leafRecords )
		{
			return btNotFound;
		}

		//	Move to the first record of the next leaf node
		scanState->recordNum = 0; 
		err = FindNextLeafNode( scanState, avoidIO );
	}
	
	//
	//	If we got an EOF error from FindNextLeafNode, then there are no more leaf
	//	records to be found.
	//
	if ( err == fsEndOfIterationErr )
		err = btNotFound;
	
	return err;
	
} /* BTScanNextRecord */


//_________________________________________________________________________________
//
//	Routine:	FindNextLeafNode
//
//	Purpose:	Point to the next leaf node in the buffer.  Read more nodes
//				into the buffer if needed (and allowed).
//
//	Inputs:
//		scanState		Scanner's current state
//		avoidIO			If true, don't do any I/O to refill the buffer
//
//	Result:
//		noErr			Found a valid record
//		fsEndOfIterationErr	No more nodes in file
//		???				Needed to do I/O to get next node, but avoidIO set
//_________________________________________________________________________________

static int FindNextLeafNode(	BTScanState *scanState, Boolean avoidIO )
{
	int err;
	BlockDescriptor block;
	FileReference fref;
	
	err = noErr;		// Assume everything will be OK
	
	while ( 1 ) 
	{
		if ( scanState->nodesLeftInBuffer == 0 ) 
		{
			//	Time to read some more nodes into the buffer
			if ( avoidIO ) 
			{
				return fsBTTimeOutErr;
			}
			else 
			{
				//	read some more nodes into buffer
				err = ReadMultipleNodes( scanState );
				if ( err != noErr ) 
					break;
			}
		}
		else 
		{
			//	Adjust the node counters and point to the next node in the buffer
			++scanState->nodeNum;
			--scanState->nodesLeftInBuffer;
			
			//	If we've looked at all nodes in the tree, then we're done
			if ( scanState->nodeNum >= scanState->btcb->totalNodes )
				return fsEndOfIterationErr;

			if ( scanState->nodesLeftInBuffer == 0 )
			{
				scanState->recordNum = 0; 
				continue; 
			}

			scanState->currentNodePtr = (BTNodeDescriptor *)(((u_int8_t *)scanState->currentNodePtr) 
										+ scanState->btcb->nodeSize);
		}
		
		/* Fake a BlockDescriptor */
		block.blockHeader = NULL;	/* No buffer cache buffer */
		block.buffer = scanState->currentNodePtr;
		block.blockNum = scanState->nodeNum;
		block.blockSize = scanState->btcb->nodeSize;
		block.blockReadFromDisk = 1;
		block.isModified = 0;
		
		fref = scanState->btcb->fileRefNum;
		
		/* This node was read from disk, so it must be swapped/checked.
		 * Since we are reading multiple nodes, we might have read an 
		 * unused node.  Therefore we allow swapping of unused nodes.
		 */
		err = hfs_swap_BTNode(&block, fref, kSwapBTNodeBigToHost, true);
		if ( err != noErr ) {
			printf("FindNextLeafNode: Error from hfs_swap_BTNode (node %u)\n", scanState->nodeNum);
			continue;
		}

		if ( scanState->currentNodePtr->kind == kBTLeafNode )
			break;
	}
	
	return err;
	
} /* FindNextLeafNode */


//_________________________________________________________________________________
//
//	Routine:	ReadMultipleNodes
//
//	Purpose:	Read one or more nodes into the buffer.
//
//	Inputs:
//		theScanStatePtr		Scanner's current state
//
//	Result:
//		noErr				One or nodes were read
//		fsEndOfIterationErr		No nodes left in file, none in buffer
//_________________________________________________________________________________

static int ReadMultipleNodes( BTScanState *theScanStatePtr )
{
	int						myErr = E_NONE;
	BTreeControlBlockPtr  	myBTreeCBPtr;
	daddr64_t				myPhyBlockNum;
	u_int32_t				myBufferSize;
	struct vnode *			myDevPtr;
	unsigned int			myBlockRun;
	u_int32_t				myBlocksInBufferCount;

	// release old buffer if we have one
	if ( theScanStatePtr->bufferPtr != NULL )
	{
	        buf_markinvalid(theScanStatePtr->bufferPtr);
		buf_brelse( theScanStatePtr->bufferPtr );
		theScanStatePtr->bufferPtr = NULL;
		theScanStatePtr->currentNodePtr = NULL;
	}
	
	myBTreeCBPtr = theScanStatePtr->btcb;
			
	// map logical block in catalog btree file to physical block on volume
	myErr = hfs_bmap(myBTreeCBPtr->fileRefNum, theScanStatePtr->nodeNum, 
	                 &myDevPtr, &myPhyBlockNum, &myBlockRun);
	if ( myErr != E_NONE )
	{
		goto ExitThisRoutine;
	}

	// bmap block run gives us the remaining number of valid blocks (number of blocks 
	// minus the first).  so if there are 10 valid blocks our run number will be 9.
	// blocks, in our case is the same as nodes (both are 4K)
	myBlocksInBufferCount = (theScanStatePtr->bufferSize / myBTreeCBPtr->nodeSize );
	myBufferSize = theScanStatePtr->bufferSize;
	if ( (myBlockRun + 1) < myBlocksInBufferCount )
	{
		myBufferSize = (myBlockRun + 1) * myBTreeCBPtr->nodeSize;
	}
	
	// now read blocks from the device 
	myErr = (int)buf_bread(myDevPtr, 
	                       myPhyBlockNum, 
	                       myBufferSize,  
	                       NOCRED, 
	                       &theScanStatePtr->bufferPtr );
	if ( myErr != E_NONE )
	{
		goto ExitThisRoutine;
	}

	theScanStatePtr->nodesLeftInBuffer = buf_count(theScanStatePtr->bufferPtr) / theScanStatePtr->btcb->nodeSize;
	theScanStatePtr->currentNodePtr = (BTNodeDescriptor *) buf_dataptr(theScanStatePtr->bufferPtr);

ExitThisRoutine:
	return myErr;
	
} /* ReadMultipleNodes */



//_________________________________________________________________________________
//
//	Routine:	BTScanInitialize
//
//	Purpose:	Prepare to start a new BTree scan, or resume a previous one.
//
//	Inputs:
//		btreeFile		The B-Tree's file control block
//		startingNode	Initial node number
//		startingRecord	Initial record number within node
//		recordsFound	Number of valid records found so far
//		bufferSize		Size (in bytes) of buffer
//
//	Outputs:
//		scanState		Scanner's current state; pass to other scanner calls
//
//	Notes:
//		To begin a new scan and see all records in the B-Tree, pass zeroes for
//		startingNode, startingRecord, and recordsFound.
//
//		To resume a scan from the point of a previous BTScanTerminate, use the
//		values returned by BTScanTerminate as input for startingNode, startingRecord,
//		and recordsFound.
//
//		When resuming a scan, the caller should check the B-tree's write count.  If
//		it is different from the write count when the scan was terminated, then the
//		tree may have changed and the current state may be incorrect.  In particular,
//		you may see some records more than once, or never see some records.  Also,
//		the scanner may not be able to detect when all leaf records have been seen,
//		and will have to scan through many empty nodes.
//