1/*
2 * Copyright (c) 1996-2002, 2005, 2012 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_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. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 *
23 *	@(#)BTreeScanner.c
24 */
25
26
27#include "BTreeScanner.h"
28#include "Scavenger.h"
29#include "../cache.h"
30#include "../fsck_hfs.h"
31
32static int FindNextLeafNode(	BTScanState *scanState );
33static int ReadMultipleNodes( 	BTScanState *scanState );
34
35
36//_________________________________________________________________________________
37//
38//	Routine:	BTScanNextRecord
39//
40//	Purpose:	Return the next leaf record in a scan.
41//
42//	Inputs:
43//		scanState		Scanner's current state
44//
45//	Outputs:
46//		key				Key of found record (points into buffer)
47//		data			Data of found record (points into buffer)
48//		dataSize		Size of data in found record
49//
50//	Result:
51//		noErr			Found a valid record
52//		btNotFound		No more records
53//
54//	Notes:
55//		This routine returns pointers to the found record's key and data.  It
56//		does not copy the key or data to a caller-supplied buffer (like
57//		GetBTreeRecord would).  The caller must not modify the key or data.
58//_________________________________________________________________________________
59
60int BTScanNextRecord(	BTScanState *	scanState,
61						void * *		key,
62						void * *		data,
63						u_int32_t *		dataSize  )
64{
65	int				err;
66	u_int16_t		dataSizeShort;
67	int64_t			maxLeafRecs;
68
69	err = noErr;
70
71	//
72	//	If this is the first call, there won't be any nodes in the buffer, so go
73	//	find the first first leaf node (if any).
74	//
75	if ( scanState->nodesLeftInBuffer <= 0 )
76		err = FindNextLeafNode( scanState );
77
78	// btcb->leafRecords may be fragile (the B-Tree header could be damaged)
79	// so in order to do a sanity check on the max number of leaf records we
80	// could have we use the catalog file's physical size divided by the smallest
81	// leaf node record size to get our ceiling.
82	maxLeafRecs = scanState->btcb->fcbPtr->fcbPhysicalSize / sizeof( HFSCatalogThread );
83
84	while ( err == noErr )
85	{
86		//	See if we have a record in the current node
87		err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr,
88								scanState->recordNum, (KeyPtr *) key,
89								(UInt8 **) data, &dataSizeShort  );
90		if ( err == noErr )
91		{
92			++scanState->recordsFound;
93			++scanState->recordNum;
94			if (dataSize != NULL)
95				*dataSize = dataSizeShort;
96			return noErr;
97		}
98
99		//	We're done with the current node.  See if we've returned all the records
100		if ( scanState->recordsFound >= maxLeafRecs )
101			return btNotFound;
102
103		//	Move to the first record of the next leaf node
104		scanState->recordNum = 0;
105		err = FindNextLeafNode( scanState );
106	}
107
108	//
109	//	If we got an EOF error from FindNextLeafNode, then there are no more leaf
110	//	records to be found.
111	//
112	if ( err == fsEndOfIterationErr )
113		err = btNotFound;
114
115	return err;
116
117} /* BTScanNextRecord */
118
119
120//_________________________________________________________________________________
121//
122//	Routine:	FindNextLeafNode
123//
124//	Purpose:	Point to the next leaf node in the buffer.  Read more nodes
125//				into the buffer if needed (and allowed).
126//
127//	Inputs:
128//		scanState		Scanner's current state
129//
130//	Result:
131//		noErr			Found a valid record
132//		fsEndOfIterationErr	No more nodes in file
133//_________________________________________________________________________________
134
135static int FindNextLeafNode(	BTScanState *scanState )
136{
137	int					err;
138    BlockDescriptor		myBlockDescriptor;
139
140	err = noErr;		// Assume everything will be OK
141
142	while ( 1 )
143	{
144		++scanState->nodeNum;
145		--scanState->nodesLeftInBuffer;
146		if ( scanState->nodesLeftInBuffer <= 0 )
147		{
148			//	read some more nodes into buffer
149			err = ReadMultipleNodes( scanState );
150			if ( err != noErr )
151				break;
152		}
153		else
154		{
155			//	Adjust to point to the next node in the buffer
156
157			//	If we've looked at all nodes in the tree, then we're done
158			if ( scanState->nodeNum >= scanState->btcb->totalNodes )
159				return fsEndOfIterationErr;
160
161			scanState->currentNodePtr = (BTNodeDescriptor *)((UInt8 *)scanState->currentNodePtr + scanState->btcb->nodeSize);
162		}
163
164        // need to manufacture a BlockDescriptor since hfs_swap_BTNode expects one as input
165        myBlockDescriptor.buffer = (void *) scanState->currentNodePtr;
166        myBlockDescriptor.blockHeader = NULL;
167        myBlockDescriptor.blockNum = scanState->nodeNum;
168        myBlockDescriptor.blockSize = scanState->btcb->nodeSize;
169        myBlockDescriptor.blockReadFromDisk = false;
170        myBlockDescriptor.fragmented = false;
171        err = hfs_swap_BTNode(&myBlockDescriptor, scanState->btcb->fcbPtr, kSwapBTNodeBigToHost);
172		if ( err != noErr )
173		{
174			err = noErr;
175			continue;
176		}
177
178		// NOTE - todo - add less lame sanity check to allow leaf nodes that
179		// only have damaged kind.
180		if ( scanState->currentNodePtr->kind == kBTLeafNode )
181			break;
182	}
183
184	return err;
185
186} /* FindNextLeafNode */
187
188
189//_________________________________________________________________________________
190//
191//	Routine:	ReadMultipleNodes
192//
193//	Purpose:	Read one or more nodes into the buffer.
194//
195//	Inputs:
196//		theScanStatePtr		Scanner's current state
197//
198//	Result:
199//		noErr				One or nodes were read
200//		fsEndOfIterationErr		No nodes left in file, none in buffer
201//_________________________________________________________________________________
202
203int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf);
204
205static int ReadMultipleNodes( BTScanState *theScanStatePtr )
206{
207	int						myErr = noErr;
208	BTreeControlBlockPtr  	myBTreeCBPtr;
209	UInt64					myPhyBlockNum;
210	SInt64  				myPhyOffset;
211	UInt64					mySectorOffset; // offset within file (in 512-byte sectors)
212	UInt32					myContiguousBytes;
213
214	myBTreeCBPtr = theScanStatePtr->btcb;
215
216	// map logical block in catalog btree file to physical block on volume
217	mySectorOffset =
218		(((UInt64)theScanStatePtr->nodeNum * (UInt64)myBTreeCBPtr->fcbPtr->fcbBlockSize) >> kSectorShift);
219	myErr = MapFileBlockC( myBTreeCBPtr->fcbPtr->fcbVolume, myBTreeCBPtr->fcbPtr,
220						   theScanStatePtr->bufferSize, mySectorOffset,
221						   &myPhyBlockNum, &myContiguousBytes );
222	if ( myErr != noErr )
223	{
224		myErr = fsEndOfIterationErr;
225		goto ExitThisRoutine;
226	}
227
228	// now read blocks from the device
229	myPhyOffset = (SInt64) ( ( (UInt64) myPhyBlockNum ) << kSectorShift );
230
231	// Go through the cache, so we can get any locked-in journal changes
232	Buf_t *tmpbuf = NULL;
233
234	myErr = CacheRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache,
235			   myPhyOffset, myContiguousBytes, &tmpbuf );
236
237	if ( myErr == noErr )
238	{
239		if (tmpbuf)
240		{
241			if (tmpbuf->Length < myContiguousBytes)
242				abort();
243			memcpy(theScanStatePtr->bufferPtr, tmpbuf->Buffer, myContiguousBytes);
244			CacheRelease(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, tmpbuf, 0);
245		} else
246			abort();
247#if DEBUG_BTREE
248		/*
249		 * This code was written to help debug a cache problem, where CacheRead()
250		 * was returning different results than CacheRawRead().  I am leaving it
251		 * around because I fear that will happen again, so it can be used for
252		 * reference, rather than rewrite it then.
253		 */
254		size_t tempBufferSize = myContiguousBytes;
255		int tempError;
256		unsigned char *tempBuffer = malloc(myContiguousBytes);
257		if (tempBuffer == NULL)
258			abort();
259		tempError = CacheRawRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache,
260				      myPhyOffset, myContiguousBytes, tempBuffer);
261		if (memcmp(tempBuffer, theScanStatePtr->bufferPtr, myContiguousBytes) != 0)
262		{
263			uint8_t *raw, *cached;
264			fprintf(stderr, "CacheRead and CacheRawRead returned different values\n");
265			fprintf(stderr, "\tmyPhyOffset = %llu, myContiguousBytes = %u\n", myPhyOffset, myContiguousBytes);
266			size_t i = 0;
267			for (i = 0; i < myContiguousBytes; i++)
268			{
269				cached = ((uint8_t*)theScanStatePtr->bufferPtr)[i];
270				raw = tempBuffer[i];
271				if (cached != raw)
272				{
273					fprintf(stderr, "\tOffset %zu:  cached value = 0x%02x, raw value = 0x%02x\n", i, cached, raw);
274					break;
275				}
276			}
277			extern void dumpCache(void*);
278			dumpCache(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache);
279			abort();
280		}
281		free(tempBuffer);
282#endif
283	}
284
285
286
287	if ( myErr != noErr )
288	{
289		myErr = fsEndOfIterationErr;
290		goto ExitThisRoutine;
291	}
292
293	theScanStatePtr->nodesLeftInBuffer = myContiguousBytes /
294		theScanStatePtr->btcb->nodeSize;
295	theScanStatePtr->currentNodePtr = (BTNodeDescriptor *) theScanStatePtr->bufferPtr;
296
297ExitThisRoutine:
298	return myErr;
299
300} /* ReadMultipleNodes */
301
302
303//_________________________________________________________________________________
304//
305//	Routine:	BTScanInitialize
306//
307//	Purpose:	Prepare to start a new BTree scan.
308//
309//	Inputs:
310//		btreeFile		The B-Tree's file control block
311//
312//	Outputs:
313//		scanState		Scanner's current state; pass to other scanner calls
314//
315//_________________________________________________________________________________
316
317int		BTScanInitialize(	const SFCB *	btreeFile,
318							BTScanState	*	scanState     )
319{
320	BTreeControlBlock	*btcb;
321	u_int32_t			bufferSize;
322
323	//
324	//	Make sure this is a valid B-Tree file
325	//
326	btcb = (BTreeControlBlock *) btreeFile->fcbBtree;
327	if (btcb == NULL)
328		return R_RdErr;
329
330	//
331	//	Make sure buffer size is big enough, and a multiple of the
332	//	B-Tree node size
333	//
334	bufferSize = (kCatScanBufferSize / btcb->nodeSize) * btcb->nodeSize;
335
336	//
337	//	Set up the scanner's state
338	//
339	scanState->bufferSize			= bufferSize;
340	scanState->bufferPtr = (void *) AllocateMemory( bufferSize );
341	if ( scanState->bufferPtr == NULL )
342		return( R_NoMem );
343
344	scanState->btcb					= btcb;
345	scanState->nodeNum				= 0;
346	scanState->recordNum			= 0;
347	scanState->currentNodePtr		= NULL;
348	scanState->nodesLeftInBuffer	= 0;		// no nodes currently in buffer
349	scanState->recordsFound			= 0;
350
351	return noErr;
352
353} /* BTScanInitialize */
354
355
356//_________________________________________________________________________________
357//
358//	Routine:	BTScanTerminate
359//
360//	Purpose:	Return state information about a scan so that it can be resumed
361//				later via BTScanInitialize.
362//
363//	Inputs:
364//		scanState		Scanner's current state
365//
366//	Outputs:
367//		nextNode		Node number to resume a scan (pass to BTScanInitialize)
368//		nextRecord		Record number to resume a scan (pass to BTScanInitialize)
369//		recordsFound	Valid records seen so far (pass to BTScanInitialize)
370//_________________________________________________________________________________
371
372int	 BTScanTerminate(	BTScanState *		scanState	)
373{
374	if ( scanState->bufferPtr != NULL )
375	{
376		DisposeMemory( scanState->bufferPtr );
377		scanState->bufferPtr = NULL;
378		scanState->currentNodePtr = NULL;
379	}
380
381	return noErr;
382
383} /* BTScanTerminate */
384
385
386