fsck_hfs/dfalib/Scavenger.h

   1 /*
   2  * Copyright (c) 1999-2011 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 /* Scavenger.h */
  24
  25 #ifndef __SCAVENGER__
  26 #define __SCAVENGER__
  27
  28 #define pascal
  29
  30 #include "SRuntime.h"
  31 #include "BTree.h"
  32 #include "BTreePrivate.h"
  33 #include "CheckHFS.h"
  34 #include "BTreeScanner.h"
  35 #include "hfs_endian.h"
  36 #include "../fsck_debug.h"
  37 #include "../fsck_messages.h"
  38 #include "../fsck_hfs_msgnums.h"
  39 #include "../fsck_msgnums.h"
  40 #include "../fsck_hfs.h"
  41
  42 #include <assert.h>
  43 #include <sys/xattr.h>
  44 #include <sys/acl.h>
  45 #include <sys/kauth.h>
  46 #include <sys/errno.h>
  47 #include <sys/syslimits.h>
  48 #include <sys/param.h>
  49 #include <sys/sysctl.h>
  50 #include <sys/mount.h>
  51 #include <hfs/hfs_mount.h>
  52
  53 #ifdef __cplusplus
  54 extern  "C" {
  55 #endif
  56
  57
  58 #define kFSCKMountVersion       0x6673636B      /* 'fsck' made changes */
  59
  60 enum {
  61         Log2BlkLo                               = 9,                                    // number of left shifts to convert bytes to block.lo
  62         Log2BlkHi                               = 23                                    // number of right shifts to convert bytes to block.hi
  63 };
  64
  65 enum {
  66         kNoHint                                         = 0
  67 };
  68
  69
  70 //
  71 // Misc constants
  72 //
  73
  74 /* IO size for reading or writing disk blocks */
  75 #define DISK_IOSIZE     32768
  76
  77 #define kMaxReScan      3       /* max times to re-scan volume on repair success */
  78
  79 #define kBTreeHeaderUserBytes   128
  80
  81 #define kBusErrorValue  0x50FF8001
  82
  83 //¥¥ Danger! This should not be hard coded
  84 #define kMaxClumpSize   0x100000        /* max clump size is 1MB (2048 btree nodes) */
  85
  86 #define MDB_FNum        1                               /* file number representing the MDB */
  87 #define AMDB_FNum       -1                              /* file number representing the alternate MDB */
  88 #define VBM_FNum        2                               /* file number representing the volume bit map */
  89 #define MDB_BlkN        2                               /* logical block number for the MDB */
  90
  91 #define kCalculatedExtentRefNum                 ( 0 )
  92 #define kCalculatedCatalogRefNum                ( 1*sizeof(SFCB) )
  93 #define kCalculatedAllocationsRefNum    ( 2*sizeof(SFCB) )
  94 #define kCalculatedAttributesRefNum             ( 3*sizeof(SFCB) )
  95 #define kCalculatedStartupRefNum                ( 4*sizeof(SFCB) )
  96 #define kCalculatedRepairRefNum                 ( 5*sizeof(SFCB) )
  97
  98 #define Max_ABSiz       0x7FFFFE00              /* max allocation block size (multiple of 512 */
  99 #define Blk_Size        512                             /* size of a logical block */
 100 #define kHFSBlockSize 512                       /* HFS block size */
 101
 102 // only the lower 7 bits are considered to be invalid, all others are valid -djb
 103 #define VAtrb_Msk       0x007F                  /* volume attribute mask - invalid bits */
 104 #define VAtrb_DFlt      0x0100                  /* default volume attribute flags */
 105 #define VAtrb_Cons      0x0100                  /* volume consistency flag */
 106 #define kHFSCatalogNodeIDsReused 0x1000
 107
 108
 109 /*
 110  *      File type and creator for TextEdit documents
 111  */
 112 enum {
 113         kTextFileType           = 0x54455854,   /* 'TEXT' */
 114         kTextFileCreator        = 0x74747874,   /* 'ttxt' */
 115 };
 116
 117 /*
 118  *      Alias type and creator for directory hard links
 119  */
 120 enum {
 121         kHFSAliasType           = 0x66647270,   /* 'fdrp' */
 122         kHFSAliasCreator        = 0x4D414353    /* 'MACS' */
 123 };
 124
 125 /*------------------------------------------------------------------------------
 126  BTree data structures
 127 ------------------------------------------------------------------------------*/
 128
 129 /* misc BTree constants */
 130
 131 #define BTMaxDepth      8                               /* max tree depth */
 132 #define Num_HRecs       3                               /* number of records in BTree Header node */
 133 #define Num_MRecs       1                               /* number of records in BTree Map node */
 134
 135
 136
 137 //      DFA extensions to the HFS/HFS+ BTreeControlBlock
 138 typedef struct BTreeExtensionsRec
 139 {
 140         Ptr                             BTCBMPtr;                       //      pointer to scavenger BTree bit map
 141         UInt32                          BTCBMSize;                      //      size of the bitmap, bytes
 142         BTreeControlBlock       *altBTCB;                       //      BTCB DFA builds up
 143         UInt32                          realFreeNodeCount;      //      Number of real free nodes, taken from disk, for more accurate progress information
 144 } BTreeExtensionsRec;
 145
 146
 147
 148 /*
 149  * Scavenger BTree Path Record (STPR)
 150  */
 151 typedef struct STPR {
 152         UInt32                  TPRNodeN;               /* node number */
 153         SInt16                  TPRRIndx;               /* record index */
 154         SInt16                  unused;                 /* not used - makes debugging easier */
 155         UInt32                  TPRLtSib;               /* node number of left sibling node */
 156         UInt32                  TPRRtSib;               /* node number of right sibling node */
 157         } STPR, *STPRPtr;
 158
 159 typedef STPR SBTPT[BTMaxDepth];                 /* BTree path table */
 160
 161 #define LenSBTPT        ( sizeof(STPR) * BTMaxDepth )   /* length of BTree Path Table */
 162
 163
 164
 165
 166 /*------------------------------------------------------------------------------
 167  CM (Catalog Manager) data structures
 168  ------------------------------------------------------------------------------*/
 169
 170 //
 171 //      Misc constants
 172 //
 173 #define CMMaxDepth      100                             /* max catalog depth (Same as Finder 7.0) */
 174
 175 #define fNameLocked 4096
 176
 177 union CatalogName {
 178         Str31                                                   pstr;
 179         HFSUniStr255                                    ustr;
 180 };
 181 typedef union CatalogName                               CatalogName;
 182
 183 //
 184 //      Scavenger Directory Path Record (SDPR)
 185 //
 186 typedef struct SDPR {
 187         UInt32                          directoryID;            //      directory ID
 188         UInt32                          offspringIndex;         //      offspring index
 189         UInt32                          directoryHint;          //      BTree hint for directory record
 190         long                            threadHint;                     //      BTree hint for thread record
 191         HFSCatalogNodeID        parentDirID;            //      parent directory ID
 192         CatalogName                     directoryName;          //      directory CName
 193 } SDPR;
 194
 195 enum {
 196 //      kInvalidMRUCacheKey                     = -1L,                                                  /* flag to denote current MRU cache key is invalid*/
 197         kDefaultNumMRUCacheBlocks       = 16                                                    /* default number of blocks in each cache*/
 198 };
 199
 200
 201 /*
 202  * UTCacheReadIP and UTCacheWriteIP cacheOption
 203  */
 204
 205 enum {
 206         noCacheBit   = 5,       /* don't cache this please */
 207         noCacheMask  = 0x0020,
 208         rdVerifyBit  = 6,       /* read verify */
 209         rdVerifyMask = 0x0040
 210 };
 211
 212
 213 /*------------------------------------------------------------------------------
 214  Low-level File System Error codes
 215 ------------------------------------------------------------------------------*/
 216
 217 /* The DCE bits are defined as follows (for the word of flags): */
 218
 219 enum
 220 {
 221         Is_AppleTalk            = 0,
 222         Is_Agent                        = 1,                    // future use
 223         FollowsNewRules         = 2,                    // New DRVR Rules Bit
 224         Is_Open                         = 5,
 225         Is_Ram_Based            = 6,
 226         Is_Active                       = 7,
 227         Read_Enable                     = 8,
 228         Write_Enable            = 9,
 229         Control_Enable          = 10,
 230         Status_Enable           = 11,
 231         Needs_Goodbye           = 12,
 232         Needs_Time                      = 13,
 233         Needs_Lock                      = 14,
 234
 235         Is_AppleTalk_Mask       = 1 << Is_AppleTalk,
 236         Is_Agent_Mask           = 1 << Is_Agent,
 237         FollowsRules_Mask       = 1 << FollowsNewRules,
 238         Is_Open_Mask            = 1 << Is_Open,
 239         Is_Ram_Based_Mask       = 1 << Is_Ram_Based,
 240         Is_Active_Mask          = 1 << Is_Active,
 241         Read_Enable_Mask        = 1 << Read_Enable,
 242         Write_Enable_Mask       = 1 << Write_Enable,
 243         Control_Enable_Mask     = 1 << Control_Enable,
 244         Status_Enable_Mask      = 1 << Status_Enable,
 245         Needs_Goodbye_Mask      = 1 << Needs_Goodbye,
 246         Needs_Time_Mask         = 1 << Needs_Time,
 247         Needs_Lock_Mask         = 1 << Needs_Lock
 248 };
 249
 250 enum {
 251         cdInternalErr                                   = -1312,                //      internal CheckDisk error
 252         cdVolumeNotFoundErr                             = -1313,                //      cound not find volume (could be offline)
 253         cdCannotReadErr                                 = -1314,                //      unable to read from disk
 254         cdCannotWriteErr                                = -1315,                //      unable to write to disk
 255         cdNotHFSVolumeErr                               = -1316,                //      not an HFS disk
 256         cdUnrepairableErr                               = -1317,                //      volume needs major repairs that CheckDisk cannot fix
 257         cdRepairFailedErr                               = -1318,                //      repair failed
 258         cdUserCanceledErr                               = -1319,                //      user interrupt
 259         cdVolumeInUseErr                                = -1320,                //      volume modifed by another app
 260         cdNeedsRepairsErr                               = -1321,                //      volume needs repairs (see repairInfo for additional info)
 261         cdReMountErr                                    = -1322,                //      Cannot remount volume
 262         cdUnknownProcessesErr                   = -1323,                //      Volume cannot be unmounted and unknown processes are running
 263         cdDamagedWrapperErr                             = -1324,                //      HFS Wrapper damaged error.
 264         cdIncompatibleOSErr                             = -1325,                //      Current OS version is incompatible
 265         cdMemoryFullErr                                 = -1326                 //      not enough memory to check disk
 266 };
 267
 268
 269 enum {
 270         fsDSIntErr      = -127  /* non-hardware Internal file system error */
 271 };
 272
 273 //      Repair Info - additional info returned when a repair is attempted
 274 enum {
 275         kFileSharingEnabled             = 0x00000001,
 276         kDiskIsLocked                   = 0x00000002,
 277         kDiskIsBoot                     = 0x00000004,
 278         kDiskHasOpenFiles               = 0x00000008,
 279         kVolumeHadOverlappingExtents    = 0x00000010,   // repairLevelSomeDataLoss
 280         kVolumeClean                    = 0x00000020,
 281
 282         kRepairsWereMade                = 0x80000000
 283 };
 284
 285 //      Input parameters to CheckDisk
 286 enum
 287 {
 288         ignoreRunningProcessesMask              = 0x00000001,   //      Assumes caller has shut down processes
 289         checkDiskVersionMask                    = 0x00000004    //      Will just return back the version in repairInfo.
 290 };
 291
 292 //      Message types, so the user can treat and display accordingly
 293 enum {
 294         kStatusMessage                                  = 0x0000,
 295         kTitleMessage                                   = 0x0001,
 296         kErrorMessage                                   = 0x0002
 297 };
 298
 299 //      <10> Current stage of CheckDisk passed to cancel proc.
 300 //      File System is marked busy during kRepairStage, so WaitNextEvent and I/O cannot be done during this stage.
 301
 302 enum {
 303         kHFSStage                                               = 0,
 304         kRepairStage,
 305         kVerifyStage,
 306         kAboutToRepairStage
 307 };
 308
 309 //      Resource ID of 'STR ' resource containing the name of of the folder to create aliases to damaged files.
 310 enum {
 311         rDamagedFilesDirSTRid                   = -20886
 312 };
 313
 314 //      Type of volume
 315 enum {
 316         kUnknownVolumeType      = 0,
 317         kHFSVolumeType,
 318         kEmbededHFSPlusVolumeType,
 319         kPureHFSPlusVolumeType
 320 };
 321
 322
 323 enum {
 324         kStatusLines    = 131,
 325         kFirstError             = 500,
 326
 327         kHighLevelInfo  = 1100,
 328         kBasicInfo              = 1200,
 329         kErrorInfo              = 1202,
 330
 331         kErrorBase              = -1310
 332 };
 333
 334
 335 /*------------------------------------------------------------------------------
 336  Minor Repair Interface (records compiled during scavenge, later repaired)
 337  Note that not all repair types use all of these fields.
 338  -----------------------------------------------------------------------------*/
 339
 340  typedef struct RepairOrder                     /* a node describing a needed minor repair */
 341  {
 342         struct RepairOrder      *link;  /* link to next node, or NULL */
 343         SInt16                  type;   /* type of error, as an error code (E_DirVal etc) */
 344         SInt16          forkType;       /* which file fork */
 345         UInt64          correct;        /* correct valence */
 346         UInt64          incorrect;      /* valence as found in volume (for consistency chk) */
 347         UInt32          maskBit;        /* incorrect bit */
 348         UInt32          hint;           /* B-tree node hint */
 349         UInt32          parid;          /* parent ID */
 350         unsigned char name[1];  /* dir or file name */
 351  } RepairOrder, *RepairOrderPtr;
 352
 353
 354  typedef struct EmbededVolDescription
 355  {
 356         SInt16                          drAlBlSt;
 357         UInt16                          drEmbedSigWord;
 358         HFSExtentDescriptor     drEmbedExtent;
 359  } EmbededVolDescription;
 360
 361
 362 // define the correct drive queue structure
 363 typedef struct ExtendedDrvQueue
 364 {
 365         char dQVolumeLocked;
 366         char dQDiskInDrive;
 367         char dQUsedInternally;
 368         char dQDiskIsSingleSided;
 369         QElemPtr qLink;
 370         short qType;
 371         short dQDrive;
 372         short dQRefNum;
 373         short dQFSID;
 374         short dQDrvSz;
 375         short dQDrvSz2;
 376 }ExtendedDrvQueue;
 377
 378
 379 /*------------------------------------------------------------------------------
 380  Scavenger Global Area - (SGlob)
 381 ------------------------------------------------------------------------------*/
 382 typedef struct MissingThread
 383 {
 384         struct MissingThread  *link;            /* link to next node, or NULL */
 385         UInt32                threadID;
 386         HFSPlusCatalogKey     nextKey;
 387         HFSPlusCatalogThread  thread;
 388 } MissingThread;
 389
 390 #define kDataFork       0
 391 #define kRsrcFork       (-1)
 392 #define kEAData         1
 393
 394 struct ExtentInfo {
 395         HFSCatalogNodeID fileID;
 396         UInt32  startBlock;
 397         UInt32  blockCount;
 398         UInt32  newStartBlock;
 399         char *  attrname;
 400         UInt8   forkType;
 401         /* didRepair stores the result of moving of overlap extent and is used
 402          * to decide which disk blocks (original blocks or blocks allocated for
 403          * for new extent location) should be marked used and free.
 404          */
 405         Boolean didRepair;
 406 };
 407 typedef struct ExtentInfo ExtentInfo;
 408
 409 struct ExtentsTable {
 410         UInt32                                                  count;
 411         ExtentInfo                                              extentInfo[1];
 412 };
 413 typedef struct ExtentsTable ExtentsTable;
 414
 415
 416 struct FileIdentifier {
 417         Boolean                                                 hasThread;
 418         HFSCatalogNodeID                                fileID;
 419         HFSCatalogNodeID                                parID;                  //      Used for files on HFS volumes without threads
 420         Str31                                                   name;                   //      Used for files on HFS volumes without threads
 421 };
 422 typedef struct FileIdentifier FileIdentifier;
 423
 424 struct FileIdentifierTable {
 425         UInt32                                                  count;
 426         FileIdentifier                                  fileIdentifier[1];
 427 };
 428 typedef struct FileIdentifierTable FileIdentifierTable;
 429
 430 /* Universal Extent Key */
 431
 432 union ExtentKey {
 433         HFSExtentKey                                    hfs;
 434         HFSPlusExtentKey                                hfsPlus;
 435 };
 436 typedef union ExtentKey                                 ExtentKey;
 437 /* Universal extent descriptor */
 438
 439 union ExtentDescriptor {
 440         HFSExtentDescriptor                     hfs;
 441         HFSPlusExtentDescriptor                 hfsPlus;
 442 };
 443 typedef union ExtentDescriptor                  ExtentDescriptor;
 444 /* Universal extent record */
 445
 446 union ExtentRecord {
 447         HFSExtentRecord                                 hfs;
 448         HFSPlusExtentRecord                     hfsPlus;
 449 };
 450 typedef union ExtentRecord                              ExtentRecord;
 451 /* Universal catalog key */
 452
 453 union CatalogKey {
 454         HFSCatalogKey                                   hfs;
 455         HFSPlusCatalogKey                               hfsPlus;
 456 };
 457 typedef union CatalogKey                                CatalogKey;
 458 /* Universal catalog data record */
 459
 460 union CatalogRecord {
 461         SInt16                                                  recordType;
 462         HFSCatalogFolder                                hfsFolder;
 463         HFSCatalogFile                                  hfsFile;
 464         HFSCatalogThread                                hfsThread;
 465         HFSPlusCatalogFolder                    hfsPlusFolder;
 466         HFSPlusCatalogFile                              hfsPlusFile;
 467         HFSPlusCatalogThread                    hfsPlusThread;
 468 };
 469 typedef union CatalogRecord                             CatalogRecord;
 470
 471 /*
 472         Key for records in the attributes file.  Fields are compared in the order:
 473                 cnid, attributeName, startBlock
 474 */
 475
 476 struct AttributeKey {
 477         UInt16                                                  keyLength;                                      /* must set kBTBigKeysMask and kBTVariableIndexKeysMask in BTree header's attributes */
 478         UInt16                                                  pad;
 479         HFSCatalogNodeID                                cnid;                                           /* file or folder ID */
 480         UInt32                                                  startBlock;                                     /* block # relative to start of attribute */
 481         UInt16     attrNameLen;     /* number of unicode characters */
 482         UInt16     attrName[127];   /* attribute name (Unicode) */
 483 };
 484 typedef struct AttributeKey                             AttributeKey;
 485 enum {
 486         kAttributeKeyMaximumLength      = sizeof(AttributeKey) - sizeof(UInt16),
 487         kAttributeKeyMinimumLength      = kAttributeKeyMaximumLength - 127 * sizeof(UInt16) + sizeof(UInt16)
 488 };
 489
 490 struct HIOParam {
 491         QElemPtr                                                qLink;                                          /*queue link in header*/
 492         short                                                   qType;                                          /*type byte for safety check*/
 493         short                                                   ioTrap;                                         /*FS: the Trap*/
 494         Ptr                                                     ioCmdAddr;                                      /*FS: address to dispatch to*/
 495         void*                           ioCompletion;                           /*completion routine addr (0 for synch calls)*/
 496         OSErr                                                   ioResult;                                       /*result code*/
 497         StringPtr                                               ioNamePtr;                                      /*ptr to Vol:FileName string*/
 498         short                                                   ioVRefNum;                                      /*volume refnum (DrvNum for Eject and MountVol)*/
 499         short                                                   ioRefNum;
 500         SInt8                                                   ioVersNum;
 501         SInt8                                                   ioPermssn;
 502         Ptr                                                     ioMisc;
 503         Ptr                                                     ioBuffer;
 504         long                                                    ioReqCount;
 505         long                                                    ioActCount;
 506         short                                                   ioPosMode;
 507         long                                                    ioPosOffset;
 508 };
 509 typedef struct HIOParam HIOParam;
 510
 511 typedef HIOParam *                                              HIOParamPtr;
 512
 513
 514 struct FCBArray {
 515         UInt32          length;         /* first word is FCB part length*/
 516         SFCB            fcb[1];         /* fcb array*/
 517 };
 518 typedef struct FCBArray FCBArray;
 519
 520 /*
 521         UserCancel callback routine
 522
 523         Input:
 524                         progress:                       number from 1 to 100 indicating current progress
 525                         progressChanged:        boolean flag that is true if progress number has been updated
 526                         context:                        pointer to context data (if any) that the caller passed to CheckDisk
 527
 528         Output:
 529                         return true if the user wants to cancel the CheckDisk operation
 530  */
 531
 532 typedef int (*UserCancelProcPtr)(UInt16 progress, UInt16 secondsRemaining, Boolean progressChanged, UInt16 stage, void *context, int passno);
 533
 534
 535 #if  0
 536
 537         //--    User Cancel Proc
 538         typedef UniversalProcPtr UserCancelUPP;
 539
 540         enum {
 541                 uppUserCancelProcInfo = kPascalStackBased
 542                          | RESULT_SIZE(kTwoByteCode)
 543                          | STACK_ROUTINE_PARAMETER(1, kTwoByteCode)
 544                          | STACK_ROUTINE_PARAMETER(2, kTwoByteCode)
 545                          | STACK_ROUTINE_PARAMETER(3, kTwoByteCode)
 546                          | STACK_ROUTINE_PARAMETER(4, kTwoByteCode)
 547                          | STACK_ROUTINE_PARAMETER(5, kFourByteCode)
 548         };
 549
 550         #define NewUserCancelProc(userRoutine)          \
 551                         (UserCancelUPP) NewRoutineDescriptor((ProcPtr)(userRoutine), uppUserCancelProcInfo, GetCurrentArchitecture())
 552
 553         #define CallUserCancelProc(userRoutine, progress, secondsRemaining, progressChanged, stage, context, p)         \
 554                         CallUniversalProc((UniversalProcPtr)(userRoutine), uppUserCancelProcInfo, (progress), (secondsRemaining), (progressChanged), (stage), (context), (p))
 555
 556 #else /* not CFM */
 557
 558         typedef UserCancelProcPtr UserCancelUPP;
 559
 560         #define NewUserCancelProc(userRoutine)          \
 561                         ((UserCancelUPP) (userRoutine))
 562
 563         #define CallUserCancelProc(userRoutine, progress, secondsRemaining, progressChanged, stage, context, p)         \
 564                         (*(userRoutine))((progress), (secondsRemaining), (progressChanged), (stage), (context), (p))
 565
 566 #endif
 567
 568
 569 /*
 570         UserMessage callback routine
 571
 572         Input:
 573                         message:                        message from CheckDisk
 574                         messageType:            type of message
 575                         context:                        pointer to context data (if any) that the caller passed to CheckDisk
 576
 577         Output:
 578                         return true if the user wants to cancel the CheckDisk operation
 579  */
 580
 581
 582 typedef pascal void (*UserMessageProcPtr)(StringPtr message, SInt16 messageType, void *context);
 583
 584 #if 0
 585
 586         //--    User Message Proc
 587         typedef UniversalProcPtr UserMessageUPP;
 588
 589         enum {
 590                 uppUserMessageProcInfo = kPascalStackBased
 591                          | STACK_ROUTINE_PARAMETER(1, kFourByteCode)
 592                          | STACK_ROUTINE_PARAMETER(2, kTwoByteCode)
 593                          | STACK_ROUTINE_PARAMETER(3, kFourByteCode)
 594         };
 595
 596         #define NewUserMessageProc(userRoutine)         \
 597                         (UserMessageUPP) NewRoutineDescriptor((ProcPtr)(userRoutine), uppUserMessageProcInfo, GetCurrentArchitecture())
 598
 599         #define CallUserMessageProc(userRoutine, message, messageType, context)         \
 600                         CallUniversalProc((UniversalProcPtr)(userRoutine), uppUserMessageProcInfo, (message), (messageType), (context))
 601
 602 #else /* not CFM */
 603
 604         typedef UserMessageProcPtr UserMessageUPP;
 605
 606         #define NewUserMessageProc(userRoutine)         \
 607                         ((UserMessageUPP) (userRoutine))
 608
 609         #define CallUserMessageProc(userRoutine, message, messageType, context)         \
 610                         (*(userRoutine))((message), (messageType), (context))
 611
 612 #endif
 613
 614 /* 3843779 Structure to determine consistency of attribute data and
 615  * corresponding bit in catalog record.  Based on Chinese Remainder
 616  * Theorem
 617  */
 618 typedef struct PrimeBuckets {
 619         UInt32  n32[32];
 620         UInt32  n27[27];
 621         UInt32  n25[25];
 622         UInt32  n7[7];
 623         UInt32  n11[11];
 624         UInt32  n13[13];
 625         UInt32  n17[17];
 626         UInt32  n19[19];
 627         UInt32  n23[23];
 628         UInt32  n29[29];
 629         UInt32  n31[31];
 630 } PrimeBuckets;
 631
 632 /* Record last attribute ID checked, used in CheckAttributeRecord, initialized in ScavSetup */
 633 typedef struct attributeInfo {
 634         Boolean isValid;
 635         Boolean hasSecurity;
 636         int16_t recordType;
 637         u_int32_t fileID;
 638         unsigned char attrname[XATTR_MAXNAMELEN+1];
 639         u_int32_t totalBlocks;
 640         u_int32_t calculatedTotalBlocks;
 641         u_int64_t logicalSize;
 642 } attributeInfo;
 643
 644 /*
 645         VolumeObject encapsulates all infomration about the multiple volume anchor blocks (VHB and MSD)
 646         on HFS and HFS+ volumes.  An HFS volume will have two MDBs (primary and alternate HFSMasterDirectoryBlock),
 647         a pure HFS+ volume will have two VHBs (primary and alternate HFSPlusVolumeHeader), and a wrapped HFS+
 648         volume will have two MDBs and two VHBs.
 649 */
 650
 651 /* values for VolumeObject.flags */
 652 enum {
 653         kVO_Inited                      = 0x00000001,           // this structured has been initialized
 654         kVO_PriVHBOK            = 0x00000002,           // the primary Volume Header Block is valid
 655         kVO_AltVHBOK            = 0x00000004,           // the alternate Volume Header Block is valid
 656         kVO_PriMDBOK            = 0x00000008,           // the primary Master Directory Block is valid
 657         kVO_AltMDBOK            = 0x00000010,           // the alternate Master Directory Block is valid
 658 };
 659
 660 typedef struct VolumeObject {
 661         UInt32                  flags;
 662         SVCB *                  vcbPtr;                         // pointer to VCB used for this volume
 663         UInt32                  volumeType;                     // (kHFSVolumeType or kEmbededHFSPlusVolumeType or kPureHFSPlusVolumeType)
 664         UInt32                  embeddedOffset;         // offset of embedded HFS+ (in bytes) volume into HFS wrapper volume
 665                                                                                 //   NOTE - UInt32 is OK since we don't support HFS Wrappers on TB volumes
 666         UInt32                  sectorSize;                     // size of a sector for this device
 667         UInt64                  totalDeviceSectors;     // total number of sectors for this volume (from GetDeviceSize)
 668         UInt64                  totalEmbeddedSectors; // total number of sectors for embedded volume
 669         // location of all possible volume anchor blocks (MDB and VHB) on this volume.  These locations
 670         // are the sector offset into the volume.  Only wrapped HFS+ volumes use all 4 of these.
 671         UInt64                  primaryVHB;                     // not used for HFS volumes
 672         UInt64                  alternateVHB;           // not used for HFS volumes
 673         UInt64                  primaryMDB;                     // not used for pure HFS+ volumes
 674         UInt64                  alternateMDB;           // not used for pure HFS+ volumes
 675 } VolumeObject, *VolumeObjectPtr;
 676
 677
 678 typedef struct SGlob {
 679         void *                          scavStaticPtr;                  // pointer to static structure allocated in ScavSetUp
 680         SInt16                          DrvNum;                                 //      drive number of target drive
 681         SInt16                          RepLevel;                               //      repair level, 1 = minor repair, 2 = major repair
 682         SInt16                          ScavRes;                                //      scavenge result code
 683         OSErr                           ErrCode;                        //      error code
 684         OSErr                           IntErr;                         //      internal error code
 685         UInt16                          VIStat;                                 //      scavenge status flags for volume info
 686         UInt16                          ABTStat;                                //      scavenge status flags for Attributes BTree
 687         UInt16                          EBTStat;                                //      scavenge status flags for extent BTree
 688         UInt16                          CBTStat;                                //      scavenge status flags for catalog BTree
 689         UInt32                          CatStat;                                //      scavenge status flags for catalog file
 690         UInt16                          VeryMinorErrorsStat;    //      scavenge status flags for very minor errors
 691         UInt16                          JStat;                                  //      scavange status flags for journal errors
 692         UInt16                          PrintStat;                              //      info about messages that should be displayed only once
 693         DrvQElPtr                       DrvPtr;                                 //      pointer to driveQ element for target drive
 694         UInt32                          TarID;                                  //      target ID (CNID of data structure being verified)
 695         UInt64                          TarBlock;                               //      target block/node number being verified
 696         SInt16                          BTLevel;                                //      current BTree enumeration level
 697         SBTPT                           *BTPTPtr;                               //      BTree path table pointer
 698         SInt16                          DirLevel;                               //      current directory enumeration level
 699         SDPR                            *DirPTPtr;                              //      directory path table pointer (pointer to array of SDPR)
 700         uint32_t                        dirPathCount;                   //  number of SDPR entries allocated in directory path table
 701         SInt16                          CNType;                                 //      current CNode type
 702         UInt32                          ParID;                                  //      current parent DirID
 703         CatalogName                     CName;                                  //      current CName
 704         RepairOrderPtr          MinorRepairsP;                  //      ptr to list of problems for later repair
 705         MissingThread           *missingThreadList;
 706         Ptr                             FCBAPtr;                                //      pointer to scavenger FCB array
 707         UInt32                          **validFilesList;               //      List of valid HFS file IDs
 708
 709         ExtentsTable            **overlappedExtents;    //      List of overlapped extents
 710         FileIdentifierTable     **fileIdentifierTable;  //      List of files for post processing
 711
 712         UInt32                          inputFlags;                             //      Caller can specify some DFA behaviors
 713
 714         UInt32                          volumeFeatures;                 //      bit vector of volume and OS features
 715         Boolean                         usersAreConnected;              //      true if user are connected
 716         Boolean                         fileSharingOn;                  //      true if file sharing is on
 717         UInt32                          altBlockLocation;
 718         Boolean                         checkingWrapper;
 719         SInt16                          numExtents;                             //      Number of memory resident extents.  3 or 8
 720         OSErr                           volumeErrorCode;
 721
 722         UserCancelUPP           userCancelProc;
 723         UserMessageUPP          userMessageProc;
 724         void                            *userContext;
 725
 726         UInt64                          onePercent;
 727         UInt64                          itemsToProcess;
 728         UInt64                          itemsProcessed;
 729         UInt64                          lastProgress;
 730         long                            startTicks;
 731         UInt16                          secondsRemaining;
 732
 733         long                            lastTickCount;
 734
 735
 736         SVCB                    *calculatedVCB;
 737         SFCB                    *calculatedExtentsFCB;
 738         SFCB                    *calculatedCatalogFCB;
 739         SFCB                    *calculatedAllocationsFCB;
 740         SFCB                    *calculatedAttributesFCB;
 741         SFCB                    *calculatedStartupFCB;
 742         SFCB                    *calculatedRepairFCB;
 743         BTreeControlBlock       *calculatedExtentsBTCB;
 744         BTreeControlBlock       *calculatedCatalogBTCB;
 745         BTreeControlBlock       *calculatedRepairBTCB;
 746         BTreeControlBlock       *calculatedAttributesBTCB;
 747
 748         Boolean                 cleanUnmount;
 749         Boolean                 guiControl;
 750         fsck_ctx_t              context;
 751         int                             chkLevel;
 752         int             repairLevel;
 753         int             rebuildOptions;                 // options to indicate type of btree(s) to rebuild
 754         Boolean                 minorRepairErrors;      // indicates some minor repairs failed
 755         Boolean         minorRepairFalseSuccess;        // indicates minor repair function is returning false success, do not delete from the list
 756         int                             canWrite;       // we can safely write to the block device
 757         int                             writeRef;       // file descriptor with write access on the volume
 758         int                             lostAndFoundMode;  // used when creating lost+found directory
 759         int                             liveVerifyState; // indicates if live verification is being done or not
 760         BTScanState             scanState;
 761         int             scanCount;      /* Number of times fsck_hfs has looped */
 762
 763         unsigned char   volumeName[256]; /* volume name in ASCII or UTF-8 */
 764         char            deviceNode[256]; /* device node in ASCII */
 765
 766         /* Extended attribute check related stuff */
 767         uint32_t        cat_ea_count;           /* number of catalog records that have attribute bit set */
 768         uint32_t        cat_acl_count;          /* number of catalog records that have security bit set */
 769         uint32_t        attr_ea_count;          /* number of unique fileID attributes found in attribute btree */
 770         uint32_t        attr_acl_count;         /* number of acls found in attribute btree */
 771         PrimeBuckets    CBTAttrBucket;          /* prime number buckets for Attribute bit in Catalog btree */
 772         PrimeBuckets    CBTSecurityBucket;      /* prime number buckets for Security bit in Catalog btree */
 773         PrimeBuckets    ABTAttrBucket;          /* prime number buckets for Attribute bit in Attribute btree */
 774         PrimeBuckets    ABTSecurityBucket;      /* prime number buckets for Security bit in Attribute btree */
 775         attributeInfo   lastAttrInfo;           /* Record last attribute ID checked, used in CheckAttributeRecord, initialized in ScavSetup */
 776         UInt16          securityAttrName[XATTR_MAXNAMELEN];     /* Store security attribute name in UTF16, to avoid frequent conversion */
 777         size_t          securityAttrLen;
 778
 779         /* File Hard Links related stuff */
 780         uint32_t        filelink_priv_dir_id;
 781
 782         /* Directory Hard Links related stuff */
 783         uint32_t        dirlink_priv_dir_id;
 784         uint32_t        dirlink_priv_dir_valence;
 785         uint32_t        calculated_dirinodes;
 786         uint32_t        calculated_dirlinks;
 787
 788         /* Journal file ID's */
 789         uint32_t        journal_file_id;
 790         uint32_t        jib_file_id;
 791 } SGlob, *SGlobPtr;
 792
 793
 794 enum
 795 {
 796         supportsTrashVolumeCacheFeatureMask             = 1,
 797         supportsHFSPlusVolsFeatureMask                  = 2,
 798         volumeIsMountedMask                                             = 4
 799 };
 800
 801 /* scavenger flags */
 802
 803 /* volume info status flags (contents of VIStat) */
 804
 805 #define S_MDB                                   0x8000  //      MDB/VHB damaged
 806 #define S_AltMDB                                0x4000  //      Unused  /* alternate MDB damaged */
 807 #define S_VBM                                   0x2000  //      volume bit map damaged
 808 #define S_WMDB                                  0x1000  //      wrapper MDB is damaged
 809 #define S_OverlappingExtents    0x0800  //      Overlapping extents found
 810 #define S_BadMDBdrAlBlSt                0x0400  //      Invalid drAlBlSt field in MDB
 811 #define S_InvalidWrapperExtents 0x0200  //      Invalid catalog extent start in MDB
 812
 813 /* BTree status flags (contents of EBTStat, CBTStat and ABTStat) */
 814
 815 #define S_BTH                                   0x8000  /* BTree header damaged */
 816 #define S_BTM                                   0x4000  /* BTree map damaged */
 817 #define S_Indx                                  0x2000  //      Unused  /* index structure damaged */
 818 #define S_Leaf                                  0x1000  //      Unused  /* leaf structure damaged */
 819 #define S_Orphan                                0x0800  // orphaned file
 820 #define S_OrphanedExtent                0x0400  // orphaned extent
 821 #define S_ReservedNotZero               0x0200  // the flags or reserved fields are not zero
 822 #define S_RebuildBTree                  0x0100  // similar to S_Indx, S_Leaf, but if one is bad we stop checking and the other may also be bad.
 823 #define S_ReservedBTH                   0x0080  // fields in the BTree header should be zero but are not
 824 #define S_AttributeCount                0x0040  // incorrect number of xattr in attribute btree in comparison with attribute bit in catalog btree
 825 #define S_SecurityCount                 0x0020  // incorrect number of security xattrs in attribute btree in comparison with security bit in catalog btree
 826 #define S_AttrRec                               0x0010  // orphaned/unknown record in attribute BTree
 827 #define S_ParentHierarchy               0x0008  // bad parent hierarchy, could not lookup parent directory record */
 828 #define S_UnusedNodesNotZero    0x0004  /* Unused B-tree nodes are not filled with zeroes */
 829
 830 /* catalog file status flags (contents of CatStat) */
 831
 832 #define S_IllName                       0x00008000      /* illegal name found */
 833 #define S_Valence                       0x00004000      /* a directory valence is out of sync */
 834 #define S_FThd                          0x00002000      /* dangling file thread records exist */
 835 #define S_DFCorruption          0x00001000      /* disappearing folder corruption detected */
 836 #define S_NoDir                         0x00000800      /* missing directory record */
 837 #define S_LockedDirName         0x00000400  // locked dir name
 838 #define S_MissingThread         0x00000200  /* missing thread record */
 839 #define S_UnlinkedFile          0x00000100      /* orphaned link node */
 840 #define S_LinkCount                     0x00000080      /* data node link count needs repair */
 841 #define S_Permissions           0x00000040      /* BSD permissions need repair */
 842 #define S_FileAllocation        0x00000020      /* peof or leof needs adjustment */
 843 #define S_BadExtent                     0x00000010      /* invalid extent */
 844 #define S_LinkErrRepair         0x00000008      /* repairable file/directory hard link corruption detected */
 845 #define S_LinkErrNoRepair       0x00000004      /* un-repairable file/directory hard link corruptions detected */
 846 #define S_FileHardLinkChain     0x00000002      /* incorrect number of file hard links, doubly linked list chain needs repair */
 847 #define S_DirHardLinkChain      0x00000001      /* incorrect number of directory hard links, doubly linked list chain needs repair */
 848
 849 /* VeryMinorErrorsStat */
 850
 851 #define S_BloatedThreadRecordFound      0x8000  // 2210409, excessivly large thread record found
 852
 853 /* user file status flags (contents of FilStat) */
 854
 855 //#define S_LockedName                  0x4000  // locked file name
 856
 857 /* Journal status flag (contents of JStat) */
 858 #define S_BadJournal            0x8000  /* Bad journal content */
 859 #define S_DirtyJournal          0x4000  /* Journal is dirty (needs to be replayed) */
 860
 861 /* Print status flag (contents of PrintStat) */
 862 #define S_DamagedDir            0x8000  /* message for M_LookDamagedDir already printed */
 863 #define S_SymlinkCreate         0x4000  /* message for E_SymlinkCreate already printed */
 864
 865 /*------------------------------------------------------------------------------
 866  ScavCtrl Interface
 867 ------------------------------------------------------------------------------*/
 868
 869 //      Command Codes (commands to ScavControl)
 870 enum
 871 {
 872         scavInitialize          = 1,                    //      Start initial volume check
 873         scavVerify,                                                     //      Start verify operation
 874         scavRepair,                                                     //      Start repair opeation
 875         scavTerminate,                                          //      Cleanup after scavenge
 876 };
 877
 878
 879 //      Repair Levels
 880 enum
 881 {
 882         repairLevelNoProblemsFound                              = 0,
 883         repairLevelRepairIfOtherErrorsExist,            //      Bloated thread records, ...
 884         repairLevelVeryMinorErrors,                                     //      Missing Custom Icon, Locked Directory name,..., Errors that don't need fixing from CheckDisk (Installer), Non Volume corruption bugs.
 885         repairLevelVolumeRecoverable,                           //      Minor Volume corruption exists
 886         repairLevelSomeDataLoss,                                        //      Overlapping extents, some data loss but no scavaging will get it back
 887         repairLevelWillCauseDataLoss,                           //      Missing leaf nodes, repair will lose nodes without scavaging (proceed at your own risk, check disk with other utils)
 888         repairLevelCatalogBtreeRebuild,                         //      Catalog Btree is damaged, repair may lose some data
 889         repairLevelUnrepairable                                         //      DFA cannot repair volume
 890 };
 891
 892
 893 /* Status messages written to summary */
 894 enum {
 895         M_FirstMessage              =  1,
 896         M_LastMessage               = 29
 897 };
 898
 899
 900 /* Internal DFA error codes */
 901 enum {
 902         errRebuildBtree                         = -1001         /* BTree requires rebuilding. */
 903 };
 904
 905
 906 enum {                                                                                                                          /*      extendFileContigMask            = 0x0002*/
 907         kEFContigBit                            = 1,                                                    /*      force contiguous allocation*/
 908         kEFContigMask                           = 0x02,
 909         kEFAllBit                                       = 0,                                                    /*      allocate all requested bytes or none*/
 910         kEFAllMask                                      = 0x01,
 911         kEFNoClumpBit                           = 2,                                                    /*      Don't round up requested size to multiple of clump size*/
 912         kEFNoClumpMask                          = 0x04,                                                 /*      TruncateFile option flags*/
 913         kEFNoExtOvflwBit                        = 3,                                                    /*  Don't use extens overflow file */
 914         kEFNoExtOvflwMask                       = 0x08,
 915
 916         kTFTrunExtBit                           = 0,                                                    /*      truncate to the extent containing new PEOF*/
 917         kTFTrunExtMask                          = 1
 918 };
 919
 920
 921
 922 // Encoding vs. Index
 923 //
 924 // For runtime table lookups and for the volume encoding bitmap we
 925 // need to map some encodings to keep them in a reasonable range.
 926 //
 927
 928 enum {
 929         kTextEncodingMacRoman           = 0L,
 930         kTextEncodingMacFarsi           = 0x8C,  /* Like MacArabic but uses Farsi digits*/
 931                                                                                                                                 /* The following use script code 7, smCyrillic*/
 932         kTextEncodingMacUkrainian       = 0x98, /* The following use script code 32, smUnimplemented*/
 933
 934         kIndexMacUkrainian      = 48,           // MacUkrainian encoding is 152
 935         kIndexMacFarsi          = 49            // MacFarsi encoding is 140
 936 };
 937
 938 #define MapEncodingToIndex(e) \
 939         ( (e) < 48 ? (e) : ( (e) == kTextEncodingMacUkrainian ? kIndexMacUkrainian : ( (e) == kTextEncodingMacFarsi ? kIndexMacFarsi : kTextEncodingMacRoman) ) )
 940
 941 #define MapIndexToEncoding(i) \
 942         ( (i) == kIndexMacFarsi ? kTextEncodingMacFarsi : ( (i) == kIndexMacUkrainian ? kTextEncodingMacUkrainian : (i) ) )
 943
 944 #define ValidMacEncoding(e)     \
 945         ( ((e) < 39)  ||  ((e) == kTextEncodingMacFarsi)  ||  ((e) == kTextEncodingMacUkrainian) )
 946
 947
 948
 949
 950 extern  void    WriteMsg( SGlobPtr GPtr, short messageID, short messageType );
 951 extern  void    WriteError( SGlobPtr GPtr, short msgID, UInt32 tarID, UInt64 tarBlock );
 952 extern  short   CheckPause( void );
 953
 954 /* ------------------------------- From SControl.c ------------------------------- */
 955
 956 void                    ScavCtrl( SGlobPtr GPtr, UInt32 ScavOp, short *ScavRes );
 957
 958 extern  short   CheckForStop( SGlobPtr GPtr );
 959
 960
 961 /* ------------------------------- From SRepair.c -------------------------------- */
 962
 963 extern  OSErr   RepairVolume( SGlobPtr GPtr );
 964
 965 extern  int             FixDFCorruption( const SGlobPtr GPtr, RepairOrderPtr DFOrderP );
 966
 967 extern  OSErr   ProcessFileExtents( SGlobPtr GPtr, SFCB *fcb, UInt8 forkType, UInt16 flags, Boolean isExtentsBTree, Boolean *hasOverflowExtents, UInt32 *blocksUsed  );
 968
 969 /* Function to get return file path/name given an ID */
 970 extern  OSErr   GetSystemFileName(UInt32 fileID, char *filename, unsigned int *filenamelen);
 971 extern  OSErr   GetFileNamePathByID(SGlobPtr GPtr, UInt32 fileID, char *fullPath, unsigned int *fullPathLen, char *fileName, unsigned int *fileNameLen, u_int16_t *status);
 972 #define FNAME_BUF2SMALL 0x001   /* filename buffer was too small */
 973 #define FNAME_BIGNAME   0x002   /* filename is greater than NAME_MAX bytes */
 974 #define FPATH_BUF2SMALL 0x010   /* path buffer was too small */
 975 #define FPATH_BIGNAME   0x020   /* intermediate component in path is greater than NAME_MAX bytes */
 976 #define F_RESERVE_FILEID 0x100  /* file ID was less than kHFSFirstUserCatalogNodeID */
 977
 978 /* ------------------------------- From SUtils.c --------------------------------- */
 979
 980 extern  int             AllocBTN( SGlobPtr GPtr, short FilRefN, UInt32 NodeNum );
 981
 982 extern  int             IntError( SGlobPtr GPtr, OSErr ErrCode );
 983
 984 extern  void    RcdError( SGlobPtr GPtr, OSErr ErrCode );
 985
 986 extern  RepairOrderPtr AllocMinorRepairOrder( SGlobPtr GPtr, size_t extraBytes );
 987
 988 extern int IsDuplicateRepairOrder(SGlobPtr GPtr, RepairOrderPtr orig);
 989
 990 extern void DeleteRepairOrder(SGlobPtr GPtr, RepairOrderPtr orig);
 991
 992 extern  void    SetDFAStage( UInt32 stage );
 993 extern  UInt32  GetDFAGlobals( void );
 994
 995 extern void             InitializeVolumeObject( SGlobPtr GPtr );
 996 extern void     CheckEmbeddedVolInfoInMDBs( SGlobPtr GPtr );
 997 extern VolumeObjectPtr  GetVolumeObjectPtr( void );
 998 extern OSErr    GetVolumeObjectVHB( BlockDescriptor * theBlockDescPtr );
 999 extern void     GetVolumeObjectBlockNum( UInt64 * theBlockNumPtr );
1000 extern OSErr    GetVolumeObjectAlternateBlock( BlockDescriptor * theBlockDescPtr );
1001 extern OSErr    GetVolumeObjectPrimaryBlock( BlockDescriptor * theBlockDescPtr );
1002 extern void     GetVolumeObjectAlternateBlockNum( UInt64 * theBlockNumPtr );
1003 extern void     GetVolumeObjectPrimaryBlockNum( UInt64 * theBlockNumPtr );
1004 extern OSErr    GetVolumeObjectAlternateMDB( BlockDescriptor * theBlockDescPtr );
1005 extern OSErr    GetVolumeObjectPrimaryMDB( BlockDescriptor * theBlockDescPtr );
1006 extern OSErr    GetVolumeObjectVHBorMDB( BlockDescriptor * theBlockDescPtr );
1007 extern void     PrintName( int theCount, const UInt8 *theNamePtr, Boolean isUnicodeString );
1008 extern void     PrintVolumeObject( void );
1009 extern Boolean  VolumeObjectIsValid( void );
1010 extern Boolean  VolumeObjectIsHFSPlus( void );
1011 extern Boolean  VolumeObjectIsHFS( void );
1012 extern Boolean  VolumeObjectIsEmbeddedHFSPlus( void );
1013 extern Boolean  VolumeObjectIsPureHFSPlus( void );
1014 extern Boolean  VolumeObjectIsHFSX(SGlobPtr);
1015
1016 extern  void    InvalidateCalculatedVolumeBitMap( SGlobPtr GPtr );
1017
1018 extern  OSErr   GetVolumeFeatures( SGlobPtr GPtr );
1019
1020 OSErr   FlushAlternateVolumeControlBlock( SVCB *vcb, Boolean isHFSPlus );
1021
1022 extern  void    ConvertToHFSPlusExtent(const HFSExtentRecord oldExtents, HFSPlusExtentRecord newExtents);
1023
1024 void add_prime_bucket_uint32(PrimeBuckets *cur, uint32_t num);
1025
1026 void add_prime_bucket_uint64(PrimeBuckets *cur, uint64_t num);
1027
1028 int compare_prime_buckets(PrimeBuckets *bucket1, PrimeBuckets *bucket2);
1029
1030 /* ------------------------------- From CatalogCheck.c -------------------------------- */
1031
1032 extern  OSErr   CheckCatalogBTree( SGlobPtr GPtr );     //      catalog btree check
1033
1034 extern  OSErr   CheckFolderCount( SGlobPtr GPtr );      //      Compute folderCount
1035
1036 extern int  RecordBadAllocation(UInt32 parID, unsigned char * filename, UInt32 forkType, UInt32 oldBlkCnt, UInt32 newBlkCnt);
1037
1038 extern int  RecordTruncation(UInt32 parID, unsigned char * filename, UInt32 forkType, UInt64 oldSize,  UInt64 newSize);
1039
1040 /* ------------------------------- From SVerify1.c -------------------------------- */
1041
1042 extern  OSErr   CatFlChk( SGlobPtr GPtr );              //      catalog file check
1043
1044 extern  OSErr   CatHChk( SGlobPtr GPtr );               //      catalog hierarchy check
1045
1046 extern  OSErr   ExtBTChk( SGlobPtr GPtr );              //      extent btree check
1047
1048 extern  OSErr   BadBlockFileExtentCheck( SGlobPtr GPtr );       //      bad block file extent check
1049
1050 extern  OSErr   AttrBTChk( SGlobPtr GPtr );             //      attributes btree check
1051
1052 extern  OSErr   IVChk( SGlobPtr GPtr );
1053
1054 /* Operation type for CheckForClean */
1055 enum {
1056         kCheckVolume,           // check if volume is clean/dirty
1057         kMarkVolumeDirty,       // mark the volume dirty
1058         kMarkVolumeClean        // mark the volume clean
1059 };
1060 extern  int     CheckForClean( SGlobPtr GPtr, UInt8 operation, Boolean *modified );
1061
1062 extern  int     CheckIfJournaled(SGlobPtr GPtr, Boolean journal_bit_only);
1063
1064 typedef struct fsckJournalInfo {
1065         int     jnlfd;  // File descriptor for journal device
1066         off_t   jnlOffset;      // Offset of journal on journal device
1067         off_t   jnlSize;        // Size of journal on same
1068         char    *name;  // Name of journal device
1069 } fsckJournalInfo_t;
1070
1071 extern  int     IsJournalEmpty(SGlobPtr, fsckJournalInfo_t *);
1072
1073 extern  OSErr   VInfoChk( SGlobPtr GPtr );
1074
1075 extern  OSErr   VLockedChk( SGlobPtr GPtr );
1076
1077 extern  void    BuildExtentKey( Boolean isHFSPlus, UInt8 forkType, HFSCatalogNodeID fileNumber, UInt32 blockNumber, void * key );
1078
1079 extern  OSErr   OrphanedFileCheck( SGlobPtr GPtr, Boolean *problemsFound );
1080
1081 extern  int             cmpLongs (const void *a, const void *b);
1082
1083 extern  int CheckAttributeRecord(SGlobPtr GPtr, const HFSPlusAttrKey *key, const HFSPlusAttrRecord *rec, UInt16 reclen);
1084
1085 extern void RecordXAttrBits(SGlobPtr GPtr, UInt16 flags, HFSCatalogNodeID fileid, UInt16 btreetype);
1086
1087 extern  int FindOrigOverlapFiles(SGlobPtr GPtr);
1088
1089 extern  void PrintOverlapFiles (SGlobPtr GPtr);
1090
1091 /* ------------------------------- From SVerify2.c -------------------------------- */
1092
1093 typedef int (* CheckLeafRecordProcPtr)(SGlobPtr GPtr, void *key, void *record, UInt16 recordLen);
1094
1095 extern  int  BTCheck(SGlobPtr GPtr, short refNum, CheckLeafRecordProcPtr checkLeafRecord);
1096
1097 extern  int             BTMapChk( SGlobPtr GPtr, short FilRefN );
1098
1099 extern  OSErr   ChkCName( SGlobPtr GPtr, const CatalogName *name, Boolean unicode );    //      check catalog name
1100
1101 extern  OSErr   CmpBTH( SGlobPtr GPtr, SInt16 fileRefNum );
1102
1103 extern  int             CmpBTM( SGlobPtr GPtr, short FilRefN );
1104
1105 extern  int             CmpMDB( SGlobPtr GPtr, HFSMasterDirectoryBlock * mdbP);
1106
1107 extern  int             CmpVBM( SGlobPtr GPtr );
1108
1109 extern  OSErr   CmpBlock( void *block1P, void *block2P, size_t length ); /* same as 'memcmp', but EQ/NEQ only */
1110
1111 extern  OSErr   ChkExtRec ( SGlobPtr GPtr, UInt32 fileID, const void *extents , unsigned int *lastExtentIndex);
1112
1113 extern  int             BTCheckUnusedNodes(SGlobPtr GPtr, short fileRefNum, UInt16 *btStat);
1114
1115
1116 /* -------------------------- From SRebuildBTree.c ------------------------- */
1117
1118 extern  OSErr   RebuildBTree( SGlobPtr theSGlobPtr, int FileID );
1119
1120
1121 /* -------------------------- From SCatalog.c ------------------------- */
1122
1123 extern OSErr    UpdateFolderCount(      SVCB *vcb,
1124                                                                         HFSCatalogNodeID pid,
1125                                                                         const CatalogName *name,
1126                                                                         SInt16 newType,
1127                                                                         UInt32 hint,
1128                                                                         SInt16 valenceDelta );
1129
1130 /* ------------------------------- From SExtents.c -------------------------------- */
1131 OSErr   ZeroFileBlocks( SVCB *vcb, SFCB *fcb, UInt32 startingSector, UInt32 numberOfSectors );
1132
1133 OSErr MapFileBlockC (
1134         SVCB            *vcb,                           // volume that file resides on
1135         SFCB                    *fcb,                           // FCB of file
1136         UInt32                  numberOfBytes,          // number of contiguous bytes desired
1137         UInt64                  sectorOffset,           // starting offset within file (in 512-byte sectors)
1138         UInt64                  *startSector,           // first 512-byte volume sector (NOT an allocation block)
1139         UInt32                  *availableBytes);       // number of contiguous bytes (up to numberOfBytes)
1140
1141 OSErr DeallocateFile(SVCB *vcb, CatalogRecord * fileRec);
1142
1143 OSErr ExtendFileC (
1144         SVCB            *vcb,                           // volume that file resides on
1145         SFCB                    *fcb,                           // FCB of file to truncate
1146         UInt32                  sectorsToAdd,           // number of sectors to allocate
1147         UInt32                  flags,                          // EFContig and/or EFAll
1148         UInt32                  *actualSectorsAdded); // number of bytes actually allocated
1149
1150 OSErr FlushExtentFile( SVCB *vcb );
1151
1152 void ExtDataRecToExtents(
1153         const HFSExtentRecord   oldExtents,
1154         HFSPlusExtentRecord     newExtents);
1155
1156 OSErr UpdateExtentRecord (
1157         const SVCB              *vcb,
1158         SFCB                                    *fcb,
1159         const HFSPlusExtentKey  *extentFileKey,
1160         HFSPlusExtentRecord             extentData,
1161         UInt32                                  extentBTreeHint);
1162
1163 OSErr ReleaseExtents(
1164         SVCB                                    *vcb,
1165         const HFSPlusExtentRecord extentRecord,
1166         UInt32                                  *numReleasedAllocationBlocks,
1167         Boolean                                 *releasedLastExtent);
1168
1169 OSErr   CheckFileExtents( SGlobPtr GPtr, UInt32 fileNumber, UInt8 forkType, const unsigned char *xattrName,
1170                           const void *extents, UInt32 *blocksUsed );
1171 OSErr   GetBTreeHeader( SGlobPtr GPtr, SFCB* fcb, BTHeaderRec *header );
1172 OSErr   CompareVolumeBitMap( SGlobPtr GPtr, SInt32 whichBuffer );
1173 OSErr   CompareVolumeHeader( SGlobPtr GPtr, HFSPlusVolumeHeader *vh );
1174 OSErr   CreateExtentsBTreeControlBlock( SGlobPtr GPtr );
1175 OSErr   CreateCatalogBTreeControlBlock( SGlobPtr GPtr );
1176 OSErr   CreateAttributesBTreeControlBlock( SGlobPtr GPtr );
1177 OSErr   CreateExtendedAllocationsFCB( SGlobPtr GPtr );
1178
1179
1180 OSErr   CacheWriteInPlace( SVCB *vcb, UInt32 fileRefNum,  HIOParam *iopb, UInt64 currentPosition,
1181         UInt32 maximumBytes, UInt32 *actualBytes );
1182
1183
1184 /* Generic B-tree call back routines */
1185 OSStatus GetBlockProc (SFCB *filePtr, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block);
1186 OSStatus ReleaseBlockProc (SFCB *filePtr, BlockDescPtr blockPtr, ReleaseBlockOptions options);
1187 OSStatus SetEndOfForkProc (SFCB *filePtr, FSSize minEOF, FSSize maxEOF);
1188 OSStatus SetBlockSizeProc (SFCB *filePtr, ByteCount blockSize, ItemCount minBlockCount);
1189
1190 void DFA_PrepareInputName(ConstStr31Param name, Boolean isHFSPlus, CatalogName *catalogName);
1191
1192 extern  UInt32  CatalogNameSize( const CatalogName *name, Boolean isHFSPlus);
1193
1194 void    SetupFCB( SVCB *vcb, SInt16 refNum, UInt32 fileID, UInt32 fileClumpSize );
1195
1196
1197 extern  void    CalculateItemCount( SGlob *GPtr, UInt64 *itemCount, UInt64 *onePercent );
1198
1199
1200
1201 //      Macros
1202 extern          BTreeControlBlock*      GetBTreeControlBlock( short refNum );
1203 #define         GetBTreeControlBlock(refNum)    ((BTreeControlBlock*) ResolveFCB((refNum))->fcbBtree)
1204
1205 /*      The following macro marks a VCB as dirty by setting the upper 8 bits of the flags*/
1206 EXTERN_API_C( void )
1207 MarkVCBDirty                                    (SVCB *                 vcb);
1208
1209 #define MarkVCBDirty(vcb)       ((void) (vcb->vcbFlags |= 0xFF00))
1210 EXTERN_API_C( void )
1211 MarkVCBClean                                    (SVCB *                 vcb);
1212
1213 #define MarkVCBClean(vcb)       ((void) (vcb->vcbFlags &= 0x00FF))
1214 EXTERN_API_C( Boolean )
1215 IsVCBDirty                                              (SVCB *                 vcb);
1216
1217 #define IsVCBDirty(vcb)         ((Boolean) ((vcb->vcbFlags & 0xFF00) != 0))
1218
1219
1220 extern  pascal void M_Debugger(void);
1221 extern  pascal void M_DebugStr(ConstStr255Param debuggerMsg);
1222 #if ( DEBUG_BUILD )
1223         #define M_Debuger()                                     Debugger()
1224         #define M_DebugStr( debuggerMsg )       DebugStr( debuggerMsg )
1225 #else
1226         #define M_Debuger()
1227         #define M_DebugStr( debuggerMsg )
1228 #endif
1229
1230
1231 /*      Test for error and return if error occurred*/
1232 EXTERN_API_C( void )
1233 ReturnIfError                                   (OSErr                                  result);
1234
1235 #define ReturnIfError(result)                                   if ( (result) != noErr ) return (result); else ;
1236 /*      Test for passed condition and return if true*/
1237 EXTERN_API_C( void )
1238 ReturnErrorIf                                   (Boolean                                condition,
1239                                                                  OSErr                                  result);
1240
1241 #define ReturnErrorIf(condition, error)                 if ( (condition) )      return( (error) );
1242 /*      Exit function on error*/
1243 EXTERN_API_C( void )
1244 ExitOnError                                             (OSErr                                  result);
1245
1246 #define ExitOnError( result )                                   if ( ( result ) != noErr )      goto ErrorExit; else ;
1247
1248 /*      Return the low 16 bits of a 32 bit value, pinned if too large*/
1249 EXTERN_API_C( UInt16 )
1250 LongToShort                                             (UInt32                                 l);
1251
1252 #define LongToShort( l )        l <= (UInt32)0x0000FFFF ? ((UInt16) l) : ((UInt16) 0xFFFF)
1253
1254
1255 EXTERN_API_C( UInt32 )
1256 GetDFAStage                                             (void);
1257
1258 EXTERN_API_C(OSErr)
1259 DeleteCatalogNode(SVCB *vcb, UInt32 pid, const CatalogName * name, UInt32 hint, Boolean for_rename);
1260
1261 EXTERN_API_C(OSErr)
1262 GetCatalogNode(SVCB *vcb, UInt32 pid, const CatalogName * name, UInt32 hint, CatalogRecord *data);
1263
1264 EXTERN_API_C( SInt32 )
1265 CompareCatalogKeys                              (HFSCatalogKey *                searchKey,
1266                                                                  HFSCatalogKey *                trialKey);
1267
1268 EXTERN_API_C( SInt32 )
1269 CompareExtendedCatalogKeys              (HFSPlusCatalogKey *    searchKey,
1270                                                                  HFSPlusCatalogKey *    trialKey);
1271 EXTERN_API_C( SInt32 )
1272 CaseSensitiveCatalogKeyCompare (HFSPlusCatalogKey * searchKey,
1273                                 HFSPlusCatalogKey * trialKey);
1274
1275 EXTERN_API_C( SInt32 )
1276 CompareExtentKeys                               (const HFSExtentKey *   searchKey,
1277                                                                  const HFSExtentKey *   trialKey);
1278
1279 EXTERN_API_C( SInt32 )
1280 CompareExtentKeysPlus                   (const HFSPlusExtentKey * searchKey,
1281                                                                  const HFSPlusExtentKey * trialKey);
1282 EXTERN_API_C( SInt32 )
1283 CompareAttributeKeys                    (const AttributeKey * searchKey,  const AttributeKey * trialKey);
1284 EXTERN_API( SFCB* )
1285 ResolveFCB                                              (short                                  fileRefNum);
1286
1287 EXTERN_API_C( OSErr )
1288 ValidVolumeHeader                               (HFSPlusVolumeHeader *  volumeHeader);
1289
1290
1291 /* Old B-tree Manager API (going away soon!) */
1292
1293 EXTERN_API_C( OSErr )
1294 SearchBTreeRecord                               (SFCB                           *fcb,
1295                                                                  const void *                   key,
1296                                                                  UInt32                                 hint,
1297                                                                  void *                                 foundKey,
1298                                                                  void *                                 data,
1299                                                                  UInt16 *                               dataSize,
1300                                                                  UInt32 *                               newHint);
1301
1302 EXTERN_API_C( OSErr )
1303 GetBTreeRecord                                  (SFCB                           *fcb,
1304                                                                  SInt16                                 selectionIndex,
1305                                                                  void *                                 key,
1306                                                                  void *                                 data,
1307                                                                  UInt16 *                               dataSize,
1308                                                                  UInt32 *                               newHint);
1309
1310 EXTERN_API_C( OSErr )
1311 InsertBTreeRecord                               (SFCB                           *fcb,
1312                                                                  const void *                   key,
1313                                                                  const void *                   data,
1314                                                                  UInt16                                 dataSize,
1315                                                                  UInt32 *                               newHint);
1316
1317 EXTERN_API_C( OSErr )
1318 DeleteBTreeRecord                               (SFCB                           *fcb,
1319                                                                  const void *                   key);
1320
1321 EXTERN_API_C( OSErr )
1322 ReplaceBTreeRecord                              (SFCB                           *fcb,
1323                                                                  const void *                   key,
1324                                                                  UInt32                                 hint,
1325                                                                  void *                                 newData,
1326                                                                  UInt16                                 dataSize,
1327                                                                  UInt32 *                               newHint);
1328
1329 EXTERN_API_C( void )
1330 InitBTreeHeader                                 (UInt32                                 fileSize,
1331                                                                  UInt32                                 clumpSize,
1332                                                                  UInt16                                 nodeSize,
1333                                                                  UInt16                                 recordCount,
1334                                                                  UInt16                                 keySize,
1335                                                                  UInt32                                 attributes,
1336                                                                  UInt32 *                               mapNodes,
1337                                                                  void *                                 buffer);
1338
1339 EXTERN_API_C( OSErr )
1340 UpdateFreeCount                                 (SVCB *                 vcb);
1341
1342
1343 EXTERN_API_C(Boolean)
1344 NodesAreContiguous(     SFCB            *fcb,
1345                         UInt32          nodeSize);
1346
1347
1348
1349 UInt32 GetTimeUTC(void);
1350 UInt32 GetTimeLocal(Boolean forHFS);
1351
1352 OSErr FlushVolumeControlBlock( SVCB *vcb );
1353
1354 pascal short ResolveFileRefNum(SFCB * fileCtrlBlockPtr);
1355
1356 extern UInt32   CatalogNameLength( const CatalogName *name, Boolean isHFSPlus);
1357
1358 extern void             CopyCatalogName( const CatalogName *srcName, CatalogName *dstName, Boolean isHFSPLus);
1359
1360 extern  void    UpdateCatalogName( ConstStr31Param srcName, Str31 destName);
1361
1362 extern  void    BuildCatalogKey( HFSCatalogNodeID parentID, const CatalogName *name, Boolean isHFSPlus,
1363                                                                  CatalogKey *key);
1364
1365 extern void             UpdateVolumeEncodings( SVCB *volume, TextEncoding encoding);
1366
1367
1368 OSErr BlockAllocate (SVCB *vcb, UInt32 startingBlock, UInt32 blocksRequested, UInt32 blocksMaximum,
1369                         Boolean forceContiguous, UInt32 *actualStartBlock, UInt32 *actualNumBlocks);
1370 OSErr   BlockDeallocate ( SVCB *vcb, UInt32 firstBlock, UInt32 numBlocks);
1371 UInt32  DivideAndRoundUp( UInt32 numerator, UInt32 denominator);
1372 OSErr   BlockFindAll(SFCB *fcb, UInt32 needed);
1373
1374 OSErr InitializeBlockCache ( UInt32 blockSize, UInt32 blockCount );
1375
1376 void    SetFCBSPtr( Ptr value );
1377 Ptr     GetFCBSPtr( void );
1378
1379
1380 /*
1381  * UTF-8 conversion routines
1382  */
1383 extern int utf_decodestr(const unsigned char *, size_t, u_int16_t *, size_t *, size_t);
1384 extern int utf_encodestr(const u_int16_t *, size_t, unsigned char *, size_t *, size_t);
1385
1386 /*
1387  * HardLink checking routines
1388  */
1389 extern int   HardLinkCheckBegin(SGlobPtr gp, void** cookie);
1390 extern void  HardLinkCheckEnd(void * cookie);
1391 extern void  CaptureHardLink(void * cookie, const HFSPlusCatalogFile *file);
1392 extern int   CheckHardLinks(void *cookie);
1393
1394 extern void hardlink_add_bucket(PrimeBuckets *bucket, uint32_t inode_id, uint32_t cur_link_id);
1395 extern int inode_check(SGlobPtr, PrimeBuckets *, CatalogRecord *, CatalogKey *, Boolean);
1396 extern void record_link_badchain(SGlobPtr, Boolean);
1397 extern int record_link_badflags(SGlobPtr, uint32_t, Boolean, uint32_t, uint32_t);
1398 extern int record_inode_badflags(SGlobPtr, uint32_t, Boolean, uint32_t, uint32_t, Boolean);
1399 extern int record_dirlink_badownerflags(SGlobPtr, uint32_t, uint8_t, uint8_t, int);
1400 extern int record_link_badfinderinfo(SGlobPtr, uint32_t, Boolean);
1401
1402 extern int get_first_link_id(SGlobPtr gptr, CatalogRecord *inode_rec, uint32_t inode_id, Boolean isdir, uint32_t *first_link_id);
1403 extern int filelink_hash_inode(UInt32 inode_id, UInt32 linkCount);
1404
1405 /*
1406  * Directory Hard Link checking routines
1407  */
1408 extern int dirhardlink_init(SGlobPtr gptr);
1409 extern int dirhardlink_check(SGlobPtr gptr);
1410
1411 extern OSErr GetCatalogRecordByID(SGlobPtr GPtr, UInt32 file_id, Boolean isHFSPlus, CatalogKey *key, CatalogRecord *rec, uint16_t *recsize);
1412
1413 struct HardLinkInfo;
1414 extern int RepairHardLinkChains(SGlobPtr, Boolean);
1415
1416 /*
1417  * Volume Bitmap checking routines
1418  */
1419 extern int  BitMapCheckBegin(SGlobPtr g);
1420 extern int  BitMapCheckEnd(void);
1421 extern int  CaptureBitmapBits(UInt32 startBit, UInt32 bitCount);
1422 extern int  ReleaseBitmapBits(UInt32 startBit, UInt32 bitCount);
1423 extern int  CheckVolumeBitMap(SGlobPtr g, Boolean repair);
1424 extern void UpdateFreeBlockCount(SGlobPtr g);
1425 extern int      AllocateContigBitmapBits (SVCB *vcb, UInt32 numBlocks, UInt32 *actualStartBlock);
1426 extern int  IsTrimSupported(void);
1427 extern void TrimFreeBlocks(SGlobPtr g);
1428
1429 /*
1430  * Variables and routines to support mapping a physical block number to a
1431  * file path
1432  */
1433 struct found_blocks {
1434         u_int64_t block;
1435         u_int32_t fileID;
1436         u_int32_t padding;
1437 };
1438 #define FOUND_BLOCKS_QUANTUM    30
1439 extern int gBlkListEntries;
1440 extern u_int64_t *gBlockList;
1441 extern int gFoundBlockEntries;
1442 extern struct found_blocks *gFoundBlocksList;
1443 extern long gBlockSize;
1444 void CheckPhysicalMatch(SVCB *vcb, UInt32 startblk, UInt32 blkcount, UInt32 fileNumber, UInt8 forkType);
1445 void dumpblocklist(SGlobPtr GPtr);
1446
1447 #ifdef __cplusplus
1448 };
1449 #endif
1450
1451 #endif /* __SCAVENGER__ */