]> git.saurik.com Git - apple/hfs.git/blob - fsck_hfs/dfalib/SRebuildBTree.c
projects / apple / hfs.git / blob
? search:


79ef408da072b9ed987f4157e9d06d4dfef29c23
[apple/hfs.git] / fsck_hfs / dfalib / SRebuildBTree.c
1 /*
2 * Copyright (c) 2002-2005, 2007-2009 Apple 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 /*
24 File: SRebuildBTree.c
25
26 Contains: This file contains BTree rebuilding code.
27
28 Written by: Jerry Cottingham
29
30 Copyright: © 1986, 1990, 1992-2002 by Apple Computer, Inc., all rights reserved.
31
32 */
33
34 #define SHOW_ELAPSED_TIMES 0
35 #define DEBUG_REBUILD 1
36
37 extern void MyIndirectLog(const char *);
38
39 #if SHOW_ELAPSED_TIMES
40 #include <sys/time.h>
41 #endif
42
43 #include "Scavenger.h"
44 #include "../cache.h"
45
46 /* internal routine prototypes */
47
48 /*static*/ OSErr CreateNewBTree( SGlobPtr theSGlobPtr, int FileID );
49 static OSErr DeleteBTree( SGlobPtr theSGlobPtr, SFCB * theFCBPtr );
50 static OSErr InitializeBTree( BTreeControlBlock * theBTreeCBPtr,
51 UInt32 * theBytesUsedPtr,
52 UInt32 * theMapNodeCountPtr );
53 static OSErr ReleaseExtentsInExtentsBTree( SGlobPtr theSGlobPtr,
54 SFCB * theFCBPtr );
55 static OSErr ValidateCatalogRecordLength( SGlobPtr theSGlobPtr,
56 CatalogRecord * theRecPtr,
57 UInt32 theRecSize );
58 static OSErr ValidateAttributeRecordLength (SGlobPtr s, HFSPlusAttrRecord * theRecPtr, UInt32 theRecSize);
59 static OSErr ValidateExtentRecordLength (SGlobPtr s, ExtentRecord * theRecPtr, UInt32 theRecSize);
60 static OSErr WriteMapNodes( BTreeControlBlock * theBTreeCBPtr,
61 UInt32 theFirstMapNode,
62 UInt32 theNodeCount );
63
64 #if DEBUG_REBUILD
65 static void PrintBTHeaderRec( BTHeaderRec * thePtr );
66 static void PrintNodeDescriptor( NodeDescPtr thePtr );
67 static void PrintBTreeKey( KeyPtr thePtr, BTreeControlBlock * theBTreeCBPtr );
68 static void PrintBTreeData(void *data, UInt32 length);
69 static void PrintIndexNodeRec( UInt32 theNodeNum );
70 static void PrintLeafNodeRec( HFSPlusCatalogFolder * thePtr );
71 #endif
72
73 void SETOFFSET ( void *buffer, UInt16 btNodeSize, SInt16 recOffset, SInt16 vecOffset );
74 #define SETOFFSET( buf,ndsiz,offset,rec ) \
75 ( *(SInt16 *)((UInt8 *)(buf) + (ndsiz) + (-2 * (rec))) = (offset) )
76
77
78 //_________________________________________________________________________________
79 //
80 // Routine: RebuildBTree
81 //
82 // Purpose: Attempt to rebuild a B-Tree file using an existing B-Tree
83 // file. When successful a new BT-ree file will exist and
84 // the old one will be deleted. The MDB an alternate MDB
85 // will be updated to point to the new file.
86 //
87 // The tree is rebuilt by walking through every record. We use
88 // BTScanNextRecord(), which iterates sequentially through the
89 // nodes in the tree (starting at the first node), and extracts
90 // each record from each leaf node. It does not use the node
91 // forward or backward links; this allows it to rebuild the tree
92 // when the index nodes are non-reliable, or the leaf node links
93 // are damaged.
94 //
95 // The rebuild will be aborted (leaving the existing btree
96 // as it was found) if there are errors retreiving the nodes or
97 // records, or if there are errors inserting the records into
98 // the new tree.
99 //
100 // Inputs:
101 // SGlobPtr->calculatedCatalogBTCB or SGlobPtr->calculatedAttributesBTCB
102 // need this as a model and in order to extract leaf records.
103 // SGlobPtr->calculatedCatalogFCB or SGlobPtr->calculatedAttributesFCB
104 // need this as a model and in order to extract leaf records.
105 // SGlobPtr->calculatedRepairFCB
106 // pointer to our repair FCB.
107 // SGlobPtr->calculatedRepairBTCB
108 // pointer to our repair BTreeControlBlock.
109 //
110 // Outputs:
111 // SGlobPtr->calculatedVCB
112 // this will get mostly filled in here. On input it is not fully
113 // set up.
114 // SGlobPtr->calculatedCatalogFCB or SGlobPtr->calculatedAttributesFCB
115 // tis will refer to the new catalog file.
116 //
117 // Result:
118 // various error codes when problem occur or noErr if rebuild completed
119 //
120 // to do:
121 // have an option where we get back what we can.
122 //
123 // Notes:
124 // - requires input BTCB and FCBs to be valid!
125 //_________________________________________________________________________________
126
127 OSErr RebuildBTree( SGlobPtr theSGlobPtr, int FileID )
128 {
129 BlockDescriptor myBlockDescriptor;
130 BTreeKeyPtr myCurrentKeyPtr;
131 void * myCurrentDataPtr;
132 SFCB * myFCBPtr = NULL;
133 SFCB * oldFCBPtr = NULL;
134 SVCB * myVCBPtr;
135 UInt32 myDataSize;
136 UInt32 myHint;
137 OSErr myErr;
138 Boolean isHFSPlus;
139 UInt32 numRecords = 0;
140
141 #if SHOW_ELAPSED_TIMES
142 struct timeval myStartTime;
143 struct timeval myEndTime;
144 struct timeval myElapsedTime;
145 struct timezone zone;
146 #endif
147
148 theSGlobPtr->TarID = FileID;
149 theSGlobPtr->TarBlock = 0;
150 myBlockDescriptor.buffer = NULL;
151 myVCBPtr = theSGlobPtr->calculatedVCB;
152 if (kHFSCatalogFileID == FileID) {
153 oldFCBPtr = theSGlobPtr->calculatedCatalogFCB;
154 } else if (kHFSAttributesFileID == FileID) {
155 oldFCBPtr = theSGlobPtr->calculatedAttributesFCB;
156 /*
157 * 12447845
158 * If we don't have an attributes btree, then we should just
159 * quit now -- nothing to rebuild.
160 */
161 if (oldFCBPtr->fcbLogicalSize == 0) {
162 if (debug)
163 plog("Requested attributes btree rebuild, but attributes file size is 0\n");
164 myErr = 0;
165 goto ExitThisRoutine;
166 }
167 } else if (kHFSExtentsFileID == FileID) {
168 oldFCBPtr = theSGlobPtr->calculatedExtentsFCB;
169 } else {
170 abort();
171 }
172
173 myErr = BTScanInitialize( oldFCBPtr, &theSGlobPtr->scanState );
174 if ( noErr != myErr )
175 goto ExitThisRoutine;
176
177 // some VCB fields that we need may not have been calculated so we get it from the MDB.
178 // this can happen because the fsck_hfs code path to fully set up the VCB may have been
179 // aborted if an error was found that would trigger a rebuild. For example,
180 // if a leaf record was found to have a keys out of order then the verify phase of the
181 // B-Tree check would be aborted and we would come directly (if allowable) to here.
182 isHFSPlus = ( myVCBPtr->vcbSignature == kHFSPlusSigWord );
183
184 if (!isHFSPlus) {
185 myErr = noMacDskErr;
186 goto ExitThisRoutine;
187 }
188
189 myErr = GetVolumeObjectVHBorMDB( &myBlockDescriptor );
190 if ( noErr != myErr )
191 goto ExitThisRoutine;
192
193 if ( isHFSPlus )
194 {
195 HFSPlusVolumeHeader * myVHBPtr;
196
197 myVHBPtr = (HFSPlusVolumeHeader *) myBlockDescriptor.buffer;
198 myVCBPtr->vcbFreeBlocks = myVHBPtr->freeBlocks;
199 myVCBPtr->vcbFileCount = myVHBPtr->fileCount;
200 myVCBPtr->vcbFolderCount = myVHBPtr->folderCount;
201 myVCBPtr->vcbEncodingsBitmap = myVHBPtr->encodingsBitmap;
202 myVCBPtr->vcbRsrcClumpSize = myVHBPtr->rsrcClumpSize;
203 myVCBPtr->vcbDataClumpSize = myVHBPtr->dataClumpSize;
204
205 // check out creation and last mod dates
206 myVCBPtr->vcbCreateDate = myVHBPtr->createDate;
207 myVCBPtr->vcbModifyDate = myVHBPtr->modifyDate;
208 myVCBPtr->vcbCheckedDate = myVHBPtr->checkedDate;
209 myVCBPtr->vcbBackupDate = myVHBPtr->backupDate;
210 myVCBPtr->vcbCatalogFile->fcbClumpSize = myVHBPtr->catalogFile.clumpSize;
211 if (myVCBPtr->vcbAttributesFile != NULL) {
212 myVCBPtr->vcbAttributesFile->fcbClumpSize = myVHBPtr->attributesFile.clumpSize;
213 }
214 myVCBPtr->vcbExtentsFile->fcbClumpSize = myVHBPtr->extentsFile.clumpSize;
215
216 // 3882639: Removed check for volume attributes in HFS Plus
217 myVCBPtr->vcbAttributes = myVHBPtr->attributes;
218
219 CopyMemory( myVHBPtr->finderInfo, myVCBPtr->vcbFinderInfo, sizeof(myVCBPtr->vcbFinderInfo) );
220 }
221 else
222 {
223 HFSMasterDirectoryBlock * myMDBPtr;
224 myMDBPtr = (HFSMasterDirectoryBlock *) myBlockDescriptor.buffer;
225 myVCBPtr->vcbFreeBlocks = myMDBPtr->drFreeBks;
226 myVCBPtr->vcbFileCount = myMDBPtr->drFilCnt;
227 myVCBPtr->vcbFolderCount = myMDBPtr->drDirCnt;
228 myVCBPtr->vcbDataClumpSize = myMDBPtr->drClpSiz;
229 myVCBPtr->vcbCatalogFile->fcbClumpSize = myMDBPtr->drCTClpSiz;
230 myVCBPtr->vcbNmRtDirs = myMDBPtr->drNmRtDirs;
231
232 // check out creation and last mod dates
233 myVCBPtr->vcbCreateDate = myMDBPtr->drCrDate;
234 myVCBPtr->vcbModifyDate = myMDBPtr->drLsMod;
235
236 // verify volume attribute flags
237 if ( (myMDBPtr->drAtrb & VAtrb_Msk) == 0 )
238 myVCBPtr->vcbAttributes = myMDBPtr->drAtrb;
239 else
240 myVCBPtr->vcbAttributes = VAtrb_DFlt;
241 myVCBPtr->vcbBackupDate = myMDBPtr->drVolBkUp;
242 myVCBPtr->vcbVSeqNum = myMDBPtr->drVSeqNum;
243 CopyMemory( myMDBPtr->drFndrInfo, myVCBPtr->vcbFinderInfo, sizeof(myMDBPtr->drFndrInfo) );
244 }
245 (void) ReleaseVolumeBlock( myVCBPtr, &myBlockDescriptor, kReleaseBlock );
246 myBlockDescriptor.buffer = NULL;
247
248 // create the new BTree file
249 if (FileID == kHFSCatalogFileID || FileID == kHFSAttributesFileID || FileID == kHFSExtentsFileID) {
250 myErr = CreateNewBTree( theSGlobPtr, FileID );
251 } else {
252 myErr = EINVAL;
253 }
254 if ( noErr != myErr ) {
255 #if DEBUG_REBUILD
256 plog("CreateNewBTree returned %d\n", myErr);
257 #endif
258 if (myErr == dskFulErr) {
259 fsckPrint(theSGlobPtr->context, E_DiskFull);
260 }
261 goto ExitThisRoutine;
262 }
263 myFCBPtr = theSGlobPtr->calculatedRepairFCB;
264
265 #if SHOW_ELAPSED_TIMES
266 gettimeofday( &myStartTime, &zone );
267 #endif
268
269 #if DEBUG_REBUILD
270 if (debug) {
271 int i;
272 HFSPlusExtentDescriptor *te = (HFSPlusExtentDescriptor*)&theSGlobPtr->calculatedRepairFCB->fcbExtents32;
273 printf("Extent records for rebuilt file %u:\n", FileID);
274 for (i = 0; i < kHFSPlusExtentDensity; i++) {
275 printf("\t[ %u, %u ]\n", te[i].startBlock, te[i].blockCount);
276 }
277 }
278 #endif
279
280 while ( true )
281 {
282 /* scan the btree for leaf records */
283 myErr = BTScanNextRecord( &theSGlobPtr->scanState,
284 (void **) &myCurrentKeyPtr,
285 (void **) &myCurrentDataPtr,
286 &myDataSize );
287 if ( noErr != myErr )
288 break;
289
290 /* do some validation on the record */
291 theSGlobPtr->TarBlock = theSGlobPtr->scanState.nodeNum;
292 if (FileID == kHFSCatalogFileID) {
293 myErr = ValidateCatalogRecordLength( theSGlobPtr, myCurrentDataPtr, myDataSize );
294 } else if (FileID == kHFSAttributesFileID) {
295 myErr = ValidateAttributeRecordLength( theSGlobPtr, myCurrentDataPtr, myDataSize );
296 } else if (FileID == kHFSExtentsFileID) {
297 myErr = ValidateExtentRecordLength( theSGlobPtr, myCurrentDataPtr, myDataSize );
298 }
299 if ( noErr != myErr )
300 {
301 #if DEBUG_REBUILD
302 {
303 plog( "%s - Record length validation (file %d) failed! \n", __FUNCTION__, FileID );
304 plog( "%s - record %d in node %d is not recoverable. \n",
305 __FUNCTION__, (theSGlobPtr->scanState.recordNum - 1),
306 theSGlobPtr->scanState.nodeNum );
307 }
308 #endif
309 myErr = R_RFail;
310 break; // this implementation does not handle partial rebuilds (all or none)
311 }
312
313 /* insert this record into the new btree file */
314 myErr = InsertBTreeRecord( myFCBPtr, myCurrentKeyPtr,
315 myCurrentDataPtr, myDataSize, &myHint );
316 if ( noErr != myErr )
317 {
318 #if DEBUG_REBUILD
319 {
320 plog( "%s - InsertBTreeRecord failed with err %d 0x%02X \n",
321 __FUNCTION__, myErr, myErr );
322 plog( "%s - numRecords = %d\n", __FUNCTION__, numRecords);
323 plog( "%s - record %d in node %d is not recoverable. \n",
324 __FUNCTION__, (theSGlobPtr->scanState.recordNum - 1),
325 theSGlobPtr->scanState.nodeNum );
326 PrintBTreeKey( myCurrentKeyPtr, theSGlobPtr->calculatedCatalogBTCB );
327 PrintBTreeData( myCurrentDataPtr, myDataSize );
328 }
329 if (myErr == btExists)
330 continue;
331 #endif
332 if (dskFulErr == myErr)
333 {
334 fsckPrint(theSGlobPtr->context, E_DiskFull);
335 }
336 myErr = R_RFail;
337 break; // this implementation does not handle partial rebuilds (all or none)
338 }
339 numRecords++;
340 #if DEBUG_REBUILD
341 if (debug && ((numRecords % 1000) == 0))
342 plog("btree file %d: %u records\n", FileID, numRecords);
343 #endif
344 }
345
346 #if SHOW_ELAPSED_TIMES
347 gettimeofday( &myEndTime, &zone );
348 timersub( &myEndTime, &myStartTime, &myElapsedTime );
349 plog( "\n%s - rebuild btree %u %u records elapsed time \n", __FUNCTION__, FileID, numRecords );
350 plog( ">>>>>>>>>>>>> secs %d msecs %d \n\n", myElapsedTime.tv_sec, myElapsedTime.tv_usec );
351 #endif
352
353 if ( btNotFound == myErr )
354 myErr = noErr;
355 if ( noErr != myErr )
356 goto ExitThisRoutine;
357
358 /* update our header node on disk from our BTreeControlBlock */
359 myErr = BTFlushPath( myFCBPtr );
360 if ( noErr != myErr )
361 goto ExitThisRoutine;
362 myErr = CacheFlush( myVCBPtr->vcbBlockCache );
363 if ( noErr != myErr )
364 goto ExitThisRoutine;
365
366 /* switch old file with our new one */
367 if (FileID == kHFSCatalogFileID) {
368 theSGlobPtr->calculatedRepairFCB = theSGlobPtr->calculatedCatalogFCB;
369 theSGlobPtr->calculatedCatalogFCB = myFCBPtr;
370 myVCBPtr->vcbCatalogFile = myFCBPtr;
371 theSGlobPtr->calculatedCatalogFCB->fcbFileID = kHFSCatalogFileID;
372 theSGlobPtr->calculatedRepairBTCB = theSGlobPtr->calculatedCatalogBTCB;
373 } else if (FileID == kHFSAttributesFileID) {
374 theSGlobPtr->calculatedRepairFCB = theSGlobPtr->calculatedAttributesFCB;
375 theSGlobPtr->calculatedAttributesFCB = myFCBPtr;
376 myVCBPtr->vcbAttributesFile = myFCBPtr;
377 if (theSGlobPtr->calculatedAttributesFCB == NULL) {
378 if (debug) {
379 plog("Can't rebuilt attributes btree when there is no attributes file\n");
380 }
381 myErr = noErr;
382 goto ExitThisRoutine;
383 }
384 theSGlobPtr->calculatedAttributesFCB->fcbFileID = kHFSAttributesFileID;
385 theSGlobPtr->calculatedRepairBTCB = theSGlobPtr->calculatedAttributesBTCB;
386 } else if (FileID == kHFSExtentsFileID) {
387 theSGlobPtr->calculatedRepairFCB = theSGlobPtr->calculatedExtentsFCB;
388 theSGlobPtr->calculatedExtentsFCB = myFCBPtr;
389 myVCBPtr->vcbExtentsFile = myFCBPtr;
390 theSGlobPtr->calculatedExtentsFCB->fcbFileID = kHFSExtentsFileID;
391 theSGlobPtr->calculatedRepairBTCB = theSGlobPtr->calculatedExtentsBTCB;
392 }
393
394 // todo - add code to allow new btree file to be allocated in extents.
395 // Note when we do allow this the swap of btree files gets even more
396 // tricky since extent record key contains the file ID. The rebuilt
397 // file has file ID kHFSCatalogFileID/kHFSCatalogFileID when it is created.
398
399 MarkVCBDirty( myVCBPtr );
400 myErr = FlushAlternateVolumeControlBlock( myVCBPtr, isHFSPlus );
401 if ( noErr != myErr )
402 {
403 // we may be totally screwed if we get here, try to recover
404 if (FileID == kHFSCatalogFileID) {
405 theSGlobPtr->calculatedCatalogFCB = theSGlobPtr->calculatedRepairFCB;
406 theSGlobPtr->calculatedRepairFCB = myFCBPtr;
407 myVCBPtr->vcbCatalogFile = theSGlobPtr->calculatedCatalogFCB;
408 } else if (FileID == kHFSAttributesFileID) {
409 theSGlobPtr->calculatedAttributesFCB = theSGlobPtr->calculatedRepairFCB;
410 theSGlobPtr->calculatedRepairFCB = myFCBPtr;
411 myVCBPtr->vcbAttributesFile = theSGlobPtr->calculatedAttributesFCB;
412 } else if (FileID == kHFSExtentsFileID) {
413 theSGlobPtr->calculatedExtentsFCB = theSGlobPtr->calculatedRepairFCB;
414 theSGlobPtr->calculatedRepairFCB = myFCBPtr;
415 myVCBPtr->vcbExtentsFile = theSGlobPtr->calculatedExtentsFCB;
416 }
417 MarkVCBDirty( myVCBPtr );
418 (void) FlushAlternateVolumeControlBlock( myVCBPtr, isHFSPlus );
419 goto ExitThisRoutine;
420 }
421
422 /* release space occupied by old BTree file */
423 (void) DeleteBTree( theSGlobPtr, theSGlobPtr->calculatedRepairFCB );
424 if (FileID == kHFSExtentsFileID)
425 (void)FlushExtentFile(myVCBPtr);
426
427 ExitThisRoutine:
428 if ( myBlockDescriptor.buffer != NULL )
429 (void) ReleaseVolumeBlock( myVCBPtr, &myBlockDescriptor, kReleaseBlock );
430
431 if ( myErr != noErr && myFCBPtr != NULL )
432 (void) DeleteBTree( theSGlobPtr, myFCBPtr );
433 BTScanTerminate( &theSGlobPtr->scanState );
434
435 return( myErr );
436
437 } /* RebuildBTree */
438
439 //_________________________________________________________________________________
440 //
441 // Routine: CreateNewBTree
442 //
443 // Purpose: Create and Initialize a new B-Tree on the target volume
444 // using the physical size of the old (being rebuilt) file as an initial
445 // size.
446 //
447 // NOTES: we force this to be contiguous in order to get this into Jaguar.
448 // Allowing the new file to go into extents makes the swap
449 // of the old and new files complicated. The extent records
450 // are keyed by file ID and the new (rebuilt) btree file starts out as
451 // file Id kHFSCatalogFileID/kHFSCatalogFileID/kHFSCatalogFileID.
452 // If there were extents then we would have to fix up the extent records in the extent B-Tree.
453 //
454 // todo: Don't force new file to be contiguous
455 //
456 // Inputs:
457 // SGlobPtr global state set up by fsck_hfs. We depend upon the
458 // manufactured and repair FCBs.
459 //
460 // Outputs:
461 // calculatedRepairBTCB fill in the BTreeControlBlock for new B-Tree file.
462 // calculatedRepairFCB fill in the SFCB for the new B-Tree file
463 //
464 // Result:
465 // various error codes when problems occur or noErr if all is well
466 //
467 //_________________________________________________________________________________
468
469 /*static*/ OSErr CreateNewBTree( SGlobPtr theSGlobPtr, int FileID )
470 {
471 OSErr myErr;
472 BTreeControlBlock * myBTreeCBPtr, * oldBCBPtr;
473 SVCB * myVCBPtr;
474 SFCB * myFCBPtr, * oldFCBPtr;
475 UInt32 myBytesUsed = 0;
476 UInt32 myMapNodeCount;
477 UInt64 myNumBlocks;
478 FSSize myNewEOF;
479 BTHeaderRec myHeaderRec;
480
481 myBTreeCBPtr = theSGlobPtr->calculatedRepairBTCB;
482 myFCBPtr = theSGlobPtr->calculatedRepairFCB;
483 ClearMemory( (Ptr) myFCBPtr, sizeof( *myFCBPtr ) );
484 ClearMemory( (Ptr) myBTreeCBPtr, sizeof( *myBTreeCBPtr ) );
485
486 if (FileID == kHFSCatalogFileID) {
487 oldFCBPtr = theSGlobPtr->calculatedCatalogFCB;
488 oldBCBPtr = theSGlobPtr->calculatedCatalogBTCB;
489 } else if (FileID == kHFSAttributesFileID) {
490 oldFCBPtr = theSGlobPtr->calculatedAttributesFCB;
491 oldBCBPtr = theSGlobPtr->calculatedAttributesBTCB;
492 } else if (FileID == kHFSExtentsFileID) {
493 oldFCBPtr = theSGlobPtr->calculatedExtentsFCB;
494 oldBCBPtr = theSGlobPtr->calculatedExtentsBTCB;
495 } else
496 abort();
497
498 // Create new FCB
499 myVCBPtr = oldFCBPtr->fcbVolume;
500 if (FileID == kHFSCatalogFileID)
501 myFCBPtr->fcbFileID = kHFSCatalogFileID;
502 else if (FileID == kHFSAttributesFileID)
503 myFCBPtr->fcbFileID = kHFSAttributesFileID;
504 else if (FileID == kHFSExtentsFileID)
505 myFCBPtr->fcbFileID = kHFSExtentsFileID;
506
507 myFCBPtr->fcbVolume = myVCBPtr;
508 myFCBPtr->fcbBtree = myBTreeCBPtr;
509 myFCBPtr->fcbBlockSize = oldBCBPtr->nodeSize;
510
511 // Create new BTree Control Block
512 myBTreeCBPtr->fcbPtr = myFCBPtr;
513 myBTreeCBPtr->btreeType = kHFSBTreeType;
514 myBTreeCBPtr->keyCompareType = oldBCBPtr->keyCompareType;
515 myBTreeCBPtr->keyCompareProc = oldBCBPtr->keyCompareProc;
516 myBTreeCBPtr->nodeSize = oldBCBPtr->nodeSize;
517 myBTreeCBPtr->maxKeyLength = oldBCBPtr->maxKeyLength;
518 if (myVCBPtr->vcbSignature == kHFSPlusSigWord) {
519 if (FileID == kHFSExtentsFileID)
520 myBTreeCBPtr->attributes = kBTBigKeysMask;
521 else
522 myBTreeCBPtr->attributes = ( kBTBigKeysMask + kBTVariableIndexKeysMask );
523 }
524
525 myBTreeCBPtr->getBlockProc = GetFileBlock;
526 myBTreeCBPtr->releaseBlockProc = ReleaseFileBlock;
527 myBTreeCBPtr->setEndOfForkProc = SetEndOfForkProc;
528
529 myNewEOF = oldFCBPtr->fcbPhysicalSize;
530
531 myNumBlocks = myNewEOF / myVCBPtr->vcbBlockSize;
532 myErr = BlockFindAll( myBTreeCBPtr->fcbPtr, myNumBlocks);
533 ReturnIfError( myErr );
534 myBTreeCBPtr->fcbPtr->fcbPhysicalSize = myNewEOF;
535 myErr = ZeroFileBlocks( myVCBPtr, myBTreeCBPtr->fcbPtr, 0, myNewEOF >> kSectorShift );
536 ReturnIfError( myErr );
537
538 /* now set real values in our BTree Control Block */
539 myFCBPtr->fcbLogicalSize = myFCBPtr->fcbPhysicalSize; // new B-tree looks at fcbLogicalSize
540 if (FileID == kHFSCatalogFileID)
541 myFCBPtr->fcbClumpSize = myVCBPtr->vcbCatalogFile->fcbClumpSize;
542 else if (FileID == kHFSAttributesFileID)
543 myFCBPtr->fcbClumpSize = myVCBPtr->vcbAttributesFile->fcbClumpSize;
544 else if (FileID == kHFSExtentsFileID)
545 myFCBPtr->fcbClumpSize = myVCBPtr->vcbExtentsFile->fcbClumpSize;
546
547 myBTreeCBPtr->totalNodes = ( myFCBPtr->fcbPhysicalSize / myBTreeCBPtr->nodeSize );
548 myBTreeCBPtr->freeNodes = myBTreeCBPtr->totalNodes;
549
550 // Initialize our new BTree (write out header node and an empty leaf node)
551 myErr = InitializeBTree( myBTreeCBPtr, &myBytesUsed, &myMapNodeCount );
552 ReturnIfError( myErr );
553
554 // Update our BTreeControlBlock from BTHeaderRec we just wrote out
555 myErr = GetBTreeHeader( theSGlobPtr, myFCBPtr, &myHeaderRec );
556 ReturnIfError( myErr );
557
558 myBTreeCBPtr->treeDepth = myHeaderRec.treeDepth;
559 myBTreeCBPtr->rootNode = myHeaderRec.rootNode;
560 myBTreeCBPtr->leafRecords = myHeaderRec.leafRecords;
561 myBTreeCBPtr->firstLeafNode = myHeaderRec.firstLeafNode;
562 myBTreeCBPtr->lastLeafNode = myHeaderRec.lastLeafNode;
563 myBTreeCBPtr->totalNodes = myHeaderRec.totalNodes;
564 myBTreeCBPtr->freeNodes = myHeaderRec.freeNodes;
565 myBTreeCBPtr->maxKeyLength = myHeaderRec.maxKeyLength;
566
567 if ( myMapNodeCount > 0 )
568 {
569 myErr = WriteMapNodes( myBTreeCBPtr, (myBytesUsed / myBTreeCBPtr->nodeSize ), myMapNodeCount );
570 ReturnIfError( myErr );
571 }
572
573 return( myErr );
574
575 } /* CreateNewBTree */
576
577
578 /*
579 * InitializeBTree
580 *
581 * This routine manufactures and writes out a B-Tree header
582 * node and an empty leaf node.
583 *
584 * Note: Since large volumes can have bigger b-trees they
585 * might need to have map nodes setup.
586 *
587 * this routine originally came from newfs_hfs.tproj ( see
588 * WriteCatalogFile in file makehfs.c) and was modified for fsck_hfs.
589 */
590 static OSErr InitializeBTree( BTreeControlBlock * theBTreeCBPtr,
591 UInt32 * theBytesUsedPtr,
592 UInt32 * theMapNodeCountPtr )
593 {
594 OSErr myErr;
595 BlockDescriptor myNode;
596 Boolean isHFSPlus = false;
597 SVCB * myVCBPtr;
598 BTNodeDescriptor * myNodeDescPtr;
599 BTHeaderRec * myHeaderRecPtr;
600 UInt8 * myBufferPtr;
601 UInt8 * myBitMapPtr;
602 UInt32 myNodeBitsInHeader;
603 UInt32 temp;
604 SInt16 myOffset;
605
606 myVCBPtr = theBTreeCBPtr->fcbPtr->fcbVolume;
607 isHFSPlus = ( myVCBPtr->vcbSignature == kHFSPlusSigWord) ;
608 *theMapNodeCountPtr = 0;
609
610 myErr = GetNewNode( theBTreeCBPtr, kHeaderNodeNum, &myNode );
611 ReturnIfError( myErr );
612
613 myBufferPtr = (UInt8 *) myNode.buffer;
614
615 /* FILL IN THE NODE DESCRIPTOR: */
616 myNodeDescPtr = (BTNodeDescriptor *) myBufferPtr;
617 myNodeDescPtr->kind = kBTHeaderNode;
618 myNodeDescPtr->numRecords = 3;
619 myOffset = sizeof( BTNodeDescriptor );
620
621 SETOFFSET( myBufferPtr, theBTreeCBPtr->nodeSize, myOffset, 1 );
622
623 /* FILL IN THE HEADER RECORD: */
624 myHeaderRecPtr = (BTHeaderRec *)((UInt8 *)myBufferPtr + myOffset);
625 myHeaderRecPtr->treeDepth = 0;
626 myHeaderRecPtr->rootNode = 0;
627 myHeaderRecPtr->firstLeafNode = 0;
628 myHeaderRecPtr->lastLeafNode = 0;
629 myHeaderRecPtr->nodeSize = theBTreeCBPtr->nodeSize;
630 myHeaderRecPtr->totalNodes = theBTreeCBPtr->totalNodes;
631 myHeaderRecPtr->freeNodes = myHeaderRecPtr->totalNodes - 1; /* header node */
632 myHeaderRecPtr->clumpSize = theBTreeCBPtr->fcbPtr->fcbClumpSize;
633
634 myHeaderRecPtr->attributes = theBTreeCBPtr->attributes;
635 myHeaderRecPtr->maxKeyLength = theBTreeCBPtr->maxKeyLength;
636 myHeaderRecPtr->keyCompareType = theBTreeCBPtr->keyCompareType;
637
638 myOffset += sizeof( BTHeaderRec );
639 SETOFFSET( myBufferPtr, theBTreeCBPtr->nodeSize, myOffset, 2 );
640
641 myOffset += kBTreeHeaderUserBytes;
642 SETOFFSET( myBufferPtr, theBTreeCBPtr->nodeSize, myOffset, 3 );
643
644 /* FIGURE OUT HOW MANY MAP NODES (IF ANY): */
645 myNodeBitsInHeader = 8 * (theBTreeCBPtr->nodeSize
646 - sizeof(BTNodeDescriptor)
647 - sizeof(BTHeaderRec)
648 - kBTreeHeaderUserBytes
649 - (4 * sizeof(SInt16)) );
650
651 if ( myHeaderRecPtr->totalNodes > myNodeBitsInHeader )
652 {
653 UInt32 nodeBitsInMapNode;
654
655 myNodeDescPtr->fLink = myHeaderRecPtr->lastLeafNode + 1;
656 nodeBitsInMapNode = 8 * (theBTreeCBPtr->nodeSize
657 - sizeof(BTNodeDescriptor)
658 - (2 * sizeof(SInt16))
659 - 2 );
660 *theMapNodeCountPtr = (myHeaderRecPtr->totalNodes - myNodeBitsInHeader +
661 (nodeBitsInMapNode - 1)) / nodeBitsInMapNode;
662 myHeaderRecPtr->freeNodes = myHeaderRecPtr->freeNodes - *theMapNodeCountPtr;
663 }
664
665 /*
666 * FILL IN THE MAP RECORD, MARKING NODES THAT ARE IN USE.
667 * Note - worst case (32MB alloc blk) will have only 18 nodes in use.
668 */
669 myBitMapPtr = ((UInt8 *)myBufferPtr + myOffset);
670 temp = myHeaderRecPtr->totalNodes - myHeaderRecPtr->freeNodes;
671
672 /* Working a byte at a time is endian safe */
673 while ( temp >= 8 )
674 {
675 *myBitMapPtr = 0xFF;
676 temp -= 8;
677 myBitMapPtr++;
678 }
679 *myBitMapPtr = ~(0xFF >> temp);
680 myOffset += myNodeBitsInHeader / 8;
681
682 SETOFFSET( myBufferPtr, theBTreeCBPtr->nodeSize, myOffset, 4 );
683
684 *theBytesUsedPtr =
685 ( myHeaderRecPtr->totalNodes - myHeaderRecPtr->freeNodes - *theMapNodeCountPtr )
686 * theBTreeCBPtr->nodeSize;
687
688 /* write header node */
689 myErr = UpdateNode( theBTreeCBPtr, &myNode );
690 M_ExitOnError( myErr );
691
692 return noErr;
693
694 ErrorExit:
695 (void) ReleaseNode( theBTreeCBPtr, &myNode );
696
697 return( myErr );
698
699 } /* InitializeBTree */
700
701
702 /*
703 * WriteMapNodes
704 *
705 * This routine manufactures and writes out a B-Tree map
706 * node (or nodes if there are more than one).
707 *
708 * this routine originally came from newfs_hfs.tproj ( see
709 * WriteMapNodes in file makehfs.c) and was modified for fsck_hfs.
710 */
711
712 static OSErr WriteMapNodes( BTreeControlBlock * theBTreeCBPtr,
713 UInt32 theFirstMapNode,
714 UInt32 theNodeCount )
715 {
716 OSErr myErr;
717 UInt16 i;
718 UInt32 mapRecordBytes;
719 BTNodeDescriptor * myNodeDescPtr;
720 BlockDescriptor myNode;
721
722 myNode.buffer = NULL;
723
724 /*
725 * Note - worst case (32MB alloc blk) will have
726 * only 18 map nodes. So don't bother optimizing
727 * this section to do multiblock writes!
728 */
729 for ( i = 0; i < theNodeCount; i++ )
730 {
731 myErr = GetNewNode( theBTreeCBPtr, theFirstMapNode, &myNode );
732 M_ExitOnError( myErr );
733
734 myNodeDescPtr = (BTNodeDescriptor *) myNode.buffer;
735 myNodeDescPtr->kind = kBTMapNode;
736 myNodeDescPtr->numRecords = 1;
737
738 /* note: must be long word aligned (hence the extra -2) */
739 mapRecordBytes = theBTreeCBPtr->nodeSize - sizeof(BTNodeDescriptor) - 2 * sizeof(SInt16) - 2;
740
741 SETOFFSET( myNodeDescPtr, theBTreeCBPtr->nodeSize, sizeof(BTNodeDescriptor), 1 );
742 SETOFFSET( myNodeDescPtr, theBTreeCBPtr->nodeSize, sizeof(BTNodeDescriptor) + mapRecordBytes, 2) ;
743
744 if ( (i + 1) < theNodeCount )
745 myNodeDescPtr->fLink = ++theFirstMapNode; /* point to next map node */
746 else
747 myNodeDescPtr->fLink = 0; /* this is the last map node */
748
749 myErr = UpdateNode( theBTreeCBPtr, &myNode );
750 M_ExitOnError( myErr );
751 }
752
753 return noErr;
754
755 ErrorExit:
756 (void) ReleaseNode( theBTreeCBPtr, &myNode );
757
758 return( myErr );
759
760 } /* WriteMapNodes */
761
762
763 /*
764 * DeleteBTree
765 *
766 * This routine will realease all space associated with the BTree
767 * file represented by the FCB passed in.
768 *
769 */
770
771 enum
772 {
773 kDataForkType = 0,
774 kResourceForkType = 0xFF
775 };
776
777 static OSErr DeleteBTree( SGlobPtr theSGlobPtr, SFCB * theFCBPtr )
778 {
779 OSErr myErr;
780 SVCB * myVCBPtr;
781 int i;
782 Boolean isHFSPlus;
783 Boolean checkExtentsBTree = true;
784
785 myVCBPtr = theFCBPtr->fcbVolume;
786 isHFSPlus = ( myVCBPtr->vcbSignature == kHFSPlusSigWord) ;
787
788 if ( isHFSPlus )
789 {
790 for ( i = 0; i < kHFSPlusExtentDensity; ++i )
791 {
792 if ( theFCBPtr->fcbExtents32[ i ].blockCount == 0 )
793 {
794 checkExtentsBTree = false;
795 break;
796 }
797 (void) BlockDeallocate( myVCBPtr,
798 theFCBPtr->fcbExtents32[ i ].startBlock,
799 theFCBPtr->fcbExtents32[ i ].blockCount );
800 theFCBPtr->fcbExtents32[ i ].startBlock = 0;
801 theFCBPtr->fcbExtents32[ i ].blockCount = 0;
802 }
803 }
804 else
805 {
806 for ( i = 0; i < kHFSExtentDensity; ++i )
807 {
808 if ( theFCBPtr->fcbExtents16[ i ].blockCount == 0 )
809 {
810 checkExtentsBTree = false;
811 break;
812 }
813 (void) BlockDeallocate( myVCBPtr,
814 theFCBPtr->fcbExtents16[ i ].startBlock,
815 theFCBPtr->fcbExtents16[ i ].blockCount );
816 theFCBPtr->fcbExtents16[ i ].startBlock = 0;
817 theFCBPtr->fcbExtents16[ i ].blockCount = 0;
818 }
819 }
820
821 if ( checkExtentsBTree )
822 {
823 (void) ReleaseExtentsInExtentsBTree( theSGlobPtr, theFCBPtr );
824 (void) FlushExtentFile( myVCBPtr );
825 }
826
827 (void) MarkVCBDirty( myVCBPtr );
828 (void) FlushAlternateVolumeControlBlock( myVCBPtr, isHFSPlus );
829 myErr = noErr;
830
831 return( myErr );
832
833 } /* DeleteBTree */
834
835
836 /*
837 * ReleaseExtentsInExtentsBTree
838 *
839 * This routine will locate extents in the extent BTree then release the space
840 * associated with the extents. It will also delete the BTree record for the
841 * extent.
842 *
843 */
844
845 static OSErr ReleaseExtentsInExtentsBTree( SGlobPtr theSGlobPtr,
846 SFCB * theFCBPtr )
847 {
848 BTreeIterator myIterator;
849 ExtentRecord myExtentRecord;
850 FSBufferDescriptor myBTRec;
851 ExtentKey * myKeyPtr;
852 SVCB * myVCBPtr;
853 UInt16 myRecLen;
854 UInt16 i;
855 OSErr myErr;
856 Boolean isHFSPlus;
857
858 myVCBPtr = theFCBPtr->fcbVolume;
859 isHFSPlus = ( myVCBPtr->vcbSignature == kHFSPlusSigWord );
860
861 // position just before the first extent record for the given File ID. We
862 // pass in the file ID and a start block of 0 which will put us in a
863 // position for BTIterateRecord (with kBTreeNextRecord) to get the first
864 // extent record.
865 ClearMemory( &myIterator, sizeof(myIterator) );
866 myBTRec.bufferAddress = &myExtentRecord;
867 myBTRec.itemCount = 1;
868 myBTRec.itemSize = sizeof(myExtentRecord);
869 myKeyPtr = (ExtentKey *) &myIterator.key;
870
871 BuildExtentKey( isHFSPlus, kDataForkType, theFCBPtr->fcbFileID,
872 0, (void *) myKeyPtr );
873
874 // it is now a simple process of getting the next extent record and
875 // cleaning up the allocated space for each one until we hit a
876 // different file ID.
877 for ( ;; )
878 {
879 myErr = BTIterateRecord( theSGlobPtr->calculatedExtentsFCB,
880 kBTreeNextRecord, &myIterator,
881 &myBTRec, &myRecLen );
882 if ( noErr != myErr )
883 {
884 myErr = noErr;
885 break;
886 }
887
888 /* deallocate space for the extents we found */
889 if ( isHFSPlus )
890 {
891 // we're done if this is a different File ID
892 if ( myKeyPtr->hfsPlus.fileID != theFCBPtr->fcbFileID ||
893 myKeyPtr->hfsPlus.forkType != kDataForkType )
894 break;
895
896 for ( i = 0; i < kHFSPlusExtentDensity; ++i )
897 {
898 if ( myExtentRecord.hfsPlus[ i ].blockCount == 0 )
899 break;
900
901 (void) BlockDeallocate( myVCBPtr,
902 myExtentRecord.hfsPlus[ i ].startBlock,
903 myExtentRecord.hfsPlus[ i ].blockCount );
904 }
905 }
906 else
907 {
908 // we're done if this is a different File ID
909 if ( myKeyPtr->hfs.fileID != theFCBPtr->fcbFileID ||
910 myKeyPtr->hfs.forkType != kDataForkType )
911 break;
912
913 for ( i = 0; i < kHFSExtentDensity; ++i )
914 {
915 if ( myExtentRecord.hfs[ i ].blockCount == 0 )
916 break;
917
918 (void) BlockDeallocate( myVCBPtr,
919 myExtentRecord.hfs[ i ].startBlock,
920 myExtentRecord.hfs[ i ].blockCount );
921 }
922 }
923
924 /* get rid of this extent BTree record */
925 myErr = DeleteBTreeRecord( theSGlobPtr->calculatedExtentsFCB, myKeyPtr );
926 }
927
928 return( myErr );
929
930 } /* ReleaseExtentsInExtentsBTree */
931
932
933 /*
934 * ValidateExtentRecordLength
935 * This routine will ensure that an extent record is the right size.
936 * This should always be the size of HFSPlusExtentRecord.
937 */
938 static OSErr ValidateExtentRecordLength (SGlobPtr s, ExtentRecord * theRecPtr, UInt32 theRecSize)
939 {
940 Boolean isHFSPlus = ( s->calculatedVCB->vcbSignature == kHFSPlusSigWord );
941 if (isHFSPlus) {
942 if (theRecSize != sizeof(HFSPlusExtentRecord))
943 return -1;
944 } else {
945 if (theRecSize != sizeof(HFSExtentRecord))
946 return -1;
947 }
948
949 return noErr;
950 }
951
952 /*
953 * ValidateAttributeRecordLength
954 *
955 * This routine will make sure that the given HFS+ attributes file record
956 * is of the correct length.
957 *
958 */
959 static OSErr ValidateAttributeRecordLength (SGlobPtr s, HFSPlusAttrRecord * theRecPtr, UInt32 theRecSize)
960 {
961 OSErr retval = noErr;
962 static UInt32 maxInlineSize;
963
964 if (maxInlineSize == 0) {
965 /* The maximum size of an inline attribute record is nodesize / 2 minus a bit */
966 /* These calculations taken from hfs_xattr.c:getmaxinlineattrsize */
967 maxInlineSize = s->calculatedAttributesBTCB->nodeSize;
968 maxInlineSize -= sizeof(BTNodeDescriptor); // Minus node descriptor
969 maxInlineSize -= 3 * sizeof(u_int16_t); // Minus 3 index slots
970 maxInlineSize /= 2; // 2 key/rec pairs minimum
971 maxInlineSize -= sizeof(HFSPlusAttrKey); // Minus maximum key size
972 maxInlineSize &= 0xFFFFFFFE; // Multiple of two
973 }
974 switch (theRecPtr->recordType) {
975 case kHFSPlusAttrInlineData:
976 if (theRecSize > maxInlineSize) {
977 if (debug)
978 plog("Inline Attribute size %u is larger than maxsize %u\n", theRecSize, maxInlineSize);
979 retval = -1;
980 }
981 break;
982 case kHFSPlusAttrForkData:
983 if (theRecSize != sizeof(HFSPlusAttrForkData)) {
984 if (debug)
985 plog("Fork Data attribute size %u is larger then HFSPlusAttrForkData size %u\n", theRecSize, sizeof(HFSPlusAttrForkData));
986 retval = -1;
987 }
988 break;
989 case kHFSPlusAttrExtents:
990 if (theRecSize != sizeof(HFSPlusAttrExtents)) {
991 if (debug)
992 plog("Extents Data attribute size %u is larger than HFSPlusAttrExtents size %u\n", theRecSize, sizeof(HFSPlusAttrExtents));
993 retval = -1;
994 }
995 break;
996 default:
997 // Right now, we don't support any other kind
998 if (debug)
999 plog("Unknown attribute type %u\n", theRecPtr->recordType);
1000 retval = -1;
1001 break;
1002 }
1003 return retval;
1004 }
1005
1006 /*
1007 * ValidateCatalogRecordLength
1008 *
1009 * This routine will make sure the given HFS (plus and standard) catalog record
1010 * is of the correct length.
1011 *
1012 */
1013
1014 static OSErr ValidateCatalogRecordLength( SGlobPtr theSGlobPtr,
1015 CatalogRecord * theRecPtr,
1016 UInt32 theRecSize )
1017 {
1018 SVCB * myVCBPtr;
1019 Boolean isHFSPlus = false;
1020
1021 myVCBPtr = theSGlobPtr->calculatedVCB;
1022 isHFSPlus = ( myVCBPtr->vcbSignature == kHFSPlusSigWord );
1023
1024 if ( isHFSPlus )
1025 {
1026 switch ( theRecPtr->recordType )
1027 {
1028 case kHFSPlusFolderRecord:
1029 if ( theRecSize != sizeof( HFSPlusCatalogFolder ) )
1030 {
1031 return( -1 );
1032 }
1033 break;
1034
1035 case kHFSPlusFileRecord:
1036 if ( theRecSize != sizeof(HFSPlusCatalogFile) )
1037 {
1038 return( -1 );
1039 }
1040 break;
1041
1042 case kHFSPlusFolderThreadRecord:
1043 /* Fall through */
1044
1045 case kHFSPlusFileThreadRecord:
1046 if ( theRecSize > sizeof(HFSPlusCatalogThread) ||
1047 theRecSize < sizeof(HFSPlusCatalogThread) - sizeof(HFSUniStr255) + sizeof(UniChar) )
1048 {
1049 return( -1 );
1050 }
1051 break;
1052
1053 default:
1054 return( -1 );
1055 }
1056 }
1057 else
1058 {
1059 switch ( theRecPtr->recordType )
1060 {
1061 case kHFSFolderRecord:
1062 if ( theRecSize != sizeof(HFSCatalogFolder) )
1063 return( -1 );
1064 break;
1065
1066 case kHFSFileRecord:
1067 if ( theRecSize != sizeof(HFSCatalogFile) )
1068 return( -1 );
1069 break;
1070
1071 case kHFSFolderThreadRecord:
1072 /* Fall through */
1073 case kHFSFileThreadRecord:
1074 if ( theRecSize != sizeof(HFSCatalogThread))
1075 return( -1 );
1076 break;
1077
1078 default:
1079 return( -1 );
1080 }
1081 }
1082
1083 return( noErr );
1084
1085 } /* ValidateCatalogRecordLength */
1086
1087
1088 #if DEBUG_REBUILD
1089 static void PrintNodeDescriptor( NodeDescPtr thePtr )
1090 {
1091 plog( "\n xxxxxxxx BTNodeDescriptor xxxxxxxx \n" );
1092 plog( " fLink %d \n", thePtr->fLink );
1093 plog( " bLink %d \n", thePtr->bLink );
1094 plog( " kind %d ", thePtr->kind );
1095 if ( thePtr->kind == kBTLeafNode )
1096 plog( "%s \n", "kBTLeafNode" );
1097 else if ( thePtr->kind == kBTIndexNode )
1098 plog( "%s \n", "kBTIndexNode" );
1099 else if ( thePtr->kind == kBTHeaderNode )
1100 plog( "%s \n", "kBTHeaderNode" );
1101 else if ( thePtr->kind == kBTMapNode )
1102 plog( "%s \n", "kBTMapNode" );
1103 else
1104 plog( "do not know?? \n" );
1105 plog( " height %d \n", thePtr->height );
1106 plog( " numRecords %d \n", thePtr->numRecords );
1107
1108 } /* PrintNodeDescriptor */
1109
1110
1111 static void PrintBTHeaderRec( BTHeaderRec * thePtr )
1112 {
1113 plog( "\n xxxxxxxx BTHeaderRec xxxxxxxx \n" );
1114 plog( " treeDepth %d \n", thePtr->treeDepth );
1115 plog( " rootNode %d \n", thePtr->rootNode );
1116 plog( " leafRecords %d \n", thePtr->leafRecords );
1117 plog( " firstLeafNode %d \n", thePtr->firstLeafNode );
1118 plog( " lastLeafNode %d \n", thePtr->lastLeafNode );
1119 plog( " nodeSize %d \n", thePtr->nodeSize );
1120 plog( " maxKeyLength %d \n", thePtr->maxKeyLength );
1121 plog( " totalNodes %d \n", thePtr->totalNodes );
1122 plog( " freeNodes %d \n", thePtr->freeNodes );
1123 plog( " clumpSize %d \n", thePtr->clumpSize );
1124 plog( " btreeType 0x%02X \n", thePtr->btreeType );
1125 plog( " attributes 0x%02X \n", thePtr->attributes );
1126
1127 } /* PrintBTHeaderRec */
1128
1129
1130 static void PrintBTreeKey( KeyPtr thePtr, BTreeControlBlock * theBTreeCBPtr )
1131 {
1132 int myKeyLength, i;
1133 UInt8 * myPtr = (UInt8 *)thePtr;
1134 char ascii[17];
1135 UInt8 byte;
1136
1137 ascii[16] = '\0';
1138
1139 myKeyLength = CalcKeySize( theBTreeCBPtr, thePtr) ;
1140 plog( "\n xxxxxxxx BTreeKey (length %d) xxxxxxxx \n", myKeyLength );
1141 for ( i = 0; i < myKeyLength; i++ )
1142 {
1143 byte = *(myPtr + i);
1144 plog( "%02X ", byte );
1145 if (byte < 32 || byte > 126)
1146 ascii[i & 0xF] = '.';
1147 else
1148 ascii[i & 0xF] = byte;
1149
1150 if ((i & 0xF) == 0xF)
1151 {
1152 plog(" %s\n", ascii);
1153 }
1154 }
1155
1156 if (i & 0xF)
1157 {
1158 int j;
1159 for (j = i & 0xF; j < 16; ++j)
1160 plog(" ");
1161 ascii[i & 0xF] = 0;
1162 plog(" %s\n", ascii);
1163 }
1164 } /* PrintBTreeKey */
1165
1166 static void PrintBTreeData(void *data, UInt32 length)
1167 {
1168 UInt32 i;
1169 UInt8 * myPtr = (UInt8 *)data;
1170 char ascii[17];
1171 UInt8 byte;
1172
1173 ascii[16] = '\0';
1174
1175 plog( "\n xxxxxxxx BTreeData (length %d) xxxxxxxx \n", length );
1176 for ( i = 0; i < length; i++ )
1177 {
1178 byte = *(myPtr + i);
1179 plog( "%02X ", byte );
1180 if (byte < 32 || byte > 126)
1181 ascii[i & 0xF] = '.';
1182 else
1183 ascii[i & 0xF] = byte;
1184
1185 if ((i & 0xF) == 0xF)
1186 {
1187 plog(" %s\n", ascii);
1188 }
1189 }
1190
1191 if (i & 0xF)
1192 {
1193 int j;
1194 for (j = i & 0xF; j < 16; ++j)
1195 plog(" ");
1196 ascii[i & 0xF] = 0;
1197 plog(" %s\n", ascii);
1198 }
1199 }
1200
1201 static void PrintIndexNodeRec( UInt32 theNodeNum )
1202 {
1203 plog( "\n xxxxxxxx IndexNodeRec xxxxxxxx \n" );
1204 plog( " node number %d \n", theNodeNum );
1205
1206 } /* PrintIndexNodeRec */
1207
1208 static void PrintLeafNodeRec( HFSPlusCatalogFolder * thePtr )
1209 {
1210 plog( "\n xxxxxxxx LeafNodeRec xxxxxxxx \n" );
1211 plog( " recordType %d ", thePtr->recordType );
1212 if ( thePtr->recordType == kHFSPlusFolderRecord )
1213 plog( "%s \n", "kHFSPlusFolderRecord" );
1214 else if ( thePtr->recordType == kHFSPlusFileRecord )
1215 plog( "%s \n", "kHFSPlusFileRecord" );
1216 else if ( thePtr->recordType == kHFSPlusFolderThreadRecord )
1217 plog( "%s \n", "kHFSPlusFolderThreadRecord" );
1218 else if ( thePtr->recordType == kHFSPlusFileThreadRecord )
1219 plog( "%s \n", "kHFSPlusFileThreadRecord" );
1220 else
1221 plog( "do not know?? \n" );
1222
1223 } /* PrintLeafNodeRec */
1224
1225
1226 #endif // DEBUG_REBUILD
mirror of hfs