1/*
2 * Copyright (c) 1996-2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 *
28 *	@(#)BTreeScanner.c
29 */
30#include <sys/kernel.h>
31#include "../../hfs_endian.h"
32
33#include "../headers/BTreeScanner.h"
34
35static int FindNextLeafNode(	BTScanState *scanState, Boolean avoidIO );
36static int ReadMultipleNodes( 	BTScanState *scanState );
37
38
39//_________________________________________________________________________________
40//
41//	Routine:	BTScanNextRecord
42//
43//	Purpose:	Return the next leaf record in a scan.
44//
45//	Inputs:
46//		scanState		Scanner's current state
47//		avoidIO			If true, don't do any I/O to refill the buffer
48//
49//	Outputs:
50//		key				Key of found record (points into buffer)
51//		data			Data of found record (points into buffer)
52//		dataSize		Size of data in found record
53//
54//	Result:
55//		noErr			Found a valid record
56//		btNotFound		No more records
57//		???				Needed to do I/O to get next node, but avoidIO set
58//
59//	Notes:
60//		This routine returns pointers to the found record's key and data.  It
61//		does not copy the key or data to a caller-supplied buffer (like
62//		GetBTreeRecord would).  The caller must not modify the key or data.
63//_________________________________________________________________________________
64
65int BTScanNextRecord(	BTScanState *	scanState,
66						Boolean			avoidIO,
67						void * *		key,
68						void * *		data,
69						u_int32_t *		dataSize  )
70{
71	int				err;
72	u_int16_t		dataSizeShort;
73
74	err = noErr;
75
76	//
77	//	If this is the first call, there won't be any nodes in the buffer, so go
78	//	find the first first leaf node (if any).
79	//
80	if ( scanState->nodesLeftInBuffer == 0 )
81	{
82		err = FindNextLeafNode( scanState, avoidIO );
83	}
84
85	while ( err == noErr )
86	{
87		//	See if we have a record in the current node
88		err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr,
89								scanState->recordNum, (KeyPtr *) key,
90								(u_int8_t **) data, &dataSizeShort  );
91
92		if ( err == noErr )
93		{
94			++scanState->recordsFound;
95			++scanState->recordNum;
96			if (dataSize != NULL)
97				*dataSize = dataSizeShort;
98			return noErr;
99		}
100		else if (err > 0)
101		{
102			//	We didn't get the node through the cache, so we can't invalidate it.
103			//XXX Should we do something else to avoid seeing the same record again?
104			return err;
105		}
106
107		//	We're done with the current node.  See if we've returned all the records
108		if ( scanState->recordsFound >= scanState->btcb->leafRecords )
109		{
110			return btNotFound;
111		}
112
113		//	Move to the first record of the next leaf node
114		scanState->recordNum = 0;
115		err = FindNextLeafNode( scanState, avoidIO );
116	}
117
118	//
119	//	If we got an EOF error from FindNextLeafNode, then there are no more leaf
120	//	records to be found.
121	//
122	if ( err == fsEndOfIterationErr )
123		err = btNotFound;
124
125	return err;
126
127} /* BTScanNextRecord */
128
129
130//_________________________________________________________________________________
131//
132//	Routine:	FindNextLeafNode
133//
134//	Purpose:	Point to the next leaf node in the buffer.  Read more nodes
135//				into the buffer if needed (and allowed).
136//
137//	Inputs:
138//		scanState		Scanner's current state
139//		avoidIO			If true, don't do any I/O to refill the buffer
140//
141//	Result:
142//		noErr			Found a valid record
143//		fsEndOfIterationErr	No more nodes in file
144//		???				Needed to do I/O to get next node, but avoidIO set
145//_________________________________________________________________________________
146
147static int FindNextLeafNode(	BTScanState *scanState, Boolean avoidIO )
148{
149	int err;
150	BlockDescriptor block;
151	FileReference fref;
152
153	err = noErr;		// Assume everything will be OK
154
155	while ( 1 )
156	{
157		if ( scanState->nodesLeftInBuffer == 0 )
158		{
159			//	Time to read some more nodes into the buffer
160			if ( avoidIO )
161			{
162				return fsBTTimeOutErr;
163			}
164			else
165			{
166				//	read some more nodes into buffer
167				err = ReadMultipleNodes( scanState );
168				if ( err != noErr )
169					break;
170			}
171		}
172		else
173		{
174			//	Adjust the node counters and point to the next node in the buffer
175			++scanState->nodeNum;
176			--scanState->nodesLeftInBuffer;
177
178			//	If we've looked at all nodes in the tree, then we're done
179			if ( scanState->nodeNum >= scanState->btcb->totalNodes )
180				return fsEndOfIterationErr;
181
182			if ( scanState->nodesLeftInBuffer == 0 )
183			{
184				scanState->recordNum = 0;
185				continue;
186			}
187
188			scanState->currentNodePtr = (BTNodeDescriptor *)(((u_int8_t *)scanState->currentNodePtr)
189										+ scanState->btcb->nodeSize);
190		}
191
192		/* Fake a BlockDescriptor */
193		block.blockHeader = NULL;	/* No buffer cache buffer */
194		block.buffer = scanState->currentNodePtr;
195		block.blockNum = scanState->nodeNum;
196		block.blockSize = scanState->btcb->nodeSize;
197		block.blockReadFromDisk = 1;
198		block.isModified = 0;
199
200		fref = scanState->btcb->fileRefNum;
201
202		/* This node was read from disk, so it must be swapped/checked.
203		 * Since we are reading multiple nodes, we might have read an
204		 * unused node.  Therefore we allow swapping of unused nodes.
205		 */
206		err = hfs_swap_BTNode(&block, fref, kSwapBTNodeBigToHost, true);
207		if ( err != noErr ) {
208			printf("hfs: FindNextLeafNode: Error from hfs_swap_BTNode (node %u)\n", scanState->nodeNum);
209			continue;
210		}
211
212		if ( scanState->currentNodePtr->kind == kBTLeafNode )
213			break;
214	}
215
216	return err;
217
218} /* FindNextLeafNode */
219
220
221//_________________________________________________________________________________
222//
223//	Routine:	ReadMultipleNodes
224//
225//	Purpose:	Read one or more nodes into the buffer.
226//
227//	Inputs:
228//		theScanStatePtr		Scanner's current state
229//
230//	Result:
231//		noErr				One or nodes were read
232//		fsEndOfIterationErr		No nodes left in file, none in buffer
233//_________________________________________________________________________________
234
235static int ReadMultipleNodes( BTScanState *theScanStatePtr )
236{
237	int						myErr = E_NONE;
238	BTreeControlBlockPtr  	myBTreeCBPtr;
239	daddr64_t				myPhyBlockNum;
240	u_int32_t				myBufferSize;
241	struct vnode *			myDevPtr;
242	unsigned int			myBlockRun;
243	u_int32_t				myBlocksInBufferCount;
244
245	// release old buffer if we have one
246	if ( theScanStatePtr->bufferPtr != NULL )
247	{
248	        buf_markinvalid(theScanStatePtr->bufferPtr);
249		buf_brelse( theScanStatePtr->bufferPtr );
250		theScanStatePtr->bufferPtr = NULL;
251		theScanStatePtr->currentNodePtr = NULL;
252	}
253
254	myBTreeCBPtr = theScanStatePtr->btcb;
255
256	// map logical block in catalog btree file to physical block on volume
257	myErr = hfs_bmap(myBTreeCBPtr->fileRefNum, theScanStatePtr->nodeNum,
258	                 &myDevPtr, &myPhyBlockNum, &myBlockRun);
259	if ( myErr != E_NONE )
260	{
261		goto ExitThisRoutine;
262	}
263
264	// bmap block run gives us the remaining number of valid blocks (number of blocks
265	// minus the first).  so if there are 10 valid blocks our run number will be 9.
266	// blocks, in our case is the same as nodes (both are 4K)
267	myBlocksInBufferCount = (theScanStatePtr->bufferSize / myBTreeCBPtr->nodeSize );
268	myBufferSize = theScanStatePtr->bufferSize;
269	if ( (myBlockRun + 1) < myBlocksInBufferCount )
270	{
271		myBufferSize = (myBlockRun + 1) * myBTreeCBPtr->nodeSize;
272	}
273
274	// now read blocks from the device
275	myErr = (int)buf_meta_bread(myDevPtr,
276	                       myPhyBlockNum,
277	                       myBufferSize,
278	                       NOCRED,
279	                       &theScanStatePtr->bufferPtr );
280	if ( myErr != E_NONE )
281	{
282		goto ExitThisRoutine;
283	}
284
285	theScanStatePtr->nodesLeftInBuffer = buf_count(theScanStatePtr->bufferPtr) / theScanStatePtr->btcb->nodeSize;
286	theScanStatePtr->currentNodePtr = (BTNodeDescriptor *) buf_dataptr(theScanStatePtr->bufferPtr);
287
288ExitThisRoutine:
289	return myErr;
290
291} /* ReadMultipleNodes */
292
293
294
295//_________________________________________________________________________________
296//
297//	Routine:	BTScanInitialize
298//
299//	Purpose:	Prepare to start a new BTree scan, or resume a previous one.
300//
301//	Inputs:
302//		btreeFile		The B-Tree's file control block
303//		startingNode	Initial node number
304//		startingRecord	Initial record number within node
305//		recordsFound	Number of valid records found so far
306//		bufferSize		Size (in bytes) of buffer
307//
308//	Outputs:
309//		scanState		Scanner's current state; pass to other scanner calls
310//
311//	Notes:
312//		To begin a new scan and see all records in the B-Tree, pass zeroes for
313//		startingNode, startingRecord, and recordsFound.
314//
315//		To resume a scan from the point of a previous BTScanTerminate, use the
316//		values returned by BTScanTerminate as input for startingNode, startingRecord,
317//		and recordsFound.
318//
319//		When resuming a scan, the caller should check the B-tree's write count.  If
320//		it is different from the write count when the scan was terminated, then the
321//		tree may have changed and the current state may be incorrect.  In particular,
322//		you may see some records more than once, or never see some records.  Also,
323//		the scanner may not be able to detect when all leaf records have been seen,
324//		and will have to scan through many empty nodes.
325//
326//		XXX�Perhaps the write count should be managed by BTScanInitialize and
327//		XXX BTScanTerminate?  This would avoid the caller having to peek at
328//		XXX internal B-Tree structures.
329//_________________________________________________________________________________
330
331int		BTScanInitialize(	const FCB *		btreeFile,
332							u_int32_t		startingNode,
333							u_int32_t		startingRecord,
334							u_int32_t		recordsFound,
335							u_int32_t		bufferSize,
336							BTScanState	*	scanState     )
337{
338	BTreeControlBlock	*btcb;
339
340	//
341	//	Make sure this is a valid B-Tree file
342	//
343	btcb = (BTreeControlBlock *) btreeFile->fcbBTCBPtr;
344	if (btcb == NULL)
345		return fsBTInvalidFileErr;
346
347	//
348	//	Make sure buffer size is big enough, and a multiple of the
349	//	B-Tree node size
350	//
351	if ( bufferSize < btcb->nodeSize )
352		return paramErr;
353	bufferSize = (bufferSize / btcb->nodeSize) * btcb->nodeSize;
354
355	//
356	//	Set up the scanner's state
357	//
358	scanState->bufferSize			= bufferSize;
359	scanState->bufferPtr 			= NULL;
360	scanState->btcb					= btcb;
361	scanState->nodeNum				= startingNode;
362	scanState->recordNum			= startingRecord;
363	scanState->currentNodePtr		= NULL;
364	scanState->nodesLeftInBuffer	= 0;		// no nodes currently in buffer
365	scanState->recordsFound			= recordsFound;
366	microuptime(&scanState->startTime);			// initialize our throttle
367
368	return noErr;
369
370} /* BTScanInitialize */
371
372
373//_________________________________________________________________________________
374//
375//	Routine:	BTScanTerminate
376//
377//	Purpose:	Return state information about a scan so that it can be resumed
378//				later via BTScanInitialize.
379//
380//	Inputs:
381//		scanState		Scanner's current state
382//
383//	Outputs:
384//		nextNode		Node number to resume a scan (pass to BTScanInitialize)
385//		nextRecord		Record number to resume a scan (pass to BTScanInitialize)
386//		recordsFound	Valid records seen so far (pass to BTScanInitialize)
387//_________________________________________________________________________________
388
389int	 BTScanTerminate(	BTScanState *		scanState,
390						u_int32_t *			startingNode,
391						u_int32_t *			startingRecord,
392						u_int32_t *			recordsFound	)
393{
394	*startingNode	= scanState->nodeNum;
395	*startingRecord	= scanState->recordNum;
396	*recordsFound	= scanState->recordsFound;
397
398	if ( scanState->bufferPtr != NULL )
399	{
400		buf_markinvalid(scanState->bufferPtr);
401		buf_brelse( scanState->bufferPtr );
402		scanState->bufferPtr = NULL;
403		scanState->currentNodePtr = NULL;
404	}
405
406	return noErr;
407
408} /* BTScanTerminate */
409
410
411