]> git.saurik.com Git - apple/hfs.git/blob - fsck_hfs/dfalib/SVerify2.c
projects / apple / hfs.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
hfs-366.50.19.tar.gz
[apple/hfs.git] / fsck_hfs / dfalib / SVerify2.c
1 /*
2 * Copyright (c) 1999-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: SVerify2.c
25
26 Contains: xxx put contents here xxx
27
28 Version: xxx put version here xxx
29
30 Copyright: � 1997-1999 by Apple Computer, Inc., all rights reserved.
31 */
32
33 #include <sys/ioctl.h>
34 #include <sys/disk.h>
35
36 #include "BTree.h"
37 #include "BTreePrivate.h"
38
39 #include "Scavenger.h"
40
41
42 // Prototypes for internal subroutines
43 static int BTKeyChk( SGlobPtr GPtr, NodeDescPtr nodeP, BTreeControlBlock *btcb );
44
45
46 /*------------------------------------------------------------------------------
47
48 Routine: ChkExtRec (Check Extent Record)
49
50 Function: Checks out a generic extent record.
51
52 Input: GPtr - pointer to scavenger global area.
53 extP - pointer to extent data record.
54
55
56 Output: lastExtentIndex - In normal case, it is set to the maximum number of
57 extents (3 or 8) for given file system. If the
58 function finds bad extent, it is set to the index
59 of the bad extent entry found.
60 ChkExtRec - function result:
61 0 = no error
62 n = error
63 ------------------------------------------------------------------------------*/
64 OSErr ChkExtRec ( SGlobPtr GPtr, UInt32 fileID, const void *extents , unsigned int *lastExtentIndex )
65 {
66 short i;
67 Boolean isHFSPlus;
68 UInt32 numABlks;
69 UInt32 maxNABlks;
70 UInt32 extentBlockCount;
71 UInt32 extentStartBlock;
72
73 maxNABlks = GPtr->calculatedVCB->vcbTotalBlocks;
74 numABlks = 1;
75 isHFSPlus = VolumeObjectIsHFSPlus( );
76
77 /* initialize default output for extent index */
78 *lastExtentIndex = GPtr->numExtents;
79
80 for ( i=0 ; i<GPtr->numExtents ; i++ )
81 {
82 if ( isHFSPlus )
83 {
84 extentBlockCount = ((HFSPlusExtentDescriptor *)extents)[i].blockCount;
85 extentStartBlock = ((HFSPlusExtentDescriptor *)extents)[i].startBlock;
86 }
87 else
88 {
89 extentBlockCount = ((HFSExtentDescriptor *)extents)[i].blockCount;
90 extentStartBlock = ((HFSExtentDescriptor *)extents)[i].startBlock;
91 }
92
93 if ( extentStartBlock >= maxNABlks )
94 {
95 *lastExtentIndex = i;
96 RcdError( GPtr, E_ExtEnt );
97 if (fsckGetVerbosity(GPtr->context) >= kDebugLog) {
98 plog ("\tCheckExtRecord: id=%u %d:(%u,%u), maxBlocks=%u (startBlock > maxBlocks)\n",
99 fileID, i, extentStartBlock, extentBlockCount, maxNABlks);
100 }
101 return( E_ExtEnt );
102 }
103 /* Check if end of extent is beyond end of disk */
104 if ( extentBlockCount >= (maxNABlks - extentStartBlock) )
105 {
106 *lastExtentIndex = i;
107 RcdError( GPtr, E_ExtEnt );
108 if (fsckGetVerbosity(GPtr->context) >= kDebugLog) {
109 plog ("\tCheckExtRecord: id=%u %d:(%u,%u), maxBlocks=%u (blockCount > (maxBlocks - startBlock))\n",
110 fileID, i, extentStartBlock, extentBlockCount, maxNABlks);
111 }
112 return( E_ExtEnt );
113 }
114 /* This condition is not checked for standard HFS volumes as it is valid
115 * to have extent with allocation block number 0 on standard HFS.
116 */
117 if ( isHFSPlus &&
118 ((extentStartBlock == 0) && (extentBlockCount != 0)))
119 {
120 *lastExtentIndex = i;
121 RcdError( GPtr, E_ExtEnt );
122 if (fsckGetVerbosity(GPtr->context) >= kDebugLog) {
123 plog ("\tCheckExtRecord: id=%u %d:(%u,%u), (startBlock == 0)\n",
124 fileID, i, extentStartBlock, extentBlockCount);
125 }
126 return( E_ExtEnt );
127
128 }
129 if ((extentStartBlock != 0) && (extentBlockCount == 0))
130 {
131 *lastExtentIndex = i;
132 RcdError( GPtr, E_ExtEnt );
133 if (fsckGetVerbosity(GPtr->context) >= kDebugLog) {
134 plog ("\tCheckExtRecord: id=%u %d:(%u,%u), (blockCount == 0)\n",
135 fileID, i, extentStartBlock, extentBlockCount);
136 }
137 return( E_ExtEnt );
138 }
139 if ( numABlks == 0 )
140 {
141 if ( extentBlockCount != 0 )
142 {
143 *lastExtentIndex = i;
144 RcdError( GPtr, E_ExtEnt );
145 if (fsckGetVerbosity(GPtr->context) >= kDebugLog) {
146 plog ("\tCheckExtRecord: id=%u %d:(%u,%u), (blockCount != 0)\n",
147 fileID, i, extentStartBlock, extentBlockCount);
148 }
149 return( E_ExtEnt );
150 }
151 }
152 numABlks = extentBlockCount;
153 }
154
155 return( noErr );
156 }
157
158
159 /*------------------------------------------------------------------------------
160
161 Routine: BTCheck - (BTree Check)
162
163 Function Description:
164 Checks out the internal structure of a Btree file. The BTree
165 structure is enunumerated top down starting from the root node.
166
167 A structure to store the current traversal state of each Btree level
168 is used. The function traverses Btree top to down till it finds
169 a leaf node - where it calls checkLeafRecord function for every
170 leaf record (if specified). The function then starts traversing
171 down from the next index node at previous BTree level. If all
172 index nodes in given BTree level are traversed top to down,
173 it starts traversing the next index node in a previous BTree level -
174 until it hits the root node.
175
176 Btree traversal:
177 The tree is traversed in depth-first traversal - i.e. we recursively
178 traverse the children of a node before visiting its sibling.
179 For the btree shown below, this function will traverse as follows:
180 root B C E I H D G F
181
182 (root node)-----
183 | B |
184 -----
185 |
186 (node B)-------------
187 | C | D | F |
188 -------------
189 / (node\ \
190 (node C)------------- D)----- -------- (node F)
191 | E | I | H | | G | | leaf |
192 ------------- ----- --------
193 / / \ |
194 -------- -------- -------- --------
195 | leaf | | leaf | | leaf | | leaf |
196 -------- -------- -------- --------
197 (node E) (node I) (node H) (node G)
198
199 Input:
200 GPtr - pointer to scavenger global area
201 refNum - file refnum
202 checkLeafRecord - pointer to function that should be
203 called for every leaf record.
204
205
206 Output: BTCheck - function result:
207 0 = no error
208 n = error code
209 ------------------------------------------------------------------------------*/
210
211 int
212 BTCheck(SGlobPtr GPtr, short refNum, CheckLeafRecordProcPtr checkLeafRecord)
213 {
214 OSErr result;
215 short i;
216 short keyLen;
217 UInt32 nodeNum;
218 short numRecs; /* number of records in current node */
219 short index; /* index to current index record in index node */
220 UInt16 recSize;
221 UInt8 parKey[ kMaxKeyLength + 2 + 2 ]; /* parent key for comparison */
222 Boolean hasParKey = false;
223 UInt8 *dataPtr;
224 STPR *tprP; /* pointer to store BTree traversal state */
225 STPR *parentP;
226 KeyPtr keyPtr;
227 BTHeaderRec *header;
228 NodeRec node;
229 NodeDescPtr nodeDescP;
230 UInt16 *statusFlag = NULL;
231 UInt32 leafRecords = 0;
232 BTreeControlBlock *calculatedBTCB = GetBTreeControlBlock( refNum );
233
234 node.buffer = NULL;
235
236 // Set up
237 if ( refNum == kCalculatedCatalogRefNum )
238 statusFlag = &(GPtr->CBTStat);
239 else if ( refNum == kCalculatedExtentRefNum )
240 statusFlag = &(GPtr->EBTStat);
241 else if ( refNum == kCalculatedAttributesRefNum )
242 statusFlag = &(GPtr->ABTStat);
243 else {
244 /* BTCheck is currently called only with the above three options.
245 * Initialize status flag correctly if we call BTCheck with other
246 * options
247 */
248 result = E_BadValue;
249 goto exit;
250 }
251
252 GPtr->TarBlock = 0;
253
254 /*
255 * Check out BTree header node
256 */
257 result = GetNode( calculatedBTCB, kHeaderNodeNum, &node );
258 if ( result != noErr )
259 {
260 if ( result == fsBTInvalidNodeErr ) /* hfs_swap_BTNode failed */
261 {
262 RcdError( GPtr, E_BadNode );
263 result = E_BadNode;
264 }
265 node.buffer = NULL;
266 goto exit;
267 }
268
269 nodeDescP = node.buffer;
270
271 result = AllocBTN( GPtr, refNum, 0 );
272 if (result) goto exit; /* node already allocated */
273
274 /* Check node kind */
275 if ( nodeDescP->kind != kBTHeaderNode )
276 {
277 RcdError( GPtr, E_BadHdrN );
278 result = E_BadHdrN;
279 goto exit;
280 }
281 /* Check total records allowed in header node */
282 if ( nodeDescP->numRecords != Num_HRecs )
283 {
284 RcdError( GPtr, E_BadHdrN );
285 result = E_BadHdrN;
286 goto exit;
287 }
288 /* Check node height */
289 if ( nodeDescP->height != 0 )
290 {
291 RcdError( GPtr, E_NHeight );
292 result = E_NHeight;
293 goto exit;
294 }
295
296 /*
297 * check out BTree Header record
298 */
299 header = (BTHeaderRec*) ((Byte*)nodeDescP + sizeof(BTNodeDescriptor));
300 recSize = GetRecordSize( (BTreeControlBlock *)calculatedBTCB, (BTNodeDescriptor *)nodeDescP, 0 );
301
302 /* Check header size */
303 if ( recSize != sizeof(BTHeaderRec) )
304 {
305 RcdError( GPtr, E_LenBTH );
306 result = E_LenBTH;
307 goto exit;
308 }
309 /* Check tree depth */
310 if ( header->treeDepth > BTMaxDepth )
311 {
312 RcdError( GPtr, E_BTDepth );
313 goto RebuildBTreeExit;
314 }
315 calculatedBTCB->treeDepth = header->treeDepth;
316
317 /* Check validity of root node number */
318 if ( header->rootNode >= calculatedBTCB->totalNodes ||
319 (header->treeDepth != 0 && header->rootNode == kHeaderNodeNum) )
320 {
321 if (debug)
322 plog("Header root node %u, calculated total nodes %u, tree depth %u, header node num %u\n",
323 header->rootNode, calculatedBTCB->totalNodes,
324 header->treeDepth, kHeaderNodeNum);
325
326 RcdError( GPtr, E_BTRoot );
327 goto RebuildBTreeExit;
328 }
329 calculatedBTCB->rootNode = header->rootNode;
330
331 /* Check if tree depth or root node are zero */
332 if ( (calculatedBTCB->treeDepth == 0) || (calculatedBTCB->rootNode == 0) )
333 {
334 /* If both are zero, empty BTree */
335 if ( calculatedBTCB->treeDepth != calculatedBTCB->rootNode )
336 {
337 RcdError( GPtr, E_BTDepth );
338 goto RebuildBTreeExit;
339 }
340 }
341
342 /*
343 * Check the extents for the btree.
344 * HFS+ considers it an error for a node to be split across
345 * extents, on a journaled filesystem.
346 *
347 * If debug is set, then it continues examining the tree; otherwise,
348 * it exits with a rebuilt error.
349 */
350 if (CheckIfJournaled(GPtr, true) &&
351 header->nodeSize > calculatedBTCB->fcbPtr->fcbVolume->vcbBlockSize) {
352 /* If it's journaled, it's HFS+ */
353 HFSPlusExtentRecord *extp = &calculatedBTCB->fcbPtr->fcbExtents32;
354 int i;
355 int blocksPerNode = header->nodeSize / calculatedBTCB->fcbPtr->fcbVolume->vcbBlockSize; // How many blocks in a node
356 UInt32 totalBlocks = 0;
357
358 /*
359 * First, go through the first 8 extents
360 */
361 for (i = 0; i < kHFSPlusExtentDensity; i++) {
362 if (((*extp)[i].blockCount % blocksPerNode) != 0) {
363 result = errRebuildBtree;
364 *statusFlag |= S_RebuildBTree;
365 fsckPrint(GPtr->context, E_BTreeSplitNode, calculatedBTCB->fcbPtr->fcbFileID);
366 if (debug == 0) {
367 goto exit;
368 } else {
369 plog("Improperly split node in file id %u, offset %u (extent #%d), Extent <%u, %u>\n", calculatedBTCB->fcbPtr->fcbFileID, totalBlocks, i, (*extp)[i].startBlock, (*extp)[i].blockCount);
370 }
371 }
372 totalBlocks += (*extp)[i].blockCount;
373
374 }
375 /*
376 * Now, iterate through the extents overflow file if necessary.
377 * Style note: This is in a block so I can have local variables.
378 * It used to have a conditional, but that wasn't needed.
379 */
380 {
381 int err;
382 BTreeIterator iterator = { 0 };
383 FSBufferDescriptor btRecord = { 0 };
384 HFSPlusExtentKey *key = (HFSPlusExtentKey*)&iterator.key;
385 HFSPlusExtentRecord extRecord = { 0 };
386 UInt16 recordSize;
387 UInt32 fileID = calculatedBTCB->fcbPtr->fcbFileID;
388 static const int kDataForkType = 0;
389
390 BuildExtentKey( true, kDataForkType, fileID, 0, (void*)key );
391 btRecord.bufferAddress = &extRecord;
392 btRecord.itemCount = 1;
393 btRecord.itemSize = sizeof(extRecord);
394
395 while (noErr == (err = BTIterateRecord(GPtr->calculatedExtentsFCB, kBTreeNextRecord, &iterator, &btRecord, &recordSize))) {
396 if (key->fileID != fileID ||
397 key->forkType != kDataForkType) {
398 break;
399 }
400 for (i = 0; i < kHFSPlusExtentDensity; i++) {
401 if ((extRecord[i].blockCount % blocksPerNode) != 0) {
402 result = errRebuildBtree;
403 *statusFlag |= S_RebuildBTree;
404 fsckPrint(GPtr->context, E_BTreeSplitNode, fileID);
405 if (debug == 0) {
406 goto exit;
407 } else {
408 plog("Improperly split node in file id %u, startBlock %u, index %d (offset %u), extent <%u, %u>\n", fileID, key->startBlock, i, totalBlocks, extRecord[i].startBlock, extRecord[i].blockCount);
409 }
410 }
411 totalBlocks += extRecord[i].blockCount;
412 }
413 memset(&extRecord, 0, sizeof(extRecord));
414 }
415 }
416 }
417
418 #if 0
419 plog( "\nB-Tree header rec: \n" );
420 plog( " treeDepth = %d \n", header->treeDepth );
421 plog( " rootNode = %d \n", header->rootNode );
422 plog( " leafRecords = %d \n", header->leafRecords );
423 plog( " firstLeafNode = %d \n", header->firstLeafNode );
424 plog( " lastLeafNode = %d \n", header->lastLeafNode );
425 plog( " totalNodes = %d \n", header->totalNodes );
426 plog( " freeNodes = %d \n", header->freeNodes );
427 #endif
428
429 if (calculatedBTCB->rootNode == 0) {
430 // Empty btree, no need to continue
431 goto exit;
432 }
433 /*
434 * Set up tree path record for root level
435 */
436 GPtr->BTLevel = 1;
437 /* BTPTPtr is an array of structure which stores the state
438 * of the btree traversal based on the current BTree level.
439 * It helps to traverse to parent node from a child node.
440 * tprP points to the correct offset to read/write.
441 */
442 tprP = &(*GPtr->BTPTPtr)[0];
443 tprP->TPRNodeN = calculatedBTCB->rootNode;
444 tprP->TPRRIndx = -1; /* last index accessed in a node */
445 tprP->TPRLtSib = 0;
446 tprP->TPRRtSib = 0;
447
448 /*
449 * Now enumerate the entire BTree
450 */
451 while ( GPtr->BTLevel > 0 )
452 {
453 tprP = &(*GPtr->BTPTPtr)[GPtr->BTLevel -1];
454 nodeNum = tprP->TPRNodeN;
455 index = tprP->TPRRIndx;
456
457 GPtr->TarBlock = nodeNum;
458
459 (void) ReleaseNode(calculatedBTCB, &node);
460 result = GetNode( calculatedBTCB, nodeNum, &node );
461 if ( result != noErr )
462 {
463 if ( result == fsBTInvalidNodeErr ) /* hfs_swap_BTNode failed */
464 {
465 RcdError( GPtr, E_BadNode );
466 result = E_BadNode;
467 }
468 node.buffer = NULL;
469 if (debug)
470 {
471 /* Try to continue checking other nodes.
472 *
473 * Decrement the current btree level as we want to access
474 * the right sibling index record, if any, of our parent.
475 */
476 GPtr->BTLevel--;
477 continue;
478 }
479 goto exit;
480 }
481 nodeDescP = node.buffer;
482
483 /*
484 * Check out and allocate the node if its the first time its been seen
485 */
486 if ( index < 0 )
487 {
488 #if 0 //
489 // this will print out our leaf node order
490 if ( nodeDescP->kind == kBTLeafNode )
491 {
492 static int myCounter = 0;
493 if ( myCounter > 19 )
494 {
495 myCounter = 0;
496 plog( "\n " );
497 }
498 plog( "%d ", nodeNum );
499
500 myCounter++;
501 }
502 #endif
503
504 /* Allocate BTree node */
505 result = AllocBTN( GPtr, refNum, nodeNum );
506 if ( result )
507 {
508 /* node already allocated can be fixed if it is an index node */
509 goto RebuildBTreeExit;
510 }
511
512 /* Check keys in the node */
513 result = BTKeyChk( GPtr, nodeDescP, calculatedBTCB );
514 if ( result )
515 {
516 /* we should be able to fix any E_KeyOrd error or any B-Tree key */
517 /* errors with an index node. */
518 if ( E_KeyOrd == result || nodeDescP->kind == kBTIndexNode )
519 {
520 *statusFlag |= S_RebuildBTree;
521 result = errRebuildBtree;
522 }
523 else
524 {
525 goto exit;
526 }
527 }
528
529 /* Check backward link of this node */
530 if ( nodeDescP->bLink != tprP->TPRLtSib )
531 {
532 result = E_SibLk;
533 RcdError( GPtr, E_SibLk );
534 if (debug)
535 printf("Node %d's back link is 0x%x; expected 0x%x\n"
536 " disk offset = 0x%llx, size = 0x%x\n",
537 nodeNum, nodeDescP->bLink, tprP->TPRLtSib,
538 ((Buf_t *)(node.blockHeader))->Offset, ((Buf_t *)(node.blockHeader))->Length);
539 if (!debug)
540 goto RebuildBTreeExit;
541 }
542 if ( tprP->TPRRtSib == -1 )
543 {
544 tprP->TPRRtSib = nodeNum; /* set Rt sibling for later verification */
545 }
546 else
547 {
548 /* Check forward link for this node */
549 if ( nodeDescP->fLink != tprP->TPRRtSib )
550 {
551 result = E_SibLk;
552 RcdError( GPtr, E_SibLk );
553 if (debug)
554 printf("Node %d's forward link is 0x%x; expected 0x%x\n"
555 " disk offset = 0x%llx, size = 0x%x\n",
556 nodeNum, nodeDescP->fLink, tprP->TPRRtSib,
557 ((Buf_t *)(node.blockHeader))->Offset, ((Buf_t *)(node.blockHeader))->Length);
558 if (!debug)
559 goto RebuildBTreeExit;
560 }
561 }
562
563 /* Check node kind - it should either be index node or leaf node */
564 if ( (nodeDescP->kind != kBTIndexNode) && (nodeDescP->kind != kBTLeafNode) )
565 {
566 result = E_NType;
567 RcdError( GPtr, E_NType );
568 if (!debug) goto exit;
569 }
570 /* Check if the height of this node is correct based on calculated
571 * tree depth and current btree level of the traversal
572 */
573 if ( nodeDescP->height != calculatedBTCB->treeDepth - GPtr->BTLevel + 1 )
574 {
575 result = E_NHeight;
576 RcdError( GPtr, E_NHeight );
577 if (!debug) goto RebuildBTreeExit;
578 }
579
580 if (result && (cur_debug_level & d_dump_node))
581 {
582 plog("Node %u:\n", node.blockNum);
583 HexDump(node.buffer, node.blockSize, TRUE);
584 GPtr->BTLevel--;
585 continue;
586 }
587
588 /* If we saved the first key in the parent (index) node in past, use it to compare
589 * with the key of the first record in the current node. This check should
590 * be performed for all nodes except the root node.
591 */
592 if ( hasParKey == true )
593 {
594 GetRecordByIndex( (BTreeControlBlock *)calculatedBTCB, nodeDescP, 0, &keyPtr, &dataPtr, &recSize );
595 if ( CompareKeys( (BTreeControlBlockPtr)calculatedBTCB, (BTreeKey *)parKey, keyPtr ) != 0 )
596 {
597 if (debug)
598 {
599 plog("Index key doesn't match first node key\n");
600 if (cur_debug_level & d_dump_record)
601 {
602 plog("Found (child; node %u):\n", tprP->TPRNodeN);
603 HexDump(keyPtr, CalcKeySize(calculatedBTCB, keyPtr), FALSE);
604 plog("Expected (parent; node %u):\n", tprP[-1].TPRNodeN);
605 HexDump(parKey, CalcKeySize(calculatedBTCB, (BTreeKey *)parKey), FALSE);
606 }
607 }
608 RcdError( GPtr, E_IKey );
609 *statusFlag |= S_RebuildBTree;
610 result = errRebuildBtree;
611 }
612 }
613 if ( nodeDescP->kind == kBTIndexNode )
614 {
615 if ( ( result = CheckForStop( GPtr ) ) )
616 goto exit;
617 }
618
619 GPtr->itemsProcessed++;
620 }
621
622 numRecs = nodeDescP->numRecords;
623
624 /*
625 * for an index node ...
626 */
627 if ( nodeDescP->kind == kBTIndexNode )
628 {
629 index++; /* on to next index record */
630 if ( index >= numRecs )
631 {
632 /* We have traversed children of all index records in this index node.
633 * Decrement the current btree level to access right sibling index record
634 * of previous btree level
635 */
636 GPtr->BTLevel--;
637 continue; /* No more records */
638 }
639
640 /* Store current index for current Btree level */
641 tprP->TPRRIndx = index;
642 /* Store current pointer as parent for next traversal */
643 parentP = tprP;
644 /* Increase the current Btree level because we traverse top to down */
645 GPtr->BTLevel++;
646
647 /* Validate current btree traversal level */
648 if ( GPtr->BTLevel > BTMaxDepth )
649 {
650 RcdError( GPtr, E_BTDepth );
651 goto RebuildBTreeExit;
652 }
653 /* Get the btree traversal state for current btree level */
654 tprP = &(*GPtr->BTPTPtr)[GPtr->BTLevel -1];
655
656 /* Get index record in the current btree level at offset index in the given node */
657 GetRecordByIndex( (BTreeControlBlock *)calculatedBTCB, nodeDescP,
658 index, &keyPtr, &dataPtr, &recSize );
659
660 nodeNum = *(UInt32*)dataPtr;
661 /* Current node number should not be header node number or greater than total nodes */
662 if ( (nodeNum == kHeaderNodeNum) || (nodeNum >= calculatedBTCB->totalNodes) )
663 {
664 RcdError( GPtr, E_IndxLk );
665 goto RebuildBTreeExit;
666 }
667
668 /*
669 * Make a copy of the parent's key so we can compare it
670 * with the child's key later.
671 */
672 keyLen = ( calculatedBTCB->attributes & kBTBigKeysMask )
673 ? keyPtr->length16 + sizeof(UInt16)
674 : keyPtr->length8 + sizeof(UInt8);
675 CopyMemory(keyPtr, parKey, keyLen);
676 hasParKey = true;
677
678 /* Store current node number for the child node */
679 tprP->TPRNodeN = nodeNum;
680 /* Initialize index to records for the child node */
681 tprP->TPRRIndx = -1;
682
683 tprP->TPRLtSib = 0; /* left sibling */
684 if ( index > 0 )
685 {
686 /* Get node number for the previous index record in current index node */
687 GetRecordByIndex( (BTreeControlBlock *)calculatedBTCB, nodeDescP, index-1, &keyPtr, &dataPtr, &recSize );
688
689 nodeNum = *(UInt32*)dataPtr;
690 /* node number should not be header node number or greater than total nodes */
691 if ( (nodeNum == kHeaderNodeNum) || (nodeNum >= calculatedBTCB->totalNodes) )
692 {
693 RcdError( GPtr, E_IndxLk );
694 goto RebuildBTreeExit;
695 }
696 /* Store this as left sibling node */
697 tprP->TPRLtSib = nodeNum;
698 }
699 else
700 {
701 if ( parentP->TPRLtSib != 0 )
702 tprP->TPRLtSib = tprP->TPRRtSib; /* Fill in the missing link */
703 }
704
705 tprP->TPRRtSib = 0; /* right sibling */
706 if ( index < (numRecs -1) )
707 {
708 /* Get node number for the next index record in current index node */
709 GetRecordByIndex( (BTreeControlBlock *)calculatedBTCB, nodeDescP, index+1, &keyPtr, &dataPtr, &recSize );
710
711 nodeNum = *(UInt32*)dataPtr;
712 /* node number should not be header node number or greater than total nodes */
713 if ( (nodeNum == kHeaderNodeNum) || (nodeNum >= calculatedBTCB->totalNodes) )
714 {
715 RcdError( GPtr, E_IndxLk );
716 goto RebuildBTreeExit;
717 }
718 /* Store this as right sibling node */
719 tprP->TPRRtSib = nodeNum;
720 }
721 else
722 {
723 if ( parentP->TPRRtSib != 0 )
724 tprP->TPRRtSib = -1; /* Link to be filled in later */
725 }
726 }
727
728 /*
729 * For a leaf node ...
730 */
731 else
732 {
733 /* If left sibling link is zero, this is first leaf node */
734 if ( tprP->TPRLtSib == 0 )
735 calculatedBTCB->firstLeafNode = nodeNum;
736 /* If right sibling link is zero, this is last leaf node */
737 if ( tprP->TPRRtSib == 0 )
738 calculatedBTCB->lastLeafNode = nodeNum;
739 leafRecords += nodeDescP->numRecords;
740
741 if (checkLeafRecord != NULL) {
742 /* For total number of records in this leaf node, get each record sequentially
743 * and call function to check individual leaf record through the
744 * function pointer passed by the caller
745 */
746 for (i = 0; i < nodeDescP->numRecords; i++) {
747 GetRecordByIndex(calculatedBTCB, nodeDescP, i, &keyPtr, &dataPtr, &recSize);
748 result = checkLeafRecord(GPtr, keyPtr, dataPtr, recSize);
749 if (result) goto exit;
750 }
751 }
752 /* Decrement the current btree level as we want to access
753 * the right sibling index record, if any, of our parent.
754 */
755 GPtr->BTLevel--;
756 continue;
757 }
758 } /* end while */
759
760 calculatedBTCB->leafRecords = leafRecords;
761
762 exit:
763 if (result == noErr && (*statusFlag & S_RebuildBTree))
764 result = errRebuildBtree;
765 if (node.buffer != NULL)
766 (void) ReleaseNode(calculatedBTCB, &node);
767
768 return( result );
769
770 RebuildBTreeExit:
771 /* force a B-Tree file rebuild */
772 *statusFlag |= S_RebuildBTree;
773 result = errRebuildBtree;
774 goto exit;
775
776 } /* end of BTCheck */
777
778
779
780 /*------------------------------------------------------------------------------
781
782 Routine: BTMapChk - (BTree Map Check)
783
784 Function: Checks out the structure of a BTree allocation map.
785
786 Input: GPtr - pointer to scavenger global area
787 fileRefNum - refnum of BTree file
788
789 Output: BTMapChk - function result:
790 0 = no error
791 n = error
792 ------------------------------------------------------------------------------*/
793
794 int BTMapChk( SGlobPtr GPtr, short fileRefNum )
795 {
796 OSErr result;
797 UInt16 recSize;
798 SInt32 mapSize;
799 UInt32 nodeNum;
800 SInt16 recIndx;
801 NodeRec node;
802 NodeDescPtr nodeDescP;
803 BTreeControlBlock *calculatedBTCB = GetBTreeControlBlock( fileRefNum );
804
805 result = noErr;
806 nodeNum = 0; /* Start with header node */
807 node.buffer = NULL;
808 recIndx = 2;
809 mapSize = ( calculatedBTCB->totalNodes + 7 ) / 8; /* size in bytes */
810
811 /*
812 * Enumerate the map structure starting with the map record in the header node
813 */
814 while ( mapSize > 0 )
815 {
816 GPtr->TarBlock = nodeNum;
817
818 if (node.buffer != NULL)
819 (void) ReleaseNode(calculatedBTCB, &node);
820 result = GetNode( calculatedBTCB, nodeNum, &node );
821 if ( result != noErr )
822 {
823 if ( result == fsBTInvalidNodeErr ) /* hfs_swap_BTNode failed */
824 {
825 RcdError( GPtr, E_BadNode );
826 result = E_BadNode;
827 }
828 return( result );
829 }
830
831 nodeDescP = node.buffer;
832
833 /* Check out the node if its not the header node */
834
835 if ( nodeNum != 0 )
836 {
837 result = AllocBTN( GPtr, fileRefNum, nodeNum );
838 if (result) goto exit; /* Error, node already allocated? */
839
840 if ( nodeDescP->kind != kBTMapNode )
841 {
842 RcdError( GPtr, E_BadMapN );
843 if (debug)
844 plog("Expected map node, got type %d\n", nodeDescP->kind);
845 result = E_BadMapN;
846 goto exit;
847 }
848 if ( nodeDescP->numRecords != Num_MRecs )
849 {
850 RcdError( GPtr, E_BadMapN );
851 if (debug)
852 plog("Expected %d records in node, found %d\n", Num_MRecs, nodeDescP->numRecords);
853 result = E_BadMapN;
854 goto exit;
855 }
856 if ( nodeDescP->height != 0 )
857 RcdError( GPtr, E_NHeight );
858 }
859
860 // Move on to the next map node
861 recSize = GetRecordSize( (BTreeControlBlock *)calculatedBTCB, (BTNodeDescriptor *)nodeDescP, recIndx );
862 mapSize -= recSize; /* Adjust remaining map size */
863
864 recIndx = 0; /* Map record is now record 0 */
865 nodeNum = nodeDescP->fLink;
866 if (nodeNum == 0)
867 break;
868
869 } /* end while */
870
871
872 if ( (nodeNum != 0) || (mapSize > 0) )
873 {
874 RcdError( GPtr, E_MapLk);
875 result = E_MapLk; /* bad map node linkage */
876 }
877 exit:
878 if (node.buffer != NULL)
879 (void) ReleaseNode(calculatedBTCB, &node);
880
881 return( result );
882
883 } /* end BTMapChk */
884
885
886
887 /*------------------------------------------------------------------------------
888
889 Routine: BTCheckUnusedNodes
890
891 Function: Examines all unused nodes and makes sure they are filled with zeroes.
892 If there are any unused nodes which are not zero filled, bit mask
893 S_UnusedNodesNotZero is set in output btStat; the function result
894 is zero in this case.
895
896 Input: GPtr - pointer to scavenger global area
897 fileRefNum - refnum of BTree file
898
899 Output: *btStat - bit mask S_UnusedNodesNotZero
900 BTCheckUnusedNodes - function result:
901 0 = no error
902 n = error
903 ------------------------------------------------------------------------------*/
904
905 int BTCheckUnusedNodes(SGlobPtr GPtr, short fileRefNum, UInt16 *btStat)
906 {
907 BTreeControlBlock *btcb = GetBTreeControlBlock(fileRefNum);
908 unsigned char *bitmap = (unsigned char *) ((BTreeExtensionsRec*)btcb->refCon)->BTCBMPtr;
909 unsigned char mask = 0x80;
910 OSErr err;
911 UInt32 nodeNum;
912 BlockDescriptor node;
913
914 node.buffer = NULL;
915
916 for (nodeNum = 0; nodeNum < btcb->totalNodes; ++nodeNum)
917 {
918 if ((*bitmap & mask) == 0)
919 {
920 UInt32 i;
921 UInt32 bufferSize;
922 UInt32 *buffer;
923
924 /* Read the raw node, without going through hfs_swap_BTNode. */
925 err = btcb->getBlockProc(btcb->fcbPtr, nodeNum, kGetBlock, &node);
926 if (err)
927 {
928 if (debug) plog("Couldn't read node #%u\n", nodeNum);
929 return err;
930 }
931
932 /*
933 * Make sure node->blockSize bytes at address node->buffer are zero.
934 */
935 buffer = (UInt32 *) node.buffer;
936 bufferSize = node.blockSize / sizeof(UInt32);
937
938 for (i = 0; i < bufferSize; ++i)
939 {
940 if (buffer[i])
941 {
942 *btStat |= S_UnusedNodesNotZero;
943 GPtr->TarBlock = nodeNum;
944 fsckPrint(GPtr->context, E_UnusedNodeNotZeroed, nodeNum);
945
946 if (!debug)
947 {
948 /* Stop now; repair will zero all unused nodes. */
949 goto done;
950 }
951
952 /* No need to check the rest of this node. */
953 break;
954 }
955 }
956
957 /* Release the node without going through hfs_swap_BTNode. */
958 (void) btcb->releaseBlockProc(btcb->fcbPtr, &node, kReleaseBlock);
959 node.buffer = NULL;
960 }
961
962 /* Move to the next bit in the bitmap. */
963 mask >>= 1;
964 if (mask == 0)
965 {
966 mask = 0x80;
967 ++bitmap;
968 }
969 }
970 done:
971 if (node.buffer)
972 {
973 (void) btcb->releaseBlockProc(btcb->fcbPtr, &node, kReleaseBlock);
974 }
975
976 return 0;
977 } /* end BTCheckUnusedNodes */
978
979
980
981 /*------------------------------------------------------------------------------
982
983 Routine: CmpBTH - (Compare BTree Header)
984
985 Function: Compares the scavenger BTH info with the BTH on disk.
986
987 Input: GPtr - pointer to scavenger global area
988 fileRefNum - file refnum
989
990 Output: CmpBTH - function result:
991 0 = no error
992 n = error
993 ------------------------------------------------------------------------------*/
994
995 OSErr CmpBTH( SGlobPtr GPtr, SInt16 fileRefNum )
996 {
997 OSErr err;
998 BTHeaderRec bTreeHeader;
999 BTreeControlBlock *calculatedBTCB = GetBTreeControlBlock( fileRefNum );
1000 SInt16 *statP;
1001 SFCB * fcb;
1002 short isBTHDamaged = 0;
1003 short printMsg = 0;
1004
1005 switch (fileRefNum) {
1006 case kCalculatedCatalogRefNum:
1007 statP = (SInt16 *)&GPtr->CBTStat;
1008 fcb = GPtr->calculatedCatalogFCB;
1009 break;
1010 case kCalculatedExtentRefNum:
1011 statP = (SInt16 *)&GPtr->EBTStat;
1012 fcb = GPtr->calculatedExtentsFCB;
1013 break;
1014 case kCalculatedAttributesRefNum:
1015 statP = (SInt16 *)&GPtr->ABTStat;
1016 fcb = GPtr->calculatedAttributesFCB;
1017 break;
1018 default:
1019 return (-1);
1020 };
1021
1022 /*
1023 * Get BTree header record from disk
1024 */
1025 GPtr->TarBlock = 0; // Set target node number
1026
1027 err = GetBTreeHeader(GPtr, fcb, &bTreeHeader );
1028 ReturnIfError( err );
1029
1030 if (calculatedBTCB->leafRecords != bTreeHeader.leafRecords) {
1031 char goodStr[32], badStr[32];
1032
1033 printMsg = 1;
1034 fsckPrint(GPtr->context, E_LeafCnt);
1035 sprintf(goodStr, "%ld", (long)calculatedBTCB->leafRecords);
1036 sprintf(badStr, "%ld", (long)bTreeHeader.leafRecords);
1037 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1038 }
1039
1040 if ( calculatedBTCB->treeDepth != bTreeHeader.treeDepth ) {
1041 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1042 plog("\tinvalid tree depth - calculated %d header %d \n",
1043 calculatedBTCB->treeDepth, bTreeHeader.treeDepth);
1044 isBTHDamaged = 1;
1045 } else if ( calculatedBTCB->rootNode != bTreeHeader.rootNode ) {
1046 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1047 plog("\tinvalid root node - calculated %d header %d \n",
1048 calculatedBTCB->rootNode, bTreeHeader.rootNode);
1049 isBTHDamaged = 1;
1050 } else if ( calculatedBTCB->firstLeafNode != bTreeHeader.firstLeafNode ) {
1051 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1052 plog("\tinvalid first leaf node - calculated %d header %d \n",
1053 calculatedBTCB->firstLeafNode, bTreeHeader.firstLeafNode);
1054 isBTHDamaged = 1;
1055 } else if ( calculatedBTCB->lastLeafNode != bTreeHeader.lastLeafNode ) {
1056 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1057 plog("\tinvalid last leaf node - calculated %d header %d \n",
1058 calculatedBTCB->lastLeafNode, bTreeHeader.lastLeafNode);
1059 isBTHDamaged = 1;
1060 } else if ( calculatedBTCB->nodeSize != bTreeHeader.nodeSize ) {
1061 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1062 plog("\tinvalid node size - calculated %d header %d \n",
1063 calculatedBTCB->nodeSize, bTreeHeader.nodeSize);
1064 isBTHDamaged = 1;
1065 } else if ( calculatedBTCB->maxKeyLength != bTreeHeader.maxKeyLength ) {
1066 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1067 plog("\tinvalid max key length - calculated %d header %d \n",
1068 calculatedBTCB->maxKeyLength, bTreeHeader.maxKeyLength);
1069 isBTHDamaged = 1;
1070 } else if ( calculatedBTCB->totalNodes != bTreeHeader.totalNodes ) {
1071 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1072 plog("\tinvalid total nodes - calculated %d header %d \n",
1073 calculatedBTCB->totalNodes, bTreeHeader.totalNodes);
1074 isBTHDamaged = 1;
1075 } else if ( calculatedBTCB->freeNodes != bTreeHeader.freeNodes ) {
1076 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1077 plog("\tinvalid free nodes - calculated %d header %d \n",
1078 calculatedBTCB->freeNodes, bTreeHeader.freeNodes);
1079 isBTHDamaged = 1;
1080 }
1081
1082 if (isBTHDamaged || printMsg) {
1083 *statP = *statP | S_BTH;
1084 if (isBTHDamaged) {
1085 fsckPrint(GPtr->context, E_InvalidBTreeHeader);
1086 }
1087 }
1088 return( noErr );
1089 }
1090
1091
1092
1093 /*------------------------------------------------------------------------------
1094
1095 Routine: CmpBlock
1096
1097 Function: Compares two data blocks for equality.
1098
1099 Input: Blk1Ptr - pointer to 1st data block.
1100 Blk2Ptr - pointer to 2nd data block.
1101 len - size of the blocks (in bytes)
1102
1103 Output: CmpBlock - result code
1104 0 = equal
1105 1 = not equal
1106 ------------------------------------------------------------------------------*/
1107
1108 OSErr CmpBlock( void *block1P, void *block2P, size_t length )
1109 {
1110 Byte *blk1Ptr = block1P;
1111 Byte *blk2Ptr = block2P;
1112
1113 while ( length-- )
1114 if ( *blk1Ptr++ != *blk2Ptr++ )
1115 return( -1 );
1116
1117 return( noErr );
1118
1119 }
1120
1121
1122
1123 /*------------------------------------------------------------------------------
1124
1125 Routine: CmpBTM - (Compare BTree Map)
1126
1127 Function: Compares the scavenger BTM with the BTM on disk.
1128
1129 Input: GPtr - pointer to scavenger global area
1130 fileRefNum - file refnum
1131
1132 Output: CmpBTM - function result:
1133 0 = no error
1134 n = error
1135 ------------------------------------------------------------------------------*/
1136
1137 int CmpBTM( SGlobPtr GPtr, short fileRefNum )
1138 {
1139 OSErr result;
1140 UInt16 recSize;
1141 SInt32 mapSize;
1142 SInt32 size;
1143 UInt32 nodeNum;
1144 short recIndx;
1145 char *p;
1146 char *sbtmP;
1147 UInt8 * dataPtr;
1148 NodeRec node;
1149 NodeDescPtr nodeDescP;
1150 BTreeControlBlock *calculatedBTCB;
1151 UInt16 *statP;
1152
1153 result = noErr;
1154 calculatedBTCB = GetBTreeControlBlock( fileRefNum );
1155
1156 switch (fileRefNum) {
1157 case kCalculatedCatalogRefNum:
1158 statP = &GPtr->CBTStat;
1159 break;
1160 case kCalculatedExtentRefNum:
1161 statP = &GPtr->EBTStat;
1162 break;
1163 case kCalculatedAttributesRefNum:
1164 statP = &GPtr->ABTStat;
1165 break;
1166 default:
1167 return (-1);
1168 };
1169
1170 nodeNum = 0; /* start with header node */
1171 node.buffer = NULL;
1172 recIndx = 2;
1173 recSize = size = 0;
1174 mapSize = (calculatedBTCB->totalNodes + 7) / 8; /* size in bytes */
1175 sbtmP = ((BTreeExtensionsRec*)calculatedBTCB->refCon)->BTCBMPtr;
1176 dataPtr = NULL;
1177
1178 /*
1179 * Enumerate BTree map records starting with map record in header node
1180 */
1181 while ( mapSize > 0 )
1182 {
1183 GPtr->TarBlock = nodeNum;
1184
1185 if (node.buffer != NULL)
1186 (void) ReleaseNode(calculatedBTCB, &node);
1187
1188 result = GetNode( calculatedBTCB, nodeNum, &node );
1189 if (result) goto exit; /* error, could't get map node */
1190
1191 nodeDescP = node.buffer;
1192
1193 recSize = GetRecordSize( (BTreeControlBlock *)calculatedBTCB, (BTNodeDescriptor *)nodeDescP, recIndx );
1194 dataPtr = GetRecordAddress( (BTreeControlBlock *)calculatedBTCB, (BTNodeDescriptor *)nodeDescP, recIndx );
1195
1196 size = ( recSize > mapSize ) ? mapSize : recSize;
1197
1198 result = CmpBlock( sbtmP, dataPtr, size );
1199 if ( result != noErr )
1200 {
1201 *statP = *statP | S_BTM; /* didn't match, mark it damaged */
1202 RcdError(GPtr, E_BadMapN);
1203 result = 0; /* mismatch isn't fatal; let us continue */
1204 goto exit;
1205 }
1206
1207 recIndx = 0; /* map record is now record 0 */
1208 mapSize -= size; /* adjust remaining map size */
1209 sbtmP = sbtmP + size;
1210 nodeNum = nodeDescP->fLink; /* next node number */
1211 if (nodeNum == 0)
1212 break;
1213
1214 } /* end while */
1215
1216 /*
1217 * Make sure the unused portion of the last map record is zero
1218 */
1219 for ( p = (Ptr)dataPtr + size ; p < (Ptr)dataPtr + recSize ; p++ )
1220 if ( *p != 0 )
1221 *statP = *statP | S_BTM; /* didn't match, mark it damaged */
1222
1223 exit:
1224 if (node.buffer != NULL)
1225 (void) ReleaseNode(calculatedBTCB, &node);
1226
1227 return( result );
1228
1229 } /* end CmpBTM */
1230
1231
1232 /*------------------------------------------------------------------------------
1233
1234 Routine: BTKeyChk - (BTree Key Check)
1235
1236 Function: Checks out the key structure within a Btree node.
1237
1238 Input: GPtr - pointer to scavenger global area
1239 NodePtr - pointer to target node
1240 BTCBPtr - pointer to BTreeControlBlock
1241
1242 Output: BTKeyChk - function result:
1243 0 = no error
1244 n = error code
1245 ------------------------------------------------------------------------------*/
1246 extern HFSPlusCatalogKey gMetaDataDirKey;
1247
1248 static int BTKeyChk( SGlobPtr GPtr, NodeDescPtr nodeP, BTreeControlBlock *btcb )
1249 {
1250 SInt16 index;
1251 UInt16 dataSize;
1252 UInt16 keyLength;
1253 UInt16 prevKeyLength = 0;
1254 KeyPtr keyPtr;
1255 UInt8 *dataPtr;
1256 KeyPtr prevkeyP = nil;
1257 unsigned sizeofKeyLength;
1258 int result = noErr;
1259
1260 if (btcb->attributes & kBTBigKeysMask)
1261 sizeofKeyLength = 2;
1262 else
1263 sizeofKeyLength = 1;
1264
1265 if ( nodeP->numRecords == 0 )
1266 {
1267 if ( (nodeP->fLink == 0) && (nodeP->bLink == 0) )
1268 {
1269 RcdError( GPtr, E_BadNode );
1270 return( E_BadNode );
1271 }
1272 }
1273 else
1274 {
1275 /*
1276 * Loop on number of records in node
1277 */
1278 for ( index = 0; index < nodeP->numRecords; index++)
1279 {
1280 GetRecordByIndex( (BTreeControlBlock *)btcb, nodeP, (UInt16) index, &keyPtr, &dataPtr, &dataSize );
1281
1282 if (btcb->attributes & kBTBigKeysMask)
1283 keyLength = keyPtr->length16;
1284 else
1285 keyLength = keyPtr->length8;
1286
1287 if ( keyLength > btcb->maxKeyLength )
1288 {
1289 RcdError( GPtr, E_KeyLen );
1290 return( E_KeyLen );
1291 }
1292
1293 if ( prevkeyP != nil )
1294 {
1295 if ( CompareKeys( (BTreeControlBlockPtr)btcb, prevkeyP, keyPtr ) >= 0 )
1296 {
1297 /*
1298 * When the HFS+ MetaDataDirKey is out of order we mark
1299 * the result code so that it can be deleted later.
1300 */
1301 if ((btcb->maxKeyLength == kHFSPlusCatalogKeyMaximumLength) &&
1302 (CompareKeys(btcb, prevkeyP, (KeyPtr)&gMetaDataDirKey) == 0))
1303 {
1304 if (fsckGetVerbosity(GPtr->context) > 0)
1305 plog("Problem: b-tree key for \"HFS+ Private Data\" directory is out of order.\n");
1306 return( E_KeyOrd + 1000 );
1307 }
1308 else
1309 {
1310 RcdError( GPtr, E_KeyOrd );
1311 if (fsckGetVerbosity(GPtr->context) > 0)
1312 plog("Records %d and %d (0-based); offsets 0x%04X and 0x%04X\n", index-1, index, (long)prevkeyP - (long)nodeP, (long)keyPtr - (long)nodeP);
1313 result = E_KeyOrd;
1314 }
1315 }
1316 }
1317 prevkeyP = keyPtr;
1318 prevKeyLength = keyLength;
1319 }
1320 }
1321
1322 if (result == E_KeyOrd)
1323 {
1324 if (cur_debug_level & d_dump_record)
1325 {
1326 for (index = 0; index < nodeP->numRecords; ++index)
1327 {
1328 GetRecordByIndex( (BTreeControlBlock *)btcb, nodeP, (UInt16) index, &keyPtr, &dataPtr, &dataSize );
1329
1330 if (btcb->attributes & kBTBigKeysMask)
1331 keyLength = keyPtr->length16;
1332 else
1333 keyLength = keyPtr->length8;
1334
1335 plog("Record %d (offset 0x%04X):\n", index, (long)keyPtr - (long)nodeP);
1336 HexDump(keyPtr, keyLength + sizeofKeyLength, FALSE);
1337 plog("--\n");
1338 HexDump(dataPtr, dataSize, FALSE);
1339 plog("\n");
1340 }
1341 }
1342
1343 if (cur_debug_level & d_dump_node)
1344 {
1345 plog("Node:\n");
1346 HexDump(nodeP, btcb->nodeSize, TRUE);
1347 }
1348 }
1349
1350 return( result );
1351 }
1352
1353
1354
1355 /*------------------------------------------------------------------------------
1356
1357 Routine: ChkCName (Check Catalog Name)
1358
1359 Function: Checks out a generic catalog name.
1360
1361 Input: GPtr - pointer to scavenger global area.
1362 CNamePtr - pointer to CName.
1363
1364 Output: ChkCName - function result:
1365 0 = CName is OK
1366 E_CName = invalid CName
1367 ------------------------------------------------------------------------------*/
1368
1369 OSErr ChkCName( SGlobPtr GPtr, const CatalogName *name, Boolean unicode )
1370 {
1371 UInt32 length;
1372 OSErr err = noErr;
1373
1374 length = CatalogNameLength( name, unicode );
1375
1376 if ( unicode )
1377 {
1378 if ( (length == 0) || (length > kHFSPlusMaxFileNameChars) )
1379 err = E_CName;
1380 }
1381 else
1382 {
1383 if ( (length == 0) || (length > kHFSMaxFileNameChars) )
1384 err = E_CName;
1385 }
1386
1387 return( err );
1388 }
1389
1390
1391 /*------------------------------------------------------------------------------
1392
1393 Routine: CmpMDB - (Compare Master Directory Block)
1394
1395 Function: Compares the scavenger MDB info with the MDB on disk.
1396
1397 Input: GPtr - pointer to scavenger global area
1398
1399 Output: CmpMDB - function result:
1400 0 = no error
1401 n = error
1402 GPtr->VIStat - S_MDB flag set in VIStat if MDB is damaged.
1403 ------------------------------------------------------------------------------*/
1404
1405 int CmpMDB( SGlobPtr GPtr, HFSMasterDirectoryBlock * mdbP)
1406 {
1407 short i;
1408 SFCB * fcbP;
1409 SVCB * vcb;
1410 short printMsg = 0;
1411 short isMDBDamaged = 0;
1412
1413 // Set up
1414 GPtr->TarID = MDB_FNum;
1415 vcb = GPtr->calculatedVCB;
1416
1417 /*
1418 * compare VCB info with MDB
1419 */
1420 if ( mdbP->drSigWord != vcb->vcbSignature ) {
1421 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1422 plog( "\tinvalid MDB drSigWord \n" );
1423 isMDBDamaged = 1;
1424 }
1425 if ( mdbP->drCrDate != vcb->vcbCreateDate ) {
1426 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1427 plog( "\tinvalid MDB drCrDate \n" );
1428 isMDBDamaged = 1;
1429 }
1430 if ( mdbP->drLsMod != vcb->vcbModifyDate ) {
1431 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1432 plog( "\tinvalid MDB drLsMod \n" );
1433 isMDBDamaged = 1;
1434 }
1435 if ( mdbP->drAtrb != (UInt16)vcb->vcbAttributes ) {
1436 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1437 plog( "\tinvalid MDB drAtrb \n" );
1438 isMDBDamaged = 1;
1439 }
1440 if ( mdbP->drVBMSt != vcb->vcbVBMSt ) {
1441 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1442 plog( "\tinvalid MDB drVBMSt \n" );
1443 isMDBDamaged = 1;
1444 }
1445 if ( mdbP->drNmAlBlks != vcb->vcbTotalBlocks ) {
1446 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1447 plog( "\tinvalid MDB drNmAlBlks \n" );
1448 isMDBDamaged = 1;
1449 }
1450 if ( mdbP->drClpSiz != vcb->vcbDataClumpSize ) {
1451 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1452 plog( "\tinvalid MDB drClpSiz \n" );
1453 isMDBDamaged = 1;
1454 }
1455 if ( mdbP->drAlBlSt != vcb->vcbAlBlSt ) {
1456 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1457 plog( "\tinvalid MDB drAlBlSt \n" );
1458 isMDBDamaged = 1;
1459 }
1460 if ( mdbP->drNxtCNID != vcb->vcbNextCatalogID ) {
1461 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1462 plog( "\tinvalid MDB drNxtCNID \n" );
1463 isMDBDamaged = 1;
1464 }
1465 if ( CmpBlock( mdbP->drVN, vcb->vcbVN, mdbP->drVN[0]+1 ) ) {
1466 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1467 plog( "\tinvalid MDB drVN \n" );
1468 isMDBDamaged = 1;
1469 }
1470 if ( mdbP->drVolBkUp != vcb->vcbBackupDate ) {
1471 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1472 plog( "\tinvalid MDB drVolBkUp \n" );
1473 isMDBDamaged = 1;
1474 }
1475 if ( mdbP->drVSeqNum != vcb->vcbVSeqNum ) {
1476 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1477 plog( "\tinvalid MDB drVSeqNum \n" );
1478 isMDBDamaged = 1;
1479 }
1480 if ( mdbP->drWrCnt != vcb->vcbWriteCount ) {
1481 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1482 plog( "\tinvalid MDB drWrCnt \n" );
1483 isMDBDamaged = 1;
1484 }
1485 if ( mdbP->drXTClpSiz != vcb->vcbExtentsFile->fcbClumpSize ) {
1486 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1487 plog( "\tinvalid MDB drXTClpSiz \n" );
1488 isMDBDamaged = 1;
1489 }
1490 if ( mdbP->drCTClpSiz != vcb->vcbCatalogFile->fcbClumpSize ) {
1491 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1492 plog( "\tinvalid MDB drCTClpSiz \n" );
1493 isMDBDamaged = 1;
1494 }
1495 if ( mdbP->drNmRtDirs != vcb->vcbNmRtDirs ) {
1496 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1497 plog( "\tinvalid MDB drNmRtDirs \n" );
1498 isMDBDamaged = 1;
1499 }
1500 if ( mdbP->drFilCnt != vcb->vcbFileCount ) {
1501 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1502 plog( "\tinvalid MDB drFilCnt \n" );
1503 isMDBDamaged = 1;
1504 }
1505 if ( mdbP->drDirCnt != vcb->vcbFolderCount ) {
1506 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1507 plog( "\tinvalid MDB drDirCnt \n" );
1508 isMDBDamaged = 1;
1509 }
1510 if ( CmpBlock(mdbP->drFndrInfo, vcb->vcbFinderInfo, 32 ) ) {
1511 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1512 plog( "\tinvalid MDB drFndrInfo \n" );
1513 isMDBDamaged = 1;
1514 }
1515
1516 /*
1517 * compare extent file allocation info with MDB
1518 */
1519 fcbP = vcb->vcbExtentsFile; /* compare PEOF for extent file */
1520 if ( mdbP->drXTFlSize != fcbP->fcbPhysicalSize )
1521 {
1522 printMsg = 1;
1523 WriteError ( GPtr, E_MDBDamaged, 3, 0 );
1524 }
1525 for ( i = 0; i < GPtr->numExtents; i++ )
1526 {
1527 if ( (mdbP->drXTExtRec[i].startBlock != fcbP->fcbExtents16[i].startBlock) ||
1528 (mdbP->drXTExtRec[i].blockCount != fcbP->fcbExtents16[i].blockCount) )
1529 {
1530 printMsg = 1;
1531 WriteError ( GPtr, E_MDBDamaged, 4, 0 );
1532 }
1533 }
1534
1535 /*
1536 * compare catalog file allocation info with MDB
1537 */
1538 fcbP = vcb->vcbCatalogFile; /* compare PEOF for catalog file */
1539 if ( mdbP->drCTFlSize != fcbP->fcbPhysicalSize )
1540 {
1541 printMsg = 1;
1542 WriteError ( GPtr, E_MDBDamaged, 5, 0 );
1543 }
1544 for ( i = 0; i < GPtr->numExtents; i++ )
1545 {
1546 if ( (mdbP->drCTExtRec[i].startBlock != fcbP->fcbExtents16[i].startBlock) ||
1547 (mdbP->drCTExtRec[i].blockCount != fcbP->fcbExtents16[i].blockCount) )
1548 {
1549 printMsg = 1;
1550 WriteError ( GPtr, E_MDBDamaged, 6, 0 );
1551 }
1552 }
1553
1554 if (isMDBDamaged || printMsg) {
1555 GPtr->VIStat = GPtr->VIStat | S_MDB;
1556 if (isMDBDamaged)
1557 WriteError ( GPtr, E_MDBDamaged, 1, 0 );
1558 }
1559 return( noErr );
1560
1561 } /* end CmpMDB */
1562
1563
1564
1565 /*------------------------------------------------------------------------------
1566
1567 Routine: CompareVolumeHeader - (Compare VolumeHeader Block)
1568
1569 Function: Compares the scavenger VolumeHeader info with the VolumeHeader on disk.
1570
1571 Input: GPtr - pointer to scavenger global area
1572
1573 Output: CmpMDB - function result:
1574 0 = no error
1575 n = error
1576 GPtr->VIStat - S_MDB flag set in VIStat if MDB is damaged.
1577 ------------------------------------------------------------------------------*/
1578
1579 OSErr CompareVolumeHeader( SGlobPtr GPtr, HFSPlusVolumeHeader *volumeHeader )
1580 {
1581 SInt16 i;
1582 SVCB *vcb;
1583 SFCB *fcbP;
1584 UInt32 hfsPlusIOPosOffset;
1585 UInt32 goodValue, badValue;
1586 char goodStr[32], badStr[32];
1587 short isVHDamaged;
1588 short printMsg;
1589
1590 vcb = GPtr->calculatedVCB;
1591 GPtr->TarID = MDB_FNum;
1592
1593 hfsPlusIOPosOffset = vcb->vcbEmbeddedOffset;
1594
1595 goodValue = badValue = 0;
1596 isVHDamaged = 0;
1597 printMsg = 0;
1598
1599 // CatHChk will flag valence errors and display the good and bad values for
1600 // our file and folder counts. It will set S_Valence in CatStat when this
1601 // problem is detected. We do NOT want to flag the error here in that case
1602 // since the volume header counts cannot be trusted and it will lead to
1603 // confusing messages.
1604 if ( volumeHeader->fileCount != vcb->vcbFileCount &&
1605 (GPtr->CatStat & S_Valence) == 0 ) {
1606 fsckPrint(GPtr->context, E_FilCnt);
1607 sprintf(goodStr, "%u", vcb->vcbFileCount);
1608 sprintf(badStr, "%u", volumeHeader->fileCount);
1609 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1610 printMsg = 1;
1611 }
1612
1613 if ( volumeHeader->folderCount != vcb->vcbFolderCount &&
1614 (GPtr->CatStat & S_Valence) == 0 ) {
1615 fsckPrint(GPtr->context, E_DirCnt);
1616 sprintf(goodStr, "%u", vcb->vcbFolderCount);
1617 sprintf(badStr, "%u", volumeHeader->folderCount);
1618 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1619
1620 printMsg = 1;
1621 }
1622
1623 if (volumeHeader->freeBlocks != vcb->vcbFreeBlocks) {
1624 fsckPrint(GPtr->context, E_FreeBlocks);
1625 sprintf(goodStr, "%u", vcb->vcbFreeBlocks);
1626 sprintf(badStr, "%u", volumeHeader->freeBlocks);
1627 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1628 printMsg = 1;
1629 }
1630
1631 if ( volumeHeader->catalogFile.clumpSize != vcb->vcbCatalogFile->fcbClumpSize ) {
1632 fsckPrint(GPtr->context, E_InvalidClumpSize);
1633 sprintf(goodStr, "%u", vcb->vcbCatalogFile->fcbClumpSize);
1634 sprintf(badStr, "%u", volumeHeader->catalogFile.clumpSize);
1635 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1636 printMsg = 1;
1637 }
1638
1639 if ( volumeHeader->signature != kHFSPlusSigWord &&
1640 volumeHeader->signature != kHFSXSigWord) {
1641 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1642 plog( "\tinvalid VHB signature \n" );
1643 isVHDamaged = 1;
1644 }
1645 /* From HFS Plus Volume Format Specification (TN1150), "It is acceptable
1646 * for a bit in encodingsBitmap to be set even though no names on the
1647 * volume use that encoding". Therefore we do not report extra bits set in
1648 * on-disk encodingsBitmap as error but will repair it silently if any other
1649 * repairs are made. We complain about extra bits cleared in
1650 * on-disk encodingsBitmap when compared to calculated encodingsBitmap.
1651 */
1652 if ( (volumeHeader->encodingsBitmap & vcb->vcbEncodingsBitmap)
1653 != vcb->vcbEncodingsBitmap ) {
1654 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1655 plog( "\tinvalid VHB encodingsBitmap, disk=0x%qx calculated=0x%qx \n", volumeHeader->encodingsBitmap, vcb->vcbEncodingsBitmap );
1656 isVHDamaged = 1;
1657 }
1658 if ( (UInt16) (hfsPlusIOPosOffset/512) != vcb->vcbAlBlSt ) {
1659 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1660 plog( "\tinvalid VHB AlBlSt \n" );
1661 isVHDamaged = 1;
1662 }
1663 if ( volumeHeader->createDate != vcb->vcbCreateDate ) {
1664 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1665 plog( "\tinvalid VHB createDate \n" );
1666 isVHDamaged = 1;
1667 }
1668 if ( volumeHeader->modifyDate != vcb->vcbModifyDate ) {
1669 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1670 plog( "\tinvalid VHB modifyDate \n" );
1671 isVHDamaged = 1;
1672 }
1673 if ( volumeHeader->backupDate != vcb->vcbBackupDate ) {
1674 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1675 plog( "\tinvalid VHB backupDate \n" );
1676 isVHDamaged = 1;
1677 }
1678 if ( volumeHeader->checkedDate != vcb->vcbCheckedDate ) {
1679 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1680 plog( "\tinvalid VHB checkedDate \n" );
1681 isVHDamaged = 1;
1682 }
1683 if ( volumeHeader->rsrcClumpSize != vcb->vcbRsrcClumpSize ) {
1684 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1685 plog( "\tinvalid VHB rsrcClumpSize (VH=%u, vcb=%u)\n", volumeHeader->rsrcClumpSize, vcb->vcbRsrcClumpSize);
1686 isVHDamaged = 1;
1687 }
1688 if ( volumeHeader->dataClumpSize != vcb->vcbDataClumpSize ) {
1689 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1690 plog( "\tinvalid VHB dataClumpSize \n" );
1691 isVHDamaged = 1;
1692 }
1693 if ( volumeHeader->nextCatalogID != vcb->vcbNextCatalogID &&
1694 (volumeHeader->attributes & kHFSCatalogNodeIDsReused) == 0) {
1695 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1696 plog( "\tinvalid VHB nextCatalogID \n" );
1697 isVHDamaged = 1;
1698 }
1699 if ( volumeHeader->writeCount != vcb->vcbWriteCount ) {
1700 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1701 plog( "\tinvalid VHB writeCount \n" );
1702 isVHDamaged = 1;
1703 }
1704 if ( volumeHeader->nextAllocation != vcb->vcbNextAllocation ) {
1705 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1706 plog( "\tinvalid VHB nextAllocation \n" );
1707 isVHDamaged = 1;
1708 }
1709 if ( volumeHeader->totalBlocks != vcb->vcbTotalBlocks ) {
1710 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1711 plog( "\tinvalid VHB totalBlocks \n" );
1712 isVHDamaged = 1;
1713 }
1714 if ( volumeHeader->blockSize != vcb->vcbBlockSize ) {
1715 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1716 plog( "\tinvalid VHB blockSize \n" );
1717 isVHDamaged = 1;
1718 }
1719 if ( volumeHeader->attributes != vcb->vcbAttributes ) {
1720 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1721 plog( "\tinvalid VHB attributes \n" );
1722 isVHDamaged = 1;
1723 }
1724 if ( volumeHeader->extentsFile.clumpSize != vcb->vcbExtentsFile->fcbClumpSize ) {
1725 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1726 plog( "\tinvalid VHB extentsFile.clumpSize \n" );
1727 isVHDamaged = 1;
1728 }
1729 if ( volumeHeader->allocationFile.clumpSize != vcb->vcbAllocationFile->fcbClumpSize ) {
1730 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1731 plog( "\tinvalid VHB allocationFile.clumpSize \n" );
1732 isVHDamaged = 1;
1733 }
1734 if ( (vcb->vcbAttributesFile != NULL) &&
1735 (volumeHeader->attributesFile.clumpSize != vcb->vcbAttributesFile->fcbClumpSize )) {
1736 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1737 plog( "\tinvalid VHB attributesFile.clumpSize \n" );
1738 isVHDamaged = 1;
1739 }
1740 if ( CmpBlock( volumeHeader->finderInfo, vcb->vcbFinderInfo, sizeof(vcb->vcbFinderInfo) ) ) {
1741 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1742 plog( "\tinvalid VHB finderInfo \n" );
1743 isVHDamaged = 1;
1744 }
1745
1746 /*
1747 * compare extent file allocation info with VolumeHeader
1748 */
1749 fcbP = vcb->vcbExtentsFile;
1750 if ( (UInt64)volumeHeader->extentsFile.totalBlocks * (UInt64)vcb->vcbBlockSize != fcbP->fcbPhysicalSize )
1751 {
1752 printMsg = 1;
1753 WriteError ( GPtr, E_VolumeHeaderDamaged, 3, 0 );
1754 }
1755 for ( i=0; i < GPtr->numExtents; i++ )
1756 {
1757 if ( (volumeHeader->extentsFile.extents[i].startBlock != fcbP->fcbExtents32[i].startBlock) ||
1758 (volumeHeader->extentsFile.extents[i].blockCount != fcbP->fcbExtents32[i].blockCount) )
1759 {
1760 printMsg = 1;
1761 WriteError ( GPtr, E_VolumeHeaderDamaged, 4, 0 );
1762 }
1763 }
1764
1765 /*
1766 * compare catalog file allocation info with MDB
1767 */
1768 fcbP = vcb->vcbCatalogFile; /* compare PEOF for catalog file */
1769 if ( (UInt64)volumeHeader->catalogFile.totalBlocks * (UInt64)vcb->vcbBlockSize != fcbP->fcbPhysicalSize )
1770 {
1771 printMsg = 1;
1772 WriteError ( GPtr, E_VolumeHeaderDamaged, 5, 0 );
1773 }
1774 for ( i=0; i < GPtr->numExtents; i++ )
1775 {
1776 if ( (volumeHeader->catalogFile.extents[i].startBlock != fcbP->fcbExtents32[i].startBlock) ||
1777 (volumeHeader->catalogFile.extents[i].blockCount != fcbP->fcbExtents32[i].blockCount) )
1778 {
1779 printMsg = 1;
1780 WriteError ( GPtr, E_VolumeHeaderDamaged, 6, 0 );
1781 }
1782 }
1783
1784
1785 /*
1786 * compare bitmap file allocation info with MDB
1787 */
1788 fcbP = vcb->vcbAllocationFile;
1789 if ( (UInt64)volumeHeader->allocationFile.totalBlocks * (UInt64)vcb->vcbBlockSize != fcbP->fcbPhysicalSize )
1790 {
1791 printMsg = 1;
1792 WriteError ( GPtr, E_VolumeHeaderDamaged, 7, 0 );
1793 }
1794 for ( i=0; i < GPtr->numExtents; i++ )
1795 {
1796 if ( (volumeHeader->allocationFile.extents[i].startBlock != fcbP->fcbExtents32[i].startBlock) ||
1797 (volumeHeader->allocationFile.extents[i].blockCount != fcbP->fcbExtents32[i].blockCount) )
1798 {
1799 printMsg = 1;
1800 WriteError ( GPtr, E_VolumeHeaderDamaged, 8, 0 );
1801 }
1802 }
1803
1804 if (isVHDamaged || printMsg) {
1805 GPtr->VIStat = GPtr->VIStat | S_MDB;
1806 if (isVHDamaged)
1807 WriteError ( GPtr, E_VolumeHeaderDamaged, 2, 0 );
1808 }
1809
1810 return( noErr );
1811 }
1812
mirror of hfs