File: BTreeScanner.c

package info (click to toggle)
hfsprogs 332.25-11
  • links: PTS
  • area: main
  • in suites: bullseye, buster, jessie, jessie-kfreebsd, sid, stretch
  • size: 6,440 kB
  • ctags: 7,805
  • sloc: ansic: 58,120; makefile: 25
file content (329 lines) | stat: -rwxr-xr-x 9,668 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
/*
 * Copyright (c) 1996-2002, 2005 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (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.
 * 
 * This 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@
 *
 *	@(#)BTreeScanner.c
 */


#include "BTreeScanner.h"
#include "Scavenger.h"
#include "../cache.h"
#include "../fsck_hfs.h"

static int FindNextLeafNode(	BTScanState *scanState );
static int ReadMultipleNodes( 	BTScanState *scanState );


//_________________________________________________________________________________
//
//	Routine:	BTScanNextRecord
//
//	Purpose:	Return the next leaf record in a scan.
//
//	Inputs:
//		scanState		Scanner's current state
//
//	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
//
//	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,
						void * *		key,
						void * *		data,
						u_int32_t *		dataSize  )
{
	int				err;
	u_int16_t		dataSizeShort;
	int64_t			maxLeafRecs;
	
	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 );

	// btcb->leafRecords may be fragile (the B-Tree header could be damaged)
	// so in order to do a sanity check on the max number of leaf records we 
	// could have we use the catalog file's physical size divided by the smallest
	// leaf node record size to get our ceiling.
	maxLeafRecs = scanState->btcb->fcbPtr->fcbPhysicalSize / sizeof( HFSCatalogThread );

	while ( err == noErr ) 
	{ 
		//	See if we have a record in the current node
		err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr, 
								scanState->recordNum, (KeyPtr *) key, 
								(UInt8 **) data, &dataSizeShort  );
		if ( err == noErr )
		{
			++scanState->recordsFound;
			++scanState->recordNum;
			if (dataSize != NULL)
				*dataSize = dataSizeShort;
			return noErr;
		}
		
		//	We're done with the current node.  See if we've returned all the records
		if ( scanState->recordsFound >= maxLeafRecs )
			return btNotFound;

		//	Move to the first record of the next leaf node
		scanState->recordNum = 0; 
		err = FindNextLeafNode( scanState );
	}
	
	//
	//	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
//
//	Result:
//		noErr			Found a valid record
//		fsEndOfIterationErr	No more nodes in file
//_________________________________________________________________________________

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

			scanState->currentNodePtr = (BTNodeDescriptor *)((UInt8 *)scanState->currentNodePtr + scanState->btcb->nodeSize);
		}
		
        // need to manufacture a BlockDescriptor since hfs_swap_BTNode expects one as input
        myBlockDescriptor.buffer = (void *) scanState->currentNodePtr;
        myBlockDescriptor.blockHeader = NULL;
        myBlockDescriptor.blockNum = scanState->nodeNum;
        myBlockDescriptor.blockSize = scanState->btcb->nodeSize;
        myBlockDescriptor.blockReadFromDisk = false;
        myBlockDescriptor.fragmented = false;
        err = hfs_swap_BTNode(&myBlockDescriptor, scanState->btcb->fcbPtr, kSwapBTNodeBigToHost);
		if ( err != noErr )
		{
			err = noErr;
			continue;
		}
		
		// NOTE - todo - add less lame sanity check to allow leaf nodes that
		// only have damaged kind. 
		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
//_________________________________________________________________________________

int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf);

static int ReadMultipleNodes( BTScanState *theScanStatePtr )
{
	int						myErr = noErr;
	BTreeControlBlockPtr  	myBTreeCBPtr;
	UInt64					myPhyBlockNum;
	SInt64  				myPhyOffset;
	UInt64					mySectorOffset; // offset within file (in 512-byte sectors)
	UInt32					myContiguousBytes;
	
	myBTreeCBPtr = theScanStatePtr->btcb;
			
	// map logical block in catalog btree file to physical block on volume
	mySectorOffset = 
		(((UInt64)theScanStatePtr->nodeNum * (UInt64)myBTreeCBPtr->fcbPtr->fcbBlockSize) >> kSectorShift);
	myErr = MapFileBlockC( myBTreeCBPtr->fcbPtr->fcbVolume, myBTreeCBPtr->fcbPtr,
						   theScanStatePtr->bufferSize, mySectorOffset, 
						   &myPhyBlockNum, &myContiguousBytes );
	if ( myErr != noErr )
	{
		myErr = fsEndOfIterationErr;
		goto ExitThisRoutine;
	}
	
	// now read blocks from the device 
	myPhyOffset = (SInt64) ( ( (UInt64) myPhyBlockNum ) << kSectorShift );
	myErr = CacheRawRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, 
						  myPhyOffset, myContiguousBytes, theScanStatePtr->bufferPtr );
	if ( myErr != noErr )
	{
		myErr = fsEndOfIterationErr;
		goto ExitThisRoutine;
	}

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

ExitThisRoutine:
	return myErr;
	
} /* ReadMultipleNodes */


//_________________________________________________________________________________
//
//	Routine:	BTScanInitialize
//
//	Purpose:	Prepare to start a new BTree scan.
//
//	Inputs:
//		btreeFile		The B-Tree's file control block
//
//	Outputs:
//		scanState		Scanner's current state; pass to other scanner calls
//
//_________________________________________________________________________________

int		BTScanInitialize(	const SFCB *	btreeFile,
							BTScanState	*	scanState     )
{
	BTreeControlBlock	*btcb;
	u_int32_t			bufferSize;
	
	//
	//	Make sure this is a valid B-Tree file
	//
	btcb = (BTreeControlBlock *) btreeFile->fcbBtree;
	if (btcb == NULL)
		return R_RdErr;
	
	//
	//	Make sure buffer size is big enough, and a multiple of the
	//	B-Tree node size
	//
	bufferSize = (kCatScanBufferSize / btcb->nodeSize) * btcb->nodeSize;

	//
	//	Set up the scanner's state
	//
	scanState->bufferSize			= bufferSize;
	scanState->bufferPtr = (void *) AllocateMemory( bufferSize );
	if ( scanState->bufferPtr == NULL )
		return( R_NoMem );

	scanState->btcb					= btcb;
	scanState->nodeNum				= 0;
	scanState->recordNum			= 0;
	scanState->currentNodePtr		= NULL;
	scanState->nodesLeftInBuffer	= 0;		// no nodes currently in buffer
	scanState->recordsFound			= 0;
		
	return noErr;
	
} /* BTScanInitialize */


//_________________________________________________________________________________
//
//	Routine:	BTScanTerminate
//
//	Purpose:	Return state information about a scan so that it can be resumed
//				later via BTScanInitialize.
//
//	Inputs:
//		scanState		Scanner's current state
//
//	Outputs:
//		nextNode		Node number to resume a scan (pass to BTScanInitialize)
//		nextRecord		Record number to resume a scan (pass to BTScanInitialize)
//		recordsFound	Valid records seen so far (pass to BTScanInitialize)
//_________________________________________________________________________________

int	 BTScanTerminate(	BTScanState *		scanState	)
{
	if ( scanState->bufferPtr != NULL )
	{
		DisposeMemory( scanState->bufferPtr );
		scanState->bufferPtr = NULL;
		scanState->currentNodePtr = NULL;
	}
	
	return noErr;
	
} /* BTScanTerminate */