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 43static int BTKeyChk( SGlobPtr GPtr, NodeDescPtr nodeP, BTreeControlBlock *btcb ); 44 45 46/*------------------------------------------------------------------------------ 47 48Routine: ChkExtRec (Check Extent Record) 49 50Function: Checks out a generic extent record. 51 52Input: GPtr - pointer to scavenger global area. 53 extP - pointer to extent data record. 54 55 56Output: 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------------------------------------------------------------------------------*/ 64OSErr 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 161Routine: BTCheck - (BTree Check) 162 163Function 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 199Input: 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 206Output: BTCheck - function result: 207 0 = no error 208 n = error code 209------------------------------------------------------------------------------*/ 210 211int 212BTCheck(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 762exit: 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 770RebuildBTreeExit: 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 782Routine: BTMapChk - (BTree Map Check) 783 784Function: Checks out the structure of a BTree allocation map. 785 786Input: GPtr - pointer to scavenger global area 787 fileRefNum - refnum of BTree file 788 789Output: BTMapChk - function result: 790 0 = no error 791 n = error 792------------------------------------------------------------------------------*/ 793 794int 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 } 877exit: 878 if (node.buffer != NULL) 879 (void) ReleaseNode(calculatedBTCB, &node); 880 881 return( result ); 882 883} /* end BTMapChk */ 884 885 886 887/*------------------------------------------------------------------------------ 888 889Routine: BTCheckUnusedNodes 890 891Function: 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 896Input: GPtr - pointer to scavenger global area 897 fileRefNum - refnum of BTree file 898 899Output: *btStat - bit mask S_UnusedNodesNotZero 900 BTCheckUnusedNodes - function result: 901 0 = no error 902 n = error 903------------------------------------------------------------------------------*/ 904 905int 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 } 970done: 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 983Routine: CmpBTH - (Compare BTree Header) 984 985Function: Compares the scavenger BTH info with the BTH on disk. 986 987Input: GPtr - pointer to scavenger global area 988 fileRefNum - file refnum 989 990Output: CmpBTH - function result: 991 0 = no error 992 n = error 993------------------------------------------------------------------------------*/ 994 995OSErr 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 1095Routine: CmpBlock 1096 1097Function: Compares two data blocks for equality. 1098 1099Input: Blk1Ptr - pointer to 1st data block. 1100 Blk2Ptr - pointer to 2nd data block. 1101 len - size of the blocks (in bytes) 1102 1103Output: CmpBlock - result code 1104 0 = equal 1105 1 = not equal 1106------------------------------------------------------------------------------*/ 1107 1108OSErr 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 1125Routine: CmpBTM - (Compare BTree Map) 1126 1127Function: Compares the scavenger BTM with the BTM on disk. 1128 1129Input: GPtr - pointer to scavenger global area 1130 fileRefNum - file refnum 1131 1132Output: CmpBTM - function result: 1133 0 = no error 1134 n = error 1135------------------------------------------------------------------------------*/ 1136 1137int 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 1223exit: 1224 if (node.buffer != NULL) 1225 (void) ReleaseNode(calculatedBTCB, &node); 1226 1227 return( result ); 1228 1229} /* end CmpBTM */ 1230 1231 1232/*------------------------------------------------------------------------------ 1233 1234Routine: BTKeyChk - (BTree Key Check) 1235 1236Function: Checks out the key structure within a Btree node. 1237 1238Input: GPtr - pointer to scavenger global area 1239 NodePtr - pointer to target node 1240 BTCBPtr - pointer to BTreeControlBlock 1241 1242Output: BTKeyChk - function result: 1243 0 = no error 1244 n = error code 1245------------------------------------------------------------------------------*/ 1246extern HFSPlusCatalogKey gMetaDataDirKey; 1247 1248static 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 1356Routine: ChkCName (Check Catalog Name) 1357 1358Function: Checks out a generic catalog name. 1359 1360Input: GPtr - pointer to scavenger global area. 1361 CNamePtr - pointer to CName. 1362 1363Output: ChkCName - function result: 1364 0 = CName is OK 1365 E_CName = invalid CName 1366------------------------------------------------------------------------------*/ 1367 1368OSErr 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 1392Routine: CmpMDB - (Compare Master Directory Block) 1393 1394Function: Compares the scavenger MDB info with the MDB on disk. 1395 1396Input: GPtr - pointer to scavenger global area 1397 1398Output: 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 1404int 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 1566Routine: CompareVolumeHeader - (Compare VolumeHeader Block) 1567 1568Function: Compares the scavenger VolumeHeader info with the VolumeHeader on disk. 1569 1570Input: GPtr - pointer to scavenger global area 1571 1572Output: 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 1578OSErr 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 1812