livefiles_hfs_plugin/lf_hfs_btrees_private.h

   1 //
   2 //  lf_hfs_btrees_private.h
   3 //  livefiles_hfs
   4 //
   5 //  Created by Yakov Ben Zaken on 22/03/2018.
   6 //
   7
   8 #ifndef lf_hfs_btrees_private_h
   9 #define lf_hfs_btrees_private_h
  10
  11 #include "lf_hfs_defs.h"
  12 #include "lf_hfs_file_mgr_internal.h"
  13 #include "lf_hfs_btrees_internal.h"
  14 #include "lf_hfs_logger.h"
  15
  16 /////////////////////////////////// Constants ///////////////////////////////////
  17
  18 #define        kBTreeVersion          1
  19 #define        kMaxTreeDepth         16
  20
  21
  22 #define        kHeaderNodeNum          0
  23 #define        kKeyDescRecord          1
  24
  25
  26 // Header Node Record Offsets
  27 enum {
  28     kHeaderRecOffset        =    0x000E,
  29     kKeyDescRecOffset       =    0x0078,
  30     kHeaderMapRecOffset     =    0x00F8
  31 };
  32
  33 #define        kMinNodeSize        (512)
  34
  35 #define        kMinRecordSize      (6)
  36 // where is minimum record size enforced?
  37
  38 // miscellaneous BTree constants
  39 enum {
  40     kOffsetSize                = 2
  41 };
  42
  43 // Insert Operations
  44 typedef enum {
  45     kInsertRecord               = 0,
  46     kReplaceRecord              = 1
  47 } InsertType;
  48
  49 // illegal string attribute bits set in mask
  50 #define        kBadStrAttribMask        (0xCF)
  51
  52
  53
  54 //////////////////////////////////// Macros /////////////////////////////////////
  55
  56 #define        M_NodesInMap(mapSize)                ((mapSize) << 3)
  57
  58 #define        M_ClearBitNum(integer,bitNumber)     ((integer) &= (~(1<<(bitNumber))))
  59 #define        M_SetBitNum(integer,bitNumber)       ((integer) |= (1<<(bitNumber)))
  60 #define        M_IsOdd(integer)                     (((integer) & 1) != 0)
  61 #define        M_IsEven(integer)                    (((integer) & 1) == 0)
  62
  63 #define        M_MapRecordSize(nodeSize)            (nodeSize - sizeof (BTNodeDescriptor) - 6)
  64 #define        M_HeaderMapRecordSize(nodeSize)      (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
  65
  66 #define        M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
  67 #define        M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))
  68
  69 ///////////////////////////////////// Types /////////////////////////////////////
  70
  71 typedef struct {                    // fields specific to BTree CBs
  72
  73     u_int8_t                        keyCompareType;        /* Key string Comparison Type */
  74     u_int8_t                        btreeType;
  75     u_int16_t                       treeDepth;
  76     FileReference                   fileRefNum;            // refNum of btree file
  77     KeyCompareProcPtr               keyCompareProc;
  78     u_int32_t                       rootNode;
  79     u_int32_t                       leafRecords;
  80     u_int32_t                       firstLeafNode;
  81     u_int32_t                       lastLeafNode;
  82     u_int16_t                       nodeSize;
  83     u_int16_t                       maxKeyLength;
  84     u_int32_t                       totalNodes;
  85     u_int32_t                       freeNodes;
  86
  87     u_int16_t                       reserved3;              // 4-byte alignment
  88
  89     // new fields
  90     int16_t                         version;
  91     u_int32_t                       flags;                  // dynamic flags
  92     u_int32_t                       attributes;             // persistent flags
  93     u_int32_t                       writeCount;
  94     u_int32_t                       lastfsync;              /* Last time that this was fsynced  */
  95
  96     GetBlockProcPtr                 getBlockProc;
  97     ReleaseBlockProcPtr             releaseBlockProc;
  98     SetEndOfForkProcPtr             setEndOfForkProc;
  99
 100     // statistical information
 101     u_int32_t                       numGetNodes;
 102     u_int32_t                       numGetNewNodes;
 103     u_int32_t                       numReleaseNodes;
 104     u_int32_t                       numUpdateNodes;
 105     u_int32_t                       numMapNodesRead;        // map nodes beyond header node
 106     u_int32_t                       numHintChecks;
 107     u_int32_t                       numPossibleHints;       // Looks like a formated hint
 108     u_int32_t                       numValidHints;          // Hint used to find correct record.
 109     u_int32_t                       reservedNodes;
 110     BTreeIterator                   iterator;               // useable when holding exclusive b-tree lock
 111
 112 #if DEBUG
 113     void                        *madeDirtyBy[2];
 114 #endif
 115
 116 } BTreeControlBlock, *BTreeControlBlockPtr;
 117
 118 u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
 119 #define CalcKeySize(btcb, key)            ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
 120
 121 u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
 122 #define KeyLength(btcb, key)            ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
 123
 124
 125 typedef enum {
 126     kBTHeaderDirty    = 0x00000001
 127 } BTreeFlags;
 128
 129 static inline void M_BTreeHeaderDirty(BTreeControlBlock *bt) {
 130 #if DEBUG
 131     bt->madeDirtyBy[0] = __builtin_return_address(0);
 132     bt->madeDirtyBy[1] = __builtin_return_address(1);
 133 #endif
 134     bt->flags |= kBTHeaderDirty;
 135 }
 136
 137 typedef int8_t              *NodeBuffer;
 138 typedef BlockDescriptor     NodeRec, *NodePtr;        //remove this someday...
 139
 140
 141 //// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
 142
 143 typedef struct {
 144     u_int32_t                node;                // node number
 145     u_int16_t                index;
 146     u_int16_t                reserved;            // align size to a power of 2
 147
 148 } TreePathRecord, *TreePathRecordPtr;
 149
 150 typedef TreePathRecord TreePathTable [kMaxTreeDepth];
 151
 152
 153 //// InsertKey - used by InsertTree, InsertLevel and InsertNode
 154
 155 typedef struct {
 156     BTreeKeyPtr         keyPtr;
 157     u_int8_t *          recPtr;
 158     u_int16_t           keyLength;
 159     u_int16_t           recSize;
 160     Boolean             replacingKey;
 161     Boolean             skipRotate;
 162 } InsertKey;
 163
 164 //// For Notational Convenience
 165
 166 typedef     BTNodeDescriptor*       NodeDescPtr;
 167 typedef     u_int8_t                *RecordPtr;
 168 typedef     BTreeKeyPtr             KeyPtr;
 169
 170
 171 //////////////////////////////////// Globals ////////////////////////////////////
 172
 173
 174 //////////////////////////////////// Macros /////////////////////////////////////
 175 //    Exit function on error
 176 #define M_ExitOnError( result )    do { if ( ( result ) != noErr )    goto ErrorExit; } while(0)
 177
 178 //    Test for passed condition and return if true
 179 #define    M_ReturnErrorIf( condition, error )    do { if ( condition )    return( error ); } while(0)
 180
 181 //////////////////////////////// Key Operations /////////////////////////////////
 182
 183 int32_t        CompareKeys                (BTreeControlBlockPtr         btreePtr,
 184                                            KeyPtr                       searchKey,
 185                                            KeyPtr                       trialKey );
 186
 187 //////////////////////////////// Map Operations /////////////////////////////////
 188
 189 OSStatus    AllocateNode            (BTreeControlBlockPtr     btreePtr,
 190                                      u_int32_t                *nodeNum);
 191
 192 OSStatus    FreeNode                (BTreeControlBlockPtr     btreePtr,
 193                                      u_int32_t                nodeNum);
 194
 195 OSStatus    ExtendBTree             (BTreeControlBlockPtr     btreePtr,
 196                                      u_int32_t                nodes );
 197
 198 u_int32_t    CalcMapBits            (BTreeControlBlockPtr     btreePtr);
 199
 200
 201 void         BTUpdateReserve        (BTreeControlBlockPtr   btreePtr,
 202                                      int                    nodes);
 203
 204 //////////////////////////////// Misc Operations ////////////////////////////////
 205
 206 u_int16_t    CalcKeyRecordSize        (u_int16_t                keySize,
 207                                        u_int16_t                recSize );
 208
 209 OSStatus    VerifyHeader            (FCB                        *filePtr,
 210                                      BTHeaderRec                *header );
 211
 212 OSStatus    UpdateHeader            (BTreeControlBlockPtr       btreePtr,
 213                                      Boolean                    forceWrite );
 214
 215 OSStatus    FindIteratorPosition    (BTreeControlBlockPtr       btreePtr,
 216                                      BTreeIteratorPtr           iterator,
 217                                      BlockDescriptor            *left,
 218                                      BlockDescriptor            *middle,
 219                                      BlockDescriptor            *right,
 220                                      u_int32_t                  *nodeNum,
 221                                      u_int16_t                  *index,
 222                                      Boolean                    *foundRecord );
 223
 224 OSStatus    CheckInsertParams        (FCB                       *filePtr,
 225                                       BTreeIterator             *iterator,
 226                                       FSBufferDescriptor        *record,
 227                                       u_int16_t                 recordLen );
 228
 229 OSStatus    TrySimpleReplace        (BTreeControlBlockPtr       btreePtr,
 230                                      NodeDescPtr                nodePtr,
 231                                      BTreeIterator              *iterator,
 232                                      FSBufferDescriptor         *record,
 233                                      u_int16_t                  recordLen,
 234                                      Boolean                    *recordInserted );
 235
 236 OSStatus    IsItAHint                (BTreeControlBlockPtr      btreePtr,
 237                                       BTreeIterator             *iterator,
 238                                       Boolean                   *answer );
 239
 240 OSStatus    TreeIsDirty             (BTreeControlBlockPtr       btreePtr);
 241
 242 //////////////////////////////// Node Operations ////////////////////////////////
 243
 244 //// Node Operations
 245
 246 OSStatus    GetNode                    (BTreeControlBlockPtr    btreePtr,
 247                                         u_int32_t               nodeNum,
 248                                         u_int32_t               flags,
 249                                         NodeRec                 *returnNodePtr );
 250
 251 /* Flags for GetNode() */
 252 #define        kGetNodeHint    0x1        /* If set, the node is being looked up using a hint */
 253
 254 OSStatus    GetLeftSiblingNode        (BTreeControlBlockPtr     btreePtr,
 255                                        NodeDescPtr              node,
 256                                        NodeRec                  *left );
 257
 258 #define        GetLeftSiblingNode(btree,node,left)            GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left))
 259
 260 OSStatus    GetRightSiblingNode        (BTreeControlBlockPtr        btreePtr,
 261                                         NodeDescPtr                 node,
 262                                         NodeRec                     *right );
 263
 264 #define        GetRightSiblingNode(btree,node,right)        GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right))
 265
 266
 267 OSStatus    GetNewNode                (BTreeControlBlockPtr   btreePtr,
 268                                        u_int32_t              nodeNum,
 269                                        NodeRec                *returnNodePtr );
 270
 271 OSStatus    ReleaseNode                (BTreeControlBlockPtr        btreePtr,
 272                                         NodePtr                     nodePtr );
 273
 274 OSStatus    TrashNode                (BTreeControlBlockPtr      btreePtr,
 275                                       NodePtr                   nodePtr );
 276
 277 OSStatus    UpdateNode                (BTreeControlBlockPtr     btreePtr,
 278                                        NodePtr                  nodePtr,
 279                                        u_int32_t                transactionID,
 280                                        u_int32_t                flags );
 281
 282 //// Node Buffer Operations
 283
 284 void        ClearNode                (BTreeControlBlockPtr      btreePtr,
 285                                       NodeDescPtr               node );
 286
 287 u_int16_t    GetNodeDataSize            (BTreeControlBlockPtr       btreePtr,
 288                                          NodeDescPtr                node );
 289
 290 u_int16_t    GetNodeFreeSize            (BTreeControlBlockPtr       btreePtr,
 291                                          NodeDescPtr                node );
 292
 293
 294 //// Record Operations
 295
 296 Boolean        InsertRecord            (BTreeControlBlockPtr     btreePtr,
 297                                         NodeDescPtr              node,
 298                                         u_int16_t                index,
 299                                         RecordPtr                recPtr,
 300                                         u_int16_t                recSize );
 301
 302 Boolean        InsertKeyRecord            (BTreeControlBlockPtr     btreePtr,
 303                                            NodeDescPtr              node,
 304                                            u_int16_t                index,
 305                                            KeyPtr                   keyPtr,
 306                                            u_int16_t                keyLength,
 307                                            RecordPtr                recPtr,
 308                                            u_int16_t                recSize );
 309
 310 void        DeleteRecord            (BTreeControlBlockPtr    btree,
 311                                      NodeDescPtr             node,
 312                                      u_int16_t               index );
 313
 314
 315 Boolean        SearchNode           (BTreeControlBlockPtr       btree,
 316                                      NodeDescPtr                node,
 317                                      KeyPtr                     searchKey,
 318                                      u_int16_t                  *index );
 319
 320 OSStatus    GetRecordByIndex        (BTreeControlBlockPtr       btree,
 321                                      NodeDescPtr                node,
 322                                      u_int16_t                  index,
 323                                      KeyPtr                     *keyPtr,
 324                                      u_int8_t *                 *dataPtr,
 325                                      u_int16_t                  *dataSize );
 326
 327 u_int8_t *    GetRecordAddress        (BTreeControlBlockPtr     btree,
 328                                        NodeDescPtr              node,
 329                                        u_int16_t                index );
 330
 331 #define GetRecordAddress(btreePtr,node,index)        ((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
 332
 333
 334 u_int16_t    GetRecordSize            (BTreeControlBlockPtr     btree,
 335                                        NodeDescPtr              node,
 336                                        u_int16_t                index );
 337
 338 u_int32_t    GetChildNodeNum            (BTreeControlBlockPtr       btreePtr,
 339                                          NodeDescPtr                nodePtr,
 340                                          u_int16_t                  index );
 341
 342 void        MoveRecordsLeft            (u_int8_t *                  src,
 343                                         u_int8_t *                  dst,
 344                                         u_int16_t                   bytesToMove );
 345
 346 #define        MoveRecordsLeft(src,dst,bytes)            bcopy((src),(dst),(bytes))
 347
 348 void        MoveRecordsRight        (u_int8_t *                 src,
 349                                      u_int8_t *                 dst,
 350                                      u_int16_t                  bytesToMove );
 351
 352 #define        MoveRecordsRight(src,dst,bytes)            bcopy((src),(dst),(bytes))
 353
 354
 355 //////////////////////////////// Tree Operations ////////////////////////////////
 356
 357 OSStatus    SearchTree                (BTreeControlBlockPtr     btreePtr,
 358                                        BTreeKeyPtr              keyPtr,
 359                                        TreePathTable            treePathTable,
 360                                        u_int32_t                *nodeNum,
 361                                        BlockDescriptor          *nodePtr,
 362                                        u_int16_t                *index );
 363
 364 OSStatus    InsertTree                (BTreeControlBlockPtr     btreePtr,
 365                                        TreePathTable            treePathTable,
 366                                        KeyPtr                   keyPtr,
 367                                        u_int8_t *               recPtr,
 368                                        u_int16_t                recSize,
 369                                        BlockDescriptor          *targetNode,
 370                                        u_int16_t                index,
 371                                        u_int16_t                level,
 372                                        Boolean                  replacingKey,
 373                                        u_int32_t                *insertNode );
 374
 375 OSStatus    DeleteTree                (BTreeControlBlockPtr     btreePtr,
 376                                        TreePathTable            treePathTable,
 377                                        BlockDescriptor          *targetNode,
 378                                        u_int16_t                index,
 379                                        u_int16_t                level );
 380
 381
 382 #endif /* lf_hfs_btrees_private_h */