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


4280b9cbca0eaba789406796e28eef16175c9d5c
[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 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);
1312 result = E_KeyOrd;
1313 }
1314 }
1315 }
1316 prevkeyP = keyPtr;
1317 prevKeyLength = keyLength;
1318 }
1319 }
1320
1321 if (result == E_KeyOrd)
1322 {
1323 if (cur_debug_level & d_dump_record)
1324 {
1325 for (index = 0; index < nodeP->numRecords; ++index)
1326 {
1327 GetRecordByIndex( (BTreeControlBlock *)btcb, nodeP, (UInt16) index, &keyPtr, &dataPtr, &dataSize );
1328
1329 if (btcb->attributes & kBTBigKeysMask)
1330 keyLength = keyPtr->length16;
1331 else
1332 keyLength = keyPtr->length8;
1333
1334 plog("Record %d (offset 0x%04X):\n", index, (long)keyPtr - (long)nodeP);
1335 HexDump(keyPtr, keyLength + sizeofKeyLength, FALSE);
1336 plog("--\n");
1337 HexDump(dataPtr, dataSize, FALSE);
1338 plog("\n");
1339 }
1340 }
1341
1342 if (cur_debug_level & d_dump_node)
1343 {
1344 plog("Node:\n");
1345 HexDump(nodeP, btcb->nodeSize, TRUE);
1346 }
1347 }
1348
1349 return( result );
1350 }
1351
1352
1353
1354 /*------------------------------------------------------------------------------
1355
1356 Routine: ChkCName (Check Catalog Name)
1357
1358 Function: Checks out a generic catalog name.
1359
1360 Input: GPtr - pointer to scavenger global area.
1361 CNamePtr - pointer to CName.
1362
1363 Output: ChkCName - function result:
1364 0 = CName is OK
1365 E_CName = invalid CName
1366 ------------------------------------------------------------------------------*/
1367
1368 OSErr ChkCName( SGlobPtr GPtr, const CatalogName *name, Boolean unicode )
1369 {
1370 UInt32 length;
1371 OSErr err = noErr;
1372
1373 length = CatalogNameLength( name, unicode );
1374
1375 if ( unicode )
1376 {
1377 if ( (length == 0) || (length > kHFSPlusMaxFileNameChars) )
1378 err = E_CName;
1379 }
1380 else
1381 {
1382 if ( (length == 0) || (length > kHFSMaxFileNameChars) )
1383 err = E_CName;
1384 }
1385
1386 return( err );
1387 }
1388
1389
1390 /*------------------------------------------------------------------------------
1391
1392 Routine: CmpMDB - (Compare Master Directory Block)
1393
1394 Function: Compares the scavenger MDB info with the MDB on disk.
1395
1396 Input: GPtr - pointer to scavenger global area
1397
1398 Output: CmpMDB - function result:
1399 0 = no error
1400 n = error
1401 GPtr->VIStat - S_MDB flag set in VIStat if MDB is damaged.
1402 ------------------------------------------------------------------------------*/
1403
1404 int CmpMDB( SGlobPtr GPtr, HFSMasterDirectoryBlock * mdbP)
1405 {
1406 short i;
1407 SFCB * fcbP;
1408 SVCB * vcb;
1409 short printMsg = 0;
1410 short isMDBDamaged = 0;
1411
1412 // Set up
1413 GPtr->TarID = MDB_FNum;
1414 vcb = GPtr->calculatedVCB;
1415
1416 /*
1417 * compare VCB info with MDB
1418 */
1419 if ( mdbP->drSigWord != vcb->vcbSignature ) {
1420 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1421 plog( "\tinvalid MDB drSigWord \n" );
1422 isMDBDamaged = 1;
1423 }
1424 if ( mdbP->drCrDate != vcb->vcbCreateDate ) {
1425 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1426 plog( "\tinvalid MDB drCrDate \n" );
1427 isMDBDamaged = 1;
1428 }
1429 if ( mdbP->drLsMod != vcb->vcbModifyDate ) {
1430 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1431 plog( "\tinvalid MDB drLsMod \n" );
1432 isMDBDamaged = 1;
1433 }
1434 if ( mdbP->drAtrb != (UInt16)vcb->vcbAttributes ) {
1435 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1436 plog( "\tinvalid MDB drAtrb \n" );
1437 isMDBDamaged = 1;
1438 }
1439 if ( mdbP->drVBMSt != vcb->vcbVBMSt ) {
1440 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1441 plog( "\tinvalid MDB drVBMSt \n" );
1442 isMDBDamaged = 1;
1443 }
1444 if ( mdbP->drNmAlBlks != vcb->vcbTotalBlocks ) {
1445 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1446 plog( "\tinvalid MDB drNmAlBlks \n" );
1447 isMDBDamaged = 1;
1448 }
1449 if ( mdbP->drClpSiz != vcb->vcbDataClumpSize ) {
1450 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1451 plog( "\tinvalid MDB drClpSiz \n" );
1452 isMDBDamaged = 1;
1453 }
1454 if ( mdbP->drAlBlSt != vcb->vcbAlBlSt ) {
1455 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1456 plog( "\tinvalid MDB drAlBlSt \n" );
1457 isMDBDamaged = 1;
1458 }
1459 if ( mdbP->drNxtCNID != vcb->vcbNextCatalogID ) {
1460 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1461 plog( "\tinvalid MDB drNxtCNID \n" );
1462 isMDBDamaged = 1;
1463 }
1464 if ( CmpBlock( mdbP->drVN, vcb->vcbVN, mdbP->drVN[0]+1 ) ) {
1465 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1466 plog( "\tinvalid MDB drVN \n" );
1467 isMDBDamaged = 1;
1468 }
1469 if ( mdbP->drVolBkUp != vcb->vcbBackupDate ) {
1470 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1471 plog( "\tinvalid MDB drVolBkUp \n" );
1472 isMDBDamaged = 1;
1473 }
1474 if ( mdbP->drVSeqNum != vcb->vcbVSeqNum ) {
1475 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1476 plog( "\tinvalid MDB drVSeqNum \n" );
1477 isMDBDamaged = 1;
1478 }
1479 if ( mdbP->drWrCnt != vcb->vcbWriteCount ) {
1480 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1481 plog( "\tinvalid MDB drWrCnt \n" );
1482 isMDBDamaged = 1;
1483 }
1484 if ( mdbP->drXTClpSiz != vcb->vcbExtentsFile->fcbClumpSize ) {
1485 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1486 plog( "\tinvalid MDB drXTClpSiz \n" );
1487 isMDBDamaged = 1;
1488 }
1489 if ( mdbP->drCTClpSiz != vcb->vcbCatalogFile->fcbClumpSize ) {
1490 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1491 plog( "\tinvalid MDB drCTClpSiz \n" );
1492 isMDBDamaged = 1;
1493 }
1494 if ( mdbP->drNmRtDirs != vcb->vcbNmRtDirs ) {
1495 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1496 plog( "\tinvalid MDB drNmRtDirs \n" );
1497 isMDBDamaged = 1;
1498 }
1499 if ( mdbP->drFilCnt != vcb->vcbFileCount ) {
1500 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1501 plog( "\tinvalid MDB drFilCnt \n" );
1502 isMDBDamaged = 1;
1503 }
1504 if ( mdbP->drDirCnt != vcb->vcbFolderCount ) {
1505 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1506 plog( "\tinvalid MDB drDirCnt \n" );
1507 isMDBDamaged = 1;
1508 }
1509 if ( CmpBlock(mdbP->drFndrInfo, vcb->vcbFinderInfo, 32 ) ) {
1510 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1511 plog( "\tinvalid MDB drFndrInfo \n" );
1512 isMDBDamaged = 1;
1513 }
1514
1515 /*
1516 * compare extent file allocation info with MDB
1517 */
1518 fcbP = vcb->vcbExtentsFile; /* compare PEOF for extent file */
1519 if ( mdbP->drXTFlSize != fcbP->fcbPhysicalSize )
1520 {
1521 printMsg = 1;
1522 WriteError ( GPtr, E_MDBDamaged, 3, 0 );
1523 }
1524 for ( i = 0; i < GPtr->numExtents; i++ )
1525 {
1526 if ( (mdbP->drXTExtRec[i].startBlock != fcbP->fcbExtents16[i].startBlock) ||
1527 (mdbP->drXTExtRec[i].blockCount != fcbP->fcbExtents16[i].blockCount) )
1528 {
1529 printMsg = 1;
1530 WriteError ( GPtr, E_MDBDamaged, 4, 0 );
1531 }
1532 }
1533
1534 /*
1535 * compare catalog file allocation info with MDB
1536 */
1537 fcbP = vcb->vcbCatalogFile; /* compare PEOF for catalog file */
1538 if ( mdbP->drCTFlSize != fcbP->fcbPhysicalSize )
1539 {
1540 printMsg = 1;
1541 WriteError ( GPtr, E_MDBDamaged, 5, 0 );
1542 }
1543 for ( i = 0; i < GPtr->numExtents; i++ )
1544 {
1545 if ( (mdbP->drCTExtRec[i].startBlock != fcbP->fcbExtents16[i].startBlock) ||
1546 (mdbP->drCTExtRec[i].blockCount != fcbP->fcbExtents16[i].blockCount) )
1547 {
1548 printMsg = 1;
1549 WriteError ( GPtr, E_MDBDamaged, 6, 0 );
1550 }
1551 }
1552
1553 if (isMDBDamaged || printMsg) {
1554 GPtr->VIStat = GPtr->VIStat | S_MDB;
1555 if (isMDBDamaged)
1556 WriteError ( GPtr, E_MDBDamaged, 1, 0 );
1557 }
1558 return( noErr );
1559
1560 } /* end CmpMDB */
1561
1562
1563
1564 /*------------------------------------------------------------------------------
1565
1566 Routine: CompareVolumeHeader - (Compare VolumeHeader Block)
1567
1568 Function: Compares the scavenger VolumeHeader info with the VolumeHeader on disk.
1569
1570 Input: GPtr - pointer to scavenger global area
1571
1572 Output: CmpMDB - function result:
1573 0 = no error
1574 n = error
1575 GPtr->VIStat - S_MDB flag set in VIStat if MDB is damaged.
1576 ------------------------------------------------------------------------------*/
1577
1578 OSErr CompareVolumeHeader( SGlobPtr GPtr, HFSPlusVolumeHeader *volumeHeader )
1579 {
1580 SInt16 i;
1581 SVCB *vcb;
1582 SFCB *fcbP;
1583 UInt32 hfsPlusIOPosOffset;
1584 UInt32 goodValue, badValue;
1585 char goodStr[32], badStr[32];
1586 short isVHDamaged;
1587 short printMsg;
1588
1589 vcb = GPtr->calculatedVCB;
1590 GPtr->TarID = MDB_FNum;
1591
1592 hfsPlusIOPosOffset = vcb->vcbEmbeddedOffset;
1593
1594 goodValue = badValue = 0;
1595 isVHDamaged = 0;
1596 printMsg = 0;
1597
1598 // CatHChk will flag valence errors and display the good and bad values for
1599 // our file and folder counts. It will set S_Valence in CatStat when this
1600 // problem is detected. We do NOT want to flag the error here in that case
1601 // since the volume header counts cannot be trusted and it will lead to
1602 // confusing messages.
1603 if ( volumeHeader->fileCount != vcb->vcbFileCount &&
1604 (GPtr->CatStat & S_Valence) == 0 ) {
1605 fsckPrint(GPtr->context, E_FilCnt);
1606 sprintf(goodStr, "%u", vcb->vcbFileCount);
1607 sprintf(badStr, "%u", volumeHeader->fileCount);
1608 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1609 printMsg = 1;
1610 }
1611
1612 if ( volumeHeader->folderCount != vcb->vcbFolderCount &&
1613 (GPtr->CatStat & S_Valence) == 0 ) {
1614 fsckPrint(GPtr->context, E_DirCnt);
1615 sprintf(goodStr, "%u", vcb->vcbFolderCount);
1616 sprintf(badStr, "%u", volumeHeader->folderCount);
1617 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1618
1619 printMsg = 1;
1620 }
1621
1622 if (volumeHeader->freeBlocks != vcb->vcbFreeBlocks) {
1623 fsckPrint(GPtr->context, E_FreeBlocks);
1624 sprintf(goodStr, "%u", vcb->vcbFreeBlocks);
1625 sprintf(badStr, "%u", volumeHeader->freeBlocks);
1626 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1627 printMsg = 1;
1628 }
1629
1630 if ( volumeHeader->catalogFile.clumpSize != vcb->vcbCatalogFile->fcbClumpSize ) {
1631 fsckPrint(GPtr->context, E_InvalidClumpSize);
1632 sprintf(goodStr, "%u", vcb->vcbCatalogFile->fcbClumpSize);
1633 sprintf(badStr, "%u", volumeHeader->catalogFile.clumpSize);
1634 fsckPrint(GPtr->context, E_BadValue, goodStr, badStr);
1635 printMsg = 1;
1636 }
1637
1638 if ( volumeHeader->signature != kHFSPlusSigWord &&
1639 volumeHeader->signature != kHFSXSigWord) {
1640 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1641 plog( "\tinvalid VHB signature \n" );
1642 isVHDamaged = 1;
1643 }
1644 /* From HFS Plus Volume Format Specification (TN1150), "It is acceptable
1645 * for a bit in encodingsBitmap to be set even though no names on the
1646 * volume use that encoding". Therefore we do not report extra bits set in
1647 * on-disk encodingsBitmap as error but will repair it silently if any other
1648 * repairs are made. We complain about extra bits cleared in
1649 * on-disk encodingsBitmap when compared to calculated encodingsBitmap.
1650 */
1651 if ( (volumeHeader->encodingsBitmap & vcb->vcbEncodingsBitmap)
1652 != vcb->vcbEncodingsBitmap ) {
1653 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1654 plog( "\tinvalid VHB encodingsBitmap, disk=0x%qx calculated=0x%qx \n", volumeHeader->encodingsBitmap, vcb->vcbEncodingsBitmap );
1655 isVHDamaged = 1;
1656 }
1657 if ( (UInt16) (hfsPlusIOPosOffset/512) != vcb->vcbAlBlSt ) {
1658 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1659 plog( "\tinvalid VHB AlBlSt \n" );
1660 isVHDamaged = 1;
1661 }
1662 if ( volumeHeader->createDate != vcb->vcbCreateDate ) {
1663 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1664 plog( "\tinvalid VHB createDate \n" );
1665 isVHDamaged = 1;
1666 }
1667 if ( volumeHeader->modifyDate != vcb->vcbModifyDate ) {
1668 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1669 plog( "\tinvalid VHB modifyDate \n" );
1670 isVHDamaged = 1;
1671 }
1672 if ( volumeHeader->backupDate != vcb->vcbBackupDate ) {
1673 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1674 plog( "\tinvalid VHB backupDate \n" );
1675 isVHDamaged = 1;
1676 }
1677 if ( volumeHeader->checkedDate != vcb->vcbCheckedDate ) {
1678 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1679 plog( "\tinvalid VHB checkedDate \n" );
1680 isVHDamaged = 1;
1681 }
1682 if ( volumeHeader->rsrcClumpSize != vcb->vcbRsrcClumpSize ) {
1683 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1684 plog( "\tinvalid VHB rsrcClumpSize (VH=%u, vcb=%u)\n", volumeHeader->rsrcClumpSize, vcb->vcbRsrcClumpSize);
1685 isVHDamaged = 1;
1686 }
1687 if ( volumeHeader->dataClumpSize != vcb->vcbDataClumpSize ) {
1688 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1689 plog( "\tinvalid VHB dataClumpSize \n" );
1690 isVHDamaged = 1;
1691 }
1692 if ( volumeHeader->nextCatalogID != vcb->vcbNextCatalogID &&
1693 (volumeHeader->attributes & kHFSCatalogNodeIDsReused) == 0) {
1694 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1695 plog( "\tinvalid VHB nextCatalogID \n" );
1696 isVHDamaged = 1;
1697 }
1698 if ( volumeHeader->writeCount != vcb->vcbWriteCount ) {
1699 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1700 plog( "\tinvalid VHB writeCount \n" );
1701 isVHDamaged = 1;
1702 }
1703 if ( volumeHeader->nextAllocation != vcb->vcbNextAllocation ) {
1704 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1705 plog( "\tinvalid VHB nextAllocation \n" );
1706 isVHDamaged = 1;
1707 }
1708 if ( volumeHeader->totalBlocks != vcb->vcbTotalBlocks ) {
1709 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1710 plog( "\tinvalid VHB totalBlocks \n" );
1711 isVHDamaged = 1;
1712 }
1713 if ( volumeHeader->blockSize != vcb->vcbBlockSize ) {
1714 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1715 plog( "\tinvalid VHB blockSize \n" );
1716 isVHDamaged = 1;
1717 }
1718 if ( volumeHeader->attributes != vcb->vcbAttributes ) {
1719 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1720 plog( "\tinvalid VHB attributes \n" );
1721 isVHDamaged = 1;
1722 }
1723 if ( volumeHeader->extentsFile.clumpSize != vcb->vcbExtentsFile->fcbClumpSize ) {
1724 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1725 plog( "\tinvalid VHB extentsFile.clumpSize \n" );
1726 isVHDamaged = 1;
1727 }
1728 if ( volumeHeader->allocationFile.clumpSize != vcb->vcbAllocationFile->fcbClumpSize ) {
1729 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1730 plog( "\tinvalid VHB allocationFile.clumpSize \n" );
1731 isVHDamaged = 1;
1732 }
1733 if ( (vcb->vcbAttributesFile != NULL) &&
1734 (volumeHeader->attributesFile.clumpSize != vcb->vcbAttributesFile->fcbClumpSize )) {
1735 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1736 plog( "\tinvalid VHB attributesFile.clumpSize \n" );
1737 isVHDamaged = 1;
1738 }
1739 if ( CmpBlock( volumeHeader->finderInfo, vcb->vcbFinderInfo, sizeof(vcb->vcbFinderInfo) ) ) {
1740 if ( fsckGetVerbosity(GPtr->context) >= kDebugLog )
1741 plog( "\tinvalid VHB finderInfo \n" );
1742 isVHDamaged = 1;
1743 }
1744
1745 /*
1746 * compare extent file allocation info with VolumeHeader
1747 */
1748 fcbP = vcb->vcbExtentsFile;
1749 if ( (UInt64)volumeHeader->extentsFile.totalBlocks * (UInt64)vcb->vcbBlockSize != fcbP->fcbPhysicalSize )
1750 {
1751 printMsg = 1;
1752 WriteError ( GPtr, E_VolumeHeaderDamaged, 3, 0 );
1753 }
1754 for ( i=0; i < GPtr->numExtents; i++ )
1755 {
1756 if ( (volumeHeader->extentsFile.extents[i].startBlock != fcbP->fcbExtents32[i].startBlock) ||
1757 (volumeHeader->extentsFile.extents[i].blockCount != fcbP->fcbExtents32[i].blockCount) )
1758 {
1759 printMsg = 1;
1760 WriteError ( GPtr, E_VolumeHeaderDamaged, 4, 0 );
1761 }
1762 }
1763
1764 /*
1765 * compare catalog file allocation info with MDB
1766 */
1767 fcbP = vcb->vcbCatalogFile; /* compare PEOF for catalog file */
1768 if ( (UInt64)volumeHeader->catalogFile.totalBlocks * (UInt64)vcb->vcbBlockSize != fcbP->fcbPhysicalSize )
1769 {
1770 printMsg = 1;
1771 WriteError ( GPtr, E_VolumeHeaderDamaged, 5, 0 );
1772 }
1773 for ( i=0; i < GPtr->numExtents; i++ )
1774 {
1775 if ( (volumeHeader->catalogFile.extents[i].startBlock != fcbP->fcbExtents32[i].startBlock) ||
1776 (volumeHeader->catalogFile.extents[i].blockCount != fcbP->fcbExtents32[i].blockCount) )
1777 {
1778 printMsg = 1;
1779 WriteError ( GPtr, E_VolumeHeaderDamaged, 6, 0 );
1780 }
1781 }
1782
1783
1784 /*
1785 * compare bitmap file allocation info with MDB
1786 */
1787 fcbP = vcb->vcbAllocationFile;
1788 if ( (UInt64)volumeHeader->allocationFile.totalBlocks * (UInt64)vcb->vcbBlockSize != fcbP->fcbPhysicalSize )
1789 {
1790 printMsg = 1;
1791 WriteError ( GPtr, E_VolumeHeaderDamaged, 7, 0 );
1792 }
1793 for ( i=0; i < GPtr->numExtents; i++ )
1794 {
1795 if ( (volumeHeader->allocationFile.extents[i].startBlock != fcbP->fcbExtents32[i].startBlock) ||
1796 (volumeHeader->allocationFile.extents[i].blockCount != fcbP->fcbExtents32[i].blockCount) )
1797 {
1798 printMsg = 1;
1799 WriteError ( GPtr, E_VolumeHeaderDamaged, 8, 0 );
1800 }
1801 }
1802
1803 if (isVHDamaged || printMsg) {
1804 GPtr->VIStat = GPtr->VIStat | S_MDB;
1805 if (isVHDamaged)
1806 WriteError ( GPtr, E_VolumeHeaderDamaged, 2, 0 );
1807 }
1808
1809 return( noErr );
1810 }
1811
mirror of hfs