livefiles_hfs_plugin/lf_hfs_btrees_internal.h

   1 //
   2 //  lf_hfs_btrees_internal.h
   3 //  livefiles_hfs
   4 //
   5 //  Created by Yakov Ben Zaken on 22/03/2018.
   6 //
   7
   8 #ifndef lf_hfs_btrees_internal_h
   9 #define lf_hfs_btrees_internal_h
  10
  11 #include "lf_hfs_file_mgr_internal.h"
  12
  13 enum {
  14     fsBTInvalidHeaderErr                = btBadHdr,
  15     fsBTBadRotateErr                    = dsBadRotate,
  16     fsBTInvalidNodeErr                  = btBadNode,
  17     fsBTRecordTooLargeErr               = btNoFit,
  18     fsBTRecordNotFoundErr               = btNotFound,
  19     fsBTDuplicateRecordErr              = btExists,
  20     fsBTFullErr                         = btNoSpaceAvail,
  21
  22     fsBTInvalidFileErr                  = ERR_BASE + 0x0302,    /* no BTreeCB has been allocated for fork*/
  23     fsBTrFileAlreadyOpenErr             = ERR_BASE + 0x0303,
  24     fsBTInvalidIteratorErr              = ERR_BASE + 0x0308,
  25     fsBTEmptyErr                        = ERR_BASE + 0x030A,
  26     fsBTNoMoreMapNodesErr               = ERR_BASE + 0x030B,
  27     fsBTBadNodeSize                     = ERR_BASE + 0x030C,
  28     fsBTBadNodeType                     = ERR_BASE + 0x030D,
  29     fsBTInvalidKeyLengthErr             = ERR_BASE + 0x030E,
  30     fsBTStartOfIterationErr             = ERR_BASE + 0x0353,
  31     fsBTEndOfIterationErr               = ERR_BASE + 0x0354,
  32     fsBTUnknownVersionErr               = ERR_BASE + 0x0355,
  33     fsBTTreeTooDeepErr                  = ERR_BASE + 0x0357,
  34     fsIteratorExitedScopeErr            = ERR_BASE + 0x0A02,    /* iterator exited the scope*/
  35     fsIteratorScopeExceptionErr         = ERR_BASE + 0x0A03,    /* iterator is undefined due to error or movement of scope locality*/
  36     fsUnknownIteratorMovementErr        = ERR_BASE + 0x0A04,    /* iterator movement is not defined*/
  37     fsInvalidIterationMovmentErr        = ERR_BASE + 0x0A05,    /* iterator movement is invalid in current context*/
  38     fsClientIDMismatchErr               = ERR_BASE + 0x0A06,    /* wrong client process ID*/
  39     fsEndOfIterationErr                 = ERR_BASE + 0x0A07,    /* there were no objects left to return on iteration*/
  40     fsBTTimeOutErr                      = ERR_BASE + 0x0A08     /* BTree scan interrupted -- no time left for physical I/O */
  41 };
  42
  43 typedef struct {
  44     void            *buffer;
  45     void            *blockHeader;
  46     daddr64_t       blockNum;    /* logical block number (used by hfs_swap_BTNode) */
  47     ByteCount       blockSize;
  48     Boolean         blockReadFromDisk;
  49     Byte            isModified;             // XXXdbg - for journaling
  50     Byte            reserved[2];
  51
  52 } BlockDescriptor, *BlockDescPtr;
  53
  54
  55 typedef struct {
  56     void *          bufferAddress;
  57     ByteCount       itemSize;
  58     ItemCount       itemCount;
  59
  60 } FSBufferDescriptor, *FSBufferDescriptorPtr;
  61
  62
  63 /*
  64  Fork Level Access Method Block get options
  65  */
  66 enum {
  67     kGetBlock               = 0x00000000,
  68     kGetBlockHint           = 0x00000001,    // if set, the block is being looked up using hint
  69     kForceReadBlock         = 0x00000002,    // how does this relate to Read/Verify? Do we need this?
  70     kGetEmptyBlock          = 0x00000008
  71 };
  72 typedef u_int32_t    GetBlockOptions;
  73
  74 /*
  75  Fork Level Access Method Block release options
  76  */
  77 enum {
  78     kReleaseBlock        = 0x00000000,
  79     kForceWriteBlock    = 0x00000001,
  80     kMarkBlockDirty        = 0x00000002,
  81     kTrashBlock            = 0x00000004,
  82     kLockTransaction    = 0x00000100
  83 };
  84 typedef u_int32_t    ReleaseBlockOptions;
  85
  86 typedef    u_int64_t    FSSize;
  87 typedef    u_int32_t    ForkBlockNumber;
  88
  89 /*============================================================================
  90  Fork Level Buffered I/O Access Method
  91  ============================================================================*/
  92
  93 typedef    OSStatus    (* GetBlockProcPtr)        (FileReference                fileRefNum,
  94                                                    uint64_t                     blockNum,
  95                                                    GetBlockOptions              options,
  96                                                    BlockDescriptor              *block );
  97
  98
  99 typedef    OSStatus    (* ReleaseBlockProcPtr)    (FileReference                fileRefNum,
 100                                                    BlockDescPtr                 blockPtr,
 101                                                    ReleaseBlockOptions          options );
 102
 103 typedef    OSStatus    (* SetEndOfForkProcPtr)    (FileReference                fileRefNum,
 104                                                    FSSize                       minEOF,
 105                                                    FSSize                       maxEOF );
 106
 107 typedef    OSStatus    (* SetBlockSizeProcPtr)    (FileReference                fileRefNum,
 108                                                    ByteCount                    blockSize,
 109                                                    ItemCount                    minBlockCount );
 110
 111 OSStatus SetEndOfForkProc ( FileReference fileRefNum, FSSize minEOF, FSSize maxEOF );
 112
 113
 114 /*
 115  B*Tree Information Version
 116  */
 117 enum BTreeInformationVersion{
 118     kBTreeInfoVersion    = 0
 119 };
 120
 121 /*
 122  B*Tree Iteration Operation Constants
 123  */
 124 enum BTreeIterationOperations{
 125         kBTreeFirstRecord,
 126         kBTreeNextRecord,
 127         kBTreePrevRecord,
 128         kBTreeLastRecord,
 129         kBTreeCurrentRecord
 130 };
 131 typedef u_int16_t BTreeIterationOperation;
 132
 133
 134 /*
 135  Btree types: 0 is HFS CAT/EXT file, 1~127 are AppleShare B*Tree files, 128~254 unused
 136  hfsBtreeType       EQU        0              ; control file
 137  validBTType        EQU        $80            ; user btree type starts from 128
 138  userBT1Type        EQU        $FF            ; 255 is our Btree type. Used by BTInit and BTPatch
 139  */
 140 enum BTreeTypes{
 141     kHFSBTreeType               =   0,        // control file
 142     kUserBTreeType              = 128,        // user btree type starts from 128
 143     kReservedBTreeType          = 255         //
 144 };
 145
 146 #define    kBTreeHeaderUserBytes    128
 147
 148 /* B-tree structures */
 149
 150 enum {
 151     kMaxKeyLength    = 520
 152 };
 153
 154 typedef union {
 155     u_int8_t    length8;
 156     u_int16_t    length16;
 157     u_int8_t    rawData [kMaxKeyLength+2];
 158
 159 } BTreeKey, *BTreeKeyPtr;
 160
 161 /* BTNodeDescriptor -- Every B-tree node starts with these fields. */
 162 typedef struct {
 163     u_int32_t       fLink;              /* next node at this level*/
 164     u_int32_t       bLink;              /* previous node at this level*/
 165     int8_t          kind;               /* kind of node (leaf, index, header, map)*/
 166     u_int8_t        height;             /* zero for header, map; child is one more than parent*/
 167     u_int16_t       numRecords;         /* number of records in this node*/
 168     u_int16_t       reserved;           /* reserved - initialized as zero */
 169
 170 } __attribute__((aligned(2), packed)) BTNodeDescriptor;
 171
 172 /* Constants for BTNodeDescriptor kind */
 173 enum {
 174     kBTLeafNode     = -1,
 175     kBTIndexNode    = 0,
 176     kBTHeaderNode   = 1,
 177     kBTMapNode      = 2
 178 };
 179
 180 /* BTHeaderRec -- The first record of a B-tree header node */
 181 typedef struct {
 182     u_int16_t       treeDepth;          /* maximum height (usually leaf nodes) */
 183     u_int32_t       rootNode;           /* node number of root node */
 184     u_int32_t       leafRecords;        /* number of leaf records in all leaf nodes */
 185     u_int32_t       firstLeafNode;      /* node number of first leaf node */
 186     u_int32_t       lastLeafNode;       /* node number of last leaf node */
 187     u_int16_t       nodeSize;           /* size of a node, in bytes */
 188     u_int16_t       maxKeyLength;       /* reserved */
 189     u_int32_t       totalNodes;         /* total number of nodes in tree */
 190     u_int32_t       freeNodes;          /* number of unused (free) nodes in tree */
 191     u_int16_t       reserved1;          /* unused */
 192     u_int32_t       clumpSize;          /* reserved */
 193     u_int8_t        btreeType;          /* reserved */
 194     u_int8_t        keyCompareType;     /* Key string Comparison Type */
 195     u_int32_t       attributes;         /* persistent attributes about the tree */
 196     u_int32_t       reserved3[16];      /* reserved */
 197
 198 } __attribute__((aligned(2), packed)) BTHeaderRec;
 199
 200 /* Constants for BTHeaderRec attributes */
 201 enum {
 202     kBTBadCloseMask         = 0x00000001,    /* reserved */
 203     kBTBigKeysMask         = 0x00000002,    /* key length field is 16 bits */
 204     kBTVariableIndexKeysMask = 0x00000004    /* keys in index nodes are variable length */
 205 };
 206
 207 /*
 208  BTreeInfoRec Structure - for BTGetInformation
 209  */
 210 typedef struct {
 211     u_int16_t            version;
 212     u_int16_t            nodeSize;
 213     u_int16_t            maxKeyLength;
 214     u_int16_t            treeDepth;
 215     u_int32_t            lastfsync;        /* Last time that this was fsynced  */
 216     ItemCount            numRecords;
 217     ItemCount            numNodes;
 218     ItemCount            numFreeNodes;
 219     u_int8_t            keyCompareType;
 220     u_int8_t            reserved[3];
 221 } BTreeInfoRec, *BTreeInfoRecPtr;
 222
 223 /*
 224  BTreeHint can never be exported to the outside. Use u_int32_t BTreeHint[4],
 225  u_int8_t BTreeHint[16], etc.
 226  */
 227 typedef struct {
 228     ItemCount                writeCount;
 229     u_int32_t                nodeNum;            // node the key was last seen in
 230     u_int16_t                index;                // index then key was last seen at
 231     u_int16_t                reserved1;
 232     u_int32_t                reserved2;
 233 } BTreeHint, *BTreeHintPtr;
 234
 235 /*
 236  BTree Iterator
 237  */
 238 typedef struct {
 239     BTreeHint                hint;
 240     u_int16_t                version;
 241     u_int16_t                reserved;
 242     u_int32_t                hitCount;            // Total number of leaf records hit
 243     u_int32_t                maxLeafRecs;        // Max leaf records over iteration
 244     BTreeKey                key;
 245 } BTreeIterator, *BTreeIteratorPtr;
 246
 247
 248 /*============================================================================
 249  B*Tree SPI
 250  ============================================================================*/
 251
 252 /*
 253  Key Comparison Function ProcPtr Type - for BTOpenPath
 254  */
 255 //typedef int32_t                 (* KeyCompareProcPtr)(BTreeKeyPtr a, BTreeKeyPtr b);
 256
 257
 258 typedef int32_t (* IterateCallBackProcPtr)(BTreeKeyPtr key, void * record, void * state);
 259
 260 OSStatus    BTOpenPath            (FCB *filePtr, KeyCompareProcPtr keyCompareProc);
 261
 262 OSStatus    BTClosePath           (FCB *filePtr );
 263
 264
 265 OSStatus    BTSearchRecord        (FCB                          *filePtr,
 266                                    BTreeIterator                *searchIterator,
 267                                    FSBufferDescriptor           *btRecord,
 268                                    u_int16_t                    *recordLen,
 269                                    BTreeIterator                *resultIterator );
 270
 271 OSStatus    BTIterateRecord       (FCB                          *filePtr,
 272                                    BTreeIterationOperation      operation,
 273                                    BTreeIterator                *iterator,
 274                                    FSBufferDescriptor           *btRecord,
 275                                    u_int16_t                    *recordLen );
 276
 277
 278 OSStatus BTIterateRecords         (FCB                          *filePtr,
 279                                    BTreeIterationOperation      operation,
 280                                    BTreeIterator                *iterator,
 281                                    IterateCallBackProcPtr       callBackProc,
 282                                    void                         *callBackState);
 283
 284 OSStatus    BTInsertRecord        (FCB                          *filePtr,
 285                                    BTreeIterator                *iterator,
 286                                    FSBufferDescriptor           *btrecord,
 287                                    u_int16_t                    recordLen );
 288
 289 OSStatus    BTReplaceRecord       (FCB                          *filePtr,
 290                                    BTreeIterator                *iterator,
 291                                    FSBufferDescriptor           *btRecord,
 292                                    u_int16_t                    recordLen );
 293
 294 OSStatus    BTUpdateRecord        (FCB                         *filePtr,
 295                                    BTreeIterator               *iterator,
 296                                    IterateCallBackProcPtr      callBackProc,
 297                                    void                        *callBackState );
 298
 299 OSStatus    BTDeleteRecord        (FCB                         *filePtr,
 300                                    BTreeIterator               *iterator );
 301
 302 OSStatus    BTGetInformation     (FCB                          *filePtr,
 303                                   u_int16_t                    vers,
 304                                   BTreeInfoRec                 *info );
 305
 306 OSStatus    BTIsDirty            (FCB *filePtr);
 307
 308 OSStatus    BTFlushPath          (FCB *filePtr);
 309
 310 OSStatus    BTReloadData         (FCB *filePtr);
 311
 312 OSStatus    BTInvalidateHint     (BTreeIterator *iterator );
 313
 314 OSStatus    BTGetLastSync        (FCB                        *filePtr,
 315                                   u_int32_t                  *lastfsync );
 316
 317 OSStatus    BTSetLastSync        (FCB                         *filePtr,
 318                                   u_int32_t                   lastfsync );
 319
 320 OSStatus    BTHasContiguousNodes(FCB *filePtr);
 321
 322 OSStatus    BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize);
 323
 324 OSStatus    BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize);
 325
 326 /* B-tree node reserve routines. */
 327 void BTReserveSetup(void);
 328
 329 int  BTReserveSpace(FCB *file, int operations, void * data);
 330
 331 int  BTReleaseReserve(FCB *file, void * data);
 332
 333 int  BTZeroUnusedNodes(FCB *file);
 334
 335
 336 #endif /* lf_hfs_btrees_internal_h */